The Serpentacci ciphers

The picture on the left is a snake with the face of Leonardo the Pisa’s (a.k.a. Fibonacci). Have I gone crazy? Perhaps so, but here the image is an attempt to visualize the unholy offspring of a renowned mathematician of the XIII century and a XX century video game. Its name is Serpentacci, and it’s bound to give nightmares to many people in the security industry.

As I explained in this other article, the Fibonacci series is made by adding two terms of the series in order to get the next. If you only keep the last digit of the result, you will find that they have a tendency to randomness, especially if the numbers being added are not contiguous but separated by some distance. This is the basis of what is known as a “lagged Fibonacci generator” (LFG), which has found some use in computers. Now, not much is understood about LFGs; only that the resulting series tends to look quite random, with a few exceptions. This has limited their use in cryptography, along with the fact that the series doesn’t quite pass all randomness tests. For instance, the series will normally fail a test of independence of consecutive digits, if one of the numbers being added to get a third is the one obtained in the previous step. If we test for correlations of digits separated by a certain distance, then the test will fail for the distances between each of the numbers being added and the result.

But what if we involve more numbers in the calculation? Then the dependence is diluted, and may end up being undetectable. This is the basis of the Serpentacci ciphers: rather than a simple sum, do a “snake sum” involving several terms on a Tabula Recta, as described in this article and this other. “Snake “sums” (actually, chained differences, where the sign of the result switches with every added term) are quite easy to do graphically, so the work added over a simple sum is not a lot. Well, it turns out that just using four terms yields a result that almost passes as random, and using five takes away the “almost”, at the expense of a little extra complication.

Since the ciphers introduced in the articles linked above involve “snake sums” of four letters, I’m going to talk in this article about ciphers that involve an odd number of letters. If it involves three, so that the “snake” actually is more like a zig-zag, we are talking about the Zigzag cipher. If four, we have the Skink cipher. If it involves five, which is the minimum needed to make the cipher reversible (encryption and decryption are identical processes), we are talking about Serpentine. I have made a Javascript version of Zigzag, then another of Skink, and another of Serpentine, which you might find useful to follow the explanation below.

Now let’s do a Zigzag encryption using an example. Zigzag involves two alphabetic keys plus an alphabetic seed. The keys are converted into mixed alphabets, which control simple letter substitutions. The seed is used to initialize the process before the three-letter zig-zag operations begin. Keys and seed can be all the same, but they also can be different, for a truly enormous key space. For our example, let us use the following: key 1 = “wonderful”, key 2 = “counselor”, seed = “marvelous” (this is from Handel’s “Messiah,” in case you were wondering). And let the secret message be: “we are discovered, flee at once.” These are the steps for encryption:

1. Make a mixed alphabet from each of the two keys, plus their negative forms, and place them surrounding a standard Tabula Recta. To make a mixed alphabet from  a key, write down every new letter as you find it in the key; if a key letter has appeared before, write instead the first letter in the alphabet that has not yet been written; after reading all the letters in the key, write the rest of the alphabet in reverse order. Thus from “wonderful” we obtain “WONDERFULZYXVTSQPMKJIHGCBA” (no letter repeats), and from “counselor” we obtain “COUNSELARZYXWVTQPMKJIHGFDB” (“O” appears twice in the key, so the second time we write “A” instead). Once we have obtained a mixed alphabet, we make its negative version this way: write the first letter, then write to its right the rest of the letters in reverse order. Therefore, the negative version of the first alphabet is “WABCGHIJKMPQSTVXYZLUFREDNO” and the negative version of the second is “CBDFGHIJKMPQTVWXYZRALESNUO”. Then we place those on the edges of a conventional Tabula Recta, this way: top: 1st alphabet, left: 2nd alphabet, right: 1st negative alphabet, bottom: 2nd negative alphabet. This is what we obtain in our example:

   W O N D E R F U L Z Y X V T S Q P M K J I H G C B A
   ---------------------------------------------------
   C | 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 | W
   O | 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 | A
   U | 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 | B
   N | 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 | C
   S | 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 | G
   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 E | H
   L | 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 | I
   A | 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 | J
   R | 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 | K
   Z | 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 | M
   Y | 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 | P
   X | 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
   W | 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 | S
   V | 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 | T
   T | 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 | V
   Q | 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 | X
   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 P | Y
   M | 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 | Z
   K | 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 | L
   J | 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 | U
   I | 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 | F
   H | 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 | R
   G | 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 | E
   F | 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 | D
   D | 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 | N
   B | 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 | O
   ---------------------------------------------------
   C B D F G H I J K M P Q T V W X Y Z R A L E S N U O
   

