[ISN] CRYPTO-GRAM, January 15, 1999

From: mea culpa (jerichoat_private)
Date: Fri Jan 15 1999 - 12:14:36 PST

  • Next message: mea culpa: "[ISN] Security show to highlight industry trends"

    Forwarded From: Bruce Schneier <schneierat_private>
                   January 15, 1999
                  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) 1999 by Bruce Schneier
    ** *** ***** ******* *********** *************
    In this issue:
         The 1998 Crypto Year-in-Review
         Counterpane Systems -- Featured Research
         Counterpane Systems News
         Comments From Readers
    ** *** ***** ******* *********** *************
          The 1998 Crypto Year-in-Review
    1998 was an exciting year to be a cryptographer, considering all the
    developments in algorithms, attacks and politics.  At first glance, the
    important events of the year seem completely unrelated: done by different
    people, at different times, and for different reasons.  But when we step
    back and reflect on the year-that-was, some common threads emerge -- as do
    important lessons about the evolution and direction of cryptography.
    New Algorithms
    In June, the NSA declassified KEA and Skipjack.  KEA is a public-key Key
    Exchange Algorithm <http://www.counterpane.com/crypto-gram-9808.html#kea>,
    while Skipjack is a block cipher first used in the ill-fated Clipper Chip
    <http://www.counterpane.com/crypto-gram-9807.html#skip>.  The NSA wanted
    Fortezza in software, and the only way they could get that was to
    declassify both algorithms.
    This marks the first time that an NSA-developed algorithm has been
    declassified and released into the public domain, and also the first time
    that the U.S. military has used a public algorithm to encrypt classified
    traffic.  More importantly, the release of Skipjack marks a watershed event
    in public cryptanalysis.  Like DES, a reference algorithm by which all
    attacks were measured, Skipjack is an example of a "reference good
    algorithm."  Think of it as alien technology: for the next decade
    researchers will pick Skipjack apart, looking for clues on how to design
    and analyze block ciphers.
    And there are lots of block ciphers to analyze.  In June, candidates for
    the Advanced Encryption Standard (AES), the replacement to DES, were
    submitted to NIST <www.nist.gov/aes>.  NIST's goal is to replace DES with
    another block cipher, one with a 128-bit block size and a key size of 128,
    192 or 256 bits.  Fifteen groups (companies, universities, individuals)
    submitted algorithms from the United States and abroad.  
    The process is a long one.  Currently, all 15 algorithms are being reviewed
    by the crypto community.  NIST will host a public workshop in Rome this
    March, with the public comment period ending this June.  After that, NIST
    will pick about five candidates for a second round.  Another workshop and
    public comment period will follow, after which NIST will pick a single
    winner sometime in 2000.  Following that, they will take the algorithm
    through the FIPS process, and it will hopefully become an ANSI, ISO, and
    IETF standard as well.
    The AES review process is important for several reasons.  First, DES is
    just too weak for modern use (see below).  Second, since there's no
    emergency, NIST can take its time and do this correctly.  And third, if
    everyone plays fair, there will be an encryption standard that is endorsed
    by the cryptographic community, one not subject to NSA tampering.
    New Attacks
    1998 also saw several important developments in the flip side of
    cryptology: cryptanalysis.  Quite simply, a lot of things were broken last
    In July, the Electronic Frontier Foundation (EFF) built Deep Crack, a
    hardware DES cracker that can break DES in an average of four-and-a-half
    days <http://www.eff.org/descracker>.  The $220,000 machine was not built
    to steal secrets or embezzle money, but to inarguably demonstrate that
    DES's 56-bit key is too short for any real security.
    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 already knew
    this; cryptographers have been saying it for years (I said it in my book,
    Applied Cryptography, back in 1994).  Technological predictions about the
    declining costs of such a machine -- predictions made from the late 1970s
    onward -- turned out to be dead-on.
    Rather, the news is how long the government has been denying that these
    machines were possible.  As recently as June 8, 1998, Robert Litt,
    principal associate deputy attorney general at the U.S. 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 at an EPIC conference.  "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."
    Litt looked foolish at the time, and he looks even more foolish now.  (See
    also: <http://www.counterpane.com/crypto-gram-9808.html#descracker>.)
    What Litt was talking about was another achievement of 1998: the cracking
    of the DES-II-1 challenge in February.  This was a software-only search of
    DES's 56-bit keyspace using spare cycles on computers connected to the
    Internet.  This break was a monumental distributed processing effort -- yet
    another piece of evidence that 56-bit keys are just too short.
    Not So Smart Cards
    Cryptanalysts gave smart cards a good whack when researchers invented power
    analysis.  In June, Paul Kocher and others demonstrated that secrets could
    be extracted from a smart card by watching the card's power usage
    <http://www.cryptography.com/dpa/index.html>.  Researchers have
    demonstrated this attack in several laboratories, extracting secret keys,
    bank balances, and everything else from supposedly secure smart cards.
    The important concept here is that there's another way of looking at a
    cryptographic algorithm.  We're used to treating algorithms as mathematics,
    but they can also be looked at as systems.  It's a biological approach:
    What are its inputs and outputs?  How does it move?  How does it respond to
    different stimuli?  By looking at a smart card as a concrete device with
    timing, power, radiation and other characteristics, it's possible to attack
    many systems that were previously believed to be secure.  By combining
    these techniques with fault analysis -- another "biological" attack that
    measures how a smart card responds to randomly induced faults -- the result
    is even more devastating
    What these attacks are telling us is not that we have to spend more effort
    making smart cards resistant -- that's probably not possible -- but that we
    need to rethink how data is stored on smart cards.  A system in which a
    device is owned by one party and the secrets within the device are owned by
    another is, fundamentally, a badly designed system.  Well-designed systems
    don't care about these attacks, because there are no secrets on the card
    that the cardholder wants.
    No Substitutes
    Some pretty lousy cryptography was exposed in 1998.  In April, University
    of California Berkeley researchers found flaws in the GSM digital cellular
    encryption algorithm, used in about 90 million cell phones worldwide
    <http://www.isaac.cs.berkeley.edu/isaac/gsm.html>.  And in an unrelated
    incident, in June researchers found flaws in Microsoft's PPTP protocol,
    used as a virtual private network (VPN) security protocol by many companies
    The moral from these two attacks is not that it's hard to do cryptography
    right and it's easy to make mistakes: we already knew that.  The moral is
    that there is no substitute for the public review process when it comes to
    security.  Both the GSM cellular system and Microsoft's PPTP system were
    designed by a closed group and remained proprietary.  No one person or
    group can be expert in all things, and as a result both systems had major
    flaws.  But because they were proprietary, the flaws were only discovered
    after the systems had been fielded.
    Contrast this approach with that for IPSec, a protocol for secure Internet
    traffic.  This protocol was developed in a public working group, and every
    step of the process has been available for public review.  As with GSM and
    PPTP, the group designing IPSec was not expert in all things, and, to be
    sure, there were flaws.  But these flaws were discovered by others involved
    in the process while the process was going on.  The system has been broken,
    fixed, broken again, fixed again and so on.  In the end we have a very
    robust system, the result of many people examining and commenting on
    drafts.  This kind of expertise simply cannot be purchased by a single
    organization, and it's foolish to believe otherwise.
    High-Profile Cracks
    In July, a Bell Labs researcher broke the RSA implementation in PKCS #1
    <http://www.counterpane.com/crypto-gram-9807.html#rsa>.  PKCS #1 is a
    padding scheme used in many products (SSL is probably the most widely
    known), and the attack worked in an operational setting against these
    products.  Vendors scrambled to fix the problem -- the fix was easy, once
    you knew the problem -- but the attack showed that even if the underlying
    algorithm is secure (RSA, in this example), the implementation may not be.
    In August, two French cryptographers described an attack against SHA-0.
    For those who don't remember, SHA is a NIST-standard hash function.  It was
    invented by the NSA in 1993, and is largely inspired by MD4.  In 1995, the
    NSA modified the standard (the new version is called SHA-1; the old version
    is now called SHA-0).  The agency claimed that the modification was
    designed to correct a weakness, although no justification was given.  Well,
    we now understand the attack against SHA-0 and how the modification
    prevents it.
    Also in August, a group of Israeli cryptographers presented "impossible
    differential cryptanalysis."  This is an esoteric mathematical
    cryptanalytic attack, applicable against several academic ciphers and one
    high-profile fielded one.  Surprisingly enough, impossible differentials
    work against a Skipjack variant with 31 rounds (the real cipher has 32
    rounds).  (See <http://www.counterpane.com/crypto-gram-9809.html#impossible>.)
    The implications of this attack are major.  There are two possible
    explanations: (1) The NSA didn't know about this attack, in which case
    academic cryptographers have scored a major win over our military
    counterparts; or (2) the NSA did know about this attack, in which case they
    have some kind of mathematical model that permits them to field algorithms
    that are just marginally above the break point.  Either explanation is
    fascinating, and points to some interesting research to come.
    Old News
    Some of the news in 1998 wasn't really news at all, since we all knew what
    was coming.
    In fall 1997, the first public-key patents expired.  These patents had
    prevented people from implementing all public-key cryptographic algorithms
    (not just RSA) without paying royalties.  So, in 1998 free public-key
    algorithms were used in standards for the first time; now, people can
    implement Diffie-Hellman key exchange, ElGamal encryption and ElGamal
    signatures without paying royalties to anyone.
    Finally, serious doubts were again raised about feasibility of key escrow
    <http://www.counterpane.com/key-escrow.html>.  Again, this isn't "new"
    news.  Researchers have long argued that the kind of key escrow the FBI
    wants causes more problems than it solves.  In June, a distinguished group
    of cryptographers released a report explaining just how insecure such a
    system would be.  The report looked at several new vulnerabilities that key
    escrow can introduce, including new ways of breaking messages, loss of
    security control, abuse by insiders, single points of attack and failure,
    loss of secrecy assumptions and complicated system design.  The amazing
    thing about this analysis is not that it echoes the NSA's own internal
    analysis (which it does), but that the more we learn about how to design
    and attack systems the harder this problem is to solve.
    What About '99?
    Looking back, most of the highlights from 1998 were completely
    unpredictable in December 1997.  Similarly, we have no idea what
    cryptographic success 1999 will bring.  Some predictions are obvious: NIST
    will choose finalists for the AES selection process; the RSA patent won't
    expire -- that will happen in September 2000; and key escrow won't get any
    more secure.  For sure, there will be some interesting cryptanalytic
    results against some interesting algorithms.  And some products we all use
    will be found to be weak, and hopefully they will be corrected.  
    But beyond these general observations, no one knows.  Cryptography is a
    unique science because research can go backwards in time.  A new
    compression algorithm might be better, but it won't make the old algorithms
    compress any less efficiently.  A new cryptographic technique can make
    already fielded algorithms, protocols, and products less secure.  There are
    a lot of very clever people working in cryptography, and it is unlikely
    they will have a dry year.  Stay tuned for more information -- as people
    invent it.
    (This originally appeared in the January 1998 issue of Information
    Security: <http://www.infosecuritymag.com>.)
    ** *** ***** ******* *********** *************
       Counterpane Systems -- Featured Research
    This paper discusses the notion of  "clueless agents," pieces of encrypted
    mobile code that cannot be decrypted until some external event occurs.  The
    idea is to build the computer equivalent of sleeper agents, who don't even
    know their own function and hence cannot be compromised.  (Think of "The
    Manchurian Candidate.")  As mobile code becomes more common, we see
    clueless agents becoming more important.
    ** *** ***** ******* *********** *************
    Human Rights watch has issued a report about restrictions on Internet
    speech around the world.  The full report, "Freedom of Expression on the
    Internet," is at:
    A summary can be found at:
    The Congressional comedy of Speakers resigning and new ones being chosen
    will have a negative effect on the fight for free cryptography in the U.S.
    Livingston supported the industry's version of SAFE, the crypto decontrol
    bill that died in Congress last session.  Hastert (the front-runner for
    Speaker of the House at this time) has shown strong solidarity with the FBI
    on encryption issues as a member of the House Commerce Committee.  Hastert
    supported the Oxley-Manton Amendment that would have turned the SAFE Act of
    1997 into a mandate for domestic regulation of encryption.  And when
    Oxley-Manton was rejected by the Committee in favor of the Markey-White
    Amendment, Hastert voted against the SAFE Act.
    "The Inevitability of Failure: The Flawed Assumption of Security in Modern
    Computing Environments."  This paper is by six NSA employees, and argues
    for secure operating systems in order to adequately address current and
    future security needs:
    Netscape 4.X can be used to read a file on a remote machine without the
    permission of the owner of that machine.  The initial posting on the topic
    can be found at:
    Additional postings can be found in the Bugtraq archives at:
    I'm not sure what to make of this next story.  Security Computing
    Corporation <http://www.smartfilter.com>, sells a content filter
    ("SmartFilter") that is used to restrict web access from within
    corporations and other organizations.  Lauren Weinstein, the moderator of
    the widely respected Privacy Forum, a mailing list and web site on the
    Internet at <http://www.vortex.com>, recently reported that for over a year
    corporate employees at sites that use SCC's SmartFilter have typically been
    restricted from accessing the Privacy Forum web site or archives because of
    the Privacy Forum's occasional discussion of cryptography.  These
    discussions -- high-level discussions of civil and ethical values, policy,
    and crypto politics -- were apparently enough to define the Privacy Forum
    web site as a repository of "criminal skill."
    In September, the National Academy of Sciences issued "Trust in
    Cyberspace," a 243-page survey of all security issues and technologies
    associated with the Internet and computer networks.  The report reviews
    prior studies such as the CRISIS report on cryptography, the PCCIP report
    on protecting US infrastructure, the DoD report on Information
    Warfare-Defense, and several others.  It assesses those findings in greater
    depth, looks at technology and research needed, and recommends what
    government (NSA and DARPA) and private industry/education should do to
    assure security.  NSA is upbraided for its opposition to strong
    cryptography and culture of over-controlling secrecy.  NSA's R2 research
    unit is singled out as needing to find ways to compete with industry for
    the best talent so that the agency's skills and tools do not lag behind the
    world market.
    Introduction only:
    http://jya.com/tic-intro.htm  (Introduction only, 58K)
    Full report:
    http://jya.com/tic.htm or http://jya.com/tic.zip
    Crypto++ 3.0 has just been released.  This is a fine, free crypto source
    code library.  You can find download instructions on the Crypto++ home page
    Electronic Frontiers Australia has posted an uncensored copy of the "Review
    of Policy relating to Encryption Technologies" (the Walsh Report) on its
    web site.  The originally censored parts are highlighted in red.  The
    report was prepared in late 1996 by Gerard Walsh, former deputy director of
    the Australian Security Intelligence Organisation (ASIO).  It was supposed
    to be released to the public, but it wasn't.  Eventually, a censored
    version was released.  Officially, this uncensored version has not been
    released.  It's worth reading, especially the censored parts.
    The press is buzzing about an Irish teenager creating a brilliant new
    public-key scheme called Cayley-Purser, supposedly much better than RSA.
    "Even when high security levels are required, her code can encrypt a letter
    in just one minute -- a widely used encryption standard called RSA would
    take 30 minutes.  'But she has also proven that her code is as secure as
    RSA,' says Dr Flannery.  'It wouldn't be worth a hat of straw if it was
    not.'"  Leaving aside the incredibly quaint Irish metaphor, this is what I
    do know:  The system is based on RSA, but I have not seen it.  It is
    believed to be as strong as RSA, but there is no proof.  The key and the
    ciphertext are about eight times the length of the modulus, rather than
    more-or-less the length of the modulus as with RSA.  It is faster, but I
    don't know by how much and under what assumptions.  Is this going to change
    the world, no.  Might it be interesting, yes.  We'll have to wait and see.
    In any case, it is cool to see serious cryptography out of a new researcher.
    The Indian Defence Research and Development Organisation (DRDO) has issued
    a "red alert" against all network security software developed in the US.
    The government is concerned that all U.S. software is weak and may contain
    government back doors.
    Furbys have been banned from the NSA, due to the possibility of them
    mimicking what they hear.  The fear is "that people would take them home
    and they'd start talking classified."
    ** *** ***** ******* *********** *************
              Counterpane Systems News
    Counterpane Systems will be featured in several panels at the 1998 RSA
    Conference in San Jose next week:
    	Mon, 3:00 PM.  Securing Audit Trails in Electronic Commerce.  Bruce
    Schneier will talk about how to secure audit trails so that they can be
    used as a forensics tool.  This is a continuation of the research found in
    	Tue, 4:00 PM.  The Twofish Encryption Algorithm.  Twofish design team
    member Doug Whiting will explain the algorithm and its implementation options.
    	Tue, 6:30 PM.  Extending PKI to Legacy Applications.  One of the companies
    we're working with, LockStar <http://www.lockstar.com>, will debut at the
    RSA Conference next week.  Bruce Schneier will speak on the above topic.
    It's in the Santa Clara room at the Hilton.  There'll be food.
    	Wed, 2:00 PM.  A Hacker Looks at Cryptography.  Bruce Schneier will speak
    at the Valicert booth.  It's a cheap trick to get into their booth, but
    I'll be entertaining and their booth is actually pretty cool.
    	Wed, 4:00 PM.  Pseudorandom Number Generation & Testing.  Counterpane
    cryptographer John Kelsey will discuss Yarrow, our free random number
    generator: <http://www.counterpane.com/yarrow.html>.
    The big Twofish news is that we've got the encryption speed down to 258
    clocks, or 16 clocks per byte.  Twofish was already the fastest algorithm
    on the Pentium, but now it is only 3% (7 clocks) slower than RC6 on the
    Pentium Pro/II.
    ** *** ***** ******* *********** *************
    	     Comments From Readers
    From: Reinhard Wobst <R.Wobst@ifw-dresden.de>
    Subject: plaintext recognition
    Your article about plaintext recognition is important.  I think people
    don't recognize that *any* plaintext format which obeys deterministic or
    probabilistic rules can be easily tested.  An example: Take a file
    generated by "compress" (which uses Ziv-Level compression) and cut off the
    3 magic bytes (otherwise the task would be too easy).  Then divide the
    bitstream into 9 bit words.  The nth word can have a value not greater than
    257+n.  So 7 ciphertext blocks should be enough to determine a 56-bit DES
    key uniquely.
    If you have GIF, JPEG or other graphic formats, then they must be
    expandable to pictures.  A picture can be defined by "most significant bits
    1...8 should not be white noise".  This should theoretically suffice to
    detect plaintext.  The practical problem is the computation time.  One has
    to find fast tests to drop the bad samples.  My idea is to write several
    rough and fast tests: the first (fastest) excludes 90% of bad samples, the
    second 80% of the rest and so on.  In practice, the speed of the first
    tests determines the speed of the whole procedure.
    Any data format with some *deterministic* relation between the bits and/or
    bytes should be even easier to test than an ASCII text which could contain
    some odd characters.  The most trivial example are word processors which
    produce lots of fixed bytes in fixed positions.  (The first KB of my
    WordPerfect files contain about 40% of zero bytes, for example.)
    Almost nobody in the "civil world" cares about such tests.  For
    demonstration purposes, I wrote a C program that cracks Vigenere enciphered
    compressed files (not using the magic bytes!).  It is contained on the CD
    in my book "Abenteuer Kryptologie."  I found up to 64 byte long passwords
    within dozens of seconds.
    ** *** ***** ******* *********** *************
    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 six-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) 1999 by Bruce Schneier
    Raphael Carter <anagramat_private>
    Subscribe: mail majordomoat_private with "subscribe isn".
    Today's ISN Sponsor: Internet Security Institute [www.isi-sec.com]

    This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:16:00 PDT