Re: linux-ipsec: Re: Summary re: /dev/random
> "Osma" == Osma Ahvenlampi <[EMAIL PROTECTED]> writes: Osma> Arnold G. Reinhold <[EMAIL PROTECTED]> writes: >> 1. Mr. Kelsey's argument that entropy should only be added in >> large quanta is compelling, but I wonder if it goes far enough. I >> would argue that entropy collected from different sources (disk, >> network, sound card, user input, etc.) should be collected in >> separate pools, with each pool taped only when enough entropy has >> been collected in that pool. Osma> You have to realize that /dev/random entropy collection doesn't Osma> get one bit, add it to the pool, and increment the entropy Osma> counter Osma> So, for each 40 bits mixed into the pool, a few bits of entropy Osma> is credited. How do you propose quantizing this? I think this is pretty simple. Right now there's one pool, which is where new stuff is stirred in and then a hash is done over it (that's the outline, the details are a bit more involved). The most straightforward way to do what's proposed seems to be like this: 1. Make two pools, one for /dev/random, one for /dev/urandom. The former needs an entropy counter, the latter doesn't need it. 2. Create a third pool, which doesn't ned to be big. That's the entropy staging area. It too has an entropy counter. 3. Have the add entropy function stir into that third pool, and credit its entropy counter. 4. Whenever the entropy counter of the staging pool exceeds N bits (a good value for N is probably the hash length), draw N bits from it, and debit its entropy counter by N. If the entropy counter of the /dev/random pool is below K% of its upper bound (K = 75 has been suggested) stir these N bits into the /dev/random pool. Otherwise, alternate between the two pools. Credit the pool's entropy counter by N. The above retains the basic structure, its mixing algorithms, entropy bookkeeping, etc. The major delta is the multiple pools and the carrying of entropy from the staging pool to the others. paul
Re: linux-ipsec: Re: Summary re: /dev/random
> "Arnold" == Arnold G Reinhold <[EMAIL PROTECTED]> writes:
Arnold> I have found this discussion very stimulating and
Arnold> enlightening. I'd like to make a couple of comments:
Arnold> 1. Mr. Kelsey's argument that entropy should only be added in
Arnold> large quanta is compelling, but I wonder if it goes far
Arnold> enough. I would argue that entropy collected from different
Arnold> sources (disk, network, sound card, user input, etc.) should
Arnold> be collected in separate pools, with each pool taped only
Arnold> when enough entropy has been collected in that pool.
Arnold> Mixing sources gives an attacker added opportunities. For
Arnold> example, say entropy is being mixed from disk accesses and
Arnold> from network activity. An attacker could flood his target
Arnold> with network packets he controlled, insuring that there would
Arnold> be few disk entropy deposits in any given quanta release. On
Arnold> the other hand, if the entropy were collected separately,
Arnold> disk activity entropy would completely rekey the PRNG
Arnold> whenever enough accumulated, regardless of network
Arnold> manipulation. Similarly, in a system with a hardware entropy
Arnold> source, adding disk entropy in a mixing mode would serve
Arnold> little purpose, but if the pools were kept separate, disk
Arnold> entropy would be a valuable backup in case the hardware
Arnold> source failed or were compromised.
I think this makes sense only if the "entropy source" under
consideration isn't actually any good. If if is reasonably sound (and
in particular, its entropy amount estimated conservatively) then there
isn't a problem. For example, if an attacker floods with network
messages, and you use network timing as an entropy source, the design
job was to pick a conservative lower bound of entropy per arrival
given that the arrivals may all be controlled by an attacker. If
you've done that, then the attack doesn't hurt.
Arnold> 2. It seems clear that the best solution combines strong
Arnold> crypto primitives with entropy collection. I wonder how much
Arnold> of the resistance expressed in this thread by has to do with
Arnold> concerns about performance. For this reason, I think RC4
Arnold> deserves further consideration. It is very fast and has a
Arnold> natural entropy pool built in. With some care, I believe RC4
Arnold> can be used in such a way that attacks on the PRNG can be
Arnold> equated to an attacks on RC4 as a cipher. The cryproanalytic
Arnold> significance of RC4's imperfect whiteness is questionable and
Arnold> can be addressed in a number of ways, if needed. I have some
Arnold> thoughts on a fairly simple and efficient multi-pool PRNG
Arnold> design based on RC4, if anyone is interested.
Well, yes, but /dev/{u,}random already does use strong crypto (a
strong cryptographic hash, to be precise). I expect RC4 could do the
job but is there any reason to replace what's there now (MD5 and
SHA-1) with RC4 or anything else?
Arnold> 3. With regard to diskless nodes, I suggest that the
Arnold> cryptographic community should push back by saying that some
Arnold> entropy source is a requirement and come up with a
Arnold> specification (minimum bit rate, maximum acceptable color,
Arnold> testability, open design, etc.). An entropy source spec would
Arnold> reward Intel for doing the right thing and encourage other
Arnold> processor manufacturers to follow their lead.
Obviously an entropy source is required, but I'm not prepared to
translate that into a requirement for dedicated hardware. I still
believe (based on experiments -- though not on PC hardware) that
network arrival timing done with low order bits from a CPU cycle
counter supply non-zero entropy.
Arnold> A hardware RNG can also be added at the board level. This
Arnold> takes careful engineering, but is not that expensive. The
Arnold> review of the Pentium III RNG on www.cryptography.com seems
Arnold> to imply that Intel is only claiming patent protection on its
Arnold> whitening circuit, which is superfluous, if not harmful. If
Arnold> so, their RNG design could be copied.
There are probably plenty of designs; at the block diagram level they
are pretty simple and pretty obvious. The devil is in the details.
By the way, various crypto accelerator chips now come with an RNG
built-in. Some may be subject to export control, which would make
them unuseable in a Linux contents, but perhaps not all of them.
paul
Re: linux-ipsec: Re: Summary re: /dev/random
> "Osma" == Osma Ahvenlampi <[EMAIL PROTECTED]> writes: Osma> Looking at this discussing going round and round, I'm very Osma> inclined to fetch the latest freeswan-snapshot, grep for Osma> /dev/random, and replace all reads with a routine that has it's Osma> own internal Yarrow-like SHA mixer that gets reseeded from Osma> /dev/random at semi-frequent intervals, and in the meantime Osma> returns random numbers from the current SHA value. That's how I Osma> believe /dev/random was intended to be used, anyway... No, that's how /dev/urandom was intended to be used. What you describe duplicates the functionality of /dev/urandom. Why do it? I agree with Ted that there may well be people that misuse /dev/random. If so, the obvious comment is RT*M. Perhaps the documentation may want to emphasize the intended use of /dev/random more strongly. (Come to think of it, it's not clear to me especially after reading the Yarrow paper that there really *are* cases where the use of /dev/random rather than /dev/urandom is actually warranted.) Re Henry Spencer's comment: >On Tue, 3 Aug 1999, bram wrote: >> The goal is to make it so that any time someone wants random numbers they >> can go to /dev/random, with no required studying of entropy and threat >> models and all that yadda yadda yadda which most developers will >> rightfully recoil from getting into when all they want is a few random >> bytes. > That, surely, is what /dev/urandom is for. (Maybe /dev/random ought to > be mode rw---, so that only root applications can use it?) That may reduce the number of applications that blindly use /dev/random without knowing why this isn't the right thing to do. On the other hand, it won't prevent applications that read /dev/urandom from causing those that use /dev/random to block (so long as both continue to use the same pool. Then again, if the valid uses of /dev/random are somewhere between rare and non-existent, which seems to be the case, this is a non-issue. Finally, from Bram: > 5) a (very small) amount of persistent memory to keep pool state in (or at > least periodically put some random bytes in to put in the pool at next > reboot.) It would have to be plugged into a trusted piece of hardware to > give it real randomness at least once, of course, but that wouldn't be a > big deal. That doesn't solve the issue of entropy sources on diskless UI-less systems. All it does is let you carry whatever you got across reboots. If you have none to carry, you still have an issue. I do agree that using any available NV memory for keeping pool state across reboots is a good thing. paul
Re: linux-ipsec: Re: Summary re: /dev/random
>>>>> "Paul" == Paul Koning <[EMAIL PROTECTED]> writes: Paul> 2. Pool size. /dev/random has a fairly small pool normally but Paul> can be made to use a bigger one. Yarrow argues that it makes Paul> no sense to use a pool larger than N bits if an N bit mixing Paul> function is used, so it uses a 160 bit pool given that it uses Paul> SHA-1. I can see that this argument makes sense. (That Paul> suggests that the notion of increasing the /dev/random pool Paul> size is not really useful.) Correction... I reread the Yarrow paper, and it seems I misquoted it. Yarrow uses the SHA-1 context (5 word hash accumulator) as its "pool" so it certainly has a 160 bit entropy limit. But /dev/random uses a much larger pool, which is in effect the input to a SHA-1 or MD5 hash, the output of which is (a) fed back into the pool to change its state, and (b) after some further munging becomes the output bitstream. In that case, the possible entropy should be as high as the bit count of the pool, not the length of the hash, so cancel my comment #2... paul
Re: linux-ipsec: /dev/random
>>>>> "John" == John Denker <[EMAIL PROTECTED]> writes: John> At 01:50 PM 8/2/99 -0400, Paul Koning wrote: >> I only remember a few proposals (2 or 3?) and they didn't seem to >> be [unduly weak]. Or do you feel that what I've proposed is this >> weak? If so, why? I've seen comments that say "be careful" but I >> don't remember any comments suggesting that what I proposed is >> completely bogus... >> >> We can waste lots of cycles having cosmic discussions, but that's >> not helping matters. What we need is a minimum of ONE decent >> quality additional entropy source, one that works for diskless >> IPSEC boxes. John> OK, I see four proposals on the table. (If I've missed John> something, please accept my apologies and send a reminder.) John> ...2) Network timing John> Discussion: John> ... John> 2) Network timing may be subject to observation and possibly John> manipulation by the attacker. My real-time clocks are pretty John> coarse (10ms resolution). But that's not what I proposed. I said "CPU cycle counter". Pentiums and up have those (and for all I know maybe older machines too, I'm no x86 wizard). If the best you have is a 10 ms clock then this proposal does NOT apply -- for the reason you stated. paul
Re: linux-ipsec: /dev/random
> "John" == John Denker <[EMAIL PROTECTED]> writes: >> Sure, you can do cat /dev/zero | md5sum > /dev/random, but I don't >> believe anyone is proposing that as a way of feeding entropy into >> it. John> That's where we might slightly disagree :-) ... I've seen some John> pretty questionable proposals ... but that's not the point. I only remember a few proposals (2 or 3?) and they didn't seem to be anything like that. Or do you feel that what I've proposed is this weak? If so, why? I've seen comments that say "be careful" but I don't remember any comments suggesting that what I proposed is completely bogus... John> The point is that there are a lot of customers out there who John> aren't ready to run out and acquire the well-designed hardware John> TRNG that you alluded to. So we need to think carefully about John> the gray area between the strong-but-really-expensive solution John> and the cheap-but-really-lame proposals. The gray area is big John> and important. Actually, the size of the gray area isn't really interesting. We can waste lots of cycles having cosmic discussions, but that's not helping matters. What we need is a minimum of ONE decent quality additional entropy source, one that works for diskless IPSEC boxes. So rather than talk about the size of the gray area, could we talk about the merits and problems of the very few concrete proposals that have been made? paul
Re: linux-ipsec: /dev/random
>>>>> "John" == John Denker <[EMAIL PROTECTED]> writes: John> At 10:09 AM 8/2/99 -0400, Paul Koning wrote: >> 1. Estimating entropy. Yes, that's the hard one. It's >> orthogonal from everything else. /dev/random has a fairly simple >> approach; Yarrow is more complex. >> >> It's not clear which is better. If there's reason to worry about >> the one in /dev/random, a good solution would be to include the >> one from Yarrow and use the smaller of the two answers. John> Hard? That's much worse than hard. In general, it's John> impossible in principle to look at a bit stream and determine John> any lower bound on its entropy. Consider the bitstream John> produced by a light encoding of /dev/zero. If person "A" knows John> the encoding, the conditional entropy is zero. If person "B" John> hasn't yet guessed the encoding, the conditional entropy is John> large. John> Similar remarks apply to physical entropy: I can prepare a John> physical system where almost any observer would measure lots of John> entropy, whereas someone who knew how the system was prepared John> could easily return it to a state with 10**23 bits less John> apparent entropy. Example: spin echoes. Fine, but we weren't talking about "in principle" or "in general". Sure, given an unspecified process of unknown (to me) properties I cannot make sensible statements about its entropy. That is true but it isn't relevant to the discussion. Instead, we're talking about systems where we have some understanding of the properties involved. For example, to pick a physical process, suppose I had a noise generator (resistor), shielding of known properties or at least bounded effectiveness, biases ditto, I would say I can then come up with a reasonable entropy estimate, especially if I'm quite conservative. This is what people typically do if they build "hardware random number generators". They certainly need to be treated with care and analyzed cautiously, but it definitely is a thing that can be done. Sure, you can do cat /dev/zero | md5sum > /dev/random, but I don't believe anyone is proposing that as a way of feeding entropy into it. paul
Re: linux-ipsec: Re: Summary re: /dev/random
I get the feeling from the discussion on /dev/random vs. alternatives (in particular, Yarrow) that not all the commenters have looked at the code for /dev/random. Let's see... 1. Estimating entropy. Yes, that's the hard one. It's orthogonal from everything else. /dev/random has a fairly simple approach; Yarrow is more complex. It's not clear which is better. If there's reason to worry about the one in /dev/random, a good solution would be to include the one from Yarrow and use the smaller of the two answers. 2. Pool size. /dev/random has a fairly small pool normally but can be made to use a bigger one. Yarrow argues that it makes no sense to use a pool larger than N bits if an N bit mixing function is used, so it uses a 160 bit pool given that it uses SHA-1. I can see that this argument makes sense. (That suggests that the notion of increasing the /dev/random pool size is not really useful.) 3. /dev/random blocks after delivering as many bits of output as its current entropy estimate. Right. But /dev/urandom does not, and neither does Yarrow. In other words, Yarrow is like /dev/urandom in that respect; if people feel Yarrow is an example of a good generator, they can't very well use the blocking behavior of /dev/random as additional ammo! Conversely, if you believe some applications really require that blocking behavior, it follows you would not want to use Yarrow in its current form. Incidentally, if you adopt Scheier's comment that the entropy pool size should be bounded by the hash value length, the blocking behavior of /dev/random doesn't make much sense anymore. Also, Scheier argues that a conservative upper bound on how many bits to extract before reseeding is 2^(n/3), i.e., 2^53 bits in the SHA-1 case... although he doesn't prevent you from using smaller numbers. 4. Questions/concerns about the cryptographic primitives used. This is where I wonder what people have looked at... Yarrow uses SHA-1 as a mixing function. /dev/random uses either SHA-1 or MD5 as a mixing function. What's the issue again? Note also that /dev/random doesn't give you the current hash state as its output; instead it "folds" it (high half xor low half) on the ultra-conservative principle that knowing a particular 160-bit SHA-1 output value might maybe give you some insight in what subsequent iterations of SHA-1 would produce. I don't believe that's currently thought to be the case, but even if it were, /dev/random doesn't suffer from it. I don't remember what Yarrow does in this area. 5. "Catastrophic reseeding" to recover from state compromise. It's been argued that this is a rather extravagant concern. I agree to a point... if someone can read kernel memory, you probably have other more immediate concerns. On the other hand, it's a really good idea to have the property that compromise at time T doesn't give the attacker a way in for time > T+n for suitable (reasonably small) n. Also, note that the state compromise is a passive attack, it may go unnoticed more readily than, say, a trojan horse patch to the kernel. So while this attack is a bit of a stretch, defending against it is really easy. It's worth doing. 6. Inadequate entropy sources for certain classes of box. This is common to both. On diskless UI-less boxes, neither Yarrow nor /dev/random currently have any entropy inputs. We've discussed this before; I've recommended adding fine grained (CPU clock cycle few low order bits) network packet timing as a source. There's been some scepticism expressed, rightly so; I've done comparable things in the past and feel comfortable that this one will work out, but I would definitely expect others to want to do their own analysis. Having a Yarrow-style entropy analyzer might help here. In summary: I think (6) is the biggest issue. Items (1) and (5) suggests pieces that could be adopted from Yarrow and put into /dev/random. I see no valid argument that there is anything major wrong with the current generator, nor that replacing it with Yarrow would be a good thing at all. In particular, I disagree with Sandy's comment that "Yarrow's two-stage design... offers significant advantages over the one-stage design in /dev/random". Apart from the long shot (iterative guessing attack) and possibly some nuances relating to entropy estimates, I don't see any significant difference in strength between the two. paul
Re: linux-ipsec: Re: TRNG, PRNG
I really wonder why people are so eager to "completely get rid of the old /dev/random and /dev/urandom code" when 1. the only defects that have been identified so far require only minor tweaks to that code, 2. the code has been around for some time and there's some reason to believe it's pretty solid, 3. apart from the issues under (1), the proposed replacement (yarrow) uses essentially the same design principles, 4. the proposed replacement either requires vast amounts of work to fit into Linux (yarrow) or is something else that hasn't been defined at all yet. In other words, why propose doing large hunks of work to fix small issues? Of course, if you want to do X and don't mind that you defined X to be large, that's your choice. But if you're trying to encourage someone else to do X, it's best to make X as small as is possible while still getting the job done. Am I missing something here? If so, what is it? paul
