A Turing/Welchman Bombe.

June 14th, 2015

This is the next step after my Enigma machine wristwatch project and putting my Orwell computer into a case. The next step was to investigate and hopefully simulate the Turing/Welchman Bombe. The Bombe is the machine used by the British in WW2 to help decode Enigma encoded messages. If you saw the film The Imitation Game you probably have some idea what the Bombe is.

IMG_3636 Enigma machine wristwatch.

IMG_3783_1 Orwell 6502 computer.

Unfortunately your idea will be mostly wrong! Turing didn’t build the Bombe single handedly. He didn’t have to fight anyone to build it. It wasn’t called Christopher and it didn’t just spit out the solution ready to be entered into an Enigma machine to decode messages. Seems Hollywood can’t make a historical film without ‘tweaking’ it for the sake of story. They even made the actual physical machine different to reality, making it bigger and with more red cabling to make it look ‘alive’. The way they are shown operating it is all wrong too. And the drums don’t move correctly. Bah!

If you want the short(ish) version here is a film of what I am doing:

If you want to skip to seeing the Bombe code written in BASIC the go here: http://www.asciimation.co.nz/bb/2015/06/14/turing-welchma…mbe-basic-code

If you want the long version keep reading! I did comment once I didn’t think anyone reads all of this stuff I put up and got comments saying otherwise. We’ll see how that goes after this post. It’s kind of long!

Many thanks to John Harper, who lead the real Bombe rebuild team, for answering my questions about how a real Bombe worked. What I have done is simple compared to what John and his team did in reconstructing the real thing. That took years of hard work and research and it really is well worth going to Bletchley Park to see it in action (I am definitely going again next time I am over there).

Also thanks to Bletchley Park themselves who saw my Enigma watch project and when I explained I was also making a Turing Welchman Bombe they found a copy of Bletchley Park report 4 to send me. I actually joined the Friends of Bletchley Park. Obviously the free entry and events aren’t much use to me (me being in New Zealand) but I want to support what they do there and that is a good way to do it.

Also thanks to Magnus Ekhall who is one of the creators of the brilliant online Bombe simulator here. If you want to play with a Bombe yourself don’t bother with my version, go and try that one! That site has a good tutorial you can follow to wire up and run the Bombe in the same way they run the real one at BP. I used their version to double check that mine was giving the same results.

I should mention here, because if I don’t I will probably get comments about it, that yes, the Polish also had an Enigma cracking machine. That was called a Bomba. The Poles did indeed crack the Enigma code very early on. The machine the Poles made exploited a procedural flaw in the German method of enciphering. It similarly used the idea of multiple Enigma machines connected together (6 in their case). But other than that I don’t think the machines are in any way connected (other than by name maybe) as they work on totally different principles.

I wanted to find out what the real story was and how the Turing-Welchman Bombe really works. Wikipedia gives all the basic details as do many other sites about. And there is of course the reconstructed Bombe at Bletchley Park in the UK which is well worth seeing.

The best places to read about the Bombe are as follows:

https://en.wikipedia.org/wiki/Bombe

http://www.ellsbury.com/enigmabombe.htm

http://www.codesandciphers.org.uk/virtualbp/tbombe/tbombe.htm

http://www.rutherfordjournal.org/article030108.html

That last link is a cut down version of Bletchley Park report 4 available here.

Other useful books and documents are Demystifying the Bombe by Dermot Turing (Alan Turing’s nephew).

Gordon Welchman’s Hut Six Story has some good details, especially on the diagonal board.

And the US Army 6812th Division Report from 1944 available on the late Tony Sale’s site.

The other site that will be extremely useful for the physical part of the build is John Harper’s Bombe rebuild site. John has been very helpful answering some of my questions and letting me know some of the details of the real Bombe and how it works. The site is a little out of date now he tell’s me but the information there is brilliant.

And of course the best thing you can do is go to Bletchley Park itself and see the reconstructed Bombe running!

I set about figuring out how the Bombe works myself so I could build my own version in software. I’ll give how I worked out in my head how the Bombe works. This probably isn’t a good way to explain it, check out the links I provide for that, but this is how I think of it. In very simple terms what it is is a giant circuit tester. To know how it works you need to know how Enigma works of course.

Enigma can be thought of as a machine that changes an input letter into a different output letter. A letter can’t, due to the physical nature of the machine, become itself. The letters are changed by sending a current through three rotors, each of which changes the letter (or not!), then through a reflector (which always changes a letter hence no letter coming out as itself) and back through the three rotors (changing the letter each time again). There is also the plug board which swaps the input and output letter to some other letter (or not). We can ignore the plug board for now. After each letter is encoded the position of the rotors change (in a known pattern) so for the next letter encoded the current will take a different path though the machine. This is why if you hit the same key on an Enigma repeatedly a different letter is likely to come out each time.

To make the Bombe work we need what was called a crib. A crib is a guess of  what the unencoded text of an encoded message might be. For example if you have an encoded message and you know the last words in it are always ‘Heil Hitler’ that is you crib, you now have the encoded letters and what they decode too. For example the first H might appears as a ‘U’ in the encoded message. Because of the way Enigma and H entered will return a U and a U entered would return an H, for that given position of the machine.

That last bit is important. It works only in that position. The crib gives us two bits of information, what letter transformation took place and at what position did that happen.

The crib they use at Bletchley Park to demonstrate their real Bombe is the weather forecast crib shown below. Wetter vorhersage means weather forecast in German.

Position:      1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
Cipher text:   S  N  M  K  G  G  S  T  Z  Z  U  G  A  R  L  V
Plain text:    W  E  T  T  E  R  V  O  R  H  E  R  S  A  G  E

From the crib we can see at position 1 ‘W’ was encoded to ‘S’, at position 2 ‘E’ encoded to ‘N’ and so on.

With an Engima machine correctly configured typing in each letter of the plain text in sequence will give you the matching letter of cipher text. Also if you were to type in the cipher text you’ll get back the plain text. That’s how who ever receives the message can decode it as long as they use the same settings. The Bombe helps find the settings (it doesn’t crack teh code itself like the films have you believe).

Instead of using one Enigma machine imagine you had 16 of them, all with the same configuration i.e. same rotors, same rotor order, same reflector, etc. You type ‘W’ on the first one and get out ‘S’. If you now go to the second machine and type in ‘E’ the rotors would need to be moved on 1 position from the first machine in order to get out ‘N’. In a real machine that position change happens automatically when you press a key. If we have 16 Enigmas we’d have to set the positions ourselves manually, the second machine at position 2, the third at position 3 and so on.

When doing this we are ignoring things like the rotor turnovers. We’ll get to that in a bit.

Now if you don’t know what the rotors are or what the starting position is one way to work it is to try them all! So you set up your 16 Enigmas with the same three drums in the same order in each one. You set up the first machine with the wheels at ZZZ, the second one to ZZA, the third to ZZB and so on. Then you could see if the encodings at each position come out as you would expect. If a letter in the sequence comes out wrong you know that can’t be the right setting so you would try another, maintaining the same relative position for each of the machines.

Say you decided to try RST on the first machine. To maintain the correct relative positions you would set the second to RSU the third to RSV and so on. By doing that you could eventually run through all the positions until you found one where the sequence came out correctly. Since each wheel has 26 letters that means 26*26*26 or 17576 possible combinations.

The Bombe basically goes through all these combinations but it is using some cleverness to do the ‘checking’. Remember the Enigma work on electrical circuits. When a key is pressed a current is sent through from that letter and comes out another letter.

If we have out 16 Enigmas set up and could arrange it so that the current was sent from one machine to another instead of manually pressing keys we could trace where the current goes and make sure it comes out in the correct place.

If you look at the crib again you can see in the correct position a ‘W’ on the 1st machine should come out as an ‘S’. Looking along the crib we can see that at position 7 an ‘S’ turns into a ‘V’. If we wired up the machine so that the ‘S’ on the 1st machine went into the ‘S’ on the 7th machine that should cause the output to be a ‘V’. We could then also wire up the ‘V’ on the 7th machine to the ‘V’ on the 16th machine and get out an ‘E’. The ‘E’ could wire to the 2nd machine and output an ‘N’. The current is going though four different Enigma’s automatically rather than us checking each individually.

Note that is doesn’t matter if the letters we use were in the crib or in the cipher text. It doesn’t matter since the transformation works the same both ways.

For understanding the Bombe we can reduce the Enigma machine into what’s called a scrambler. A scrambler is an Enigma machine with a given rotor choice and order.  For now we ignore the plug board and we can also ignore the ring setting. A scrambler has 26 inputs and 26 outputs corresponding to the letters of the alphabet. At a given time, one letter goes into a scrambler and a different letter comes out. In Enigma the current goes into the machine via a ring of 26 contacts (one for each letter) then comes back out on the same ring in a different position. Our scramblers however are double ended. You have one ring of 26 contacts and a current on that ring will cause a current to appear on another ring of 26 contacts. This works in both directions so if ‘A’ on the first ring goes to ‘G’ on the second ring an ‘A’ on the second will go to an ‘G’ on the first. It doesn’t matter which way you send current through the scrambler, the transformation is the same.

These double ended scramblers let us easily connect up the letters in the menu as we did above and send currents though them. If you just send the current through one scrambler there is quite a high chance that the correct output letter is seen even if you have the wrong settings on the scrambler – a false positive. If you send it through one scrambler then send the output of that through another as we did above and the right letter comes up we’ve reduced our chance of a false positive because now both scramblers have to be in the right positions. In our example above we sent it through four scramblers which all have to be in the right position.

You can draw out what we did above like this:

W – S – V – E

The lines – represent the scramblers. We can write in what each scramblers relative position is.

W -(1) – S – (7) – V – (16) – N

We can go ahead and make other connections based on the crib we have. If we draw all these out we end up with a diagram like this:

IMG_3878

Since each scrambler, the lines on the above picture, is an Enigma machine we can show the positions as the positions of the three rotors in each scrambler. We assume a pre-starting position of ZZZ for the rotors so position one is then ZZA. Position 2 is ZZB and so on. In an Enigma machine the rotors move BEFORE the letter is encoded. So if the rotors are in position ZZZ the first actual encoding is done in position ZZA.

Redrawing we get this what is called a menu.

IMG_3877

What we now have is a diagram showing us all the transitions we know we should get from our crib and in what positions they happen and how they are linked together.

This is where things start getting complicated.

One thing you can see on the menu is we have a closed loop: G-E-V-S-A-R-G. If all the scramblers between all those letters are in the correct positions then we should have a closed loop. If you put a current in at G it should go around the loop of scramblers and only come out on G.

This seems simple enough but for one thing. Remember we ignored the plug board earlier. Now it is back to complicate matters. The menu shows us the transformations as if there were no plugboard. But the plug board was always used when encoding Enigma messages. It swapped 10 pairs of letters with another letter. So in the menu above the ‘G’ we see isn’t actually what we want to use as the input into the scramblers. This is because the ‘G’ in the message might have been through the plug board in which case the letter fed into the scrambler may be something totally different.

This is one of the clever bits Turing worked out. We make an assumption about what letter we think the ‘G’ in the message was connected to on the plug board. We feed that letter into the scramblers. So if we assumed ‘G’ was plugged to ‘k’ we would put a current on the ‘k’ input of those scramblers connected to ‘G’ in the menu. And because ‘G’ goes to ‘k’ then ‘k’ also goes back to ‘G’. We write the assumed partner lower case to avoid confusion with the menu letters.

Because we have a loop if feeding the voltage into ‘k’ isn’t correct it will come out on another letter. Turing’s idea was that the letter that did come back out  is then used as a new guess to what the partnering is. This happens automatically because of the way the machine is wired up. Remember the current flows both directions though the scramblers. I didn’t when I did my first algorithm but more on that later!  There are various possible outcomes when we do this.

You’ll note that those conditions above aren’t mutually exclusive. In the third case when the scramblers are in the wrong position we could end with similar result to the first two cases!

Now you might be able to see why the menu is important. The more loops you have the more chance there is of the current working it’s way around the circuit and eliminating the false positives. But you don’t want to have too many letters in the menu because something else we ignored will then come back to bite you.

In a real Enigma machine the rotors are arranged to turn over at certain points. In our menu we are assuming that this isn’t happening so that our relative positions are correct. If a turn over had occurred in the message during the crib text the relative positions of the rotors is now completely different. If you have a crib longer than 26 letters you know that a rotor turn over must have happened and so your relative positions will be all wrong after a certain point. If you have less that 13 letters in the crib you’re reduced the chance of that happening by half. You can’t have menus that are too short though because then you’re not providing enough paths for the currents to work their way around the machine.

