High-security low-tech ciphers compared

Not a totally unlikely scenario: you need to send some extremely sensitive information to someone, using email or whatnot, and you suspect that your phone, your computer, and all electronic devices around you have been bugged. The only thing you have is paper, pencil, maybe some stone as in the picture, and your brains. Some people would prefer that everything is done in your head, but I will presume that you can burn the paper where you did your work afterwards, leaving no traces (hard to do with stone, though). There are a few admittedly low-tech symmetric ciphers that claim to work well in this situation, producing ciphertext that even the NSA would have trouble cracking. I go first over desirable features, then look at the different ciphers and what they have to offer, and conclude with some scores and comparison between them. Nothing prevented their having been invented centuries ago and, had they been available back then the history of the world might have turned out quite different.

So let’s start with the desirable features of this kind of cipher. A few come to mind right away:

1. Resistance against ciphertext-only attack, meaning that finding the plaintext by some other method must be as computationally expensive as trying every possible key until the good one is found.
2. Resistance against known- or chosen-plaintext attack, so that finding the key by some other method is as expensive as trying every possible key.
3. Simplicity, so that not too many steps are involved. A related property is reversibility: encryption and decryption are the same method, so the user only needs to remember one set of instructions.
4. Speed, meaning that a person can encrypt a given plaintext in a short time. This is related to simplicity but is not the same, since not all operations take the same time.
5. Key space size. The larger the space of possible keys, the longer a brute-force attack will take.

And then, there are some other desirable traits that are not so obvious. For instance:

1. Ciphertext randomness. The more random the ciphertext appears to be, the harder to identify the method used, which makes it more secure in practice. This also makes it more effective to chain methods in order to achieve greater security.
2. Wrong plaintext randomness. It should not be possible to tell whether a key guess is “close” to the correct key, because then the attacker could guess the key gradually. In practice, this means that the statistical properties of the “plaintext” obtained from a wrong key should not change much as the key changes, especially if it is close to the correct key. Related to the trait described above.
3. Key reusability. If one can use the same key for many messages without creating a weakness, so much the better. An alternative is adding a serial, which gets transmitted in plaintext, which makes it possible to reuse the main key.
4. Multiplicity. This means that the same plaintext can be encrypted as several, perhaps many, different ciphertexts while using the same key.
5. Non-malleability. An attacker who does not know the key should not be able to change the ciphertext so it decrypts to a plaintext of their choosing.
6. Simple key maintenance. Some ciphers rely on keys that are hard to set up and protect from corruption, such as the state of a shuffled deck of cards. Better still if the key can be memorized.
7. Resistance to error. If a mistake is made in processing, this does not corrupt the whole message or, even better, only certain parts of the message are corrupted.
8. Resistance to lazy operator. If steps are skipped while encrypting, the result should be undecipherable so that lazy operators are not rewarded for compromising security. Probably not an issue for ciphers meant for personal use, but important in situations where several people are using the same keys.
9. Mutability. This property means that the method admits several variations of comparable security, which might or might not be known to the attacker. This would make it very hard to attack, since one always assumes that the method itself, though not the key, is known to the attacker.

Of course, not all properties listed have equal importance. Resistance against a ciphertext-only attack is paramount, but it can be further decomposed as properties on the second list. Speed and simplicity are very important too, for otherwise people won’t use the cipher. Resistance to error is important because no machines are supposed to be involved, which means errors. This is related to simplicity: the more steps, the greater opportunity for error. I have attempted to weigh these properties in a reasonable matter when I made the table below. You may disagree with these weights, but then you can re-calculate the results using weights more of your liking.

A couple notes before introducing the contestants. The first is that only symmetric ciphers are considered. I don’t know of any asymmetric ciphers that can be done by hand and give decent security. Second: I am not considering one-time pads and their variants. These are a category apart, for two reasons:

1. They are mathematically impossible to crack. If they are, it’s due to errors in their implementation, which I don’t wish to go over in this article. I will assume, therefore, that all the ciphers are implemented correctly, with a single score given to how easy it is to do so.
2. Their keys are exceptionally hard to exchange, and their mere possession can be quite incriminating. Therefore, we will be assuming that keys are relatively short and can be exchanged in a casual encounter and, perhaps, kept in memory rather than physical form.

Ladies and gentlemen, here are the contestants for this comparison: Bruce Schneier’s Solitaire, a 26-letter version of the RC4 algorithm, the Aguilar cipher (3 or 6 transpositions), the classic VIC cipher used during the Cold War, Handy Cipher by Bruce Kallick, Chaocipher by John F. Byrne, and my own SuperSkink, Scrabble, and FibonaRNG ciphers. Let’s take a look at them one by one (links are on the titles):

Solitaire (a.k.a. Pontifex)

This cipher was first published as an appendix to the novel “Cryptonomicon”, by Neal Stephenson. In the novel, it takes the name Pontifex, and is used by some characters to communicate while in jail. It is a stream cipher that uses a French card deck, containing 52 numbered cards plus two Jokers, to generate a base26 keystream that that is added to the plaintext (or maybe subtracted from it, so the process is reversible). It has been looked at by experts, who have uncovered significant bias in the supposedly random output of the keystream generation algorithm, but this flaw is only of concern for long messages so I will give Solitaire a full security score. It is however, a very slow process involving counting of cards, so that one can produce about one keystream character per minute. Additionally, the deck must be scrupulously kept in sync on both ends of the encryption, or further communication is impossible; no way to go back if a mistake is made.

Like all stream ciphers, Solitaire must use a new key for each new message, or both the old and the new messages would be easy prey to an attacker. The key consists of the state of a shuffled deck, which is hard to describe simply and about impossible to memorize. It does have, however, a significant key space of size 26!*26*26 = 2.7E29, corresponding to about 98 binary bits (only two suits are used, rather than four).

RC4 (Shevek’s or Mindflare’s version)

In some very recent posts, people have taken the RC4 stream cipher, originally designed to work with a 256-bit “alphabet” and have modified it so it uses the regular  26-letter English alphabet. The result is a stream cipher with an excellent track record, if the qualities of RC4 translate with the conversion. Once you get to the algorithm itself, it looks a lot like a simplification of Solitaire, which makes me suspect that it might share its undesirable bias. In essence, a mixed alphabet containing all 26 character is used as key, and this is shifted through a few simple operations, after which a single pseudo-random character is produced as output. Like Solitaire, RC4 is a stream cipher and must use a new key for each new message, The key space is slightly smaller than Solitaire’s, since the pointers (the Jokers, in Solitaire) always start at the beginning, leading to a total of 26! possibilities, which is about 88.7 binary bits.

Aguilar cipher

This cipher has three-stage and six-stage versions that are conceptually quite similar. The plaintext is written down by rows in a special form containing blanked-out spaces, and is read out by consecutive columns, sometimes after the letters have been subtracted modulo 26 from the key. The ciphers uses one 43-character “mixed alphabet” as permanent key, and a similar one as initialization vector, which is transmitted with the ciphertext. The permanent key is meant to be random-looking and written on a strip of paper so it can be easily swallowed in case of need. The size of the key space is, therefore, 43! = 6E52, or 176 binary bits, which is quite respectable.

The Aguilar cipher consists essentially of straight unkeyed transpositions that are quite easy to reverse, though sometimes the key or the initialization vector are subtracted mod 43, as many times as necessary to complete multiples of 43 characters. This is quite similar to the standard Vigenère cipher, which today is well known to be insecure. Because of this, I am reducing its security score to about half of the maximum. Speed is better than the previous two, but not stellar because of the relatively large number of steps required. These steps are different from each other, which is less than ideal from the simplicity viewpoint. In addition, the cipher needs special forms, which could not have other uses. A good feature, however, is that the key can be reused, especially since the random initialization vector is changed for each message. Mutability is assured by using forms with different patterns of blocked-out cells.

VIC cipher

