Crypto Key Exchange …like taking candy from a digital baby

For those among you who have read my previous SemiWiki articles, you will no doubt see a theme: the security of our connected world is badly broken, and for the bad guys, violating our online lives – both business and personal – is as easy as taking candy from the proverbial baby.

And while I’ve often used reports of numerous horrific online breaches to reinforce my perspective, I think it’s now time to get a little deeper into the real issues and risks we are facing, and to make a suggestion as to how we can effect an about-face and get ourselves back on a path which will render our connected world truly secure.

What the really smart people have discovered

Earlier this month at the 22nd ACM Conference on Computer and Communications Security, an elite group of computer scientists received the “Best Paper Award,” for their publication entitled ‘Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice’ – in this paper, the Logjam TLS/SSL vulnerability is highlighted, and much more. This insightful document came to a very disturbing conclusion. The Diffie-Hellman (D-H) key exchange, which is the cryptographic protocol used to “secure” a massive amount of Internet communication, is broken. Put another way, a security ingredient that is being relied upon by 66% of all VPNs, 25% of all servers and roughly 20% of the top million websites in the world is ineffective in protecting the good guys from the onslaught of sophisticated, organized, for-hire cybercriminals bent on wreaking havoc (or worse) online.

Without getting all technical, the D-H key exchange relies on prime numbers to secure connections, rather than utilizing random numbers. For the non-mathematician, the notion of prime numbers seems simple enough. Remember Math 101? A prime number is only divisible by the number 1 and itself. Now here’s something that makes prime numbers seem a whole lot more complex. A story I recently read suggested that discovering new large prime numbers would require a super computer that would cost hundreds of millions of dollars, and even at such a massive cost, the computer would only be able to discover one new prime per year. Not so. The Great Internet Mersenne Prime Search (GIMPS) initiative proved otherwise. GIMPS harnesses the power of distributed computing to search for new prime numbers and has repeatedly demonstrated its prowess by discovering 15 new large prime numbers since the project’s 1996 inception. And if you think that doesn’t sound like a great track record, think again. The last large prime discovered last week is 22 million digits in length. That’s a big number.

Back to Diffie-Hellman
As this cryptographic protocol uses prime numbers, it stands to reason that determined hackers could discover the primes being used to secure Internet communications. To quote the scientists who won the Best Paper award, “With sufficient precomputation, an attacker can quickly break any D-H instances that use a particular prime.” And while some might say, just lengthen the prime number to make it more difficult to break it, think about GIMPS. Today’s cybercriminals aren’t kids slurping soft drinks, and living off junk food, while toiling away in their parents’ basements. They are highly-sophisticated, well-organized and very capable of tapping into the networked-computing resources available to them to run their own version of GIMPS, focused not on discovering new primes but on discovering existing prime numbers being used in D-H.

In Today’s Hackers Are Way More Sophisticated Than You Think, Lance Cottrell states, “…when most people think about hackers and security, they are clinging to an outdated vision. Hackers are now part of a highly specialized and distributed criminal ecology.”

And, let’s be realistic. It’s not just the hackers of the world that are attacking the vulnerabilities inherent in D-H. Back to our award winning computer scientists: “We then examine…published Snowden documents that suggests NSA may already be exploiting 1024-bit Diffie-Hellman to decrypt VPN traffic.”May be exploiting? Regrettably, history (NSA-funded backdoors) suggests that the phrase “is exploiting,” is more likely to be the case.

The Argument for Random Numbers
The message is abundantly clear: by using known or discoverable prime numbers as key security ingredients, we are leaving ourselves open and vulnerable to state agencies and hackers who choose to violate or endanger our everyday lives. What’s also clear is that it’s time for the global leaders in IT security to move away from key exchange based on known or discoverable prime numbers, and instead use true random numbers. A hardware (true) random number generator, is a piece of electronics that plugs into a computer and produces genuine random numbers, as opposed to the pseudo-random numbers that are produced by a computer program such as newran.

The computer scientists agree, writing, “in the longer term, we advocate that protocols migrate to stronger Diffie-Hellman groups, such as those based on elliptic curves.” The recommendation made sense when first published (in April 2014, then presented in Oct 2015). After all, the NSA (in the mid-late 90’s) had widely promoted Suite B – pushing hard for adoption of the first public cryptography standard to include non-classified algorithms certified for encrypting Secret and Top Secret data.

