Multiple anagramming

2008-05-26

in Geek stuff, Security

Emily Horn in a heap of clothes

The process of cryptanalysis can be greatly simplified if one possesses more than one message encrypted with the same key. One especially important technique is multiple anagramming. Indeed, it may be the only way to decipher two or more messages that have been enciphered using a one time pad.

The basic idea of multiple anagramming is that you can use one message to guess what possible keys might be, then use another message to check whether it might be correct. For instance, imagine we have these two messages and think they were enciphered using the Vigenere cipher:

SGEBVYAUZUYKRQLBCGKEFONNKNSMFRHULSQ
TUEEDAKHNVKUEOICHKIEPOHRIFDQSPHGEGQ

Now, suppose we think the first message might be addressed to Derek, Sarah, or Steve.

Using words we think the message might start with, we can guess at a key. If the first word is DEREK, the key would start with ‘PCNXL’. If the first word is SARAH, the key would start with ‘AGNBO’. Finally, if the first word is STEVE, the key would start with ‘ANAGR’. Here, the key is a bit of a clue. Normally, there would be no easy way to tell from one message whether we had found the correct key or not.

We can then test those keys against the second message. The first key yields ‘ESRHS’ for the first five letters. The second, ‘TORDP’. The third yields ‘THEYM’. The third looks the most promising. Through either guessing or testing further letters, we can discover that the key is ‘ANAGRAM’. The second message is thus ‘THEYMAYHAVEDECIPHEREDOURCODESCHANGE.’ Having two ciphertexts that produce sensible plaintexts from the same key suggests that we have properly identified the cipher and key being used. We can then easily decipher any other messages based on the same combination.

Report a typo or inaccuracy

{ 7 comments… read them below or add one }

Milan May 25, 2008 at 8:59 pm

Other cryptography related posts:

Some useful patterns in English
Friday, May 2nd, 2008

Rainbow tables
Tuesday, March 25th, 2008

Unicity distance
Tuesday, October 23rd, 2007

Quantum computers and cryptography
Friday, September 14th, 2007

The Code Book
Tuesday, August 14th, 2007

Strengthening substitution ciphers
Thursday, August 9th, 2007

Making a hash of things
Friday, February 23rd, 2007

More amateur cryptography
Friday, February 2nd, 2007

Something to try over the weekend: cryptography by hand
Wednesday, July 26th, 2006

Milan May 26, 2008 at 9:42 am

Oh, and in a case where you have a very great many messages enciphered with the same key, there is a further variant on this technique.

If the cipher always uses the first letter of the key to encipher the first message of the ciphertext, that means that the first letters in all the messages are enciphered by the same key. That means they are potentially subject to frequency analysis. The same is true for the second letter, and so forth.

This is especially easy if the cipher uses cipher alphabets comprised of simple Caesar shifts, as the standard Vigenere tableau does.

. May 26, 2008 at 12:02 pm

Bletchley Park Facing Financial Ruin

biscuitfever11 writes “Bletchley Park, the home of Station X, Britain’s secret code-breaking base during World War II, barely scraping by financially, as shown in these images compiled by ZDNet this week. The site has undergone major redevelopment as an act of remembrance for the Allied efforts to break the German Enigma code, but now its future is clouded — among others, the Bill and Melinda Gates Foundation turned them down for financial assistance (since it doesn’t have to do with the Internet). Its director estimates that Bletchley Park’s funds will be exhausted in three years. Hungry land developers are circling. This is an insightful look at what’s happened to Bletchley Park these days and the pain it’s going through.”

Sarah May 26, 2008 at 2:37 pm

Cute picture ;-)

Neal May 26, 2008 at 3:21 pm

The comments in the slashdot thread regarding Bletchley Park is discouraging. It seems bizarre that so many nerds are so callously dismissive of a place that holds perhaps the strongest claim of being the birthplace of modern computing.

Anonymous May 27, 2008 at 1:23 pm

(CR: Seq)
(CR: Canidae)
(CR: Somno)
(CR: 25AUG05)
(CR: T)
(CR: ISM)
(CR: HD)

. May 30, 2008 at 10:15 am

Schneier on Security

A blog covering security and security technology.

Bletchley Park May Close Due to Lack of Funds

Sad.

Leave a Comment

You can use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Previous post:

Next post: