- November 04, 2015
- Suggested Reading
A group of researchers reconsidered the cost of attacking a security protocol used by so many programs and web sites that it could now be worth it for state actors to invest. This note gives pointers that will allow readers to make their minds.
The Diffie-Hellman protocol
Diffie-Hellman (DH) is a cryptographic protocol used a.o by VPN, SSH, and HTTPS clients and servers to negotiate secret session keys. One of the parameters of the protocol is a large prime number. These parameters are public, and need to be agreed on by both client and server. The security of the protocol relies on the difficulty to compute a discrete logarithm, which is similar in complexity to factoring very large numbers.
Documents called RFCs are used to make interoperability between various client and server implementations possible. RFC3526 gives recommendations for DH key exchange.
WeakDH, or: Imperfect forward secrecy
There is a well-known attack on DH: knowing the parameters, it is possible to perform pre-computations that are valid for all uses of these parameters. This pre-computation gives a huge table of integers, called a number field sieve. Individual sessions can then be cracked by using the result of these pre-computations with comparatively few resources. Until now, this kind of attack was deemed too expensive to perform.
A team of 14 researchers published a paper describing practical attacks against DH as commonly implemented. Without getting into the mathematics details the attack leverages a weakness of the standards and advances in computing power:
- The RFC defines a small number of groups of parameters. For each key size, a single prime number is defined.
- Discrete logarithm is a problem that easily lends itself to parallel computing. An attacker can use a large number of specialised computing nodes to perform pre-computation that will serve as basis for the decryption of individual traffic.
The result of their research shows that computing the sieve for one prime for the 1024 bit version of the protocol would cost "a few hundred million dollars", and would take about one year.
While this is a huge amount of money, it is within the reach of at least one state actor, provided the returns are worth it. Thanks to the small number of primes used, this may be the case: two members of the research team mention that cracking just one prime would allow to decrypt the traffic for two thirds of VPNs and one fourth of SSH servers. Another prime would yield 20% of the HTTPS web sites.
ArsTechnica gives a description of the attack, and comes to an "unsettling conclusion". Robert Graham put things in perspective by comparing the pre-computing to bitcoin mining: Graham concluded that cracking one prime for 1024-bit DH is equivalent to two and a half hours of global bitcoin-mining.
Steve Bellovin shows that the results are not surprising, and that expressing outrage at nation states exploiting them is wrong.
Protection will come from abandoning the weaker versions of the protocol. The IETF is working on improving its standards.
About "Suggested Reading" from ENISA
With the “Suggested Reading” series ENISA aims at giving the interested reader guidance on controversial and inscrutable NIS related discussions that are carried out in Media, by suggesting selected pre-reviewed articles that in our view explain the issue at hand and related circumstances in a reasonable and understandable manner. This view is derived from past experiences and common sense; in no way should “Suggested Reading” be understood as recommended course of action in a specific incident or investigation, or being a final conclusion. Feel free to get in touch with ENISA to discuss or inquire more information to the “Suggested Reading” series (email@example.com).