The celebration surrounding the 30th anniversary of public key cryptography (video here), invented by Whitfield Diffie and Martin Hellman, gave me the opportunity to contact a number of guests from the event and digest a lot of information. I also had a chance to speak with the retired technical director of the NSA, Brian Snow, who offered many bits of insight at the PKC celebration. Dan Farber described Snow as the "chief scientist at the NSA."
|From left to right: Whitfield Diffie, Martin Hellman, Brian Snow, Jim Bidzos, Ray Ozzie, and moderator John Markoff. Photo source is the host of the PKC event, Voltage Security.|
The PKC event ended with a short Q&A session. One of the questions that came up concerned quantum cryptography. Panelist Dan Boneh (Stanford professor and inventor of Identity Base Encryption, IBE) clarified that there were two aspects of quantum physics that pertain to computing: quantum computing and quantum cryptography
Quantum computing is something we can't do yet, but we can do quantum cryptography. A quantum computer is basically a "better computer," which can do things much faster than the conventional computer, including the faster breaking of cryptographic algorithms. Quantum cryptography is an emerging encryption technology that allows us to theoretically guarantee the ability to detect the existence of eavesdropping due to quantum physics. Snow described quantum cryptography as something that at least in theory is "absolutely perfect," adding, "I will go after the implementation."
Expensive commercial quantum cryptography products are currently available from MagiQ. They have extremely limited applications for fixed point-to-point dedicated, uninterrupted fiber optic links with distance limitations of 120 kilometers. But even this niche market implementation of quantum cryptography presents challenges, since you have to ensure that you're talking to the right endpoints. There are various methods for doing this. One way to ensure that there aren't any man-in-the-middle attacks is to check for the existence of additional delays. The challenge is to get an accurate baseline delay measurement at the time of installation--but you must make sure that there isn't an eavesdropper on that fiber link to begin with or the baseline measurement is worthless. Of course, this would mean you'd have to guard every meter of that link when you're doing the baseline measurements, which isn't trivial.
Other quantum cryptography implementations from surface to satellite might be simpler with highly directional antennas because you simply have to look at the sky to make sure there aren't any hovering aircraft blocking line of sight to the satellite. There are other ways of securing quantum cryptography systems, but each poses its own implementation challenges.
Even if we ignored the heavy price tag of quantum cryptography (currently $100,000 for the hardware endpoints per fiber connection), the bigger problem with quantum cryptography is its limited application. Because it can be deployed only in fixed point-to-point dedicated links with limited range, it doesn't meet the communication requirements of modern computing systems. We need point-to-many and many-to-many secure communication channels for fixed and mobile applications that traverse land, sea, and air over a wide range of physical transport layers. Many of those transport layers, such as the Internet or wireless radio frequency communications, make it impossible to control the physical layer, so that we basically have to assume they're compromised by eavesdroppers to begin with. This is the beauty of modern encryption algorithms and public key cryptography--they can provide security in any environment with high assurance and low cost.
On quantum computing, Snow pointed out that the NSA had studied the possibility of quantum computers and initially set out to prove that it was impossible. But the harder the NSA studied, the more it came to the conclusion that quantum computing was simply a massively difficult engineering problem that may eventually be solved. He went on to warn that when quantum computing becomes a reality, it could severely compromise existing encryption algorithms (used for bulk payload encryption) and public key crypto algorithms (used for key exchange). Quantum computing could effectively slash the bit strength of encryption algorithms in half. Because of this potential threat from quantum computing in the future, the AES standards body put in a long-term "insurance policy" by doubling the bit count to 256 bits. If quantum computing ever becomes a reality, AES 128-bit encryption will become the weak equivalent of a 64-bit encryption algorithm. But AES 256-bit encryption will still be plenty secure, even if it gets knocked down 128 bits.
Public key crypto key exchange algorithms, such as Diffie-Hellman and RSA, would essentially be "flat lined" by quantum computing, rendering them completely broken. This is an "open problem," Snow said, and he implored the research community to come up with public key crypto algorithms that could withstand a future quantum computer attack. At this point, Diffie said that some of the public key crypto research on the "lattice system" could potentially withstand an attack from quantum computers. I asked Snow about this via e-mail and he responded that it might work conceptually, but that it has "knownproblems under TRADITIONAL computing." He said that a lot of research still needs to be done.
The myth of the U.S. government AES backdoor
One audience member asked, "Is there a clear distinction in cryptography where national security ends and commercial applications begin?" He basically wanted to know the difference between commercial and government class cryptography. Diffie responded that there has been a recognition that "the strength of cryptography is not the place to separate the two." He said that the most important development of the last several years has been the adoption by NSA of Suite B, which is a public set of standard cryptographic algorithms that are approved for unclassified and classified government data.
The gentleman who asked the question seemed surprised by the response and said that surely this was meant only for commercial applications, like e-commerce. Diffie made it clear that this was for all levels of classified government traffic. Snow said that the same algorithms are also available to the public commercial sector if anyone wants to use them, but emphasized that the government views them as good enough for highly classified traffic. If you, the public, want to use NSA Suite B, Snow said, please do, adding, "Because we like to buy in bulk and get a cheap price," which garnered laughs from the audience. This was absolutely fascinating to me, because here was the government that was once afraid of public cryptography now hoping to buy cheap commercial cryptography.
I asked Snow in a subsequent phone conversation about NSA Suite B and he said that the government will use good commercial implementations of AES if the software meets the NSA's stringent security standards after a thorough review of the product. These cryptographic solutions could be software but they're almost always hardware because no commodity operating system currently on the market meets the government's standards for high-grade security. This isn't to say that there's something wrong with the AES algorithm, just that the implementation of the encryption algorithm and all the software components surrounding it need to be absolutely flawless. It really doesn't matter what gets hacked since the result is equally damaging if any component in the system gets compromised.
In 2003, the U.S. government announced that AES was be good enough for classified information. Here's an excerpt from that document:
The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.
It has always bothered me that commercial security vendors are going around telling people to use their proprietary encryption technology and saying that they shouldn't use AES because there are probably government backdoors in it. I asked Snow about this, and he pointed out that AES was created by an international standards body that selected the best encryption algorithm from a large pool of candidates. The winning encryption algorithm, Rijndael, wasn't even American--it came from two Belgian cryptographers. Snow said it's ridiculous to assume that AES is somehow under the control of the U.S. government, or any government for that matter. The U.S. government and the NSA, along with the rest of the world, simply selected AES because it is a superb open standard encryption algorithm. It would be highly unlikely that the International community would select a cryptography standard that was compromised by any single country. Furthermore, proprietary cryptographic algorithms haven't gone through anywhere near the kind of public scrutiny and audits that NSA Suite B algorithms went though and are most likely inferior. So the next time a salesperson shows you a super secret proprietary encryption algorithm, I would suggest that you show them the door.