Forwarded From: Bruce Schneier <schneierat_private> CRYPTO-GRAM August 15, 1998 by Bruce Schneier President Counterpane Systems schneierat_private http://www.counterpane.com A free monthly newsletter providing summaries, analyses, insights, and commentaries on cryptography and computer security. Back issues are available at http://www.counterpane.com. To subscribe or unsubscribe, see below. Copyright (c) 1998 by Bruce Schneier ** *** ***** ******* *********** ************* In this issue: A Hardware DES Cracker KEA (Key Exchange Algorithm) Counterpane Systems -- Featured Research News Biometrics: Truths and Fictions Counterpane Systems News ** *** ***** ******* *********** ************* A Hardware DES Cracker On 17 July the Electronic Frontier Foundation (EFF) announced the construction of a DES brute-force hardware cracker. This $220,000 device can break a DES key in an average of 4.5 days. The news here is not that DES is insecure, that hardware algorithm-crackers can be built, or that a 56-bit key length is too short. We've known all of this already; cryptographers have been saying it for years. (My book said it in 1994.) Technological predictions made about the declining costs of such a machine, made in the late 1970s, the 1980s, and the early 1990s, turned out to be dead-on. The news is how long the government has been denying that these machines were possible. As recently as 8 June 98, Robert Litt, principal associate deputy attorney general at the Department of Justice, denied that it was possible for the FBI to crack DES. "[It is a myth that] we have supercomputers that can crack anything that is out there," Litt said. "Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message.... We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department." (See the full story at http://www.wired.com/news/news/politics/story/12830.html.) My comment was that the FBI is either incompetent or lying, or both. EFF's machine is not cutting-edge engineering. It is not state-of-the-art cryptography. It is not bleeding-edge technology. The machine uses old, boring chip technologies, simple hardware design, not-very-interesting software, and no cryptography. This is not a marvel of engineering; the only interesting thing is how straightforward the design really is. Moreover, the machine scales nicely. EFF spent $220,000 on their first machine. Now that the design work is done, they can build a second for about $50,000. For every doubling of that price, they can double the speed of the machine (so a second machine for $250,000 can break DES in less than a day). And Moore's Law predicts that the same machine will be either twice as fast or twice as cheap in another 18 months. The EFF machine broke DES, but it could just as easily have been designed to break any other encryption algorithm. The attack was against the key length, not against the algorithm design. Moreover, a slightly more expensive design would have used FPGAs, allowing the system to work against a variety of algorithms and algorithm variants. The only solution here is to pick an algorithm with a longer key. DES has a fixed 56-bit key. Triple-DES has a 112-bit key; there isn't enough silicon in the galaxy or enough time before the sun burns out to brute-force triple-DES. AES requires 128-, 192-, and 256-bit keys. The EFF is a civil liberties group, and this was just a demonstration project. Government agencies like the FBI and the NSA would presumably spend a lot more time engineering a more efficient solution. It is reasonable to assume that any country with an intelligence budget has built this sort of machine, probably one a couple of orders of magnitude faster. There are undoubtably many, many technical improvements that can be made to the EFF design to make brute-force search cheaper and faster. But the fact that a civil liberties group can use old technology to build something that the adminstration has denied can be built...that's the real news. EFF's press release: http://www.eff.org/descracker/ Wired News: http://www.wired.com/news/news/technology/story/13800.html Cnet: http://www.news.com/News/Item/0%2C4%2C24322%2C00.html?sas.mail New York Times story: http://www.nytimes.com/library/tech/yr/mo/biztech/articles/17encrypt.html. ** *** ***** ******* *********** ************* KEA (Key Exchange Algorithm) Last month the NSA declassified Fortezza, including the Skipjack symmetric cipher and the KEA key agreement algorithm. Last month I talked about Skipjack. This month, it's KEA's turn. Before declassification, I heard KEA described as "Diffie-Hellman with a twist." Actually, there's a twist and a half. In normal Diffie-Hellman, Alice combines Bob's public key with her own private key to create a session key. Bob then combines his private key with Alice's public key to create the same session key. KEA does this a little differently. Alice and Bob both have a long-term public key and private key, but they also generate a one-time public and private key for the specific session. Alice combines her long-term private key with Bob's session public key, and her session private key with Bob's long-term public key. The benefit with this approach is that the same Diffie-Hellman key is not created twice; each session creates two unique combinations and two unique keys. (The downside, of course, is that there is twice as much computation going on.) The half twist is how the two Diffie-Hellman-generated keys are used. Instead of being used directly as keys, the two 80-bit values go through a one-way function (based on Skipjack) to create a single 80-bit value that becomes the key. I assume the point is that the mathematics is never used directly; there is some "muddle" process in the middle. KEA is a straightforward design, so it isn't getting anywhere near the same attention as Skipjack. That's a shame, really. I expect to see KEA popping up in various standards committees as people use it in other key-exchange systems. http://csrc.nist.gov/encryption/skipjack-kea.htm ** *** ***** ******* *********** ************* Counterpane Systems -- Featured Research "Protocol Interactions and the Chosen Protocol Attack" J. Kelsey, B. Schneier, and D. Wagner, Security Protocols, 5th International Workshop April 1997 Proceedings, Springer-Verlag, 1998, pp. 91--104. Many systems use the same crypto keys for different protocols (e.g. both SSL and S/MIME use the same public-key certificate). This paper presents attacks on protocol interactions. An attacker can create a new protocol that is individually strong, but which breaks a target protocol when both are run using the same keys. The paper concludes with a discussion of design principles to resist this class of attack. http://www.counterpane.com/chosen_protocol.html ** *** ***** ******* *********** ************* News It seems that every few months we get key-escrow repackaged with a new name. The latest new name is "Private Doorbell," and the spin is that the keys are escrowed in the routers. Other than the name, there's really no difference between this and other key escrow schemes: 1) You have to trust the security of your communications to the strength of this system; if it fails your communications are no longer private. 2) Communications keys are escrowed, for which there is no legitimate business purpose. 3) There is a massive and expensive infrastructure that has to be in place to make this work. The FBI likes this proposal, of course. http://www.wired.com/news/news/technology/story/13658.html http://www.zdnet.com/zdnn/stories/zdnn_smgraph_display/0,3441,336043,00.html http://www.infoworld.com/cgi-bin/displayStory.pl?980714.wnencryption.htm Researchers are continuing to analyze Skipjack. I've seen attacks against 28-round variants (the full cipher has 32 rounds) that are more efficient than brute force. It looks like Skipjack has been carefully designed to be no more secure than its 80-bit key. The Pentagon's top civil servant believes that no two people in the world have a "God-given right" to communicate in total secrecy. Man, who spit in his Cheerios? http://www.wired.com/news/news/technology/story/14098.html IBM is giving away the source code to PKIX. Good for them. http://www.techweb.com/se/directlink.cgi?INW19980803S0013 ** *** ***** ******* *********** ************* Biometrics: Truths and Fictions Biometrics are seductive: you are your key. Your voiceprint unlocks the door of your house. Your retinal scan lets you in the corporate offices. Your thumbprint logs you on to your computer. Unfortunately, the reality of biometrics isn't that simple. Biometrics are the oldest form of identification. Dogs have distinctive barks. Cats spray. Humans recognise each other's faces. On the telephone, your voice identifies you as the person on the line. On a paper contract, your signature identifies you as the person who signed it. Your photograph identifies you as the person who owns a particular passport. What makes biometrics useful for many of these applications is that they can be stored in a database. Alice's voice only works as a biometric identification on the telephone if you already know who she is; if she is a stranger, it doesn't help. It's the same with Alice's handwriting; you can recognize it only if you already know it. To solve this problem, banks keep signature cards on file. Alice signs her name on a card, and it is stored in the bank (the bank needs to maintain its secure perimeter in order for this to work right). When Alice signs a check, the bank verifies Alice's signature against the stored signature to ensure that the check is valid. There are a bunch of different biometrics. I've mentioned handwriting, voiceprints, and face recognition. There are also hand geometry, fingerprints, retinal scans, DNA, typing patterns, signature geometry (not just the look of the signature, but the pen pressure, signature speed, etc.), and others. The technologies behind some of them are more reliable than others, and they'll all improve. "Improve" means two different things. First, it means that the system will not incorrectly identify an impostor as Alice. The whole point of the biometric is to prove that Alice is Alice, so if an impostorcan successfully fool the system it isn't working very well. This is called a false positive. Second, "improve" means that the system will not incorrectly identify Alice as an impostor. Again, the point of the biometric is to prove that Alice is Alice, and if Alice can't convince the system that she is her then it's not working very well, either. This is called a false negative. In general, you can tune a biometric system to err on the side of a false positive or a false negative. Biometrics are great because they are really hard to forge: it's hard to put a false fingerprint on your finger, or make your retina look like someone else's. Some people can mimic others' voices, and Hollywood can make people's faces look like someone else, but these are specialized or expensive skills. When you see someone sign his name, you generally know it is him and not someone else. Biometrics are lousy because they are so easy to forge: it's easy to steal a biometric after the measurement is taken. In all of the applications discussed above, the verifier needs to verify not only thatthe biometric is accurate but that it has been input correctly. Imagine a remote system that uses face recognition as a biometric. "In order to gain authorization, take a Polaroid picture of yourself and mail it in. We'll compare the picture with the one we have in file." What are the attackshere? Easy. To masquerade as Alice, take a Polaroid picture of her when she's not looking. Then, at some later date, use it to fool the system. This attack works because while it is hard to make your face look like Alice's, it's easy to get a picture of Alice's face. And since the system does not verify that the picture is of your face, only that it matches the picture of Alice's face on file, we can fool it. Similarly, we can fool a signature biometric using a photocopier or a fax machine. It's hard to forge the vice-president's signature on a letter giving you a promotion, but it's easy to cut his signature out of another letter, paste it on the letter giving you a promotion, and then photocopy the whole thing and send it to the human resources department...or just send them a fax. They won't be able to tell that the signature was cut from another document. The moral is that biometrics work great only if the verifier can verify two things: one, that the biometric came from the person at the time of verification, and two, that the biometric matches the master biometric on file. If the system can't do that, it can't work. Biometrics are unique identifiers, but they are not secrets. (Repeat that sentence until it sinks in.) Here's another possible biometric system: thumbprints for remote login authorizations. Alice puts her thumbprint on a reader embedded in the keyboard (don't laugh, there are a lot of companies who want to make this happen). The computer sends the digital thumbprint to the host. The host verifies the thumbprint and lets Alice in if it matches the thumbprint on file. This won't work because it's so easy to steal Alice's digital thumbprint, and once you have it it's easy to fool the host, again and again. Biometrics are unique identifiers, but they are notsecrets. Which brings us to the second major problem with biometrics: it doesn't handle failure very well. Imagine that Alice is using her thumbprint as a biometric, and someone steals it. Now what? This isn't a digital certificate, where some trusted third party can issue her another one. This is her thumb. She only has two. Once someone steals your biometric, it remains stolen for life; there's no getting back to a secure situation. (Other problems can arise: it's too cold for Alice's fingerprint to register on the reader, or her finger is too dry, or she loses it in a spectacular power-tool accident. Keys just don't have as dramatic a failure mode.) A third, more minor problem, is that biometrics have to be common across different functions. Just as you should never use the same password on two different systems, the same encryption key should not be used for two different applications. If my fingerprint is used to start my car, unlock my medical records, and read my email, then it's not hard to imagine some very bad situations arising. Biometrics are powerful and useful, but they are not keys. They are useful in situations where there is a trusted path from the reader to the verifier; in those cases all you need is a unique identifier. They are not useful when you need the characteristics of a key: secrecy, randomness, the ability to update or destory. Biometrics are unique identifiers, but they are not secrets. ** *** ***** ******* *********** ************* Counterpane Systems News Twofish, our submission to the Advanced Encryption Standard (AES) process, has been accepted as a valid submission by NIST. All this means is that we received a form letter and are presenting Twofish at the first AES workshop in Ventura next week. Expect a multi-year process to select AES. http://www.counterpane.com/twofish.html Counterpane Systems is working with several smart-card companies to implement solutions to differential power analysis and other side-channel attacks. The first in a series of theoretical papers to come out of this work will be presented at the ESORICS conference in September. http://www.counterpane.com/side_channel.html Over 70 products are now using the Blowfish encryption algorithm. It's fast, and it's free. http://www.counterpane.com/products.html ** *** ***** ******* *********** ************* CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses, insights, and commentaries on cryptography and computer security. To subscribe, visit http://www.counterpane.com/crypto-gram.html or send a blank message to crypto-gram-subscribeat_private To unsubscribe, visit http://www.counterpane.com/unsubform.html. Back issues are available on http://www.counterpane.com. Please feel free to forward CRYPTO-GRAM to colleagues and friends who will find it valuable. Permission is granted to reprint CRYPTO-GRAM, as long as it is reprinted in its entirety. CRYPTO-GRAM is written by Bruce Schneier. Schneier is president of Counterpane Systems, the author of "Applied Cryptography," and an inventor of the Blowfish, Twofish, and Yarrow algorithms. He served on the board of the International Association for Cryptologic Research, EPIC, and VTW. He is a frequent writer and lecturer on cryptography. Counterpane Systems is a five-person consulting firm specializing in cryptography and computer security. Counterpane provides expert consulting in: design and analysis, implementation and testing, threat modeling, product research and forecasting, classes and training, intellectual property, and export consulting. Contracts range from short-term design evaluations and expert opinions to multi-year development efforts. http://www.counterpane.com/ Copyright (c) 1998 by Bruce Schneier -o- Subscribe: mail majordomoat_private with "subscribe isn". Today's ISN Sponsor: New Dimensions International [www.newdimensions.net]
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:01:10 PDT