Crypto Column

^{BY DR. SCOTT VANSTONE}

There has been much discussion lately about RSA public key sizes for a number of reasons. Those who are reluctant to migrate from 1024-bit RSA to the larger keys sizes defend these RSA keys by arguing that they are strong enough for the foreseeable future and that they don’t want to increase costs. These arguments are being called into question.

Many security deployments implement the 1024-bit RSA for key transport because it’s relatively easy to get an X.509 digital certificate that uses 1024-bit RSA from a number of commercial certificate providers. This is a very dangerous approach because the security of the public key system must be matched with the symmetric cipher used. NIST mandates it and it’s only common sense. We know that 1024-bit RSA does not match the 128-bit security level now used for symmetric ciphers as the two recent examples outlined below demonstrate.

First, research published this past February by Adi Shamir, the “S” in RSA, raises new concerns about the security of 1024-bit RSA. His paper describes a new hardware implementation for factoring that makes it 3 to 4 orders more cost-effective than previous designs. He estimates the factoring for 512-bit RSA can be completed in 10 minutes by a $10K device and 1024-bit RSA in less than 1 year with a $10M device. It sounds like a lot of money, but since every secure e-commerce server on the planet uses 1024-bit RSA (in SSL/TLS), the investment may be a good one for certain parties.

The second is highlighted by Microsoft’s concern with RSA key size when they built the Xbox. They chose to install a 2,048-bit RSA key to prevent the user from running executables that have not been authorized by Microsoft. Despite little chance of success, a group of hackers started the Neo Project that uses distributed computing techniques (similar to the Seti@Home project) to recover the secret key.

The Neo Project software is now running on thousands of idle PC resources to try to guess the 2,048-bit encryption key used by the Xbox, a brute force approach that will likely never yield the result. While a brute force attack may be fun to watch, Shamir is on the right track by using mathematics to improve the likelihood of recovering the key.

The bottom line is that implementers should not be complacent with 1024-bit RSA as it may be practically broken sooner than you think. Security systems need to be designed to have a reasonable lifetime in the field.

We know many organizations understand this when looking at symmetric ciphers as they are moving from 3DES to AES, even if they only moved from DES a couple of years ago. However, when making this move to 128-bit AES, you need to use a matching public key scheme that demands 3072-bit RSA or 256-bit ECC. As you can see in this issue, there are tradeoffs in efficiency when making this decision. The important thing to remember is to not compromise the security of the system and to address these performance issues.