Lessons from the VIC cipher

In the mid-1950’s, the Soviet spy Reino Hayhanen, codenamed VIC, and his handler Rudolph Abel (in the picture) pulled off an incredible feat: they utilized a paper-and-pencil cipher that not even the FBI (the NSA wasn’t operating within US borders back then) was able to crack until Hayhanen defected and explained its inner workings. Computers already existed, and they were used primarily to crack ciphers like VIC. In this article, I go over some of its features, and how they can be used to enhance other simple ciphers.

Now that we know how the VIC cipher works, we realize why it managed to remain unbroken. It’s a combination of several things:

1. Straddling checkerboard encoding of the text into numbers, which smooths out single letter frequencies quite effectively and provides some fractionation.
2. Double columnar transposition, the latter of which was of the disrupted kind. This scrambles the encoded plaintext and, for letters that were split into two characters, those characters get separated in the ciphertext in a way that it is hard to see their relationship.
3. Lagged Fibonacci generators to stretch number series into long, apparently random sequences.
4. A per-message five-digit serial, which is hidden somewhere in the ciphertext, so that not two messages are enciphered the same way.
5. A longish 20-character literal key, plus a 5-digit secret date and a 1 or 2 digit personal number. That’s a lot of key material for the time.

And, of course, the fact that the algorithm was unknown to others.

Now that the algorithm is known, the VIC cipher isn’t very secure anymore, because the key, although quite long for the 1950’s, is not up to today’s standards. The twenty characters were used to generate two 10-place permutations, which means that there are at most 10!^2 = 13.168×10^12 combinations. Multiply that by the 5-digit decimal date (100×365 = 36500 combinations) and the two-digit personal number, and you get a maximum of 4.8×10^19 combinations. It’s best to put that as bits of entropy, so we take the decimal logarithm and divide by log(2) = 0.3 to get a rather low 65.6 bits. This is roughly as much entropy as four words taken from an English dictionary.

So the question is, can we update VIC, or something like it, so it would stand a chance against today’s computers? In order to achieve this, we need the following:

1. The ability to use a longer key. At 13.3 bits per dictionary word, a sentence containing a number of words can quickly collect a lot of entropy while remaining easy to remember. The problem is making the algorithm use all of that material.
2. It must be so that any change in the key or the serial number, if there is one, will result in a completely different encryption. This way cryptanalysts won’t know if they are “getting closer” to the solution as guesses are being made and tested.
3. Any regularities present in the plaintext are destroyed by the encryption, so that the ciphertext appears to be completely random, or has statistical properties that have nothing to do with those of the plaintext.

Since we are talking about a paper-and-pencil cipher, we also need the labor involved to be minimum and the process to not be conducive to errors. VIC struck a good balance between security and ease of use, but some steps appear to be unnecessary complication. We need to use processes that have a high ratio of security to labor, and avoid those with a low ratio.

Here are the kinds of processes involved in the VIC cipher:

1. Substitution. A single substitution is insecure as it does not mask regularities in the plaintext. It does, however, lead to a relatively large keyspace. Using the 26-letter Latin alphabet, there are 26! = 4×10^26 possibilities, or 88.7 bits of entropy. Chained substitutions simply convert into other substitutions without increasing the keyspace. Special substitutions, like straddling checkerboards for instance, do a better job at masking single-letter language statistics, but multi-letter statistics remain so that they are better used in combination with transposition.

2. Transposition. A single transposition usually leaves too much regularity so that a double transposition is more commonly used. Unlike substitutions, the complexity of a chain of transpositions grows as more transpositions are added (unless some are inverse of other transpositions), up to a limit equal to the factorial of the plaintext length. The actual keyspace size depends on the length (number of columns) of each transposition. Transpositions are even faster to perform than substitutions. The special “disrupted” transpositions used in the VIC cipher are a little harder to perform, but security is greatly increased because the transposed pieces are of irregular, hard to predict lengths.

3. Stretching. VIC uses lagged Fibonacci generators (LFG) in order to lengthen a sequence of numerical digits, the seed. The process is fairly quick and the result has good random-like properties. LFGs do not increase the entropy of the seed, however, since the final sequence can be reversed back to the seed by solving a linear system. A way to prevent an attacker from reversing the sequence back to the seed is to use fewer digits than those originally in the seed, but in this case the LFG actually contracts the seed rather than expand it.

