October 17, 2016 by

Researchers Show NSA’s Capability to Break Trillions of Encrypted Connections

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.

About the author

Image of Author

LIFARS is the global leader in Digital Forensics and Cyber Resiliency Services. Our experience spans two decades working on high profile events, often in concert with Law Enforcement Agencies around the world. Our proprietary methodology derives directly and indirectly from our experience working with and for U.S. Intelligence Agencies, Interpol, Europol, and NATO. We are solely dedicated to Cyber Resiliency and thus pay close attention to all aspects of our clients’ engagements experience while providing a strategic and integrated array of services to minimum risk and disruption while protecting your brand.

Related articles

Kaspersky Denies Involvement in Russia’s Hack of NSA Contractor

Moscow-based cybersecurity firm Kaspersky Labs has denied a Wall Street Journal report that alleges...

Read more arrow_forward

NSA White-Hat Hackers are Reportedly Quitting in Droves

The NSA is seeing an increased number of employed hackers and cyberespionage agents quitting the...

Read more arrow_forward

Former NSA Contractor Indicted Over Theft of Govt Hacking Tools

A former contractor has been indicted for the alleged theft of government property that includes...

Read more arrow_forward