[prev in list] [next in list] [prev in thread] [next in thread]
List: best-of-security
Subject: BoS: dfa.htm
From: Julian Assange <proff () suburbia ! net>
Date: 1996-10-21 20:23:02
[Download RAW message or body]
To: cypherpunks@toad.com
Subject: FYI - Biham/Shamir Differential Fault Analysis of DES, etc.
Date: Fri, 18 Oct 1996 15:10:51 -0400
From: Matt Blaze <mab@research.att.com>
_________________________________________________________________
------- Forwarded Message
_________________________________________________________________
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>
To: benaloh@microsoft.com, brassard@iro.umontreal.ca,
canetti@theory.lcs.mit.edu, crepeau@iro.umontreal.ca,
david@digicash.com, daw@cs.berkeley.edu, mab@research.att.com,
mihir@watson.ibm.com, rogaway@cs.ucdavis.edu, schneier@counterpane.com
Subject: A new attack on DES
_________________________________________________________________
Research announcement: A new cryptanalytic attack on DES
_________________________________________________________________
Eli Biham , Computer Science Department, The Technion, Israel
Adi Shamir, Applied Math Department, The Weismann Institute, 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
attention (see, e.g., John Markoff's 9/26/96 article in the New York
Times). Their full paper had not been published so far, but Bellcore's
press release and the authors' FAQ (available at
http://www.bellcore.com/PRESS/ADVSRY96/medadv.html) specifically state
that the attack is applicable only to public key cryptosystems such as
RSA, and not to secret key algorithms such as the Data Encryption
Standard (DES). According to Boneh, "The algorithm that we apply to
the device's faulty computations works against the algebraic structure
used in public key cryptography, and another algorithm will have to be
devised to work against the nonalgebraic operations that are used in
secret key techniques." In particular, the original Bellcore attack is
based on specific algebraic properties of modular arithmetic, and
cannot handle the complex bit manipulations which underly most secret
key algorithms.
In this research announcement, we describe a related attack (which we
call Differential Fault Analysis, or DFA), and show that it is
applicable to almost any secret key cryptosystem proposed so far in
the open literature. In particular, we have actually implemented DFA
in the case of DES, and demonstrated that under the same hardware
fault model used by the Bellcore researchers, we can extract the full
DES key from a sealed tamperproof DES encryptor by analysing fewer
than 200 ciphertexts generated from unknown cleartexts. The power of
Differential Fault Analysis is demonstrated by the fact that even if
DES is replaced by triple DES (whose 168 bits of key were assumed to
make it practically invulnerable), essentially the same attack can
break it with essentially the same number of given ciphertexts.
We would like to gratefully acknowledge the pioneering contribution of
Boneh Demillo and Lipton, whose ideas were the starting point of our
new attack.
In the rest of this research announcement, we provide a short
technical summary of our practical implementation of Differential
Fault Analysis of 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 a sealed tamperproof device such as a smart card to certain
physical effects (e.g., ionizing or microwave radiation), one can
induce with reasonable probability a fault at a random bit location in
one of the registers at some random intermediate stage in the
cryptographic computation. Both the bit location and the round number
are unknown to the attacker.
We further assume that the attacker is in physical possesion of the
tamperproof-device, 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 correct
and the other is the result of a computation corrupted by a 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 rounds of
DES is flipped from 0 to 1 or vice versa, and that both the bit
position and the round number are uniformly distributed.
In the first step of the attack we identify the round in which the
fault occurred. This identification is very simple and effective: If
the fault occurred in the right half of round 16, then only one bit in
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 48
out of the 56 key bits in order to guess the missing 8 bits in all the
possible 2^8=256 ways. Alternatively, we can use our knowledge of the
last subkey to peel up the last round (and remove faults that we
already identified), and analyse the preceding rounds with the same
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
cryptosystems, including IDEA, RC5 and Feal. Some ciphers, such as
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
_________________________________________________________________
The New York Times, October 19, 1996, p. 37.
_________________________________________________________________
2 Israelis Outline New Risk To Electronic Data Security
Hints That 'Smart Cards' Aren't So Smart
By John Markoff
San Francisco, Oct. 18 -- Two of Israel's leading computer scientists
say they have found a way to more easily decode and then counterfeit
the electronic cash "smart cards" that are now widely used in Europe
and are being tested in the United States.
The researchers have begun circulating the draft of a paper that
points out higher security risks than those discovered last month by
scientists at Bell Communications Research.
The Bell communications researchers had reported that it might be
possible to counterfeit many types of the "smart cards" that are being
tested by banks and credit card companies, including Visa and
Mastercard.
The two Israeli scientists, Adi Shamir, a professor at the applied
mathematics department at the Weizmann Institute, and Eli Biham, a
member of the faculty of the computer science department at the
Technion, reported that in addition to the so-called public key coding
systems that were found vulnerable by the Bellcore team, private key
data coding systems such as the American Data Encryption Standard, or
DES, can be successfully attacked if a computer processor can be made
to produce an error.
The two Israeli's made a draft of their research available via the
Internet on Thursday. In their paper the two wrote, "We can extract
the full DES key from a sealed tamperproof DES encryptor" by analyzing
fewer than 200 encoded messages.
Both public key and private key data scrambling methods are based on
the difficulty involved in factoring large numbers. A public key
system permits two parties who have never met to exchange secret
information. A private key system requires that a secret key be
exchanged beforehand.
Data coding experts said that the new Israeli method might be a more
practical system than the previously announced Bellcore method,
because unlike public keys, which are frequently used only once per
message, a private secret key may be used repeatedly to scramble
electronic transactions.
"This seems a lot closer to something that might actually Matt Blaze,
a computer researcher at AT&T Laboratories.
Smart cards have been promoted as tamper proof, which is why computer
scientists at Bellcore, one of the nation's leading
information-technology laboratories, sounded the alarm last month,
saying that a savvy criminal might be able to tweak a smart-card chip
to make a counterfeit copy of the monetary value on a legitimate card.
Executives at smart card companies said at the time that the attack
was theoretical and that it would be impossible to make a smart card
generate an error without actually destroying the card.
However, Mr. Biham responded that he believed such hardware attacks
were possible. The cards are generally damaged using heat or
radiation, which causes the computer chip in the card to generate an
error, which the Israeli scientists used to obtain the code key and
copy the card.
"I have ample evidence that hardware faults can be generated without
too much difficulty," he said in an electronic mail message. "As a
consultant to some high-tech companies, I had numerous opportunities
to witness successful attacks by commercial pirates on pay-TV systems
based on smart cards. I know for a fact that some of these attacks
were based on intentional clock and power supply glitches, which can
often cause the execution of incorrect instructions by the smart
card."
Other researchers said that the class of attacks demonstrated by the
Bellcore team and the Israelis had been known by some members of the
tightly knit community of cryptographers for several years, but the
results had not been published.
"Some of the smart card manufacturers are well aware of this flaw,"
said Paul Kocher, an independent Silicon Valley data security
consultant. "But it doesn't mean that they have fixed it."
[End]
_________________________________________________________________
Wall Street Journal, October 21, 1996, p. B14.
_________________________________________________________________
Smart Cards Are Open to New Attack By Hackers, Say Israeli Researchers
By David Bank
Smart cards, the wallet-size electronic devices that have been touted
as the tamper-proof solution to computer security, are vulnerable to a
new attack by sophisticated hackers, according to two Israeli
researchers who have simulated such an attack.
The finding, reported in an Internet announcement last week, is the
second time in the past month that the devices have been reported to
be vulnerable. Smart cards are expected to become widely used in the
U.S. as electronic "purses" for cash transactions, in access controls
for buildings and equipment, and for identity authentication for
documents transmitted over computer networks.
Visa International Inc., Mastercard International Inc. and several
major banks are testing the devices, which are already common in
Europe.
An estimated two billion smart cards are expected to be in circulation
worldwide by 2000, according to Catherine Allen and William Barr,
editors of the book Smart Card: Seizing Strategic Business
Opportunities. More than 300 million cards with computer chips were
issued in 1993 alone, for use in telephones, health care, banking and
pay-TV services, according to the Smart Card Forum, a trade group in
Tampa, Fla.
"If you have a card that controls very important pieces of equipment,
or funds, it would potentially be vulnerable to attack," said Ronald
Rivest, a professor at the Massachusetts Institute of Technology and
an associate of the Israeli researchers. "If it's a bank card, the
attacker could raid your bank account."
Mr. Rivest said the reports of the cards' vulnerability could take
some of the shine off their image, but deployment of the cards isn't
expected to be slowed. He predicted few breaches of the cards'
security because of the sophisticated understanding of cryptography
required.
Despite the vulnerabilities, smart cards are far more secure than
common magnetic-stripe cards, such as credit cards, which are easy to
counterfeit, Mr. Rivest said. Unlike magnetic-stripe cards, which
simply store data, smart cards contain a computer chip which generates
a digital key used to encrypt data.
"Compared to the risks of using nonsmart cards, we're still much
better off," Mr. Rivest said.
Adi Shamir of the Weizmann Institute and Eli Biham of the Technion,
both in Israel, said they used a personal computer to demonstrate that
the secret cryptographic key contained in a smart card could be
deduced relatively quickly. The researchers created a mathematic model
to demonstrate that once a card could be induced to commit an error,
by subjecting it to ionizing or microwave radiation for example, then
the card's faulty results could be compared with accurate ones. By
alternating between the correct and incorrect results, they said they
were able to deduce the cryptographic key.
The researchers said they had used the method, known as Differential
Fault Analysis, to crack one of the most commonly used cryptographic
formulas, the Digital Encryption Standard. More ominously, Mr. Biham
and Mr. Shamir said the same method could be used to crack the much
stronger Triple DES, as well as "almost any other secret key
cryptosystem proposed so far."
In practical terms, a hacker might secure the key by rigging a machine
that accepts smart cards to zap inserted cards with radiation and then
to collect the data for analysis. Once the secret key is acquired, the
hacker could easily counterfeit the card, Mr. Rivest said.
The latest research announcement follows reports last month that
scientists at Bellcore, in Morristown, N.J., found a way to deduce the
keys in a particular type of card that use the so-called public
key-method of encryption. In that method the sender and receiver use
different keys to encode and decode messages. In the "secret key"
systems, now used in most smart cards, both sender and receiver use
the same key for encoding and decoding.
[End]
_________________________________________________________________
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic