[ISN] CRYPTO-GRAM, August 15, 1998

From: mea culpa (jerichoat_private)
Date: Sat Aug 15 1998 - 16:21:38 PDT

  • Next message: mea culpa: "[ISN] Hackers Likely to Copy Clinton Testimony"

    Forwarded From: Bruce Schneier <schneierat_private>
                   August 15, 1998
                  by Bruce Schneier
                 Counterpane Systems
    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
    	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
    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
    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
    EFF's press release:
    Wired News:
    New York Times story:
    ** *** ***** ******* *********** *************
            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. 
    ** *** ***** ******* *********** *************
       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.
    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. 
    ** *** ***** ******* *********** *************
    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. 
    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? 
    IBM is giving away the source code to PKIX.  Good for them.
    ** *** ***** ******* *********** *************
          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
    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
    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. 
    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. 
    Over 70 products are now using the Blowfish encryption algorithm.  It's
    fast, and it's free. 
    ** *** ***** ******* *********** *************
    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. 
    Copyright (c) 1998 by Bruce Schneier
    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