From: Ross Anderson 
Prev-Resent-Message-Id: <"EnGBn1.0.MK5.GPNVo"@suburbia>
X-Mailing-List: archive/latest/489
Subject: BoS: Warning to Crypto and Banking Communities

                    A serious weakness of DES
                    Draft - 2nd November 1996

Eli Biham and Adi Shamir recently pointed out that if an attacker
can  induce  unidirectional faults in key memory of cryptographic
devices, then keys could be extracted quickly. Although their at-
tack  is  very  elegant, it is not practical against many fielded
systems. For example, inducing a single bit change in a  DES  key
will cause a proper implementation to return a key parity error.

However, when combined with Peter Gutman's recent work on  memory
remanence,  there are two very practical attacks. One of them al-
lows smartcard electronic wallet keys to be extracted  with  much
less  expensive  equipment  than  that  currently  used by pay-TV
pirates; the other yields an  effective  attack  against  fielded
banking  security  modules.  These attacks show that a feature of
DES that had long been thought innocuous is  actually  a  serious
design error.

In a research announcement of  30th  October,  Biham  and  Shamir
point out that if a cryptographic hardware module employes EEPROM
for key memory only, an opponent who can turn EEPROM values  from
`1' to `0' with a small controlled probability (e.g., by applying
UV light) might cause a test input to be encrypted with a  series
of  keys,  each  of  Hamming  distance  one  from the next in the
series, and ending with the all zero key [1].

There are a number of reasons why their attack is not  likely  to
work  against  real  systems.  For example, the typical smartcard
system has several kilobytes of program code in EEPROM as well as
typically  two  to five DES keys. An undirected stress applied to
such a card is more likely to cause a program crash or  an  unin-
formative  error than to yield a ciphertext encrypted under a key
at Hamming distance one from a genuine key. Even if we  only  had
to  cause  a  hundred cards to fail to get a single input for the
Biham-Shamir attack, if we needed on average 28 inputs to recover
a DES key, then the number of cards required could be O(100^28).

The situation is made still worse by the fact that DES keys  have
odd  parity, and a proper implementation will reject a key if any
of its bytes has even parity. So one would be reduced to  looking
for keys at a Hamming distance of two rather than one. It is this
objection that inspired the following work.

A Modified Attack
My idea is to turn the DES key parity problem on its head and en-
able  parity  to help rather than hinder the attack. Let us first
consider an opponent who can  perform  directed  attacks  on  the
chip.  Reading  the contents of an EEPROM cell directly is diffi-
cult, and people who do it for a  living  use  focused  ion  beam
workstations  to  modify  the chip [2]. However, it is trivial to
set an EEPROM cell to the value of your choice if you do not have
to read it first; you only need two microprobes. A 10mS 18V pulse
from the cell's source to its control gate will do the trick [3].

