Special prime numbers help passively listen to the Diffie-Hellman key exchange protocol.

Slide from ANB presentation

In 2013, thanks to Edward Snowden, NSA documents appeared in the media. Among them - zamylenny slide from the presentation, which pointed to the possibility of the NSA to decrypt VPN traffic. The NSA had no reason to lie in a secret presentation, so the experts took this information as evidence of some fundamental vulnerability in modern public key cryptography systems.

Fundamentals of cryptography and implementation of algorithms revised again. Soon came the first assumptions . The most likely of these was that the fundamental vulnerability is hidden in the practical implementation of the Diffie-Hellman protocol . Specifically, the implementation of the protocol recommended by the DSA standard encourages users not to calculate the unique large modules p when generating keys, but to use standard numbers.

For example, here is the recommended prime number in RFC 2409 .
')


This is how it turned out in practice: until recently, 92% of the most popular HTTPS sites from the Alexa list used two standard prime numbers . Diffie-Hellman protocol is also used to generate keys that are used in the SSH, VPN, SMTPS, IPsec and other protocols.

These numbers were considered safe with a sufficiently large value of a prime number. Now, experts from the University of Pennsylvania (USA), INRIA, CNRS and the University of Lorraine (France) have managed to prove that not all such numbers are safe, so the NSA does have a theoretical possibility of decrypting HTTPS traffic. In practice, cryptographers have demonstrated that a specially designed large prime number, when used as a p module in the generation of encryption keys, can act as a “trapdoor” that allows you to learn other secret key components and, as a result, decrypt the secret message.

Generally speaking, the ability of large groups of users to use a standard prime number as a p module evoked instant criticism from experts immediately after the publication of the Digital Signature Algorithm (DSA) standard in 1991, which provided for such a possibility and, in fact, encouraged this practice.

DSA is a cryptographic algorithm using the public key to create an electronic signature. The signature is created secretly, but can be publicly verified. The algorithm is based on the computational complexity of taking logarithms in finite fields, that is, the discrete logarithm.

The classic DSA-based cryptographic scheme is the Diffie-Hellman common key generation scheme. Its cryptographic strength is based on the supposedly high computational complexity of converting an exponential function. As specialists assumed, the algorithms for computing the discrete logarithm have a very high complexity, which is comparable to the complexity of the fastest factorization algorithms.

It turns out that this is not true. As cryptographers have shown, with a certain number p for a 1024-bit key, it is possible to calculate the discrete logarithm in a quite observable time - namely, 10,000 faster than theoretically calculated for random primes. Researchers did this in two months on a cluster of approximately 3000 processor cores in the university network (the actual number of machines changed as the task progressed).



The only question is whether “standard” prime numbers are such “loopholes” and where they came from. It is theoretically possible that the pre-calculations and the compilation of primes involved the attackers. And then we understand what the statement of the NSA about the possibility of decrypting "trillions of encrypted connections" means. With the computing power in the NSA's data centers, deciphering messages will take them orders of magnitude less than two months.

The possibility of introducing a specially selected module p into a standard does not mean that the NSA really implemented this idea. We cannot verify whether the prime numbers currently used are “good” or “bad” without knowing the algorithm that the NSA uses. But if this is true, then this will not be the first attempt by the NSA to weaken public encryption standards. The story of the “random” number generator Dual_EC_DRBG - RNG by default in RSA BSAFE and Data Protection Manager, among other programs, has not yet been erased from memory. As shown by the documents of Snowden, this generator was originally designed with the participation of the NSA to give predictable numbers.

To protect against potential “loopholes” through specially selected prime numbers, the DSA provided the ability to select primes in a “virtually random” way, with the publication of a pseudo-random "seed value". But practically no one uses this opportunity now. As already mentioned, the absolute majority of sites generate keys with standard prime numbers proposed in documents for general use.

The simplest protection against possible vulnerabilities in the encryption algorithm is the choice of keys longer than 1024 bits, the authors say. According to their calculations, the calculation for a 2048-bit key with the same "weakened" prime will take about 16 million times longer than for a 1024-bit key. According to the SSL Pulse survey , now, 27.3% of sites using SSL exchange keys of 1024 bits or less.

In the future, researchers believe, for safety, all prime numbers should be published along with sowing values.

In general, it is necessary to take simple numbers only from reliable sources.