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. <desmedt@cs.uwm.edu>. 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."
In This chapter.
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.
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.
The DES is the NBS* and ANSI+ standard for encryption. It has been proposed to become an ISO# 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.§ However the design was criticized because practical problems as size and power dissipation were not taken into
___________________
* "Data Encryption Standard", FIPS (National Bureau of Standards Federal Information Processing Standards Publ.), no. 46, Washington D.C., January 1977.
+ "Data Encryption Algorithm", ANSI X3.92-1981, (American National Standards Institute), New York, December 31, 1980.
# "Data Encipherment, Specification of Algorithm DEA1", ISO/DP 8227 (Draft Proposal), 1983.
§ Diffie, W., and Hellman, M.E.: "Exhaustive cryptanalysis of the NBS Data Encryption Standard", Computer, vol. 10, no. 6, pp. 74 -84, June 1977.
9-1
9-2
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.
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+ 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!
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
___________________
* 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.
+ DES modes of operation", FIPS (NBS Federal Information Processing Standards Publ.), no. 81, Washington D.C., December 2, 1980.
9-3
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[not provided]). 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.
9-4
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).# The protection of the authenticity of (e.g. short) messages with DES is sometimes insecure.§ 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.
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.
___________________
* 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.
+ Quisquater, J.-J., Philips Research Laboratory, Brussels, paper in preparation.
# 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
§ 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).
9-5
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.
Y.Desmedt
ESAT Laboratory
Katholieke Universiteit Leuven
Kard. Mercierlaan 94
B-3030 Heverlee, Belgium