Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[linux]

The thing to do, on modern machines, is to stop relying on
external sources and start using the timer interrupt.

Since there is a gigahertz-rate clock available, the jitter between it
and another clock can be a fruitful source of entropy.  Frankly, I think
there's > 1 bit of entropy available per sample, but even at 0.01 bits
per sample (which is saying that it's exactly predictable at least 99.914%
of the time), that's still 128 bits of key in 13 seconds.

Even though both the processor clock and the timer clock are ultimately
derived from the same crystal, the phase-locked loops which do
the frequency multiplying have quite detectable noise.  And that's
ignoring the "spread-spectrum" frequency modulation that many modern PC
motherboards do.

In these days of wireless keyboards and mice, /dev/random's faith in
those sources is probably misplaced, but with much faster processor
clocks, a new, purely internal source becomes much more practical.

Machines without TSCs are still a challenge.  For PCs, I'd suggest using
the 32 kHz-crystal-driven RTC and beating that against the 2 MHz PIT.
On other platforms, I'm a little unclear.

If you want to test this, collect the appropriate data points on an
otherwise idle machine, with speread-spectrum clocking turned off in
the BIOS of possible, subtract the slope, and delete all the outlyers.
Then look at the scatter of the remaining data and subject it to various
randomness tests.  Note that if there is a PLL connecting the two
clocks, a sufficiently high-resolution slope measurement will reveal
the rational number ratio.


For those intersted, the entropy (in bits) of a based coin is related
to the chance of its landing heads (or tails) as follows:

Entropy	Probability
1	0.5
0.999	0.518614
0.99	0.558802
0.9	0.683981
0.8	0.756996
0.7	0.810702
0.6	0.853898
0.5	0.889972
0.4	0.920617
0.3	0.946761
0.2	0.968876
0.1	0.987013
0.09	0.988590
0.08	0.990119
0.07	0.991598
0.06	0.993024
0.05	0.994393
0.04	0.995699
0.03	0.996936
0.02	0.998090
0.01	0.999140
0.009	0.999237
0.008	0.999333
0.007	0.999427
0.006	0.999519
0.005	0.999608
0.004	0.999695
0.003	0.999779
0.002	0.999860
0.001	0.999935

If there are more secondary alternatives than just "tails", the
numbers - either the entropy for a certain probability of heads,
or the probability of heads to get a certain entropy - go up.



As for the discussion of hash functions "broken", /dev/random is very
conservative about its use of the hash function.

There are three major kinds of attacks against hash functions.
In increasing order of difficulty:
	1) Collision attack.  Find x and y such that H(x) == H(y)
	2) Second pre-image attack.  Given y, find x so H(x) == H(y).
	3) (First) pre-image attack.  Given y, find x so H(x) == y.

There is an obvious brute-force solution to a collision attack for
an n-bit hash in O(2^(n/2)) steps.  (Basically, compute the hashes of
2^(n/2) random strings; you will alsmost certainly find a collision.
There re clever ways to avoid storing 2^(n/2) input values.)

Generally, when collsions are easy to find in a hash function, it is
considered broken for practical purposes.  For example, if I know a
collision for two values x and y, suppose I give you $x in return for
a digitally signed negotiable instrument for $x.  Then I can change it
to read $y and present it for payment.  Assuming that x < y, this has
potential for profit.  (Reality is a bit more complicated, but hopefully
you get the idea.)

A pre-image attack, where there is a *single* hash value you want to
match, is far more difficult.  For example, even for the generally
laughable MD4, a second pre-image attack is only known for a class of
"weak" messages consituting 2^-122 of possible inputs.  (Xiaoyun Wang
et. al, "Cryptanalysis of the Hash Functions MD4 and RIPEMD", 2005)

To break /dev/urandom with cryptanalysis, the basic difficulty lies in
deducing the internal random pool state.  The pool is by default 1024
bits in size, but you only get 80 bits of hash function output at a time.
So the first thing you have to do is read at least as many bits from the
pool as there is entropy, and then solve a pre-image problem.  But not
just ANY pre-image will do; you have to find the one of the 2^1024 states
that simultaneously satisfies your a priori knowledge of the pool state
and the (possibly multiple) hash function pre-image conditions.  This is
vastly harder than a simple pre-image attack, which is much much harder
than a collision attack.

Even if the hash function is so thoroughly broken that it's are useless
for most purposes, it can still shield /dev/urandom's internal state.

It's a very conservative and robust design.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[linux]

Eek!  I just realized that my earlier posting about the entropy from
biased coin flips was wrong.  More dangerous than obviously wrong, it
was subtly wrong.

The table I posted was based on the common Shannon entropy measure.
However, it is well known in the theory of "randomness extractors" that
Shannon entropy is not the appropriate measure to use when judging an
entropy source which you are going to derive key material from; you need
to use the more conservative min-entropy.

For a reminder, if your random variable has a number of possible states
1..n, with corresponding probabilities p[1]..p[n], then the Shannon entropy
of this variable is

	sum -p[i] * log(p[i]), for i = 1..n

while the min-entropy is simply

	min -log(p[i]), for i = 1..n

(For entropy in bits, we will use the base-2 logarithm.)
These are identical if all the p[i] are equal, but the min-entropy is
lower in all other cases.


The classic example of a bad source with good Shannon entropy is a 256-bit
key that has 255 bits of randomness half the time, but has a single fixed
value the other half of the time.  If you plug this distribution into
the Shannon entropy formula, you get 128.5 bits of entropy.  That should
be enough to keep out an attacker, right?

Well, except for the half of the time when you're using the single
fixed value!  The problem is that the fact that you have much more than
the required 128 bits half of the time doesn't make up for the drastic
loss the other half of the time.


For an entropy-accumulation example, suppose you have a source which
produces 31 truly random bits (0..07fffffff) half of the time, and
a fixed value of -1 the other half of the time.  Again, the Shannon
entropy of this source is easily computed as 16.5 bits per sample.

Just to work through the math for the Shannon entropy,
we have p[-1] = 1/2, and p[0] = p[1] = ... = p[0x7fffffff] = 2^-32.

	sum -p[i] * log(p[i]),			for i = -1..0x7fffffff
=	(-(1/2) * log(1/2) ) +			The i = -1 case
	sum -(2^-32) * log(2^-32),		for i = 0..0x7fffffff
= 	-1/2 * -1  +  2^31 * -(2^-32 * -32)
=	1/2 + 1/2 * 32
=	1/2 + 16
=	16.5

So taking 8 such samples should produce 132 bits of entropy, which
can be hashed into a good 128-bit key, right?

Well, except for the 1/256 of the time when the key is the
hash of 8 copies of -1.  And an additional 8/256 = 1/32 of the time,
the key has 34 bits of entropy.  (31 bits in one of the 8 seeds,
plus 3 bits of uncertainty as to which seed.)

Again, even though on average the input has more than 128 bits of entropy,
the hashing throws away the excess, while the naive Shannon estimate
averages that wasted excess with the cases that are severly lacking.


Unsing the min-entropy estimate, the source has 1 bit if min-entropy,
so 8 samples have 8 bits of min-entropy, and a good hash won't change
that much.  (It can't make it better, and collisions will make it slightly
worse.)  The highest-probability key will occur 2^-8 = 1/256 of the time.


In particular, the table of the probabilities needed to achieve
a particular entropy should be amended as follows:

Entropy	     Probability		min-entropy of
(bits)	Shannon		min		Shannon prob
1	0.5		0.5		1
0.999	0.518614        0.500347	0.947267
0.99	0.558802        0.503478        0.839591
0.9	0.683981        0.535887        0.547972
0.8	0.756996        0.574349        0.401642
0.7	0.810702        0.615572        0.302756
0.6	0.853898        0.659754        0.227864
0.5	0.889972        0.707107        0.168168
0.4	0.920617        0.757858        0.119327
0.3	0.946761        0.812252        0.078928
0.2	0.968876        0.870551        0.045616
0.1	0.987013        0.933033        0.018859
0.09	0.988590        0.939523        0.016556
0.08	0.990119        0.946058        0.014326
0.07	0.991598        0.952638        0.012173
0.06	0.993024        0.959264        0.010100
0.05	0.994393        0.965936        0.008112
0.04	0.995699        0.972655        0.006218
0.03	0.996936        0.979420        0.004427
0.02	0.998090        0.986233        0.002758
0.01	0.999140        0.993092        0.001241
0.009	0.999237        0.993781        0.001101
0.008	0.999333        0.994470        0.000963
0.007	0.999427        0.995160        0.000827
0.006	0.999519        0.995850        0.000694
0.005	0.999608        0.996540        0.000566
0.004	0.999695        0.997231        0.000440
0.003	0.999779        0.997923        0.000319
0.002	0.999860        0.998615        0.000202
0.001	0.999935        0.999307        0.000094
	(WRONG)		(RIGHT)		(RIGHT entropy of WRONG probability)

You need a most-likely probability less than the "min probability" column
to achieve the min-entropy given in the first column.  The fourth column
gives the actual min-entropy you'd get if you used the Shannon-derived
probability.  Note that it's off by a factor of >10 near the bottom of
the list.  (1-p = e*ln(2) is a very close approximation when e is
much less than 1.)

Also, unlike the Shannon entropy, the number and probabilities of
less-likely alternatives do not matter.  This actually makes analysis of
interrupt timing easier, because you don't have to worry about outliers.
Just see how often you can predict the EXACT timestamp of an interrupt
and ignore the rest.

(This in turn leads to the possibility of real-time entropy measurement
of timer interrupts.  Assuming both are derived from a common crystal
via PLLs, the slope of the interrupt number vs. timestamp should be a
simple exact rational number.  You can build a histogram of the measured
timestamps around the predicted slope, discarding outliers, and use the
maximum value to compute the min-entropy.  To be conservative, take the
sum of the largest two in case the wiggle between them is modelable.)

[PATCH 1/14] random: Remove SA_SAMPLE_RANDOM from floppy driver

[Matt Mackall]

Remove SA_SAMPLE_RANDOM from floppy driver

The floppy driver is already calling add_disk_randomness as it should,
so this was redundant.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: 2.6/include/asm-alpha/floppy.h
===================================================================
--- 2.6.orig/include/asm-alpha/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-alpha/floppy.h	2006-05-03 11:18:46.000000000 -0500
@@ -26,9 +26,8 @@
 #define fd_enable_irq()         enable_irq(FLOPPY_IRQ)
 #define fd_disable_irq()        disable_irq(FLOPPY_IRQ)
 #define fd_cacheflush(addr,size) /* nothing */
-#define fd_request_irq()        request_irq(FLOPPY_IRQ, floppy_interrupt, \
-					    SA_INTERRUPT|SA_SAMPLE_RANDOM, \
-				            "floppy", NULL)
+#define fd_request_irq()        request_irq(FLOPPY_IRQ, floppy_interrupt,\
+					    SA_INTERRUPT, "floppy", NULL)
 #define fd_free_irq()           free_irq(FLOPPY_IRQ, NULL);
 
 #ifdef CONFIG_PCI
Index: 2.6/include/asm-arm/floppy.h
===================================================================
--- 2.6.orig/include/asm-arm/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-arm/floppy.h	2006-05-03 11:19:14.000000000 -0500
@@ -25,7 +25,7 @@
 
 #define fd_inb(port)		inb((port))
 #define fd_request_irq()	request_irq(IRQ_FLOPPYDISK,floppy_interrupt,\
-					SA_INTERRUPT|SA_SAMPLE_RANDOM,"floppy",NULL)
+					    SA_INTERRUPT,"floppy",NULL)
 #define fd_free_irq()		free_irq(IRQ_FLOPPYDISK,NULL)
 #define fd_disable_irq()	disable_irq(IRQ_FLOPPYDISK)
 #define fd_enable_irq()		enable_irq(IRQ_FLOPPYDISK)
Index: 2.6/include/asm-arm26/floppy.h
===================================================================
--- 2.6.orig/include/asm-arm26/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-arm26/floppy.h	2006-05-03 11:13:31.000000000 -0500
@@ -22,7 +22,7 @@
 
 #define fd_inb(port)		inb((port))
 #define fd_request_irq()	request_irq(IRQ_FLOPPYDISK,floppy_interrupt,\
-					SA_INTERRUPT|SA_SAMPLE_RANDOM,"floppy",NULL)
+					SA_INTERRUPT,"floppy",NULL)
 #define fd_free_irq()		free_irq(IRQ_FLOPPYDISK,NULL)
 #define fd_disable_irq()	disable_irq(IRQ_FLOPPYDISK)
 #define fd_enable_irq()		enable_irq(IRQ_FLOPPYDISK)
Index: 2.6/include/asm-i386/floppy.h
===================================================================
--- 2.6.orig/include/asm-i386/floppy.h	2006-05-02 17:28:46.000000000 -0500
+++ 2.6/include/asm-i386/floppy.h	2006-05-03 11:03:21.000000000 -0500
@@ -147,9 +147,8 @@ static int fd_request_irq(void)
 		return request_irq(FLOPPY_IRQ, floppy_hardint,SA_INTERRUPT,
 						   "floppy", NULL);
 	else
-		return request_irq(FLOPPY_IRQ, floppy_interrupt,
-						   SA_INTERRUPT|SA_SAMPLE_RANDOM,
-						   "floppy", NULL);	
+		return request_irq(FLOPPY_IRQ, floppy_interrupt, SA_INTERRUPT,
+				   "floppy", NULL);
 
 }
 
Index: 2.6/include/asm-mips/mach-generic/floppy.h
===================================================================
--- 2.6.orig/include/asm-mips/mach-generic/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-mips/mach-generic/floppy.h	2006-05-03 11:11:14.000000000 -0500
@@ -98,7 +98,7 @@ static inline void fd_disable_irq(void)
 static inline int fd_request_irq(void)
 {
 	return request_irq(FLOPPY_IRQ, floppy_interrupt,
-	                   SA_INTERRUPT | SA_SAMPLE_RANDOM, "floppy", NULL);
+	                   SA_INTERRUPT, "floppy", NULL);
 }
 
 static inline void fd_free_irq(void)
Index: 2.6/include/asm-mips/mach-jazz/floppy.h
===================================================================
--- 2.6.orig/include/asm-mips/mach-jazz/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-mips/mach-jazz/floppy.h	2006-05-03 11:11:44.000000000 -0500
@@ -90,7 +90,7 @@ static inline void fd_disable_irq(void)
 static inline int fd_request_irq(void)
 {
 	return request_irq(FLOPPY_IRQ, floppy_interrupt,
-	                   SA_INTERRUPT | SA_SAMPLE_RANDOM, "floppy", NULL);
+	                   SA_INTERRUPT, "floppy", NULL);
 }
 
 static inline void fd_free_irq(void)
Index: 2.6/include/asm-parisc/floppy.h
===================================================================
--- 2.6.orig/include/asm-parisc/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-parisc/floppy.h	2006-05-03 11:12:56.000000000 -0500
@@ -159,10 +159,8 @@ static int fd_request_irq(void)
 		return request_irq(FLOPPY_IRQ, floppy_hardint,SA_INTERRUPT,
 						   "floppy", NULL);
 	else
-		return request_irq(FLOPPY_IRQ, floppy_interrupt,
-						   SA_INTERRUPT|SA_SAMPLE_RANDOM,
-						   "floppy", NULL);	
-
+		return request_irq(FLOPPY_IRQ, floppy_interrupt, SA_INTERRUPT,
+				   "floppy", NULL);
 }
 
 static unsigned long dma_mem_alloc(unsigned long size)
Index: 2.6/include/asm-powerpc/floppy.h
===================================================================
--- 2.6.orig/include/asm-powerpc/floppy.h	2006-05-02 17:28:46.000000000 -0500
+++ 2.6/include/asm-powerpc/floppy.h	2006-05-03 11:15:32.000000000 -0500
@@ -28,8 +28,7 @@
 #define fd_disable_irq()        disable_irq(FLOPPY_IRQ)
 #define fd_cacheflush(addr,size) /* nothing */
 #define fd_request_irq()        request_irq(FLOPPY_IRQ, floppy_interrupt, \
-					    SA_INTERRUPT|SA_SAMPLE_RANDOM, \
-				            "floppy", NULL)
+					    SA_INTERRUPT, "floppy", NULL)
 #define fd_free_irq()           free_irq(FLOPPY_IRQ, NULL);
 
 #ifdef CONFIG_PCI
Index: 2.6/include/asm-ppc/floppy.h
===================================================================
--- 2.6.orig/include/asm-ppc/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-ppc/floppy.h	2006-05-03 11:10:41.000000000 -0500
@@ -99,10 +99,8 @@ static int fd_request_irq(void)
 		return request_irq(FLOPPY_IRQ, floppy_hardint,SA_INTERRUPT,
 						   "floppy", NULL);
 	else
-		return request_irq(FLOPPY_IRQ, floppy_interrupt,
-						   SA_INTERRUPT|SA_SAMPLE_RANDOM,
-						   "floppy", NULL);
-
+		return request_irq(FLOPPY_IRQ, floppy_interrupt, SA_INTERRUPT,
+				   "floppy", NULL);
 }
 
 static int vdma_dma_setup(char *addr, unsigned long size, int mode, int io)
Index: 2.6/include/asm-sh/floppy.h
===================================================================
--- 2.6.orig/include/asm-sh/floppy.h	2005-10-27 19:02:08.000000000 -0500
+++ 2.6/include/asm-sh/floppy.h	2006-05-03 11:04:48.000000000 -0500
@@ -147,11 +147,10 @@ static int fd_request_irq(void)
 {
 	if(can_use_virtual_dma)
 		return request_irq(FLOPPY_IRQ, floppy_hardint,SA_INTERRUPT,
-						   "floppy", NULL);
+				   "floppy", NULL);
 	else
-		return request_irq(FLOPPY_IRQ, floppy_interrupt,
-						   SA_INTERRUPT|SA_SAMPLE_RANDOM,
-						   "floppy", NULL);	
+		return request_irq(FLOPPY_IRQ, floppy_interrupt, SA_INTERRUPT,
+				   "floppy", NULL);
 
 }
 
Index: 2.6/include/asm-x86_64/floppy.h
===================================================================
--- 2.6.orig/include/asm-x86_64/floppy.h	2006-05-02 17:28:46.000000000 -0500
+++ 2.6/include/asm-x86_64/floppy.h	2006-05-03 11:09:30.000000000 -0500
@@ -147,10 +147,8 @@ static int fd_request_irq(void)
 		return request_irq(FLOPPY_IRQ, floppy_hardint,SA_INTERRUPT,
 						   "floppy", NULL);
 	else
-		return request_irq(FLOPPY_IRQ, floppy_interrupt,
-						   SA_INTERRUPT|SA_SAMPLE_RANDOM,
-						   "floppy", NULL);	
-
+		return request_irq(FLOPPY_IRQ, floppy_interrupt, SA_INTERRUPT,
+				   "floppy", NULL);
 }
 
 static unsigned long dma_mem_alloc(unsigned long size)

[PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

Remove SA_SAMPLE_RANDOM from network drivers

/dev/random wants entropy sources to be both unpredictable and
unobservable. Network devices are neither as they may be directly
observed and controlled by an attacker. Thus SA_SAMPLE_RANDOM is not
appropriate.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: 2.6/drivers/net/3c523.c
===================================================================
--- 2.6.orig/drivers/net/3c523.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/3c523.c	2006-05-02 18:37:00.000000000 -0500
@@ -289,8 +289,7 @@ static int elmc_open(struct net_device *
 
 	elmc_id_attn586();	/* disable interrupts */
 
-	ret = request_irq(dev->irq, &elmc_interrupt, SA_SHIRQ | SA_SAMPLE_RANDOM,
-			  dev->name, dev);
+	ret = request_irq(dev->irq, &elmc_interrupt, SA_SHIRQ, dev->name, dev);
 	if (ret) {
 		printk(KERN_ERR "%s: couldn't get irq %d\n", dev->name, dev->irq);
 		elmc_id_reset586();
Index: 2.6/drivers/net/3c527.c
===================================================================
--- 2.6.orig/drivers/net/3c527.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/3c527.c	2006-05-02 18:37:00.000000000 -0500
@@ -435,7 +435,7 @@ static int __init mc32_probe1(struct net
 	 *	Grab the IRQ
 	 */
 
-	err = request_irq(dev->irq, &mc32_interrupt, SA_SHIRQ | SA_SAMPLE_RANDOM, DRV_NAME, dev);
+	err = request_irq(dev->irq, &mc32_interrupt, SA_SHIRQ, DRV_NAME, dev);
 	if (err) {
 		release_region(dev->base_addr, MC32_IO_EXTENT);
 		printk(KERN_ERR "%s: unable to get IRQ %d.\n", DRV_NAME, dev->irq);
Index: 2.6/drivers/net/ibmlana.c
===================================================================
--- 2.6.orig/drivers/net/ibmlana.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/ibmlana.c	2006-05-02 18:37:00.000000000 -0500
@@ -782,7 +782,8 @@ static int ibmlana_open(struct net_devic
 
 	/* register resources - only necessary for IRQ */
 
-	result = request_irq(priv->realirq, irq_handler, SA_SHIRQ | SA_SAMPLE_RANDOM, dev->name, dev);
+	result = request_irq(priv->realirq, irq_handler,
+			     SA_SHIRQ, dev->name, dev);
 	if (result != 0) {
 		printk(KERN_ERR "%s: failed to register irq %d\n", dev->name, dev->irq);
 		return result;
Index: 2.6/drivers/net/ixgb/ixgb_main.c
===================================================================
--- 2.6.orig/drivers/net/ixgb/ixgb_main.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/ixgb/ixgb_main.c	2006-05-02 18:37:00.000000000 -0500
@@ -258,8 +258,7 @@ ixgb_up(struct ixgb_adapter *adapter)
 
 #endif
 	if((err = request_irq(adapter->pdev->irq, &ixgb_intr,
-				  SA_SHIRQ | SA_SAMPLE_RANDOM,
-				  netdev->name, netdev)))
+			      SA_SHIRQ, netdev->name, netdev)))
 		return err;
 
 	/* disable interrupts and get the hardware into a known state */
Index: 2.6/drivers/net/mv643xx_eth.c
===================================================================
--- 2.6.orig/drivers/net/mv643xx_eth.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/mv643xx_eth.c	2006-05-02 18:37:00.000000000 -0500
@@ -778,7 +778,7 @@ static int mv643xx_eth_open(struct net_d
 	int err;
 
 	err = request_irq(dev->irq, mv643xx_eth_int_handler,
-			SA_SHIRQ | SA_SAMPLE_RANDOM, dev->name, dev);
+			SA_SHIRQ, dev->name, dev);
 	if (err) {
 		printk(KERN_ERR "Can not assign IRQ number to MV643XX_eth%d\n",
 								port_num);
Index: 2.6/drivers/net/sk_mca.c
===================================================================
--- 2.6.orig/drivers/net/sk_mca.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/sk_mca.c	2006-05-02 18:37:00.000000000 -0500
@@ -824,7 +824,7 @@ static int skmca_open(struct net_device 
 	/* register resources - only necessary for IRQ */
 	result =
 	    request_irq(priv->realirq, irq_handler,
-			SA_SHIRQ | SA_SAMPLE_RANDOM, "sk_mca", dev);
+			SA_SHIRQ, "sk_mca", dev);
 	if (result != 0) {
 		printk("%s: failed to register irq %d\n", dev->name,
 		       dev->irq);
Index: 2.6/drivers/net/tg3.c
===================================================================
--- 2.6.orig/drivers/net/tg3.c	2006-05-02 18:36:54.000000000 -0500
+++ 2.6/drivers/net/tg3.c	2006-05-02 18:37:00.000000000 -0500
@@ -6602,12 +6602,12 @@ static int tg3_request_irq(struct tg3 *t
 		fn = tg3_msi;
 		if (tp->tg3_flags2 & TG3_FLG2_1SHOT_MSI)
 			fn = tg3_msi_1shot;
-		flags = SA_SAMPLE_RANDOM;
+		flags = 0;
 	} else {
 		fn = tg3_interrupt;
 		if (tp->tg3_flags & TG3_FLAG_TAGGED_STATUS)
 			fn = tg3_interrupt_tagged;
-		flags = SA_SHIRQ | SA_SAMPLE_RANDOM;
+		flags = SA_SHIRQ;
 	}
 	return (request_irq(tp->pdev->irq, fn, flags, dev->name, dev));
 }
@@ -6626,7 +6626,7 @@ static int tg3_test_interrupt(struct tg3
 	free_irq(tp->pdev->irq, dev);
 
 	err = request_irq(tp->pdev->irq, tg3_test_isr,
-			  SA_SHIRQ | SA_SAMPLE_RANDOM, dev->name, dev);
+			  SA_SHIRQ, dev->name, dev);
 	if (err)
 		return err;
 
Index: 2.6/drivers/net/cris/eth_v10.c
===================================================================
--- 2.6.orig/drivers/net/cris/eth_v10.c	2006-04-20 17:00:40.000000000 -0500
+++ 2.6/drivers/net/cris/eth_v10.c	2006-05-03 16:35:13.000000000 -0500
@@ -672,7 +672,7 @@ e100_open(struct net_device *dev)
 	/* allocate the irq corresponding to the receiving DMA */
 
 	if (request_irq(NETWORK_DMA_RX_IRQ_NBR, e100rxtx_interrupt,
-			SA_SAMPLE_RANDOM, cardname, (void *)dev)) {
+			0, cardname, dev)) {
 		goto grace_exit0;
 	}
 
Index: 2.6/drivers/net/e1000/e1000_main.c
===================================================================
--- 2.6.orig/drivers/net/e1000/e1000_main.c	2006-05-02 17:29:27.000000000 -0500
+++ 2.6/drivers/net/e1000/e1000_main.c	2006-05-03 16:34:33.000000000 -0500
@@ -463,8 +463,7 @@ e1000_up(struct e1000_adapter *adapter)
 	}
 #endif
 	if ((err = request_irq(adapter->pdev->irq, &e1000_intr,
-		              SA_SHIRQ | SA_SAMPLE_RANDOM,
-		              netdev->name, netdev))) {
+			       SA_SHIRQ, netdev->name, netdev))) {
 		DPRINTK(PROBE, ERR,
 		    "Unable to allocate interrupt Error: %d\n", err);
 		return err;

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Kyle Moffett]

On May 5, 2006, at 12:42:35, Matt Mackall wrote:
> Remove SA_SAMPLE_RANDOM from network drivers
>
> /dev/random wants entropy sources to be both unpredictable and  
> unobservable. Network devices are neither as they may be directly  
> observed and controlled by an attacker. Thus SA_SAMPLE_RANDOM is  
> not appropriate.

I thought I saw an analysis somewhere of why it was actually OK to  
include randomness from network devices (or even basically any  
interrupt source that isn't periodic on a fundamental hardware  
level).  It had something to do with investigating interrupt arrival  
time from real-time network traffic; they hooked a logic analyzer of  
sorts up to the physical ethernet cable itself and to the system bus  
of the destination computer (and wrote software that recorded a TSC  
timestamp of every interrupt).  Essentially the interaction between  
the occasional ethernet retransmission, variable internal network  
card latencies and queues, variable CPU-dependent interrupt  
latencies, critical sections in the OS, etc, plus the high-resolution  
nature of the TSC used for a seed value made it a chaotic system and  
basically cryptographically impossible to predict the interrupt  
data.  It's possible that the analysis I saw was later proven  
incorrect; but I'd be interested if you've seen some paper or  
research on the topic that I haven't, I'd be interested in references.

Cheers,
Kyle Moffett

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Fri, May 05, 2006 at 01:13:23PM -0400, Kyle Moffett wrote:
> On May 5, 2006, at 12:42:35, Matt Mackall wrote:
> >Remove SA_SAMPLE_RANDOM from network drivers
> >
> >/dev/random wants entropy sources to be both unpredictable and  
> >unobservable. Network devices are neither as they may be directly  
> >observed and controlled by an attacker. Thus SA_SAMPLE_RANDOM is  
> >not appropriate.
> 
> I thought I saw an analysis somewhere of why it was actually OK to  
> include randomness from network devices (or even basically any  
> interrupt source that isn't periodic on a fundamental hardware  
> level).  It had something to do with investigating interrupt arrival  
> time from real-time network traffic; they hooked a logic analyzer of  
> sorts up to the physical ethernet cable itself and to the system bus  
> of the destination computer (and wrote software that recorded a TSC  
> timestamp of every interrupt).  Essentially the interaction between  
> the occasional ethernet retransmission, variable internal network  
> card latencies and queues, variable CPU-dependent interrupt  
> latencies, critical sections in the OS, etc, plus the high-resolution  
> nature of the TSC used for a seed value made it a chaotic system and  
> basically cryptographically impossible to predict the interrupt  
> data.  It's possible that the analysis I saw was later proven  
> incorrect; but I'd be interested if you've seen some paper or  
> research on the topic that I haven't, I'd be interested in references.

I haven't seen such an analysis, scholarly or otherwise and my bias
here is to lean towards the paranoid.

Assuming a machine with no TSC and an otherwise quiescent ethernet
(hackers burning the midnight oil), I think most of the
hard-to-analyze bits above get pretty transparent.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Theodore Tso]

On Fri, May 05, 2006 at 12:24:26PM -0500, Matt Mackall wrote:
> I haven't seen such an analysis, scholarly or otherwise and my bias
> here is to lean towards the paranoid.
> 
> Assuming a machine with no TSC and an otherwise quiescent ethernet
> (hackers burning the midnight oil), I think most of the
> hard-to-analyze bits above get pretty transparent.

As always, whether or not the packet arrival times could be guessable
and/or controlled by an attacker really depends on your threat model.
For someone who has an ethernet monitor attached directly to the
segment right next to your computer, it's very likely that they would
be successful in guessing the inputs into the entropy pool.  However,
an attacker with physical access to your machine could probably do all
sorts of other things, such as install a keyboard sniffer, etc.  

For a remote attacker, life gets much more difficult.  Each switch,
router, and bridge effectively has a queue into which packets must
flow through, and that is _not_ known to a remote attacker.  This is
especially true today, when most people don't even use repeaters, but
rather switches/bridges, which effectly make each ethernet connection
to each host its own separate collision domain (indeed that term
doesn't even apply for modern high-speed ethernets).

I've always thought the right answer is that whether or not network
packet arrival times should be used as entropy input should be
configurable, since depending on the environment, it might or might
not be safe, and for some hosts (particularly diskless servers), the
network might be the only source of entropy available to them.

						- Ted

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Stephen Hemminger]

On Fri, 5 May 2006 15:11:27 -0400
Theodore Tso <tytso@mit.edu> wrote:

> On Fri, May 05, 2006 at 12:24:26PM -0500, Matt Mackall wrote:
> > I haven't seen such an analysis, scholarly or otherwise and my bias
> > here is to lean towards the paranoid.
> > 
> > Assuming a machine with no TSC and an otherwise quiescent ethernet
> > (hackers burning the midnight oil), I think most of the
> > hard-to-analyze bits above get pretty transparent.
> 
> As always, whether or not the packet arrival times could be guessable
> and/or controlled by an attacker really depends on your threat model.
> For someone who has an ethernet monitor attached directly to the
> segment right next to your computer, it's very likely that they would
> be successful in guessing the inputs into the entropy pool.  However,
> an attacker with physical access to your machine could probably do all
> sorts of other things, such as install a keyboard sniffer, etc.  
> 
> For a remote attacker, life gets much more difficult.  Each switch,
> router, and bridge effectively has a queue into which packets must
> flow through, and that is _not_ known to a remote attacker.  This is
> especially true today, when most people don't even use repeaters, but
> rather switches/bridges, which effectly make each ethernet connection
> to each host its own separate collision domain (indeed that term
> doesn't even apply for modern high-speed ethernets).
> 
> I've always thought the right answer is that whether or not network
> packet arrival times should be used as entropy input should be
> configurable, since depending on the environment, it might or might
> not be safe, and for some hosts (particularly diskless servers), the
> network might be the only source of entropy available to them.
> 
> 						- Ted

An added problem is that many of the high speed interfaces have
interrupt mitigation. The chip will hold off the interrupt for a short
time to try and aggregate multiple packets. This has the effect
of synchronizing the interrupt, and reduces the entropy, especially
under load. NAPI also eliminates much of the entropy in network drivers.
So the quality of the entropy also depends on the chipset. Most of
the older, dumber hardware probably has better entropy but worse performance.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Fri, May 05, 2006 at 03:11:27PM -0400, Theodore Tso wrote:
> On Fri, May 05, 2006 at 12:24:26PM -0500, Matt Mackall wrote:
> > I haven't seen such an analysis, scholarly or otherwise and my bias
> > here is to lean towards the paranoid.
> > 
> > Assuming a machine with no TSC and an otherwise quiescent ethernet
> > (hackers burning the midnight oil), I think most of the
> > hard-to-analyze bits above get pretty transparent.
> 
> As always, whether or not the packet arrival times could be guessable
> and/or controlled by an attacker really depends on your threat model.
> For someone who has an ethernet monitor attached directly to the
> segment right next to your computer, it's very likely that they would
> be successful in guessing the inputs into the entropy pool.  However,
> an attacker with physical access to your machine could probably do all
> sorts of other things, such as install a keyboard sniffer, etc.  
> 
> For a remote attacker, life gets much more difficult.  Each switch,
> router, and bridge effectively has a queue into which packets must
> flow through, and that is _not_ known to a remote attacker.  This is
> especially true today, when most people don't even use repeaters, but
> rather switches/bridges, which effectly make each ethernet connection
> to each host its own separate collision domain (indeed that term
> doesn't even apply for modern high-speed ethernets).
> 
> I've always thought the right answer is that whether or not network
> packet arrival times should be used as entropy input should be
> configurable, since depending on the environment, it might or might
> not be safe, and for some hosts (particularly diskless servers), the
> network might be the only source of entropy available to them.

Nonetheless, the current SA_SAMPLE_RANDOM scheme should go. A) it's in
the IRQ fast path B) most of its users are bogus which strongly
indicates it's a bad API.

Instead (if we want network entropy) we should add an
add_network_randomness call in some central location in the network
stack (probably right next to netpoll's RX hooks) and probably have it
compiled out by default.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Theodore Tso]

On Fri, May 05, 2006 at 03:34:37PM -0500, Matt Mackall wrote:
> Nonetheless, the current SA_SAMPLE_RANDOM scheme should go. A) it's in
> the IRQ fast path B) most of its users are bogus which strongly
> indicates it's a bad API.
> 
> Instead (if we want network entropy) we should add an
> add_network_randomness call in some central location in the network
> stack (probably right next to netpoll's RX hooks) and probably have it
> compiled out by default.

I disagree.  It really wants to be a run-time controllable thing, and
probably on a per-interface/per-device driver basis, since it should
be up to the system administrator who is deploying the box, not the
developer or distribution compiling the kernel, to make that
determination.

Also, the entropy sampling *really* wants to be done in the hard IRQ
handling path, not some place higher in the stack since the scheduler
would smooth out the unpredictable timing information.  Moving it into
the interrupt routines is in fact a problem for CONFIG_PREEMPT_RT,
since the device driver's interrupt handlers become a schedulable
entity, since the IRQ handling is moved into a separate kernel thread.
So I would much prefer to see the entropy sampling stay in its current
location, since people using real-time deserve real randomness too.
(In fact, some of them may have a **much** stronger need for it.  :-)

As far as your reasons that you've given, (A) I find it hard to
believe a single conditional jump is really going to be measurable,
and (B) sure, fix the bad users, but the downside of screwing up
SA_SAMPLE_RANDOM is fairly limited; it only messes up the entropy
estimator, and in practice most users are using /dev/urandom anyway.
The random driver's algorithms are designed so that /dev/random can be
world writable, and an attacker can write arbitrary data, include all
zero's, without degrading the entropy in the pool.(*) Hence, while a
bad user of SA_SAMPLE_RANDOM should be fixed, it is hardly a
catastrophic failure.

						- Ted

(*)So if User A writes data which he knows into /dev/random, it
doesn't help User A guess what /dev/random or /dev/urandom might
produce next --- and if User B doesn't know what User A has written
into the pool, User B's job just got harder.  So if User's B, C, and D
all do the same thing, the net result is that effective
unpredictability of the random pool has increased for everyone.)

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sat, May 06, 2006 at 07:55:02AM -0400, Theodore Tso wrote:
> On Fri, May 05, 2006 at 03:34:37PM -0500, Matt Mackall wrote:
> > Nonetheless, the current SA_SAMPLE_RANDOM scheme should go. A) it's in
> > the IRQ fast path B) most of its users are bogus which strongly
> > indicates it's a bad API.
> > 
> > Instead (if we want network entropy) we should add an
> > add_network_randomness call in some central location in the network
> > stack (probably right next to netpoll's RX hooks) and probably have it
> > compiled out by default.
> 
> I disagree.  It really wants to be a run-time controllable thing, and
> probably on a per-interface/per-device driver basis, since it should
> be up to the system administrator who is deploying the box, not the
> developer or distribution compiling the kernel, to make that
> determination.

Ok, I can agree with that. The interface would have to be extended to
pass more than just IRQ number to do anything vaguely intelligent in
random.c.

> Also, the entropy sampling *really* wants to be done in the hard IRQ
> handling path, not some place higher in the stack since the scheduler
> would smooth out the unpredictable timing information.  Moving it into
> the interrupt routines is in fact a problem for CONFIG_PREEMPT_RT,
> since the device driver's interrupt handlers become a schedulable
> entity, since the IRQ handling is moved into a separate kernel thread.

Yes, PREEMPT_RT definitely does break my proposal. Sigh.

> So I would much prefer to see the entropy sampling stay in its current
> location, since people using real-time deserve real randomness too.
> (In fact, some of them may have a **much** stronger need for it.  :-)

This is the point that bothers me. It's one thing to optimistically
mix network samples (or any other convenient source) into the entropy
pool. I'm all for that. The more, the better.

But let's take a step back from network devices and look at entropy
accounting in the abstract for a moment. The whole point of
/dev/random vs /dev/urandom is: entropy(output) < entropy(input) so
that even if the hash function is broken, we can't guess the internal
pool state and we still have some security. Consider these cases:

Case 1:
Hash function not broken: /dev/random and /dev/urandom are equally
secure, but /dev/random blocks at inconvenient moments. One should
thus really use /dev/urandom for everything unless one suspects that
an attacker is able to observe and record enough /dev/urandom output
that they'll be able to make use of it should the following happen
(aka forward security):

Case 2:
Hash function broken, entropy accounting is conservative: /dev/urandom
is breakable when entropy runs low because it's revealing more
internal entropy than it's collecting and an attacker can eventually
collect enough information to guess the internal state. Fortunately
/dev/random stays secure but blocks.

Case 3:
Hash function broken, entropy accounting is over-optimistic:
/dev/urandom and /dev/random are both equally insecure because both
are revealing more internal entropy than they're collecting. So you
should just use /dev/urandom because at least it doesn't block.

Putting aside all the practical issue of what exactly is entropy and
what decent entropy sources are, we should be able to agree on this
much. And this basically says that if you do your entropy accounting
badly, you throw the baby out with the bathwater.

Now I'll throw out a proposed definition of entropy for our purposes:
the amount of information in a sample that's both unpredictable and
unobservable. If something is partially observable or predictable, we
must take the minimum of the two.

Our current entropy estimator assumes its sources are unobservable and
are at least largely unpredictable. This is arguably not the case, but
that's a separate discussion. Let's assume for the sake of argument
that our entropy estimator gets it right.

But network traffic should be _assumed_ to be observable to some
degree. Everything else in network security makes the assumption that
traffic is completely snoopable. By contrast, we assume people can't
see us type our passwords[1]. So while our entropy estimator assumes
observability == 0, for the network case, 0 < observability <= 1. And
if it's greater than what our entropy estimator assumes, our entropy
estimates are now too optimistic and /dev/random security degrades to
that of /dev/urandom.

Yes, this is all strictly theoretical. But the usefulness of
/dev/random is exactly as theoretical. So if you use /dev/random for
it's theoretical advantages (and why else would you?), this defeats
that.

On the other hand, another approach to this is probably to just be
much more paranoid about our entropy estimates and take a factor of 10
or so off of all of them (and do our accounting in fixed point).
Thoughts?

[1] though hearing someone type a password is actually enough
-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Bernd Eckenfels]

Matt Mackall <mpm@selenic.com> wrote:
>> So I would much prefer to see the entropy sampling stay in its current
>> location, since people using real-time deserve real randomness too.
>> (In fact, some of them may have a **much** stronger need for it.  :-)
> 
> This is the point that bothers me. It's one thing to optimistically
> mix network samples (or any other convenient source) into the entropy
> pool. I'm all for that. The more, the better.

Isnt it possible to use timestamps on the received packages. So you get the
indeterministic timing from interrupt context and can process it in a less
hot path. Also the timestamps are helpfull for other stuff, also.

Gruss
Bernd

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Theodore Tso]

On Sat, May 06, 2006 at 11:48:08AM -0500, Matt Mackall wrote:
> Case 3:
> Hash function broken, entropy accounting is over-optimistic:
> /dev/urandom and /dev/random are both equally insecure because both
> are revealing more internal entropy than they're collecting. So you
> should just use /dev/urandom because at least it doesn't block.
> 
> Putting aside all the practical issue of what exactly is entropy and
> what decent entropy sources are, we should be able to agree on this
> much. And this basically says that if you do your entropy accounting
> badly, you throw the baby out with the bathwater.

Agreed, but I'd an additional point of nuance; this assumes that the
attacker (call him Boris for the sake of argument) can actually gain
access to enough /dev/random or /dev/urandom outputs, and be
knowledgable about all other calls to /dev/random and exactly when
they happen (since entropy extractions cause the TSC to be mixed into
the pool) so Boris can can actually determine the contents of the
pool.  Note that simply "breaking" a cryptographic hash, in the sense
of finding two input values that collide to the same output value,
does not mean that the hash has been sufficiently analyzed that it
would be possible to accomplish this feat.  And given that it took
80,000 CPU hours to determine find this collision, and the complexity
of the attack was 2**51, it seems highly likely that with a poolsize
of 4096 bits, that it would take a huge amount of /dev/random
extractions, complete with the exact TSC timestamp when the
extractions were happening, such that an attacker would be able to
have enough information to break the pool.

Does this mean we should __depend__ on this?  No, we should always do
the best job that we can.  But it's also fair to say that even if the
hash function is "broken", that the results are not automatically
going to be catastrophic.  If the attacker can't get their hands on
enough of an output stream from /dev/random, then it's not likely to
do much.  For an attacker who only has network access, this could be
quite difficult.

> But network traffic should be _assumed_ to be observable to some
> degree. Everything else in network security makes the assumption that
> traffic is completely snoopable. By contrast, we assume people can't
> see us type our passwords[1]. So while our entropy estimator assumes
> observability == 0, for the network case, 0 < observability <= 1. And
> if it's greater than what our entropy estimator assumes, our entropy
> estimates are now too optimistic and /dev/random security degrades to
> that of /dev/urandom.

