|
| |
| Figure 1: Front Side of Rotor | Figure 2: Back Side of Rotor (mirror image) | |
The Nundrum Cipher Machine |
The challenge for today is to design a crypto machine that could have been built using WWII-era electromechanical technology (i.e. no electronics), yet offering greater security than the actual machines of that era. In particular, we want to avoid the known weaknesses discussed in section 4.
The objective is simple yet lofty: Even if the adversary captures the machine, including the whole ensemble of rotors, along with a goodly number of known plaintexts, they still won’t be able to decrypt other messages from that day, or any past or future day, assuming of course that they don’t capture the codebook containing the daily keys.
The proposed machine is called Nundrum.
It makes use of the following good ideas that were available at the time:
Each rotor in the Nundrum machine is made using PCB technology. It has two sub-boards laminated together, with a total of three metal layers. The front sub-board has metal on the front side, while the back sub-board has metal on both sides.
One sector of the front of a typical Nundrum rotor is shown in figure 1. The rotor has 24 rows, spaced every 15∘ around the circle, but for simplicity only three rows are shown in the figure. The rectangular areas are contact pads. These are the same on all rows of all rotors, so they don’t give away any information about the wiring. On each row there are ten pads, in five groups of two, which handle a five-bit binary code (such as Baudot code) using the two-wire representation. The generalization to six or more bits is straightforward.
An analogous mirror-image view of one sector of the back of the combined board is shown in figure 2.
Figure 3 shows the wiring of the rotor. This is sandwiched in the middle, where nobody can see it. Figure 4 shows an Xray view of all three layers together.
The round blobs at the end of the wires are vias. This is where electrical connection is made from one layer to another, by soldering. Plated-through holes were not developed until 1947 (reference 9), so it would be ahistorical to rely on them. More generally, electroless autocatalytic deposition was not developed until 1946 (reference 10). The vias are positioned so that the contact fingers never rub against them.
The wiring is set up so that on the row that is horizontal in the diagram (the 9:00 row) each pad on the front is connected to the pad directly behind it on the back. Meanwhile, on the row above that (the 9:30 row), each pair of pads is cross-wired. Since we are using the two-wire representation, this is the logical NOT function. To say the same thing another way, on the horizontal row the input is XORed with subkey 00000, while on the row above that, the input is XORed with subkey 11111. On the row below horizontal (the 8:30 row), the input is XORed with subkey 10011.
Each rotor can rotate to 24 different positions. Each rotor can be flipped front-to-back, which means it cycles through its various subkeys in the reverse order.
The Nundrum machine uses N such rotors in series, where N is at least 12.
In the machine, there is a stator between each pair of rotors. On each side of the stator there are spring-loaded fingers that make contact with the pads on the rotors. Only one row of the rotor is active at any one time, so the stator needs only ten fingers on each side.
The main rotors used to encrypt a character are called the cipher rotors. In addition, there are N control rotors and N index rotors. The control and index rotors function as a PRNG, and are used to control the advance of the cipher rotors. After each character of the message, a random subset of the cipher rotors is advanced. On average, half of the rotors advance each time.
The advance of the control rotors themselves is influenced by the ciphertext. This implements ciphertext feedback (CFB) mode. It introduces an important nonlinearity. It means that Nundrum is not simply a stream cipher. It also means that encryption is not the same as decryption. A switch is needed to select ciphertext=output (during encryption) or ciphertext=input (during decryption). Note that the control rotors are advanced during one phase of the cycle, and the cipher wheels are advanced at a later phase. This implements a form of master/slave timing, so there are no glitches, no race conditions.
This setup provides 243N bits of state that can change during the message, even if one assumes that the adversary knows the choice of rotors, the order of rotors, and the wiring of each rotor. Note that 2436 ≈ 2165. This stands in contrast with a three-rotor Enigma, where the message keyspace was only 263 = 17576 ≈ 214.
There is additional state that is static, i.e. does not change during the message. We devalue this, because cryptanalytic strength depends more on the changes of state than on the state itself.
The combination of rotors and stators, arranged on the spindle, is called a basket of rotors. The choice of rotors does not change during a given message. Good practice is to change it on a daily basis, by installing a new basket of rotors. (The old basket should be kept around for a little while, to handle messages that were encoded before the changeover but not decoded until after.)
On a character-by-character basis, the order of rotors within the basket does not matter, because XOR is a linear operation, i.e. addition modulo 2. However, over the course of a message the order does matter, because the advance is different for each rotor position.
Each machine ships with a set of dice. Each session key (aka message indicator) is 3N characters long. For each character, operator rolls the dice and then looks into a small codebook. The importance of randomness is strongly emphasized. Headquarters keeps records of all session keys used. Any operator caught re-using a session key, or otherwise using a non-random session key, is in serious trouble.
The session key is encoded using the key of the day. Then the message payload is encoded using the session key.
Here is one way of looking at the contrast between Nundrum and Enigma:
| Nundrum uses a large number of simple rotors. | In contrast Enigma used a smaller number of more complicated rotors. |
| There is such a thing as an emergent property. One quill taken from a porcupine isn’t very scary, but the living porcupine as a whole is not to be trifled with. | The state space of the Enigma was too small. What’s worse, during a message, the state changed only slowly from one character to the next. The complexity of the rotors did not make up for the small keyspace and slowly changing state vector. |
| On a character-by-character basis, a single Nundrum rotor can implement any one of 25 different permutations of the alphabet. Putting N rotors in series does not change this number. It’s always a simple five-bit XOR. | A single Enigma rotor can implement an arbitrary permutation of the alphabet. There are 26 factorial ≈ 288 such permutations. Putting N rotors in series does not change this number. |
| It could be argued that Enigma devoted too much attention to character-by-character security, and not enough to message-by-message security. We prefer a balanced approach, with sufficient character-by-character security and vastly improved message-by-message security. |
| For a simple stream cipher, the nightmare scenario is when (a) the adversary obtains a known plaintext and the corresponding ciphertext, and (b) the key is reused. The adversary can trivially read all messages enciphered using that key. | With a more general substitution, knowing how letter A is encoded gives away very little about how letter B is encoded. |
| On the other hand, this advantage comes at the cost of complicated and bulky rotors, and the advantage largely evaporates if/when the adversary learns the rotor wirings. |
| One way to proceed is to accept the inherent limitations of a stream cipher, and just do whatever is necessary to make sure no two messages are ever sent with related keys. This is easier to arrange when the keyspace is large. | Ray Dillinger pointed out that Enigma is vulnerable to “a related-key attack from hell.” |
| A second line of defense is to operate in CFB (ciphertext feedback) mode. This means the system is no longer simply a stream cipher. You’re still in trouble if the same key is used for similar plaintexts, so the fact remains that the primary source of strength is to make sure you never use a repeated key or a related key. |
Known plaintext permits a rather direct attack on the cipher rotors, but there is no correspondingly direct attack on the index or control rotors.
This multi-phase advance process can be carried out more than once per character, with the timing controlled perhaps by a camshaft. This increases the rate at which the internal state changes. This increases the workload for the codebreaker who has achieved a partial break and is trying to extend it.
A Feistel structure is guaranteed to be reversible. That is one way of guaranteeing that a cipher can be deciphered. However, we are not making use of that property. Instead, we benefit from knowing that the PRNG update rule is reversible in the thermodynamic sense. Phase space is conserved. This guarantees that key bits are not being wasted. (This stands in contrast to an operation such as XORing the key [or some part of the key] with itself, which would produce all zeros, which would constitute a highly undesirable loss of significance.)
On the other hand, there are other ways of doing it, using lugs and levers and one big actuator.
In Nundrum, reflection does not prevent a character from encoding to itself.
This makes the cipher slightly less resistant to cryptanalysis, insofar as subkey bits get re-used twice as often. This is probably not worth worrying about. However, if you insist on worrying about it, you can compensate for it by adding another rotor in series, increasing N by 1. That still leaves us with a substantial decrease in size and mass of the rotor system.
| This is significant because permutations do not commute, in contrast to XORs which do commute. This means that re-ordering the rotors within the basket changes the transformation. | On a character-by-character basis this doesn’t make the transformation more random (since it was already as random as could possibly be). Also it does not change the rate at which the internal state changes during a message. |
| The best you could hope for is that this would provide additional 12 factorial ≈ 229 bits of state that the adversary needs to figure out on a day-by-day basis. This information is static on a character-by-character or message-by-message basis. | The order of the rotors already matters, since different rotors advance differently. |
All in all, it’s not clear that permutation wiring on cipher rotors is worth the trouble, even though the cost would be extremely low.
There is a slight cost, namely the cost of transmitting a larger session key. Another slight cost is the risk that a stator could become lost or worn out, which is much less of a problem if the stators are interchangeable and spares are available.
What’s worse, the additional state is static over the course of a message. The Nundrum design philosophy puts a premium on changes of state, rather than state per se. Therefore we judge that such a permutation can’t hurt and might help, but the security of the machine does not rely on it.
All in all, it’s not clear that permutation wiring on the stators is worth the trouble.
Early Enigmas had three rotors. Later ones had four, or maybe five if you count the reflector. This is not enough. See reference 11.
Note that using a fixed reflector doubles the number of rounds but does not increase the keyspace at all.
It could be argued that this is not a fault of the cipher hardware, but rather an operator error. However, we should consider the system as a whole. It would be an improvement to design a system where it is easier to do the right thing and harder to do the wrong thing. This is why the Nundrum machine includes a set of dice.
Tunny had a much larger keyspace, but several rotors did not change at all during the course of a message, so in effect those rotors implemented a monoalphabetic substitution.
In contrast, SIGABA and KL7 used much more active and much more complicated ways of advancing the rotors.
This was a serious weakness, especially when coupled with a known or probable plaintext.
This is a convenience insofar as the exact same setup can be used for encryption and decryption, but it must be considered a weakness with respect to cryptanalytic attack.
Note that it would have been much more secure, slightly more convenient, and just as useful to encode the session key only once but then transmit it twice.
