When NIST disallows the use of 1024-bit keys, what effect will that have on SHA-3 (with max. 512 bits)?

Quoting the article Gone in 60 Months or Less:

The National Institute of Standards and Technology (NIST) has disallowed the use of 1024-bit keys after 31 December 2013 because they are insecure. Rapid advances in computational power and cloud computing make it easy for cybercriminals to break 1024-bit keys. When a researcher from Ecole Polytechnique Fédérale de Lausanne (EPFL) in Switzerland cracked a 700-bit RSA key in 2007, he estimated that 1024-bit key lengths would be exploitable 5 to 10 years from then. Not even three years later, in 2010, researchers cracked a 1024-bit RSA key.

So, we're talking about a 512-bit "cryptographically secure" hash meeting cipher implementations where 1024-bit keys are not disallowed anymore by the end of this year.

What does that mean for SHA-3, as the NIST submission sets the rate $r$ as 1152, 1088, 832, or 576 (144, 136, 104 and 72 bytes) for 224, 256, 384 and 512-bit hash sizes, respectively? Can we still think about using SHA-3 to hash passwords to the desired bit-length and comply to NIST rules on the long run, or do we need to expect NIST gradually starting to enforce that 1024-bit key rule across all protocols?

-
1024-bit RSA keys have nothing to do with 512-bit hash algorithms. –  Stephen Touset Oct 1 '13 at 18:53
That article is misrepresenting the result from 2010. They used side-channel attacks to recover a private key, not factor a modulus. –  pg1989 Oct 1 '13 at 18:55
Originally NIST was intending to disallow 1024-bit keys back in 2010. Discussion between NIST and other government agencies found out that it is not viable alternative from cost perspective and that the agencies are not currently ready. NIST decided to postpone transition until 2013, and it is due soon. The transition affects many other algorithms as well, like DSA, ECDSA, ... Read SP 800-131A for details. The SHA-3 has next to nothing to do with this, except that SHA-1 is get deprecated. But, SHA-2 already exists and is ok. –  user4982 Oct 1 '13 at 19:08

That's not the same kind of key.

Symmetric keys are bunch of bits, such that any sequence of bits of the right size is a possible keys. Such keys are subject to brute force attacks, with cost $2^n$ for a $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect" then enumerating all possible keys is the most efficient attack (i.e., "no shortcut").

RSA keys are mathematical objects with a lot of internal structure. In a 1024-bit RSA key, there is a 1024-bit integer value, called the modulus: this is a big integer whose value lies between $2^{1023}$ and $2^{1024}$. To break a RSA key, you "just" have to factor this modulus into its prime factors. There are relatively efficient algorithms for that, to the extent that factoring a 1024-bit RSA modulus is on the verge of the feasible. It has been estimated that the "cost" of factoring a 1024-bit RSA modulus is similar to the "cost" of brute-forcing a 77-bit symmetric key. Note that this is not the same kind of cost (you need a lot of fast RAM for factoring big integers, whereas enumerating many AES keys requires no RAM at all).

DSA and Diffie-Hellman keys are also mathematical objects, with again a lot of internal structure. There again, there is a modulus, but a prime one, so it is not about factorization, but something else, called discrete logarithm. It so happens that breaking discrete logarithm modulo a $n$-bit prime has a cost which is roughly similar to the cost of factoring a $n$-bit RSA modulus (the DL cost is in fact a bit higher). So a 1024-bit DSA or DH key is also similar in strength to a 77-bit symmetric key (or maybe an 80-bit symmetric key).

Elliptic curve cryptography yet again uses mathematical objects as keys, but with another structure which fits in less bits for a given security level. Basically, you get "$n$-bit security" (resistance similar to that of a $n$-bit symmetric key) with a $2n$-bit curve.

Hash functions have no keys. Yet there is a concept of resistance to various attacks (collisions, preimages, second preimages...) with costs which can be estimated depending on the function output size (assuming that the function is "perfect"). For a hash function with a $n$-bit output size, resistance to collisions is in $2^{n/2}$, resistance to preimages (and second preimages) is in $2^n$. (There are ongoing discussions about making SHA-3 faster by relaxing this latter value, i.e. having "only" 128-bit security against preimages with a 256-bit output length.)

See this site for lots of data on comparative strength estimates. In particular the NIST recommendations which illustrate the point of view of NIST, which says that:

• 1024-bit RSA/DSA/DH and 160-bit ECC are "as good" as an 80-bit symmetric key.
• 2048-bit RSA/DSA/DH and 224-bit ECC are "as good" as a 112-bit symmetric key.
• 3072-bit RSA/DSA/DH and 256-bit ECC are "as good" as a 128-bit symmetric key.
• 7680-bit RSA/DSA/DH and 384-bit ECC are "as good" as a 192-bit symmetric key.
• 15360-bit RSA/DSA/DH and 512-bit ECC are "as good" as a 256-bit symmetric key.

NIST also says that the "80-bit" security level should be shunned except when mandated for interoperability with legacy systems.

These five formal "security levels" are the reason why AES was defined with three key sizes (128, 192 and 256 bits -- the two lower levels mapping to 2DES and 3DES), and SHA-2 with four output sizes (SHA-224, SHA-256, SHA-384 and SHA-512, the "80-bit" level being used for SHA-1); and, similarly, SHA-3 is (was) meant to offer the four output sizes 224, 256, 384 and 512 bits.

-
Thanks for the time and effort you've put in your reply. The insights you're providing are more than appreciated! –  e-sushi Oct 1 '13 at 19:19
Thomas: Very good answer. BTW, the expert opinions on effect of memory cost in context of RSA or DH (bit length range 2550 - 3200 depending on source has been suggested to match a perfect 128-bit cipher). And then there is hypothetical quantum computer. –  user4982 Oct 1 '13 at 19:37