The difference between security done right and not quite right can make what is theoretically secure into something that is practically crackable. New results demonstrate how falling back to a small encryption key can make the data readable by almost anyone with the need - this is the LOGJAM vulnerability. But given enough resources can state agencies break 1024 bit keys?

This is news but almost as important is that with sufficient resources even large keys can be broken and it is suggested that the NSA does this on a regular basis. 

The LOGJAM vulnerability stems from the USA restriction on selling encryption software that worked with more than 512 bit keys to the world so that the codes could be broken. This restriction was abandoned ages ago but encryption software like TLS still had, and still has to, cope with software that cannot work at more than 512 bits. As a result many still have fallback protocols.  

First we need a little theory to understand how the Diffie-Hellman-Merkle DHM key exchange protocol works. DHM was the first protocol that allowed two parties to securely exchange an encryption key over an open network.  

Before read on consider how amazing the DHM protocol is. How can you possibly transfer a secret number over on open connection such that the number is only known to the sender and receiver?

The answer is very clever. 

Alice and Bob agree on a large prime p and a number g - they can do this in public or in secret it doesn't make a lot of difference. 

Next Alice picks a number a and sends g^a mod p to Bob. 

Bob picks a number b and sends g^b mod p to Alice. 

Again both values can be transmitted over the public internet but Alice must keep a secret and Bob must keep b secret. 

Now Alice computes (g^b)^a mod p - recall that only Alice knows a.

Bob computes (g^a)^b mod p - and again only Bob knows b. 

Of course (g^a)^b mod p= (g^b)^a mod p= g^ab mod p  and so Alice and Bob have the same result - the encryption key. 

The reason only Alice and Bob have the encryption key is that the outside world only knows the values of  g^a mod p and g^b mod p and there is no direct way to use these to form g^ab mod p. If you multiply them together you get g^a+b mod p.

The only way you can form g^ab mod p is to deduce either a or b and this means solving:

v=g^a mod p

to find a.

This is the discrete log problem and there is no known fast way of doing it other than by guessing values of a and seeing if they give you the value v. If you had an inverse function i.e. log then the solution would simply be a=log_gv mod p.

The whole security of the DHM key exchange depends on the difficulty of computing the discrete logarithm and despite some progress in speeding things up it is still thought to be a problem that requires time that is exponential in the number of bits. 

Now we come to the failure of implementation that was promised in the introduction. Information suggests that the NSA has a project to read encrypted data. Could it be they are using a quantum computer or could they have solved the discrete logarithm problem? 

The latest results suggest a much simpler, theoretically simpler, solution. 

The first surprise is that most DHM systems make use of a small number of primes for p. This shouldn't make any difference because the protocol allows p to be known and the discrete log problem is just as hard as long as the prime is large. However let's suppose that only one prime was in use then you could compute a complete table for the discrete log and simply use a lookup to find a or b. Of course you can do better than brute force computation, but this is the basic idea. 

For a 512-bit key the computation of the table is possible with just a few thousand cores. The researchers did the job in 7 days and the resulting 2.5GB lookup table can find a discrete log in just 90s using a 24 core machine. This means that 512 bit keys can be cracked by almost anyone with access to a compute cluster. 

The LOGJAM procedure is a man-in-the-middle attack that first forces the server to downgrade to 512 bits, then it stalls for 12 seconds while it works out the session key. From this point on the man-in-the-middle can intercept all communication and even modify it. 

Of course, the reaction to all of this is to upgrade to 1024-bit encryption but the research suggests that an agency with state-level resources could crack even this. It is estimated that it would take 45M core years to compile the table for a 1024-bit key. This sounds huge, but with special hardware a facility costing a few hundred million dollars could create the table in about one year. Once the terabyte size table had been constructed, looking up the discrete log could be done in a few minutes using a supercomputer. 

All of these estimates are based on known algorithms and techniques. It is likely that a state agency could find theoreticians to work on the problem and make the methods more efficient. 

The solution to the problem is to either increase the key size - 2048 bits would make the computation of the table beyond the reach of even a state agency without some major theoretical breakthrough, or to stop using the same prime numbers. Generating huge primes is expensive, but working with a bigger library of primes would make the construction of the tables more difficult. 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info