Aphid cipher

Aphids are those pesky green bugs that eat the plants in your garden. But here the name designates a high-security paper-and-pencil cipher similar to Restonia, based on a couple ciphers that are more than a hundred years old.

Aphid derives from the “bifid” cipher invented by Philip Delastelle in 1895, to which it adds an extended columnar transposition step. Bifid was never used in practice despite its excellent properties, but its inner design influenced cryptography in a profound way, so that today’s computer-based symmetric encryption algorithms are a longer, more complex implementation of the same basic ideas: fractionation and diffusion. Fractionation means that every plaintext character is broken apart into several pieces, and diffusion means that the pieces are sent to different spots on the ciphertext, where they might be recombined into something else. Unfortunately, the original bifid cipher was easy to break because the plaintext pieces were sent to predictable locations, which makes it possible to reconstruct the original before encoding, at which point it can be solved like any monoalphabetic cipher. Like all ciphers devised before the computer age, bifid also suffered from short keys, liable to be found by exhaustive brute-force trial of all possible combinations.

Another classical cipher in Aphid’s family is ADFGX, which actually saw use during World War I on behalf of the German army. This cipher also used a 5×5 Polybius square for its substitution step, and then it had a simple columnar transposition. ADFGX was soon broken, however, because a single transposition does not really obscure the plaintext very much. We know now that just a double transposition is much better. In addition, there was no recombination of the 2 parts made from each plaintext letters, which wasted much of the potential of fractionation. Still, cryptanalysts were only able to break it on days of great traffic, when operators got overwhelmed and began reusing keys for a large number of messages, some of them with stereotyped contents known to the Allies.

In order to strengthen bifid and ADFGX into a derivative that can resist modern computer-aided cryptanalysis, we are going to follow a similar approach as in the Restonia cipher, where transposition based on a long passphrase is combined with substitution into digits based on a straddling checkerboard. The main difference between Aphid and Restonia is that Aphid uses a “Polybius square” substitution rather than a straddling checkerboard, and that the encoded result is converted back to letters at the end of the whole process. To illustrate the instructions, we will encipher “MEET ME AT THE STATION MONDAY AT 5 PM” using the passphrase “secret code” (too short, but will serve for illustration purposes) as the serial “ABC”. These are the steps, which perhaps you can follow better if you also look at this JavaScript implementation of aphid:

1. Serial code (optional). In order to prevent multiple anagramming attacks, which are possible when two messages of the same length are encrypted with the same key, it is a good practice to use a different serial code for each message. The length of the serial code depends on how many messages will be exchanged. Three characters are good enough for a few hundred messages. For our example, we will use “ABC” as serial.
2. Code generation. Two codes are made from the passphrase and the serial: one for encoding the plaintext by substitution, and the other for scrambling the encoded result. The easiest to make is the scrambling code: just number each word in the serial + passphrase, according to their order in the dictionary; if a letter is repeated, begin from the right (for better scrambling). If a word contains less than four letters, which would lead to insufficient scrambling, merge it with the next one before finding the order. For the serial + passphrase “ABC” + “secret code” = “abcsecret code”, this results in: “124863759,1423”. The encoding table is made into a 5×5 “Polybius square”, which contains the letters of the alphabet (J is combined with I). We fill it this way: Take the passphrase and place each new letter you find, in sequence, on the first row beginning from the left, and continuing on the other rows as needed. This is the first partial table in our example :

Now fill the table with the rest of the dictionary in reverse order, for better security. This is the result:

To ease the encoding of long messages, this can also be expressed as an alphabet, with the coordinates for each (table,row,column) written below each letter:

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

5 5 1 2 1 5 5 5 4 4 4 4 4 4 2 3 3 1 1 1 3 3 3 2 2 2

5 4 3 2 2 3 2 1 5 5 4 3 2 1 1 5 4 4 1 5 3 2 1 5 4 3

One last remark is that the cipher will be stronger if instead of one we use two different encoding tables: one for encoding the text into figures in step 3, and the other for decoding the figures back into text in step 5. The second table can come from a second passphrase for best security, although it can come from the same, drawing the letters in different order.

