Re: EDP (entropy distribution protocol), userland PRNG design
On Sun, Jul 02, 2006 at 03:25:09AM -0500, Travis H. wrote: > Going over old emails. > > On 10/12/05, Jack Lloyd <[EMAIL PROTECTED]> wrote: > >I prefer a multi-stage design, as described by various people smarter than > >I > >am: > > > > source(s) --> mixer --> pool --> extractor --> X9.31 > > Did you really mean X9.31 and not X9.17? Yes. IIRC, same thing, just in a different standard. (And I have a copy of X9.31, while I've never even read X9.17) -J - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
Going over old emails. On 10/12/05, Jack Lloyd <[EMAIL PROTECTED]> wrote: I prefer a multi-stage design, as described by various people smarter than I am: source(s) --> mixer --> pool --> extractor --> X9.31 Did you really mean X9.31 and not X9.17? -- Resolve is what distinguishes a person who has failed from a failure. Unix "guru" for sale or rent - http://www.lightconsulting.com/~travis/ -><- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
At 01:01 AM 2/4/2006, Travis H. wrote: Assume further that it is not cost-effective to furnish each with a HWRNG, even one as inexpensive as a sound card (for example, they may not have a spare slot on the motherboard nor built-in sound). ... Suppose that /dev/random is too slow (SHA-1 was never meant to generate a lot of output) because one of these machines wishes to generate a large file for use as a one-time pad*. One-time pads are expensive protocols to use properly - the operational costs of generating easily-disposable media, putting couriers with briefcases handcuffed to their arms onto airplanes, shredder costs when trashing the CD/DVD/etc., /dev/thermite for the PCs, and all the other things that you need to do for a real OTP threat model add up to real money after a while. If you can afford that, you can afford to spend $100 for an external sound card or USB hardware random generator dongle or whatever or a PC case with more slots in it. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
"Travis H." <[EMAIL PROTECTED]> writes: > On 2/4/06, Eric Rescorla <[EMAIL PROTECTED]> wrote: >> Look, this design just reduces to a standard cryptographic PRNG with >> some of the seed being random and periodically being reseeded by the >> "random" network stream you're sending around. There's no need to >> worry about the integrity or confidentiality of the "random" stream >> because anyone who controls the network already knows this input. The >> only information they don't have is your "random" private key. > > How do you figure? If the random stream conveys 1kB/s, and I'm > reading 1kB/s from /dev/random, and the network traffic is not > observed, then I am not stretching the bits in any way, and the result > should be equivalent to reading from the HWRNG, right? Well, for starters the assumption that nobody is monitoring the network traffic is in general unwarranted. However, the equivalence (or lack thereof) to a HWRNG depends entirely on the details of the mixing function in /dev/random, network buffering, etc. But since /dev/random is basically a PRNG, it's not clear why you think there's any difference between your and my designs. -Ekr - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
On Sat, 4 Feb 2006, Travis H. wrote: Suppose that /dev/random is too slow (SHA-1 was never meant to generate a lot of output) because one of these machines wishes to generate a large file for use as a one-time pad*. That leaves distributing bits. * /dev/random's output is limited by available entropy, not the speed of sha1. You want /dev/urandom instead. * You're talking about a stream cipher, not a OTP, especially since an attacker could see the "plaintext" over the network and would only need to break the cipher to get at the "pad" * It's dangerous to offhandedly propose stream ciphers, especially when we have some tried and tested ones, and it doesn't really make sense to use them as if they were OTPs, since then you get the benefits of neither * Hash functions are comparably fast to ciphers anyway, and are plenty fast for the application you propose: [EMAIL PROTECTED] ~$ openssl speed sha1 Doing sha1 for 3s on 16 size blocks: 1718543 sha1's in 2.99s ... [EMAIL PROTECTED] ~$ dc 1718543 20 *p 34370860 So sha1 generates 34Mbyte/sec, which is enough to saturate a gigabit ethernet link in many installations. -J - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
"Travis H." <[EMAIL PROTECTED]> writes: > That leaves me with the following design: > > That random numbers be sent en clair from the system that can generate > them to the system that needs them, where they are decrypted using a > random key (generated locally by /dev/random) and fed into the system > that needs them, in this case the pool used by /dev/random (where they > will be hashed together with interrupt timings and other complex > phenomena before being used). > > If the attacker has no access to the LAN traffic, then it gives the > benefit of a local HWRNG. If the attacker has access to all the > network traffic and a great deal of the output of /dev/random on the > receiving machine, he has at best, a "ciphertext" and the hash of the > (completely random) "plaintext" to work with. In actuality it is > liable to be less clear than that, as /dev/random will scramble it > with a bunch of low-level stuff and give the hash of that. State > remains in the /dev/random pool, so that the next transmission will be > mixed with the pool created by the first transmission and so on. So > in practice an attacker wouldn't even have the hash of the plaintext. > > Does anyone see any problem with the reasoning or resultant design? > I'd prefer to not argue over the assumptions. Does anyone have any > ideas about how to handle authentication/integrity? Look, this design just reduces to a standard cryptographic PRNG with some of the seed being random and periodically being reseeded by the "random" network stream you're sending around. There's no need to worry about the integrity or confidentiality of the "random" stream because anyone who controls the network already knows this input. The only information they don't have is your "random" private key. That said, frankly, this is all rather silly. A good cryptographic PRNG seeded with a few hundred bytes of high-quality randomness is good enough for bits of randomness is good enough for practically any purpose. Practically the only thing it's not useful for is for generating OTPs, which, as people have repeatedly told you on this list, you shouldn't be doing anyway. Note further that no CPRNG can be safely used to generate OTPs--except for rather short ones--because the entropy of the resulting randomness stream is bounded by the size of the CPRNG state no matter how many bits of entropy you feed into it. The technical term for this is a stream cipher. -Ekr - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
Assume that one is the sole user of a LAN and that the 10-20 machines on this network have a need for unpredictable numbers. Assume further that it is not cost-effective to furnish each with a HWRNG, even one as inexpensive as a sound card (for example, they may not have a spare slot on the motherboard nor built-in sound). So basically, one must either: 1) Use something like /dev/random, which uses complex but deterministic events to hopefully generate unpredictable numbers, albeit at a slow rate. 2) Send random numbers to them over the LAN. First a mention of /dev/random. In this case, let's assume NetBSD's /dev/random implementation. That is a pool with an estimated entropy count, and it mixes inputs into the pool using a simple LFSR algorithm, and hashes the pool to get output using SHA-1. For people who want the gory details, source is here: http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/dev/rnd.c?rev=1.46.2.1&content-type=text/x-cvsweb-markup http://cvsweb.netbsd.org/bsdweb.cgi/src/sys/dev/rndpool.c?rev=1.19&content-type=text/x-cvsweb-markup Suppose that /dev/random is too slow (SHA-1 was never meant to generate a lot of output) because one of these machines wishes to generate a large file for use as a one-time pad*. That leaves distributing bits. So now that one has decided to send them numbers over the LAN, one decides to protect the confidentiality via encryption, and to protect against malicious insertion via authentication and integrity. So one could use a conventional cipher and signature to protect it in transit. For simplicity let's just consider the encryption, and ignore integrity/authentication for a moment. Since these numbers are random to begin with, and the only goal is to get random numbers on the receiving node, is there any reason to use the same encryption key on both ends? That is, would it not be safer to use a random key (obtained from the slow /dev/random device) on the receiving end, since it then would have very little chance of being disclosed (by virtue of never being negotiated or transmitted)? And since the receiver's key is randomly generated (via local means), is there any reason to do any encryption at all on the sending end? That leaves me with the following design: That random numbers be sent en clair from the system that can generate them to the system that needs them, where they are decrypted using a random key (generated locally by /dev/random) and fed into the system that needs them, in this case the pool used by /dev/random (where they will be hashed together with interrupt timings and other complex phenomena before being used). If the attacker has no access to the LAN traffic, then it gives the benefit of a local HWRNG. If the attacker has access to all the network traffic and a great deal of the output of /dev/random on the receiving machine, he has at best, a "ciphertext" and the hash of the (completely random) "plaintext" to work with. In actuality it is liable to be less clear than that, as /dev/random will scramble it with a bunch of low-level stuff and give the hash of that. State remains in the /dev/random pool, so that the next transmission will be mixed with the pool created by the first transmission and so on. So in practice an attacker wouldn't even have the hash of the plaintext. Does anyone see any problem with the reasoning or resultant design? I'd prefer to not argue over the assumptions. Does anyone have any ideas about how to handle authentication/integrity? [*] Alternately, I could use FreeBSD's /dev/random, which is essentially Yarrow, but reseeded with some low-level timings. This would leave me with pseudorandom bits that are somewhere between counter-mode AES and truly random bits. I feel that this would not create strong enough OTPs to justify using an OTP algorithm, but I suppose you could argue that the method I propose isn't either, if you don't trust the privacy of your own LAN. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
I've been following this thread for a couple of weeks now, and so far virtually none of it makes any sense to me. Back on 10/12/2005 Travis H. wrote: I am thinking of making a userland entropy distribution system, so that expensive HWRNGs may be shared securely amongst several machines. What evidence is there that HRNGs are expensive? How many machines do you have? How many of them already have soundcards? How much entropy do they need (bits per second)? The obvious solution is to put a high-performance low-cost HRNG in each machine. http://www.av8n.com/turbid/ Is there some reason why this cannot be done? If so, please explain. Otherwise, this whole discussion seems like a futile exercise, i.e. trying to find the optimal way of doing the wrong thing. ]] ABSTRACT: We discuss the principles of a High-Entropy Randomness Generator (also called a True ]] Random Number Generator) that is suitable for a wide range of applications, including ]] cryptography, high-stakes gaming, and other highly adversarial applications. It harvests entropy ]] from physical processes, and uses that entropy efficiently. The hash saturation principle is used ]] to distill the data, resulting in virtually 100% entropy density. This is calculated, not ]] statistically estimated, and is provably correct under mild assumptions. In contrast to a ]] Pseudo-Random Number Generator, it has no internal state to worry about, and does not depend on ]] unprovable assumptions about “one-way functions”. We also describe a low-cost high-performance ]] implementation, using the computer’s audio I/O system. For details, see http://www.av8n.com/turbid/ Here's the algorithm from generation to use: 1) Entropy harvested from HWRNG. OK so far. 2) Entropy mixed with PRNG output to disguise any biases present in source. ... (Is XOR sufficent and desirable?) If it were a decent HRNG it would have this built in. XOR is not even remotely sufficient. 3) Entropy 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. What's an extractor? What is needed is a compressor. 4) Entropy passed through OWF to occlude state of previous systems in this chain. A decent HRNG is stateless and does not need any one-way functions. 5?) Entropy ciphered with a randomly-generated key (taken from the previous step), rotated periodically. A decent HRNG does not need any such encipherment. Similarly, I also would like to use ID Quantique's HWRNG based on optics, Why? 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. Such assurances are discussed at: http://www.av8n.com/turbid/ 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. turbid is already written in C++ for this reason. Strings and suchlike are part of the language, defined in the Standard Template Library. 1) Lack of standardization in the naming or semantics of kernel facilities, such as the names of devices in /dev. The semantics is just broken ... which is why turbid defines and implements /dev/hrandom with its own semantics. Optionally it can feed entropy to /dev/[u]random for the benefit of legacy applications under certain limited conditions. 2) Lack of support for sockets in the target language. Really not a problem with turbid. 3) The use of ioctls for interfacing to sources of entropy in the kernel. Really not a problem with turbid. 4) The use of tty devices to interface to HWRNGs Really not a problem with turbid. 5) Multiple clients petitioning the daemon for random bits at once. Really not a problem with turbid. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
> I can't say I a fan of the idea of having multiple ways of mixing entropy into > the system. In particular, the idea of producing output by XORing your PRNGs > output with the output of a semi-public RNG seems like a bad idea to me, > because an attacker can easily control those values by taking over the web > server or modifying packets in the network, and if they can somehow predict > your PRNG outputs then they will be able to actually control the final output. Is it that XOR is too simple? That is, if I used a "secure mixing function" (RFC 1750), perhaps a OWF, would this solve the problem? Then an attacker couldn't find a preimage that would produce a chosen output. > source(s) --> mixer --> pool --> extractor --> X9.31 I would think you'd want to use an extractor* on the sources before they get commingled with other stuff. Of course the extractor operates on two sources (one weakly random, the other uniformly random) to generate nearly-uniform values, so it is doing a kind of mixing of streams. However, the output of the PRNG subsystem could be fed back as the "uniformly random" input probably. Of course you'd need a good seed to bootstrap the whole thing. [*] mathematics sense of the word: http://en.wikipedia.org/wiki/Extractor One good reason to do some randomness work outside the kernel is you can't do floating point in most Unix kernels, so if you're computing chi-square or some other statistic, you've either got to convert it to integer math or do it outside the kernel. On the down side, you've got scheduler delays adding to the latency of each request. > I believe most common hardware RNGs produce data at fairly high rates, often I don't trust most of those sources to generate non-correlated bits at high rates. You know, the designs where they latch the output of oscillators based on some signal with random jitter is kind of like performing a modulo operation. Some information is thrown away in a many-to-one mapping, I wonder if you could gain something by modeling the jitter measurement before it is used to latch the output of the oscillator. It'd be like knowing g^x prior to modular reduction (mod n) in Diffie-Hellman. > You could also just solve the problem you mention directly, and try to find a > cheaper HWRNG design. I know people who have built them for a few dollars Terry Ritter has a lot of designs like this: http://www.ciphersbyritter.com/NOISE/NOISRC.HTM I'd like a system that is elegant and simple for harnessing, purifying, and securely stretching such values. By elegant and simple, what I mean is that it obviously has no weaknesses, as opposed to having no obvious weaknesses. -- http://www.lightconsulting.com/~travis/ -><- "We already have enough fast, insecure systems." -- Schneier & Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
On 10/18/05, Jack Lloyd <[EMAIL PROTECTED]> wrote: > Peter Gutmann has several good papers on RNG design, as have some folks > currently or formerly associated with Counterpane (ie Wagner, Kelsey, Hall, > ...). It is worth reading their analysis papers as well as their design > papers, > especially the ones that cover fielded PRNG designs. It's interesting that you mention that, because that counterpane paper, http://www.schneier.com/paper-prngs.html points out several flaws in the ANSI X9.17 PRNG. > mentioned, "oversampling won't help you generate random bits any faster; you > will get more bits but no more randomness." Yeah... in most cases you'll get serial-correlated (autocorrelated) bits, and then if you're using a von Neumann corrector, you'll get bias, and if you have bias you'll be unhappy, and if you're unhappy you'll sleep a lot, and we can't be having that. > However, I don't see how you are protecting the confidentiality of the data at > all in your current design. Well, you transmit the data, and then it gets encrypted with a random key before it is used... effectively this is a one-way function, so you'd have to mount a search on the key used if you want to be able to interpret how the network traffic is used downstream. Of course you'd want a cipher such that encryption with a random key doesn't introduce any bias. -- http://www.lightconsulting.com/~travis/ -><- "We already have enough fast, insecure systems." -- Schneier & Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
On Tue, Oct 18, 2005 at 12:18:57AM -0500, Travis H. wrote: > > > > source(s) --> mixer --> pool --> extractor --> X9.31 > > Where can I find out more about the design choices for these stages? Peter Gutmann has several good papers on RNG design, as have some folks currently or formerly associated with Counterpane (ie Wagner, Kelsey, Hall, ...). It is worth reading their analysis papers as well as their design papers, especially the ones that cover fielded PRNG designs. > > I believe most common hardware RNGs produce data at fairly high rates, often > > over 100 kbytes per second. > > Some do, some don't. Depends on the random source they are tapping. Of course. I was just pointing out that there are many that do produce at that rate. Since you weren't specific, I assumed it was a COTS hardware RNG. > However, that's a sealed opaque package, so I don't fully trust it. > I've been wondering if there's a way I could use it such that I didn't > have to fully trust it. For example, if I could combine several, so > that an effective attack would require collusion of several parties. That does not seem very difficult: just sample all of them. As long as your PRNG is good, an attacker won't be able to do anything by only controlling a subset of them. > > > Instead of treating the two entropy sources as somehow different in your > > mixing > > strategy, just use the HWRNG for most of the inputs, but every tenth sample > > (or > > whatever), instead use the hash of all the random-looking system data you > > can > > get ahold of. Only doing it occasionally means there is a reasonable chance > > that sufficient changes have happend to the system since the sample > > worthwhile > > in terms of entropy gained, and doing a large block of it all at once > > prevents > > iterative guessing attacks if an attacker can control your HWRNG outputs but > > not your system statistics. > > That seems like a very ad-hoc system that treats the HWRNG and > random-looking system data as somehow different (one is used for 90% > of the samples, one for 10%). Sorry, I should have been a little more clear. That 1/10 split was only supposed to be an example. You would presumably determine the appropriate sample rate based on an analysis of the system statistics. It is just as you mentioned, "oversampling won't help you generate random bits any faster; you will get more bits but no more randomness." You should sample each possible source so as to reach some maximum; presumably you either want to maximize total entropy over time, or total entropy over bits sampled, or maybe total entropy over # of samples. In any case, it's highly likely that alternating between reading 160 bits from a good HWRNG and the SHA1 hash of the output of `ps` is not going to produce any such maxiumum. The point of my suggestion was not that you implement those specific steps, but that you desing your PRNG so that it can make the best use of an arbitrary number of entropy sources with various (known or estimated) distributions. This ties in well with the previous point about using multiple HWRNGs. > > > Encrypting the output using keys generated by the PRNG is a good idea, but > > you > > presented it in a somewhat confusing way, in that it sounded almost like you > > were doing message transfer. [...] > > At not point do the two sides actually exchange messages, > > I don't follow. I'm transmitting entropy from the source to where it > is needed; surely this is a message of some kind? But that is all you are moving - entropy. As best as I could tell from your original proposal, the two sides never actually shared a key. So while one side was encrypting stuff and the other side was decrypting, at no point were they actually exchanging information. [...] > > > If > > you want to try to keep the entropy values sent from the box with the HWRNG > > to > > the client a secret from people on the network, just open up a TLS session. > > TLS is SSL, right? Yes. > > Transmitting over SSL would limit the strength to the minimum of the > strength of the asymmetric and symmetric ciphers. Using my method > alone would not involve PK, so would be faster, need less entropy to > start with, and also the upper bound on strength is the same or > higher. What I'm saying is that a chain is only as strong as its > weakest link, and my protocol has one less link. However, I don't see how you are protecting the confidentiality of the data at all in your current design. I was not suggesting TLS as an alternative, but as a method of achieving what you (apparently?) meant to do. However, if you could perhaps clarify what you meant with regards to encrypting the data that is transferred, that might help - I may well have simply misread you. In particular, how do the two sides agree on an initial key? I'm afraid I don't see how it is possible for two parties to use the same key starting out with no shared knowledge and without any public key operations.
Re: EDP (entropy distribution protocol), userland PRNG design
> I can't say I a fan of the idea of having multiple ways of mixing entropy into > the system. In particular, the idea of producing output by XORing your PRNGs > output with the output of a semi-public RNG seems like a bad idea to me, > because an attacker can easily control those values by taking over the web > server or modifying packets in the network, and if they can somehow predict > your PRNG outputs then they will be able to actually control the final output. Ah yes, leveraging a known output into a controlled output would be bad indeed. > I prefer a multi-stage design, as described by various people smarter than I > am: > > source(s) --> mixer --> pool --> extractor --> X9.31 Where can I find out more about the design choices for these stages? > I believe most common hardware RNGs produce data at fairly high rates, often > over 100 kbytes per second. Some do, some don't. Depends on the random source they are tapping. Mine, the Atom Age HWRNG, produces them at 9600bps: http://atom_age.tripod.com Here are two others: The Intel Random Number Generator http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf The Via C3 Nehemiah RNG http://www.cryptography.com/resources/whitepapers/VIA_rng.pdf The actual output rate depends on things like whitening and von Neumann correctors, and so may vary. In any case, the source has some limit on the entropy rate, and oversampling won't help you generate random bits any faster; you will get more bits but no more randomness. With HWRNGs based on radioactive decay, going fast means using some very unsafe substances. There are some very fast RNGs, such as the quantis: http://www.idquantique.com/products/quantis.htm However, that's a sealed opaque package, so I don't fully trust it. I've been wondering if there's a way I could use it such that I didn't have to fully trust it. For example, if I could combine several, so that an effective attack would require collusion of several parties. > Instead of treating the two entropy sources as somehow different in your > mixing > strategy, just use the HWRNG for most of the inputs, but every tenth sample > (or > whatever), instead use the hash of all the random-looking system data you can > get ahold of. Only doing it occasionally means there is a reasonable chance > that sufficient changes have happend to the system since the sample worthwhile > in terms of entropy gained, and doing a large block of it all at once prevents > iterative guessing attacks if an attacker can control your HWRNG outputs but > not your system statistics. That seems like a very ad-hoc system that treats the HWRNG and random-looking system data as somehow different (one is used for 90% of the samples, one for 10%). > Encrypting the output using keys generated by the PRNG is a good idea, but you > presented it in a somewhat confusing way, in that it sounded almost like you > were doing message transfer. [...] > At not point do the two sides actually exchange messages, I don't follow. I'm transmitting entropy from the source to where it is needed; surely this is a message of some kind? I think I see what you mean, though, in that you don't need to think of the encryption as part of the network protocol, but rather as processing of the already-transmitted data. > If > you want to try to keep the entropy values sent from the box with the HWRNG to > the client a secret from people on the network, just open up a TLS session. TLS is SSL, right? Transmitting over SSL would limit the strength to the minimum of the strength of the asymmetric and symmetric ciphers. Using my method alone would not involve PK, so would be faster, need less entropy to start with, and also the upper bound on strength is the same or higher. What I'm saying is that a chain is only as strong as its weakest link, and my protocol has one less link. > at little or no extra cost. You can buy a PCI board with a low-end Hifn crypto > chip on it for less than $80 online. For anyone who is interested, here is a link: http://www.hifn.com/info/candp/Boardpartners.html -- http://www.lightconsulting.com/~travis/ -><- "We already have enough fast, insecure systems." -- Schneier & Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
On Wed, Oct 12, 2005 at 04:49:43AM -0500, Travis H. wrote: > I am thinking of making a userland entropy distribution system, so > that expensive HWRNGs may be shared securely amongst several machines. [...] > Comments? > -- > http://www.lightconsulting.com/~travis/ -><- > "We already have enough fast, insecure systems." -- Schneier & Ferguson I can't say I a fan of the idea of having multiple ways of mixing entropy into the system. In particular, the idea of producing output by XORing your PRNGs output with the output of a semi-public RNG seems like a bad idea to me, because an attacker can easily control those values by taking over the web server or modifying packets in the network, and if they can somehow predict your PRNG outputs then they will be able to actually control the final output. The difference between knowing and controlling the PRNG output is a big deal when you're using it for something like DSA. I prefer a multi-stage design, as described by various people smarter than I am: source(s) --> mixer --> pool --> extractor --> X9.31 Take the sources, mix it into an entropy pool and then use an extraction function to derive values from the pool. Then use the values of that to seed a X9.31 PRNG and produce the final output with that (with the DT values also being generated by the extractor function). That helps make sure that even if you make a mistake with the extractor and/or mixer function you still have some level of protection. For example, even if an attacker can correctly guess every 16th bit of your extractor function, it will still be very difficult for them to guess the final PRNG outputs. I've found that it is much easier to think about the two functions as distinct, so you can reason about what specific properties you want or need the mixer and extractor to have, and it also makes it simpler to replace one or the other to make different security/speed tradeoffs. I believe most common hardware RNGs produce data at fairly high rates, often over 100 kbytes per second. If you have one of those you'll be able to get much more entropy from that than you will out of regular system sources, especially as the entropy of those samples usually decreases pretty strongly after the first sample or two, while the HWRNG keeps producing entropy at the same rate. Instead of treating the two entropy sources as somehow different in your mixing strategy, just use the HWRNG for most of the inputs, but every tenth sample (or whatever), instead use the hash of all the random-looking system data you can get ahold of. Only doing it occasionally means there is a reasonable chance that sufficient changes have happend to the system since the sample worthwhile in terms of entropy gained, and doing a large block of it all at once prevents iterative guessing attacks if an attacker can control your HWRNG outputs but not your system statistics. Encrypting the output using keys generated by the PRNG is a good idea, but you presented it in a somewhat confusing way, in that it sounded almost like you were doing message transfer. Then I realized you're not actually doing that at all, just a postprocessing (or preprocessing, in the case of the recipient) operation using a randomly keyed block cipher (which the X9.31 RNG would also provide nicely). At not point do the two sides actually exchange messages, so in this situation, your mention of key distribution is somewhat misleading. If you want to try to keep the entropy values sent from the box with the HWRNG to the client a secret from people on the network, just open up a TLS session. TLS is cheap if you use session resumption, and with self-signed certificates or anonymous DH there is no key distribution. It makes bootstrapping a little more difficult, but presumably the client can get at least some entropy via the traditional means currently available on common platforms. You could also just solve the problem you mention directly, and try to find a cheaper HWRNG design. I know people who have built them for a few dollars worth of stuff at Radio Shack, and apparently VIA, Intel, and AMD have all found them cheap enough at various times to ship them included in components they've built at little or no extra cost. You can buy a PCI board with a low-end Hifn crypto chip on it for less than $80 online. -Jack - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
