BombeMachine

High Level Design

Figure 1: Enigma Design

Background

First, we recreated the Enigma machine that is used to encrypt and decrypt messages. The main components of an Enigma are the plugboard, the three rotors, and the reflector.

The plugboard appears twice and consists of up to 10 pairs of letters that are swapped using cables. In the example above, T enters the plugboard and exits after being swapped for K. The plugboard is also reciprocal, meaning that if G is connected in the plugboard to W, then that means W must also be connected to G. The largest contribution to the number of total possible combinations for the Enigma results from the plugboard

There are 3 rotors, with each having 26 pins on both the input/output and internal scrambled wiring for all 26 letters. For every key press, the rightmost rotor moves one step. When the rightmost rotor reaches a certain position, the middle rotor moves one step. Similarly, when the middle rotor reaches a certain position, the left rotor moves one step.

Lastly, the reflector connects letters in pairs. In terms of the overall flow when a letter is encrypted, it first passes through the plugboard, the three rotors, the reflector, the three rotors again, and then the plugboard again.

The key of a message is which rotors are used, the rotor order, starting position of the rotors, which reflector is used, and the plugboard connections. If two Enigma machines are set up the exact same way and one uses the first one to output an encrypted message, one can then use the other Enigma machine to input the encrypted message and get the original message out. The plugboard connections add the most amount of complexity and combinations. We implemented the Enigma machine in both Verilog and C.

The Bombe machine takes advantage of the plugboard being reciprocal, and how the Enigma cannot encrypt a character to itself. First, we can utilize that flaw and also our knowledge of stereotypical phrases that will always appear in an encrypted message (another potential weakness of the Germans’ encryption scheme). For example, WETTERVORHERSAGE, which means “weather forecast in German, was a phrase always present in one of the morning messages.

We can use this to find a crib, a piece of clear text corresponding to a part of an encrypted message. We look for a correspondence where, for all letters in the crib, the same letter does not appear in the same position in the original and the encrypted message. When we find this, we know a potential position for where the known phrase (crib) sits in the encrypted message This crib can be used to make a menu, which is a graph where you draw a line between each letter and its encrypted counterpart. An example is shown below:

Figure 2: Example Crib and Menu

The goal is to have one connected graph with as many loops as possible. If a menu does not contain enough letters/loops, there will be more false stops on the Bombe meaning there will be a lot more work required to determine the correct key. As shown by the chain in green, we then find a connected sequence of at least 13 letters (12 links) that will be an input into the Bombe machine.

The Bombe machine, which can be thought of as consisting of multiple Enigma machines, is mainly used to figure out plugboard connections and consists of linked drum banks each processing one letter-encryption pair. During the war, a Bombe had 36 drum banks arranged in three rows of 12 drum banks per row. Each drum bank has 3 drums (representing the 3 rotors) and each bank represents just the rotor scrambler and reflector parts of an Enigma machine.

Figure 3: Bombe Machine Drum Arrangement

The machine works by making an assumption about the first plugboard mapping, deducing the other plugboard mappings, and checking for conflicts knowing that the same letter can not be mapped to two different letters on the plugboard. For example, if A is mapped to B from one plugboard mapping, we know that it is not possible for A also to be mapped to C. The Bombe stops when a specific plugboard setting that matches the crib is found, and can stop multiple times since there can be multiple possibilities.

These stops can result in partial plugboard mappings and therefore we must manually check afterwards for the additional plugboard connections for the letters not mapped by the Bombe. During WWII, this required a lot of patience and expertise from codebreakers as it was done by hand and with the help of a checking machine to slightly speed up the process.

Design Overview

To develop a better understanding of how to construct a Bombe machine, we first started off constructing an Enigma machine in C and then an Enigma module in Verilog, consisting of rotor modules, a stepping module, a reflector module, and a plugboard wired together.

We then created example cribs/menus (as described above) and moved on to recreating the Bombe machine which mainly consists of a drumbank of 12 drum modules (one for processing the beginning of each link of the 13 letter sequence we found from our graph). Each drum basically replicates a double-ended scrambler (just the rotor and reflector parts of the Enigma machine). We make an assumption about the mapping for the first input letter of the sequence, step all the rotors in each drum of the drum bank to the correct positions, and sequentially check each drum for a plugboard mapping that does not conflict with existing mappings. To check for conflicts, we use a 26-partition M10K memory block so we can check if there is a conflict/multiple mappings for one letter. If there is a conflict, we notify the top level Bombe module, use a different input plugboard setting, and restart the drumbank.

