A new look at one-time pads

In another article, I describe how text taken from a book in your library can possibly be used to serve as a one-time pad of sorts, since normal text also contains some unpredictability. The trick is to use a piece of text from an agreed-upon book that is five times the length of the plaintext. That method uses a computer-based hash function, but in this article I tell you how to obtain good security from simple paper and pencil calculations, actually using a key text out of the book that is only three times the length of the plaintext.

This cipher can be performed with pencil and paper, but in any case I have made a JavaScript version of it, which you may find useful as you read the article. It can be downloaded from this link

Yes, doing a standard hash by hand is incredibly long and tedious. This video shows a man trying to do a SHA256 by hand, which is enough to dissuade anyone from even trying. But perhaps nothing as complicated as that is needed. What we need is a way to convert a piece of encoded text, which will have a lot of underlying patterns that can be exploited by an adversary, into something that will pass most statistical tests for randomness. In other words, we need some sort of pseudo-random number generator (PRNG).

Earlier versions of BookPad used a lagged Fibonacci generator (LFG) for this purpose, but testing showed that randomness was sufficient even when this step was skipped, so long as the key text had the required length. Therefore, the BookPad spec was simplified to what you see here. The result is a cipher that achieves perfect secrecy (that is, it can never be broken, no matter how much computing power adversaries might have) with only a few simple steps that can be carried out by paper and pencil.

So here’s the BookPad cipher step by step, illustrated with an example in which the plaintext I wish to conceal is “Alice”:

1. BookPad uses randomness extracted from common text. Therefore, I identify a piece of text that my friend on the other side can also obtain and won’t incriminate me in the event of a search. It can come from  a popular book, a newspaper, a blog, whatever. What matters is that my friend can obtain an exact copy, that adversaries cannot guess the source, and that neither I nor my friend use that text again, ever. Let’s say the text begins: “This is my password. It is long.” We’ll call this key text.
2. The next step is to encode it, and the plaintext, as decimal digits. I will use the “Arsenio” straddling checkerboard below, which works well with most Western languages, or a similar one deriving from my key text. Spaces are encoded (represented by “+”), and there is an extra generic punctuation mark “=”. Letters on the top row are replaced by the single digit above and those in the other two rows by the digit on the left followed by that on top.

    1 2 3 4 5 6 7 8 9 0
   --------------------
  | A R S E N I O +
9 | B C D F G H J K L M
0 | P Q T U V W X Y Z =

which would lead to the encoding “Alice” = “1 99 6 92 4” (7 digits).

But I can also use a key-derived checkerboard made this way: 1. Take the first sentence (up to the first period) of the key text. 2. Count the number of letters in the first and second words (subtract 10, if necessary); these will be the numbers at the top of the checkerboard that won’t have a letter directly below; if the second word has the same number of letters as the first, take the third, and so on; if you reach the end without a different number, take the first + 1 . 3. Place the letters in the key text in the order they come, on the checkerboard: those in “arsenio” plus the space (represented as +) on the top row, the others in the second and third rows. 4. When you reach the end of the sentence, place the period (or = sign), and then the rest of the letters that have not appeared, in reverse alphabetical order (in reverse “arsenio” order, placed on the top row, for those in this word that have not appeared in the first sentence). Since the first sentence in the key text is “This is my password,” the empty cells on the top row are under the digits 4 (length of “This”) and 2 (length of “is”), and the filled checkerboard becomes:

    1 2 3 4 5 6 7 8 9 0
   --------------------
  | I   S   + A O R N E
4 | T H M Y P W D = Z X
2 | V U Q L K J G F C B

The key-derived checkerboard takes just a little longer to compose, and makes the resulting ciphertext non-malleable without the need to make a message authentication code (MAC), as described in this article, which usually takes a lot more work than generating a checkerboard. Highly recommended. With this encoding, the plaintext becomes “6 24 1 29 0”.

2. Now I also convert the key text into decimal digits using the chosen checkerboard. If I chose the key-derived checkerboard, the key text gets encoded as:414213513543445456334 67847481425135247927 (41 digits). The minimum I need is 3 x N digits, where N is the number of digits of the encoded plaintext, and the rest of the digits are ignored. I only need 7 x 3 = 21 digits needed to encrypt a message containing 7 digits. I take this piece of encoded key text and split it into three parts of equal length: 4142135, 1354344, 5456334. At this point I can put away the book since I’ll never use that key text again. This is very important.
3. Now I need to obtain the keystream from this encoded key text. To do this, I add the three parts digit by digit without carries, which can be done from left to right. This is what I get:

    4142135
   +1354344
   +5456334
   --------
    0842703

4. Finally, I subtract the encoded plaintext from the keystream, also without carries, which can be done from left to right. The result is the ciphertext.

    0842703
   -6241290
   --------
    4601513

And that’s it. I take the result 4601513 and send it out to my friend, along with the start location (page or chapter, line or paragraph number) of the key text. Obviously, I won’t send the book’s name. For added security, I may want to insert those numbers at a predetermined location in the ciphertext so an adversary won’t know where it is.

My friend at the other end performs steps 1-3 in the same way as I did, thus obtaining the same keystream. Then he subtracts from it the ciphertext I transmitted, also without carries, like this:

 0842703
-4601513
--------
 6241290

The result is the encoded plaintext, which now he decodes using the straddling checkerboard back to “Alice”.

For those of us who are really paranoid, BookPad can be strengthened in a few ways:

1. Use a key-derived straddling checkerboard instead of the default “Arsenio” checkerboard. The process for deriving this, which is described in step 1, does not add a lot of work, and using a key-derived straddling checkerboard prevents an adversary from changing the contents to something else of his/her/its choice.
2. Decode the ciphertext back to letters, and send it that way. This works especially well if a key-derived checkerboard is in use, since the digits to letter decoding is unknown to attackers.
3. Split the plaintext at a random spot and arrange the parts in reverse order prior to decoding, perhaps with a special code such as “..” separating the two. This is to lessen the impact of stereotyped beginnings and endings.
4. Add nulls here and there in the plaintext. Nulls are nonsensical characters that the recipient can easily spot and ignore, but which make cryptanalysis more difficult.
5. (Deprecated) Add a message authentication code (MAC) to prevent an adversary from modifying the message at ciphertext level. The process for making a MAC is described in this article. It is deprecated because using a key text-derived checkerboard also achieves this and is much easier to do.
6. (Deprecated) Use a randomly chosen serial, and do the same as in point 3 above. Serials were found found to be insecure in this same article, so serial usage is no longer included in the BookPad spec in this article, and has been replaced with a shift of the encoded key text. The JavaScript code that still implements a serial can be found at this link.
7. (Also deprecated) Use a randomly chosen and never-reused shift, and then insert the shift at a location in the ciphertext based on the key text, rather than sending them in the clear or inserting them always in the same spot. For instance, count the length of the first two words of the key text, and insert the shift (and MAC, if any) after so many ciphertext digits have elapsed, and then continue with the rest of the ciphertext. If this is then decoded back to letters, so much better. An attacker will have a hard time finding the shift because he won’t even know where it is.  Unfortunately, the same article shows that shifts, although better than serials, still provide no real security when a key text is reused. The JavaScript code that still implements a shift can be found at this link.

These are added as well to a webpage that implements all the steps mentioned above, programmed in JavaScript. You can find it at this link. I think you will find this program quite useful, especially since it allows you to experiment with the cipher with a minimum of hassle.

Okay, but how secure is all this? I’m going to address this by putting on my cryptanalyst’s (hacker’s if you will) hat and looking at different ways to attack the process. Here’s a few things I’d try:

1. Statistical analysis of the ciphertext. The straddling checkerboard encoding makes it more difficult since the resulting digits, unlike the original text, have a fairly flat expected frequency distribution. But digraphs and trigraphs are preserved after encoding so it may be possible to find a few on a long piece of text. Additionally, there will be other patterns and repetitions that may be picked up by statistical tools. The problem for me poor hacker is that each plaintext digit is combined with a quite “random” (in the statistical sense) keystream, so I shouldn’t expect any statistical properties of the plaintext to survive in the ciphertext.
2. Brute force. I can try every possible key text, but this won’t help much since the number of possible key texts is equal to the number of possible ciphertexts, due to the high entropy of the long key text. Brute force will produce every possible plaintext, and I don’t have a way to tell which is the good one (not even using the MAC, which would require additional brute forcing). I can still try all the books from obvious places like gutenberg.org, all the articles from nytimes.com, etc., etc., etc., and I might get lucky. The Wikipedia article on the running key cipher, which is a lot like BookPad except that the key text has identical length as the plaintext and no extra randomizing step is used, states that the number of published books in the world is of the order of 2^40, which is within the reach of today’s computers to process. Still, the risk of missing the source is great, especially if it is not as obvious as those noted above.
3. Somehow get the plaintext for a particular ciphertext, and then get the keystream by subtracting the known plaintext from the ciphertext. Then reverse the keystream back to key text so I can guess what book it was taken from. The problem is that the keystream derived from a piece of key text split into three and combined by addition is quite random, even without the LFG step (see this article), so that it could derive from a variety of key texts.
4. Change the hidden plaintext by changing the ciphertext in certain ways (especially if I know the plaintext). This is possible if the encoding is known and there is no MAC accompanying the ciphertext, but not easy at all if there is a MAC of sufficient length or the encoding is derived from the key text. I could try different encodings in the latter case, but for this attack I have to be right on the first try, which doesn’t seem possible if the encoding derives from the key text, and therefore I don’t know how it’s done.
5. Force the sender to re-use a key text for two messages, and then subtract the ciphertexts to eliminate the keystream and apply statistical tools to the result, which combines the two plaintexts. This won’t work if the sender never reuses a key text, as he/she should. Still, I could try to mount a related-key attack, where the sender has used the same key text and two different shifts. This is studied in this article.
6. Early versions of BookPad used Lagged Fibonacci generators, which are known to have problems, which I exploit. One of them is their linearity, which makes combining a serial number with the seed quite ineffective, as discussed here. LFGs are also very sensitive to the seed, so that a bad seed will lead to a sequence of digits that repeats after a short interval. If all the digits in the seed are even or divisible by 5, every digit in the sequence will be even or divisible by 5, respectively. In BookPad, the seed is not being tested for this, so it is possible that the resulting keystream is not statistically random, especially if the keystream is long and the key text is short, because then there is room for a bad LFG to start repeating digits. These and other reasons recommend not using a LFG. If a key text of sufficient length is used, the keystream passes randomness tests even without a LFG.

Does all this mean that BookPad has no flaws and you can go ahead and entrust high secrets to it? By no means, but at least you are encouraged to test it. Time and testing will tell if it lives out to its promise of perfect security with a minimum of work.