Daily Archives: 28 January, 2015

Fixing Enigma, Part 2

Okay, in my last crypto article I outlined how and why the Allies were able to break Enigma. I then proposed a revised machine that could mostly be built out of its parts, and which would be secure against WWII cryptanalytic capabilities. The reflector would be removed and the steckerboard would be used (with single rather than paired plugs) to permute the alphabet at the output side, both for 18 lines of feedback and 8 lines of I/O on each side. It could use the same set of rotors and the same keyboard and output board. You’d need to replace the alphabet rings with some that are the same size and function exactly the same mechanically but use different cam patterns to turn the next rotor more frequently.

The new parts you’d need for the revised Enigma would be a couple of diodes, two terminal bars, some wire, the replacement alphabet rings, and a small box of ring terminals, and single-terminal plugs to replace the two-terminal paired plugs for the steckerboard. When you were done you’d have the old alphabet rings and the reflector left over. Somebody with a screwdriver and a pair of crimping pliers could make the conversion in an afternoon. The revised machine would be within the same budget of size, mass, complexity, power requirements, and parts as the original, meaning it could just as easily have been produced and deployed using WWII technology.

To recap, the important differences from the original Enigma are:

  • letters are encoded by putting the positive charge on one of 8 inputs and the negative charge on a different one of the same 8 inputs. Both impulses pass through the rotors, where they come out through the steckerboard, either to one of 8 selected outputs or into a feedback cycle by being shunted to one of the 18 non-input terminals on the input side for another trip. After some number of passes through the rotors, both positive and negative impulses must appear at one of the 8 output terminals – where they complete a circuit through a lamp that indicates an output letter. This feedback cycle is the most important change because it is highly nonlinear and simultaneously eliminates Enigma’s antireflexive property – a cryptographic weakness in which no letter can be encrypted to itself. The designers of the original Enigma underestimated the gravity of this weakness and willingly accepted it for the sake of convenience. They did this in order to produce a self-reciprocal cipher (a cipher where the same operation starting from the same settings encrypts plaintext or decrypts ciphertext).
  • In the revised machine each rotor drives the following rotor seventeen times instead of once each revolution, preventing sequences longer than two letters from ever differing by only the position of the first rotor.  This makes it much harder to isolate information about any single rotor by comparing ciphertexts with expected plaintext words, and much harder to work out the wiring of the first rotor by comparing plaintexts with ciphertexts.  This would have made it a lot harder to break with World War II capabilities, and in combination with the two-position encoding and feedback mechanism outlined above would have made it completely impossible to cryptanalyze given contemporary knowledge of group theory and the best compute power the Allies could have built.
  • The revised machine is no longer self-reciprocal, meaning it can no longer be used to decrypt its own output with the same procedure as encrypting the input.  This was necessary to produce a cipher with no anti-reflexive property. This opens up a possibility for a cipher clerk to make mistakes that could not have been made with Enigma, but this type of mistake is a far less grave security threat than the anti-reflexive  property.  This means encrypting and decrypting are now different operations which you have to select by plugging the power plug the other way in a reversible configuration.

Now I’m going to talk about building a rotor machine to achieve the goal of remaining possible to construct and use at WWII levels of technology, but capable of resisting modern cryptanalysis.

Before I go further, a word of caution; just because I personally can’t think of an attack does not mean this revision would be secure against all comers. It is a truism in cryptography that anybody, no matter their actual level of competence, can devise a cipher which he or she cannot break. I am no exception to the rule, and there exists no way to know that there’s nobody out there who could figure out an attack.

