Skip to contentSkip to conversation

random32: avoid attempt to late reseed if in the middle of seeding

PATCH Superseded Sasha Levin 3 participants 9 messages Mar 26, 2014 – Mar 27, 2014

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 random32: avoid attempt to late reseed if in the middle of seeding

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

---
 lib/random32.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)
lib/random32.c +15 -1
index 1e5b2df..b59da12 100644
@@ -241,14 +241,27 @@ static void __prandom_reseed(bool late)
 {
 	int i;
 	unsigned long flags;
-	static bool latch = false;
+	static bool latch = false, reseeding = false;
 	static DEFINE_SPINLOCK(lock);
 
+	/*
+	 * Asking for random bytes might result in bytes getting
+	 * moved into the nonblocking pool and thus marking it
+	 * as initialized. In this case we would double back into
+	 * this function and attempt to do a late reseed.
+	 * Ignore the pointless attempt to reseed again if we're
+	 * already waiting for bytes when the nonblocking pool
+	 * got initialized
+	 */
+	if (reseeding)
+		return;
+
 	/* only allow initial seeding (late == false) once */
 	spin_lock_irqsave(&lock, flags);
 	if (latch && !late)
 		goto out;
 	latch = true;
+	reseeding = true;
 
 	for_each_possible_cpu(i) {
 		struct rnd_state *state = &per_cpu(net_rand_state,i);
@@ -263,6 +276,7 @@ static void __prandom_reseed(bool late)
 		prandom_warmup(state);
 	}
 out:
+	reseeding = false;
 	spin_unlock_irqrestore(&lock, flags);
 }
 
Signature · 1 line
1.8.3.2
Acked-by on v1 1/1
#1 lore raw
Quoted 9 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Quoted 4 lines

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Ohh, I overlooked that. Thanks for fixing this, looks good.

#2 lore raw
In reply to Sasha Levin
Quoted 9 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Quoted 4 lines

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

I.e. like:

static void __prandom_reseed(bool late)

{
    int i;
    unsigned long flags;
    static bool latch = false;
    static DEFINE_SPINLOCK(lock);

    /* Asking for random bytes might result in bytes getting
     * moved into the nonblocking pool and thus marking it
     * as initialized. In this case we would double back into
     * this function and attempt to do a late reseed.
     * Ignore the pointless attempt to reseed again if we're
     * already waiting for bytes when the nonblocking pool
     * got initialized.
     */

    /* only allow initial seeding (late == false) once */
    if (!spin_trylock_irqsave(&lock, flags))
        return;

    if (latch && !late)
        goto out;

    latch = true;

    for_each_possible_cpu(i) {
        struct rnd_state *state = &per_cpu(net_rand_state,i);
        u32 seeds[4];

        get_random_bytes(&seeds, sizeof(seeds));
        state->s1 = __seed(seeds[0],   2U);
        state->s2 = __seed(seeds[1],   8U);
        state->s3 = __seed(seeds[2],  16U);
        state->s4 = __seed(seeds[3], 128U);

        prandom_warmup(state);
    }
out:
    spin_unlock_irqrestore(&lock, flags);
}
Quoted 46 lines
---
  lib/random32.c | 16 +++++++++++++++-
  1 file changed, 15 insertions(+), 1 deletion(-)
lib/random32.c +15 -1
index 1e5b2df..b59da12 100644
@@ -241,14 +241,27 @@ static void __prandom_reseed(bool late)
  {
  	int i;
  	unsigned long flags;
-	static bool latch = false;
+	static bool latch = false, reseeding = false;
  	static DEFINE_SPINLOCK(lock);
 
+	/*
+	 * Asking for random bytes might result in bytes getting
+	 * moved into the nonblocking pool and thus marking it
+	 * as initialized. In this case we would double back into
+	 * this function and attempt to do a late reseed.
+	 * Ignore the pointless attempt to reseed again if we're
+	 * already waiting for bytes when the nonblocking pool
+	 * got initialized
+	 */
+	if (reseeding)
+		return;
+
  	/* only allow initial seeding (late == false) once */
  	spin_lock_irqsave(&lock, flags);
  	if (latch && !late)
  		goto out;
  	latch = true;
+	reseeding = true;
 
  	for_each_possible_cpu(i) {
  		struct rnd_state *state = &per_cpu(net_rand_state,i);
@@ -263,6 +276,7 @@ static void __prandom_reseed(bool late)
  		prandom_warmup(state);
  	}
  out:
+	reseeding = false;
  	spin_unlock_irqrestore(&lock, flags);
  }
 
#3 lore raw
Quoted 13 lines · Daniel Borkmann
Quoted 12 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Quoted 8 lines
Quoted 1 line

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

Your code looks much better, I'll should really stop sending patches too early in the morning...

It's also worth adding lib/random32.c to the MAINTAINERS file, as my list of recipients is solely based on what get_maintainer.pl tells me to do (and I'm assuming that I'm not the last person who will be sending patches for this).

Thanks,
Sasha

#4 lore raw
Quoted 23 lines · Sasha Levin
Quoted 13 lines · Daniel Borkmann
Quoted 12 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Quoted 8 lines
Quoted 1 line

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

Quoted 7 lines

Your code looks much better, I'll should really stop sending patches too early in the morning...

It's also worth adding lib/random32.c to the MAINTAINERS file, as my list of recipients is solely based on what get_maintainer.pl tells me to do (and I'm assuming that I'm not the last person who will be sending patches for this).

Sounds like a good idea, afaik, historically, this got ripped out as a lib from networking subsystem. That's why we've sent it to netdev last time.

