Path: gmdzi!unido!mcsun!uunet!tut.cis.ohio-state.edu!ucsd!pacbell.com!
pacbell!hoptoad!gnu
From: gnu@hoptoad.uucp (John Gilmore)
Newsgroups: sci.crypt
Subject: Adi Shamir and Eli Biham reveal "Differential Cryptanalysis"
Message-ID: <12001@hoptoad.uucp>
Date: 17 Aug 90 19:02:03 GMT
References: <11999@hoptoad.uucp>
Organization: Cygnus Support, Palo Alto
Lines: 96
Posted: Fri Aug 17 20:02:03 1990
The biggest news of Crypto '90 was that Adi Shamir revealed the
technique he and Eli Biham have been using to cryptanalyze DES. Their
paper introduces "Differential Cryptanalysis" and shows how they used
this chosen plaintext technique to blow away FEAL-8, Snefru with two
rounds, Lucifer with 8 rounds, N-Hash with 6 rounds, and DES with less
than 16 rounds. NOTE that this method is harder than exhaustive search
for DES with 16 rounds -- DES has not been broken here, but has been
quite a bit better understood.
The crucial realizations are: XOR is self-inverse, and the DES key
mixes into the plaintext with XOR. The rest of the DES, except the
S-boxes, are linear with respect to XOR. And the S-boxes are far from
random if you look at the XOR of their inputs and compare it to the
XOR of their outputs. These properties are exploited to push knowledge
about the inputs deep into the guts of DES where there is hope of getting
it out the other side as visible relationships in the ciphertext.
The technique is to look at a system that has two DES's going on
in parallel: one with plaintext X and the other with plaintext Y.
(Both use the same key.) What we look at is the XOR of X and Y.
The inputs are chosen to have a specific XOR value and then we
watch the XOR evolve as the encryption proceeds. Since the key
is XOR'd in on both DES's, it has no effect on the XOR between the
two sides -- the method is key-independent!
What happens to the XOR is completely predictable EXCEPT through the
S-box. There, however, the probabilities are non-even, and this gives
us a handle. E.g. if the XOR of the inputs to the S-box is 0, you know
the XOR of the outputs will be 0 also (the inputs were the same, so
will the outputs be the same). If the XOR of the inputs to S1 is 0x34,
the probability of the XOR of the outputs being 0x2 is 16/64 or 1/4th
(you can determine this from enumerating all the possible inputs and
looking them up in the box, which is fixed for all time and well
known). Since there are 4 output bits of the S-box, a smooth
probability would be 1/16th -- much different from 1/1 or 1/4th. We
can feed various plaintexts through that S-box, and depending which key
bits are XOR'd in, we will see different probabilities of results.
From the probability distribution of the results, we can work backwards
to determine what the S-box input was, and since the S-box input was
the XOR of part of the key and part of the plaintext -- and we know the
plaintext -- we then know part of the key.
This only works in the last round of DES, since we need to see
unmangled ciphertext bits. The rest of the attack (which I'll leave
the paper to explain) is how you select interesting plaintext pairs,
whose S-box probabilities are 1 or otherwise abnormally high, to
propagate your knowledge through the first N rounds to get it to the
last round where you can break key bits.
The on-site proceedings include a very readable paper describing
the attack (the only thing it lacks is a good drawing of how one
round of DES works); they are available from Sherry McMahan as
described in the parent message to this one. If you want to get
the full gory details, ask for "Differential Cryptanalysis of
DES-like Cryptosystems" from:
Adi Shamir
The Weizmann Institute
Applied Math Dept.
Rehovot 76100, ISRAEL
phone 9728 343253
Folks at the conference paid $5 for copying costs of this 100+ page
tech report; I'm sure he'd appreciate contributions if you ask for a
copy. The cost of clearing foreign checks often runs $10-15 though.
I heard several people predict that next year's Crypto conference
would have a whole session devoted to differential cryptanalysis
and what uses people come up with for it.
Things that I read into this (personal opinions) are:
* The designers of DES knew about this attack, or about
this class of attacks. The attack SUCCEEDS (costs less
than brute force) for 15 rounds of DES, FAILS (costs more)
for 16 rounds of DES. Guess how many rounds DES uses?
* Adi and Eli also discovered that almost any change they
made to DES, even rearranging the order of the eight
S-boxes, made it weaker and made it possible to break
in less than brute force. The S-boxes were designed
either knowing about this attack and testing against it, or
knowing of other design criteria that manage to foil this
attack even if the particular attack was not envisioned.
* DES was not weakened by reducing the key to 56 bits,
since with a 56-bit key and 16 rounds it is STILL
harder to break than with brute force. The work factor
at 16 rounds is 2^58. Regardless of the length of the
key, this is still true, so a 128-bit key would not
have been any better.
--
John Gilmore {sun,pacbell,uunet,pyramid}!hoptoad!gnu g...@toad.com
The Gutenberg Bible is printed on hemp (marijuana) paper. So was the July 2,
1776 draft of the Declaration of Independence. Why can't we grow it now?