Sorry for the ramblingness of that email, it was written nearly a decade ago in a fit of pique. I'll rewrite it all one day, just figured I'd share while the iron was hot.
On Wed, Mar 19, 2014 at 04:28:08PM -0700, [email protected] wrote: > I am thinking of making a userland unpredictability distribution > system, so that expensive HWRNGs may be shared securely amongst > several machines. > > Here's the algorithm from generation to use: Please note that each node gets a stream of data which is computationally independent of the other streams, so the most this system can give is computational security. As such, if the receiving pool (entropy sink) is /dev/urandom, then the listener should not update entropy counts. But you generally only use /dev/random for key generation and OTP generation anyway, so no big deal; if you need that, get it straight from stage 2, and don't send it over the network. > 1) Unpredictability harvested from HWRNG. Step 1.5) test output of HWRNG prior to anything else, alert if it falls into certain failure modes. > 2) Unpredictability mixed with PRNG output to disguise any biases > present in source. The Mersenne Twister suggests itself due to its > extremely long period and fast use but I think a CSPRNG is better. > (Is XOR sufficent and desirable as mix function?) We can reseed the mixing CSPRNG with /dev/urandom periodically; the idea is to whiten the HWRNG output before it hits the network, and do so (if using CSPRNG) with computational security guarantees. For that matter, we could use a "CSPRNG with input" like /dev/urandom on this side so that there's no looping, ever, assuming this HWRNG box has some other source of entropy. > 3) Unpredictability used as "truly random" input in an extractor to > map "somewhat random" input (interrupt timing, memory contents, disk > head settling times) into "strongly random" output. Extractor can > range from hash to proper extractor functions (look them up, they are > not what you think). New sponge funtions (keccac, a/k/a SHA-3) are > promising here. > > 4) Unpredictability passed through OWF to occlude state of previous > systems in this chain. Actually re-reading this idea (nearly 10 years old, with minor recent comments) it appears that given new sponge functions like Keccac, we can actually merge step 3 and 4. > 5?) Unpredictability ciphered with a randomly-generated key (taken > from the previous step), rotated periodically. Unclear on if this is really useful; I doubt it. Seems redundant to combining with CSPRNG. > 6) Unpredictability transmitted over the network. Can use subnet-directed UDP broadcasts over LAN so that every listener receives a constant stream of unpredictability they can tune into at any time, no handshaking required, etc. > 7) Recipient ciphers the unpredictability with a randomly-generated > key, rotated periodically. The randomly-generated key is taken from > the previous output of step 8 so that data on the wire is never used > directly to cipher future data sent over the wire (requiring an > attacker to be able to accurately model step 8). Can use MAC address, other system-unique information, system fingerprint, IP address, dakarand, etc. to seed the initial pool used to generate this receipient key. It's important that no two systems have the same recipient key so that their randomness streams are computationally independent. > 8) Recipient repeats steps 2-4 locally. This might simply involve > dumping it to /dev/random, as one option that requires no changes to > the client OS. > > 9) Unpredictability is used in an application needing it. > > Here's my claims: > > 1) There is no key distribution to worry about. > > 2) Eavesdropping only gets you known-ciphertext. You still have no > idea about the plaintext, which is random, so you have no general way > to recognize a successful brute-force attempt on the > randomly-generated key used by the recipient. To be perfectly accurate, you're getting x before f_k(x) is mixed into the local system, where f is some computationally-strong function and k is a locally-generated unique key which is as unpredictable as the local system could do without the udd system in place. > 3) You'd have to figure out how some part of the transmitted data was > used by the recipient, and work forward with each trial key to see if > the results match in order to recognize a successful guess at the key > used in step 7. Would re-ordering data randomly on the recipient be > useful to thwart this, or is it unnecessary? This claim could be clarified; basically, to get the unique recipient key in step 7, you'd have to find network input, and use of the client RNG (e.g. nonce), and brute force the key. > 4) The most effective way to compromise such a distribution system > that I can think of would involve cracking the recipient system, and > if the enemy can do that, no crypto can help you. > > I deliberately used the term cipher instead of en/decrypt because I am > not sure it matters which direction we go, as long as it doesn't > introduce any detectable statistical biases in the unpredictability > (weakening it). For that matter, we could HMAC it. What properties > should I look for, and what level of assurances? > > Can you see any weaknesses or unnecessary steps in this model? I'm > not sure 5 is necessary (it was just suggested by symmetry). > > Regarding the userland daemon, I was thinking of replacing the > /dev/urandom functionality with a userland daemon, because: > > (a) cryptographic operations can be slow, and putting them in the > kernel, which cannot block, is not desirable > > (b) development is easier, this will encourage people to tinker with > it more > > (c) having the kernel perform HTTP requests to get random numbers from > web sites is inappropriate > > I am not sure this is good solution, though... perhaps better > to have userland daemon which tends the pool. > > What I want to do is: > > 1) Mix various sources of "untrusted" unpredictability in such a way > as to make a strong claim as to the mixture. For example, these web > sites offer free random numbers: > > http://www.random.org/ > http://www.randomnumbers.info/ > http://www.fourmilab.ch/hotbits/ > > Why shouldn't I download some numbers from these sites periodically, > and combine them with the pool? I don't have to update the > unpredictability count (indeed, this is a PRNG and so tracking > "actual" unpredictability is somewhat irrelevant). The way I see it, > if I XOR numbers from these sites with my PRNG output, even if an > attacker eavesdrops on this traffic, I'm no worse off than if I hadn't > used them at all. Unpredictability XORed with predictability is still > unpredictable. > > Similarly, I also would like to use ID Quantique's HWRNG based on > optics, but their modules are sealed and opaque. What I want to do is > explore what kind of assurances I can make about the output, based on > assumptions about the attacker's ability to control, predict, or > observe one of the sources. > > 2) Occlude common biases in the HWRNG, which is the main input to the > daemon. > > 3) Combine PRNG components in novel ways. > > 4) Create a plug-in framework for PRNG components. > > 5) Do it in a language not as prone to security-relevant errors as C > and containing support for large numbers and bitstrings as first-class > objects. I'm leaning towards python, heard good things about ruby, > and open to suggestions that something very different like ocaml might > be better. > > Stumbling blocks that I can see: > > 1) Lack of standardization in the naming or semantics of kernel > facilities, such as the names of devices in /dev. > > 2) Lack of support for sockets in the target language. > > 3) The use of ioctls for interfacing to sources of unpredictability in > the kernel. > > 4) The use of tty devices to interface to HWRNGs > > 5) Multiple clients petitioning the daemon for random bits at once. > However, this is also a good thing; two consecutive values used by a > client may not be consecutive outputs from the PRNG subsystem. -- http://www.subspacefield.org/~travis/ Remediating... LIKE A BOSS
pgp5O3BbjBZEq.pgp
Description: PGP signature
_______________________________________________ RNG mailing list [email protected] http://lists.bitrot.info/mailman/listinfo/rng