The physical Bombe is wired up to do all this testing above. When you look at a picture of the Bombe you will see rows of drums. The drums are split into three banks, each has 12 columns and three rows. Each bank can be though of a separate machine electrically (they can be wired together though).  Typically a menu is wired up using one bank.

In a bank the columns are the rotors of our scramblers. So each column is one scrambler. The drums are versions of the Enigma machine rotors wired to be double ended. Each drum shows around it’s edge the letters of the alphabet, A-Z. The drums rotate clockwise and the letters are arranged to go in sequence (so reading the front of a drum the letters go backwards). The colour of the drums correspond to the number of the rotor. This is why when you see pictures of the Bombe (in colour!) the colour will be consistent across the rows of each bank. Remember each scrambler in a menu has the same rotors, just the relative positions of each rotor are different.

The machine also has three indicator drums on the front. These spin in synchronisation with the other drums and are important for telling us what the ‘stop’ is. That is the settings the machine is showing when it finds a possibly correct position for the drums. The indicator drums also spin clockwise but the letters are arranged in reverse order. This becomes important later.

The back of the machine allows wiring up of the menu. The scramblers (each column) are wired to other scramblers as shown on the menu. The reflectors are housed on the left hand side of the machine and each scrambler connects to them. The right side of the machine has switches to allow you to select the input test letter (‘k’ in our example above). Then there is what’s called a test register. This is connected to one of the letters in the menu (the connections between the scramblers). The test register shows the current on every input/output on the connected scramblers. There are other controls we don’t need to go into now.

The menu is wired up on the machine and the drums of the scramblers are set to their starting positions also shown on the menu. When the machine is turned on the test letter current is sent into the menu into the test register menu letter. From there it flows around the circuit to all points it can reach. The most likely situation is that the positions of the drums are wrong and so the current flows around and around and eventually (well, almost immediately since it moves at the speed of electricity!)  it gets to everywhere. Most likely it will get to all 26 terminals. In this case the machine steps ALL the scramblers to the next position. All of the have to move since we need to maintain the relative positioning. It then checks the next position.

If the current didn’t get to all 26 terminals then we might possibly have one of the conditions mentioned above so the machine stops. A stop doesn’t guarantee the position is correct however. Each stop had to be checked to find the wrong ones. That’s a whole other machine and procedure I haven’t even got to yet! A stop that doesn’t correspond to a correct position is called a false stop.

One interesting thing to note here is that while in an Enigma machine it’s the right most wheel that moves (so it it was at ZZZ it will go to ZZA) in the Bombe it is the top drum that moves (so it goes from ZZA to AZZ). Because we’re doing all the positions though this doesn’t matter! This is also why we can ignore (for now) the ring settings. In the Enigma the ring setting is just an offset of the internal wiring of the rotor from what letter it says it is on. Again because we are testing all positions we don’t need to worry about this yet.

The ring setting does however come into it later on when they use what the Bombe tells us to actually try to break the code. And it is also because of the ring setting that the indicator is lettered backwards.

The description above is of the Bombe as Turing designed it. You can see that the only letters involved are the ones actually in the menu since the current can only move between each letter via the connection through the scramblers. It relied very heavily on the menu containing loops so that current sent on the wrong path would flow back around to go though the loop again. With no loops the current would flow from one end of the menu to the other and not be able to feed back in. The test register would have many positions without current on them so the machine would stop. These are most likely false stops.

This is where Gordon Welchman comes into it. What he did was very clever and it’s a complete travesty he wasn’t even mentioned in that Imitation game film! This took me a long time to get my head around but apparently it took Alan Turing a minute or two to get it so I don’t feel too bad (despite it taking me months)!

Welchman realised that the plug board complexity actually helps us out but providing many more paths for the current to flow around the machine. The reasoning is this. We make an assumption that one letter is steckered to another, ‘G’ is steckered to ‘k’. Because the plug board swaps pairs of letters that mean that ‘K’ is also steckered to ‘g’. So in our machine is we send the current in on ‘k’ to menu letter ‘G’ and it comes back out on ‘r’ say we can now say ah-ha, because ‘r’ came out on ‘G’ then that means a current could also go from ‘R’ to ‘g’. So we create a new current and bung it back through the circuit. The way we create that extra current is with the diagonal board.

