With the egoless interest of someone really passionate about his craft, Martin Hellman explained to me the limitations of the cryptographic system he helped create and how Dif e-Hellman encryption was being picked apart by modern researchers. So he’s entirely credible when he says that cryptography faces some surprising challenges.
He told me that in 1970 there was a major breakthrough in factoring, called continued fractions. The dif culty involved in factoring large numbers is what makes cryptographic systems so complex, and therefore dif cult to crack. Any advance in factoring reduces the complexity of the cryptographic system, making it more vulnerable. Then in 1980, a breakthrough pushed factoring further, thanks to Pomerance’s quadratic sieve and the work of Richard Schroeppel. “Of course, RSA [computer encryption] didn’t exist in 1970, but if it did, they would have had to double key sizes. 1980, they had to double them again. 1990 roughly, the number eld sieve roughly doubled the size of numbers again that we could factor. Notice, almost every 10 years—1970, 1980, 1990—there’s been a doubling of key size required. Except in 2000, there was no advance, no major advance since then.”
Some people, Hellman said, might look at that pattern and assume mathematicians had hit a wall. Hellman thinks differently. He invited me to think of a series of coin ips. Would I assume, he asked, that after coming up heads six times in a row, it was a certainty that the next ip would be heads?
The answer, of course, is absolutely not. “Right,” said Hellman. “We need to worry that there might be another advance in factoring.” That could weaken existing cryptographic systems or render them useless altogether.
This might not be a problem right now, but Hellman thinks we should be looking for backup systems for modern crypto in the event of future breakthroughs.
But it’s the possibility of quantum computing, and with it, quantum cryptanalysis, that could actually break every system that currently relies on encryption. Today’s computers rely on a binary 1-or-0 system to operate, with light and electricity behaving as they should. A quantum computer, on the other hand, could take advantage of quantum properties to function. It
Another advance in factoring could weaken existing cryptographic systems or render them useless altogether.
could, for example, use a superposition of states—not just 1 or 0 but 1 and 0 at the same time—enabling it to perform many calculations simultaneously. It could also make use of quantum entanglement, in which a change to one particle is expressed in its entangled twin faster than light.
It’s the sort of thing that makes your head ache, especially if you already get tripped up trying to understand classical computers. The fact that we even have the phrase “classical computers” is perhaps indicative of how far we have come with practical quantum computing.
“Pretty much all of the public key encryption algorithms we use today are vulnerable to quantum cryptanalysis,” said Matt Green. Remember, the utility of modern encryption is that it takes seconds to encrypt and decrypt information with the right keys. Without the keys, it could take an incredibly long time even with a modern computer. It’s that differential in time, more than math and implementations, that makes encryption valuable.
“Normally [it] would take millions and millions of years for standard classical computers to break, but if we are able to build a quantum computer, we know algorithms we can run on it that would break these cryptographic algorithms in a few minutes or a few seconds. These are the algorithms we use to encrypt pretty much everything that goes over the Internet, so if you go to a secure webpage, we use these algorithms; if you do nancial transactions, you’re probably using some of these algorithms. Yes, the person who builds a quantum computer rst will be able to break and listen in on a lot of your conversations and your nancial transactions,” said Green.
If you’ve wondered why major world players like the U.S. and China are spending enormous volumes of cash investing in quantum computing, that’s at least part of the answer. The other part is doing some computational work that could yield breakthroughs of enormous importance: say, ending diseases.
But as Hellman suggested, researchers are already working on new cryptographic protocols that would stand up to scouring by a quantum computer. The quest for a working quantum computer has yielded promising results, but anything even resembling an effective quantum computer is far from the mainstream. Thee research in how to guard against quantum cryptanalysis goes forward operating under the assumptions we can make about how such a computer would work. The result is a wildly different kind of encryption.
“These problems are fundamentally mathematically different from [the] algorithms that you can use the quantum computer to break,” Maria
Dubovitskaya told me. A new kind of math using lattice-based assumptions, explained Dubovitskaya, is being used to ensure that when the next generation of computers comes online, cryptography doesn’t disappear.
But quantum computers that would give Einstein a heart attack are just one of the threats to modern encryption. A more real concern is the ongoing attempt to make encryption fundamentally insecure in the name of national security. The tensions between government and law enforcement efforts to make encryption more accessible to surveillance has gone on for decades. The so- called Crypto Wars of the 1990s had many battles: The CLIPPR chip, an NSA- endorsed system designed to introduce a cryptographic backdoor into the U.S. mobile telephony system; attempting to bring criminal charges against PGP’s creator Phil Zimmerman for using more secure encryption keys than were legally allowed; and so on. And of course, in recent years, the focus has moved from limiting encryption systems to introducing backdoors or “master keys” to unlock messages secured with those systems.
The issue, of course, is far more complex than it appears. Phil Dunkelberger said that, in the case of bank records, there can be dozens of records with individual encryption keys, and then keys to simply look at the data stream. This, he said, brings about the discussion of so-called master keys that would cut through these layers by weakening the math at the heart of the systems. “They start talking about weaknesses in the algorithm themselves, not the implied use of encryption,” he said. “You’re talking about being able to run at the foundation of that protection itself.”
And perhaps frustration looms even larger than the danger. “We’ve got to get out of revisiting the same problems,” said Dunkelberger. “We’ve got to start looking at innovative ways to solve the problems and move the industries forward, so the users can just go about their lives as they would any other day.”
Reference taken from Featured Article published on PC MAG October 2016.