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

[K. S. Kyosuke]

Which was probably destroyed a long time ago.

Which is, some time after destroying the one-time pet?

Re:No surprise there

[ReptileQc]

That's what I was about to say. Knowing the algorythm, they should brute force it and look at the results. Even if the results are impossible to detect automatically, this is when slashdot citizens come in and sort through the information. :)

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

[camperdave]

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.

LOL! R U srs? Propr spellx? ROFL.

Re:No surprise there

[interval1066]

...looks supiciously like it was encoded with a one time pad

Exactly. One time pad encryption the most secure. Unless they can track down the encrypting agent, he's (she's) still alive, and lucid enough to speak, its not happening. Or they find a code book with that day's pad in it, in a long forgotten room or something.

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

[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

[lgw]

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

Not generally true (assuming a genuinely random one-time pad). In order to decrypt anything, and know you have arrived at the original plaintext, not some arbitrary plaintext, the plaintext needs more bits of redundancy than the length of the key; otherwise multiple possible keys will yield "probable content" when tried.

Because the key for a one-time pad is longer than the message itself, you're going to get every possible "probable content" as a candidate, because there's a one-time pad that will "decrypt" the cyphertext into every possible plaintext of the same length.

Now, English has a lot of redundancy, so if the one-time pad isn't really random, you might have something to go on. If you could predict, say, half the bits in a one-time pad from the other half, and the encryption was something as simple as XOR with the key, you could have some confidence that there's only one decryption that yields well-formed plain text: because in that case the reduncdancy in the message exceeds the entopy in the key.

This principle is the Shannon Something Length, but I cant remember the exact name, and half of information theory is the Shannon Something Something, so my google-fu is weak.

Re:No surprise there

[jspoon]

Grandparent is getting OTP mixed up with ROT13. I do that all the time. It cost me my job once.

Re:No surprise there

[arose]

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. Less than perfectly random sources can be another attack vector. "Used properly" is not just about protecting the key.

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: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

[l0ungeb0y]

Messages small enough to be carried by pigeon were most likely necessarily small

So you're saying that this message was quite literally a "tweet".

Re:No surprise there

[Anonymous Coward]

Indeed. One theory is its a one time pad combined with a code book.

If a code book was used its be specific to the mission and long destroyed or buried in the archives.

It could be the first block decodes to DRG translating to 'primary target destroyed' or some such... Using such code words would make it impossible to tell when a message had been decoded properly because it'd be unintelligible.

Such code books were popular for saying a lot in a short message and getting extra security. They're essentially a book code so a level of encryption on their own.

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

[Anonymous Coward]

if the one time pad is truly random the encrypted message is random and there is no way of telling what the message is unless you have the pad

if it wasn't so a monkey hammering on a keyboard would be writing Shakespeare, you'd just need to brute force the one time pad it used ...

Re: No surprise there

[turbidostato]

I think you still don't get it: with OTP there's no way to tell appart "we must attack" from "I'll miss you.".

Re:No surprise there

[somersault]

Nope..

it is possible to "decrypt" out of the ciphertext any message whatsoever with the same number of characters, simply by using a different key, and there is no information in the ciphertext which will allow [the reader] to choose among the various possible readings of the ciphertext.

Got that from this . It's an interesting read. In a message encrypted by a one time pad, even two letters right next to each other may not represent the same letter in the original plaintext..

Re:No surprise there

[PolygamousRanchKid]

If the pad was used more than once or used repeatedly over the message, then there might be hints to decode it.

You mean one-time-pad-recycling? Like in environmentally friendly Soviet Russia . . .

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

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

[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

[linebackn]

Aw, but according to the TV all anybody needs is a few hours, perhaps a larger computer than usual if it is "military grade" encryption, and a gui front end in VB, and you can decode ANYTHING!

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

[Mr Z]

One Time Pads are indeed impossible to crack, if the pad is indeed used only one time, and is indeed fully random. That's because it makes any message that's the same length as or shorter than the ciphertext equally likely.

If I sent you the ciphertext PDXS, how would you know if it decoded to "EAST", "WEST", or any other four letter word?

Re:No surprise there

[Anonymous Coward]

So, which of the following is correct?

"Air drop at 2300."
"Air drop at 1000."
"Air drop aborted!"
"Pad compromised"

With a correctly used one-time pad you can never know unless you know the pad.

Re:No surprise there

[aliquis]

Maybe they didn't wore any glasses?

Tried safety googles?

Still no solution? Then I have no idea.

UV light maybe?

Re:No surprise there

[allsorts46]

You're still missing something here. As parent says, "Given a ciphertext N characters long, there exists a one-time pad that will decrypt that ciphertext to ANY clear text message.". That's ANY, not A LOT, or VERY MANY. So yes, whilst you could easily dismiss a cookie recipe, you're still going to get an extremely large number of plausible results, plenty of which will contradict each other. Your example of a time for a drop is particularly bad - 01:00 is equally as likely as 02:00 as 03:00 as 04:00...

Re:No surprise there

[Anonymous Coward]

LOL, good joke.

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

[Anonymous Coward]

You're really going to call that a no-true-Scotsman argument? Really?

Re:No surprise there

[ceoyoyo]

From the GP's quote:

"never reused in whole or part"

I know reading comprehension isn't among the best of a typical Slashdotter's abilities, but really? It's not a one time pad if it's used more than once, is it?

Re:No surprise there

[Anonymous Coward]

No, you're not using it properly, no reason to define it away with true-Scotsmanning (would apply to the random part just as well anyway).

This is not at all true-Scotsmanning. This is negative-duck-typing. If it doesn't quack like a duck nor look like a duck, it's not a duck.

A one-time pad that's used more than one time isn't a one-time pad now, is it? If you're trying to bludgeon this into a true-Scotsman fallacy, this would be akin to you saying that a Scotsman born and raised in Brazil is no true Scotsman, and, to be honest, that person actually seriously WOULDN'T be a Scotsman at all.

Re:No surprise there

[arose]

Yes, otherwise there is no possibility of consider improper use at all.

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

[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

[Anonymous Coward]

It is theoretically impossible to decrypt as there exists a OTP to convert the ciphertext into any plaintext of the same length. There is nothing to tell you when you have correctly decoded it.

Re:No surprise there

[__aajfby9338]

You can discount gibberish and orders for lamb chops if you are quite confident that the message was, for example, English text, and that "lamb chops" was not a code phrase for something like "crates of ammunition". But you still can't distinguish between "FOURTEENTH TANK BRIGADE WILL ATTACK ON NOVEMBER TWELFTH" vs. "EIGTH INFANTRY BRIGADE RETREATING WITH HEAVY CASUALTIES". In any case, code words, code phrases, abbreviations, jargon and spelling errors can all be reasonably expected in legitimate military and espionage communications, so without detailed inside information, you can't even discount a possible decoding like "RABBITS ARE RUNNING DUE TO CRITICAL LAMB CHOP SHORTAGES". For any given message length, it is quite possible to come up with possible decodings of the same length with exactly contradictory meanings. Thus, even in real life, an intercepted OTP message only gives you an opportunity for traffic analysis.

When properly implemented, one-time pad messages are truly unbreakable in the lab and in practice. Successful cryptanalysis of them is only possible when serious mistakes are made, such as using a single key more than once, using a key that can be predicted by some means, etc.

As an aside, Between Silk and Cyanide was an interesting account of one person's involvement in WW2 cryptography related to espionage operations. If we can assume the author's account is accurate, then there was a lot of WW2 espionage activity using ciphers other than OTP, and OTP (in particular, OTP using letters rather than numbers) was a later development in the war, still further delayed by the complications of distributing key material. So, it makes sense to me for cryptologists to have made an attempt at breaking this recovered cryptogram based on the possibility that some system other than OTP was used to encipher it.

Incidentally, five-letter groups of seemingly-random characters is a common form for enciphered text, and is not specific to OTP. It's conventional to break enciphered text into five-letter groups to make it easier to avoid losing one's place when transmitting it by telegraph or teletype. Cipher machines such as my US WW2 M-209B or my Soviet cold-war Fialka even automatically space the ciphertext out into five-letter groups. It takes actual analysis of a ciphertext to determine what system(s) may have been used to create it. For practical purposes, there will often be information called "indicators" embedded in the ciphertext, so that a busy cipher clerk will know which machine to use and which key to load into it to process that message. There are extant examples of such indicator systems that I've seen, such as in WW2 training materials for message center staff. Knowledge of the indicator system(s) in use by a particular adversary can help a cryptographer determine the best approach for a particular intercepted message, such as "assume this message is a Playfair cipher from some low-level guy we don't really care about", "send this one straight to the folks breaking Enigma traffic", or "put this one in the don't-bother-trying box".

Re:No surprise there

[Anonymous Coward]

I know right, lol. OP clearly boded things in a way that implies they take precedent over the rest to emphasize the rest, amIrte. ROFL one-time pads are actually unbreakable by defition so OP is wrong anywayz because his citatiton is sElf contradictory acodring to yourz.

Re:No surprise there

[Anonymous Coward]

I can't believe this idiocy was modded +2, Informative. It shows a blatant misunderstanding of OTPs, something so incredibly simple.

Re:No surprise there

[__aajfby9338]

You are right, except for one nit-picky detail: We only have an upper bound on the message length. It's fairly common practice to pad messages out to a five-letter boundary, so the actual message may be shorter than the captured ciphertext. We also don't know whether the sender used some letter to indicate spaces or just ran the words together, both of which are common and valid practices. Cryptosystems of the era often had no provisions for numbers or symbols, which would need to be spelled out in text. Sometimes a letter would be reserved for use as a space character, such as 'Z' on the US M-209 machines, or a different letter on other Hagelin-designed machines intended for different markets. It makes sense to use the least common letter in the native language of the intended users, so for example, the CX-52 machines could be easily reconfigured in the field to use one of four letters IIRC to represent a space.

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

[Anonymous Coward]

And if you tried to bake a cake without a recipe or knowledge of what ingredients go into a cake, and so ended up with concrete, would you cry no-true-Scotsman when someone says it's not cake?

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

[Chris Mattern]

It doesn't matter that the message isn't random, the *key* is random, and never reused. While the message (most likely) not something nonsensical, it could be *anything* that *does* make sense, as well. You can't narrow it down to something that makes sense or something that doesn't make sense. You can't narrow it down at all.

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

[OneAhead]

Now you're just making a fool of yourself. People already linked you to a wikipedia page that explains in detail why you're wrong, yet you stubbornly refuse to read it (or perhaps you're too daft to understand what it says?)

Here's a demonstration. From TFA, the secret message is:
AOAKN HVPKD FNFJU YIDDC
RQXSR DJHFP GOVFN MIAPX
PABUZ WYYNP CMPNW HJRZH .
NLXKG MEMKK ONOIB AKEEQ
UAOTA . RBQRH DJOFM TPZEH
LKXGH RGGHT JRZCQ FNKTQ .
KLDTS GQIRU AOAKN

My sources are telling me that "AOAKN" is most likely the identifier of the OTP or code page that was used, so the actual content of the message is
HVPKD FNFJU YIDDC RQXSR
DJHFP GOVFN MIAPX PABUZ
WYYNP CMPNW HJRZH NLXKG
MEMKK ONOIB AKEEQ UAOTA
RBQRH DJOFM TPZEH LKXGH
RGGHT JRZCQ FNKTQ KLDTS
GQIRU

Being a 1337 cryptography expert, I determined that the code page in the sender's code book started with:
SBXDZ CUYSG ECWKO CMRSZ
JRGOH DIRFA JRWEP LFXRK
OLULB XHHAW UGKLL NUUKT
JQPKX LMUGR IGRCC AHKCW
OKMZZ LQOSK PPGNH YPPVW
NRVDT RNHYD CNCCY RUVJO
VCNNA
Don't believe me? Go to this page, copy-paste the above "actual content" in the field that says "input" and the key in the field that says "key", and click decode.

Oh wait, I was wrong, the real key is:
ZTLJV VJXRU VERZP YMUND
PYLYB WBHJV ZUWCR ESJNL
FMYUI KMCKU HWYID NIJTM
ZBITS VNBFI TGIWG MLKQS
RMQLD PWASI AHNAS LHFBN
PWYUN XRTPM MVDFU HXKMO
IUUAK

Allright, I'm just messing with you, it's
JHVGR QUHCQ YFZAC EILSG
YVTCW PABZG QALLG HVBDG
OLAZV LGLAS QJGWZ WHVRY
YROWQ XBAPU WTIEY UTOHI
YXZRU ALALV OPGXD USLCW
YSBDI GNILZ OWTSM TUMCB
PZANC

Re:No surprise there

[BlueBlade]

One time pads *are* impossible to crack, by the very definition. With a one-time pad, there's no "partial" decoding whatsoever, no attack vector, no weakness. Any method that you apply that result in a structured sentence would be pure random chance. In fact, you can apply any random "pad" to the cipher to obtain anything, from a grocery list to rocket schematics.

Re:No surprise there

[BlueBlade]

Wow, I don't witness that particular brand of cluelessness very often on slashdot.

With a one-time pad there *are* any number of possible decoding. The key is the same length as the clear text. This means that you have *literally* no way of knowing that you have successfully decoded it without knowing the clear text or the pad.

Re:No surprise there

[DrVomact]

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.

I'm curious: how do you tell by the looks of a cyphertext that it was encrypted with a one-time pad? Yeah, it's written in groups of five characters, and makes no (obvious) sense...but that is no clue as to the method used to encrypt the text. Breaking up words into equal groups is done (obviously) to obfuscate word boundaries, it's not a practice restricted to one-time pads.

Re:No surprise there

[arose]

If you tried to bake a cake with a recipe and/or knowledge of what ingredients go into a cake and how to put them together, but mis-measured the eggs/used high-protein flour and so ended up with a shitty cake I would cry no-true-Scotsman when someone said you weren't making a cake.

Re:No surprise there

[emt377]

Exactly.

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

For any plaintext message of the same length you can construct a pad. This makes the cipher impossible to break. One pad will yield "attack at dawn", another "hello kitty". For any message there is a pad. A brute-force iteration of all possible pads will only yield all possible messages. The only angle of attack is to see how the pad might have been created in the first place (like seeds and sequences used) and attempt to reconstruct it.

Re:No surprise there

[arose]

You are of course right, a "Scotsman" who ever set foot outside of Scotland wouldn't be a true Scotsman no more, it would take the Scot out of them and that's clearly in the name.

Re:No surprise there

[arose]

And since it doesn't have anything regarding the nature of the pad in the name it doesn't matter. Semantically though you can read it as "cleartext only needs to be padded once" just as well, which is why the semantic argument is nitpicking. It's either possible to misapply one-time pads or it isn't, that one misapplication might be implied in the name doesn't change that.

Re:No surprise there

[Sulphur]

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])

Venona was supposed to be an OTP and it was cracked by the reuse of the pad.

Re:No surprise there

[__aajfby9338]

Well, that's a matter of semantics. If you implement a large-scale, properly-designed one-time pad system, but then a pair of lazy and/or ignorant code clerks re-uses individual OTP sheets for some of the traffic between them (contrary to orders and training, of course), then do we say "it's not a one-time pad system", or that "it's a misused one-time pad system"? Either statement might be arguably valid.

Or maybe all of your code clerks properly use each sheet once and then immediately destroy it, but the factory that produced the keying materials messed up and included duplicate sheets mixed into some of the books, resulting in compromise of the system. Which has actually happened, by the way. You might say that it wasn't actually an OTP system, or you might say it was an OTP system in which implementation mistakes were made which compromised some of the traffic. Those mistakes may have been unintentional errors or deliberate acts by undercover agents to weaken the system, but the folks who designed and oversaw the system intended to deploy a proper OTP system and thought that they were doing just that.

Or maybe you create an OTP system, distribute good keying material without blunders like repeated pages, but then an undercover agent runs out of keying material, has no way to obtain more, and then must choose between stopping communication, communicating in plaintext, or re-using OTP sheets to get critical information through and hoping that the adversaries don't detect the situation. I lean towards calling this situation "not OTP", but it's still a matter of semantics.

Re:No surprise there

[__aajfby9338]

Good point! I mentioned elsewhere here that it's normal to pad out a message to a 5-letter boundary, but padding it out still further by copying the remainder of the sheet makes even more sense. The only drawback is that it places more burden on the communications channel, which may be a serious issue when a single radio operator needs to send all of the traffic for a number of agents and faces greater risk of capture by staying on the air longer (see Kahn's The Codebreakers for accounts of such overloaded radio operators, and their capture). But if the added traffic doesn't prove to be too risky or burdensome, then padding out messages that way would be a good way to reduce the amount of information that your adversary might infer from traffic analysis. If your situation and available keying materials allow you to routinely send large empty messages, then your adversary may not even notice when you suddenly change from standby to a high level of activity just before an important mission.

Re:No surprise there

[SQLGuru]

It probably would have helped if they had used the right letters. In the last line, it should be GQIRW. The writer's F's were shaped entirely different (as evident in the second line).

AOAKN HVPKD FNFJW YIDDC
  RQXSR DJHFP GOVFN MIAPX
  PABUZ WYYNP CMPNW HJRZH
  NLXKG MEMKK ONOIB AKEEQ
  WAOTA RBQRH DJOFM TPZEH
  LKXGH RGGHT JRZCQ FNKTQ
  KLDTS FQIRW AOAKN 27 1525/6

Re:No surprise there

[Anonymous Coward]

Actually, a one time pad is a character operation, and there's no prohibition about repeating entries. In your case, you would not have N! possible one time pads, but N^N

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

[gadzook33]

Actually I read something interesting about WWII One Time Pads. Apparently the pads were generated by women (typically) drawing ping pong balls out of a hopper and writing down the letters. The problem was if they drew the same letter multiple times in a row, they might put it back thinking that it wasn't "random" enough. Of course, in doing so they changed the distribution of letters to no longer be uniform. My understanding is that this very quickly erodes the cryptographic integrity of the one-time pad to the point where you can start to look for the plaintext based on letter frequency. I'm not saying that's applicable here (and I have to imagine the cryptographers would have looked at this) but interesting nonetheless.

Re:No surprise there

[Anonymous Coward]

That last batch activated my copy of Windows XP.

Re:No surprise there

[Anonymous Coward]

Actually I read something interesting ...

By 'something interesting' you must mean Neal Stephenson's Cryptonomicon. I agree, it is quite an interesting book. One of my favorites in fact.

Re:No surprise there

[Burning1]

If I recall correctly, you can recover the key simply by compareing the two encrypted messages. You don't even need the plaintext.

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

[Anonymous Coward]

Well not all random numbers are truely random and some will repeat or have other characteristics. If you can find information about how the pad was generated it could pottentially be possible to break.

Re:No surprise there

[Jah-Wren Ryel]

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.

At that point it is no longer a one-time pad it is a multiple-times pad.

Re:No surprise there

[Anonymous Coward]

This is an interesting topic since what a human considers random isn't truly random. Randomness demands clusters and humans dislike clusters when looking for a design for random data. This is actually used as a indicator of determining random data.

Re: No surprise there

[grumbel]

A clue does not help you a bit. The only thing you can get out of a OTP is the maximum length of the message, but not the minimum or actual length,. Everything else is completely arbitrary and depends completely on the key. You can literally decode all possible messages with that maximum length out of that encrypted sequence with the right key. All Twitter posts ever written, all messages passed around in WWII, a whole bunch of Haiku's and what ever else you want you can get out of that sequence with the right key. That encoded sequence is essentially just random junk without the original key. The only clue that brings you to the original message is the original key used to decrypt it.

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.

Re:No surprise there

[MrNaz]

The original message was NOT encrypted using an OTP, as OTP cyphertext looks like random noise. Given that there are several repeated sequences there, the use of an OTP is extremely unlikely.

Re:No surprise there

[Anonymous Coward]

If I were baking a cake and used incorrect flour and fuck it both your mothers are whores.

Re:No surprise there

[MrNaz]

I don't think you have even the remotest idea what Venona was.

Re:No surprise there

[MrNaz]

I understand why a piece of pad cannot be reused, but why not in part? If I have a page of, say 1000 chars of pad, and I send messages usually between 50 to 100 chars length, why can't I use the 1000 char page as just a sequence of 10 x 100 char pads? Or, assuming I don't consider length discovery to be an issue, why can't I just use as much of the pad as necessary for a given message? Ignoring the challenges of coordinating which part of the pad is used (which can be resolved with difficulty but is not insurmountable), why is this always recommended againts when implementing OTPs?

Re: No surprise there

[MrNaz]

With an OTP, there is no way to differentiate "Attack at dawn" from "Attack at dusk", both of which are contextually valid. Even if you were given the ciphertext AND the key for the first 11 characters of that message, finding the last 3 would be no less impossible than without them.

Properly used OTP is uncrackable. No ifs, buts, maybes or edge cases.

Re:No surprise there

[Anonymous Coward]

Actually I read something interesting about WWII One Time Pads. Apparently the pads were generated by women (typically) drawing ping pong balls out of a hopper and writing down the letters. The problem was if they drew the same letter multiple times in a row, they might put it back thinking that it wasn't "random" enough. Of course, in doing so they changed the distribution of letters to no longer be uniform. My understanding is that this very quickly erodes the cryptographic integrity of the one-time pad to the point where you can start to look for the plaintext based on letter frequency. I'm not saying that's applicable here (and I have to imagine the cryptographers would have looked at this) but interesting nonetheless.

I somewhat doubt that ; if the pad is based on 26-letters and for some reason you occasionally select from 25-letters it only slightly reduces the number of possibilities. Afaik a decrypter still wouldn't have any other choice but a bruteforce attack and that'd be running all the combinations of letters for a given length of text.

Maybe I've gotten something wrong, dunno.

Re:No surprise there

[Anonymous Coward]

He has a 5-digit id. There is a possibility of senility.

Re:No surprise there

[Anonymous Coward]

I know she gave great head.

Re:No surprise there

[Anonymous Coward]

How do you know which of those is the "valid decoding"?

You're (of course) right. We only know one of those, IPHONE, is invalid as it's longer than the cipher.

Re:No surprise there

[MaskedSlacker]

5/5 Made me laugh unnaturally loudly in the middle of a quiet coffee shop. Would decode again.

Re:No surprise there

[Anubis IV]

Actually, as has been pointed out, your example is not for a one-time pad at all (yours is a code book, which is theoretically quite crackable after a single use, assuming a sufficiently large message).

In contrast, a one-time pad operates by providing a value for each character of the message (and thus it establishes the limit for the size of the message at being less than or equal to the number of values provided). The letters are then incremented by the amount specified by their corresponding value (e.g. A + 3 = D), and if you go past Z, you just start over again at A. Doing so ensures that each character is individually encoded separately from every other letter and that there are no relationships between them, thus ensuring that a code breaker can't use a distribution of values analysis to try and determine which values might correspond to more commonly-occurring letters (or, in your example, they could apply an analysis to find more commonly-used words, theoretically).

For instance, a proper one-time pad might be more like this (note: letters were pulled out of my head, so they are not sufficiently random): E, A, H, F, M, Y, Z

And if I wanted to encode "retreat", it would be:
R+E(5) = W
E+A(1) = F
T+H(8) = B
R+F(6) = X
E+M(13) = R
A+Y(25) = Z
T+Z(26) = T

If the random values had been different, I could have spelled any other six-letter word and ended up with that same result. And a person decoding my message would simply use their copy of the one-time pad to subtract the values from the encoded message in order to recover the plaintext message telling them to retreat.

Of course, you also need to account for spaces and the like, so you'd probably go beyond 1-26 in order to handle non-alphabetical characters, but you get the idea.

Re:No surprise there

[MaskedSlacker]

Repeated sequences are expected in actual random noise. The question is how long/frequent are they? The 'correct' values are easily calculable (and left as an exercise to the reader), along with the probability of the message being encrypted with a OTP (or rather, the probability that the ciphertext is consistent with a OTP).

Re:No surprise there

[Anonymous Coward]

A bunch of British sissies they are, can't even toss a log.

Re:No surprise there

[Anonymous Coward]

Except this adds an additional layer of randomness - "they might put it back". So you've got "two letters in the one time pad may, or may not be consecutively the same, and this rule may or may not change within the same one time pad, depending on the generators whim".

Re:No surprise there

[Anonymous Coward]

My Scottish grandmother was born in Argentina.

Re:No surprise there

[Sulphur]

I don't think you have even the remotest idea what Venona was.

It was the code used by the atomic spies. Alexander Fomin (nee Feklisov) was the agent in charge of the ring. Klaus Prigsheim a faculty member at KU was the host when he talked in IIRC 1960. Arthur Schlesinger Jr. was his debate counterpart. Fomin sounded a lot like Bela Lugosi.

Several point out that it is not a OneTime Pad if you reuse the pad. The pad was reused because of the workload, and the code was broken. Fomin said that Ethel Rosenberg was not involved.

Re: No surprise there

[turbidostato]

"The expected message has certain bounds."

That end up being at least "A" or "no A" -or "A" or "B" (if there were just one message that could be recieved, you wouldn't need to get the text at all). As long as there're two messages that renders the same lenght, you won't be able to decypher by "cluing" it, not at all.

Just my previous message proves the point: if you are meant to attack, I'll send you a message telling just "option A", if I want you to retreat, I'll tell you "option B" -which is the most proper way to act if you are relying on OTP *because* of the fact that it can't be guessed at all unless you get your hands on the key (they already knew that by the war).

In other words: "Order 66" can't be set appart from the other 99 ones.

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:No surprise there

[AK Marc]

So sending the decryption key insecurly isn't improper use of a one-time-pad? Using a non-random seed for a generator isn't improper usage, because there is no improper usage possible, other than violating the very definition of a ONE-time-pad? I think your ignorance has you arguing stupid so you don't have to say "oops, I don't even know what a Scotsman is."

Re:No surprise there

[bruce_the_loon]

No technical reason that you can't split it up, as long as the decoders know where you are in the page. But if you're only using 10 percent of a page, you may as well tell your handlers so they can save money by printing shorter pages.

There are logistical issues though. If you're halfway through the 1000 chars and you're caught with the page still in the pad, it'll only be a matter of time before your captors extract that information from you. By destroying your page as soon as you've used even part of it keeps that information from being useful.

The second issue comes up with communicating what part of the page is in use. In the message sent by dead pigeon, there is an identifier somewhere in there of the page or at very least the book. That has to be done to tell the decoders what to use. While it is a risk to do so, it is mitigated by the destruction of your page. Now if you're using only segments of the page, then if the page still exists in your pad, the captors might not even have to break your kneecaps and extract your molars because they have identifiers in your captured messages of where to look.

Re:No surprise there

[udippel]

This sounds correct, but it isn't. Unfortunately.
It does contain relevant information, but kind of mixed up.

Length can be a helper when statistics comes into perspective. And when the one-time pad is a non-random piece of letters (book, e.g.) the ciphertext can display statistic non-uniform properties.

On the other hand, imagine a purely random sequence, then random + [non-random] plaintext = random. Or, as example, the ciphertext 'qgrmy' that I have just generated in this manner (so-called Vernam Cipher), could represent any 5 letter-word, or two words with an intermediate blank, or "a pad" or whatever. Continue on this thought, and length and statistics are no remedy. A ciphertext of length N produced with this method can represent any other text of length N. And brute-force does not help at all, because brute-force would come up with any possible text of length N; be it Shakespeare's Hamlet or the latest news from BBC. The likelihood of all those texts are all identical.
The major setback of this method is of course that the recipient would need the one-time pad of length N as well to decrypt the message, so it is not feasible for real-world cryptography.
Using a book-cipher as source of the random sequence is dangerous, because letters are usually unevenly distributed in books. Make it a Vignière of length N of random letters, and nobody will ever be able to decrypt it.

Re:No surprise there

[udippel]

One-time pad does not necessarily obstruct key reuse for longer messages. Like cyclic use of the one-time pad. One-time can as well imply 'once', in the sense of using this pad once, for one message, scribble it on silk and pass it to a messenger for easy hiding and digestion in the case of being caught; with another message using another one-time pad, and so forth. Like the transaction numbers for online banking. [I know that they are not used as keys, but for the sake of explanation of the term 'one-time'.]

Re:No surprise there

[udippel]

[How is this worth mod points?]
Two different messages can never be encrypted with a one-time pad.

Re:No surprise there

[Geirzinho]

Not true. The probability that the next letter in the OTP is (say) an A is always 1/26 when you have no prior knowledge about how the cipher clerk selected it. This is the optimal case, and any changes in how it is selected will only reduce the entropy of the pad.

*or did I just hear a whoosh over my head?*

Re:No surprise there

[Anonymous Coward]

It's like saying "long division is wrong" because sometimes you might perform it wrong ending with erroneous results.

That's just absurd.

Re:No surprise there

[Anonymous Coward]

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?

iPhone is a five letter word

Re:No surprise there

[Robert Frazier]

Depending on circumstances, one might also garner information by doing traffic analysis.
http://en.wikipedia.org/wiki/Traffic_analysis

If one is a known sending or receiving station for messages sent with a one time pad, one needs to make the pad storage and pad transfer procedures safe (I've transferred pads, by hand, while, unusually, armed). Then it is probably best to send messages of exactly the same length at exactly the same intervals, or, perhaps even better, (semi) random lengths at (semi) random intervals, making sure that the shortest length is greater than the longest needed message, and the longest interval is shorter than the time sensitivity of the message.

Best wishes,
Bob

Re:No surprise there

[Anonymous Coward]

Uh, no. If you're using a one-time-pad cyclically, it's not a one-time-pad, it's a message encoded with the one-time-pad as the key. And yes, the difference is huge. The whole point of the one-time-pad is that there is no pattern to the encryption, making brute force impossible. Cyclical use introduces a pattern into the encryption.

Re:No surprise there

[AK Marc]

There have been successful attacks against one-time pads where the cipher wasn't sufficiently random.

Re:No surprise there

[Sean Hederman]

The clue is that it isn't subject to cryptanalysis, it's indistinguishable from random letters. Virtually all non one time pad methods used in that period would be crackable using today's cryptanalysis tools.

Re:No surprise there

[Anonymous Coward]

Well, that's a matter of semantics. If you implement a large-scale, properly-designed one-time pad system, but then a pair of lazy and/or ignorant code clerks re-uses individual OTP sheets for some of the traffic between them (contrary to orders and training, of course), then do we say "it's not a one-time pad system", or that "it's a misused one-time pad system"?

Not really. If you give me a recipe for a cake, and I disobey the recipe and end up making a bread, is the bread a "misused cake"?

The system, as described by the instructions, is an OTP system. The system, in practice, is not.

Re:No surprise there

[joss]

The people running the program understood this stuff at least as well as you. The girls picking out the balls would have been working with exceptionally clear and inflexible rules.

Re:No surprise there

[Rich0]

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.

You might want to avoid getting personal when it is fairly obvious that you don't understand one-time pads.

With a properly-used one-time pad every possible message of the same length has equal probability of being the correct message. So, the decoded message might be "Meet infiltrator on beach bravo at 16:30 zulu." or "Assassinate general living at 1310 Main Street" or "Go to beach bravo for pickup at 11:10 zulu." or anything else you can imagine. There will be trillions of messages that don't make sense in context, and trillions of messages that do make sense in context. Likely it will be far more than trillions - however many valid sentences of that length.

Properly used one-time pads are simply impossible to break. They're also highly impractical, which is why they're rarely used.

I'm not sure if they were used for field agents in WWII. The problem with using them is that your agent would run out of key if too many messages were sent (though I guess you could take a risk and re-use some of it - if two messages were intercepted using the same key then they might be decoded, though if your transmission system is carrier pigeon the risk of that has to be lower). One-time pad systems are not designed to protect against key reuse so you're extremely vulnerable if you do it. Other systems normally involve key re-use and doing so does increase the risk of the code being broken, but only minimally. Re-supplying the agent with new key material would be difficult (you're talking about submarines carrying code books or whatever. One advantage of a one-time pad is that it is very simple to use, even by hand. Strong ciphers generally are fairly difficult to implement by hand.

To use a one-time pad the agent would need a code book as long as all the messages he would ever send or receive. Every time a line was used it would be crossed out, and pages should be destroyed when used up. Whoever is talking to all those agents would need a copy of the book for each one, and would need to follow the same procedure.

Re:No surprise there

[Anonymous Coward]

I'm curious: how do you tell by the looks of a cyphertext that it was encrypted with a one-time pad? Yeah, it's written in groups of five characters, and makes no (obvious) sense...but that is no clue as to the method used to encrypt the text. Breaking up words into equal groups is done (obviously) to obfuscate word boundaries, it's not a practice restricted to one-time pads.

Not only does the 5 group letters obfuscate word boundaries but is also a telltale sign that a look-up table was used for word encoding before encryption (If the message has any encryption apart from the look-up table at all and with the assumption that the UK military used a similar encoding as the military I served with.)

They way it works is that you had a list of common military terms like "tank platoon" "bridge" "infantry" and a corresponding five letter combination. Five letters are easy to remember short term so it works well for radio communication where you just tell the five letters with a short pause to let the writer catch up. If you only get four letters you know that you messed something.
The look-up table was changed at regular intervals in case the enemy gets their hands on it.

Re:No surprise there

[mikael]

Could be something like the "playfair cipher".
http://practicalcryptography.com/ciphers/playfair-cipher/

All you have to do is figure out the 26-letter code phrase used, of which there are 26! (26 x 25 x 24 x ... x 1) possibilities.

Could be something as simple as "The quick brown fox jumps over the lazy dog" (which was the original coded message to
signal the invasion of Normandy on D-day) or some words from a poem, novel or even the bible.

Re:No surprise there

[wvmarle]

In war time I can very well imagine a one-time pad being re-used for practical reasons, for example not having another one at hand and still needing to send out another message. Especially in older times, like the WW2 era.

Then also a whole lot of "security by obscurity" kicks in: not knowing two messages are encrypted with the same one-time pad, when you expect they are indeed using different pads, does add a real extra barrier for a potential interceptor to decrypt them.

Re:No surprise there

[Capt.Albatross]

Yes, otherwise there is no possibility of consider improper use at all.

But the possibility of improper use is considered in the citation that you questioned, through its very explicit list of conditions that must be met for the encryption to be unbreakable. You are being pedantic in an attempt to cover a mistake you made, but we can all see that the citation was satisfactory (it contained sufficient information for its purpose), and therefore that you were mistaken (or shall we say pointlessly pedantic, if we are being pedantic?) to say the citation was incomplete.

Re:No surprise there

[RobertLTux]

well if you figure out that your OTP has been compromised then yes you would use an alternate channel to get a new one.

Re:No surprise there

[Chris Mattern]

In war time I can very well imagine a one-time pad being re-used for practical reasons, for example not having another one at hand and still needing to send out another message. Especially in older times, like the WW2 era.

In which case, it's no longer a one-time pad. The user may keep calling it that, but calling a cow a horse doesn't make it a horse.

Then also a whole lot of "security by obscurity" kicks in: not knowing two messages are encrypted with the same one-time pad, when you expect they are indeed using different pads, does add a real extra barrier for a potential interceptor to decrypt them.

This makes no sense at all. A true one-time pad is completely unbreakable to anyone not in possession of the key. Deviating from the one-time pad protocol cannot do anything but weaken it.

Re: No surprise there

[gumbi west]

SSH does not use a one-time pad. If it did, you'd have to get data sent over sneaker net to act as the pads, and that doesn't happen.

Re:No surprise there

[wvmarle]

Deviating of course weakens it. But in practice, this may be irrelevant.

Imagine you're a German code cracker, and your men intercept like 100 messages sent out by the British forces (by shooting those pigeons) that are known to be encrypted using one-time pads and using code words. Maybe two of them have used the same pad: you don't know which ones, nor that this is actually the case.

As one-time pads are known to be uncrackable, you're likely not even going to try.

Re:No surprise there

[Capt.Albatross]

Strictly speaking, Venona was the project to decrypt the intercepted messages, started once it was realized that the encryption keys were being reused. Nevertheless, MrNaz is adopting troll-like behavior in his snarky and cryptic post, and his post here, unlike yours, contributes nothing to the discussion.

Re:No surprise there

[Sulphur]

Strictly speaking, Venona was the project to decrypt the intercepted messages, started once it was realized that the encryption keys were being reused.

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

Re:No surprise there

[TeknoHog]

Any cipher worth its salt will have this characteristic.

I see what you did there.

Re:No surprise there

[gadzook33]

Yeah, the government never makes mistakes.

Re:No surprise there

[Capt.Albatross]

If you tried to bake a cake with a recipe and/or knowledge of what ingredients go into a cake and how to put them together, but mis-measured the eggs/used high-protein flour and so ended up with a shitty cake I would cry no-true-Scotsman when someone said you weren't making a cake.

This is quite ironic, considering your sig:

Analogies don't equal equalities, they are merely somewhat analogous.

This is not a useful analogy of the one-time-pad issue, because in that case, the distinction is not predicated on an ad-hoc definition.

The essence of the no-true-Scotsman fallacy is its arbitrary and entirely self-referential circularity: the definition of trueness implicitly adopted by the fallacy's maker is exactly that which (in his mind) makes his argument true - nothing more, nothing less. In particular, it is not derived from any consideration beyond the fallacious argument, and it is not a useful definition in any wider context.

You claim that it is a no-true-Scotsman fallacy to say that an encryption key is not a one-time pad if it is used more than once.

Firstly, it is important to note that this is a narrow claim about semantics: what, exactly, can the the phrase 'one-time pad' be used to denote? It is not a claim about encryption (even though it is made in the context of encryption) because the facts of encryption do not depend on whether this claim is correct.

For your claim to be correct, the assertion 'an encryption key that has been reused is not a one-time pad' must be ad-hoc, introduced solely for the purpose of making an argument look valid, but it is the opposite of that. As you yourself point out, non-reuse is essential to the purpose for what one-time pads are created and used, so the assertion is predicated on a very meaningful distinction. Therefore, it is not a no-true-Scotsman fallacy.

You may think you are still right on the usage issue. Rather than take a position on it, the rest of us can ignore it, because we can make ourselves perfectly clear to one another by considering the context in which the phrase is used. In particular, your original claim that the citation (about the security of one-time-pad-encrypted messages) was incomplete is still wrong, as it very adequately covered the ways in which a key intended to be a one-time pad can be misused.
 

Re:No surprise there

[vikingpower]

Another approach would be the calculus of an entropy vector, based upon the relative frequencies of the letters of the alphabet. If the used alphabet has n letters, then one would need to calculate an n-dimensional entropy vector, and compare that one with entropy vectors calculated from texts used in WW II for one-time pads. Could that possibly work ? ( I know, the encrypted text is very short, I know... )

Re:No surprise there

[Capt.Albatross]

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. Less than perfectly random sources can be another attack vector. "Used properly" is not just about protecting the key.

Reusing a key or generating a key from less than perfectly random keys are both key-protection issues, as they both provide avenues by which an attacker may recover the key, and in both cases, these attacks depend on properties of the key, not the message.

Re:No surprise there

[Burning1]

It's no longer a one time pad, if you use it twice.

You are technically correct, the best kind of correct.

You're also being pedantic and confusing in that sort of way that detracts from a conversation rather than adding to it.

Re:No surprise there

[Capt.Albatross]

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

In addition to all the valid arguments against this fallacy that have been made here, it is perhaps worth noting that most of the clues you are positing are equally valid whether or not you have an intercepted message. The only constraints that having a message puts on your set of clues is the fact that some message was sent, the maximum length of that message, and some constraints on the time and location of its creation. You cannot even know whether the message is pertinent to your clues. Guessing the content of a message from these clues is not decrypting it, even if, by chance, you get the exact wording right, and if you are doing this sort of guessing, the specifics of the message's encryption are irrelevant.

Re:No surprise there

[mysidia]

Bad things happen when people attempt to use intuition to make decisions about security and risk, without fully understanding the mathematics and the statistics involved.

Re:No surprise there

[hairyfeet]

Exactly, just because it was 70+ years ago didn't mean they didn't have strong crypto back then. Just look at VENONA or the Enigma, in both of those cases what allowed them to be broken was that the other side screwed up and either kept using a pad (VENONA) or in the case of Enigma there were flaws in the design (a letter could never be encoded to itself) and several times messages were re-broadcast due to transmission troubles without bothering to change the settings.

Most likely like those handful of late war enigma cyphers (or the 70% of VENONA messages we failed to crack) we'll never decode it, the message is simply lost to history, any copies of that pad were trashed decades ago and without it all you will get is gibberish.

Re:No surprise there

[Anonymous Coward]

Or they find a code book with that day's pad in it, in a long forgotten room or something.

That would be their best bet. The message states that there were two copies sent (two different pigeons) so assuming that one message got through a copy might exist. I don't know if it was procedure back then to destroy the message after it was delivered, or if a copy is archived somewhere.

Re:No surprise there

[Anonymous Coward]

Semantics, just like this?

Re:No surprise there

[laejoh]

Calculating he Airspeed Velocity of an Unladen Pigeon (African or European) will give you two OTPs!

Re:No surprise there

[Anonymous Coward]

Well not all random numbers are truely random

Please elaborate.

Re:No surprise there

[DrVomact]

That seems surely reasonable. My problem with the OP was that he seemed to say that you could tell it was a one-time pad by merely looking at it. Also, SOE by no means used good cryptographic techniques consistently (the infamous "poem code" comes to mind). But this may not have been SOE, of course.

Re:No surprise there

[pointyhat]

Ha I actually weed myself. Thats the price of getting old.

Re:No surprise there

[v1]

Considering the brits managed to reverse design an enigma machine based entirely on analysis of the traffic, (and were btw quite amazed at the similarity when they finally got one off a nazi sub) it's easy to see that they will go to extraordinary lengths to decrypt messages.

Reuse of an OTP would very quickly be identified and broken if your adversaries are resourceful and serious. And in world wars, they usually are.

Re:No surprise there

[ld a,b]

If you only have two messages you can only get K^A K^B and A^B. This doesn't directly give you the key.
However as A^B is just a plaintext encoded plaintext, decyphering both plaintexts is relatively easy. Where relatively here means infinitely easier than provable impossibility.
Ridiculously easy if A and B were black and white images. See http://www.cryptosmith.com/archives/70
Getting the key is then trivial.

Re:No surprise there

[Anonymous Coward]

Bolding, it means nothing, it was inserted randomly!

Re:No surprise there

[arose]

It's like saying that long division performed with an error is not long division any more, and that therefore it's impossible to get wrong results with long division. Then furthermore defending such a position on the basis that "division" is right in the name and getting incorrect results means that you weren't dividing at all, but rather something else entirely.

Re:No surprise there

[arose]

All cakes are perfect, there is no such thing as a chewy cake as it falls outside of the definition. It's impossible to make a cake wrong, it's only possible to not make a cake. In fact, it's impossible to do anything wrong, there are no true errors.

Re:No surprise there

[arose]

So, Debian was not in fact generating weakened DSA keys when they messed up the RNG in OpenSSL? The spec requires proper entropy, thus the keys though seemingly compatible weren't DSA keys at all?

Re:No surprise there

[arose]

OP was selectively emphasizing their quote to support the argument that only the full key can be considered a clue to the key, this is not the case outside of perfect implementations. It's the difference between determining that a one-time pad was (attempted to be, if one insists on defining away errors) used and giving up because it's impossible to decrypt and attempting to crack it on the basis that knowing the definition doesn't tell you everything about the message in front of you.

Re:No surprise there

[Chris Mattern]

If the DSA spec has entropy requirements that they were not meeting in key generation, then, yes, they were not DSA keys, but merely DSA-compatible keys.

Re:No surprise there

[jeepien]

(also, even a single re-use can completely compromise all other messages that used a given pad....)

You mean the one other message?

Re:No surprise there

[Anonymous Coward]

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.

No. There are not just "any number" of possible decodings - every decoding is possible. The only piece of knowledge that can help you decode the message is the key or a fragment thereof (or a decrypted copy of the message - but that's cheating). That's it. No amount of clues can help.

Context can help you narrow down from a huge list of possibilities to a smaller list of possibilities, but you gain no information from this. You start with the context that your enemy is sending a message on what time to attack. With that knowledge, you narrow down the list of possible messages to all messages about attack time. So you know that your enemy is sending one of the messages about what time to attack. Which is your "clue" - you added nothing.

Re:No surprise there

[jalind]

Not surprised by any of this.

One thing that sets this message apart and makes it unique from the 30 or so museum examples of Pigeon Service messages is that it contains 27 five-character blocks of encrypted content.

Messages not only comprise their message text, but also preambles, postambles and handling annotations that comprise other information about the message and its transmission. Comments elsewhere indicate XO2 was UK's Bomber Command in WWII. There are a number of items that are probably not part of the encrypted message but are message header material and relevant to its context that may be important to routing it to where the message itself can be properly decoded and its contents used. They are quite distinct from the 27 five-character blocks in the message body. The more enigmatic one of them is the AOAKN that is the first and last cypher block in the text. It may or may not be encrypted, part of the message or may serve some other purpose in the encryption/decryption or message itself. By looking at the writing, at least two, possibly three persons, or more, wrote on the message form. The 27 is most likely a check count of cypher blocks. There are 27 cypher blocks and the number 27 is most likely a check count for the message (in case it gets damaged en route). Another annotation not part of the 27 cypher blocks is the 1525/6 at the end of the cypher blocks. It may refer to an OTP serial number and page within the OTP or some other similar identifier to get to arrive at a correct decryption key by the recipient.

If OTPs were used with pigeons, there would be no guarantee as to which messages would arrive in what order, so some indicator would be needed to sequence the use of the OTP pages at the receiving end. Also note that there is a full-stop (i.e. period) at the end of each 12 cypher block group and one after the 1525/6 annotation. There are two other dots as well. They may be as simple as a pencil rest point when counting blocks, have other causes or have more significance. Also note that the digit 6 after the virgule follows the digit 5 before the virgule. This may be shorthand for 1525 and 1526 indicating that two pages of an OTP were used because the message exceeded the length of a single OTP page.

The message was sent by two different pigeons, their serial numbers both noted on this message. Something to note about these particular serial numbers is that neither are recorded in the British records of their military pigeon service which gives reasonable speculation, along with other information about where the pigeon was found and its likely flight path, that they were part of a very secret set of pigeons managed at Bletchley Park that belonged to MI6 (or its equivalent in WWII).

There is another annotation in roundhand (cursive) that appears to be "lib." followed a four-digit number that may or may not be a 24hr clock time. It may or may not be a reference to when the pigeons were released as opposed to when the message was created. It was written using the same type of writing instrument as the XO2. The cypher text and cypher notations ("27" and "1526/6") are in blue, along with the time of origin and the sender's signature. The rest are in black. Letter and number formations appear somewhat different between the blue and black. The blue may be from using a "blue" type carbon paper to create two identical copies of the original message and the other annotations in black from subsequent handling before being sent by the pigeon(s).

Another thing to keep in mind is that civilian non-commercial, commercial and military messaging very frequently use short-hand codes for standard message texts and handling. Typical non-military examples are Q signals, ARL signals, and commercially created telegram encoding to reduce the length of common message texts and eliminate the possiblity of transmission errors. One example from the US Amateur Radio Service used in Radiograms is ARL FIFTY where the prefix ARL indicates a numbered message text and FIFTY (spelled out) is th

Re:No surprise there

[jalind]

Yes, it would erode the cryptographic integrity. However, one needs a little more material than just the 27 five-character groups to do a statistical attack based on that possibility.

Re:No surprise there

[jalind]

With this stuff, not likely. The amount of supervision and the clarity of instructions and severity of consequences for not following them would have made it very unlikely that they would have deviated from what they were told to do. The women the US Navy got to make the US mechanical and electrical equivalents of German Enigma machines were told uneqivocally that they would be subjected to a court-martial and shot if they revealed anything about what they were doing. These US made machines were the ones used to decrypt intercepted German message traffic encrypted with German Enigma machines after the Bletchley Park code breakers were able to crack the key used for a batch of messages.

Re:No surprise there

[gadzook33]

As a government employee I can assure you our incompetence knows no bounds.

Re:No surprise there

[Pseudonym]

Yes, I was considering mentioning this, but didn't.

Padding to a five-letter boundary is indeed very common. However, for completeness, it's rare to pad more than that when the encryption is done by hand, as appears to be the case here.

Re:No surprise there

[Pseudonym]

Actually, it was even worse than that. The same physical wires were used both for "input" and "output".

Let me try to explain. Each rotor was a short cylinder with 26 contacts on each end. Inside the wheel were wires which connected the pads on one end with the pads on the other end. Typically, these were not the same pads. So applying a voltage to a pad on one side would make the voltage appear on some corresponding pad on the other side. This effectively implemented a permutation of the alphabet.

The machines, of course, had several (interchangable) rotors, which rotated after every keypress. Ignoring the rotation for the moment, pressing a key would apply a voltage to one of the pads on the first wheel, then the voltage would be transferred through the wheels to the other side, so you'd apply one permutation, followed by another, followed by another.

However, the lamps which indicated the "output" letter were not (electrically speaking) on the other side of the rotors. They were back on the keyboard side. On the other side of the rotors was a component known as the "reflector ring", which implemented yet another permutation which never mapped a letter back to itself, and then reflected the electrical signal back through the rotors. The lamps were wired to the same side of the rotors as the keys.

That's the main reason why Enigma could never substitute a letter with itself: you need a separate return path to make a circuit.

(Note: This is the basic Enigma design. The actual machines changed throughout the 30s and 40s, usually implementing a new security measure withing weeks or months of the Polish or British cryptographers cracking the previous one. The introduction of the steckerboard was the biggest hurdle, and famously it was Alan Turing himself who worked out a method of breaking it. I digress.)

The weakness wasn't actually that Enigma couldn't map a letter to itself, though that did help a little. The weakness was actually that the permutation applied by the rotors in one direction was "undone" on the way out, which revealed an awful lot about the design of the system to anyone who knows some group theory. Someone like Marian Rejewski, in particular.

You see, the bare Enigma can be thought of as a group action on an alphabet. We'll call the group action of the rotors W, and the group action of the reflector ring R. Then the overall cipher is C = W' R W. Now here's the neat bit: C and R have the same conjugacy class and hence the same cycle structure. By analysing the cycle structure of C (which you can do by traffic analysis, since all operators in the same domain started off with the same rotor settings every day), you can completely recover R.

This theorem, by the way, is informally known as the theorem which won World War II.

Re:No surprise there

[Pseudonym]

No. The Brits managed to reverse engineer an Enigma machine based on traffic analysis and the materials provided by Polish crypographers. The Poles, in turn, managed to reverse engineer an Enigma machine based on traffic analysis, and a copy of the original patent, and a bunch of stolen material.

The British crypographers also had one trick up their sleeve which wasn't available to the Polish ones: they could mount a fairly effective known-plaintext attack. They would send ships out to be deliberately "spotted" by Germain submarines and then listen for the inevitable signal, using direction-finding to be certain that they were capturing the correct one. These reports would have a fixed structure, and since they knew exactly where and when the ship was spotted, they effectively had the plaintext as well as the ciphertext.

Re:No surprise there

[Anonymous Coward]

3 and 1/8th times!

Re:No surprise there

[socceroos]

I need mod points.

Re:No surprise there

[jalind]

Yes, I do.

VENONA was a project, a collaboration between the US and UK, that partially cracked the Soviet diplomatic/spy encryption that used a OTP key system. In my remark, I casually referred to the OTP system used by the Soviets as Venona, but VENONA was the project that partially cracked it, not the OTP system itself. The Soviets made a serious blunder when some of the same key sequences were re-used in the system. Some of the re-use is possibly accidental by the Soviets responsible for creating the keys, other of the re-use may have been caused by the need for huge amounts of key material and a shortage of available material. The creation of really random OTP key material in the time-frame of VENONA was labor intensive and slow.

The re-use enabled the US and UK to eventually decrypt all of some messages and portions of others in the post-WWII 1940s and very early 1950s. There can be a lot of conjecture as to how the US/UK cracked the keys, but some of it may have involved obtaining clear text for some of the messages compromised elsewhere, reverse-engineering the key material from that and then seeing if any other encrypted texts would decrypt with the key material thus obtained. The bottom line is that the VENONA project would have had ZERO success if the Soviets had not re-used key material in the messages on which the VENONA project was working.

Re:No surprise there

[Anonymous Coward]

It took you a week to read all that on Wikipedia?

Re:No surprise there

[NikeHerc]

Considering the brits managed to reverse design an enigma machine based entirely on analysis of the traffic, (and were btw quite amazed at the similarity when they finally got one off a nazi sub)...

As another poster has pointed out, the Brits didn't reverse engineer an Enigma based on traffic analysis. The Americans did, however, reverse engineer the Japanese Purple machine in spite of never having seen one. It was quite a feat of cryptanalysis.

Packet Loss

[Anonymous Coward]

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

Re:Packet Loss

[Anonymous Coward]

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

This packet wasn't lost. It was just delayed in transit.

Maybe they should try

[Anonymous Coward]

Pigeon. It is a difficult and nuanced language but there are plenty of speakers.

It was easy with...

[Anonymous Coward]

Little Orphan Annie's secret decoder ring.

It says: BESUR ETODR INKYO UROVA LTINE

Which is WWII code for staying hydrated w/ vitamins.

Re:It was easy with...

[AwesomeMcgee]

ironic timing...my wife makes me sit and watch a christmas story every thanksgiving eve

Re:It was easy with...

[camperdave]

You could make her watch my brother's favorite Christmas movie: Die Hard.

Re:It was easy with...

[Anonymous Coward]

Merry fuckin' Christmas

Re:It was easy with...

[Anonymous Coward]

Yipee ki yi yay motherfucker!

Re:It was easy with...

[Anonymous Coward]

Yipee Ki-yay, Mr. Falcon!

Weeks

[nurb432]

Should give it some time before one calls it quits.

Re:Weeks

[Anonymous Coward]

Indeed. Lacking the one-time pad, this is simply a matter of having enough computing power. Waiting a hundred years may provide us with enough computing power to crack the code in a matter of centuries.

Re:Weeks

[OneAhead]

It very much looks like they quickly concluded that it was encrypted with a one-time pad. Bearing in mind that this was encrypted using practices devised by the same institution that's trying to decrypt it now, this conclusion can't be difficult to reach. Now, a truly random OTP with a length that is equal to or longer than the length of the message has been mathematically proven to be 100% secure against cryptanalysis by anyone who doesn't have the key. So that's what they're doing now - figuring out if the key is archived somewhere.

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:Weeks

[drkim]

...One of those permutations will yield LOVE. Another will yield HATE. Which one is the correct message?

Considering this is /. probably: NERD

Re:Weeks

[__aajfby9338]

Neither. The correct message is "BUTT". :)

Re:Weeks

[CPNABEND]

Wouldn't the key be XYZZY?

Re:Weeks

[yusing]

WXYZ = The Detroit radio station where The Lone Ranger got his start.

In case that's a clue.

Re:Weeks

[mikael]

What happened to the other pigeon? There were two of them. Did they both fall down chimneys?

Cracked!

[Anonymous Coward]

I just installed windows XP using the first row.

Cannot be decoded

[Anonymous Coward]

Have they tried a german dictionary yet?

The answer

[erroneus]

Eggs, Milk, Cheese, Bell Peppers, Ham and Onions... ...it's the recipe for my typical omlette!!

Re:The answer

[Pseudonym]

Ah, but in the UK, they're called "sweet peppers" or just "peppers". Maybe it's a duress code?

Be sure to drink

[mrmeval]

OVOMALTINE!

http://www.ovomaltine.com/

BTW light wheat malt, fresh milk and fresh chocolate syrup is tastier but not as convienient. For an improved taste use sprouted wheat flour ala diastatic malt. This is the only ahref=http://www.ehow.com/how_4620081_sprouted-wheat-flour-diastatic-malt.htmlrel=url2html-22218http://www.ehow.com/how_4620081_sprouted-wheat-flour-diastatic-malt.html> place I could find it.

Yes it is on topic if you know history. ;)

Done

[Lord_of_the_nerf]

"Dearest Benito, bunker is boring. Eva going stir crazy. Any idea how Battle for Berlin going?"

Re:Done

[drkim]

Shouldn't someone do a "Hitler Rants" subtitled clip for this already?

Paging.....

[Anonymous Coward]

Paging DVD Jon, to reception please...

It probably said:

[fotoguzzi]

pleas ebloc kallc himne ysstu pidpi geons

Re:It probably said:

[Anonymous Coward]

pleas ebloc kallc himne ysstu pidpi geons

gean yus

Easy!

[Anonymous Coward]

Wenn ist das Nunstück git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!

Re:Easy!

[Anonymous Coward]

Wenn ist das Nunstück git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!

HHAHAHAHAHAHAHAHAHAHAHAHA!

*dies*

Re:Easy!

[Anonymous Coward]

Wow, some people really don't know comedy!

Re:Easy!

[Anonymous Coward]

Let's see what he wanted to tell us:
Wenn - When
ist - is
das - the
Nunstück - sorry, no such word exists in German, but the second part translates to "piece". Did you mean "Mundstück" (mouthpiece)?
git - sorry, no such word exists in German. Did you mean "gilt" (is in effect/is considered)?
und - and
Slotermeyer? - Based on the second half of the word, this must be a family name.
Ja! - Yes!
Beiherhund - Did you mean "Berher Hund!" (Come here dog)? Btw., few people use "beiher" nowadays.
das - the
Oder - As it starts with an uppercase letter, it must be the name of the river at the border to Poland. But then you should have used the feminin definite article.
die - the
Flipperwaldt - Must be a name. As it ends on an old form of "wald", it is probably related to a forest.
gersput! - Sorry, no such word exists in German.

Re:Easy!

[Anonymous Coward]

It was from a Monty Python sketch.

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

So then.....

[Anonymous Coward]

If Highly trained and I suspect well paid crypto experts can't handle it, only one thing left to do.

Post it on the internet and watch it decrypt faster than a Valve ARG game.

Re:There's an Idiocracy joke in here somewhere.

[icebike]

For all we know 4 or 5 pigeons were released, each with only every 4th or 5th letter of the text, all encoded differently.
With that kind of packet loss even three letter agencies would be at a loss

Maybe it was a fake...

[3seas]

... a joke someone intentionally left... it can't be crecked because its not encrypted.

Get Valve to post it

[Anonymous Coward]

And claim it holds secrets to Half Life Ep 3 and it will be cracked in hours.

Its worse than that.

[Anonymous Coward]

My Aunt was a radio communication specialist in the channel islands where they communicated with the underground and later the anti Nazis within the third reich. My Dad was involved in counter espionage within Great Britton. They were both recruited by the Canadian military and then trained by the combined British and Canadian military intelligence division long before the US joined in.

Not only was key info done with one time cipher it also used specialist language. For instance the word pie after decryption might be construed to be to mean supplies. Only the individuals who were taught the language could decode it and no more than a few individual agents sending info from within Germany or France used the same code specific language.

If the pigeon corpse was from D Day then it would have been really early in the landing. As the beach head was secured the code receiving specialist people moved in to undisclosed places in Normandy. Are they absolutely certain the pigeon was from D Day? If not it may have been from other sources as my aunt told me there was some underground agents using them before 1944...Some even in the Dieppe region!

Re:Its worse than that.

[ewanm89]

The message was sent to GCHQ in Cheltnam to decode, GCHQ is what replaced the Government Code and Cipher School which was based at Bletchley Park and had 2 tasks: 1) keep our communications secure using codes and ciphers and 2) break AXIS codes and ciphers. People focus on the second one but the first is also important and we were very good at both parts. Now they kept copies of the code books like you describe (our bomber crews replaced them regularly and were charged with burning their copies if they crashed), these were mostly used for spoken communication where one is still saying words into a radio. I expect they just can't figure out which cipher key was used as this is a cipher not a code. And they would just have to go through the codebooks to find the right one if they found it was a code too.

Re:Its worse than that.

[Anonymous Coward]

So is it safe to say, then, that they were Dieppe undercover?

Re:Its worse than that.

[Anonymous Coward]

The message was sent to GCHQ in Cheltnam to decode, GCHQ is what replaced the Government Code and Cipher School which was based at Bletchley Park

Thanks ;-)
Most of what my Aunt sent came from GCHQ. So we can assume the pigeon is post August1942 Dieppe for the reason you stated? Oddly enough much of what happened to my Father is still classified as there are still some family members who would be hurt by the truth about what happened in England and the covert events surrounding Dieppe!

