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:

 

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.


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/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (5)

  1. #1 Ralf Buelow
    29. September 2019

    Claude Shannon used “brute force” in connection with exhaustive searches in his 1950 paper about chess programming, see https://www.chessprogramming.org/Brute-Force He also worked for the Armed Forces Security Agency then, a forerunner of the NSA.

  2. #2 Ralf Buelow
    29. September 2019

    Just found: “It Wasn’t All Magic: The Early Struggle to Automate Cryptanalysis, 1930s-1960s” https://archive.org/details/NSA-WasntAllMagic_2002/page/n1 “Brute Force” is in the index.

  3. #3 George Lasry
    29. September 2019

    I would also include dictionary attacks in the list. And we have the ‘extended’ dictionary attacks that you the Gutenberg project (the two latest solutions by Richard Bean) or wikipedia (which I used to solved your cold war challenge).

    But as you mention, semi-brute-force (divide and conquer) attacks are probably more prevalent than pure ones. For example, the SHA-1 collision found recently.

  4. #4 Klaus Schmeh
    30. September 2019

    Nils Kopal via Facebook:
    I would suggest that the cyclometer that Rejewski developed in 1934 was maybe the first or at least one of the first brute-force devices for cryptanalysis. See https://en.m.wikipedia.org/wiki/Cyclometer

  5. #5 Klaus Schmeh
    30. September 2019

    Bill Ricker via Facebook:
    I might hold that the first brute force attack would have been trying all 26 (25) keys in a Caesar cipher. I presume you’re speaking however of automation of brute-force.

    The various enigma Bombe contraptions were checking all rotor orders and positions to check match to a menu that was based on multiple intercepts — effectively a depth for the ground settings of the indicators. That seems like a brute-force attack on the ground setting. Multiple other specialized hardware setups in WW2 may also qualify. TICOM documented machinery in the German Chi shop too.