Upgraded Enigma

The standard Enigma was almost unbreakable. Breaking it required tremendous cleverness and enormous resources. So we shouldn’t be too surprised by the idea that it could be upgraded to make it truly unbreakable by the standards of the time.

1.1 Ground rules; goals and non-goals

A cryptosystem that is suitable for purpose (A) may be unsuitable for purpose (B) and vice versa. Actually IHMO Enigma was a lose/lose proposition: Too clunky for purpose (A) but too insecure for purpose (B). The goal here is to upgrade it, to make it secure enough for highly-demanding type-B situations, without making it unduly laborious.

In particular, the focus here is on a system that would be suitable for U-boats communicating to/from their headquarters.

There is a famous example where codebreaker Mavis Batey at Bletchley Park noticed that a particular intercepted ciphertext contained not a single letter "L" anywhere. Evidently some Italian soldier had formed a test message by hitting the "L" key again and again. The Enigma is pretty strong in a number of ways, but the fact that no letter can map to itself was a glaring weakness. In this case, it gave the codebreakers a known plaintext to work with.

So one of my criteria is to defend against this sort of thing. Specifically: Even if there is chosen plaintext, or a known plaintext, or a plaintext repeated in depth, or merely a stupid plaintext, this cannot easily be detected by looking at the ciphertext, and cannot be used to attack the system.

The present discussion is limited to schemes for upgrading security without replacing the thousands of enigma machines that were already in the field. (It is possible to do much much better, in terms of both convenience and security, if we design a replacement machine from scratch.)

In more detail: The machine has a tremendous amount of configurable state, but the Germans relied far too much on changing the state once per day. The amount that changed on a per-message basis – the session key – was only three letters. Later they increased this to four letters, but that’s still not nearly enough.

Combining weaknesses (a) and (b), we can say that the machine is vulnerable to "the related-key attack from hell" as Ray Dillinger eloquently put it.²

To a first approximation, the answer is superencryption. Combining Enigma with almost anything else is a major improvement. Using an Alberti cipher disk (known since the 1400s) is simple and very effective:

cipher_disk(key ab) → Enigma(key cde)

(1)

This increases the size of the session key space (bug a), Assuming three rotors, the Enigma needs three sesson-key letters. In addition, we use two letters to look up a key-stream to use with the Alberti cipher disk. All in all, this superencryption scheme enlarges the key space to 26⁵, i.e. almost 12 million. (This stands in contrast to the standard WWII Enigma key space, which is only 26³, i.e. 17576).

Note: For simplicity, this discussion assumes a three-rotor Enigma, except as noted. You can easily re-do the analysis for a four-rotor Enigma.

We can greatly improve key selection using diceware and hashing. This significantly alleviates bug (e).

1.2 Background and review: Basic Enigma

Each day, the machine is set up with the configuration-of-the-day, based on a codebook. This is very elaborate. You get to choose a set of rotors, permute the rotors, shift the rings on the rotors, and wire the stecker board. There is nothing particularly wrong with this step.

In addition to the configuration, there is also a three-letter key-of-the-day, which also comes from the codebook.

On a per-message basis, the operator is required to choose a session key. This consists of three letters. It is supposed to be random. A common operator error was to choose one that was not nearly random enough. In any case, even if it is random, three letters is not enough. That is to say, the size of the key-space for the session key is not big enough. Really not.

The procedure is to set the key-of-the-day into the machine, and use that to encode the session key. This creates a header block that is sent to the recipient.

Then the machine is reset to use the session key. This is used to encode the actual message.

2 Procedures for Enigma 2.5

We must introduce one new concept, namely the pre-key. Rather than encrypting the session key and sending that over the wire, we encrypt the pre-key and send that. The actual session key is computed from the pre-key.

We use dice to create letters for the pre-key. Roll pair of dice, and use that to choose a letter according to Table I. Use colored dice: Red for the row in the table and blue for the column in the table.

In the table, the ϕ symbol means "invalid; roll again". Re-do just the most recent roll of the dice-pair; you don’t need to re-start the pre-key from scratch. (You have to re-roll the pair, not just one die or the other.)

Procedural rule: The dice should be permanently part of the machine, so they can’t get lost or "borrowed". Enclose them in some sort of "dice popper".

** Table I **

This scheme produces pre-keys with absolutely flat statistics. Guaranteed. Dice are reliably random; people are not.

For a three-rotor enigma plus Alberti, if you need 5 letters for the session key, so generate a 10-letter pre-key. For a four-rotor enigma, generate a 12-letter pre-key.

Add the pre-key letters in a running sum. The Alberti disk serves a slide rule to perform modular addition in the base-26 number system. Every second partial sum becomes a session-key letter. Here’s an example. For simplicity we assume the inner and outer disks on the Alberti disk are the same, so no substitution is being performed, just modular additioan:

In the row labeled partial sums, each letter is the sum of the one above it plus the one to its left.

Using a mixed alphabet on the Alberti disk makes this fancier with no extra workload on the user.

The pre-key gets encoded using the configuration-of-the-day and the key-of-the-day, then transmitted. This is called the header block.

At this stage of the process, the pre-key is considered slightly tainted. That’s because the adversary gets to see an encrypted version of it. In particular, consider what would happen if the session key itself is transmitted, as it was in the standard WWII Enigma procedure. It gets transmitted in encrypted form, but everybody in the same region is using the same key-of-the-day, so the attacker can detect collisions and pounce on them. By sending the pre-key instead, we make it very much harder to detect the collisions. Session-key collisions still occur, but they are harder to detect.