The diagonal board is literally that. There are 26 rows corresponding to the 26 letters of the alphabet that could be in our menu. Each row has 26 columns also corresponding to the alphabet letters. The rows and columns are wired together so that Row A, Column B goes to row B column A. Row A, Column C goes to Row C column A and so on. If you start drawing it out you see where the name comes from, the connections are physically diagonal!

IMG_3879

Basically the diagonal board vastly increases the number of currents flowing about in the machine and helps eliminate a lot of the false stops. It was a massive improvement on the origin Turing machine hence the machine becoming known as the Turing-Welchman Bombe. One thing to note about the diagonal board is that only the diagonals that are themselves involved in the menu help in this process. This is much easier to see in a software version than on the real machine.

If you’ve got this far this is a good time to point out another massive flaw in The Imitation Game film. In that Sherlock builds the machine and THEN figures out about the cribs from a girl who in the bar at Bletchley Park (that bar set really is in Bletchley Park – the rest isn’t) about the cribs. That’s all totally backwards. It’s like watching a film about Apollo 11 where they built the Saturn V and Apollo spacecraft and then decide to go to the moon. Also I doubt a girl at Bletchley would be talking about EXACTLY what her job there is. They took secrets a lot more seriously back then.

Right, onto my version of the Bombe. I have written up the BASIC version in another post here: http://www.asciimation.co.nz/bb/2015/06/14/turing-welchma…mbe-basic-code

All the code is available there. That version is a simplified version of the Bombe set up to run the Bletchley Park weather forecast menu they use to demonstrate with there. The code can be easily modified to run other menus. A full Bombe run on Orwell running at 1Mhz takes around 4.8 months!

My C version is a port of that code with minor differences. It is much more configurable, the menus and settings are read from a file. I haven’t quite finished it yet but the code is running and on my Intel i5 2.2Ghz machine it takes about 10 seconds for a full run.

It will also simulate the actual motion of the real Bombe but turning the fast drum 1 and a half revolutions for each middle drum turnover. It will drive my hardware correctly then. I have it running on my laptop in Visual Studio so the next step is to get it running on the Raspberry Pi 2. Once I have done that I can interface it to the Arduino driving the stepper motors. Once all that is working I will build the physical model. I am glad I only have three drums to build and not the hundreds they needed on the real thing!

IMG_3870 IMG_3872

IMG_3875 IMG_3876

Now what I have described here is only part of the whole Turing Welchman Bombe Enigma solving process. There is a lot more we haven’t even started talking about. My version of the Bombe is what is known as a Spider Bombe. There is also what was called the Jumbo Bombes which did extra checks to eliminate false stops. I have actually written the Jumbo logic into my C version but since the Bletchley Park reconstructed Bombe is a Spider one I won’t use those in my little model (or will at least make it an option that’s off by default).

I haven’t said anything about how they checked the stops were accurate and how they then used the correct stop to crack the actual Enigma code. That is a whole other complicated story in itself. Again I just want my model to do the same thing as the BP machine. I don’t actually have any pressing Enigma coded messages I desperately need to decode right now!

4 Responses to “A Turing/Welchman Bombe.”

  1. Asciimation » Blog Archives » Turing Welchman Bombe BASIC code. Says:

    […] This is a follow on from my software Bombe post here: http://www.asciimation.co.nz/bb/2015/06/14/a-turingwelchman-bombe […]

  2. EdS Says:

    I felt a need to check the statement that the plugboard swapped 10 pairs of letters – it was of course physically capable of swapping more or fewer. But it seems that procedurally it was generally 10, even though that’s not optimal. See
    http://www.cryptomuseum.com/crypto/enigma/working.htm

  3. Simon Says:

    Yes, they could of course have swapped 13 pairs of letters. Procedurally they used 10 pairs (if you look at the daily charts the army and Luftwaffe used they used they always show 10 pairs). The optimal number of plug board leads to use is actually 11! I don’t understand the mathematics behind it but that’s explained here: http://www.codesandciphers.co.uk/enigma/steckercount.htm

  4. Jim Says:

    Awesome again Simon.