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

Question

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 the year 2013.

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?

Answer 1

That's not the same kind of key.

Symmetric keys are a bunch of bits, such that any sequence of bits of the right size is a possible key. Such keys are subject to brute force attacks, with a cost of $2^n$ for an $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 an 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 is also 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 an $n$-bit prime has a cost that is roughly similar to the cost of factoring an $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 that fits in fewer bits for a given security level. Basically, you get "$n$-bit security" (resistance similar to that of an $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 that can be estimated depending on the function output size (assuming that the function is "perfect"). For a hash function with an $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, these NIST recommendations illustrate their point of view:

• 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.