Did you know that the actual cipher invented by Blaise de Vigenère, back in the XVI century, is not the one that bears his name? The so-called Vigenère cipher was actually invented a few years earlier by Giovan Battista Bellaso. Vigenère’s own creation is a version of what today we call “autokey” cipher, and it is more secure than Bellaso’s. Of course, today’s computers can break both of them in seconds, but there things we can do to strengthen them to the current standard. Best of all, the resulting ciphers, which I’m calling “Visionnaire” and “Worm” (you will see why), can be done with paper and pencil. Visionnaire has its own article, so I’ll be talking about Worm here.
Worm follows right in the heels (assuming it had any legs) of the Snake cipher. That cipher achieves near-perfect unbreakability by using a key text that is three times the length of the plaintext. That key can be obtained from a book or similar source that both the sender and the recipient know, and transmit only the ciphertext plus a marker to find the starting position of the key text within the book. A lot better than having to make a set of special-purpose one-time pads, but still they need to have the same book and never reuse a page from it. But what if they don’t have the book? Can a similar level of security can be achieved with a relatively short key, through paper and pencil?
Here’s where Vigenère (pictured at right) comes in. His autokey cipher replaced key material with the plaintext itself, after the encipherment had been initiated with a proper key. It worked quite well, except for the fact that an attacker only needs to guess pieces of plaintext, which are then subtracted from the ciphertext at every possible point in order to obtain other pieces of plaintext. This progressively leads to recovering the whole plaintext and eventually the key. This is possible because the plaintext used as key can be recognized easily as common text.
In our case, however, we are going to use this approach to lengthen the key text so eventually it is as long as the plaintext, which is always possible since what we are adding comes from the plaintext itself. Now this still would fall short of the triple-length key text that Snake uses. No problem. The second piece can be the short key itself repeated as often as necessary, as done in the so-called Vigenère cipher.
Only one more piece to go. Well, we have the ciphertext, which looks quite random. Why not use it to lengthen the key until a third row of key text is completed? This choice has the additional advantage that, since the plaintext must be used as it is being recovered during decryption, this operation is identical to that one, so that the processes for encryption and decryption are the same.
As it turns out, Vigenère’s second cipher is exactly what I just described, using the ciphertext as it is produced to lengthen the key. Not very secure by itself (you’re giving away most of the key with the ciphertext), but in our case it’s going to help quite a bit. So, we end up using all of Vigenère’s ciphers: the two that he actually authored, and the one that he didn’t but ended up getting credit for anyway.
Snake uses a Tabula Recta to do the operations, and Worm is not going to be less in that regard. Like optionally in Snake, Worm will use a key-derived scrambled alphabet at the top and sides of the table, in order to add a substitution to plaintext and ciphertext with hardly any extra effort. This substitution, as it turns out (read this paper, for instance), would have made a straight Vigenère cipher a lot harder to crack. In addition, it makes the ciphertext non-malleable so that an attacker knowing the plaintext could not modify the ciphertext to decrypt to something else. Additionally, the substitution key can be different from the repeated key (which I am going to call “seed” from now on, and I’ll call the substitution key simply “key”), greatly increasing the key space available.
I have made a JavaScript version of the Worm cipher, which you can access at this link. Use it along with the example that follows.
Let’s say the plaintext to be encrypted is “attack at dawn” using “key” as key and seed. Obviously this is too short, but it will serve for the example. We do this:
- First we generate a scrambled alphabet by writing down each new letter in the key as it appears, and if a letter has already been used we take the first alphabet letter not yet used or the first available letter if the one in the key has been used already, and then the rest of the alphabet in reverse order. We get “KEYZXWVUTSRQPONMLJIHGFDCBA” and write it at the top, bottom, and sides of a standard Tabula Recta, to get this:
K E Y Z X W V U T S R Q P O N M L J I H G F D C B A --------------------------------------------------- K | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z | K E | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A | E Y | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B | Y Z | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C | Z X | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D | X W | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E | W V | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F | V U | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G | U T | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H | T S | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I | S R | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J | R Q | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K | Q P | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L | P O | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M | O N | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N | N M | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O | M L | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P | L J | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q | J I | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R | I H | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S | H G | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T | G F | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U | F D | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V | D C | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W | C B | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X | B A | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y | A --------------------------------------------------- K E Y Z X W V U T S R Q P O N M L J I H G F D C B A
- Then we make a table consisting of three rows, this way:
- First row is the plaintext with spaces and punctuation removed. If there are any numbers, convert them to letters using a predetermined encoding (for instance: 1 = A, 2 = B, etc.). We call this the processed plaintext. In our example, the processed plaintext is: ATTACKATDAWN
- We fill the second row with as many copies of the seed as necessary to reach the plaintext length. In our example: KEYKEYKEYKEY
- Finally, the third row will contain the ciphertext and so it’s empty for now. But we are going to fill the spaces under the first copy of the seed this way: take the plaintext letter (top row), look it up on the top, bottom, or sides of the Tabula Recta, and then follow that row or column until the corresponding seed letter (immediately below the plaintext letter) is found, then follow that column or row, switching direction from the previous, to read the ciphertext letter on one of the edges, or at top or bottom. For the example: A+K = Q, T+E = D, T+Y = L. Keep doing this until you have used all the seed letters once. So, in our example the table looks like this at this point (I’m separating the first group for clarity):
ATT ACKATDAWN KEY KEYKEYKEY QDL
- Each ciphertext letter (bottom row) after this is the result of a four-letter “snake” operation on the Tabula Recta, where one starts looking up the first letter at the top, then down to the second letter, then right or left to the third, then up or down to the fourth, and finally right or left to read the result on the sides. Alternatively, one can start at the sides and read the result at top, switching direction with each new letter. Draw the letters in this order: first is the plaintext letter (top row) above the spot to be filled; second, third, and fourth are the letters on the column one seed length left of the spot to be filled, read from top to bottom. Mark each column right after using it, so it is clear which is the next column to be used. So, for instance: A+A+K+Q = U, and we mark the first column with a dot at the bottom so we don’t use it again; C+T+E+D = F, and so on. We repeat this until the third row of the work table is as long as the others. This third row is the ciphertext (plaintext when decrypting):
ATT ACKATDAWN KEY KEYKEYKEY QDL UFVQFQUMU ... ......
To decrypt, our friend who knows the same key and seed will follow exactly the same steps, using the ciphertext instead of the plaintext, resulting in the original plaintext (ATTACKATDAWN) while making this work table:
QDL UFVQFQUMU
KEY KEYKEYKEY
ATT ACKATDAWN
... ......If we perform some statistical analysis on the ciphertext, we will immediately see that the Friedman’s index of coincidence (IC) of the ciphertext is close to 0.038, which is that of random text (English text has an IC of 0.066). The same and other tests performed on the “keystream” right before the plaintext is added (actually, subtracted) and the final substitution (done at the top of the table) reveal a keystream that passes almost all tests of randomness, including the very stringent chi-squared test on single letters and pairs of letters (more on the test that fails later on).
In terms of efficiency, it is hard to beat the final “snake sum” combination of four-letter columns. Making the work table is pretty fast, too, since it mostly involves copying down strings—plaintext, key, ciphertext—without additional processing. Making the key-derived alphabet is pretty quick too, but you must take care to avoid re-writing letters that are already in it. Crossing out the letters in a straight alphabet as you write down the scrambled one is a good way to make this operation fast and error-free. Still, it is possible to make an even faster cipher if we drop two of the letters and use only the direct autokey part, which in the end is the one that really contributes to the cipher’s strength. This is the “Visionnaire” cipher (because it is so close to the original one invented by Vigenère). I’m not describing it here because this article is getting kind of long already. But you can read all about it here.
Worm produces output similar to that made by Snake, while using a much shorter key (hence the Worm name). But is it secure, though? Leaving aside brute-force methods, insecurity would come from a ciphertext that can be told apart from random. Unfortunately for cryptanalysts trying to crack it, the ciphertext passes the tests quite well up to about 3000 letters. This is because it is the result of adding and subtracting three essentially uncorrelated pieces of text (plaintext, repeated key, ciphertext) plus a shifted plaintext. But the correlation between plaintext letters fades with separation, so if the key is five characters or longer it is as if we were adding four independent letters each time. Since there is a substitution built into entering the plaintext and retrieving the ciphertext, the fact that the first row closely resembles the plaintext does not mean that we are subtracting it out when the ciphertext is created, leaving the result of combining just the two bottom rows.
But what about brute force? If the key is short, a computer could perform trial decryptions for all the possible keys, and detect the correct decryption by its higher value of the IC. So don’t use a short key! Typically, a single word has about 13 bits of entropy. Five unrelated words will give you 60 bits, which is respectable but not an awful lot. If you want to get a strength comparable to that of a computer cipher (128 bits minimum), you will need ten words. That is, a single-word “password” won’t do (neither would for a computer cipher, but that’s a whole different discussion). The “key” I’ve been talking about is actually a multi-word “passphrase”. The longer, the better. If you want to defeat computers using huge dictionaries, make sure to misspell some of the words in some peculiar way. This is aided by the algorithm, which doesn’t give you much clue as to whether you are getting “close” with a given key guess, which is what you need to perform a “hill-climbing” attack. Here are the results of decrypting the sample ciphertext with some “close” keys:
Key plaintext obtained -------------------------------- key ATTACKATDAWN kez ATSACBATPAWA kex ATUACXATRAWZ kdy AYTAZKAVEATM jey BTTECJXTFCWL
As you can see, being off by a single letter in the key can produce a “plaintext” that looks like complete gibberish. For longer keys, this is even more so. Statistical analysis for longer texts confirms that the result of using a wrong key, especially as substitution key, produces statistically random results even if off by a single letter. This is a very desirable property, for it gives a cryptanalyst no clue as to whether he/she/it is getting closer to a solution, as guesses are made for the key. This precludes progressive search methods like the hill-climbing attack.
To have an idea of the enormity of the task, consider guessing the substitution key alone. This has 26! = 4E26 different possibilities. Guessing values until the correct one is found is like a blind golfer putting on a green as big as the orbit of Saturn. Here’s the calculation: the diameter of the green is sqrt(26!) = 2E16 times larger than that of the hole; if the hole is 6 inches across, the radius of the green is 3 x 2E16 = 6E16 inches, or 950 million miles. But even then, if there was a way to tell how far a guess is from being correct, the blind golfer would be putting on a green that funnels into the hole, if ever so slightly.
I have found that the chi-squared test of dependence for adjacent characters serves this purpose quite well for other ciphers, which would allow a computer to converge on the correct guess rather quickly. For Worm, the test of dependence for characters separated by the seed length is even more sensitive. This measure has a value below 670 for random strings made of the 26 Latin alphabet letters. For normal text, the value obtained is easily in the many thousands, and larger the longer the text is. A “funneling” green would be a situation where a wrong, but reasonably close guess of the key leads to a “plaintext” whose chi-squared test number is noticeably above 670. The situation would be even better for the cryptanalyst if that number bears a relationship with how good the guess is: larger for trial keys closer to the real key. How do they perform?
I’m happy to report that Worm performed well in my tests. The chi-squared test is very sensitive to the right length of the seed (highest value for the correct length in a trial decryption), but once this has been determined it offers little assistance to the cryptanalyst. The seed can be completely wrong, with the correct substitution key, and still give about the same value. Also, if the seed is correct but the key differs by just one letter, it settles into a range of values that might actually be higher than that for the correct decipherment but usually bears no correlation with the actual closeness to the correct key. All letters may be wrong and the chi-squared value still in the same range of values as for much closer guesses.
Unfortunately, Worm falls miserably under known-plaintext attack, as seen in this article. In fact, it does worse than any other cipher of its class presented on this blog because the seed can be deduced at the same time as the substitution key simply by solving a system of linear equations. Disguising the initial seed by prepending the plaintext with a string of random nulls does no good, since the seed keeps getting re-used and can be extracted from other pieces of ciphertext. To lessen the danger, you should avoid stereotyped beginnings and endings in the plaintext, as well as any kind of boilerplate text. Sprinkle the plaintext liberally with randomly placed nulls, for good measure.
Let me finish this article with a little extra gift, which is another Javascript program implementing the Worm cipher in base64 rather than base26 letters. Since files can be loaded on a browser as base64 blobs, this little program allow users to encrypt files quite efficiently, to be decrypted by those knowing the correct set of keys.