Re: [PATCH 4/5] tsc: wire up entropy generation function
On Mon, 13 Jun 2011, Venkatesh Pallipadi wrote: On Mon, Jun 13, 2011 at 3:06 PM, Jarod Wilson ja...@redhat.com wrote: TSC is high enough resolution that we can use its low-order byte to stir new data into the random number generator entropy pool. From what I vaguely remember from years past, rdtsc, especially last few bits of it are not very good as random number source. As they are based on lower bus frequency and a multiplier. May be things have changed these days. Adding Peter and Suresh for comments. Recommended reading: https://www.osadl.org/fileadmin/dam/rtlws/12/Okech.pdf Thanks, tglx -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
H. Peter Anvin wrote: Those already are doing this. They used to via IRQF_SAMPLE_RANDOM, but these are being removed (according to Documentation/feature-removal-schedule.txt). In 2.6.39 I can only find 10 remaining instances, out of many more network drivers. The alternative is supposed to be calls to add_*_randomness(), but that family of functions seems to only have one exported symbol: add_input_randomness(), which looks like is called only for things dealing with human input. So network entropy is being eradicated, and nothing is being done to replace it. This is crazy. Consider the case where the TSC is running in steps of 64 and you're using the low 6 bits. It does that? I thought it was a time stamp counter, that is incremented. You know, incremented by one. (Why would someone have it jump by 64? Wiring it up on the cheap side of the clock multiplier? What chips do that?) Maybe this patch is not sensible. If it is only going to be called on timer, then there is the feedback issue that will badly limit the entropy, and if a TSC is sometimes only jumping in big steps, then the available entropy is being masked. Let me fall back to a different (but related) topic: eradicating IRQF_SAMPLE_RANDOM is stupid. The only argument in favor seems to be that the entropy estimation might be too high. But entropy estimation is never going to be accurate. Better to credit no entropy than to collect no entropy. -kb -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
H. Peter Anvin wrote: On 06/13/2011 05:39 PM, Kent Borg wrote: I was assuming that drivers, responding to an interrupt from some external event, would want to make this call. Such as a network driver. Those already are doing this. Two points: 1. Why look at the high-order bits? How are they going to have values that cannot be inferred? If you are looking for entropy, the low-order bits is where they're going keep it. (Think Willie Sutton.) If looking at the low-byte is cheaper, then let's be cheap. If, however, if looking at more bytes *is* as cheap, then there is no harm. But in any case let's keep the code lean enough that it can be called from an interrupt service routine. Consider the case where the TSC is running in steps of 64 and you're using the low 6 bits. What if we mix the low byte into the pool, but only increase the entropy estimate if a comparison with the prior read actually shows a change? Another thought is to perhaps mix the counter value with a value read from ansi_cprng, which is similar to a tactic referred to in NIST's 140sp750.pdf. Peter, as long as I've got your attention here... Patch 3 in the set adds essentially the same sort of support using the hpet instead of the tsc. Is that less contentious, as far as precision in the low byte(s) to provide entropy data? My initial local implementation was actually hpet-only, before reworking things to try to be more generic. -- Jarod Wilson ja...@redhat.com -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
On Tue, 2011-06-14 at 08:39 -0400, Kent Borg wrote: H. Peter Anvin wrote: Those already are doing this. They used to via IRQF_SAMPLE_RANDOM, but these are being removed (according to Documentation/feature-removal-schedule.txt). In 2.6.39 I can only find 10 remaining instances, out of many more network drivers. That's down from three. Oh wait, that's up. So network entropy is being eradicated, and nothing is being done to replace it. Nothing is being done is a more accurate summary of the situation. -- Mathematics is the supreme nostalgia of our time. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
Matt Mackall wrote: Kent Borg wrote: So network entropy is being eradicated, and nothing is being done to replace it. Nothing is being done is a more accurate summary of the situation. So the feature-removal-schedule.txt entry about IRQF_SAMPLE_RANDOM is obsolete? (Then the trend from three network drivers to ten network drivers should be accelerated and restore we should restore the deleted instances of IRQF_SAMPLE_RANDOM??) -kb, the Kent who sees network adapter interrupt timing as a usually good source of entropy. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
On Tue, 2011-06-14 at 13:48 -0400, Kent Borg wrote: Matt Mackall wrote: Kent Borg wrote: So network entropy is being eradicated, and nothing is being done to replace it. Nothing is being done is a more accurate summary of the situation. So the feature-removal-schedule.txt entry about IRQF_SAMPLE_RANDOM is obsolete? (Then the trend from three network drivers to ten network drivers should be accelerated and restore we should restore the deleted instances of IRQF_SAMPLE_RANDOM??) -kb, the Kent who sees network adapter interrupt timing as a usually good source of entropy. It's a great source of potential entropy, a bad source of guaranteed entropy. The current RNG tries to do accounting on the latter. Accounting on the former is extremely suspect. -- Mathematics is the supreme nostalgia of our time. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
On 06/13/2011 04:10 PM, Matt Mackall wrote: Well the issue is that samples are going to be roughly aligned to some multiple of the bus frequency. If an interrupt occurs on bus cycle X, this code will be hit at roughly TSC cycle X*M+d. This is correct; at the very least I would multiply the low 32 bits of the TSC with a 32-bit prime number before mixing. This multiply doesn't actually accomplish anything. Mixing known values into the pool is harmless because the mixing function is fully reversable. ie: unmix(sample, mix(sample, pool)) = pool If you didn't know the contents of pool before, you can't guess it after. The danger comes if you (a) already know pool and (b) can narrow sample to a tractable set of values. Then you can calculate a set of possible pool' values and compare the resulting output to confirm the actual state of pool' (aka state extension attack). Sticking a constant multiplier on sample doesn't affect this attack at all. It only matters if you actually truncate it to LSBs. However, the big issue with this is that it's recursive... what causes this to be invoked... probably an interrupt, which is going to have been invoked by a timer, quite possible the TSC deadline timer. Oops. ..and the sampling function already mixes in a TSC timestamp with the provided timestamp. Right. -hpa -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
Matt Mackall wrote: [network adapters are] a great source of potential entropy, a bad source of guaranteed entropy. The current RNG tries to do accounting on the latter. Accounting on the former is extremely suspect. So we need a patch that: - Deletes the IRQF_SAMPLE_RANDOM mention in feature-removal-schedule.txt, - Restores instances of IRQF_SAMPLE_RANDOM in drivers, and - Changes the credit_entropy_bits() to credit less entropy*. * The code seems to only handle integer values of entropy. Maybe when crediting, choose between 1 and 0 credits. Then once that kernel makes it into the field, a bunch of entropy starved machines will no longer be entropy starved. A few machines that are run by people who worship an entropy estimate will still have to install mice and users, explicit RNGs, etc., but entropy will flow. Make sense? -kb -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 4/5] tsc: wire up entropy generation function
On 06/13/2011 05:39 PM, Kent Borg wrote: I was assuming that drivers, responding to an interrupt from some external event, would want to make this call. Such as a network driver. Those already are doing this. Two points: 1. Why look at the high-order bits? How are they going to have values that cannot be inferred? If you are looking for entropy, the low-order bits is where they're going keep it. (Think Willie Sutton.) If looking at the low-byte is cheaper, then let's be cheap. If, however, if looking at more bytes *is* as cheap, then there is no harm. But in any case let's keep the code lean enough that it can be called from an interrupt service routine. Consider the case where the TSC is running in steps of 64 and you're using the low 6 bits. -hpa -- H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
