More on the Unabomber's Code

Last month I posted about Ted Kaczynski’s pencil-and-paper cryptography. It seems that he invented his own cipher, which the police couldn’t crack until they found a description of the code amongst his personal papers.

The link I found was from KPIX, a CBS affiliate in the San Francisco area. Some time after writing it, I was contacted by the station and asked to comment on some other pieces of the Unabomber’s cryptography for a future story (video online).

There were five new pages of Unabomber evidence that I talked about (1, 2, 3, 4, and 5). All five pages were presented to me as being pages written by the Unabomber, but it seems pretty obvious to me that pages 4 and 5, rather than being Kaczynski’s own key, are notes written by a cryptanalyst trying to break the Unabomber’s code.

In any case, it’s all fascinating.

Tags: , , , ,

Posted on January 3, 2007 at 6:59 AM • 27 Comments

Comments

Mac • January 3, 2007 8:02 AM

“In any case, it’s all fascinating.”

Yes, it most certainly is! I find it incredibly engrossing. Kudos and Thank You.

Milan • January 3, 2007 9:08 AM

Do you think this has actually never been cracked, or is it more likely that it was cracked in a way that was never made public.

You would expect that a pen-and-paper cipher invented by a non-cryptographer would not be able to stand up to analysis from someone with access to advanced techniques and lots of computing power.

Carlo Graziani • January 3, 2007 9:27 AM

The routing diagram makes it look like a transposition cipher, but I guess there are substitution rules as well. So, is it a hybrid of some sort? Bruce, do you have the algorithm now?

Bryan Geraghty • January 3, 2007 9:31 AM

Milan,

I don’t remember where it was but I’ve read that most groundbreaking encryption algorithms are designed by people who are not part of the cryptology field. I’m not sure how much truth there is to that but it’s an interesting prospect.

greg • January 3, 2007 9:55 AM

@Bryan

Err i don’t think so-certinaly non come to mind. Most would be easily broken. We have a lot to learn, but someone “unskilled” in the arts will make all the clasic mistakes.

But if you want to make a hard cypher I belive that the trick is to use more rounds than anything else.

CuriousG • January 3, 2007 9:58 AM

One thing I have always wondered about: couldn’t you take a weakly encrypted message and add random characters at frequent but randomly assigned positions?

To decrypt, you would need to filter them all out. At the same time, their presence would make it much harder for someone who thought the whole message was real to decrypt. Or would it?

Bruce Schneier • January 3, 2007 10:05 AM

“Do you think this has actually never been cracked, or is it more likely that it was cracked in a way that was never made public.”

The story is that they couldn’t crack the code, until they found the key amongst his papers. We know that it’s been cracked, because decrypted evidence was introduced at the trial.

“You would expect that a pen-and-paper cipher invented by a non-cryptographer would not be able to stand up to analysis from someone with access to advanced techniques and lots of computing power.”

He was a math professor, which gave him a little more saavy than most. Pencil-and-paper ciphers can be very difficult if you don’t know the algorithm….

Nilz • January 3, 2007 10:25 AM

I would like to know if the problems for the codebreakers were mainly due to security by obscurity (the algorithm was unknown) or due to a really good algorithm (cryptoanalysis did not work).

Is there any easy to use (given “the math is strong with oneself”) pencil-and-paper cipher?

Or even more interesting would be an algorithm for this situation: Alice, Bob and Eve are sitting around the same table. Alice wants Bob to know her phone number but not Eve. So Alice and Bob start talking numbers … As long as all of them are equally good with math and Eve is unable to remember or record the whole conversation, could it be secure and also easy to compute?

Bruce Schneier • January 3, 2007 10:27 AM

“The routing diagram makes it look like a transposition cipher, but I guess there are substitution rules as well. So, is it a hybrid of some sort? Bruce, do you have the algorithm now?”

It’s a combination of a transposition and substitution cipher, with some message expansion.

I don’t have the entire algorithm. All I have are the pages that have been made public on that website.

Bruce Schneier • January 3, 2007 10:29 AM

“One thing I have always wondered about: couldn’t you take a weakly encrypted message and add random characters at frequent but randomly assigned positions?”

Of course, this kind of message expansion will make an algorithm harder to break.

In general, computer cryptography has ignored message expansion techniques. We don’t have the freedom to make ciphertext significantly larger than plantext, so we work on techniques that keep encrypted messages the same size as unencrypted messages.

MikeA • January 3, 2007 10:30 AM

@Bruce
“We know that it’s been cracked, because decrypted evidence was introduced at the trial.”

Not to get my head too far into the tinfoil hat, but “decrypted evidence”, with explanation of decryption method watered down for the courtroom, presented against a not-exactly-sane defendant, is a fine thread to hang a word like “know” from.

In my (limitted) experience as a juror, I’ve seen some pretty outrageous claims for the provenance of evidence. O.J. is probably the most notorious case of the prosecution being called on it.

Bruce Schneier • January 3, 2007 10:31 AM

“I would like to know if the problems for the codebreakers were mainly due to security by obscurity (the algorithm was unknown) or due to a really good algorithm (cryptoanalysis did not work).”

Primarily the former, I think.

But in this sort of instance, security by obscurity works.

Milan • January 3, 2007 10:35 AM

@greg

“We have a lot to learn, but someone “unskilled” in the arts will make all the clasic mistakes.”

This may be the wrong place to ask, but I would be very interested in knowing what the ‘classic’ mistakes in cryptography are.

Fred P • January 3, 2007 10:39 AM

@CuriousG-

I’m hardly a cryptographer, but here’s a stab:

Problem: The purpose of a cryptographic system is to communicate with another entity who has the information to decode it. How would that entity determine which characters were part of the message, and which ones were noise? There are possible approaches I can think of:
A: There is an algorithm to this “random noise”, which can be determined by the intended recipient.
As the algorithm is either a static secret, or it has a unary key, or a binary key (such as a public/private key system), it would seem that this approach is little more than applying two (presumably weak) cryptographic algorithms instead of one.
B: The “random noise” is easy to separate from the actual text (possible example: between two digits, the noise would need to be a letter; between two letters, the noise would need to be a number, etc.). In this case, once the attacker has figured out that you’re using such an obfuscatory algorithm, if should be easy to change how the attacker is searching for plain text to take this into account.
C: The “random noise” is non-algorithmic, and is difficult to discern from the actual text. In this case, the receiver would have difficulty getting the message. In this case, you presumably have a failed cryptography system, since to guarantee transmission, you’d need to send your message multiple times, using different “random noise” which would make it easy for either the receipent or the attacker to remove that noise.

So I think that in the best case, you’d have a message which effectively is using two weak cryptographic algorithms rather than 1. Personally, I’d choose one strong one instead.

Fred P • January 3, 2007 10:42 AM

@Milan-
Personally, I’d suggest starting by purchasing a copy of Bruce Schneier’s Applied Cryptography. I hope that the moderator doesn’t mind the plug 🙂

greg • January 3, 2007 10:51 AM

google broken or weak cyphers (usally not enough rounds). But the best place is the current flavours of DRM. Both CSS and AACS are good ones. True crapola and its deployed.

The most common mistake is to come up with a real strong cypher and leave the key on a piece of paper with the cypher text. No really.

This is what the current DRM flavours all do. Encryption is not the weak link. Thats the commen miskate to assume that a “secure” cypher is a secure system. aka side channel attacks on RSA and the like.

However I’m not a real cryptologist and have probably made some of the clasic miskates as well.

Greg

Valdis Kletnieks • January 3, 2007 11:20 AM

There was a very nice (sort of) pen-and-pencil crypto scheme called Solitaire, presented in Neal Stephenson’s “Cryptonomicon”. I believe it’s developer is lurking here someplace… 🙂

K. Signal Eingang • January 3, 2007 11:32 AM

@Fred P, Curious G

Random garbage characters in the plaintext would work well in a case like this. For one thing, Ted’s both the author and reader of his own notes, so he only needs to write mnemonics or coded messages – just enough for him to recall the important parts of whatever he’s writing. He doesn’t have to worry much about accidentally changing the meaning of the message by inserting noise, or in having any method to extract the noise afterwards.

So a plaintext of “LXEFT BOLMB AT FOZURTY LONE FIDFTY MAIND STREBET”, suitably encrypted, is going to be somewhat harder to analyze via computer, because the plaintext doesn’t look very much like plaintext. But the person who wrote it will get the gist – “oh right, 4150 Main St!”
(Even better is if 4150 Main is actually secret code for 5041 Elm)

Clive Robinson • January 3, 2007 12:02 PM

@Milan

“You would expect that a pen-and-paper cipher invented by a non-cryptographer would not be able to stand up to analysis from someone with access to advanced techniques and lots of computing power.”

Have a look at

http://www.schneier.com/blog/archives/2006/12/unabombers_code.html#c129479

For a possible reason why. The original post was in two parts but it did not read to well (Opps on my part).

Where it say’s

“past one (fairly) reliable method ”

It should say,

“past one (fairly) reliable ciphering method”

Just remember that one of the only “provably secure” cipher systems is the One Time Pad, you cannot break it unless you do have the key (which is a random string atleast as long as the message).

You can make a One Time Pad with a couple of dice and a bit of squared paper and a lot of patience 😉

dragonfrog • January 3, 2007 12:39 PM

@ Nilz

Last month I spent a bit of time trying to figure out if you could come up with any complete cryptographic protocols based on pen-and-paper ciphers, that would stand up to computer cryptography.

I did find a nice implementation of RC4 as a pencil and paper algorithm(must be a pencil and some sturdy paper – there’s lots of erasing). It was especially elegant if you used a pair of chessboards instead of paper to represent the internal state of the RC4 engine.

I didn’t get as far as a good hash for a signature, but I did conclude (preliminarily) that you could probably just about work RSA with pen and paper, but it would be hella slow and error-prone, and you’d want to avoid it as much as possible. I have yet to test this in practice, as my appetite for punishment is limited

Given that, you could do something like WPA’s TKIP to rekey your RC4 engine, and cut down on your need for public key operations.

Actually, I think I noted an error in the posted RC4 implementation. It may not actually reduce the security, but it’s not the exact same starting state as the documented Arcfour algorithm. It would be easily corrected though. Assuming it’s not actually my mistake; the posted one could be right.

Frederick • July 6, 2008 9:17 AM

“This may be the wrong place to ask, but I would be very interested in knowing what the ‘classic’ mistakes in cryptography are.”

I would very much like to know this as well. Please do tell.

Frank • August 13, 2008 6:10 PM

A very popular book “The memory book”, by Harry Loraine and Jerry Lucas which came out about the time the Unibomber started, had a system for remembering numbers.
I called the F.B.I. in the early nineties telling them that his latest letter threatening to bomb the L.A. airport, with a return address of “549 wood street”, could be spelled as “L.A. Airport” with the Loraine/Lucas system.
At least the abreviated version. “L.A. ARPT which the airport itself uses.
In fact, If “Uni” means “One”, if you translate “wood” it is the number “1”!
They wood not listen to me. (Sorry, little joke)
I asked them for the nine digit number so that I could see if it meant anything but they wouldn’t give it to me….
So, I can’t make sense of the number now that i see it. But if anyone is interested, his 9 digit code (550-25-4394) according to the book translates to (L L S or Z – N L – R M B R)

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.