This cipher was in use by Soviet spies during the Cold War. Even though it is a classical cipher, it defied all of the US intelligence agencies’ attacks until it was revealed by a defector. It is, however, quite complicated, involving several steps of key-stretching by way of a not particularly secure lagged Fibonacci generator plus a couple transpositions, one of them of the disrupted type. It security lay especially in that the method was not known by the intelligence agencies until it was revealed. The keys used in the cipher were short, so that its key space is also small.

Handy cipher

From the description of the cipher, we know that it is a stream cipher, with all their advantages and disadvantages, and that its key space is of size 31! or 113 bits. It does include a homophonic nomenclator with 3045 entries, but this is likely to remain fixed so it does not constitute key material (though it adds some mutability if those are changed). The encryption process is quite complicated, partly due to the fact that two different messages can be encrypted at the same time, under two separate keys. Being a stream cipher keys cannot be reused, and there is no allowance for initialization vectors that might make this somewhat better. Apparently no one has studied its security in a serious way, but the definition paper includes some theoretical attacks. It states that the security of the cipher against hill-climbing attacks depends on the randomness of nulls that are supposed to be inserted at various times in the process. Therefore, I am giving it a high but less than perfect score in the security area.

Chaocipher

This was invented by John Byrne in 1918 and kept secret until 2010, 50 years beyond Byrne’s death. The description that has come down to us involves two wheels with the alphabet around them, the letters placed in such a way that they can be switched by pairs. One wheel contains the alphabet used for the plaintext, the other for the ciphertext. Users look up each letter on one wheel, then read off the ciphertext letter on the other wheel, and then both wheels are rotated and two letters switched according to a fixed pattern. Byrne’s working prototype, if it did exist, has not survived to be analyzed, but the underlying cipher gleaned from the papers is quite strong and relatively simple. It is, however, vulnerable to a known plaintext attack, unless some simple precautions are used. Keyspace size is claimed to be 26!ˆ2 = 1.62E53, or 177 binary bits, but analysis reveals that the key encoded in one of the wheels adds hardly any security, so it is more like 26! 0r 88.7 bits.

Super Skink

This is one of my ciphers based on “snake” operations on a Tabula Recta, plus a regular substitution after that in order to combat a known plaintext attack. The snake operations involve four letters: three from the plaintext and one from the ciphertext, with most of the effort being invested in looking up those letters as they are entered, which is quite fast in any case. It uses two substitution keys plus a transposition key for a maximum key space of size 26!^3, equivalent to 266 binary bits. It can be done on a piece of paper with a standard Tabula Recta printed on it.

Scrabble

This is also mine, deriving from Byrne’s Chaocipher but greatly simplified so that you only need a set of two alphabets made of letter tiles. Unlike Super Skink, Scrabble can be made impervious to known plaintext attacks without the transposition step simply by prepending a number of random characters to the true plaintext prior to encryption, so it’s a one-step cipher. In this configuration, the key space is a smallish 26!, or 88.7 bits, which becomes twice that if a transposition is added. This cipher involves very little mental effort, but it does require a set of alphabet tiles to be executed properly, which lets Super Skink take the lead in this survey.

FibonaRNG

My most recent paper-and-pencil cipher, it is based on a lagged Fibonacci pseudo-random number generator rather than on the entropy of the plaintext itself, which makes it more suitable for low-entropy plaintexts, like lists of numbers or even files. It has a basic computational complexity similar to that of Skink (Super Skink minus the transposition) since it does not need a transposition step in order to avert a known plaintext attack, which ends up making it simpler. It is simply amazing that this works at all. The key space is a respectable 26!^2*26^n, where n is the length of the seed. Like Super Skink, it does not need any props beyond a Tabula Recta, which can be made up by hand if necessary.

And here is the summary of all scores:

Unsurprisingly, my own ciphers come up on top 😉 They do so well because they have been designed with all of the above requirements in mind. Maybe you can come up with a different list of requirements where a different cipher will do better (human-computable only, of course). FibonaRNG comes out as clear winner, but in a fairly quiet situation where you have been able to procure yourself a set of letter tiles (two complete alphabets), Scrabble may be just as good because it requires less mental effort, although its key space is not so large. You can always increase the key space by adding transpositions.