If no conflicts are found, we have a potential valid plugboard mapping. We used a recursive method written in our Bombe checker program in C to go through all possible combinations of the letters that weren’t already mapped to find the remaining mappings, finding all unique, non-repeating permutations of pairs. We then try each of these permutations in our C implementation of the Enigma machine, which is included in the Bombe checker program, to look for the correct mapping. With the user interface, we can then correctly decrypt messages now knowing the valid Enigma machine key.

Verilog

Enigma Machine in Verilog

As mentioned above, the Enigma machine in Verilog consists of rotor, stepping, reflector, and plugboard modules that are used in a main Enigma module that puts them all together.

The rotor module passes in the rotor input, rotor position, rotor configuration (I, II, or II) and the direction. To finally determine the letter to output, we first check which direction the letter is passing through the rotor (forward or backward) since a letter passes through each rotor once forward and then once backward. We then check which rotor config (I, II, or III) we are passing the letter through and then find the corresponding mapping which is the output of our module.

The stepping module is used to account for rotor turnover. In particular, if the rightmost rotor makes a full rotation (reaches position 25) the rotor position is then set back to position 0. If the rightmost rotor is in the middle of a rotation, we simply increment the position by 1. Similarly, we check if the rightmost and middle rotors have reached their specified rotor turnover positions and then change the step the positions of either the middle and left rotors respectively. If a reset signal is received, the module sets the rotor positions to inputted initial rotor positions.

The reflector module takes in a 5 bit input letter and outputs the letter swapped according to a predefined reflector setting we have set. For example, if the letter “A” was put into the module, the letter “Y” would be returned. Since the plugboard is reciprocal, if the letter “Y” was the input, the letter “A” would be returned. Similarly, the plugboard swaps letters in a reciprocal way for only the letters we are using in the plugboard.

The Enigma module operates synchronously and connects all the above modules. We are assuming preset rotor orders, rotor wirings, and reflector wiring, and the information we input into the Enigma module includes the initial rotor positions and the turnover positions. First, we instantiate plugboard1 which takes in the plugboard letter as an input. The output of plugboard1 feeds into the first rotor, which passes in that plugboard output, the rotor turnover position for the rightmost rotor, the rotor configuration (2 for the rightmost rotor) and the direction (forwards or backwards). Likewise, we pass the output of this to rotor 1 (the middle rotor) and then pass this into rotor 2 (the left rotor).

After passing through all 3 rotors once in the forward direction, we then pass that letter as the input to a reflector module which outputs a letter that then goes through the three rotors again in the opposite direction. Finally, the letter once again enters the plugboard as an input and exits as the output of the Enigma machine.

Bombe Machine Overview

For our implementation of the Bombe machine, we define a drum module as consisting of a double-ended scrambler (going through 3 rotors forward, a reflector, and then the 3 rotors backward) and an FSM for reading and writing to M10K memory. We use M10K memory with 26 partitions(corresponding to the 26 letters of the alphabet) of 5 bits each to give us the ability to read if a letter has already been mapped, and therefore if there are any conflicts that indicate an invalid mapping.

After drawing out the menu from the crib we’re using (as described in the background section), we use the 13 letter chain as an input to the Bombe machine. For example, if the chain we find is VGKHCYJNALSEP, we split this into two 12 letter sequences excluding the last and first letter respectively (VGKHCYJNALSE and GKHCYJNALSEP) which we call msg_input and msg_output.

Drum Module

At a high level, our drum module consists of an FSM that writes/reads from M10K memory and a double-ended scrambler. The scrambler combines three rotor modules, a stepping module, and a reflector module, with the input being the plugboard_passin_mapping.

The FSM starts in the INIT state when it is reset, disabling writing into M10K memory, setting the fault signal to 0, and setting the stepping count equal to the msg_position. It then moves into the STEPPING state where stepping_count is decremented until it is 0, meaning the rotors have been stepped to their correct position. We then move into the READ state where the read address for M10K memory is set as msg_output, we wait for one cycle for the M10K read, and then enter the RUN state where we look for faults/conflicts (such as if A is mapped to both B and C, which cannot happen). If a fault is found, we set run_fault to be 1, and move to the DONE state.

If instead, a fault is not found, we write the mapping by enabling M10K writes, setting the write address to be the output of the double ended scrambler, and setting the message to be written to msg_output (for example, writing B to A’s address). We then enter the WRITE state where we write the opposite way (for example, writing A to B’s address) and also write 1 to the corresponding bits for plugboard_out (a 26 bit value holding the current plugboard setting) for those two letters. Additionally, we set plugboard_passout_mapping equal to the output of the double-ended scrambler.

Figure 4: Drum Module FSM

Drum Bank Module

In the drumbank module, we have 12 drum modules, each corresponding to a different letter of the 12-letter chain that we are inputting into the Bombe machine, as described in the background section. We create the 12 drums using a generate statement, offsetting the input values/addresses that we instantiate each drum module with according to the instance number. We also instantiate the M10K memory, which consists of 26 partitions with a data width of 5 bits each. We use the M10K memory to check if a letter has already been mapped, and therefore if there are any conflicts that indicate an invalid mapping. If any of the drums have faults, the drumbank will have a fault signal.

To set up the drumbank, we have a simple FSM. First, we start in the INIT state when a reset signal is received. In this INIT state, we initialize both the drum and plugboard write enable signals as 0. We then move to the WRITE0 where we enable writing to the plugboard. We write the first letter of msg_input into the M10K for plugboard_passin_mapping (the first plugboard mapping that we pass in), and then in WRITE1, we correspondingly write plugboard_passin_mapping into the first letter of msg_input. From there, we move to the RUN state where we set the drum enable to 1 so the first out of our 12 drums knows when to start reading from M10K memory.

Bombe Module

The Bombe top-level module uses an FSM to try different input plugboard settings and restart the drumbank if there are any faults. As seen, the FSM starts in the INIT states where we initialize all variables and pass in the first plugboard mapping to test. We then remain in this RUN state until a bank fault is detected or the bank is done. If there is a bank fault, we move into the UPDATE state where we try different plugboard settings (meaning we try a different first mapping, leading to different mappings for the remaining 11 letters). We stop going to the UPDATE once plugboard_passin_mapping > 25, meaning we have tried all plugboard possibilities for the first letter of our 12-link sequence.

If we are in the RUN state and the bank instead sends a done signal, we enter the VALID state. This means that a valid/possible mapping has been found. If there are additional valid mappings found, the user can press 2 buttons (we use 2 buttons and a CONTINUE state to implement debouncing) to send the FSM back to the UPDATE state and try a different plugboard setting. If there are no additional valid mappings, we move to the DONE state, meaning all possible plugboards for our input have been found.

Figure 5: Bombe Top-level FSM

C Program

HPS Code

We use PIO ports to send data between the FPGA and the HPS. In particular, we send values like the initial rotor positions, rotor turnover positions, the reset signal, and the 13-letter chain found from our graph. While we split this into two 12 letter sequences excluding the last and first letter respectively, we also split those two 64-bit sequences into 2 variables of 32 bits each to pass through our PIO ports. The FPGA passes to the HPS the found plugboard mappings from the Bombe module and also ctrl signals that indicate whether the FPGA has found a valid mapping or is done with computation.

Hps_driver.c is the HPS code that runs in companion with the FPGA code. The main purpose of the HPS code is that it serves as the GUI that takes in user commands. After initialization, parallel port connections, and declaration variables, the while(1) loop takes in user input. It first calls the printf function to ask the user for the command and then uses the scanf function to take user input and store that in the input buffer.

In the if statements, we use the strcmp function to check the input_buffer for certain commands. After the user inputs in “reset”, they will first be asked to enter “Y” or “N” to decide whether the program runs with default settings. If the answer is yes, it will print out the default settings, which involve a default test case we have. Otherwise, it will prompt more scanf functions that ask the user to input rotor position, rotor turnover letters, input message, output message, and rotor positions. Once that information is received, the values will be assigned to the output ports to the FPGA. If the user types in the “read” command, all the settings and the discovered plugboard mappings will be displayed in a formatted and organized manner. Since the discovered plugboard mapping is most likely a partial mapping, we then use this as an input to our Bombe checker.

Bombe Checker in C

The Bombe machine is an effective tool in eliminating a large number of incorrect plugboard settings, but after such elimination, there is still a large amount of possible but unverified plugboard settings. We know that a letter may or may not be matched in a plugboard and once it is mapped to another letter, those two letters are matched to each other. One needs to take all the unmatched letters in the plugboard and test out all the possible unique and non overlapping pairs. Back in WWII, this process involved an abundance of manpower and effort. We condensed this time intensive process to less than a second by developing a recursive C program that can create unique and non-overlapping pairs of letters from a list of unique letters.

Before digging into the detailed implementation, let’s first look at the complexity of such an algorithm. The number of possible pairs can be summarized by this equation:

Equation 1: Number of Permutations