Re:Its worse than that.

[wvmarle]

This article, the source of it all, suggests something like you describe - but even better. But instead of using actual words as code, each five-letter group stands for a word (or common phrase maybe?). So without having the key to how to replace the five-letter groups to something sensible, there is no way of knowing what the meaning is.

On top of that they suspect the coded message is in turn encrypted using a one-time pad. Making it impossible to even get back the coded message.

The only real weakness in these encryption schemes is of course the key exchange, the encryption itself is better than what we use now: most modern encryption is crackable by brute force (albeit so hard it takes like forever).

Re:Its worse than that.

[Anonymous Coward]

My Dad was scheduled to go to Dieppe to oversee the gun placements on the beach that would target the streets around the hotel where the real objective of the Dieppe raid was. German Navy HQ.

However like many loyal soldiers after the first cancellation of the raid he knew it was now a suicide mission, and spoke up about it in the barracks. He was called on the carpet and his loyalty was questioned. Because his IQ score was ranked very high and he was being groomed as a gunnery intelligence officer, the intelligence branch grabbed him for other duty within Great Britain (which I miss spelled the first time because I am schooled in Old English and nervous as I write this). His sister who was younger was at the time being trained in radio communications and the use of code. She was also a crack Morse operator as this was her initial training.

At the time there were some Nazi agents using prostitutes as bait around about the Canadian army encampments. HE WAS BRIEFED about how to find them from some others within his battalion whose loyalty was in question but were not as smart about what they were doing and talking up about how bad an idea the raid was.

After gaining the info about where and who to get in contact with about the brothel/spy ring he was then told to go awol and gather info on the pimp.
He obeyed and found the location and the info about the spy/pimp....then he allowed himself to be picked up by the MPs and was debriefed. Later he was told that the target agent and the prostitutes had been summarily executed...

End of one very short and inglorious story about Dieppe but as GOD is my witness this is what he told to me. Both my Father and his Sister are dead now so it is time that their story in all its ugliness and secrecy be told.

Thanks slashdot for letting me finally spit it out!

Re:Its worse than that.

[ganjadude]

Thank you for sharing, I love hearing stories from that era, Especially from family members of those involved.

Re:lol

[Anonymous Coward]

Really, Mr. Ballmer, you need to take some anger management classes.

Re:There's an Idiocracy joke in here somewhere.

[_Shad0w_]

The bits of government responsible for creating and maintaining cyphers are different to the bits of government that use them; the problem is generally with the end users.

onetime pad vs code designed for a single mission

[Anonymous Coward]

"Code breakers believe there are at least two possibilities for how the message was encrypted, and why it’s so hard to decrypt. It may be based on a “onetime pad” that uses a random set of letters (known only to the sender and the recipient) or on a now probably destroyed code book designed specifically for a single operation or mission."

isn't a "on a now probably destroyed code book designed specifically for a single operation or mission." a onetime pad technically. if not, what is it?

The Next Step.

[gallondr00nk]

In the UK, in our authoritarian wisdom, we made it illegal not to provide passwords or decryption to encrypted material.

GCHQ are now well within their rights to arrest the pigeon to learn it's secrets.

Re:The Next Step.

[vux984]

GCHQ are now well within their rights to arrest the pigeon to learn it's secrets.

http://xkcd.com/538/

Looks like we've found an edge case where that might not work. I'm not putting it past them trying though.

Re:There's an Idiocracy joke in here somewhere.

[Kjella]

WWII had codes we can't crack but governments today are routinely hacked and their passwords dumped in pastebin?

Only because things have to be decrypted at some point. The cryptographic primitives (symmetric encryption, public/private encryption, hashes, MACs etc.) don't change much and have been pretty much rock solid. People still use RSA as invented in the 1970s, except with longer keys. I don't recall any mainstream symmetric cipher being broken either, DES had too short keys (56 bits) but you still have to brute force it. If all you have is an encrypted message you'll get nowhere in 2012 with RSA/AES, you'd get nowhere in 1991 with PGP using RSA/IDEA and you'd get nowhere in WWII with this pigeon code. Back then you could break into the pigeon farm and find their codes, today you can break into servers and find their keys. Not much has changed there either.

Fawlty Towers, pigeon scene

