2
$\begingroup$

Knuth describes in "the art of computer programming part 2" an algorithm called "M" for mixing two streams of random numbers. This can be used to mix random number streams giving the assurance that the result is still random even if one (but only one) of the streams suddenly becomes predictable.

Now I have a situation where I do have two streams but they're asymmetrical: one produces +/- 800 bytes per second, the other +/- 340.

My question now is: what can I do so that I can still combine these two and accomplish the same as Knuth's algorithm?

I was thinking of "just feeding them to a hash" and use that result. What do you think?

Improve this question
$\endgroup$
0
2
$\begingroup$

You can slow the faster stream down to match the slower (e.g. throw away about half the bytes) and use Knuth's algorithm. You will only run at the speed of the slower, but that's the only way to assure full entropy when only one of the streams is unpredictable.

If you want to also account for cases where both streams are only partially unpredictable, you could use a hash instead. E.g. take the SHA-256 of the concatenation of 40 bytes from stream A and 17 bytes from stream B, then truncate that to 17 bytes. For example, if the high bit in each input byte was predictable, this hash would still be completely unpredictable, while the XOR would not.

However, hashing may lose some entropy in the case where stream A is completely predictable, but stream B completely unpredictable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your reply. I've got a further question: I vaguely remember something about mixing your entropy-data with a known good prng. This then would prevent hacks or whatever as the stream would still look random for outsiders. Any commments on this? My idea was to feed the 340Bps stream into a self-feeding prng and use that for "the 2nd stream" to feed in algorithm m. $\endgroup$ – Folkert van Heusden Jul 14 '14 at 12:53
  • $\begingroup$ Well, you could seed a CSPRNG using the slower source, then XOR its output with the faster source, but if you have a CSPRNG you could just seed that once and use that as is. See also: crypto.stackexchange.com/a/17898/13625 $\endgroup$ – otus Jul 14 '14 at 13:23

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.