Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1392001 > unrolled thread

[RFC PATCH 0/3] random: replace urandom pool with a CRNG

Back to article view | Back to linux.kernel

Contents

  [RFC PATCH 0/3] random: replace urandom pool with a CRNG Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
    [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Stephan Mueller <smueller@chronox.de> - 2016-05-03 11:00 +0200
        Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG Jeffrey Walton <noloader@gmail.com> - 2016-05-04 19:00 +0200
        Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG tytso@mit.edu - 2016-05-04 19:40 +0200
          Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-04 20:00 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Stephan Mueller <smueller@chronox.de> - 2016-05-03 11:40 +0200
        Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG Stephan Mueller <smueller@chronox.de> - 2016-05-04 08:30 +0200
      Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG Jeffrey Walton <noloader@gmail.com> - 2016-05-04 16:50 +0200
        Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG tytso@mit.edu - 2016-05-04 19:50 +0200
          Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG Jeffrey Walton <noloader@gmail.com> - 2016-05-04 20:30 +0200
            Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-04 20:40 +0200
              Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG tytso@thunk.org - 2016-05-04 21:10 +0200
                Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-04 23:00 +0200
                Re: [PATCH 1/3] random: replace non-blocking pool with a  Chacha20-based CRNG John Denker <jsd@av8n.com> - 2016-05-04 23:50 +0200
                  Re: better patch for linux/bitops.h John Denker <jsd@av8n.com> - 2016-05-05 00:00 +0200
                    Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 03:40 +0200
                      Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 04:50 +0200
                        Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 05:00 +0200
                          Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 05:10 +0200
                            Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 05:40 +0200
                              Re: better patch for linux/bitops.h Theodore Ts'o <tytso@mit.edu> - 2016-05-05 06:00 +0200
                                Re: better patch for linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 06:10 +0200
                                  Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 08:40 +0200
                                    Re: UB in general ... and linux/bitops.h in particular John Denker <jsd@av8n.com> - 2016-05-05 18:20 +0200
                                      Re: UB in general ... and linux/bitops.h in particular Andi Kleen <andi@firstfloor.org> - 2016-05-05 19:40 +0200
                                      Re: UB in general ... and linux/bitops.h in particular Jeffrey Walton <noloader@gmail.com> - 2016-05-06 04:30 +0200
                                Re: better patch for linux/bitops.h Sandy Harris <sandyinchina@gmail.com> - 2016-05-05 23:40 +0200
                                  Re: better patch for linux/bitops.h tytso@mit.edu - 2016-05-06 00:20 +0200
                                    Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 00:30 +0200
                                    Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 00:40 +0200
                                    Re: better patch for linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 02:20 +0200
                  Re: [PATCH 1/3] random: replace non-blocking pool with a Chacha20-based CRNG "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 00:00 +0200
                    Re: linux/bitops.h John Denker <jsd@av8n.com> - 2016-05-05 00:10 +0200
                      Re: linux/bitops.h Andi Kleen <andi@firstfloor.org> - 2016-05-05 01:10 +0200
                        Re: linux/bitops.h John Denker <jsd@av8n.com> - 2016-05-05 02:20 +0200
                        Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 03:30 +0200
                        Re: linux/bitops.h Jeffrey Walton <noloader@gmail.com> - 2016-05-05 03:30 +0200
                      Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-05 02:40 +0200
                        Re: linux/bitops.h Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-05 02:50 +0200
                          Re: linux/bitops.h Sasha Levin <sasha.levin@oracle.com> - 2016-05-06 22:10 +0200
                        Re: linux/bitops.h Sasha Levin <sasha.levin@oracle.com> - 2016-05-06 22:10 +0200
                          Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 22:30 +0200
                          Re: linux/bitops.h "H. Peter Anvin" <hpa@zytor.com> - 2016-05-06 22:40 +0200
    [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
      Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs Stephan Mueller <smueller@chronox.de> - 2016-05-02 09:10 +0200
        Re: [PATCH 2/3] random: make /dev/urandom scalable for silly  userspace programs Theodore Ts'o <tytso@mit.edu> - 2016-05-02 15:00 +0200
          Re: [PATCH 2/3] random: make /dev/urandom scalable for silly  userspace programs Theodore Ts'o <tytso@mit.edu> - 2016-05-02 15:50 +0200
            Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs Stephan Mueller <smueller@chronox.de> - 2016-05-02 16:00 +0200
    [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Theodore Ts'o <tytso@mit.edu> - 2016-05-02 08:30 +0200
      Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Jeffrey Walton <noloader@gmail.com> - 2016-05-02 11:10 +0200
        Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Stephan Mueller <smueller@chronox.de> - 2016-05-02 11:20 +0200
          Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler Theodore Ts'o <tytso@mit.edu> - 2016-05-02 15:00 +0200

Page 3 of 3 — ← Prev page 1 2 [3]

#1396095 — Re: linux/bitops.h

On 05/04/2016 08:48 PM, Linus Torvalds wrote:
> That said, the fact that the other cases weren't changed
> (rol64/ror64/ror32) does make that argument less interesting. Unless
> there was some particular code that actively ended up using
> "rol32(..0)" but not the other cases.

Right, the others seemed wrong as well but I couldn't find any code
that triggers that, and preferred to fix just the one I was hitting.

I can go fix the rest if that's something we want to do?


Thanks,
Sasha

[toc] | [prev] | [next] | [standalone]

#1396096 — Re: linux/bitops.h

On 05/04/2016 08:30 PM, H. Peter Anvin wrote:
> On 05/04/16 15:06, John Denker wrote:
>> On 05/04/2016 02:56 PM, H. Peter Anvin wrote:
>>>> Beware that shifting by an amount >= the number of bits in the
>>>> word remains Undefined Behavior.
>>
>>> This construct has been supported as a rotate since at least gcc2.
>>
>> How then should we understand the story told in commit d7e35dfa?
>> Is the story wrong?
>>
>> At the very least, something inconsistent is going on.  There
>> are 8 functions.  Why did d7e35dfa change one of them but
>> not the other 7?
> 
> Yes. d7e35dfa is baloney IMNSHO.  All it does is produce worse code, and the description even says so.

No, the description says that it produces worse code for *really really* ancient
GCC versions.

> As I said, gcc has treated the former code as idiomatic since gcc 2, so that support is beyond ancient.

Because something works in a specific way on one compiler isn't a reason to
ignore this noncompliance with the standard.


Thanks,
Sasha

[toc] | [prev] | [next] | [standalone]

#1396099 — Re: linux/bitops.h

On May 6, 2016 1:07:13 PM PDT, Sasha Levin <sasha.levin@oracle.com> wrote:
>On 05/04/2016 08:30 PM, H. Peter Anvin wrote:
>> On 05/04/16 15:06, John Denker wrote:
>>> On 05/04/2016 02:56 PM, H. Peter Anvin wrote:
>>>>> Beware that shifting by an amount >= the number of bits in the
>>>>> word remains Undefined Behavior.
>>>
>>>> This construct has been supported as a rotate since at least gcc2.
>>>
>>> How then should we understand the story told in commit d7e35dfa?
>>> Is the story wrong?
>>>
>>> At the very least, something inconsistent is going on.  There
>>> are 8 functions.  Why did d7e35dfa change one of them but
>>> not the other 7?
>> 
>> Yes. d7e35dfa is baloney IMNSHO.  All it does is produce worse code,
>and the description even says so.
>
>No, the description says that it produces worse code for *really
>really* ancient
>GCC versions.
>
>> As I said, gcc has treated the former code as idiomatic since gcc 2,
>so that support is beyond ancient.
>
>Because something works in a specific way on one compiler isn't a
>reason to
>ignore this noncompliance with the standard.
>
>
>Thanks,
>Sasha

4.6.2 is not "really, really ancient."
-- 
Sent from my Android device with K-9 Mail. Please excuse brevity and formatting.

[toc] | [prev] | [next] | [standalone]

#1396100 — Re: linux/bitops.h

On May 6, 2016 1:07:13 PM PDT, Sasha Levin <sasha.levin@oracle.com> wrote:
>On 05/04/2016 08:30 PM, H. Peter Anvin wrote:
>> On 05/04/16 15:06, John Denker wrote:
>>> On 05/04/2016 02:56 PM, H. Peter Anvin wrote:
>>>>> Beware that shifting by an amount >= the number of bits in the
>>>>> word remains Undefined Behavior.
>>>
>>>> This construct has been supported as a rotate since at least gcc2.
>>>
>>> How then should we understand the story told in commit d7e35dfa?
>>> Is the story wrong?
>>>
>>> At the very least, something inconsistent is going on.  There
>>> are 8 functions.  Why did d7e35dfa change one of them but
>>> not the other 7?
>> 
>> Yes. d7e35dfa is baloney IMNSHO.  All it does is produce worse code,
>and the description even says so.
>
>No, the description says that it produces worse code for *really
>really* ancient
>GCC versions.
>
>> As I said, gcc has treated the former code as idiomatic since gcc 2,
>so that support is beyond ancient.
>
>Because something works in a specific way on one compiler isn't a
>reason to
>ignore this noncompliance with the standard.
>
>
>Thanks,
>Sasha

When the compiler in question is our flagship target and our reference compiler, then yes, it matters.
-- 
Sent from my Android device with K-9 Mail. Please excuse brevity and formatting.

[toc] | [prev] | [next] | [standalone]

#1392004 — [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs

On a system with a 4 socket (NUMA) system where a large number of
application processes were all trying to read from /dev/urandom, this
can result in the system spending 80% of its time contending on the
global urandom spinlock.  The application have used its own PRNG, but
let's try to help it from running, lemming-like, straight over the
locking cliff.

Reported-by: Andi Kleen <ak@linux.intel.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 62 insertions(+), 5 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 95f4451..d5bb3b3 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -746,6 +746,17 @@ struct crng_state primary_crng = {
 };
 static DECLARE_WAIT_QUEUE_HEAD(crng_init_wait);
 
+#ifdef CONFIG_NUMA
+/*
+ * Hack to deal with crazy userspace progams when they are all trying
+ * to access /dev/urandom in parallel.  The programs are almost
+ * certainly doing something terribly wrong, but we'll work around
+ * their brain damage.
+ */
+static struct crng_state **crng_node_pool __read_mostly;
+#endif
+
+
 static void _initialize_crng(struct crng_state *crng)
 {
 	int		i;
@@ -761,11 +772,13 @@ static void _initialize_crng(struct crng_state *crng)
 	crng->init_time = jiffies - CRNG_RESEED_INTERVAL;
 }
 
+#ifdef CONFIG_NUMA
 static void initialize_crng(struct crng_state *crng)
 {
 	_initialize_crng(crng);
 	spin_lock_init(&crng->lock);
 }
+#endif
 
 static int crng_fast_load(__u32 pool[4])
 {
@@ -822,19 +835,23 @@ out:
 	return ret;
 }
 
+static inline void maybe_reseed_primary_crng(void)
+{
+	if (crng_init > 2 &&
+	    time_after(jiffies, primary_crng.init_time + CRNG_RESEED_INTERVAL))
+		crng_reseed(&input_pool);
+}
+
 static inline void crng_wait_ready(void)
 {
 	wait_event_interruptible(crng_init_wait, crng_ready());
 }
 
-static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE])
+static void _extract_crng(struct crng_state *crng,
+			  __u8 out[CHACHA20_BLOCK_SIZE])
 {
 	unsigned long v, flags;
-	struct crng_state *crng = &primary_crng;
 
-	if (crng_init > 2 &&
-	    time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL))
-		crng_reseed(&input_pool);
 	spin_lock_irqsave(&crng->lock, flags);
 	if (arch_get_random_long(&v))
 		crng->state[14] ^= v;
@@ -844,6 +861,30 @@ static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE])
 	spin_unlock_irqrestore(&crng->lock, flags);
 }
 
