Getting RSA 256 Bits Wrong

For the past month people have been asking me about the Crown Sterling announcement of a successful attack on RSA. The company first came to notice after they sued the Black Hat conference over the audience response to their announcement. They have since upped the ante and ‘demonstrated’ a live ‘attack’ on stage.

Bruce Schneier and others have tried to bat down this nonsense already. But like the Black Knight in Monty Python and the Holy Grail, Crown Sterling CEO Robert Grant is a man who refuses to admit he has been defeated. So I thought I would give a fuller explanation of the situation and why there is no need to panic.

The other thing I realized as I was writing this piece is that Schneier used his snake-oil warning signs for bogus cryptography to analyze this piece. But this isn’t just cryptography, it is cryptanalysis which means that there is a whole additional dimension of crazy.

1: The attack does not affect every public key algorithm

Reports of the original Black Hat talk, stated that the secret algorithm works by making it possible to predict prime numbers and that this allows ‘every form’ of public key cryptography to be broken.

This broad claim is not remotely true. While it is true that almost every public key cryptographic system involves the use of prime numbers, the only widely used public key encryption system which relies on the secrecy of a prime number is RSA.

The modular integer and elliptic curve variants of Diffie-Hellman involve the use of a prime number but that is a shared parameter which is agreed by all the participants in advance. The IRTF recently spent three years choosing two prime numbers to use for an elliptic curve algorithm. The numbers we chose are not secret, they are 2²⁵⁵-19 and 2⁴⁴⁸-2²²⁴-1.

Since the prime numbers we chose are not secret in the first place, an algorithm that allows Crown Sterling to guess prime numbers is not going to have any effect on the security of elliptic curve algorithms.

2: The WebPKI doesn’t run on RSA alone

If someone had discovered a way to break RSA in 2010, the world would be in very deep trouble. The cryptography that secures the entire global financial system would be at risk because a large part of the infrastructure only supported RSA cryptography. If RSA fell, the whole system would have fallen with it.

Fortunately, this situation was recognized well in advance and pretty much every Web browser and server has supported elliptic curve algorithms in addition to RSA. Moving from RSA to elliptic curves would still be costly but it is certainly achievable.

The reason this is important is that as an industry, we are if anything too aggressive in forcing transitions to new cryptographic algorithms. We took rather too long to transition from MD5 to SHA-1 but we moved away from SHA-1 faster than was absolutely necessary and broke things in the process. Caesar's wife must be above suspicion and so must the cryptography we use.

Currently, the shortest RSA keys permitted in the WebPKI are 2048 bits which present a work factor of approximately 2⁹⁵ bits against the best known attack. The largest RSA key that has been broken today is 768 bits which has a work factor of about 2⁶³. I suspect that all it will take to begin the process of decommissioning RSA is for someone to break a 1024 bit key. 2048 bits is approximately four million times harder to break than 1024 bits but I suspect that would be too little for comfort. We are very conservative with respect to choice of algorithms.

The point is that as an industry, we have given ourselves options precisely so that we do not face a situation where RSA is broken and we have nothing to replace it with. We are currently spending a great deal of time and effort trying to work out what our response would be if a quantum computer of sufficient size to break public key cryptosystems could be built even though it is highly unlikely that this will happen for at least a decade.

3: There is a challenge problem, Crown Sterling ignored it.

After Ron Rivest, the R in RSA got fed up of constantly being told of ‘new’ approaches to factoring, he persuaded RSA Labs to set up a challenge competition with cash prizes for factoring numbers. The cash prizes were withdrawn some years ago but people still try factoring the numbers for fame and glory.

Crown Sterling claim that they cannot prove that their scheme works because revealing how it works would allow people how to bring down the world financial system. But they don’t need to show me how it works to prove that they can break larger RSA keys than was previously possible. All they need to do that is to factor this number:

RSA-1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

This is really a case of put up or shut up. If you want to convince me that you can factor RSA keys, then factor at least one of the RSA challenge keys that have been sitting out there waiting to be solved for a quarter century. If you can’t or won’t do that, you are an obvious fraud and haven’t earned the right to be given time of day let alone a hearing for your scheme.

4. Breaking a 256 bit RSA key is a trivial problem

