5
$\begingroup$

I understand that attempting to brute force the decryption of a message coded with a one time pad results in generating every possible message. The Wikipedia example is that decoding "EQNVZ" with key "XMCKL" produces "HELLO", but the key "TQURI" produces equally plausible "LATER".

However, a "more random" one time pad is supposedly better than a "less random" one time pad. So there's a way to compare the randomness of two pads, right?

If key TQURI is "measured" as less random than XMCKL, doesn't the likelihood the pad is as random as possible mean HELLO is the more likely message?

Say a coded message consists of only plain English. A 50-character message could decode to a huge number of possible messages using the same huge number of possible keys. As we decode character-by-character we can discard anything that isn't obvious English. That would still leave a large number of possible messages (I have no idea how to estimate how many), but we would simultaneously be increasing the length of the supposedly random key.

If one possible decoding begins ATTACK AT DAWN using the key GJXWHELZYHWLXE while another decoding begins SEND MONEY NOW using the key AABBCCDDEEFFGG, we can probably discard the latter since a pad would never use such a repetitive key.

Therefore, the rule would be to only retain the English decodings for the "most random" keys. (I have no idea how to pick such a cutoff.) Could that possibly reduce the potential messages to a reasonable number of candidates? (I imagine longer keys let you determine their degree of randomness with greater confidence, but I don't know how to calculate that kind of stuff.)

Another possibility would be to retain only messages that parse reasonably well. BATTALION ALPHA ATTACKS AT DAWN makes sense, but SUNSET DOGGY COOKIE FLOOR can probably be discarded.

Even if individual messages generate a large number of decoded candidates with sufficiently random keys, it would seem a sequence of messages would establish a context that hints at which decodings are valid. For example, if Message 1 "equally" (because of key randomness) decodes to the candidates

A. WHEN DO WE ATTACK
B. SHOES GREENER ARE
C. MASHED ROOF CARRY

and Message 2 in reply "equally" decodes to

A. ATTACK AT DAWN
B. LEAVE PARLANCE
C. DOG ALPHA MODE

then it seems the "conversation" is probably WHEN DO WE ATTACK/ATTACK AT DAWN. (Granted, the reply would also decode to ATTACK AT 0100, ATTACK AT 0200, ATTACK AT DUSK, etc., but we're picking the solutions with the "most random" keys. And even if the keys for ATTACK AT 0100 and ATTACK AT DUSK tied at an equal level of randomness, it's still useful to know an attack is imminent.) It would seem the more messages you have, the easier it is to guess (or apply some AI regarding) the general thread being discussed.

Therefore, a modified brute force approach would prune away possible but unlikely decodings by (1) discarding invalid and nonsensical content within messages, (2) abandoning decodings with keys not meeting a required threshold of randomness, and (3) abandoning decodings that don't fit intermessage context. Pruning would have to be done as each new message character is input, to avoid wasting time and space on futile branches.

Would that kind of approach still leave an astronomical number of possible decodings? Or could it reduce the candidates to a resonably small enough number that NSA computers might possibly be willing to take a stab at predicting (at some level of confidence) what a set of coded messages is probably talking about?

Wikipedia's entry on brute force says a one time pad attack

...would eventually reveal every... character string possible, including the correct answer – but of all the answers given, there would be no way of knowing which was the correct one.

But it seems like some answers could be computed as more likely than others. Can the set of possible answers be reduced to a reasonable number, especially when the randomness of the required key is taken into account?

$\endgroup$
  • $\begingroup$ "However, a "more random" one time pad is supposedly better than a "less random" one time pad. So there's a way to compare the randomness of two pads, right?" There is no more random if the length is fixed. In OTP, every single bit (or letter, if you use an alphabet) is independent of each other and drawn from a uniform distribution. So no, there is no way to compare randomness. $\endgroup$ – tylo Jan 18 '17 at 11:47
  • $\begingroup$ No way to compare randomness? Per the example, the key GJXWHELZYHWLXE sure looks more random than the key AABBCCDDEEFFGG, so I would never expect the OTP to contain the latter and therefore it wouldn't have to be considered as a solution. $\endgroup$ – joe snyder Jan 18 '17 at 19:14
  • 1
    $\begingroup$ "looks more random" is no valid criteria. If you have a truly random pad (uniform distributed, letters statistically independent) - and that is a hard requirement for OTP - then both strings have the very same probability. If you disregard any single one of those possibilities, you don't have an OTP any more. $\endgroup$ – tylo Jan 19 '17 at 9:34
  • $\begingroup$ That's OK. I'm disregarding unlikely keys, even though they have a remote possibility of being the answer, in exchange for reduced brute force searches. See example calculations in the self-answer. $\endgroup$ – joe snyder Jan 19 '17 at 16:23
  • 1
    $\begingroup$ No, that's not okay. You ignore the very basic assumption of OTP, which means it's not OTP any more. And then you find an attack on your not-OTP - based on those flaws you put in there deliberately. $\endgroup$ – tylo Jan 20 '17 at 8:55
-2
$\begingroup$

The confusion is probably coming from using the term "randomness" instead of "the probability a key uses N different characters". The more characters the set of possible keys uses, the more characters a randomly selected key will tend to have. In other words, after randomly choosing a key of 14 characters from A to Z, the key will probably use about 11 different characters. It's going to be rare that you end up with only 1 or 2 different characters in the key.

Here's a run of 10 million random 14-character keys using A to Z:

chars per key

Over 3 million keys used 11 characters, while only 56 keys used only 5 characters. There were no keys using 4 or fewer characters. Over 130,000 keys had no repeating characters and used all 14. Trying only keys with 10 to 12 different characters still gives you over 78% of the keys.

Therefore, yes, skipping the most unlikely keys will reduce your search time and probably not skip the correct answer. You'll still need to do a lot of computing for the remaining cases.

$\endgroup$
  • $\begingroup$ This is neither answering the question nor adressing the gravely wrong belief of the OP about OTP. $\endgroup$ – tylo Jun 13 '17 at 14:38
  • $\begingroup$ I think this answer (and maybe the question) is mixing up a dictionary attack with a brute force attack. The plain text may be random data instead of some words, and the key by definition of a OTP is uniformly distributed random data from a TRNG. $\endgroup$ – daniel Jun 21 '17 at 12:57
  • $\begingroup$ Skipping the most unlikely keys will reduce your search time the same amount as any other key. You can save 1/26 of your search time by skipping all keys starting with "P" for example... unless the correct key starts with "P". $\endgroup$ – immibis Jan 14 at 2:13
16
$\begingroup$

There is no such thing as a random key. There are only randomly generated keys.

What I mean by that is that randomness is not a property of the key (or message, or number, or whatever), but of the process that generates it. For example, it is not meaningful to ask whether the number 5 is random, or whether it is somehow more or less random than the number 4. However, if I pick up a die and roll it, and it lands with the "5" face up, then I can meaningfully say that I have just randomly selected the number 5 (and we can also meaningfully discuss just how random or not the way I rolled the die may have been).

In English we often do use "random" as an adjective to describe a thing (as opposed to an action), when we really should be saying "randomly chosen" or something similar. But this needs to be understood as just a linguistic shorthand. "A random number" really means "a randomly chosen number", and that's all there is, or can be, to it.

Why am I stressing this point so much? It's because when you ask something like:

If key TQURI is "measured" as less random than XMCKL, ...

you're revealing a fundamental confusion about what "a random key" really means. As I wrote above, randomness is not a property of the key string itself, so there's no way to assert that, say, the string "TQURI" is somehow more or less random than "XMCKL" or, for that matter, "ABCDE". Even trying to make the comparison is meaningless.

All that we can meaningfully ask is how likely it is that each of those key strings would appear if we, say, randomly picked five letters from a bag containing each letter of the alphabet and wrote them down (returning each picked letter to the bag before picking the next one). And the answer to that question is that each of those strings (yes, even "ABCDE") is equally likely to be the result of that process.

Thus, if our one-time pad was generated using the method I described (or by any other equally random means), then none of those proposed keys is any more likely to be the correct one than any other, and so examining them yields no information about the message.


Ps. Yes, this also means that randomness testing is, strictly speaking, a fool's endeavor: a truly random process is equally likely to output any string of a given length, so no such string can be said to be any more or less random than any other in that sense.

The best we can do is to look for distinctive features that may appear disproportionately more often in the results of certain kinds of non-random (or incompletely random) processes, and declare the observation of such features as evidence that the process that generated the output may not be perfectly random. In that sense, it would be more appropriate to call any such tests "non-randomness testing".

Even then, in doing so, we must necessarily accept the possibility of "false positives", i.e. the possibility that even a perfectly random process can, and will, occasionally generate outputs that look like the output of some non-random process. A perfectly random 5-letter string generator must, necessarily, generate the string "AAAAA" with probability $1/26^5 \approx 0.00000008$ — and if it did not, it would not be perfectly random.

$\endgroup$
  • $\begingroup$ I don't want to test a key for randomness, I want to determine which of two keys (pads) is more likely to be random. If one candidate key is GJXWHELZYHWLXE and the other is AAAAAAAAAAAAAA then I would prune the latter. I understand that all A's would inevitably be generated while considering all keys, I just don't expect a one time pad to actually be all A's as frequently as some other sequence. $\endgroup$ – joe snyder Jan 18 '17 at 19:21
  • 2
    $\begingroup$ ...and that would be where your intuition is going wrong. If the key letters are chosen independently and uniformly at random (and they'd better be, for a proper one-time pad), then both GJXWHELZYHWLXE and AAAAAAAAAAAAAA will appear with the same probability, $1/26^{14}$. $\endgroup$ – Ilmari Karonen Jan 19 '17 at 2:07
  • $\begingroup$ Doesn't matter. Look at it this way: if I pick a 14-character key out of a OTP, what is the probability it has all the same characters vs. the probability it doesn't? All-repeating chars is less likely, so I'll ignore that possibility. See the proposed procedure in the self-answer. $\endgroup$ – joe snyder Jan 19 '17 at 4:01
  • 1
    $\begingroup$ @joesnyder The very same probability. Each and every single possible pad has the same probability - otherwise it is not OTP. So no, your intuition is absolutely wrong. $\endgroup$ – tylo Jan 19 '17 at 9:39
  • 3
    $\begingroup$ @joesnyder: A pad of 1000 random characters is also extremely unlikely to contain the string GJXWHELZYHWLXE. In fact, if the pad is indeed randomly generated, it is exactly as unlikely to have the string GJXWHELZYHWLXE at any given position than it is to have AAAAAAAAAAAAAA at that position. $\endgroup$ – Ilmari Karonen Jan 20 '17 at 3:26
7
$\begingroup$

The point is you don't have an OTP unless all characters in the pad are uniformly distributed and independent. So, at a theoretical level, your question is meaningless.

More practically, you seem to be attempting to infer context from different segments of trial decryptions, but these trial phrases have nothing to do with the pad so in essence you are using side information from, say in a military context, external tactical information sources.

The main point is whatever nonsensical phrases you prune away, all meaningful English phrases remain equally likely and your use of external information is independent of the OTP. Surely the fact that a trial decryption is meaningful English has nothing to do with the probability distribution of the difference (subtraction mod 26) between that phrase and the ciphertext segment,i.e., the probability distribution of the OTP segment used to encrypt that purported plaintext. This difference is not a segment of English.

$\endgroup$
  • $\begingroup$ "...you don't have an OTP unless all characters in the pad are uniformly distributed". Exactly! So if one solution tells me the pad had to be GJXWHELZYHWLXE and another solution says the pad had to be AAAAAAAAAAAAAA I'll pick the former and prune the latter. $\endgroup$ – joe snyder Jan 18 '17 at 19:25
  • $\begingroup$ "...all meaningful English phrases remain equally likely" I think is true when examining only the phrases. But a given phrase + the "randomness" of the OTP necessary to generate that phrase + whether the phrase fits the context of the previous and next phrase I'm thinking makes some phrases more likely than others. Does it reduce the number of phrases in a significant way? Perhaps a contest to see who can guess what five 140-character coded phrases probably meant would be an interesting challenge. $\endgroup$ – joe snyder Jan 18 '17 at 19:30
4
$\begingroup$

There are a few wrong assumptions in your question:

  1. a random number generator that is not cryptographically secure can easily be distinguished from a secure random number generator;
  2. brute forcing is possible for any sufficiently large ciphertext;

To show point 1, let's take a look at the Mersenne Twister PRNG. This is a fine random number generator that is, however easy to reverse, mathematically speaking. The randoms will simply pass any (generic) randomness test you throw at it. This means that you cannot simply disregard any key streams, which in turn means you cannot simply disregard resulting plaintext. You would need to crypt-analyze the random number generator for any meaningful result.

You also mention brute forcing the ciphertext to retrieve the plaintext. This is not feasible for any ciphertext containing 128 secure, pseudo-random bit values (in total), even if you can distinguish the result. Without some knowledge of the bits in the key stream you would still not know what to compare against to validate your guess.


As you can see, directly attacking the one-time-pad scheme won't easily return any result.

What you can do is to crypt-analyze the random number generator. Using this you could indeed generate candidate key streams and therefore candidate plaintext to validate your informed guesses.

$\endgroup$
  • $\begingroup$ I think my assumption was that a pad that isn't random could be distinguished from a random pad, so solutions using keys from the nonrandom pad could be discarded. I'm also not assuming brute forcing alone is possible, but hoping that the number of potential solutions might be significantly reduced by discarding those generated with the "less random" keys plus poor English plus not fitting a context. In other words, using multiple simultaneous tests against each candidate allows pruning the less-likely candidates. $\endgroup$ – joe snyder Jan 18 '17 at 19:40
  • $\begingroup$ The problem is that a pad can be non-random without directly leaking bits or octets. Now if that was the case I can see how you can disregard certain combinations. But usually that idea makes no sense - the randomness doesn't directly leak bits, it leaks mathematical relations between bits / bytes of the key. You'd first have to find those to start disregarding specific values. $\endgroup$ – Maarten Bodewes Jan 20 '17 at 9:25
  • $\begingroup$ I don't care if the pad used was random or not. I'll assume it was random, and therefore keys like AAAAAAAAAAAAAA are unlikely to occur, so I won't consider such keys during the brute force search. $\endgroup$ – joe snyder Jan 20 '17 at 17:59
  • $\begingroup$ Your point #1 becomes moot if (as is common with OTPs) the generator is a true random number generator. Whilst Joe wasn't specific in his question, that must be the inference otherwise why bother with a OTP? $\endgroup$ – Paul Uszak Jan 22 '17 at 14:15
  • $\begingroup$ @PaulUszak For a true one-time-pad, sure. But with the question already posing "However, a "more random" one time pad is supposedly better than a "less random" one time pad. So there's a way to compare the randomness of two pads, right?" that's already out of the window. So I think it is safe to assume we aren't talking about the fully secure theoretical construction here. $\endgroup$ – Maarten Bodewes Jan 22 '17 at 14:36
1
$\begingroup$

One thing you're missing that no one else mentioned is the difference between the primitive (one-time pad) and the method of use (eg mode of operation and protocol).

In the naive "textbook" OTP the pad is exactly the same length as the message, and thus reveals the length of the plaintext. It also does nothing to prevent the attacker from gathering metadata (who the sender and receiver are, patterns in when messages get sent, etc.) These weaknesses allow the search space to be narrowed a bit, quite a lot as messages get shorter and shorter.

Real One-Time Pads were originally just that: pads of paper, where each page had a key and could be torn off and destroyed after use. To prevent leaking the length of the messages was easy: Encrypt the message normally, then append the unused part of the page to the end (XOR with a fixed padding null character). Discard the page as normal. This means that every message sent is a full page of text. That's around 1500 characters, which makes pruning of candidate keys utterly useless.

With a computerized version you do essentially the same thing, and pad all messages to a multiple of a fixed block length.

$\endgroup$
  • $\begingroup$ Let's face it, a OTP, whether analog or digital, is obsolete because generation, distribution, synchronization, + security isn't practical or competitive nowadays, so this discussion is probably only academic (although government archives of old uncracked messages might still get attention). My main point is that most OTP descriptions imply it's invulnerable to brute force techniques, and I think that's not 100% true, per the calculations discussed. And padding doesn't matter, I'll just work on the first N chars, where N is whatever amount my supercomputers can handle in reasonable time. $\endgroup$ – joe snyder Jan 20 '17 at 18:22
  • $\begingroup$ Just where do you get the 1500 character size from? Have a look at a miniaturised OTP and you'll see they might only be a few tens of characters. I don't think that SOE agents routinely sent huge messages. $\endgroup$ – Paul Uszak Jan 22 '17 at 14:25
-1
$\begingroup$

I think that yes, pruning candidate keys based on randomness (actually, their likelihood of appearing on a one time pad) will significantly reduce bruce force effort. You'll miss some correct answers, but you can make that probability small. Whether the results are still practical and informative, I'm not sure.

For example, say a 14-character message like ATTACK AT DAWN has been coded from a one time pad of A-Z characters. That means there are 26^14 possible keys. For simplicity let's say a key with any repeated character is less random than a key with no repeats. Now you only have to consider P(26,14) different keys, which is still a big number (841,941,782,922,240,000), but looking more attackable.

The "first" key with no repeats would be ABCDEFGHIJKLMN. A pad containing such a key could theoretically be random, but it would be highly suspect. Similarly, how often would a 14-character run contain 2 repeats of the same character? 3 repeats? 10 repeats? It would seem we can decide whatever criteria and cutoff we'd like to use to avoid unlikely keys, knowing we'd lose some answers, but with whatever confidence level we desire for our pruning. For example, "we're rejecting key K because there is a 99% probability it does not appear on any one time pad".

For now let's stick with the "no repeats" cutoff that reduced our keys from 26^14 to P(26,14). If we can process a million keys per second, a single CPU would need almost 27,000 years, but processing in parallel perhaps makes it doable by NSA supercomputers (or a big enough botnet).

The next question is how many of the P(26,14) candidate messages are English? Say in our dictionary all words beginning with Q are followed by U. So if the current candidate key decodes the message as QX... we can skip considering the remaining 9,657,700 keys for that message.

90% of the time English speakers use just 7,500 words, so let's use that as our dictionary.

Average English word length is 5.1 characters, so let's say our 14-character message will on average contain 3 words. That means there are around 7,500^3 possible phrases in the message which we'll detect with our dictionary lookups, so now we've reduced the 841,941,782,922,240,000 candidate messages to 421,875,000,000.

How many of the 421,875,000,000 messages parse sensibly? Since there are probably so few words in the message, let's estimate that any word is possible to start, half the words make sense for the second word, and half again for the last, or 7,500 * 3,750 * 1,875 = 52,734,375,000 phrases. An actual parser might find far fewer candidates in many cases.

53 billion phrases is a lot, but a sequence of coded messages would often be concerned with a single topic, and the longer the sequence the more detectable the topic should be. Let's assume any noun found in a message is the topic. If after 10 14-character messages the most frequently occuring nouns among the 10 * 53 billion candidates are PASTRY, HOUSE, and TRUMP, the best candidate can probably be chosen by knowing who the messaging parties are. For example, for Starbucks PASTRY is probably the topic while for Putin TRUMP is probably the topic. Although any given noun could always be computed as appearing in any message, hopefully the keys necessary to do that are rejected often enough because they don't meet our criteria for randomness.

Bottom line: it would seem that pruning candidate keys based on their likelihood of appearing on a one time pad, along with the other heuristics above, would significantly reduce the effort to find potential messages above a selected confidence level, but it probably doesn't make a big enough dent to help much, and the resulting final collection of candidate messages is probably usually so large that even determining just the topic of an exchange of messages would be too difficult or expensive.

$\endgroup$
  • 2
    $\begingroup$ This is all based on the misconception, that one pad is more likely than another. And that is just false. Also, repetitions are to be expected. If you say "they are not likely", you cut off valid strings. And for a string with $x$ letters, each and every single string has the same probability $1/26^x$. This entire answer is wrong from the get go. $\endgroup$ – tylo Jan 20 '17 at 9:01
  • $\begingroup$ No, it's based on some keys being more likely to appear on a pad than others. "Try all keys" is brute force. For fewer answers, "Try all keys, ignore if not English". For even fewer, "Try all keys, ignore if can't parse". For even fewer answers and attempts, "Try all keys, skip AAAAAAAAA, ignore if can't parse". For even fewer, "Try all keys, skip any with 9 or more repeats of a char, ignore if can't parse". For the least work of all, "Try all keys, skip any key unlikely to be on the pad, ignore if can't parse", where "unlikely" is any probability you wish to choose. $\endgroup$ – joe snyder Jan 20 '17 at 18:33
  • $\begingroup$ Yes, every key is potentially valid, but I'm willing to roll the dice to save time. If I don't consider the 96 keys with 1 char repeated 7 times that turned up on my 10 million pads, I might miss a valid message, but they probably weren't valid English that parsed anyway. I'll gamble that the correct keys were somewhere in the other 9,999,904. I'm not looking for perfection, I'm looking for likely answers with less effort. $\endgroup$ – joe snyder Jan 20 '17 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.