+static void extract_crng(__u8 out[CHACHA20_BLOCK_SIZE])
+{
+#ifndef CONFIG_NUMA
+	maybe_reseed_primary_crng();
+	_extract_crng(&primary_crng, out);
+#else
+	int node_id = numa_node_id();
+	struct crng_state *crng = crng_node_pool[node_id];
+
+	if (time_after(jiffies, crng->init_time + CRNG_RESEED_INTERVAL)) {
+		unsigned long flags;
+
+		maybe_reseed_primary_crng();
+		_extract_crng(&primary_crng, out);
+		spin_lock_irqsave(&crng->lock, flags);
+		memcpy(&crng->state[4], out, CHACHA20_KEY_SIZE);
+		crng->state[15] = numa_node_id();
+		crng->init_time = jiffies;
+		spin_unlock_irqrestore(&crng->lock, flags);
+	}
+	_extract_crng(crng, out);
+#endif
+}
+
 static ssize_t extract_crng_user(void __user *buf, size_t nbytes)
 {
 	ssize_t ret = 0, i;
@@ -1548,6 +1589,22 @@ static void init_std_data(struct entropy_store *r)
  */
 static int rand_initialize(void)
 {
+#ifdef CONFIG_NUMA
+	int i;
+	int num_nodes = num_possible_nodes();
+	struct crng_state *crng;
+
+	crng_node_pool = kmalloc(num_nodes * sizeof(void *),
+				 GFP_KERNEL|__GFP_NOFAIL);
+
+	for (i=0; i < num_nodes; i++) {
+		crng = kmalloc(sizeof(struct crng_state),
+			       GFP_KERNEL | __GFP_NOFAIL);
+		initialize_crng(crng);
+		crng_node_pool[i] = crng;
+
+	}
+#endif
 	init_std_data(&input_pool);
 	init_std_data(&blocking_pool);
 	_initialize_crng(&primary_crng);
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1392015 — Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs

Am Montag, 2. Mai 2016, 02:26:52 schrieb Theodore Ts'o:

Hi Theodore,

I have not digested the patch set yet, but I have the following questions to 
your patch set.

> On a system with a 4 socket (NUMA) system where a large number of
> application processes were all trying to read from /dev/urandom, this
> can result in the system spending 80% of its time contending on the
> global urandom spinlock.  The application have used its own PRNG, but
> let's try to help it from running, lemming-like, straight over the
> locking cliff.

- initialization: In my DRBG based patch-set I tried serialize the 
initialization of the per-NUMA node RNGs as follows: first the node 0 pool is 
seeded completely, followed by the other nodes in a completely serial fashion. 
If during that initialization time, say, node 3 wants some random number, but 
the RNG for node 3 is not yet fully seeded, it goes back to the "default" RNG 
of node 0. This way, it is ensured that we try to have properly seeded RNGs 
even during heavy load at boot time. Would that make sense here?

- reseed avalanche: I see that you added a time-based reseed code too (I am 
glad about that one). What I fear is that there is a reseed avalanche when the 
various RNGs are seeded initially closely after each other (and thus the 
reseed timer will expire at the same time). That would mean that they can be 
reseeded all at the same time again when the timer based threshold expires and 
drain the input_pool such that if you have many nodes, the input pool will not 
have sufficient capacity (I am not speaking about entropy, but the potential 
to store entropy) to satisfy all RNGs at the same time. Hence, we would then 
have the potential to have entropy-starved RNGs.

- entropy pool draining: when having a timer-based reseeding on a quiet 
system, the entropy pool can be drained during the expiry of the timer. So, I 
tried to handle that by increasing the timer by, say, 100 seconds for each new 
NUMA node. Note, even the baseline of 300 seconds with CRNG_RESEED_INTERVAL is 
low. When I experimented with that on a KVM test system and left it quiet, 
entropy pool draining was prevented at around 500 seconds.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1392203 — Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs

On Mon, May 02, 2016 at 09:00:22AM +0200, Stephan Mueller wrote:
> - reseed avalanche: I see that you added a time-based reseed code too (I am 
> glad about that one). What I fear is that there is a reseed avalanche when the 
> various RNGs are seeded initially closely after each other (and thus the 
> reseed timer will expire at the same time). That would mean that they can be 
> reseeded all at the same time again when the timer based threshold expires and 
> drain the input_pool such that if you have many nodes, the input pool will not 
> have sufficient capacity (I am not speaking about entropy, but the potential 
> to store entropy) to satisfy all RNGs at the same time. Hence, we would then 
> have the potential to have entropy-starved RNGs.

The crng is a CRNG, not an entropy pool.  So we don't pretend to track
entropy on the CRNG's at all.  The current rule is that when you draw
from a crng, if it has been over 5 mintues, it will reseed from its
"parent" source.  In the case of the primary_crng will draw between
128 and 256 bits of entropy from the input pool.  In the per-NUMA node
case, they draw from the primary_crng.

So if there are many secondary (per-NUMA node) CRNG's that are seeded
within five minutes of each other, the input pool only gets drawn down
once to seed the primary_crng.  The per-NUMA node crng's feed from the
primary crng, and absent some catastrophic security breach where the
adversary can read kernel memory (at which point you're toast anyway)
the output of the primary_crng is never exposed directly outside of
the system.  So even if you have some crazy SGI system with 1024 NUMA
nodes, the primary_crng will only be generating at most 32k worth of
data to seed the secondary crng's before it gets reseed --- and the
input pool is only going to be debited at most 128-256 bits of entropy
each time.

I thought about using the primary_crng to serve double duty as the
CRNG for NUMA node 0, but I decided that on a NUMA system you have
TB's and TB's of memory, and so blowing another 80 bytes or so on a
separate primary_crng state makes the security analysis much simpler,
and the code much simpler.  I also thought about only dynamically
initializing a node_id's CRNG if a spin_trylock on node 0's CRNG
failed, but again, decided against it in the itnerests of keeping
things simple and that NUMA people can afford to be profligate with
memory --- and they're blowing way more than 80 bytes per NUMA node
anyway.  Besides, manufactuers of crazy-expensive NUMA systems have to
feed their children, too.  :-)

> - entropy pool draining: when having a timer-based reseeding on a quiet 
> system, the entropy pool can be drained during the expiry of the timer. So, I 
> tried to handle that by increasing the timer by, say, 100 seconds for each new 
> NUMA node. Note, even the baseline of 300 seconds with CRNG_RESEED_INTERVAL is 
> low. When I experimented with that on a KVM test system and left it quiet, 
> entropy pool draining was prevented at around 500 seconds.

Sure, but if no one is actually *using* the system, who cares about
whether the input pool's entropy is getting drawn down?  The usual
reason why we might want to worry about reseeding frequently is if the
system is generating a huge amount of randomness for some reason.
This might be a good reason (you're running a IPSEC server and
generating lots of IKE session keys) or it might be for a really
stupid reason (dd if=/dev/urandom of=/dev/sdX bs=4k), but either way,
there will be lots of disk or networking interrupts to feed the input
pool.

I have thought about adding something a bit more sophisticated to
control the reseed logic (either tracking amount of data used, or
making the reseed interval adjustable, or dynamically adjustable), but
this was the simplest thing to do as a starting point.  Besides for
the people who believe that it's realistic to write academic papers
about recovering from catastrophic security exposures where the bad
guy can read arbitrary kernel memory, and somehow _not_ managed to
bootstrap that into a full privilege escalation attack and installed a
backdoor into your BIOS so that you are permanently pwned, they might
be happy that we will be trying to recover within 5 minutes.  :-)

					- Ted

[toc] | [prev] | [next] | [standalone]

#1392220 — Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs

On Mon, May 02, 2016 at 08:50:14AM -0400, Theodore Ts'o wrote:
> > - entropy pool draining: when having a timer-based reseeding on a quiet 
> > system, the entropy pool can be drained during the expiry of the timer. So, I 
> > tried to handle that by increasing the timer by, say, 100 seconds for each new 
> > NUMA node. Note, even the baseline of 300 seconds with CRNG_RESEED_INTERVAL is 
> > low. When I experimented with that on a KVM test system and left it quiet, 
> > entropy pool draining was prevented at around 500 seconds.

One other thought.  If your KVM test system was completely quiet, then
all of the entropy was coming from timer interrupts.  It is an open
question whether an adversary could predict the bit of "entropy" you
are generating with better than 50% probability if both the host and
the guest system are quiescent.  And if they can, then maybe assuming
one bit of entropy per interrupt might be a too optimistic.

This is especially true on bare metal where very often, especially on
smaller machines, where there is a single oscillator from which all of
the clocks on the SOC or motherboard are derived.  There is a reason
why I was being ultra conservative in sampling 64 interrupts into a
32-bit fast-mix pool before mixing it into the input pool, and only
crediting the pool with a single bit of entropy each time I did this.

(It's also because of this conservatism that I was comfortable with
having add_disk_randomness giving some extra credit for interrupts
that are probably more likely to be hard-to-predict by an adversary.
Especially if the interrupts are coming from a device with spinning
rust platters.)

						- Ted

[toc] | [prev] | [next] | [standalone]

#1392225 — Re: [PATCH 2/3] random: make /dev/urandom scalable for silly userspace programs

Am Montag, 2. Mai 2016, 09:48:57 schrieb Theodore Ts'o:

Hi Theodore,

> On Mon, May 02, 2016 at 08:50:14AM -0400, Theodore Ts'o wrote:
> > > - entropy pool draining: when having a timer-based reseeding on a quiet
> > > system, the entropy pool can be drained during the expiry of the timer.
> > > So, I tried to handle that by increasing the timer by, say, 100 seconds
> > > for each new NUMA node. Note, even the baseline of 300 seconds with
> > > CRNG_RESEED_INTERVAL is low. When I experimented with that on a KVM
> > > test system and left it quiet, entropy pool draining was prevented at
> > > around 500 seconds.
> 
> One other thought.  If your KVM test system was completely quiet, then
> all of the entropy was coming from timer interrupts.  It is an open
> question whether an adversary could predict the bit of "entropy" you
> are generating with better than 50% probability if both the host and
> the guest system are quiescent.  And if they can, then maybe assuming
> one bit of entropy per interrupt might be a too optimistic.

It is not entirely quiet -- systemd likes to dump data on the disk once in a 
while. So, it is no timer interrupt that I see.

Note, my test system runs as tickless kernel.
> 
> This is especially true on bare metal where very often, especially on
> smaller machines, where there is a single oscillator from which all of
> the clocks on the SOC or motherboard are derived.  There is a reason
> why I was being ultra conservative in sampling 64 interrupts into a
> 32-bit fast-mix pool before mixing it into the input pool, and only
> crediting the pool with a single bit of entropy each time I did this.

As I do not think that we see any timer interrupts, I think this argument may 
not count.

Besides, I have not seen any timer interrupts lately (with or without a 
tickless kernel). Thus, which interrupt do you think is a timer interrupt?


Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1392008 — [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler

From: Stephan Mueller <smueller@chronox.de>

The Hyper-V Linux Integration Services use the VMBus implementation for
communication with the Hypervisor. VMBus registers its own interrupt
handler that completely bypasses the common Linux interrupt handling.
This implies that the interrupt entropy collector is not triggered.

This patch adds the interrupt entropy collection callback into the VMBus
interrupt handler function.

Signed-off-by: Stephan Mueller <stephan.mueller@atsec.com>
Signed-off-by: Stephan Mueller <smueller@chronox.de>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>
---
 drivers/char/random.c  | 1 +
 drivers/hv/vmbus_drv.c | 3 +++
 2 files changed, 4 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d5bb3b3..c3f17c9 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1133,6 +1133,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	/* award one bit for the contents of the fast pool */
 	credit_entropy_bits(r, credit + 1);
 }
+EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
 #ifdef CONFIG_BLOCK
 void add_disk_randomness(struct gendisk *disk)
diff --git a/drivers/hv/vmbus_drv.c b/drivers/hv/vmbus_drv.c
index 64713ff..9af61bb 100644
--- a/drivers/hv/vmbus_drv.c
+++ b/drivers/hv/vmbus_drv.c
@@ -41,6 +41,7 @@
 #include <linux/ptrace.h>
 #include <linux/screen_info.h>
 #include <linux/kdebug.h>
+#include <linux/random.h>
 #include "hyperv_vmbus.h"
 
 static struct acpi_device  *hv_acpi_dev;
@@ -801,6 +802,8 @@ static void vmbus_isr(void)
 		else
 			tasklet_schedule(hv_context.msg_dpc[cpu]);
 	}
+
+	add_interrupt_randomness(HYPERVISOR_CALLBACK_VECTOR, 0);
 }
 
 
-- 
2.5.0

[toc] | [prev] | [next] | [standalone]

#1392077 — Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler

On Mon, May 2, 2016 at 2:26 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> From: Stephan Mueller <smueller@chronox.de>
>
> The Hyper-V Linux Integration Services use the VMBus implementation for
> communication with the Hypervisor. VMBus registers its own interrupt
> handler that completely bypasses the common Linux interrupt handling.
> This implies that the interrupt entropy collector is not triggered.
> ...

Stephan correctly identified the problem of virtualized environments
in his paper, but there does not appear to be any real defenses in
place for VM rollback attacks.

Perhpas the following will make interesting reading:

* When Virtual is Harder than Real: Security Challenges in Virtual
Machine Based Computing Environments,
https://www.usenix.org/legacy/event/hotos05/final_papers/full_papers/garfinkel/garfinkel.pdf

* When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities
and Hedging Deployed Cryptography,
http://pages.cs.wisc.edu/~rist/papers/sslhedge.pdf

Jeff

[toc] | [prev] | [next] | [standalone]

#1392081 — Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler

Am Montag, 2. Mai 2016, 05:00:47 schrieb Jeffrey Walton:

Hi Jeffrey,

> On Mon, May 2, 2016 at 2:26 AM, Theodore Ts'o <tytso@mit.edu> wrote:
> > From: Stephan Mueller <smueller@chronox.de>
> > 
> > The Hyper-V Linux Integration Services use the VMBus implementation for
> > communication with the Hypervisor. VMBus registers its own interrupt
> > handler that completely bypasses the common Linux interrupt handling.
> > This implies that the interrupt entropy collector is not triggered.
> > ...
> 
> Stephan correctly identified the problem of virtualized environments
> in his paper, but there does not appear to be any real defenses in
> place for VM rollback attacks.

The issue the patch addresses is only that on Hyper-V with para-virt drivers, 
the /dev/random implementation does not receive interrupts.

The issue of rollback (if you refer to activating an earlier saved image of 
the guest) is a real issue the guest cannot do anything about it that is 
effective (i.e. the guest can do without the help of the VMM). Note, rollback 
is just a special case of a much broader issue of the duplication of the RNG 
state by the VMM (be it snapshots, move of a guest to another VMM, 
suspend/resume, ...). However, the patch to enable interrupts does not seem to 
be related to that issue as interrupts are not re-issued in case of rollbacks, 
are they?

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1392204 — Re: [PATCH 3/3] random: add interrupt callback to VMBus IRQ handler

