Posted by: jonkatz | May 6, 2011

Cryptanalysis of amateur ciphers

I was interviewed a while back for an article on slate.com about the FBI’s recent request for help in decoding an encrypted message found on the body of a murder victim. In the course of my discussion with the reporter, she asked me why ciphers are so hard to break; in response, I pointed to the amazing successes by the Allies in World War II in breaking, among others, the Enigma code. Maybe that was a mistake, because she then asked me why amateur ciphers (like the Beale cipher, the cipher used by the Zodiac killer, and the one the FBI is interested) in were so secure, and why amateurs were apparently just as good at designing ciphers as, well, real cryptographers. At one point it even sounded as if she were suggesting that we should use amateur ciphers to encrypt our communication on the Internet…

In an attempt to correct these misimpressions, I came up with a list of reasons why it should not be surprising that breaking the Enigma code (to take one example) was easier than breaking many of the “unsolved” amateur ciphers that are out there or, conversely, why it is easier to design a “secure” amateur cipher but very difficult to design a secure encryption scheme for, say, military applications:

  • Fundamentally, most amateur ciphers are not really encryption schemes in the sense that they are intended to hide information but are not usually intended or used to communicate information between two parties. In particular, amateur ciphers don’t usually require there to be a decryption algorithm (whether efficient or not). This is doubly true for ciphers that are intended purely as “puzzles” (e.g., in the case of the Zodiac killer).
  • Modern ciphers are required to be secure even if the algorithm is known; secrecy of the key should be enough. In contrast, amateur ciphers have the advantage of using a completely unknown algorithm. (Is this an argument that “security by obscurity” can be beneficial?)
  • Modern ciphers are required to be secure even when the same key is used to encrypt tons of data of a relatively predictable form (e.g., military orders in German), and even if the cryptanalyst has lots of plaintext/ciphertext pairs. Amateur ciphers are typically used to encrypt a very small amount of data of completely unknown form (even the underlying language may not be known), and certainly no plaintext/ciphertext pairs are available.
  • For any given amateur ciphertext, it is possible that a “solution” is not even possible. For example, there is no reason why someone who really wanted to hide a small amount of text could not just use some version of the one-time pad, writing the key on a piece of paper stored in one location, and the ciphertext on another piece of paper stored somewhere else. Constructing an “unbreakable” cipher is easy if efficiency is not a concern. I wonder also about many of the ciphers intended purely as “puzzles” — who says that a solution is possible? Or maybe the person who generated the ciphertext made several mistakes in the course of writing it out, to the point where even the correct solution would not be convincing?
  • Finally, it is clear that less effort is being spent on cryptanalysis of most amateur ciphers than was expended on breaking Enigma. (This is not an argument for why it is easier to break Enigma, but justifies why Engima was eventually broken even though the Beale cipher is not.)
Advertisements

Responses

  1. I think you have only just touched on the real reason so many amateur ciphers have gone unbroken in your third point. In my opinion the real reason for so many famous amateur ciphers going unbroken is down to the limited amount of cipher text available. Generally there is only a very small quantity of ciphertext available (often just one or two short messages). This excludes many types of attacks, such as known plaintext attacks. Further, for short samples, the inherent entropy of language combined with the entropy of the key and even the encryption algorithm if it is kept secret, yield a ciphertext which is almost entirely random. Given many more samples of cipher text, or worse yet a few plaintext-ciphertext pairs, many of these schemes would likely be easily broken.

  2. Two more reasons: 1. far less effort has been expended in cracking amateur ciphers by professional cryptanalysts. 2. selection bias — millions of amateurs have created ciphers; we only hear about the ones that have withstood scrutiny.

  3. Can I take this opportunity to express my disappointment that CRYPTO 2011 PC has not yet made the accepted papers list available online even after *so many* days since the notification?

    It is amazing to me people don’t understand that youngsters in our community wait impatiently to for this list. Is it really that hard to understand this concern?

    Reasons such as “authors have not yet confirmed the final titles and author list of their papers” are not good enough to not publish this list. The list can be published under the “preliminary list” title so people can see what got in and what did not.

  4. @PissedOff, hmm, I guess that doesn’t resonate with me (if you already know whether your own paper got in or not). Then again, I’m not sure I’d qualify as a youngster, so maybe I just don’t understand. I’m happy to have it explained to me. I’m ready to believe that it’s a big deal — do you want to say why? Is it that it generates excitement and enthusiasm?

  5. The list is available now. I wonder if complaining on Jon’s blog played a role in it.. 🙂

    @ExCryptographer: I love research, and want to know *as soon as possible* the list of accepted papers (typically for Crypto/Eurocrypt). And yes, the primary reasons are excitement and enthusiasm for the newly announced results.

    Also, I am not going to be shy about my overall feeling: I feel that this is an increasingly annoying trend of PC Chairs not putting up the accepted papers list as soon as it is finalized and the notifications go out. And I keep wondering what the hell is it that prevents them from sharing this information with everyone as quickly as they can. If any of the current/future PC chairs are reading this comment, please understand this concern and take active steps to provide the accepted papers list as quickly as you are able to!

    As for an explanation of why I am always so keen on this information, I don’t think I can explain. Its just one of those things, but i can try. If you’re into sports and following an event or something, you want to know which team won a particular game, and who is advancing to the next round and so on. Its not merely about “your” team. Or if you’re crazy about stock market, or the first car that you bought, or the first child you had, you probably had a similar excitement (and of course with time some of these things got less exciting but still…). I hope you get the idea.

  6. @NotPissedOffAnyMore: Fair enough! Thanks for reminding us about the important of generating enthusiasm, while the suspense is still high.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: