How exactly is "true randomness" defined in the realms of cryptography?

Question

Especially in relation to stream ciphers, I frequently read about (sometimes theoretical, sometimes practical) attacks that are able to "distinguish a ciphertext from a truly random stream".

What's logical to me is that - just because a ciphertext looks random, it isn't necessarily random. Looking around, the general consensus is that "ciphertext needs to be indistinguishable from a stream of truly random bits".

This got me thinking: what exactly is "true randomness"? According to (cryptographically related) definitions I found, "true randomness is unpredictable". So far, so good... but that's also marks the exact point where I've lost it.

"Unpredictable" would practically mean that we have nothing to compare the ciphertext with, because we can not predict what output "true randomness" might produce. Also, there is a (minimal) chance that "true randomness" might output the exact same series of bits as a ciphertext. Meaning: a ciphertext might read 63F1t49X43 and there's a (minimal) chance "true randomness" might produce exactly the same output 63F1t49X43. No one can tell, because "true randomness is unpredictable".

Not being able to predict any true randomness, how can we compare, distinguish, or even claim that a ciphertext is not truly random? Obviously not by comparing it with "true randomness" as that would be impossible due to "true randomness being unpredictable".

Now, I'm pretty sure cryptography is not philosophy and — as a result — I'm absolutely sure I'm missing something obvious in relation to the cryptographic meaning of "true randomness". I'm guessing the details are to be found in the cryptographic definition of "true randomness", which leads to my question:

How exactly is "true randomness" defined in the realms of cryptography?

Practically, I guess you could say that I'm not really sure I correctly understand how someone can provide (cryptographically sound) proof to the claim that a series of bits is truly random when "true randomness" is considered to be unpredictable. So, if you think it's not the definition that might be confusing me here, please feel invited to set my head straight by pointing me to whatever I might be interpreting incorrectly.

EDIT

To avoid misunderstandings: when talking about "true randomness", I'm thinking along the lines of "True Random Number Generators" and not "Pseudo Random Number Generators". That's why I'm asking about "true randomness" and not pseudo-randomness.

Answer 1

Randomness is not a property of strings of bits (or characters of any sort). Rather it is a property of the process that generates those strings. However, it is convenient to conflate the string with the thing that produced the string, and thus to speak about strings being “random” or “not random”.

The string 00000, for example, is random if it was the outcome of “random process”, such as a coin being tossed five times and landing on tails five times in a row. Similarly, the string 1,2,3,4,5,6 is random if it was the outcome from rolling a die six times. Note, the random process does not need to be “fair” to be random, though processes that deviate substantially from the uniform distribution are not as useful for cryptographic purposes.

What is a “random process”? As I think about it, a random process is either an indeterministic process (if any actually exist), or a deterministic process for which the entropy of what we don't know (that is germane to the outcome) is greater than the entropy of the generated string. There is a lot we don't know (and can never know, given the Uncertainty Principle) about the state of the flipped coin – e.g. the exact position and momentum of every particle in the coin, the air around it, and the hand that flips it (all of which are germane, in that we presumably would need to know them to accurately predict the outcome of the flip).

If the string 00000 was the outcome of a number-generating algorithm, where the entropy of what was unknown and germane about the algorithm was less than 5 bits (e.g. we knew the algorithm and all but four bits of information about the seed), then the string would be “not-random”. At best it could be “pseudorandom”, meaning computationally difficult to distinguish from random.

Answer 2

Randomness is the information loss of any causal relationship between events.

The universe needn't be a clockwork universe for the assumption of pervasive causality - if events are "sticky" and accrue localised causality in the same way that a molecular cloud accretes into stars and planets. The underlying cause of the speed of light might also be the prime inducer of localised causality, but I digress.

Sources we attribute as random a priori are simply streams of related events with all the information regarding their causal relationships deleted.

This is a subtle point and deserves expanding: When we see patterns in a long* stream of data we are seeing causal information that has been preserved. The most persistent source of causality is temporal causality. As the order we receive events is due to the propagation speed (max of c) from and between events - hence localised non-temporal causality is often strongly preserved in temporal propagation as the shortest path to the observer involves little if any extraneous interference.

