So today I had a little brainwave about CSPRNGs. I was pondering the many-millenia history of people trying to determine Pi - and then later to find patterns in it.
And it turns out that it was this silly little BPP formula, which is well described and has interesting digressions here: http://www.ams.org/notices/201307/rnoti-p844.pdf Essentially they decided to fuzz some equation parameters for Pi, and it worked. So anyway, it occured to me that the main thing about this process is the throwing away of information when generating a digit... at least in the "mod 1" section of the document (I haven't worked through the parenthetical calculations yet, but they involve computing GCDs and whatnot). Anyway that mod 1 reminded me of reduction mod N. And then it struck me that this throwing away of infromation was used quite extensively in HWRNGs too, where we take an analog signal and reduce it to a bit (or a small number thereof), depriving an attacker of valuable information about the actual analog measurement, which could be used to model the internal process. But we can go farther: Blum Blum Shub takes the form x_{n+1}=x_{n}^{2} (mod M) where M = pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1. And here we see some confusion of the bits of xn+1 into a parity bit. What could be better to prevent knowing internals, than to have large entropy in a pool, and hash it together before output? Certainly this is an improvement over reduction mod N of some particular internal state, yes? Or taking its parity? And so, it seems, we have a useful general form for PRNGs; we have some "diffusion" step which alters the internal state, allowing a change to spread around to other bits, or allowing a chaotic function to lead to new states, and a "confusion" property for the extraction which prevents the adversary from knowing precisely the internal state of the system. I'm too tired to elaborate on this and bring it up to Linux /dev/random pool but I think you will see the ideas. The injection of bits and movement of steppers throughout the pool... the hash on extraction. I would wager that many other CSPRNGs fall into this pattern. Which leads me to wonder if we can build significantly better ones, especially given that the simple Pi formula eluded us for so long. -- http://www.subspacefield.org/~travis/ | if spammer then [email protected] "Computer crime, the glamor crime of the 1970s, will become in the 1980s one of the greatest sources of preventable business loss." John M. Carroll, "Computer Security", first edition cover flap, 1977 _______________________________________________ RNG mailing list [email protected] https://lists.bitrot.info/cgi-bin/mailman/listinfo/rng
