Does one time pad randomness help brute force attacks? 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?
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$ &mdash; and if it did not, it would not be perfectly random.