No computation is needed to obtain the key-of-the-day. The key itself (not the pre-key) comes from the codebook.

The pre-key/session-key worksheets must be promptly destroyed. Make absolutely certain that no session-key is ever reused.

Further discussion: There are 26⁵ possible session keys in this system. That’s more than 12 million. However, accounting for birthdays, if the adversary collects 6,000 messages they have a chance of finding two keys the same. Reportedly Bletchley Park at its peak collected "thousands" of messages per day. So there’s a collection problem: It’s only barely possible to collect enough messages to find a collision. On top of that, there’s a computation problem: Searching for related keys would require millions of comparisons, which is beyond the capabilities of the available technology. Thirdly, it would not be easy to pick out the pairs that collide, because the pre-keys are bigger than the actual session keys.

Note: The key-of-the-day is never used to encode anything except pre-keys. The header block does not contain any routing information or anything like that. And the pre-keys are random with absolutely flat statistics. So there is no chance of a known-plaintext attack against the key of the day.

3 Using the cipher disk

	plain	mixed
	alphabets	alphabets

		prehistoric
fixed:	Caesar	monoalphabetic
	cipher	substitution

short weak key:	Vigenère	classic
	cipher	Alberti

long random key:	Vernam	overkill
	cipher

By “short” we mean shorter than the message being encrypted. By “weak” we mean there are patterns in the key.

In the case of an endless random key-stream, the disk functions as little more than a slide rule for performing non-carrying modular addition in the base-26 number system. It also may function as an S-box, but if the key-stream is random that doesn’t really improve things.

For present purposes, we obtain the key-stream from the codebook. There are 26 pages, each of which has 26 starting points. Starting at the appropriate point, read off the key-stream letters. At the end of the line, continue to the next line. Continue to the next page if necessary. At the end of the last page, wrap around to the first page. (The codebook can use the same 26 pages for an entire month; there is no need for 26 pages per day.)

Use the key-stream letter as follows: Set the index on the disk according to the key-stream letter. Then find the input message letter on the inner disk, and read off the corresponding output letter from the outer disk.

Discussion: In some sense, using this cipher disk is like adding another rotor to the Enigma machine – but with some very important differences.

For starters, unlike the rotors in the machine which only step from one position to a neighboring position, the disk index spins wildly after each letter. This alleviates problem (b): The state of this part of the machine changes a lot at each step.

Secondly, the disk solves problem (c). Each letter can map to itself, with the ordinary probability. As a related point, decryption is different from encryption. During decryption you find the ciphertext letter on the outer disk, then read off the plaintext letter on the inner disk.

With only 26² starting points, it is guaranteed that different messages will sometimes use the same key-stream. If we relied on this exclusively, it would be insecure – but remember that it is used in conjunction with the Enigma machine. For present purposes the codebook must contain a long-enough key-stream so that it does not repeat within any given message. Messages using the same disk-key will be using different Enigma-keys.

Let’s be clear: We are combining two things, neither of which would be secure without the other.

Although there are only 26 starting points, each page has 27 lines. The last line is reached by continuation from the previous line. Similarly, there is a 27th page, which is reached by continuation from the previous page. This is to ensure that the cycle-length for the Alberti cipher is incommensurate with the cycle-length for the Enigma.

The 27-page tabulated key-stream described above is enough to handle a 7000-word message. You could impose a rule that long messages must be broken up into parts, with no part longer than a couple thousand words, with each part using its own unique session key ... but that’s not really necessary, because by the time the cipher-disk key-stream repeats, the machine state has changed substantially. So the attackers will have a hard time exploiting the repeat. Also, it is a_priori unlikely that a lot of 7000-word messages will be sent.

Remark: Disk ciphers were used in the field during the US civil war in the 1860s. I take this as evidence that the method is practical and reliable under combat conditions.

A new codebook (with a new key-stream table) is issued every month. A submarine leaving for a 45-day deployment will need two or three codebooks.

4 Extensions and Ramifications

Security always involves a tradeoff. One of the goals is to increase the workload on the adversaries without disproportionately increasing the workload for your own team.

For example, you could increase the size of the keyspace by one letter, as follows: In addition to the two letters use to look up a key-stream starting point, as previously described, use a third letter as an additive. That is, use the cipher disk as a slide rule to add this key letter to each letter in the key-stream that comes out of the book. This increases the key space to 26⁶ – three for the Enigma and three for the cipher disk.

It’s not clear this is worth it. Perhaps it could be kept in reserve. If the 5-letter keys appear to be vulnerable, you could quickly switch to 6-letter keys.

Another possibility might be to use Enigma to superencrypt itself, by making two passes through the machine, using two different keys:

Enigma(key abc) → Enigma(key def)

(2)

However, this is not really such a good idea, because some of the weaknesses remain. In particular, the cycle-length of the two machines is the same (26³ = 17576).

Another problem with this is that unless you have two Enigma machines side by side, this would require writing down the intermediate results. This is a significant inconvenience, and a possible source of error. (Note that in contrast, the combination of Alberti disk and Enigma machine, equation 1, can be operated in tandem, online, without writing down any intermediate results.)