Picking the Crypto Locks

[nobody@REPLAY.COM (Anonymous)]

Byte, October, 1995, pp. 77, 80.


Picking the Crypto Locks

A new technique called differential cryptanalysis can
break even DES quickly

By Peter Wayner


How secure is your encrypted data? Advances in
mathematics and increased computing power mean you need
longer keys and stronger algorithms if you still want to
keep your secrets. Both private-key encryption (which
uses a single key for coding and decoding) and public-key
systems (which use separate keys for encryption and
decryption) are increasingly vulnerable to determined
attack. But do these weaknesses represent a real threat
to encrypted data, or are they still just intriguing
research results?

Unfortunately, when we try to assess the effectiveness of
today's popular cryptographic systems, we run into a
problem of mathematical ignorance. Most people who are
familiar with mathematics can work in two directions,
forward and backward, like the simple algebraic equation
a = b + 1. We can determine the value of the first
variable from that of the second and vice versa. Crypto
systems, however, generally rely on mathematics that
works only in one direction. People assume these systems
are secure because no one has yet shown how to work the
mathematics backward and break open the message. In
general, we determine the strength of most cryptographic
systems by seeing how well they avoid the attacks we know
have been used on other systems. If none of the past
attacks seems to work, then we deem a system secure. For
now.

Let's look at how today's codebreakers work, the
resources and time they need, and what we require in the
way of new systems and longer keys. Recent assessments of
the strength of private-key crypto systems involve
looking for theoretical holes and measuring the time
needed for a brute-force attack. Finding the holes can be
devilishly hard, calling for deep mathematical insights.
Brute-force attacks are easier to mount if enough
computational hardware is available, but they're also
easy to defend against.

The most important development in the realm of data
encryption in recent years is Eli Biham and Adi Shamir's
differential cryptanalysis. They showed how to mount a
limited attack on today's most widely used cryptosystem,
DES (the federal Data Encryption Standard), which is also
the basis for Unix's password system.

Imagine that you had access to your victim's DES cipher
"box" (the common term for an enciphering system) with
preloaded keys. Your goal is to determine the 56-bit key,
so that you can decrypt the other messages your victim
had encrypted with the box. Biham and Shamir showed that
you could infer the hidden key if you could pass 247
messages through the box and observe what came out. This
chosen plaintext attack builds up a statistical model of
the cipher, and it needs this many plaintexts to produce
an answer with confidence.

Most intriguing, this work exposed flaws in many DES
substitutes. Because the U.S. government classified the
details behind DES's design, many assumed that there
might be a trapdoor through which the government could
eavesdrop. To circumvent these potential trapdoors, some
folks designed their own variations of DES. Most of these
new ciphers, however, fall even faster to Biham and
Shamir's mathematical machinery. FEAL-4, a faster
replacement, for example, takes only four well-chosen
plaintexts.

_______________________________________________________

Strengths and Weakness of Crypto Algorithms
_______________________________________________________

Algorithm      Comment      Strengths     Weaknesses
_______________________________________________________

DES            Standard,    Long-tested   Has yielded
               Widely                     to DC
               Accepted
_______________________________________________________

FEAL-4         DES                        Easily broken
               substitute                 by DC
_______________________________________________________

GDES,          DES-like                   Easily broken
New DES                                   by DC
_______________________________________________________

Khufu          DES-like     Secure        New, unknown
                                          against DC
_______________________________________________________

Blowfish       DES-like     Secure        New, unknown
                                          against DC
_______________________________________________________

RC-4           Proprietary  Variable-     Unknown
                            length key
_______________________________________________________

RSA            Widely used  Long-tested   Vulnerable to
Public Key                                advances in
                                          factoring  
_______________________________________________________

Skipjack       Classified   Considered    Algorithm must
                            strong        remain secret
                                          to preserve
                                          law-enforcement
                                          trapdoor
_______________________________________________________

DC = differential cryptanalysis
_______________________________________________________


Recently, the IBM scientists who originally designed DES
revealed that they anticipated Biham and Shamir's attack
and optimized DES to resist it. Because other
nongovernment cryptographers didn't know about this
attack, they couldn't design their software to resist it.
Now the information is public, and there are new ciphers
that hold up well against these attacks. Ralph Merkle's
Khufu and Bruce Schneier's Blowfish are two private-key
ciphers that are similar to DES but resist differential
cryptography. They do this by creating new S-boxes for
each encryption, using the key to randomize them.
(S-boxes are the essential scrambling elements of
DES-like ciphers. Think of them as lookup tables or
nonlinear functions; their outputs should be as random as
possible.) Differential cryptanalysis works only if the
attacker knows what's in the S-boxes.

This work also revealed some stunning counterintuitive
results. Key length is usually taken as a rough measure
of a system's security. DES uses 56-bit keys; a
brute-force attacker might need to try all 2^56 keys to
find the right one. A longer key would mean a longer
brute-force attack. However, Biham and Shamir showed that
even if DES used longer keys, it would hardly be any
stronger against differential cryptanalysis. The
statistical model would still be solvable if DES used the
maximum of 768 bits.

Applying this knowledge to other types of ciphers is
tricky. RSA Data Security markets a proprietary algorithm
called RC-4 that accepts a variable-length key; this
algorithm is used in many products. The flexible key
length can be an advantage in some situations. For
example, the government allows general export of software
using RC-4 with a 40-bit key, but similar software using
a longer key must stay within the U.S. While we don't
know if differential cryptanalysis can be applied to RC-4
directly, because of the algorithm's proprietary nature,
the results with DES suggest that more key is not
necessarily stronger.

Men and Machines

Mathematical tools like differential cryptanalysis can be
the most powerful attack against a cipher system.
Brute-force attacks are normally a last resort, rare in
practice because cipher designers routinely use long key
lengths specifically to preclude them. But times are
changing. We're reaching a point at which a large machine
can quickly search the entire keyspace of DES. DES is
still in wide use; it' s been the commercial and
governmental standard for nearly two decades. Replacing
such standards can be a painfully slow process.

DES users should be thinking about what can be done with
off-the-shelf hardware.

Brute-force attacks simply use large machines that try
all possible passwords in parallel. It's even possible to
produce native chips that run DES. Michael Wiener of Bell
Northern Research described how to build a $1 million
machine using a pipelined DES processor that could cruise
through all possible keys in about 7 hours.

Massively parallel machines can also attack the problem.
Some of the most promismg emergmg machines distribute
small, 1-bit processors directly onto the memory chips.
Some have 1024 processors on a chip with 42 bits of
memory per processor. (Before it entered Chapter 11, Cray
Computer was building for the National Security Agency a
special Cray 3 with such processor-embedded memory.) In
1992 I designed a machine using 1 million associative
processor memory chips (standard DRAM densihes) from
Coherent Research (Syracuse, NY) that could attack all of
DES in one day. This machine could be reprogrammed to
attack other DES-like ciphers. Linden Technology (Austin,
TX) is currently exploring manufacturing new 4-Mb DRAMs
with the 1024 associative processors built onto the chip.

The effect of brute-force attacks on DES is also
important for Unix security, which stores each password
after passing it through DES 25 times. At log-in, you
type your password; it's encrypted 25 times and the
result compared against the password file. If it matches,
the system grants you access. Because the password file
doesn't contain the passwords themselves, unauthorized
users can't use the file to recover them directly. They
must use a brute-force machine. However, the brute-force
attack can be relatively successful against Unix, because
the keyspace is smaller. Most users limit their passwords
to alphabetic characters, occasionally adding numbers.
This makes searching for passwords much faster; it could
be done quite quickly with an associative-memory parallel
processor. One estimate suggests that a computer using
512 of Linden's chips could test all six-character
alphanumeric passwords in 15 minutes. Clearly. the Unix
password structure needs to be rethought in light of
today's machines and code-breaking techniques.

Because of this new vulnerability, you may want to
explore other, newer ciphers. such as Merkle's Khufu or
Schneier's Blowfish. The classified Skipjack algorithm
buried inside the U.S. government's Clipper and Capstone
encryption chips also uses S-boxes, but little is known
about their design. There's little reliable public
information about RSA Data Security's RC-4. Anyone who
uses these algorithms must be prepared to trust the wits
of the designers, because the algorithms have not
undergone the intensely thorough and long-time public
scrutiny given to DES.

Many organizations have opted to continue with DES, but
the current state of the art is triple-DES -- three
passes of the algorithm with either 112- or 168-bit keys.
This effectively guards against both brute-force and
differential analysis attacks. These users can rest
assured that, paradoxically, all the attacks focused on
DES continues to keep it strong.

-----

Peter Wayner is a BYTE consulting editor living in
Baltimore, MD. You can reach him on the Internet at
pcw@access.digex.net, on BIX as pwayner@bix.com, or on
the World Wide Web at http://access.digex.net/~pcw/
pcwpage.html.

-----


Byte, October, 1995, p. 78.


Factoring in Public-Key's Future

Long thought nearly unbreakable, public-key cryptogratphy
is yielding to attack. The secret of security here is key
length.

By Bruce Schneier


Factoring large numbers is hard but not as hard as it
used to be. This has grave implications for the
effectiveness of public key cryptocraphy, which relies on
the difficulty of factoring long keys for its security.
But how long is long enough'?

