After Weeks of Trying, UK Cryptographers Fail To Crack WWII Code

An anonymous reader writes "A dead pigeon discovered a few weeks ago in a UK chimney may be able to provide new answers to the secrets of World War II. Unfortunately, British cryptographers at the country's Government Communications Headquarters (GCHQ) have been unable to crack the code encrypting a message the bird was tasked with sending and say they are confident it cannot be decoded 'without access to the original cryptographic material.'"

Comments

No surprise there

[Anonymous Coward]

Given that the original message looks supiciously like it was encoded with a one time pad, it's really not at all surprising that they can't crack it without the relevant pad. Which was probably destroyed a long time ago.

Re:No surprise there

[Anonymous Coward]

One time pads are not impossible to crack, provided you have some clues about detecting a successful decoding. A decoding that renders a perfectly structured sentence with proper spelling, and/or recognized jargon could be picked out by computer as a "highly probable content" from all the other gibberish decoding.

Your statement demonstrates a fundamental misunderstanding of the one-time pad. One-time pads are not like other forms of encryption, they are simply modular arithmetic with a set of random characters. The encrypted data could decode to literally anything, depending on the key used.

https://en.wikipedia.org/wiki/One-time_pad

Re:No surprise there

[Pseudonym]

One-time pads are impossible to crack, in the sense that all messages are equally likely. Think about this for a moment. You can think of many plaintexts of that length. Each one could be the result of a different pad. Since those pads are equally likely, the plaintexts are also equally likely.

We do have the message length, and we also have some information in cleartext (e.g. the time it was sent and who sent it). That's it.

There are weaknesses in an OTP system, but they are typically due to poor key management.

Re:No surprise there

[BitterOak]

Your citation is incomplete. Key reuse is one way to weaken the encoding without forking over the key itself, though this needs multiple messages encoded with the same key.

If you've re-used a key, you're no longer using a one time pad. (Hint: Why do you think it's called a one time pad? [emphasis mine])

Re:No surprise there

[0123456]

You're right. If you know what the decoded message is, you can easily decode it without knowing the pad.

Otherwise, you have no chance if the pad was correctly created and used, as any character in the message can decode to any other character.

Re:No surprise there

[v1]

Your citation is incomplete. Key reuse is one way to weaken the encoding

Please re-read the entire cited text. Pay special attention to "never reused in whole or part"

(also, even a single re-use can completely compromise all other messages that used a given pad, if the plaintext of a single message encoded with that pad is discovered by other means)

I'm not a cryptoanalyst, but I play one on TV

Re:No surprise there

[0123456]

You still don't get it.

You might know that the message is 'The Commies have XXX tanks' where XXX is a number, but if the pad is correctly generated and used, the XXX can decode to any three digit number whatsoever, so that knowledge gives you no information at all.

Re:No surprise there

[hawguy]

While that is true, you will note that i said probable content. Yes there are any number of equally valid decodings. However few will make sense in the context in which they were sent.

The assertion that there are any number of possible decodings only works when you have zero knowledge of expected content, and as such its a tired and juvenile objection.

It's not that there are "any number of equally valid decodings", but there is every possible decoding. If the word "APPLE" is encypted with a one-time pad into "XYZZY", there are potential one-time pads that will decrypt that string into "APPLE", "IPHONE", "STEVE", "WINMO", "GOOGL", "ANDRD", "SBRIN", "LPAGE", "BILLG", etc.

How do you know which of those is the "valid decoding"? How does your knowledge of expected content help you?

Re:No surprise there

[ceoyoyo]

He's right, you clearly don't understand how one time pads work.

With a properly used one time pad, ANY message (of the same length) is equally valid. Typically you salt the message with some nonsense or whitespaces too, so any message of length = the length of the encrypted message is possible.

So you can make up any message you want, gibberish or real words, and you have no idea if it's the real message or not. You cannot use frequency analysis, dictionary attacks, content hints, or anything else against a properly used one time pad.

You're thinking of simpler encryption algorithms that DON'T use completely random pads. Things like Enigma. If you know something of the content of the message that can help immensely in decrypting those messages, but again, prior knowledge, guesses or whatever have no effect on the security of a properly used OTP.

Re:No surprise there

[BetterSense]

It's humorous that you encourage me to use my head, when you are so completely wrong. Since you don't believe me, I can only invite you to read up on cryptography and one-time pads, until you understand exactly why and how you are wrong. Afterward, please attempt to educate others so that the world wastes less time arguing over solved problems.

The reason one-time-pads cannot be broken is fairly non-intuitive, but it's worth understanding. You should understand that it is beyond pointless to even attempt to brute-force a one-time-pad transmission, because you know before you even begin wasting CPU cycles that you WILL find EVERY N-length message that can exist, and you will have no reason to favor any of them. That's why you don't even try. You jump right to trying known/broken ciphers, frequency analysis, looking for possible misapplications of the one-time-pad technique, or something else, because brute-forcing one-time-pad transmissions mathematically cannot work. It's not that it doesn't work, or that it's too hard, but it mathematically is beyond being possible for it to work.

Re:No surprise there

[Chris Mattern]

Key reuse is one way to weaken the encoding without forking over the key itself,

In which case, YOU AREN'T USING A ONE-TIME PAD! It's called "one-time" for a reason, you know.

Re:No surprise there

[v1]

Length isn't even relevant. Proper use of a OTP recommends simply copying the remaining pad past the end of the cleartext, or to a random length beyond it. This makes it impossible to determine the length of the cleartext. The cleartext just ends in a standard End of Message, which can only be identified by the recipient with the pad key. "We will attack at dawn. End of Message." could be transmitted as a two page block of ciphertext. It's not a waste since the pad cannot be reused in whole or in part anyway. That entire page of pad just gets torn out of the book and burned when the message is sent.

Re:No surprise there

[slew]

As another aside, one of the weaknesses of the Enigma Cipher was that the subsitution wheels never substituted one letter with the same letter. This fact turned out to be somewhat helpful in breaking the cipher...

Many early ciphers had weaknesses that were the result of not fully understanding the loss of randomness from seemingly logical "optimizations".

Re: No surprise there

[gumbi west]

Your point can only be this: the set of messages that might reasonably have been sent can be guessed as the deciphered text. The actual encrypted data gives you zero information on that if the OTP was used properly.