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

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

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

[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

[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.