Reviewing the biggest security flaws in the Enigma:

  • The biggest problem is that it has a highly predictable state evolution and, by modern standards, a catastrophically short period until the state evolution repeats. The short period reflects a mechanical limitation of the original machine; once the day key was set, the rotor positions were the only things that could change. There being only 264 rotor positions, this means it can have only 264 different states given any particular day’s key. The revised Enigma visits them in a different sequence in order to limit the ability to extract information about individual rotors, but as long as we restrict the changing state to the rotor positions alone, it does not have more than 264 states given the same day key, so it repeats its evolution just as quickly as the Enigma.
  • Enigma used only four kinds of state transitions (one to four rotors may move at any time), and it made them in a predictable sequence, at known or knowable intervals relative to each other.
  • Finally, Enigma had a message key far too short and the Nazis were using exactly the wrong thing (rotor positions) for the message keys. Given that different rotor positions determined only different starting positions in the same too-short cycle of states, it exposed a horrific related-key attack against the individual messages.  Had they instead used alphabet ring settings, then every message key would determine an entirely different cycle of states for the encryptions to be on and it would become impossible to find multiple message encrypted with the same sequence of substitution ciphers.

These are all catastrophic security failures in a cipher under scrutiny with modern methods. The revised machine while secure agains WWII cryptanalytic capabilities, shares them.  Using the worst possible choice for message keys could be considered to be a user error rather than a flaw in the design of the machine.  But given the revised machine the Nazis would probably have made the same mistake.

A modern rotor machine needs more mechanical parts, to maximize the number of total states it can be in.  However, having  more possible states is necessary but not sufficient. More states will NOT make the machine secure if an opponent can still figure out the sequence of state transitions.  I’ll get to a chaotic state transition mechanism later, so bear with me on just making the problem space larger and placing barriers against easy analysis for now before we get to the problem of making the analysis take  mathematically different techniques to solve.  A sufficient application of “larger” can add up to mathematically intractable; the two important tricks are to know exactly how hard increased size actually makes a problem, and to be right about that. The second of these two tricks is much harder than the first because, as with most things, it is far, far easier to be certain than right.

The most straightforward way to add more different states is to add more rotors.  To make a rotor machine with enough different positions to be secure against modern analysis methods, you’d need at least 9. I repeat the warning here about more states being necessary but not sufficient to security.  Another way, still mechanically simple, is to make the rotors larger.  But for use with WWII technology levels we’d still want an easy, unambiguous  way to express rotor positions, so we shouldn’t use more than 36 positions per rotor.  I choose 36 because then the rotor positions could still be written alphanumerically, and not require people to distinguish upper and lower case letters.  Between them these two changes make the rotor cage of the machine take up about 8 times more volume, so mechanically this machine would be at least twice as large and heavy as the original Enigma and with its increased mechanical complexity it would be at least 5 times as expensive to manufacture. There’s really no way around that.

Instead of encoding an alphabet of 28 symbols by selecting any pair of 8 I/O points, a more aggressive revision would care which terminal is positive and which is negative, allowing an alphabet of 30 symbols to be used occupying 6 I/O points.  This would require adding 12 diodes – 2 per output.  By making the number of input/output positions smaller and the number of total positions larger, we have our encryption depending on an average of 10.42 rather than an average of 5.90 trips through the rotors, which, given any particular number and size of the rotors, would nearly double the order of magnitude of the analysis problem.

Also significant for purposes of resisting analysis, it depends on an average of 10.42 trips through the rewirable steckerboard rather than one, and the stecker is applied between trips through the rotors rather than just being added before or after the trips through as it was in the Enigma.  This makes the analysis problem about 36!/(36-10)!x10! or about 2.54×108 times harder. Again however, while these differences make the problem much bigger, they do not make it fundamentally different.

A principle of modern cryptography, somewhat counterintuitively, is that in a cipher with state (in modern parlance these are called stream ciphers), you make your output and/or your transition to the next state depend on as much of the state as possible at once, in order to make it hard for a cryptanalyst to gather information about any single part of the state.  In making so many trips through the rotors, and applying the stecker wirings at intervals between the rotor trips, we’re permuting the output repeatedly according to many parts of the machine’s state that would not be used in a non-feedback configuration.  Exposing more state by using feedback loops like this makes it drastically harder to isolate information about any single part of the state.

With 9 rotors having 36 positions each, there are about 1014 different rotor positions given a particular set and sequence of rotors.   Enigma, including my proposed revision of Enigma, for comparison had 4.57×105 .

Next, we consider the rotors themselves. Enigma’s rotors were painstakingly, individually, hand-wired, soldered, and sealed at a secure facility – a slow and expensive process, which explains why the Nazis had only deployed 8 different rotors by the end of the war. Sealing them didn’t help at all as a security measure because, on the several occasions when the Allies recovered machines, it was trivial to use a connectivity tester, or just a flashlight and two wires, to test the rotor wirings directly. And there is absolutely no way to manufacture them so that it wouldn’t be trivial, given their basic electromechanical function. As with so many other choices, it demonstrates that decisions about how cryptography was to be used were not being made by people who understood cryptography – or, in this case, by people who understood the basic principles of operation of the cipher machine. But, as already discussed, the allies had usually worked out the wirings from the message traffic long before they ever saw the physical rotors, because of other cryptographic problems and mistakes with Enigma.

The rotors themselves, in the original Enigma, were nice little electromechanical devices, with 26 springloaded contacts on one side and 26 smooth metallic contacts on the other. Inside, a maze of insulated wires connected the sides in a permutation. The revised Enigma I proposed used the same rotors. But for modern use, I’d want to construct the rotors differently. First, I’d have it possible to take the rotor apart in the field using a screwdriver. Second, there would be no wires inside, just bare contacts. Third, instead of the springs in the spring-loaded contacts being contained in the original recesses, they’d press directly, but lightly, against the contact on the other side. Adding four wiring discs in between the left and right sides would compress the springs, allowing the springs to ensure that the contacts on the sides of the wiring discs meet each other.

What’s a wiring disc? Take a ring of some thin, flexible insulating material the size of the inside of the rotor. Put a circle of 36 contacts on each side. Connect the contacts on the left side, with wires running through the central hole in the ring, to contacts on the right side to make a permutation. Then to make things neat and prevent wires from snagging on anything, you then put a sheet of your thin flexible insulating material, with holes for the contacts to poke through, on both sides. Finally, you punch holes or notches or something between the contacts around the circle to allow you to determine and solidly set their rotations on a pin or rod, and label the holes or notches so an operator can tell them apart.

Here is what’s great about wiring discs. They’re cheap and easy to manufacture, especially considering that printed circuits had been invented by the time of WWII. They don’t take up much weight or space, and the space they take up is inside the rotors so you don’t need any extra storage space. They can be used in 36 different rotations, and you can turn them over and use them in 36 more. And the permutations they make can be composed just by stacking them together inside the rotor.

Consider our nine rotors, given a stack of four wiring discs inside each one and assuming that they are chosen from a set of exactly 36 wiring discs so none are stored outside the rotors. There are 36!/9! possible sequences of wiring discs (there would be 36! except we’re not counting sequences that would be redundant given that the rotors themselves can be rearranged). There are 236 possible sets of facings for the wiring discs. And there are 2736 possible rotations for the discs relative to each other (it would be 3636 except that we’re not counting rotations that would be redundant with the rotations of the rotors relative to each other). That makes a total of 2.38×1098 different electrical configurations of the rotors, even if the cryptanalyst knows the wiring of every disc. If we had instead just used a permutation of nine rotors, we would have 9! possible configurations or 3.62×105. Enigma, and the revised Enigma, both used a permutation of four chosen from 8, or 8!/(8-4)! possible electrical configurations – which is only 1680.

In use, the cipher clerk would open all his rotors once a week, take out the wiring discs, put them back in a different order, rotation, and orientation according to the week’s key, and close the rotors. Each day, he would use a different permutation of the nine configured rotors according to the day’s key. Use of a stack of wiring discs rather than fixed wiring, even given complete enemy knowledge of their wiring, adds 90 orders of magnitude to the number of settings available, meaning that knowledge of the wiring would become useless.

But this is still not enough to achieve security.  All that more rotors, multiple feedback through the stecker, a greater percentage of feedback, and the use of wiring discs have done is to make the problem much, much larger – over 200 orders of magnitude larger by the best methods I know if I’m counting right.  This would make it take a god-awful amount of compute power, but does not significantly change the methods needed to attack it. The methods required to attack it are group theory, cyclometry, and multidimensional matrix algebra – not what they teach in beginning math courses, but still easier than the modern ideal of forcing your enemy to use a brute force search.

