What's the point?

Every once in a while, I see someone asking "what's the strongest pen-and-paper cipher?" or "are there any strong hand ciphers?". Before, all that was really available was Bruce Schneier's Solitaire. Now, there's a second strong pen-and-paper cipher: Sarah2.

How do I use this?

S-box

First, you'll need to make an S-box. Sarah2 uses a 27x27 (729 entry) S-box. This S-box (which you can see an example of above) consists all the pairings of letters from aa to zz, including underscores. The easiest way to do this is to use a computer, and simply shuffle all the entries randomly. If you don't have a computer, some kind of random number generator would probably work. This S-box is your secret key, and needs to be shared with whoever would receive your encrypted messages.

Encrypting: Alphabet and padding

Sarah2 only supports the letters a-z, and the underscore character. You can use underscore as a word separator, but it's just a lot more obvious to look at than a space character. Any other characters are discarded, or can be spelled out (like numbers). If your message's length isn't divisible by 2, add an underscore at the end to make it divisible by 2.

Encrypting: Substitution

The first step to encrypting with Sarah2 is substitution. Take each pair of letters in the plaintext, and look them up in the S-box. The first letter is the row, and the second letter is the column. Then replace those two letters with the letters from the S-box. Do this for every pair of letters in the plaintext.

Encrypting: Shuffling (Permutation)

The second step of Sarah2 is shuffling (also known as permutation). To shuffle, take every other letter (the odd-numbered letters: 1, 3, 5, etc.) in the plaintext and move them to the left. Then take the remaining letters (the even-numbered letters: 2, 4, 6) and move them to the right. For example:

        1 2 3 4 5 6 7 8  or  a b c d e f g h
        1 3 5 7 2 4 6 8      a c e g b d f h
      

Encrypting: Number of rounds

Now that you know how to substitute, and how to permute... that's it! Just keep applying those two steps over and over until the plaintext is thoroughly mixed. When you get to the "last round", there's no need to do a final shuffle step, because it's trivial to unshuffle those letters, so that step can be omitted. My recommendation for how many rounds is (n is the number of letters in the message to be encrypted):

  1. log2n rounds: "I'm only encrypting a handful of messages, and adversaries will never get a chance to make me encrypt anything they choose."
  2. log2n+2 rounds: "I'm encrypting tons of messages, but adversaries will still probably not get a chance to make me encrypt anything they choose."
  3. 2 x log2n rounds: "My adversary can encrypt and decrypt things using my key, but they don't know the key." My expectation is that this provides a fairly strong level of security, even against attacks involving a fair amount of computational power.
So, for a 14 character message, we round up to 16 (the next highest power of 2), take the log2 of that (4), and then do 8 rounds of encryption.

Estimated time

How long does this take? Well, if we estimate 2 seconds per lookup, encrypting the sample test message: attack_at_dawn takes about 2-3 minutes, not bad.

Why is this maybe secure?

Confusion

To quote the great Wikipedia:

Confusion means that each binary digit (bit) [letters in Sarah2's case] of the ciphertext should depend on several parts of the key, obscuring the connections between the two. The property of confusion hides the relationship between the ciphertext and the key. This property makes it difficult to find the key from the ciphertext and if a single bit in a key is changed, most or all the bits in the ciphertext will be changed. Confusion increases ambiguity of ciphertext and it is used by both block and stream ciphers.
In the case of Sarah2, we create confusion by substituting pairs of letters many times. The interactive diagram above shows how much key material gets used, even in a small encryption.

Diffusion

From Wikipedia:

Diffusion means that if we change a single bit [letter] of the plaintext, then (statistically) half of the bits in the ciphertext should change, and similarly, if we change one bit of the ciphertext, then approximately one half of the plaintext bits should change.[2] Since a bit can have only two states, when they are all re-evaluated and changed from one seemingly random position to another, half of the bits will have changed state. The idea of diffusion is to hide the relationship between the ciphertext and the plain text. This will make it hard for an attacker who tries to find out the plain text and it increases the redundancy of plain text by spreading it across the rows and columns; it is achieved through transposition of algorithm and it is used by block cipher only.
Diffusion in Sarah2 is accomplished through the permutation step, combined with taking letters pairwise through the S-box. The particular shuffle used ensures that even a one letter difference can propagate to the whole ciphertext in as few as log2 rounds.

Key

The key (the shuffled S-box) has 729! (about 101772 different configurations, which gives about log2101772 = 5887 bits of entropy. That's not really the whole story, since some keys would be weaker than others, but it's still a very large possibility space for an adversary to try and search. As an aside, not all of the key is even used unless a lot of text is encrypted, making it fairly hard to extract (I believe) even with an adaptive-plaintext attack.

Code for this project