[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: use of RDRAND in $random_library

Gunnar Wolf <gwolf@gwolf.org> writes:
> Russ Allbery dijo [Thu, Jun 12, 2014 at 07:08:40PM -0700]:

>> I would certainly hope that the mixing algorithm of any decent random
>> number source is better than just xor.  And given that, I don't believe
>> the mathematics supports your assertion here.  It's considerably harder
>> to backdoor a random number generator to cause a higher-level mixing
>> random number generator that combines multiple sources of entropy to
>> produce predictable random numbers than it is to cause it to spit out
>> predictable random numbers directly.

> Excuse me if I'm blunt here, but I understand that, on the point of
> using entropy to seed a PRNG, if you have several shitty entropy sources
> and one _really_ good one, and you xor them all together, the resulting
> output is as random as the best of them. If your hardware entropy source
> is faulted and produces just an endless stream of '001001001001001001',
> xoring it with a valid Golomb sequence will give you something even more
> random than a Golomb sequence.

> Or am I misunderstanding my crypto?

I don't think you are, but xor has a bunch of unintuitive properties
where, if you know or can predict even portions or mathematical properties
of one of the byte streams involved in the xor, you can do lots of
interesting things with the results.  I was assuming that Josh was
thinking of something along those lines.

It's possible that xor with other entropy sources is good enough and xor
defeats a backdoored random number source, but I don't know the math well
enough to hazard an opinion.  I do know that the cryptographically secure
random number generators whose algorithms I've read about use stronger
one-way functions instead of xor: stream ciphers, block ciphers, or
cryptographic hash functions.  At least based on my understanding of the
theory, I think that mixing a backdoored entropy source with other entropy
sources in a random number generator like Fortuna (which is based on the
AES block cipher in counter mode) would make it quite difficult for an
attacker with knowledge of the back door to exploit that knowledge.

I don't know enough about the exact algorithm behind /dev/random to be
sure that the same is true for it, but I would hope that it is.  (Although
Wikipedia says that it's hash-based, which would probably make it quite a
bit slower than Fortuna since hashes are slower than block ciphers.)

Russ Allbery (rra@debian.org)               <http://www.eyrie.org/~eagle/>

Reply to: