[Cryptography] combining lots of lousy RNGs ... or not

Ron Garret ron at flownet.com
Tue Nov 22 15:03:23 EST 2016


On Nov 22, 2016, at 7:13 AM, Phillip Hallam-Baker <phill at hallambaker.com> wrote:

> On Mon, Nov 21, 2016 at 5:53 PM, John Denker <jsd at av8n.com> wrote:
> 
>> Here are some useful equations:
>>   random XOR squish = random
>>   squish XOR squish = squish   (*not* random)
>> 
> ​No. random XOR squish = squish
> 
> If I can interfere with squish, I can undo your random if I know it. And in real world systems I can often know it. 
> 
> ​A better equation is H (random + squish) = random​

Talk about burying the lede.

If you XOR, then correlations among sources manifest themselves.  If you hash, then they don’t.  Hashing extracts any and all entropy in the system wherever it happens to be (assuming a cryptographically secure hash, of course).  XORing does not.

I am constantly surprised by how often discussions of randomness arise on this list, and how long they continue.  Everything that matters about randomness can be summarized in four bullet points:

1. You need two things: an entropy source, and a whitener. No entropy source is perfect, so you need a whitener no matter what. You don't have to do anything fancy in your whitener. Any cryptographically secure hash function (like SHA512) will do.

2. Since you need a whitener no matter what, it doesn't really matter how good your entropy source is, except insofar as it might take a long time to collect enough entropy from a very poor source. All that matters is that you have an accurate lower bound for how much entropy your source actually provides, and this is the case no matter how good (or bad) your source actually is. As long as you feed >N bits of entropy into your whitener, you can safely extract N bits of true randomness out of it.

3. You don't need more than a few hundred bits of randomness. 128 bits is enough, 256 is a comfortable margin, 512 is serious overkill. Seed a cryptographically secure PRNG with a few hundred bits of entropy and you can safely extract gigabytes of key material out of it.

4. Because of 1-4, putting a lot of effort into designing and tuning a HWRNG is pointless. Such a device provides no value over a poor entropy source fed through a whitener provided you have an accurate lower bound on the entropy content so you can be sure you have seeded your PRNG with enough initial entropy.

But if it makes you feel warm and fuzzy to pay a lot of money for a HWRNG, I am more than happy to sell you one!  https://sc4.us/hsm (NOTE: I am currently out of stock but will be shipping again in January.)

rg



More information about the cryptography mailing list