Re: [PATCH 0/5] Feed entropy pool via high-resolution clocksources
On Sat, Jun 18, 2011 at 03:40:50PM -0700, H. Peter Anvin wrote: On 06/17/2011 01:28 PM, Matt Mackall wrote: The one use case that it is cryptographically insufficient for is to seed a new PRNG, which probably means it is unsuitable for being fed as-is into /dev/random. The thing to understand about the input side of /dev/random is that it's COMPLETELY immune to untrusted data. So there's absolutely no harm in sending it data of questionable entropy so long as you don't tell it to account it. And, of course, if it DOES contain entropy, it makes things better. Think of it this way: I have a coin in my pocket. You, the attacker, tell me to flip it. You can do that any number of times and not improve your guess about the coin's state over your initial guess. This is what it means to have a reversible mixing function: no number of iterations reduces the degrees of freedom of the pool. What I meant is that it is unsuitable to *bypass the pool* for /dev/random. I think we can -- and almost certainly should -- use RDRAND on the input side; we just have to figure out the accounting. From your description of the instruction, this sounds almost identical to me as what I suggested in using an instance of the cprng module in the kernel as the drng coupled with using the tsc entropy as the trng input to reseed it. We could use rnrand when possible on the input to the entropy pool, and the software cprng when that wasn't available. However, RDRAND is high enough quality (and high enough bandwidth) that it should be not just possible but desirable to completely bypass the pool system for /dev/urandom users and pull straight from the RDRAND instruction. I don't actually know what the exact numbers look like, but the stall conditions being looked at are of the order of every core in the socket trying to execute RDRAND at the same time. It sounds to me like, if its desireous to bypass the entropy pool, then we should bypass the /dev/random path altogether. Why not write a hwrng driver that can export access to the rdrand instruction via a misc device. Neil -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 -- 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 0/5] Feed entropy pool via high-resolution clocksources
On Sun, Jun 19, 2011 at 09:38:43AM -0400, Neil Horman wrote: It sounds to me like, if its desireous to bypass the entropy pool, then we should bypass the /dev/random path altogether. Why not write a hwrng driver that can export access to the rdrand instruction via a misc device. I presume the rdrand instruction can be used from user-space directly. Cheers, -- Email: Herbert Xu herb...@gondor.apana.org.au Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- 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 0/5] Feed entropy pool via high-resolution clocksources
On 06/19/2011 08:07 AM, Herbert Xu wrote: On Sun, Jun 19, 2011 at 09:38:43AM -0400, Neil Horman wrote: It sounds to me like, if its desireous to bypass the entropy pool, then we should bypass the /dev/random path altogether. Why not write a hwrng driver that can export access to the rdrand instruction via a misc device. I presume the rdrand instruction can be used from user-space directly. Yes, it can. Again, RDRAND is not suitable for /dev/random (as opposed to /dev/urandom users.) /dev/urandom is used both by user space (and here the only reason to hook it up to /dev/urandom is compatibility with existing userspace; we are working separately to enabling user space users like OpenSSL to use RDRAND directly) and by kernel users via the internal APIs. /dev/random as far as I can tell is only ever fed to userspace, however, the guarantees that it is at least supposed to give are very, very strict. RDRAND do not fulfill those criteria, but we should be able to use it as part of its implementation. -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
Re: [PATCH 0/5] Feed entropy pool via high-resolution clocksources
On 06/17/2011 01:28 PM, Matt Mackall wrote: The one use case that it is cryptographically insufficient for is to seed a new PRNG, which probably means it is unsuitable for being fed as-is into /dev/random. The thing to understand about the input side of /dev/random is that it's COMPLETELY immune to untrusted data. So there's absolutely no harm in sending it data of questionable entropy so long as you don't tell it to account it. And, of course, if it DOES contain entropy, it makes things better. Think of it this way: I have a coin in my pocket. You, the attacker, tell me to flip it. You can do that any number of times and not improve your guess about the coin's state over your initial guess. This is what it means to have a reversible mixing function: no number of iterations reduces the degrees of freedom of the pool. What I meant is that it is unsuitable to *bypass the pool* for /dev/random. I think we can -- and almost certainly should -- use RDRAND on the input side; we just have to figure out the accounting. However, RDRAND is high enough quality (and high enough bandwidth) that it should be not just possible but desirable to completely bypass the pool system for /dev/urandom users and pull straight from the RDRAND instruction. I don't actually know what the exact numbers look like, but the stall conditions being looked at are of the order of every core in the socket trying to execute RDRAND at the same time. -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
Re: [PATCH 0/5] Feed entropy pool via high-resolution clocksources
Matt Mackall wrote: On Wed, 2011-06-15 at 10:49 -0400, Jarod Wilson wrote: Matt Mackall wrote: On Tue, 2011-06-14 at 18:51 -0400, Jarod Wilson wrote: Matt Mackall wrote: ... But that's not even the point. Entropy accounting here is about providing a theoretical level of security above cryptographically strong. As the source says: Even if it is possible to analyze SHA in some clever way, as long as the amount of data returned from the generator is less than the inherent entropy in the pool, the output data is totally unpredictable. This is the goal of the code as it exists. And that goal depends on consistent _underestimates_ and accurate accounting. Okay, so as you noted, I was only crediting one bit of entropy per byte mixed in. Would there be some higher mixed-to-credited ratio that might be sufficient to meet the goal? As I've mentioned elsewhere, I think something around .08 bits per timestamp is probably a good target. That's the entropy content of a coin-flip that is biased to flip heads 99 times out of 100. But even that isn't good enough in the face of a 100Hz clock source. And obviously the current system doesn't handle fractional bits at all. What if only one bit every n samples were credited? So 1/n bits per timestamp, effectively, and for an n of 100, that would yield .01 bits per timestamp. Something like this: Something like that would work, sure. But it's a hack/abuse -relative to the current framework-. I'm reluctant to just pile on the hacks on the current system, as that just means getting it coherent is that much further away. Something I should have probably made clearer was that we were looking for a semi-quick improvement for a particular use case that involves a certain 2.6.32-based kernel... For the short term, we're looking at some userspace alternatives, such as a Linux implementation of an entropy seed approach BSI approves of. Reference doc here, but in German: https://www.bsi.bund.de/ContentBSI/Publikationen/TechnischeRichtlinien/tr02102/index_htm.html Longer-term, we're having some discussions related to the revamped framework you've laid out. I'll table this clocksource-based entropy contribution code for now. Also, thank you for putting up with me. ;) -- 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 0/5] Feed entropy pool via high-resolution clocksources
On Fri, Jun 17, 2011 at 02:51:31PM -0400, Jarod Wilson wrote: Matt Mackall wrote: On Wed, 2011-06-15 at 10:49 -0400, Jarod Wilson wrote: Matt Mackall wrote: On Tue, 2011-06-14 at 18:51 -0400, Jarod Wilson wrote: Matt Mackall wrote: ... But that's not even the point. Entropy accounting here is about providing a theoretical level of security above cryptographically strong. As the source says: Even if it is possible to analyze SHA in some clever way, as long as the amount of data returned from the generator is less than the inherent entropy in the pool, the output data is totally unpredictable. This is the goal of the code as it exists. And that goal depends on consistent _underestimates_ and accurate accounting. Okay, so as you noted, I was only crediting one bit of entropy per byte mixed in. Would there be some higher mixed-to-credited ratio that might be sufficient to meet the goal? As I've mentioned elsewhere, I think something around .08 bits per timestamp is probably a good target. That's the entropy content of a coin-flip that is biased to flip heads 99 times out of 100. But even that isn't good enough in the face of a 100Hz clock source. And obviously the current system doesn't handle fractional bits at all. What if only one bit every n samples were credited? So 1/n bits per timestamp, effectively, and for an n of 100, that would yield .01 bits per timestamp. Something like this: Something like that would work, sure. But it's a hack/abuse -relative to the current framework-. I'm reluctant to just pile on the hacks on the current system, as that just means getting it coherent is that much further away. Something I should have probably made clearer was that we were looking for a semi-quick improvement for a particular use case that involves a certain 2.6.32-based kernel... For the short term, we're looking at some userspace alternatives, such as a Linux implementation of an entropy seed approach BSI approves of. Reference doc here, but in German: https://www.bsi.bund.de/ContentBSI/Publikationen/TechnischeRichtlinien/tr02102/index_htm.html Longer-term, we're having some discussions related to the revamped framework you've laid out. I'll table this clocksource-based entropy contribution code for now. Also, thank you for putting up with me. ;) Not to prolong this conversation, but Matt, since you seem talkative about it, has any consideration been given to using a periodically reseeded DRNG as an input to the entropy pool? some of the papers that Jarod referenced in this thread suggest that using the tsc entropy as a reseed factor to a drng can provide a good non-predictable source of entropy. Thoughts? Neil -- 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 -- 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 0/5] Feed entropy pool via high-resolution clocksources
On 06/14/2011 04:12 PM, Matt Mackall wrote: Various people have offered to spend some time fixing this; I haven't had time to look at it for a while. So on my (long...) list of things to do for a while is enablement of RDRAND, which is a new instruction in Ivy Bridge disclosed in the latest few revisions of the AVX spec and is now in the SDM (the functional description is in vol 1, section 7.3.18 of the May 2011 edition.) Fenghua Yu did an initial enabling patch, but we have had to make some changes. From the SDM: The random numbers that are returned by the RDRAND instruction are supplied by a cryptographically secure Random Number Generator that employs a hardware DRBG (Digital Random Bit Generator, also known as a Pseudo Random Number Generator) seeded by a hardware NRBG (Nondeterministic Random Bit Generator, also known as a TRNG or True Random Number generator). In order for the hardware design to meet its security goals, the random number generator continuously tests itself and the random data it is generating. Runtime failures in the random number generator circuitry or statistically anomalous data occurring by chance will be detected by the self test hardware and flag the resulting data as being bad. In such extremely rare cases, the RDRAND instruction will return no data instead of bad data. Additionally, there is a software enabling guide containing a *lot* more detail at: http://tinyurl.com/6x6dmd2/ This basically means it is similar in behavior to our /dev/urandom in that it may gracefully degrade to a PRNG for short stretches of time, but will not degrade to a PRNG for an extended time, nor will it produce guessable data, ever; instead it will fail shut. The one use case that it is cryptographically insufficient for is to seed a new PRNG, which probably means it is unsuitable for being fed as-is into /dev/random. -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 0/5] Feed entropy pool via high-resolution clocksources
On Fri, 2011-06-17 at 12:48 -0700, h...@zytor.com wrote: On 06/14/2011 04:12 PM, Matt Mackall wrote: Various people have offered to spend some time fixing this; I haven't had time to look at it for a while. So on my (long...) list of things to do for a while is enablement of RDRAND, which is a new instruction in Ivy Bridge disclosed in the latest few revisions of the AVX spec and is now in the SDM (the functional description is in vol 1, section 7.3.18 of the May 2011 edition.) Fenghua Yu did an initial enabling patch, but we have had to make some changes. From the SDM: The random numbers that are returned by the RDRAND instruction are supplied by a cryptographically secure Random Number Generator that employs a hardware DRBG (Digital Random Bit Generator, also known as a Pseudo Random Number Generator) seeded by a hardware NRBG (Nondeterministic Random Bit Generator, also known as a TRNG or True Random Number generator). In order for the hardware design to meet its security goals, the random number generator continuously tests itself and the random data it is generating. Runtime failures in the random number generator circuitry or statistically anomalous data occurring by chance will be detected by the self test hardware and flag the resulting data as being bad. In such extremely rare cases, the RDRAND instruction will return no data instead of bad data. Additionally, there is a software enabling guide containing a *lot* more detail at: http://tinyurl.com/6x6dmd2/ This basically means it is similar in behavior to our /dev/urandom in that it may gracefully degrade to a PRNG for short stretches of time, but will not degrade to a PRNG for an extended time, nor will it produce guessable data, ever; instead it will fail shut. The one use case that it is cryptographically insufficient for is to seed a new PRNG, which probably means it is unsuitable for being fed as-is into /dev/random. The thing to understand about the input side of /dev/random is that it's COMPLETELY immune to untrusted data. So there's absolutely no harm in sending it data of questionable entropy so long as you don't tell it to account it. And, of course, if it DOES contain entropy, it makes things better. Think of it this way: I have a coin in my pocket. You, the attacker, tell me to flip it. You can do that any number of times and not improve your guess about the coin's state over your initial guess. This is what it means to have a reversible mixing function: no number of iterations reduces the degrees of freedom of the pool. -- 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 0/5] Feed entropy pool via high-resolution clocksources
Matt Mackall wrote:
On Tue, 2011-06-14 at 18:51 -0400, Jarod Wilson wrote:
Matt Mackall wrote:
...
But that's not even the point. Entropy accounting here is about
providing a theoretical level of security above cryptographically
strong. As the source says:
Even if it is possible to analyze SHA in some clever way, as long as
the amount of data returned from the generator is less than the inherent
entropy in the pool, the output data is totally unpredictable.
This is the goal of the code as it exists. And that goal depends on
consistent _underestimates_ and accurate accounting.
Okay, so as you noted, I was only crediting one bit of entropy per byte
mixed in. Would there be some higher mixed-to-credited ratio that might
be sufficient to meet the goal?
As I've mentioned elsewhere, I think something around .08 bits per
timestamp is probably a good target. That's the entropy content of a
coin-flip that is biased to flip heads 99 times out of 100. But even
that isn't good enough in the face of a 100Hz clock source.
And obviously the current system doesn't handle fractional bits at all.
What if only one bit every n samples were credited? So 1/n bits per
timestamp, effectively, and for an n of 100, that would yield .01 bits
per timestamp. Something like this:
void add_clocksource_randomness(int clock_delta)
{
static int samples;
/* only mix in the low byte */
u8 mix = clock_delta 0xff;
DEBUG_ENT(clock event %u\n, mix);
preempt_disable();
if (input_pool.entropy_count trickle_thresh
(__get_cpu_var(trickle_count)++ 0xfff))
goto out;
mix_pool_bytes(input_pool, mix, sizeof(mix));
samples++;
/* Only credit one bit per 100 samples to be conservative */
if (samples == 100) {
credit_entropy_bits(input_pool, sizeof(mix));
samples = 0;
}
out:
preempt_enable();
}
Additionally, this function would NOT be exported, it would only be
utilized by a new clocksource entropy contribution function in
kernel/time/clocksource.c. Locally, I've made most of the changes as
discussed with John, so clocksources now have an entropy rating rather
than an entropy function, and if the rating is not high enough, the
clocksource won't be able to add entropy -- all clocksources default to
a rating of 0, only hpet and tsc have been marked otherwise.
Additionally, hpet has a higher rating than tsc, so it'll be preferred
over tsc, even if tsc is the system timer clocksource. This code will
effectively do absolutely nothing if not running on x86 PC hardware with
an hpet or tsc (and it seems maybe tsc shouldn't even be considered, so
perhaps this should be hpet-only).
One further thought: what if reads of both the hpet and tsc were mixed
together to form the sample value actually fed into the entropy pool?
This of course assumes the system has both available, and that the tsc
is actually fine-grained enough to be usable, but maybe it strengthens
the randomness of the sample value at least somewhat?
This could also be marked as experimental or dangerous or what have you,
so that its a kernel builder's conscious decision to enable clock-based
entropy contributions.
(If I appear to be grasping at straws here, well, I probably am.) ;)
Look, I understand what I'm trying to say here is very confusing, so
please make an effort to understand all the pieces together:
- the driver is designed for -perfect- security as described above
- the usual assumptions about observability of network samples and other
timestamps ARE FALSE on COMMON NON-PC HARDWARE
- thus network sampling is incompatible with the CURRENT design
- nonetheless, the current design of entropy accounting is not actually
meeting its goals in practice
Heh, I guess that answers my question already...
- thus we need an alternative to entropy accounting
- that alternative WILL be compatible with sampling insecure sources
Okay. So I admit to really only considering and/or caring about x86
hardware, which doesn't seem to have helped my cause. But you do seem to
be saying that clocksource-based sampling *will* be compatible with the
new alternative, correct? And is said alternative something on the
relatively near-term radar?
Various people have offered to spend some time fixing this; I haven't
had time to look at it for a while.
Okay, I know how that goes. So not likely to come to fruition in the
immediate near-term. I'd offer to spend some time working on it, but I
don't think I'm qualified. :)
--
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 0/5] Feed entropy pool via high-resolution clocksources
On Wed, 2011-06-15 at 10:49 -0400, Jarod Wilson wrote:
Matt Mackall wrote:
On Tue, 2011-06-14 at 18:51 -0400, Jarod Wilson wrote:
Matt Mackall wrote:
...
But that's not even the point. Entropy accounting here is about
providing a theoretical level of security above cryptographically
strong. As the source says:
Even if it is possible to analyze SHA in some clever way, as long as
the amount of data returned from the generator is less than the inherent
entropy in the pool, the output data is totally unpredictable.
This is the goal of the code as it exists. And that goal depends on
consistent _underestimates_ and accurate accounting.
Okay, so as you noted, I was only crediting one bit of entropy per byte
mixed in. Would there be some higher mixed-to-credited ratio that might
be sufficient to meet the goal?
As I've mentioned elsewhere, I think something around .08 bits per
timestamp is probably a good target. That's the entropy content of a
coin-flip that is biased to flip heads 99 times out of 100. But even
that isn't good enough in the face of a 100Hz clock source.
And obviously the current system doesn't handle fractional bits at all.
What if only one bit every n samples were credited? So 1/n bits per
timestamp, effectively, and for an n of 100, that would yield .01 bits
per timestamp. Something like this:
Something like that would work, sure. But it's a hack/abuse -relative
to the current framework-. I'm reluctant to just pile on the hacks on
the current system, as that just means getting it coherent is that much
further away.
The current system says things like I've gotten 20 samples at intervals
that look vaguely random based on their timestamps, I'm calling that 64
bits of entropy. That's enough to reseed! But what it doesn't know is
that those all came from the local network from an attacker with access
to a better clock than us. Or that they all came from an HPET, but the
attacker was directly driving its firing. Or that they came from a
wireless mouse, and the attacker has an RF snooper. So that in the end,
it's only 20 bits of entropy and the attacker can brute-force its way
through the state space. (Yes, this is obviously paranoid, because
that's a ground rule.)
A better framework would say something like I don't actually pretend to
know how to 'measure' entropy, but I've got 1000 samples batched from 4
different subsystems (clock, scheduler, network, block I/O), an attacker
is going to have a very hard time monitoring/predicting all of those,
and even if it's got 99% accuracy per sample on all sources, it's still
got 2^64 work to guess the current state. Let's refresh our pool and
call it full. See?
Here's a sketch. Each subsystem does something like:
add_rng_sample(RNG_NETWORK, some_packet_data);
And that code does something like:
pool = per_cpu(sample_pool);
timestamp = sched_clock();
mix(pool, MAKESAMPLE(sample_data, source, timestamp), sizeof(rng_sample));
pool.sample_count++;
if (!(source pool.source_mask)) {
/* haven't seen this source since last reseed */
pool.source_mask |= source;
pool.source_count++;
/* Do we have enough sample depth and diversity in our per-cpu pool? */
if (pool.sample_count[pool.source_count] threshold[pool.source_count]) {
/* yes, reseed the main pool */
reseed(input_pool, pool, reseed_entropy);
/* empty our sample pool */
pool.sample_count = pool.source_count = pool.source_mask = 0;
}
--
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 0/5] Feed entropy pool via high-resolution clocksources
john stultz wrote: On Mon, 2011-06-13 at 18:06 -0400, Jarod Wilson wrote: Many server systems are seriously lacking in sources of entropy, as we typically only feed the entropy pool by way of input layer events, a few NIC driver interrupts and disk activity. A non-busy server can easily become entropy-starved. We can mitigate this somewhat by periodically mixing in entropy data based on the delta between multiple high-resolution clocksource reads, per: https://www.osadl.org/Analysis-of-inherent-randomness-of-the-L.rtlws11-developers-okech.0.html Additionally, NIST already approves of similar implementations, so this should be usable in high-securtiy deployments requiring a fair chunk of available entropy data for frequent use of /dev/random. http://csrc.nist.gov/groups/STM/cmvp/documents/140-1/140sp/140sp750.pdf (section 6.1 mentions a clock-based seed source). Yes, thus far, I've only bothered with x86-based clocksources, since that is what I can test most easily. If this patch series isn't deemed totally insane, adding support for other clocksources should be trivial. Also note that unless you explicitly build and load the clock-entropy driver, there should be little or no change whatsoever to the way anything behaves right now, its purely opt-in. There's probably room for some improvement here, and I'm kind of outside my comfort area, but hey, it seems to work pretty well here in my own testing, so here it is... Jarod Wilson (5): random: add new clocksource entropy interface clocksource: add support for entropy-generation function hpet: wire up entropy generation function tsc: wire up entropy generation function misc: add clocksource-based entropy generation driver So this is interesting work, but I have a few questions. 1) hpet_add_entropy() and tsc_add_entropy() are basically identical. It seems there should be a generic bit of code that uses the clocksource's read() function and does the same calculation. 2) If the .entropy() functions really aren't clocksource specific, it doesn't really seem like this functionality belongs in the clocksource layer. Instead it seems it should be a layer above, that makes use of the clocksource code in a generic fashion. Wasn't sure at first if there might be a need for more differentiation in the entropy-gathering functions, but yeah, at least with these two, just using the clocksource read function from a common entropy-gathering function does look to make more sense. 3) Why are you making use of the curr_clocksource? The timekeeping code has very strict rules about what makes a clocksource usable for timekeeping. I suspect entropy generation has different requirements, and thus shouldn't lean on the curr_clocksource value (ie: TSC may be unsynced or halts in idle, and thus unusable for time, but likely still ok for entropy). 4) Further on that point, there's a likely bug: If an entropy supporting clocksource is available, clocksource_entropy_available() will return true, but if the one curr_clocksource is not the one that supports entropy, clocksource_add_entropy() won't do anything. I suspect the add_entropy function needs to scan for a entropy flagged clocksource and use it instead. Yeah, there are definitely different requirements. Using curr_clocksource was sort of the easy way out, I guess. :) So yeah, its entirely possible for someone to set a non-entropy-generating clocksource as their active one, and still have an entropy-generating one that is available -- I was actually running tsc as my primary clocksource and using the hpet for entropy in my initial internal implementation here. Each clocksource currently has a rating for how good a timekeeping clocksource it is, would it make sense to have a second rating that indicates how good an entropy source it is, and use that to determine which clocksource would best serve for entropy generation? 5) Does the entropy calculation need to be flagged clocksource by clocksource? Or could a generic metric be made (ie: frequency?) in order to enable such functionality on all capable clocksources automatically? I honestly haven't a clue here. I'm not sure if there are possibly clocksources that have a relatively high frequency, but lack precision in their lowest bits, nor am I sure (yet?) how to figure out what the frequency and/or precision of a given clocksource actually is. I guess I assume its non-trivial, since we have to have the 'rating' value to choose primary timekeeping clocksource. My initial thinking is that it would be best to have this purely opt-in, for clocksources that have been evaluated and deemed acceptable for this use. So I'll see what I can come up with in the way of removing the per-clocksource entropy functions. Doing so adds a new complication, by way of removing what I was keying off of to decide if the clocksource should be providing entropy, but perhaps I can try working in an entropy quality rating at the same
Re: [PATCH 0/5] Feed entropy pool via high-resolution clocksources
On Mon, 2011-06-13 at 18:06 -0400, Jarod Wilson wrote: Many server systems are seriously lacking in sources of entropy, as we typically only feed the entropy pool by way of input layer events, a few NIC driver interrupts and disk activity. A non-busy server can easily become entropy-starved. We can mitigate this somewhat by periodically mixing in entropy data based on the delta between multiple high-resolution clocksource reads, per: https://www.osadl.org/Analysis-of-inherent-randomness-of-the-L.rtlws11-developers-okech.0.html Additionally, NIST already approves of similar implementations, so this should be usable in high-securtiy deployments requiring a fair chunk of available entropy data for frequent use of /dev/random. So, mixed feelings here: Yes: it's a great idea to regularly mix other data into the pool. More samples are always better for RNG quality. Maybe: the current RNG is not really designed with high-bandwidth entropy sources in mind, so this might introduce non-negligible overhead in systems with, for instance, huge numbers of CPUs. No: it's not a great idea to _credit_ the entropy count with this data. Someone watching the TSC or HPET from userspace can guess when samples are added by watching for drop-outs in their sampling (ie classic timing attack). (I see you do credit only 1 bit per byte: that's fairly conservative, true, but it must be _perfectly conservative_ for the theoretical requirements of /dev/random to be met. These requirements are in fact known to be unfulfillable in practice(!), but that doesn't mean we should introduce more users of entropy accounting. Instead, it means that entropy accounting is broken and needs to be removed.) http://csrc.nist.gov/groups/STM/cmvp/documents/140-1/140sp/140sp750.pdf (section 6.1 mentions a clock-based seed source). Yes, thus far, I've only bothered with x86-based clocksources, since that is what I can test most easily. If this patch series isn't deemed totally insane, adding support for other clocksources should be trivial. Also note that unless you explicitly build and load the clock-entropy driver, there should be little or no change whatsoever to the way anything behaves right now, its purely opt-in. There's probably room for some improvement here, and I'm kind of outside my comfort area, but hey, it seems to work pretty well here in my own testing, so here it is... Jarod Wilson (5): random: add new clocksource entropy interface clocksource: add support for entropy-generation function hpet: wire up entropy generation function tsc: wire up entropy generation function misc: add clocksource-based entropy generation driver arch/x86/kernel/hpet.c | 18 ++ arch/x86/kernel/tsc.c| 18 ++ drivers/char/random.c| 28 ++ drivers/misc/Kconfig | 14 + drivers/misc/Makefile|1 + drivers/misc/clock-entropy.c | 122 ++ include/linux/clocksource.h |6 ++ include/linux/random.h |1 + kernel/time/clocksource.c| 33 +++ 9 files changed, 241 insertions(+), 0 deletions(-) create mode 100644 drivers/misc/clock-entropy.c CC: Matt Mackall m...@selenic.com CC: Venkatesh Pallipadi (Venki) ve...@google.com CC: Thomas Gleixner t...@linutronix.de CC: Ingo Molnar mi...@elte.hu CC: John Stultz johns...@us.ibm.com CC: Herbert Xu herb...@gondor.apana.org.au CC: David S. Miller da...@davemloft.net -- 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 0/5] Feed entropy pool via high-resolution clocksources
Jarod Wilson wrote: Matt Mackall wrote: On Mon, 2011-06-13 at 18:06 -0400, Jarod Wilson wrote: Many server systems are seriously lacking in sources of entropy, as we typically only feed the entropy pool by way of input layer events, a few NIC driver interrupts and disk activity. A non-busy server can easily become entropy-starved. We can mitigate this somewhat by periodically mixing in entropy data based on the delta between multiple high-resolution clocksource reads, per: https://www.osadl.org/Analysis-of-inherent-randomness-of-the-L.rtlws11-developers-okech.0.html Additionally, NIST already approves of similar implementations, so this should be usable in high-securtiy deployments requiring a fair chunk of available entropy data for frequent use of /dev/random. So, mixed feelings here: Yes: it's a great idea to regularly mix other data into the pool. More samples are always better for RNG quality. Maybe: the current RNG is not really designed with high-bandwidth entropy sources in mind, so this might introduce non-negligible overhead in systems with, for instance, huge numbers of CPUs. The current implementation is opt-in, and single-threaded, so at least currently, I don't think there should be any significant issues. I stand corrected. Hadn't considered the possible issues with doing a regular preempt_disable() and __get_cpu_var() on a system with tons of cpus. (I'm still not sure exactly what the issues would be, but I think I see the potential for issues of some sort.) -- 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 0/5] Feed entropy pool via high-resolution clocksources
On Tue, 2011-06-14 at 11:18 -0400, Jarod Wilson wrote: Matt Mackall wrote: On Mon, 2011-06-13 at 18:06 -0400, Jarod Wilson wrote: Many server systems are seriously lacking in sources of entropy, as we typically only feed the entropy pool by way of input layer events, a few NIC driver interrupts and disk activity. A non-busy server can easily become entropy-starved. We can mitigate this somewhat by periodically mixing in entropy data based on the delta between multiple high-resolution clocksource reads, per: https://www.osadl.org/Analysis-of-inherent-randomness-of-the-L.rtlws11-developers-okech.0.html Additionally, NIST already approves of similar implementations, so this should be usable in high-securtiy deployments requiring a fair chunk of available entropy data for frequent use of /dev/random. So, mixed feelings here: Yes: it's a great idea to regularly mix other data into the pool. More samples are always better for RNG quality. Maybe: the current RNG is not really designed with high-bandwidth entropy sources in mind, so this might introduce non-negligible overhead in systems with, for instance, huge numbers of CPUs. The current implementation is opt-in, and single-threaded, so at least currently, I don't think there should be any significant issues. But yeah, there's nothing currently in the implementation preventing a variant that is per-cpu, which could certainly lead to some scalability issues. The pool itself is single-threaded. On large-ish machines (100+ CPUs), we've seen contention rise to 60% or more. Hence the addition of the trickle threshold. But I can see that breaking down with a lot more writers. No: it's not a great idea to _credit_ the entropy count with this data. Someone watching the TSC or HPET from userspace can guess when samples are added by watching for drop-outs in their sampling (ie classic timing attack). I'm admittedly a bit of a novice in this area... Why does it matter if someone watching knows more or less when a sample is added? It doesn't really reveal anything about the sample itself, if we're using a high-granularity counter value's low bits -- round-trip to userspace has all sorts of inherent timing jitter, so determining the low-order bits the kernel got by monitoring from userspace should be more or less impossible. And the pool is constantly changing, making it a less static target on an otherwise mostly idle system. I recommend you do some Google searches for ssl timing attack and aes timing attack to get a feel for the kind of seemingly impossible things that can be done and thereby recalibrate your scale of the impossible. (I see you do credit only 1 bit per byte: that's fairly conservative, true, but it must be _perfectly conservative_ for the theoretical requirements of /dev/random to be met. These requirements are in fact known to be unfulfillable in practice(!), but that doesn't mean we should introduce more users of entropy accounting. Instead, it means that entropy accounting is broken and needs to be removed.) Hrm. The government seems to have a different opinion. Various certs have requirements for some sort of entropy accounting and minimum estimated entropy guarantees. We can certainly be even more conservative than 1 bit per byte, but yeah, I don't really have a good answer for perfectly conservative, and I don't know what might result (on the government cert front) from removing entropy accounting altogether... Well, the deal with accounting is this: if you earn $.90 and spend $1.00 every day, you'll eventually go broke, even if your rounded-to-the-nearest-dollar accounting tells you you're solidly in the black. The only distinction between /dev/random and urandom is that we claim that /dev/random is always solidly in the black. But as we don't have a firm theoretical basis for making our accounting estimates on the input side, the whole accounting thing kind of breaks down into a kind of busted rate-limiter. We'd do better counting a raw number of samples per source, and then claiming that we've reached a 'full' state when we reach a certain 'diversity x depth' score. And then assuring we have a lot of diversity and depth going into the pool. Any thoughts on the idea of mixing clocksource bits with reads from ansi_cprng? Useless. The definition of entropy here can be thought of as 'log(volume of state space that can't be observed by an attacker)'. There is nothing we can do algorithmically to a sample that will increase that volume, we can only shrink it! And any function that is not completely reversible (aka 1:1) will in fact shrink that volume, so you have to be very careful here. The mixing primitives are already quite solid, no need to layer on more potentially faulty ones. -- Mathematics is the supreme nostalgia of our time. -- To unsubscribe from this list: send the line unsubscribe linux-crypto in the body of a
Re: [PATCH 0/5] Feed entropy pool via high-resolution clocksources
Matt Mackall wrote: On Tue, 2011-06-14 at 11:18 -0400, Jarod Wilson wrote: Matt Mackall wrote: ... No: it's not a great idea to _credit_ the entropy count with this data. Someone watching the TSC or HPET from userspace can guess when samples are added by watching for drop-outs in their sampling (ie classic timing attack). I'm admittedly a bit of a novice in this area... Why does it matter if someone watching knows more or less when a sample is added? It doesn't really reveal anything about the sample itself, if we're using a high-granularity counter value's low bits -- round-trip to userspace has all sorts of inherent timing jitter, so determining the low-order bits the kernel got by monitoring from userspace should be more or less impossible. And the pool is constantly changing, making it a less static target on an otherwise mostly idle system. I recommend you do some Google searches for ssl timing attack and aes timing attack to get a feel for the kind of seemingly impossible things that can be done and thereby recalibrate your scale of the impossible. Hm. These are attempting to reveal a static key though. We're talking about trying to reveal the exact value of the counter when it was read by the kernel. And trying to do so repeatedly, several times per second. And this can't be done without getting some form of local system access, so far as I know. And the act of trying to monitor and calculate deltas should serve to introduce even more potential randomness into the actual clock read deltas. This code is largely spurned on by someone here at Red Hat who I probably should have had in the cc list to begin with, Steve Grubb, who pointed to slides 23-25 and the chart in slide 30 of this doc... https://www.osadl.org/fileadmin/dam/presentations/RTLWS11/okech-inherent-randomness.pdf ...as the primary arguments for why this is a good source of entropy. (I see you do credit only 1 bit per byte: that's fairly conservative, true, but it must be _perfectly conservative_ for the theoretical requirements of /dev/random to be met. These requirements are in fact known to be unfulfillable in practice(!), but that doesn't mean we should introduce more users of entropy accounting. Instead, it means that entropy accounting is broken and needs to be removed.) Hrm. The government seems to have a different opinion. Various certs have requirements for some sort of entropy accounting and minimum estimated entropy guarantees. We can certainly be even more conservative than 1 bit per byte, but yeah, I don't really have a good answer for perfectly conservative, and I don't know what might result (on the government cert front) from removing entropy accounting altogether... Well, the deal with accounting is this: if you earn $.90 and spend $1.00 every day, you'll eventually go broke, even if your rounded-to-the-nearest-dollar accounting tells you you're solidly in the black. The only distinction between /dev/random and urandom is that we claim that /dev/random is always solidly in the black. But as we don't have a firm theoretical basis for making our accounting estimates on the input side, the whole accounting thing kind of breaks down into a kind of busted rate-limiter. Well, they *are* understood to be estimates, and /dev/random does block when we've spent everything we've (estimated we've) got, and at least circa 2.6.18 in RHEL5.4, NIST was satisfied that /dev/random's estimation was good enough by way of some statistical analysis done on data dumped out of it. What if we could show through statistical analysis that our entropy estimation is still good enough even with clock data mixed in? (Ignoring the potential of timing attacks for the moment). We'd do better counting a raw number of samples per source, and then claiming that we've reached a 'full' state when we reach a certain 'diversity x depth' score. And then assuring we have a lot of diversity and depth going into the pool. Hrm. I presume NIST and friends would still need some way to translate that into estimated bits of entropy for the purposes of having a common metric with other systems, but I guess we could feel better about the entropy if we had some sort of guarantee that no more than x% came from a single entropy source -- such as, say, no more than 25% of your entropy bits are from a clocksource. But then we may end up right back where we are right now -- a blocking entropy-starved /dev/random on a server system that has no other significant sources generating entropy. -- 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 0/5] Feed entropy pool via high-resolution clocksources
Matt Mackall wrote: On Tue, 2011-06-14 at 16:17 -0400, Jarod Wilson wrote: Matt Mackall wrote: On Tue, 2011-06-14 at 11:18 -0400, Jarod Wilson wrote: Matt Mackall wrote: ... No: it's not a great idea to _credit_ the entropy count with this data. Someone watching the TSC or HPET from userspace can guess when samples are added by watching for drop-outs in their sampling (ie classic timing attack). I'm admittedly a bit of a novice in this area... Why does it matter if someone watching knows more or less when a sample is added? It doesn't really reveal anything about the sample itself, if we're using a high-granularity counter value's low bits -- round-trip to userspace has all sorts of inherent timing jitter, so determining the low-order bits the kernel got by monitoring from userspace should be more or less impossible. And the pool is constantly changing, making it a less static target on an otherwise mostly idle system. I recommend you do some Google searches for ssl timing attack and aes timing attack to get a feel for the kind of seemingly impossible things that can be done and thereby recalibrate your scale of the impossible. Hm. These are attempting to reveal a static key though. We're talking about trying to reveal the exact value of the counter when it was read by the kernel. And trying to do so repeatedly, several times per second. I read this as I am not yet properly recalibrated. Probably not. :) Yes, it's hard. Hard != impractical. And this can't be done without getting some form of local system access, Ok, now Google remote timing attack. The stuff I'm reading seems to require that the data you're trying to discern is somehow exposed over the network, which so far as I know, the entropy input pool isn't, but you obviously know this stuff WAY better than I do, so I'll stop trying. ;) This code is largely spurned on by someone here at Red Hat who I probably should have had in the cc list to begin with, Steve Grubb, who pointed to slides 23-25 and the chart in slide 30 of this doc... https://www.osadl.org/fileadmin/dam/presentations/RTLWS11/okech-inherent-randomness.pdf ...as the primary arguments for why this is a good source of entropy. ..on a sixth-generation desktop CPU with a cycle-accurate counter. Welcome to the real world, where that's now a tiny minority of deployed systems. Sure, but that's part of why only the hpet and tsc clocksources were wired up in this patchset. But that's not even the point. Entropy accounting here is about providing a theoretical level of security above cryptographically strong. As the source says: Even if it is possible to analyze SHA in some clever way, as long as the amount of data returned from the generator is less than the inherent entropy in the pool, the output data is totally unpredictable. This is the goal of the code as it exists. And that goal depends on consistent _underestimates_ and accurate accounting. Okay, so as you noted, I was only crediting one bit of entropy per byte mixed in. Would there be some higher mixed-to-credited ratio that might be sufficient to meet the goal? Look, I understand what I'm trying to say here is very confusing, so please make an effort to understand all the pieces together: - the driver is designed for -perfect- security as described above - the usual assumptions about observability of network samples and other timestamps ARE FALSE on COMMON NON-PC HARDWARE - thus network sampling is incompatible with the CURRENT design - nonetheless, the current design of entropy accounting is not actually meeting its goals in practice Heh, I guess that answers my question already... - thus we need an alternative to entropy accounting - that alternative WILL be compatible with sampling insecure sources Okay. So I admit to really only considering and/or caring about x86 hardware, which doesn't seem to have helped my cause. But you do seem to be saying that clocksource-based sampling *will* be compatible with the new alternative, correct? And is said alternative something on the relatively near-term radar? -- 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
[PATCH 0/5] Feed entropy pool via high-resolution clocksources
Many server systems are seriously lacking in sources of entropy, as we typically only feed the entropy pool by way of input layer events, a few NIC driver interrupts and disk activity. A non-busy server can easily become entropy-starved. We can mitigate this somewhat by periodically mixing in entropy data based on the delta between multiple high-resolution clocksource reads, per: https://www.osadl.org/Analysis-of-inherent-randomness-of-the-L.rtlws11-developers-okech.0.html Additionally, NIST already approves of similar implementations, so this should be usable in high-securtiy deployments requiring a fair chunk of available entropy data for frequent use of /dev/random. http://csrc.nist.gov/groups/STM/cmvp/documents/140-1/140sp/140sp750.pdf (section 6.1 mentions a clock-based seed source). Yes, thus far, I've only bothered with x86-based clocksources, since that is what I can test most easily. If this patch series isn't deemed totally insane, adding support for other clocksources should be trivial. Also note that unless you explicitly build and load the clock-entropy driver, there should be little or no change whatsoever to the way anything behaves right now, its purely opt-in. There's probably room for some improvement here, and I'm kind of outside my comfort area, but hey, it seems to work pretty well here in my own testing, so here it is... Jarod Wilson (5): random: add new clocksource entropy interface clocksource: add support for entropy-generation function hpet: wire up entropy generation function tsc: wire up entropy generation function misc: add clocksource-based entropy generation driver arch/x86/kernel/hpet.c | 18 ++ arch/x86/kernel/tsc.c| 18 ++ drivers/char/random.c| 28 ++ drivers/misc/Kconfig | 14 + drivers/misc/Makefile|1 + drivers/misc/clock-entropy.c | 122 ++ include/linux/clocksource.h |6 ++ include/linux/random.h |1 + kernel/time/clocksource.c| 33 +++ 9 files changed, 241 insertions(+), 0 deletions(-) create mode 100644 drivers/misc/clock-entropy.c CC: Matt Mackall m...@selenic.com CC: Venkatesh Pallipadi (Venki) ve...@google.com CC: Thomas Gleixner t...@linutronix.de CC: Ingo Molnar mi...@elte.hu CC: John Stultz johns...@us.ibm.com CC: Herbert Xu herb...@gondor.apana.org.au CC: David S. Miller da...@davemloft.net -- 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