where N is the total number of letters to be paired and P is the number of pairs. To select P pairs from N objects, there are N!/(N-2P)! ways. Since the ordering of those pairs and the order of the two objects in the pair do not matter, P! and (2!)^P are in the denominator. For example, there are 4!/((4-22)!2!(2!)^2)=3 unique pairs, as shown in the figure below. In our case, the maximal number of unique and non-overlapping pairs we will need to test is 14!/((14-62)!6!(2!)^6)=945945 number of pairs, when we are trying to find 6 unique pairs in 14 letters. While this looks like a huge number, it actually does not take the C program that long to run if we keep optimization in mind while implementing the algorithm. We later use the number of possible permutations to verify the correctness of our algorithm.

In the main function of the program, we first call the pairing_cleanup(). This function takes the output plugboard setting from the Bombe machine and creates an array to store the undetermined ones. It accomplishes this by labeling whatever already appears in the Bombe output in a 26-index array. Each index represents a letter from A to Z. After the labeling, we simply read out all the indexes that are not labeled and put them in an array. At this point, we will have an array with zeros and the same length as the number of unmatched letters. Each index of the unMatchedLetter[] array corresponds to an unmatched letter.

After we obtain the unmatched letters, we call the recursive function to find all remaining possible pairs. The findPair() function takes three inputs: number of pairs, an initial i value, and an initial j value. The number of pairs is the same as the number of recursive levels and ‘i’ and ‘j’ indicate the indexes of the first number and the second number that we are currently searching for. We also implement helper functions including findLastUnmatched() (that finds the last unmatched letter in the array), findSecLastUnmatched(), findFirstUnmatched(), and printUnmatchedLetter().

As mentioned before, if we are looking for N pairs, then the recursive function will be called recursively for N times. The variable level is decremented at each recursive cycle. When the level variable is larger than one, the function will find the next possible unmatched pair by searching the index after the current i and j. Once a possible pair is found, the current i and j indexes of the unmatchedLetter array need to be labeled to ensure the uniqueness of each pair. This is because on the physical plugboard, a letter can only be matched once. Then the findPair function will be called recursively with level-1. If i and j reach the end of the array, it means that the current level is already searched extensively; therefore the function returns. Whenever we find that the current index is not a correct plugboard setting, we need to unlabeled the index. There are also a series of boundary conditions to ensure nothing is out of bounds.

The base case is when the level is one, which means the function already finds the number of pairs we would like to try. We implemented an enigma_test() function to be called here. It runs our Enigma machine in C through the enigma_running() function and compares if the decrypted crib is the one we expected. If they are the same, the function will print out “Correct, continue?” and wait for the user input. When the user inputs “Y” the program will continue running to try to solve for other possible plugboard settings. If the enigma_test() function does not return a positive result, the label on the i and j indexes will be removed and i/j will be incremented in a manner that will cover all the possible cases.

For example, the below figure shows how the function operates when it tries to find two pairs in four letters. First, unmatchedletter array starts with 0000 since none of the indexes are labeled. In level2, the function first tries to grab the left two letters. “i” starts at index zero, and “j” starts at index one. Then the recursive call is spawned to level one, where it grabs the last two. If the plugboard setting is not matched, it returns to level 2 and then j will be incremented by 1. Therefore, 0 and 2 indexes are labeled. As you can see, this algorithm will then follow this routine and test three unique plugboard settings.

As mentioned before, if we are looking for N pairs, then the recursive function will be called recursively for N times. The variable level is decremented at each recursive cycle. When the level variable is larger than one, the function will find the next possible unmatched pair by searching the index after the current i and j. Once a possible pair is found, the current i and j indexes of the unmatchedLetter array need to be labeled to ensure the uniqueness of each pair. This is because on the physical plugboard, a letter can only be matched once. Then the findPair function will be called recursively with level-1. If i and j reach the end of the array, it means that the current level is already searched extensively; therefore the function returns. Whenever we find that the current index is not a correct plugboard setting, we need to unlabeled the index. There are also a series of boundary conditions to ensure nothing is out of bounds.

Figure 6: Recursion for Finding Remaining Plugboard Permutations

Testing, Analysis & Results

Demo of Bombe Machine Operation

As shown in the video at the attached link, we show a screen recording of the example we presented at our final demo. Our crib is THEYSAYECESCANDOEVERYTHING and we encrypt the message using our Enigma machine implemented in C, meaning we know the key used (the plugboard settings, rotor settings, etc.). We also know the initial rotor positions, initial rotor turnover positions, as well as the 13-letter chain (split into two messages) that we found when creating a menu from our crib previously. First, we reset the Bombe and input those 13 letters as well as their corresponding stepping positions according to the menu as an input to the Bombe.

