15 January 1999

               January 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:
     The 1998 Crypto Year-in-Review
     Counterpane Systems -- Featured Research
     News
     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
year.

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
<http://www.counterpane.com/crypto-gram-9806.html#side>.

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
<http://www.counterpane.com/pptp.html>.

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.

http://www.counterpane.com/clueless-agents.html


** *** ***** ******* *********** *************

                    News



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:
http://www.hrw.org/hrw/worldreport99/special/internet.html
A summary can be found at:
http://www.nytimes.com/library/tech/98/12/cyber/cyberlaw/18law.html

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:
http://www.jya.com/paperF1.htm

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:
http://lwn.net/1998/1203/netscape.html
Additional postings can be found in the Bugtraq archives at:
http://geek-girl.com/bugtraq/

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
at:
http://www.eskimo.com/~weidai/cryptlib.html
http://cryptography.org/cgi-bin/crypto.cgi/libraries/crypto30.zip

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.
http://www.efa.org.au/Issues/Crypto/Walsh/index.htm

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.
http://news.bbc.co.uk/hi/english/sci/tech/newsid_254000/254236.stm
http://www.msnbc.com/news/231690.asp
http://jya.com/flannery.htm

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.
http://www.economictimes.com/120199/lead2.htm

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."
http://news.bbc.co.uk/hi/english/world/americas/newsid_254000/254094.stm


** *** ***** ******* *********** *************

          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
<http://www.counterpane.com/secure-logs.html>.

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-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



--
Raphael Carter <anagram@chaparraltree.com>