The timing of network arrivals is observable to *some* degree.  Of
course, so is the timing from block I/O interrupts.  The question is
whether or not it is predictable enough at the finest resolution.  For
block device interrupts, there has been papers showing that air
currents inside the spinning media is chaotic enough that it can
actually influence the timing at which interrupts are returned --- at
least for systems a decade ago.  To be honest, it would probably be a
useful and worthwhile masters thesis for a grad student to revisit the
problem using modern disk drive technologies, controllers, and
interconnects to see if this is still a valid assumption.

For network traffic, again, it depends on your threat model.  For an
attacker stationed in Fort Mead, Maryland, with over a dozen router
and ethernet switches between them and the target system, there are
enough packet queues and buffers that any hope of observing packet
interarrival times is almost certainly hopeless.  As I've said, if an
attacker has direct physical access to the ethernet segment between
your host and the switch, then while the attacker is busy installing a
keyboard switcher and possibly doing a black bag job on your hard disk
to install monitoring software directly in the OS software, yes, the
FBI agent could probably install something on the ethernet between
your host and the switch that could precisely measure packet arrival
times very accurately.  Is that something the system administrator
should care about?  Maybe, maybe not.

That's why I think it should be configurable.  If you don't have a
real hardware number generator, maybe blocking would be preferable to
not having good entropy.  But in other circumstances, what people need
is the best possible randomness they can get, and their security is
not enhanced by simply taking it away from them altogether.  That
makes about as much sense as GNOME making its applications "easier to
use" by removing functionality (to quote Linus).

> Yes, this is all strictly theoretical. But the usefulness of
> /dev/random is exactly as theoretical. So if you use /dev/random for
> it's theoretical advantages (and why else would you?), this defeats
> that.

This becomes a philosophical arugment.  Yes, we should strive for as
much theoretical perfection as possible.  But at the same time, we
need to live in the real world, and adding network entropy which can
defeat the bored high school student in Russia using some black hat
toolkit they downloaded of the internet is useful --- even if it can't
defeat the NSA/FBI agent who can perform a black bag job and place a
monitoring device on your internal ethernet segment.

							- Ted

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sat, May 06, 2006 at 02:05:51PM -0400, Theodore Tso wrote:
> On Sat, May 06, 2006 at 11:48:08AM -0500, Matt Mackall wrote:
> > Case 3:
> > Hash function broken, entropy accounting is over-optimistic:
> > /dev/urandom and /dev/random are both equally insecure because both
> > are revealing more internal entropy than they're collecting. So you
> > should just use /dev/urandom because at least it doesn't block.
> > 
> > Putting aside all the practical issue of what exactly is entropy and
> > what decent entropy sources are, we should be able to agree on this
> > much. And this basically says that if you do your entropy accounting
> > badly, you throw the baby out with the bathwater.
> 
> Agreed, but I'd an additional point of nuance; this assumes that the
> attacker (call him Boris for the sake of argument) can actually gain
> access to enough /dev/random or /dev/urandom outputs, and be
> knowledgable about all other calls to /dev/random and exactly when
> they happen (since entropy extractions cause the TSC to be mixed into
> the pool) so Boris can can actually determine the contents of the
> pool.

Yes, that's assumed. Because otherwise /dev/urandom would be
sufficient in all cases.

> Note that simply "breaking" a cryptographic hash, in the sense
> of finding two input values that collide to the same output value,
> does not mean that the hash has been sufficiently analyzed that it
> would be possible to accomplish this feat.

I'm not talking about any existing attacks, I'm talking about what
would theoretically be possible were a first preimage attack on our
hash to become practical.

> Does this mean we should __depend__ on this?  No, we should always do
> the best job that we can.  But it's also fair to say that even if the
> hash function is "broken", that the results are not automatically
> going to be catastrophic.  If the attacker can't get their hands on
> enough of an output stream from /dev/random, then it's not likely to
> do much.  For an attacker who only has network access, this could be
> quite difficult.

All agreed. But that applies equally to /dev/urandom. The only thing that
distinguishes the two is entropy accounting and entropy accounting
only makes a difference if it's conservative. 

I am _not_ arguing that any of this is practical. I'm arguing that
it's completely beside the point.
 
> > But network traffic should be _assumed_ to be observable to some
> > degree. Everything else in network security makes the assumption that
> > traffic is completely snoopable. By contrast, we assume people can't
> > see us type our passwords[1]. So while our entropy estimator assumes
> > observability == 0, for the network case, 0 < observability <= 1. And
> > if it's greater than what our entropy estimator assumes, our entropy
> > estimates are now too optimistic and /dev/random security degrades to
> > that of /dev/urandom.
> 
> The timing of network arrivals is observable to *some* degree.  Of
> course, so is the timing from block I/O interrupts.

That's a whole 'nother topic we can tackle separately.
 
> For network traffic, again, it depends on your threat model.

Here's a threat model: I remotely break into your LAN and 0wn insecure
Windows box X that's one switch jump away from the web server Y that
processes your credit card transactions. I use standard techniques to
kick the switch into broadcast mode so I can see all its traffic or
maybe I break into the switch itself and temporarily isolate Y from
the rest of the world so that only X can talk to it. I'm still in
Russia, but I might as well be in the same room.

> That's why I think it should be configurable.  If you don't have a
> real hardware number generator, maybe blocking would be preferable to
> not having good entropy.  But in other circumstances, what people need
> is the best possible randomness they can get, and their security is
> not enhanced by simply taking it away from them altogether.  That
> makes about as much sense as GNOME making its applications "easier to
> use" by removing functionality (to quote Linus).

Again, I think it's perfectly reasonable to sample from all sorts of
sources. All my issues are about the entropy accounting.

> > Yes, this is all strictly theoretical. But the usefulness of
> > /dev/random is exactly as theoretical. So if you use /dev/random for
> > it's theoretical advantages (and why else would you?), this defeats
> > that.
> 
> This becomes a philosophical arugment.  Yes, we should strive for as
> much theoretical perfection as possible.  But at the same time, we
> need to live in the real world, and adding network entropy which can
> defeat the bored high school student in Russia using some black hat
> toolkit they downloaded of the internet is useful --- even if it can't
> defeat the NSA/FBI agent who can perform a black bag job and place a
> monitoring device on your internal ethernet segment.

No thoughts on scaling back our entropy estimates?

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[David S. Miller]

From: Matt Mackall <mpm@selenic.com>
Date: Sat, 6 May 2006 15:33:04 -0500

> On Sat, May 06, 2006 at 02:05:51PM -0400, Theodore Tso wrote:
> > For network traffic, again, it depends on your threat model.
> 
> Here's a threat model: I remotely break into your LAN and 0wn insecure
> Windows box X that's one switch jump away from the web server Y that
> processes your credit card transactions. I use standard techniques to
> kick the switch into broadcast mode so I can see all its traffic or
> maybe I break into the switch itself and temporarily isolate Y from
> the rest of the world so that only X can talk to it. I'm still in
> Russia, but I might as well be in the same room.

Doesn't matter.

You cannot measure any of the delays happening between network packet
being seen on the wire to interrupt handler actually executing.

There is so much variable jitter and it depends on so many minute
details at both the hardware and software level, that you can't guess
this stuff.  What's the load on the box?  How many clock cycles does
it take for an interrupt to propagate to the cpu, how many clock
cycles from interrupt reception until the cpu executes the interrupt
handler, how are the hw interrupt mitigation facilities programmed
and how do their timers work, what is the wire to PHY delay, what is
the PHY to MAC delay, how many cycles does it take for the FIFO to
DMA the packet into main memory, what is the delay from DMA'ing the
packet to main memory and the indication of the interrupt condition.
etc. etc. etc.

You can't know any of that.

Please put together a real reproducable attack that others can run too
and would validate justify SA_SAMPLE_RANDOM from networking drivers.
It's all swiss cheese theory until you do this.  And we should not be
making kernel changes merely due to swiss cheese theory.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Theodore Tso]

On Sat, May 06, 2006 at 03:33:04PM -0500, Matt Mackall wrote:
> I'm not talking about any existing attacks, I'm talking about what
> would theoretically be possible were a first preimage attack on our
> hash to become practical.

Note that even the first preimage attack on a hash (none of which have
been demonstrated for MD-5, SHA-0, SHA-1, or reduced-round or
otherwise weakened versions of the same, as far as I know), would be
sufficient by itself to guarantee that the attacker would be able to
determine the contents of the entropy pool from the output stream.  A
preimage attack merely states that the attacker can find a _single_
input which hashes to a particular output value of the crypto
checksum.  Because we are hashing the entire pool to produce each
chunk of output, by the pigeonhole principle and the observed
statistical random distribution properties of the hash, there are a
very large number of potential pool values that could result in that
particular hash (we are compressing 4096 bits down to 80 bits).   

So a successful cryptographic attack would have to combine a
successful preimage attack of the cryptographic hash core with
additional refinements so that the preimage attack technique can
produce *multiple" (in fact, probably all possible) preimages, and
correlate that with the pool mixing function to successful rule out
preimages based on the successive outputs from the algorithm (assuming
that the attacker can determine the exact TSC timestamp when the
extraction happened, since that's mixed into the pool as part of the
extraction process).

The point is that we are using a *very* conservative design, unlike
Yarrow which used a minimally-sized entropy pool and which would be
far more vulnerable to the discovery of a preimage attack on the hash.

> All agreed. But that applies equally to /dev/urandom. The only thing that
> distinguishes the two is entropy accounting and entropy accounting
> only makes a difference if it's conservative. 

OK, but in that case, in order to make /dev/urandom as secure as
possible (which is what most programs would use anyway for things like
session keys, etc.), we shouldn't be throwing away the entropy from
network interrupts, but rather always collecting the input and merely
changing how much entropy credits to assign to various interrupts.

After all, the only application where /dev/random is really justified
is for key generation of long-term public/private keypairs, and in
those cases you almost always have a keyboard attached since the
security requirements are such that you probably don't want ot be
doing it remotely anyway.

My philosophy on the entropy accounting is that it isn't necessarily
accurate; sometimes it over-estimates entropy, and sometimes it
under-estimates entropy.  The main thing it does is to make it
significantly harder for an attacker to gather a huge number of data
points to use for carrying out a theoretical cryptographic attack.  It
provides additional security, but it isn't necessarily perfect
(nothing in this world is).

> Here's a threat model: I remotely break into your LAN and 0wn insecure
> Windows box X that's one switch jump away from the web server Y that
> processes your credit card transactions. I use standard techniques to
> kick the switch into broadcast mode so I can see all its traffic or
> maybe I break into the switch itself and temporarily isolate Y from
> the rest of the world so that only X can talk to it. I'm still in
> Russia, but I might as well be in the same room.

I could ask questions about why the insecure Windows box is on the
same network as the box processing the credit card transactions, or
how the attacker is familiar with the network topology, or knows the
clock frequencies of your CPU(s) and when your box was last rebooted
so it can make guesses about the TSC values that will be hashed in ---
or know which CPU (for SMP boxes) an interrupt will be processed on
since on current Intel/AMD boxes the TSC is not synchronized.  But
even if the attacker knows all of this, the attacker still doesn't
know the current starting point of the pool.   