Cheers,

Daniel

#5 lore raw
In reply to Sasha Levin
Quoted 14 lines · Sasha Levin
Quoted 13 lines · Daniel Borkmann
Quoted 12 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Quoted 8 lines
Quoted 8 lines
Quoted 1 line

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

I totally agree with Daniel spin_trylock_irqsave seems like the best solution.

In case we really want to make sure that even early seeding doesn't race with late seed and the pool is only filled by another CPU, we would actually need per-cpu bools to get this case correct.

I really doubt this isn't worth the effort and wouldn't do that.

Quoted 7 lines

Your code looks much better, I'll should really stop sending patches too early in the morning...

It's also worth adding lib/random32.c to the MAINTAINERS file, as my list of recipients is solely based on what get_maintainer.pl tells me to do (and I'm assuming that I'm not the last person who will be sending patches for this).

Would be a nice idea, especially because prandom_u32 changes are sensitive to network security and should get reviewed there, too.

Greetings,

Hannes

#6 lore raw
Quoted 24 lines · Hannes Frederic Sowa
Quoted 14 lines · Sasha Levin
Quoted 13 lines · Daniel Borkmann
Quoted 12 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Quoted 8 lines
Quoted 8 lines
Quoted 1 line

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

Quoted 6 lines

I totally agree with Daniel spin_trylock_irqsave seems like the best solution.

In case we really want to make sure that even early seeding doesn't race with late seed and the pool is only filled by another CPU, we would actually need per-cpu bools to get this case correct.

But then again, we would just exit via spin_trylock_irqsave() now, no? Whenever something enters this section protected under irq save spinlock we would do a reseed of the entire state (s1-s4) for each cpu.

Quoted 10 lines
Quoted 7 lines

Your code looks much better, I'll should really stop sending patches too early in the morning...

It's also worth adding lib/random32.c to the MAINTAINERS file, as my list of recipients is solely based on what get_maintainer.pl tells me to do (and I'm assuming that I'm not the last person who will be sending patches for this).

Would be a nice idea, especially because prandom_u32 changes are sensitive to network security and should get reviewed there, too.

Indeed, sounds good to me.

Quoted 4 lines

Greetings,

Hannes

#7 lore raw
Quoted 28 lines · Daniel Borkmann
Quoted 27 lines · Hannes Frederic Sowa
Quoted 14 lines · Sasha Levin
Quoted 13 lines · Daniel Borkmann
Quoted 12 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Quoted 8 lines
Quoted 8 lines
Quoted 1 line

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

I totally agree with Daniel spin_trylock_irqsave seems like the best solution.

Quoted 8 lines
Quoted 3 lines

In case we really want to make sure that even early seeding doesn't race with late seed and the pool is only filled by another CPU, we would actually need per-cpu bools to get this case correct.

But then again, we would just exit via spin_trylock_irqsave() now, no? Whenever something enters this section protected under irq save spinlock we would do a reseed of the entire state (s1-s4) for each cpu.

If early reseed races with late one, we would actually need to spin on maybe another cpu, so the early call can leave critical section before late call enters. If we don't spin we could possibly miss the late call when nonblocking pool is fully seeded (entropy may be added in batches and first cpus of the early reseeding might miss better entropy).

If the early call blocks the late call, maybe even on another cpu, the late call should spin until the early call left the critical section. We can only deadlock on same cpu.

I consider this just hypothetical.

Bye,

Hannes

#8 lore raw
Quoted 44 lines · Hannes Frederic Sowa
Quoted 28 lines · Daniel Borkmann
Quoted 27 lines · Hannes Frederic Sowa
Quoted 14 lines · Sasha Levin
Quoted 13 lines · Daniel Borkmann
Quoted 12 lines · Sasha Levin

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized") has added a late reseed stage that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized during __prandom_reseed()'s call to get_random_bytes(). In that case we'd double back into __prandom_reseed() in an attempt to do a late reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already occuring.

Quoted 8 lines
Quoted 8 lines
Quoted 1 line

Thanks for catching! (If you want Dave to pick it up, please also Cc netdev.)

Why not via spin_trylock_irqsave() ? Thus, if we already hold the lock, we do not bother any longer with doing the same work twice and just return.

I totally agree with Daniel spin_trylock_irqsave seems like the best solution.

Quoted 8 lines
Quoted 3 lines

In case we really want to make sure that even early seeding doesn't race with late seed and the pool is only filled by another CPU, we would actually need per-cpu bools to get this case correct.

But then again, we would just exit via spin_trylock_irqsave() now, no? Whenever something enters this section protected under irq save spinlock we would do a reseed of the entire state (s1-s4) for each cpu.

If early reseed races with late one, we would actually need to spin on maybe another cpu, so the early call can leave critical section before late call enters. If we don't spin we could possibly miss the late call when nonblocking pool is fully seeded (entropy may be added in batches and first cpus of the early reseeding might miss better entropy).

Quoted 5 lines

If the early call blocks the late call, maybe even on another cpu, the late call should spin until the early call left the critical section. We can only deadlock on same cpu.

I consider this just hypothetical.

I think I agree with you, it seems hypothetical. We perhaps could have tested e.g. if the nonblocking pool is initialized and in case not, would have a fallback to get_random_bytes_arch() for that short time to have presumably better 'entropy'. On the other hand, if the _arch() version would have been backdoored by the NSA, as we possibly reseed all states later on, or just s1 and xor it with all other states, it seems that eventually there's still no real gain for doing that. So the spin_trylock_irqsave() version seems okay ... plus prandom() API is not cryptographically secure anyway.