| Message ID | 9c2a0549519b4eb5eee2d5d480f8e83a574273df.1405620944.git.luto@amacapital.net (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
On Thu, Jul 17, 2014 at 11:22:17AM -0700, Andy Lutomirski wrote: > Currently, init_std_data contains its own logic for using arch > random sources. This logic is a bit strange: it reads one long of > arch random data per byte of internal state. This isn't true. Check out the init_std_data() a bit more closely. unsigned long rv; ... for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { ... In particular, note the "i -= sizeof(rv)". We are reading one bit per bit of internal state beeing seeded. > Assuming the arch sources are perfect, this is the right thing to > do. They're not, though, so the followup patch attempts to > implement the correct logic on x86. ... and that's not a problem because we aren't giving any entropy credit --- and this is deliberate, because we don't want to trust un-auditable hardware. We are deliberately trying to be conservative here. So I don't think either this patch or the next one is needed. It adds far more complexity than is warranted. Regards, - Ted -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Jul 22, 2014 at 6:59 AM, Theodore Ts'o <tytso@mit.edu> wrote: > On Thu, Jul 17, 2014 at 11:22:17AM -0700, Andy Lutomirski wrote: >> Currently, init_std_data contains its own logic for using arch >> random sources. This logic is a bit strange: it reads one long of >> arch random data per byte of internal state. > > This isn't true. Check out the init_std_data() a bit more closely. > > unsigned long rv; > > ... > > for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { > ... > > In particular, note the "i -= sizeof(rv)". We are reading one bit per > bit of internal state beeing seeded. Whoops, my bad. > >> Assuming the arch sources are perfect, this is the right thing to >> do. They're not, though, so the followup patch attempts to >> implement the correct logic on x86. > > ... and that's not a problem because we aren't giving any entropy > credit --- and this is deliberate, because we don't want to trust > un-auditable hardware. We are deliberately trying to be conservative > here. True. But, if you Intel's hardware does, in fact, work as documented, then the current code will collect very little entropy on RDSEED-less hardware. I see no great reason that we should do something weaker than following Intel's explicit recommendation for how to seed a PRNG from RDRAND. > > So I don't think either this patch or the next one is needed. It adds > far more complexity than is warranted. The real reason I did this is because I didn't want to pollute the kernel with yet more arch_get_random_xyz functions. In the previous iteration of this patchset, init_std_data had to deal with no less than three arch random sources. If Xen adds something (which, IMO, they should), then either it'll be up to four, or one of them will have to multiplex. Another benefit of this split is that it will potentially allow arch_get_rng_seed to be made to work before alternatives are run. There's no fundamental reason that it couldn't work *extremely* early in boot. (The KASLR code is an example of how this might work.) On the other hand, making arch_get_random_long work very early in boot would either slow down all the other callers or add a considerable amount of extra complexity. So I think that this patch is a slight improvement in RNG initialization and will actually result in simpler code. (And yes, if I submit a new version of it, I'll fix the changelog.) --Andy -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 07/22/2014 01:44 PM, Andy Lutomirski wrote: > > But, if you Intel's hardware does, in fact, work as documented, then > the current code will collect very little entropy on RDSEED-less > hardware. I see no great reason that we should do something weaker > than following Intel's explicit recommendation for how to seed a PRNG > from RDRAND. > Very little entropy in the architectural worst case. However, since we are running single-threaded at this point, actual hardware performs orders of magnitude better. Since we run the mixing function (for no particularly good reason -- it is a linear function and doesn't add security) there will be enough delay that RDRAND will in practice catch up and the output will be quite high quality. Since the pool is quite large, the likely outcome is that there will be enough randomness that in practice we would probably be okay if *no* further entropy was ever collected. > Another benefit of this split is that it will potentially allow > arch_get_rng_seed to be made to work before alternatives are run. > There's no fundamental reason that it couldn't work *extremely* early > in boot. (The KASLR code is an example of how this might work.) On > the other hand, making arch_get_random_long work very early in boot > would either slow down all the other callers or add a considerable > amount of extra complexity. > > So I think that this patch is a slight improvement in RNG > initialization and will actually result in simpler code. (And yes, if > I submit a new version of it, I'll fix the changelog.) There really isn't any significant reason why we could not permit randomness initialization very early in the boot, indeed. It has largely been useless in the past because until the I/O system gets initialized there is no randomness of any kind available on traditional hardware. -hpa -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Jul 22, 2014 at 1:57 PM, H. Peter Anvin <hpa@zytor.com> wrote: > On 07/22/2014 01:44 PM, Andy Lutomirski wrote: >> >> But, if you Intel's hardware does, in fact, work as documented, then >> the current code will collect very little entropy on RDSEED-less >> hardware. I see no great reason that we should do something weaker >> than following Intel's explicit recommendation for how to seed a PRNG >> from RDRAND. >> > > Very little entropy in the architectural worst case. However, since we > are running single-threaded at this point, actual hardware performs > orders of magnitude better. Since we run the mixing function (for no > particularly good reason -- it is a linear function and doesn't add > security) there will be enough delay that RDRAND will in practice catch > up and the output will be quite high quality. Since the pool is quite > large, the likely outcome is that there will be enough randomness that > in practice we would probably be okay if *no* further entropy was ever > collected. Just to check: do you mean the RDRAND is very likely to work (i.e. arch_get_random_long will return true) or that RDRAND will actually reseed several times during initialization? I have no RDRAND-capable hardware, so I can't benchmark it, but I imagine that we're talking about adding 1-2 ms per boot to ensure that the pool is filled to capacity with *NRBG* data according to the the architectural specification. Anyway, the current code is IMO very much encoding some form of knowledge of how arch_get_random_* work into init_std_data, and I don't think that's the place for it. > >> Another benefit of this split is that it will potentially allow >> arch_get_rng_seed to be made to work before alternatives are run. >> There's no fundamental reason that it couldn't work *extremely* early >> in boot. (The KASLR code is an example of how this might work.) On >> the other hand, making arch_get_random_long work very early in boot >> would either slow down all the other callers or add a considerable >> amount of extra complexity. >> >> So I think that this patch is a slight improvement in RNG >> initialization and will actually result in simpler code. (And yes, if >> I submit a new version of it, I'll fix the changelog.) > > There really isn't any significant reason why we could not permit > randomness initialization very early in the boot, indeed. It has > largely been useless in the past because until the I/O system gets > initialized there is no randomness of any kind available on traditional > hardware. To me, the question is whether this is a sufficient reason to add arch_get_rng_data. If it is, then great. If not, then I'd like to know what other way of doing this would be acceptable. You disliked arch_get_slow_rng_u64 or whatever I called it, and I agree -- I think it sucked. --Andy -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 07/22/2014 02:04 PM, Andy Lutomirski wrote: > > Just to check: do you mean the RDRAND is very likely to work (i.e. > arch_get_random_long will return true) or that RDRAND will actually > reseed several times during initialization? > I mean that RDRAND will actually reseed several times during initialization. The documented architectural limit is actually extremely conservative. Either way, it isn't really different from seeding from a VM hosts /dev/urandom... -hpa -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Jul 22, 2014 at 2:08 PM, H. Peter Anvin <hpa@zytor.com> wrote: > On 07/22/2014 02:04 PM, Andy Lutomirski wrote: >> >> Just to check: do you mean the RDRAND is very likely to work (i.e. >> arch_get_random_long will return true) or that RDRAND will actually >> reseed several times during initialization? >> > > I mean that RDRAND will actually reseed several times during > initialization. The documented architectural limit is actually > extremely conservative. > > Either way, it isn't really different from seeding from a VM hosts > /dev/urandom... > Sure it is. The VM host's /dev/urandom makes no guarantee (or AFAIK even any particular effort) to reseed such that the output has some minimum entropy per bit, so there would be no point to reading extra data from it. Anyway, I'd be willing to drop the conservative RDRAND logic, but I *still* think that arch_get_rng_seed is a much better interface than arch_get_slow_rng_u64. --Andy -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 07/22/2014 02:10 PM, Andy Lutomirski wrote: > On Tue, Jul 22, 2014 at 2:08 PM, H. Peter Anvin <hpa@zytor.com> wrote: >> On 07/22/2014 02:04 PM, Andy Lutomirski wrote: >>> >>> Just to check: do you mean the RDRAND is very likely to work (i.e. >>> arch_get_random_long will return true) or that RDRAND will actually >>> reseed several times during initialization? >>> >> >> I mean that RDRAND will actually reseed several times during >> initialization. The documented architectural limit is actually >> extremely conservative. >> >> Either way, it isn't really different from seeding from a VM hosts >> /dev/urandom... > > Sure it is. The VM host's /dev/urandom makes no guarantee (or AFAIK > even any particular effort) to reseed such that the output has some > minimum entropy per bit, so there would be no point to reading extra > data from it. Depends on what you define as "extra data". If the data pulled is less than the size of the output pool, it *may* be fully entropic. (Fun fact: it may even have been fully entropic at the time you pull it, but then turn out not to be later because *another* process consumed data from /dev/urandom without adequate reseeding.) > Anyway, I'd be willing to drop the conservative RDRAND logic, but I > *still* think that arch_get_rng_seed is a much better interface than > arch_get_slow_rng_u64. That I will leave up to you and Ted. -hpa -- To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/drivers/char/random.c b/drivers/char/random.c index 0a7ac0a..be7a94e 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1236,6 +1236,10 @@ void get_random_bytes_arch(void *buf, int nbytes) } EXPORT_SYMBOL(get_random_bytes_arch); +static void seed_entropy_store(void *ctx, u32 data) +{ + mix_pool_bytes((struct entropy_store *)ctx, &data, sizeof(data), NULL); +} /* * init_std_data - initialize pool with system data @@ -1251,15 +1255,19 @@ static void init_std_data(struct entropy_store *r) int i; ktime_t now = ktime_get_real(); unsigned long rv; + char log_prefix[128]; r->last_pulled = jiffies; mix_pool_bytes(r, &now, sizeof(now), NULL); for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) { - if (!arch_get_random_seed_long(&rv) && - !arch_get_random_long(&rv)) - rv = random_get_entropy(); + rv = random_get_entropy(); mix_pool_bytes(r, &rv, sizeof(rv), NULL); } + + sprintf(log_prefix, "random: seeded %s pool", r->name); + arch_get_rng_seed(r, seed_entropy_store, 8 * r->poolinfo->poolbytes, + log_prefix); + mix_pool_bytes(r, utsname(), sizeof(*(utsname())), NULL); } diff --git a/include/linux/random.h b/include/linux/random.h index 57fbbff..a17065e 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -106,6 +106,46 @@ static inline int arch_has_random_seed(void) } #endif +#ifndef __HAVE_ARCH_GET_RNG_SEED + +/** + * arch_get_rng_seed() - get architectural rng seed data + * @ctx: context for the seed function + * @seed: function to call for each u32 obtained + * @bits_per_source: number of bits from each source to try to use + * @log_prefix: beginning of log output (may be NULL) + * + * Synchronously load some architectural entropy or other best-effort + * random seed data. An arch-specific implementation should be no worse + * than this generic implementation. If the arch code does something + * interesting, it may log something of the form "log_prefix with + * 8 bits of stuff". + * + * No arch-specific implementation should be any worse than the generic + * implementation. + */ +static inline void arch_get_rng_seed(void *ctx, + void (*seed)(void *ctx, u32 data), + int bits_per_source, + const char *log_prefix) +{ + int i, longs = (bits_per_source + BITS_PER_LONG - 1) / BITS_PER_LONG; + + for (i = 0; i < longs; i++) { + unsigned long rv; + + if (arch_get_random_seed_long(&rv) || + arch_get_random_long(&rv)) { + seed(ctx, (u32)rv); +#if BITS_PER_LONG > 32 + seed(ctx, (u32)(rv >> 32)); +#endif + } + } +} + +#endif /* __HAVE_ARCH_GET_RNG_SEED */ + /* Pseudo random number generator from numerical recipes. */ static inline u32 next_pseudo_random32(u32 seed) {
Currently, init_std_data contains its own logic for using arch random sources. This logic is a bit strange: it reads one long of arch random data per byte of internal state. This replaces that logic with a generic function arch_get_rng_seed that allows arch code to supply its own logic. The default implementation tries arch_get_random_seed_long and arch_get_random_long individually, requesting one bit per bit of internal state being seeded. Assuming the arch sources are perfect, this is the right thing to do. They're not, though, so the followup patch attempts to implement the correct logic on x86. Signed-off-by: Andy Lutomirski <luto@amacapital.net> --- drivers/char/random.c | 14 +++++++++++--- include/linux/random.h | 40 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 51 insertions(+), 3 deletions(-)