Modern cryptography uses two types of encryption algorithm, symmetric algorithms in which the encryption and decryption keys are the same and asymmetric algorithms in which different keys are used. Using different keys for different roles allows those roles to be separated. Public key encryption is interesting because anyone can encrypt a message using the public key but only a person who knows the private key can decrypt.

The work factor of a cryptographic algorithm is a measure of how difficult it is to break. These are traditionally specified in terms of powers of two. An algorithm that has a work factor of 2⁶⁵ is twice as difficult to break as one that has a work factor of 2⁶⁴.

For reasons I will get to shortly, the work factors we use in most commercial cryptography are 2¹²⁸ and 2²⁵⁶.

For a symmetric algorithm, the work factor and the key size are almost always the same (if not, it is a bad algorithm) and so the two key sizes typically used are 128 bits and 256 bits.

And here we have one of the many slights of hand used in the Crown Sterling PR assault because if 256 bit AES is as secure as we believe it to be, it presents a work factor of 2²⁵⁶ operations which is a really big number. A planet sized computer operating at the fastest possible speed for the life of the universe wouldn’t even begin to come close to breaking it. But 256 bit RSA does not present a work factor of 2²⁵⁶, it presents a work factor of less than 2⁴⁰. Not only is RSA 256 not secure today, it never was.

The very shortest RSA key that has ever been used in commercial cryptography* is 1000 bits which presents a work factor of (roughly) 2⁷⁰. Which means a difference in difficulty of 2³⁰. What does that mean in practice?

Remember the chess board story in which the inventor is paid one grain of rice for the first square, double that for the second and so on? By the time we reach the 33rd square and the second half of the board, the price is a 20 ton lorry load of rice and by the time we get to the last square, the cost is a mountain of grain the size of Mount Everest. The RSA 256 work factor, 2⁴⁰ means 256 lorry loads of rice, a lot to be sure but probably no more than some farms produce in a year. 2⁷⁰ is 64 Mount Everests of rice.

The 2048 bit keys that are the shortest used today present a work factor of 2⁹⁵ which is a mountain of rice about the size of the planet earth.

The Crown Sterling attack was laughed at because the attack they demonstrated was against a system roughly thirty million billion times easier than the real thing. And that number isn’t an exaggeration, its the value of 2⁵⁵.

[* After this was first published, someone pointed out that 512 or 768 bit RSA moduli were in fact used in some EDIFACT applications.]

5. The attack described is significantly worse than existing attacks.

What Crown Sterling claim to have discovered is some sort of structure in the distribution of primes that allows them to predict them. As mathematical claims go, this is neither astonishing nor remarkable. There are many known patterns in prime numbers. It would be rather surprising if there weren’t. For a start, all even numbers apart from 2 are not prime.

But let us leave aside the gobbledygook and assume that the claim made is correct and Crown Sterling have discovered some function that would allow what amounts to an enumeration of the prime numbers. Could that be used to improve factoring of RSA keys?

Let us assume that they have discovered a function f(n) which returns the nth prime number with negligible computational effort. In making this assumption we are not of course suggesting that they have done anything of the sort, we are merely looking to see if that might help in factoring.

For large values of N, the probability that it is prime is approximately 1/ln(N). If N = 2¹⁰²⁴, the probability N is prime is approximately 1/710. Which means that the work factor of a factoring algorithm based on prime prediction would be 2¹⁰²⁴/710 or approximately 2¹⁰¹⁴. And that is assuming that this prime prediction mechanism takes no effort at all. That is 2⁹¹⁹ or approximately 10²⁷⁶ worse. And remember that the number 10¹⁰⁰ is so large that Google is named after it.

In summary

In his first piece on Crown Sterling, Schneier showed that every aspect of the presentation set off his ‘snake oil’ detector. Now that we can take a deeper look, it shows that the snake oil detector was right. At this point it is really hard to see how Crown Sterling’s claims could be made in good faith.

But even thought this case is obvious nonsense, it is probably worth our while to put some serious effort into explaining to the public what does and does not constitute a serious threat to the security of public key cryptography. Because it is not just improvements in mathematics that provide a fertile ground for hucksters. Some of the claims made with respect to quantum computers are less than candid.