My modified attack therefore proceeds as follows. Set  the  first
bit  of  the EEPROM containing the target DES key to 1 (or 0, the
choice doesn't matter) and operate the device. If it still works,
the keybit was a 1. If you get a `key parity error' message, then
the bit was zero. Move on to the next bit; set it to 1 and see if
this  changes  the device's response (from encryption to error or
vice versa).

This is a practical attack even on chips whose software we do not
know  in  detail, as many smartcard software writers seem to have
adopted a convention that the keys are located at the bottom  end
of  the  EEPROM memory. It will also work with protocols that use
redundancy which we do not understand: we just  change  each  key
bit back to its original value.

The use of predictable memory addresses for keys is not restrict-
ed to smartcards; many banking security modules also keep keys at
low memory. I will now describe a related  attack  that  extracts
master keys from these modules.

An Attack on Fielded Systems
In a brilliant Usenix  paper  [4],  Peter  Gutman  described  the
mechanisms  that  cause both static and dynamic RAM to `remember'
values that they have stored for a long period of time. A prudent
security engineer will ask what the effect of this is in the real

I looked at an instance of a security  module  used  in  banking.
This  security  module  has 12 pairs of DES master keys stored in
low memory.  The device is tamper resistant in that power to  the
key  memory  is cut when the box is opened for servicing (this is
needed every few years to change the battery).  Keys  are  loaded
into the device afterwards in multiple components by trusted bank

In this device, which dated from the late 1980's, the key  values
were  substantially intact on power-up. The number of bits in er-
ror was of the order of 5-10%. I cannot give more  accurate  fig-
ures  as I was not permitted to copy down either the correct mas-
ter key values, nor  the  almost-correct  values  that  had  been
`burned  in'  to the static RAM chips. I am also not permitted to
name the bank at which these modules are installed,  and  it  may
not be prudent to name their manufacturer.

Nonetheless the  crypto  community  should  consider  the  conse-

If each DES key is wrong by five bits, then the  effort  involved
in  seaching  for  the 10 wrong bits in a double DES key might be
thought to be 112-choose-10 operations. Each operation would  in-
volve (a) doing a 2-key 3DES decryption of a 64 bit PIN key whose
enciphered value is widely known to the bank's programmers (b) in
the 2^{-8} of cases where this result has odd parity, enciphering
an account number with this as a DES key to see if the  (decimal-
ised)  result  is  the  corresponding  PIN. The effort is 4 times
112-choose-10 DES operations - about 2^50. But it would  probably
be  cheaper  to  do  a hardware keysearch on the PIN key directly
than to try to implement this more complex 2^50 search in  either
hardware or software.

However, the bytewise nature of the DES  key  redundancy  reduces
the  effort  by  orders of magnitude. If no key byte has a double
error, then the effort is seven tries for each even  parity  byte
observed,  or  7^10  - about 2^28, which is easy. If there is one
key byte with a double error, the effort is 2^38, giving a search
of 2^40 DES operations - which is still feasible for an individu-

I have shown that the key parity in DES enables us to  slash  the
cost  of  real  attacks  on  both  old  systems (banking security
modules) and new ones (electronic wallet smartcards).

I had already mentioned in [5] that a common fault in the  driver
software for banking security modules was that `key parity error'
messages were often ignored rather  than  copied  to  the  bank's
security  manager  to  give  warning of an attempted attack. This
note shows that key parity is even more serious than that.

The nature of DES key redundancy now appears to be a  design  er-
ror;  it  would have been much better to calculate the redundancy
on the whole key. The 16 bit MAC used in the Clipper and Capstone
chips is preferable (although as shown in [6], 16 bits may not be
enough to prevent some protocol attacks).

The lesson for bankers is that  existing  security  modules  (and
other cryptographic devices) should be destroyed carefully at the
end of their working life.

The lesson for security engineers  is  that  we  should  add  key
redundancy, and the question of whether we can rely on a device's
eventual destruction, to the growing list  of  system  parameters
that  must be (a) explicitly considered during design and (b) ex-
amined carefully when the product is being evaluated.

[1] ``The Next Stage of Differential Fault Analysis: How to break
completely  unknown  cryptosystems'',  Eli Biham, Adi Shamir, Oc-
tober 30th, 1996

[2] ``Tamper Resistance - A  Cautionary  Note'',  Ross  Anderson,
Markus Kuhn, to appear at Usenix Electronic Commerce 96 (19th No-

[3] ``Hardwaresicherheit von Mikrochips  in  Chipkarten'',  Osman
Kocar,  Datenschutz  und  Datensicherheit  v 20 no 7 (July 96) pp

[4] ``Secure Deletion  of  Data  from  Magnetic  and  Solid-State
Memory'', Peter Gutmann, Usenix Security 96 pp 77--89

[5] ``Why Cryptosystems Fail'', Ross Anderson, in  Communications
of the ACM v 7 no 11 (Nov 94) pp 32--40

[6] ``Protocol Failure in  the  Escrowed  Encryption  Standard'',
Matt  Blaze, in Proceedings of the 2nd ACM Conference on Computer
and Communications Security (2-4 November 1994),  ACM  Press,  pp