In 1976, Richard Guy wrote: "I shall be surprised if
anyone regularly factors numbers of size 10^80 without
special form during the present century." In 1977, Ron
Rivest said that factoring a 125-digit number would take
40 quadrillion years. In 1994, a 129-digit number was
factored. The lesson here is that making predictions is
foolish.

Today, 512-bit keys are common. Factoring them, thus
destroying their security, is well within the range of
possibility for today's computing resources. A weekend-
long worm on the Internet could do it.

Computing power is measured in MIPS-years: a
million-instructions-per-second computer running for one
year, or about 3 x 10^13 instructions. A 100-MHz Pentium
is about a 50-MIPS machine; a 1600-node Intel Paragon is
about 50,000 MIPS.

In 1983, a Cray X-MP supercomputer factored a 71-digit
number in 0.1 MIPS-years, using 9.5 CPU hours. That's
expensive. Factoring the 129-digit number in 1994
required 5000 MlPS-years and used the idle time on 1600
computers around the world over an eight-month period.
Although it took longer, it was essentially free.

Those two computations used what's called the *quadratic
sieve*, but a newer, more powerful algorithm has arrived.
The *general number filed sieve* is faster than the
quadratic sieve for numbers well below 116 digits and can
factor a 512-bit number over 10 times faster -- it would
take less than a year to run on  an 1800-node Intel
Paragon.

And the process gets still faster. Mathematicians keep
coming up with new tricks, new optimizations, and new
techniques. A related algorithm, the special number field
sieve, can already factor numbers of a specialized form
(not generally used for cryptography) much faster. So we
can probably optimize the general number field sieve to
run that fast. For all we know, the National Security
Agency is already doing it.

The figure "MIPS Years Needed to Factor" gives the number
of MlPS-years required to factor "special" and "general"
numbers of different lengths.

How Big Is Big Enough?

The wise cryptographer is ultraconservative when choosing
key lengths for a public-key system. You must consider
the intended security, the key's expected lifetime, and
the current state of the factoring art. Now you need a
1024-bit number to get the same security you got from a
512-bit number in the early 1980s. If you want your keys
to remain secure for 20 years, 1024 bits is probably too
short.

Consider these assumptions from the mathematicians who
factored RSA-129: We believe we could acquire 100,000
machines without superhuman or unethical efforts and
without an Internet womm or virus. Many organizations
have several thousand machines on the Net. Using their
facilities would require diplomacy but should not be
impossible. Assuming an average power of 5 MIPS and one
year elapsed time, we could reasonably embark on a
project that would require half a million MIPS-years. The
project to factor the 129-digit number harnessed an
estimated 0.03 percent of the Internet's total computing
power. A well-publicized project might be able to harness
2 percent of the world's computing power for a year.

My recommendations for public-key lengths are given in
the figure "Recommended Public-Key Key Lengths" according
to how long you require the key to be secure. There are
three key lengths given for each period -- one secure
against an individual cryptanalyst who can get his hands
on 10,000 MlPS-years, one against a major corporation
that could harness 10^7 MIPS-years, and the third secure
against a major govemment and 10^9 MIPS-years. These
figures assume that computing power will increase by a
factor of 10 every five years and that mathematical
advances will let us factor numbers at the speeds of the
special number field sieve.

Not everyone will agree with these final recommendations.
The National Institute of Standards and Technology has
mandated 512- to 1024-bit keys for its Digital Signature
Standard. PGP has a maximum RSA key length of 1280 bits.
Aljen Lenstra, the world's most successful factorer,
refuses to predict beyond 10 years. There's always the
possibility that an advance in factoring will surprise me
as well, though I tried to factor everything into my
calculations. But why trust me? I just proved my own
foolishness by making predictions.

_______________________________________________________

MIPS Years Needed to Factor
_______________________________________________________

Ascending Line of General Number Field Sieve

Ascending Line Special Number Field Sieve

Y-axis: MIPS-years
10^0, 10^3, 10^6, 10^9, 10^12, 10^15, 10^18, 10^21

X-axis: Bits
512, 768, 1024, 1280, 1536, 2048
_______________________________________________________


_______________________________________________________

Recommended Public-Key Key Lengths
_______________________________________________________

Ascending bars for: Individual, Company, Government

Y-axis: Bits 0, 500, 1000, 1500, 2000, 2500

X-axis: Year 1995  2000  2005  2010  2015
_______________________________________________________

-----

Bruce Schneier is the author of Applied Cryptography
(John Wiley), the second edition of which is due out in
December. He can be reached on the Internet as
schneier@winternet.com, or on BIX c/o editors@bix.com.

-----