From there, we can see the Bombe machine generates a list of discovered plugboard mappings. Since this is not the full mapping, we then plug our discovered plugboard settings into our Bombe checker program, which finds which letters have not been matched and checks the other possible combinations. After finding the correct mapping, we can test it on our original encrypted message. Additionally, we added GOBIGRED to the end of our original message and put it through our Enigma machine with the discovered plugboard settings to confirm that our Bombe machine has found the correct plugboard mappings. We repeated this process for several test cases to ensure the accuracy and efficiency of our system.

Demo of Bombe Machine Operation

To calculate the exact duration of the bombe computation, we added a cycle count feature. In the demo, we showed that it takes 302 cycles to find one valid solution. Given that the clock speed is 50MHz, the time it takes is 6.04 microseconds. Searching through all possible input takes 1131 clock cycles, which is equivalent to 22.62 microseconds. Considering this process used to take 20 minutes (1200000000 microseconds), we accelerated the process by about one million times.

Bombe Checker Computation Time

Figure 7: Average Time vs Number of Pairs for 14 Unmatched Letters

Figure 8: Average Time vs Number of Unmatched Letters for 4 Pairs

The above charts and plots illustrate how the computation time and the number of unique pairs found change with the number of unmatched letters and the number of pairs (N and P values in equation one). The number of unmatched letters matches the number we calculated from the equation. Therefore, we know the recursive search is extensive and complete. From the plots, we can see that the average time of computation increases logarithmically since the plot is almost linear when plotted in the semilog scale. We can also see that the longest computation time it will take is only 63.090 ms, which is much faster compared to doing the search manually back in WWII.

Given the same plugboard settings, initial rotor position, and rotor settings, the Enigma machine has deterministic outputs. Therefore, the Bombe machine, which eliminates the plugboard settings, and the Bombe checker, which linearly tries out all the possible remaining settings, will guarantee that we find the correct plugboard setting. Because of this, our design has an accuracy of 100%.

As described in the HPS implementation section, our GUI on the HPS part of the DE1-SoC is concise and user-friendly. The user simply needs to follow the instructions prompted on the command window to put in very simple commands. The display of the output of the Bombe machine is also direct and clear and the GUI for the Bombe checker C program is implemented in a similar manner. While the HPS code and the Bombe checker C program are currently two separate programs, they were actually two separate procedures back in WWII so this user workflow makes sense. If we had more time, we would like to integrate them to enhance the user experience.

Conclusion

Based on the successful results from our test cases and user feedback, we are satisfied with how well our design meets our expectations and replicates the hardware of the actual Bombe machine built during WWII. Eighty-two years after it was invented, we preserved its original algorithm in hardware but shortened its computation time tremendously. Considering how many more resources we have and how we were replicating a pre-existing design, we appreciate this ingenious mechanism even more.

Since we tried to closely follow the original Bombe algorithm described in a Turing Bombe Tutorial by Magnus Ekhall and Fredrik Hallenberg, there is not much we would want to change in our algorithm. One thing we could add is being able to check for different rotor orders or reflector options, since this is something that generates a reasonable number of options that are checkable by the Bombe. With the already high complexity of our project, we did not choose to add this to our current design, but it could be added to further replicate the original machine.

Regarding usability, currently we need to manually enter the output of the Bombe into the Bombe checker program to obtain the final solution. If we had more time, we would automate our system further by combining those parts. The user would then only need to interface with the HPS GUI, and thus enhance the usability.

From a system perspective, we can improve our overall timeline and the integrity of our system. We tried to implement our system by following the order of decrypting a message: implementing the Enigma, the Bombe, and, lastly, the Bombe checker. If we had a better understanding of the overall system in the first place, we could have worked on multiple pieces in parallel to save time.

In terms of intellectual property, we are replicating in code the designs of the Enigma and Bombe machines, which were existing complex electromechanical machines. The Enigma machine was patented in the US on November 12, 1929 (US1905593) but the patent was never renewed and therefore expired 20 years after it was patented. It is legal to recreate it in any form we want. There is no patent for the Bombe machine and we did not use any code in the public domain to create our version of the Bombe machine in Verilog.

Bombe

Machine

Angela Zou, Kathleen Wang, Robby Huang

Project Introduction

High Level Design

Background

Design Overview

Verilog

Enigma Machine in Verilog

Bombe Machine Overview

Drum Module

Drum Bank Module

Bombe Module

C Program

HPS Code

Bombe Checker in C

Testing, Analysis & Results

Demo of Bombe Machine Operation

Demo of Bombe Machine Operation

Bombe Checker Computation Time

Conclusion

Appendix

Appendix A

Appendix B (References)

Appendix C (Code)

Contact

Info

More