This could have happened during WWI

Back in 1914, the German Army used a cipher that we have later come to know as “übchi”. It was a double columnar transposition that was quickly solved by French cryptanalysts, including Lt. Georges Painvin, in the picture, who later went on to break the more difficult ADFGX and ADFGVX German ciphers. At the time, the US Army was using a very similar method to “übchi”, so it was fortunate that the French shared their discovery, so they could switch to something better (they didn’t). As it turned out, the French were so bad about keeping this secret that the Germans soon got word of it and replaced it with the ABC cipher, which turned out to be weaker. But not necessarily so, and this article is about what might have happened.

Burned by the disappointment to find übchi broken, they decided to replace one of the two rounds of transposition with a classic Vigenère step, where a repeating and constant “ABC” key was added to the letters before the remaining single transposition. Since the addition key was always the same, the step did not add any security, so that the ABC cipher was in fact little more a single transposition, much easier to break than a double transposition like übchi. They must have had a personnel problem back there, because otherwise it is hard to fathom why they would have done such a stupid change. Painvin lost no time, and before the end of January, 1915, he had produced a method that would recover the transposition key from a single message encrypted with ABC. Once again, the Germans got wind of this and this time they replaced ABC with something stronger, which Painvin and associates eventually broke, as well as all their replacements all the way to the end of the conflict.

But what if instead they had fixed the essential problems of the ABC cipher? These are two:

1. Using always the same additive key. Easily solved. One could use the same key as for the transposition or a completely different one, for a larger keyspace.
2. Using the so-called Vigenère cipher as a first step. This is a weak cipher, and they could have done a lot better with little extra effort. The rest of the article shows some good options.

In a recent article, I discussed some extensions of Blaise the Vigenère’s classic autokey cipher, which uses the plaintext itself as a running key, after an initial “seed” key. Using “snake” operations on a standard Tabula Recta, one can involve several letters in the calculation of each ciphertext letter, rather than just two, with little extra effort. Three is a lot better than two, and four already gives a result that is hard to distinguish from random. Additionally, one can replace the alphabets on the sides of the Tabula Recta with mixed alphabets based on a key, and this increases the difficulty of cryptanalysis enormously with, again, little extra effort, as this paper attests to.

In this article, I show some results from combining the Skink cipher (4-letter operations, non-reciprocal) with a transposition, much like ABC combined the Vigenère cipher with a transposition. The Skink cipher by itself produces output that is close to random, but it has two lingering problems:

1. Dependency measures for ciphertext letters separated by a distance equal to the seed length show a rise over the values for other distances, because those have one letter in common. This means that statistical analysis of the ciphertext can determine the length of the seed, which facilitates cryptanalysis somewhat.
2. Like most classical ciphers, Skink and all the ciphers presented in the same article are vulnerable to a known-plaintext attack, which would recover the substitution key(s) even if the seed is not known.

Adding a transposition step helps a lot with the second problem, since an attacker won’t know a priori which ciphertext letters correspond to which plaintext letters but, as we will see, it also helps with the first problem. To test this, I encrypted the first four chapters of Dickens’s “Oliver Twist” (Gutenberg.org edition) with key “wonderful” for all key and seed choices, and recorded the dependence chi-square measure of the ciphertext letters, both contiguous and separated by seed distance (9 characters in this case). This is what I got, when a single direct or inverse transposition was added at the beginning (plaintext) or end (ciphertext) of the process. In all cases, values below 671 denote less than 10% chance of not being random.

We can see that the transposition has an effect in all cases. A direct transposition at end has the result of moving the point of highest dependence from seed distance to contiguous letters if the transposition key length is equal to the seed length (not otherwise), this is because the transposition joins letters originally separated by the key length. Likewise, a reverse transposition at the start places originally contiguous, highly correlated plaintext letters into positions separated by the key length; if this equal to the seed length, the high correlation of ciphertext letters separated by this distance become all the greater. A reverse transposition at the end seems to lower all the correlations significantly, even for equal lengths of seed and transposition key, but then originally contiguous ciphertext letters end up placed largely at locations separated by a predictable distance, which is bad against a plaintext attack. The best choice overall, therefore, seems to be the direct transposition on the plaintext, which reduces the telltale statistics while protecting against a plaintext attack and does not introduce new problems. We have a winner so far, which from now on will be known as “Super Skink 1,” and which was already mentioned in this article.