Although I personally can’t figure out any way to even begin to derive the equations in the presence of the feedback mechanism, and the numbers involved are big enough that I can’t imagine any tractable elimination process that would work, one thing remains true. As long as the movement of each rotor depends solely and in a predictable way on the position of one other rotor, there exists a simple set of linear equations that describes how the machine’s state evolves in operation. And that set of linear equations is what an opponent needs to start making progress, if they know better than me about a way progress can be made, using group theory, cyclometry, and multidimensional matrix algebra.

Besides, I could very easily be wrong about the existence of no tractable method of solving the rest of the problem. I am not at all likely to be the smartest cryptographer or cryptanalyst on the planet, and even if I were, there would still be methods I don’t know that somebody else out there does. So if we want this thing to be secure against modern methods – against capabilities that some opponent might plausibly have if they know analytical methods I don’t – it has to have a nonlinear mechanism for determining its rotor movements.

The greatest source of nonlinearity available in this machine is the rotor stack itself. So, an immediate thought is to have the machine encrypt ‘X’ or some other fixed input through the rotors when the key is released, and use the output to select one of 30 different rotor movements.

And that would actually work fairly well, except for one thing: on average it would make cyclic sequences only as long as the square root of the number of different rotor positions, in this case meaning cyclic sequences about 107 characters long. The Enigma was designed to maximize its period by visiting literally every possible rotation state before repeating any, and the revised Enigma was designed to do the same thing without exposing easily-available information about any particular rotor enabling attackers to work them out one at a time. These properties depended on a predictable repeating sequence of rotor movements. But if we make a completely nonlinear selection of state transitions based solely on our current state, we don’t get that luxury. Our selections will come back to the same state (and therefore begin a cycle again), on average after traversing only the square root of the number of states in the total state space, so our cryptanalyst opponent will get messages encrypted according to a repeated sequence of states starting when we have transmitted only about ten million characters of traffic. And, on unpredictable occasions, slightly later or even sooner. That’s much longer than Enigma’s cycle length given a single day key, but for a modern cipher, that short cycle would be a disaster and, even against WWII capabilities, it would not be completely secure against decryption of individual messages on the basis of finding messages encrypted according to the same sequence of states.

Here we must deal with a design problem of classic rotor machines. In the context of an individual message, rotor machines have both fixed state, which is usually called settings, and changing state. The rotor positions are changing while an individual message is transmitted. Everything that does not change is settings. Out of all the things I have so far proposed to build into a modern rotor machine, many make the analysis harder and many multiply the amount of fixed state. But the only ones that matter to the amount of changing state are the larger rotors and the existence of more rotors. That increased the amount of varying state from Enigma’s 456976 to about 1014. Which, for modern purposes, is not really enough. And its square root, about 107 which is what we’d get on average if we let just that the state and the settings determine the state transitions, would render it breakable even to an opponent who knows nothing about the machine.

So what can we do? Using the output of encrypting a fixed input will make a choice among 30 different transitions or rotor movements, one for each symbol of our alphabet. Assuming that each rotor can move one position forward, one position backward, or remain in place for each transition, a choice among just 27 movements is needed to control 3 rotors. We can map a set of 27 (or less if we want to leave out some options such as the no-movement option) movements of the first 3 rotors to our 30 outputs strictly on the basis of ensuring that statistically the 3 rotors we’re controlling all have a net continued movement and move at different rates.

How should the 6 linearly driven rotors move? They should move in a way that minimizes or eliminates the number of times when a single rotor moves by itself (because that isolates information about a single rotor), minimizes or eliminates the number of times 2 rotors next to each other move in unison or both stand still (because then the new permutation presented by both is then just a rotation of the previous one rather than a new combination), and maximizes the period of the cycle. Here is one proposed solution that meets these criteria reasonably well. The first rotor is driven clockwise with every input, and drives the second counterclockwise 29 times every revolution. The second rotor drives the fourth rotor counterclockwise 29 times every revolution. The fourth rotor drives the sixth rotor counterclockwise 29 times every revolution. The first rotor also drives the fifth rotor clockwise 25 times every revolution, and the fifth rotor drives the third clockwise 25 times every revolution.

