Is a book cipher provably secure?

I've seen ciphers (usually in spy drama shows) that involve taking a book and writing down an index to individual characters. Essentially it's a keyed substitution cipher, where the key is the name and exact edition number of the book.

Example:

Imagine a book that has 500 pages, with approximately 60 lines per page and 80 characters per line. We might write 238:4:64 to specify that we're on the 238th page, 4th line, 64th character. A five character message might be encrypted into 114:25:22 374:41:46 182:17:62 63:53:8 50:8:18.

Without knowing what the book is, I would imagine this is provably secure as long as the person encrypting never re-used an index. Am I correct in this assumption?

For fun, you could try this out: 12:9:3 183:15:7 238:14:11 310:9:38 194:11:17 7:1:1

I'm using a page:line:character format, ignoring titles, spaces and punctuation. The book is Charles Darwin's On The Origin of Species, 6th edition.

N.B: I'm not trying to get you to crack this, just adding it because it nicely demonstrates the way this works :)

-

Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and 321:42:36. Therefore, merely not reusing exact index values is not sufficient; you should refrain from using two index values from the same word. This reduces the lifetime of a given book as a cipher key.

Another problem is in the "random choice". When you want to encrypt a letter, you must choose one of the index values in the book which correspond to that letter. Human beings are very bad at making random choices in their head. But non-random choices can exhibit biases. So the encryption process is important, and not completely described. An unbiased process would have you use dice to select at random the page, line and column; and if that does not correspond to your target letter, try again. That's tedious.

Also, in order to avoid reusing a given index, you must keep a list of the index places you have used, e.g. by marking the already used letters in the book. The book then ceases to be an inconspicuous object: instead of a brain-only key ("use this book"), you have a physical key ("use this, I mean that specific printed instance, book").

And, of course, anybody who has scanned millions of book and extracted the text into searchable computer structures, can easily try all existing books in a few minutes, and report a hit when the decryption result appears to look like meaningful words. So you are at the mercy of Google (and of whoever acquires Google's services).

-
Right, I would say that the main difference between this and a one-time pad is that: a one time pad's security is based on all possible pads that could be created, whereas a book cipher's security is based on all possible books that have been created. – John Gietzen Nov 25 '11 at 20:31

An obstacle to proving that a book cipher is secure is that the letters in (most) books are not chosen independently at random. Thus, in principle, if two indices are chosen too close to each other, an adversary could deduce some statistical information about how the corresponding plaintext letters may be correlated.

As a toy example, suppose that an adversary has already deduced (e.g. from known plaintext) that the indices 123:7:41 to 123:7:46 spell out E-N-C-R-Y-P. It's then not much of a leap of deduction to guess that index 123:7:47 probably denotes a T.

A more realistic case might be one where the book used as a key happens to be e.g. a collection of statistical tables, in which some pages consist mostly of text and others mostly of numbers. A clever attacker might then be able to deduce (again e.g. by comparing ciphertext with known plaintext) which pages are which, and thus be able to tell with fairly high accuracy which ciphertext indices denote numbers.

Also worth noting is that the keyspace, i.e. the number of distinct usable books, is not as large as one might think. Especially in the modern era of computers, it would not be hard to write a program to try to decrypt a message repeatedly using each of a collection of digitized books as keys, and to apply a statistical test to the output to see how random it looks. Indeed, with enough known plaintext, one could even make the test robust against changes in pagination and other minor differences between editions.

And, of course, a major weakness of a book cipher is that one must carry the book around as a key (or otherwise obtain repeated access to it, e.g. by regularly visiting a library). If one had captured some messages that one suspected of being encrypted with a book cipher, and had a hunch about the identity of the sender, some simple old-fashioned surveillance (and perhaps burglary) would narrow down the possible keyspace significantly.

-
Interesting. Given an attacker with moderate resources (i.e. one that doesn't have access to the entire world's literature) it seems that it would be secure as long as the pages, lines and letter offsets were chosen with reasonably random distribution. – Polynomial Nov 24 '11 at 12:42

hummm... some thoughts about it:

1. I think that it could be secure depending on what you want to hide. The bigger and the more "real world words" you want to protect, the easier it gets to crack. Why? Because in books, in general, you'll only have letters, few numbers, and that's only. Ok, so I know your transmitting one or more words. By the size of the index you provide, I know how long it should be.

2. Knowing that, I can easily write some program to use it in a large collection of books. And since I know what to look for (look for letters that will make regular words), it's easy to reduce the search (this book is just giving trash? skip to the next one)

3. How many books are there in the world? This site, citing google, says: 129,864,880. So I would have so search your index in the 130 million books. Not that hard. Ok, perhaps hard for me to have all that, but Google, perhaps government, already have all them.

4. That will procuce some false positives. Ok, just check all them out.

5. Remember "The Bible Code" ? Looking for secret codes / informations that could be revealed if you applied some search using constant search rules. Ex.: look for every 1004th letter of the Bible. It's how the false positives can be produced.

6. So, it all depends on what you want to hide, from who you want to hide, and what would happen to you if someone find out your secret.

7. Using different books on each message would help a bit. Using some "encoding" inside your code could help more: for example, the person who knows how to decrypt the message have to put the letters in the correct order, that only he knows. That avoids / slows down the brute-force search-in-every-book. But not that much, since any word not having a vowel indicates that the book is the wrong one. Perhaps using some Ceaser cipher could help.

-
+1 for the 130 million figure. That's not really all that much; we're talking about the equivalent of a 27-bit keyspace. – Ilmari Karonen Nov 24 '11 at 12:57

If the book cipher refers to words as opposed to letters then the book cipher could be made more secure by the different ciphers refering to the same word. Therefore where a word appears more than once in the book likely use a different reference to it.

Another way of making it more secure is not to use a book in your native language for example an English Langauge speaker using a book in French.

-
Of course, if the book cipher refers to words, you're stuck with the words found in the book. If you're book is French, that means that you're stuck with French vocabulary... – poncho Jul 3 '15 at 20:43

There are a very large number of books that have never been scanned, and most of those which have are full of garbage characters and/or are usually scanned into pdf as images, which makes them unusable.

If I used an unusual book, transcribed it in text, and wrote a program which took each letter of each word and put them into a numbered database, and then used the database to encrypt a message - also making sure no number was used more than once, it would be very difficult to decrypt without having the book. For instance, using the first paragraph of this reply 3, 5, 8, 11, etc. all represent the letter "e". So the program would pick one at random, say "5", for the first "e" in the message, then eliminate it from further use, maybe picking "11" the next time "e" occurred.

Decryption would require either the book or the database derived from the book. The program would take the number and search the database for the letter corresponding to it.

Probably the database would use numbers with the same number of digits, like "000001" for "1", and "000090" for "90", to make it easier, then all the numbers could be run together without spaces, making it harder to figure out what it was to begin with.

-
How is this an answer to the question? – poncho Jul 19 '15 at 3:08