[tor-dev] Subject: Re: The consequences of key compromise (or the reasons for changing)

[Jon Callas]

On Nov 4, 2011, at 12:14 AM, Markku-Juhani O. Saarinen wrote:

> 
> From: Jon Callas <joncallas at me.com>
> 
>> People should get off of 80-bit crypto as soon as is reasonably possible. This means RSA 1024, SHA-1, etc. NIST recommended doing this by the end of 2010, but are now holding their nose and saying that 2013 is the real new date.
> 
> Absolutely agree. The 80-bit figure was apparently adopted by U.S.
> Government some 25+ years ago (skipjack etc).

Yeah, Skipjack is one of the others in the suite, but we civilians don't use it. We're pretty good at 128-bit crypto on the symmetric side. However, the other major thing to remember is that a block size of 64 bits also is an issue. There are birthday-bounds problems for objects of size around the size of a Blu-Ray disk.

> 
>> This seems basically reasonable to me. No one has yet factored a 768-bit number, let alone a 1K one. 
> 
> 768-bit RSA was factored in 2009 and the authors of that paper
> conjecture that 1024 bits would be factored "within a decade" and
> recommend that 1024-bit RSA should be phased out within a couple of
> years. http://eprint.iacr.org/2010/006.pdf
> 
> I am certainly doing that with the stuff that I am maintaining.

It was a special-form number, though. It wasn't a general-case one. I didn't go into details because we should all be getting off 1024. In many cases, jumping to 2K-bit keys works fine. In others, it doesn't.

> 
>> SHA-1 actually looks safer today than it did in 2005. But still. Moving away is a Good Thing, so long as it doesn't make you do something stupid.
> 
> Well, after the 2005 Wang-Yin-Yu paper which had a 2^69 attack, there
> was a claimed 2^52 attack in 2009 which turned out to have a flawed cost
> evaluation. There has also been talk of a 2^63 attack, but that
> difference can be put down to attack implementation skill and detail.

I'll repeat what I said after the 2^52 paper: 2^52 *whats*? It matters. 2^52 seconds is still a large number, and smaller than  (but near to) 2^80 clock cycles. I've never gotten a good answer to that.

But -- I was recommending "walk, do not run to the exit" in 2005. NIST wanted people off of it by 2010. My comment is at best a left-handed compliment.


> 
> I was always doubtful whether or not those techniques could be expanded
> to work against the SHA-2 algorithms. 

Me too, but there were people who were sure of it in 2004-2005.

> 
> It is also funny that many people talk about SHA-2 as if was a single
> algorithm; there are actually two quite distinct algorithms, one for
> (now fading) 32-bit architectures (SHA-224,SHA-256) and one for 64-bit
> algorithms (SHA-384,SHA-512,SHA-512/224,SHA-512/256). The variants of
> these two algorithms only differ in the number of output bits and the IV
> values and hence have a constant speed regardless of their digest size.
> You can run "openssl speed sha" to see a real-world performance
> comparison on a particular box.


You are, of course, correct.

I try to call out SHA-256 and SHA-512, but sometimes it's simpler to call them SHA-2, especially since NIST does.

	Jon