Re: randomdev entropy gathering is really weak
On Sun, Jul 30, 2000 at 01:25:18AM -0400, Jeroen C. van Gelderen wrote: Hmm, maybe the complainers should provide proof that they do need more than 2^256 complexity. Makes it easier for us, proponents ;-/ How about creating one-time pads? That said, in Applied Cryptography, Schneier makes the comment (end of section 7.1) that, based on thermodynamic limitations, "brute force attacks against 256-bit keys will be infeasible until computers are build from something other than matter and occupy something other than space". (Though it's possible that a quantum computer would meet those criteria - since it doesn't need to iterate through all possible keys, it can bypass that part of the second law of thermodynamics). This implies that if brute force is the best attack against Yarrow-256 (Blowfish), it is unbreakable. (Of course, that's a big if). Peter To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 30 Jul 2000, Mark Murray wrote: This is a reversion to the count-entropy-and-block model which I have been fiercely resisting (and which argument I thought I had sucessfully defended). Actually, I was waiting for your reply to Jeroen's question about changing the semantics of the random devices. Oops; I thought I got that one. ISTR something about looking for different algorithms that may do it, and you pointed me at 2 sites; one had no write-up, and I'm looking at the other. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Content-Disposition: attachment; filename="yarrow_blocking.patch" Brian: I want to take a different approach to this one. Do not commit anything to the /dev/random device, please, without running it by me. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 30 Jul 2000, Mark Murray wrote: Content-Disposition: attachment; filename="yarrow_blocking.patch" Brian: I want to take a different approach to this one. Do not commit anything to the /dev/random device, please, without running it by me. I was not planning on it. You really should take a look at the bugfixes, though; reading buffer sizes of 8 bytes but not-8-byte-multiple should do it. There's also the ioctl handler which you need stubs for and then checking for open devices when you attempt to unload the module. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 30 Jul 2000, Mark Murray wrote: This is a reversion to the count-entropy-and-block model which I have been fiercely resisting (and which argument I thought I had sucessfully defended). My solution is to get the entropy gathering at a high enough rate that this is not necessary. How does entropy gathering at a high enough rate solve this particularly? Unless you wait for reseeds while reading, it simply doesn't matter how much entropy is being gathered at the time since reading any amount just doesn't give you a new key. Indeed, if you can get enough entropy that the blocking in read would be very short, you would still need to block in read to give it time to use the entropy. The only alternative I can see that you might be thinking of would be that the user would be encouraged to only read a small amount at a time and reading more soon later in the assumption that Yarrow will be rekeyed. Then this would be just forcing the user to do the blocking manually, and non-deterministically. So how exactly _would_ just having a high entropy gathering rate help the case that you need a large amount of data from /dev/random with true entropic value, not only 256 bits worth? It's not like reseeds would be occurring while reads were in progress; reads are too fast for that and are splsofttq() protected, anyway. I also agreed to _maybe_ look at a re-engineer of the "old" code in a secure way if a decent algorithm could be found (I am reading some papers about this ATM). M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Do not commit anything to the /dev/random device, please, without running it by me. I was not planning on it. You really should take a look at the bugfixes, though; reading buffer sizes of 8 bytes but not-8-byte-multiple should do it. There's also the ioctl handler which you need stubs for and then checking for open devices when you attempt to unload the module. Will do, thanks! M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
How does entropy gathering at a high enough rate solve this particularly? EG, by having it such that Yarrow state perturbations happen often enough that each read is "guaranteed" to be associated with at least one and preferably more. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 30 Jul 2000, Mark Murray wrote: How does entropy gathering at a high enough rate solve this particularly? EG, by having it such that Yarrow state perturbations happen often enough that each read is "guaranteed" to be associated with at least one and preferably more. Can you give me an idea how this would work, at least with e.g. pseudocode annotation of the current code? I'm curious what you're going to change that will allow reseeeding while a read is in progress. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
EG, by having it such that Yarrow state perturbations happen often enough that each read is "guaranteed" to be associated with at least one and preferably more. Can you give me an idea how this would work, at least with e.g. pseudocode annotation of the current code? I'm curious what you're going to change that will allow reseeeding while a read is in progress. I didn't say "reseed", I said "perturb". Same code, (improved reseed control), more harvesting calls. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 30 Jul 2000, Mark Murray wrote: This is a reversion to the count-entropy-and-block model which I have been fiercely resisting (and which argument I thought I had sucessfully defended). Actually, I was waiting for your reply to Jeroen's question about changing the semantics of the random devices. I still maintain that as OS developers we can't predict the uses of this tool and that some users may require new entropy in every 256-bit output. I don't think that "near enough is good enough" is a valid excuse :-) Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote: What I meant with that point is that the user may get, say an extra few hundred bits out of it with no new entropy before the scheduled reseed task kicks in. How does he know which bits are which? His analysis task just got a whole lot more difficult. Again, not entirely correct but not relevant either... Kris is simply right in that the /dev/random semantics change and that more bits can be output by Yarrow than there is entropy gathered. *In theory* the complexity of an attack on our Yarrow has an upper bound of 2^256 and *in theory* this is less than the complexity of an attack on our current /dev/random. This is a hard fact, no way around that. Even if the attack on a single non-blocking read from Yarrow is only of 2^256 complexity, it is designed to be much more expensive than just cracking a single block cipher. Blowfish has a very large keying step, and Yarrow is designed to exploit having large keying steps and then adding more complexity in its setup in addition. This makes it infeasible to mount attacks on Yarrow, and the security is really not as weak as just cracking 20-round Blowfish-256. However, none of this makes Yarrow useless for getting many bits of high-quality random data for, e.g., generation of an RSA key. However, the big question here is not about theory but about *practicality*. Is Yarrow less secure than /dev/random in practice? How does our /dev/random hold up under attack? How does Yarrow compare? I think we need to evaluate these practical questions instead of deep theoretical issues as Yarrow is all about practicality. At a more fundamental level we will need to answer the question: "Do we need to preserve the current /dev/random semantics or can we decide to change 'em? [1]". And how will this affect our applications *in practice*. Mark already stated that in *practicality*, Yarrow-BF-cbc-256 1.0 (I guess that's the proper name for this :-) is complex enough and generates good enough ouput. If you /really/ want to make the attack on it much harder, how about this: if you're going to read 1024 bits of entropy from Yarrow on /dev/random, you will request it all at once and block just as the old random(4) used to block; the blocking can occur at 256 bit intervals and sleep until there is a reseed. Waiting to reseed for each read will ensure a much larger amount of "real" entropy than it "maybe" happening at random times. Can you really find anything wrong with doing what I propose *in practice*? I'm certain that it would make it about as hard to brute-force the key while knowing certain parameters of its generation as it would be to just factor the damned 1024-bit number. I've already implemented this as well as some other bugfixes, so see the attached diff. So let's concentrate this discussion on the practical issues and explain why you think backing /dev/random with Yarrow and changing the semantics is justifyable or even a good thing. Cheers, Jeroen [1] And, should we decide not to change /dev/random semantics, can we still back /dev/random with a modified Yarrow? I think it makes sense :) -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ -- Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! / [EMAIL PROTECTED]`--' Index: sys/sys/random.h === RCS file: /usr2/ncvs/src/sys/sys/random.h,v retrieving revision 1.25 diff -u -r1.25 random.h --- sys/sys/random.h2000/07/25 21:18:45 1.25 +++ sys/sys/random.h2000/07/29 23:19:20 @@ -36,6 +36,8 @@ enum esource { RANDOM_WRITE, RANDOM_KEYBOARD, RANDOM_MOUSE, RANDOM_NET, \ ENTROPYSOURCE }; void random_harvest(void *, u_int, u_int, u_int, enum esource); +void set_wakeup(int *, int); +void set_wakeup_exit(int *, int, int); #endif Index: sys/dev/randomdev/harvest.c === RCS file: /usr2/ncvs/src/sys/dev/randomdev/harvest.c,v retrieving revision 1.4 diff -u -r1.4 harvest.c --- sys/dev/randomdev/harvest.c 2000/07/25 21:18:46 1.4 +++ sys/dev/randomdev/harvest.c 2000/07/29 23:18:50 @@ -30,6 +30,7 @@ #include sys/systm.h #include sys/types.h #include sys/queue.h +#include sys/kthread.h #include sys/linker.h #include sys/libkern.h #include sys/mbuf.h @@ -72,4 +73,23 @@ nanotime(timebuf); (*reap)(timebuf, entropy, count, bits, frac, origin); } +} + +/* + * Helper routines to let kthread_exit() do its stuff properly (i.e. no crash). + */ +void +set_wakeup(int *var, int value) +{ + + *var = value; +
Re: randomdev entropy gathering is really weak
Brian Fundakowski Feldman wrote: On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote: What I meant with that point is that the user may get, say an extra few hundred bits out of it with no new entropy before the scheduled reseed task kicks in. How does he know which bits are which? His analysis task just got a whole lot more difficult. Again, not entirely correct but not relevant either... Kris is simply right in that the /dev/random semantics change and that more bits can be output by Yarrow than there is entropy gathered. *In theory* the complexity of an attack on our Yarrow has an upper bound of 2^256 and *in theory* this is less than the complexity of an attack on our current /dev/random. This is a hard fact, no way around that. Even if the attack on a single non-blocking read from Yarrow is only of 2^256 complexity, it is designed to be much more expensive than just cracking a single block cipher. Blowfish has a very large keying step, and Yarrow is designed to exploit having large keying steps and then adding more complexity in its setup in addition. This makes it infeasible to mount attacks on Yarrow, and the security is really not as weak as just cracking 20-round Blowfish-256. Actually, it is. The low key agility doesn't add anything in terms of practical security because it only affects brute force attacks and can be optimized out in a pipelined implementation. Expensive, yes, but can be done. There is some more details on this in the Yarrow paper I think... Anyway, not that is matters, Yarrow was designed to be as secure as the underlying blockcipher and Blowfish is generally considered to be reasonably secure. So, the security still is 2^256 maximum, no way around that. However, none of this makes Yarrow useless for getting many bits of high-quality random data for, e.g., generation of an RSA key. Well, you will need to back that up with arguments if you want to convince the more sceptical (not me). A mere statement will not do it, you need proof or at least arguments :-) The question that Kris posed basically boiled down to: "Does 2^256 complexity equal 2^x (x 256) complexity in practice?" . I can't think of a practical system where it wouldn't be sufficient in practice but that's just me. Well, you seem to agree and MarkM seems to too. Hmm, maybe the complainers should provide proof that they do need more than 2^256 complexity. Makes it easier for us, proponents ;-/ Also, since a 1024 RSA-key only has ~2^77 complexity it isn't a very good example. A more interesting question is, what if you generate a couple of 256-bit symmetric keys in a row. Their total complexity is 2^256 which is less than they could have. Does that matter in practice? Mark already stated that in *practicality*, Yarrow-BF-cbc-256 1.0 (I guess that's the proper name for this :-) According to Bruce S. one would call it Yarrow-256 (implementation details go here) You would definately spell out Blowfish completely. Btw, how exactly is the hash actually constructed in our Yarrow? I wonder how one constructs a 256-bit hash out of Blowfish with a 64-bit block size. A quick explanation would be appreciated. is complex enough and generates good enough ouput. If you /really/ want to make the attack on it much harder, how about this: if you're going to read 1024 bits of entropy from Yarrow on /dev/random, you will request it all at once and block just as the old random(4) used to block; the blocking can occur at 256 bit intervals and sleep until there is a reseed. Waiting to reseed for each read will ensure a much larger amount of "real" entropy than it "maybe" happening at random times. Sounds like a good idea. It looks like it would be reasonably easy to then add an extra entropy counter to the pool from which you subtract the number of bits that are output and to which you add the number of entropy bits that are mixed in. You can then extract bytes until that counter hits 0 and then block until it goes positive again which would ensure that the entropy output trough /dev/random is not re-used for output trough /dev/urandom. This would not affect the security of Yarrow at all but preserve the semantics of /dev/random almost completely. Can you really find anything wrong with doing what I propose *in practice*? No. Although I think you can make it nearly perfect by incorporating the above suggestion. You would then *never* return more bits than you have gathered entropy and you would never use those entropy bits twice. I've already implemented this as well as some other bugfixes, so see the attached diff. Cool. [1] And, should we decide not to change /dev/random semantics, can we still back /dev/random with a modified Yarrow? I think it makes sense :) Me too, especially with your changes (or modification thereof) to preserve current /dev/random semantics. Cheers, Jeroen -- Jeroen C. van Gelderen
Re: randomdev entropy gathering is really weak
How does OpenBSD handle this issue? Anyone know? -- Ben 220 go.ahead.make.my.day ESMTP Postfix To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Wed, 26 Jul 2000, void wrote: How does OpenBSD handle this issue? Anyone know? It looks like they have four different kernel-exported random-number generators: #define RND_RND 0 /* real randomness like nuclear chips */ #define RND_SRND1 /* strong random source */ #define RND_URND2 /* less strong random source */ #define RND_PRND3 /* pseudo random source */ #define RND_ARND4 /* aRC4 based random number generator */ RND_RND is not implemented. /dev/random (RND_SRND) and /dev/urandom (RND_URND) are very similar to our old system (based on the same code, in fact, and also used in Linux) although OpenBSD use more entropy sources than us. /dev/prandom (RND_PRND): This just returns the output of random() (Why bother?) /dev/arandom (RND_ARND): This uses the arc4 stream cipher to output a stream of bytes based on an internal key, which is periodically (but I don't know how often) reseeded using entropy samples. Much like arc4random(), except it's periodically reseeded (which arc4random() doesn't do, by default). All of these systems have weaknesses (some serious), even if entropy is estimated accurately (there were indications it was not, for our old PRNG). That was the main motivation for moving to a cryptographically well-designed system (Yarrow). Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
http://www.counterpane.com/pseudorandom_number.html Cryptlib is described here: http://www.cs.auckland.ac.nz/~pgut001/cryptlib/ Thanks! Asynchonous reseeding _improves_ the situation; the attacker cannot force it to any degree of accuracy, and if he has the odds stacked heavily against him that each 256-bits of output will have an associated reseed, it makes his job pretty damn difficult. What I meant with that point is that the user may get, say an extra few hundred bits out of it with no new entropy before the scheduled reseed task kicks in. How does he know which bits are which? His analysis task just got a whole lot more difficult. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, Jul 23, 2000 at 03:06:34PM +0200, Poul-Henning Kamp wrote: In message [EMAIL PROTECTED], Stefan `Sec` Zehl writes: With the current approach it has a 256bits key. This is, in my eyes, not good. Although yarrow is nice, It's suited for any kind of key generation. The first law of crypto clearly states: "Know what you're doing". There is no way around that law. We cannot load down FreeBSD with impossibly heavy computations to cater for any and all conceiveable application of random numbers. But FreeBSD should provide a way to get truely random numbers when it asks for them. /dev/random was invented so the applications don't have to bother with entropy-gathering. I agree that yarrow is good, but we need some way to get really random numbers. Maybe call it /dev/rrandom. The way Kris describes it, it won't really use cpu time until it is read. CU, Sec -- I even remember having a private exchange of messages with you about other possible approaches to that problem. :-) Hopefully, these approaches involved slowly crushing of tender body parts. -- Liviu Wietse about broken Mailers ~ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Mon, 24 Jul 2000, Jeroen C. van Gelderen wrote: 1. The overhead will probably be insignificant. One doesn't use such vast amounts of random numbers. True, but the effect on slow CPUs for a single read may be signfificant. We'll have to see. 2. At least the generator gate can be optimized out if it turns out to be a problem. Yes. 3. We could use a cipher with better key agility (CAST) to make each operation less computationally intensive. Yes. ITYM Pg = k 2^(-k/3) though - you want a maximum k bits of output, not 1. Pg is the number of blocks IIRC. Pg is the number of (n=64)-bit blocks between generator gates, but min(2^n,2^(k/3)Pg) is the maximum number of output bits you'll get before the thing shuts up and waits for a reseed. So Pg 1 means we'll take a generator gate after every output block, but will still output our 2^(k/3)Pg = k bits (i.e. 4 blocks worth) In practice we'd probably have to just special-case this since the required Pg is approximately 10^-24 :-) Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Mark Murray wrote: [...] Asynchonous reseeding _improves_ the situation; the attacker cannot force it to any degree of accuracy, and if he has the odds stacked heavily against him that each 256-bits of output will have an associated reseed, it makes his job pretty damn difficult. This is not correct for a variety of reasons. But that's all fairly theoretical and ... not relevant for the discussion at hand. What I meant with that point is that the user may get, say an extra few hundred bits out of it with no new entropy before the scheduled reseed task kicks in. How does he know which bits are which? His analysis task just got a whole lot more difficult. Again, not entirely correct but not relevant either... Kris is simply right in that the /dev/random semantics change and that more bits can be output by Yarrow than there is entropy gathered. *In theory* the complexity of an attack on our Yarrow has an upper bound of 2^256 and *in theory* this is less than the complexity of an attack on our current /dev/random. This is a hard fact, no way around that. However, the big question here is not about theory but about *practicality*. Is Yarrow less secure than /dev/random in practice? How does our /dev/random hold up under attack? How does Yarrow compare? I think we need to evaluate these practical questions instead of deep theoretical issues as Yarrow is all about practicality. At a more fundamental level we will need to answer the question: "Do we need to preserve the current /dev/random semantics or can we decide to change 'em? [1]". And how will this affect our applications *in practice*. So let's concentrate this discussion on the practical issues and explain why you think backing /dev/random with Yarrow and changing the semantics is justifyable or even a good thing. Cheers, Jeroen [1] And, should we decide not to change /dev/random semantics, can we still back /dev/random with a modified Yarrow? -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
RE: randomdev entropy gathering is really weak
/dev/random should block if the system does not contain as much real entropy as the reader desires. Otherwise, the PRNG implementation will be the weakest link for people who have deliberately selected higher levels of protection from cryptographic attack. I don't want to rehash this thread from the beginning. Please go back, read the Yarrow paper, and recognise that Yarrow is not an entropy-counter, it is a cryptographically secure PRNG. The "count random bits and block" model does not apply. Then the current implementation cannot provide the usual semantics for /dev/random, while it can provide the semantics for /dev/urandom. As I understand it, /dev/random is supposed to provide true randomness suitable for generating keys of unlimited length, whereas /dev/urandom is supposed to provide cryptographically-strong randomness for general applications. If people want /dev/random to seed 1024-bit keys, /dev/random must be stronger than a 1024-bit key. DS To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Mark Murray wrote: So what it if I want/need 257 bits? :-) Read them. You'll get them. If you want higher quality randomness than Yarrow gives, read more than once. Do other stuff; play. Don't get stuck in the "I have exhausted the randomness pool" loop; Yarrow does not play that game. I think you're missing the point. The only way I can get a random number with more than n bits of entropy out of Yarrow-n is if I sample either side of a reseed operation, which in general comes down to timing guesswork and having to make assumptions about the PRNG implementation. I understand that. :-) Your are missing the point that it is not possible to get more than the ${number-of-bits-ofrandomness} from any accumulator or PRNG. You have to draw the line somewhere; The current implementation has it at 256. If you want to generate a cryptographic key of length n bits then you really want n bits of entropy in the random source you're deriving it from, otherwise your key is actually much weaker than advertised because it's easier for the attacker to attack the state of the PRNG that derived it than to attack the key itself. Aha! That is where Yarrow wins. The paper argues it much better than me: Section 4.1, the paragraph that begins "Yarrow takes a different approach...". We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could make it so. Well, if we did that then how about generating 2048-bit keys? :-) Where do you draw the line? I could make it Yarrow-N, only to have someone insist on $((N+1)) in the very next breath. With what we have, I am staking my career on the "uncrackability" of Blowfish-256. If that holds then Yarrow is safe. (The old one was MD5, with all its weaknesses such as birthday attacks, and blocking added to compensate for folk raping it for internal state; this blocking was compromised by the non-blocking /dev/urandom. The design was too simple. The current design has multiple accumulators, dual pools, and cryptographically overseen reseed mechanism; on top of that, the output is encrypted in its own right, so there is added protection against folk guessing the internal state.). M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
The core of my complaint is that even though our old PRNG did crappy entropy handling, we used to have such a method, which is now gone. I'd like to see yarrow hang off /dev/urandom and have /dev/random tap directly into the entropy pool (perhaps a third pool separate from Yarrow's fast/slow) so I can generate my large keys safely. By your own admission, the old system was bad; yet you still want ${it}? You'd like to see a programmer with less experience than Schneier come up with a more secure algorithm than him? M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
The core of my complaint is that even though our old PRNG did crappy entropy handling, we used to have such a method, which is now gone. I'd like to see yarrow hang off /dev/urandom and have /dev/random tap directly into the entropy pool (perhaps a third pool separate from Yarrow's fast/slow) so I can generate my large keys safely. By your own admission, the old system was bad; yet you still want ${it}? You'd like to see a programmer with less experience than Schneier come up with a more secure algorithm than him? M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Okay, using RSA keys wasn't the best example to pick, but Yarrow also seems easy to misuse in other cases: for example if you want to generate multiple 256-bit symmetric keys (or other random data) at the same time, each additional key after the first won't contain any additional entropy, so if you break the state of the PRNG at the time the first one was generated you get the others for free (until the thing reseeds). This design tradeoff is discussed in section 4.1 of the paper. Tweakable. That said, there is nothing to prevent the system admin from tweaking the Yarrow security parameters so that Yarrow will only spit out as many bits or pseudo-randomness as it gathers bits of entropy.[4] Well, I don't see a way to tune this without modifying the Yarrow design, since the entropy pool is intentionally decoupled from the output mechanism, and it seems like it would add additional (unnecessary) overhead anyway to use it in that fashion. Look at the sysctls (some improvements and documentation coming). Indications are we can probably get quite a lot of usable entropy from a standard system (on the order of many kilobytes per second - but I need to read more of the literature about processing of entropy samples) - in this case I think maintaining a third pool which is directly tapped by /dev/random, and leaving Yarrow sitting behind /dev/urandom is the way to go. I suspect you are missing the whole point of yarrow. Yarrow protects you from the compromises inherent in attackers injecting their own junk into the "third pool". M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Mark Murray wrote: Your are missing the point that it is not possible to get more than the ${number-of-bits-ofrandomness} from any accumulator or PRNG. You have to draw the line somewhere; The current implementation has it at 256. Uhh..a PRNG which hashes entropy samples with e.g. SHA1 and outputs the digest once the bucket is "full" will have 1-epsilon bit of entropy per 1 bit of output. It may not be very fast depending on the rate of entropy accumulation, but you can get as much entropy out of it as you want. This is basically the model I am advocating for /dev/random. It's also the alternative "basic design philosophy" described in the yarrow paper. If you want to generate a cryptographic key of length n bits then you really want n bits of entropy in the random source you're deriving it from, otherwise your key is actually much weaker than advertised because it's easier for the attacker to attack the state of the PRNG that derived it than to attack the key itself. Aha! That is where Yarrow wins. The paper argues it much better than me: Section 4.1, the paragraph that begins "Yarrow takes a different approach...". See "important issue" number 2 on p6. Yarrow-derived numbers are only "good for" 256 bits of strength. Modulo reseeds, Yarrow never accumulates more than 256 bits of entropy. Therefore you are silly to use it for applications which require more than 256 bits of randomness. Where do you draw the line? I could make it Yarrow-N, only to have someone insist on $((N+1)) in the very next breath. Precisely, which is why /dev/random shouldn't use Yarrow, or any other seeded-cipher PRNG. With what we have, I am staking my career on the "uncrackability" of Blowfish-256. If that holds then Yarrow is safe. (The old one I'm not bothered about this. My point is that, by design, Yarrow is not suitable as a replacement for /dev/random (/dev/urandom, yes). Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Mark Murray wrote: By your own admission, the old system was bad; yet you still want ${it}? You'd like to see a programmer with less experience than Schneier come up with a more secure algorithm than him? The old implementation was bad. The class of algorithm is not, as long as you are conservative about your entropy estimates. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Mark Murray wrote: Okay, using RSA keys wasn't the best example to pick, but Yarrow also seems easy to misuse in other cases: for example if you want to generate multiple 256-bit symmetric keys (or other random data) at the same time, each additional key after the first won't contain any additional entropy, so if you break the state of the PRNG at the time the first one was generated you get the others for free (until the thing reseeds). This design tradeoff is discussed in section 4.1 of the paper. Tweakable. Doing a reseed operation with every output is going to be *very* computationally expensive. That said, there is nothing to prevent the system admin from tweaking the Yarrow security parameters so that Yarrow will only spit out as many bits or pseudo-randomness as it gathers bits of entropy.[4] Well, I don't see a way to tune this without modifying the Yarrow design, since the entropy pool is intentionally decoupled from the output mechanism, and it seems like it would add additional (unnecessary) overhead anyway to use it in that fashion. Look at the sysctls (some improvements and documentation coming). Please tell me which of the following sysctls will cause Yarrow to deactivate the keyed cipher feature that spits out a constant data stream independent of the state of the entropy pools: kern.random.yarrow.gengateinterval: 10 kern.random.yarrow.bins: 10 kern.random.yarrow.fastthresh: 100 kern.random.yarrow.slowthresh: 160 kern.random.yarrow.slowoverthresh: 2 Indications are we can probably get quite a lot of usable entropy from a standard system (on the order of many kilobytes per second - but I need to read more of the literature about processing of entropy samples) - in this case I think maintaining a third pool which is directly tapped by /dev/random, and leaving Yarrow sitting behind /dev/urandom is the way to go. I suspect you are missing the whole point of yarrow. Yarrow protects you from the compromises inherent in attackers injecting their own junk into the "third pool". Mark, I understand this stuff quite well - I'm not "missing the whole point of Yarrow" at all. Yarrow is a good system as far as it goes, but the authors themselves admit this limitation - you just can't use this tool in contexts it was not designed for. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Kri s Kennaway writes: On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote: I agree that you need long RSA keys ... but the real discussion isn't really about key length but rather about the overall complexity of attacking the key: Okay, using RSA keys wasn't the best example to pick, but Yarrow also seems easy to misuse in other cases: for example if you want to generate multiple 256-bit symmetric keys (or other random data) at the same time, Kris, Obviously, if you need more randomness than a stock FreeBSD system can provide you with, you add hardware to give you more randomness. In other words, and more bluntly: Please shut up now, will you ? -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
This is basically the model I am advocating for /dev/random. It's also the alternative "basic design philosophy" described in the yarrow paper. Erm, read 4.1 again :-). The paragraph that begins "One approach..." is the old approach. It is also the approach that you are advocating. The next paragraph "Yarrow takes..." is Yarrow, and the current implementation. See "important issue" number 2 on p6. Yarrow-derived numbers are only "good for" 256 bits of strength. Modulo reseeds, Yarrow never accumulates more than 256 bits of entropy. Therefore you are silly to use it for applications which require more than 256 bits of randomness. Where do you draw the line? I could make it Yarrow-N, only to have someone insist on $((N+1)) in the very next breath. Precisely, which is why /dev/random shouldn't use Yarrow, or any other seeded-cipher PRNG. It should not use the old method, which is attackable for many reasons that Schneier makes clear. (Effectively a 128 bit hash with a reseed ("stir") every read. Can you spell "Iterative attack"? :-) ). Where does that leave us? How good were our old numbers? How many users have I screwed by implementing that system? How do we fix it? What accumulation algorithm do we use that does not clue the reader into what the internal state is? With what we have, I am staking my career on the "uncrackability" of Blowfish-256. If that holds then Yarrow is safe. (The old one I'm not bothered about this. My point is that, by design, Yarrow is not suitable as a replacement for /dev/random (/dev/urandom, yes). _My_ point is that the old system is broken, and that IMO Yarrow is a good replacement. (I support my point by noting that Schneier is a far better cryptographer than I, and he designed the algorithm that I implemented). M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Poul-Henning Kamp wrote: Obviously, if you need more randomness than a stock FreeBSD system can provide you with, you add hardware to give you more randomness. This won't help if it's fed through Yarrow. In other words, and more bluntly: Please shut up now, will you ? No. There are legitimate technical issues to be resolved here. If you don't want to participate, press 'D' and move on with your life. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Mark Murray wrote: Erm, read 4.1 again :-). The paragraph that begins "One approach..." is the old approach. It is also the approach that you are advocating. The next paragraph "Yarrow takes..." is Yarrow, and the current implementation. "The strength of the first approach is that, if properly designed, it is possible to get unconditional security from the PRNG." This is a good thing :-) It should not use the old method, which is attackable for many reasons that Schneier makes clear. (Effectively a 128 bit hash with a reseed ("stir") every read. Can you spell "Iterative attack"? :-) ). Where does that leave us? How good were our old numbers? How many users have I screwed by implementing that system? Please understand that this is not a personal attack - I appreciate your work, and welcome it in FreeBSD. My concern is with what Yarrow does not do, but which FreeBSD needs: a PRNG which is capable of generating arbitrarily large keys. How do we fix it? What accumulation algorithm do we use that does not clue the reader into what the internal state is? I suggest we ask Bruce Schneier instead of bantering back and forth about the issue. I claim (supported by the quote above) that it's possible to implement such a system securely and have it co-exist with Yarrow. _My_ point is that the old system is broken, and that IMO Yarrow is a good replacement. (I support my point by noting that Schneier is a far better cryptographer than I, and he designed the algorithm that I implemented). Yarrow is a good replacement for /dev/urandom. However it doesn't provide features which I believe are necessary, namely the ability to generate high-entropy keys of arbitrary size, without severely impacting on PRNG performance by constantly reseeding. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Kri s Kennaway writes: On Sun, 23 Jul 2000, Poul-Henning Kamp wrote: Obviously, if you need more randomness than a stock FreeBSD system can provide you with, you add hardware to give you more randomness. This won't help if it's fed through Yarrow. Nobody has said anything about forcing you to use Yarrow, have they ? In other words, and more bluntly: Please shut up now, will you ? No. There are legitimate technical issues to be resolved here. If you don't want to participate, press 'D' and move on with your life. I think the general concensus is that all legitimate technical issues has been resolved and that we are stuck with a small band of merry men wasting bandwidth by repeatedly rehashing the obvious: "Any source of random bits has a finite capacity and you should not exceed that capacity." I have not seen any new information in the last N emails from you. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Obviously, if you need more randomness than a stock FreeBSD system can provide you with, you add hardware to give you more randomness. This won't help if it's fed through Yarrow. *BTTT!* Wrong. A good hardware RNG when fed at a high-enough rate through Yarrow can easily produce a continuous stream of what you need. (If we take that route, the current implementation may need to be tweaked a bit to stop reseeding after a period of unuse to avoid hammering the kernel too much; this needs careful thought). Been thinking about this; the current implemnetation runs continuously (thanks to taskqueue(9)). There is no reason that it couldn't be made (somewhat) use-driven, so that it works harder at harvesting when being used heavily. This may make it slower, but it would hurt the kernel a bit less when not in use. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Poul-Henning Kamp wrote: Obviously, if you need more randomness than a stock FreeBSD system can provide you with, you add hardware to give you more randomness. This won't help if it's fed through Yarrow. *BTTT!* Wrong. A good hardware RNG when fed at a high-enough rate through Yarrow can easily produce a continuous stream of what you need. (If we take that route, the current implementation may need to be tweaked a bit to stop reseeding after a period of unuse to avoid hammering the kernel too much; this needs careful thought). M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
This design tradeoff is discussed in section 4.1 of the paper. Tweakable. Doing a reseed operation with every output is going to be *very* computationally expensive. Tradeoff. What do you want? Lightning fast? Excessive security? Balance it out. Well, I don't see a way to tune this without modifying the Yarrow design, since the entropy pool is intentionally decoupled from the output mechanism, and it seems like it would add additional (unnecessary) overhead anyway to use it in that fashion. Look at the sysctls (some improvements and documentation coming). Please tell me which of the following sysctls will cause Yarrow to deactivate the keyed cipher feature that spits out a constant data stream independent of the state of the entropy pools: kern.random.yarrow.gengateinterval: 10 kern.random.yarrow.bins: 10 kern.random.yarrow.fastthresh: 100 kern.random.yarrow.slowthresh: 160 kern.random.yarrow.slowoverthresh: 2 None, but very paranoid reseed intervals can be set if required. (Requires more entropy-harvesting, but doable). I suspect you are missing the whole point of yarrow. Yarrow protects you from the compromises inherent in attackers injecting their own junk into the "third pool". Mark, I understand this stuff quite well - I'm not "missing the whole point of Yarrow" at all. The acknowlegment that I am looking for is that the old, simple "gather entropy, stir with hash, serve" model is inadequate IMO, and I have not seen any alternatives. Yarrow is a good system as far as it goes, but the authors themselves admit this limitation - you just can't use this tool in contexts it was not designed for. Goes for any tool; a universal truth. I'm trying to come up with a better tool that what was, and I believe that I have, and I am perhaps misunderstanding folks' motives in shouting for the blocking model. In quite a few cases, it has been a very obvious non-understanding of what Yarrow is (I apologise for lumping you in this category). I'll relent somewhat if a secure entropy distilling algorithm could be found; one which stands up to crypanalysis. Will you relent a step or two if I can get the entropy harvesting _rate_ high enough? :-) M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Mark Murray wrote: This design tradeoff is discussed in section 4.1 of the paper. Tweakable. Doing a reseed operation with every output is going to be *very* computationally expensive. Tradeoff. What do you want? Lightning fast? Excessive security? Balance it out. Thinking about it further, I dont think Yarrow can even do this (introduce entropy into every output value) without bypassing the block cipher. And if you reseed with every 256 bits of output then you're vulnerable to an iterative guessing attack because the fast pool won't have much in it. So if we want to use the Yarrow "backend" we'd have to basically reduce it to the system I describe below. The acknowlegment that I am looking for is that the old, simple "gather entropy, stir with hash, serve" model is inadequate IMO, and I have not seen any alternatives. There are two other models which rate "pretty well-designed" in the Yarrow paper: the cryptlib and PGP PRNGs. I don't know what their properties are right now (the cryptlib one is described in the paper on PRNG cryptanalysis). I'll relent somewhat if a secure entropy distilling algorithm could be found; one which stands up to crypanalysis. Well, a simple scheme which doesn't seem to suffer from any of the vulnerabilities discussed in the schneier papers is to accumulate entropy in a pool, and only return output when the pool is full. i.e. the PRNG would either block or return 0 bytes of data, or a full pool's worth. Will you relent a step or two if I can get the entropy harvesting _rate_ high enough? :-) If we get the entropy pools filling fast enough that the reseed is triggering close to every 256 bits of output then it becomes much less of a concern (but it's still there, because reseeding happens asynchronously with respect to PRNG output). However I think that in practice this will be too heavy on the CPU (unless we weaken the reseed operation) and make dd if=/dev/urandom of=/dev/null a very effective local user DoS :-( Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
The acknowlegment that I am looking for is that the old, simple "gather entropy, stir with hash, serve" model is inadequate IMO, and I have not seen any alternatives. There are two other models which rate "pretty well-designed" in the Yarrow paper: the cryptlib and PGP PRNGs. I don't know what their properties are right now (the cryptlib one is described in the paper on PRNG cryptanalysis). Do you have copies of the articles concerned? I'd surely appreciate a photocopy of the relevant pages if you don't mind! :-) I'll relent somewhat if a secure entropy distilling algorithm could be found; one which stands up to crypanalysis. Well, a simple scheme which doesn't seem to suffer from any of the vulnerabilities discussed in the schneier papers is to accumulate entropy in a pool, and only return output when the pool is full. i.e. the PRNG would either block or return 0 bytes of data, or a full pool's worth. Hmm. Timing attacks? Known-input attacks? Will you relent a step or two if I can get the entropy harvesting _rate_ high enough? :-) If we get the entropy pools filling fast enough that the reseed is triggering close to every 256 bits of output then it becomes much less of a concern (but it's still there, because reseeding happens asynchronously with respect to PRNG output). However I think that in practice this will be too heavy on the CPU (unless we weaken the reseed operation) and make dd if=/dev/urandom of=/dev/null a very effective local user DoS :-( The dd if=/dev/urandom of=/dev/null is _already_ a doozy of a dos. Likewise a fork-bomb, a /tmp-filler, likewise a whole bunch of things much worse. Heck, you can hurt your system with cat /dev/zero /dev/null. Asynchonous reseeding _improves_ the situation; the attacker cannot force it to any degree of accuracy, and if he has the odds stacked heavily against him that each 256-bits of output will have an associated reseed, it makes his job pretty damn difficult. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Stefan `Sec` Zehl writes: Assume I want to encrypt a message by XOR'ing with randomness. If I then exchange my keys securely, the message is uncrackable. With the current approach it has a 256bits key. This is, in my eyes, not good. Although yarrow is nice, It's suited for any kind of key generation. The first law of crypto clearly states: "Know what you're doing". There is no way around that law. We cannot load down FreeBSD with impossibly heavy computations to cater for any and all conceiveable application of random numbers. In particular I fear that the current implementation already has killed battery lifetimes on laptops :-( -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
David Schwartz wrote: /dev/random should block if the system does not contain as much real entropy as the reader desires. Otherwise, the PRNG implementation will be the weakest link for people who have deliberately selected higher levels of protection from cryptographic attack. I don't want to rehash this thread from the beginning. Please go back, read the Yarrow paper, and recognise that Yarrow is not an entropy-counter, it is a cryptographically secure PRNG. The "count random bits and block" model does not apply. Then the current implementation cannot provide the usual semantics for /dev/random, while it can provide the semantics for /dev/urandom. As I understand it, /dev/random is supposed to provide true randomness suitable for generating keys of unlimited length, whereas /dev/urandom is supposed to provide cryptographically-strong randomness for general applications. If people want /dev/random to seed 1024-bit keys, /dev/random must be stronger than a 1024-bit key. 1. The current /dev/random cannot do it, it's less secure than Yarrow for a variety of reasons. So we have a net improvement anyway. Thanks Mark. 2. Most people do not want to seed 1024-bit keys as outlined in another mail in this thread. If they *understand* the issues involved they will realize that 2^256 complexity is plenty uncrackable for all practical purposes. FreeBSD is about practical purposes IMHO. 3. Yarrow can be modified to just do this, should someone think this is neccessary. Read the paper and think of what happens when you set Pg to 1/(2^(k/3)). (Note that the paper restricts this value to 1 = Pg but that's of no importance here.) ** This is overly conservative for most applications I can think of; Even a multi-million dollar financial transactioning system will be practically secure when Pg is set to 1. 4. Nothing prevents you from adapting Yarrow so that current /dev/random semantics are preserved, making Yarrow even better. It can be done with the current design it's just not very beneficial to do it. 5. Yarrow was designed as a better replacement for most any PRNG by a couple of bright cryptographers. Can you do better than that? Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Kris Kennaway wrote: On Sun, 23 Jul 2000, Mark Murray wrote: This design tradeoff is discussed in section 4.1 of the paper. Tweakable. Doing a reseed operation with every output is going to be *very* computationally expensive. Tradeoff. What do you want? Lightning fast? Excessive security? Balance it out. Thinking about it further, I dont think Yarrow can even do this (introduce entropy into every output value) without bypassing the block cipher. Why not? And if you reseed with every 256 bits of output then you're vulnerable to an iterative guessing attack because the fast pool won't have much in it. You would block until the pool is filled with entropy. [...] There are two other models which rate "pretty well-designed" in the Yarrow paper: the cryptlib and PGP PRNGs. I don't know what their properties are right now (the cryptlib one is described in the paper on PRNG cryptanalysis). Fortunately you don't need them :-) I'll relent somewhat if a secure entropy distilling algorithm could be found; one which stands up to crypanalysis. Well, a simple scheme which doesn't seem to suffer from any of the vulnerabilities discussed in the schneier papers is to accumulate entropy in a pool, and only return output when the pool is full. i.e. the PRNG would either block or return 0 bytes of data, or a full pool's worth. And you can make Yarrow do just that. Not very practical but you can do it. You effectively set Pg to 1/(2^(k/3)). Will you relent a step or two if I can get the entropy harvesting _rate_ high enough? :-) If we get the entropy pools filling fast enough that the reseed is triggering close to every 256 bits of output then it becomes much less of a concern (but it's still there, because reseeding happens asynchronously with respect to PRNG output). Reseeds do not *have* to happen asynchronously as pointed out above. What is of importance is that you *cannot* forcibly trigger a reseed without there being enough entropy in the pools. There is nothing against having /dev/random block until the pools have accumulated enough entropy. Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
RE: randomdev entropy gathering is really weak
5. Yarrow was designed as a better replacement for most any PRNG by a couple of bright cryptographers. Can you do better than that? Nope, I agree. Ignore my previous objections. DS To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Mark Murray wrote: There are two other models which rate "pretty well-designed" in the Yarrow paper: the cryptlib and PGP PRNGs. I don't know what their properties are right now (the cryptlib one is described in the paper on PRNG cryptanalysis). Do you have copies of the articles concerned? I'd surely appreciate a photocopy of the relevant pages if you don't mind! :-) The paper I was referring to was: http://www.counterpane.com/pseudorandom_number.html Cryptlib is described here: http://www.cs.auckland.ac.nz/~pgut001/cryptlib/ Well, a simple scheme which doesn't seem to suffer from any of the vulnerabilities discussed in the schneier papers is to accumulate entropy in a pool, and only return output when the pool is full. i.e. the PRNG would either block or return 0 bytes of data, or a full pool's worth. Hmm. Timing attacks? Known-input attacks? Inasmuch as the hash function has no timing attacks (data-dependent code paths, etc) I don't see a weakness there. Chosen input attacks can be mitigated by using a hash function which provides strong mixing (e.g. SHA1), so there is no correlation between partially-known input and output. Yarrow of course takes it a step further by using a very heavy mixing function to regenerate the key, although it seems to me from the design rationale that this is to remove correlations between the Yarrow key before and after reseeding, which doesn't affect an unkeyed PRNG which doesnt maintain state. Will you relent a step or two if I can get the entropy harvesting _rate_ high enough? :-) If we get the entropy pools filling fast enough that the reseed is triggering close to every 256 bits of output then it becomes much less of a concern (but it's still there, because reseeding happens asynchronously with respect to PRNG output). However I think that in practice this will be too heavy on the CPU (unless we weaken the reseed operation) and make dd if=/dev/urandom of=/dev/null a very effective local user DoS :-( The dd if=/dev/urandom of=/dev/null is _already_ a doozy of a dos. Likewise a fork-bomb, a /tmp-filler, likewise a whole bunch of things much worse. Heck, you can hurt your system with cat /dev/zero /dev/null. Well, all of the others can be mitigated by resource limits. It's something which needs to be revisited. Asynchonous reseeding _improves_ the situation; the attacker cannot force it to any degree of accuracy, and if he has the odds stacked heavily against him that each 256-bits of output will have an associated reseed, it makes his job pretty damn difficult. What I meant with that point is that the user may get, say an extra few hundred bits out of it with no new entropy before the scheduled reseed task kicks in. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 23 Jul 2000, Jeroen C. van Gelderen wrote: Well, a simple scheme which doesn't seem to suffer from any of the vulnerabilities discussed in the schneier papers is to accumulate entropy in a pool, and only return output when the pool is full. i.e. the PRNG would either block or return 0 bytes of data, or a full pool's worth. And you can make Yarrow do just that. Not very practical but you can do it. You effectively set Pg to 1/(2^(k/3)). Oh, I missed this - thanks. It does introduce an extra overhead, namely applying a generator gate with every output (since n k and Pg 1) and then the full reseed with every k bits of output. ITYM Pg = k 2^(-k/3) though - you want a maximum k bits of output, not 1. I'm not sure if the current implementation will let you do this (since Pg 1 here). Reseeds do not *have* to happen asynchronously as pointed out above. Yeah, but they do in the current implementation (AFAICT). Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
I'm all for storing a sample at shutdown and using it to help seed the PRNG at startup, but it shouldn't be the only seed used (for example, the case where the system has never been shut down (cleanly) before and so has no pre-existing seed file is a BIG corner case to consider since thats how the system is at the time it first generates SSH keys after a fresh install). Agreed; we need more entropy sources that are available early enough to be useful. It might be only an academic vulnerability, but if someone can read your HD during the time the system is shut down then I'd prefer them not to know the precise state when the system next starts up again. Yes, if they can read they can probably also write, but it seems like a mistake when there's nothing really gained by saving the complete state, as opposed to an extract. Academic argument noted; with more entropy sources, this situation will improve. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
After rereading the paper in more detail, Step 7 of the reseed algorithm seems not entirely consistent with this: they explicitly refer to writing out "the next 2k bits of output from the generator to the seed file" (slightly different terminology, but I couldn't find any other references to the "seed file") He doesn't talk about it too much :-(. Another important point is that Yarrow-160 is not useful for generating keys 160 bits, because of Shannon's theorem and the fact that it uses SHA-1. You seem to be using a blowfish-based hash function with 256-bit keysize (do you have a reference for using blowfish in that fashion?), but the point stands. It seems we would need to use an alternative interface which either synchronously reseeds with every output to generate stronger random data, or just taps into the (hashed) entropy pools directly. Lots of references: Schneier's "Applied Cryptography" talks about using Good Hashes for crypto and Good Crypto for hashes. Schneier's site at www.counterpane.com will give you plenty. It is also an extension and improvement on the way OpenBSD do their bcrypt (passwd) hash. This was also a problem with our /dev/urandom (by design), but not with /dev/random since that tapped the entropy pool directly. Incidentally, it also looks like a problem with OpenBSD's /dev/arandom which is a stream cipher (arc4 with 256-bit key) periodically reseeded. The differnce with the old system and Yarrow is yarrow's self-recovery property; Yarrow screens its internal state from the ouside world very heavily, and provides enough perturbation of it from its copious :-) entropy harvesting to keep the state safe from compromise. Yarrow also keeps multiple (fast/slow pools + key) states, and the long, slow interactions between those give much better protection that the old system which was pretty much a simple PRNG+simple random perturbations. (I know MD5 is not "simple", but it is deterministic, and was only used once). M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Mark Murray wrote: Lots of references: Schneier's "Applied Cryptography" talks about using Good Hashes for crypto and Good Crypto for hashes. Schneier's site at www.counterpane.com will give you plenty. I havent been able to get my hands on Applied Cryptography, but I don't recall seeing anything like this on the website. I'll check again. The differnce with the old system and Yarrow is yarrow's self-recovery property; Yarrow screens its internal state from the ouside world very heavily, and provides enough perturbation of it from its copious :-) entropy harvesting to keep the state safe from compromise. Yeah, I know all this and agree that Yarrow makes a better /dev/urandom, but it doesn't change the fact that Yarrow-256 is only good for 256 bits of entropy between reseeding operations. You can pull all you want out of it but will never get more than 256 bits until it reseeds. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
The differnce with the old system and Yarrow is yarrow's self-recovery property; Yarrow screens its internal state from the ouside world very heavily, and provides enough perturbation of it from its copious :-) entropy harvesting to keep the state safe from compromise. Yeah, I know all this and agree that Yarrow makes a better /dev/urandom, but it doesn't change the fact that Yarrow-256 is only good for 256 bits of entropy between reseeding operations. You can pull all you want out of it but will never get more than 256 bits until it reseeds. Aaah! I understand your question better; this is the "conservation of entropy" argument which Yarrow "breaks". Because of Yarrow's cryptographic protection of its internal state, its frequent reseeds and its clever geneation mechanism, this paradigm is less important - the output is 256-bit safe (Blowfish safe) for any size of output[*]. When you read 1000 bits, I am not selling you 1000 bits each guaranteed random, I am selling you 1000 bits that are predictable within the constraints of needing to crack 256-bit Blowfish. [*] Assuming no errors on the part of the implementor (me). :-) M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Mark Murray wrote: Because of Yarrow's cryptographic protection of its internal state, its frequent reseeds and its clever geneation mechanism, this paradigm is less important - the output is 256-bit safe (Blowfish safe) for any size of output[*]. When you read 1000 bits, I am not selling you 1000 bits each guaranteed random, I am selling you 1000 bits that are predictable within the constraints of needing to crack 256-bit Blowfish. So what it if I want/need 257 bits? :-) Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Mark Murray wrote: Because of Yarrow's cryptographic protection of its internal state, its frequent reseeds and its clever geneation mechanism, this paradigm is less important - the output is 256-bit safe (Blowfish safe) for any size of output[*]. When you read 1000 bits, I am not selling you 1000 bits each guaranteed random, I am selling you 1000 bits that are predictable within the constraints of needing to crack 256-bit Blowfish. So what it if I want/need 257 bits? :-) Read them. You'll get them. If you want higher quality randomness than Yarrow gives, read more than once. Do other stuff; play. Don't get stuck in the "I have exhausted the randomness pool" loop; Yarrow does not play that game. From the Yarrow paper: ``Yarrow's outputs are cryptographically derived. Systems that use Yarrow's outputs are no more secure than the generation mechanism used.'' We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could make it so. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Kris Kennaway wrote: On Sat, 22 Jul 2000, Mark Murray wrote: Lots of references: Schneier's "Applied Cryptography" talks about using Good Hashes for crypto and Good Crypto for hashes. Schneier's site at www.counterpane.com will give you plenty. I havent been able to get my hands on Applied Cryptography, but I don't recall seeing anything like this on the website. I'll check again. The differnce with the old system and Yarrow is yarrow's self-recovery property; Yarrow screens its internal state from the ouside world very heavily, and provides enough perturbation of it from its copious :-) entropy harvesting to keep the state safe from compromise. Yeah, I know all this and agree that Yarrow makes a better /dev/urandom, but it doesn't change the fact that Yarrow-256 is only good for 256 bits of entropy between reseeding operations. You can pull all you want out of it but will never get more than 256 bits until it reseeds. You don't care in practice, 256 bits are unguessable. If you do care, you load a different random module :-) Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Kris Kennaway wrote: On Fri, 21 Jul 2000, Mark Murray wrote: Section 2.1, last paragraph: "If a system is shut down, and restarted, it is desirable to store some high-entropy data (such as the key) in non-volatile memory. This allows the PRNG to be restarted in an unguessable state at the next restart. We call this data the reseed file." I'm all for storing a sample at shutdown and using it to help seed the PRNG at startup, but it shouldn't be the only seed used (for example, the case where the system has never been shut down (cleanly) before and so has no pre-existing seed file is a BIG corner case to consider since thats how the system is at the time it first generates SSH keys after a fresh install). It might be only an academic vulnerability, but if someone can read your HD during the time the system is shut down then I'd prefer them not to know the precise state when the system next starts up again. Yes, if they can read they can probably also write, but it seems like a mistake when there's nothing really gained by saving the complete state, as opposed to an extract. Well, academic or not (not when you run financial transactioning systems on FreeBSD) you can edit rc.shutdown to not write out a seed file. You don't have to use it but it's good that it's there. Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Fri, 21 Jul 2000, Mark Murray wrote: Section 2.1, last paragraph: "If a system is shut down, and restarted, it is desirable to store some high-entropy data (such as the key) in non-volatile memory. This allows the PRNG to be restarted in an unguessable state at the next restart. We call this data the reseed file." I'm all for storing a sample at shutdown and using it to help seed the PRNG at startup, but it shouldn't be the only seed used (for example, the case where the system has never been shut down (cleanly) before and so has no pre-existing seed file is a BIG corner case to consider since thats how the system is at the time it first generates SSH keys after a fresh install). It might be only an academic vulnerability, but if someone can read your HD during the time the system is shut down then I'd prefer them not to know the precise state when the system next starts up again. Yes, if they can read they can probably also write, but it seems like a mistake when there's nothing really gained by saving the complete state, as opposed to an extract. And for folks like us who do mass installs via dd if=/dev/da1 of=/dev/da2, where da1 is a mastered image created via ``make installworld DESTDIR=/mnt'', the corner case is very large. I have been bitten by an event where the master disk was booted once before replication, and thus all systems had _IDENTICAL_ /etc/ssh contents. Not a very good idea !! We have amended the manufacturing process now, so that part of the disk replication is the nuking and regeneration of /etc/ssh. -- Rod Grimes - KD7CAX @ CN85sl - (RWG25) [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
RE: randomdev entropy gathering is really weak
From the Yarrow paper: ``Yarrow's outputs are cryptographically derived. Systems that use Yarrow's outputs are no more secure than the generation mechanism used.'' We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could make it so. M -- Mark Murray It doesn't matter if it's Yarrow-256, Yarrow-1024, or Yarrow-10. /dev/random should block if the system does not contain as much real entropy as the reader desires. Otherwise, the PRNG implementation will be the weakest link for people who have deliberately selected higher levels of protection from cryptographic attack. DS To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
/dev/random should block if the system does not contain as much real entropy as the reader desires. Otherwise, the PRNG implementation will be the weakest link for people who have deliberately selected higher levels of protection from cryptographic attack. I don't want to rehash this thread from the beginning. Please go back, read the Yarrow paper, and recognise that Yarrow is not an entropy-counter, it is a cryptographically secure PRNG. The "count random bits and block" model does not apply. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Mark Murray wrote: So what it if I want/need 257 bits? :-) Read them. You'll get them. If you want higher quality randomness than Yarrow gives, read more than once. Do other stuff; play. Don't get stuck in the "I have exhausted the randomness pool" loop; Yarrow does not play that game. I think you're missing the point. The only way I can get a random number with more than n bits of entropy out of Yarrow-n is if I sample either side of a reseed operation, which in general comes down to timing guesswork and having to make assumptions about the PRNG implementation. If you want to generate a cryptographic key of length n bits then you really want n bits of entropy in the random source you're deriving it from, otherwise your key is actually much weaker than advertised because it's easier for the attacker to attack the state of the PRNG that derived it than to attack the key itself. From the Yarrow paper: ``Yarrow's outputs are cryptographically derived. Systems that use Yarrow's outputs are no more secure than the generation mechanism used.'' We currently have Yarrow-256(Blowfish); wanna make it Yarrow-1024? I could make it so. Well, if we did that then how about generating 2048-bit keys? :-) Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote: You don't care in practice, 256 bits are unguessable. Actually, I do..that's the entire point of using long keys. If you do care, you load a different random module :-) The core of my complaint is that even though our old PRNG did crappy entropy handling, we used to have such a method, which is now gone. I'd like to see yarrow hang off /dev/urandom and have /dev/random tap directly into the entropy pool (perhaps a third pool separate from Yarrow's fast/slow) so I can generate my large keys safely. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Kris Kennaway wrote: On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote: You don't care in practice, 256 bits are unguessable. Actually, I do..that's the entire point of using long keys. I agree that you need long RSA keys ... but the real discussion isn't really about key length but rather about the overall complexity of attacking the key: The complexity of factoring a 1024-bit RSA keys is on the order of 2^71 operations. For a 3214-bit key it is roughly equivalent to 2^101 complexity. (See [1][2] for gloriously arcane details.) Now, assuming that you generate a 3214-bit RSA key from a 256-bit entropy pool, the complexity of factoring it (2^101) is much lower than the complexity of guessing the entropy pool from which it was generated (2^256); Actually, factoring is the most efficient attack up to the point where you are using something like a 13841-bit RSA key[3]. So, for practical key purposes Yarrow-256 is in excess of complexity requirements. (I can't say anything about other uses than crypto but seeing as the promise of /dev/random is cryptographically secure random numbers this should not pose a problem.) That said, there is nothing to prevent the system admin from tweaking the Yarrow security parameters so that Yarrow will only spit out as many bits or pseudo-randomness as it gathers bits of entropy.[4] Check out http://www.cryptosavvy.com/table.htm and preferrably the full paper at http://www.cryptosavvy.com/cryptosizes.pdf if you remain unconvinced :-) Cheers, Jeroen [1] Numbers from http://www.cryptosavvy.com/table.htm . [2] Yes, this sortof means that using = 128-bit keys is overkill for most applications that use assymmetric algorithms for key-negotiation :-) [3] http://www.cryptosavvy.com/suggestions.htm [4] And if you really would like to restore the old semantics of /dev/[u]random, you could code it into Yarrow. Just make /dev/random block based on the entropy estimation that Yarrow keeps anyway. -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sat, 22 Jul 2000, Jeroen C. van Gelderen wrote: I agree that you need long RSA keys ... but the real discussion isn't really about key length but rather about the overall complexity of attacking the key: Okay, using RSA keys wasn't the best example to pick, but Yarrow also seems easy to misuse in other cases: for example if you want to generate multiple 256-bit symmetric keys (or other random data) at the same time, each additional key after the first won't contain any additional entropy, so if you break the state of the PRNG at the time the first one was generated you get the others for free (until the thing reseeds). This design tradeoff is discussed in section 4.1 of the paper. That said, there is nothing to prevent the system admin from tweaking the Yarrow security parameters so that Yarrow will only spit out as many bits or pseudo-randomness as it gathers bits of entropy.[4] Well, I don't see a way to tune this without modifying the Yarrow design, since the entropy pool is intentionally decoupled from the output mechanism, and it seems like it would add additional (unnecessary) overhead anyway to use it in that fashion. Indications are we can probably get quite a lot of usable entropy from a standard system (on the order of many kilobytes per second - but I need to read more of the literature about processing of entropy samples) - in this case I think maintaining a third pool which is directly tapped by /dev/random, and leaving Yarrow sitting behind /dev/urandom is the way to go. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Tue, 18 Jul 2000, Dan Moschuk wrote: Well, how many other OSs out there allow /dev/random to be written to? FreeBSD, OpenBSD, NetBSD, Linux... Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
What about saving the state of the RNG and re-reading it on bootup? That will allow Yarrow to continue right where it left off. :-) That's a bad thing. You don't want someone to be able to examine the exact PRNG state at next boot by looking at your hard disk after the machine has shut down. It is a Yarrow-mandated procedure. Please read the Yarrow paper. If they can do that, they have either the console (==root) or they have root. Either way, who cares what they know about your machine, they have the whole darn thing :-O. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
| | Gotcha - fix coming; I need to stash some randomness at shutdown time, and | | use that to reseed the RNG at reboot time. | | What about saving the state of the RNG and re-reading it on bootup? That | will allow Yarrow to continue right where it left off. :-) | | That's a bad thing. You don't want someone to be able to examine the exact | PRNG state at next boot by looking at your hard disk after the machine has | shut down. I don't see how. If the attacker has physical access to the machine, there are plenty worse things to be done than just reading the state of a PRNG. If the random device is initialized in single user mode, and the file is then unlink()ed, I don't see any problems with that. -Dan To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Mark Murray wrote: What about saving the state of the RNG and re-reading it on bootup? That will allow Yarrow to continue right where it left off. :-) That's a bad thing. You don't want someone to be able to examine the exact PRNG state at next boot by looking at your hard disk after the machine has shut down. It is a Yarrow-mandated procedure. Please read the Yarrow paper. Actually, it's not. You don not want to save the exact PRNG state to disk, ever. It's not Yarrow mandated procedure but a big security hole. That said, you do not write out the state of the PRNG, you write out a couple of blocks of output from which the state cannot be derived. That *is* okay and that's what you are doing. And just for completeness: it's not mandatory to do so. I don't know where you read that in the paper. If they can do that, they have either the console (==root) or they have root. Either way, who cares what they know about your machine, they have the whole darn thing :-O. Someone may well compromise your randomness source without you noticing. And read your PGP mail for the coming couple of years because your PGP key was compromised without you noticing. Perfect Trojan horse to write for the FBI, IRS, anyone who doesn't like you. Oops. Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Dan Moschuk wrote: | | Gotcha - fix coming; I need to stash some randomness at shutdown time, and | | use that to reseed the RNG at reboot time. | | What about saving the state of the RNG and re-reading it on bootup? That | will allow Yarrow to continue right where it left off. :-) | | That's a bad thing. You don't want someone to be able to examine the exact | PRNG state at next boot by looking at your hard disk after the machine has | shut down. I don't see how. If the attacker has physical access to the machine, there are plenty worse things to be done than just reading the state of a PRNG. If the random device is initialized in single user mode, and the file is then unlink()ed, I don't see any problems with that. You generate a new PGP keypair and start using it. Your co-worker reboots your machine afterwards and recovers the PRNG state that happens to be stashed on disk. He can then backtrack and potentially recover the exact same random numbers that you used for your key. Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Jeroen C. van Gelderen wrote: Dan Moschuk wrote: I don't see how. If the attacker has physical access to the machine, there are plenty worse things to be done than just reading the state of a PRNG. If the random device is initialized in single user mode, and the file is then unlink()ed, I don't see any problems with that. You generate a new PGP keypair and start using it. Your co-worker reboots your machine afterwards and recovers the PRNG state that happens to be stashed on disk. He can then backtrack and potentially recover the exact same random numbers that you used for your key. I don't follow your logic. A normal boot/shutdown sequence would be: (1) power on (or shutdown -r) (2) in single-user mode (a) read /dev/saved_entropy into buffer (b) unlink /dev/saved_entropy (c) create /dev/saved_entropy with all zeros (d) test contents in buffer against all zeros (I) buffer contents is different from all zeros; initialize entropy pool (II) buffer contents matches all zeros; use a fall-back method. (3) go multi-user (4) normal shutdown (a) kick everybody off system (b) kill off daemons (c) umount all partitions except the partition with /dev (c) save entropy to /dev/saved_entropy (d) umount partition with /dev After a crash or panic, the system reboots. Step 2(c) has left a finger print to test for valid saved entropy. If all zeros are found use a suitable fallback method to stir the entropy. I don't see how co-worker can do what you suggest. And, if he can easily reboot your system, you have other problems to worry about. -- Steve To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
It is a Yarrow-mandated procedure. Please read the Yarrow paper. Actually, it's not. You don not want to save the exact PRNG state to disk, ever. It's not Yarrow mandated procedure but a big security hole. Section 2.1, last paragraph: "If a system is shut down, and restarted, it is desirable to store some high-entropy data (such as the key) in non-volatile memory. This allows the PRNG to be restarted in an unguessable state at the next restart. We call this data the reseed file." Perhaps "mandated" was a bit strong; "desired" might be better. That said, you do not write out the state of the PRNG, you write out a couple of blocks of output from which the state cannot be derived. That *is* okay and that's what you are doing. Writing the 256-bit key would have been OK according to the paper. And just for completeness: it's not mandatory to do so. I don't know where you read that in the paper. See above. If they can do that, they have either the console (==root) or they have root. Either way, who cares what they know about your machine, they have the whole darn thing :-O. Someone may well compromise your randomness source without you noticing. And read your PGP mail for the coming couple of years because your PGP key was compromised without you noticing. Perfect Trojan horse to write for the FBI, IRS, anyone who doesn't like you. Oops. Sure; we neet to be appropriately paranoid about that, but let's not get ridiculous. The seed file could certainly use some decent protection, but unfortunately, PC architectures don't come with SIMcards or the like. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
You generate a new PGP keypair and start using it. Your co-worker reboots your machine afterwards and recovers the PRNG state that happens to be stashed on disk. He can then backtrack and potentially recover the exact same random numbers that you used for your key. Said state is rm'med after use. If you didn't detect the breakin, your fault for poor intrusion detection. lets put the paranoia to practical use and detect the breakin, not nitpick the systems that are supposed to be protected. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Fri, 21 Jul 2000, Mark Murray wrote: : :Sure; we neet to be appropriately paranoid about that, but let's not :get ridiculous. The seed file could certainly use some decent protection, :but unfortunately, PC architectures don't come with SIMcards or the like. : Is it possible to combine the state of the disk based seed with some other source of real entropy? That would redudce the risk of having someone read your disks while the system is shutdown. David To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
:Sure; we neet to be appropriately paranoid about that, but let's not :get ridiculous. The seed file could certainly use some decent protection, :but unfortunately, PC architectures don't come with SIMcards or the like. : Is it possible to combine the state of the disk based seed with some other source of real entropy? That would redudce the risk of having someone read your disks while the system is shutdown. I'm working on haresting some more entropy; that should do what you want. (Things like disk activity, network stack, process tables and so on). If you are worried about someone reading the disk of a rebooting box, then you need to be worried about console access; if your attacker has console, you are screwed anyway. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
RE: randomdev entropy gathering is really weak
You generate a new PGP keypair and start using it. Your co-worker reboots your machine afterwards and recovers the PRNG state that happens to be stashed on disk. He can then backtrack and potentially recover the exact same random numbers that you used for your key. If that is possible, then Yarrow's algorithm is badly broken. It should not be possible to run a PRNG backwards without knowing what it output. Once it outputs something, the state information neccessary to produce that output should be removed by the output process. Imagine if I have a PRNG in state 0 (which I'll call "S(0)"). It then outputs a particular 32-bit PRN, called 'A' and is now in a new state S(1). Now, if one tries to backtrack from S(1) to S(0), one needs to know A. For every possible 32-bit A that could have been output, there's a different corresponding S'(0) (state that might have been S(0)). Since the attacker does not know A, he does not know which S'(0) corresponds to S(0), and hence cannot backtrack. Since the people who developed this algorithm are pretty bright, I will conculde that this is not the case. DS To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Fri, 21 Jul 2000, Mark Murray wrote: Section 2.1, last paragraph: "If a system is shut down, and restarted, it is desirable to store some high-entropy data (such as the key) in non-volatile memory. This allows the PRNG to be restarted in an unguessable state at the next restart. We call this data the reseed file." I'm all for storing a sample at shutdown and using it to help seed the PRNG at startup, but it shouldn't be the only seed used (for example, the case where the system has never been shut down (cleanly) before and so has no pre-existing seed file is a BIG corner case to consider since thats how the system is at the time it first generates SSH keys after a fresh install). It might be only an academic vulnerability, but if someone can read your HD during the time the system is shut down then I'd prefer them not to know the precise state when the system next starts up again. Yes, if they can read they can probably also write, but it seems like a mistake when there's nothing really gained by saving the complete state, as opposed to an extract. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Fri, 21 Jul 2000, Mark Murray wrote: If you are worried about someone reading the disk of a rebooting box, then you need to be worried about console access; if your attacker has console, you are screwed anyway. For most people, yes. But it's like all of the buffer overflows in non-setuid utilities: they're not security risks for the vast majority of users, but who's to say there won't be a situation somewhere when it is one. Better not to take the risk, since it's not necessary here. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
RE: randomdev entropy gathering is really weak
On Fri, 21 Jul 2000, David Schwartz wrote: You generate a new PGP keypair and start using it. Your co-worker reboots your machine afterwards and recovers the PRNG state that happens to be stashed on disk. He can then backtrack and potentially recover the exact same random numbers that you used for your key. If that is possible, then Yarrow's algorithm is badly broken. It should not be possible to run a PRNG backwards without knowing what it output. Once it outputs something, the state information neccessary to produce that output should be removed by the output process. Yarrow only reseeds every so often when it has enough entropy accumulated, and changes its internal key using a "generator gate" every few inputs (the paper suggests 10). So if you break the state of the algorithm (e.g. if it were stored on disk after a reboot) you can learn up to 10 previous PRNG outputs with that key, back to the previous generator gate or reseed. This issue is common to all PRNGs that don't reseed with every output value - it's discussed in the Yarrow paper, which you should read :-) Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Fri, 21 Jul 2000, Kris Kennaway wrote: Section 2.1, last paragraph: "If a system is shut down, and restarted, it is desirable to store some high-entropy data (such as the key) in non-volatile memory. This allows the PRNG to be restarted in an unguessable state at the next restart. We call this data the reseed file." After rereading the paper in more detail, Step 7 of the reseed algorithm seems not entirely consistent with this: they explicitly refer to writing out "the next 2k bits of output from the generator to the seed file" (slightly different terminology, but I couldn't find any other references to the "seed file") Another important point is that Yarrow-160 is not useful for generating keys 160 bits, because of Shannon's theorem and the fact that it uses SHA-1. You seem to be using a blowfish-based hash function with 256-bit keysize (do you have a reference for using blowfish in that fashion?), but the point stands. It seems we would need to use an alternative interface which either synchronously reseeds with every output to generate stronger random data, or just taps into the (hashed) entropy pools directly. This was also a problem with our /dev/urandom (by design), but not with /dev/random since that tapped the entropy pool directly. Incidentally, it also looks like a problem with OpenBSD's /dev/arandom which is a stream cipher (arc4 with 256-bit key) periodically reseeded. Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
The reason why ntp is interesting is that we compare the received data with our unpredictable local clock. It is the result of this comparison which is good entropy bits. Is the resolution of thermal sensors on many new motherboards and CPU high enough to get thermal randomness? Peter -- Peter Dufault ([EMAIL PROTECTED]) Realtime development, Machine control, HD Associates, Inc. Fail-Safe systems, Agency approval To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On 19-Jul-00 Peter Dufault wrote: Is the resolution of thermal sensors on many new motherboards and CPU high enough to get thermal randomness? The voltage sensors have some noise too (maybe not enough). -- Steve O'Hara-Smith [EMAIL PROTECTED] http://sohara.webhop.net/ A Better Way To Focus The Sun To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Wed, 19 Jul 2000, Steve O'Hara-Smith wrote: On 19-Jul-00 Peter Dufault wrote: Is the resolution of thermal sensors on many new motherboards and CPU high enough to get thermal randomness? The voltage sensors have some noise too (maybe not enough). Fan speed too. Leif To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED] Alexander Leidinger writes: : systems which have a more or less precise clock attached (e.g. GPS or : atomic clocks which sync the system clock via nptd)? And what are the : numbers for this solution (for those people which are interested in : numbers to be their own judge)? I can tell you right now that the variation between GPS and a good cesium clock is on the order of +- 25ns. With nanosecond resolution, this gives you about 5 bits. The variation of the system clock when synchronized to the GPS receiver is on the order of +-10us as measured with a parallel port interrupt and a pps line from the gps receiver. The pps interrupt is measured using a fast interrupt (we hacked ppc to do fast interrupts for this), so the latency is fairly small and fairly constant. I don't have datasets that I can point people at, however. Warner To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Warner Losh writes: Another good source would be if you had a Cesium clock and a GPS receiver. The delay due to atmospherics is another good source of random data. This varies +- 25ns and is highly locale dependent. One can measure this variance down to the nanosecond easily (giving about 5 bits of randomness) and with a lot of effort down to the pico second level, which would give you about 15 bits of randomness. A geiger counter and a smoke-detector would be *so much* cheaper and give more bits per second :-) It certainly would be better than nothing and would be a decent source of randomness. It would be my expectation that if tests were run to measure this randomness and the crypto random tests were applied, we'd find a fairly good source. The trick here is to actually measure the quality of our entropy. I have asked Markm to provide us with some kernel option which can be used to get a copy of the entropy so we can study the quality off it. BTW: You have *no* idea how much I envy your access to high quality timing hardware :-) -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
[ A whole bunch of sane stuff removed ] It certainly would be better than nothing and would be a decent source of randomness. It would be my expectation that if tests were run to measure this randomness and the crypto random tests were applied, we'd find a fairly good source. The randomness is good, no doubt; I worry about how accessible that randomness is to an attacker? If the attacker is on your computer (he us a user, say), he might know a lot about the current frequency of your xtal. He can also get the same (remote) time offsets as you. What does that give him? Not much, but it could reduce the bits that he needs to guess. By how much? I don't know. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED] Poul-Henning Kamp writes: : A geiger counter and a smoke-detector would be *so much* cheaper : and give more bits per second :-) Agreed. And a lot less hassle. A *LOT* less hassle. :-) : It certainly would be better than nothing and would be a decent source : of randomness. It would be my expectation that if tests were run to : measure this randomness and the crypto random tests were applied, : we'd find a fairly good source. : : The trick here is to actually measure the quality of our entropy. : I have asked Markm to provide us with some kernel option which can : be used to get a copy of the entropy so we can study the quality : off it. Yes. That's the hard part. that's one area where my knowledge is somewhat weak. : BTW: You have *no* idea how much I envy your access to high quality : timing hardware :-) Well, there are hidden benefits working here that I never knew :-) Warner To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED] Mark Murray writes: : The randomness is good, no doubt; I worry about how accessible that : randomness is to an attacker? That's a good thing to worry about. : If the attacker is on your computer (he us a user, say), he might know : a lot about the current frequency of your xtal. He can also get the same : (remote) time offsets as you. What does that give him? Not much, but it : could reduce the bits that he needs to guess. By how much? I don't : know. I don't know the answers to that either. Of course, if the attaker has root access to your machine, then you have bigtime problems with keeping the random bits secret anyway... Warner To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Mark Murray writes: [ A whole bunch of sane stuff removed ] It certainly would be better than nothing and would be a decent source of randomness. It would be my expectation that if tests were run to measure this randomness and the crypto random tests were applied, we'd find a fairly good source. The randomness is good, no doubt; I worry about how accessible that randomness is to an attacker? If the attacker is on your computer (he us a user, say), he might know a lot about the current frequency of your xtal. He can also get the same (remote) time offsets as you. What does that give him? Not much, but it could reduce the bits that he needs to guess. By how much? I don't know. Mark, this is one of the reasons why we need a way to measure the quality of our entropy, please -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED] Peter Dufault writes: : The reason why ntp is interesting is that we compare the received data : with our unpredictable local clock. It is the result of this comparison : which is good entropy bits. : : Is the resolution of thermal sensors on many new motherboards and : CPU high enough to get thermal randomness? Yes. You'll also find that the voltage drifts as well. However, I doubt you'd be able to get more than 1 bit out of the voltage readings. The thermal readings, depending on their precision, would also yield several random bits. But this several may be only 3 or 4. The temperature varies based on work load and on the climate controls in place at the site. I actually meant can you get real randomness, measuring the thermal noise in the on-chip temperature diode should be a good source of randomness. Except they are probably "kind" enough to fully filter it out. Peter -- Peter Dufault ([EMAIL PROTECTED]) Realtime development, Machine control, HD Associates, Inc. Fail-Safe systems, Agency approval To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
The trick here is to actually measure the quality of our entropy. I have asked Markm to provide us with some kernel option which can be used to get a copy of the entropy so we can study the quality off it. I have something that is _very_ crude, and definitely not commitworthy, but it is up to the doing the job above. As soon as I've prettyfied it a bit, I'll give y'all some patches. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
: If the attacker is on your computer (he us a user, say), he might know : a lot about the current frequency of your xtal. He can also get the same : (remote) time offsets as you. What does that give him? Not much, but it : could reduce the bits that he needs to guess. By how much? I don't : know. I don't know the answers to that either. Of course, if the attaker has root access to your machine, then you have bigtime problems with keeping the random bits secret anyway... My scenario assumed that the attacker/user was not root. Of course if he is root, he knows a bit more, but even a non-root attacker can make a statistical study of the local clock and some hand-rolled ntp code. (I'm not suggesting it is easy, just possible :-) ) M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
If the attacker is on your computer (he us a user, say), he might know a lot about the current frequency of your xtal. He can also get the same (remote) time offsets as you. What does that give him? Not much, but it could reduce the bits that he needs to guess. By how much? I don't know. Mark, this is one of the reasons why we need a way to measure the quality of our entropy, please I understand 100%! That's why I'm doing it :-) M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Actually, you could really use this in ntpd(8), rather than just ntpdate. You could crank in the offset and delay samples for each packet received from an NTP peer; this will have the effect of adding into the entropy pool the "noise" in the latency of the path between you and each of your NTP peers. This varies over time with each sample, and in fact, NTP goes to considerable effort in it's sample filtering to exclude the noisy samples. We need to get that date before it's discarded and contribute it to the entropy cause. You forget; a snooper watching your (ether)net has access to nearly all of this information. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Mark Murray writes: Actually, you could really use this in ntpd(8), rather than just ntpdate. You could crank in the offset and delay samples for each packet received from an NTP peer; this will have the effect of adding into the entropy pool the "noise" in the latency of the path between you and each of your NTP peers. This varies over time with each sample, and in fact, NTP goes to considerable effort in it's sample filtering to exclude the noisy samples. We need to get that date before it's discarded and contribute it to the entropy cause. You forget; a snooper watching your (ether)net has access to nearly all of this information. No, he doesn't have access to the offset from the machines local clock. I ran a quick dirty test here on some logfiles: that offset is very close to white noise. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
People have tried for 30+ years to predict what a quartz xtal will do next. Nobody expects any chance of success. Add to this the need to predict the difference between one or more NTP servers and your local qartz xtal and I think we can safely say "impossible". You can't predict this, but you can _measure_ it with a degree of accuracy. The attacker can use this accuracy to reduce the number of tries in his attack. I think we first need to figure out the security implications. I think the security implications of having no entropy are much worse than having entropy which a truly superhuman *maybe* could guess *some* of the bits in, are far worse. Yarrow addresses this problem; even if the attacker does manage to get the internal state, Yarrow will revover. M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Mark Murray writes: People have tried for 30+ years to predict what a quartz xtal will do next. Nobody expects any chance of success. Add to this the need to predict the difference between one or more NTP servers and your local qartz xtal and I think we can safely say "impossible". You can't predict this, but you can _measure_ it with a degree of accuracy. The attacker can use this accuracy to reduce the number of tries in his attack. No he cannot. The NTP poll period is 64 seconds or longer and unless you have done something special about your hardware, he cannot predict all bits. If he could, ntp would have a longer poll period :-) -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Poul-Henning Kamp wrote: In message [EMAIL PROTECTED], "Jeroen C. van Gelderen" writes : Predicting the clock's offset from reality and the two way path to the server of choice is impossible, plus if people enable authentication later on the packets will be choke full of high-quality entropy. Please quantify 'impossible'. People have tried for 30+ years to predict what a quartz xtal will do next. Nobody expects any chance of success. Add to this the need to predict the difference between one or more NTP servers and your local qartz xtal and I think we can safely say "impossible". See my reply to David Schwartz. What kind of numbers are we talking about? I think we first need to figure out the security implications. I think the security implications of having no entropy are much worse than having entropy which a truly superhuman *maybe* could guess *some* of the bits in, are far worse. I agree, but to paraphrase: that's policy decision. Just quantify it so that people can be their own judge. Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Mon, 17 Jul 2000 16:27:17 MST, "Kurt D. Zeilenga" wrote: Note that there should be no need to cron the job. You're right. My suggestion to use cron's @reboot was as stupid as they come. :-) Sorry, Sheldon. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Poul-Henning Kamp wrote: In message [EMAIL PROTECTED], "Jeroen C. van Gelderen" writes: People have tried for 30+ years to predict what a quartz xtal will do next. Nobody expects any chance of success. Add to this the need to predict the difference between one or more NTP servers and your local qartz xtal and I think we can safely say "impossible". See my reply to David Schwartz. What kind of numbers are we talking about? With microsecond timestamps, 64second ntp poll period we are talking about approx 10 bits of randomness in the received packet and about 3 bits of randomness in the clock difference. FreeBSD uses nanosecond timestamping (Actually could do nanoseconds with 32 bitfractions), but that only adds about 4 bits to the clock difference due to the clock frequency end interrupt hardware. Thanks! This is useful. I think we first need to figure out the security implications. I think the security implications of having no entropy are much worse than having entropy which a truly superhuman *maybe* could guess *some* of the bits in, are far worse. I agree, but to paraphrase: that's policy decision. Just quantify it so that people can be their own judge. No, it is not policy to try to get as many random bits as we can by default. It would be policy to *not* do so for some obscure principle of scientific purity. It's up to the user to decide what security level he needs. Both ought to be possible but having an insecure box ought to be an explicit decision. I think you will agree that there needs to be a decent security level by default. I.e. newly generated SSH host keys are sufficiently secure. Cheers, Jeroen -- Jeroen C. van Gelderen o _ _ _ [EMAIL PROTECTED] _o /\_ _ \\o (_)\__/o (_) _ \_ _(_) (_)/_\_| \ _|/' \/ (_)(_) (_)(_) (_)(_)' _\o_ To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
No, he doesn't have access to the offset from the machines local clock. I ran a quick dirty test here on some logfiles: that offset is very close to white noise. With what amplitude? M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], Mark Murray writes: No, he doesn't have access to the offset from the machines local clock. I ran a quick dirty test here on some logfiles: that offset is very close to white noise. With what amplitude? Depends on the termal environment of your xtal obviously :-) -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
In message [EMAIL PROTECTED], "Jeroen C. van Gelderen" writes It's up to the user to decide what security level he needs. Both ought to be possible but having an insecure box ought to be an explicit decision. Principle of POLA: The box doesn't come up in a stupid configuration right after install. Principle of "tools, not politics": You can configure it stupidly if you want, you can also strengthen it beyond practical use if you want. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 [EMAIL PROTECTED] | TCP/IP since RFC 956 FreeBSD coreteam member | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
Thus spake Louis A. Mamakos ([EMAIL PROTECTED]): Actually, you could really use this in ntpd(8), rather than just ntpdate. Hmm, as addition, I agree. However, I think more people use ntpdate than ntpd, and thus ntpdate is a good place :) Alex -- cat: /home/alex/.sig: No such file or directory To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Sun, 16 Jul 2000, Kris Kennaway wrote: On the other hand, doing a dd if=/dev/random of=/dev/null gives me infinite "randomness" at 10MB/sec - have the semantics of /dev/random changed? Yes. /dev/random is now just an alias for /dev/urandom (or vice versa). You must have a fast machine to get 10MB/sec. I see the following speeds (using a better reading program than dd; dd gives up on EOF on the old /dev/random): old /dev/random on P5/1335K/sec old /dev/urandom on P5/133 244K/sec old /dev/random on Celeron 366 overclocked to 5.5*9525K/sec old /dev/urandom on Celeron 366 overclocked to 5.5*95 970K/sec new /dev/*random on Celeron 400 overclocked to 6.0*75 270K/sec Bruce To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
With microsecond timestamps, 64second ntp poll period we are talking about approx 10 bits of randomness in the received packet and about 3 bits of randomness in the clock difference. FreeBSD uses nanosecond timestamping (Actually could do nanoseconds with 32 bitfractions), but that only adds about 4 bits to the clock difference due to the clock frequency end interrupt hardware. So the attacker is down to 17 bits == 128k guesses. Now that is good entropy, but we need to know what the attacker can see inside the packet etc. How else can he reduce his keyspace? No, it is not policy to try to get as many random bits as we can by default. It would be policy to *not* do so for some obscure principle of scientific purity. Pray explain? M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
On Tue, 18 Jul 2000, Bruce Evans wrote: You must have a fast machine to get 10MB/sec. I see the following speeds (using a better reading program than dd; dd gives up on EOF on the old /dev/random): Oops, I misread the rate by 2 orders of magnitude. I get about 100K/sec on my PPro/233 :-) old /dev/random on P5/1335K/sec old /dev/urandom on P5/133 244K/sec old /dev/random on Celeron 366 overclocked to 5.5*9525K/sec old /dev/urandom on Celeron 366 overclocked to 5.5*95 970K/sec new /dev/*random on Celeron 400 overclocked to 6.0*75 270K/sec Kris -- In God we Trust -- all others must submit an X.509 certificate. -- Charles Forsythe [EMAIL PROTECTED] To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message
Re: randomdev entropy gathering is really weak
I ran a quick dirty test here on some logfiles: that offset is very close to white noise. With what amplitude? Depends on the termal environment of your xtal obviously :-) Help me here! :-) In your observed sample, what was the white noise amplitude? M -- Mark Murray Join the anti-SPAM movement: http://www.cauce.org To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-current" in the body of the message