This is complicated to visualize, but what it amounts to is that adjacent rotors move in opposite directions, and the fastest clockwise rotors are adjacent to the slowest counterclockwise rotors and vice versa. Because 25, 29, and 36 have no factors in common, the period is maximized – these wheels will go through every possible position before repeating their cycle. Because adjacent rotors are moving in opposite directions it will never happen that both move in unison. And because no rotor which is only intermittently driven is driving any rotor directly adjacent to it, it will very seldom happen – and when it does happen it won’t happen at the same relative rotations more often than chance would dictate – that two adjacent rotors both stand still. This is complex, but accomplishes reasonably well the goal of maximizing the amount of relevant state change at every transition to prevent analysis from extracting information about any single rotor.

To recap, here is a design for a rotor machine that could be built with WWII technology, and would (I believe) secure WWII traffic even against modern cryptanalysts.

It has nine rotors with 36 contacts on each side. Each rotor contains four wiring discs. The discs are unique and can be composed in different rotations and facings, making a huge number of possible electrical configurations for each rotor. This largely prevents opposing knowledge of the connectivity of each disc from being useful in cryptanalyzing the device unless the combinations and orientations in use are also known – and those combinations can be changed frequently enough to make it effectively impossible to derive them given only the amount of traffic each combination would be used to encrypt.

An alphabet of 30 symbols (letters, space, and a few punctuations) is encoded by sending a positive and a negative impulse through the rotors at 2 of 6 selected input points. The 36 contact points on the output side are directed through a reconfigurable plugboard, with 30 going back in a feedback loop to non-input contact points on the input side, and 6 going to output points. The ciphertext letter is read by seeing which circuit they complete (and in what direction) at the 6 output points.

The first 6 rotors are driven by a lever under the keyboard, in a pattern that exhausts all permutations before repeating. Adjacent rotors are driven in opposite directions to prevent movement in unison, and except for the first rotor, which is always driven, no rotor drives a rotor that’s adjacent to it, in order to minimize and decorrelate the instances of adjacent rotors remaining at rest together.

The last 3 rotors are independently driven by solenoids energized at the release of each key, depending on the output when the letter ‘X’ is encrypted using the rotor positions reached before the previous letter was encrypted. The solenoids are energized using the same decoding grid as the output lamp board, with an electromechanical switch diverting current from the lamps for the impulse released on the key release. The mapping of output symbols to movements is selected to cause a slight net movement of the rotors, on average, relative to each other. This is in order to prevent rotor positions from having the statistical property of normal distribution around a fixed point relative to each other, which would happen if all possible movements were used equally.

With fixed settings, that gives 6 rotors going through every possible permutation of 2.18×109 positions, and 3 rotors moving chaotically within a space of 46656 states. That makes the repeating cycle for a given key average about 4.7×1011 outputs or 470 billion characters, which is acceptable even against modern cryptanalysis if used for WWII levels of traffic.

This means that – assuming I’m right about its resistance to cryptanalysis, which is by no means assured – the Nazis could have built this machine and used it, and if they had, then even given the ciphertext transcripts of all the messages they sent during WWII, modern cryptanalysts would still not be able to read the messages.

Again assuming I’m right, this describes a secure cipher machine, not a secure cipher. While this would have secured WWII levels of traffic against modern cryptanalysis, its period given a particular configuration of settings is still too short, and today we are sending multi-gigabyte files over the wire. Encrypting 470 billion characters in a 30-symbol alphabet amounts to only about 290 gigabytes of modern traffic, which some individual users go through in a week and which modern ISP’s transmit and receive every hour, so this cannot be considered a secure cipher for modern use, and building a software simulation of it will not enable you to secure any great amount of traffic.

Even so, it is a secure cipher machine. If you built this thing as a physical machine and tried to run it at the speeds needed to encrypt an amount of traffic that would make cryptanalyzing it possible, it would immediately explode. Its mechanical limitations as a physical device made out of matter, which has inconvenient properties like momentum and shear strength, would be sufficient to prevent it from ever being used to encrypt a volume of traffic that it could not secure.