Now, a large-scale war is not the same situation as two people secretly communicating with one another. In a large-scale application one has to worry about two extra considerations:

1. A lot of different people will be using the same keys, even if they only last for a day. This will produce a lot of traffic using that one key. The situation is particularly bad if some users fall into the habit of including easily guessable boilerplate text into their messages, which is pretty much unavoidable. This provides the opportunity for a partial plaintext attack, so the cipher must be able to resist this.
2. You get lazy operators that will skip parts of the process if they can get away with it. The result might be still decipherable, but a fatal flaw has been introduced, which an attacker will find and exploit.

Specifically, a lazy operator may decide to skip the initial transposition in Super Skink. When the message is being deciphered, the operators on the other end will get the plaintext before the last reverse transposition, at which point they will stop. Everybody has saved time, but the message has become vulnerable to the known plaintext attack, thus endangering all messages transmitted that day. Because of this, if the cipher is to be used on a large scale, it is best to do the transposition at the end on the ciphertext, rather than at the beginning on the plaintext. Then decryption will have to start with a reverse transposition; if the enciphering clerk skips the final transposition on his end, then those deciphering will end up scrambling the ciphertext, and the decryption will fail. Now, this choice introduces a statistical artifact in the ciphertext if the transposition key has the same length as the seed, but in this situation the keys are issued by a central authority, who can make sure that those keys are of different lengths. Because in this case the transposition is done at the end, it can use with advantage the addition of a few nulls before the plaintext right before the first operation, which the JavaScript file linked below also implements via a button.

There is another powerful reason why it is better to do the transposition on the ciphertext rather than on the plaintext. Since transpositions do not change the actual letters in a text, but only their relative order, if the transposition is performed on the plaintext the partially decrypted message prior to the final reverse transposition will contain a highly biased set of characters. This makes it possible to know when the correct substitution set of keys has been used, even if the transposition key is completely wrong. Therefore, the key space represented by the transposition (26! possibilities, give or take a factor of 2 to account for keys shorter than 26 characters) does not multiply the substitution key space, but rather adds to it. This is an immense loss of key space that it is best to avoid.

So this is the final Super Skink cipher, specifically designed for the German High Command of World War 1:

1. Make mixed alphabets from as many as two separate keys, which will be used for a substitution at the edges of the Tabula Recta used in operations.
2. If decrypting, use the transposition key to do a reverse transposition of the ciphertext. Skip this if encrypting.
3. Write the seed above the start of the plaintext (ciphertext when decrypting), and do two-letter operations on the Tabula Recta with the plaintext (1st) and the seed (2nd) to fill in the beginning of the ciphertext (plaintext when decrypting).
4. After the seed letters have been used, do four-letter “snake” operations on the Tabula Recta with these letters to find the rest of the pre-transposition ciphertext (plaintext when decrypting). For encryption: plaintext (1st), plaintext at seed length before (2nd), plaintext at seed length minus one before (3rd), ciphertext at seed length before (4th). For decryption: ciphertext (1st), plaintext at seed length before (2nd), plaintext at seed length minus one before (3rd), ciphertext at seed length before (4th).
5. If encrypting, use the transposition key to do a direct transposition of the ciphertext. Skip this if decrypting.

All in all, this is not a lot more complex than ABC already was. Finding mixed alphabets for the substitutions (step 1) will add perhaps one minute per key. The operation in step 3 are equally complex to those in ABC, and those in step 4 take perhaps 50% longer per letter. There is only one transposition step, as in ABC. Super Skink could have been used to replace ABC if the Germans had had at their disposal the statistical tools that allowed us to optimize the method. Had they received it on time, it is likely that the Allies would have seen a complete blackout in their main source of intelligence, arguably leading to a very different outcome for the whole war effort.