[ISN] CRYPTO-GRAM, March 15, 1999

From: mea culpa (jerichoat_private)
Date: Wed Mar 17 1999 - 05:43:40 PST

  • Next message: mea culpa: "[ISN] Cracking the Code"

    Forwarded From: Bruce Schneier <schneierat_private>
                    March 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:
         Why the Worst Cryptography is in the Systems that Pass Initial Analysis
         Counterpane Systems -- Featured Research
         The Doghouse -- Motorola's MDC-4800 Police Data Terminal
         Security Hole in IE/Outlook and Office
         AES News
         Counterpane Systems News
         RSA-140 Factored
         Comments from Readers
    ** *** ***** ******* *********** *************
    Why the Worst Cryptography is in the Systems that Pass Initial Analysis
    Imagine this situation: An engineer builds a bridge.  It stands for a day,
    and then collapses.  He builds another.  It stands for three days, and then
    collapses.  Then, he builds a third, which stands for two weeks but
    collapses during the first rainstorm.  So he builds a fourth.  It's been
    standing for a month, and has survived two rainstorms.  Do you believe this
    fourth bridge is strong, secure and safe?  Or is it more likely just
    another accident waiting to happen?
    As bizarre as it may seem, this kind of design process happens all the time
    in cryptography, a field that is full of people who love to design their
    own algorithms and  protocols.  With so many aspiring cryptanalysts out
    there, however, there's bound to be a lot of weak designs. The problem is
    this:  Anyone, no matter how unskilled, can design an algorithm that he
    himself cannot break.  Though a competent cryptanalyst can break most of
    this stuff after a short review, the rest of it survives, and in most cases
    is never looked at again (especially outside the military world).  But just
    because an algorithm survives an initial review is no reason to trust it.
    I had a client once who desperately wanted to design his own encryption
    algorithm.  He had no cryptographic training, no experience analyzing other
    algorithms.  He was a designer, he said, not an analyst.  So Counterpane
    did his analysis for him, and we broke his algorithm in a day.  He fixed it
    and sent it back, and we broke it in two days.  He fixed it and sent it
    back again, and we broke it again.  Finally, the fourth version of his
    algorithm resisted our attempts at cryptanalysis...at least for the full 40
    hours our contract specified.  The client was happy; finally, he had a
    secure algorithm.
    In a way, the client is worse off than he was before he started.  At first,
    he had an algorithm that was obviously flawed.  If he included it in a
    product, he would have no analysis to show potential buyers and no
    responses to questions about its security. If a competent cryptographer
    looked at the algorithm -- either because it was made public or by
    reverse-engineering the code -- he could easily break it. 
    But after we went through the break-fix-break cycle a few times, he ended
    up with an algorithm that was not obviously flawed.  He had a written
    analysis showing that we could not break it within 40 hours.  Even if a
    competent cryptographer looked at the algorithm for a few days, he probably
    would not find a problem.  Unless the algorithm was being used in some
    high-profile application -- cellular telephony, a Microsoft product, an
    Internet standard -- it might never be looked at any more closely.  But
    that doesn't mean that it's not still flawed, or that it can't be broken
    given enough time and resources. 
    This is not to say that the break-fix-break cycle is completely flawed.
    It's not.  In fact, it's how most good cryptographic systems got to be
    good.  Consider IPSec, the Internet IP security protocol.  It was designed
    by committee, out in the open and in public, and from the start has been
    the subject of considerable public scrutiny.  Everyone knew it was an
    important protocol, and people spent a lot of effort trying to get it
    right.  Things were proposed, broken and then modified.  Versions were
    codified and analyzed.  Debates raged over its security merits,
    performance, ease-of-implementation, upgradability and use.  Then, in
    November 1998, a pile of RFCs were published, the next in a series of steps
    to make IPSec an Internet standard.  It is impossible to mimic this kind of
    analysis with a proprietary system.  Still, many companies try, which begs
    the question: Why try to develop new algorithms and protocols at all?
    They're generally not faster, or smaller, or more efficient.  They're just
    Unfortunately, in the world of cryptography, different is bad.
    Cryptography is at its best when it is conservative, and the conservative
    approach is to choose an algorithm that has already been analyzed.  The
    admonition not to put all your eggs in one basket does not apply in this
    case.  The security of a system is the security of its weakest component,
    since the weakest component breaks the entire system.  In cryptography,
    there is security in following the crowd.  A home-grown algorithm can't
    possibly be subjected to the hundreds of thousands of hours of analysis
    that DES and triple-DES have been subjected to.  A company just can't
    mobilize the resources that are being brought to bear against the AES
    candidates, or the IPSec Internet security protocol.  No one can duplicate
    the confidence that RSA offers after 20 years of cryptanalytic review.  A
    standard security review, even by competent cryptographers, can only prove
    insecurity; it can never prove security.  By following the pack you can
    leverage the cryptanalytic expertise of the worldwide community, not just a
    handful of hours of a consultant's time.
    This article originally appeared in the March 1999 issue of Information
    Security magazine <http://www.infosecuritymag.com>.
    ** *** ***** ******* *********** *************
       Counterpane Systems -- Featured Research
    "Performance Comparison of the AES Submissions"
    B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, and N. Ferguson
    2nd AES Candidate Conference, March 1999, to appear.
    In this paper, we compare the performance of the leading AES candidates on
    a variety of common platforms: 32-bit CPUs, 64-bit CPUs, cheap 8-bit smart
    card CPUs, and dedicated hardware.  For each platform, we first make some
    general observations on the performance issues of the platform, then
    compare the various AES candidates, and finally look at the specific issues
    for each of the candidates.
    ** *** ***** ******* *********** *************
     The Doghouse -- Motorola's MDC-4800 Police Data Terminal
    There's a Windows program that decodes the police car mobile data terminal
    transmissions.  If you thought listening in on police radio frequencies was
    interesting, you should see what comes over on those data transcripts.
    Motorola's "encryption" wasn't designed for privacy, it's more like a
    checksum for transmission integrity. Basically, it's XOR.
    The software is free, although there is this helpful notice on the Web
    site:  "Decoding MDT transmissions may be illegal in some countries, you
    may want to check the laws for your country before using this program."
    ** *** ***** ******* *********** *************
        Security Hole in IE/Outlook and Office
    Here's further proof, if you needed it, that Microsoft prefers to treat
    security holes as a public relations problem, rather than fixing the actual
    problem.  Microsoft recently announced a prompt fix for a security hole in
    IE4.0 and Word 97.  Turns out, it wasn't so prompt after all.
    In December 1997, David Foster discovered a security hole in Office 97.
    This bug allows any Web page to contain executable code that will run
    without warning on the user's machine.  For anyone who knows Word and VBA
    (Word 97's macro language), the problem is obvious.
    Foster went to the bug reporting Web pages for Internet Explorer and Word,
    and reported the problem.  There was no response from Microsoft.  In late
    1998, he discovered that not only had MS still not fixed the problem in
    Word 97, but the bug also existed in the beta version of Word 2000.  He
    posted a further message to Microsoft, and received the following:
    "Microsoft appreciates your input regarding this issue, however in lieu of
    modern technology being what it is, we all need to be personally
    responsible for knowing what we are downloading off the internet."  In case
    it's not immediately obvious, this is arrant nonsense.
    It wasn't until Woody Leonhard, Word guru and Office 97 iconoclast, heard
    about the problem and threatened to publish particulars of the security
    hole in the next issue of "Woody's Office Watch," with a readership of
    140,000, that Microsoft finally did something.  With that incentive,
    Microsoft had a patch available on their Web site within days.
    Patch URLs: 
    David Foster's story of the bug: http://www.panix.com/~dfoster/sec/chrono.html
    Woody's Office Watch article: http://www.wopr.com/wow/wowv4n3.html
    ** *** ***** ******* *********** *************
                       AES News
    For those who haven't been paying attention, the AES (Advanced Encryption
    Standard) will be the eventual replacement for DES.  It's a 128-bit block
    cipher with key lengths of 128, 192, and 256 bits.  And there's a
    competition going on right now to determine what it is.  (For details, see:
    Step 1 was the submission of algorithms: NIST received 15 last June.  Step
    2 is the solicitation of public comments on the algorithms.  To that end,
    NIST is hosting an AES Candidate Conference in Rome the week of March 22nd.
     NIST received 28 submissions to present at the conference, and they
    accepted most of them.
    The papers are available on the NIST Web site.  No real suprises, but if
    you can't get to Rome and are interested, take a look.
    ** *** ***** ******* *********** *************
    The Palm VII (the on-line capable version of the PalmPilot) will come with
    public-key cryptography built in.  Certicom managed to convince them that
    elliptic curve public-key cryptography is the way to go.  I haven't seen
    this yet, but I'm hopeful it will be good.
    NIST exports strong crypto.  Cool!  NIST went and did it; they exported
    strong cryptography to the world electronically.  See the appendix to:
    It's sort-of good news.  On March 4th, Tony Blair told a bunch of computer
    executives that the government will not tie key escrow requirements with
    the licensing of CAs.  At least some countries are listening.  But then he
    gave everyone three weeks to come up with a better alternative -- whatever
    "better" means in this context -- or he just might do it anyway.
    While the debate rages over Intel's unique ID and its plans to use it for
    identification over the Internet, the New York Times reports that Microsoft
    uses the unique ID on the network card (or generates a substitute) and
    secretly inserts it into MS Word and Excel documents for purposes of
    Microsoft announced that they will fix it.
    Hey, the U.S. has a privacy czar!  The question is whether or not he'll do
    anything useful.
    All right, so I think it's funny.
    The UK Consultation Document on the proposed e-commerce legislation is now
    available on the Web at http://www.dti.gov.uk/CII/elec/consfn1.pdf.
    Summary document: http://www.dti.gov.uk/CII/elec/elec_com.html
    Comments are required by Thursday 1 April.
    The Pentagon is claiming that cyber terrorists are launching sophisticated,
    coordinated attacks -- as many as 100 per day -- on military computers.
    Honestly, this sounds like a bid for more funding to me.
    Meanwhile, Computer Security Institute and the FBI last week released
    survey results showing cyber crooks caused more than $100 million in losses
    last year. 
    If this keeps up I won't have to do any more marketing.
    ** *** ***** ******* *********** *************
              Counterpane Systems News
    Bruce Schneier is going to give the keynote speech at the fifth annual
    Public-Key Solutions (PKS) conference in Toronto.  The conference is April
    12-14 1999 at the Four Seasons hotel, and Bruce's talk will be given at
    9:00 AM on the 12th.
    Slides from the talk are available in Powerpoint format at:
    Counterpane Systems is presenting four talks at the Second AES Candidate
    	New Results on the Twofish Encryption Algorithm
    	Performance Comparison of the AES Submissions
    	Cryptanalysis of FROG
    	Key Schedule Weakness in SAFER+
    and one talk at the Fast Software Encryption conference:
    	Mod n Cryptanalysis, with Applications against RC5P and M6
    This is all happening in Rome, the week of March 22nd.
    ** *** ***** ******* *********** *************
                  RSA-140 Factored
    A new factoring record has been set.  Herman J.J. te Riele, and his group
    at CWI in Amsterdam, announced that they have factored a 140-digit
    (465-bit) number.  This number was one of the RSA challenge numbers
    (RSA-140): the product of two large primes and the kind of number used in
    the RSA cryptosystem.
    The amount of work is estimated to be about 2000 mips years.  (A "mips
    year" is the computing power of a one mips computer running for a year.  A
    DEC 11/780 is a one mips machine.  A top-of-the-line Pentium II is about a
    200 mips machine.  The ASCI Red TFLOPS supercomputer, recently installed in
    Sandia National Laboratory -- presumably for nuclear blast simulations --
    with its 9216 Pentium Pro processors, is about a 1.8-million mips machine.)
    They used an algorithm called the Number Field Sieve, the same algorithm
    used to factor the 130-digit RSA challenge number in 1000 mips years.  And
    given what they learned on this project, if they had to start over again
    they estimate that they could have factored RSA-150 in 1500 mips years, and
    RSA-130 in 500 mips years.
    What does this mean for the security of RSA?  How does it affect 512-bit
    keys?  1024-bit keys?  No one is sure.  It's tricky to extrapolate these
    work efforts to larger key sizes.  Theoretically, increasing the number of
    decimal digits by three or four doubles the computing effort required to
    factor the number by the method they used).  So RSA-150 would require about
    six times as much computing effort as we spent on RSA-140.
    Larger numbers are much harder to extrapolate.  Arjen Lenstra often points
    out that the various steps used in the Number Field Sieve don't scale as
    you'd expect, and that many of these techniques just won't work for larger
    number sizes.  It's not simply a matter of raw mips, you need enough memory
    to hold the intermediate results.  While this is true, I am more optimistic
    about the ability to tweak algoritms.  Just based on this one project, they
    estimate that they could have cut the work to factor RSA-140 by 25%.  Who
    knows what they will learn next time, or the time after that.
    Factoring has been getting easier.  It's been getting easier faster than
    anyone has anticipated.  I see four reasons why this is so:  
    	Computers are getting faster.
    	Computers are better networked.
    	The factoring algorithms are getting more efficient.
    	Fundamental advances in mathematics are giving us better 
    	  factoring algorithms.
    Using current mathematics and technology, it is impossible to even consider
    factoring a 1024-bit number.  I'm not willing to make any hard predictions
    about tomorrow.  
    Menewhile, the group's next project is a 155 digit (512-bit) RSA number.
    They expect to finish by the end of the year.
    Some info on the factoring research at CWI can be found at:
    Another intersting URL is Paul Zimmermann's:
    who has also contributed to the RSA-140 record.  (Note that this is NOT
    Phil Zimmerman.)
    ** *** ***** ******* *********** *************
               Comments from Readers
    From: John Washburn <johnwashburnat_private>
    Subject: UL for Crypto?
    I very much enjoyed my February 1999 Crypto-Gram.  Your statement that
    Cryptography as a commercial product is like pharmaceuticals at the the
    turn of the century is true.  Commercial cryptography is also similar to
    electrical power and electrical appliance industries at the turn of the
    century.  One industry went the route of Underwriter's Laboratory.  The
    other industry lobbied for the FDA.  Another industry (telephone) simply
    went for the monopoly.  Now with at least 75 years of data (FDA), I would
    argue the UL route has proven the best.
    The incidence of accidental (or deliberate) electrocution is statistically
    insignificant.  The standards for electrical appliances have steadily
    increased.  I.e. a product that passed the UL standards in 1945 would
    likely fail the 1995 standards.
    The FDA kills (or more precisely allows to die) more than 25,000 people per
    year.  This does not include drug overdoses, misfilled prescriptions,
    incorrect prescriptions or unforseen drug interactions.  The 25,000 is the
    most conservative estimate of people who die from unavailable (non FDA
    approved) medical treatment.  This is simply because the FDA does not care
    how you die, as long as death is not by an FDA approved method.
    Given the fork in the road faced by the cryptography industry how can the
    cryptographic industry opt for the Underwriter's Laboratory model.  The
    only way I see is insurance / bonding.  
    For example:  I sell crypto and submit my crypto to Wausau Insurance for
    bonding.  Wausau Insurance inspects my system.  If I balk at their
    inspection requirements I get no bond. After inspection Wausau Insurance
    quotes me a premium.  If the premium is too high (system is too risky for
    Wausau Insurance), I balk.  After I pay my premium, I can now add to my
    sales pitch, "an insured cryptographic product from a bonded crytographic
    The bond is a variation of liability insurance.  I picked Wausau Insurance
    because it specializes in business liability insurance and is close to you
    in Wausau Wisconsin.  Wausau Insurance does not provide such a product at
    this time.  Any liability company would have done for my example.  
    My point is an insurance company is cautious enough to issue a bonding
    (liability) policy only after review by third parties or internal experts.
    In turn, the insurance company's reputation and finacial stake would make
    the claim of strong crypto easier to believe.  This would be true even if
    the review of the commercial crypto was done complete under NDA's.  Also an
    insurance company would be far more sensitive to implementation, use and
    system integration issues.  Netscape is a prime example where the crypto
    was good, but the system as a whole sucked (poor PRNG for session key
    Also having a multi-billion dollar industry that is already adept at
    lobbying in many countries lobbying for strong crypto as well is not a Bad
    Thing.  For the insurance company bonding weak crypto is equivalent to
    writing a series of claim checks.
    Note from Bruce:  For a contrary point of view, see Tan's essay on why the
    Underwriter's Laboratory model would NOT work for cryptography and computer
    security products:  http://www.l0pht.com/cyberul.html.  I agree with Tan.
    ** *** ***** ******* *********** *************
    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
    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:21:06 PDT