2. Next we process the plaintext so that only letters are left. This involves removing spaces, punctuation, and accents of several kinds, and converting digits to letters according to a prearranged code (such as 1 = A, 2 = B, and so on, it doesn’t matter what). Optionally, we can further strengthen the cipher by prepending a number of gibberish characters equal to the seed length. Since the seed “marvelous” has 9 letters, we’ll put 9 random letters at the start (it doesn’t matter what). Result: “WWONEIYYT WEAREDISCOVEREDFLEEATONCE”.
3. Now the initial phase of the encryption. Write the seed above the processed plaintext and do this on the Tabula Recta for each letter of the plaintext until all seed letters have been used: Look up the plaintext letter on the top of the Tabula Recta, go down that column until the seed letter is found, then left to the edge and write down the letter you find there under the plaintext letter. For instance: W + M = W, W + A = C, O + R = P. In the end, we have started making a work table, which at this point looks like this:

   MARVELOUS                          
   WWONEIYYT WEAREDISCOVEREDFLEEATONCE
   WCPJCMSYE                          
   

4. And now the main phase of the encryption, using zig-zag operations involving three letters each. We are going to fill the spaces below each plaintext letter this way: take the plaintext letter above the spot to be filled and look it up at the top of the Tabula Recta (“W”), then go down until you find the first plaintext letter not yet used in this phase (“W”, all the way to the left), then right or left until you find the plaintext letter that follows that one (“W” once again, so we don’t move), finally go down to read the ciphertext letter at the bottom (“C”) and write it down in its spot, then mark the position of the second letter you used so you don’t use it again. Keep doing this until the bottom row is filled. Thus, W + W + W = C, E + W + O = S, A + O + N = U, and so on. In the end, this is the way the work table looks, including dots added to mark second-letter positions that have been used:

   MARVELOUS                          
   WWONEIYYT WEAREDISCOVEREDFLEEATONCE
   WCPJCMSYE CSUSKALMCMKERFKYRYQKCWBOP
   ......... ................         
   

The bottom row is the ciphertext, which you can send out through insecure channels: “WCPJCMSYECSUSKALMCMKERFKYRYQKCWBOP”.

Decryption is quite similar, though not identical. The first two steps are the same, except that we do not add any gibberish letters in step 2. In step 3, we write the ciphertext, not the plaintext, immediately below the seed. And then, we look up ciphertext letters on the left side, not the top, and read them at the top. This is our work table after step 3:

MARVELOUS                          
WCPJCMSYE CSUSKALMCMKERFKYRYQKCWBOP
WWONEIYYT                          

The zig-zag operations in step 4 are also similar, but we take plaintext letters (bottom row) rather than ciphertext letters (second row) for letters 2 and 3 in each zig-zag operation, and we start on the left side and read the result of the operation at the bottom. Thus, C + W + W = W, S + W + O = E, U + O + N = A, and so on. In the end the work table, including markers, looks like this:

MARVELOUS                          
WCPJCMSYE CSUSKALMCMKERFKYRYQKCWBOP
WWONEIYYT WEAREDISCOVEREDFLEEATONCE
......... ................         

Since we know that the first nine letters are nulls (because the seed has nine letters), we strip them now from the beginning of the bottom row, to read the original processed plaintext: “WEAREDISCOVEREDFLEEATONCE”.

The reason why we need “negative” alphabets at bottom and right is that every leg of a zig-zag operation is actually a base26 subtraction modulo 26, and the sign of the result changes with every leg. Since there are three legs, the result is negative (modulo 26), and we need to change its sign. This is accomplished by using a “negative” alphabet constructed as described, which changes the sign of the result at the same time as the substitution takes place.