The way that we can deliberately (or nature can incidentally) remove temporal causality is force an observer to collapse multiple frames of reference into a single frame of reference; losing information in the process. For example, with Brownian Motion, if the history of every particle is tracked then causality is preserved and all future behaviour can be predicted. If the observer can only observe one particle, causality is not preserved and influence on that particle by other particles is essentially random.

PRNG avalanches work in much the same way; so the difference between a TRNG and PRNG is simply that PRNGs have a tiny amount of unknown information (e.g. 1024 bits) while TRNG natural phenomena have enormous amounts of unknown information (e.g. a state size of 10^24 bits for a cup of hot coffee).

We can't store, transmit or meaningfully brute force the massive state size of natural phenomena so TRNGs are considered completely random; providing you choose a natural phenomena that collapses multiple frames (e.g. "Each molecule in the Sun") into a single frame of reference (e.g. "Current rate of solar wind").

A distinction also has to be made between Randomness and Uniqueness. A random collection of data has no obligation to be unique in totality or any part thereof. Dilbert demonstrates.

This is why you need a trust chain for any random number generator you haven't analysed or don't control. I can give you a page of data that looks random to you because it passes every test for uniqueness, repetition and distribution but isn't random to me since I used a PRNG and kept the seed.

_{* Short steams of data can very easily have patterns due to ascribing causality where none reliably exists.}

---

The same answer without explanation:

• A TRNG is a stochastic process with an extremely large unknown internal state.
• A PRNG is a stochastic process with an extremely small unknown internal state.
• TRNGs are created by picking a proven stochastic process which is easy to observe the output of.
• TRNGs measure natural phenomena as they already contain extremely large unknowns; or superposition so much state information as to qualify as "extremely large unknowns".

Answer 3

To be concise, true randomness boils down to the selected data being causally unrelated. That is, if each piece of data is the result of no common cause, then there is no relation by which the rest of the data can be predicted or inferred. So being unpredictable is a consequence of being truly random, but it is the lack of causal relationship that is the determining factor.

Answer 4

In the context of the original question, what you're comparing your stream cipher to is a particular probability model. That model has each bit have probability 0.5 of being a 1, and has that probability be independent of the bit's position in the string and any surrounding bits. It's the kind of source you would get if you flipped a fair coin to determine each bit in the sequence.

The reason this matters for a stream cipher: Imagine drawing a keystream from the ideal random source and XOR-ing it into the plaintext to encrypt it. This would never leak any information about the plaintext and would be unbreakable — it's a one time pad.

Now, suppose instead we draw our keystream from a stream cipher, and suppose there is no way to distinguish this stream cipher's outputs from an ideal random sequence up to some limit in computation and observed keystream.

Now, let's imagine an attack algorithm that uses less than those limits of keystream and computation to break the stream cipher and recover some information about the plaintext. If I had such an attack algorithm, I could always use it to build an algorithm that would distinguish my stream cipher outputs from an ideal random sequence. I would just take the stream cipher output, use it to encrypt some plaintext, and then try my attack against it.

That means that we know that if there is no way to distinguish the stream cipher outputs from an ideal random sequence, then there is no attack that recovery information about the plaintext from the data encrypted by the stream cipher.

Answer 5

I think there are two issues involved here:

1. How do you tell if a ciphertext has the properties of a truly random stream?
2. How do you tell if a stream actually is truly random?

For the first part, there are many statistical techniques. But the basic question is whether there is any detectable relationship between the plaintext and the ciphertext. If modifying any bit of the plaintext has a 50% chance of changing any bit of the ciphertext, that's one good sign.

For the second part, I believe it's impossible to tell the difference between a truly random stream and a sufficiently good pseudo-random stream without knowing the implementation details or seeing repetition. No deterministic algorithm can generate true randomness.

Answer 6

Randomness in the realm of Cryptology is defined by the cipher you cannot solve. The process that converts the order of the plaintext to the order of the ciphertext is unknown to you. As far as you are concerned the ciphertext has been put together without an identifiable pattern, plan, system, or connection. It is disordered. To you it is random.

If I can solve the cipher but you cannot, then either I have been lucky or else I can see patterns that you fail to see, which help me solve the cipher. In the latter case, for me the ciphertext is not random. I have an intuition that you do not possess and my observation of the cipher (and probably many other, unrelated things in this world) are different to yours.