Recently on a cryptography mailing list I read regularly, Henry Baker
asked a question:
Since The Imitation Game is playing & is quite likely to win some awards, I was wondering if anyone has written an analysis of the Enigma & Lorenz encryption systems using 2015 eyes?
What would be required to “fix” these codes for modern usage, e.g., converting the mechanical bits into software, adding more wheels, etc. ?
I spent far too much time thinking about this. The age of machine ciphers immediately preceding the modern era of electronic ciphers is a fascinating era that can be considered as the beginning of modern cryptography. Modern cryptographers feel about those elegant old machines probably the same way modern sailors feel about the beautiful hand-crafted brass antique navigation instruments that were replaced by GPS.
It’s also an excellent case study because following World War II, conspiracy theorists in the US accused the President and Congress of knowing about the Japanese bombing of Pearl Harbor before it happened, and as a result there was a witch-hunt. The search for someone in authority to blame more or less forced the US to release all the information it had about breaking Axis cryptography by the mid-1950s.
As a result, we have all this information that’s now unclassified, and we can have a good look at the weaknesses of the famous Enigma machine were and how the Allied forces broke it.
So let’s set a challenge: Given the Enigma Machine’s budget of size, weight, cost, and complexity, given the same record of insecure practices, operational failures, and Allied recovery of secrets that actually happened during the war, using no parts that would have been more expensive to manufacture using WWII technology, and with the fewest possible mechanical changes, can a machine be designed that would have been utterly beyond the Allies’ abilities to crack, and possibly even pose a serious problem for cryptanalysts today?
The short answer to the first part (secure vs. WWII capabilities) is “yes”. The short answer to the second part (problem for cryptanalysts today) is “maybe but I’d need a more complicated machine.”
There are several versions of the Enigma machine that saw use during the war. I’m going to pick one version to use as a reference. And, arbitrarily, I’m going to pick a combination of features mostly for the hardware budget that it represents, so I’m looking at a combination of the best features the Third Reich deployed with its system.
Here’s the basic hardware we’re going to compare our proposed solution with. It has a battery for power, a keyboard for input, a series of four rotors to implement a rotor cipher, a rotating reflector to impose a remapping and send the signal back through the same stack of rotors a second time, a steckerbrett (plugboard) to superimpose a substitution cipher on the output of the rotor cipher, and a light board for output.
The rotors are driven mechanically by a lever which is part of the
keyboard.
The operator has a set of eight different rotors and three different reflectors, and selects a set each day according to the code book. Each rotor is also fitted with a movable alphabet ring. Moving the alphabet ring changes the point in the rotation when each ring causes the next one to move.
So, returning to our question: Given this size, weight, complexity, and manufacturing capabilities, can a machine be designed that would have been beyond the Allies’ abilities to crack, and possibly even pose a serious problem for cryptanalysts today?
The Enigma had two glaring cryptographic weaknesses each of which made the other worse. The first was its antireflexive property, and the second was its highly predictable linear state evolution.
The greatest of these was the antireflexive property – that a letter could never encrypt to itself. This meant that if a cryptanalyst had a “crib” – a word or phrase that he suspected might be in the message – he could identify all the positions where it could not possibly be in because if it were in one of those positions, a letter of plaintext would match a letter of ciphertext.
The second greatest weakness was that the vast majority of the state evolutions (25 out of 26) were just moving a single rotor – and always the same rotor – a single space in the same direction. This meant any encryptions of the same letter occurring more than once in any short “crib” were usually related to each other in a very specific way depending on the number of characters between them. In that number of characters the state of the machine had undergone a very predictable well-defined small change. Collecting the information about encryptions of letters repeated at a given interval therefore generated a set of cycles on the alphabet for that interval.
This allowed the cryptanalysists to confirm ‘cribs’ because the ones that were accurate transcriptions would give rise to cyclometrics that agreed with each other, whereas the ones that were false transcriptions would give rise to non-matching cyclometric properties. And with every confirmed ‘crib’ they got access to known encryptions of letters they hadn’t known before at known offsets to other encryptions of those same plaintext letters, and therefore more complete cyclometric information. Worse than that, once they had found full sets of cycles for two different intervals on the same rotor, it could be used to figure out the complete wiring diagram of the rotor. And this is exactly what the Cyclometer was built to do.
The information gained from the Cyclometer can be leveraged further, because once the cryptanalyst knows the wiring diagram of the first rotor, he can cancel it out, leaving data that he can then apply to all the observed “bumps” (where the movement of the first rotor does not explain the relationship of previous plaintext/ciphertext to subsequent plaintext/ciphertext) in the knowledge that 24 or 25 of every 26 bumps will be caused by exactly the same kind of predictable one-space movement of a single rotor in a single direction – in this case the second rotor. The “bumps” where the movement of both the first and second rotors does not explain the relationship of previous plaintext/ciphertext to subsequent plaintext/ciphertext are called “crashes” meaning they are caused by movement of more than just the first and second rotors. But once he studies the “bumps” enough he knows the second rotor well enough to build a wiring diagram, and then he can subtract out the first and second rotor to study “crashes” and try to figure out the third rotor.
In practice he never would, for two reasons. First because knowing the first and second rotors allows him to reduce the encryption to a series of simple substitution ciphers which change only once every 676 letters. That is enough to make it very easy to decrypt traffic, so he doesn’t need to worry about the third or fourth rotor, nor the reflector. As far as he’s concerned, they’re just an arbitrary substitution cipher that changes once in a while but not so often that it impedes his work. Second, he is unlikely to collect enough information in a single day to fully work out the third and fourth rotors, and anyway he is very likely to have worked them out on a previous day when they were the first or second rotor. In any case, if he hasn’t already worked them out, then it will be much easier on a subsequent day when that same rotor occupies the first or second position.
So the cryptanalysts exploited the antireflexive property to identify possible locations of “cribs” in messages, and the Cyclometers were then used to confirm the presence or absence of “cribs” and exploit the predictable evolution of the state to get cyclometric information which could confirm or disprove cribs and reveal rotor wirings. Either of these weaknesses, by itself, would have been relatively difficult to exploit, but each weakness made the other weakness easier to exploit, and the Enigma crumbled.
So, how do we design a machine that doesn’t have these weaknesses?
Honestly, I’ve thought of a bunch of ways. So let’s start with how easy it was to extract information from the slow, linear, predictable evolution of the cipher state.
The Enigma, as deployed, had a “fast” rotor that was driven every time a letter was typed, but only drove the next fastest rotor once or twice during each revolution. Likewise the second rotor drove the third only once or twice each revolution, and the third rotor drove the fourth only once or twice each revolution.
This occurs because the Germans were trying to maximize the period between cycles of the substitution key. Maximizing the period between repetitions is a good idea, but for the reasons explained above, doing it in such a way that the vast majority of cipher state evolutions result from a very simple predictable movement which exposes information about that part of your cipher is a bad plan.
But consider a different movement scheme. We could change the number of times each rotor drives the next rotor, and could do so without making the period of the cipher’s state evolution any shorter. One time out of twenty-six maximizes the period of the evolution not because one is small, but because one is prime relative to twenty-six. Among other numbers, seventeen is also prime relative to twenty-six.
Suppose each rotor drove the next rotor seventeen times instead of just once or twice out of each twenty-six advances. This would be a very simple change to make to the machine; it could in fact use exactly the same control machinery with a change in the cams that were built into the alphabet rings. It would have the first rotor moving, as before, 100% of the time, but the second rotor about 65% of the time, the third rotor about 43% of the time, and the fourth rotor about 28% of the time. This uses the same four movements that the basic Enigma cipher used, but it divides those four movement types up in a way much closer to equal. As before, first-wheel movement occurs every character. But now “bumps” where both the first two wheels move occur in any sequence more than two characters long, “crashes” where all of the first three wheels move occur at intervals of about 3 characters, and “breaks” where all four wheels move a bit more often than once every four characters. This would be much harder to cryptanalyze because it would not be nearly so easy to isolate the cyclometric information of the fast rotor. Also, having cyclometric information for the first rotor alone wouldn’t allow you to confirm cribs more than two characters long – and that only if they happen to be characters between which no “crashes” or “breaks” occur.
Finally, cyclometric information, even about the first interval in the first rotor, wouldn’t be easily available because of the feedback mechanism I’ll introduce while getting rid of the antireflexive property. The first rotor would move by itself only about one time out of four, but 99% of the time when that happened, the feedback properties would also change, meaning you’d be getting cyclometric information about the sum of different sets of multiple locations in the first rotor, and you wouldn’t know what set or how large a set of the first-rotor locations. Further, you don’t know which one percent of the time the movement is between two positions of the first rotor both of which didn’t result in multiple passes through the first rotor. And by the time those two positions of the first rotor arrive again, you can’t confirm anything because the odds against them lining up with locations that don’t cause feedback changes a second time are on the order of once in ten thousand.
A cryptanalyst could still possibly work it out with modern methods, but it would be difficult to do even with today’s advanced group theory methods and, I believe, impossible without modern computing hardware. It would be, in particular, much harder than any of the cryptanalysis that was done in WWII.
This is still a predictable and linear evolution of the cipher’s state, and information could still be extracted from it eventually breaking the cipher. This simple fix only makes a greater amount of the state change more often, giving a cryptanalyst less access to any single part of the state information before it is disrupted by other parts of the state.
I could go a lot further with fixing the predictable and linear evolution of the cipher’s state, and if designing for a modern application where people would be using actual computers to attack something, I definitely would have to. I’m noting that for our purposes here the “fixed” version would be adequate for WWII but I’d need more complicated machinery to make it safe from modern cryptanalysts.
The other major cryptological weakness the Enigma had was its antireflexive property. The machine’s designers desired that every letter’s encryption should depend on at least two trips through the set of rotors rather than one, in order to improve the cipher’s security, so they turned the electrical impulse around at the slow rotor and sent it back the other direction, where of course it could be on any path except the path it had entered the rotors on. Like maximizing the period of the cipher’s state, making the encryption depend on more than one trip through the rotors is a good impulse and had it been done well would have improved security. But the way they chose to do it created the antireflexive property, which like the rotor movement scheme, was one of the worst possible ways to achieve the worthwhile goal.
So how do we achieve that security goal without creating an antireflexive property? The best way I can think of is to simply pass two different electrical paths through the rotors. If we encode each letter as two electrical impulses entering the rotors at separate locations, the two electrical pathways are guaranteed to also exit the rotors at separate locations – but now the output contacts and the input contacts are separate, so there’s no reason why a character can’t map to itself.
Having two pathways through the rotors just means that the battery can be on the input side, and both the positive and the negative terminals are connected to different contacts. On the other side, we have positive and negative terminals appearing at two different output contacts. It’s easy to do; each key needs to have two plungers (or one plunger with two separate conductors on it) to complete the positive and negative sides of the circuit simultaneously, and each lamp is simply located at a point on the grid where it is the available connection between a given positive line and the corresponding negative line. For different reasons having to do with symmetric encryption and decryption, each key used on the Enigma keyboard completed two circuits anyway, so this is something that could have been done just by rewiring the machine.
If we don’t care about which direction the current runs through the lamps and switches, we can encode a 28-character alphabet using eight input and eight output contacts. But our rotors have 26 contacts on each side. What happens when the contact we reach on the output side isn’t one of the eight we’ve designated as output contacts? Well, we just loop wires back from each of the non-output contacts on the output side back to one of the non-input contacts on the input side. Because we can never map anything back to either of the input contacts used, nor any of the same input contacts reached from any different output contact, neither the positive nor the negative path can ever get into a nonterminating cycle, nor routed into each other shorting the circuit somewhere in the rotors. So both paths will just loop through additional trips through the rotors until they do reach one of the output terminals.
Given this alteration, we now have achieved the designer’s goal of having each letter encrypted depend on two trips through the rotors. But we have done better, for a couple of reasons. Most obviously, the feedback mechanism will actually result in more than two trips through the rotors in the vast number of cases. Each letter encrypted will depend on something between two and twenty passes through the rotor stack, with the average being about six. The simplest case, where there are only two paths through the rotors, will occur less than ten percent of the time, meaning any cryptanalysts trying to work out cyclometric information or wiring diagrams will have to wade through many times as much data before being able to distinguish noise from signal. And we have removed the antireflexive property meaning that now it’s impossible to easily identify or eliminate possible locations for cribs in the ciphertext.
Viewing the rotor stack as having 26 input contacts and 26 output contacts, we want to wire 18 outputs back to 18 inputs, then wire the remaining 8 outputs to the lamp board and the remaining 8 inputs to the keyboard. The way to do this would be to have all the wiring except for the rotor stack in a central case. 26 red wires come out of one side and 26 white wires come out of the other side. The rotor stack has 26 sockets in a red terminal strip and 26 sockets in a white terminal strip, and you connect the wires in a different sequence along each strip for different keys.
Eighteen wires of both sets are simply patch cables that pass through the case with both ends sticking out. The remaining eight on each side go to the keyboard and lamp board.
Having wires into different terminals on both sides, and selecting which terminals to connect to which wires as part of the day’s key, would replace both the reflector and steckerbrett in terms of complexity, but, amplified by multiple passes through the rotor stack, would get vastly more cryptographic leverage than both of them combined.
This is conceptually simple enough, but requires one thing the Enigma did not have: a mode switch. The Enigma implemented a strictly invertible cipher, meaning that at any moment if E would have encrypted as H, then if H had been encrypted at that particular moment, it would have produced E. So encrypting and decrypting were the same operation. If you set the key and fed it the plaintext, you’d get the ciphertext, and if you set the same key and fed it the ciphertext you’d get the plaintext. The revised machinery I outline above does not implement an invertible cipher. Because encrypting and decrypting are now different operations, the machine needs a control that allows the cipher clerk to do one or the other.
The easiest mode switch I can think of consists of two diodes mounted at the battery inputs, and a battery “plug” facing the operator which can be inserted in either orientation. On one side, the plug is Red and says “encrypting”, and on the other side it is white and says “decrypting.” You switch modes by taking out the plug, turning it around, and putting it back in the opposite direction.
Now let’s see how it fares, in theory and guesswork at any rate, against the Third Reich’s history of three major operational errors.
First of all, the general design of the machine was well-known to everybody; the company that made it sold a civilian version of it openly, and England had purchased commercial three-rotor versions as early as 1927. So the idea that there is any secrecy in the design of the machine itself is rubbish to start with. What the Germans sought to prevent the Allies from learning was the wiring of their rotors and their daily keys. For other reasons they wanted to obscure their message keys but did a rather poor job of it.
The military Enigmas wired the keyboard to the input terminals differently than the civilian version, but the difference was hardly made for the sake of security. Whereas the civilian version was wired to input in order from left to right across the keyboard, the military version was wired to input in alphabetic order. With the schema of the redesigned machine outlined above, the wiring of the keyboard to the input is changed each day, so this change is entirely inapplicable.
In operation, the Germans used a daily key and a message key. In their case the daily key was the selection of a permutation of four rotors out of a set of eight, the selection of ring settings, and the plugboard wiring. The revised machine has the same choice of rotors and ring settings, and the plugboard wiring is analogous to the wiring of keyboard/lightboard to input/output side of the rotors. The message key was just the initial position of the rotors.
The message keys had to be transmitted with each message, where the Allies would receive them as part of their regular interceptions. The Allies intercepting the transmissions was expected; the purpose of the message keys was to ensure that messages were not encrypted with exactly the same key, because when they were, the allies could do frequency analysis on each position in the cipher and break all the traffic easily.
The first German procedural error was that message keys were too short. The sequence of only four letters for a message key ensured that messages encrypted with identical day keys and identical or closely related message keys would be available to the Allies, and with a depth of just a half-dozen messages having identical keys, a cryptanalyst can break into the traffic by frequency analysis even if he knows nothing about the evolution of the cipher’s state. They should have made both the ring settings and the initial positions of the rotors part of the message keys. And if they were going to use a four-letter day key, they should have used the ring settings rather than the rotor positions. But they didn’t, because people who understood cryptography were not among those making decisions about how it should be used.
I should explain here how the frequency analysis attack works, because it is equally applicable to the revised machine. Given two messages transmitted with the same key, the cipher will substitute the same ciphertext letters for the same plaintext letters whenever the same plaintext letters occur in the same position. So if the twelfth letter of both plaintexts are the same, then the twelfth letter of both ciphertexts will also be the same. If the cryptanalyst has seen several messages with the same key, he knows the frequency of different ciphertext letters for each position given that key. And those will match up with the frequency of the corresponding plaintext letters in each position for those messages, making it easy to build a set of simple substitution ciphers, one for each message position, that create simultaneous solutions for those messages. In practice, a depth of only two to eight messages transmitted with the same key is sufficient for a cryptanalyst to read all of those messages.
The combination of short message keys and sending too much traffic for those message keys to be reliably unique for every message, meant that some percentage of the German traffic would be read on the basis of frequency analysis, even if nobody knew anything about the key and cipher state. We can assume that they would make the same error with the revised machine, with the same result.
Using the rotor positions rather than the ring settings as message keys was a particularly bad choice, because using the rotor positions, when the rotor positions are the only thing that changes during the operation of the cipher machine, and the change depends only on the current rotor position, meant that the message keys used with Enigma were subject to a very severe related key attack. The set of states that the cipher machine evolved through given a particular day key, were exactly the same set of states that could be specified by different message keys. And this meant that ALL the messages transmitted on a given day started on some point in the same sequence of the states of the Enigma cipher. For example, a message whose message key was AAAA would reach the state AAAC as soon as its fast rotor moved twice. A different message whose message key was AAAC would therefore be subject to the frequency analysis attack relative to the message whose key was AAAA when shifted by an offset of two. That is, an E at the tenth position of the plaintext of the first message would be encrypted as the same letter as an E at the eigth position of the second.
And for the early part of the war, the Germans were transmitting the rotor positions at the beginning of every message, which means in the same position of the message, encrypted according to the same setting. This was a horrible mistake, because it meant the Allied cryptographers could tell, without decrypting anything, which message keys were related by having which rotor positions in common. So they knew that any two message keys differing in the last rotor would be some offset less than 26 from each other, making it trivial to find. And having found the differences for messages differing in the last rotor, they could then turn to the second-to-last rotor, knowing that those messages would be offset by the same number of positions indicated by the difference in the last rotor, plus some multiple of 26. And so on through the last rotor.
Okay, so assume the Germans make the same mistakes with the revised Enigma I describe above. They use the rotor positions – that is to say, the worst possible part of the key – as the message key. Then they transmit the message key, encrypted, at the same position at the start of every message. A cryptanalyst can tell immediately which keys have which rotors in common, but with the faster evolution of the rotors, that’s a smaller problem with the revised machine, because all the message keys are separated by no more than two positions in the sequence from message keys having no rotors in common with them. In fact the longest sequence having any rotors in common positions is only four characters long, which is exactly how long it takes for the sequences to diverge in the first four characters – meaning, as the message keys are transmitted. You knew there was a reason I picked seventeen, didn’t you?
Therefore, the operational mistake of using message keys too short is still a problem because it means messages will occasionally be transmitted with identical message keys and enables frequency attacks against those messages. The operational mistake of using the rotor positions as the message keys is still a problem because it puts all the traffic from a given day on the same cycle of states enabling an extended frequency attack, but with the revised machine, at least it doesn’t tell the cryptographers exactly where to look for overlapping state sequences; they have to find that for themselves.
But the Germans weren’t finished making operational mistakes. At the beginning of the war they transmitted the message key twice at the beginning of each message, giving the allied cryptographers certain knowledge that the ciphertext in the first through fourth positions represented exactly the same plaintext characters as the ciphertext in the fifth through eighth positions. This meant that the allies got cyclometric information for the interval four on the first rotor.
But with the revised machine, it means they get diddley. By the time the offset is four, three rotors have moved at least once, and the fourth rotor is more likely to have moved than not. Additionally, with each movement of the faster rotors, odds are the impulses are being routed through a different number of trips through the rotors. Only ten percent of the time do both impulses go through only one trip through the rotors, and only only once in ten thousand times do they do that four times in a row. Given that the last rotor moves about 25% of the time, the odds of the allies seeing anything that can give away interval information about anything less than ALL of the rotors at once – and here it would be giving very complex interval information about the first three rotors with the fourth one in place – is about one in forty thousand characters. And they have no way of knowing which one. The cyclometric information revealed by that statistically insignificant fraction, taking into account the feedback cycles, is ridiculously complex; I can’t immediately think of a way to derive anything useful about any rotor at that interval even with modern group theory and compute power.
Another operational mistake was the ANX problem. The German operators used Enigma as though it were absolutely the same as sending unsecured messages via paper. As a result, they used a very standard form of addressing everything, just as though it were an internal memo. The German for “to” is “an”, and they were using X for punctuation and spaces. Therefore most messages began with ANX followed by the name of the person or unit to whom the message was addressed, the same way most memos in English begin with TO: followed by someone’s name.
Because the Allies knew the names of the commanders of various German units, and could often guess who needed to get messages to whom, this provided a fertile source of cribs allowing the Allies to see how ANX followed by a name they were likely to be able to guess looked when encrypted according to the day’s key plus a given message key.
However, because of the fast state evolution and unpredictable changes in feedback cycles, it’s still damned hard to use even a correct crib to derive information about any particular rotor. Moreover, the cryptanalysts wouldn’t have the antireflexive property to help eliminate possibilities as to which unit or commander the message was intended for, so they couldn’t even use the process of elimination to know that a given sequence represented the name of a particular commander and therefore what all the other letters of that officer’s name encrypted to at those positions given that message key.
I think that with the revised Enigma described here the Allies could not have made any progress whatsoever on cracking the darn thing using World War II techniques, even given the basic cryptographic mistakes and excessive traffic typical of the Third Reich.
And I see that this post is now over 5K, so I’ll stop here for now. Join us next time as we try to see how, with a little bit of additional hardware, we can try to harden this against modern cryptanalysis.