Serpentine is almost the same as Zigzag, except that the operations in step 3 involve five letters, namely: 1, the letter above the spot we want to fill; 2, the letter on the same row, a number of spaces to the left equal to the seed length; 3, the letter immediately to the right from letter 2; 4, the letter immediately below letter 2, on the bottom row; and 5, the letter immediately to the right of letter 4. The pattern is identical for encryption and decryption, and so the Javascript program for this cipher uses the same mixed alphabet on top and left side of the Tabula Recta (bottom and right are the negative version of that one). This cipher obviously takes more effort that Zigzag, but it is simplified by being reciprocal (only one alphabet to deal with), and produces output that passes all tests of randomness with flying colors. Because of this, I’ve chosen it to serve as the basis of a program, which I call the Fileine cipher, which applies the algorithm to the base64 blobs of any file. You can find Fileine here. If you don’t care so much for the reciprocal property but wish to have a bigger key space, simply use different mixed alphabets for top and sides, as in Zigzag, and then apply them in reverse order for encryption and decryption.

A skink is a lizard, some species of which are legless and might be easily mistaken for a snake. Like the Snake cipher, Skink involves four letters in each operation after an initiation phase identical to those of Zigzag and Serpentine. Because it involves an even number of letters there is no need to place negative versions of the mixed alphabets at the output locations, which simplifies the process a little bit. Like Zigzag and unlike Serpentine, encryption and decryption are different. The four letters involved in encryption are: 1, the letter above the spot we want to fill; 2, the letter on the same row, a number of spaces to the left equal to the seed length; 3, the letter immediately to the right from letter 2; 4, the letter immediately below letter 2, on the bottom row. For decryption, letters 2 and 3 are from the bottom row (plaintext) and letter 4 is from the top row (ciphertext). Its base64 version for files, is called FileSkink. You can find FileSkink here.

After having introduced all of these ciphers, the question is: which one to use? Clearly if you want to encrypt files the winner is Fileine, since it produces output that is almost always nearly indistinguishable from random, and you are not going to be doing it by hand anyway. If you want to encrypt text by hand, however, the answer is not so clear-cut. Ciphers involving more letters in each operation produce output that is closer to pure random, and is therefore harder to crack, but they also take more effort. Some of them (odd number of letters in each operation) require negative alphabets to me used for the output, which takes some (small) extra effort. In order to ascertain which one would be the best, I have made a text in which I encrypt a relatively short (5th paragraph, 202 letters), and a longer piece of text(whole chapter, 17301 letters), both taken from the 2nd chapter of Dickens’s “Oliver Twist” using the same key and seed “wonderful” in all cases. The JavaScript programs return some statistical properties, which among which is the chi-squared statistic of the cipherstream, which can be be considered random with a 90% assurance if the statistic falls below 34.4. Here are the results as a table:

You can see that the result is acceptable with all ciphers for a relatively short message, but when we encrypt a long one we need to involve a minimum of 4 letters per operation. Visionnaire begins to fail the test consistently for messages around 280 characters long, Zigzag for 1400 characters. The other three remain solid for messages up to 100,000 characters, but Skink begins to show a high level of two-letter chi-squared statistic (when the letters are separated by seed distance) when the plaintext is merely 3000 letters long, while Worm and Serpentine remain within bounds in this respect, too. This, together with a method that is both reciprocal (though it can be easily modified to use two keys rather than one, and then it won’t be reciprocal) and less likely to lead to confusion (letters involved in an operation form a column in the working table), recommend the Worm cipher for long plaintexts. More on Worm can be found at this article.

Security? All of these ciphers are highly resistant to ciphertext-only attacks (especially those involving more letters per operation) because the resulting ciphertext looks so much like random text. Also, a trial decryption with a key that is wrong in a single character yields random gibberish, so it is not possible to mount a hill-climbing attack, for instance. But unfortunately all of these ciphers collapse under a known-plaintext attack, as this article explains. The reason is that the ciphertext is a linear combination of other pieces, and it is simple to set up a system of linear equations to find all the values involved in the substitutions. To lessen the impact, users should avoid stereotyped beginnings and endings on the plaintext as well as any boilerplate text. Sprinkle the plaintext with randomly-located nulls, including a whole string of them at the start, equal in length to the seed.