4. Sequencing. Often a series of digits are converted into a permutation of the same length by counting the digits present from smallest to greatest (repeated digits are counted sequentially from left to right). This process actually reduces the entropy, but is necessary as a prior step for a transposition or a substitution. Since entropy is reduced, it is best to use this operation only when strictly necessary.

5. Modular addition and subtraction. This is normally done near the end, when the plaintext encoded as decimal digits is combined with a pseudorandom numerical sequence. It is a quick process, though not as quick as transposition. The entropy of the result is that of the operand having the largest entropy. Thus, adding a high-entropy sequence to a low-entropy plaintext results in a high-entropy ciphertext suitable for transmission over insecure channels.

Some of these processes are quick and fairly resistant to error, such as transposition, substitution, and sequencing. Other processes, however, involve mental calculations, and are therefore more conducive to errors; of this kind are stretching and modular addition and subtraction, which therefore it is best to avoid. Even the very mechanical transposition process can easily lead to errors when the number of different symbols involved is small, so that they are repeated often, and tedium sets in.

In other articles, I presented the Restonia and Aphid ciphers, which combine substitution with transposition using arbitrarily long passphrases in order to obtain great security with a minimum of effort. In an even older article, I presented the Root stream cipher, where those passphrases can be used to generate a high-security pseudorandom keystream.  Can some of the techniques used in the VIC cipher be used in order to strengthen them further without adding too much complexity? I believe we can start with these three:

1. Always use a random serial. This would take the form of a three-letter sequence for Aphid, a five-digit number for Restonia or Root. This way, every message would in fact be using a different key. In Aphid, the sequence would be prepended to the first passphrase word in order to find the first transposition key. In Restonia, the same thing could be done, perhaps after the serial has been converted into letters via the checkerboard, or using the serial alone for an additional transposition performed before the others.
2. Hide the serial within the final ciphertext, rather than putting it always on the same spot. For instance, one could do this: take the lengths of the last two words of the passphrase (say, 6 and 4, for “secret code”), and count the resulting number of characters on the ciphertext (64), insert the serial there, and then continue with the ciphertext. If the ciphertext is shorter, reverse the figures; if that is still too long, add them instead; if still too long, take only the first; if still too long, take the smallest. The recipient will know where to find the serial since he/she knows the passphrase, whereas cryptanalysts will tear their hair out trying to spot it among so many similar characters.
3. Always use disrupted transpositions. The type used in VIC, consisting of making triangular areas based on the key numbers at the top of each table, which are filled first on the left, then on the right, is quite easy to do. The only complication is having to calculate the size of the transposition tableau, and then mark the triangular areas before filling them. The process is identical on the receiving side. VIC used a disrupted transposition only for the final step, but there’s nothing stopping us from using the process in every transposition step.
4. Hide the start of the message. This seems like a silly thing to do, but if you stop to think that many messages start or end in the same stereotyped way (they shouldn’t, but we’re human) you’ll realize that this is is making the cryptanalyst’s job easier. This is how Enigma and a bunch of other “unbreakable” ciphers were broken. Hiding the start is like cutting a deck of cards: select a spot in the plaintext at random, place a marker there, then reverse the position of the two parts: message after the marker goes first, then the marker, then the message before the marker. Upon decryption, the recipient will be able to spot the marker easily enough in order to put the two parts in the right order.

There are other features of VIC that I think would add too much complexity for little additional gain:

4.  Stretch the serial + passphrase before deriving transposition keys. This would involve conversion into decimal digits and at least one instance of lagged Fibonacci sequencing of the result. In this way, any change in the serial or the passphrase would propagate so it would affect a number of digits in the stretched key, resulting in greater security. Unfortunately, the process is linear so that anyone who has figured out the serial can stretch it by itself and then subtract the result in order to get just the stretched passphrase (and possibly stretch it again with a different serial). Moreover, the process involves a lot of mental calculations where it is easy to introduce errors.

5.  Use part of the passphrase to perform an additional substitution, this time on the transposition codes. Since this is passphrase-dependent, it hardly adds any security to the overall process, just extra work and opportunity for errors.

Let me finish with a worked-out example. Suppose we want to encrypt “Extraction will proceed at 6:23 am at end of pier 49” using the strengthened Restonia cipher with passphrase “secret code” (only two words so the example isn’t too boring; you should use five or more) and random serial “83755”. Here’s what we do:

1.  Make the straddling checkerboard as explained in this article:

  1 2 3 4 5 6 7 8 9 0

  S E R   T   O A I N

6 C D . # Z Y X W V U

4 Q P M L K J H G F B

2.  Turn the serial into letters using the checkerboard, if a digit is still wanting, take the first letter available: 83755 = AROTT. Then use it as the first word of the passphrase. Make the transposition codes from the serial and the passphrase words, as also explained in the Restonia article:

13254, 531427, 1423

3.  Encode the message into digits using the checkerboard:

267538615970 6894444 4237612262 85 646236464 843 85 5472 2062 749 42923 6449

4.  Make the disrupted transposition tables. I will show how the first one, corresponding to the serial, is organized and then filled. Since there are 65 digits in the message and the serial has 5 digits, there will be 5 columns and 13 rows. The triangular areas are made this way: find the “1” on the transposition code and mark the first cell under it as a “right” (we’ll use a “*”), plus all the cells to the right of it; then on the next row start one cell to the right of the original column and mark as right all the cells to the right; keep doing this on every row until there are no more cells to mark as “right”. For the next row, find the cell under the “2” on the code and do the same on this row and those below it. Then do it for “3” and so on; if you run out of code, start with “1” again. Here’s the result:

1 3 2 5 4

* * * * *

  * * * *

    * * *

      * *

        *

    * * *

      * *

        *

  * * * *

    * * *

      * *

        *

        *

5. Now we fill the table with the digits of the encoded message, from left to right and top to bottom, first on the unmarked “left” area, then on the marked “right” area. Here’s the “left” half:

1 3 2 5 4

empty

2

6 7

5 3 8

6 1 5 9

7 0

6 8 9

4 4 4 4

4

2 3

7 6 1

2 2 6 2

8 5 6 4

And here’s the whole filled table:

1 3 2 5 4
6 2 3 6 4

2 6 4 8 4

6 7 3 8 5

5 3 8 5 4

6 1 5 9 7

7 0 2 2 0

6 8 9 6 2

4 4 4 4 7

4 4 9 4 7

2 3 9 2 3

7 6 1 6 4

2 2 6 2 4

8 5 6 4 9

5.  We now read the table by columns (skipping the header codes), starting from the one headed “1”, then “2”, and so on:

6265676442728 3438529499166 2673108443625 4454702773449 6885926442624

This will be input into the second transposition table, which is made along the same process as the first, but using the second code, and then the result of this into the third, at the end we’ll still have 65 digits, but in a different order.

6.  Finish by putting the serial itself at a position what only the recipient can find. Since the first passphrase word had 6 letters and the second had 4, we’ll try to put it after digit 64, if possible. In our example, this means one digit from the end of the message, so we’ll take the first 64 digits, then the serial, and then the final digit in order to make the code that will be transmitted.

The recipient will start by retrieving the serial from the transmitted ciphertext since he/she will know its position from the passphrase word lengths, then will make the transposition codes and the straddling checkerboard. Next step is to fill the last transposition table by columns, following the order dictated by the code at the top, and then read off the result by rows taking into account the left and right areas (marked out as the table was filled), first the left, then the right. Then the second-last table, and so on until the first transposition, which is derived from the serial. After this, the code can be converted back to the plaintext using the straddling checkerboard.

The cryptanalyst has several things to figure out, pretty much all at the same time:

1. The location and value of the serial, and what it is. The number of possible guesses is the length of the ciphertext minus five, if a five-digit serial is used. This obtains the serial and, in the unlikely case of a two-word passphrase, the digits on the left side of the checkerboard.
2. The number, length, and value of each of the transposition codes, other than the serial. There are many combinations here; the number is quite difficult to estimate without knowing the length of the passphrase, but is by far largest. Five words out of a 10,000-word dictionary each would give 10^20 possibilities.
3. The location of the letters on the straddling checkerboard. There are 8!*10*9*16! = 7.59×10^19 possibilities. This is related to the previous, so the two combine into the 10^20 number (if five words were used; multiply by 10^4 for each additional word).

Going by successive approximations based on fitness to language statistics will be very difficult because single-letter statistics are undone by the checkerboard substitution, and multiple-letter statistics are undone by the transpositions. Multiple anagramming is undone by the serial producing different transpositions for different messages. All that’s left is brute force, and here’s where the ability to use an unlimited-length passphrase comes in.