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?

  • 8
    $\begingroup$ That article is misrepresenting the result from 2010. They used side-channel attacks to recover a private key, not factor a modulus. $\endgroup$
    – pg1989
    Oct 1, 2013 at 18:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – user4982
    Oct 1, 2013 at 19:08
  • $\begingroup$ as @pg1989 said, the quote is misleading. 1024 bits RSA integers have so far not been factored in public. $\endgroup$ Jul 18, 2016 at 20:59
  • 1
    $\begingroup$ @David天宇Wong Yeah, I quickly realized that too then in 2013 when I asked the question. It also quickly dawned upon me that it wasn’t even the same kind of key I was comparing there. All in all, I guess you could call this “one of my oldschool self-facepalm moments” which I probably would have killed a long time ago… if it weren’t for @Pornin’s superb answer which might (or might not) help others in one way or another. $\endgroup$
    – e-sushi
    Jul 18, 2016 at 21:13

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

  • 1
    $\begingroup$ 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. $\endgroup$
    – user4982
    Oct 1, 2013 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.