From: Bruce Schneier [mailto:[log in to unmask]]
Sent: 15 October 2002 23:50
To: [log in to unmask]
Subject: CRYPTO-GRAM, October 15, 2002
CRYPTO-GRAM
October 15, 2002
by Bruce Schneier
Founder and CTO
Counterpane Internet Security, Inc.
[log in to unmask]
<http://www.counterpane.com>
A free monthly newsletter providing summaries, analyses, insights, and
commentaries on computer security and cryptography.
Back issues are available at
<http://www.counterpane.com/crypto-gram.html>. To subscribe, visit
<http://www.counterpane.com/crypto-gram.html> or send a blank message
to [log in to unmask]
Copyright (c) 2002 by Counterpane Internet Security, Inc.
** *** ***** ******* *********** *************
In this issue:
National Strategy to Secure Cyberspace
More on AES Cryptanalysis
Crypto-Gram Reprints
The Doghouse: GreatEncryption
News
Counterpane News
One-Time Pads
Comments from Readers
** *** ***** ******* *********** *************
National Strategy to Secure Cyberspace
On 18 September, the White House officially released its National
Strategy to Secure Cyberspace. Well, it didn't really release it on
that date; versions had been leaking here and there for a while. And
it really isn't a national strategy; it's just a draft for
comment. But still, it's something.
No, it isn't. The week it was released I got all sorts of calls from
reporters asking me what I thought of the report, whether the
recommendations made sense, and why certain things were omitted. My
primary reaction was: "Who cares? It doesn't matter what the report says."
For some reason, Richard Clarke continues to believe that he can
increase cybersecurity in this country by asking nicely. This
government has tried this sort of thing again and again, and it never
works. This National Strategy document isn't law, and it doesn't
contain any mandates to government agencies. It has lots of
recommendations. It has all sorts of processes. It has yet another
list of suggested best practices. It's simply another document in my
increasingly tall pile of recommendations to make everything
better. (The Clinton Administration had theirs, the "National Plan for
Information Systems Protection." And both the GAO and the OMB have
published cyber-strategy documents.) But plans, no matter how detailed
and how accurate they are, don't secure anything; action does.
And consensus doesn't secure anything. Preliminary drafts of the plan
included strong words about wireless insecurity, which were removed
because the wireless industry didn't want to look bad for not doing
anything about it. Preliminary drafts included a suggestion that ISPs
provide all their users with personal firewalls; that was taken out
because ISPs didn't want to look bad for not already doing something
like that.
And so on. This is what you get with a PR document. You get lots of
varying input from all sorts of special interests, and you end up with
a document that offends no one because it demands nothing.
The worst part of it is that some of the people involved in writing the
document were high-powered, sincere security practitioners. It must
have been a hard wake-up call for them to learn how things work in
Washington. You can tell that a lot of thought and effort went into
this document, and the fact that it was gutted at the behest of special
interests is shameful...but typical.
So now everyone gets to feel good about doing his or her part for
security, and nothing changes.
Security is a commons. Like air and water and radio spectrum, any
individual's use of it affects us all. The way to prevent people from
abusing a commons is to regulate it. Companies didn't stop dumping
toxic wastes into rivers because the government asked them
nicely. Companies stopped because the government made it illegal to do so.
In his essay on the topic, Marcus Ranum pointed out that consensus
doesn't work in security design. Consensus security results in some
good decisions, but mostly bad ones. By itself consensus isn't
harmful; it is the compromises that are almost always harmful, because
the more parties you have in the discussion, the more interests there
are that conflict with security. Consensus doesn't work because the
one crucial party in these negotiations -- the attackers -- aren't
sitting around the negotiating table with everyone else. "And the
hackers don't negotiate anyhow. In other words, it doesn't matter if
you achieve consensus...; whether it works or not is subject to a
different set of rules, ones over which your wishes exercise zero control."
If the U.S. government wants something done, they should pass a
law. That's what governments do. It's like pollution; don't mandate
specific technologies, legislate results. Make companies liable for
insecurities, and you'll be surprised how quickly things get more
secure. Leave the feel-good PR activities to the various industry
trade organizations; that's what they're supposed to do.
The draft report:
<http://www.whitehouse.gov/pcipb/>
News articles:
<http://www.bangkokpost.com/021002_Database/02Oct2002_dbcol10.html>
<http://www.infoworld.com/articles/hn/xml/02/09/18/020918hnnatcyber.xml?
s=IDGNS>
<http://www.computerworld.com/securitytopics/security/story/0,10801,7444
9,00.html>
<http://www.computerworld.com/governmenttopics/government/story/0,10801,
74353,00.html>
<http://www.news.com.com/2102-1023-958545.html>
Marcus Ranum's essay:
<http://www.tisc2002.com/newsletters/414.html>
Other essays:
<http://www.infowarrior.org/articles/2002-11.html>
<http://online.securityfocus.com/columnists/110>
<http://online.securityfocus.com/news/677>
<http://www.zdnet.com/anchordesk/stories/story/0,10738,2882094,00.html>
<http://www.avolio.com/columns/21-SecuringCyberspace.HTML>
** *** ***** ******* *********** *************
More on AES Cryptanalysis
I can say with certainty that no one knows for certain if XLS can break
Rijndael or Serpent or anything else. Actually, I can say something
stronger: no one has produced an actual demonstration of XLS breaking
even a simplified version of Rijndael or Serpent or anything
else. This makes a lot of people skeptical.
Demonstrations are important. When differential cryptanalysis finally
broke the full 16-round DES, the authors did not demonstrate the
attack. Even though the attack was faster than brute force, it was
still too complicated to demonstrate practically. But the authors did
demonstrate the attack against reduced-round variants of DES, and
against other algorithms. The community believed that the attack
worked because the techniques had been demonstrated multiple times and
the theory behind the techniques were well understood.
The XLS techniques have not been demonstrated yet. A number of
respectable cryptographers, whose opinions I value highly, don't think
the techniques work. Don Coppersmith has published a note on the
topic. And T. Moh has a Web page about this. (To be fair, T. Moh and
Nicolas Courtois have an ongoing diagreement about another
crypto-related topic. But while that certainly affects the
motivations, it doesn't necessarily invalidate the math.)
I know that several groups are working on the techniques, and if they
work one of those groups should be able to demonstrate something, on
something, soon. I'll provide additional information when I learn of it.
Coppersmith's comment:
<http://aes.nist.gov/aes/FMPro?-token=S021&-DB=discufm.fp3&-lay=detail&-
Format=Detail.htm&SubIDMatch=S021&-op=cn&ActiveMessages=x&-Skip=1&-Max=1
&-sortfield=ThreadID&-sortorder=descending&-sortfield=MessageID&-sortord
er=ascending&-LOP=and&-Find>
Sorry about the ridiculous link. The substance of the note is in the
"Letters from Readers" column below, or here's a referral link.
<http://makeashorterlink.com/?K27C515E1>
Moh's site:
<http://www.usdsi.com/aes.html>
My essay on XLS from last month:
<http://www.counterpane.com/crypto-gram-0209.html#1>
** *** ***** ******* *********** *************
Crypto-Gram Reprints
Crypto-Gram is currently in its fifth year of publication. Back issues
cover a variety of security-related topics, and can all be found on
<http://www.counterpane.com/crypto-gram.html>. These are a selection
of articles that appeared in this calendar month in other years.
Cyberterrorism:
<http://www.counterpane.com/crypto-gram-0110.html#1>
Dangers of Port 80
<http://www.counterpane.com/crypto-gram-0110.html#9>
Semantic Attacks:
<http://www.counterpane.com/crypto-gram-0010.html#1>
NSA on Security:
<http://www.counterpane.com/crypto-gram-0010.html#7>
So, You Want to be a Cryptographer:
<http://www.counterpane.com/crypto-gram-9910.html#SoYouWanttobeaCryptogr
apher>
Key Length and Security:
<http://www.counterpane.com/crypto-gram-9910.html#KeyLengthandSecurity>
Steganography: Truths and Fictions:
<http://www.counterpane.com/crypto-gram-9810.html#steganography>
Memo to the Amateur Cipher Designer:
<http://www.counterpane.com/crypto-gram-9810.html#cipherdesign>
** *** ***** ******* *********** *************
The Doghouse: GreatEncryption
It's got all the snake-oil warning signs: a novel encryption algorithm
that isn't discussed, an obvious ignorance of cryptography, a patent in
progress, and a bogus contest. Sample sentences from the Web site:
"Keys 2,000-4,000 characters long are recommended for key strength that
is far greater than that of other software programs now sold." And:
"Software with a key strength of 109^4000 + 109^3999 + ... 109^1." Egads.
The funniest bit is when they claim that their encryption is fast,
"encrypting about 5,000 plaintext characters/second on an average
PC." Assume the average PC is 500 MHz; that translates to about
100,000 clock cycles per byte (ASCII character) encrypted. AES
encrypts at 20 clock cycles per byte; there are stream ciphers that are
over twice as fast. That means AES is 5,000 times faster than
GreatEncryption.
The Web site says: "Permission to export Great Encryption to the rest
of the world, except for terrorist states, is being sought." If we're
lucky, they'll get permission to export it ONLY to terrorist states.
<http://www.greatencryption.com/>
** *** ***** ******* *********** *************
News
Good article on the myth of cyberterrorism:
<http://online.securityfocus.com/columnists/111>
And more silly hype:
<http://www.theregus.com/content/6/26414.html>
64-bit key brute-forced:
<http://slashdot.org/article.pl?sid=02/09/26/1449257&mode=thread&tid=93>
Interesting Q&A with Whitfield Diffie, conducted by Richard Thieme:
<http://www.cisomagazine.com/2002/aug/qa.shtml>
Security vs. Open Society:
<http://www.osopinion.com/perl/story/19416.html>
Can Software be Certified?
<http://www.businessweek.com/technology/content/oct2002/tc2002101_6896.htm>
This is about as pathetic as you can get. The Federal Trade Commission
has decided that computer security needs a mascot, kind of like Smokey
the Bear. So we now have Dewey the Turtle, who's here to promote
secure computing for everyone. "When you see the ping of death, duck
and cover."
<www.ftc.gov/bcp/conline/edcams/infosecurity/index.html>
A Russian hacker was sentenced to three years in prison here in the
United States for breaking computer crime laws here. It's an
interesting story. He was in Russia at the time, and broke no laws in
his country. However, the U.S. prosecution broke Russian laws to
collect evidence against him. The judge agreed with the FBI's
assertion that Russian law didn't apply to them. Isn't international
jurisprudence fun?
<http://in.tech.yahoo.com/021005/137/1w2bq.html>
Secure software: will we ever see it?
<http://www.computerworld.com/securitytopics/security/story/0,10801,7476
4,00.html>
Insiders are the biggest computer security threat:
<http://www.pcworld.com/news/article/0,aid,105528,00.asp>
** *** ***** ******* *********** *************
Counterpane News
It was an excellent quarter for Counterpane. Sales up 100% over last
year, a bunch of new resellers, way more monitoring, that sort of
thing. We'll have a press release with the details real soon now.
Schneier is speaking at SMAU 2002 in Milan on 25 Oct:
<http://www.smau.it/smau2002/english/docs/flash.html>
Schneier is speaking at the Symposium on Privacy & Security in Zurich
on 30 and 31 October:
<http://www.privacy-security.ch/english/programm/default.htm>
Schneier is speaking at Comdex in Las Vegas on 18 November:
<http://www.comdex.com/fall/>
** *** ***** ******* *********** *************
One-Time Pads
It's a meme that never seems to go away. Every time I write about this
cryptanalytic result, or the insecurity of that system, someone starts
crowing about one-time pads. "Every other cryptographic algorithm is
based on some assumption, and one-time pads are the only provably
secure system," they say. "They're the only safe algorithm," they
say. "They're the future," they say.
Well, they're wrong. And step, by step, I will explain why. (Parts of
this essay are taken from my book "Secrets and Lies.")
One-time pads are the simplest of all algorithms, and were invented
early on in the 20th century. The basic idea is that you have a pad of
paper with a bunch of randomly chosen key letters, the same size as the
message, on it. You add one key letter to each plaintext letter, and
never repeat the key letters. (That's the "one-time" part.) For
example, assume the message is IT and the pad letters are CM. You add
I (9) to C (3) to get L (12), or T (20) to M (13) to get G (7). (20 +
13 = 7 mod 26.) Then you burn the paper afterwards. The receiver
reverses the process using his pad of paper, and then burns the key
letters when he's done. This system works with any alphabet, including
a binary one.
One-time pads are the only provably secure cryptosystem. Because the
key is the same size as the plaintext, every possible plaintext is
equally likely. With different keys, the ciphertext DKHS could decrypt
to SELL, STOP, BLUE, or WFSH. With a normal algorithm, such as DES or
AES or even RSA, you can tell which key is correct because only one key
can produce a reasonable plaintext. (Formally, the message size needed
is called the "unicity distance." It's about 19 ASCII bytes for an
English message encrypted with a cipher with a 128-bit block. With a
one-time pad, the unicity distance approaches infinity and it becomes
impossible to recognize plaintext. This is the security
proof.) Because a one-time pad's key is the same size as the message,
it's impossible to tell when you have the correct decryption.
This is the only provably secure cryptosystem we know of.
It's also pretty much useless. Because the key has to be as long as
the message, it doesn't solve the security problem. One way to look at
encryption is that it takes very long secrets -- the message -- and
turns them into very short secrets: the key. With a one-time pad, you
haven't shrunk the secret any. It's just as hard to courier the pad to
the recipient as it is to courier the message itself. Modern
cryptography encrypts large things -- Internet connections, digital
audio and video, telephone conversations, etc. -- and dealing with
one-time pads for those applications is just impracticable.
If you think you know how to do key management, but you don't have much
confidence in your ability to design good ciphers, a one-time pad might
make sense. We're in precisely the opposite situation, however: we
have a hard time getting the key management right (partly because most
applications won't really support couriers with briefcases handcuffed
to their wrists, Marines with rifles guarding the room with the
encryption equipment in it, or thermite charges available for
physically destroying storage media before the bad guys get past the
Marines with rifles guarding the encryption equipment), but we're
pretty confident in our ability to build reasonably strong
algorithms. It's just not the weak point in our systems.
What a one-time pad system does is take a difficult message security
problem -- that's why you need encryption in the first place -- and
turn it into a just-as-difficult key distribution problem. It's a
"solution" that doesn't scale well, doesn't lend itself to mass-market
distribution, is singularly ill-suited to computer networks, and just
plain doesn't work.
The exceptions to this are generally in specialized situations where
simple key management is a solvable problem and the security
requirement is timeshifting. In these situations, the problem isn't
transporting the bits securely, but transporting the bits securely at
the time the message is generated. Securing the bits beforehand is
easy. And there are historical examples of one-time pads being used
successfully, in specialized circumstances. Russian spies used pencil
and paper one-time pads to communicate. (The NSA broke the system
because the Russians reused the same one-time pads. Oops.) An early
Teletype hotline between Washington and Moscow was encrypted using a
one-time pad system. One-time pads were also used successfully in WWII
by the English; spies in locations with radios but no other encoding
equipment were given pads printed on silk, and were able to encode
messages for transmission faster and more securely than by previous
methods involving memorized poetry.
Those examples used real one-time pads. Generally, products that claim
to use a one-time pad actually don't. My guess is that the engineers
quickly realize that they can't possibly implement a one-time pad, so
they use the output of a stream cipher and call that a one-time-pad
generator, or a virtual one-time pad, or almost a one-time pad, or some
other marketing-speak. It's not a one-time pad. The security proof
completely fails when you use a stream cipher.
On the other hand, if you ever find a product that actually uses a
one-time pad, it is almost certainly unusable and/or insecure.
So, let me summarize. One-time pads are useless for all but very
specialized applications, primarily historical and non-computer. And
almost any system that uses a one-time pad is insecure. It will claim
to use a one-time pad, but actually use a two-time pad (oops). Or it
will claims to use a one-time pad, but actually use a steam cipher. Or
it will use a one-time pad, but won't deal with message
re-synchronization and re-transmission attacks. Or it will ignore
message authentication, and be susceptible to bit-flipping attacks and
the like. Or it will fall prey to keystream reuse attacks. Etc.,
etc., etc.
One-time pads may be theoretically secure, but they are not secure in a
practical sense. They replace a cryptographic problem that we know a
lot about solving -- how to design secure algorithms -- with an
implementation problem we have very little hope of solving. They're
not the future. And you should look at anyone who says otherwise with
deep and profound suspicion.
** *** ***** ******* *********** *************
Comments from Readers
From: "Christian Hampson" <[log in to unmask]>
Subject: Your name on Reveal's list
Regarding the reason for the inclusion of your name and Rabbi
Schneerson on the list for Reveal, the term "crypt" is considered to be
an occult word. Your name is highly associated with
cryptography. Also, Avi Schneier is associated with Tai Chi in New
York and Arthur Schneier is part of the International Center for
Religion and Diplomacy. As for Schneerson, I also noticed such words
as "Judeo," "Hasidi," and "Kaballah" as being occult. It appears that
anything other than Civil Religion is to be considered occult, as
"Allah," "Chant," "Mahayana," "Sabat," "Ritual," "Prophet," and
"Resurrection" are also included on the list. Perhaps you should feel
honored by your inclusion.
From: Douglas Davidson <[log in to unmask]>
Subject: Your name on Reveal's list
I just wanted to point out that this might not necessarily be
illegitimate. If this organization is using some form of statistical
filtering (something along the lines of that described for spam
filtering in <http://www.paulgraham.com/spam.html>), then it is quite
possible that their word list is derived entirely automatically from
the analysis of some corpus. In that case, there may not be any way
for a human to explain the presence of a particular word; it is there
simply because it occurs in the corpus -- not necessarily frequently,
either. In Graham's case, for example, the resulting word lists were a
surprise even to Graham.
Unfortunately, if AntiChildPorn is using some technique of this sort,
it becomes difficult to validate their filters. In the case of spam
filtering, every user naturally has a sufficiently large corpus of spam
and non-spam e-mail available to construct their own filters. However,
not everyone has a large corpus of pornographic, racist, or similar
material available. Unless AntiChildPorn makes their corpus available
for examination -- which they probably are not willing to do -- it
would be difficult to evaluate their techniques without assembling a
large corpus yourself and seeing what their software says about it.
If AntiChildPorn is doing what they say they are doing, then one might
make a guess that anti-Semitic writings occasionally include the names
of rabbis. If they are not doing what they say they are doing, then
perhaps they have fed Phrack or something similar into the
mix. Without further evidence there is no way to tell.
From: "Don Coppersmith" <[log in to unmask]>
Subject: XLS Against Rijndael
Your recent "Crypto-gram" leads people to believe that Courtois and
Pieprzyk's XLS work breaks Rijndael.
I believe that the Courtois-Pieprzyk work is flawed. They overcount
the number of linearly independent equations. The result is that they
do not in fact have enough linear equations to solve the system, and
the method does not break Rijndael.
The details: The problem is evident in the "T' method" of section 6.3
of their IACR reprint #2002/044. They generate $ T' = t' t^{P-1} * {
{S-1} \choose {P-1} }$ terms that can be multiplied by x1 and still
remain in their set of $T$ monomials, and then seem to claim to have
that many new equations. But in fact, any of the $t' [ t^{P-1} -
(t-r)^{P-1} ] * { {S-1} \choose {P-1} }$ equations that come from
multiplication of a basic equation by a monomial, have already been
counted among their $R$ equations, and so they can't count them again.
The method has some merit, and is worth investigating, but it does not
break Rijndael as it stands.
** *** ***** ******* *********** *************
CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses,
insights, and commentaries on computer security and cryptography. Back
issues are available on <http://www.counterpane.com/crypto-gram.html>.
To subscribe, visit <http://www.counterpane.com/crypto-gram.html> or
send a blank message to [log in to unmask] To
unsubscribe, visit <http://www.counterpane.com/unsubform.html>.
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 founder and CTO
of Counterpane Internet Security Inc., the author of "Secrets and Lies"
and "Applied Cryptography," and an inventor of the Blowfish, Twofish,
and Yarrow algorithms. He is a member of the Advisory Board of the
Electronic Privacy Information Center (EPIC). He is a frequent writer
and lecturer on computer security and cryptography.
Counterpane Internet Security, Inc. is the world leader in Managed
Security Monitoring. Counterpane's expert security analysts protect
networks for Fortune 1000 companies world-wide.
<http://www.counterpane.com/>
Copyright (c) 2002 by Counterpane Internet Security, Inc.
************************************************************************************
Distributed through Cyber-Society-Live [CSL]: CSL is a moderated discussion
list made up of people who are interested in the interdisciplinary academic
study of Cyber Society in all its manifestations.To join the list please visit:
http://www.jiscmail.ac.uk/lists/cyber-society-live.html
*************************************************************************************
|