[Anonymous Coward]

http://www.youtube.com/watch?v=SvBOLCFRAFc

/.'rs already told you what it said -

[Anonymous Coward]

Drink more Ovaltine!

Re:Dumb down

[pluther]

When you are complaining about how stupid other people are, you really should make an effort to use correct spelling, grammar, and punctuation. Your post failed at all three, in addition to your lack of understanding of how capital letters work.

Re:There's an Idiocracy joke in here somewhere.

[drkim]

For all we know 4 or 5 pigeons were released, each with only every 4th or 5th letter of the text, all encoded differently.
With that kind of packet loss even three letter agencies would be at a loss

...and this might only be the "CheckSum" pigeon...

Re:onetime pad vs code designed for a single missi

[drkim]

...a now probably destroyed code book designed specifically for a single operation or mission...

Perhaps it is possible that the MOD still has a backup of the book/pad. While a field agent would tear off and destroy one-time pad pages, the HQ would retain the original.

Re:Dumb down

[cusco]

In addition to being too dumb to figure out how to register for an account.

What if that is the one time pad?

[LordZardoz]

What if that is not an encrypted message, but the encryption key for a message?

I am not a cryptography expert, but I suppose there would be no way to discern the two right?

If it is the key and not a message, than no amount of decryption effort would matter.

