Join Log in
Score:2
Matt avatar Crypto

Conditioning a biased source with a block cipher?

pe flag
Matt

I'm working my way through Stallings's book Cryptography and Network Security. I'm self-taught on crypto, never took a class but I've implemented some crypto accelerator functions in hardware at work and am interested in learning more.

Chapter 8 covers random bit generation. The discussion of true random number generators talks about bias and how to remove it with conditioning algorithms. One such option is to feed the true rng output into a block cipher such as AES. What?

I understand how this would produce data that appears random and passes tests of randomness. But if the input is known to be biased a certain way, brute force could be used to try to reproduce the random bit stream. Taken to an extreme, what if the true rng supplied only 1s very rarely. An attacker could try a small number of one-hot, two-hot, etc. keys in the block cipher and something will match.

Surely I'm missing something...

45
0 + 0
fgrieu avatar
ng flag
fgrieu
It might help to state edition of Cryptography and Network Security, and a more precise description of how the block cipher is used, if one is given.
1
Reply
Score:1
Paul Uszak avatar Crypto
cn flag
Paul Uszak

A more appropriate reference is NIST Special Publication 800-90B, "Recommendation for the Entropy Sources Used for Random Bit Generation" since you're using the term "true random number generators" and not "deterministic".

There's too much for this answer, so I refer you to §3.1.5.

What if the true rng supplied only 1s very rarely

Irrelevant, and very common in ring oscillator entropy sources. Let's say "rarely" means one transition in a 100 samples. You throw away 99 samples, and just keep the 100th through a process called decimation. I seen divide by 512 decimators in experimental ring oscillators. E.g.:-

decimator

NIST keep changing the entropy estimation procedures (to discourage their use?) but the latest is §3.1.5.1.2 Entropy Assessment using Vetted Conditioning Components reproduced here:-

grab

This is NIST's version of the Left Over Hash lemma (inferred from above step 4). Although many designs simply use the original lemma when no cryptographic conditioning components are necessary. And the advantage of the lemma is that it allows direct computation of the final entropy bias.

So in summary, entropy source bias is easily dealt with by well established techniques. Of course the more bias, the slower the final output rate/less efficient design.

0 + 0
Matt avatar
pe flag
Matt
Implicit in this answer is the same concept as the other answer, that a more biased source produces bits slower because of less entropy per bit. Thanks.
0
Reply
Paul Uszak avatar
cn flag
Paul Uszak
@Matt Of course, but it directly answers your _"what if the true rng supplied only 1s very rarely"_ question (hopefully). And it shows you how to do it, essentially making the level of bias moot wrt a brute force attempt at RNG inversion.
0
Reply
Score:1
fgrieu avatar Crypto
ng flag
fgrieu

Often, conditioning algorithms have an output sizably smaller than their input, which goes a long way towards solving the real problem in the question: if there is not enough entropy in the input, there can't be in an output of the same length.

As a simple example using AES-256, splitting a 384-bit input bitstring into a 128-bit and a 256-bit bitstring, then encrypting the first per AES-256 with key the second will output a 128-bit conditioned output.

If each input bit has at least 0.5 bit entropy (for independent bits: mean in [0.11…, 0.89…] ), the 256-bit key has 128-bit entropy; and the 64-bit entropy of the 128-bit block further makes it hopeless to build a practical distinguisher working on the output alone.

0 + 0
Matt avatar
pe flag
Matt
I think this makes sense to me. The idea is to throw away enough bits so that we only obtain the same number of bits as the entropy of the source. I think my lack of background in information theory stopped this from being obvious to me, but it makes intuitive sense.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.