> Again, I think it's perfectly reasonable to sample from all sorts of
> sources. All my issues are about the entropy accounting.

But in that case your patch which removes the call to add_entropy() is
probably not the right thing, yes?  Maybe making the amount of entropy
which is credited for each device interrupt ought to be configurable,
sure.  But we should be collecting the interrupt-arrival times
regardless of how much we bump the entropy accounting.

						- Ted

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sat, May 06, 2006 at 09:22:00PM -0400, Theodore Tso wrote:
> > Again, I think it's perfectly reasonable to sample from all sorts of
> > sources. All my issues are about the entropy accounting.
> 
> But in that case your patch which removes the call to add_entropy() is
> probably not the right thing, yes?

Note the emphatic "again", because I conceded that in my very first
response to you.

The question is, what is the right thing? Not what we have now.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Sami Farin]

On Sat, May 06, 2006 at 21:22:00 -0400, Theodore Tso wrote:
... 
> I could ask questions about why the insecure Windows box is on the
> same network as the box processing the credit card transactions, or
> how the attacker is familiar with the network topology, or knows the
> clock frequencies of your CPU(s) and when your box was last rebooted
> so it can make guesses about the TSC values that will be hashed in ---

Currently init_std_data plays only with do_gettimeofday and
system_utsname.  Why not also feed get_cycles(), jiffies, pointer
to init_std_data function or something to add_entropy_words?

For example, I notice that syncookie_secret is initialized very early
in the boot, and it's never written to again.
If system clock is +-1 s accurate at boot and kernel is from
some common distro, I wonder how secure syncookie_secret is.

And if I read correctly, get_random_int() keeps producing the
same output during the same jiffy, if CONFIG_X86_HAS_TSC is undef?
Why not create a new function for get_random_int()
(instead of just calling secure_ip_id())
which includes 64bit-counter, pid and jiffies in the hash given
to half_md4_transform?

Also, I believe add_input_randomness needs fixing.
I noticed that when using e.g. evdev in Xorg, one mouse movement or
button press causes eight events, and all of them are fed to
add_timer_randomness.  There maybe 7 out of 8 of the events
get 1 bit of entropy added because they happen on the same jiffy.

I have been playing with Fortuna patch (JLC's patch with 
dozens of fixes by me), and from looking at debug outputs,
it seems that last input "event" is marked by
  (type == 0) && (code == 0) && (value == 0) ...

So I am doing this way:
keep on jhash'ing type, code, value in add_input_randomness
till they're all-zeros,
then give the resulting u32 to add_timer_randomness.
jhash value can be static variable and you can ignore the
fact you are "mixing" different events from different
sources into the hash.

Now when I press and release ANY key (or e.g. click mouse button),
I get exactly two calls to add_timer_randomness, which each add
3-11 bits of entropy.  I think this is how it should work.
At least 3 bits doesn't sound too overestimated ;-O

And for disk events, maybe limit to at max a couple of
calls to add_timer_randomness per jiffy?
Maybe also limit similarly in add_input_randomness?
(For disk events I also add disk_stat_read(disk, sectors[0]/[1])
 as entropy)

For add_interrupt_randomness, if there anything what could
be added as entropy, besides irq and time?

http://safari.iki.fi/fortuna-random-2.6.16.14-safari.patch.bz2
Warning: enabling debug might produce sensitive data into log files
and/or console.
/proc/sys/kernel/random/debug specifies which debugs to produce
(valid values 0-63 , OR 1, 2, 4, 8, 16, 32 together).
If link does not seem to work, I am either rebooting a
a newer Fortuna version or my system blew up or I have
dropped your packets with netfilter.

What about adding entropy from data received from network?
For example, with netfilter module, pass every Nth checksum
from a packet (for example, from DNS replies) to
add_entropy_words() ?

> or know which CPU (for SMP boxes) an interrupt will be processed on
> since on current Intel/AMD boxes the TSC is not synchronized.  But
> even if the attacker knows all of this, the attacker still doesn't
> know the current starting point of the pool.   
...

-- 

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Marcin Dalecki]

On 2006-05-06, at 20:05, Theodore Tso wrote:

> Agreed, but I'd an additional point of nuance; this assumes that the
> attacker (call him Boris for the sake of argument) can actually gain
> access to enough /dev/random or /dev/urandom outputs, and be
> knowledgable about all other calls to /dev/random and exactly when
> they happen (since entropy extractions cause the TSC to be mixed into
> the pool) so Boris can can actually determine the contents of the
> pool.  Note that simply "breaking" a cryptographic hash, in the sense
> of finding two input values that collide to the same output value,
> does not mean that the hash has been sufficiently analyzed that it
> would be possible to accomplish this feat.  And given that it took
> 80,000 CPU hours to determine find this collision, and the complexity
> of the attack was 2**51, it seems highly likely that with a poolsize
> of 4096 bits, that it would take a huge amount of /dev/random
> extractions, complete with the exact TSC timestamp when the
> extractions were happening, such that an attacker would be able to
> have enough information to break the pool.

Anytime you start to make unquantified assumptions in the context of / 
dev/random
the issue turns up that this whole thing is not worth the trouble  
because much
simpler approaches will be sufficient enough to acomplish what it  
does. On the other
hand you can't provide any actual full analysis of it's behaviour -  
which is just
*not acceptable* for anybody trully concerned. And this in  
conjunction makes the WHOLE
idea behind it questionable.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Theodore Tso]

On Thu, May 25, 2006 at 12:47:18AM +0200, Marcin Dalecki wrote:
> Anytime you start to make unquantified assumptions in the context of
> / dev/random the issue turns up that this whole thing is not worth
> the trouble because much simpler approaches will be sufficient
> enough to acomplish what it does. On the other hand you can't
> provide any actual full analysis of it's behaviour - which is just
> *not acceptable* for anybody trully concerned. And this in
> conjunction makes the WHOLE idea behind it questionable.

Nobody can provide any kind of full analysis about whether or not
SHA-2 or AES is secure, either.  Does that we mean we just give up and
go home?  No, we do the best job we can, with the best information we
have.  Sometimes that means we have to make assumptions, but the
entire construction of AES and SHA-2 is based on similar assumptions,
too.

Academics who make "full analysis" generally use as axioms things like
"assume MD5 is secure" or "assume SHA-1 is secure", which are really
fancy assumptions.  If we had used a "simpler approaches" based such
axioms we might have been in trouble.  So I think some of the analysis
and designs choices that I made in /dev/random is most definitely
worth the trouble.

Regards,

						- Ted

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Bill Davidsen]

Theodore Tso wrote:
> On Thu, May 25, 2006 at 12:47:18AM +0200, Marcin Dalecki wrote:
>> Anytime you start to make unquantified assumptions in the context of
>> / dev/random the issue turns up that this whole thing is not worth
>> the trouble because much simpler approaches will be sufficient
>> enough to acomplish what it does. On the other hand you can't
>> provide any actual full analysis of it's behaviour - which is just
>> *not acceptable* for anybody trully concerned. And this in
>> conjunction makes the WHOLE idea behind it questionable.
> 
> Nobody can provide any kind of full analysis about whether or not
> SHA-2 or AES is secure, either.  Does that we mean we just give up and
> go home?  No, we do the best job we can, with the best information we
> have.  Sometimes that means we have to make assumptions, but the
> entire construction of AES and SHA-2 is based on similar assumptions,
> too.
> 
> Academics who make "full analysis" generally use as axioms things like
> "assume MD5 is secure" or "assume SHA-1 is secure", which are really
> fancy assumptions.  If we had used a "simpler approaches" based such
> axioms we might have been in trouble.  So I think some of the analysis
> and designs choices that I made in /dev/random is most definitely
> worth the trouble.
> 
> Regards,
> 
> 						- Ted
As usual I agree with you, for lack of a really good random source it's 
worth doing the best possible job with what's available. Would be nice 
to have a cheap USB bit babbler, tho.

-- 
Bill Davidsen <davidsen@tmr.com>
   Obscure bug of 2004: BASH BUFFER OVERFLOW - if bash is being run by a
normal user and is setuid root, with the "vi" line edit mode selected,
and the character set is "big5," an off-by-one errors occurs during
wildcard (glob) expansion.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[David S. Miller]

From: Matt Mackall <mpm@selenic.com>
Date: Sat, 6 May 2006 11:48:08 -0500

> But network traffic should be _assumed_ to be observable to some
> degree.

But, and this is a huge but and the one that matters, nothing
between the network packet arriving and the interrupt being
delivered is observable outside of the machine.

The PHY of the network card has some tiny delays internal
to how it decodes the coding sequence on the wire and passes
it on to the MAC.

The MAC and the bus frontend have all sorts of timing and
delays wrt. making sure the necessary RX descriptor is fetched
and if a free packet buffer is available, DMA'ing the packet
into memory.

If the chip has hw interrupt mitigation enabled, these add other
delays and almost across the board these interrupt mitigation
timers are relatively imprecise.  If the first packet that starts
the time hits half-way between two clock ticks, the mitigation
fire will be a half clock off.

There are propagation delays for the interrupt to get to the cpu.
Every implementation is there, but the delays are there and highly
variable.  In many cases, it's the time to send a cacheline over
the main system bus to the target cpu (MSI, or sparc64 style PCI
controllers which turn traditional INTX signals into 64-byte
interrupt packets targeted at specific cpus).

Then there is the trap entry delay, and perhaps the cpu has interrupts
disabled while holding a spinlock or whatever.  Then there are all the
cache misses and instruction execution delays just to get into the
interrupt handler.

None of this is observable or predictable outside of the machine.
So the arguments about the SA_SAMPLE_RANDOM samples being risky in
the networking drivers is bogus.

Please put together a test case that proves that /dev/random can
be predicted just by being on the wire sniffing packets going into
the machine.  Then you will have my full support.

Everything shown so far is theoretical swiss cheese.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sat, May 06, 2006 at 05:08:10PM -0700, David S. Miller wrote:
> From: Matt Mackall <mpm@selenic.com>
> Date: Sat, 6 May 2006 11:48:08 -0500
> 
> > But network traffic should be _assumed_ to be observable to some
> > degree.
> 
> Please put together a test case that proves that /dev/random can
> be predicted just by being on the wire sniffing packets going into
> the machine.  Then you will have my full support.

Sure.

First, since the existence of /dev/random's entropy accounting scheme
is predicated on the assumption that we can break the hash function at
will, I'll replace SHA1 with, oh, say, CRC-16. This'll be illustrative
until someone has a nice preimage attack against SHA1.

Then I'll run my test on one of the various arches where HZ=~100 and
we don't have a TSC. Like Sparc?

  /* XXX Maybe do something better at some point... -DaveM */
  typedef unsigned long cycles_t;
  #define get_cycles()    (0)
 
Now all the inputs are easily predictable from anywhere with <10ms
ping, with the occassional need to guess between a pair of timer
ticks. And since I can calculate preimages of CRC-16, I can now deduce
the state of the pool if I can watch some subset of its output, say
https session keys I request. And then I can start guessing future
outputs and breaking into other people's https sessions.

The point of /dev/random is to -survive- SHA1 being broken by never
giving out more secrets than we take in. That doesn't work if we give
it observable inputs and claim they're not observable, which is what
you're doing by setting SA_SAMPLE_RANDOM.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[David S. Miller]

From: Matt Mackall <mpm@selenic.com>
Date: Sat, 6 May 2006 23:59:20 -0500

> First, since the existence of /dev/random's entropy accounting scheme
> is predicated on the assumption that we can break the hash function at
> will, I'll replace SHA1 with, oh, say, CRC-16. This'll be illustrative
> until someone has a nice preimage attack against SHA1.

I don't understand why you're changing one of the preconditions
in order to "prove" that what we have now can be broken.  This
is more swiss cheese theory.

We use SHA1 right now, so you have to use SHA1 in your reproducable
attack.  Since there is no preimage attack for SHA1 you can't
prove that it can be done.

> Then I'll run my test on one of the various arches where HZ=~100 and
> we don't have a TSC. Like Sparc?
> 
>   /* XXX Maybe do something better at some point... -DaveM */
>   typedef unsigned long cycles_t;
>   #define get_cycles()    (0)

You're really stretching things here, using a platform that is
basically in almost no usage at all.  Sure if you use a silly
example, almost anything is possible.  CRC-16 and sparc 32-bit,
give me a break.

And the remote person has to know that the machine is a 32-bit sparc
box, good luck with that.  And this is yet another variable amongst
all of the highly variable and unpredictable delays between packet
visibility on the wire and the actual interrupt being serviced, which
you have not addressed at all.

You haven't addressed the real case that matters, the ones on
platforms that have a TSC that works and with SHA1.

Until you prove that can be broken, you are simply still spewing
more of your incredible swiss cheese theory.  Don't give me any
crap about an almost entirely abandoned architecture that doesn't
implement TSC, and using algorithms other than SHA1.  The real code
uses SHA1, so that's what you have to prove can be broken.

You're just circling around the real issues and trying to be "right"
and this is what I dislike so much about theoretical people.  They
show you what can be done theoretically, yet never in practice with
what we really have now.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sat, May 06, 2006 at 10:46:39PM -0700, David S. Miller wrote:
> You're just circling around the real issues and trying to be "right"
> and this is what I dislike so much about theoretical people.  They
> show you what can be done theoretically, yet never in practice with
> what we really have now.

What you're missing is this:

/dev/random's entropy counting scheme sole reason to exist is to
defend against theoretical future attacks against its cryptographic
primitives. Thus _any_ discussion of its correctness must perforce be
theoretical.

By substituting CRC-16 for SHA1, I've simply brought the future 
attack we're concerned about to today.

As I said at the beginning of this thread, I'm perfectly happy to
continue taking samples from network devices. My concerns are entirely
with how we account their entropy, which is strictly in the realm of
theory to start with.

I will instead change the entropy estimator to be more conservative
and to note the presence of high resolution clocks so that we can feed
it garbage more safely.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Thiago Galesi]

> Sure.
>
> First, since the existence of /dev/random's entropy accounting scheme
> is predicated on the assumption that we can break the hash function at
> will, I'll replace SHA1 with, oh, say, CRC-16. This'll be illustrative
> until someone has a nice preimage attack against SHA1.
>
> Then I'll run my test on one of the various arches where HZ=~100 and
> we don't have a TSC. Like Sparc?
>
> Now all the inputs are easily predictable from anywhere with <10ms
> ping, with the occassional need to guess between a pair of timer
> ticks. And since I can calculate preimages of CRC-16, I can now deduce
> the state of the pool if I can watch some subset of its output, say
> https session keys I request. And then I can start guessing future
> outputs and breaking into other people's https sessions.
>
> The point of /dev/random is to -survive- SHA1 being broken by never
> giving out more secrets than we take in.

OK, here goes...

1 - by eliminating feeding enthopy from network cards you are
eliminating all sources of enthropy for _lots_ of people (think
headless servers, embedded systems - even though there can be other
sources of enthropy there) Unfortunatelly, bad enthropy is still
better than no enthropy (just think - no ssh / https, etc, etc)

2 - some platforms have much better enthropy sources than ethernet (or
user input), just think hardware rngs, or even the sound card rng
thing mentioned above

3 - as people said, your example (CRC-16 on specific platfoms) is
(IMHO) an exxageration. Of course, /dev/random should try and protect
us from whatever protocol being broken. That being said, this
protection should be 'realistic'. In theory most things are broken if
we have enough equipment and computing power.

My conclusion, I have no problem removing SA_SAMPLE_RANDOM *IN
SPECIFIC CASES* (meaning, this should be user configurable). In a
secure environment / platform has rng, it could be turned off, and in
a headless server / embedded system / it could be left on.

Of course, that's just MHO...

Thiago

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sun, May 07, 2006 at 10:13:50AM -0300, Thiago Galesi wrote:
> >Sure.
> >
> >First, since the existence of /dev/random's entropy accounting scheme
> >is predicated on the assumption that we can break the hash function at
> >will, I'll replace SHA1 with, oh, say, CRC-16. This'll be illustrative
> >until someone has a nice preimage attack against SHA1.
> >
> >Then I'll run my test on one of the various arches where HZ=~100 and
> >we don't have a TSC. Like Sparc?
> >
> >Now all the inputs are easily predictable from anywhere with <10ms
> >ping, with the occassional need to guess between a pair of timer
> >ticks. And since I can calculate preimages of CRC-16, I can now deduce
> >the state of the pool if I can watch some subset of its output, say
> >https session keys I request. And then I can start guessing future
> >outputs and breaking into other people's https sessions.
> >
> >The point of /dev/random is to -survive- SHA1 being broken by never
> >giving out more secrets than we take in.
> 
> OK, here goes...
> 
> 1 - by eliminating feeding enthopy from network cards you are

Keep up, folks, I dropped that position in the very first round of replies.
 
> 2 - some platforms have much better enthropy sources than ethernet (or
> user input), just think hardware rngs, or even the sound card rng
> thing mentioned above

Point?

> 3 - as people said, your example (CRC-16 on specific platfoms) is
> (IMHO) an exxageration.

Yes, CRC-16 was a rhetorical device. MD4 would not have been. HZ=100
is not an exaggeration. Odds are pretty good you have such a Linux box
in the form of a router or such already. This completely invalidates
all the arguments about the hardware making the timing too
unpredictable as it does so on a timescale of microseconds or less.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Thiago Galesi]

> >
> > OK, here goes...
> >
> > 1 - by eliminating feeding enthopy from network cards you are
>
> Keep up, folks, I dropped that position in the very first round of replies.

>As I said at the beginning of this thread, I'm perfectly happy to
>continue taking samples from network devices. My concerns are entirely
>with how we account their entropy, which is strictly in the realm of
>theory to start with.

ok, now I get it...

>
> > 2 - some platforms have much better enthropy sources than ethernet (or
> > user input), just think hardware rngs, or even the sound card rng
> > thing mentioned above
>
> Point?

Point is, sometimes you have plenty of enthropy available and
sometimes you only have the network card (and maybe an HD). Two
different situations, in one of them we can accept (it's even beter)
not acquiring enthropy from the network card completely.

>
> > 3 - as people said, your example (CRC-16 on specific platfoms) is
> > (IMHO) an exxageration.
>
> Yes, CRC-16 was a rhetorical device. MD4 would not have been. HZ=100
> is not an exaggeration.

Agreed

 Odds are pretty good you have such a Linux box
> in the form of a router or such already. This completely invalidates
> all the arguments about the hardware making the timing too
> unpredictable as it does so on a timescale of microseconds or less.

Yes, that situation is pretty common.

Here is my point: I don't think the kernel shoud "try very hard" to
fix "lack of good enthropy sources". Yes, you've presented situations
where someone (ultimately) could guess what is being read from
/dev/random.

In practice, though, it should ultimatelly fall upon the
end-user/developer to have a system with good enough (for him/her)
enthropy sources. If he is happy with lots of "bad enthropy" so be it.
Hovever, if he wants / needs to be sure that /dev/random is not
predictable, (IMHO) he can always plug a hardware RNG and only read
from that (hence what I said about configuring who are your enthropy
sources).

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Theodore Tso]

On Sun, May 07, 2006 at 11:00:14AM -0500, Matt Mackall wrote:
> Yes, CRC-16 was a rhetorical device. MD4 would not have been. 

MD4 is succeptible to a 2nd pre-image attack, yes.  This means that
given a specific message and its MD4 checksum, you can find another
message which will have the same MD4 checksum.  But that doesn't help
you at all if you only have the MD4 checksum.  And even the 2nd
pre-image attack still requires O(2**40) operations.  That's within
the reach of modern CPU's yes, but that simply gives you a *second*
pre-image that has the same MD4 checksum as original message.  

In order to crack the entropy pool, you need a large number of outputs
from /dev/random, and be able to find a large number of pre-images
very rapidly.  This is the main reason why I believe the entropy
accounting is still useful.  Even if the entropy accounting is off by
several orders of magnitude, it is still useful, since the attacks
that we're talking about will very likely require a huge number of
data points.  For example, the most powerful cryptoanalytic attack
against DES still requires 2**43 plaintext/ciphertext pairs.

But in answer to your question, what should we do, my suggestion would
be to sample all interrupts, and calculate the estimated entropy
credits as we to day, but scaled by an amount that can range from 0 to
100%.  This amount can be configured by system administrators, and
will have intelligent defaults for each device driver to the amount of
entropy should be credited for a particular device.  If we care, we
can set the default percentage scalaing factor for platforms with no
TSC reguster and HZ=100 to be zero.  But for most normal/modern
platforms, I would argue the default scaling factor should be 100%.

The bottom line is this is much ado about nothing.  As I have said,
most programs use /dev/urandom, not /dev/random; the only really
appropriate use of /dev/random is to generate long-term public/private
keypairs, or perhaps to seed some other cryptographic random number
generator (like /dev/urandom).

						- Ted

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sun, May 07, 2006 at 08:13:33PM -0400, Theodore Tso wrote:
> But in answer to your question, what should we do, my suggestion would
> be to sample all interrupts, and calculate the estimated entropy
> credits as we to day, but scaled by an amount that can range from 0 to
> 100%.

I actually posted a patch to add a sysctl to do exactly that a few
years ago.

> But for most normal/modern platforms, I would argue the default
> scaling factor should be 100%.

And I would argue it should be no more than 50%. Just because I've
seen so many would-have-thought-they-were-impossible attacks pan out.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Pavel Machek]

Hi!

> Then I'll run my test on one of the various arches where HZ=~100 and
> we don't have a TSC. Like Sparc?
> 
>   /* XXX Maybe do something better at some point... -DaveM */
>   typedef unsigned long cycles_t;
>   #define get_cycles()    (0)

Seems like sparc32 is broken :-(, and probably broken terminally...
there are very little randomness sources that can handle 10msec
sampling period :-(.

Maybe we should disable /dev/random on sparc32?
-- 
Thanks for all the (sleeping) penguins.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[David S. Miller]

From: Pavel Machek <pavel@suse.cz>
Date: Mon, 8 May 2006 06:26:05 +0000

> > Then I'll run my test on one of the various arches where HZ=~100 and
> > we don't have a TSC. Like Sparc?
> > 
> >   /* XXX Maybe do something better at some point... -DaveM */
> >   typedef unsigned long cycles_t;
> >   #define get_cycles()    (0)
> 
> Seems like sparc32 is broken :-(, and probably broken terminally...
> there are very little randomness sources that can handle 10msec
> sampling period :-(.
> 
> Maybe we should disable /dev/random on sparc32?

What do other platforms without a TSC do?

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Mon, May 08, 2006 at 12:07:54AM -0700, David S. Miller wrote:
> From: Pavel Machek <pavel@suse.cz>
> Date: Mon, 8 May 2006 06:26:05 +0000
> 
> > > Then I'll run my test on one of the various arches where HZ=~100 and
> > > we don't have a TSC. Like Sparc?
> > > 
> > >   /* XXX Maybe do something better at some point... -DaveM */
> > >   typedef unsigned long cycles_t;
> > >   #define get_cycles()    (0)
> > 
> > Seems like sparc32 is broken :-(, and probably broken terminally...
> > there are very little randomness sources that can handle 10msec
> > sampling period :-(.
> > 
> > Maybe we should disable /dev/random on sparc32?
> 
> What do other platforms without a TSC do?

Using get_cycles() for /dev/random is new as of 2.6. Before that, we
were directly calling rdtsc on x86 alone. 10msec resolution is fine
for plenty of sources.

>From a brief glance, the following don't have a useful get_cycles:

v850, sh, sh64, h8300, m32r, arm, arm26, cris, frv, um, m68k, xtensa,
sparc

And several others like mips (and x86) have one on only some hardware.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Pavel Machek]

Hi!

> > What do other platforms without a TSC do?
> 
> Using get_cycles() for /dev/random is new as of 2.6. Before that, we
> were directly calling rdtsc on x86 alone. 10msec resolution is fine
> for plenty of sources.

For what devices are timestamps still 'random/unobservable' in 10msec
range?

Maybe keyboard... but no, keyboard has autorepeat and can be observed
remotely with 10msec accuracy in many cases. (telnet to bbs?)

Disk requests take less than 10msec.

It is trivial to measure packets with 10msec accuracy.

Mouse will generate many events within 10msec when user actually uses
it.

...so, what devices are still random with 10msec sampling?
-- 
Thanks for all the (sleeping) penguins.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Mon, May 08, 2006 at 05:21:12PM +0000, Pavel Machek wrote:
> Hi!
> 
> > > What do other platforms without a TSC do?
> > 
> > Using get_cycles() for /dev/random is new as of 2.6. Before that, we
> > were directly calling rdtsc on x86 alone. 10msec resolution is fine
> > for plenty of sources.
> 
> For what devices are timestamps still 'random/unobservable' in 10msec
> range?
> 
> Maybe keyboard... but no, keyboard has autorepeat and can be observed
> remotely with 10msec accuracy in many cases. (telnet to bbs?)

Please go look at the code.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Pavel Machek]

On Po 08-05-06 12:27:26, Matt Mackall wrote:
> On Mon, May 08, 2006 at 05:21:12PM +0000, Pavel Machek wrote:
> > Hi!
> > 
> > > > What do other platforms without a TSC do?
> > > 
> > > Using get_cycles() for /dev/random is new as of 2.6. Before that, we
> > > were directly calling rdtsc on x86 alone. 10msec resolution is fine
> > > for plenty of sources.
> > 
> > For what devices are timestamps still 'random/unobservable' in 10msec
> > range?
> > 
> > Maybe keyboard... but no, keyboard has autorepeat and can be observed
> > remotely with 10msec accuracy in many cases. (telnet to bbs?)
> 
> Please go look at the code.

Ok, so perhaps it got autorepeat right. Still you claimed "plenty" of
usable sources, and keyboard is remotely observable. Please show me
"plenty".
								Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Ph. Marek]

On Monday 08 May 2006 19:21, Pavel Machek wrote:
> Hi!
>
> > > What do other platforms without a TSC do?
> >
> > Using get_cycles() for /dev/random is new as of 2.6. Before that, we
> > were directly calling rdtsc on x86 alone. 10msec resolution is fine
> > for plenty of sources.
>
> For what devices are timestamps still 'random/unobservable' in 10msec
> range?
>
> Maybe keyboard... but no, keyboard has autorepeat and can be observed
> remotely with 10msec accuracy in many cases. (telnet to bbs?)
>
> Disk requests take less than 10msec.
>
> It is trivial to measure packets with 10msec accuracy.
>
> Mouse will generate many events within 10msec when user actually uses
> it.
>
> ...so, what devices are still random with 10msec sampling?
There may be no devices with randomness in 10msec ...

... but how about the *count* of events during 10msec?

Keyboard presses may be observable from outside, but disk accesses, network 
interrupts, mouse moves etc. .... especially if the (outside) accesses have 
to be correlated to the (internal) timer interrupt.

Get the count of events in 10msec, take the lowest bit. In 1.28 seconds you'll 
get your 128bit key.

Or, to be conservative, take only the XOR of 8 consecutive bits ... then 
you'll have to wait 10 seconds, but will be a bit more secure.

Such a mechanism could even be used on machines with TSC ... just do an 
(non-locked) increment of some counter, reset it on every jiffie, and take a 
bit of entropy.


How about that?



Regards,

Phil

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Marcin Dalecki]

On 2006-05-05, at 21:11, Theodore Tso wrote:

> I've always thought the right answer is that whether or not network
> packet arrival times should be used as entropy input should be
> configurable, since depending on the environment, it might or might
> not be safe, and for some hosts (particularly diskless servers), the
> network might be the only source of entropy available to them.

The trully concerned should simply use true random number generators.  
Like a zenner diodes noise.
For everybody else... most if not all of what /dev/random does, just  
simply
isn't worth the trouble at all. Thus the less of it the better.
BTW. Did somebody notice that the whole disc seek time dance around / 
dev/random does,
is quite idiotic for deterministic flash drives? It will screw yours  
"randomness" silently...

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[David S. Miller]

From: Matt Mackall <mpm@selenic.com>
Date: Fri, 05 May 2006 11:42:35 -0500

> Remove SA_SAMPLE_RANDOM from network drivers
> 
> /dev/random wants entropy sources to be both unpredictable and
> unobservable. Network devices are neither as they may be directly
> observed and controlled by an attacker. Thus SA_SAMPLE_RANDOM is not
> appropriate.
> 
> Signed-off-by: Matt Mackall <mpm@selenic.com>

Besides the other issues discussed, what you are doing is
essentially making a headless machine with a quiet disk have
next to zero entropy available.

I don't think we can seriously consider this patch, as I've seen real
users run into this lack of entropy issue.

If you want to do a generic thing in the networking to create
entropy, fine, but it must be on by default or else people in
the above situation (and there are many) will have an unusable
/dev/random and friends.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Fri, May 05, 2006 at 02:10:40PM -0700, David S. Miller wrote:
> From: Matt Mackall <mpm@selenic.com>
> Date: Fri, 05 May 2006 11:42:35 -0500
> 
> > Remove SA_SAMPLE_RANDOM from network drivers
> > 
> > /dev/random wants entropy sources to be both unpredictable and
> > unobservable. Network devices are neither as they may be directly
> > observed and controlled by an attacker. Thus SA_SAMPLE_RANDOM is not
> > appropriate.
> > 
> > Signed-off-by: Matt Mackall <mpm@selenic.com>
> 
> Besides the other issues discussed, what you are doing is
> essentially making a headless machine with a quiet disk have
> next to zero entropy available.
> 
> I don't think we can seriously consider this patch, as I've seen real
> users run into this lack of entropy issue.

And my claim is they don't actually have any entropy. If they want to
continue fooling themselves, they can copy the device node for
/dev/urandom to /dev/random.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[David S. Miller]

From: Matt Mackall <mpm@selenic.com>
Date: Fri, 5 May 2006 18:03:24 -0500

> And my claim is they don't actually have any entropy. If they want
> to continue fooling themselves, they can copy the device node for
> /dev/urandom to /dev/random.

Prove it and convince us.

The burdon of proof is on your shoulders, since you're the one
who wants to just rip it out without any satisfactory replacement.

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Folkert van Heusden]

> > Remove SA_SAMPLE_RANDOM from network drivers
> > /dev/random wants entropy sources to be both unpredictable and
> > unobservable. Network devices are neither as they may be directly
> > observed and controlled by an attacker. Thus SA_SAMPLE_RANDOM is not
> > appropriate.
> Besides the other issues discussed, what you are doing is
> essentially making a headless machine with a quiet disk have
> next to zero entropy available.

Consider adding a cheap soundcard to the system and run
'audio-entropyd': www.vanheusden.com/aed


Folkert van Heusden

-- 
www.biglumber.com <- site where one can exchange PGP key signatures 
----------------------------------------------------------------------
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Lee Revell]

On Sat, 2006-05-06 at 16:08 +0200, Folkert van Heusden wrote:
> Consider adding a cheap soundcard to the system and run
> 'audio-entropyd': www.vanheusden.com/aed 

Can't get much cheaper than the crap that comes on every motherboard
these days ;-)

Also aren't temp sensors (on the disk or mobo) a good entropy source?

Lee

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Folkert van Heusden]

> > Consider adding a cheap soundcard to the system and run
> > 'audio-entropyd': www.vanheusden.com/aed 
> Can't get much cheaper than the crap that comes on every motherboard
> these days ;-)
> Also aren't temp sensors (on the disk or mobo) a good entropy source?

Not sure about that. If I look at
http://keetweej.vanheusden.com/draw_temp.php?limit=86400 it looks like
that at least the cpu sensor gets only updated every x seconds.


Folkert van Heusden

-- 
Feeling generous? -> http://www.vanheusden.com/wishlist.php
----------------------------------------------------------------------
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com

Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers

[Matt Mackall]

On Sun, May 07, 2006 at 12:35:08PM +0200, Folkert van Heusden wrote:
> > > Consider adding a cheap soundcard to the system and run
> > > 'audio-entropyd': www.vanheusden.com/aed 
> > Can't get much cheaper than the crap that comes on every motherboard
> > these days ;-)
> > Also aren't temp sensors (on the disk or mobo) a good entropy source?
> 
> Not sure about that. If I look at
> http://keetweej.vanheusden.com/draw_temp.php?limit=86400 it looks like
> that at least the cpu sensor gets only updated every x seconds.

Yeah, heat sensors are not terribly useful. Thermal insulation acts as
a very aggressive low pass filter on whatever noise might exist in the
input.

-- 
Mathematics is the supreme nostalgia of our time.