DES utilized a 56-bit key (out of 64 bits, with 8 bits used for parity). While considered robust when standardized in the 1970s, the rapid advancements in computational power quickly rendered this key length inadequate.
By the mid-1990s, a 56-bit key became highly susceptible to **brute-force attacks**. Attackers could systematically try all 2^56 possible keys until the correct one was found, effectively compromising the encrypted data. This vulnerability was famously demonstrated by the EFF's "Deep Crack" machine, which could break DES in a matter of days.
This fundamental flaw highlighted the need for longer keys, ultimately leading to DES's deprecation in favor of stronger algorithms like Triple DES (3DES) and AES.
From
Date: Sun, 3 Nov 1996 18:16:37 -0500
From: Ross Anderson <
To:
Subject: BoS: Announcement - Warning to Crypto and Banking Communities
Resent-Date: Mon, 4 Nov 1996 15:51:30 +1100
Resent-From:
A serious weakness of DES
Draft - 2nd November 1996
Abstract
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 attack 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 allows
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.
Introduction
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 uninformative 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 enable
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 difficult, 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 restricted 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
world.
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 staff.
In this device, which dated from the late 1980's, the key values were
substantially intact on power-up. The number of bits in error was of
the order of 5-10%. I cannot give more accurate figures as I was not
permitted to copy down either the correct master 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 consequences.
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 involve (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 (decimalised) 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 individual.
Conclusions
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 error; 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) examined
carefully when the product is being evaluated.
Bibliography
[1] ``The Next Stage of Differential Fault Analysis: How to break completely
unknown cryptosystems'', Eli Biham, Adi Shamir, October 30th, 1996
[2] ``Tamper Resistance - A Cautionary Note'', Ross Anderson, Markus Kuhn, to
appear at Usenix Electronic Commerce 96 (19th November)
[3] ``Hardwaresicherheit von Mikrochips in Chipkarten'', Osman Kocar,
Datenschutz und Datensicherheit v 20 no 7 (July 96) pp 421--424
[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 59--67