Forwarded From: Bruce Schneier <schneier@counterpane.com>
CRYPTO-GRAM
August 15, 1998
by Bruce Schneier
President
Counterpane Systems
schneier@counterpane.com
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-subscribe@chaparraltree.com. 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 majordomo@sekurity.org with "subscribe isn".
Today's ISN Sponsor: New Dimensions International [www.newdimensions.net]
Received on Sat Aug 15 22:31:10 1998