------=_NextPart_000_01BBC0CB.C9165A40
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Heads up
----------
> From: Donald E. Eastlake 3rd <dee@cybercash.com>
> To: tedk <tpk@sensorsys.com>
> Cc: Digital Commerce Society of Boston <dcsb@ai.mit.edu>
> Subject: Re: Attack on Smart Cards
> Date: Wednesday, October 23, 1996 9:45 AM
>
>
> It seems pretty real. I've attached further info. As with many crpto
> attacks, once you know about it you can make your equipment resistant
> to it.
>
> Donald
>
> On Wed, 23 Oct 1996, tedk wrote:
>
> > Date: Wed, 23 Oct 1996 12:34:49 -0300
> > From: tedk <tpk@sensorsys.com>
> > To: Digital Commerce Society of Boston <dcsb@ai.mit.edu>
> > Subject: Attack on Smart Cards
> >
> > To all interested in smart cards,
> >
> > The Wall Street Journal (Monday, Oct 21, 1996) had an article
concerning a
> > claim by a group of Isreali researchers (not cyberpunks) associated
with Ron
> > Rivest of MIT who claim to be able to crack smart cards.
> >
> > They used a PC to simulate an actual attack but claim that they could
crack
> > any smart card using DES or even 3X DES.
> >
> > They require a smart card and some method to induce it to incorrectly
> > generate an encryption (suggested but not tested exposure to x-rays,
> > magnetic fields etc). By comparing the correct encryption of a known
test
> > to the incorrect encryption and then using a mathematical technique
known as
> > differential fault analysis, the original key could be deduced. Once
this
> > is known counterfeiting is easy.
> >
> > They claim that this process is workable with any smart card. They
further
> > claim that there is no defense that will prevent this attack.
> >
> > Rivest seems to concur at least in the general level.
> >
> > If this is in fact the case -- then smart card based cyber cash is
really in
> > trouble since a ring could pickpocket cards (or take them by force),
supply
> > the cards to some unscrupulous group with an x-ray machine
(questionable
> > perhaps) and a PC and access to blank cards - - the result new cards
with
> > the original key.
> >
> > What do others think/know about this issue (Outside of a couple of
people
> > who think this is too technical and not in the main line of inquiry of
the
> > DCSB mailing list)
> >
> > "Be Seeing You"
> > Ted
> >
***************************************************************************
> > Ted Kochanski, Ph.D.
> > Sensors Signals Systems --- "Systematic Solutions to Complex
Problems"
> > http://www.sensorsys.com
> > e-mail tpk@sensorsys.com phone (617) 861-6167 fax 861-0476
> > 11 Aerial St., Lexington, MA 02173
>
> =====================================================================
> Donald E. Eastlake 3rd +1 508-287-4877(tel) dee@cybercash.com
> 318 Acton Street +1 508-371-7148(fax) dee@world.std.com
> Carlisle, MA 01741 USA +1 703-620-4200(main office, Reston, VA)
> http://www.cybercash.com http://www.eff.org/blueribbon.html
>
------=_NextPart_000_01BBC0CB.C9165A40
Content-Type: application/octet-stream; name="tmp"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment; filename="tmp"
Date: Mon, 21 Oct 1996 14:05:02 -0400 (EDT)
From: "Donald E. Eastlake 3rd" <dee@cybercash.com>
To: dee-interest@cybercash.com
Subject: FWD - Biham/Shamir Differential Fault Analysis of DES
[This appears to be a very powerful new attack that will require=20
substantial re-engineering of all smart cards and the like... dee3]
Date: Mon, 21 Oct 1996 14:00:18 -6
From: Peter Trei <trei@process.com>
Date: Fri, 18 Oct 1996 15:10:51 -0400
From: Matt Blaze <mab@research.att.com>
From: Shamir Adi <shamir@wisdom.weizmann.ac.il>
Date: Fri, 18 Oct 1996 16:30:34 +0200
Message-Id: <199610181430.QAA20359@white.wisdom.weizmann.ac.il>
Subject: A new attack on DES
Research announcement: A new cryptanalytic attack on DES
Eli Biham Adi Shamir
Computer Science Dept. Applied Math Dept.
The Technion The Weizmann Institute
Israel Israel
October 18, 1996
(DRAFT)
In September 96, Boneh Demillo and Lipton from Bellcore announced an
ingenious new type of cryptanalytic attack which received widespread=20
attention (see, e.g., John Markoff's 9/26/96 article in the New=20
York Times). Their full paper had not been published so far, but=20
Bellcore's press release and the authors' FAQ (available at =20
http://www.bellcore.com/PRESS/ADVSRY96/medadv.html) specifically=20
state that the attack is applicable only to public key cryptosystems=20
such as RSA, and not to secret key algorithms such as the Data =
Encryption=20
Standard (DES). According to Boneh, "The algorithm that we apply to the=20
device's faulty computations works against the algebraic structure used
in public key cryptography, and another algorithm will have to be =
devised=20
to work against the nonalgebraic operations that are used in secret key=20
techniques." In particular, the original Bellcore attack is based on=20
specific algebraic properties of modular arithmetic, and cannot handle=20
the complex bit manipulations which underly most secret key algorithms.
In this research announcement, we describe a related attack=20
(which we call Differential Fault Analysis, or DFA), and show that=20
it is applicable to almost any secret key cryptosystem proposed so far=20
in the open literature. In particular, we have actually implemented=20
DFA in the case of DES, and demonstrated that under the same=20
hardware fault model used by the Bellcore researchers, we can=20
extract the full DES key from a sealed tamperproof DES encryptor by=20
analysing fewer than 200 ciphertexts generated from unknown cleartexts.
The power of Differential Fault Analysis is demonstrated by the fact=20
that even if DES is replaced by triple DES (whose 168 bits of key were=20
assumed to make it practically invulnerable), essentially the same =
attack=20
can break it with essentially the same number of given ciphertexts.=20
We would like to greatfully acknowledge the pioneering contribution
of Boneh Demillo and Lipton, whose ideas were the starting point of
our new attack.=20
In the rest of this research announcement, we provide a short technical
summary of our practical implementation of Differential Fault Analysis =
of=20
DES. Similar attacks against a large number of other secret key =
cryptosystems
will be described in the full version of our paper.
TECHNICAL DETAILS OF THE ATTACK
The attack follows the Bellcore fundamental assumption that by exposing=20
a sealed tamperproof device such as a smart card to certain physical=20
effects (e.g., ionizing or microwave radiation), one can induce with=20
reasonable probability a fault at a random bit location in one of the=20
registers at some random intermediate stage in the cryptographic=20
computation. Both the bit location and the round number are unknown=20
to the attacker.=20
We further assume that the attacker is in physical possesion of the=20
tamperproofdevice, so that he can repeat the experiment with
the same cleartext and key but without applying the external
physical effects. As a result, he obtains two ciphertexts derived from
the same (unknown) cleartext and key, where one of the ciphertexts is=20
correct and the other is the result of a computation corrupted by a=20
single bit error during the computation. For the sake of simplicity,
we assume that one bit of the right half of the data in one of the 16=20
rounds of DES is flipped from 0 to 1 or vice versa, and that both the=20
bit position and the round number are uniformly distributed.
In the first step of the attack we identify the round in which the=20
fault occurred. This identification is very simple and effective: If=20
the fault occurred in the right half of round 16, then only one bit in=20
the right half of the ciphertext (before the final permutation) differs
between the two ciphertexts. The left half of the ciphertext can
differ only in output bits of the S box (or two S boxes) to which this
single bit enters, and the difference must be related to non-zero
entries in the difference distribution tables of these S boxes. In
such a case, we can guess the six key bit of each such S box in the
last round, and discard any value which disagree with the expected
differences of these S boxes (e.g., differential cryptanalysis). On
average, about four possible 6-bit values of the key remain for each
active S box.
If the faults occur in round 15, we can gain information on the key
bits entering more than two S boxes in the last round: the difference
of the right half of the ciphertext equals the output difference of
the F function of round 15. We guess the single bit fault in round
15, and verify whether it can cause the expected output difference,
and also verify whether the difference of the right half of the
ciphertext can cause the expected difference in the output of the F
function in the last round (e.g., the difference of the left half of
the ciphertext XOR the fault). If successful, we can discard possible
key values in the last round, according to the expected differences.
We can also analyse the faults in the 14'th round in a similar way.
We use counting methods in order to find the key. In this case, we
count for each S box separately, and increase the counter by one for
any pair which suggest the six-bit key value by at least one of its
possible faults in either the 14'th, 15'th, or 16'th round.
We have implemented this attack on a personal computer. Our analysis
program found the whole last subkey given less than 200 ciphertexts,
with random single-faults in all the rounds.
This attack finds the last subkey. Once this subkey is known, we can
proceed in two ways: We can use the fact that this subkey contains=20
48 out of the 56 key bits in order to guess the missing 8 bits in
all the possible 2^8=3D256 ways. Alternatively, we can use our knowledge
of the last subkey to peel up the last round (and remove faults that=20
we already identified), and analyse the preceding rounds with the same=20
data using the same attack. This latter approach makes it possible to
attack triple DES (with 168 bit keys), or DES with independent subkeys
(with 768 bit keys).
This attack still works even with more general assumptions on the
fault locations, such as faults inside the function F, or even faults
in the key scheduling algorithm. We also expect that faults in
round 13 (or even prior to round 13) might be useful for the analysis,
thus reducing the number of required ciphertext for the full analysis.
OTHER VULNERABLE CIPHERS
Differential Fault Analysis can break many additional secret key=20
cryptosystems, including IDEA, RC5 and Feal. Some ciphers, such as=20
Khufu, Khafre and Blowfish compute their S boxes from the key material. =
In such ciphers, it may be even possible to extract the S boxes
themselves, and the keys, using the techniques of Differential Fault
Analysis. Differential Fault Analysis can also be applied against
stream ciphers, but the implementation might differ by some technical
details from the implementation described above.
------- End of Forwarded Message
Peter Trei
Senior Software Engineer
Purveyor Development Team =20
Process Software Corporation
http://www.process.com
trei@process.com
------=_NextPart_000_01BBC0CB.C9165A40--