END COMMUNICATION

Re:What if that is the one time pad?

[swillden]

If a one-time pad was used, it doesn't matter one bit whether the paper contains the key or the message. No amount of cryptanalysis will recover anything, ever.

Re:onetime pad vs code designed for a single missi

[Mr Z]

You could design a single-use code that isn't a random pad, such as assigning meanings to sequences of letters, in essence making a set of "words" for that mission. For example, "CQ" might mean "soldiers", "TQ" might mean tanks, etc. Notice in the ciphertext, the triad JRZ is repeated twice and the first and last 5 characters are the same.

That said, spot checking a few letters, it appears the distribution is pretty flat, suggesting an OTP. If you strike the last 5 letters (assume they're a repeat of the first 5, a sort of framing protocol), you'd expect each letter of the alphabet to get used around 5 times, and that's about what I see.

It's not ROT13

[anonymous_wombat]

Grandparent is getting OTP mixed up with ROT13. I do that all the time. It cost me my job once.

I tested that. I even ran it twice, just to make sure.

Re:It's not ROT13

[marcosdumay]

What did you run twice? The XOR one time pad or the ROT-13?

Re:It's not ROT13

[redalien]

What did you run twice? The XOR one time pad or the ROT-13?

Why, for the love of all that is holy, is this not +5 funny?

Re:It's not ROT13

[redalien]

Good job, people with mod points.

Have the tried India?

[140Mandak262Jamuna]

When all the old Cobol programmers were dead are retired, and the y2k hysteria descended up on us, they found a large and active community of cobol programmers in India. May be the Indian Army is still using the techniques they learnt from the Brits to get secret messages our of Islamabad and Lahore, Pakistan to the Research and Analysis Wing in New Delhi. So check them out. Some Havaldar-Major Harpreet Singh, 109th Signal Company, 7th Punjab Guards might recognize the code.

Re:onetime pad vs code designed for a single missi

[__aajfby9338]

Nope. A codebook is an entirely different system than a one-time pad. Codebooks are breakable given enough traffic; see Kahn's The Codebreakers for many examples of codebook breaking in history, as well as some insight into how it's done. One-time pads are truly unbreakable if properly implemented (they can be broken if certain serious mistakes are made such as re-using a key, allowing key material to fall into the hands of an adversary, etc.). Code books and OTP can be used together, including informal code-book-like schemes such as using understood nicknames for things. For example, "Charlie" probably wasn't formally recorded in a true codebook during the Vietnam war, yet it would have been a commonly understood code word for enemy troops among US soldiers.

lets name the algorithm...

[CosaNostra Pizza Inc]

Even though it hasn't been cracked, yet...let's call it "Dead Pigeon Cipher"

Re:There's an Idiocracy joke in here somewhere.

[DrVomact]

For all we know 4 or 5 pigeons were released, each with only every 4th or 5th letter of the text, all encoded differently. With that kind of packet loss even three letter agencies would be at a loss

Actually, I'm pretty sure there were two copies of the message sent. I deduce this because of the arabic numeral "2" entered on the form field titled "Number of copies sent". Also, there's the identifier codes for two pigeons on the message. Or didn't you look at the pretty picture in TFA?

One-time pad

[ebcdic]

Having "some clues about detecting a successful decoding" doesn't help with a (correctly-used) one-time pad. Every message of the correct length can encode to the same cyphertext, for some one-time pad, so in the absence of the pad the cyphertext contains no information at all about the message except its length.

Just to be quite clear about this: you say "[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", but *every* perfectly structured sentence of the right length with those properties is a possible decoding.

But Slashdot can!

[jago25_98]

$5 in BTC says Slashdot can do it ;)

