I frequently get asked to consult on building out new Public Key Infrastructures here in Premier Field Engineering. One of the things that I get asked commonly is “How do I choose a key length and Hash Algorithm?”. That’s a complex question, that generally is difficult to answer, but I thought I might collect “Some Thoughts” on that and put them in a single place.

First, some current background

There is a subtle kind of arms race going on – encryption and hash algorithms are always going to be subject to increasingly sophisticated attacks. CPU’s get faster and faster, making brute force attacks against encryption easier and easier, requiring longer keys. We recently released a security update that by default disallows RSA keys of less than 1024 bits in length. Kurt Hudson documented that here:

http://blogs.technet.com/b/pki/archive/2012/06/12/rsa-keys-under-1024-bits-are-blocked.aspx

Mathematicians and hackers work to manipulate hash algorithms in order to create collision attacks, like the one used by the Flame Malware:

http://blogs.technet.com/b/srd/archive/2012/06/06/more-information-about-the-digital-certificates-used-to-sign-the-flame-malware.aspx

So when choosing hash algorithms and key lengths, one needs to take into account the current landscape. You need to do a little bit of research on how hash algorithms are currently standing up to collision attacks and what key lengths are acceptable.

One of the key indicators here that I frequently refer to is the Certificate Policy for the U.S. Federal PKI:

Section 1.4.1 states that

The use of SHA-1 to create digital signatures is deprecated beginning January 1, 2011. As such, use of SHA-1 certificates issued under this policy should be limited to applications for which the risks associated with the use of a deprecated cryptographic algorithm have been deemed acceptable.

And section 6.1.5 states

Trusted Certificates that expire before January 1, 2031 shall contain subject public keys of 2048 or 3072 bits for RSA or 256 or 384 bits for elliptic curve, and be signed with the corresponding private key. Trusted Certificates that expire on or after January 1, 2031 shall contain subject public keys of 3072 bits for RSA or 256 or 384 bits for elliptic curve, and be signed with the corresponding private key.

This provides an excellent starting point for choosing a hash algorithm, and key lengths for RSA or ECC algorithms for public/private key pairs. Additionally, the Microsoft Root Certificate Update Program contains some excellent verbiage that closely corresponds:

“we require a minimum crypto key size of RSA 2048-bit modulus for any root and all issuing CAs. Microsoft will no longer accept root certificates with RSA 1024-bit modulus of any expiration. We prefer that new roots are valid for at least 8 years from date of submission but expire before the year 2030, especially if they have a 2048-bit RSA modulus.”

Now, some history

There are a large number of clients that cannot understand anything greater than a 2048 bit key length, or hash algorithms more current than SHA-1. For example, Windows Server 2003 offers limited support for the SHA2 hash algorithms:

948963 An update is available to adds support for the TLS_RSA_WITH_AES_128_CBC_SHA AES128-SHA and the TLS_RSA_WITH_AES_256_CBC_SHA AES256-SHA AES cipher suites in Windows Server 2003
http://support.microsoft.com/kb/948963/EN-US

and

968730 Windows Server 2003 and Windows XP clients cannot obtain certificates from a Windows Server 2008-based certification authority (CA) if the CA is configured to use SHA2 256 or higher encryption
http://support.microsoft.com/kb/968730/EN-US

document that level of support. So in addition to thinking about the future, you’ve got to consider the past when building out a hierarchy. One of the hierarchies I helped build had a 2048 bit key for a Root Certificate primarily because of the requirement to support legacy operating systems and devices.

And finally a Recommendation

If you absolutely must support legacy applications that don’t understand CNG algorithms, and are building out a new public key infrastructure, my advice today is to build two hierarchies. The first hierarchy – a legacy hierarchy if you will – would have a lower key lifetime aimed at a documented point at which legacy applications and devices MUST support CNG algorithms. You could issue certificates based on this “lower assurance” hierarchy for a limited time only to legacy clients, perhaps with limited EKUs and a specific Certificate Policy attached to it. The second PKI would be erected with more current algorithms and key lengths to support more current clients and with much longer expiry periods. When building that PKI, you could follow the stronger guidance put forth in the Federal CP and choose SHA-256, or SHA-384 along with RSA Keys of 4096 bits or ECC keys of 256 or 384 bits. I agree that this adds complexity, but I find in the IT industry that we’re constantly dragging older applications and devices into a new security world – often, kicking and screaming the entire way.

 

-Rick Sasser

 

References:

A.Sotirov, M.Stevens, J.Applebaum, A.Lenstra, D.Molnar, D.A. Osvik, B. de Weger, “MD5 considered harmful today”, http://www.win.tue.nl/hashclash/rogue-ca/, Dec.30, 2008.

Microsoft Root Certificate Update Program, http://technet.microsoft.com/en-us/library/cc751157.aspx