5
$\begingroup$

I came across the following statement regarding true random number generators (TRNG):

A “P1 medium” [AIS31] true random number generator (TRNG) may not be directly used due to cryptographic reasons. Even smart cards or other advanced security solutions which possess high-quality physical sources of randomness usually rely at least on a compression of the TRNG output.

My question is, what is it about the compression of the TRNG output that makes it insecure? I have tried searching, but I cant find anything more information regarding this point wither in the spec the above quote came from, or anywhere I have looked online.

The only thing I can think of is that somehow the result of the compression algorithm can be predicted based on the input. However, if the input was generated randomly, I don't understand how that could matter.

$\endgroup$
  • 17
    $\begingroup$ "what is it about the compression of the TRNG output that makes it insecure?"; I don't understand how you got that from the quote, which states "even things with a high quality entropy source DO use compression" (although I have more usually heard that referenced to as 'conditioning') $\endgroup$ – poncho Sep 4 at 17:30
  • 1
    $\begingroup$ The word compression in this context is referring to this. See the answer by Serpent27. $\endgroup$ – President James K. Polk Sep 5 at 14:00
  • $\begingroup$ Note that this is precisely what "Randomness Extraction" studies. Salil Vadhan has some writing which motivates it here. $\endgroup$ – Mark Sep 6 at 0:08
34
$\begingroup$

I think you're misinterpreting the source. The source says the TRNGs "rely" on compression (a cryptographic hash would be the compression function, or possibly some simpler function to increase throughput).

The random data isn't insecure after compression, it's insecure before compression.

Why?

When you roll dice there's an equal probability of it being any one of the possible values, but let's say the dice aren't quite perfect - in nature you'll find things are almost always more like weighted dice than perfect RNGs.

If the output is biased it means it's less likely to produce certain outputs, breaking the security of an RNG - for a CSPRNG to be secure it must produce every output with equal probability, and a TRNG isn't exempt from that rule.

The solution is to take more random bytes than you plan to use, then use a compression function to merge them. It could be as simple as XORing every pair of bytes, or as thought-out as a cryptographic hash, but you need something to even out the probabilities.

That said, using a compression function like what's used to shrink your ZIP files would be an easy way to mess with the probabilities in a way you don't want, so that should be avoided, but that's not what they were referring to.

| improve this answer | |
$\endgroup$
  • 11
    $\begingroup$ The implication is that "as random as realistically achievable" isn't actually all that good. $\endgroup$ – Harry Johnston Sep 5 at 2:58
  • 8
    $\begingroup$ @Jordan To me, the phrase "advanced security solutions [...] rely at least on a compression of the TRNG output" seems to imply, pretty clearly, that "a compression of the TRNG output" is considered secure, as opposed to "high-quality physical sources of randomness," which may have a lot of "quality" but still be insecure. I don't know how you look at the phrase "advanced security solutions [...] rely at least on a compression of the TRNG output" and conclude from it that a compression is less secure. $\endgroup$ – Tanner Swett Sep 5 at 4:50
  • 12
    $\begingroup$ @Jordan, consider a randomness source that's a biased coin, with uneven odds for landing on its two sides for each flip but without correlation between flips. That's obviously imperfect as a source for random bits, but can be trivially unbiased by looking for heads-tails and tails-heads pairs. Looking for pairs is the "compression" here (it reduces the number of bits). For other kinds of bias, you'd need better compression/whitening, of course. $\endgroup$ – ilkkachu Sep 5 at 16:28
  • 1
    $\begingroup$ A cryptographic hash needs to be collision-resistant, while a TRNG's compression function has no such requirement. The term "hash" would be more intuitive to understand but the term "compression" is more accurate, at least by the cryptographic definition of compression. $\endgroup$ – Serpent27 Sep 7 at 0:13
  • 3
    $\begingroup$ A simple way to think about it is this: N bits of perfect random data contains N bits of entropy. N bits of imperfectly random data contains fewer than N bits of entropy. So you need to compress it to fewer than N bits of output if you want its output to be closer to perfect. $\endgroup$ – David Schwartz Sep 7 at 8:51
2
$\begingroup$

tl;dr It's not actually a true-random generator so much as a physically-sourced-random generator. The underlying physical processes can have patterns that compression helps to strip away, improving the quality of the generator.


In context, "true" randomness is referring to randomness sourced from physical phenomena in contrast to pseudo-randomness sourced from deterministic algorithms.

My suggestion would be to not take the terminology overly literally: it's not really "true" randomness (or else it shouldn't be viably compressible in the first place) so much as physically-sourced randomness.

The compression actually helps improve the generated randomness. Fundamentally, compression works by identifying patterns and redescribing them more concisely, so, by compressing something, you strip away predicable correlations. In principle, any theoretically optimal compression algorithm would ensure (actually) true randomness – being a major reason for compressing data before encrypting it.


Three reasons for compressing the raw data stream.

There're 3 big reasons to compress the data stream:

  1. There's more raw data than entropy.

  2. It's difficult to properly bin entropy into independent outcomes.

  3. Entropy's subjective, and an attacker might model it better.


Reason 1: More raw data than entropy.

Say you're generating random data using coin flips.

If it's a fair coin, then each flip has an entropy of $$ \begin{alignat}{7} H ~=~ & - \sum_{\forall \text{outcomes}~i}{\left(P\left(x_i\right) \log_{2}{\left(P\left(x_i\right)\right)}\right)} \\ ~=~ & - \left( \frac{1}{2} \log_{2}{\left(\frac{1}{2}\right)} + \frac{1}{2} \log_{2}{\left(\frac{1}{2}\right)} \right) \\ ~=~ & 1 \, \mathrm{bit} \,, \end{alignat} $$ meaning that there's $1 \, \mathrm{bit}$ of entropy.

However, biased coins generate less entropy per flip. Using the same equation as above for coins with a bias towards landing Heads-up: $$ {\def\Entry#1#2{ #1 \% & #2 \\[-25px] \hline }} { \begin{array}{|c|c|} \hline \begin{array}{c}\textbf{Odds of} \\[-25px] \textbf{Heads}\end{array} & \begin{array}{c} \textbf{Entropy} \\[-25px] \left(\frac{\mathrm{bit}}{\mathrm{flip}}\right) \end{array} \\ \hline \Entry{50}{1\phantom{.000}} \Entry{55}{0.993} \Entry{60}{0.971} \Entry{65}{0.934} \Entry{70}{0.881} \Entry{75}{0.811} \Entry{80}{0.722} \Entry{85}{0.610} \Entry{90}{0.469} \Entry{95}{0.286} \Entry{100}{0\phantom{.000}} \end{array} }_{\Large{.}} $$

So unless you have an ideal fair coin, you'll have less entropy than flips.


Reason 2: Difficult to properly sort entropy into independent bins.

Say we want 2 bits of entropy, so we flip a coin with a known bias: it'll land on Heads $50.001 \%$ of the time, for about $0.9999999997 \frac{\mathrm{bit}}{\mathrm{flip}} ,$ or about $3 \times {10}^{-10} \frac{\mathrm{bit}}{\mathrm{flip}}$ from perfect.

Flipping the coin three times would give us almost $3 \, \mathrm{bits}$ of entropy – more than the $2 \, \mathrm{bits}$ that we wanted. But, unfortunately, 3 flips wouldn't be enough.

The problem's that we can't bin it. There'd be 8 possible outcomes of 3 coin flips, $$ { \begin{array}{ccc|c} \text{H} & \text{H} & \text{H} & h^3 t^0 \\[-25px] \text{H} & \text{H} & \text{T} & h^2 t^1 \\[-25px] \text{H} & \text{T} & \text{H} & h^2 t^1 \\[-25px] \text{H} & \text{T} & \text{T} & h^1 t^2 \\[-25px] \text{T} & \text{H} & \text{H} & h^2 t^1 \\[-25px] \text{T} & \text{H} & \text{T} & h^1 t^2 \\[-25px] \text{T} & \text{T} & \text{H} & h^1 t^2 \\[-25px] \text{T} & \text{T} & \text{T} & h^0 t^3 \end{array} }_{\Large{,}} $$ giving us 8 different outcomes:

  • 1 $h^3 ;$

  • 3 $h^2 t ;$

  • 3 $h t^2 ;$

  • 1 $t^3 .$

To get 2 bits of entropy, we'd want to sort all possible outcomes into $2^2=4$ bins of equal probability, where each bin represents one possible random-result stream: $\left\{0,0\right\},$ $\left\{0,1\right\},$ $\left\{1,0\right\},$ or $\left\{1,1\right\}.$ Then once we're done flipping, we select the bin that contained the observed outcome, yielding the corresponding random-result stream.


Reason 3: Entropy's subjective.

In real life, we don't have fair coins or even coins with known, uniform biases.

For example, say you're going to generate random-data with a coin. How would you even do that? Probably best to start out by flipping it a ton of times to try to guess its bias, right? And then start using the coin to produce random-data, assuming the experimental bias?

What if an attacker knows more about modeling coin-flips than you do? For example, what if coins tend to wear unevenly, or people/machines who flip coins shift their behaviors over time, in a way that an attacker knows about but you don't? Or what if the attacker just watches you flip long enough to get more data than you got before starting to use the coin?

Such an attacker would predict different likelihoods of coin-flip outcomes. They'd calculate different entropies, and presumably find any fine-tuned binning strategy you'd construct to be imperfect. Perhaps they'd find a way to exploit that imperfection to crack whatever secret you were trying to hide under a random-oracle assumption.

In short, this is the third problem: that while we can do the math to fine-tune our processes if we assume that we know the underlying physics perfectly, that's not how the real world works; attackers can treat your own random-data generation as experimental trials to do science on your underlying physical system to better model it.


Fixing these 3 problems.

So we've identified 3 problems:

  1. Entropy-per-trial can be less than ideal, meaning that we can't generate as much random-data as experimental-data.

  2. Binning possible outcomes can be lossful, generating less entropy than a naive calculation would suggest possible. This requires generating even more data, and even then binning might not be perfect.

  3. All of these models are empirical and imperfect; a dedicated or advanced attacker might be able to model the underlying physics better than the random-data generator, breaking the random-data-generator's assumptions.

In short, the output from a "True" Random Number Generator (TRNG) (a term which I really dislike, but that's another rant) can be insecure before it's been compressed.

These compression methods fix these problems (in a practical sense, anyway).

  1. By reducing the random-data produced to be more in line with experimental entropy, the idea that the random-data represents "true" entropy can seem more plausible to some.

  2. The cryptographic hash functions guard against attackers trying to back-calculate anything.

Ultimately, it's a clumsy process that probably isn't quite as robust as one might like to imagine, but it gives everyone what they want. Folks who want to believe that the random-data is truly independent are enabled to hold that belief by the seeming plausibility of having the entropy of the experimental source while folks who want random-as-far-as-anyone-can-tell data can be provided for by the power of cryptographic hash functions.


Summary.

There're a lot of theoretical problems with common practices in generating allegedly "true" random data, but lossfully cryptographically hashing everything makes it work.

So your source probably meant that the experimental-data produced by the physical process was insecure before the lossful cryptographic hashing (which they referred to as "compression"). But it's that step that's meant to smooth over all these issues.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ We're not talking compressing files to a smaller size, we're talking about a one-way compression function as defined in cryptology. There is no "describing" the data in the sense most people would think of it, only making less of it in a way that removes biases. Also, if you use such a strict definition of true randomness, nothing is truly random; even TRNGs built from the inherent randomness of quantum mechanics have to be passed through a compression function. $\endgroup$ – Serpent27 Sep 7 at 6:25
  • $\begingroup$ @Serpent27: There's a lot to untangle here. For example, we seem to be mixing compression with a lossful truncation with whitening, and further assuming a realist interpretation of quantum mechanics. There's no need to come up with a way to define "true" randomness; if the concept doesn't precisely fit something, we needn't refer to it. I see "true" randomness with the same sort of disdain academic cryptographers hold for "military-grade" encryption -- it's a silly buzzword that twists things to sound cooler. $\endgroup$ – Nat Sep 7 at 6:35
  • $\begingroup$ @Serpent27: I can probably write more later to note some extra stuff (on mobile, so it's obnoxious to type here). For example, I do like your point that this compression can be lossful, as there's no requirement to decompress. $\endgroup$ – Nat Sep 7 at 6:40
  • $\begingroup$ I never mentioned truncation. I'm simply pointing out the goal isn't to describe something more concisely, the goal is to remove bias. If you want to describe the data generated by your TRNG you'll surely remove some bias but the data still won't be usable in my definition of "usable" as a cryptologist. You'll still have enough bias that I would think twice before using your TRNG, and you'll introduce side-channel attacks that could allow an attacker to observe the data as it's generated. $\endgroup$ – Serpent27 Sep 7 at 6:45
  • $\begingroup$ The key is to remove relationships, not explain them more concisely. That's why you end up with less data - you use a compression function that only keeps patterns you'll never find in the input data, producing a patternless stream of usable data. Even lossy compression will keep patterns if you think you're going to make the data more random by describing it differently. $\endgroup$ – Serpent27 Sep 7 at 6:47
0
$\begingroup$

I see this as being relatively straight forward. If the compression algorithm could detect the next chunk of data from the previous chunks of data such that it was able to reliably compress it. Then it wasn't a great random chunk anyway, so there's not much benefit in including all of it in your 'secure' coding. If you compress it, then it can still contribute something, but it will be further transformed (via the compression). As noted, lots of sources of entropy will still have some bias. I think you'd find that many of them, like smart cards etc, will already factor in compression when returning results. i.e. if you ask for 2048 bits of 'entropy data', then this is probably not just the next 2048 bits that fly out of its signal generator. It probably already runs that through compression so that you do actually get 2048 bits of compressed data (hence removing less 'random' data).

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is not a completely unreasonable answer, but I think based on the context provided in the quote the word "compression" refers to this definition $\endgroup$ – President James K. Polk Sep 5 at 13:58
  • $\begingroup$ Good reference, thanks. $\endgroup$ – BevanWeiss Sep 6 at 5:45

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.