[ISN] CRYPTO-GRAM, September 15, 1998

From: mea culpa (jerichoat_private)
Date: Wed Sep 16 1998 - 02:16:30 PDT

  • Next message: mea culpa: "[ISN] Quo Vatis: More notes from the FBI re computer crime."

    Forwarded From: Bruce Schneier <schneierat_private>
                  September 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:
         Cramer-Shoup Cryptosystem
         Impossible Cryptanalysis and Skipjack
         Counterpane Systems - Featured Research
         Private Doorbell
         Corrections to 15 August 1998 CRYPTO-GRAM
         More on Biometrics
    ** *** ***** ******* *********** *************
              Cramer-Shoup Cryptosystem
    So there I was, sitting in the audience at Crypto, listening to the various 
    presentations.  Crypto is the largest and most important annual 
    cryptography research conference, and the papers were interesting.
    Monday afternoon I checked my messages.  Five reporters called me about 
    some big IBM announcement at Crypto about their amazing new cryptographic 
    algorithm.  Nothing stood out from the day's presentations.  I looked 
    through the proceedings, and only found one IBM paper that it could be.  I 
    skimmed it again, and it didn't look like anything.  So I started calling 
    reporters back.
    It seems that the IBM public relations department was working overtime.  
    There was a story in The Wall Street Journal, and another in The Industry 
    Standard.  The news was glowing, and predicted that this new algorithm 
    would replace SSL, save the Internet, and cure cancer.  Hype was 
    everywhere, and facts were few.  Near as I can tell, the only reason this 
    got out of hand so badly is that every cryptographer was at Crypto, and 
    This is my attempt to inject some reality into the conversation.
    What is the Cramer-Shoup Cryptosystem?  It's an academic paper (a good one) 
    with an overly aggressive public relations department behind it.
    Simply, Cramer-Shoup is a public-key cryptosystem that prevents adaptive 
    chosen ciphertext attacks.  This is an attack where a cryptanalyst is able 
    to get the decryption of different ciphertexts related to the ciphertext he 
    is interested in.  The cryptanalyst might want to know the decryption of C.  
    So the cryptanalyst gets the decryptions of several other ciphertexts, C', 
    C'', etc., and uses that information to decrypt C.  The attack against RSA 
    in PKCS #1 by Bleichenbacher, discussed in the 15 July 1998 CRYPTO-GRAM, is 
    an example of an adaptive chosen ciphertext attack: a cryptanalyst can 
    learn how to decrypt C by sending the system several related C's, and 
    seeing if the system can decrypt those.
    This resistance is a nice feature of the Cramer-Shoup algorithm, and there 
    are some nice security proofs to back the claims up.  The algorithm is a 
    little more annoying than some others: ciphertext is about four times 
    plaintext (not a big deal in most applications) and takes about twice as 
    much computation as ElGamal.  But it's not new.  It's not earth-shattering.  
    It's not going to change the world.  Or even reduce itching.
    The cryptographic community hasn't been bemoaning the problem, utterly lost 
    in how to defend against the attacks, and desperately hoping for some 
    company (like IBM) to come swooping down out of the sky with the answer.  
    RSA's vulnerability to adaptive chosen ciphertext attacks was pointed out 
    soon after the algorithm was invented.  In most cases, the attacks are not 
    possible within the application.  And solutions have been devised for 
    dealing with the attacks when they are possible.  They are usually dealt 
    with in the protocol; PKCS #1 was vulnerable to an adaptive chosen 
    ciphertext attack, but version 2 of the protocol uses a message packing 
    protocol called OAEP that makes the attack infeasible.  And not leaking 
    related plaintexts is another good defense.
    Cramer-Shoup is good work and a good academic paper.  The results are 
    suprising: provable security against adaptive chosen ciphertexts and only 
    twice as slow and four times the data expansion.  But the proofs are based 
    on something called the Diffie-Hellman Decision Problem (not the 
    Diffie-Hellman Problem), which is much weaker.  And IBM's provably secure 
    algorithm from last year's Crypto, Atjai-Dwork, has at least three 
    different breaks.  The breaks don't attack the proofs, but the assumptions 
    surrounding the proofs.  
    If, in a few years, Cramer-Shoup still looks secure, cryptographers may 
    look at using it instead of other defenses they are already using.  But 
    since IBM is going to patent Cramer-Shoup, probably not.  (There have been 
    some reports that IBM will give the patent away, but I have seen nothing 
    conclusive.)  But we have many other solutions to the problem of adaptive 
    chosen ciphertext attacks.
    excite news: http://nt.excite.com:80/news/bw/980824/ibm-research-encryption
    BBCnews: http://news.bbc.co.uk:80/hi/english/sci/tech/newsid_157000/157441.stm
    Nando (Reuters):
    MSNBC: http://www.msnbc.com:80/news/190053.asp
    news.com (Reuters): http://www.news.com:80/News/Item/0,4,25598,00.html?owv
    Wired: http://www.wired.com:80/news/news/technology/story/14590.html
    PCWeek: http://www8.zdnet.com:80/pcweek/news/0824/24eibm.html
    ** *** ***** ******* *********** *************
         Impossible Cryptanalysis and Skipjack
    Eli Biham, Alix Biryukov, and Adi Shamir invented something called 
    "impossible cryptanalysis," which they presented at the rump session (the 
    informal session where recent results are briefly described) of Crypto '98.  
    (Biham and Shamir are two Israeli cryptographers who independently invented 
    differential cryptanalysis in 1991, setting the foundations for pretty much 
    every general cryptanalytic technique since then.)
    The basic idea is that they look for differentials (differences between 
    pairs of plaintexts that have some percentage of holding true for the 
    corresponding differences between pairs of ciphertexts) that are 
    impossible; i.e., that cannot happen.  It turns out that in many cases 
    these impossible differentials are more powerful than normal differentials, 
    and can be used to attack encryption algorithms.
    The group presented an attack against 31-round Skipjack that is faster than 
    brute force.  Skipjack has 32 rounds, so their attack is just shy of being 
    better than brute force.  On the other hand, I can't imagine that the NSA 
    would field an algorithm with 32 rounds when they could break 31, so I 
    believe that the NSA did not know about this attack.  And the cryptanalysts 
    are still working on improving their attack, so it is possible that they 
    will get to 32 rounds.
    Since none of the AES submissions have been designed with impossible 
    cryptanalysis in mind (with the possible exception of Biham's own Serpent), 
    it will be interesting to see how the algorithms fare against this new form 
    of attack.  My guess is that all will be strongly resistant to it, with a 
    couple of exceptions.
    ** *** ***** ******* *********** *************
       Counterpane Systems -- Featured Research
    "Electronic Commerce and the Street Performer Protocol"
    J. Kelsey and B. Schneier, The Third USENIX Workshop on Electronic Commerce 
    Proceedings, USENIX Press, September 1998. 
    Copyright will be increasingly difficult to enforce in the future.  The 
    barriers to making high-quality pirated copies of digital works are getting 
    lower and lower, and solutions such as hardware tamper-resistance and 
    watermarking just don't work.  We introduce the Street Performer Protocol, 
    an electronic-commerce mechanism to facilitate the private financing of 
    public works.  Using this protocol, people would place donations in escrow, 
    to be released to an author in the event that the promised work is put in 
    the public domain.  This protocol has the potential to fund alternative or 
    "marginal" works. 
    ** *** ***** ******* *********** *************
    A U.S. programmer has posted encryption software on his website, just 
    daring the government to pick him off.  He's looking to be a test case.  
    Good for him.
    Fifteen algorithms are lined up as potential replacements for DES.  
    Counterpane's Twofish is one of them.  On 20-23 August, NIST held the First 
    AES Conference.  Twofish is now one of twelve remaining.
    Congressman Tauzin takes a hard line against the FBI's access to encryption 
    keys.  Tauzin chairs the House Commerce Committee's subcommittee on 
    telecommunications, so this matters.
    PGP adds support for X.509 certificates.  This will probably help them get 
    accepted as mainstream, but they still are not compatible with S/MIME.
    Pegging the Clueless Meter....  "With PCs 1,000 times more powerful than 
    they used to be, our encryption keys can and should be 1,000 times bigger 
    too. That means cryptokeys of at least 56,000 bits."
    Toni Patti, "Available right now: Uncrackable encryption, Dirt Cheap"
    ** *** ***** ******* *********** *************
                   Private Doorbell
    Last month I posted a quick reaction to Private Doorbell, a Cisco 
    key-recovery program, which was that it was the same old key-escrow 
    repackaged with a new name.  It seems my analysis was a bit hasty.
    Private Doorbell is an attempt to hack the government's key-escrow export 
    policy.  The goal is to export existing, unmodified, encrypting routers, 
    while at the same time satisfying the letter of the regulations.  What the 
    export regulations require is that there be an access point for 
    eavesdropping, not necessarily that the access be provided by releasing 
    keys.  Now by definition, encrypting routers have an unencrypted side and 
    an encrypted side.  If you want to eavesdrop, you can already eavesdrop on 
    the unencrypted side.  Administration functions are already built into 
    these routers; a network administrator can certainly respond to a court 
    order.  Hence, encrypting routers should be exportable, no modifications 
    Of course there's nothing stopping users from pre-encrypting with PGP or 
    S/MIME; that, Private Doorbell supporters argue, is not their problem.  And 
    there's no "key escrow"; the keys are already in the routers, encrypting 
    and decrypting traffic as before.
    This is actually pretty clever.  There are no modifications to the routers, 
    no special key-collection features or additional key management 
    infrastructure; the routers are doing what encrypted routers do anyway.  
    The FBI gets what it asked for (although not the no-warrant no-block 
    wiretaps Louis Freeh really wants), and it already can produce a warrant 
    and wiretap an ISP.  The only group that is pissed is NSA.
    The whole deal is a "policy initiative" based on the wording in Section 
    740.8(d)(1)(ii) of the EAR (Export Administration Regulations), which says 
    that "other recoverable encryption products" shall receive "favorable 
    consideration" for export.  The products all promise to provide a 
    configurable interface that lets encryption be controlled based on source 
    and destination addresses, and provide means to route plaintext traffic of 
    interest to a port that law enforcement can tap.  This is to address law 
    enforcement's concerns.  For NSA, they offer restrictions on their proposed 
    export licensing arrangements that would prevent sales (without an ordinary 
    BXA license review) to military and diplomatic agencies in a list of 
    Cisco got a pile of companies to submit similar applications 
    simultaneously, including Sun, 3Com, HP, and Bay Networks.  These were 
    filed July 12; the government has 90 days to respond.  It remains to be 
    seen how the Commerce Department (actually, the FBI, State Department, and 
    NSA) will respond, or what the companies will do if it doesn't.
    Cisco has been working on this since October 1997, and went public because 
    they felt that their export paperwork was being stalled by the NSA.  This 
    "stalling" seems to have been done in secret; Cisco says that no one in any 
    agency has questioned the legitimacy of their original filing.
    This is a legal/political strategy that we hadn't thought of: Split the law 
    enforcement and national security communities by offering to satisfy law 
    enforcement's problem (after pushing its desires back into the box defined 
    by the Constitution).  Then national security has to step out from behind 
    the FBI's skirts and acknowledge itself.  And the initiative tries to offer 
    what a national intelligence agency that's only concerned with diplomatic 
    and military traffic would need, so if they need more, they have to expose 
    those needs.
    This won't work for all encryption products (file encryptors, for example), 
    but it does work for a lot of communications products, especially 
    network-layer encryption products.  Depending on how they are implemented, 
    IPSec systems could sneak through this same loophole.  And that's without 
    the addition of any key-escrow functionality.
    ** *** ***** ******* *********** *************
      Corrections to 15 August 1998 CRYPTO-GRAM
    In my lead story on Deep Crack, I said that follow-on machines would cost 
    only $50K.  This turns out not to be true.  John Gilmore attributes the 
    incorrect fact to someone at EFF, who got the story wrong.  It has been 
    repeated ever since, so I am taking this opportunity to correct the record:  
    A second Deep Crack machine will cost about the same as the first.  Of 
    course, if someone were to spend time researching the efficiencies of brute 
    force machines, costs could probably come down significantly.
    Last month I mentioned a Wired News story where "the Pentagon's top civil 
    servant believes that no two people in the world have a 'God-given right' 
    to communicate in total secrecy."  Wired has since changed the news story.  
    This is the new lead paragraph:
    	The Pentagon's top civil servant said that no company has a 
    	"God-given right" to export powerful American data scrambling 
    	technology that would allow foreign nationals to communicate in 
    	total secrecy, according to information made public this week.
    The article contains the following retraction:
    	Editor's Note: The headline and first paragraph of this story have 
    	been corrected to better reflect the context of John Hamre's 
    	remarks regarding the export of powerful US encryption technology. 
    	In the original story, Hamre's comments regarding "no God-given 
    	right" were misrepresented as suggesting that no two people in the 
    	world had the right to communicate in total secrecy. Wired News 
    	regrets the error. 
    Apologies for promulgating an error.
    ** *** ***** ******* *********** *************
                 More on Biometrics
    This comment is from Tom Rowley, CEO of Veridicom:
    As always, your analysis is impeccable.  But I think it misses the real 
    value that biometrics offer.  I've noticed that most people trained in 
    security tend to ignore this value but it's very real.
    People like biometrics because they believe in them.  And, therefore, use 
    them.  And it's certainly true that a poor security system used all the 
    time is better than a "perfect" security system never used.
    When I think about people's attitudes to biometrics, I tend to draw 
    conclusions from signatures, as opposed to fingerprints, because signatures 
    have the most extensive use in real "security" applications.  People are 
    willing to accept fingerprints as valid authorization for very high value 
    transactions, even life and death, because they believe in them.  All of 
    the security flaws which you pointed out about signatures are true.  
    Nevertheless, they pervade the authorization infrastructure.  Their 
    non-repudiation character, which you correctly rebut, is nonetheless a fact 
    because users want it to be.
    I observe that this hunger for an understandable authentication mechanism 
    is so strong that a variety of higher level infrastructures are added by 
    the world to deal with improving the legitimacy of signatures, e.g. notary 
    public.  (I've always thought that the value of someone that neither of you 
    know certifying that you are who you say you are is fascinating.)
    Or the insistence on "originals" of signed documents on the presumption 
    that these will be more difficult to forge than copies.  Or a raised seal 
    over a signed passport photograph.
    This sort of psychological analysis of the value of signatures (and by 
    extension, fingerprints) for authentication may seem bizarre from a crypto 
    science standpoint but it's very acceptable to users.
    ** *** ***** ******* *********** *************
    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: Repent Security Incorporated [www.repsec.com]

    This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:04:22 PDT