3. Encoding. Now we convert our plaintext into a numerical code. Below each plaintext letter we write vertically the two-digit code for each letter. In order to write numerals, we’ll write “X”, followed by two digits for each figure according to the following table (in the text, we’ll write “X” as “CS” or similar), and the code “55” at the end of the digits. The rest of the codes can be used for punctuation signs, etc.:

Here’s the result of encoding:

MEET ME AT THE STATION MONDAY AT X5end PM

4111 41 51 151 1151424 424252 51 215   34

2225 22 55 512 1555511 211254 55 455   52

If we want the final result to be a certain length—perhaps in order to disguise it as something else—this is the place to add as many gibberish pairs as needed, usually at the end of the text.

4. Scrambling. The numerical code is now scrambled with each code we obtained earlier. To do this, we first write the first scrambling code, and then underneath it we write left to right by rows the code we just obtained in the previous step, starting from the first row, then the second row, then the third. Then we read the scrambled code vertically, beginning with the column marked as “1”, then “2” and so on until the end. Then we scramble the result in the same way with the second scrambling code, and so on until there are no more scrambling codes. For our example, we obtain these two tables, whre the top row in both cases is the scrambling code:

Result read off by columns in the given sequence: 4541254 1125555 1122215 1143515 1215522 4552125 5452115 1124514 142255

Result read off by columns in the given sequence: 4215253155255415 445121112251112 115114554141242 5525215225521545

5. Decoding. We write this code into two rows of equal length, filling one row at a time, and find the corresponding letters in the Polybius square by reading from top to bottom, taking the upper figure as row and the lower figure as column. This is the result (here we leave numerical shifts alone, if encountered, without trying to shift into numbers and special characters):

4 2 1 5 2 5 3 1 5 5 2 5 5 4 1 5 4 4 5 1 2 1 1 1 2 2 5 1 1 1 2

1 1 5 1 1 4 5 5 4 1 4 1 2 4 2 5 5 2 5 2 1 5 2 2 5 5 2 1 5 4 5

N O T H O B P T B H Y H G K E A I M G E O T E E X X G S T R X

So the final result, which we can transmit by insecure channels, is this preceded by the serial:

ABCNO THOBP TBHYH GKEAI MGEOT EEXXG STRX

Decryption is roughly the reverse of encryption. This way:

1. Retrieve the serial (if any) from the beginning of the ciphertext.
2. Code generation. This step is identical to step 2 for encryption, starting from the serial and the passphrase.
3. Encoding. This is the reverse of encryption step 5. We find the 2-digit codes for each letter in the ciphertext and write it in two rows underneath, then we read it off by rows, to be descrambled in the next step. if two different encoding tables are used, this step involves the second one.
4. Descrambling. This is the reverse of encryption step 4. We begin making a table for the last scrambling code, with as many columns as digits in the code. The number of rows is the numerical ciphertext length divided by the code length, rounded up. The remainder of the division tells us how many cells in the last row should be blanked out. Then write the ciphertext numbers from top to bottom, starting on column 1, then 2, and so forth, filling all active cells in each column. The resulting table should be identical to the last scrambling table made when encrypting, but this time the result will be read off horizontally from the top, left to right. Then the result will be written in columns on a table made for the second-last scrambling code, and so on until the first scrambling code is used. The final result read by rows is the encoded plaintext, which we divide into two equal rows.
5. Decoding. Now take the encoded plaintext and decode it back to letters (and numbers, if any) where the top number is the row and the bottom number the column in the Polybius square, thus reversing encryption step 3. If two different encoding tables are used, this step involves the first one.

This cipher shares many features with the Restonia cipher, but in a different way. Fractionation and diffusion are better because every plaintext letter gets split into two pieces, and the pieces are sent to distant spots within the ciphertext where they recombine to form letters that are most likely different from those in the plaintext. Aphid doesn’t take into account expected plaintext frequencies as Restonia does, but the combination of fractionation and scrambling is very effective to destroy language-derived statistics present in the plaintext, although not completely. All the properties having to do with the scrambling are the same as for Restonia, and there are two additional column to row shuffles (one when encoding to numbers, and one when decoding back to text), which come for free with the Polybius encoding. Fractionation can be made even stronger by using a 3x3x3 “Polybius cube” rather than the 5×5 square, and using three-digit codes for all letters. This is what Delastelle’s “trifid” cipher, an evolution of bifid, did back then. The problem is that, having only three different values for the encoded digits, we end up with long, tedious repetitions, and the likelihood of mistakes becomes much greater.

