18 March 1999
CRYPTO-GRAM
March 15, 1999
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) 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
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
different.
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.
http://www.counterpane.com/aes-performance.html
** *** ***** ******* *********** *************
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."
http://www.geocities.com/ResearchTriangle/Facility/7646/
** *** ***** ******* *********** *************
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:
http://officeupdate.microsoft.com/downloaddetails/wd97sp.htm
http://officeupdate.microsoft.com/downloaddetails/fm2paste.htm
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:
http://www.counterpane.com/crypto-gram-9805.html#aes.)
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.
http://csrc.nist.gov/encryption/aes/round1/conf2/aes2conf.htm
** *** ***** ******* *********** *************
News
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.
http://www.zdnet.com/pcweek/stories/jumps/0,4270,383613,00.html
NIST exports strong crypto. Cool! NIST went and did it; they
exported
strong cryptography to the world electronically. See the appendix to:
http://csrc.nist.gov/encryption/aes/round1/conf2/papers/baudron2.pdf
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.
http://news.bbc.co.uk/hi/english/business/the_economy/newsid_290000/290902.stm
http://news.bbc.co.uk/hi/english/sci/tech/newsid_290000/290964.stm
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
identification.
http://www.nytimes.com/library/tech/99/03/biztech/articles/03privacy.html
Microsoft announced that they will fix it.
http://www.zdnet.com/zdnn/stories/news/0,4586,2221330,00.html
http://www.wired.com/news/news/technology/story/18315.html
Hey, the U.S. has a privacy czar! The question is whether or not he'll
do
anything useful.
http://www.zdnet.com/zdnn/stories/news/0,4586,2221341,00.html
All right, so I think it's funny.
http://www.nottingham.ac.uk/~ppzmajoc/filks/customs.html
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.
http://www.zdnet.com/zdnn/stories/news/0,4586,2220773,00.html
Meanwhile, Computer Security Institute and the FBI last week released
survey results showing cyber crooks caused more than $100 million in losses
last year.
http://www.gocsi.com/prelea990301.htm
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.
http://www.certicom.com/pks99/index2.htm
Slides from the talk are available in Powerpoint format at:
http://www.counterpane.com/crypto-flaws.ppt
Counterpane Systems is presenting four talks at the Second AES Candidate
Conference:
New Results on the Twofish Encryption Algorithm
http://www.counterpane.com/twofish-aes.html
Performance Comparison of the AES Submissions
http://www.counterpane.com/aes-performance.html
Cryptanalysis of FROG
http://www.counterpane.com/frog.html
Key Schedule Weakness in SAFER+
http://www.counterpane.com/safer.html
and one talk at the Fast Software Encryption conference:
Mod n Cryptanalysis, with Applications against RC5P and M6
http://www.counterpane.com/mod3.html
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:
http://dbs.cwi.nl/cwwwi/owa/cwwwi.print_projects?ID=12
Another intersting URL is Paul Zimmermann's:
http://www.loria.fr/~zimmerma/records/factor.html
who has also contributed to the RSA-140 record. (Note that this is
NOT
Phil Zimmerman.)
** *** ***** ******* *********** *************
Comments from
Readers
From: John Washburn <johnwashburn@usa.net>
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
company".
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
generation).
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-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 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.
http://www.counterpane.com/
Copyright (c) 1999 by Bruce Schneier