Enigma Too Far?

Written by ysf

The first two crypto challenges where pretty quick to solve. Seeing the name I was very curious how this would turn out. The ENIGMA machine should be a very thrilling topic for every crypto fan. It’s been almost 25 years know that I read Bruce Schneiers Applied Cryptography and other books, but still remember how important solving the Enigma was for the Allies in WWII.

So What is this machine about? Straight from wikipedia:

Like other rotor machines, the Enigma machine is a combination of mechanical and electrical subsystems. The mechanical subsystem consists of a keyboard; a set of rotating disks called rotors arranged adjacently along a spindle; one of various stepping components to turn at least one rotor with each key press, and a series of lamps, one for each letter

Most people remember or even credit Alan Turing for cracking the Enigma. Unfortunately this is not the full story, Marian Rejewski did it in the 1930s! Another blatantly talented cryptographer whose biography you should dig into. Alan Turing built upon Rejewskis methods and found other attacks later on.

Back to the challenge:

Agent Bob is working at a law firm and loved history. He could not figure out how to crack
the python enigma emulator, even though it was broken before. Since he could not crack the
python enigma emulator, he decided that it would be ok to to encrypt all his emails with the
emulator before sending them. NOT A GOOD IDEA!! Can you crack it?

You have intercepted two messages. 

1. The first is "IPUXZGICZWASMJFGLFVIHCAYEGT". The second is "LTHCHHBUZODFLJOAFNNAEONXPLDJQVJCZPGAVOLN"
2. You have decrpted the first message and found that it is "HOWDYAGGIESTHEWEATHERISFINE"
3. Assume that "I II III" are rotors.
4. Plugboard is "AV BS CG DL FU HZ IN KM OW RX"

What is the flag? (The flag is in a slightly different format.)

My first impulse was to try some kind of text sliding attack as I remember the key weakness of Enigma was that no character could be encrypted to itself. (A in cleartext could not become an encrypted A). However I think that’ll take way more data to solve, so why not take the python enigma emulator as a big hint and, as always when playing CTFs, head for the low-hanging fruit.

Googling “Python enigma emulator” 1st hit is Py-Enigma:

Py-Enigma is a historically accurate Enigma machine simulation library written in Python. Py-Enigma includes a simple command-line application to allow for quick experimenting and scripting.

Sounds nice so far. There is even a Quick Example on their site:

from enigma.machine import EnigmaMachine

# setup machine according to specs from a daily key sheet:
machine = EnigmaMachine.from_key_sheet(
    rotors='II IV V',
    reflector='B',
    ring_settings=[1, 20, 11],
    plugboard_settings='AV BS CG DL FU HZ IN KM OW RX')

machine.set_display('WXC')            # set machine initial starting position
msg_key = machine.process_text('KCH') # decrypt the message key
machine.set_display(msg_key)          # decrypt the cipher text with the unencrypted message key

ciphertext = 'NIBLFMYMLLUFWCASCSSNVHAZ'
plaintext = machine.process_text(ciphertext)

print(plaintext)

Yay! Looks even better. Now it resolves to passing the data we’ve been given and brute force the rest. Let’s see what we’ll need to setup EnigmaMachine.from_key_sheet() and machine.set_display()

rotors              # we have those
reflector           # missing
ring_settings       # missing
plugboard_settings  # we have those
set_display()       # missing

Duh’. That’ll take quite some time. Sticking to the plan I chose to write down the brute forcer and start helping on other categories while it run in the background. After digging through the documentation I came up with following ranges to brute force:

reflector -> 'B', 'C', 'B-Thin', 'C-Thin'
ring_settings -> [1..25, 1..25, 1..25]
set_display -> 'A..Z' + 'A..Z' + 'A..Z'

Luckily it’s quite easy to generate those inputs in python without much charset increment if then else modulo loop kung-fu! Pythons itertools - Functions creating iterators for efficient looping handle everything. The helper we’re looking for is called itertools.product(). If you don’t know it, feel free to play with it in the (i)python REPL/shell:

In [1]: import itertools

In [2]: list(itertools.product('ABC', 'xy'))
Out[2]: [('A', 'x'), ('A', 'y'), ('B', 'x'), ('B', 'y'), ('C', 'x'), ('C', 'y')]

The algorithm to crack agent Bobs message should do the following:

1. Loop through every possible setting of reflector, rotor and set_display
2. Decrypt the first message using the current setup
3. Compare the decrypted message with given plaintext (“HOWDYAGGIES…”)
4. Repeat the loop until they match.
5. If they do, you found the correct setup! Decrypt the second message using the same configuration.
6. Print the decrypted message and quit

The following python script implements almost all of it:

#!/usr/bin/python

import string
import itertools

from enigma.machine import EnigmaMachine

# given by challenge
first_message  = "IPUXZGICZWASMJFGLFVIHCAYEGT"
second_message = "LTHCHHBUZODFLJOAFNNAEONXPLDJQVJCZPGAVOLN"
plaintext      = "HOWDYAGGIESTHEWEATHERISFINE"
plug_board     = 'AV BS CG DL FU HZ IN KM OW RX'

def new_machine(ring_config):
    return EnigmaMachine.from_key_sheet(
           rotors = 'I II III',
           reflector = 'B', 
           ring_settings = ring_config,
           plugboard_settings = plug_board)

if __name__ == '__main__':
    ring_space = itertools.product(list(range(25)), repeat=3)

    for setting in ring_space:
        start_pos = itertools.product(string.ascii_uppercase, repeat=3)
        enigma = new_machine(setting)

        # let's show that we're still running
        print("current setting: {}".format(setting)) 
        for position in start_pos:
            current_display = ''.join(position) 
            enigma.set_display(current_display)

            current_plaintext = enigma.process_text(first_message)

            if plaintext != current_plaintext:
                continue

            enigma.set_display(current_display)
            print("Flag: ", enigma.process_text(second_message)); 

            exit()

If you check the script thouroughly you’ll notice that it does not loop through all the possible reflector setups. Allowing only four different settings (B, B-Thin, C, C-Thin) the reflector had the lowest key space. I chosed not to brute through it in program but started the script four times running parallel, with different reflector settings for each instance, instead. That would save some time and follow my gut instinct that the reflector might be the default value ‘B’. This is due to the nature of CTF events, the creators want it to be fun and maybe even hard, but try to lessen the useless time you have while solving the challenges.

After running for a minute or so, the ‘B’ reflector instance was successful already and showed (with more debug output at that time):

# reflector     = 'B'
# ring_settings = (0, 0, 15)
# set_display() = 'HYB'

PASSWORDISGIGEMXHISTORYROCKSLEARNCRYPTOX

Entering GIGEMXHISTORYROCKSLEARNCRYPTOX solved the challenge! Yay! Actually a quite straight forward solution but it did not have much solves at that time.

If you’re still reading, you seem to be interested in that topic. Why don’t you grab a bag of chips and watch some youtube videos starting with Numberphile on Enigma and please, whenever you hear someone crediting Alan Turing for cracking it again, mention Marian Rejewski too!