tdd-deciphered.com

created by @parsingphase

Table of Contents

This series was initially developed back in 2009. Five years is a long time in software, so I’m now revising the project to use current technologies and methods.

Way back in August 2009, I first visited Bletchley Park. Back then, the site and its history were almost unknown, and the Park was in a very difficult situation. However, following a major social media campaign, and support from various major technology companies, it’s now in a much better position to tell its story to future generations.

And it’s a pretty incredible story. Bletchley Park was the site of the British Government Code and Cipher school in the Second World War, the “home of the codebreakers”. Here, numerous Axis codes were broken and read, giving the Allies critical knowledge about enemy action and strategy which in turn helped shorten the war by many months and save millions of lives. …

Test-driven development (or TDD), is a programming methodology that’s been around for a little over a decade now. The fundamental principle is that of defining what software needs to do by writing tests that confirm that it can do it. By writing tests for each unit of functionality before implementing it, we can guarantee that we’re always adding correct functionality to a system. Over time, these collected tests evolve from helping build the code to providing a sort of immune system, ensuring new changes never break what’s already present. Tests serving this purpose are generally referred to as “regression tests”, and can ultimately make the difference between proven code that you trust, and legacy code that you dread. You can usually tell whether you’ve written enough tests by how much confidence you have in your codebase.

Realistically, though, very few people develop every line of code by writing tests first. …

Architecture of the Enigma system

The Enigma hardware was an electromechanical system, weighing about 12 kilos and measuring about 30 cm square by 15 cm deep. It was built in a number of increasingly complex formats from the late 1920s and throughout the Second World War, was highly configurable, and would always be operated by one, or a pair of, trained operators.

In appearance, it looked more like a typewriter than anything else, but instead of striking keys and a roller for paper, it had a set of three or four vertically mounted rotors and a lightboard displaying the output for each letter.

The Enigma was a fully stateless machine that operated letter-by-letter, with the output for each input character depending entirely the on rotor position and configuration that applied when that letter was input.

The vital elements of the Enigma were:

Keyboard

This provided the system input, one character at a time. …

Note: if you want to follow along with this code, you’ll need the following installed on your system. Some of them may already be present depending on your operating system.

  • PHP, version 5.3.2 or better (ideally version 5.4 or better). You’ll only need the command-line version; we won’t be using a web server for most of this project.
  • Git, any reasonably recent version.
  • Composer, any reasonably recent version. I’ll assume that you’ve installed it globally as per the instructions.
  • A decent text editor or (much preferred) IDE. I use and enthusiastically endorse PHPStorm. Grab the free trial at least.
  • If you want to push your code to a public location, you’ll also need an account on Github or similar. …

Having specified our system architecture in Chapter 3, and our class namespaces in Chapter 4, we now need to combine these by creating tests and code. We’re going to take a test-first approach here, so let’s test our decision that our Rotors implement the Enigma Encryptor Interface:

In our test file tests\Phase\Enigma\RotorTest.php, we add:

<?php
namespace Phase\Enigma;

class RotorTest extends \PHPUnit_Framework_TestCase
{
    public function testRotorIsAnEncryptor ()
    {
        $rotor = new Rotor();
        $this->assertTrue($rotor instanceof EncryptorInterface, "Rotor must support EncryptorInterface");
    }
}

This is a perfectly valid test, even though the classes it purports to test don’t exist yet. If it tells us so when it runs, it’s entirely correct as a test. …

So far we've made one very simple comment about the Rotor class - that it's an encryptor - but we've made no attempt to actually model the real rotor's behaviour. In order to do that, we need to more closely specify the rotor's properties and capabilities:

  • A rotor has 26 inputs on its right hand side, and 26 outputs on its left hand side.
  • Each input is connected to exactly one output. The way in which it connects is specified by the internal wiring of the rotor, which is determined by the rotor’s identity, generally referred to by roman numerals.
  • A rotor consists of an internal disk or "core" carrying the wiring, and an external ring, often referred to as a tyre, which carries the letter indicators.
  • Each rotor has at least one carry notch on the left side of the ring, which can cause the next rotor up to move around one place.
  • The ring can be moved relative to the core. The offset is referred to as the "Ring Setting" or "Ringstellung". …

