chap-9.html
92f4e7972867f2ef1b9d56750a0e1eb580571e2fb9827a188880dadfe8bcf9cb<!DOCTYPE HTML PUBLIC "html.dtd">
<HTML>
<HEAD>
<TITLE>Cracking DES: Secrets of Encryption Research, Wiretap Politics, and
Chip Design </TITLE>
</HEAD>
<BODY BGCOLOR="#ffffff">
<P><FONT SIZE="-2">
Note: Yvo Desmedt granted permission on August 1, 1998 to publish this chapter.
Mr. Desmedt stated that he is responsible only for this chapter and not the
book. His current addresses are the University of Wisconsin - Milwaukee,
and the University of London.
<<A HREF="mailto:desmedt@cs.uwm.edu">desmedt@cs.uwm.edu</A>>. And,
"Note that it is said in the book that this paper was presented at Eurocrypt
'87, which is incorrect. A more general paper, with a different title was
presented at Eurocrypt '86. The chapter may have been presented at a rump
session, but I do not remember it."</FONT>
<H1>
<A NAME="9">9</A>
</H1>
<H2>
<I>Breaking One Million DES Keys by Yvo Desmedt</I>
</H2>
<P>
<I>In This chapter.</I>
<P>
<UL>
<LI>
<I>Abstract</I>
</UL>
<UL>
<LI>
<I>Introduction</I>
</UL>
<UL>
<LI>
<I>The basic idea</I>
</UL>
<UL>
<LI>
<I>Details of such a machine</I>
</UL>
<UL>
<LI>
<I>Obtained results and remarks</I>
</UL>
<UL>
<LI>
<I>Conclusion</I>
</UL>
<UL>
<LI>
<I>Acknowledgement</I>
</UL>
<P>
<P>
<I>This paper was presented at Eurocrypt 1987 by Yvo Desmedt and Jean-Jacques
Quisquater, under the title "An Exhaustive Key Search Machine Breaking One
Million DES Keys". We publish it here for the first time, since no proceedings
were made. It points out some research directions in parallel brute force
codebreaking that are still useful today.</I>
<H3>
<I>Abstract</I>
</H3>
<P>
The DES is in the commercial and industrial world the most used cryptoalgorithm.
A realistic exhaustive key search machine will be proposed which breaks thousands
of keys each hour, when DES is used in its standard 8 byte modes to protect
privacy. Also authenticity protection with DES is sometimes insecure.
<H3>
<I>Introduction</I>
</H3>
<P>
The DES is the NBS* and ANSI<SUP>+</SUP> standard for encryption. It has
been proposed to become an ISO<SUP>#</SUP> standard, under the name DEA1.
From the beginning Diffie and Hellman mentioned that one DES key could be
broken under a known plaintext attack using an exhaustive keysearch
machine.<SUP>§</SUP> However the design was criticized because practical
problems as size and power dissipation were not taken into
<P>
___________________
<P>
<SMALL>* "Data Encryption Standard", FIPS (National Bureau of Standards Federal
Information Processing Standards Publ.), no. 46, Washington D.C., January
1977.</SMALL>
<P>
<SMALL>+ "Data Encryption Algorithm", ANSI X3.92-1981, (American National
Standards Institute), New York, December 31, 1980.</SMALL>
<P>
<SMALL># "Data Encipherment, Specification of Algorithm DEA1", ISO/DP 8227
(Draft Proposal), 1983.</SMALL>
<P>
<SMALL>§ Diffie, W., and Hellman, M.E.: "Exhaustive cryptanalysis of
the NBS Data Encryption Standard", Computer, vol. 10, no. 6, pp. 74 -84,
June 1977.</SMALL>
<P>
<I>9-1</I>
<P>
<HR>
<P>
<I>9-2</I>
<P>
consideration. Hoornaert* proposed last year a realistic exhaustive keysearch
machine, which solved all practical problems. Instead of breaking DES in
half a day (as in the Diffie-Hellman machine), the cheap version ($1 million)
needs maximum 4 weeks to find the key. In practice however companies or secret
agencies want to break several keys at once. Indeed for doing industrial
espionage, companies want to break as many communications as possible of
their main competitors. Secret agencies want to be able to eavesdrop all
communications and to follow up industrial developments in other countries
which may be used for military purposes. The above machine is unpractical
or expensive for this purpose. Instead of using thousands of machines for
breaking thousands of keys, one modified machine is enough.
<H3>
<I>The basic idea</I>
</H3>
<P>
At first sight if one wants to break one million keys with an exhaustive
machine one needs one million pairs (plaintext,ciphertext)=(Mi,Ci) and do
the job for each different pair. If all these pairs have the same plaintext
M, the exhaustive machine can do the same job by breaking all these one million
ciphertexts, as in the case it had only to break one. This assumption is
very realistic, indeed in letters some pattern as e.g."Yours Sincerely" are
common. For all standard<SUP>+</SUP> 8 bytes modes a partially known plaintext
attack is sufficient. In the case of ECB a ciphertext only attack is sufficient.
Indeed the most frequent combination of 8 bytes can easily be detected and
used. Evidently more machines can handle more different plaintext patterns.
So, a few machines can break millions of keys. The number of different patterns
can be reduced by using a chosen plaintext attack!
<H3>
<I>Details of such a machine</I>
</H3>
<P>
Although we did not built it, in this section sufficient details are given
to show that such a machine is feasible. The machine will be based on a small
extension of the DES chips used in Hoornaert's machine. We will call the
ciphertexts for which one wants to break the key: "desired" ciphertexts.
In one machine, each of the (e.g.) 25 thousand DES chips will calculate
ciphertexts for variable keys starting from the same 8 byte "plaintext" pattern.
The machine has to verify if such a ciphertext is the same as some "desired"
ciphertext. If so, it has to communicate the corresponding key to the Key
Handling Machine (KHM) and the "number" of the "desired" ciphertext. However
each used DES chip generates each second about
<P>
___________________
<P>
<SMALL>* Hoornaert, F., Goubert, J., and Desmedt, Y.: "Efficient hardware
implementations of the DES", Advances in Cryptology, Proceedings of Crypto
84, Santa Barbara, August 1984 (Lecture Notes in Computer Science,
Springer-Verlag, Berlin, 1985), pp. 147-173.</SMALL>
<P>
<SMALL>+ DES modes of operation", FIPS (NBS Federal Information Processing
Standards Publ.), no. 81, Washington D.C., December 2, 1980.</SMALL>
<P>
<HR>
<P>
<I>9-3</I>
<P>
one million pairs (ciphertext, key). This gives a major communication problem.
Indeed all this information (about 110Mbit/sec.= (56 key bits + 64 ciphertext
bits) x 1M DES/sec.) cannot be communicated constantly outside the chip.
To avoid this communication problem, the chip will internally exclude ciphertexts
which certainly are not equal to a "desired" ciphertext. So only a fraction
has to be communicated to the outside world. Hereto the "desired" ciphertexts
were previously ordered based on their first 20 bits, which are used as address
of the desired ciphertexts. If more than one of these "desired" ciphertexts
have the same 20 first bits then one of them will later be transferred to
the exhaustive machine. The others will be put on a waiting list. In the
exhaustive machine bits of the desired ciphertexts are spread in RAMs, as
explained later, using the 20 first bits as address. Each extended DES chip
is put on a hybrid circuit together with 4 RAMs of 1Mbit and a refresh controller
(see also fig. 1<I>[not provided]</I>). For each enumerated key the DES chip
communicates the 20 first bits of the corresponding generated ciphertext
to the RAMs as address. The 4 bits information stored in the RAMs correspond
to the next 4 bits of the desired ciphertexts. The RAMs communicate to the
modified DES chip these 4 bits. Only if these 4 bits are equal to the
corresponding ones in the generated ciphertext, the generated pair (ciphertext,
key) is communicated outside the DES chip to a local bus (see fig. 1). So
in average the communication rate is reduced, by excluding the ciphertexts
which are certainly not desired. About 10 of these hybrids are put on a small
PCB. A custom designed chip checks the next 10 bits (the bits 25 till 34)
of the ciphertexts using the same idea as for the 4 bits (the bits 21 till
24). Hereto 10 RAMs each of 1Mbit are used, the address is again the first
20 bits of the generated ciphertext. Only if the check succeeds the pair
(ciphertext, key) is communicated to the outside world via a global bus.
This reduces the communication between the local bus and the global bus with
a factor 1000. About 2500 similar PCBs are put in the machine. The last 30
bits of the ciphertext are checked further on. Hereto similar hardware controls
several PCBs. Finally a small machine can do the final check. The machine
KHM checks the correctness of the key on other (plaintext, ciphertext) pairs
or on the redundancy in the language. Once each (e.g.) hour the machine KHM
will update the broken keys and put the ones which are on the waiting list
into the exhaustive machine (if possible). Suppose that one hybrid cost $80,
then the price of $3 million (25,000 x hybrid + custom chips + PCBs + etc)
for this machine is realistic.
<P>
<HR>
<P>
<I>9-4</I>
<H3>
<I>Obtained results and remarks</I>
</H3>
<P>
The described machine breaks about one million keys in 4 weeks, or in average
about 3000 keys each hour. By updating the broken keys better results can
be obtained.* Practical problems as buffering, synchronization, MTBF, power
dissipation, size, reloading of the RAMs and so on are solved by the author.
Optimizations under several circumstances and variants of the machine are
possible. In view of the existing rumors that a trapdoor was built in DES
by NSA, the feasibility of this machine shows that a trapdoor was not needed
in order to break it. Old RAM technology allowed to design similar (or larger)
machines which break less keys (e.g. thirty-two thousand keys). This attack
can be avoided if the users of DES use the CFB one byte mode appropriately,
or use new modes+ or triple encryption with two different keys. DES-like
algorithms can be designed which are more secure against the described attack
and which use a key of only 48 bit, and which have the same encryption/decryption
speed as DES (if used with fixed key).<SUP>#</SUP> The protection of the
authenticity of (e.g. short) messages with DES is sometimes
insecure.<SUP>§</SUP> These results combined with the above one, shows
that the authentication of standardized messages with DES may be worthless.
Remark finally that the DES chip used in this machine does not use the state
of the art of VLSI. Indeed about only 10,000 transistors are used in it.
Megabits RAMs are easily available.
<H3>
<I>Conclusion</I>
</H3>
<P>
Every important company or secret agency over the world can easily build
such a machine. Because it is not excluded that such machines are already
in use by these organizations, the author advises the users to be careful
using DES. Because the most used modes are breakable, the users have to modify
their hard- or software in a mode which avoids this attack. Meanwhile only
low-sensitive information can be transmitted with DES. If the authenticity
of the messages is protected with DES under its standardized use, short messages
have to be enlarged.
<P>
___________________
<P>
<SMALL>* Desmedt, Y., "Optimizations and variants of exhaustive key search
machines breaking millions of DES keys and their consequences on the security
of privacy and authenticity with DES", Internal Report, ESAT Laboratory,
Katholieke Universiteit Leuven, in preparation.</SMALL>
<P>
<SMALL>+ Quisquater, J.-J., Philips Research Laboratory, Brussels, paper
in preparation.</SMALL>
<P>
<SMALL># Quisquater, J.-J., Desmedt, Y., and Davio, M.: "A secure DES* scheme
with < 48 bit keys", presented at the rump session at Crypto '85, Santa
Barbara, August, 1985</SMALL>
<P>
<SMALL>§ Desmedt, Y.: "Unconditionally secure authentication schemes
and practical and theoretical consequences", presented at Crypto '85, Santa
Barbara, August, 1985, to appear in the proceedings: Advances in Cryptology
(Springer-Verlag, Berlin, 1986).</SMALL>
<P>
<HR>
<P>
<I>9-5</I>
<H3>
<I>Acknowledgement</I>
</H3>
<P>
The author is sponsored by the Belgian NFWO. The author is very grateful
to F. Hoornaert, IMEC-ESAT, Leuven, and J.-J. Quisquater, Philips Research
Laboratory, Brussels, for many suggestions and improvements.
<P>
Y.Desmedt <BR>
ESAT Laboratory <BR>
Katholieke Universiteit Leuven <BR>
Kard. Mercierlaan 94 <BR>
B-3030 Heverlee, Belgium
<P>
</BLOCKQUOTE>
</BODY></HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed