Breaking SSL (Again)

Another encryption land mark was reached towards the end of last year with the factorization of RSA-768. To put this is simpler terms, RSA-768 is a 768 binary bit number (232 digits in decimal) which is the product of two prime numbers, usually denoted as p and q. It forms part of the public and private keys used in TLS/SSL encryption most commonly used for securing internet traffic. If you can determine p and q from the public key, i.e. factor the RSA-768 number, then you can also calculate the private key and hence “crack” the encryption. It sounds easy, but try to factor the number 6947 into its prime factors? (See below for answer). Now try doing that with a 232 digit number.

Although some mathematics was used, notably the General Number Field Sieve, the attack was still effectively a brute force effort spread out over hundreds of processors and took over two and a half years. If the effort were repeated for a different 768 bit number, the experience would surely result in finding the solution in a shorter time. However it’s not clear if the result from the first test can be reused for a different number and I suspect not, meaning that an attack against a 768 bit key is still theoretical other than for the most critical of data.

One of the conclusions of the study was that 1024 bit keys although safe today should be phased out in the next 3 to 4 years and replaced with 2048 bit keys. A quick unscientific survey of certificates used on some of the more popular web sites suggests that 1024 bits is more or less ubiquitous, although there are some 2048 bit certificates out there. It is possible that some older browsers would not support the longer keys, but no one is flagging this as an issue.

For me, the most interesting part of the study was how the researchers concentrated on introducing parallelism into their algorithms to allow the load to be spread over multiple systems. This of course leads on to one thinking that a cloud setup such as Amazon’s EC2 could eventually be used for such tasks rather than private academic systems .

(89,73)