Public-Key Crypto May Be Dead In a Few Years (and more Snowden)

Recent mathematical breakthroughs in solving something called the “discrete logarithm problem” mean that, once the practical security types figure out how to implement them, public key cryptography as we know it may be in trouble. With it would go just about every popular application of encryption.

Diffie-Hellman key exchange (a core part of OTR messaging), RSA (which Tor relies on), and ElGamal (which GPG uses by default, RSA is the alternative) — all these appear to rely on the discrete logarithm problem remaining unsolved.

Which it has, at least as far as we members of the public know, until fairly recently. Now mathematicians appear to making steady progress on it.

As the linked article points out, progress in theoretical math tends to predict otherwise surprising progress in practical attacks not too long after.

Snowden: Sources from all over the woodwork have emerged to point out that Snowden didn’t have access to the NSA’s “dark inner secrets,” the documents that the NSA “guarded most closely,” and even that the NSA “didn’t believe the documents Snowden stole were critical enough to national security to limit who within the agency could see them.” [1]

What’s more secret than a backdoor in Gmail? Well, traditionally the closest-guarded secrets of a group like the NSA is their cryptanalytic capability. In WWII, Winston Churchill famously allowed the Nazis to bomb Coventry unhindered — killing some 500 people and causing untold damage — rather than risk compromising the secret that the Allies could read the Enigma encryption scheme.[2]

This all begs the question… could Snowden really speak authoritatively when, asked whether encrypting your email (presumably with PGP/GPG), he replied that “Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on” …? [3]

We have at least one answer to the contrary. Some time ago, the former East German ruling party (now known as “The Left”, and still in German parliament) posed a series of questions to German intelligence. One of them was whether the intelligence services were capable of “decrypting at least partially, or evaluating encrypted communications (eg via SSH or PGP)”. The answer was quite clear:

“Yes, the technology used is generally able to do that, depending on the type and quality of the encryption.”

While commenters at the time attributed this answer to endpoint attacks (stealing keys with trojans and the like), given the mathematical developments cited in the main article… I have to wonder.

Does that mean we should forget about setting up OTR/XMPP over Tor, and instead develop telepathic abilities so we can hold “secure chats” in our dreams? That, I think is up to the reader… but I would caution not to feel too safe with “mental encryption,” as there’s anecdotal evidence of uncertain credibility the Russians managed to intercept and mount MITM attacks on telepathic links in the 70s! [4]




[4] Ostrander & Schroeder, “Psychic Discoveries: The Iron Curtain Lifted”

“a number of academic breakthroughs in solving a complex mathematics problem could have a real impact on the security of the crypto systems that underpin much of today’s Internet’s security, three security consultants will argue at the Black Hat Security USA Briefings later this month. Just as successful attacks on MD5 hashes were presaged by the academic discovery of weaknesses in the hashing algorithm, a number of academic papers on advances in solving what is known as the discrete logarithm problem may be a predictor of rough times ahead for many public-key crypto systems, says Alex Stamos, a presenter and chief technology officer for secure-domain administrator Artemis Internet.

“We keep on having these big breakthroughs in practical crypto attacks that, if you were paying attention to the academic side, would not be much of a surprise,” he says.

The complexity of the discrete algorithm problem, or DLP, is the basis for many popular crypto systems, such as ElGamal — the default encryption used in GNU Privacy Guard — and Diffie-Hellman key exchange. In addition, advances in solving the discrete logarithm problem can lead to advances in factoring, the basis of the popular RSA asymmetric encryption algorithm.

“We are not predicting that this will happen, but looking at past progressions, it is possible that in the next couple of years there could be a breakthrough in these problems,” Stamos says. “If that happens, most asymmetric cryptography would be useless.”

The researchers’ concerns stem from two papers published earlier this year. In January, cryptographer Antoine Joux of CryptoExperts found a method to improve the efficiency of solving a subset of the discrete logarithm problem and demonstrated it on a fairly complex DLP with a field size of 1,425 bits and then, two months later, of 4,080 bits. A group of four other researchers — Faruk Gologlu, Robert Granger, Gary McGuire, and Jens Zumbragel — boosted that to 6,120 bits in April. […]

“It is a best practice to consider that any estimate regarding the exploitability of a weakness will come sooner than we originally thought,” he says.

Companies should design their crypto systems to be easily changed out in the case that an algorithm is broken, Bocek says.”

%d bloggers like this: