Back to previous post: Pandemic: The Game

Go to Making Light's front page.

Forward to next post: That Voodoo That You Do

Subscribe (via RSS) to this post's comment thread. (What does this mean? Here's a quick introduction.)

September 9, 2008

Keep It Secret, Keep It Safe
Posted by Jim Macdonald at 02:17 AM * 105 comments

Let us talk, dearly beloved, about a reasonable pencil-and-paper crypto system, for those times when you don’t want to use your computer to encrypt stuff that you need to send to some other pal.

Nothing is totally secure. Aside from strong-arm mathematical cryptanalysis, any crypto system has weaknesses. The first of them is this: All pipes leak at both ends.

Someone knows what the message was before it was encrypted. Someone else knows what it is after it’s decrypted. Both of those people are vulnerable to black bag cryptanalysis, to checkbook cryptanalysis, and to rubber hose cryptanalysis. They are even more vulnerable to dumb-shit cryptanalysis. The more people who know the contents of the message the greater the vulnerabilities up.

But leave that aside. Here’re the workshop instructions.

Start with the Straddling Checkerboard. This is a substitution cypher devised by those clever buggers the Jesuits back during the Enlightenment.

 
     

Neat little table there. Notice how it’s different from those little 5x5 checker boards that everyone knows. The first thing you’ll notice is that it uses all the numbers, and all the letters are available. The second thing you’ll notice is that one of the rows has no number at all. I’ve stashed the most common English letters up there.

One of the disadvantages of a standard checkerboard is that it doubles the message length. With a straddling checkerboard, that isn’t the case.

Here’s how it works:

Let’s take our message: “Don’t let them scare you.”

D is at the intersection of 1 and 5, so it becomes 15. O is on the first row, so it just becomes 6. N is on the top row too, so it becomes 7. T, similarly, becomes 4.

Proceed in similar manner until you have the entire message:

15674 11344 18312 01458 32962 5

There it is, broken into five-number groups (for ease in transmission). Fill up the last group with random numbers until it, too, is five numbers long.

In order to unambiguously decrypt the message, go through it. Every time you see a 1 or a 2, circle it and the next number. All the remaining numbers will be single letters.

Right. Very good. But still not secure. Let’s do something else with it. This is a wrinkle added to the old Jesuit Straddling Checkerboard by the Red Orchestra, the Soviet spy ring that operated in Berlin during WWII.

We’re going to add pseudo-random numbers to the mix. We’ll get them from an almanac: in this case the World Almanace and Book of Facts, 2008 edition.

Find a page within that contains a Whole Lot of Numbers. For example, take page 160, Non-marital Childbearing in the US, 1970-2004.

We’ll also need to know how to do non-carrying addition. 1+1=2. 6+6 also = 2.

In that World Factbook, on page 160, I’m going to start on line 07. That’s the line that starts “All races.” We’ll just follow the numbers across the page, then down the page, then to the next page, and as far as we need until we have enough numbers to write under our little encyphered text.

Thus:

15674 11344 18312 01458 32962 51234 (note the padding)

10714 31842 20280 32232 83303 32335 (and so on)

Add the numbers, vertically, with non-carrying addition and you get your final ciphertext:

25388 42186 38592 33680 15265 83569

To reverse this, just subtract the keynumbers from the ciphertext, borrowing as necessary.

One more step. You’ll need a couple of other five-digit numbers, now, which you’ll have memorized: Say the first one is 12121 and the second is 98765. You and your buddy know these numbers; no one else does. This is how you’re going to tell your chum which page and line to start on.

Page 160 line 07 becomes 16007. When added to 12121 that becomes 28128. When added to 98765 that becomes 04762. Now add in the date of transmission: 090908 (drop the last 8 because you only need five numbers) and you get: 27118 and 03752.

Put those numbers in pre-arranged places in your ciphertext (say second from the start and third from the end), and you’re done.

25388 27118 42186 38592 33680 03752 15265 83569

The only punctuation you use is the period (.) which is also encrypted. The slash (/) is the numeral shift sign. In order to put numbers into your text, you put in the shift sign, then repeat each digit three times, then the shift sign again. Thus “Meet me at 247 Main Street” becomes “Meet me at /222444777/ Main Street.”

Some other notes on craft: Always construct your checkerboard from memory each time you use it, and destroy it immediately afterward. Do not do any work on an electronic device. Stay away from windows. The checkerboard and the plaintext should never be on the same physical sheet of paper. The plaintext and the ciphertext should never be on the same physical sheet of paper. Work on a hard surface that will not take impressions.

Immediately after you’ve created the ciphertext, destroy all the intermediate sheets of paper.

Since the beginnings and ends of messages are often standard, split your message in two and reverse the parts so the beginning and end are together, somewhere near the middle.

You and your pal will need to agree on a book to use. Have several different books of tables in your house (so which one you used isn’t obvious).

All that a crypto system buys you is time. Don’t send anything where the information has a longer shelf life than your cipher.

Assume that the bad guys know everything about your crypto system except the specific keys you used today.

Make all arrangements (keys, etc.) face to face. Nothing by any electronic means of communication. If anything at all makes you feel hinky, change the keys right then.

You can change the arrangement of letters inside the checkerboard, and which numbers are the straddle, regularly. Like, daily. (One way to change the arrangement of letters is to use a keyphrase, writing it into the checkerboard and using each letter only once. One advantage of using keyphrases is that they’ll near-automatically put the most common letters in the top row.) For example, Now is the winter of our discontent yields:

 
     
Comments on Keep It Secret, Keep It Safe:
#1 ::: Linkmeister ::: (view all by) ::: September 09, 2008, 02:31 AM:

Also ensure that your correspondent knows which edition of the book you used to encrypt the message, particularly if it's something as common as an almanac. I'm sure I've seen that twist used in some novel or another, followed by great whoops of laughter as the detective realizes the error.

#2 ::: Doug Burbidge ::: (view all by) ::: September 09, 2008, 02:45 AM:

The suggested algorithm is, I think, subject to differential cryptanalysis. That is, if two different messages are encrypted using the same key, it's much easier to crack than brute force would suggest.

Another weakness is that the keystream suggested is not evenly distributed: in a list of numbers like this, numbers are more likely to start with small digits.

Crptonomicon references a crypto scheme which uses a deck of cards (or, really, two matched decks of cards: one for encrypt, one for decrypt). The algorithm is in the back of the book, and on Wikipedia.

#3 ::: Dave Bell ::: (view all by) ::: September 09, 2008, 02:56 AM:

Sherlock Holmes, I think. It's a book code, he discounts Bradshaw on grounds of limited vocabulary, tries Whitaker's Almanac, and then realises he has the latest edition, only just published...

[Googles...]

It's the opening of The Valley of Fear.

#4 ::: Devin ::: (view all by) ::: September 09, 2008, 04:28 AM:

It's cryptanalysis that you use for reading other folks' mail (assuming you're not a gentleman or an old-timey secretary of state, that is). Rubberhose cryptography would be like beating someone up and using the number of times you hit them before they lost consciousness as the seed to your pseudo-random number generator.

And in response to the present and likely future comments on how this isn't really mathematically much better than ROT13... Honestly if you're using anything better than a Caesar cipher, your crypto is fairly likely to be the strongest link in the chain*. Think hard about whether your end is safe from black bag work, traffic analysis, etc, and whether your correspondents are scrupulous and trustworthy before you work any harder than something like this or a tableaux cipher, if it really has to be pen and paper. If you're corresponding in email anyhow, you might as well use GPG etc, but make sure you don't save the plaintext, you scrub everything, etc etc.

*Certain channels can expect technologically sophisticated attackers, but few of us ever need to think about how to secure those channels. The stuff we need to think about, usually the attacker will have more human savvy than tech savvy, and so checkbook, black bag, traffic analysis, and subornment are more likely modes of attack.

#5 ::: -dsr- ::: (view all by) ::: September 09, 2008, 06:04 AM:

If your threat model allows you to do all these manipulations and send a note to your ally which will be received even though it is intercepted... I don't know what your threat model is.

Let me suggest something much simpler and harder: two code words which you arrange with your ally. One word means "I'm in trouble"; the other word means "Don't trust anything from me until you see me in person." The words should be common enough that you can work them into a phone conversation or an email, but not so common that you will use them by accident. An uncommon synonym for a common thing is plausible.

#6 ::: Zeborah ::: (view all by) ::: September 09, 2008, 06:09 AM:

I have a fondness for a variation on the Vigenere cipher whereby a+a=b (meaning I can do it in my head so don't need a square) and the key is a) at least as long as the plaintext and b) not English. This can be trivially combined with the general theory of book cipherage in any number of ways I leave as an exercise to the reader.

Phone books, TV guides, and newspapers (depending how often one wants to change the source of the key) are handy and unremarkable sources of pseudo-random letters and numbers.

#7 ::: David Goldfarb ::: (view all by) ::: September 09, 2008, 06:18 AM:

I just read Dave Duncan's The Alchemist's Code and he describes a ROT-polyalphabetic that seemed pretty good. Probably not proof against the NSA, but then not a lot is.

Basically you pick a key word or phrase, and write out rotated alphabets where A goes to each successive letter in the key. So for example if the key were MAKING LIGHT you'd have

MNOPQRSTUVWXYZABCDEFGHIJKL
ABCDEFGHIJKLMNOPQRSTUVWXYZ
KLMNOPQRSTUVWXYZABCDEFGHIJ
IJKLMNOPQRSTUVWXYZABCDEFGH

...and so on. Then to encipher, you go through your successive alphabets one by one. So the word FOOL, say, here would go to ROYT.

#8 ::: Zeborah ::: (view all by) ::: September 09, 2008, 06:25 AM:

David@7 - I think that's a Vigenere cipher sideways. The problem is that with a short key like "Making Light" you run out of alphabets and have to start again at the top, and repetition is a Bad Thing.

#9 ::: Peter Erwin ::: (view all by) ::: September 09, 2008, 07:02 AM:

David Goldfarb @ 7:
That's basically a Vigenère cipher, which was pretty much state-of-the-art from the 16th Century until the 19th Century, when it was broken. (By, among others, Charles Babbage.) These days, there are online applets that can help you break messages enciphered this way.


Whoops -- I see that Zeborah (#8) just pointed that out. I'll add that the advantage of what James described is that they key -- the sequence of letters or numbers you use to generate the substitution -- is intended to be long enough that it doesn't repeat before the message ends. If the sequence of numbers is genuinely random as well (unlike, say, a passage of text in a particular language), then you have a proper one-time pad, which is unbreakable. Unless you re-use it for later messages...

A slightly better approach might be for you and your friend to use some regularly updated, public source of pseudo-random numbers. E.g., the last digit of each price or trading-volume amount, taken from the most recent close-of-market summary in a particular newspaper or other widely available listing. Now you've got a (nearly) inexhaustible source of numbers. (Of course, this only works if no one knows that's where you're getting the random numbers from. But the same is true with using numbers from an almanac.)

#10 ::: Dave Bell ::: (view all by) ::: September 09, 2008, 07:15 AM:

The basic advantage of the method Jim describes is that it is a reasonably efficient method of converting alphabetic characters to numbers. And you can rearrange the numbering to use different digits for the horizontal rows.

But that would be a false complication, because the security is in the arithmetic, derived from the keytext. Even with a poor key source, such as described, it's difficult. It's going to need professional cryptanalysis.

And if you keep your messages short, it can be practically unbreakable.

You can combine the idea of a "don't trust me" code with any means of sending a message. You might pad out the beginning and end of the message with a couple of random words--it helps avoid easy-to-spot patterns--and that's where your warning code will go.

And if you're using a book of statistical information, agree to drop the first couple of digits of each number.


#11 ::: John Stanning ::: (view all by) ::: September 09, 2008, 07:16 AM:

The drawback of using cryptography is that it reveals to the opposition that you have something to conceal. If they already know you're on the other side, that doesn't matter of course; if they don't, and you want to prevent or delay them finding out, then you use steganography, "the art and science of writing hidden messages in such a way that no one apart from the sender and intended recipient even realizes there is a hidden message" (Wikipedia article). With a numerical code, you might format it so as to look like accounts or budget or some such, assuming that you and your pal have cover that would fit, and you'd pad the significant numbers with non-significant numbers.

A nice example of steganography is given in Dorothy L. Sayers' novel The Nine Tailors (worth reading for other reasons). You can find the coded text by Googling for the opening words "I thought to see the fairies in the fields", but for the solution you may have to read the book. (I'd love to know how long it took Sayers to compose the text.) It has some nice twists: the decoding 'key' is a method of English change-ringing, which an opposition without knowledge of this rather arcane subject might miss (also, you don't have to memorise the key, only the method that generates it); and the result of decoding is itself cryptic, requiring further understanding to reveal the actual message.

#12 ::: heresiarch ::: (view all by) ::: September 09, 2008, 07:33 AM:

It's funny; I just finished rereading Cryptonomicon yesterday. Hmm--I've been inspired to go back and actually learn Solitaire.

#13 ::: Neil Willcox ::: (view all by) ::: September 09, 2008, 07:36 AM:

You might pad out the beginning and end of the message with a couple of random words--it helps avoid easy-to-spot patterns--and that's where your warning code will go.

I think there's a bit in a John LeCarre novel when a directive comes down to stop calling all their operations Operation $Whatever but just $Whatever.

#14 ::: BSD ::: (view all by) ::: September 09, 2008, 07:51 AM:

Unless you're engaged in ongoing espionage, how is this easier than planning to be terse and generating sufficient one-time pads?

#15 ::: Graydon ::: (view all by) ::: September 09, 2008, 08:02 AM:

The presence of a one-time pad is difficult to conceal and a functional admission of guilt.

#16 ::: Carrie S. ::: (view all by) ::: September 09, 2008, 09:04 AM:

The drawback of using cryptography is that it reveals to the opposition that you have something to conceal...use steganography, "the art and science of writing hidden messages in such a way that no one apart from the sender and intended recipient even realizes there is a hidden message"

I came up with a rather nice method of steganography that has the added advantage of being encodable in any format that will allow you to transmit ones and zeros. Fits on a 3x5 card, too.

Of course I'm not going to post it here. :)

The presence of a one-time pad is difficult to conceal and a functional admission of guilt.

I remember seeing an Edwardian-era spy drama on A&E once, in which the main character begins to suspect that the lady to whom he's been attracted is in fact the enemy agent he was sent to discover. So he searches her room and finds a bunch of papers covered in incomprehensible strings of letters and numbers, and, sick at heart, turns her in. I don't remember if he killed her himself or if other agents of his employer did so after she was in custody. Her code-sheets get taken back to headquarters to be deciphered, but the codebreakers are utterly stumped until a secretary gets a look at them and wonders why everyone's making such a big fuss over a bunch of knitting patterns...

Which of course raises the possibility of a code based on knitting/crochet/cross-stitch patterns. You could even have different keys based on, say, the first letter of the second word of the pattern's "name": if it's called "Chinese Lantern", use Transcription 4, but if it's called "Chinese Dragon", use Transcription 17, etc.

#17 ::: ajay ::: (view all by) ::: September 09, 2008, 09:10 AM:

15: there's also the bulk issue. For OTP encryption, you need to use one sheet per message. If you're sending a lot of messages, that's a lot of pads to handle, keep safe, not lose, not accidentally damage or destroy, keep away from damp and mice (yes, it happens!) etc, at both ends of the link - and/or a lot of risky meetings with your handler to get new ones.

All you need for the system above is the source of pseudo random numbers, which is innocuous and easily replaceable, and your two five-digit keys, which you can memorise.

You can combine the idea of a "don't trust me" code with any means of sending a message. You might pad out the beginning and end of the message with a couple of random words--it helps avoid easy-to-spot patterns--and that's where your warning code will go.

Simply leave it out if you are transmitting under duress. And pray that your handlers are better at their jobs than the SOE handlers for the Dutch agents caught and forced to transmit by the Gestapo during Operation NORTH POLE; at least one captured agent, sending from Gestapo HQ, was horrified to receive a stern reminder from Broadway - "next time, do not forget to include your security check!"

#18 ::: ajay ::: (view all by) ::: September 09, 2008, 09:12 AM:

Which of course raises the possibility of a code based on knitting/crochet/cross-stitch patterns.

Neal Stephenson, "The Confusion" - gros-point embroidery.

#19 ::: James D. Macdonald ::: (view all by) ::: September 09, 2008, 09:22 AM:

#2 That is, if two different messages are encrypted using the same key, it's much easier to crack than brute force would suggest.

That's why you do your best to never use the same key twice.

#20 ::: ajay ::: (view all by) ::: September 09, 2008, 09:28 AM:

Another weakness is that the keystream suggested is not evenly distributed: in a list of numbers like this, numbers are more likely to start with small digits.

Ha! Benford's Rule! Good catch. I think you could get round it, though, by omitting the first digit of every value in the list. Mathematicians - would that work?

#21 ::: C.E. Petit ::: (view all by) ::: September 09, 2008, 09:30 AM:

Many of Jim's imprecations on how to maintain security pale in comparison to the most important one:

Don't give a cryptanalyst a known plaintext by either:

* Extensively quoting something in current events that is also widely quoted in news sources, such as the text of the State of the Union (anything of more than around 900 characters will create enough text to analyze rather thoroughly using 1970s computing equipment and software). This kind of attack is behind how CSS was broken so quickly.

* Avoid unique terms wherever possible, and in particular avoid overrepetition of proper names that will be directly linked to either the sender or receiver. One of the best examples of this is Yardley's decryption of Japanese codes during the World War Interregnum by assuming that they would include extensive repetition of "Irish independence"... in a language that Yardley did not speak.

#22 ::: John Mark Ockerbloom ::: (view all by) ::: September 09, 2008, 09:31 AM:

I suspect that a message of sufficient length that's been checkerboard-ciphered can be recognized as such with a computer, due to the high frequencies of 1's and 2's, and the frequency of repeats of the 1 and 2-digit patterns. Moreover, if I've gotten the message decoded as far as the checkerboard cipher, it's essentially a newspaper cryptogram, which is easy for computers (or humans) to solve if the message is of sufficient length.

So if I were the eavesdropper, knew that my targets were using this type of scheme, and had access to a computer and some clerical staff, I'd probably want to have some files preloaded with the tables from common reference works, like the World Almanac. (And if my agents noticed some uncommon reference works in my target's houses, I might also get someone to copy from them, particularly if two targets had the same uncommon reference work.)

Then, if I intercepted a message, I could try running it against *all* the starting rows in my repertoire, and see which ones result in something looking like a checkerboard cipher. If I'm lucky, there are only a few that do; and I can then try seeing if any of them can be solved as a cryptogram.

If one can, I not only have the message, but I know what book they're using, where the two "control strings" are being put, and since I know the starting row, I also know what 5-digit keys they're using for this message. All of these
extra bits of information can make it a lot easier to decode the next intercepted message.

There's obviously a lot of prep work involved here, but once the files are prepared, a computer could potentially grind through the problem in seconds, without needing keys, and unlike rubber-hose or checkbook cryptanalysis, neither the sender nor the recipient would get an obvious indication that their code had been cracked.

#23 ::: Kevin J. Maroney ::: (view all by) ::: September 09, 2008, 09:33 AM:

The presence of a one-time pad is difficult to conceal and a functional admission of guilt.

One of the brilliant bits of Bruce Schneier's Solitaire Cipher (referenced above--it's the cipher in Cryptonomicon) is that the decryption pad is a deck of cards. Everyone has a deck of cards. You can key the deck to a Bridge column in a newspaper that both the sender and receiver reliably get, or (these days) to a Bridge website.

I've long thought that Usenet, esp. the binaries newsgroups, would be a great source of random data for one-time pads and a great hiding place for steganographic messages.

#24 ::: Scott Taylor ::: (view all by) ::: September 09, 2008, 09:34 AM:

-dsr -
If your threat model allows you to do all these manipulations and send a note to your ally which will be received even though it is intercepted... I don't know what your threat model is.

Any delivery system is susceptible to man-in-the-middle attacks. E-mail and snail mail* messages can be intercepted, copied, and allowed to continue (to prevent either end of the communication link from sending up the red flag via alternate methods), and then analyzed (via brute-force if necessary) at leisure.

Let me suggest something much simpler and harder: two code words which you arrange with your ally. One word means "I'm in trouble"; the other word means "Don't trust anything from me until you see me in person." The words should be common enough that you can work them into a phone conversation or an email, but not so common that you will use them by accident. An uncommon synonym for a common thing is plausible.

This kind of scheme is useful, and can be implemented in addition to other methods.

One useful tool for something like this is to incorporate a "Start word" - a word that allows you to use those other flag words in conversation - as long as they are not used after that word.

For example, let's take the following set -
"Absolutely" - START WORD.
"Supper" - In trouble. Send Lawyers, Guns, and Money.
"Dinner" - In trouble. Attempt No Rescue. Abandon.
"Bibliophile" - Person mentioned in this sentence is a traitor!
"Automobile" - Trust no communication from my cell until I speak with you directly.

Then the communication -

Sure, Abi, that's great. Look, we should get together sometime soon. Say, Dinner next week? I'll see if Daniel wants to come along - he's been dying to meet you - says he's a real bibliophile, and wants to talk to you about book-binding.

is totally innocuous, but

Absolutely, Abi, that's great. Look, we should get together sometime soon. Say, Dinner next week? I'll see if Daniel wants to come along - he's been dying to meet you - says he's a real bibliophile, and wants to talk to you about book-binding.

means that I'm compromised (and likely my cell is as well), the situation is precarious enough that I don't want even an attempt to rescue (time for a Burn Notice), and that I know my turncoat is Daniel - who should either be encysted, or killed.

*It should be assumed, at all times, that any and all broadcast based data transmission methods are compromised - this includes not just radio and cell phones, but also bluetooth (infra-red might be okay), and electronic devices in general (unless TEMPEST rated, or operated inside a Faraday cage). There are just too many snooping devices out there, and too many ways to capture signal.

#25 ::: Carrie S. ::: (view all by) ::: September 09, 2008, 09:38 AM:

#24: Was it Campion who had an elaborate system along those lines? Like, there were certain phrases which meant, "Whatever time I say in this sentence, meet me three hours later" and so forth? I could swear it was, but my google-fu fails me.

#26 ::: ajay ::: (view all by) ::: September 09, 2008, 09:52 AM:

23: using a daily bridge column falls foul of the same brute force approach that 22 mentions, as Schneier points out; there are ways to set up a Solitaire pack using a passphrase, though.

Another useful source of pseudo random numbers would be the day's closing stock prices as printed in the Financial Times.

Or a Numbers Station! All you have to include in your key is which frequency to listen on and when to start listening. And those are probably much more robustly pseudo random than stock prices or almanac data.

#27 ::: Scott Taylor ::: (view all by) ::: September 09, 2008, 09:59 AM:

Carrie S -
#24: Was it Campion who had an elaborate system along those lines? Like, there were certain phrases which meant, "Whatever time I say in this sentence, meet me three hours later" and so forth? I could swear it was, but my google-fu fails me.

It may have been. This type of scheme has been used in fiction quite a lot, AIR (Didn't they have a similar schema in The Moon is a Harsh Mistress?)

Such systems have to be kept pretty small - the whole "seven +/- two" deal, and should, of course, never be written down in "exploded" format - but this is true with all codes.

Code systems, other than very small ones like this, have mostly been supplanted by ciphers like the one James describes above, one-time pads, and computer-aided cryptography like PGP, because if you capture the codebook, you've cracked the whole system, while a cipher *should* (theoretically) be resistant to analysis unless samples of the plaintext are available, *even* if you know the encryption schema, as long as you don't have the keys used to encrypt and decrypt.

(Theoretically because not all encryption schemas are created equal, and some are more susceptible to brute-force analysis than others).

#28 ::: albatross ::: (view all by) ::: September 09, 2008, 10:19 AM:

Devin #4:

WEP is one very nice, public example of incompetently done crypto that is the weak point of real-world communications. I think the crappy cellphone encryption and truly embarrassing cordless phone "encryption" (aka frequency hopping with a short pseudorandom spreading sequence, for the best ones, as far as I can tell) are other examples of the crypto being the weak point. Similarly, NSA apparently imposed a 56-bit key on DES (IBM wanted a 128-bit key; left to their own devices, I think they'd have produced a cipher that was weaker with respect to academic attacks, but which would also have been secure in practice even today), and required dumbing down commercial crypto products for export to 40 bits for many years. Those both indicate places where the crypto is liable to be the weak link, because the cryptanalysis can be done efficiently and automated. (In particular, keysearch attacks as on DES and those 40-bit ciphers are very susceptible to doing a godawful precomputation, storing a lot of intermediate information, and then pretty quickly being able to break a given instance of the cipher.)

More to the point, you need to think about what resources your attacker has. If he's installed malware on your computer, all ciphers done on that computer are trivially breakable to him[1]. If not, you will do much better with a computer-mediated cipher than you can with any paper-and-pencil cipher, not least because even using some random shared information as a one-time pad and just doing mod 26 addition on it is a massive pain, and so you'll be tempted not to encrypt everything. (And you don't want to encrypt known stuff under a weak paper-and-pencil cipher!)

The flaw with Jim's comment here about cryptography buying you time is that once someone has spent the time to work out an effective break against the paper-and-pencil cipher you're using, they can code up their break or the tools needed for their break. Developing the attack requires a moderately bright person, but using the tools to break future things usually doesn't. (Sometimes, Bruce Schneier calls this phenomenon a "class break"--once the thing is attacked once, the attack spreads throughout the whole world very quickly.)

If you decide to use paper and pencil ciphers and books for running key material, you really, really want a book that's not online anywhere. That's kind-of hard to guarantee, but maybe you can manage it. But if there's any way you can get a trusted computer, you're going to to much better. You can leverage the trusted computer to do some really cool things. For example, there are visual one-time-pads and visual secret sharing schemes that are amazingly cool, and that can be used to communicate with computerless agents in the field using magazine or newspaper photos, faxes, etc., of completely innocuous things. See this Wikipedia article for more information.

I think paper-and-pencil schemes are really hard to use to secure communications, though one-time-pads will work if you can avoid messing up handling your key material. (Note that a one-time pad is unconditionally secure, and a two-time pad is unconditionally insecure.) It's probably a lot easier to use paper and pencil to authenticate a message, and that's often just as important.

[1] Modulo the assumption he can get information back out, or knows your crypto scheme well enough to target the malware at it specifically.

#29 ::: JJ Fozz ::: (view all by) ::: September 09, 2008, 10:26 AM:

Ah, the Jesuits - one of the few things I am thankful for when it comes to being raised Catholic - along with never being touched by Father McFeelmeup in my "swimsuit area."

#30 ::: James D. Macdonald ::: (view all by) ::: September 09, 2008, 10:35 AM:

Scott's #24 is why the Bug Every Phone Call project that the Republicans have launched to Keep Us Safe From Terrorists is useless against actual terrorists.

Terrorists' phone calls would most likely sound like, "Hey, Fred, are you coming to the party on Saturday? Maude is making potato salad!"

Where the Bug Every Phone program would be actually useful would be in making sure Halliburton is never underbid again, and in finding out what the Democratic National Committee is planning in the way of ad buys over the next couple of weeks.

#31 ::: albatross ::: (view all by) ::: September 09, 2008, 10:36 AM:

Scott #27:

I think the (rather old) state of the art is that you destroy (burn) the one-time pads as you use them, and that (modulo screwups) nobody on Earth but your sender and recipient have the one-time pads. An interesting question to ask is how you would know if your one time pads (or computer) had been tampered with--the police sometimes get warrants to silently come in and install keyloggers on computers, and criminals or spies obviously won't care a bit about warrants.

One known weakness for PGP and similar systems is the use of passwords to derive symmetric keys; for PGP, if I capture a copy of your keyring, plus guess your password, I have your private key. (And for encryption, as with encrypted disks and such, I just have to guess your password.) The countermeasures to this in practice involve making the mapping from a password to a key unique to an instance (so you have to guess the passwords for every distinct encrypted file, not once for all of them) and more expensive (by making you do a million iterations of some computation before you get the key out). But that's not a great solution, because doubling the amount of work the attacker does also doubles the amount of work the legitimate user does! To make dictionary attacks really hard, I probably want to set an iteration count so it takes me several seconds after I type the password in until the key is derived.

The underlying problem here is that people aren't very good at making up or remembering good passwords, especially if you know any of their other passwords, as a lot of people use a pattern: ("Xxxamazon123", "Xxxmyspace123", "Xxxgmail123", etc.) A lot of practical cryptanalysis of this kind is done by the police at various levels, and the FBI apparently has a large set of computers on which they do massive password searches (aka dictionary attacks). There are some private companies in this business, as well.

Graydon #15:

In any environment in which the presence of one-time-pads is incriminating, so is the presence of ciphertext coming from you, or worksheets on which you were computing your encryption (which are necessary for anyone not named Gauss or Libby for a lot of paper-and-pencil schemes).

#32 ::: Bruce Schneier ::: (view all by) ::: September 09, 2008, 10:45 AM:

Information on my Cryptonomicon cipher, Solitaire, here.

#33 ::: Liza ::: (view all by) ::: September 09, 2008, 11:02 AM:

Re steganography more than cryptography: Charlotte MacLeod had a book in which a character is continually embroidering French knots on a set of curtains. After her death it's discovered (by accident) that knots' patterns make words in Braille--she was writing her diary.

#34 ::: Carrie S. ::: (view all by) ::: September 09, 2008, 11:09 AM:

#33: That was Gur Snzvyl Inhyg, was it not? Been a while since I've read that series.

#35 ::: Brooks Moses ::: (view all by) ::: September 09, 2008, 11:14 AM:

It is entertaining to consider that my small collection of old, out-of-date books of engineering and mathematics tables might actually have a practical use. (There was a time when I was considering getting a copy of every single edition of the CRC Math Handbook, and though I soon decided that I had better uses for my bookshelf space, I still have a fair number of them.) Though if a correspondent of mine had a similar collection, I suppose it might produce a bit of suspicion. Perhaps better to skip them entirely, and use something like the printed copy of the source code to TeX, which isn't tables but is still surprisingly number-heavy.

On second thought, though, those numbers are very heavily skewed towards 1. A minor version of that skew is also present in the World Book's numbers, though, given any reasonable distribution, and this statistical skew can IIRC be useful in cracking the cipher. Perhaps it would be useful to, instead of copying out all of the numbers on the page, only use the ones that are second (third?) or later digits of numbers counting from the left, which will eliminate a lot of the bias.

Or one could use letters and convert them to numbers, thereby avoiding the need for obvious reference books. A high-school friend of mine could convert letters to numbers in the a=1, b=2, etc., sequence with sufficient ease to be fluent in reading and writing that way.

#36 ::: P J Evans ::: (view all by) ::: September 09, 2008, 11:14 AM:

#31
Why I use passwords that are random strings.

#37 ::: Graydon ::: (view all by) ::: September 09, 2008, 11:15 AM:

Albatross --

Sure, but ciphertext is potentially deniable, and potentially concealable in transmission. For a paper-and-pencil cipher, you really need a woodstove, because that's where all your worksheets go as soon as you have completed the ciphertext.

One time pads, by their nature, have to be stored.

Note that pretty much everywhere, encrypted anything is considered an admission of guilt in practise, no matter what the law says.

#38 ::: P J Evans ::: (view all by) ::: September 09, 2008, 11:19 AM:

Random numbers: Project Gutenberg has text files with pi and e to a million digits. This gives you a nice selection of numbers for practical use (like random-number-generated cable patterns). Merge the files in interesting ways and confuse the bad guys further!

#39 ::: Scott Taylor ::: (view all by) ::: September 09, 2008, 11:29 AM:

Albatross @ 31-
I think the (rather old) state of the art is that you destroy (burn) the one-time pads as you use them, and that (modulo screwups) nobody on Earth but your sender and recipient have the one-time pads. An interesting question to ask is how you would know if your one time pads (or computer) had been tampered with--the police sometimes get warrants to silently come in and install keyloggers on computers, and criminals or spies obviously won't care a bit about warrants.

This is true for one-time pads, where each sheet is destroyed after use - but was not true for old-school codebooks, which were used for a period of time, then destroyed when replaced (on a regular schedule, normally). (OTPs were not developed until the 20th century).

This made these books highly valued, of course (and hard to distribute securely, and annoying in general - one reason why ciphers and OTPs are preferred today).

"Idiot" code systems are secure against casual or limited surveillance, but are susceptible to continued analysis - eventually the code breaks (if every time there's an attack on Lincolnshire, your messages contain reference to the North Field, eventually someone will figure out that North Field = Lincolnshire).

#40 ::: Carrie S. ::: (view all by) ::: September 09, 2008, 11:30 AM:

I am now thinking about a way to convert Solitare to use with a Tarot deck. Use the Magician and the High Priestess (or the Emperor and Empress, or the Fool and the World, or whatever) as jokers, but the problem is what to do with the other majors and the pages. You could just take them out when performing the encryption, or have them count as 0, or perhaps they'd be counted when performing the count cut but if you land on one go to the next "real" card*. Would that help or hurt the security?

* If you're going for "count as 0", then when you hit, say, the Star and your plaintext letter is A, you just write down 1. If they take up space but you skip them, then if you'd land on the Star and the next card is 5 Pentacle (==5 Diamond), your encrypted value would be 19 because the Star punts to the next "real" card.

#41 ::: Alex ::: (view all by) ::: September 09, 2008, 11:31 AM:

Making Light comments threads. As long as you exclude the statistically implausible use of "fluorosphere" and "squamous".

#42 ::: John Mark Ockerbloom ::: (view all by) ::: September 09, 2008, 11:33 AM:

Jim@24: I'd thought that a lot of the impetus of the Bug Every Phone projects (or, more precisely, Bug Every Switch) was traffic analysis: collecting who called whom, and when, and mining that data to decide whom to monitor more closely. For that dragnet purpose, it doesn't matter what's said on the call, or whether encryption is used on the call. You just need to know where each call originates, and where it terminates.

I think that's part of why the administration is so reluctant to have these programs subject to Fourth Amendment scrutiny. If you already have legitimate evidence that certain people might be up to something, you can get a warrant to tap their phones specifically. But it'd be much harder to get a judge under this country's constitution to sign off on monitoring *everyone's* calling patterns; hence the attempts to keep the judiciary out of the loop.


#43 ::: Jules ::: (view all by) ::: September 09, 2008, 11:45 AM:

Why I love Making Light: where else would you find a random and arbitrary cryptography thread which has Bruce Schneier drop in to comment, and nobody seems to notice? :)

#44 ::: John Stanning ::: (view all by) ::: September 09, 2008, 12:09 PM:

Jules - we saw, and bowed silently to the Master.

#45 ::: Terry Karney ::: (view all by) ::: September 09, 2008, 12:16 PM:

For those who want a very pleasant read on the subject.... The Code Book by Simon Singh does a very good job of the history, and up to the publication date (1999) state of the art.

It even has a contest (still active).

#46 ::: Seth ::: (view all by) ::: September 09, 2008, 12:27 PM:

albatross #28: A two-time pad is not necessarily insecure.

C.H. Bennett, G. Brassard and S. Breidbart, "Quantum Cryptography II: How to reuse a one-time pad safely even if P=NP"

#47 ::: Nenya ::: (view all by) ::: September 09, 2008, 12:37 PM:

Jules #43: Like John M. Ford, Bruce Schneier was known to me for ages as a ML commentator before I learned anything about his field of expertise.

#48 ::: Scott Taylor ::: (view all by) ::: September 09, 2008, 12:44 PM:

Jules @ 43 -
Why I love Making Light: where else would you find a random and arbitrary cryptography thread which has Bruce Schneier drop in to comment, and nobody seems to notice? :)

I may be a bit jaded - I knew (if somewhat peripherally) Mr. Schneier many years ago, when he was a member of URSGA...

(oh, btw, Bruce - Dan Quackenbush says Quack! - or maybe just Hi!)

#49 ::: JJ Fozz ::: (view all by) ::: September 09, 2008, 12:45 PM:

Cryptonomicon by Neal Stephenson, is fiction based on some fact, and is an excellent, if arduous, read.

#50 ::: Devin ::: (view all by) ::: September 09, 2008, 01:03 PM:

@Ajay #17:

I think you've pointed out the reason NOT to use the duress signal you suggest: It's much more common to forget to include your security word than it is to actually be captured, even for real spies.

Having a real duress signal makes it easy for your handlers to avoid the mistake you cite.

#51 ::: ajay ::: (view all by) ::: September 09, 2008, 01:03 PM:

where else would you find a random and arbitrary cryptography thread

Excuse me. ML crypto threads are merely pseudo-random.

#52 ::: Jules ::: (view all by) ::: September 09, 2008, 01:04 PM:

My favourite manual cryptosystem:

First use any appropriate polygraphic substitution (e.g. Playfair). This gives a set of letter pairs that can be reasonably easily analysed and turned back into their source message. So we need to break those pairs. For this, we need a grid in which some of the squares are empty and some are filled (e.g. a crossword grid[1]). Write the letters in horizontally. Fill with random letters. Read out vertically.

If you're feeling particularly energetic, repeat.

Decryption is the performed in the reverse order.

For best security, avoid long messages.

[1] You don't actually want to use a crossword grid, particularly not a published one. They're too regular and could be brute forced. One possibility is to take a crossword grid and alter it to make it less regular, e.g. by blacking out the spaces for a pre-selected set of questions.

#53 ::: Raphael ::: (view all by) ::: September 09, 2008, 01:05 PM:

James Macdonald @30:
Where the Bug Every Phone program would be actually useful would be in making sure Halliburton is never underbid again, and in finding out what the Democratic National Committee is planning in the way of ad buys over the next couple of weeks.

Another possible use of that programm is to use the fact that terrorist phonecalls would most likely look the way you described to have officials explain at length why this or that case of Fred chatting with Maud about potatoe salad is really code for some evil terrorist plot, if, for this specific Fred and this specific Maud, that interpretation is politically desired.

#54 ::: Beable ::: (view all by) ::: September 09, 2008, 01:21 PM:

Terry #45: Indeed an excellent book, but it looks here like the contest has long-since been solved.

#55 ::: Earl Cooley III ::: (view all by) ::: September 09, 2008, 01:31 PM:

Detected use of strong crypto can rationalize "probable cause" (or at the very least, "reasonable suspicion"). The problem becomes how to have secure communications that makes traffic analysis more difficult.

I suppose one could have a face-to-face conversation while stark raving naked in a portable Schrödinger's catbox (kitty litter optional), but the use of such extraordinary methods to communicate could justify escalatingly intense levels of pervasive surveillance. You can't win.

By the way, Google indexes Making Light comments, citizen. Have a nice day!

#56 ::: Terry Karney ::: (view all by) ::: September 09, 2008, 01:42 PM:

Beable: Ah well. I wasn't going to try to solve it, so I didn't really pursue the rate of solution.

Earl: A fact for which I am grateful, as there have been things I wanted to copy from here, and the traffic is high enough that even recalling what thread it was in gets pretty hard.

There are other ways of being secure; and the net has made it a lot easier to be steganographic, as well as for simple coms (plaintext ) which are much harder to spot.

Dead-drops, and other such tradecraft are still really useful.

#57 ::: albatross ::: (view all by) ::: September 09, 2008, 01:56 PM:

Bruce #32:

Hi, Bruce!

Do you know what the best current result on Solitaire is? The best one I'm aware of is Paul Crowley's, but I haven't followed it too closely.

Graydon #37:

This is the reasoning behind (IMO very important) attempts to get crypto turned on by default as widely as possible. Ideally, it would be very unusual for a VoIP call to go out in the clear, cordless phone to base station encryption would be ubiquitous and strong, every hard drive would be encrypted, all e-mails would be encrypted, etc.

#58 ::: albatross ::: (view all by) ::: September 09, 2008, 02:04 PM:

Devin #4:

"Rubber hose cryptanalysis" just means beating (or intimidating) you until you hand over your key. It's a way to entirely do an end-run around the crypto being used.

#59 ::: James D. Macdonald ::: (view all by) ::: September 09, 2008, 02:15 PM:

#5: If your threat model allows you to do all these manipulations and send a note to your ally which will be received even though it is intercepted... I don't know what your threat model is.

Shortwave Morse is the classic.

#60 ::: James D. Macdonald ::: (view all by) ::: September 09, 2008, 02:16 PM:

#58: "Rubber hose cryptanalysis" just means beating (or intimidating) you until you hand over your key.

Or the plaintext.

#61 ::: albatross ::: (view all by) ::: September 09, 2008, 02:23 PM:

Jim:

If I have access to the data from which the running key is drawn (say, I know the almanac), then this is pretty trivially breakable with a computer, or more tediously breakable with paper and pencil. Just slide along through the set of possible starting points of the running key against your ciphertext, and look for decryptions that match the expected character frequencies. (If you're doing it by hand, this will take awhile....)

If the running key is unknown but biased in a known way (I love the idea of using Benford's law here; you could also use common rounding rules.), then it will be breakable or not based on how close to uniform and independent the running key is. But note that XORing (or adding mod 26) long English texts together doesn't obscure them--it's generally possible to extract both texts back out. So the running key needs to, in some sense, be more random than normal text. (This also implies something about the idea of doing the Vignerre thing with a long running key from a book.) I don't recall how long the texts need to be to make this work.

#62 ::: Carrie S. ::: (view all by) ::: September 09, 2008, 02:25 PM:

So the running key needs to, in some sense, be more random than normal text.

You could use the first letter of each line, starting on a given page and line.

#63 ::: Graydon ::: (view all by) ::: September 09, 2008, 02:28 PM:

Albatross --

The problem with that is that you'd be required to make public -- as in, public utility, rather than "for profit corporation" -- pretty much all of the network backbone, and then fight a really tough, long term fight to keep someone from installing a back door.

The reason for not encrypting email or hard drives is that these are seen as critical systems, and adding cryptography tends to sharply increase the failure rate; it'd have to be added in hardware somewhere, and that presents a severe design challenge and another severe security challenge with respect to the back doors.

This is more or less impossible in the US given the current legal constructions of liability, too; corporates make the excellent argument that if they're liable for what you say with their email account, their agents must be able to read your email.

(I am, by the way, all for public-utility-izing the entire comms infrastructure.)

#64 ::: Graydon ::: (view all by) ::: September 09, 2008, 02:30 PM:

Carrie --

Nothing that makes sense is meaningfully random.

I suggest rolling dice.

If you need something that can be referenced by multiple parties, I'd suggest astronomical data; least significant digits of spectral results or something like that.

#65 ::: Mycroft W ::: (view all by) ::: September 09, 2008, 02:34 PM:

1) So, what is the legal-beatstick equivalent to "rubber-hose cryptography" called? Cue the recent case where the courts are ruling that in some cases, you are required to turn over the passphrase to any encrypted information on evidence legally acquired/confiscated.

2) If you are using the "have lots of books of tables" method - for "protect me from my so-called friends or boss" level of security (or "doesn't matter tomorrow" security, which is more common) - READ THEM ALL REGULARLY, carelessly by preference. It doesn't matter how many books you have with lotsa-numbers, if only one is worn or stained, with the spine broken to make it easier to sit on a table, and it opens to a particular page, and the rest are pristine...

#66 ::: Mycroft W ::: (view all by) ::: September 09, 2008, 02:38 PM:

Oh, and a shoutout from the old PBM days: use the last digit of the closing stock price for "yesterday" for an agreed set of well-traded companies as the seed/scramble. Who would suspect a guy in a suit and tie (or in geek chic, for that matter) reading the financials?

#67 ::: Clifton Royston ::: (view all by) ::: September 09, 2008, 02:45 PM:

Mycroft @ 66: Quiller, more or less. (Actually, I think in The Quiller Memorandum case the British government was manipulating the closing price of some small stock to transmit codewords.)

#68 ::: albatross ::: (view all by) ::: September 09, 2008, 02:53 PM:

Graydon #63:

For some stuff, getting widespread encryption is hard, because you have to get everyone doing it at the same time. Getting decent encryption in cellphones requires getting the cellphone infrastructure switched over to decent encryption, though a cellphone manufacturer could set things up so that calls from, say, Nokia to Nokia phones did an additional key agreement and encrypted their data end to end. (But cellphone providers and manufacturers are easy to subject to government presure not to strengthen their encryption.) Getting widespread e-mail encryption in use is a pain, because you can't encrypt to me until you're sure I know how to decrypt it. But people could do it, and mostly don't. (But maybe more police state measures all over the place will have an impact on this.)

Other stuff doesn't require any negotiation, or only requires very limited negotiation. Encrypting your own hard drive or files is relatively easy to do, and a bunch of companies (and the feds, too) are establishing policies requiring laptop hard drive encryption, because it's very common for laptops to be lost or stolen. Windows and MacOS have built-in support for this, and there are nice programs that will do it for you, too. Cordless phones (which I think courts have held have no reasonable expectation of privacy) could be made secure pretty trivially by moving them to WPA2 and having the phones and base stations establish shared keys when they are put on the handset to recharge; that would get rid of a huge privacy leak that's waiting for people to exploit it.

Ideally, every website would support https (TLS, encryption for TCP) requests for everything. That would require no great negotiation with anyone, and it would make a whole bunch of data flowing over the internet simply go opaque. As it is, a lot of sites don't support it even when it's crazy not to. Earthlink's webmail doesn't support https for anything but the login screen.

My take on this is that the main problem is that adding casual, automatic encryption impacts performance, complicates design (because key management is usually a big pain to get right), and has very little obvious benefit, at least until it's being done everywhere.

#69 ::: Earl Cooley III ::: (view all by) ::: September 09, 2008, 03:15 PM:

I wonder if there is some interesting way to leverage Bible Code pseudomath instead of using almanacs.

#70 ::: Clifton Royston ::: (view all by) ::: September 09, 2008, 03:36 PM:

Ideally, every website would support https (TLS, encryption for TCP) requests for everything. That would require no great negotiation with anyone, and it would make a whole bunch of data flowing over the internet simply go opaque. As it is, a lot of sites don't support it even when it's crazy not to.

I haven't been running any kind of high-volume webserver recently, but as I recall, if you don't have cryptographic hardware installed in the server - and 99% of webservers don't - using SSL takes a non-trivial chunk of the CPU per session. That means fewer connections you can support on a given machine, which for very busy sites means either adding more servers - maybe two or three times as many - or else adding funky add-on cards to them. The latter is also a big pain for ISPs or hosting companies which want to deal with lots of precisely identical hardware. Given Gmail's scale, I suspect it took a pretty substantial investment for them to announce the checkbox feature where everyone can easily turn on and require https.

I'm not saying it's bad - on the contrary, SSL is Good! - but there's a cost there which is hidden from the end-user's perspective. That's one reason we don't see it everywhere all the time.

#71 ::: Lila ::: (view all by) ::: September 09, 2008, 03:46 PM:

It would probably be possible for me and some of my acquaintances to carry on a converation consisting entirely of allusions to shared experiences, obscure bad movies, and fanfic.

There was an episode of ST:TNG that included a similar idea ("Darmok and Jalad at Tanagra"). See also classic Chinese poetry.

(Come to think of it, bad fanfiction would be a great place to hide all kinds of things. The Sturgeon's Law Cipher!)

#72 ::: James D. Macdonald ::: (view all by) ::: September 09, 2008, 04:07 PM:

For all we know half the stories at Fanfiction.net read (if you know how to read them), "Shipment of weapons-grade plutonium to leave Minsk at 0300, track 5. Only two guards."

#73 ::: Madeline F ::: (view all by) ::: September 09, 2008, 04:26 PM:

If someone's out there looking for books of tables, I suggest the stuff from MAKE magazine. I picked up Handyman In-Your-Pocket at the last MakerFaire, and was somewhat saddened to figure out that it was mostly stuff like "what angle roof needs what strength and spacing of beams in what climate". So far only useful to me as a paperweight. But now I'm mollified, because it is pocket-sized, and relatively cheap, and packed to the gills with tables of numbers; and it isn't completely useless, so many of the people I'd want to talk to have an excuse for having it around.

#74 ::: Seth ::: (view all by) ::: September 09, 2008, 04:26 PM:

A few years ago, somebody had a filter that turned plaintext into typical-looking spam.

#75 ::: Beable ::: (view all by) ::: September 09, 2008, 04:30 PM:

Lila #71: A friend of mind has a theory about this in the far future of the Babylon-5 'verse. He figures that the Vorlons honestly thought they were being transparent and clear when they were talking to the humans ...

One million years from now when humans are the new Vorlons:

Human (in an encounter suit): Ok, so, here's what you need to know. There will be a big battle. You will need to pick sides. We're the good guys, so we'll tell you everything you want to know. Go on, ask me anything.

New younger race: Darmok and Jalad at Tinagra?

#76 ::: Mycroft W ::: (view all by) ::: September 09, 2008, 05:01 PM:

#67 Clifton: Exactly the opposite, in fact, for exactly that reason - low-volume-traded stocks are susceptible to manipulation (not likely in the PBM case, but in traditional encryption, there's more money involved, so you can afford to do that) and also have a non-negligible chance of No Trading on that account today, meaning the probability of the last digit (well, all of them, really) being the same as yesterday (or last week, for that matter) is much higher than the one-in-ten it would ideally be.

But that's one more book to find for the pile, so thank you.

#77 ::: Eric K ::: (view all by) ::: September 09, 2008, 06:37 PM:

As noted by several people upthread, this is trivially crackable by anybody who has your book of numbers and a computer. In this case, "trivially crackable" means "well under a second."

Assume there are 500 pages in your book, and each page contains 100 lines of numbers. That's 50,000 possible keys to try.

For each key, decode 10 letters of the ciphertext. Compare those 10 letters to a table of English letter frequencies. Do you get "zqadtv.mlp"? It's not English text. Try the next line. At a billion instructions per second, this won't take long. English text is incredibly distinctive, so your computer will have no problem recognizing it.

If you're impatient, sort the lines of numbers, and store them in a trie. Decode the first character of the ciphertext using the digits from 1 to 10. Pick whichever digit decodes the first letter to "E", and walk down that branch of the trie recursively. If that results in nonsense, try the other branches in order of letter frequency: "EATOIN SHRDLU".

With a reasonably large database, you will be able to decrypt the message as fast as you can type it into your computer.

What if you don't have an electronic copy of the table of numbers? First, see if you can find out what book is in use. (This is left as an exercise for the reader.) If that fails, just pick the 200 best-selling books of numbers, and run them through an OCR system like that of Google books. You'll have a ton of OCR errors, but that's OK--you can adapt the algorithm to work with error-filled tables; it will just take longer to run.

If you want a reasonably strong pencil-and-paper cipher, follow Bruce Schneier's Solitaire link upthread.

#78 ::: Jules ::: (view all by) ::: September 09, 2008, 06:55 PM:

Clifton @70:

I haven't been running any kind of high-volume webserver recently, but as I recall, if you don't have cryptographic hardware installed in the server - and 99% of webservers don't - using SSL takes a non-trivial chunk of the CPU per session.

It's not so much of a problem these days. Sure, it would add overhead, but most web server applications are IO bound, so doing something that uses CPU wouldn't be too much of an issue.

No, the *really big* problem is that SSL only allows you to have one domain per IP address, whereas 99.something% of web sites share their IP address with one or (more usually) 50 others.

We have a real shortage of IP addresses, and if every web site suddenly decided to do SSL, we'd run out pretty quickly.

#79 ::: Kevin Riggle ::: (view all by) ::: September 09, 2008, 07:38 PM:

Jules @78: Well, you /can/ run more than one site off the same IP, but whichever ones aren't in the certificate will make Firefox put up a BIG ANNOYING WARNING MESSAGE that takes 3+ clicks to work around. (Not that I'm annoyed or anything.)

It seems to me that the best solution to this is to extend SSL to let you list multiple sites in the certificate, but I haven't looked into it closely.

(Given that I'm trying to run four-ish Web apps off a sad little hosted VM with 128MB of RAM that's running near capacity, I won't be enabling SSL on all my sites any time soon, because the overhead would kill it; there's only one that really needs it. I do send grumpy e-mails to web sites I run across which really should use SSL and don't, like the VoIP provider I was looking at a few days ago, and I encourage others to do the same. :-)

#80 ::: Randolph ::: (view all by) ::: September 09, 2008, 07:39 PM:

Jules, #78: obviously we must all convert to IPv6. See? The Chinese are really just doing us a favor.

I'm sorry, I have yielded to temptation.

#81 ::: Lila ::: (view all by) ::: September 09, 2008, 07:48 PM:

Jim @ #72: and the thought of all those NSA/CIA flunkies being assigned to read *everything* posted on fanfiction.net, hour after hour, day after day, makes me want to bake up a big ol' Schadenfreude Pie.

#82 ::: Erik Nelson ::: (view all by) ::: September 09, 2008, 08:00 PM:

Remember, there must be no starch in the collar!

#83 ::: Devin ::: (view all by) ::: September 09, 2008, 08:28 PM:

Aside to Albatross @ 58

I know what rubberhose cryptanalysis is. When I wrote that comment, the OP referenced "rubberhose cryptography." It appears Jim's fixed that, or perhaps I was hallucinating in the first place (maybe Jim will tell us which?) Please do re-read my comment in light of that, so that I look like a smartass with a little bit of clever instead of confused and nonsensical.

Also, my original point there was really that using nontrivial pen and paper crypto probably makes your ciphertext a harder point of attack for the sorts of people likely to be trying to attack it than any other link in the chain. In my life, the sorts of folks I'd be concerned about (if I had concerns, which right now I don't) are like business rivals, potentially local police, the odd reporter, neighborhood kids, personal rivals, that sort of thing. Some of those people (cops and reporters for sure) are very good at social engineering and may have considerable resources at their command for attacks on human links, but none of them tend to have cryptanalytic resources.

Your advice about class breaks is extremely relevant, however. This sort of cryptography is very useful when you have a day or even a week of messages to pass, but if it remains in use... It may take local cops six months to get the FBI to send your stuff to the NSA and have it decrypted, but once they've done that, assume that they can decrypt any further messages as fast as they need to. Further, cut that lead time in half for any country without the US's peculiar law-enforcement/intelligence rivalry, and reduce further as appropriate to the organization/country.

#84 ::: P J Evans ::: (view all by) ::: September 09, 2008, 09:38 PM:

#83
I saw it as 'cryptanalysis'. (I was snickering at the list of methods, something which tends to make it stick in the mind.)

#85 ::: Terry Karney ::: (view all by) ::: September 09, 2008, 09:59 PM:

If I were looking for a book to extract numbers from... I'd use an out of date copy of the Machinist's handbook. The tables are dense, there are sets/directions which avoid the Benford paradox, and it will have a reason to be worn.

It's also not as subject to the sort of brute force described by Eric K., (though most of the values are the same, some of the ordering is different) you can choose a column, instead of a row... or checkerboard the selection criteria (even build a version of the Vingiere cipher to manufacture the key).

And they are both inexpensive, and easy to come by.

#86 ::: Sandy B. ::: (view all by) ::: September 09, 2008, 11:27 PM:

#84 You were snickering... I was creeped out as hell.

I dunno, these days I've gotten sensitive or something.

#87 ::: Brooks Moses ::: (view all by) ::: September 10, 2008, 12:22 AM:

Devin @83: FWIW, I don't actually directly recall what I saw in the original post, but I remember that your joke made perfect sense to me the first time that I read it.

#88 ::: ajay ::: (view all by) ::: September 10, 2008, 06:23 AM:

85: but it doesn't pass the test of being an obvious, unsuspicious book to have lying around (for most of us anyway).
Phone book?

#89 ::: Scott Taylor ::: (view all by) ::: September 10, 2008, 07:08 AM:

ajay@88 -
85: but it doesn't pass the test of being an obvious, unsuspicious book to have lying around (for most of us anyway).
Phone book?

hmmm... perhaps not, but it's also not a book that would go amiss on most shelves, especially given the miscellany many of us seem to accumulate - I've got a copy (22nd edition) that I picked up cheap in a "going out of business, moving someplace warm" bookstore sale recently - it's currently sitting on my shelves next to Kipling, Paine, the Poetic Eddas, Lies My Teacher Told Me, and some SimCity manuals (otherwise known as Nonfiction: unsorted...).

(and I live in an apartment, so it's not like there's a workshop downstairs for it to go with).

(Note that with traffic analysis, and some B&E work, it might become obvious if everyone you communicated with via e-mail had a copy of the 25th edition of the Machinists Handbook somewhere in their library).

#90 ::: Dr. Tom Bibey ::: (view all by) ::: September 10, 2008, 07:09 AM:

Everyone worries about privacy. I understand that, but with my blog, I worry 'cause I can't get anyone to find me.

As far as I know I am the only physician bluegrass fiction writer on wordpress.

Maybe I picked the wrong genre.

Dr. Tom Bibey

drtombibey.wordpress.com

#91 ::: Dave Bell ::: (view all by) ::: September 10, 2008, 12:09 PM:

The thing is, this system gives decent short term security, expecially if you keep the messages short. The key may be susceptible to a brute-force attack: trying every common book of data tables. If you're attracting the attention of people who can do that, you're going to be in trouble anyway.

If you want to stop teacher or mom reading a diary, it doesn't need to be this complicated. The simple Julius Caesar cipher (ROT-13 is an example) is too simple, but you don't need anything much more complicated. It's the sort of thing you can learn to do in your head as you write, even if you use a keyword to jumble the alphabet.

It stops people just picking up your diary and reading it.

The method described is good enough to protect a message for a few days, even against government-level attack. Especially if the messages are short. But if you're up against a government, there are all sorts of ways they can mess things up for you. Lose the letter in the mail for a few days, and your escape plans are FUBARed.

If you're entangled with heavy-duty Spooksville, you almost need to play by what some have called "Moscow Rules". And anything like that can be a giveaway.

That sort of situation needs somebody on the outside. It is very unusual for a wholly internal resistance to survive against a Police State.

#92 ::: sherrold ::: (view all by) ::: September 10, 2008, 12:56 PM:

So, MIJI (Meaconing, Intrusion, Jamming, and Interference) is supposed to be used against electronic signals (navigation, comms, etc.), but now I'm trying to figure out plausible miji scenarios against the crypto examples you've all come up with.

#93 ::: Terry Karney ::: (view all by) ::: September 10, 2008, 12:59 PM:

ajay: What Scott said. I used to be a machinist, so my having a couple of different editions is sort of normal.

But it's a way cool book for other things, and anyone who has a shelf of useful information ought to get one. Unless one is doing CNC machining, with with a powered mill, there's no need to get anything more recent than the '50s, and it's not that strange a thing. The articles on acme threading are interesting all by themselvses, as are the disquisitions on the various uses of allow steels.

But I digress.

#94 ::: Mary Aileen ::: (view all by) ::: September 10, 2008, 02:06 PM:

Terry (93): But I digress.

If we didn't digress, this wouldn't be the Making Light we know and love.

#95 ::: Lee ::: (view all by) ::: September 10, 2008, 03:42 PM:

Dave, #91: True, if you just want to keep your mother from reading your mail, the simple substitution cipher I employed in college (based on Tolkien's Dwarvish runes) works just fine. But I get the impression that this post was about rather more complicated things, and situations requiring much heavier security.

#96 ::: debcha ::: (view all by) ::: September 10, 2008, 04:54 PM:

Ajay, #88: "but it doesn't pass the test of being an obvious, unsuspicious book to have lying around (for most of us anyway)."

Phone book?

I haven't had a phone book in my home since I first got wifi, lo these many years ago. To be fair, that may be an artifact of living in large cities (=ginormous phone books + high-rent-induced small apartments).

#97 ::: mpo ::: (view all by) ::: September 10, 2008, 08:39 PM:

this describes the Moscow Rules

#98 ::: Michael Turyn ::: (view all by) ::: September 11, 2008, 02:00 AM:

I'm glad rubber-hose cryptanalysis was mentioned; the first time I heard about strong encryption (early 90s, late 80s?) I responded with, 'Congratulations, the incentive to torture people just went way up.'

Yes, there are other reasons why people are being tortured in my name, mostly because it makes some people look effective and all butch and electable and such, but maybe torture consciousness is encouraged by the presence of one situation in which it 's easy to think that it would be all you've got---it knocks the dust off that tool, making it stand out just a little bit more....

#99 ::: Terry Karney ::: (view all by) ::: September 11, 2008, 11:06 AM:

Michael Turyn: No, I don't think strong cryptography increases the odds/incentives for torture, because the number of cases in which it comes into play hasn't gone up to any great degree.

We expect spies, and terrorists and crooks (more or less) to do things to hide their activities. The amazing thing is how rarely they use strong encryption (or good tradecraft).

#100 ::: albatross ::: (view all by) ::: September 11, 2008, 01:12 PM:

Lee #95:

Yeah, any commercial encryption, even the lame ones that often come with word processors and such, will keep your prying mom out of your files. That should be done on a computer unless you're worried about keyloggers or some such thing.

Terry #99:

That's the sense I have, too. Some criminals manage to use good crypto, but most of them apparently use crappy crypto. I suspect part of this is that they don't know the difference between good and bad crypto, but laziness and the fact that it hasn't bit them before probably also come into play.

One of the really hard things about trying to make casual eavesdropping/spying harder is that if you produce a strong encryption product or strong anonymizing service, some notable subset of the folks who want to use it will be obvious bad people. Child pornographers need anonymity more than random citizens commenting on weblogs under a pseudonym.

I suspect that there's a kind of J-shaped curve describing well being of the society as strong cryptography becomes widespread--the early adopters are some combination of cryptographers and privacy fanatics and bad guys, and total social well being likely goes down. Then, further adoption makes total social well being go back up, and eventually it ends up better. (Shorter me: We're best off when everyone has privacy, not too bad off when nobody has privacy, and in the worst state when only the bad guys have privacy.)

#101 ::: albatross ::: (view all by) ::: September 11, 2008, 01:29 PM:

Sherrold #92:

The obvious one here is replay attack, and more broadly, reordering/delaying messages. If I note that you're sending messages that set up meetings, I can delay one till I figure out where the meeting is supposed to be, then send it to your recipient and be waiting for him. Or I may be able to cause him to return to the same place twice.

Depending on the cipher, you can sometimes splice together information or alter information in the ciphertext without knowing the plaintext, or without knowing all the plaintext, or without knowing the key. For example, in Jim's cipher above, suppose you know that the first word in the ciphertext is "Don't," and want to change it to "Won't." D is encoded as 15, W is encoded as 27, so if you add (without carries) a 1 to the first number in the ciphertext, and a 2 to the second number, you change the ciphertext from "DONT LET THEM SCARE YOU" to "WONT LET THEM SCARE YOU". (That's a pretty standard thing to do to this kind of cipher.)

I suspect you can use this, in practice, to test guesses about the plaintext. In a real-world system, there will be encryption errors. If you cause a rare garbled message, it may not be detected as an attack. So, if you think you know what a given word at some place in the text should be, alter it into a similar word using this technique, and then observe the reaction of the receiver.

It's also obviously easy to "jam" the transmissions by blocking transmission of anything that looks like ciphertext. More interestingly, it's easy to wait till you think they've got something interesting to send, and then silently block the ciphertext. (99% effective way to prevent the use of encrypting telephones in practice: Introduce enough line noise to mess up the call whenever you detect ciphertext. Eventually, the users will give up and just use normal unencrypted voice, if they are given a choice.)

#102 ::: Henry Troup ::: (view all by) ::: September 11, 2008, 10:16 PM:

Lo, many years ago, more than forty, a British comic used to run cyphered stories available only to the "club". My father and I spent a cheerful couple of hours breaking the transposition cypher.

This particular one is a little cooler than Caesar: you need two words that total 13 letters with no repetition. e.g.

DOLPHINSAFETY
then write the remaining letters in order
BCGJKMQRUVWXZ

and encode straight up and down.

wurz! Cqgz xec ecsb xc seougg.

Useless for anything serious ... although short messages - like passwords for something stronger ... are hard to break.

#103 ::: David Dyer-Bennet ::: (view all by) ::: September 13, 2008, 04:23 PM:

Getting a secure computer: Boot a public system, like a demo in a store, off optical or USB media. Depending on the level of opposition you're facing, booting *your own* computer that way might be good enough (obviously not if they've installed a *hardware* keylogger).

Software for Palm, phone, or Nokia tablet platforms may also make it harder to install a hardware keylogger. These probably also protect you against the bit where they can tell what you're typing from the sounds.

#104 ::: Mycroft W ::: (view all by) ::: September 15, 2008, 03:36 PM:

#103: Optical, or WRITE-ONLY USB. There are way too many compromising ways to infect the USB drive, and then you're using a "known secure" system, which is worse than using an insecure system.

Unfortunately, hardware write-lock USB keys are harder to find these days.

But one big key, which I'm glad to see others mention here, is "how long?" and "against whom?" Unfortunately, if "how long?" > a week, the law is getting to the point where strong cryptography is no longer useful, because they'll just put you in jail/force decryption through discovery requests anyway. Strong Crypto == good for anything involving money, because "against whom?" is "about 10 000 people who are getting paid to get banking information from people like ME."

#105 ::: Mary Aileen sees old maybe-spam ::: (view all by) ::: May 08, 2010, 10:24 AM:

#90 makes a stab at being on-topic, but it's his only post here and is touting his blog.

Welcome to Making Light's comment section. The moderators are Avram Grumer, Jim Macdonald, Teresa & Patrick Nielsen Hayden, and Abi Sutherland. Abi is the moderator most frequently onsite. She's also the kindest. Teresa is the theoretician. Are you feeling lucky?

If you are a spammer, your fate is in the hands of Jim Macdonald, and your foot shall slide in due time.

Comments containing more than seven URLs will be held for approval. If you want to comment on a thread that's been closed, please post to the most recent "Open Thread" discussion.

You can subscribe (via RSS) to this particular comment thread. (If this option is baffling, here's a quick introduction.)

Post a comment.
(Real e-mail addresses and URLs only, please.)

HTML Tags:
<strong>Strong</strong> = Strong
<em>Emphasized</em> = Emphasized
<a href="http://www.url.com">Linked text</a> = Linked text

Spelling reference:
Tolkien. Minuscule. Gandhi. Millennium. Delany. Embarrassment. Publishers Weekly. Occurrence. Asimov. Weird. Connoisseur. Accommodate. Hierarchy. Deity. Etiquette. Pharaoh. Teresa. Its. Macdonald. Nielsen Hayden. It's. Fluorosphere. Barack. More here.















(You must preview before posting.)

Dire legal notice
Making Light copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014 by Patrick & Teresa Nielsen Hayden. All rights reserved.