Algorithm and Key Length Deprecation

Dan Kaminsky posted on twitter the following:

http://eprint.iacr.org/2010/006.pdf Is it time to deprecate 1024bit RSA for, say, 1276bit? (2048 has perf issues.)

The link Dan provided is a research paper which reports the successful factorization of the 768-bit number from the original 2001 RSA challenge. I responded to him that NIST had already deprecated the use of 1024-bit RSA in the government, and it was time for industry to follow suit. Since I posted that, I’ve been surprised that a number of people don’t understand the upcoming changes in key lengths and algorithm strengths that have been mandated by NIST. So, this post offers some information about why I can confidently say the U.S. government has deprecated certain algorithms and key lengths.

What is being deprecated?

• Hashing: 160-bit SHA-1 (note: MD4/MD5 was never an “acceptable algorithm” to the government, and should already be deprecated)
• Signatures: 1024-bit DSA, 1024-bit RSA, 160-bit ECDSA
• Encryption: 80/112-bit 2TDEA (two key triple DES)

When are they deprecated?

• Hashing: for all hashes generated after 12/31/2010
• Signatures: for all signatures generated after 12/31/2010
• Encryption: for any information that needs to remain confidential after 12/31/2010

Where does it say they are deprecated?
While a little more complicated, there is a direct chain of requirements and documents which point to this. The government has unfortunately not made this as obvious and direct as it should be in order to get the maximum buy-in and cooperation from industry. This post is my attempt to help put the pieces together.

• FIPS 200, Minimum Security Requirements for Federal Information and Information Systems requires “Federal agencies must meet the minimum security requirements as defined herein through the use of the security controls in accordance with NIST Special Publication 800-53, Recommended Security Controls for Federal Information Systems, as amended.”
• NIST Special Publication 800-53, Recommended Security Controls for Federal Information Systems, indicates that information systems which need to protect information using cryptography must “produce, control, and distribute symmetric cryptographic keys using [Selection: NIST-approved, NSA-approved] key management technology and processes” and references NIST Special Publication 800-57.
• Section 5.6 of NIST Special Publication 800-57 Part 1, Recommendation for Key Management contains Table 4 indicating the above deprecations I list.

So, here’s the bottom line: 1024-bit algorithms and SHA-1 shouldn’t be used after the end of this year. The government has mandated it, and industry should follow along. It is time — perhaps well past time — to start testing your cryptographic systems, applications, and tools with 2048-bit keys and SHA-2.