So, we’ve decided we need to test for a valid ring offset; we're going to be rolling these rotors around later on, and if they can get stuck in illogical positions we will get very confused.

So what defines a valid offset, and what does that offset mean? We could take a look at our system and say that we're looking at an offset in an array of mappings, and so that'll logically go from 0-25. But does that make sense with the hardware? Would it be meaningful to an original Enigma user or codebreaker?

Well, yes and no. It's incredibly tricky trying to nail down precise details for an 80-year old hardware device that was classified as Secret until 30 years ago, and most of the books on the topic weren't written for software engineers trying to write simulators. But you're lucky, because this site is.

The "yes and no" answer lies in the fact that there were at least two dozen different types of Enigma device (see the [Enigma Family Tree](http://www.cryptomuseum. …

We noted in the previous chapter that a rotor's behaviour depended on its core mapping, and on the rotation offset of that core with regards to the wheel, specified either alphabetically or numerically.

We didn't say, however, what that offset actually meant. Where are we offsetting from?

On the physical rotor, there's a catch on the core that clips into a location next to any letter on the alphabet ring. That letter gives the alphabetic offset, or alternately a numeric offset where 1 is A, 2 is etc (considered as 'distance from Z'). The core mapping we’ve looked at previously is specified as the mapping through the rotor at the "default" offset of 'A' or ‘1’, but to simulate the electrical behaviour of the rotor as an encryptor, we need to be able to determine the output character that corresponds to any input character, whether at the the default position or at another offset. …

In the last chapter, we got the rotors working. Now, we'll work on the framework they sit in, starting with the rotor slots

As we did with the Rotors themselves, we need to analyse the behaviour we need from the slots: - Any time a letter is sent to the right-hand rotor in slot 1, it will be turned over by one position before the electrical signal is sent. - If the rotor in a slot is in a position to engage the rotor shift mechanism (aka the pre-turnover position), and it turns over, it will cause the rotor to its left to turn over before the electrical signal is passed. - The position of the rotor in the slot must also be taken into account in routing the electrical signal.

From this, we can see that each slot will need to know: - What position it's in (ie, which slot number it is) - Whether its rotor is in the pre-turnover position - Whether the rotor to its right (if it has one) will cause it to turn over - What rotary position its rotor is in. …

Having handled the electrical aspects of the rotors and slots, we need to consider how the mechanical interaction works. For the rightmost rotor (slot 1), the motion of pushing down the key will also push around the rotor in slot one. If this rotor is in its turnover position, when it turns it will also push around the rotor in slot 2, and so on. At the end of its downward mechanical motion the key completes the electrical circuit and so the signal current flows after all turnovers have taken place.

In terms of functional requirements, this means:

The rightmost rotor will turn over on every keypress, but not all rotors will turn over on every keypress. The action of the remaining rotors depends on the identity and position of the adjacent rotors.

Before we consider the general case, we'll handle the simple case of the first rotor. This simply needs an "increment rotor position" function that we'll trigger manually. …

So far, every time we’ve picked up a rotor, we’ve specified its core mapping directly - something that’s going to be increasingly fiddly and error-prone if we have to effectively wire the rotors by hand each time we use them.

To reduce those errors, we’ll build a small factory to give ourselves easy access to copies the standard rotors.

The wiring of each of these rotors can conveniently be found at http://www.codesandciphers.org.uk/enigma/rotorspec.htm, thanks to the late and much missed Tony Sale. We’ll stand on the shoulders of giants by making use of that information here.

We need to build a factory that contains a simple template for each rotor and allows us to request each by name. We’ll also give this factory a QA department by writing some tests to ensure that its output is internally consistent. …

Having defined our collection of rotors and slots, we now need to look at how they work together. We’ve already alluded to the fact that a wheel can cause the one next to it to turn over, but how and when does this happen?

It turns out that the mechanism isn’t quite what you’d expect. The simplest assumption is that the rotors work like a car odometer, with a complete rotation of each rotor nudging the one to its right up one position. It turns out that while you can model the system this way, it only works most of the time.

The actual mechanism is a set of pawls (think “pushy fingers”), one for each rotor, that try to push that rotor around on each keypress by engaging with the teeth on the right side of the rotor. …

From our understanding of the pawl and notch mechanism, we can see that we can only simulate this part of the system properly by integrating the elements that affect each other. We can consider a structure looking like:

Slot 2 Slot 1 Slot 0
Rotor Rotor Rotor
Pawl 2 Pawl 1 Pawl 0

If we simulate a Pawl class, we need to give it a canPush method that relates to the rotor notch positions in the adjacent slots. We noted the requirement above:

pawl.canPush = (rightRotor.isAbsent OR rightRotor.hasNotchOnLeftSideInCurrentPosition)

The rotor in a given slot will turn on keypress if slot.leftPawl.canPush or slot.rightPawl.canPush

So each slot needs to be told the identify of its adjacent pawls, and each pawl needs to know its right-hand slot’s rotor position. …

Two further elements are required to assemble a complete Enigma simulation. How do these fit into our system?

The best way to answer this is to look at the full electrical path from input key to output lamp.

The first element encountered is the plugboard (Steckerbrett) that we’ve not yet described or yet implemented. This consists of a board on the front of the Enigma with 26 pairs of sockets marked A-Z. When nothing is plugged into these sockets, they simply map A-A, B-B etc and so have no enciphering effect. However, when a twin doubled-headed cable is plugged between two pairs, the letters are swapped over. Typically, around 10 cables were used at once.

The second element reached is our first rotor slot, from where the signal routes through the rotor core, out to the second slot, through that core, to the third slot, through that core, and to our second missing element. …

As mentioned previously, we can consider the reflectors as simpler, fixed rotors, and so we can define their configuration as a simple array mapping. As this mapping must be entirely reciprocal (the inputs and outputs are the same physical contacts), we can define just 13 mapping pairs which we refer to as a “half mapping”. …

Now that we’ve simulated all the parts, we can put them together into a single, functional machine, which also implements our EncryptorInterface. …

We’re now in position to do end-to-end assembly and test. The easiest test to envision is one where we take known inputs and settings and see if we can achieve the correct outputs. To do this you’ll need one or more of:

  • Access to an original Enigma machine.
  • An existing message encrypt or decrypt with rotor settings and output.
  • An existing known-good simulator.

Now, original Enigma machines typically retail in the order of £100,000, so the first option won’t be widely available. And while I was lucky enough to have the chance to use one while volunteering at Bletchley Park, I don’t have any notes of the rotor and plugboard settings used.

Fortunately though, there are other simulators, such as Mininigmafor iOS, or Terry Long's simulator for OSX - and I’ve had the chance to verify these against a real machine. …

Having written our code “test-first”, we can expect that it’s well tested and thereby protected against changes, but can we quantify this? Fortunately so, as PHPUnit comes will some extremely useful tools to do just that, able to quantify both the coverage and “change protection” that we’ve achieved.

To use them, all we have to do is add another parameter to our call to phpunit:

wechsler@tahr:~/host/repos/enigma-simulator$ ./vendor/bin/phpunit --color --coverage-html=docs/coverage tests

You may notice that this runs a little more slowly than it did before as it analyses exactly what code is being exercised by the tests. It may also complain that you’ve not got xdebug installed; if so, install it via your package manager (eg sudo apt-get install php5-xdebug on ubuntu) or consult http://xdebug.org/docs/install. Once the command has successfully run, we can look at the file docs/coverage/index.html to see how our coverage looks. …

Any noteworthy changes not covered in the main documentation will be added here:

  • 2014/10/10 - Tag Chapter19-1-EntryDisc adds a changeable Entry Disc into the simulation, for anyone who wants to simulate the pre-war "Commercial" machines, or the T-series "Tirpitz" Enigma used by the Japanese.