Does one time pad randomness help brute force attacks?

Question

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?

Answer 1

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:

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.