At the NSA Symposium on Cryptologic History, I will give a presentation about brute-force attacks. There’s one thing I still haven’t figured out: when was the first brute-force described or carried out?
Every second year, the Center for Cryptologic History, operated by the NSA, hosts a symposium dedicated to the history of cryptology. It goes without saying that this event is an absolute highlight for me. The next issue will take place on October 2019, only three weeks from now. I will take part for the sixth time in a row.
Source: Schmeh
This time, I will give two presentations. The first one is about steganography used by prisoners of war and concentration camp inmates. The second one will be a part of a panel session I share with Jean-Jacques Quisquater, Marek Grajek and Nicolas Courtois. The topic of the panel is block ciphers. My talk will be about the history of brute-force attacks on block ciphers.
Brute force attacks
In computer science, the term “brute force” refers to methods that check every potential solution of a certain problem, until the correct one or the best one is found. In cryptology, a potential solution is usually represented by a key. Applying a brute-force attack on an encryption algorithm therefore means to decipher a certain ciphertext with one key after the other until the correct one is found. Such a method is also referred to as exhaustive key search.
An important question is how the correct key can be identified. In classical cryptography, one usually tests if the plaintext candidate has statistical properties that are similar to natural langauage. In modern cryptography, one typically assumes that the plaintext is known (known-plaintext attack), which means that checking if a certain key is correct, is trivial.
A brute-force attack on a modern crypto algorithm with 128 key bits or more, such as AES, is as good as impossible. Even if the correct key is found after, say, 0.1 percent of all keys checked, such an attack requires much longer than the time that has passed since the Big Bang.
Nevertheless, there have been successful brute-force attacks on modern symmetric ciphers. One reason for this is that the key length of the DES, the first non-classified modern cipher that found wide-spread use, is only 56 bit. In the 1990s, there were even crypto programs that worked with a 40-bit key – this was the maximum allowed to be exported from the USA.
Here are a few milestones in the history of brute-forece attacks on modern symmetric ciphers:
- 1977: First major publication about a brute-force attack on DES by Whitfield Diffie (Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard)
- 1996: Michael Wiener publishes the paper Efficient DES Key Search‘
- 1997: RSA Secret-Key Challenge
- 1997: Ian Goldberg breaks a 40 bit encryption within hours
- 1997: DESCHALL project breaks DES challenge after 96 days
- 1998: EFF DES Cracker (Deep Crack) breaks DES within 56 hours
- 1999: Deep Crack and distributed.net break DES within 22 hours and 15 minutes
- 2002: 64 bit RC5 encryption broken by distributed.net after 1,757 days
- 2006: COPACABANA (Cost-Optimized Parallel Code Breaker)
- 2009: MTC3 World Record Challenge
- 2017: Nils Kopal’s PHD thesis Secure Volunteer Computing for Distributed Cryptanalysis
- Future: Quantum computer attacks on symmetric ciphers
Early history of brute-force attacks
As can be seen above, there is plenty of literature about brute-force attacks on modern symmetric ciphers. However, it is still not clear to me which role brute force played in the pre-computer age. Of course, I know about WW2 codebreaking machines, such as the Turing Bombe and Colossus. Although these machines did not check every existing key, they implemented brute-force methods on parts of the key space.
Perhaps, my readers can help me to learn more about brute-force attacks in the pre-computer era. Does anybody know of machines that carried out brute force attacks? Are there examples of brute-force attacks executed by hand?
Answers on these questions are highly appreciated. And of course, I will credit everybody who provides information I will use in my presentation.
Follow @KlausSchmeh
Further reading: How I explained lettuce-based cryptography at a London conference
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (8)