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.'"

Re:No surprise there

[v1]

One time pads are not impossible to crack, provided you have some clues about detecting a successful decoding.

[ citation needed ]

Here, let me help you.

citation [wikipedia.org]

In cryptography, the one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext, never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or break without knowing the key.

So unless you classify the key as a "clue" (rather than a cluebat) you need to rethink that.

Re:No surprise there

[Ksevio]

No, a proper one time pad is random and the results will also appear random. The only vulnerability is if the pad it was generated off of isn't truly random or if it's improperly used. If the pad was used more than once or used repeatedly over the message, then there might be hints to decode it. Otherwise, you can brute force it all you want, but you're just as likely to come up with an incorrect "decoded" message as the real one. Since each letter of each word is coded with its own key, guessing the word "Germany" doesn't help you figure out if the word after is "attacks" or "retreats".

Re:No surprise there

[BetterSense]

No. You reveal that you do not understand one-time pads.

Given a ciphertext N characters long, there exists a one-time pad that will decrypt that ciphertext to ANY clear text message. So if you have an N-length bit of ciphertext (as it appears these chaps do) and you brute force it and decode an N-length string that 'looks' correct (e.g. "The fleet has launched") that's just great...the problem is that THAT clear text is equally likely to be the correct clear text as any other string of text that long, including all perfectly-structured sentences, with correct pronunciation, containing jargon...in all languages...that long. And if they are salting and/or stuffing the clear text, you don't even have the length as a clue.

Re:Weeks

[Deadstick]

You would seem to miss the point. Here's a message encrypted with a one-time pad: WXYZ. Want to brute-force it? OK, try all the permutations of four letters that can exist in the OTP (36^4 of them, if the pad accommodates English letters and digits). Spoiler alert: One of those permutations will yield LOVE. Another will yield HATE. Which one is the correct message?

Re:No surprise there

[AJWM]

You're still wrong.

Here's a message encrypted with a (very short) one-time pad: 03 02 05 06.

Here's one one-time pad:
01 - add, 02 - retreat, 03 - flee, 04 - foo, 05 - at, 06 - once, 07 - rats
and here's another:
01 - zebra, 02 - attack, 03 - start, 04 - frobozz, 05 - at, 06 - midnight, 07 - gun
or a third:
01 - innumerate, 02 - tired, 03 - who's, 05 - and, 06 - juvenile, 07 - now

Depending on which one-time pad you use, you get either: "flee all is lost" or "start attack at midnight". I'll let you figure out the third.

Not very helpful, is it? The number of possible one-time pads for a given set of N words is N! (N factorial) (could actually be higher if you allow repetitions in the pad, which you should for common words). A common practice is to use a (specific edition of a) book as your pad, with page/line/word number as key. How many books, now?

Sure, maybe there's only one (out of all the millions of possible editions of books) that renders comprehensible sentences. But if the codemakers are half-intelligent they can confound that, too, by scrambling the order of the words in the cleartext in a pre-arranged way.

Re:No surprise there

[Jappus]

But as stated elsewhere, messages are not random, so the laboratory exercise does not represent the real world.
When you send a spy in to determine the number of tanks crossing a certain bridge, you don't consider an order for lamb chops and left hand threded eels to be a proper decoding.

Yes, but you don't understand the fundamental problem of your argument. With an OTP, the sentence "0 tanks crossed" is just as likely as the following:

"2 tanks crossed"
"3 tanks crossed"
"4 tanks crossed"
[...]
"144 tanks cross"
"346 tanks cross"

And so on and so forth. You can only run a reasonability analysis, if any of those above was less reasonable than the others. So not only would you need to know that there is a spy and that the spy counted tanks (instead of, say, planes or flowerpots), you would also need to know the exact number he counted and that the spy has not counted wrong. You'd also need to know how he phrased the answer.

In short: You'd need to already know the decoded message to say which decoded message is correct. The reason is very simple: In a One-Time-Pad, the key and message are completely interchangeable. Given only the encrypted text, it is just as hard to find the key as it is to find the original message. This is the ideal property all encryption methods strive for.

Re:No surprise there

[mysidia]

even two letters right next to each other may not represent the same letter in the original plaintext..

Any cipher worth its salt will have this characteristic.

A one time pad is a mixing operation; a combination of random data with the plaintext being protected, using an operation that preserves entropy; which means that none of the randomless from the one time pad bits are lost EVEN though the plain message being encrypted is non-random, the result will have exactly as much randomness as the more random of the two bits being mixed, and therefore it is mathematically impossible to discover the value of a single bit of plaintext, without knowing the corresponding bit of one time pad.

Nor is it possible to determine the value of any single bit of one time pad, without knowing the corresponding plaintext bit.

Any attack requires discovering the value of the one time pad through an outside source, or exploiting a weakness in the pad, such as key reuse, OR inadequate random number generator used to produce the pad.

The only thing you can ascertain about the one time pad by looking at the enciphered message, is its maximum potential length, since you can see the number of symbols that are printed on the card, and that will be a finite number.

Re:No surprise there

[Coryoth]

That's a codebook, not a one time pad. They are distinctly different. Code books are theoretically crackable given sufficient ciphertext and a model for the plaintext (e.g. English). In practice "sufficient" ciphertext is never going to happen. One time pads are uncrackable in theory. In practice mistakes can be made that make them not true one time pads and thus potentially crackable (but that require multiple messages using the same pad -- not the case here).

Re:No surprise there

[AK Marc]

True-Scotsman is saying that someone born in Scotland doesn't count as a Scotsman because he doesn't act correctly. That's a false/useless assertion that's factually wrong and asserted only to move the goalposts for the "correct" definition. A "one-time" pad used more than once isn't just a misused one-time pad, but is also a "two-time" (or more) pad, and, by definition, is no longer a one-time pad. That's not a no true Scotsman argument, but a "you defined it properly - no fair" argument.

Re:Easy!

[Anonymous Coward]

It was from a Monty Python sketch.

http://en.wikipedia.org/wiki/The_Funniest_Joke_in_the_World