On Mon, May 02, 2016 at 11:14:25AM +0200, Stephan Mueller wrote:
> The issue of rollback (if you refer to activating an earlier saved image of 
> the guest) is a real issue the guest cannot do anything about it that is 
> effective (i.e. the guest can do without the help of the VMM). Note, rollback 
> is just a special case of a much broader issue of the duplication of the RNG 
> state by the VMM (be it snapshots, move of a guest to another VMM, 
> suspend/resume, ...). However, the patch to enable interrupts does not seem to 
> be related to that issue as interrupts are not re-issued in case of rollbacks, 
> are they?

Rollback is just a much broader issue of how can you maintain security
when the VMM is run by the NSA, and can do arbitrary things to mess
with the security of the guest OS (including reading keys straight out
of guest kernel memory, etc.).   Hint: you can't.  :-)

If we are talking about someone who is realistically trying to do
something useful with duplicating VMM state, I'm not aware of anyone
who is actually trying to clone a running VMM in order to launch new
worker nodes.  People will clone disk snapshots to rapidly bring up
rapid nodes, and so making sure we have a way to handle cases where
you can't count on /var/state/random.seed on being useful is
important.  The usual answer is to use something like virtio-rng, but
all of the answers are going to assume that the host system is
trustworthy.

If you are worried about a potential attack where the CIA has cut a
deal with Amazon AWS just as the NSA did with RSADSI and DUAL-EC DRBG,
you might as well go home...

						- Ted

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | linux.kernel

csiph-web