Suite B relies exclusively on elliptical curve cryptography (ECC) for public key encryption and key agreement (ECC uses dramatically shorter keys than alternative public-key algorithms such as RSA and “classical” Diffie-Hellman.) It utilizes a Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG), which generates random-looking numbers using the mathematics of elliptic curves.

But, here’s the rub. Despite being around for close to two decades, and the promise that a D-H key exchange protocol based on Elliptic Curves (EC DH) holds, ECC has never really been accepted by the ITSec community as a whole. Why not?

Let’s put it out there:

MANY IN THE CRYPTO COMMUNITY DO NOT TRUST ANY NIST STANDARD PROMOTED BY THE NSA

The Elephant in the Room
Why not? Well, smart money says that the ECC in use today, much of which is standardized by NIST, has embedded backdoors. And it’s not just smart money conjecturing. It’s very smart people like Koblitz and Menezeswho present the argument that the NSA deliberately back-doored the NIST elliptic curves. Matthew Green, one of the most highly respected members of the crypto community, penned a brilliant summary of the eye-popping Koblitz/Menezes paper here.

And maybe, just maybe, the NSA itself is telling us that backdoors into ECC exist, and that they have been discovered and penetrated by cybercriminals. After all, why after promoting Suite B and ECC, would they suddenly do a 180 and advise people to run away from ECC technology, citing concerns about quantum computing? Especially when there is no evidence, even in the Snowden documents, that suggests any massive quantum breakthroughs on the horizon that would necessitate a rapid transition from ECC.

Here’s an excerpt from Mr. Green’s summary that reads like the foundation for a spy thriller:

“…the NSA isn’t worried about quantum computers at all, but rather, that they’ve made a major advance in classical cryptanalysis of the elliptic curve discrete logarithm problem — and panic is the result.
Let me lay the groundwork. The security of most EC cryptosystems rests on the presumed intractability of a few basic mathematical problems. The most important of these is called the Elliptic Curve Discrete Logarithm Problem (ECDLP). This problem must be supremely hard to solve, or virtually every cryptosystem built on ECC unravels very quickly.

The definition of “hard” is important here. What we mean in the context of ECC is that the best known algorithm for solving the ECDLP requires a number of operations that is fully exponential in the security parameter. In practice, this means we can achieve 128-bit equivalent security using an elliptic curve set in a 256 bit field — which implies similarly-small keys and ciphertexts. To achieve equivalent security with RSA, where sub-exponential algorithms apply, your keys need to be at least 3072 bits (!) long.
But while the ability to use (relatively) tiny elliptic curve points is wonderful for implementers, it leaves no room for error. If NSA’s mathematicians began to make even modest, but sustained advances in the state of the art for solving the ECDLP, it would put the entire field at risk. Beginning with the smallest of the standard curves, P-256, which would now provide less than the required 128-bit security.
Did I mention that as part of the recent announcement, NSA also deprecated P-256?”

In layman’s terms. ECC is unraveling and quickly. Translation: the bad guys are winning. Again.

A Digital War Measures Act? Maybe, it’s time
We’re at war with the cyber-criminal/cyber-terrorist community, and from all accounts our traditional, lengthy standards-based approach to digital security isn’t cutting it – mostly because it takes years to get anything done. Now is the time for accelerated innovation and rapid adoption of crypto schemas that aren’t susceptible to hacking from government agencies or the bad guys who we all fear.

Private and Public sector leaders need to step up and drive change now, collectively declaring a Digital War Measures act – where traditional rules and governances are tossed aside in favour of securing our people and resources and, ultimately, stopping the daily, dangerous intrusions that plague our connected world.

Widespread adoption of Identity Based Encryption 3.0 (IBE 3.0) would be a great start. IBE 3.0 eliminates the need to use RSA, Diffie-Hellman, or EC DH, and would instantly render useless the backdoors that sadly define these dated technologies.

IBE 3.0/CLAE is an authentication and crypto scheme, and it is a key exchange protocol used to securely communicate secret keys (AES or PGP keys for example) between two parties.

We are not open source. We are, though, open for scrutiny.

Share this post via:

• 
• 
• 
•