Unlike with the Restonia cipher, the last decoding step is necessary in order to collect the diffusion effect and transform each plaintext letter into two different letters in the ciphertext. Because of this, Aphid encryption and decryption takes a little longer than Restonia, but its theoretical strength is greater due to the more complete diffusion of the plaintext, especially when using two different tables for the initial encoding and the final decoding. Check it out and compare it with Restonia, and see which one you like better. I use Aphid when I want the end result to be letters, Restonia when I want it to be numerals.

Just about everything said about attacking the Restonia cipher can be said about Aphid. The main difficulty lies in having to descramble a code whose alphabetic conversion isn’t known. The ciphertext before conversion back to letters contains very few different characters, so that any type of frequency analysis is bound to fail. Frequency analysis would be effective once those have been (correctly) encoded as letters, but this cannot be done before the number codes are descrambled. Anagramming will fail form the same reason: there’s too few different numerical characters to be able to eliminate unlikely solutions. Many grammatically correct solutions are possible for a given ciphertext if one only has to descramble the figures and convert them back to letters. For a typical five-word passphrase (around 60 bits of entropy), the “unicity distance” for English plaintext is 60/3.5 = 17.1. This means that a ciphertext consisting of 17 or fewer characters would be theoretically impossible to crack, no matter how much computational effort is put into it. Which doesn’t mean that longer texts would be easy to crack, either.

The classical method used to crack ADFGX won’t work with Aphid for two reasons: 1, there will normally be more than one scrambling step, which is way better than one, and 2, the final decoding back to letters effectively obfuscates any language-dependent frequency that might have remained, which was needed in order to break ADFGX. In this regard, Restonia still suffers from this weakness, which is only patched up (quite effectively, though) by the fact that the straddling checkerboard used in the initial substitution messes up the most important letter frequencies.

How about using methods for attacking Delastelle’s bifid cipher? In essence, the conventional attack tries first to determine the “period” of the cipher (bifid converts columns to rows by blocks of a certain size) by evaluating certain statistics on the ciphertext. When the period is known, descrambling of the blocks can be done immediately, and then what is left is a digraphic substitution involving a single alphabet, which is readily solved by standard frequency analysis. But this will not work for Aphid because the blocks are not predictably scrambled and, in fact, the whole text is a single block. The closest thing to a “period” to be determined is the number of columns of each scrambling step, and there are several of them all mixed together. Unless the passphrase was very badly chosen, the Aphid “period”, resulting from all the scrambling steps, will likely be longer than the ciphertext length.

I believe Aphid and Restonia are actually stronger than the famous Enigma code, which the Germans used during World War II and was the first routinely cracked with the help of the first digital computers. It was quite an epic effort, nicely rendered in the 2014 film “The Imitation Game.” Enigma was essentially a stream cipher based on a mechanical pseudo-random number generating machine. Aphid and Restonia are block ciphers operating on the full message length. Even today’s digital block ciphers, such as AES, don’t operate on full-message blocks, but on fixed-length blocks, and they use fixed substitution and permutation operations, while in Restonia and Aphid, they are key-dependent.

Their superior resistance to cryptanalysis of modern ciphers lies in the fact that another substitution is made before each permutation, and several “rounds” including a substitution and a permutation are performed before the final ciphertext is produced. As a result, each character in the plaintext ends up influencing every character in the ciphertext, in ways that depend nonlinearly on the key. Aphid is meant to be simple enough to do with pencil and paper, so that the number of operations is reduced to the minimum necessary while providing as much diffusion as possible, which is two positions per character. Its superior strength relative to bifid and other classic ciphers lies primarily in its ability to use arbitrarily long keys, having a much larger entropy, so it stands a chance against computer-aided cryptanalysis.