Saturday, May 23, 2015

Precomputation renders Diffie-Hellman vulnerable...

Precomputation renders Diffie-Hellman vulnerable...  The Diffie-Hellman key exchange algorithm is at the heart of a great many cryptographic systems, including those that you likely use every single day.  News that it may be vulnerable isn't exactly comforting, even when that vulnerability costs hundreds of millions of dollars to exploit.  That cost is only going to go down, too.  Today only a major state actor (like, say, the NSA or FAPSI) could afford this, but that could change relatively quickly.

The new attack is enabled by the use of an enormous table of precomputed partial results for a particular prime number used in the Diffie-Hellman scheme.  The details aren't important to understanding the vulnerability.  The key is that you need one of these tables for each possible prime number being used – and that most Diffie-Hellman implementations use one of a very few number of such primes.

There are three main mitigations available, but both are going to be challenging to roll out.  One mitigation is to use longer keys (this always seems to be the mitigation for a vulnerability!).  Another is to stop using the magic few prime numbers, and switch to using frequently generated prime numbers. The last is to quit using classical Diffie-Hellman. 

It will be interesting to watch how the world reacts to this.

Much more technical information in the original paper, and here, here, and here...

No comments:

Post a Comment