From:	SMTP%"proff@suburbia.net" 22-OCT-1996 18:42:38.48
To:	EVERHART
CC:	
Subj:	BoS: dfa.htm

Resent-Date: Tue, 22 Oct 1996 06:33:37 +1000
Old-X-Envelope-From: proff  Tue Oct 22 06:23:02 1996
Date: Tue, 22 Oct 1996 06:23:02 +1000
From: Julian Assange <proff@suburbia.net>
Message-Id: <199610212023.GAA09752@suburbia.net>
X-URL: http://jya.com/dfa.htm
To: best-of-security@suburbia.net
Approved: proff@suburbia.net
Resent-Message-ID: <"38MlC2.0.TX2.WuzQo"@suburbia>
Resent-From: best-of-security@suburbia.net
X-Mailing-List: <best-of-security@suburbia.net> archive/latest/466
X-Loop: best-of-security@suburbia.net
Precedence: list
Resent-Sender: best-of-security-request@suburbia.net
Subject: BoS: dfa.htm


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