hiya

[Anonymous Coward]

vice president just arrived in Amsterdam (and some coordinates i can't make sense of)
i think it was written by an american, because germany only had a prime minister.

this is too dumb.

cracked part of it

[bigpickle]

?? ???? ?? drink your ovaltine

Thinking in reverse

[Garybaldy]

Is there a possibility of that being the one time pad?

...? Really?

[skyggen]

If only we had a device capable of permutating every possible combination.

Re:...? Really?

[Arker]

If only we had a device capable of permutating every possible combination.

If only it were that easy. Unfortunately without knowing what kind of code or cipher this is the possible permutations are pretty much infinite. It seems very likely to me from glancing at it that this is a simple substitution cipher from a one-time pad, but I could easily be wrong. IF that is correct, then yes, a modern computer shouldnt have real difficulty calculating all the possible permutations. Unfortunately that doesnt mean you have solved it, you will be looking at a very large number of possible plaintexts. Even once you use another computer program to reject ones that are obviously wrong, you may still have quite a few possibles to review by hand. And it's quite possible that more than one of them will actually make sense, in which case you STILL have no way to tell which one is right. You cant even be sure that any of them are right, if there isnt some way to independently verify your assumptions. That sort of decryption method will produce intelligent messages when used to analyse meaningless noise.

Re:...? Really?

[jalind]

Yes, really. With a OTP, every possible permutation and combination of letters and numbers is an equally probable decryption including all texts from the Bible, Shakespeare, the Unabridged Dictionary, Encyclopedia Britannica, Journey to the West (Chinese), War and Peace (Russian), El Cid (Spanish) and any other text in any possible language since every possible permutation and combination of letters and numbers is a possible key. That is the great strength of OTPs. Any string of letters and numbers is an equally probable key and any usable and/or readable text an equally probable decryption. They are completely impossible to crack unless the OTP is not generated correctly or is misused.

The CIA would not have been able to break the Soviet's Venona if it weren't for its misuse, and, even then, it was not broken completely. In the case of Venona, the CIA was able to use plain text or predictable plain text from one use of a one-time-key with something they didn't know that (through ineptness or stupidity) that used the same key. Otherwise, the Venona documents would be just encrypted junk. The downside of OTPs are that each end has to have the same OTP, the use has to stay synchronized and, if the OTP gets captured, every message created with it is potentially compromised if any already used portion of the OTP is captured. That is why, with OTPs, the most important rules were to never reuse any portion of the pad and to destroy all already used portions.

In this case, the sender would have destroyed the part of the OTP used on creation of the message. if the other copy (there were two copies sent) was received and a OTP was used, the receiver's part of that OTP would have been destroyed making ultimate decryption impossible. What is possible is marrying up the encrypted message with the other copy that was sent if it was received and decrypted. Marrying the two together would use information such as the header, preamble and postamble information which would be the time sent, the person sending it (Sjt Stott, in modern spelling Sgt Stott), the recipient, the pigeon serial numbers and the somewhat enigmatic AOAKN starting and ending blocks and 1525/6 found at the message end.

Re:...? Really?

[jalind]

Yes, really. Brute force is useless with OTP encryptions if they are used correctly. With a OTP, every possible permutation and combination of letters and numbers is an equally probable decryption including all texts from the Bible, Shakespeare, the Unabridged Dictionary, Encyclopedia Britannica, Journey to the West (Chinese), War and Peace (Russian), El Cid (Spanish) and any other text in any possible language since every possible permutation and combination of letters and numbers is a possible key. That is the great strength of OTPs. Any string of letters and numbers is an equally probable key and any usable and/or readable text an equally probable decryption. They are completely impossible to crack unless the OTP is not generated correctly or is misused.

The CIA would not have been able to break the Soviet's Venona if it weren't for its misuse, and, even then, it was not broken completely. In the case of Venona, the CIA was able to use plain text or predictable plain text from one use of a one-time-key with something they didn't know that (through ineptness or stupidity) that used the same key. Otherwise, the Venona documents would be just encrypted junk. The downside of OTPs are that each end has to have the same OTP, the use has to stay synchronized and, if the OTP gets captured, every message created with it is potentially compromised if any already used portion of the OTP is captured. That is why, with OTPs, the most important rules were to never reuse any portion of the pad and to destroy all already used portions.

In this case, the sender would have destroyed the part of the OTP used on creation of the message. if the other copy (there were two copies sent) was received and a OTP was used, the receiver's part of that OTP would have been destroyed making ultimate decryption impossible. What is possible is marrying up the encrypted message with the other copy that was sent if it was received and decrypted. Marrying the two together would use information such as the header, preamble and postamble information which would be the time sent, the person sending it (Sjt Stott, in modern spelling Sgt Stott), the recipient, the pigeon serial numbers and the somewhat enigmatic AOAKN starting and ending blocks and 1525/6 found at the message end.

What a bunch of scrubs, that was easy

[Ambiguous Coward]

Was anyone working on this even trying? I cracked it without even reading the entire summary!

BE SURE TO DRINK YOUR OVALTINE

Cracked

[Anonymous Coward]

"Dwindling marmite supply... morale low... send the vegemite"

Sigma Functions..

[nanospook]

Echos of Cryptonomicon?

One time pads

[Anonymous Coward]

These sort of messages often were encrypted with one time pads. If you don't have the reference material and pad, decryption is almost impossible.

NURP

[jasnw]

Well, looks like those two "NURP" lines, in a different ink and a different hand, look like they might be pidgeon IDs. For example, see:

http://www.pdsa.org.uk/about-us/animal-bravery-awards/dickin-medal-pigeons

FSM knows what that might mean, but it could tie the message to other birds.

OTP Security

[AlbusTalpa]

One-time pad's are secure if the key is used only once (hence the name, one-time pad). The key needs to be as long as the original message, which makes this method unpractical in most real-life situations. If you use a smaller key than your plaintext, your encrypted message is compromised. If you re-use the key, then all your encrypted messages are compromised.

There's a very nice visual representation of this property here:

http://www.cryptosmith.com/archives/70

I like this example as it provides a visual representation of the leak. If you encrypt two different images with the same key using OTP and if you have access to both encrypted images, then you can XOR the encrypted images together to get information from the original images. It's surprising how much information is actually leaked when you re-use a key in OTP.

In the case of WWII pigeons, if anyone re-used an OTP key and an attacker captured two pigeons carrying messages encrypted with the same key, these messages would all be compromised.

Possible pad in plain sight?

[Anonymous Coward]

I wonder if they could have used something common that wouldn't arouse any suspicion for the purposes of pad-based encryption. Either a bible that was in print at that time or a common infantry soldier's basic training manual. The enemy likely wouldn't be none the wiser. The key would be knowing which page or passage for where the encryption starts, but it could be encoded using something fairly simple like a Vigenere cypher. Do something like selecting the page and paragraph based on the date, and perhaps mix those up based on which individual is using them and you'll have a pretty good and nearly impossible to crack system worked out.

It would be pretty darn impossible to break given WWII tech, but with a modern computer it would be possible to sort through books commonly found amongst soldiers of the era in place of the key and see if any recognizable phrases show up in the output. At least that seems like something plausible enough to try as a starting point.

Re: encoded with a one time pad

[neonsignal]

... and in this case, sent with a one time pigeon

Re:onetime pad vs code designed for a single missi

[Anonymous Coward]

;isn't a "on a now probably destroyed code book designed specifically for a single operation or mission." a onetime pad technically. if not, what is it?

No, because elements in an ops code book could be simple word substitution and any word reused - like substituting 'lettuce' for 'ammunition', 'lance' for 'artillery', 'John' for 'rifle', 'red' for 'send', beach' for 'don't' etc. You could use 'red John lettuce' for send rifle ammunition and '' as well as 'beach red lance'. for 'don't send artillery'. This of course opens up for statistical analysis as well as situational hints, but can be reinforced with multiple available substitutions for commonly used words, as well as limiting the time span any given code book was in use - so that IF the code was broken it would by that time already be obsolete, and any intercepted messages already overtaken by events.

and, the British did use one-time pads

[G3ckoG33k]

From the link you gave "A number of nations have used one-time pad systems for their sensitive traffic. Leo Marks reports that the British Special Operations Executive used one-time pads in World War II to encode traffic between its offices. One-time pads for use with its overseas agents were introduced late in the war.[11] Other one-time tape cipher machines include the British machines Rockex and Noreen."

Redundant, but one should also stress that it is also known that the British actually did use one-time pads.

Well they weren't tryiny to crack a code

[Lincolnshire Poacher]

Code: "The Eagle has landed"
Cipher: AKINSHXHHDUQOANSPQJCDHSG

The message was written in Greek!

[Crypto Gnome]

Graecum est, non legitur.

And THAT's why it cannot be read.

Re:There's an Idiocracy joke in here somewhere.

[mikael]

The parts of the message that begin with NURP is the identifier for the pigeon. There were two in the message:

NURP.40.TW.194 and NURP.37.OK.76

Other noted pigeons who contributed important messages:
http://www.thebirdman.org/Index/Others/Others-Doc-Birds&OtherAnimals/+Doc-Birds&OtherAnimals-Birds/RoleOfPigeonsInWartime.htm

Bruteforce with hints - Re:No surprise there

[rbenech]

Actually, Having a real message (i.e. pass spellcheck) is quite easy to detect. It's getting there that's the hard part. It can take some time (time we have). Finding the one time pad key (where the key is as long as the message) is to use enough known messages to force a collision. Known plain text comparisons (like known plain text of similar pigeon messages). The governments might already have the exact message decoded by other means. Generate one time pads for the entire known text and see if you get a hit. Use statistical methods to create agents to process certain targets of known plaintext pairs. Having a message header or sign off pattern would be a great place to start!

Not to say I told you so, but...

[Anonymous Coward]

I'll just bet the dumb Limey fuckers are regretting what they did to Turing now, aren't they!!! If he were still around, maybe they'd know what the message said. (It said, the U-Boat with the 10,000 tons of gold went down at xx.xxxx degrees West, yy.yyyy degrees North, not too far from Zzzzzzzzzzz.

Re:onetime pad vs code designed for a single missi

[Anonymous Coward]

"Charlie" probably wasn't formally recorded in a true codebook during the Vietnam war, yet it would have been a commonly understood code word for enemy troops among US soldiers.

Wrong. See https://en.wikipedia.org/wiki/Charlie for why. It wasn't code, any more than calling someone named James, "Jim".

Re:onetime pad vs code designed for a single missi

[Arker]

No, a one-time pad is a type of cipher, while a codebook is an element of a code. Quite different categories of encryption, very dissimilar.

In a one-time pad, the pad is used as a key for a cipher process, where each letter in the message is transformed into a different letter using a different cipher, based on the corresponding letter in the key. Since each succeeding letter is encrypted with a different simple cipher, this immunizes the message from statistical analysis which otherwise allows simple ciphers to be cracked rather easily.

With a codebook no ciphers are involved. A codebook is sort of like a DNA server but with a 1:1 ratio between numbers and domain names that is preserved going either way. Each element in the codebook is a word or phrase in plane, which is represented with a specific sequence of letters and/or numbers. Individual characters are generally not encoded, just words and/or phrases. Since it is not based on a mathematical transformation of the original message it isnt vulnerable to the same attacks as a cipher.

I have the decoded message

[rocjoe71]

"Send more pigeons"

...you're welcome.

What Kind of Pigeon?

[Anonymous Coward]

I think it should first be determined if it was an African pigeon or a European pigeon.

two (2) mesages were sent.

[eionmac]

1. GCHQ knows the pigeon that the mesage was on [ID number known and pigeon origin unknown]. Second identical message was sent by another pigeon (ID number known & shown om message , but pigeon not known (records held at Bletchly archives etc being checked now.)) (Personal message to me by interested parties at GCHQ)
2. 1 Assumption. Field operative/ recipiant got message and got on with things Pigeon no 2 this one lost. This is Case 1
2.2 . Assumption. Field operative/ recipiant did not get message and did not get on with things Both Pigeon no 2 and pigeon 1 also did not arrive. This is case 2.
3. if case1 the mesage is/was known to those who needed it in time (probally S/He dead by now). If case 2 no mesage was received and now does not matter for any war effort but only as an example in generating a lot of interest.
Also note point of operative /handler working languages. Key points in my own messages when active switched from English (common language) to Gaelic (handler was also a Gael) so three languages Force Jargon/English/Gaelic even in a tweet length message on one time pads.

well

[MakersDirector]

The technology to decrypt it may not have been invented yet in this reality..

Maybe they should have the chimpanzees look at it.

I CRACKED IT

[Anonymous Coward]

decoded and translated.... from Pigeon English... it reads...

Help, I am stuck in a chimney...

Re:lol

[RockDoctor]

Really, Mr. Ballmer, you need to take some chair management classes.

FTFY.