Sunday, November 25, 2012

Encrypted world war II droppings

The public's imagination has apparently been captured this month by stories of an encrypted World War II message found attached to the leg bone of a carrier pigeon that had apparently been lodged in a chimney in Surrey for the past 70 years.

There doesn't seem to be complete consensus on the identity of one or two of the letters, but a transcription of the message looks essentially as follows:


The dots in parentheses probably aren't part of the encoded message as such, assuming word/phrase/sentence boundaries were not explicitly encoded. But they may be a clue to such boundaries, with the scribe inadvertently inserting them as they came to the end of a sentence/phrase. They suggest that at the time of transcription, such boundaries were still present, probably ruling out a system akin to today's modern block ciphers.

Notice the sequence "AOAKN" appearing both at the start and end, which is presumably not part of the encoded message, but possibly a reference to the encryption key, some kind of "message start/end codeword", or some kind of authentication sequence.

So what does the message say? Can it be decoded with modern computational methods? Simple schemes such as letter substitutions and even variants of the FairPlay cipher apparently used at one point during WWII could potentially be deciphered.

But despite various rumours and hypotheses I have seen on a few Internet forums, unfortunately, the distribution of letters in our mystery message appears to be consistent with encryption using a one time pad. In a one time pad, one "mixes" each letter in the message with the next letter of a secret randomly generated sequence known only to the sender and recipient. If implemented properly (meaning the stream of letters forming the one time pad has to be genuinely random and never re-used for multiple messages or parts of messages) then this scheme is completely secure. (Modern stream ciphers are inspired by the technique, but rely on a generating a pseudorandom sequence from a relatively small secret random key; as with modern cryptographic techniques in general, they are "secure enough in practice for the use to which they are put" if their usage guidelines and limitations are properly understood.)

One hope for "cracking" the message would be if the such a scheme was not implemented properly (for example, using as "secret" one time pad a sequence of letters based on a known text such as the American Constitution, or indeed any text in a common language with well-studied letter/word distributions.

One other thing seems clear: if the message is crackable without more information, the people with the tools and knowledge to crack it are GCHQ if they can be bothered.  So my guess is that (a) with minimal resources and standard tools they have decoded the message and this is a recruitment drive, or (b) GCHQ have ascertained the scheme is some variant of a one time pad (or not something they can trivially decode with the resources they can be bothered to devote to some one-off 150 character message from World War II) and what is being sought is some of the "social" knowledge around locating the key/clues to its generation in case they can then idly decode it with close to zero effort.

And in the worst case, the story has revived public interest in history, mathematics, computing etc while being a temporary distraction from the humdrum financial turmoil and political scandal which otherwises graces our news outlets.


Anonymous said...

"a known text such as the American Constitution, or indeed any text in a common language with well-studied letter/word distributions"
What if the ONE TIME PAD is the Bible? Think you may be on to something there.

Anonymous said...

a known text such as the American Constitution, or indeed any text in a common language with well-studied letter/word distributions.

What if the ONE TIME PAD is the BIBLE?

Anonymous said...

The solution to the problem will be soon by you.