Researchers have fundamentally proven that NSA broke the most-widely used encryption on the internet.
It was 2014 when documents leaked by former NSA employee Edward Snowden revealed the NSA’s capability to break trillions of encrypted connections by exploiting standard implementations of the Diffie-Hellman key exchange (DHE) algorithm.
Cryptographers and computer scientists, at the time, pointed to the notion that some 92 percent of the top 1 million Alexa HTTPS domains had only used a few prime numbers. Applications relying on the DHE generate ephemeral keys using groups of large prime numbers, fundamentally taking hundreds of even thousands of years with massive infrastructure to decrypt secure communications.
NSA’s $11 billion annual budget underlined its intent to develop a system that had “groundbreaking crypto-analytic capabilities”, leaving a majority of the world’s HTTPS domains under the NSA’s crosshairs.
Now, researchers from the University of Pennsylvania, INRIA, CNRS and Université de Lorraine have demonstrated how the NSA gained such capabilities. With 3,000 CPUs working over a two-month period, researchers were able to break one of the 1024-bit keys. This gave them the capability to passively decrypt HTTPS-based communications in their millions.
The DHE algorithm enables exchanging cryptographic keys over untrusted channels. Channels that allow protcols including HTTPS, SSH, VPN and more, to negotiate a secret key and create a secure connection.
In their research paper, the researchers explained how the DHE was intentionally weakened in a clandestine manner, masking how various applications generate prime numbers.
Researchers created a weak 1024-bit DHE trapdoor. In other words, they randomly selected a large prime number from a predetermined group. This enabled them to solve the discreet logarithm problem, some 10,000 times easier.
The research explained:
Current estimates for 1024-bit discrete log in general suggest that such computations are likely within range for an adversary who can afford hundreds of millions of dollars of special-purpose hardware,” the researchers wrote in their paper.
Fundamentally, any state-sponsored hacking endeavor with advanced hackers and the necessary resources who are aware of prime numbers generated for trapdoor function while looking to decrypt 1024-bit secured communications can unscramble the discreet logarithm, enabling them to decrypt hundreds of millions of DHE connections.
The researchers added:
The discrete logarithm computation for our backdoored prime was only feasible because of the 1024-bit size, and the most effective protection against any backdoor of this type has always been to use key sizes for which any computation is infeasible.
Researchers estimate that similar computations for 2048-bit keys, even those with backdoored prime numbers, would be 16 million times harder to crack, compared to 1024-bit keys. Meanwhile, 1024-bit keys remain the most widely used online.
Image credit: Wikimedia.
