ocf-linux-20050315 - Asynchronous Crypto support for linux

ocf-linux-20050315 - Asynchronous Crypto support for linux

[David McCullough]

Hi all,

The latest release of ocf-linux (20050315) is available for download
from the project page:

	http://ocf-linux.sourceforge.net/

This release includes the following changes:

	* Hifn PLL bug fixes
	* Makefile fixes for 2.6 builds
	* 2.6.11 and 2.4.29 patches
	* cleanups for x86 builds

OCF-Linux is a Linux port of the OpenBSD/FreeBSD Cryptographic Framework
(OCF). This port aims to bring full asynchronous HW/SW crypto
acceleration to the Linux kernel and applications running under Linux.
Results have shown improvements of up to 7 times that of software crypto
for bulk crypto throughput using OpenSSL.

At this point in time OCF-Linux provides acceleration for OpenSSL,
OpenSSH (scp, ssh, ...) and also supports the BSD crypto testing
applications. It can accelerate DES, 3DES, AES, MD5, SHA, and Public Key
operations with plans to include Random Number generators and more. This
project is being actively developed as a high performance crypto
solution for embedded devices but also applies equally well to any linux
based server or desktop.

Cheers,
Davidm

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

[PATCH] API for true Random Number Generators to add entropy (2.6.11)

[David McCullough]

Hi all,

Here is a small patch for 2.6.11 that adds a routine:

	add_true_randomness(__u32 *buf, int nwords);

so that true random number generator device drivers can add a entropy
to the system.  Drivers that use this can be found in the latest release
of ocf-linux,  an asynchronous crypto implementation for linux based on
the *BSD Cryptographic Framework.

	http://ocf-linux.sourceforge.net/

Adding this can dramatically improve the performance of /dev/random on
small embedded systems which do not generate much entropy.

Cheers,
Davidm

Signed-off-by: David McCullough <davidm@snapgear.com>

Index: linux-2.6.11/include/linux/random.h
===================================================================
RCS file: linux-2.6.11/include/linux/random.h,v
retrieving revision 1.1.1.6
diff -u -r1.1.1.6 random.h
--- linux-2.6.11/include/linux/random.h	3 Mar 2005 00:45:49 -0000	1.1.1.6
+++ linux-2.6.11/include/linux/random.h	18 Mar 2005 01:46:16 -0000
@@ -48,6 +48,8 @@
 				 unsigned int value);
 extern void add_interrupt_randomness(int irq);
 
+extern void add_true_randomness(__u32 *buf, int nwords);
+
 extern void get_random_bytes(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
 
Index: linux-2.6.11/drivers/char/random.c
===================================================================
RCS file: linux-2.6.x/drivers/char/random.c,v
retrieving revision 1.1.1.28
diff -u -r1.1.1.28 random.c
--- linux-2.6.11/drivers/char/random.c	3 Mar 2005 00:45:31 -0000	1.1.1.28
+++ linux-2.6.11/drivers/char/random.c	18 Mar 2005 01:46:16 -0000
@@ -902,6 +902,39 @@
 
 EXPORT_SYMBOL(add_disk_randomness);
 
+/*
+ * provide a mechanism for HW to add entropy that is of
+ * very good quality from a true random number generator
+ */
+void add_true_randomness(__u32 *buf, int nwords)
+{
+	struct entropy_store *r;
+	int wakeup_check = 0;
+
+
+	if (!random_state || !sec_random_state)
+		return;
+
+	/*
+	 * if we have too much entropy, put some in the secondary pool
+	 */
+	r = random_state;
+	if (r->entropy_count >= r->poolinfo.POOLBITS)
+		r = sec_random_state;
+	else
+		wakeup_check = (r->entropy_count < random_read_wakeup_thresh);
+
+	add_entropy_words(r, buf, nwords);
+	credit_entropy_store(r, nwords * 32);
+
+	/*
+	 * wakeup if we added enough entropy to cross the threshold
+	 */
+	if (wakeup_check && r->entropy_count >= random_read_wakeup_thresh)
+		wake_up_interruptible(&random_read_wait);
+}
+EXPORT_SYMBOL(add_true_randomness);
+
 /******************************************************************
  *
  * Hash function definition

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

[PATCH] API for true Random Number Generators to add entropy (2.4.29)

[David McCullough]

Hi all,

Here is a small patch for 2.4.29 that adds a routine:

	add_true_randomness(__u32 *buf, int nwords);

so that true random number generator device drivers can add a entropy
to the system.  Drivers that use this can be found in the latest release
of ocf-linux,  an asynchronous crypto implementation for linux based on
the *BSD Cryptographic Framework.

	http://ocf-linux.sourceforge.net/

Adding this can dramatically improve the performance of /dev/random on
small embedded systems which do not generate much entropy.

Cheers,
Davidm

Signed-off-by: David McCullough <davidm@snapgear.com>

Index: linux-2.4.29/include/linux/random.h
===================================================================
RCS file: /cvs/sw/linux-2.4.29/include/linux/random.h,v
retrieving revision 1.1.1.1
retrieving revision 1.3
diff -u -r1.1.1.1 -r1.3
--- linux-2.4.29/include/linux/random.h	9 Jul 2001 00:39:16 -0000	1.1.1.1
+++ linux-2.4.29/include/linux/random.h	18 Mar 2005 04:33:35 -0000	1.3
@@ -52,6 +52,7 @@
 extern void add_mouse_randomness(__u32 mouse_data);
 extern void add_interrupt_randomness(int irq);
 extern void add_blkdev_randomness(int major);
+extern void add_true_randomness(__u32 *buf, int nwords);
 
 extern void get_random_bytes(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
Index: linux-2.4.29/drivers/char/random.c
===================================================================
RCS file: /cvs/sw/linux-2.4.29/drivers/char/random.c,v
retrieving revision 1.1.1.9
retrieving revision 1.11
diff -u -r1.1.1.9 -r1.11
--- linux-2.4.29/drivers/char/random.c	4 Feb 2005 00:28:36 -0000	1.1.1.9
+++ linux-2.4.29/drivers/char/random.c	18 Mar 2005 04:33:35 -0000	1.11
@@ -842,6 +837,39 @@
 	add_timer_randomness(blkdev_timer_state[major], 0x200+major);
 }
 
+/*
+ * provide a mechanism for HW RNG's to add entropy that is of
+ * very good quality.
+ */
+void add_true_randomness(__u32 *buf, int nwords)
+{
+	struct entropy_store *r;
+	int wakeup_check = 0;
+
+
+	if (!random_state || !sec_random_state)
+		return;
+
+	/*
+	 * if we have too much entropy, put some in the secondary pool
+	 */
+	r = random_state;
+	if (r->entropy_count >= r->poolinfo.POOLBITS)
+		r = sec_random_state;
+	else
+		wakeup_check = (r->entropy_count < random_read_wakeup_thresh);
+
+	add_entropy_words(r, buf, nwords);
+	credit_entropy_store(r, nwords * 32);
+
+	/*
+	 * wakeup if we added enough entropy to cross the threshold
+	 */
+	if (wakeup_check && r->entropy_count >= random_read_wakeup_thresh)
+		wake_up_interruptible(&random_read_wait);
+}
+EXPORT_SYMBOL(add_true_randomness);
+
 /******************************************************************
  *
  * Hash function definition

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

On Thu, Mar 24, 2005 at 02:27:08PM +1000, David McCullough wrote:
> 
> Hi all,
> 
> Here is a small patch for 2.6.11 that adds a routine:
> 
> 	add_true_randomness(__u32 *buf, int nwords);
> 
> so that true random number generator device drivers can add a entropy
> to the system.  Drivers that use this can be found in the latest release
> of ocf-linux,  an asynchronous crypto implementation for linux based on
> the *BSD Cryptographic Framework.
> 
> 	http://ocf-linux.sourceforge.net/
> 
> Adding this can dramatically improve the performance of /dev/random on
> small embedded systems which do not generate much entropy.

We've already had hardware RNG support for a while now.

No kernel patching needed.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[David McCullough]

Jivin Jeff Garzik lays it down ...
> On Thu, Mar 24, 2005 at 02:27:08PM +1000, David McCullough wrote:
> > 
> > Hi all,
> > 
> > Here is a small patch for 2.6.11 that adds a routine:
> > 
> > 	add_true_randomness(__u32 *buf, int nwords);
> > 
> > so that true random number generator device drivers can add a entropy
> > to the system.  Drivers that use this can be found in the latest release
> > of ocf-linux,  an asynchronous crypto implementation for linux based on
> > the *BSD Cryptographic Framework.
> > 
> > 	http://ocf-linux.sourceforge.net/
> > 
> > Adding this can dramatically improve the performance of /dev/random on
> > small embedded systems which do not generate much entropy.
> 
> We've already had hardware RNG support for a while now.
> 
> No kernel patching needed.

Are you talking about /dev/hw_random ?  If not then sorry I didn't see it :-(

On a lot of the small systems I work on,  /dev/random is completely
unresponsive,  and all the apps use /dev/random,  not /dev/hw_random.

Would you suggest making /dev/random point to /dev/hw_random then ?

Thanks,
Davidm

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Michal Ludvig]

David McCullough wrote:

> Are you talking about /dev/hw_random ?  If not then sorry I didn't see it :-(
> 
> On a lot of the small systems I work on,  /dev/random is completely
> unresponsive,  and all the apps use /dev/random,  not /dev/hw_random.
> 
> Would you suggest making /dev/random point to /dev/hw_random then ?

Or feed the entropy pool from hw_random?

Michal Ludvig

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

David McCullough wrote:
> Jivin Jeff Garzik lays it down ...
> 
>>On Thu, Mar 24, 2005 at 02:27:08PM +1000, David McCullough wrote:
>>
>>>Hi all,
>>>
>>>Here is a small patch for 2.6.11 that adds a routine:
>>>
>>>	add_true_randomness(__u32 *buf, int nwords);
>>>
>>>so that true random number generator device drivers can add a entropy
>>>to the system.  Drivers that use this can be found in the latest release
>>>of ocf-linux,  an asynchronous crypto implementation for linux based on
>>>the *BSD Cryptographic Framework.
>>>
>>>	http://ocf-linux.sourceforge.net/
>>>
>>>Adding this can dramatically improve the performance of /dev/random on
>>>small embedded systems which do not generate much entropy.
>>
>>We've already had hardware RNG support for a while now.
>>
>>No kernel patching needed.
> 
> 
> Are you talking about /dev/hw_random ?  If not then sorry I didn't see it :-(
> 
> On a lot of the small systems I work on,  /dev/random is completely
> unresponsive,  and all the apps use /dev/random,  not /dev/hw_random.
> 
> Would you suggest making /dev/random point to /dev/hw_random then ?

All the apps are supposed to use /dev/random, so that's correct.

For Hardware RNGs, userspace rngd daemon obtains entropy, checks it 
(mainly checking for hardware failures), and then stuffs entropy into 
the kernel random device.   http://sf.net/projects/gkernel/

On the "to do" list is making rngd directly generate entropy use 
'xstore' on VIA CPUs, rather than going kernel -> userland -> kernel.

Also, there are other entropy daemons floating about.  I think there is 
one that obtains noise from an audio device.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Folkert van Heusden]

> Also, there are other entropy daemons floating about.  I think there is 
> one that obtains noise from an audio device.

That's correct: http://www.vanheusden.com/aed/ audio-entropyd

There's also one for doing the same with video4linux devices: 
http://www.vanheusden.com/ved/


Folkert van Heusden

Auto te koop! Zie: http://www.vanheusden.com/daihatsu.php
Op zoek naar een IT of Finance baan? Mail me voor de mogelijkheden!
+------------------------------------------------------------------+
|UNIX admin? Then give MultiTail (http://vanheusden.com/multitail/)|
|a try, it brings monitoring logfiles to a different level! See    |
|http://vanheusden.com/multitail/features.html for a feature list. |
+------------------------------------------= www.unixsoftware.nl =-+
Phone: +31-6-41278122, PGP-key: 1F28D8AE
Get your PGP/GPG key signed at www.biglumber.com!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[David McCullough]

Jivin Jeff Garzik lays it down ...
> David McCullough wrote:
> >Jivin Jeff Garzik lays it down ...
> >
> >>On Thu, Mar 24, 2005 at 02:27:08PM +1000, David McCullough wrote:
> >>
> >>>Hi all,
> >>>
> >>>Here is a small patch for 2.6.11 that adds a routine:
> >>>
> >>>	add_true_randomness(__u32 *buf, int nwords);
> >>>
> >>>so that true random number generator device drivers can add a entropy
> >>>to the system.  Drivers that use this can be found in the latest release
> >>>of ocf-linux,  an asynchronous crypto implementation for linux based on
> >>>the *BSD Cryptographic Framework.
> >>>
> >>>	http://ocf-linux.sourceforge.net/
> >>>
> >>>Adding this can dramatically improve the performance of /dev/random on
> >>>small embedded systems which do not generate much entropy.
> >>
> >>We've already had hardware RNG support for a while now.
> >>
> >>No kernel patching needed.
> >
> >
> >Are you talking about /dev/hw_random ?  If not then sorry I didn't see it 
> >:-(
> >
> >On a lot of the small systems I work on,  /dev/random is completely
> >unresponsive,  and all the apps use /dev/random,  not /dev/hw_random.
> >
> >Would you suggest making /dev/random point to /dev/hw_random then ?
> 
> All the apps are supposed to use /dev/random, so that's correct.

Ok

> For Hardware RNGs, userspace rngd daemon obtains entropy, checks it 
> (mainly checking for hardware failures), and then stuffs entropy into 
> the kernel random device.   http://sf.net/projects/gkernel/
> 
> On the "to do" list is making rngd directly generate entropy use 
> 'xstore' on VIA CPUs, rather than going kernel -> userland -> kernel.
> 
> Also, there are other entropy daemons floating about.  I think there is 
> one that obtains noise from an audio device.

I had looked at hw_random,  but it seemed a little platform specific (x86),
and it doesn't currently have a way for RNG providers to register themselves.
Admittedly I did not know how it's output was being used in practice.

The drivers I am working with do crypto/public key and RNG.  Not all of
them can easily have the RNG support taken from the driver and plugged
into hw_random.c,  since it is (in most cases) a single PCI chip with
it's own  registers, initialisation and configuration,  that,  IMO
belongs in the driver for the particular chip.

Not that it isn't possible,  but hw_random would start supporting a
much larger number of HW variants and I think it would get ugly.

It would be possible to add a "register" interface to hw_random so that
you can register other RNG's easily.  This would seem reasonable.

I work on fairly resource constrained embedded devices a lot of the
time, so when I can avoid adding applications and reduce kernel size,
I do.  Thus my motivation to add a simple API for adding entropy to
/dev/random.

Cheers,
Davidm

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

David McCullough wrote:
> Jivin Jeff Garzik lays it down ...
> 
>>David McCullough wrote:
>>
>>>Jivin Jeff Garzik lays it down ...
>>>
>>>
>>>>On Thu, Mar 24, 2005 at 02:27:08PM +1000, David McCullough wrote:
>>>>
>>>>
>>>>>Hi all,
>>>>>
>>>>>Here is a small patch for 2.6.11 that adds a routine:
>>>>>
>>>>>	add_true_randomness(__u32 *buf, int nwords);
>>>>>
>>>>>so that true random number generator device drivers can add a entropy
>>>>>to the system.  Drivers that use this can be found in the latest release
>>>>>of ocf-linux,  an asynchronous crypto implementation for linux based on
>>>>>the *BSD Cryptographic Framework.
>>>>>
>>>>>	http://ocf-linux.sourceforge.net/
>>>>>
>>>>>Adding this can dramatically improve the performance of /dev/random on
>>>>>small embedded systems which do not generate much entropy.
>>>>
>>>>We've already had hardware RNG support for a while now.
>>>>
>>>>No kernel patching needed.
>>>
>>>
>>>Are you talking about /dev/hw_random ?  If not then sorry I didn't see it 
>>>:-(
>>>
>>>On a lot of the small systems I work on,  /dev/random is completely
>>>unresponsive,  and all the apps use /dev/random,  not /dev/hw_random.
>>>
>>>Would you suggest making /dev/random point to /dev/hw_random then ?
>>
>>All the apps are supposed to use /dev/random, so that's correct.
> 
> 
> Ok
> 
> 
>>For Hardware RNGs, userspace rngd daemon obtains entropy, checks it 
>>(mainly checking for hardware failures), and then stuffs entropy into 
>>the kernel random device.   http://sf.net/projects/gkernel/
>>
>>On the "to do" list is making rngd directly generate entropy use 
>>'xstore' on VIA CPUs, rather than going kernel -> userland -> kernel.
>>
>>Also, there are other entropy daemons floating about.  I think there is 
>>one that obtains noise from an audio device.
> 
> 
> I had looked at hw_random,  but it seemed a little platform specific (x86),
> and it doesn't currently have a way for RNG providers to register themselves.
> Admittedly I did not know how it's output was being used in practice.
> 
> The drivers I am working with do crypto/public key and RNG.  Not all of
> them can easily have the RNG support taken from the driver and plugged
> into hw_random.c,  since it is (in most cases) a single PCI chip with
> it's own  registers, initialisation and configuration,  that,  IMO
> belongs in the driver for the particular chip.

Agreed.


> Not that it isn't possible,  but hw_random would start supporting a
> much larger number of HW variants and I think it would get ugly.

Agreed.


> It would be possible to add a "register" interface to hw_random so that
> you can register other RNG's easily.  This would seem reasonable.

Agreed.


> I work on fairly resource constrained embedded devices a lot of the
> time, so when I can avoid adding applications and reduce kernel size,
> I do.  Thus my motivation to add a simple API for adding entropy to
> /dev/random.

We already have the facilities to add entropy, as current use of 
hw_random+rngd shows.

	Jeff

Re: API for true Random Number Generators to add entropy (2.6.11)

[Jan Engelhardt]

>Would you suggest making /dev/random point to /dev/hw_random then ?

No. I for example do not have a hardware RNG, so `modprobe hw_random` fails 
with No Such Device. Making it a symlink would make it a dangling one.


Jan Engelhardt
-- 

Re: API for true Random Number Generators to add entropy (2.6.11)

[Dave Jones]

On Thu, Mar 24, 2005 at 08:18:35AM +0100, Jan Engelhardt wrote:
 > 
 > >Would you suggest making /dev/random point to /dev/hw_random then ?
 > 
 > No. I for example do not have a hardware RNG, so `modprobe hw_random` fails 
 > with No Such Device. Making it a symlink would make it a dangling one.

It shouldn't be a symlink. Something like rngd should read from it
and feed it into /dev/random's entropy pool.

		Dave

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andrew Morton]

David McCullough <davidm@snapgear.com> wrote:
>
> Here is a small patch for 2.6.11 that adds a routine:
> 
>  	add_true_randomness(__u32 *buf, int nwords);

It neither applies correctly nor compiles in current kernels.  2.6.11 is
very old in kernel time.

Are we likely to see any in-kernel users of this?

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Andrew Morton wrote:
> David McCullough <davidm@snapgear.com> wrote:
> 
>>Here is a small patch for 2.6.11 that adds a routine:
>>
>> 	add_true_randomness(__u32 *buf, int nwords);
> 
> 
> It neither applies correctly nor compiles in current kernels.  2.6.11 is
> very old in kernel time.

Hrm.  This is getting pretty lame, if you can't take patches from the 
-latest- stable release.  It's pretty easy in BK:

	bk clone -ql -rv2.6.11 linux-2.6 rng-2.6.11
	cd rng-2.6.11
	{ apply patch }
	bk pull ../linux-2.6

Can you set up something like that?


> Are we likely to see any in-kernel users of this?

We already have a hardware RNG system.  This is completely unneeded.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andrew Morton]

Jeff Garzik <jgarzik@pobox.com> wrote:
>
> > It neither applies correctly nor compiles in current kernels.  2.6.11 is
>  > very old in kernel time.
> 
>  Hrm.  This is getting pretty lame, if you can't take patches from the 
>  -latest- stable release.  It's pretty easy in BK:
> 
>  	bk clone -ql -rv2.6.11 linux-2.6 rng-2.6.11
>  	cd rng-2.6.11
>  	{ apply patch }
>  	bk pull ../linux-2.6
> 
>  Can you set up something like that?

About thirty patches have gone into random.c since 2.6.11.  But the patch
was easy enough to apply anyway.

And then, it didn't compile.  I don't think bk will fix that.

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Matt Mackall]

On Wed, Mar 23, 2005 at 09:32:26PM -0800, Andrew Morton wrote:
> Jeff Garzik <jgarzik@pobox.com> wrote:
> >
> > > It neither applies correctly nor compiles in current kernels.  2.6.11 is
> >  > very old in kernel time.
> > 
> >  Hrm.  This is getting pretty lame, if you can't take patches from the 
> >  -latest- stable release.  It's pretty easy in BK:
> > 
> >  	bk clone -ql -rv2.6.11 linux-2.6 rng-2.6.11
> >  	cd rng-2.6.11
> >  	{ apply patch }
> >  	bk pull ../linux-2.6
> > 
> >  Can you set up something like that?
> 
> About thirty patches have gone into random.c since 2.6.11.  But the patch
> was easy enough to apply anyway.
> 
> And then, it didn't compile.  I don't think bk will fix that.

No, the names of all the pools changed. I agree with Jeff, this patch
is unnecessary. If we actually wanted such an interface, I'd rather it
refactor things so as not to reproduce the wake up logic.

-- 
Mathematics is the supreme nostalgia of our time.

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Randy.Dunlap]

Jeff Garzik wrote:
> Andrew Morton wrote:
> 
>> David McCullough <davidm@snapgear.com> wrote:
>>
>>> Here is a small patch for 2.6.11 that adds a routine:
>>>
>>>     add_true_randomness(__u32 *buf, int nwords);
>>
>>
>>
>> It neither applies correctly nor compiles in current kernels.  2.6.11 is
>> very old in kernel time.
> 
> 
> Hrm.  This is getting pretty lame, if you can't take patches from the 
> -latest- stable release.  It's pretty easy in BK:
> 
>     bk clone -ql -rv2.6.11 linux-2.6 rng-2.6.11
>     cd rng-2.6.11
>     { apply patch }
>     bk pull ../linux-2.6
> 
> Can you set up something like that?

I thought that the latest stable release was 2.6.11.5.

However, what I really want to do is ask what patches should be
made against.  I suggested on linux-scsi a day or 2 ago that
they should be made against the latest linus-bk (or snapshot)
unless the patch only applies to -mm, then they should obviously
be made against -mm.  2.6.11 plain is relatively aged IMO also....

-- 
~Randy

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 746 bytes --]

On Wed, 2005-03-23 at 20:38 -0800, Andrew Morton wrote:
> David McCullough <davidm@snapgear.com> wrote:
> >
> > Here is a small patch for 2.6.11 that adds a routine:
> > 
> >  	add_true_randomness(__u32 *buf, int nwords);
> 
> It neither applies correctly nor compiles in current kernels.  2.6.11 is
> very old in kernel time.
> 
> Are we likely to see any in-kernel users of this?

Any external crtypto framework can add entropy using that routing.
Currently it can be
 - OCF
 - acrypto
 - hw_random.c

hw_random.c already does it using userspace daemons,
which is bad idea for very fast HW - like VIA xstore/xcrypt 
instructions.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> hw_random.c already does it using userspace daemons,
> which is bad idea for very fast HW - like VIA xstore/xcrypt 
> instructions.

This is incorrect, because it implies that a user would want to use the 
'xstore' feature at full speed -- which would dominate the CPU, 
drastically slowing down the applications that are actually doing work.

As I mentioned in another message, VIA xstore support should be removed 
from hw_random.c and moved completely to userspace rngd.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1028 bytes --]

On Thu, 2005-03-24 at 15:39 -0500, Jeff Garzik wrote:
> Evgeniy Polyakov wrote:
> > hw_random.c already does it using userspace daemons,
> > which is bad idea for very fast HW - like VIA xstore/xcrypt 
> > instructions.
> 
> This is incorrect, because it implies that a user would want to use the 
> 'xstore' feature at full speed -- which would dominate the CPU, 
> drastically slowing down the applications that are actually doing work.

If user want to get RNG data at full speed we do not want to allow it?
Something changed in the world...

User actually do not want to use xstore, but only read from /dev/random.

If kernelspace can assist and driver _knows_ in advance that data
produced is cryptographically strong, why not allow it directly
access pools?

> As I mentioned in another message, VIA xstore support should be removed 
> from hw_random.c and moved completely to userspace rngd.
> 
> 	Jeff
> 
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> On Thu, 2005-03-24 at 15:39 -0500, Jeff Garzik wrote:
> 
>>Evgeniy Polyakov wrote:
>>
>>>hw_random.c already does it using userspace daemons,
>>>which is bad idea for very fast HW - like VIA xstore/xcrypt 
>>>instructions.
>>
>>This is incorrect, because it implies that a user would want to use the 
>>'xstore' feature at full speed -- which would dominate the CPU, 
>>drastically slowing down the applications that are actually doing work.
> 
> 
> If user want to get RNG data at full speed we do not want to allow it?
> Something changed in the world...

I agree with this sentiment; this is mainly a policy decision that 
kernel programmers should not make.

Certainly _by default_ the RNG should not be run "full blast" all the 
time.  This is a needless CPU soaker.

This is another example of why the userspace rngd is useful:  it is 
trivial to implement "CPU soaker" policy if you wish, or use the default 
"don't eat all my CPU" policy.


> User actually do not want to use xstore, but only read from /dev/random.

That's a policy decision to be made by the user, not you.

Some users may wish to use RNG directly.


> If kernelspace can assist and driver _knows_ in advance that data
> produced is cryptographically strong, why not allow it directly
> access pools?

A kernel driver cannot know in advance that the data from a hardware RNG 
is truly random, unless the data itself is 100% validated beforehand.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Thu, Mar 24, 2005 at 11:45:53PM -0500, Jeff Garzik wrote:
> 
> I agree with this sentiment; this is mainly a policy decision that 
> kernel programmers should not make.

Exactly.  Policy decisions like this as well as entropy checking
should be done in user-space.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[David McCullough]

Jivin Jeff Garzik lays it down ...
...
> >If kernelspace can assist and driver _knows_ in advance that data
> >produced is cryptographically strong, why not allow it directly
> >access pools?
> 
> A kernel driver cannot know in advance that the data from a hardware RNG 
> is truly random, unless the data itself is 100% validated beforehand.

You can also say that it cannot know that data written to /dev/random
is truly random unless it is also validated ?

For argument you could just run "cat < /dev/hwrandom > /dev/random"
instead of using rngd.

If /dev/random demands a level of randomness,  shouldn't it enforce it ?

If the HW is using 2 random sources, a non-linear mixer and a FIPS140
post processor before handing you a random number it would be nice to
take advantage of that IMO.

Cheers,
Davidm

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for TRNG (2.6.11) [Fortuna]

[Jean-Luc Cooke]

On Thu, Mar 31, 2005 at 01:52:14PM +1000, David McCullough wrote:
> 
> Jivin Jeff Garzik lays it down ...
> ...
> > >If kernelspace can assist and driver _knows_ in advance that data
> > >produced is cryptographically strong, why not allow it directly
> > >access pools?
> > 
> > A kernel driver cannot know in advance that the data from a hardware RNG 
> > is truly random, unless the data itself is 100% validated beforehand.
> 
> You can also say that it cannot know that data written to /dev/random
> is truly random unless it is also validated ?
> 
> For argument you could just run "cat < /dev/hwrandom > /dev/random"
> instead of using rngd.
> 
> If /dev/random demands a level of randomness,  shouldn't it enforce it ?
> 
> If the HW is using 2 random sources, a non-linear mixer and a FIPS140
> post processor before handing you a random number it would be nice to
> take advantage of that IMO.


For those who are interested, my Fortuna patch to the Linux RNG (/dev/random,
/dev/urandom) is available here (2.6.12-rc1, works on kernels as low as
2.6.11.4):
  http://jlcooke.ca/random/

Fortuna is a Cryptographically Secure Random Number Generator (CSRNG)
developed by Neils Ferguson and Bruce Schnier and published in their book
Applied Cryptography.

By most regards, it is the state of the art as far as software based CSRNGs
go.  The website gives an over view of the design, here is a summary:
  Fortuna uses a block cipher (AES128) in CTR mode to generate output.
  Fortuna uses a 32 hash states (SHA-256) which collect event data from
  sources of randomness (as usual in Linux).
  Once every 0.1sec or so, some of the hash states are finalised and the
  digests are collected.
  These digests are hashed together with with the current block cipher key to
  produce the new block cipher key.

Ferguson goes into detail in Practical Cryptography as to why this design is
superior to Yarrow based RNG (like the existing Linux RNG) and also delves
into why entropy estimation is impossible and is infact a liability in RNG
design.

My patch keep the entropy estimation from the current Linux RNG since this is
a very controversial issue with most people.  Disabling entropy estimation
and /dev/random blocking can be done by changing the RANDOM_NO_ENTROPY_COUNT
macro to 1.

I have not tested the syncookie code yet.  But networking works smoothly
after I echo "1" to /proc/sys/net/ipv4/tcp_syncookies.  Any help on this
would be great.

JLC

Re: [PATCH] API for TRNG (2.6.11) [Fortuna]

[Jean-Luc Cooke]

[-- Attachment #1: Type: text/plain, Size: 2834 bytes --]

Patch attached.

JLC

On Thu, Mar 31, 2005 at 08:58:22AM -0500, Jean-Luc Cooke wrote:
> On Thu, Mar 31, 2005 at 01:52:14PM +1000, David McCullough wrote:
> > 
> > Jivin Jeff Garzik lays it down ...
> > ...
> > > >If kernelspace can assist and driver _knows_ in advance that data
> > > >produced is cryptographically strong, why not allow it directly
> > > >access pools?
> > > 
> > > A kernel driver cannot know in advance that the data from a hardware RNG 
> > > is truly random, unless the data itself is 100% validated beforehand.
> > 
> > You can also say that it cannot know that data written to /dev/random
> > is truly random unless it is also validated ?
> > 
> > For argument you could just run "cat < /dev/hwrandom > /dev/random"
> > instead of using rngd.
> > 
> > If /dev/random demands a level of randomness,  shouldn't it enforce it ?
> > 
> > If the HW is using 2 random sources, a non-linear mixer and a FIPS140
> > post processor before handing you a random number it would be nice to
> > take advantage of that IMO.
> 
> 
> For those who are interested, my Fortuna patch to the Linux RNG (/dev/random,
> /dev/urandom) is available here (2.6.12-rc1, works on kernels as low as
> 2.6.11.4):
>   http://jlcooke.ca/random/
> 
> Fortuna is a Cryptographically Secure Random Number Generator (CSRNG)
> developed by Neils Ferguson and Bruce Schnier and published in their book
> Applied Cryptography.
> 
> By most regards, it is the state of the art as far as software based CSRNGs
> go.  The website gives an over view of the design, here is a summary:
>   Fortuna uses a block cipher (AES128) in CTR mode to generate output.
>   Fortuna uses a 32 hash states (SHA-256) which collect event data from
>   sources of randomness (as usual in Linux).
>   Once every 0.1sec or so, some of the hash states are finalised and the
>   digests are collected.
>   These digests are hashed together with with the current block cipher key to
>   produce the new block cipher key.
> 
> Ferguson goes into detail in Practical Cryptography as to why this design is
> superior to Yarrow based RNG (like the existing Linux RNG) and also delves
> into why entropy estimation is impossible and is infact a liability in RNG
> design.
> 
> My patch keep the entropy estimation from the current Linux RNG since this is
> a very controversial issue with most people.  Disabling entropy estimation
> and /dev/random blocking can be done by changing the RANDOM_NO_ENTROPY_COUNT
> macro to 1.
> 
> I have not tested the syncookie code yet.  But networking works smoothly
> after I echo "1" to /proc/sys/net/ipv4/tcp_syncookies.  Any help on this
> would be great.
> 
> JLC
> _______________________________________________
> 
> Subscription: http://lists.logix.cz/mailman/listinfo/cryptoapi
> List archive: http://lists.logix.cz/pipermail/cryptoapi

[-- Attachment #2: fortuna-random-2.6.11.4.patch --]
[-- Type: text/plain, Size: 65305 bytes --]

--- linux-2.6.11.6/crypto/Kconfig	2005-03-25 22:28:37.000000000 -0500
+++ linux-2.6.11.6-fort/crypto/Kconfig	2005-03-30 09:11:12.000000000 -0500
@@ -9,6 +9,20 @@
 	help
 	  This option provides the core Cryptographic API.
 
+config CRYPTO_RANDOM_FORTUNA
+	bool "The Fortuna CSRNG"
+	depends on CRYPTO && EXPERIMENTAL
+	select CRYPTO_SHA256
+	select CRYPTO_AES if !(CRYPTO && (X86 && !X86_64))
+	select CRYPTO_AES_586 if CRYPTO && (X86 && !X86_64)
+	help
+	  Replaces the legacy Linux RNG with one using the CryptoAPI
+	  and Fortuna designed by Ferguson and Schneier.  Entropy estimation,
+	  and a throttled /dev/random remain.  Improvements include faster
+	  /dev/urandom output and event input mixing.  Entropy estimation
+	  can be removed by changing source code.
+	  Note: Requires AES and SHA256 to be built-in.
+
 config CRYPTO_HMAC
 	bool "HMAC support"
 	depends on CRYPTO
--- linux-2.6.11.6/drivers/char/random-fortuna.c	1969-12-31 19:00:00.000000000 -0500
+++ linux-2.6.11.6-fort/drivers/char/random-fortuna.c	2005-03-31 08:54:37.321371752 -0500
@@ -0,0 +1,2121 @@
+/*
+ * random-fortuna.c -- A cryptographically strong random number generator
+ *			using Fortuna.
+ *
+ * Version 2.1.7, last modified 29-Mar-2005
+ * Change log:
+ *  v2.1.7:
+ * 	- Ported to 2.6.11.4
+ *  v2.1.6:
+ *	- Sami Farin pointed out RANDOM_MAX_BLOCK_SIZE was used for __u32[]'s
+ *	  and u8[]'s, fixed.
+ *	- Sami also found TCP sequence numbers wern't very secure.  Typo
+ *	  in code fixed.
+ *	- Sami found crypto_cipher_encrypt() uses nbytes and not
+ *	  numscatterlists.  Fixed.
+ *  v2.1.5:
+ *	- random-fortuna.c is no longer #include'd from random.c, the
+ *	  drivers/char/Makefile takes care of this now thanks to Chris Han
+ *  v2.1.4:
+ *	- Fixed flaw where some situations, /dev/random would not block.
+ *  v2.1.3:
+ *	- Added a seperate round-robin index for use inputs.  Avoids a
+ *	  super-cleaver user from forcing all system (unknown) random
+ *	  events from being fed into, say, pool-31.
+ *	- Added a "can only extract RANDOM_MAX_EXTRACT_SIZE bytes at a time"
+ *	  to extract_entropy()
+ *  v2.1.2:
+ *	- Ts'o's (I love writting that!) recomendation to force reseeds
+ * 	  to be at least 0.1 ms apart (complies with Ferguson/Schnier's
+ *	  design).
+ *  v2.1.1:
+ * 	- Re-worked to keep the blocking /dev/random.  Yes I finally gave
+ *	  in to what everyone's been telling me.
+ *	- Entropy accounting is *only* done on events going into pool-0
+ *	  since it's used for every reseed.  Those who expect /dev/random
+ *	  to only output data when the system is confident it has
+ *	  info-theoretic entropy to justify this output, this is the only
+ *	  sensible method to count entropy.
+ *  v2.0:
+ *	- Inital version
+ * 
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
+ * rights reserved.
+ * Copyright Jean-Luc Cooke, 2004.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, and the entire permission notice in its entirety,
+ *    including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior
+ *    written permission.
+ * 
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL are
+ * required INSTEAD OF the above restrictions.  (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ * 
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+/*
+ * Taken from random.c, updated by Jean-Luc Cooke <jlcooke@certainkey.com>
+ * (now, with legal B.S. out of the way.....) 
+ * 
+ * This routine gathers environmental noise from device drivers, etc.,
+ * and returns good random numbers, suitable for cryptographic use.
+ * Besides the obvious cryptographic uses, these numbers are also good
+ * for seeding TCP sequence numbers, and other places where it is
+ * desirable to have numbers which are not only random, but hard to
+ * predict by an attacker.
+ *
+ * Theory of operation
+ * ===================
+ * 
+ * Computers are very predictable devices.  Hence it is extremely hard
+ * to produce truly random numbers on a computer --- as opposed to
+ * pseudo-random numbers, which can easily generated by using a
+ * algorithm.  Unfortunately, it is very easy for attackers to guess
+ * the sequence of pseudo-random number generators, and for some
+ * applications this is not acceptable.  So instead, we must try to
+ * gather "environmental noise" from the computer's environment, which
+ * must be hard for outside attackers to observe, and use that to
+ * generate random numbers.  In a Unix environment, this is best done
+ * from inside the kernel.
+ * 
+ * Sources of randomness from the environment include inter-keyboard
+ * timings, inter-interrupt timings from some interrupts, and other
+ * events which are both (a) non-deterministic and (b) hard for an
+ * outside observer to measure.  Randomness from these sources are
+ * added to an "entropy pool", which is mixed.
+ * As random bytes are mixed into the entropy pool, the routines keep
+ * an *estimate* of how many bits of randomness have been stored into
+ * the random number generator's internal state.
+ * 
+ * Even if it is possible to analyze Fortuna in some clever way, as
+ * long as the amount of data returned from the generator is less than
+ * the inherent entropy we've estimated in the pool, the output data
+ * is totally unpredictable.  For this reason, the routine decreases
+ * its internal estimate of how many bits of "true randomness" are
+ * contained in the entropy pool as it outputs random numbers.
+ * 
+ * If this estimate goes to zero, the routine can still generate
+ * random numbers; however, an attacker may (at least in theory) be
+ * able to infer the future output of the generator from prior
+ * outputs.  This requires successful cryptanalysis of Fortuna, which is
+ * not believed to be feasible, but there is a remote possibility.
+ * Nonetheless, these numbers should be useful for the vast majority
+ * of purposes.
+ * 
+ * Exported interfaces ---- output
+ * ===============================
+ * 
+ * There are three exported interfaces; the first is one designed to
+ * be used from within the kernel:
+ *
+ * 	void get_random_bytes(void *buf, int nbytes);
+ *
+ * This interface will return the requested number of random bytes,
+ * and place it in the requested buffer.
+ * 
+ * The two other interfaces are two character devices /dev/random and
+ * /dev/urandom.  /dev/random is suitable for use when very high
+ * quality randomness is desired (for example, for key generation or
+ * one-time pads), as it will only return a maximum of the number of
+ * bits of randomness (as estimated by the random number generator)
+ * contained in the entropy pool.
+ * 
+ * The /dev/urandom device does not have this limit, and will return
+ * as many bytes as are requested.  As more and more random bytes are
+ * requested without giving time for the entropy pool to recharge,
+ * this will result in random numbers that are merely cryptographically
+ * strong.  For many applications, however, this is acceptable.
+ *
+ * Exported interfaces ---- input
+ * ==============================
+ * 
+ * The current exported interfaces for gathering environmental noise
+ * from the devices are:
+ * 
+ * 	void add_keyboard_randomness(unsigned char scancode);
+ * 	void add_mouse_randomness(__u32 mouse_data);
+ * 	void add_interrupt_randomness(int irq);
+ * 
+ * add_keyboard_randomness() uses the inter-keypress timing, as well as the
+ * scancode as random inputs into the "entropy pool".
+ * 
+ * add_mouse_randomness() uses the mouse interrupt timing, as well as
+ * the reported position of the mouse from the hardware.
+ *
+ * add_interrupt_randomness() uses the inter-interrupt timing as random
+ * inputs to the entropy pool.  Note that not all interrupts are good
+ * sources of randomness!  For example, the timer interrupts is not a
+ * good choice, because the periodicity of the interrupts is too
+ * regular, and hence predictable to an attacker.  Disk interrupts are
+ * a better measure, since the timing of the disk interrupts are more
+ * unpredictable.
+ * 
+ * All of these routines try to estimate how many bits of randomness a
+ * particular randomness source.  They do this by keeping track of the
+ * first and second order deltas of the event timings.
+ *
+ * Ensuring unpredictability at system startup
+ * ============================================
+ * 
+ * When any operating system starts up, it will go through a sequence
+ * of actions that are fairly predictable by an adversary, especially
+ * if the start-up does not involve interaction with a human operator.
+ * This reduces the actual number of bits of unpredictability in the
+ * entropy pool below the value in entropy_count.  In order to
+ * counteract this effect, it helps to carry information in the
+ * entropy pool across shut-downs and start-ups.  To do this, put the
+ * following lines an appropriate script which is run during the boot
+ * sequence: 
+ *
+ *	echo "Initializing random number generator..."
+ *	random_seed=/var/run/random-seed
+ *	# Carry a random seed from start-up to start-up
+ *	# Load and then save the whole entropy pool
+ *	if [ -f $random_seed ]; then
+ *		cat $random_seed >/dev/urandom
+ *	else
+ *		touch $random_seed
+ *	fi
+ *	chmod 600 $random_seed
+ *	dd if=/dev/urandom of=$random_seed count=8 bs=256
+ *
+ * and the following lines in an appropriate script which is run as
+ * the system is shutdown:
+ *
+ *	# Carry a random seed from shut-down to start-up
+ *	# Save the whole entropy pool
+ * 	# Fortuna resists using all of its pool matirial, so we need to
+ *      # draw 8 seperate times (count=8) to ensure we get the entropy
+ *	# from pool[0,1,2,3]'s entropy.  count=2048 pool[0 .. 10], etc.
+ *	echo "Saving random seed..."
+ *	random_seed=/var/run/random-seed
+ *	touch $random_seed
+ *	chmod 600 $random_seed
+ *	dd if=/dev/urandom of=$random_seed count=8 bs=256
+ *
+ * For example, on most modern systems using the System V init
+ * scripts, such code fragments would be found in
+ * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
+ * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
+ * 
+ * Effectively, these commands cause the contents of the entropy pool
+ * to be saved at shut-down time and reloaded into the entropy pool at
+ * start-up.  (The 'dd' in the addition to the bootup script is to
+ * make sure that /etc/random-seed is different for every start-up,
+ * even if the system crashes without executing rc.0.)  Even with
+ * complete knowledge of the start-up activities, predicting the state
+ * of the entropy pool requires knowledge of the previous history of
+ * the system.
+ *
+ * Configuring the /dev/random driver under Linux
+ * ==============================================
+ *
+ * The /dev/random driver under Linux uses minor numbers 8 and 9 of
+ * the /dev/mem major number (#1).  So if your system does not have
+ * /dev/random and /dev/urandom created already, they can be created
+ * by using the commands:
+ *
+ * 	mknod /dev/random c 1 8
+ * 	mknod /dev/urandom c 1 9
+ * 
+ * Acknowledgements:
+ * =================
+ *
+ * Ideas for constructing this random number generator were derived
+ * from Pretty Good Privacy's random number generator, and from private
+ * discussions with Phil Karn.  Colin Plumb provided a faster random
+ * number generator, which speed up the mixing function of the entropy
+ * pool, taken from PGPfone.  Dale Worley has also contributed many
+ * useful ideas and suggestions to improve this driver.
+ * 
+ * Any flaws in the design are solely my (jlcooke) responsibility, and
+ * should not be attributed to the Phil, Colin, or any of authors of PGP
+ * or the legacy random.c (Ted Ts'o).
+ * 
+ * Further background information on this topic may be obtained from
+ * RFC 1750, "Randomness Recommendations for Security", by Donald
+ * Eastlake, Steve Crocker, and Jeff Schiller.  And Chapter 10 of
+ * Practical Cryptography by Ferguson and Schneier.
+ */
+
+#include <linux/utsname.h>
+#include <linux/config.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/major.h>
+#include <linux/string.h>
+#include <linux/fcntl.h>
+#include <linux/slab.h>
+#include <linux/random.h>
+#include <linux/poll.h>
+#include <linux/init.h>
+#include <linux/fs.h>
+#include <linux/workqueue.h>
+#include <linux/genhd.h>
+#include <linux/interrupt.h>
+#include <linux/spinlock.h>
+#include <linux/percpu.h>
+#include <linux/crypto.h>
+
+#include <asm/scatterlist.h>
+#include <asm/processor.h>
+#include <asm/uaccess.h>
+#include <asm/irq.h>
+#include <asm/io.h>
+
+
+/*
+ * Configuration information
+ */
+
+/* Set to 1 to disable entropy estimation (once it reaches its max) and
+ * blocking of /dev/random */
+#define RANDOM_NO_ENTROPY_COUNT 0
+/* Queue of input events to queue for input into our pools */
+#define BATCH_ENTROPY_SIZE 256
+/* micro-seconds between random_reseeds for non-blocking reads */
+#define RANDOM_RESEED_INTERVAL 100
+/*
+ * Number of bytes you can extract at a time, 1MB is recomended in
+ * Practical Cryptography rev-0
+ */
+#define RANDOM_MAX_EXTRACT_SIZE  (1<<20)
+#define RANDOM_DEFAULT_DIGEST_ALGO "sha256"
+#define RANDOM_DEFAULT_CIPHER_ALGO "aes"
+/* Alternatives */
+//#define RANDOM_DEFAULT_DIGEST_ALGO "whirlpool"
+//#define RANDOM_DEFAULT_CIPHER_ALGO "twofish"
+
+#define DEFAULT_POOL_NUMBER 5 /* 2^{5} = 32 pools */
+#define DEFAULT_POOL_SIZE ( (1<<DEFAULT_POOL_NUMBER) * 256)
+/* largest block of random data to extract at a time when in blocking-mode */
+#define TMP_BUF_SIZE		512
+/* SHA512/WHIRLPOOL have 64bytes == 512 bits */
+#define RANDOM_MAX_DIGEST_SIZE	64
+/* AES256 has 16byte blocks == 128 bits */
+#define RANDOM_MAX_BLOCK_SIZE	16
+/* AES256 has 32byte keys == 256 bits */
+#define RANDOM_MAX_KEY_SIZE	32
+
+/*
+ * The minimum number of bits of entropy before we wake up a read on
+ * /dev/random.  We also wait for reseed_count>0 and we do a 
+ * random_reseed() once we do wake up.
+ */
+static int random_read_wakeup_thresh = 64;
+
+/*
+ * If the entropy count falls under this number of bits, then we
+ * should wake up processes which are selecting or polling on write
+ * access to /dev/random.
+ */
+static int random_write_wakeup_thresh = 128;
+
+/*
+ * When the input pool goes over trickle_thresh, start dropping most
+ * samples to avoid wasting CPU time and reduce lock contention.
+ */
+
+static int trickle_thresh = DEFAULT_POOL_SIZE * 7;
+
+static DEFINE_PER_CPU(int, trickle_count) = 0;
+
+#define POOLBYTES\
+	( (1<<random_state->pool_number) * random_state->digestsize )
+#define POOLBITS	( POOLBYTES * 8 )
+
+/*
+ * Linux 2.2 compatibility
+ */
+#ifndef DECLARE_WAITQUEUE
+#define DECLARE_WAITQUEUE(WAIT, PTR)	struct wait_queue WAIT = { PTR, NULL }
+#endif
+#ifndef DECLARE_WAIT_QUEUE_HEAD
+#define DECLARE_WAIT_QUEUE_HEAD(WAIT) struct wait_queue *WAIT
+#endif
+
+/*
+ * Static global variables
+ */
+static struct entropy_store *random_state; /* The default global store */
+static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
+static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
+
+/*
+ * Forward procedure declarations
+ */
+#ifdef CONFIG_SYSCTL
+static void sysctl_init_random(struct entropy_store *random_state);
+#endif
+
+/*****************************************************************
+ *
+ * Utility functions, with some ASM defined functions for speed
+ * purposes
+ * 
+ *****************************************************************/
+
+/*
+ * More asm magic....
+ * 
+ * For entropy estimation, we need to do an integral base 2
+ * logarithm.  
+ *
+ * Note the "12bits" suffix - this is used for numbers between
+ * 0 and 4095 only.  This allows a few shortcuts.
+ */
+#if 0	/* Slow but clear version */
+static inline __u32 int_ln_12bits(__u32 word)
+{
+	__u32 nbits = 0;
+	
+	while (word >>= 1)
+		nbits++;
+	return nbits;
+}
+#else	/* Faster (more clever) version, courtesy Colin Plumb */
+static inline __u32 int_ln_12bits(__u32 word)
+{
+	/* Smear msbit right to make an n-bit mask */
+	word |= word >> 8;
+	word |= word >> 4;
+	word |= word >> 2;
+	word |= word >> 1;
+	/* Remove one bit to make this a logarithm */
+	word >>= 1;
+	/* Count the bits set in the word */
+	word -= (word >> 1) & 0x555;
+	word = (word & 0x333) + ((word >> 2) & 0x333);
+	word += (word >> 4);
+	word += (word >> 8);
+	return word & 15;
+}
+#endif
+
+#if 0
+	#define DEBUG_ENT(fmt, arg...) printk("random: " fmt, ## arg)
+#else
+	#define DEBUG_ENT(fmt, arg...) do {} while (0)
+#endif
+#if 0
+	#define STATS_ENT(fmt, arg...) printk("random-stats: " fmt, ## arg)
+#else
+	#define STATS_ENT(fmt, arg...) do {} while (0)
+#endif
+
+
+/**********************************************************************
+ *
+ * OS independent entropy store.   Here are the functions which handle
+ * storing entropy in an entropy pool.
+ * 
+ **********************************************************************/
+
+struct entropy_store {
+	const char *digestAlgo;
+	unsigned int  digestsize;
+	struct crypto_tfm *pools[1<<DEFAULT_POOL_NUMBER];
+	/* optional, handy for statistics */
+	unsigned int pools_bytes[1<<DEFAULT_POOL_NUMBER];
+
+	const char *cipherAlgo;
+	/* the key */
+	unsigned char key[RANDOM_MAX_DIGEST_SIZE];
+	unsigned int  keysize;
+	/* the CTR value */
+	unsigned char iv[16];
+	unsigned int  blocksize;
+	struct crypto_tfm *cipher;
+
+	/* 2^pool_number # of pools */
+	unsigned int  pool_number;
+	/* current pool to add into */
+	unsigned int  pool_index;
+	/* size of the first pool */
+	unsigned int  pool0_len;
+	/* number of time we have reset */
+	unsigned int  reseed_count;
+	/* time in msec of the last reseed */
+	time_t reseed_time;
+	/* digest used during random_reseed() */
+	struct crypto_tfm *reseedHash;
+	/* cipher used for network randomness */
+	struct crypto_tfm *networkCipher;
+	/* flag indicating if networkCipher has been seeded */
+	char networkCipher_ready;
+
+	/* read-write data: */
+	spinlock_t lock ____cacheline_aligned_in_smp;
+	int		entropy_count;
+#if RANDOM_NO_ENTROPY_COUNT
+	int		entropy_count_bogus;
+#endif
+};
+
+/*
+ * Initialize the entropy store.  The input argument is the size of
+ * the random pool.
+ *
+ * Returns an negative error if there is a problem.
+ */
+static int create_entropy_store(int poolnum, struct entropy_store **ret_bucket)
+{
+	struct  entropy_store   *r;
+	unsigned long pool_number;
+	int     keysize, i, j;
+
+	pool_number = poolnum;
+
+	r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
+	if (!r) {
+		return -ENOMEM;
+	}
+
+	memset (r, 0, sizeof(struct entropy_store));
+	r->pool_number = pool_number;
+	r->digestAlgo = RANDOM_DEFAULT_DIGEST_ALGO;
+
+	DEBUG_ENT("create_entropy_store() pools=%u index=%u\n",
+			1<<pool_number, r->pool_index);
+	for (i=0; i<(1<<pool_number); i++) {
+		DEBUG_ENT("create_entropy_store() i=%i index=%u\n",
+				i, r->pool_index);
+		r->pools[i] = crypto_alloc_tfm(r->digestAlgo, 0);
+		if (r->pools[i] == NULL) {
+			for (j=0; j<i; j++) {
+				if (r->pools[j] != NULL) {
+					kfree(r->pools[j]);
+				}
+			}
+			kfree(r);
+			return -ENOMEM;
+		}
+		crypto_digest_init( r->pools[i] );
+	}
+	r->lock = SPIN_LOCK_UNLOCKED;
+	*ret_bucket = r;
+
+	r->cipherAlgo = RANDOM_DEFAULT_CIPHER_ALGO;
+	if ((r->cipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+		return -ENOMEM;
+	}
+
+	/* If the HASH's output is greater then the cipher's keysize, truncate
+	 * to the cipher's keysize */
+	keysize = crypto_tfm_alg_max_keysize(r->cipher);
+	r->digestsize = crypto_tfm_alg_digestsize(r->pools[0]);
+	r->blocksize = crypto_tfm_alg_blocksize(r->cipher);
+
+	r->keysize = (keysize < r->digestsize) ? keysize : r->digestsize;
+DEBUG_ENT("create_RANDOM %u %u %u\n", keysize, r->digestsize, r->keysize);
+
+	if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+		return -EINVAL;
+	}
+
+	/* digest used during random-reseed() */
+	if ((r->reseedHash=crypto_alloc_tfm(r->digestAlgo, 0)) == NULL) {
+		return -ENOMEM;
+	}
+	/* cipher used for network randomness */
+	if ((r->networkCipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+		return -ENOMEM;
+	}
+
+	return 0;
+}
+
+/*
+ * This function adds a byte into the entropy "pool".  It does not
+ * update the entropy estimate.  The caller should call
+ * credit_entropy_store if this is appropriate.
+ */
+static void add_entropy_words(struct entropy_store *r, const __u32 *in,
+			      int nwords, int dst_pool)
+{
+	unsigned long flags;
+	struct scatterlist sg[1];
+	static unsigned int totalBytes=0;
+	static unsigned int keyidx = 0;
+
+	if (r == NULL)
+		return;
+
+	spin_lock_irqsave(&r->lock, flags);
+
+	totalBytes += nwords * sizeof(__u32);
+
+	sg[0].page = virt_to_page(in);
+	sg[0].offset = offset_in_page(in);
+	sg[0].length = nwords*sizeof(__u32);
+
+	if (dst_pool == -1) {
+		r->pools_bytes[r->pool_index] += nwords * sizeof(__u32);
+		crypto_digest_update(r->pools[r->pool_index], sg, 1);
+		if (r->pool_index == 0) {
+			r->pool0_len += nwords*sizeof(__u32);
+		}
+		/* idx = (idx + r) mod ( (2^N)-1 ) */
+		r->pool_index = (r->pool_index + r->key[keyidx])
+					& ((1<<random_state->pool_number)-1);
+		/* first 8 bytes of the key are used, 8 * 8 = 64 bits */
+		keyidx = (keyidx + 1) & 7;
+	} else {
+		/* Let's make sure nothing mean is happening... */
+		dst_pool &= (1<<random_state->pool_number) - 1;
+		r->pools_bytes[dst_pool] += nwords * sizeof(__u32);
+		crypto_digest_update(r->pools[dst_pool], sg, 1);
+	}
+DEBUG_ENT("r->pool0_len = %u\n", r->pool0_len);
+
+
+	spin_unlock_irqrestore(&r->lock, flags);
+DEBUG_ENT("0 add_entropy_words() nwords=%u pool[i].bytes=%u total=%u\n",
+	nwords, r->pools_bytes[r->pool_index], totalBytes);
+}
+
+/*
+ * Credit (or debit) the entropy store with n bits of entropy
+ */
+static void credit_entropy_store(struct entropy_store *r, int nbits)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&r->lock, flags);
+
+	if (r->entropy_count + nbits < 0) {
+		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
+			  r->entropy_count, nbits);
+		r->entropy_count = 0;
+	} else if (r->entropy_count + nbits > POOLBITS) {
+		r->entropy_count = POOLBITS;
+	} else {
+		r->entropy_count += nbits;
+		if (nbits)
+			DEBUG_ENT("%04d : added %d bits\n",
+				  r->entropy_count,
+				  nbits);
+	}
+
+	spin_unlock_irqrestore(&r->lock, flags);
+}
+
+/**********************************************************************
+ *
+ * Entropy batch input management
+ *
+ * We batch entropy to be added to avoid increasing interrupt latency
+ *
+ **********************************************************************/
+
+struct sample {
+	__u32 data[2];
+	int credit;
+};
+
+static struct sample *batch_entropy_pool, *batch_entropy_copy;
+static int	batch_head, batch_tail;
+static spinlock_t batch_lock = SPIN_LOCK_UNLOCKED;
+
+static int	batch_max;
+static void batch_entropy_process(void *private_);
+static DECLARE_WORK(batch_work, batch_entropy_process, NULL);
+
+/* note: the size must be a power of 2 */
+static int __init batch_entropy_init(int size, struct entropy_store *r)
+{
+	batch_entropy_pool = kmalloc(size*sizeof(struct sample), GFP_KERNEL);
+	if (!batch_entropy_pool)
+		return -1;
+	batch_entropy_copy = kmalloc(size*sizeof(struct sample), GFP_KERNEL);
+	if (!batch_entropy_copy) {
+		kfree(batch_entropy_pool);
+		return -1;
+	}
+	batch_head = batch_tail = 0;
+	batch_work.data = r;
+	batch_max = size;
+	return 0;
+}
+
+/*
+ * Changes to the entropy data is put into a queue rather than being added to
+ * the entropy counts directly.  This is presumably to avoid doing heavy
+ * hashing calculations during an interrupt in add_timer_randomness().
+ * Instead, the entropy is only added to the pool by keventd.
+ */
+void batch_entropy_store(u32 a, u32 b, int num)
+{
+	int new;
+	unsigned long flags;
+
+	if (!batch_max)
+		return;
+
+	spin_lock_irqsave(&batch_lock, flags);
+
+	batch_entropy_pool[batch_head].data[0] = a;
+	batch_entropy_pool[batch_head].data[1] = b;
+	batch_entropy_pool[batch_head].credit = num;
+
+	if (((batch_head - batch_tail) & (batch_max-1)) >= (batch_max / 2)) {
+		/*
+		 * Schedule it for the next timer tick:
+		 */
+		schedule_delayed_work(&batch_work, 1);
+	}
+
+	new = (batch_head+1) & (batch_max-1);
+	if (new == batch_tail) {
+		DEBUG_ENT("batch entropy buffer full\n");
+	} else {
+		batch_head = new;
+	}
+
+	spin_unlock_irqrestore(&batch_lock, flags);
+}
+
+EXPORT_SYMBOL(batch_entropy_store);
+
+/*
+ * Flush out the accumulated entropy operations, adding entropy to the passed
+ * store (normally random_state).  If that store has enough entropy, alternate
+ * between randomizing the data of the primary and secondary stores.
+ */
+static void batch_entropy_process(void *private_)
+{
+	int max_entropy = POOLBITS;
+	unsigned head, tail;
+
+	/* Mixing into the pool is expensive, so copy over the batch
+	 * data and release the batch lock. The pool is at least half
+	 * full, so don't worry too much about copying only the used
+	 * part.
+	 */
+	spin_lock_irq(&batch_lock);
+
+	memcpy(batch_entropy_copy, batch_entropy_pool,
+	       batch_max*sizeof(struct sample));
+
+	head = batch_head;
+	tail = batch_tail;
+	batch_tail = batch_head;
+
+	spin_unlock_irq(&batch_lock);
+
+	while (head != tail) {
+		if (random_state->entropy_count >= max_entropy) {
+			max_entropy = POOLBITS;
+		}
+		/*
+		 * Only credit if we're feeding into pool[0]
+		 * Otherwise we'd be assuming entropy in pool[31] would be
+		 * usable when we read.  This is conservative, but it'll
+		 * not over-credit our entropy estimate for users of
+		 * /dev/random, /dev/urandom will not be effected.
+		 */
+		if (random_state->pool_index == 0) {
+			credit_entropy_store(random_state,
+				batch_entropy_copy[tail].credit);
+		}
+		add_entropy_words(random_state,
+			batch_entropy_copy[tail].data, 2, -1);
+;
+
+		tail = (tail+1) & (batch_max-1);
+	}
+	if (random_state->entropy_count >= random_read_wakeup_thresh
+		&& random_state->reseed_count != 0)
+		wake_up_interruptible(&random_read_wait);
+}
+
+/*********************************************************************
+ *
+ * Entropy input management
+ *
+ *********************************************************************/
+
+/* There is one of these per entropy source */
+struct timer_rand_state {
+	__u32		last_time;
+	__s32		last_delta,last_delta2;
+	int		dont_count_entropy:1;
+};
+
+static struct timer_rand_state input_timer_state;
+static struct timer_rand_state extract_timer_state;
+static struct timer_rand_state *irq_timer_state[NR_IRQS];
+
+/*
+ * This function adds entropy to the entropy "pool" by using timing
+ * delays.  It uses the timer_rand_state structure to make an estimate
+ * of how many bits of entropy this call has added to the pool.
+ *
+ * The number "num" is also added to the pool - it should somehow describe
+ * the type of event which just happened.  This is currently 0-255 for
+ * keyboard scan codes, and 256 upwards for interrupts.
+ * On the i386, this is assumed to be at most 16 bits, and the high bits
+ * are used for a high-resolution timer.
+ *
+ */
+static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
+{
+	__u32		time;
+	__s32		delta, delta2, delta3;
+	int		entropy = 0;
+
+	/* if over the trickle threshold, use only 1 in 4096 samples */
+	if ( random_state->entropy_count > trickle_thresh &&
+	     (__get_cpu_var(trickle_count)++ & 0xfff))
+		return;
+
+#if defined (__i386__) || defined (__x86_64__)
+	if (cpu_has_tsc) {
+		__u32 high;
+		rdtsc(time, high);
+		num ^= high;
+	} else {
+		time = jiffies;
+	}
+#elif defined (__sparc_v9__)
+	unsigned long tick = tick_ops->get_tick();
+
+	time = (unsigned int) tick;
+	num ^= (tick >> 32UL);
+#else
+	time = jiffies;
+#endif
+
+	/*
+	 * Calculate number of bits of randomness we probably added.
+	 * We take into account the first, second and third-order deltas
+	 * in order to make our estimate.
+	 */
+	if (!state->dont_count_entropy) {
+		delta = time - state->last_time;
+		state->last_time = time;
+
+		delta2 = delta - state->last_delta;
+		state->last_delta = delta;
+
+		delta3 = delta2 - state->last_delta2;
+		state->last_delta2 = delta2;
+
+		if (delta < 0)
+			delta = -delta;
+		if (delta2 < 0)
+			delta2 = -delta2;
+		if (delta3 < 0)
+			delta3 = -delta3;
+		if (delta > delta2)
+			delta = delta2;
+		if (delta > delta3)
+			delta = delta3;
+
+		/*
+		 * delta is now minimum absolute delta.
+		 * Round down by 1 bit on general principles,
+		 * and limit entropy entimate to 12 bits.
+		 */
+		delta >>= 1;
+		delta &= (1 << 12) - 1;
+
+		entropy = int_ln_12bits(delta);
+	}
+	batch_entropy_store(num, time, entropy);
+}
+
+extern void add_input_randomness(unsigned int type, unsigned int code,
+			 unsigned int value)
+{
+	static unsigned int last_value;
+
+	/* ignore autorepeat (multiple key down w/o key up) */
+	if (value != last_value)
+		return;
+
+	DEBUG_ENT("input event\n");
+	last_value = value;
+	add_timer_randomness(&input_timer_state,
+			(type << 4) ^ code ^ (code >> 4) ^ value);
+}
+
+void add_interrupt_randomness(int irq)
+{
+	if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
+		return;
+
+	add_timer_randomness(irq_timer_state[irq], 0x100+irq);
+}
+
+EXPORT_SYMBOL(add_interrupt_randomness);
+
+void add_disk_randomness(struct gendisk *disk)
+{
+	if (!disk || !disk->random)
+		return;
+	/* first major is 1, so we get >= 0x200 here */
+	add_timer_randomness(disk->random,
+				0x100+MKDEV(disk->major, disk->first_minor));
+}
+
+EXPORT_SYMBOL(add_disk_randomness);
+
+/*********************************************************************
+ *
+ * Entropy extraction routines
+ *
+ *********************************************************************/
+
+#define EXTRACT_ENTROPY_USER		1
+#define EXTRACT_ENTROPY_LIMIT		4
+
+static ssize_t extract_entropy(struct entropy_store *r, void * buf,
+			       size_t nbytes, int flags);
+
+static inline void increment_iv(unsigned char *iv, const unsigned int IVsize) {
+	switch (IVsize) {
+	case 8:
+		if (++((u32*)iv)[0])
+			++((u32*)iv)[1];
+	break;
+
+	case 16:
+		if (++((u32*)iv)[0])
+			if (++((u32*)iv)[1])
+				if (++((u32*)iv)[2])
+					++((u32*)iv)[3];
+	break;
+
+	default:
+		{
+		int i;
+		for (i=0; i<IVsize; i++)
+			if (++iv[i])
+				break;
+		}
+	break;
+	}
+}
+
+/*
+ * Fortuna's Reseed
+ * 
+ * Key' = hash(Key || hash(pool[a0]) || hash(pool[a1]) || ...)
+ * where {a0,a1,...} are facators of r->reseed_count+1 which are of the form
+ * 2^j, 0<=j.
+ * Prevents backtracking attacks and with event inputs, supports forward
+ * secrecy
+ */
+static void random_reseed(struct entropy_store *r, size_t nbytes, int flags) {
+	struct scatterlist sg[1];
+	unsigned int i, deduct;
+	unsigned char tmp[RANDOM_MAX_DIGEST_SIZE];
+	unsigned long cpuflags;
+ 
+	deduct = (r->keysize < r->digestsize) ? r->keysize : r->digestsize;
+
+	/* Hold lock while accounting */
+	spin_lock_irqsave(&r->lock, cpuflags);
+
+	DEBUG_ENT("%04d : trying to extract %d bits\n",
+		  random_state->entropy_count,
+		  deduct * 8);
+
+	/*
+	 * Don't extract more data than in the entropy in the pooling system
+	 */
+	if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8) {
+		nbytes = r->entropy_count / 8;
+	}
+
+	if (deduct*8 <= r->entropy_count) {
+		r->entropy_count -= deduct*8;
+	} else {
+		r->entropy_count = 0;
+	}
+
+	if (r->entropy_count < random_write_wakeup_thresh)
+		wake_up_interruptible(&random_write_wait);
+
+	DEBUG_ENT("%04d : debiting %d bits%s\n",
+		  random_state->entropy_count,
+		  deduct * 8,
+		  flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)");
+
+	r->reseed_count++;
+	r->pool0_len = 0;
+
+	/* Entropy accounting done, release lock. */
+	spin_unlock_irqrestore(&r->lock, cpuflags);
+
+	DEBUG_ENT("random_reseed count=%u\n", r->reseed_count);
+
+	crypto_digest_init(r->reseedHash);
+
+	sg[0].page = virt_to_page(r->key);
+	sg[0].offset = offset_in_page(r->key);
+	sg[0].length = r->keysize;
+	crypto_digest_update(r->reseedHash, sg, 1);
+
+#define TESTBIT(VAL, N)\
+  ( ((VAL) >> (N)) & 1 )
+	for (i=0; i<(1<<r->pool_number); i++) {
+		/* using pool[i] if r->reseed_count is divisible by 2^i
+		 * since 2^0 == 1, we always use pool[0]
+		 */
+		if ( (i==0)  ||  TESTBIT(r->reseed_count,i)==0 ) {
+			crypto_digest_final(r->pools[i], tmp);
+
+			sg[0].page = virt_to_page(tmp);
+			sg[0].offset = offset_in_page(tmp);
+			sg[0].length = r->keysize;
+			crypto_digest_update(r->reseedHash, sg, 1);
+
+			crypto_digest_init(r->pools[i]);
+			/* Each pool carries its past state forward */
+			crypto_digest_update(r->pools[i], sg, 1);
+		} else {
+			/* pool j is only used once every 2^j times */
+			break;
+		}
+	}
+#undef TESTBIT
+
+	crypto_digest_final(r->reseedHash, r->key);
+	crypto_cipher_setkey(r->cipher, r->key, r->keysize);
+	increment_iv(r->iv, r->blocksize);
+}
+
+static inline time_t get_msectime(void) {
+	struct timeval tv;
+	do_gettimeofday(&tv);
+	return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
+}
+
+/*
+ * This function extracts randomness from the "entropy pool", and
+ * returns it in a buffer.  This function computes how many remaining
+ * bits of entropy are left in the pool, but it does not restrict the
+ * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
+ * flag is given, then the buf pointer is assumed to be in user space.
+ */
+static ssize_t extract_entropy(struct entropy_store *r, void * buf,
+			       size_t nbytes, int flags)
+{
+	ssize_t ret, i;
+	__u32 tmp[RANDOM_MAX_BLOCK_SIZE/sizeof(__u32)];
+	struct scatterlist sgiv[1], sgtmp[1];
+	time_t nowtime;
+
+	/* Redundant, but just in case... */
+	if (r->entropy_count > POOLBITS)
+		r->entropy_count = POOLBITS;
+
+	/*
+	 * To keep the possibility of collisions down, limit the number of
+	 * output bytes per block cipher key.
+	 */
+	if (RANDOM_MAX_EXTRACT_SIZE < nbytes)
+		nbytes = RANDOM_MAX_EXTRACT_SIZE;
+
+	if (flags & EXTRACT_ENTROPY_LIMIT) {
+		/* if in blocking, only output upto the entropy estimate */
+		if (r->entropy_count/8 < nbytes)
+			nbytes = r->entropy_count/8;
+		/*
+		 * if blocking and there is no entropy by our estimate,
+		 * break out now.
+		 */
+		if (nbytes == 0)
+			return 0;
+	}
+
+	/*
+	 * If reading in non-blocking mode, pace ourselves in using up the pool
+	 * system's entropy.  reseed every .1 sec (Ferguson/Schnier)
+	 */
+	if (! (flags & EXTRACT_ENTROPY_LIMIT) ) {
+		nowtime = get_msectime();
+		if (r->pool0_len > 64
+		&& (nowtime - r->reseed_time) > RANDOM_RESEED_INTERVAL) {
+			random_reseed(r, nbytes, flags);
+			r->reseed_time = nowtime;
+		}
+	}
+
+	sgiv[0].page = virt_to_page(r->iv);
+	sgiv[0].offset = offset_in_page(r->iv);
+	sgiv[0].length = r->blocksize;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = r->blocksize;
+
+	ret = 0;
+	while (nbytes) {
+		/*
+		 * Check if we need to break out or reschedule....
+		 */
+		if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) {
+			if (signal_pending(current)) {
+				if (ret == 0)
+					ret = -ERESTARTSYS;
+				break;
+			}
+
+			DEBUG_ENT("%04d : extract sleeping (%d bytes left)\n",
+				  random_state->entropy_count,
+				  nbytes);
+
+			schedule();
+
+			/*
+			 * when we wakeup, there will be more data in our
+			 * pooling system so we may reseed
+			 */
+			nowtime = get_msectime();
+			if (r->pool0_len > 64
+			&& (nowtime-r->reseed_time) > RANDOM_RESEED_INTERVAL) {
+				random_reseed(r, nbytes, flags);
+				r->reseed_time = nowtime;
+			}
+
+			DEBUG_ENT("%04d : extract woke up\n",
+				  random_state->entropy_count);
+		}
+
+		/*
+		 * Reading from /dev/random, we limit this to the amount
+		 * of entropy to deduct from our estimate.  This estimate is
+		 * most naturally updated from inside Fortuna-reseed, so we
+		 * limit our block size here.
+		 *
+		 * At most, Fortuna will use e=min(r->digestsize, r->keysize) of
+		 * entropy to reseed.
+		 */
+		if (flags & EXTRACT_ENTROPY_LIMIT) {
+			r->reseed_time = get_msectime();
+			random_reseed(r, nbytes, flags);
+		}
+
+		crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+		increment_iv(r->iv, r->blocksize);
+		
+		/* Copy data to destination buffer */
+		i = (nbytes < r->blocksize) ? nbytes : r->blocksize;
+		if (flags & EXTRACT_ENTROPY_USER) {
+			i -= copy_to_user(buf, (__u8 const *)tmp, i);
+			if (!i) {
+				ret = -EFAULT;
+				break;
+			}
+		} else
+			memcpy(buf, (__u8 const *)tmp, i);
+		nbytes -= i;
+		buf += i;
+		ret += i;
+	}
+
+	/* generate a new key */
+	/* take into account the possibility that keysize >= blocksize */
+	for (i=0; i+r->blocksize<=r->keysize; i+=r->blocksize) {
+		memcpy(tmp, r->key+i, r->blocksize);
+		crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+		increment_iv(r->iv, r->blocksize);
+	}
+	memcpy(tmp, r->key+i, r->keysize-i);
+	memset(tmp+r->keysize-i, 0, r->blocksize-(r->keysize-i));
+	crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+	increment_iv(r->iv, r->blocksize);
+
+	if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+		return -EINVAL;
+	}
+
+	/* Wipe data just returned from memory */
+	memset(tmp, 0, sizeof(tmp));
+	
+	return ret;
+}
+
+/*
+ * This function is the exported kernel interface.  It returns some
+ * number of good random numbers, suitable for seeding TCP sequence
+ * numbers, etc.
+ */
+void get_random_bytes(void *buf, int nbytes)
+{
+	if (random_state)
+		extract_entropy(random_state, (char *) buf, nbytes, 0);
+	else
+		printk(KERN_NOTICE "get_random_bytes called before "
+				   "random driver initialization\n");
+}
+
+EXPORT_SYMBOL(get_random_bytes);
+
+/*********************************************************************
+ *
+ * Functions to interface with Linux
+ *
+ *********************************************************************/
+
+/*
+ * Initialize the random pool with standard stuff.
+ * This is not secure random data, but it can't hurt us and people scream
+ * when you try to remove it.
+ *
+ * NOTE: This is an OS-dependent function.
+ */
+static void init_std_data(struct entropy_store *r)
+{
+	struct timeval 	tv;
+	__u32		words[2];
+	char 		*p;
+	int		i;
+
+	do_gettimeofday(&tv);
+	words[0] = tv.tv_sec;
+	words[1] = tv.tv_usec;
+	batch_entropy_store(words[0], words[1], -1);
+
+	/*
+	 *	This doesn't lock system.utsname. However, we are generating
+	 *	entropy so a race with a name set here is fine.
+	 */
+	p = (char *) &system_utsname;
+	for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
+		memcpy(words, p, sizeof(words));
+		batch_entropy_store(words[0], words[1], -1);
+		p += sizeof(words);
+	}
+}
+
+static int __init rand_initialize(void)
+{
+	int i;
+
+	if (create_entropy_store(DEFAULT_POOL_NUMBER, &random_state))
+		goto err;
+	if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
+		goto err;
+	init_std_data(random_state);
+#ifdef CONFIG_SYSCTL
+	sysctl_init_random(random_state);
+#endif
+	for (i = 0; i < NR_IRQS; i++)
+		irq_timer_state[i] = NULL;
+	memset(&input_timer_state, 0, sizeof(struct timer_rand_state));
+	memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
+	extract_timer_state.dont_count_entropy = 1;
+	return 0;
+err:
+	return -1;
+}
+module_init(rand_initialize);
+
+void rand_initialize_irq(int irq)
+{
+	struct timer_rand_state *state;
+	
+	if (irq >= NR_IRQS || irq_timer_state[irq])
+		return;
+
+	/*
+	 * If kmalloc returns null, we just won't use that entropy
+	 * source.
+	 */
+	state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
+	if (state) {
+		memset(state, 0, sizeof(struct timer_rand_state));
+		irq_timer_state[irq] = state;
+	}
+}
+ 
+void rand_initialize_disk(struct gendisk *disk)
+{
+	struct timer_rand_state *state;
+	
+	/*
+	 * If kmalloc returns null, we just won't use that entropy
+	 * source.
+	 */
+	state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
+	if (state) {
+		memset(state, 0, sizeof(struct timer_rand_state));
+		disk->random = state;
+	}
+}
+
+static ssize_t
+random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
+{
+	DECLARE_WAITQUEUE(wait, current);
+	ssize_t	n, retval = 0, count = 0;
+	
+	if (nbytes == 0)
+		return 0;
+
+	while (nbytes > 0) {
+		n = nbytes;
+
+		DEBUG_ENT("%04d : reading %d bits, p: %d s: %d\n",
+			  random_state->entropy_count,
+			  n*8, random_state->entropy_count,
+			  random_state->entropy_count);
+
+		n = extract_entropy(random_state, buf, n,
+				    EXTRACT_ENTROPY_USER |
+				    EXTRACT_ENTROPY_LIMIT);
+
+		DEBUG_ENT("%04d : read got %d bits (%d needed, reseeds=%d)\n",
+			  random_state->entropy_count,
+			  random_state->reseed_count,
+			  n*8, (nbytes-n)*8);
+
+		if (n == 0) {
+			if (file->f_flags & O_NONBLOCK) {
+				retval = -EAGAIN;
+				break;
+			}
+			if (signal_pending(current)) {
+				retval = -ERESTARTSYS;
+				break;
+			}
+
+			DEBUG_ENT("%04d : sleeping?\n",
+				  random_state->entropy_count);
+
+			set_current_state(TASK_INTERRUPTIBLE);
+			add_wait_queue(&random_read_wait, &wait);
+
+			if (random_state->entropy_count / 8 == 0
+				||  random_state->reseed_count == 0)
+				schedule();
+
+			set_current_state(TASK_RUNNING);
+			remove_wait_queue(&random_read_wait, &wait);
+
+			DEBUG_ENT("%04d : waking up\n",
+				  random_state->entropy_count);
+
+			continue;
+		}
+
+		if (n < 0) {
+			retval = n;
+			break;
+		}
+		count += n;
+		buf += n;
+		nbytes -= n;
+		break;		/* This break makes the device work */
+				/* like a named pipe */
+	}
+
+	/*
+	 * If we gave the user some bytes, update the access time.
+	 */
+	if (count)
+		file_accessed(file);
+	
+	return (count ? count : retval);
+}
+
+static ssize_t
+urandom_read(struct file * file, char __user * buf,
+		      size_t nbytes, loff_t *ppos)
+{
+	/* Don't return anything untill we've reseeded at least once */
+	if (random_state->reseed_count == 0)
+		return 0;
+
+	return extract_entropy(random_state, buf, nbytes,
+			       EXTRACT_ENTROPY_USER);
+}
+
+static unsigned int
+random_poll(struct file *file, poll_table * wait)
+{
+	unsigned int mask;
+
+	poll_wait(file, &random_read_wait, wait);
+	poll_wait(file, &random_write_wait, wait);
+	mask = 0;
+	if (random_state->entropy_count >= random_read_wakeup_thresh)
+		mask |= POLLIN | POLLRDNORM;
+	if (random_state->entropy_count < random_write_wakeup_thresh)
+		mask |= POLLOUT | POLLWRNORM;
+	return mask;
+}
+
+static ssize_t
+random_write(struct file * file, const char __user * buffer,
+	     size_t count, loff_t *ppos)
+{
+	static int	idx = 0;
+	int		ret = 0;
+	size_t		bytes;
+	__u32 		buf[16];
+	const char 	__user *p = buffer;
+	size_t		c = count;
+
+	while (c > 0) {
+		bytes = min(c, sizeof(buf));
+
+		bytes -= copy_from_user(&buf, p, bytes);
+		if (!bytes) {
+			ret = -EFAULT;
+			break;
+		}
+		c -= bytes;
+		p += bytes;
+
+		/*
+		 * Use input data rotates though the pools independantly of
+		 * system-events.
+		 *
+		 * idx = (idx + 1) mod ( (2^N)-1 )
+		 */
+		idx = (idx + 1) & ((1<<random_state->pool_number)-1);
+		add_entropy_words(random_state, buf, bytes, idx);
+	}
+	if (p == buffer) {
+		return (ssize_t)ret;
+	} else {
+		file->f_dentry->d_inode->i_mtime = CURRENT_TIME;
+		mark_inode_dirty(file->f_dentry->d_inode);
+		return (ssize_t)(p - buffer);
+	}
+}
+
+static int
+random_ioctl(struct inode * inode, struct file * file,
+	     unsigned int cmd, unsigned long arg)
+{
+	int size, ent_count;
+	int __user *p = (int __user *)arg;
+	int retval;
+	
+	switch (cmd) {
+	case RNDGETENTCNT:
+		ent_count = random_state->entropy_count;
+		if (put_user(ent_count, p))
+			return -EFAULT;
+		return 0;
+	case RNDADDTOENTCNT:
+		if (!capable(CAP_SYS_ADMIN))
+			return -EPERM;
+		if (get_user(ent_count, p))
+			return -EFAULT;
+		credit_entropy_store(random_state, ent_count);
+		/*
+		 * Wake up waiting processes if we have enough
+		 * entropy.
+		 */
+		if (random_state->entropy_count >= random_read_wakeup_thresh
+			&&  random_state->reseed_count != 0)
+			wake_up_interruptible(&random_read_wait);
+		return 0;
+	case RNDGETPOOL:
+		/* can't do this anymore */
+		return 0;
+	case RNDADDENTROPY:
+		if (!capable(CAP_SYS_ADMIN))
+			return -EPERM;
+		if (get_user(ent_count, p++))
+			return -EFAULT;
+		if (ent_count < 0)
+			return -EINVAL;
+		if (get_user(size, p++))
+			return -EFAULT;
+		retval = random_write(file, (const char __user *) p,
+				      size, &file->f_pos);
+		if (retval < 0)
+			return retval;
+		credit_entropy_store(random_state, ent_count);
+		/*
+		 * Wake up waiting processes if we have enough
+		 * entropy.
+		 */
+		if (random_state->entropy_count >= random_read_wakeup_thresh
+			&&  random_state->reseed_count != 0)
+			wake_up_interruptible(&random_read_wait);
+		return 0;
+	case RNDZAPENTCNT:
+		/* Can't do this anymore */
+		return 0;
+	case RNDCLEARPOOL:
+		/* Can't to this anymore */
+		return 0;
+	default:
+		return -EINVAL;
+	}
+}
+
+struct file_operations random_fops = {
+	.read		= random_read,
+	.write		= random_write,
+	.poll		= random_poll,
+	.ioctl		= random_ioctl,
+};
+
+struct file_operations urandom_fops = {
+	.read		= urandom_read,
+	.write		= random_write,
+	.ioctl		= random_ioctl,
+};
+
+/***************************************************************
+ * Random UUID interface
+ * 
+ * Used here for a Boot ID, but can be useful for other kernel 
+ * drivers.
+ ***************************************************************/
+
+/*
+ * Generate random UUID
+ */
+void generate_random_uuid(unsigned char uuid_out[16])
+{
+	get_random_bytes(uuid_out, 16);
+	/* Set UUID version to 4 --- truely random generation */
+	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
+	/* Set the UUID variant to DCE */
+	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
+}
+
+EXPORT_SYMBOL(generate_random_uuid);
+
+/********************************************************************
+ *
+ * Sysctl interface
+ *
+ ********************************************************************/
+
+#ifdef CONFIG_SYSCTL
+
+#include <linux/sysctl.h>
+
+static int sysctl_poolsize;
+static int min_read_thresh, max_read_thresh;
+static int min_write_thresh, max_write_thresh;
+static char sysctl_bootid[16];
+
+static int proc_do_poolsize(ctl_table *table, int write, struct file *filp,
+			    void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	int	ret;
+
+	sysctl_poolsize = POOLBITS;
+
+	ret = proc_dointvec(table, write, filp, buffer, lenp, ppos);
+	if (ret || !write ||
+	    (sysctl_poolsize == POOLBITS))
+		return ret;
+
+	return ret; /* can't change the pool size in fortuna */
+}
+
+static int poolsize_strategy(ctl_table *table, int __user *name, int nlen,
+			     void __user *oldval, size_t __user *oldlenp,
+			     void __user *newval, size_t newlen, void **context)
+{
+	int	len;
+	
+	sysctl_poolsize = POOLBITS;
+
+	/*
+	 * We only handle the write case, since the read case gets
+	 * handled by the default handler (and we don't care if the
+	 * write case happens twice; it's harmless).
+	 */
+	if (newval && newlen) {
+		len = newlen;
+		if (len > table->maxlen)
+			len = table->maxlen;
+		if (copy_from_user(table->data, newval, len))
+			return -EFAULT;
+	}
+
+	return 0;
+}
+
+/*
+ * These functions is used to return both the bootid UUID, and random
+ * UUID.  The difference is in whether table->data is NULL; if it is,
+ * then a new UUID is generated and returned to the user.
+ * 
+ * If the user accesses this via the proc interface, it will be returned
+ * as an ASCII string in the standard UUID format.  If accesses via the 
+ * sysctl system call, it is returned as 16 bytes of binary data.
+ */
+static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
+			void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	ctl_table	fake_table;
+	unsigned char	buf[64], tmp_uuid[16], *uuid;
+
+	uuid = table->data;
+	if (!uuid) {
+		uuid = tmp_uuid;
+		uuid[8] = 0;
+	}
+	if (uuid[8] == 0)
+		generate_random_uuid(uuid);
+
+	sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
+		"%02x%02x%02x%02x%02x%02x",
+		uuid[0],  uuid[1],  uuid[2],  uuid[3],
+		uuid[4],  uuid[5],  uuid[6],  uuid[7],
+		uuid[8],  uuid[9],  uuid[10], uuid[11],
+		uuid[12], uuid[13], uuid[14], uuid[15]);
+	fake_table.data = buf;
+	fake_table.maxlen = sizeof(buf);
+
+	return proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
+}
+
+static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
+			 void __user *oldval, size_t __user *oldlenp,
+			 void __user *newval, size_t newlen, void **context)
+{
+	unsigned char	tmp_uuid[16], *uuid;
+	unsigned int	len;
+
+	if (!oldval || !oldlenp)
+		return 1;
+
+	uuid = table->data;
+	if (!uuid) {
+		uuid = tmp_uuid;
+		uuid[8] = 0;
+	}
+	if (uuid[8] == 0)
+		generate_random_uuid(uuid);
+
+	if (get_user(len, oldlenp))
+		return -EFAULT;
+	if (len) {
+		if (len > 16)
+			len = 16;
+		if (copy_to_user(oldval, uuid, len) ||
+		    put_user(len, oldlenp))
+			return -EFAULT;
+	}
+	return 1;
+}
+
+ctl_table random_table[] = {
+	{
+		.ctl_name	= RANDOM_POOLSIZE,
+		.procname	= "poolsize",
+		.data		= &sysctl_poolsize,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_do_poolsize,
+		.strategy	= &poolsize_strategy,
+	},
+	{
+		.ctl_name	= RANDOM_ENTROPY_COUNT,
+		.procname	= "entropy_avail",
+		.maxlen		= sizeof(int),
+		.mode		= 0444,
+		.proc_handler	= &proc_dointvec,
+	},
+	{
+		.ctl_name	= RANDOM_READ_THRESH,
+		.procname	= "read_wakeup_threshold",
+		.data		= &random_read_wakeup_thresh,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &min_read_thresh,
+		.extra2		= &max_read_thresh,
+	},
+	{
+		.ctl_name	= RANDOM_WRITE_THRESH,
+		.procname	= "write_wakeup_threshold",
+		.data		= &random_write_wakeup_thresh,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &min_write_thresh,
+		.extra2		= &max_write_thresh,
+	},
+	{
+		.ctl_name	= RANDOM_BOOT_ID,
+		.procname	= "boot_id",
+		.data		= &sysctl_bootid,
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_do_uuid,
+		.strategy	= &uuid_strategy,
+	},
+	{
+		.ctl_name	= RANDOM_UUID,
+		.procname	= "uuid",
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_do_uuid,
+		.strategy	= &uuid_strategy,
+	},
+	{
+		.ctl_name	= RANDOM_DIGEST_ALGO,
+		.procname	= "digest_algo",
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_dostring,
+	},
+	{
+		.ctl_name	= RANDOM_CIPHER_ALGO,
+		.procname	= "cipher_algo",
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_dostring,
+	},
+	{ .ctl_name = 0 }
+};
+
+static void sysctl_init_random(struct entropy_store *random_state)
+{
+	int i;
+
+	/* If the sys-admin doesn't want people to know how fast
+	 * random events are happening, he can set the read-threshhold
+	 * down to zero so /dev/random never blocks.  Default is to block.
+	 * This is for the paranoid loonies who think frequency analysis
+	 * would lead to something.
+	 */
+	min_read_thresh = 0;
+	min_write_thresh = 0;
+	max_read_thresh = max_write_thresh = POOLBITS;
+	for (i=0; random_table[i].ctl_name!=0; i++) {
+		switch (random_table[i].ctl_name) {
+		case RANDOM_ENTROPY_COUNT:
+			// If we don't want 
+#if RANDOM_NO_ENTROPY_COUNT
+			random_table[i].data = &random_state->entropy_count_bogus;
+			random_state->entropy_count_bogus = POOLBITS;
+#else
+			random_table[i].data = &random_state->entropy_count;
+#endif
+		break;
+
+		case RANDOM_DIGEST_ALGO:
+			random_table[i].data = (void*)random_state->digestAlgo;
+		break;
+
+		case RANDOM_CIPHER_ALGO:
+			random_table[i].data = (void*)random_state->cipherAlgo;
+		break;
+
+		default:
+		break;
+		}
+	}
+}
+#endif 	/* CONFIG_SYSCTL */
+
+/********************************************************************
+ *
+ * Random funtions for networking
+ *
+ ********************************************************************/
+
+/*
+ * TCP initial sequence number picking.  This uses the random number
+ * generator to pick an initial secret value.  This value is encrypted
+ * with the TCP endpoint information to provide a unique starting point
+ * for each pair of TCP endpoints.  This defeats attacks which rely on
+ * guessing the initial TCP sequence number.  This algorithm was
+ * suggested by Steve Bellovin, modified by Jean-Luc Cooke.
+ *
+ * Using a very strong hash was taking an appreciable amount of the total
+ * TCP connection establishment time, so this is a weaker hash,
+ * compensated for by changing the secret periodically.  This was changed
+ * again by Jean-Luc Cooke to use AES256-CBC encryption which is faster
+ * still (see `/usr/bin/openssl speed md4 sha1 aes`)
+ */
+
+/* This should not be decreased so low that ISNs wrap too fast. */
+#define REKEY_INTERVAL	(300*HZ)
+/*
+ * Bit layout of the tcp sequence numbers (before adding current time):
+ * bit 24-31: increased after every key exchange
+ * bit 0-23: hash(source,dest)
+ *
+ * The implementation is similar to the algorithm described
+ * in the Appendix of RFC 1185, except that
+ * - it uses a 1 MHz clock instead of a 250 kHz clock
+ * - it performs a rekey every 5 minutes, which is equivalent
+ * 	to a (source,dest) tulple dependent forward jump of the
+ * 	clock by 0..2^(HASH_BITS+1)
+ *
+ * Thus the average ISN wraparound time is 68 minutes instead of
+ * 4.55 hours.
+ *
+ * SMP cleanup and lock avoidance with poor man's RCU.
+ * 			Manfred Spraul <manfred@colorfullife.com>
+ * 		
+ */
+#define COUNT_BITS	8
+#define COUNT_MASK	( (1<<COUNT_BITS)-1)
+#define HASH_BITS	24
+#define HASH_MASK	( (1<<HASH_BITS)-1 )
+
+static spinlock_t ip_lock = SPIN_LOCK_UNLOCKED;
+static unsigned int ip_cnt, network_count;
+
+static void __check_and_rekey(time_t time)
+{
+	u8 tmp[RANDOM_MAX_KEY_SIZE];
+	spin_lock_bh(&ip_lock);
+
+	get_random_bytes(tmp, random_state->keysize);
+	crypto_cipher_setkey(random_state->networkCipher,
+					(const u8*)tmp,
+					random_state->keysize);
+	random_state->networkCipher_ready = 1;
+	network_count = (ip_cnt & COUNT_MASK) << HASH_BITS;
+	mb();
+	ip_cnt++;
+
+	spin_unlock_bh(&ip_lock);
+	return;
+}
+
+static inline void check_and_rekey(time_t time)
+{
+	static time_t rekey_time=0;
+
+	rmb();
+	if (!rekey_time || (time - rekey_time) > REKEY_INTERVAL) {
+		__check_and_rekey(time);
+		rekey_time = time;
+	}
+
+	return;
+}
+
+#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
+__u32 secure_tcpv6_sequence_number(__u32 *saddr, __u32 *daddr,
+				   __u16 sport, __u16 dport)
+{
+	struct timeval 	tv;
+	__u32		seq;
+	__u32		tmp[4];
+	struct scatterlist sgtmp[1];
+
+	/*
+	 * The procedure is the same as for IPv4, but addresses are longer.
+	 * Thus we must use two AES operations.
+	 */
+
+	do_gettimeofday(&tv);	/* We need the usecs below... */
+	check_and_rekey(tv.tv_sec);
+
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	/*
+	 * AES256 is 2.5 times faster then MD4 by openssl tests.
+	 * We can afford to encrypt 2 block in CBC with
+	 * and IV={(sport)<<16 | dport, 0, 0, 0}
+	 *
+	 * seq = ct[0], ct = Enc-CBC(Key, {ports}, {daddr, saddr});
+	 *                 = Enc(Key, saddr xor Enc(Key, daddr))
+	 */ 
+	
+	/* PT0 = daddr */
+	memcpy(tmp, daddr, random_state->blocksize);
+	/* IV = {ports,0,0,0} */
+	tmp[0] ^= (sport<<16) | dport;
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+	/* PT1 = saddr */
+	random_state->networkCipher->crt_cipher.cit_xor_block((u8*)tmp,
+		(const u8*)saddr);
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	seq = tmp[0];
+	seq += network_count;
+	seq += tv.tv_usec + tv.tv_sec*1000000;
+
+	return seq;
+}
+EXPORT_SYMBOL(secure_tcpv6_sequence_number);
+
+__u32 secure_ipv6_id(__u32 *daddr)
+{
+	__u32 tmp[4];
+	struct scatterlist sgtmp[1];
+
+	check_and_rekey(get_seconds());
+
+	memcpy(tmp, daddr, random_state->blocksize);
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	/* id = tmp[0], tmp = Enc(Key, daddr); */
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	return tmp[0];
+}
+
+EXPORT_SYMBOL(secure_ipv6_id);
+#endif
+
+
+__u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
+				 __u16 sport, __u16 dport)
+{
+	struct timeval 	tv;
+	__u32		seq;
+	__u32 tmp[4];
+	struct scatterlist sgtmp[1];
+
+	/*
+	 * Pick a random secret every REKEY_INTERVAL seconds.
+	 */
+	do_gettimeofday(&tv);	/* We need the usecs below... */
+	check_and_rekey(tv.tv_sec);
+
+	/*
+	 *  Pick a unique starting offset for each TCP connection endpoints
+	 *  (saddr, daddr, sport, dport).
+	 *  Note that the words are placed into the starting vector, which is 
+	 *  then mixed with a partial MD4 over random data.
+	 */
+	/*
+	 * AES256 is 2.5 times faster then MD4 by openssl tests.
+	 * We can afford to encrypt 1 block
+	 *
+	 * seq = ct[0], ct = Enc(Key, {(sport<<16)|dport, daddr, saddr, 0})
+	 */ 
+	
+	tmp[0] = (sport<<16) | dport;
+	tmp[1] = daddr;
+	tmp[2] = saddr;
+	tmp[3] = 0;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	seq = tmp[0];
+	seq += network_count;
+	/*
+	 *	As close as possible to RFC 793, which
+	 *	suggests using a 250 kHz clock.
+	 *	Further reading shows this assumes 2 Mb/s networks.
+	 *	For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
+	 *	That's funny, Linux has one built in!  Use it!
+	 *	(Networks are faster now - should this be increased?)
+	 */
+	seq += tv.tv_usec + tv.tv_sec*1000000;
+
+#if 0
+	printk("init_seq(%lx, %lx, %d, %d) = %d\n",
+	       saddr, daddr, sport, dport, seq);
+#endif
+	return seq;
+}
+
+EXPORT_SYMBOL(secure_tcp_sequence_number);
+
+/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
+ *  All blames to Andrey V. Savochkin <saw@msu.ru>.
+ *  Changed by Jean-Luc Cooke <jlcooke@certainkey.com> to use AES & C.A.P.I.
+ */
+__u32 secure_ip_id(__u32 daddr)
+{
+	struct scatterlist sgtmp[1];
+	__u32 tmp[4];
+
+	check_and_rekey(get_seconds());
+
+	/*
+	 *  Pick a unique starting offset for each IP destination.
+	 *  id = ct[0], ct = Enc(Key, {daddr,0,0,0});
+	 */
+	tmp[0] = daddr;
+	tmp[1] = 0;
+	tmp[2] = 0;
+	tmp[3] = 0;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	return tmp[0];
+}
+
+u32 secure_tcp_port_ephemeral(__u32 saddr, __u32 daddr, __u16 dport)
+{
+	struct scatterlist sgtmp[1];
+	__u32 tmp[4];
+
+	check_and_rekey(get_seconds());
+
+	/*
+	 *  Pick a unique starting offset for each ephemeral port search
+	 *  id = ct[0], ct = Enc(Key, {saddr,daddr,dport,0});
+	 */
+	memset(tmp, 0, sizeof(tmp));
+	tmp[0] = saddr;
+	tmp[1] = daddr;
+	tmp[2] = dport;
+	tmp[3] = 0;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	return tmp[0];
+}
+
+#ifdef CONFIG_SYN_COOKIES
+/*
+ * Secure SYN cookie computation. This is the algorithm worked out by
+ * Dan Bernstein and Eric Schenk.
+ *
+ * For linux I implement the 1 minute counter by looking at the jiffies clock.
+ * The count is passed in as a parameter, so this code doesn't much care.
+ * 
+ * SYN cookie (and seq# & id#) Changed in 2004 by Jean-Luc Cooke
+ * <jlcooke@certainkey.com> to use the C.A.P.I. and AES256.
+ */
+
+#define COOKIEBITS 24	/* Upper bits store count */
+#define COOKIEMASK (((__u32)1 << COOKIEBITS) - 1)
+
+__u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport,
+		__u16 dport, __u32 sseq, __u32 count, __u32 data)
+{
+	struct scatterlist sg[1];
+	__u32   tmp[4];
+
+	/*
+	 * Compute the secure sequence number.
+	 *
+	 * Output is the 32bit tag of a CBC-MAC of
+	 * PT={count,0,0,0} with IV={addr,daddr,sport|dport,sseq}
+	 *   cookie = {<8bit count>,
+	 *             truncate_24bit(
+	 *               Encrypt(Sec, {saddr,daddr,sport|dport,sseq})
+	 *             )
+	 *            }
+	 *
+	 * DJB wrote (http://cr.yp.to/syncookies/archive) about how to do this
+	 * with hash algorithms.
+	 * - we can replace two SHA1s used in the previous kernel with 1 AES
+	 *   and make things 5x faster
+	 * - I'd like to propose we remove the use of two whittenings with a
+	 *   single operation since we were only using addition modulo 2^32 of
+	 *   all these values anyways.  Not to mention the hashs differ only in
+	 *   that the second processes more data... why drop the first hash?
+	 *   We did learn that addition is commutative and associative long ago.
+	 * - by replacing two SHA1s and addition modulo 2^32 with encryption of
+	 *   a 32bit value using CAPI we've made it 1,000,000,000 times easier
+	 *   to understand what is going on.
+	 */
+
+	tmp[0] = saddr;
+	tmp[1] = daddr;
+	tmp[2] = (sport << 16) + dport;
+	tmp[3] = sseq;
+
+	sg[0].page = virt_to_page(tmp);
+	sg[0].offset = offset_in_page(tmp);
+	sg[0].length = random_state->blocksize;
+	if (!random_state->networkCipher_ready) {
+		check_and_rekey(get_seconds());
+	}
+	/* tmp[]/sg[0] = Enc(Sec, {saddr,daddr,sport|dport,sseq}) */
+	crypto_cipher_encrypt(random_state->networkCipher, sg, sg,
+		random_state->blocksize);
+
+	/* cookie = CTR encrypt of 8-bit-count and 24-bit-data */
+printk("random: secure_tcp_syn_cookie cook=%x", tmp[0] ^ ( (count << COOKIEBITS) | (data & COOKIEMASK) ) );
+	return tmp[0] ^ ( (count << COOKIEBITS) | (data & COOKIEMASK) );
+}
+
+/*
+ * This retrieves the small "data" value from the syncookie.
+ * If the syncookie is bad, the data returned will be out of
+ * range.  This must be checked by the caller.
+ *
+ * The count value used to generate the cookie must be within
+ * "maxdiff" if the current (passed-in) "count".  The return value
+ * is (__u32)-1 if this test fails.
+ */
+__u32 check_tcp_syn_cookie(__u32 cookie, __u32 saddr, __u32 daddr, __u16 sport,
+		__u16 dport, __u32 sseq, __u32 count, __u32 maxdiff)
+{
+	struct scatterlist sg[1];
+	__u32 tmp[4], thiscount, diff;
+
+printk("random: check_tcp_syn_cookie state=%p", random_state);
+	if (random_state == NULL  ||  !random_state->networkCipher_ready)
+		return (__u32)-1;       /* Well, duh! */
+
+	tmp[0] = saddr;
+	tmp[1] = daddr;
+	tmp[2] = (sport << 16) + dport;
+	tmp[3] = sseq;
+	sg[0].page = virt_to_page(tmp);
+	sg[0].offset = offset_in_page(tmp);
+	sg[0].length = random_state->blocksize;
+	crypto_cipher_encrypt(random_state->networkCipher, sg, sg,
+		random_state->blocksize);
+
+	/* CTR decrypt the cookie */
+	cookie ^= tmp[0];
+
+	/* top 8 bits are 'count' */
+	thiscount = cookie >> COOKIEBITS;
+
+	diff = count - thiscount;
+printk("random: check_tcp_syn_cookie diff=%x maxdiff=%x", diff, maxdiff);
+	if (diff >= maxdiff)
+		return (__u32)-1;
+
+	/* bottom 24 bits are 'data' */
+	return cookie & COOKIEMASK;
+}
+#endif
--- linux-2.6.11.6/drivers/char/Makefile	2005-03-25 22:28:37.000000000 -0500
+++ linux-2.6.11.6-fort/drivers/char/Makefile	2005-03-30 09:04:49.000000000 -0500
@@ -7,7 +7,13 @@
 #
 FONTMAPFILE = cp437.uni
 
-obj-y	 += mem.o random.o tty_io.o n_tty.o tty_ioctl.o
+obj-y	 += mem.o
+ifeq ($(CONFIG_CRYPTO_RANDOM_FORTUNA),y)
+  obj-y	 += random-fortuna.o
+else
+  obj-y	 += random.o
+endif
+obj-y	 += tty_io.o n_tty.o tty_ioctl.o
 
 obj-$(CONFIG_LEGACY_PTYS)	+= pty.o
 obj-$(CONFIG_UNIX98_PTYS)	+= pty.o
--- linux-2.6.11.6/include/linux/sysctl.h	2005-03-25 22:28:22.000000000 -0500
+++ linux-2.6.11.6-fort/include/linux/sysctl.h	2005-03-30 09:04:49.000000000 -0500
@@ -202,7 +202,9 @@
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,
 	RANDOM_BOOT_ID=5,
-	RANDOM_UUID=6
+	RANDOM_UUID=6,
+	RANDOM_DIGEST_ALGO=7,
+	RANDOM_CIPHER_ALGO=8
 };
 
 /* /proc/sys/kernel/pty */

[PATCH 2.6.12-rc1] API for true Random Number Generators to add entropy

[David McCullough]

Hi all,

Here is a revised patch for 2.6.12-rc1 that adds a routine:

    add_true_randomness(__u32 *buf, int nwords);

so that true random number generator device drivers can add a entropy
to the system.

Cheers,
Davidm

Signed-off-by: David McCullough <davidm@snapgear.com>

--- linux-2.6.12-rc1.orig/drivers/char/random.c	2005-03-18 11:33:49.000000000 +1000
+++ linux-2.6.12-rc1/drivers/char/random.c	2005-03-24 16:16:40.000000000 +1000
@@ -1148,6 +1148,36 @@
 EXPORT_SYMBOL(generate_random_uuid);
 
 /********************************************************************
+ * provide a mechanism for HW to add entropy that is of
+ * very good quality from a true random number generator
+ ***************************************************************/
+
+void add_true_randomness(__u32 *buf, int nwords)
+{
+	struct entropy_store *r;
+	int wakeup_check = 0;
+
+	/*
+	 * if we have too much entropy, put some in the secondary pool
+	 */
+	r = &blocking_pool;
+	if (r->entropy_count >= r->poolinfo->POOLBITS)
+		r = &nonblocking_pool;
+	else
+		wakeup_check = (r->entropy_count < random_read_wakeup_thresh);
+
+	add_entropy_words(r, buf, nwords);
+	credit_entropy_store(r, nwords * 32);
+
+	/*
+	 * wakeup if we added enough entropy to cross the threshold
+	 */
+	if (wakeup_check && r->entropy_count >= random_read_wakeup_thresh)
+		wake_up_interruptible(&random_read_wait);
+}
+EXPORT_SYMBOL(add_true_randomness);
+
+/********************************************************************
  *
  * Sysctl interface
  *
--- linux-2.6.12-rc1.orig/include/linux/random.h	2005-03-18 11:34:37.000000000 +1000
+++ linux-2.6.12-rc1/include/linux/random.h	2005-03-24 15:59:42.000000000 +1000
@@ -48,6 +48,8 @@
 				 unsigned int value);
 extern void add_interrupt_randomness(int irq);
 
+extern void add_true_randomness(__u32 *buf, int nwords);
+
 extern void get_random_bytes(void *buf, int nbytes);
 void generate_random_uuid(unsigned char uuid_out[16]);
 

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[David McCullough]

Jivin Andrew Morton lays it down ...
> David McCullough <davidm@snapgear.com> wrote:
> >
> > Here is a small patch for 2.6.11 that adds a routine:
> > 
> >  	add_true_randomness(__u32 *buf, int nwords);
> 
> It neither applies correctly nor compiles in current kernels.  2.6.11 is
> very old in kernel time.

Sorry about that,  I had actually checked a fairly recent bk version
and noticed quite a few changes.  I used that to figure out what I could
do that would apply reasonably to both 2.4 and 2.6 kernels,  and then
forgot about all those new changes and used the older release kernel.

See the new patch.

> Are we likely to see any in-kernel users of this?

Both the OCF port that I am working on and Evgeniy Polyakov's acrypto
support devices that could use such an API.  The OCF port has already
has two drivers (hifn and safenet) that are using this and,  depending
on how this pans out,  there will be another for Xscale soon.

Whether or not these users of it end up in the kernel is out of my hands
somewhat :-)

Cheers,
Davidm

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andi Kleen]

Andrew Morton <akpm@osdl.org> writes:

> David McCullough <davidm@snapgear.com> wrote:
>>
>> Here is a small patch for 2.6.11 that adds a routine:
>> 
>>  	add_true_randomness(__u32 *buf, int nwords);
>
> It neither applies correctly nor compiles in current kernels.  2.6.11 is
> very old in kernel time.
>
> Are we likely to see any in-kernel users of this?

I added similar support to the pre hw_random AMD8111 driver
a long time ago. Basically a timer that regularly read some
dat from the hw random generator and feed it into the random
code.

I think it is a good idea, because it doesnt make much sense
imho to run a daemon for something that can be done in 20 lines
of code in the kernel.

-Andi 

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Andi Kleen wrote:
> Andrew Morton <akpm@osdl.org> writes:
> 
> 
>>David McCullough <davidm@snapgear.com> wrote:
>>
>>>Here is a small patch for 2.6.11 that adds a routine:
>>>
>>> 	add_true_randomness(__u32 *buf, int nwords);
>>
>>It neither applies correctly nor compiles in current kernels.  2.6.11 is
>>very old in kernel time.
>>
>>Are we likely to see any in-kernel users of this?
> 
> 
> I added similar support to the pre hw_random AMD8111 driver
> a long time ago. Basically a timer that regularly read some
> dat from the hw random generator and feed it into the random
> code.
> 
> I think it is a good idea, because it doesnt make much sense
> imho to run a daemon for something that can be done in 20 lines
> of code in the kernel.

Check your kernel history.

We -used- to need data from RNG directly into the kernel randomness 
pool.  The consensus was that the FIPS testing should be moved to userspace.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andi Kleen]

> We -used- to need data from RNG directly into the kernel randomness 

Are you sure? I dont think there was ever code to do this in
mainline. There might have been something in -ac*, but not mainline.

> pool.  The consensus was that the FIPS testing should be moved to userspace.

Consensus from whom? And who says the FIPS testing is useful anyways?

I think you just need to trust the random generator, it is like
you need to trust any other piece of hardware in your machine. Or do you 
check regularly if you mov instruction still works? @)

I think it is a trade off between easy to use and saving of 
resources and overly paranoia. With an user space solution
which near nobody uses currently (I am not aware of 
any distribution that runs that daemon)
it means most people wont have hardware supported randomness
in their ssh, and I think that is a big drawback.

Also I dont like the memory consumption of the daemon. It needs
at least 20+k for kernel stack, page tables etc. I know
a lot of people dont care about memory usage anymore, but I still
do.  It is not a lot of memory, but bloat does usually not come in big
pieces but in small amounts of a time. And the code to do it
from kernel space is really simple. 

And it would suddenly make a lot of peoples ssh/https etc. more secure, 
which is a good thing. Probably would help Linux security a lot 
more than all these crazy - "ABI, what ABI?" - buffer overflow 
workarounds.

If you are really paranoid you can always turn off the sysctl
and do it from userspace. 

-Andi

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[folkert]

[-- Attachment #1: Type: text/plain, Size: 1218 bytes --]

> > pool.  The consensus was that the FIPS testing should be moved to userspace.
> Consensus from whom? And who says the FIPS testing is useful anyways?
> I think you just need to trust the random generator, it is like
> you need to trust any other piece of hardware in your machine. Or do you 
> check regularly if you mov instruction still works? @)

For joe-user imho it's better to do a check from a cronjob once a day. But for
high demand security, maybe make it pluggable? Like that a user can plug-in some
module which does the testing? Then you can have several kinds of tests
depending on your needs.


Folkert van Heusden

Auto te koop! Zie: http://www.vanheusden.com/daihatsu.php
Op zoek naar een IT of Finance baan? Mail me voor de mogelijkheden!
+------------------------------------------------------------------+
|UNIX admin? Then give MultiTail (http://vanheusden.com/multitail/)|
|a try, it brings monitoring logfiles to a different level! See    |
|http://vanheusden.com/multitail/features.html for a feature list. |
+------------------------------------------= www.unixsoftware.nl =-+
Phone: +31-6-41278122, PGP-key: 1F28D8AE
Get your PGP/GPG key signed at www.biglumber.com!

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andi Kleen]

On Sun, Mar 27, 2005 at 08:55:03PM +0200, folkert@vanheusden.com wrote:
> > > pool.  The consensus was that the FIPS testing should be moved to userspace.
> > Consensus from whom? And who says the FIPS testing is useful anyways?
> > I think you just need to trust the random generator, it is like
> > you need to trust any other piece of hardware in your machine. Or do you 
> > check regularly if you mov instruction still works? @)
> 
> For joe-user imho it's better to do a check from a cronjob once a day. But for
> high demand security, maybe make it pluggable? Like that a user can plug-in some
> module which does the testing? Then you can have several kinds of tests
> depending on your needs.

In my old 2.4 patch there was a sysctl to turn off the kernel reseeding.
If you turn it off you can do it in user space. That might be
an option for the clinical paranoid. 

BTW what do you do when the FIPS test fails? I dont see a good fallback
path for this case.

-Andi

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[folkert]

> > For joe-user imho it's better to do a check from a cronjob once a day. But for
> > high demand security, maybe make it pluggable? Like that a user can plug-in some
> > module which does the testing? Then you can have several kinds of tests
> > depending on your needs.
> In my old 2.4 patch there was a sysctl to turn off the kernel reseeding.
> If you turn it off you can do it in user space. That might be
> an option for the clinical paranoid. 
> BTW what do you do when the FIPS test fails? I dont see a good fallback
> path for this case.

Send a message to klogd and let read() block untill the test no longer fails.


Folkert van Heusden

Auto te koop! Zie: http://www.vanheusden.com/daihatsu.php
Op zoek naar een IT of Finance baan? Mail me voor de mogelijkheden!
+------------------------------------------------------------------+
|UNIX admin? Then give MultiTail (http://vanheusden.com/multitail/)|
|a try, it brings monitoring logfiles to a different level! See    |
|http://vanheusden.com/multitail/features.html for a feature list. |
+------------------------------------------= www.unixsoftware.nl =-+
Phone: +31-6-41278122, PGP-key: 1F28D8AE
Get your PGP/GPG key signed at www.biglumber.com!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Andi Kleen wrote:
> BTW what do you do when the FIPS test fails? I dont see a good fallback
> path for this case.

If the FIPS test fails, do the obvious:  don't feed that data to the 
kernel (and credit entropy), and possibly stop using the hardware RNG 
under a human has intervened.

This is not rocket science.  The fallback path is "use software", which 
is what most users do right now anyway.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andi Kleen]

On Tue, Mar 29, 2005 at 02:17:24AM -0500, Jeff Garzik wrote:
> Andi Kleen wrote:
> >BTW what do you do when the FIPS test fails? I dont see a good fallback
> >path for this case.
> 
> If the FIPS test fails, do the obvious:  don't feed that data to the 
> kernel (and credit entropy), and possibly stop using the hardware RNG 

This will just cause hangs; basically it is a DOS. 

> under a human has intervened.
> 
> This is not rocket science.  The fallback path is "use software", which 
> is what most users do right now anyway.

Just that use software does not work on a headless machine sitting
in a rack with not much disk IO. 

-Andi

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

folkert@vanheusden.com wrote:
>>>pool.  The consensus was that the FIPS testing should be moved to userspace.
>>
>>Consensus from whom? And who says the FIPS testing is useful anyways?
>>I think you just need to trust the random generator, it is like
>>you need to trust any other piece of hardware in your machine. Or do you 
>>check regularly if you mov instruction still works? @)
> 
> 
> For joe-user imho it's better to do a check from a cronjob once a day. But for

That would not catch the hardware failures seen in the field, in the past.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andi Kleen]

On Tue, Mar 29, 2005 at 02:16:12AM -0500, Jeff Garzik wrote:
> folkert@vanheusden.com wrote:
> >>>pool.  The consensus was that the FIPS testing should be moved to 
> >>>userspace.
> >>
> >>Consensus from whom? And who says the FIPS testing is useful anyways?
> >>I think you just need to trust the random generator, it is like
> >>you need to trust any other piece of hardware in your machine. Or do you 
> >>check regularly if you mov instruction still works? @)
> >
> >
> >For joe-user imho it's better to do a check from a cronjob once a day. But 
> >for
> 
> That would not catch the hardware failures seen in the field, in the past.

I am sure that all hardware in the field has failed in the past
at some point - but that still does not mean we dont trust
hardware in Linux. There simply is no choice.

I think we have a case here of the perfect being the enemy of the good.

I just want a simple solution that works for near all users out of 
the box without needing resource eating and hard to configure daemons
of dubious value.

You are extrapolating from extremly unlikely events and think
it makes sense to handle them - which I think is wrong.

The cronjob once a day or once an hour setup should catch
the hardware failures anyways, and for shorter time amounts
the random buffer in the kernel can handle bad input.

-Andi (who should probably just resubmit the patch)

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Andi Kleen wrote:
>>We -used- to need data from RNG directly into the kernel randomness 
> 
> 
> Are you sure? I dont think there was ever code to do this in
> mainline. There might have been something in -ac*, but not mainline.

Yes, I am positive.  I wrote the code.  Look at the old Intel RNG driver 
code, before it grew AMD and VIA support, and became hw_random.


>>pool.  The consensus was that the FIPS testing should be moved to userspace.
> 
> 
> Consensus from whom? And who says the FIPS testing is useful anyways?

lkml.  Read the archives.

> I think you just need to trust the random generator, it is like
> you need to trust any other piece of hardware in your machine. Or do you 
> check regularly if you mov instruction still works? @)

Hardware RNGs -have- failed in the past.  And if you are going to credit 
entropy to the data -- a very big deal -- it damn well better be random 
data.  Otherwise failures cascade through the system.


> I think it is a trade off between easy to use and saving of 
> resources and overly paranoia. With an user space solution
> which near nobody uses currently (I am not aware of 
> any distribution that runs that daemon)

Debian does.

It's under-use is mainly because nobody has an RNG.


> it means most people wont have hardware supported randomness
> in their ssh, and I think that is a big drawback.

"big drawback" == 99% of users right now.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 6854 bytes --]

On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
> Hi all,
> 
> Here is a small patch for 2.6.11 that adds a routine:
> 
> 	add_true_randomness(__u32 *buf, int nwords);
> 
> so that true random number generator device drivers can add a entropy
> to the system.  Drivers that use this can be found in the latest release
> of ocf-linux,  an asynchronous crypto implementation for linux based on
> the *BSD Cryptographic Framework.
> 
> 	http://ocf-linux.sourceforge.net/
> 
> Adding this can dramatically improve the performance of /dev/random on
> small embedded systems which do not generate much entropy.

People will not apply any kind of such changes.
Both OCF and acrypto already handle all RNG cases - no need for any kind
of userspace daemon or entropy (re)injection mechanism.
Anyone who want to use HW randomness may use OCF/acrypto mechanism.
For example here is patch to enable acrypto support for hw_random.c
It is very simple and support only upto 4 bytes request, of course it
is 
not interested for anyone, but it is only 2-minutes example:

--- ./drivers/char/hw_random.c.orig     2005-03-24 13:36:05.000000000 +0300
+++ ./drivers/char/hw_random.c  2005-03-24 14:48:30.470407432 +0300
@@ -34,6 +34,10 @@
 #include <linux/smp_lock.h>
 #include <linux/mm.h>
 #include <linux/delay.h>
+#include <linux/acrypto.h>
+#include <linux/crypto_def.h>
+#include <linux/crypto_stat.h>
+#include <linux/highmem.h>

 #ifdef __i386__
 #include <asm/msr.h>
@@ -73,6 +77,8 @@
 #endif

 #define RNG_MISCDEV_MINOR              183 /* official */
+
+static DEFINE_SPINLOCK(rng_lock);

 static int rng_dev_open (struct inode *inode, struct file *filp);
 static ssize_t rng_dev_read (struct file *filp, char __user *buf, size_t size,
@@ -482,7 +488,6 @@
 static ssize_t rng_dev_read (struct file *filp, char __user *buf, size_t size,
                                loff_t * offp)
 {
-       static DEFINE_SPINLOCK(rng_lock);
        unsigned int have_data;
        u32 data = 0;
        ssize_t ret = 0;
@@ -526,7 +531,109 @@
        return ret;
 }

+#define CONFIG_ACRYPTO
+#ifdef CONFIG_ACRYPTO
+static struct crypto_device *hwr_cdev;
+static struct crypto_capability hwr_caps[] =   {
+       {CRYPTO_OP_RNG, 0, 0, 100},
+};
+

+static void hwr_data_ready(struct crypto_device *dev)
+{
+       struct crypto_session *s, *n;
+       unsigned long flags;
+       u32 data = 0;
+       unsigned int have_data;
+       u8 *ptr, *optr;
+
+       local_irq_save(flags);
+       if (spin_trylock(&dev->session_lock)) {
+               local_irq_restore(flags);
+               return;
+       }
+
+       list_for_each_entry_safe(s, n, &dev->session_list, dev_queue_entry) {
+               if (!session_completed(s) && !session_is_processed(s)) {
+                       start_process_session(s);
+                       spin_lock(&rng_lock);
+                       have_data = 0;
+                       if (rng_ops->data_present()) {
+                               data = rng_ops->data_read();
+                               have_data = rng_ops->n_bytes;
+                       }
+                       spin_unlock (&rng_lock);
+
+                       optr = ptr = kmap_atomic(s->data.sg_dst[0].page, KM_USER0) + s->data.sg_dst[0].offset;
+                       while (s->data.sg_dst[0].length && have_data) {
+                               *ptr++ = data & 0xff;
+                               s->data.sg_dst[0].length--;
+                               have_data--;
+                               data >>= 8;
+                       }
+                       kunmap_atomic(optr, KM_USER0);
+
+                       if (s->data.sg_dst[0].length)
+                               broke_session(s); /* Need proper work deferring, see async_provider.c as example. */
+
+                       crypto_stat_complete_inc(s);
+                       crypto_session_dequeue_route(s);
+                       complete_session(s);
+                       stop_process_session(s);
+               }
+       }
+
+       spin_unlock(&dev->session_lock);
+       local_irq_restore(flags);
+}
+
+static int hwr_acrypto_init(struct rng_operations *ops)
+{
+       int err;
+
+       hwr_cdev = kmalloc(sizeof(*hwr_cdev), GFP_KERNEL);
+       if (!hwr_cdev) {
+               printk(KERN_ERR "Failed to allocate new crypto_device structure.\n");
+               return -ENOMEM;
+       }
+
+       memset(hwr_cdev, 0, sizeof(*hwr_cdev));
+
+       hwr_cdev->cap           = hwr_caps;
+       hwr_cdev->cap_number    = sizeof(hwr_caps)/sizeof(hwr_caps[0]);
+       hwr_cdev->priv          = ops;
+       hwr_cdev->data_ready    = &hwr_data_ready;
+       snprintf(hwr_cdev->name, sizeof(hwr_cdev->name), "%s", "hwr");
+
+       err = crypto_device_add(hwr_cdev);
+       if (err) {
+               kfree(hwr_cdev);
+               hwr_cdev = NULL;
+               return err;
+       }
+
+       printk(KERN_INFO "%s acrypto support is turned on.\n", hwr_cdev->name);
+
+       return err;
+}
+
+static void hwr_acrypto_fini(void)
+{
+       crypto_device_remove(hwr_cdev);
+       printk(KERN_INFO "%s acrypto support is turned off.\n", hwr_cdev->name);
+       kfree(hwr_cdev);
+       hwr_cdev = NULL;
+}
+#else
+static int hwr_acrypto_init(struct rng_operations *ops)
+{
+       return 0;
+}
+
+static void hwr_acrypto_fini(void)
+{
+}
+#endif

 /*
  * rng_init_one - look for and attempt to init a single RNG
@@ -549,9 +656,15 @@
                goto err_out_cleanup_hw;
        }

+       rc = hwr_acrypto_init(rng_ops);
+       if (rc)
+               goto err_out_misc_unregister;
+
        DPRINTK ("EXIT, returning 0\n");
        return 0;

+err_out_misc_unregister:
+       misc_deregister(&rng_miscdev);
 err_out_cleanup_hw:
        rng_ops->cleanup();
 err_out:
@@ -617,6 +730,8 @@
 {
        DPRINTK ("ENTER\n");

+       hwr_acrypto_fini();
+
        misc_deregister (&rng_miscdev);

        if (rng_ops->cleanup)


So, one may use crypto_session_alloc(gimme_real_randomness) and that is
all
(either from userspace or kernelspace).
As far as I can see, OCF support is also very simple.

What I want to say, is that since OCF and acrypto already support
all RNG cases, it is better to port existing drivers to them, but
not the reverse.
That will allow to use both old hw_random.c driver and
any new one(HIFN, VIA, safenet, any other) without breaking any
interfaces from both userspace and kernelspace.

If one of the asynchronous crypto layers will be included, 
/dev/random implementation can be changed to support it.

> Cheers,
> Davidm

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
> 
>>Hi all,
>>
>>Here is a small patch for 2.6.11 that adds a routine:
>>
>>	add_true_randomness(__u32 *buf, int nwords);
>>
>>so that true random number generator device drivers can add a entropy
>>to the system.  Drivers that use this can be found in the latest release
>>of ocf-linux,  an asynchronous crypto implementation for linux based on
>>the *BSD Cryptographic Framework.
>>
>>	http://ocf-linux.sourceforge.net/
>>
>>Adding this can dramatically improve the performance of /dev/random on
>>small embedded systems which do not generate much entropy.
> 
> 
> People will not apply any kind of such changes.
> Both OCF and acrypto already handle all RNG cases - no need for any kind
> of userspace daemon or entropy (re)injection mechanism.
> Anyone who want to use HW randomness may use OCF/acrypto mechanism.
> For example here is patch to enable acrypto support for hw_random.c
> It is very simple and support only upto 4 bytes request, of course it
> is 
> not interested for anyone, but it is only 2-minutes example:

If you want to add entropy to the kernel entropy pool from hardware RNG, 
you should use the userland daemon, which detects non-random (broken) 
hardware and provides throttling, so that RNG data collection does not 
consume 100% CPU.

If you want to use the hardware RNG directly, it's simple:  just open 
/dev/hw_random.

Hardware RNG should not go kernel->kernel without adding FIPS tests and 
such.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 2120 bytes --]

On Thu, 2005-03-24 at 07:48 -0500, Jeff Garzik wrote:
> Evgeniy Polyakov wrote:
> > On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
> > 
> >>Hi all,
> >>
> >>Here is a small patch for 2.6.11 that adds a routine:
> >>
> >>	add_true_randomness(__u32 *buf, int nwords);
> >>
> >>so that true random number generator device drivers can add a entropy
> >>to the system.  Drivers that use this can be found in the latest release
> >>of ocf-linux,  an asynchronous crypto implementation for linux based on
> >>the *BSD Cryptographic Framework.
> >>
> >>	http://ocf-linux.sourceforge.net/
> >>
> >>Adding this can dramatically improve the performance of /dev/random on
> >>small embedded systems which do not generate much entropy.
> > 
> > 
> > People will not apply any kind of such changes.
> > Both OCF and acrypto already handle all RNG cases - no need for any kind
> > of userspace daemon or entropy (re)injection mechanism.
> > Anyone who want to use HW randomness may use OCF/acrypto mechanism.
> > For example here is patch to enable acrypto support for hw_random.c
> > It is very simple and support only upto 4 bytes request, of course it
> > is 
> > not interested for anyone, but it is only 2-minutes example:
> 
> If you want to add entropy to the kernel entropy pool from hardware RNG, 
> you should use the userland daemon, which detects non-random (broken) 
> hardware and provides throttling, so that RNG data collection does not 
> consume 100% CPU.
> 
> If you want to use the hardware RNG directly, it's simple:  just open 
> /dev/hw_random.
> 
> Hardware RNG should not go kernel->kernel without adding FIPS tests and 
> such.

hw_random can not and will not support HIFN, freescale, ixp and 
great majority of the existing and future HW crypto devices.
I mean that userspace daemon(or any other one) which want to contribute
entropy
should use crypto framwork to obtain all it's data, but not different
access methods for each separate driver.

> 	Jeff

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> hw_random can not and will not support HIFN, freescale, ixp and 
> great majority of the existing and future HW crypto devices.
> I mean that userspace daemon(or any other one) which want to contribute
> entropy
> should use crypto framwork to obtain all it's data, but not different
> access methods for each separate driver.


I don't mean to imply that hw_random should be modified to support all 
hardware RNGs.  Separate drivers are perfectly OK with me.  I would even 
take patches that split up hw_random into an RNG registration interface, 
and AMD/Intel/VIA support modules.

The part I disagree with is direct kernel->kernel RNG usage, with no 
intervening checks.

This has all been discussed years ago, when the FIPS testing was in the 
kernel (and then removed, per consensus).

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[David McCullough]

Jivin Jeff Garzik lays it down ...
> Evgeniy Polyakov wrote:
> >On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
> >
> >>Hi all,
> >>
> >>Here is a small patch for 2.6.11 that adds a routine:
> >>
> >>	add_true_randomness(__u32 *buf, int nwords);
> >>
> >>so that true random number generator device drivers can add a entropy
> >>to the system.  Drivers that use this can be found in the latest release
> >>of ocf-linux,  an asynchronous crypto implementation for linux based on
> >>the *BSD Cryptographic Framework.
> >>
> >>	http://ocf-linux.sourceforge.net/
> >>
> >>Adding this can dramatically improve the performance of /dev/random on
> >>small embedded systems which do not generate much entropy.
> >
> >
> >People will not apply any kind of such changes.
> >Both OCF and acrypto already handle all RNG cases - no need for any kind
> >of userspace daemon or entropy (re)injection mechanism.
> >Anyone who want to use HW randomness may use OCF/acrypto mechanism.
> >For example here is patch to enable acrypto support for hw_random.c
> >It is very simple and support only upto 4 bytes request, of course it
> >is 
> >not interested for anyone, but it is only 2-minutes example:
> 
> If you want to add entropy to the kernel entropy pool from hardware RNG, 
> you should use the userland daemon, which detects non-random (broken) 
> hardware and provides throttling, so that RNG data collection does not 
> consume 100% CPU.
> 
> If you want to use the hardware RNG directly, it's simple:  just open 
> /dev/hw_random.
> 
> Hardware RNG should not go kernel->kernel without adding FIPS tests and 
> such.

For reference,  the RNG on the Safenet I am using this with is
FIPS140 certified.  I believe the HIFN part  is also but I place the doc that
says so.

Cheers,
Davidm

-- 
David McCullough, davidm@snapgear.com  Ph:+61 7 34352815 http://www.SnapGear.com
Custom Embedded Solutions + Security   Fx:+61 7 38913630 http://www.uCdot.org

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 2624 bytes --]

On Thu, 2005-03-24 at 23:23 +1000, David McCullough wrote:
> Jivin Jeff Garzik lays it down ...
> > Evgeniy Polyakov wrote:
> > >On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
> > >
> > >>Hi all,
> > >>
> > >>Here is a small patch for 2.6.11 that adds a routine:
> > >>
> > >>	add_true_randomness(__u32 *buf, int nwords);
> > >>
> > >>so that true random number generator device drivers can add a entropy
> > >>to the system.  Drivers that use this can be found in the latest release
> > >>of ocf-linux,  an asynchronous crypto implementation for linux based on
> > >>the *BSD Cryptographic Framework.
> > >>
> > >>	http://ocf-linux.sourceforge.net/
> > >>
> > >>Adding this can dramatically improve the performance of /dev/random on
> > >>small embedded systems which do not generate much entropy.
> > >
> > >
> > >People will not apply any kind of such changes.
> > >Both OCF and acrypto already handle all RNG cases - no need for any kind
> > >of userspace daemon or entropy (re)injection mechanism.
> > >Anyone who want to use HW randomness may use OCF/acrypto mechanism.
> > >For example here is patch to enable acrypto support for hw_random.c
> > >It is very simple and support only upto 4 bytes request, of course it
> > >is 
> > >not interested for anyone, but it is only 2-minutes example:
> > 
> > If you want to add entropy to the kernel entropy pool from hardware RNG, 
> > you should use the userland daemon, which detects non-random (broken) 
> > hardware and provides throttling, so that RNG data collection does not 
> > consume 100% CPU.
> > 
> > If you want to use the hardware RNG directly, it's simple:  just open 
> > /dev/hw_random.
> > 
> > Hardware RNG should not go kernel->kernel without adding FIPS tests and 
> > such.
> 
> For reference,  the RNG on the Safenet I am using this with is
> FIPS140 certified.  I believe the HIFN part  is also but I place the doc that
> says so.

At least HIFN 795x is certified.

Idea to validate entropy data is good in general, 
but it should be implemented in a way allowing external both in-kernel
and userspace
processes to contribute data.
So for in-kernel use we need such a mechanism, and userspace gkernel
daemon
should use it(as the latest "step") too.

Your changes are correct, ioctl(RNDADDENTROPY) could even use it instead
of direct
add_entropy_words()/credit_entropy_store(), but without external entropy
contributors
it will not be applied by maintainers.

> Cheers,
> Davidm
> 
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> On Thu, 2005-03-24 at 23:23 +1000, David McCullough wrote:
> 
>>Jivin Jeff Garzik lays it down ...
>>
>>>Evgeniy Polyakov wrote:
>>>
>>>>On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
>>>>
>>>>
>>>>>Hi all,
>>>>>
>>>>>Here is a small patch for 2.6.11 that adds a routine:
>>>>>
>>>>>	add_true_randomness(__u32 *buf, int nwords);
>>>>>
>>>>>so that true random number generator device drivers can add a entropy
>>>>>to the system.  Drivers that use this can be found in the latest release
>>>>>of ocf-linux,  an asynchronous crypto implementation for linux based on
>>>>>the *BSD Cryptographic Framework.
>>>>>
>>>>>	http://ocf-linux.sourceforge.net/
>>>>>
>>>>>Adding this can dramatically improve the performance of /dev/random on
>>>>>small embedded systems which do not generate much entropy.
>>>>
>>>>
>>>>People will not apply any kind of such changes.
>>>>Both OCF and acrypto already handle all RNG cases - no need for any kind
>>>>of userspace daemon or entropy (re)injection mechanism.
>>>>Anyone who want to use HW randomness may use OCF/acrypto mechanism.
>>>>For example here is patch to enable acrypto support for hw_random.c
>>>>It is very simple and support only upto 4 bytes request, of course it
>>>>is 
>>>>not interested for anyone, but it is only 2-minutes example:
>>>
>>>If you want to add entropy to the kernel entropy pool from hardware RNG, 
>>>you should use the userland daemon, which detects non-random (broken) 
>>>hardware and provides throttling, so that RNG data collection does not 
>>>consume 100% CPU.
>>>
>>>If you want to use the hardware RNG directly, it's simple:  just open 
>>>/dev/hw_random.
>>>
>>>Hardware RNG should not go kernel->kernel without adding FIPS tests and 
>>>such.
>>
>>For reference,  the RNG on the Safenet I am using this with is
>>FIPS140 certified.  I believe the HIFN part  is also but I place the doc that
>>says so.
> 
> 
> At least HIFN 795x is certified.
> 
> Idea to validate entropy data is good in general, 
> but it should be implemented in a way allowing external both in-kernel
> and userspace
> processes to contribute data.
> So for in-kernel use we need such a mechanism, and userspace gkernel
> daemon
> should use it(as the latest "step") too.

See the earlier discussion, when data validation was -removed- from the 
original Intel RNG driver, and moved to userspace.


> Your changes are correct, ioctl(RNDADDENTROPY) could even use it instead
> of direct
> add_entropy_words()/credit_entropy_store(), but without external entropy
> contributors
> it will not be applied by maintainers.

No changes are needed, as the system is currently functional without 
these changes.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1764 bytes --]

On Thu, 2005-03-24 at 15:56 -0500, Jeff Garzik wrote:

> > Idea to validate entropy data is good in general, 
> > but it should be implemented in a way allowing external both in-kernel
> > and userspace
> > processes to contribute data.
> > So for in-kernel use we need such a mechanism, and userspace gkernel
> > daemon
> > should use it(as the latest "step") too.
> 
> See the earlier discussion, when data validation was -removed- from the 
> original Intel RNG driver, and moved to userspace.
> 

I'm not arguing against userspace validation, but if data produced
_is_ cryptographically strong, why revalidate it again?

I definitely prefer such mechanism to be implemented, and if you want,
it
can be turned by default off, and can be turned on using new ioctl() 
over /dev/random.

> > Your changes are correct, ioctl(RNDADDENTROPY) could even use it instead
> > of direct
> > add_entropy_words()/credit_entropy_store(), but without external entropy
> > contributors
> > it will not be applied by maintainers.
> 
> No changes are needed, as the system is currently functional without 
> these changes.

And how HIFN driver can contribute entropy?
It needs to create /dev/hifn_random, and rngd should be patched too?
And even using any existing crypto framework why add 2 kernel/user
copying, if we _want_ fast RNG and _know_ that it is valid?

You may say, that hardware can be broken and thus produces 
wrong data, but if user want, it can turn it on or off.

What about new ioctl() that will enable/disable entropy contribution
from kernelspace without validating it? I can create a patch on
top of David's.

> 	Jeff
> 
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> On Thu, 2005-03-24 at 15:56 -0500, Jeff Garzik wrote:
>>See the earlier discussion, when data validation was -removed- from the 
>>original Intel RNG driver, and moved to userspace.
> 
> I'm not arguing against userspace validation, but if data produced
> _is_ cryptographically strong, why revalidate it again?

You cannot prove this without validating the data in software.

Otherwise, you are not handling the hardware-fault case.

It is foolish to presume that hardware always works correctly.  It is 
-very- foolish to presume this, in cryptography.


> And how HIFN driver can contribute entropy?

Use the current chrdev->rngd method.


> You may say, that hardware can be broken and thus produces 
> wrong data, but if user want, it can turn it on or off.

The user cannot know the data is bad unless it is constantly being 
validated.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 976 bytes --]

On Thu, 2005-03-24 at 23:48 -0500, Jeff Garzik wrote:

> > And how HIFN driver can contribute entropy?
> 
> Use the current chrdev->rngd method.

Why HIFN must be chardev?

> > You may say, that hardware can be broken and thus produces 
> > wrong data, but if user want, it can turn it on or off.
> 
> The user cannot know the data is bad unless it is constantly being 
> validated.

The user can not use HW crypto processors, since he does not
know if HW is broken or not, and thus must validate each crypto
operation, i.e. reencrypt data in SW.

Not the point.

Validation can be performed in other HW 
(like Xilinx which routes HW requests to the real devices),
or in driver (if it is not FIPS validation).

So I still insist on creating ability to contribute entropy directly,
without userspace validation.
It will be turned off by default.

> 	Jeff

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> So I still insist on creating ability to contribute entropy directly,
> without userspace validation.
> It will be turned off by default.

If its disabled by default, then you and 2-3 other people will use this 
feature.  Not enough justification for a kernel API at that point.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 693 bytes --]

On Fri, 2005-03-25 at 00:58 -0500, Jeff Garzik wrote:
> Evgeniy Polyakov wrote:
> > So I still insist on creating ability to contribute entropy directly,
> > without userspace validation.
> > It will be turned off by default.
> 
> If its disabled by default, then you and 2-3 other people will use this 
> feature.  Not enough justification for a kernel API at that point.

It is only because there are only couple of HW crypto devices
in the tree, with one crypto framework inclusion there will be
at least redouble.
Let's return to this discussion after it.

Thank you.

> 	Jeff
> 
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Fri, Mar 25, 2005 at 09:16:01AM +0300, Evgeniy Polyakov wrote:
> On Fri, 2005-03-25 at 00:58 -0500, Jeff Garzik wrote:
>
> > If its disabled by default, then you and 2-3 other people will use this 
> > feature.  Not enough justification for a kernel API at that point.
> 
> It is only because there are only couple of HW crypto devices
> in the tree, with one crypto framework inclusion there will be
> at least redouble.

You missed the point.  This has nothing to do with the crypto API.
Jeff is saying that if this is disabled by default, then only a few
users will enable it and therefore use this API.

Since we can't afford to enable it by default as hardware RNG may
fail which can lead to catastrophic consequences, there is no point
for this API at all.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1608 bytes --]

On Fri, 2005-03-25 at 17:13 +1100, Herbert Xu wrote:
> On Fri, Mar 25, 2005 at 09:16:01AM +0300, Evgeniy Polyakov wrote:
> > On Fri, 2005-03-25 at 00:58 -0500, Jeff Garzik wrote:
> >
> > > If its disabled by default, then you and 2-3 other people will use this 
> > > feature.  Not enough justification for a kernel API at that point.
> > 
> > It is only because there are only couple of HW crypto devices
> > in the tree, with one crypto framework inclusion there will be
> > at least redouble.
> 
> You missed the point.  This has nothing to do with the crypto API.
> Jeff is saying that if this is disabled by default, then only a few
> users will enable it and therefore use this API.
> 
> Since we can't afford to enable it by default as hardware RNG may
> fail which can lead to catastrophic consequences, there is no point
> for this API at all.

Currently implemented in-tree drivers(hw_random.c, do not have spec
about 
VIA) do not perform any kind of validation, drivers created for
OCF/acrypto
have HW validated RNG.
Such hardware is used mostly in embedded world where SW crypto
processing
is too expensive, so users of such HW likely want to trust to 
theirs hardware and likely will turn in on.
That would be even be a good idea to have two way of turning it on - 
kernel config option and ioctl() one - to allow embedded systems
with too limited userspace not change it's applications.
Of course with big fat warning about possible dramatical consequences.

> Cheers,
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Fri, Mar 25, 2005 at 09:34:19AM +0300, Evgeniy Polyakov wrote:
>
> Such hardware is used mostly in embedded world where SW crypto
> processing
> is too expensive, so users of such HW likely want to trust to 
> theirs hardware and likely will turn in on.

That's fine.  All you need for these embedded users is a user-space
daemon that feeds data from the hardware directly into /dev/random.
No matter how small your system is, I'm sure you can spare a few
hundred bytes for such a thing.

In fact most of these systems will have some sort of a general-purpose
daemon that sits around which can perform such a task.

System calls on Linux are fast enough that there is really no
advantage in doing this in the kernel.

But if you're really desparate, write a kernel module that does this
in a kernel thread.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1593 bytes --]

On Fri, 2005-03-25 at 17:33 +1100, Herbert Xu wrote:
> On Fri, Mar 25, 2005 at 09:34:19AM +0300, Evgeniy Polyakov wrote:
> >
> > Such hardware is used mostly in embedded world where SW crypto
> > processing
> > is too expensive, so users of such HW likely want to trust to 
> > theirs hardware and likely will turn in on.
> 
> That's fine.  All you need for these embedded users is a user-space
> daemon that feeds data from the hardware directly into /dev/random.
> No matter how small your system is, I'm sure you can spare a few
> hundred bytes for such a thing.
> 
> In fact most of these systems will have some sort of a general-purpose
> daemon that sits around which can perform such a task.
> 
> System calls on Linux are fast enough that there is really no
> advantage in doing this in the kernel.
> 
> But if you're really desparate, write a kernel module that does this
> in a kernel thread.

It is not only about userspace/kernelspace system calls and data
copying,
but about whole revalidation process, which can and is quite expensive,
due to system calls, copying and validating itself,
I even think that using userspace rng daemon is completely useless for 
crypto HW devices - it is faster to obtain entropy from interrupts, 
than revalidating it in that way.
And what about initial bootup? When system needs to create randoom
IP/dhcp/any ids? What about small router?
There are too many cases where userspace validation is just making
things worse.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Fri, Mar 25, 2005 at 09:59:18AM +0300, Evgeniy Polyakov wrote:
> 
> It is not only about userspace/kernelspace system calls and data
> copying,
> but about whole revalidation process, which can and is quite expensive,
> due to system calls, copying and validating itself,

What I meant is if you don't need the revalidation then don't do it.
That's the advantage of having it in user-space, *you* get to decide,
not us.

> And what about initial bootup? When system needs to create randoom
> IP/dhcp/any ids? What about small router?

Let's not reinvent the wheel, this is exactly what initramfs is for.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1368 bytes --]

On Fri, 2005-03-25 at 17:56 +1100, Herbert Xu wrote:
> On Fri, Mar 25, 2005 at 09:59:18AM +0300, Evgeniy Polyakov wrote:
> > 
> > It is not only about userspace/kernelspace system calls and data
> > copying,
> > but about whole revalidation process, which can and is quite expensive,
> > due to system calls, copying and validating itself,
> 
> What I meant is if you don't need the revalidation then don't do it.
> That's the advantage of having it in user-space, *you* get to decide,
> not us.

One can not add entropy data directly to the pool from kernelspace now.
But now noone may do it, since all presented data is not validated.
So when there will be validated HW RNG they still need to pass
it's data through userspace validation daemon
(which btw makes tens to hundreds operations per bit according to FIPS).

> > And what about initial bootup? When system needs to create randoom
> > IP/dhcp/any ids? What about small router?
> 
> Let's not reinvent the wheel, this is exactly what initramfs is for.

It is not panacea and even not always working solution.

If user turn that feature on - he is on his own.
Noone will complain on Linux if NIC is broken and produces wrong
checksum
and HW checksum offloading is enabled using ethtools.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Evgeniy Polyakov wrote:
> Noone will complain on Linux if NIC is broken and produces wrong
> checksum
> and HW checksum offloading is enabled using ethtools.


Actually, that is a problem and people have definitely complained about 
it in the past.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 678 bytes --]

On Fri, 2005-03-25 at 02:19 -0500, Jeff Garzik wrote:
> Evgeniy Polyakov wrote:
> > Noone will complain on Linux if NIC is broken and produces wrong
> > checksum
> > and HW checksum offloading is enabled using ethtools.
> 
> 
> Actually, that is a problem and people have definitely complained about 
> it in the past.

And what they were recommended to do? :)
I believe not changing drivers and stack, but only disable it using
ethtool.

And people of course should be able to turn kernlspace <-> kernelspace
RNG dataflow off if they fill it is insecure.

> 	Jeff
> 
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Fri, Mar 25, 2005 at 10:19:55AM +0300, Evgeniy Polyakov wrote:
> 
> Noone will complain on Linux if NIC is broken and produces wrong
> checksum
> and HW checksum offloading is enabled using ethtools.

This is completely different.  The worst that can happen with checksum
offloading is that the packet is dropped.  That's something people deal
with on a daily basis since the Internet as a whole does not guarantee
the delivery of packets.

On the other hand, /dev/random is something that has always promised
to deliver random numbers that are totally unpredictable.  People out
there *depend* on this.

If that assumption is violated the result could be catastrophic.

That's why it's OK to have hardware RNG spit out unverified numbers
in /dev/hw_random, but it's absolutely unaccpetable for the same
numbers to add entropy to /dev/random without verification.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1803 bytes --]

On Fri, 2005-03-25 at 18:25 +1100, Herbert Xu wrote:
> On Fri, Mar 25, 2005 at 10:19:55AM +0300, Evgeniy Polyakov wrote:
> > 
> > Noone will complain on Linux if NIC is broken and produces wrong
> > checksum
> > and HW checksum offloading is enabled using ethtools.
> 
> This is completely different.  The worst that can happen with checksum
> offloading is that the packet is dropped.  That's something people deal
> with on a daily basis since the Internet as a whole does not guarantee
> the delivery of packets.

It will just completely stop network dataflow.
It is of course not as catastrophic as removing strong random numbers 
from system.
But nevertheless - write cahce in disks may corrupt data on power-down,
but people do not turn it off, crypto HW can be broken and does not 
encrypt dataflow, but people want it, broken NIC can corrupt data with 
various sg/offload combinations, but it can be enabled.

It is a feature, that _may_ broke thing badly.
But if all is ok - it is extremly usefull.

And as I said there may be other [HW/driver] validating techniques, 
not only userspace daemon.

> On the other hand, /dev/random is something that has always promised
> to deliver random numbers that are totally unpredictable.  People out
> there *depend* on this.
> 
> If that assumption is violated the result could be catastrophic.
> 
> That's why it's OK to have hardware RNG spit out unverified numbers
> in /dev/hw_random, but it's absolutely unaccpetable for the same
> numbers to add entropy to /dev/random without verification.

Userspace daemon can read data from /dev/random and validate it
in background, if it fells it is broken - turn feature off.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

On Fri, Mar 25, 2005 at 04:50:16PM -0600, Kim Phillips wrote:
> I did some tests and found that the udelay(200) call in hw_random.c is 
> not good for extreme RNG consumption.  Whether or not such extremes 
> occur in real life, on the mpc8541, /dev/hwrandom is an order of 
> magnitude slower than /dev/random, and two orders of magnitude slower 
> than /dev/urandom.  The hardware RNG is capable of exceeding software 
> /dev/random speeds plus it would alleviate the core to do other, more 
> useful things (that's being realistic).

Consider what an RNG does:  spews garbage.

In practical applications, you -do not- want to dedicate the machine to 
spewing garbage.  The vast majority of users would prefer to use their
machines for real stuff.  Thus, "extreme RNG consumption" is largely
irrelevant to sane usage.

That said, I cannot remember if the udelay() is hardcoding a policy
decision (bad), or required for the hardware.

In any case, it is the wrong solution to simply "turn on the tap" and
let the RNG spew data.  There needs to be a limiting factor... typically
rngd should figure out when /dev/random needs more entropy, or simply
delay a little bit between entropy collection/stuffing runs.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Fri, Mar 25, 2005 at 06:43:49PM -0500, Jeff Garzik wrote:
> 
> In any case, it is the wrong solution to simply "turn on the tap" and
> let the RNG spew data.  There needs to be a limiting factor... typically
> rngd should figure out when /dev/random needs more entropy, or simply
> delay a little bit between entropy collection/stuffing runs.

Completely agreed.  Having it in rngd also allows the scheduler to
do its job.

When applications need entropy from /dev/random and they can't get it,
they'll simply block which allows rngd to run to refill the tank.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

On Sat, 26 Mar 2005 10:47:45 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> On Fri, Mar 25, 2005 at 06:43:49PM -0500, Jeff Garzik wrote:
> > 
> > In any case, it is the wrong solution to simply "turn on the tap" and
> > let the RNG spew data.  There needs to be a limiting factor... typically
> > rngd should figure out when /dev/random needs more entropy, or simply
> > delay a little bit between entropy collection/stuffing runs.
> 
> Completely agreed.  Having it in rngd also allows the scheduler to
> do its job.

It looks like we all misunderstand each other - 
why do you think that if there will be kernel <-> kernel
RNG dataflow, then system will continuously spent all
it's time to produce that data?
_Ability_ existence does not mean that only it must be used.
Userspace daemon should be able to turn it on or off, 
but it is too expensive to allow it to be not only dataflow
controller, but the only random numbers dataflow initiator.

I can create following patch on top of rngd - 
it will read from /dev/random, if read succeds too fast
(or even better just to check pool counts), then rngd
will turn HW RNG assist off and examine received data
to check if it is valid.
Later it can be turned on again.

> When applications need entropy from /dev/random and they can't get it,
> they'll simply block which allows rngd to run to refill the tank.

Such a blocking will be definitely a sign to turn 
HW RNG assist on.

> -- 
> Visit Openswan at http://www.openswan.org/
> Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

	Evgeniy Polyakov

Only failure makes us experts. -- Theo de Raadt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Sat, Mar 26, 2005 at 03:47:33AM +0300, Evgeniy Polyakov wrote:
> 
> It looks like we all misunderstand each other - 
> why do you think that if there will be kernel <-> kernel
> RNG dataflow, then system will continuously spent all
> it's time to produce that data?

It doesn't matter whether it's like that or not.

The point is if you do it in the kernel then either you'll have very
coarse controls over the rate of data coming out of the hardware RNG,
e.g., only on/off, or you'll have to put more code in to set the rate 
appropriately.

Either way it's a loss compared to doing it in user-space.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

On Sat, 26 Mar 2005 11:36:02 +1100
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> On Sat, Mar 26, 2005 at 03:47:33AM +0300, Evgeniy Polyakov wrote:
> > 
> > It looks like we all misunderstand each other - 
> > why do you think that if there will be kernel <-> kernel
> > RNG dataflow, then system will continuously spent all
> > it's time to produce that data?
> 
> It doesn't matter whether it's like that or not.
> 
> The point is if you do it in the kernel then either you'll have very
> coarse controls over the rate of data coming out of the hardware RNG,
> e.g., only on/off, or you'll have to put more code in to set the rate 
> appropriately.

It is not the problem absolutely - just sleep if pool is full.
It will limit usage but this is better than nothing.
 
> Either way it's a loss compared to doing it in user-space.
>
>
> -- 
> Visit Openswan at http://www.openswan.org/
> Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt


	Evgeniy Polyakov

Only failure makes us experts. -- Theo de Raadt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jean-Luc Cooke]

On Fri, Mar 25, 2005 at 06:43:49PM -0500, Jeff Garzik wrote:
> 
> Consider what an RNG does:  spews garbage.
> 
> In practical applications, you -do not- want to dedicate the machine to 
> spewing garbage.  The vast majority of users would prefer to use their
> machines for real stuff.  Thus, "extreme RNG consumption" is largely
> irrelevant to sane usage.

I have clients who run online Casinos.  So spewing lots of reliable garbage
is a good thing.  That's why they chose Fortuna.  Bad random data input is
not a factor as long as there is enough trustwothy random data coming in.

JLC

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Mon, Mar 28, 2005 at 08:45:10AM -0500, Jean-Luc Cooke wrote:
> 
> I have clients who run online Casinos.  So spewing lots of reliable garbage
> is a good thing.  That's why they chose Fortuna.  Bad random data input is
> not a factor as long as there is enough trustwothy random data coming in.

I don't think the Casino operators will be very happy when their supposed
hardware RNGs degenerate into software RNGs because it's feeding all zeros
into /dev/random and nobody noticed...
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Pavel Machek]

Hi!

On Pá 25-03-05 18:25:31, Herbert Xu wrote:
> On Fri, Mar 25, 2005 at 10:19:55AM +0300, Evgeniy Polyakov wrote:
> > 
> > Noone will complain on Linux if NIC is broken and produces wrong
> > checksum
> > and HW checksum offloading is enabled using ethtools.
> 
> This is completely different.  The worst that can happen with checksum
> offloading is that the packet is dropped.  That's something people deal
> with on a daily basis since the Internet as a whole does not guarantee
> the delivery of packets.
> 
> On the other hand, /dev/random is something that has always promised
> to deliver random numbers that are totally unpredictable.  People out
> there *depend* on this.
> 
> If that assumption is violated the result could be catastrophic.

Yes, and we had huge security hole where it sometimes gave same random
data to two different processes on smp, and noone noticed for 10
years.... /dev/random is not as critical as you paint it.

								Pavel
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Pavel Machek]

On Pá 25-03-05 17:13:11, Herbert Xu wrote:
> On Fri, Mar 25, 2005 at 09:16:01AM +0300, Evgeniy Polyakov wrote:
> > On Fri, 2005-03-25 at 00:58 -0500, Jeff Garzik wrote:
> >
> > > If its disabled by default, then you and 2-3 other people will use this 
> > > feature.  Not enough justification for a kernel API at that point.
> > 
> > It is only because there are only couple of HW crypto devices
> > in the tree, with one crypto framework inclusion there will be
> > at least redouble.
> 
> You missed the point.  This has nothing to do with the crypto API.
> Jeff is saying that if this is disabled by default, then only a few
> users will enable it and therefore use this API.
> 
> Since we can't afford to enable it by default as hardware RNG may
> fail which can lead to catastrophic consequences, there is no point
> for this API at all.

What catastrophic consequences? Noone is likely to even *notice*, and
it does not help practical attack at all. Unless hardware RNGs are
*very* flakey (like, more flakey than harddrives), this is not a problem.

I can assure you that failing hdd will have more catastrophic
consequences.
								Pavel
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Tue, Mar 29, 2005 at 12:21:04PM +0200, Pavel Machek wrote:
> 
> What catastrophic consequences? Noone is likely to even *notice*, and
> it does not help practical attack at all. Unless hardware RNGs are
> *very* flakey (like, more flakey than harddrives), this is not a problem.

The reason some people use hardware RNGs in the first place is because
they don't trust the software RNGs.  When the hardware RNG fails but
continues to send data to /dev/random, /dev/random essentially degenerates
into a software RNG.  Now granted /dev/random is a pretty good software
RNG, however, for some purposes it just isn't good enough.

Otherwise we can just do away with it and always use /dev/urandom.

Someone else raised the example of Casinos using hardware RNGs.  Some
of them are doing this to comply with government regulation.  In that
case, using data from the software RNG when the hardware has failed
would be violating the law.

> I can assure you that failing hdd will have more catastrophic
> consequences.

That's we have things like RAID and backups.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Pavel Machek]

Hi!

> > What catastrophic consequences? Noone is likely to even *notice*, and
> > it does not help practical attack at all. Unless hardware RNGs are
> > *very* flakey (like, more flakey than harddrives), this is not a problem.
> 
> The reason some people use hardware RNGs in the first place is because
> they don't trust the software RNGs.  When the hardware RNG fails but
> continues to send data to /dev/random, /dev/random essentially degenerates
> into a software RNG.  Now granted /dev/random is a pretty good software
> RNG, however, for some purposes it just isn't good enough.

It seems to me that people wanting this level of assurance should do
their own FIPS (or whatever) tests.

Interrupts are not totally unpredictable, either, yet noone runs FIPS
tests on them. I'd say that hardware generator is still better than
interrupt timing. If someone really wants casino-level of randomness,
they should do it all in userspace, probably off interrupt entropy
sources, and do their own FIPS testing.

> Otherwise we can just do away with it and always use /dev/urandom.
> 
> Someone else raised the example of Casinos using hardware RNGs.  Some
> of them are doing this to comply with government regulation.  In that
> case, using data from the software RNG when the hardware has failed
> would be violating the law.

Well, you are still using hardware RNG, but failed one. I do not see
how you can break law with that... given that hardware RNG had proper
certification in the first place.
								Pavel
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Tue, Mar 29, 2005 at 12:38:01PM +0200, Pavel Machek wrote:
> 
> It seems to me that people wanting this level of assurance should do
> their own FIPS (or whatever) tests.

That's exactly what the current scheme of driver + rngd allows you
to do.  For those that require high assurance, they can let rngd
do the checks.  Otherwise they can disable the checks and just let
rngd feed data from /dev/hw_random into /dev/random.

It's not just about the quality checks.  It's also about deciding the
rate at which data should be fed into /dev/random.

Feeding too much means that you might be wasting system resources
(CPU/PCI bus/etc.).  Feeding too little means that /dev/random users
may block unnecessarily.

Doing the feeding in a process means that you can feed exactly the
right amount.  You feed only when the /dev/random's pool is depleted
and you feed exactly the amount of data that is needed to replenish
the pool.

> Interrupts are not totally unpredictable, either, yet noone runs FIPS

I haven't looked at this but if that's the case we might want to
look at lowering the entropy count for that.

> > Someone else raised the example of Casinos using hardware RNGs.  Some
> > of them are doing this to comply with government regulation.  In that
> > case, using data from the software RNG when the hardware has failed
> > would be violating the law.
> 
> Well, you are still using hardware RNG, but failed one. I do not see
> how you can break law with that... given that hardware RNG had proper
> certification in the first place.

Actually in the scheme proposed in this thread the hardware RNG could
be feeding a stream of zeros into /dev/random which means that the
/dev/random user will be using a software RNG.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1216 bytes --]

On Tue, 2005-03-29 at 20:30 +1000, Herbert Xu wrote:
> On Tue, Mar 29, 2005 at 12:21:04PM +0200, Pavel Machek wrote:
> > 
> > What catastrophic consequences? Noone is likely to even *notice*, and
> > it does not help practical attack at all. Unless hardware RNGs are
> > *very* flakey (like, more flakey than harddrives), this is not a problem.
> 
> The reason some people use hardware RNGs in the first place is because
> they don't trust the software RNGs.  When the hardware RNG fails but
> continues to send data to /dev/random, /dev/random essentially degenerates
> into a software RNG.  Now granted /dev/random is a pretty good software
> RNG, however, for some purposes it just isn't good enough.

I think the most people use hardware accelerated devices to
speed up theirs calculations - embedded world is the best example - 
applications that are written to use /dev/random
will work just too slow, so hardware vendors
place HW assistant chips to unload that very cpu-intencive work
from main CPU.
Without ability speed this up in kernel, we completely [ok, almost] 
loose all RNG advantages.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Tue, Mar 29, 2005 at 02:50:28PM +0400, Evgeniy Polyakov wrote:
>
> Without ability speed this up in kernel, we completely [ok, almost] 
> loose all RNG advantages.

Well if you can demonstrate that you're getting a higher rate of
throughput from your RNG by doing this in kernel space vs. doing
it in user space please let me know.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1490 bytes --]

On Tue, 2005-03-29 at 20:46 +1000, Herbert Xu wrote:
> On Tue, Mar 29, 2005 at 02:50:28PM +0400, Evgeniy Polyakov wrote:
> >
> > Without ability speed this up in kernel, we completely [ok, almost] 
> > loose all RNG advantages.
> 
> Well if you can demonstrate that you're getting a higher rate of
> throughput from your RNG by doing this in kernel space vs. doing
> it in user space please let me know.

Quote from VIA RNG crypto analysis:

"Bitrate. The RNG generates output at significantly
higher rates than most PC-based randomness resources.
Raw bits are produced at rates of 30 to 50 Mbits/sec,
and whitened bits were observed at rates of 4 to 9
Mbits/sec. Variations in output rates depend on the
RNG configuration and the oscillator rates. PRNGs
seeded with the Nehemiah RNG should be able to
easily sustain output in excess of 2 Mbits of entropy per
second, which should eliminate blocked PRNG reads in
virtually all applications."


While raw bits reading from hw_random on the fastest 
VIA boards can exceed 55mbits per second 
[above quite was taken from VIA C3 Nehemiah analysis], 
it is not evaluated in rngd and is not written 
back to the /dev/random.

David provided his patch exactly because of
"Adding this can dramatically improve the performance of 
/dev/random on small embedded systems which do not 
generate much entropy."
and it works.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Tue, Mar 29, 2005 at 03:42:05PM +0400, Evgeniy Polyakov wrote:
> On Tue, 2005-03-29 at 20:46 +1000, Herbert Xu wrote:

> > Well if you can demonstrate that you're getting a higher rate of
> > throughput from your RNG by doing this in kernel space vs. doing
> > it in user space please let me know.
> 
> While raw bits reading from hw_random on the fastest 
> VIA boards can exceed 55mbits per second 
> [above quite was taken from VIA C3 Nehemiah analysis], 
> it is not evaluated in rngd and is not written 
> back to the /dev/random.

Well when you get 55mb/s from /dev/random please get back to me.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 863 bytes --]

On Tue, 2005-03-29 at 21:39 +1000, Herbert Xu wrote:
> On Tue, Mar 29, 2005 at 03:42:05PM +0400, Evgeniy Polyakov wrote:
> > On Tue, 2005-03-29 at 20:46 +1000, Herbert Xu wrote:
> 
> > > Well if you can demonstrate that you're getting a higher rate of
> > > throughput from your RNG by doing this in kernel space vs. doing
> > > it in user space please let me know.
> > 
> > While raw bits reading from hw_random on the fastest 
> > VIA boards can exceed 55mbits per second 
> > [above quite was taken from VIA C3 Nehemiah analysis], 
> > it is not evaluated in rngd and is not written 
> > back to the /dev/random.
> 
> Well when you get 55mb/s from /dev/random please get back to me.

I cant, noone writes 55mbit into it, but HW RNG drivers could. :)

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Pavel Machek]

Hi!


> > > > Well if you can demonstrate that you're getting a higher rate of
> > > > throughput from your RNG by doing this in kernel space vs. doing
> > > > it in user space please let me know.
> > > 
> > > While raw bits reading from hw_random on the fastest 
> > > VIA boards can exceed 55mbits per second 
> > > [above quite was taken from VIA C3 Nehemiah analysis], 
> > > it is not evaluated in rngd and is not written 
> > > back to the /dev/random.
> > 
> > Well when you get 55mb/s from /dev/random please get back to me.
> 
> I cant, noone writes 55mbit into it, but HW RNG drivers could. :)

Exactly, on via machines, it might be good idea to hook /dev/random
directly to hardware random generator... that should give you
55mbit/sec.
								Pavel
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Tue, Mar 29, 2005 at 04:15:17PM +0400, Evgeniy Polyakov wrote:
> > > On Tue, 2005-03-29 at 20:46 +1000, Herbert Xu wrote:
> > 
> > > > Well if you can demonstrate that you're getting a higher rate of
> > > > throughput from your RNG by doing this in kernel space vs. doing
> > > > it in user space please let me know.
>
> > Well when you get 55mb/s from /dev/random please get back to me.
> 
> I cant, noone writes 55mbit into it, but HW RNG drivers could. :)

Are you intending to feed that into /dev/random at 55mb/s?

If not then how is this an argument against doing it in userspace
through rngd?
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1216 bytes --]

On Tue, 2005-03-29 at 22:43 +1000, Herbert Xu wrote:
> On Tue, Mar 29, 2005 at 04:15:17PM +0400, Evgeniy Polyakov wrote:
> > > > On Tue, 2005-03-29 at 20:46 +1000, Herbert Xu wrote:
> > > 
> > > > > Well if you can demonstrate that you're getting a higher rate of
> > > > > throughput from your RNG by doing this in kernel space vs. doing
> > > > > it in user space please let me know.
> >
> > > Well when you get 55mb/s from /dev/random please get back to me.
> > 
> > I cant, noone writes 55mbit into it, but HW RNG drivers could. :)
> 
> Are you intending to feed that into /dev/random at 55mb/s?
>
> If not then how is this an argument against doing it in userspace
> through rngd?

Yes.
Untill pool is filled and then sleep there.
When someone wants to draw from the pool - awake and fill it again.

I clearly see your point here and I agree that it must be
default method for entropy producing, but if there are 
possibility to speed that up, such techniques should be 
allowed to be used.

It is really faster to fill pool from the kernelspace
without copying/validating it in userspace.

-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 1433 bytes --]

On Tue, 2005-03-29 at 17:11 +0400, Evgeniy Polyakov wrote:
> On Tue, 2005-03-29 at 22:43 +1000, Herbert Xu wrote:
> > On Tue, Mar 29, 2005 at 04:15:17PM +0400, Evgeniy Polyakov wrote:
> > > > > On Tue, 2005-03-29 at 20:46 +1000, Herbert Xu wrote:
> > > > 
> > > > > > Well if you can demonstrate that you're getting a higher rate of
> > > > > > throughput from your RNG by doing this in kernel space vs. doing
> > > > > > it in user space please let me know.
> > >
> > > > Well when you get 55mb/s from /dev/random please get back to me.
> > > 
> > > I cant, noone writes 55mbit into it, but HW RNG drivers could. :)
> > 
> > Are you intending to feed that into /dev/random at 55mb/s?
> >
> > If not then how is this an argument against doing it in userspace
> > through rngd?
> 
> Yes.
> Untill pool is filled and then sleep there.
> When someone wants to draw from the pool - awake and fill it again.
> 
> I clearly see your point here and I agree that it must be

I mean userspace validating and load balancing must be
default method for entropy producing.

> default method for entropy producing, but if there are 
> possibility to speed that up, such techniques should be 
> allowed to be used.
> 
> It is really faster to fill pool from the kernelspace
> without copying/validating it in userspace.
> 
-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jean-Luc Cooke]

On Tue, Mar 29, 2005 at 09:39:21PM +1000, Herbert Xu wrote:
> Well when you get 55mb/s from /dev/random please get back to me.

I will add you to my list for notification of Fortuna Patch to /dev/random
(/dev/urandom)

JLC

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Andrew James Wade]

On March 29, 2005 05:50 am, Evgeniy Polyakov wrote:
> I think the most people use hardware accelerated devices to
> speed up theirs calculations - embedded world is the best example - 
> applications that are written to use /dev/random
> will work just too slow, so hardware vendors
> place HW assistant chips to unload that very cpu-intencive work
> from main CPU.
> Without ability speed this up in kernel, we completely [ok, almost] 
> loose all RNG advantages.

The reason for hardware random number generators is that computers
are pretty deterministic machines and random number sources tend to be
few, far between, very low bitrate, and of uncertain randomness. So much
so that without a user (a decent entropy source), a computer might take
minutes to collect a few hundred bits of entropy.[1] The advantage of a
hardware RNG is that it is random in the first place, high bitrates are
just icing on the cake.

[1] Vague recollection from a hardware RNG article.

The thing is few applications need truly random data, and even fewer
need much. (Maybe casinos). Even cryptographic applications don't need
much; they can be served by a carefully crafted pseudo-random number
generator, so long as that generator is seeded with enough entropy. (512
bits of entropy is plenty). And while a crypographically strong
pseudo-random number generator is pretty cpu-intensive, I would be
quite surprised to learn that a hardware RNG is faster.

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Bill Davidsen]

Herbert Xu wrote:

> You missed the point.  This has nothing to do with the crypto API.
> Jeff is saying that if this is disabled by default, then only a few
> users will enable it and therefore use this API.
> 
> Since we can't afford to enable it by default as hardware RNG may
> fail which can lead to catastrophic consequences, there is no point
> for this API at all.

Wait a minute, if it fails the system drops back to software, which is 
not as good in a pedantic analysis, but perhaps falls a good bit short 
of "catastrophic consequences" as most people would characterize that 
phrase. And more to the point, now that many CPUs and chipsets are the 
RNG of choice, what is the actual probability of a failure of the RNG 
leaving a functional system (that's a real question seeking response 
from someone who has some actual data).

It would be desirable for the kernel to detect a failure and do 
something appropriate, but I have to feel that if an RNG is in the CPU 
or chipset, it would serve users better to use it. By default. People 
who need quality entropy would be better served by a hardware source, 
and people who don't (or fail to realize they do) would not be hurt by 
use of better numbers.

I'm not sure you would get people to agree what should be done if a 
hardware RNG fails, other than make the failure information available to 
user space.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Kyle Moffett]

On Mar 29, 2005, at 17:02, Bill Davidsen wrote:
> Wait a minute, if it fails the system drops back to software,

Does it?  It would seem that if it fails and begins returning
all zeroes, then the seed function would (depending on the
implementation) be called like this:

add_random_bytes("\0\0\0\0".... , 4096);
add_random_bytes("\0\0\0\0".... , 4096);
[...]

Or:

add_random_bytes("\0\0\0\0".... , 4096);
add_random_bytes(soft_random()  , 64);
add_random_bytes("\0\0\0\0".... , 4096);
add_random_bytes(soft_random()  , 64);
[...]

In either case, it's very bad, and will likely return cause
some _very_ predictable data to be emitted.

> I'm not sure you would get people to agree what should be
> done if a hardware RNG fails, other than make the failure
> information available to user space.

How do you know if it fails?  You know when your disk fails
and begins giving bad data because the filesystem detects
that the data is invalid, but how do you tell when your
random number generator starts giving bad data? AFAIK, the
only way to do that is to continuously monitor the random
data produced and _immediately_ stop the data flow when
you start getting bad data.  That should only be done from
a userspace rngd-type daemon.

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a18 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$
L++++(+++) E W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+
PGP+++ t+(+++) 5 X R? tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$ r  
!y?(-)
------END GEEK CODE BLOCK------

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Bill Davidsen wrote:
> Herbert Xu wrote:
> 
>> You missed the point.  This has nothing to do with the crypto API.
>> Jeff is saying that if this is disabled by default, then only a few
>> users will enable it and therefore use this API.
>>
>> Since we can't afford to enable it by default as hardware RNG may
>> fail which can lead to catastrophic consequences, there is no point
>> for this API at all.
> 
> 
> Wait a minute, if it fails the system drops back to software, which is 
> not as good in a pedantic analysis, but perhaps falls a good bit short 
> of "catastrophic consequences" as most people would characterize that 
> phrase. And more to the point, now that many CPUs and chipsets are the 
> RNG of choice, what is the actual probability of a failure of the RNG 
> leaving a functional system (that's a real question seeking response 
> from someone who has some actual data).

As I've said, in the past the Intel RNGs in particular -have- failed, 
but the rest of the system keeps on working just fine.

It probably depends on the hardware implementation; I think the Intel 
RNG was based on a thermal diode, or somesuch.

In the cases where an RNG has failed in the past, the system has worked 
as expected:  rngd stopped feeding data into the entropy pool.

If the VIA RNG (on-CPU) fails, that's probably indicative of a larger 
problem, though.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Bill Davidsen]

Jeff Garzik wrote:
> Bill Davidsen wrote:
> 
>> Herbert Xu wrote:
>>
>>> You missed the point.  This has nothing to do with the crypto API.
>>> Jeff is saying that if this is disabled by default, then only a few
>>> users will enable it and therefore use this API.
>>>
>>> Since we can't afford to enable it by default as hardware RNG may
>>> fail which can lead to catastrophic consequences, there is no point
>>> for this API at all.
>>
>>
>>
>> Wait a minute, if it fails the system drops back to software, which is 
>> not as good in a pedantic analysis, but perhaps falls a good bit short 
>> of "catastrophic consequences" as most people would characterize that 
>> phrase. And more to the point, now that many CPUs and chipsets are the 
>> RNG of choice, what is the actual probability of a failure of the RNG 
>> leaving a functional system (that's a real question seeking response 
>> from someone who has some actual data).
> 
> 
> As I've said, in the past the Intel RNGs in particular -have- failed, 
> but the rest of the system keeps on working just fine.

People have been hit by meteors, too. I wasn't questioning that it was 
possible in practice, or even that it did happen, but trying to get some 
quantitative values for failure rates. I guess that wasn't clear, I know 
entropy is scarse on embedded systems, I don't know what the magnitude 
of the RNG failure is, so I'm coming from the "router in a cigar box" 
point of view.
> 
> It probably depends on the hardware implementation; I think the Intel 
> RNG was based on a thermal diode, or somesuch.
> 
> In the cases where an RNG has failed in the past, the system has worked 
> as expected:  rngd stopped feeding data into the entropy pool.

If the hardware RNG always fails to all zeros it should be possible to 
detect that it failed with the need for userspace daemons.  While true 
random bits might legitimately have 10k zeros in a row, I will bet that 
if it happens the device isn't working.

I'm assuming that the hardware RNG is only read when a read on 
/dev/random occurs and there isn't enough entropy available to satisfy 
the read. I realize that may not be true, I just haven't had time to go 
study the code.
> 
> If the VIA RNG (on-CPU) fails, that's probably indicative of a larger 
> problem, though.


-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Bill Davidsen wrote:
> If the hardware RNG always fails to all zeros it should be possible to 
> detect that it failed with the need for userspace daemons.  While true 
> random bits might legitimately have 10k zeros in a row, I will bet that 
> if it happens the device isn't working.


Or all 1's (more likely), or all 0x55's, or...

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Paul Jackson]

Jeff wrote:
> Or all 1's (more likely), or all 0x55's, or...

Stray thought - to follow up stray thought:

    Hmmm ... run some numbers through a good compression program,
    and complain if they compress much.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@engr.sgi.com> 1.650.933.1373, 1.925.600.0401

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Pavel Machek]

Hi!


> >>See the earlier discussion, when data validation was -removed- from the 
> >>original Intel RNG driver, and moved to userspace.
> >
> >I'm not arguing against userspace validation, but if data produced
> >_is_ cryptographically strong, why revalidate it again?
> 
> You cannot prove this without validating the data in software.
> 
> Otherwise, you are not handling the hardware-fault case.
> 
> It is foolish to presume that hardware always works correctly.  It is 
> -very- foolish to presume this, in cryptography.

We trust hardware, anyway. Like your disk *could* accidentaly turn on
setuid bit on /bin/bash, and we do not insist on userspace
disk-validator.

I do not think paranoia about random generators is neccessary. If
vendor provides you with random generator, it should be ok to just use
it. [Did anyone see failing hw random generator, *at all*?] I can
provide you with plenty of failing hdds....
								Pavel
-- 
People were complaining that M$ turns users into beta-testers...
...jr ghea gurz vagb qrirybcref, naq gurl frrz gb yvxr vg gung jnl!

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Tue, Mar 29, 2005 at 12:18:16PM +0200, Pavel Machek wrote:
>
> I do not think paranoia about random generators is neccessary. If
> vendor provides you with random generator, it should be ok to just use
> it. [Did anyone see failing hw random generator, *at all*?] I can
> provide you with plenty of failing hdds....

We've been through this before.  It's not a question of trusting the
hardware to be /dev/hw_random, it's a question of trusting it to be
/dev/random.

/dev/random is special in that we've gone to extraordinary lengths to
make sure that it contains the amount of entropy that we say it does.

So while it'd be perfectly OK to feed unverified data through
/dev/hw_random, the same cannot be done for /dev/random.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Martin Mares]

Hello!

> We trust hardware, anyway. Like your disk *could* accidentaly turn on
> setuid bit on /bin/bash, and we do not insist on userspace
> disk-validator.

But there is a very important difference: the most likely (both in theory
and practice) failure of a disk is clearly visible, while failures of HW RNG's
are likely to be silent (the data are just less random than they should be).

				Have a nice fortnight
-- 
Martin `MJ' Mares   <mj@ucw.cz>   http://atrey.karlin.mff.cuni.cz/~mj/
Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
Top ten reasons to procrastinate: 1.

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

David McCullough wrote:
> Jivin Jeff Garzik lays it down ...
> 
>>Evgeniy Polyakov wrote:
>>
>>>On Thu, 2005-03-24 at 14:27 +1000, David McCullough wrote:
>>>
>>>
>>>>Hi all,
>>>>
>>>>Here is a small patch for 2.6.11 that adds a routine:
>>>>
>>>>	add_true_randomness(__u32 *buf, int nwords);
>>>>
>>>>so that true random number generator device drivers can add a entropy
>>>>to the system.  Drivers that use this can be found in the latest release
>>>>of ocf-linux,  an asynchronous crypto implementation for linux based on
>>>>the *BSD Cryptographic Framework.
>>>>
>>>>	http://ocf-linux.sourceforge.net/
>>>>
>>>>Adding this can dramatically improve the performance of /dev/random on
>>>>small embedded systems which do not generate much entropy.
>>>
>>>
>>>People will not apply any kind of such changes.
>>>Both OCF and acrypto already handle all RNG cases - no need for any kind
>>>of userspace daemon or entropy (re)injection mechanism.
>>>Anyone who want to use HW randomness may use OCF/acrypto mechanism.
>>>For example here is patch to enable acrypto support for hw_random.c
>>>It is very simple and support only upto 4 bytes request, of course it
>>>is 
>>>not interested for anyone, but it is only 2-minutes example:
>>
>>If you want to add entropy to the kernel entropy pool from hardware RNG, 
>>you should use the userland daemon, which detects non-random (broken) 
>>hardware and provides throttling, so that RNG data collection does not 
>>consume 100% CPU.
>>
>>If you want to use the hardware RNG directly, it's simple:  just open 
>>/dev/hw_random.
>>
>>Hardware RNG should not go kernel->kernel without adding FIPS tests and 
>>such.
> 
> 
> For reference,  the RNG on the Safenet I am using this with is
> FIPS140 certified.  I believe the HIFN part  is also but I place the doc that
> says so.


FIPS certification is not relevant to the discussion.

I am talking about active testing of -all data- that is produced by an 
RNG, before making use of it.  Please read the source code of rngd.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jean-Luc Cooke]

On Thu, Mar 24, 2005 at 07:48:18AM -0500, Jeff Garzik wrote:
> If you want to add entropy to the kernel entropy pool from hardware RNG, 
> you should use the userland daemon, which detects non-random (broken) 
> hardware and provides throttling, so that RNG data collection does not 
> consume 100% CPU.
> 
> If you want to use the hardware RNG directly, it's simple:  just open 
> /dev/hw_random.
> 
> Hardware RNG should not go kernel->kernel without adding FIPS tests and 
> such.

If your RNG were properly written, it shouldn't matter if the data you're
pumping into /dev/random passed muster or not.  If you're tracking entropy
count, then that's a different story of course.

I've been commissioned to write Fortuna RNG for Linux and weddings, houses and
cars not withstanding, I should I it ready soon to be given to LKML for
digestion.

JLC

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Jeff Garzik]

Jean-Luc Cooke wrote:
> On Thu, Mar 24, 2005 at 07:48:18AM -0500, Jeff Garzik wrote:
> 
>>If you want to add entropy to the kernel entropy pool from hardware RNG, 
>>you should use the userland daemon, which detects non-random (broken) 
>>hardware and provides throttling, so that RNG data collection does not 
>>consume 100% CPU.
>>
>>If you want to use the hardware RNG directly, it's simple:  just open 
>>/dev/hw_random.
>>
>>Hardware RNG should not go kernel->kernel without adding FIPS tests and 
>>such.
> 
> 
> If your RNG were properly written, it shouldn't matter if the data you're
> pumping into /dev/random passed muster or not.  If you're tracking entropy
> count, then that's a different story of course.

It's rather lame to add data, without also crediting entropy.

Further, it wastes many CPU cycles in many places, if you are doing 
nothing but pumping bad data (all 1's, for example) into /dev/random.


> I've been commissioned to write Fortuna RNG for Linux and weddings, houses and
> cars not withstanding, I should I it ready soon to be given to LKML for
> digestion.

Sounds great.

	Jeff

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Herbert Xu]

On Thu, Mar 24, 2005 at 09:25:40AM -0500, Jean-Luc Cooke wrote:
> 
> If your RNG were properly written, it shouldn't matter if the data you're
> pumping into /dev/random passed muster or not.  If you're tracking entropy
> count, then that's a different story of course.

We're talking about hardware RNGs here so we need to take hardware faults
into account.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] API for true Random Number Generators to add entropy (2.6.11)

[Evgeniy Polyakov]

[-- Attachment #1: Type: text/plain, Size: 8304 bytes --]

On Thu, 2005-03-24 at 14:59 +0300, Evgeniy Polyakov wrote:

> For example here is patch to enable acrypto support for hw_random.c
> It is very simple and support only upto 4 bytes request, of course it
> is not interested for anyone, but it is only 2-minutes example:

Full port.

--- ./drivers/char/hw_random.c.orig     2005-03-24 13:36:05.000000000 +0300
+++ ./drivers/char/hw_random.c  2005-03-25 08:46:03.841601032 +0300
@@ -34,6 +34,10 @@
 #include <linux/smp_lock.h>
 #include <linux/mm.h>
 #include <linux/delay.h>
+#include <linux/acrypto.h>
+#include <linux/crypto_def.h>
+#include <linux/crypto_stat.h>
+#include <linux/highmem.h>

 #ifdef __i386__
 #include <asm/msr.h>
@@ -73,6 +77,8 @@
 #endif

 #define RNG_MISCDEV_MINOR              183 /* official */
+
+static DEFINE_SPINLOCK(rng_lock);

 static int rng_dev_open (struct inode *inode, struct file *filp);
 static ssize_t rng_dev_read (struct file *filp, char __user *buf, size_t size,
@@ -482,7 +488,6 @@
 static ssize_t rng_dev_read (struct file *filp, char __user *buf, size_t size,
                                loff_t * offp)
 {
-       static DEFINE_SPINLOCK(rng_lock);
        unsigned int have_data;
        u32 data = 0;
        ssize_t ret = 0;
@@ -526,7 +531,163 @@
        return ret;
 }

+#ifdef CONFIG_ACRYPTO
+static struct crypto_device *hwr_cdev;
+static struct crypto_capability hwr_caps[] =   {
+       {CRYPTO_OP_RNG, 0, 0, 100},
+};
+static int hwr_pid, hwr_need_exit;
+static struct completion hwr_thread_exited;
+static DECLARE_WAIT_QUEUE_HEAD(hwr_wait);
+
+
+static void hwr_data_ready(struct crypto_device *dev)
+{
+       wake_up(&hwr_wait);
+}
+
+static int hwr_process(void *data)
+{
+       struct crypto_device *dev = data;
+       struct crypto_session *s, *n;
+       u32 rng_data = 0;
+       unsigned int have_data, size;
+       int i;
+       u8 *ptr;
+
+       daemonize("%s", dev->name);
+       allow_signal(SIGTERM);
+
+       while (!hwr_need_exit) {
+               interruptible_sleep_on_timeout(&hwr_wait, 10);
+
+               list_for_each_entry_safe(s, n, &dev->session_list, dev_queue_entry) {
+                       if (!session_completed(s) && !session_is_processed(s)) {
+                               start_process_session(s);
+
+                               if (s->data.sg_src_num != s->data.sg_dst_num) {
+                                       dprintk("%s: session %llu [%llu]: different src/dst sg numbers: %d %d.\n",
+                                                       dev->name, s->ci.id, s->ci.dev_id,
+                                                       s->data.sg_src_num, s->data.sg_dst_num);
+                                       broke_session(s);
+                                       goto out_complete_session;
+                               }
+
+                               for (i=0; i<s->data.sg_src_num; ++i) {
+                                       if (s->data.sg_dst[i].length != s->data.sg_src[i].length) {
+                                               dprintk("%s: session %llu [%llu]: sg %d different src/dst lengths: %u %u.\n",
+                                                               dev->name, s->ci.id, s->ci.dev_id, i,
+                                                               s->data.sg_src[i].length, s->data.sg_dst[i].length);
+                                               if (s->data.sg_dst[i].length)
+                                                       s->data.sg_src[i].length = s->data.sg_dst[i].length;
+                                               else
+                                                       s->data.sg_dst[i].length = s->data.sg_src[i].length;
+
+                                       }
+
+                                       size = s->data.sg_dst[i].length;
+
+                                       while (size) {
+                                               spin_lock(&rng_lock);
+                                               have_data = 0;
+                                               if (rng_ops->data_present()) {
+                                                       rng_data = rng_ops->data_read();
+                                                       have_data = rng_ops->n_bytes;
+                                               }
+                                               spin_unlock (&rng_lock);
+
+                                               ptr = kmap_atomic(s->data.sg_dst[i].page, KM_USER0) + s->data.sg_dst[i].offset +
+                                                       s->data.sg_dst[i].length - size;
+
+                                               while (size && have_data) {
+                                                       *ptr = rng_data & 0xff;
+                                                       size--;
+                                                       have_data--;
+                                                       rng_data >>= 8;
+                                               }
+                                               kunmap_atomic(ptr, KM_USER0);
+
+                                               if (size)
+                                                       msleep_interruptible(1);
+                                       }
+                               }
+
+                               crypto_stat_complete_inc(s);
+
+out_complete_session:
+                               crypto_session_dequeue_route(s);
+                               complete_session(s);
+                               stop_process_session(s);
+                       }
+               }
+       }
+
+       complete_and_exit(&hwr_thread_exited, 0);
+}
+
+static int hwr_acrypto_init(struct rng_operations *ops)
+{
+       int err;
+
+       hwr_cdev = kmalloc(sizeof(*hwr_cdev), GFP_KERNEL);
+       if (!hwr_cdev) {
+               printk(KERN_ERR "Failed to allocate new crypto_device structure.\n");
+               return -ENOMEM;
+       }
+
+       memset(hwr_cdev, 0, sizeof(*hwr_cdev));
+
+       hwr_cdev->cap           = hwr_caps;
+       hwr_cdev->cap_number    = sizeof(hwr_caps)/sizeof(hwr_caps[0]);
+       hwr_cdev->priv          = ops;
+       hwr_cdev->data_ready    = &hwr_data_ready;
+       snprintf(hwr_cdev->name, sizeof(hwr_cdev->name), "%s", "hwr");
+
+       init_completion(&hwr_thread_exited);
+       hwr_pid = kernel_thread(hwr_process, hwr_cdev, CLONE_FS | CLONE_FILES);
+       if (hwr_pid < 0) {
+               err = hwr_pid;
+               goto err_out_free_cdev;
+       }

+       err = crypto_device_add(hwr_cdev);
+       if (err)
+               goto err_out_remove_thread;
+
+       printk(KERN_INFO "%s acrypto support is turned on.\n", hwr_cdev->name);
+
+err_out_remove_thread:
+       hwr_need_exit = 1;
+       kill_proc(hwr_pid, SIGTERM, 0);
+       wait_for_completion(&hwr_thread_exited);
+err_out_free_cdev:
+       kfree(hwr_cdev);
+       hwr_cdev = NULL;
+       return err;
+}
+
+static void hwr_acrypto_fini(void)
+{
+       crypto_device_remove(hwr_cdev);
+       printk(KERN_INFO "%s acrypto support is turned off.\n", hwr_cdev->name);
+
+       hwr_need_exit = 1;
+       kill_proc(hwr_pid, SIGTERM, 0);
+       wait_for_completion(&hwr_thread_exited);
+
+       kfree(hwr_cdev);
+       hwr_cdev = NULL;
+}
+#else
+static int hwr_acrypto_init(struct rng_operations *ops)
+{
+       return 0;
+}
+
+static void hwr_acrypto_fini(void)
+{
+}
+#endif

 /*
  * rng_init_one - look for and attempt to init a single RNG
@@ -549,9 +710,15 @@
                goto err_out_cleanup_hw;
        }

+       rc = hwr_acrypto_init(rng_ops);
+       if (rc)
+               goto err_out_misc_unregister;
+
        DPRINTK ("EXIT, returning 0\n");
        return 0;

+err_out_misc_unregister:
+       misc_deregister(&rng_miscdev);
 err_out_cleanup_hw:
        rng_ops->cleanup();
 err_out:
@@ -617,6 +784,8 @@
 {
        DPRINTK ("ENTER\n");

+       hwr_acrypto_fini();
+
        misc_deregister (&rng_miscdev);

        if (rng_ops->cleanup)


-- 
        Evgeniy Polyakov

Crash is better than data corruption -- Arthur Grabowski

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]