Re: drivers/char/random.c needs a (new) maintainer

[Sandy Harris]

Pavel Machek  wrote:

> To play devil's advocate, does RNG subsystem need to evolve? Its task
> is to get random numbers. Does it fail at the task?
>
> Problem is, random subsystem is hard to verify, and big rewrite is
> likely to cause security problems...

Parts of the problem, though, are dead easy in many of today's
environments.

Many CPUs, e,g. Intel, have an instruction that gives random
numbers. Some systems have another hardware RNG. Some
can add one using a USB device or Denker's Turbid
(https://www.av8n.com/turbid/). Many Linux instances run on
VMs so they have an emulated HWRNG using the host's
/dev/random.

None of those is necessarily 100% trustworthy, though the
published analysis for Turbid & for (one version of) the Intel
device seem adequate to me. However, if you use any
of them to scribble over the entire 4k-bit input pool and/or
a 512-bit Salsa context during initialisation, then it seems
almost certain you'll get enough entropy to block attacks.

They are all dirt cheap so doing that, and using them
again later for incremental squirts of randomness, looks
reasonable.

In many cases you could go further. Consider a system
with an intel CPU and another HWRNG, perhaps a VM.
Get 128 bits from each source & combine them using
the 128-bit finite field multiplication from the GSM
authentication. Still cheap & it cannot be worse than
the better of the two sources. If both sources are
anywhere near reasonable, this should produce 128
bits of very high grade random material, cheaply.

I am not suggesting any of these should be used for
output, but using them for initialisation whenever
possible looks obvious to me.

Re: Looking for an open-source thesis idea

[Sandy Harris]

Eric Curtin  wrote:

> Hope I'm not bothering you. I'm looking for a masters thesis idea, ...

Here's a report claiming 70% of security bugs involve memory errors.
https://www.zdnet.com/article/chrome-70-of-all-security-bugs-are-memory-safety-issues/
Build a tool to find or fix those?

Another report I saw on Slashdot recently said lots of web vulnerabilities
were due to problems in widely used open source libraries.

Re: [kernel-hardening] Re: [PATCH v4] security/keys: rewrite all of big_key crypto

[Sandy Harris]

On Tue, Sep 19, 2017 at 9:39 AM, Theodore Ts'o  wrote:

> On Mon, Sep 18, 2017 at 01:24:18PM +0200, Jason A. Donenfeld wrote:
>> Good luck with getting approval... While Ted and I have our
>> differences like any two kernel developers, I really tend agree with
>> him in his attitude about this FIPS silliness. ...
>
> Let me add one more reason why FIPS compliance for the kernel is just
> ***stupid***.  The way FIPS compliance works, you have to pay hundreds
> of thousands of dollars to a FIPS certification lab to certify a
> specific binary, complete with the exact build environment (compiler,
> binutils, etc.) used to build that kernel binary.
>
> The moment you need to make a change --- say, to fix a critical
> zero-day security bug --- this breaks the FIPS certification, ...
>
> You might say that FIPS certification != FIPS compliance.  Sure, but
> the only silly people who care about FIPS compliance also need FIPS
> certification, for the US Goverment signoff.

I do not think it is just the US that matters here. If I understand
Stefan correctly, one of his concerns is German (or EU?) gov't
standards that are somehow related. I'm very hazy on details.

I emphatically agree with Ted on some points here. Making
FIPS certification a goal for kernel development would be
really dumb. Having multiple RNGs available & compile-time
options to select among them also looks silly to me; we just
need one good one.

On the other hand, I do not see why the driver should not
use a FIPS-compliant PRNG where it can. This would make
things easier for anyone who does seek certification. One
of the big distro vendors? A gov't department or contractor
that wants to use Linux? A corporation's sys admin or
security reviewer? Stefan?

I cannot see much downside to this. Is the current PRNG
more efficient? More easily maintained? Is it still the case
that random(4) must use only hashes, not ciphers, to
avoid restrictions under export laws?

Re: [kernel-hardening] Re: [PATCH v4] security/keys: rewrite all of big_key crypto

[Sandy Harris]

On Tue, Sep 19, 2017 at 9:39 AM, Theodore Ts'o  wrote:

> On Mon, Sep 18, 2017 at 01:24:18PM +0200, Jason A. Donenfeld wrote:
>> Good luck with getting approval... While Ted and I have our
>> differences like any two kernel developers, I really tend agree with
>> him in his attitude about this FIPS silliness. ...
>
> Let me add one more reason why FIPS compliance for the kernel is just
> ***stupid***.  The way FIPS compliance works, you have to pay hundreds
> of thousands of dollars to a FIPS certification lab to certify a
> specific binary, complete with the exact build environment (compiler,
> binutils, etc.) used to build that kernel binary.
>
> The moment you need to make a change --- say, to fix a critical
> zero-day security bug --- this breaks the FIPS certification, ...
>
> You might say that FIPS certification != FIPS compliance.  Sure, but
> the only silly people who care about FIPS compliance also need FIPS
> certification, for the US Goverment signoff.

I do not think it is just the US that matters here. If I understand
Stefan correctly, one of his concerns is German (or EU?) gov't
standards that are somehow related. I'm very hazy on details.

I emphatically agree with Ted on some points here. Making
FIPS certification a goal for kernel development would be
really dumb. Having multiple RNGs available & compile-time
options to select among them also looks silly to me; we just
need one good one.

On the other hand, I do not see why the driver should not
use a FIPS-compliant PRNG where it can. This would make
things easier for anyone who does seek certification. One
of the big distro vendors? A gov't department or contractor
that wants to use Linux? A corporation's sys admin or
security reviewer? Stefan?

I cannot see much downside to this. Is the current PRNG
more efficient? More easily maintained? Is it still the case
that random(4) must use only hashes, not ciphers, to
avoid restrictions under export laws?

Re: [RFC PATCH v12 3/4] Linux Random Number Generator

[Sandy Harris]

Sandy Harris <sandyinch...@gmail.com> wrote:

> The biggest problem with random(4) is that you cannot generate good
> output without a good seed & just after boot, ...
>
> The only really good solution I know of is to find a way to provide a
> chunk of randomness early in the boot process. John Denker has a good
> discussion of doing this by modifying the kernel image & Ted talks of
> doing it via the boot loader. ...

Would it be enough to have a kernel module that does more-or-less what
the current shell scripts do, but earlier in the boot process? Throw
the stored data into the random(4) driver at module init time & update
it periodically later. This would not help much for first boot on a
new system, unless its store could be updated during install; Denker's
point that you need each system provisioned differently is important.
However it looks like it would be enough on other boots.

It also looks like it might be easier to implement & test. In
particular it is an isolated do-one-thing-well tool; the programmer
only needs to worry about his or her module, not several different
boot loaders or the procedures that distros have for CD images or
manufacturers for device setup.

Re: [RFC PATCH v12 3/4] Linux Random Number Generator

[Sandy Harris]

Sandy Harris  wrote:

> The biggest problem with random(4) is that you cannot generate good
> output without a good seed & just after boot, ...
>
> The only really good solution I know of is to find a way to provide a
> chunk of randomness early in the boot process. John Denker has a good
> discussion of doing this by modifying the kernel image & Ted talks of
> doing it via the boot loader. ...

Would it be enough to have a kernel module that does more-or-less what
the current shell scripts do, but earlier in the boot process? Throw
the stored data into the random(4) driver at module init time & update
it periodically later. This would not help much for first boot on a
new system, unless its store could be updated during install; Denker's
point that you need each system provisioned differently is important.
However it looks like it would be enough on other boots.

It also looks like it might be easier to implement & test. In
particular it is an isolated do-one-thing-well tool; the programmer
only needs to worry about his or her module, not several different
boot loaders or the procedures that distros have for CD images or
manufacturers for device setup.

Re: [RFC PATCH v12 3/4] Linux Random Number Generator

[Sandy Harris]

On Tue, Jul 18, 2017 at 5:08 PM, Theodore Ts'o  wrote:

> I've been trying to take the best features and suggestions from your
> proposal and integrating them into /dev/random already.

A good approach.

> Things that I've chosen not take is basically because I disbelieve
> that the Jitter RNG is valid. ...

The biggest problem with random(4) is that you cannot generate good
output without a good seed & just after boot, especially first boot on
a new system, you may not have enough entropy. A user space process
cannot do it soon enough and all the in-kernel solutions (unless you
have a hardware RNG) pose difficulties.

The only really good solution I know of is to find a way to provide a
chunk of randomness early in the boot process. John Denker has a good
discussion of doing this by modifying the kernel image & Ted talks of
doing it via the boot loader. Neither looks remarkably easy. Other
approaches like making the kernel read a seed file or passing a
parameter on the kernel command line have been suggested but, if I
recall right, rejected.

As I see it, the questions about Jitter, or any other in-kernel
generator based on timing, are whether it is good enough to be useful
until we have one of the above solutions or useful as a
defense-in-depth trick after we have one. I'd say yes to both.

There's been a lot of analysis. Stephan has a detailed rationale & a
lot of test data in his papers & the Havege papers also discuss
getting entropy from timer operations. I'd say the best paper is
McGuire et al:
https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf

There is enough there to convince me that grabbing some (256?) bits
from such a generator early in the initialization is worthwhile.

> So I have been trying to do the evolution thing already.
> ...

> I'm obviously biased, but I don't see I see the Raison d'Etre for
> merging LRNG into the kernel.

Nor I.

Re: [RFC PATCH v12 3/4] Linux Random Number Generator

[Sandy Harris]

On Tue, Jul 18, 2017 at 5:08 PM, Theodore Ts'o  wrote:

> I've been trying to take the best features and suggestions from your
> proposal and integrating them into /dev/random already.

A good approach.

> Things that I've chosen not take is basically because I disbelieve
> that the Jitter RNG is valid. ...

The biggest problem with random(4) is that you cannot generate good
output without a good seed & just after boot, especially first boot on
a new system, you may not have enough entropy. A user space process
cannot do it soon enough and all the in-kernel solutions (unless you
have a hardware RNG) pose difficulties.

The only really good solution I know of is to find a way to provide a
chunk of randomness early in the boot process. John Denker has a good
discussion of doing this by modifying the kernel image & Ted talks of
doing it via the boot loader. Neither looks remarkably easy. Other
approaches like making the kernel read a seed file or passing a
parameter on the kernel command line have been suggested but, if I
recall right, rejected.

As I see it, the questions about Jitter, or any other in-kernel
generator based on timing, are whether it is good enough to be useful
until we have one of the above solutions or useful as a
defense-in-depth trick after we have one. I'd say yes to both.

There's been a lot of analysis. Stephan has a detailed rationale & a
lot of test data in his papers & the Havege papers also discuss
getting entropy from timer operations. I'd say the best paper is
McGuire et al:
https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf

There is enough there to convince me that grabbing some (256?) bits
from such a generator early in the initialization is worthwhile.

> So I have been trying to do the evolution thing already.
> ...

> I'm obviously biased, but I don't see I see the Raison d'Etre for
> merging LRNG into the kernel.

Nor I.

Re: [kernel-hardening] Re: [PATCH] random: silence compiler warnings and fix race

[Sandy Harris]

On Tue, Jun 20, 2017 at 5:49 AM, Jeffrey Walton  wrote:
> On Tue, Jun 20, 2017 at 5:36 AM, Theodore Ts'o  wrote:
>> On Tue, Jun 20, 2017 at 10:53:35AM +0200, Jason A. Donenfeld wrote:

>>> > Suppressing all messages for all configurations cast a wider net than
>>> > necessary. Configurations that could potentially be detected and fixed
>>> > likely will go unnoticed. If the problem is not brought to light, then
>>> > it won't be fixed.

> Are there compelling reasons a single dmesg warning cannot be provided?
>
> A single message avoids spamming the logs. It also informs the system
> owner of the problem. An individual or organization can then take
> action based on their risk posture. Finally, it avoids the kernel
> making policy decisions for a user or organization.

I'd say the best solution is to have no configuration option
specifically for these messages. Always give some, but let
DEBUG_KERNEL control how many.

If DEBUG_KERNEL is not set, emit exactly one message & ignore any
other errors of this type. On some systems, that message may have to
be ignored, on some it might start an incremental process where one
problem gets fixed only to have another crop up & on some it might
prompt the admin to explore further by compiling with DEBUG_KERNEL.

If DEBUG_KERNEL is set, emit a message for every error of this type.

Re: [kernel-hardening] Re: [PATCH] random: silence compiler warnings and fix race

[Sandy Harris]

On Tue, Jun 20, 2017 at 5:49 AM, Jeffrey Walton  wrote:
> On Tue, Jun 20, 2017 at 5:36 AM, Theodore Ts'o  wrote:
>> On Tue, Jun 20, 2017 at 10:53:35AM +0200, Jason A. Donenfeld wrote:

>>> > Suppressing all messages for all configurations cast a wider net than
>>> > necessary. Configurations that could potentially be detected and fixed
>>> > likely will go unnoticed. If the problem is not brought to light, then
>>> > it won't be fixed.

> Are there compelling reasons a single dmesg warning cannot be provided?
>
> A single message avoids spamming the logs. It also informs the system
> owner of the problem. An individual or organization can then take
> action based on their risk posture. Finally, it avoids the kernel
> making policy decisions for a user or organization.

I'd say the best solution is to have no configuration option
specifically for these messages. Always give some, but let
DEBUG_KERNEL control how many.

If DEBUG_KERNEL is not set, emit exactly one message & ignore any
other errors of this type. On some systems, that message may have to
be ignored, on some it might start an incremental process where one
problem gets fixed only to have another crop up & on some it might
prompt the admin to explore further by compiling with DEBUG_KERNEL.

If DEBUG_KERNEL is set, emit a message for every error of this type.

Re: get_random_bytes returns bad randomness before seeding is complete

[Sandy Harris]

Stephan's driver, the HAVEGE system & several others purport to
extract entropy from a series of timer calls. Probably the best
analysis is in the Mcguire et al. paper at
https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf & the
simplest code in my user-space driver at
https://github.com/sandy-harris/maxwell The only kernel-space code I
know of is Stephan's.

If the claim that such calls give entropy is accepted (which I think
it should be) then if we get one bit per call, need 100 or so bits &
space the calls 100 ns apart, loading up a decent chunk of startup
entropy takes about 10,000 ns or 10 microseconds which looks like an
acceptable delay. Can we just do that very early in the boot process?

Of course this will fail on systems with no high-res timer. Are there
still some of those? It might be done in about 1000 times as long on a
system that lacks the realtime library's nanosecond timer but has the
Posix standard microsecond timer, implying a delay time in the
milliseconds. Would that be acceptable in those cases?

Re: get_random_bytes returns bad randomness before seeding is complete

[Sandy Harris]

Stephan's driver, the HAVEGE system & several others purport to
extract entropy from a series of timer calls. Probably the best
analysis is in the Mcguire et al. paper at
https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf & the
simplest code in my user-space driver at
https://github.com/sandy-harris/maxwell The only kernel-space code I
know of is Stephan's.

If the claim that such calls give entropy is accepted (which I think
it should be) then if we get one bit per call, need 100 or so bits &
space the calls 100 ns apart, loading up a decent chunk of startup
entropy takes about 10,000 ns or 10 microseconds which looks like an
acceptable delay. Can we just do that very early in the boot process?

Of course this will fail on systems with no high-res timer. Are there
still some of those? It might be done in about 1000 times as long on a
system that lacks the realtime library's nanosecond timer but has the
Posix standard microsecond timer, implying a delay time in the
milliseconds. Would that be acceptable in those cases?

Re: [kernel-hardening] Re: get_random_bytes returns bad randomness before seeding is complete

[Sandy Harris]

The only sensible & general solution for the initialisation problem
that I have seen is John Denker's.
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

If I read that right, it would require only minor kernel changes &
none to the API Ted & others are worrying about. It would be secure
except against an enemy who can read your kernel image or interfere
with your install process. Assuming permissions are set sensibly, that
means an enemy who already has root & such an enemy has lots of much
easier ways to break things, so we need not worry about that case.

The difficulty is that it would require significant changes to
installation scripts. Still, since it is a general solution to a real
problem, it might be better to implement that rather than work on the
other suggestions in the thread.

Re: [kernel-hardening] Re: get_random_bytes returns bad randomness before seeding is complete

[Sandy Harris]

The only sensible & general solution for the initialisation problem
that I have seen is John Denker's.
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

If I read that right, it would require only minor kernel changes &
none to the API Ted & others are worrying about. It would be secure
except against an enemy who can read your kernel image or interfere
with your install process. Assuming permissions are set sensibly, that
means an enemy who already has root & such an enemy has lots of much
easier ways to break things, so we need not worry about that case.

The difficulty is that it would require significant changes to
installation scripts. Still, since it is a general solution to a real
problem, it might be better to implement that rather than work on the
other suggestions in the thread.

Re: [PATCH] crypto: sun4i-ss: support the Security System PRNG

[Sandy Harris]

Add Ted T'so to cc list. Shouldn't he be included on anything affecting
the random(4) driver?

On Tue, Oct 18, 2016 at 8:34 AM, Corentin Labbe
 wrote:

> From: LABBE Corentin 
>
> The Security System have a PRNG.
> This patch add support for it as an hwrng.

Which is it? A PRNG & a HW RNG are quite different things.
It would, in general, be a fairly serious error to treat a PRNG
as a HWRNG.

If it is just a prng (which it appears to be from a quick look
at your code) then it is not clear it is useful since the
random(4) driver already has two PRNGs. It might be
but I cannot tell.

Re: [PATCH] crypto: sun4i-ss: support the Security System PRNG

[Sandy Harris]

Add Ted T'so to cc list. Shouldn't he be included on anything affecting
the random(4) driver?

On Tue, Oct 18, 2016 at 8:34 AM, Corentin Labbe
 wrote:

> From: LABBE Corentin 
>
> The Security System have a PRNG.
> This patch add support for it as an hwrng.

Which is it? A PRNG & a HW RNG are quite different things.
It would, in general, be a fairly serious error to treat a PRNG
as a HWRNG.

If it is just a prng (which it appears to be from a quick look
at your code) then it is not clear it is useful since the
random(4) driver already has two PRNGs. It might be
but I cannot tell.

Re: [PATCH] poly1305: generic C can be faster on chips with slow unaligned access

[Sandy Harris]

On Wed, Nov 2, 2016 at 4:09 PM, Herbert Xu  wrote:

> On Wed, Nov 02, 2016 at 06:58:10PM +0100, Jason A. Donenfeld wrote:
>> On MIPS chips commonly found in inexpensive routers, this makes a big
>> difference in performance.
>>
>> Signed-off-by: Jason A. Donenfeld 
>
> Can you give some numbers please? What about other architectures
> that your patch impacts?

In general it is not always clear that using whatever hardware crypto
is available is a good idea. Not all such hardware is fast, some CPUs
are, some CPUs have hardware for AES, and even if the hardware is
faster than the CPU, the context switch overheads may exceed the
advantage.

Ideally the patch development or acceptance process would be
testing this, but I think it might be difficult to reach that ideal.

The exception is a hardware RNG; that should always be used unless
it is clearly awful. It cannot do harm, speed is not much of an issue,
and it solves the hardest problem in the random(4) driver, making
sure of correct initialisation before any use.

Re: [PATCH] poly1305: generic C can be faster on chips with slow unaligned access

[Sandy Harris]

On Wed, Nov 2, 2016 at 4:09 PM, Herbert Xu  wrote:

> On Wed, Nov 02, 2016 at 06:58:10PM +0100, Jason A. Donenfeld wrote:
>> On MIPS chips commonly found in inexpensive routers, this makes a big
>> difference in performance.
>>
>> Signed-off-by: Jason A. Donenfeld 
>
> Can you give some numbers please? What about other architectures
> that your patch impacts?

In general it is not always clear that using whatever hardware crypto
is available is a good idea. Not all such hardware is fast, some CPUs
are, some CPUs have hardware for AES, and even if the hardware is
faster than the CPU, the context switch overheads may exceed the
advantage.

Ideally the patch development or acceptance process would be
testing this, but I think it might be difficult to reach that ideal.

The exception is a hardware RNG; that should always be used unless
it is clearly awful. It cannot do harm, speed is not much of an issue,
and it solves the hardest problem in the random(4) driver, making
sure of correct initialisation before any use.

Re: Entropy sources (was: /dev/random - a new approach)

[Sandy Harris]

On Thu, Aug 25, 2016 at 5:30 PM, H. Peter Anvin <h...@zytor.com> wrote:

> The network stack is a good source of entropy, *once it is online*.
> However, the most serious case is while the machine is still booting,
> when the network will not have enabled yet.
>
> -hpa

One possible solution is at:
https://github.com/sandy-harris/maxwell

A small (< 700 lines) daemon that gets entropy from timer imprecision
and variations in time for arithmetic (cache misses, interrupts, etc.)
and pumps it into /dev/random. Make it the first userspace program
started and all should be covered. Directory above includes a PDF doc
with detailed rationale and some discussion of alternate solutions.

Of course if you are dealing with a system-on-a-chip or low-end
embedded CPU & the timer is really inadequate, this will not work
well. Conceivably well enough, but we could not know that without
detailed analysis for each chip in question.

Re: Entropy sources (was: /dev/random - a new approach)

[Sandy Harris]

On Thu, Aug 25, 2016 at 5:30 PM, H. Peter Anvin  wrote:

> The network stack is a good source of entropy, *once it is online*.
> However, the most serious case is while the machine is still booting,
> when the network will not have enabled yet.
>
> -hpa

One possible solution is at:
https://github.com/sandy-harris/maxwell

A small (< 700 lines) daemon that gets entropy from timer imprecision
and variations in time for arithmetic (cache misses, interrupts, etc.)
and pumps it into /dev/random. Make it the first userspace program
started and all should be covered. Directory above includes a PDF doc
with detailed rationale and some discussion of alternate solutions.

Of course if you are dealing with a system-on-a-chip or low-end
embedded CPU & the timer is really inadequate, this will not work
well. Conceivably well enough, but we could not know that without
detailed analysis for each chip in question.

Re: [kernel-hardening] [PATCH v7 0/9] x86/mm: memory area address KASLR

[Sandy Harris]

Jason Cooper  wrote:

> Modern systems that receive a seed from the bootloader via the
> random-seed property (typically from the hw-rng) can mix both sources
> for increased resilience.
>
> Unfortunately, I'm not very familiar with the internals of x86
> bootstrapping.  Could GRUB be scripted to do a similar task?  How would
> the address and size of the seed be passed to the kernel?  command line?

One suggestion is at:
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

Re: [kernel-hardening] [PATCH v7 0/9] x86/mm: memory area address KASLR

[Sandy Harris]

Jason Cooper  wrote:

> Modern systems that receive a seed from the bootloader via the
> random-seed property (typically from the hw-rng) can mix both sources
> for increased resilience.
>
> Unfortunately, I'm not very familiar with the internals of x86
> bootstrapping.  Could GRUB be scripted to do a similar task?  How would
> the address and size of the seed be passed to the kernel?  command line?

One suggestion is at:
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

Re: [PATCH v5 0/7] /dev/random - a new approach

[Sandy Harris]

On Sun, Jun 19, 2016 at 3:36 PM, Pavel Machek  wrote:

>> The following patch set provides a different approach to /dev/random ...
>
> Dunno. It is very similar to existing rng, AFAICT.

I do not think so. A lot of the basic principles are the same of course,
but Stephan is suggesting some real changes. On the other hand, I'm
not sure all of them are good ideas & Ted has already incorporated
some into the driver, so it is debatable how much here is really useful.

> And at the very least, constants in existing RNG could be tuned
> to provide "entropy at the boot time".

No, this is a rather hard problem & just tweaking definitely will
not solve it. Ted's patches, Stephan's, mine, the grsecurity
stuff and the kernel hardening project all have things that
might help, but as far as I can see there is no complete
in-kernel solution yet.

Closest thing I have seen to a solution are Denker's suggestions at:
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

Those, though, require changes to build & installation methods
& it might be hard to get distros & device vendors to do it.

> So IMO this should be re-done as tweaks to existing design, not as
> completely new RNG.

I agree, & I think Stephan has already done some of that.

Re: [PATCH v5 0/7] /dev/random - a new approach

[Sandy Harris]

On Sun, Jun 19, 2016 at 3:36 PM, Pavel Machek  wrote:

>> The following patch set provides a different approach to /dev/random ...
>
> Dunno. It is very similar to existing rng, AFAICT.

I do not think so. A lot of the basic principles are the same of course,
but Stephan is suggesting some real changes. On the other hand, I'm
not sure all of them are good ideas & Ted has already incorporated
some into the driver, so it is debatable how much here is really useful.

> And at the very least, constants in existing RNG could be tuned
> to provide "entropy at the boot time".

No, this is a rather hard problem & just tweaking definitely will
not solve it. Ted's patches, Stephan's, mine, the grsecurity
stuff and the kernel hardening project all have things that
might help, but as far as I can see there is no complete
in-kernel solution yet.

Closest thing I have seen to a solution are Denker's suggestions at:
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

Those, though, require changes to build & installation methods
& it might be hard to get distros & device vendors to do it.

> So IMO this should be re-done as tweaks to existing design, not as
> completely new RNG.

I agree, & I think Stephan has already done some of that.

Re: [PATCH v4 0/5] /dev/random - a new approach

[Sandy Harris]

David Jaša  wrote:

>
> BTW when looking at an old BSI's issue with Linux urandom that Jarod
> Wilson tried to solve with this series:
> https://www.spinics.net/lists/linux-crypto/msg06113.html
> I was thinking:
> 1) wouldn't it help for large urandom consumers if kernel created a DRBG
> instance for each of them? It would likely enhance performance and solve
> BSI's concern of predicting what numbers could other urandom consumers
> obtain at cost of memory footprint
> and then, after reading paper associated with this series:
> 2) did you evaluate use of intermediate DRBG fed by primary generator to
> instantiate per-node DRBG's? It would allow initialization of all
> secondary DRBGs right after primary generator initialization.

Theodore Ts'o, the random maintainer, already has a patch that
seems to deal with this issue. He has posted more than one
version & I'm not sure this is the best or latest, but ...
https://lkml.org/lkml/2016/5/30/22

Re: [PATCH v4 0/5] /dev/random - a new approach

[Sandy Harris]

David Jaša  wrote:

>
> BTW when looking at an old BSI's issue with Linux urandom that Jarod
> Wilson tried to solve with this series:
> https://www.spinics.net/lists/linux-crypto/msg06113.html
> I was thinking:
> 1) wouldn't it help for large urandom consumers if kernel created a DRBG
> instance for each of them? It would likely enhance performance and solve
> BSI's concern of predicting what numbers could other urandom consumers
> obtain at cost of memory footprint
> and then, after reading paper associated with this series:
> 2) did you evaluate use of intermediate DRBG fed by primary generator to
> instantiate per-node DRBG's? It would allow initialization of all
> secondary DRBGs right after primary generator initialization.

Theodore Ts'o, the random maintainer, already has a patch that
seems to deal with this issue. He has posted more than one
version & I'm not sure this is the best or latest, but ...
https://lkml.org/lkml/2016/5/30/22

Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

[Sandy Harris]

On Thu, Apr 28, 2016 at 10:25 PM, Linus Torvalds
<torva...@linux-foundation.org> wrote:

> It's the hashes that _look_ like they might be good hashes, but
> there's not a lot of analysis behind it, that I would worry about. The
> simple prime modulus _should_ be fine, but at the same time I kind of
> suspect we can do better. Especially since it has two multiplications.
>
> Looking around, there's
>
> http://burtleburtle.net/bob/hash/integer.html
>
> and that 32-bit "full avalanche" hash in six shifts looks like it
> could be better. You wouldn't want to inline it, but the point of a
> full avalanche bit mixing _should_ be that you could avoid the whole
> "upper bits" part, and it should work independently of the target set
> size.
>
> So if that hash works better, it would be a pretty good replacement
> option for hash_int().
>
> There is also
>
> https://gist.github.com/badboy/6267743
>
> that has a 64 bit to 32 bit hash function that might be useful for
> "hash_long()".
>
> Most of the people who worry about hashes tend to have strings to
> hash, not just a single word like a pointer, but there's clearly
> people around who have tried to search for good hashes that really
> spread out the bits.
>
> Linus

Here's another possibility, from my GPL code at:
https://github.com/sandy-harris/maxwell

Not very efficient -- two each of 32-bit multiply & modulo
in most cases -- but provably good mixing.

/*
Quasi-Hadamard transform
My own invention

Goal is to mix a 32-bit object
so that each output bit depends
on every input bit

Underlying primitive is IDEA
multiplication which mixes
a pair of 16-bit objects

This is analogous to the
pseudo-Hadamard transform
(PHT) originally from the
SAFER cipher, later in
Twofish and others

Conceptually, a two-way PHT
on a,b is:

x = a + b
y = a + 2b
a = x
b = y

This is reversible; it loses
no information. Each output
word depends on both inputs.

A PHT can be implemented as

a += b
b += a

which is faster and avoids
using intermediate variables

QHT is the same thing using
IDEA multiplication instead
of addition, calculating a*b
and a*b^2 instead of a+b and
a+2b

IDEA multiplication operates
on 16-bit chunks and makes
every output bit depend on
all input bits. Therefore
QHT is close to an ideal
mixer for 32-bit words.
*/

u32 qht(u32 x)
{
u32 a, b ;
a = x >> 16 ;// high 16 bits
b = x & 0x ;// low 16
a = idea(a,b) ;// a *= b
b = idea(a,b) ;// b *= a
return( (a<<16) | b) ;
}

/*
IDEA multiplication
borrowed from the IDEA cipher
*/
#defineMAX (1<<16)
#define MOD (MAX+1)

u32 idea(u32 a, u32 b)
{
u32 x ;
// make sure they are in range
a %= MOD ;
b %= MOD ;
// special cases
if( (a == 0) && (b == 0))
return(1) ;
else if( a == 0)
return(MOD - b) ;
else if( b == 0)
return(MOD - a) ;
// non-special
else{
x = (a*b) % MOD ;
if(x == MAX)
return(0) ;
elsereturn(x) ;
}
}

Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

[Sandy Harris]

On Thu, Apr 28, 2016 at 10:25 PM, Linus Torvalds
 wrote:

> It's the hashes that _look_ like they might be good hashes, but
> there's not a lot of analysis behind it, that I would worry about. The
> simple prime modulus _should_ be fine, but at the same time I kind of
> suspect we can do better. Especially since it has two multiplications.
>
> Looking around, there's
>
> http://burtleburtle.net/bob/hash/integer.html
>
> and that 32-bit "full avalanche" hash in six shifts looks like it
> could be better. You wouldn't want to inline it, but the point of a
> full avalanche bit mixing _should_ be that you could avoid the whole
> "upper bits" part, and it should work independently of the target set
> size.
>
> So if that hash works better, it would be a pretty good replacement
> option for hash_int().
>
> There is also
>
> https://gist.github.com/badboy/6267743
>
> that has a 64 bit to 32 bit hash function that might be useful for
> "hash_long()".
>
> Most of the people who worry about hashes tend to have strings to
> hash, not just a single word like a pointer, but there's clearly
> people around who have tried to search for good hashes that really
> spread out the bits.
>
> Linus

Here's another possibility, from my GPL code at:
https://github.com/sandy-harris/maxwell

Not very efficient -- two each of 32-bit multiply & modulo
in most cases -- but provably good mixing.

/*
Quasi-Hadamard transform
My own invention

Goal is to mix a 32-bit object
so that each output bit depends
on every input bit

Underlying primitive is IDEA
multiplication which mixes
a pair of 16-bit objects

This is analogous to the
pseudo-Hadamard transform
(PHT) originally from the
SAFER cipher, later in
Twofish and others

Conceptually, a two-way PHT
on a,b is:

x = a + b
y = a + 2b
a = x
b = y

This is reversible; it loses
no information. Each output
word depends on both inputs.

A PHT can be implemented as

a += b
b += a

which is faster and avoids
using intermediate variables

QHT is the same thing using
IDEA multiplication instead
of addition, calculating a*b
and a*b^2 instead of a+b and
a+2b

IDEA multiplication operates
on 16-bit chunks and makes
every output bit depend on
all input bits. Therefore
QHT is close to an ideal
mixer for 32-bit words.
*/

u32 qht(u32 x)
{
u32 a, b ;
a = x >> 16 ;// high 16 bits
b = x & 0x ;// low 16
a = idea(a,b) ;// a *= b
b = idea(a,b) ;// b *= a
return( (a<<16) | b) ;
}

/*
IDEA multiplication
borrowed from the IDEA cipher
*/
#defineMAX (1<<16)
#define MOD (MAX+1)

u32 idea(u32 a, u32 b)
{
u32 x ;
// make sure they are in range
a %= MOD ;
b %= MOD ;
// special cases
if( (a == 0) && (b == 0))
return(1) ;
else if( a == 0)
return(MOD - b) ;
else if( b == 0)
return(MOD - a) ;
// non-special
else{
x = (a*b) % MOD ;
if(x == MAX)
return(0) ;
elsereturn(x) ;
}
}

Re: better patch for linux/bitops.h

[Sandy Harris]

On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'o  wrote:

> Instead of arguing over who's "sane" or "insane", can we come up with
> a agreed upon set of tests, and a set of compiler and compiler
> versions ...

I completely fail to see why tests or compiler versions should be
part of the discussion. The C standard says the behaviour in
certain cases is undefined, so a standard-compliant compiler
can generate more-or-less any code there.

As long as any of portability, reliability or security are among our
goals, any code that can give undefined behaviour should be
considered problematic.

> But instead of arguing over what works and doesn't, let's just create
> the the test set and just try it on a wide range of compilers and
> architectures, hmmm?

No. Let's just fix the code so that undefined behaviour cannot occur.

Creating test cases for a fix and trying them on a range of systems
would be useful, perhaps essential, work. Doing tests without a fix
would be a complete waste of time.

Re: better patch for linux/bitops.h

[Sandy Harris]

On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'o  wrote:

> Instead of arguing over who's "sane" or "insane", can we come up with
> a agreed upon set of tests, and a set of compiler and compiler
> versions ...

I completely fail to see why tests or compiler versions should be
part of the discussion. The C standard says the behaviour in
certain cases is undefined, so a standard-compliant compiler
can generate more-or-less any code there.

As long as any of portability, reliability or security are among our
goals, any code that can give undefined behaviour should be
considered problematic.

> But instead of arguing over what works and doesn't, let's just create
> the the test set and just try it on a wide range of compilers and
> architectures, hmmm?

No. Let's just fix the code so that undefined behaviour cannot occur.

Creating test cases for a fix and trying them on a range of systems
would be useful, perhaps essential, work. Doing tests without a fix
would be a complete waste of time.

Re: random(4) changes

[Sandy Harris]

On Mon, Apr 25, 2016 at 12:06 PM, Andi Kleen <a...@firstfloor.org> wrote:

> Sandy Harris <sandyinch...@gmail.com> writes:
>
> There is also the third problem of horrible scalability of /dev/random
> output on larger systems, for which patches are getting ignored.

I did not write that. I think Andi is quoting himself here, not me.

> https://lkml.org/lkml/2016/2/10/716
>
> Ignoring problems does not make them go away.
>
> -Andi
> --
> a...@linux.intel.com -- Speaking for myself only

Re: random(4) changes

[Sandy Harris]

On Mon, Apr 25, 2016 at 12:06 PM, Andi Kleen  wrote:

> Sandy Harris  writes:
>
> There is also the third problem of horrible scalability of /dev/random
> output on larger systems, for which patches are getting ignored.

I did not write that. I think Andi is quoting himself here, not me.

> https://lkml.org/lkml/2016/2/10/716
>
> Ignoring problems does not make them go away.
>
> -Andi
> --
> a...@linux.intel.com -- Speaking for myself only

random(4) changes

[Sandy Harris]

Stephan has recently proposed some extensive changes to this driver,
and I proposed a quite different set earlier. My set can be found at:
https://github.com/sandy-harris

This post tries to find the bits of both proposals that seem clearly
worth doing and entail neither large implementation problems nor large
risk of throwing out any babies with the bathwater.

Unfortunately, nothing here deals with the elephant in the room -- the
distinctly hard problem of making sure the driver is initialised well
enough & early enough. That needs a separate post, probably a separate
thread. I do not find Stepan's solution to this problem plausible and
my stuff does not claim to deal with it, though it includes some
things that might help.

I really like Stephan's idea of simplifying the interrupt handling,
replacing the multiple entropy-gathering calls in the current driver
with one routine called for all interrupts. See section 1.2 of his
doc. That seems to me a much cleaner design, easier both to analyse
and to optimise as a fast interrupt handler. I also find Stephan's
arguments that this will work better on modern  systems -- VMs,
machines with SSDs, etc. -- quite plausible.

Note, though, that I am only talking about the actual interrupt
handling, not the rest of Stephan's input handling code: the parity
calculation and XORing the resulting single bit into the entropy pool.
I'd be happier, at least initially, with a patch that only implemented
a single-source interrupt handler that gave 32 or 64 bits to existing
input-handling code.

Stephan: would you want to provide such a patch?
Ted: would you be inclined to accept it?

I also quite like Stephan's idea of replacing the two output pools
with a NIST-approved DBRG, mainly because this would probably make
getting various certifications easier. I also like the idea of using
crypto lib code for that since it makes both testing & maintenance
easier. This strikes me, though, as a do-when-convenient sort of
cleanup task, not at all urgent unless there are specific
certifications we need soon.

As for my proposals, I of course think they are full of good ideas,
but there's only one I think is really important.

In the current driver -- and I think in Stephan's, though I have not
looked at his code in any detail, only his paper -- heavy use of
/dev/urandom or the kernel get_random_bytes() call can deplete the
entropy available to /dev/random. That can be a serious problem in
some circumstances, but I think I have a fix.

You have an input pool (I) plus a blocking pool (B) & a non-blocking
pool (NB). The problem is what to do when NB must produce a lot of
output but you do not want to deplete I too much. B & NB might be
replaced by DBRGs and the problem would not change.

B must be reseeded before very /dev/random output, NB after some
number of output blocks. I used #define SAFE_OUT 503 but some other
number might be better depending how NB is implemented & how
paranoid/conservative one feels.

B can only produce one full-entropy output, suitable for /dev/random,
per reseed but B and NB are basically the same design so B can also
produce SAFE_OUT reasonably good random numbers per reseed. Use those
to reseed NB.and you reduce the load on I for reseeding NB from
SAFE_OUT (use I every time NB is reseeded) to SAFE_OUT*SAFE_OUT (use I
only to reseed B).

This does need analysis by cryptographers, but at a minimum it is
basically plausible and, even with some fairly small value for
SAFE_OUT, it greatly alleviates the problem.

random(4) changes

[Sandy Harris]

Stephan has recently proposed some extensive changes to this driver,
and I proposed a quite different set earlier. My set can be found at:
https://github.com/sandy-harris

This post tries to find the bits of both proposals that seem clearly
worth doing and entail neither large implementation problems nor large
risk of throwing out any babies with the bathwater.

Unfortunately, nothing here deals with the elephant in the room -- the
distinctly hard problem of making sure the driver is initialised well
enough & early enough. That needs a separate post, probably a separate
thread. I do not find Stepan's solution to this problem plausible and
my stuff does not claim to deal with it, though it includes some
things that might help.

I really like Stephan's idea of simplifying the interrupt handling,
replacing the multiple entropy-gathering calls in the current driver
with one routine called for all interrupts. See section 1.2 of his
doc. That seems to me a much cleaner design, easier both to analyse
and to optimise as a fast interrupt handler. I also find Stephan's
arguments that this will work better on modern  systems -- VMs,
machines with SSDs, etc. -- quite plausible.

Note, though, that I am only talking about the actual interrupt
handling, not the rest of Stephan's input handling code: the parity
calculation and XORing the resulting single bit into the entropy pool.
I'd be happier, at least initially, with a patch that only implemented
a single-source interrupt handler that gave 32 or 64 bits to existing
input-handling code.

Stephan: would you want to provide such a patch?
Ted: would you be inclined to accept it?

I also quite like Stephan's idea of replacing the two output pools
with a NIST-approved DBRG, mainly because this would probably make
getting various certifications easier. I also like the idea of using
crypto lib code for that since it makes both testing & maintenance
easier. This strikes me, though, as a do-when-convenient sort of
cleanup task, not at all urgent unless there are specific
certifications we need soon.

As for my proposals, I of course think they are full of good ideas,
but there's only one I think is really important.

In the current driver -- and I think in Stephan's, though I have not
looked at his code in any detail, only his paper -- heavy use of
/dev/urandom or the kernel get_random_bytes() call can deplete the
entropy available to /dev/random. That can be a serious problem in
some circumstances, but I think I have a fix.

You have an input pool (I) plus a blocking pool (B) & a non-blocking
pool (NB). The problem is what to do when NB must produce a lot of
output but you do not want to deplete I too much. B & NB might be
replaced by DBRGs and the problem would not change.

B must be reseeded before very /dev/random output, NB after some
number of output blocks. I used #define SAFE_OUT 503 but some other
number might be better depending how NB is implemented & how
paranoid/conservative one feels.

B can only produce one full-entropy output, suitable for /dev/random,
per reseed but B and NB are basically the same design so B can also
produce SAFE_OUT reasonably good random numbers per reseed. Use those
to reseed NB.and you reduce the load on I for reseeding NB from
SAFE_OUT (use I every time NB is reseeded) to SAFE_OUT*SAFE_OUT (use I
only to reseed B).

This does need analysis by cryptographers, but at a minimum it is
basically plausible and, even with some fairly small value for
SAFE_OUT, it greatly alleviates the problem.

Re: [RFC][PATCH 0/6] /dev/random - a new approach

[Sandy Harris]

On Thu, Apr 21, 2016 at 10:51 PM, Theodore Ts'o <ty...@mit.edu> wrote:

> I still have a massive problem with the claims that the "Jitter" RNG
> provides any amount of entropy.  Just because you and I might not be
> able to analyze it doesn't mean that somebody else couldn't.  After
> all, DUAL-EC DRNG was very complicated and hard to analyze.  So would
> be something like
>
>AES(NSA_KEY, COUNTER++)
>
> Very hard to analyze indeed.  Shall we run statistical tests?  They'll
> pass with flying colors.
>
> Secure?  Not so much.
>
> - Ted

Jitter, havege and my maxwell(8) all claim to get entropy from
variations in timing of simple calculations, and the docs for
all three give arguments that there really is some entropy
there.

Some of those arguments are quite strong. Mine are in
the PDF at:
https://github.com/sandy-harris/maxwell

I find any of those plausible as an external RNG feeding
random(4), though a hardware RNG or Turbid is preferable.

Re: [RFC][PATCH 0/6] /dev/random - a new approach

[Sandy Harris]

On Thu, Apr 21, 2016 at 10:51 PM, Theodore Ts'o  wrote:

> I still have a massive problem with the claims that the "Jitter" RNG
> provides any amount of entropy.  Just because you and I might not be
> able to analyze it doesn't mean that somebody else couldn't.  After
> all, DUAL-EC DRNG was very complicated and hard to analyze.  So would
> be something like
>
>AES(NSA_KEY, COUNTER++)
>
> Very hard to analyze indeed.  Shall we run statistical tests?  They'll
> pass with flying colors.
>
> Secure?  Not so much.
>
> - Ted

Jitter, havege and my maxwell(8) all claim to get entropy from
variations in timing of simple calculations, and the docs for
all three give arguments that there really is some entropy
there.

Some of those arguments are quite strong. Mine are in
the PDF at:
https://github.com/sandy-harris/maxwell

I find any of those plausible as an external RNG feeding
random(4), though a hardware RNG or Turbid is preferable.

Re: [PATCH 1/7] A couple of generated files

[Sandy Harris]

This set of patches, plus some later ones that simplify the
code and get rid of one major bug are now at:
https://github.com/sandy-harris

Directory for these changes is random.gcm

An out-of-kernel test program for an older version
is in random.test

On Sat, Nov 7, 2015 at 1:50 PM, Sandy Harris <sandyinch...@gmail.com> wrote:

> There are two groups of changes, each controlled by a config
> variable. Default for both is 'n'.
>
> CONFIG_RANDOM_INIT: initialise the pools with data from
> /dev/urandom on the machine that compiles the kernel.
> Comments for the generator program scripts/gen_random.c
> have details.
>
> The main change in random.c is adding conditionals
> to make it use the random data if CONFIG_RANDOM_INIT
> is set. There is also a trivial fix updating a reference to an
> obsoleted in a comment, and I added some sanity-check
> #if tests for odd #define parameter values.
>
> This is a fairly simple change. I do not think it needs a config
> variable; it should just be the default. However I put it under
> config control for testing.
>
> CONFIG_RANDOM_GCM controls a much larger and
> less clearly desirable set of changes. It switches
> compilation between random.c and and a heavily
> modified version random_gcm.c
>
> This uses the hash from AES-GCM instead of SHA-1,
> and that allows a lot of other changes. The main
> design goal was to decouple the two output pools
> so that heavy use of the nonblocking pool cannot
> deplete entropy in the input pool. The nonblocking
> pool usually rekeys from the blocking pool instead.
> random_gcm.c has extensive comments on both
> the rationale for this approach & the details of my
> implementation.
>
> random_gcm.c is not close to being a finished
> product, in particular my code is not yet well
> integrated with existing driver code.
>
> Most of the code was developed and has been
> fairly well tested outside the kernel.
> Test program is at:
> https://github.com/sandy-harris/random.test
>
> I just dropped a large chunk of that code into
> a copy of random.c, made modifications to
> make the style match better & to get it to
> compile in the kernel context, then deleted
> a few chunks of existing driver code and
> replaced them with calls to my stuff.
>
> Proper integration would involve both
> replacing more of the existing code with
> new and moving a few important bits of
> the existing code into some of my functions.
> In particular, my stuff does not yet block
> in the right places.

Re: [PATCH 1/7] A couple of generated files

[Sandy Harris]

This set of patches, plus some later ones that simplify the
code and get rid of one major bug are now at:
https://github.com/sandy-harris

Directory for these changes is random.gcm

An out-of-kernel test program for an older version
is in random.test

On Sat, Nov 7, 2015 at 1:50 PM, Sandy Harris  wrote:

> There are two groups of changes, each controlled by a config
> variable. Default for both is 'n'.
>
> CONFIG_RANDOM_INIT: initialise the pools with data from
> /dev/urandom on the machine that compiles the kernel.
> Comments for the generator program scripts/gen_random.c
> have details.
>
> The main change in random.c is adding conditionals
> to make it use the random data if CONFIG_RANDOM_INIT
> is set. There is also a trivial fix updating a reference to an
> obsoleted in a comment, and I added some sanity-check
> #if tests for odd #define parameter values.
>
> This is a fairly simple change. I do not think it needs a config
> variable; it should just be the default. However I put it under
> config control for testing.
>
> CONFIG_RANDOM_GCM controls a much larger and
> less clearly desirable set of changes. It switches
> compilation between random.c and and a heavily
> modified version random_gcm.c
>
> This uses the hash from AES-GCM instead of SHA-1,
> and that allows a lot of other changes. The main
> design goal was to decouple the two output pools
> so that heavy use of the nonblocking pool cannot
> deplete entropy in the input pool. The nonblocking
> pool usually rekeys from the blocking pool instead.
> random_gcm.c has extensive comments on both
> the rationale for this approach & the details of my
> implementation.
>
> random_gcm.c is not close to being a finished
> product, in particular my code is not yet well
> integrated with existing driver code.
>
> Most of the code was developed and has been
> fairly well tested outside the kernel.
> Test program is at:
> https://github.com/sandy-harris/random.test
>
> I just dropped a large chunk of that code into
> a copy of random.c, made modifications to
> make the style match better & to get it to
> compile in the kernel context, then deleted
> a few chunks of existing driver code and
> replaced them with calls to my stuff.
>
> Proper integration would involve both
> replacing more of the existing code with
> new and moving a few important bits of
> the existing code into some of my functions.
> In particular, my stuff does not yet block
> in the right places.

Re: [PATCH 1/7] A couple of generated files

[Sandy Harris]

Jason Cooper  wrote:

> I know we talked  about this series offlist, but we need to fill in
> folks who are seeing it for the first time.  Usually, this is done with
> a coverletter (--coverletter for git format-patch).

Yes, your help plus the O'Reilly book got me using git without
too many errors, but I'm still getting things wrong & missing
the cover letter was one.

> No need to resend
> before receiving feedback, but would you mind replying with a
> description of the problem you're attempting to solve and how the series
> solves it?

There are two groups of changes, each controlled by a config
variable. Default for both is 'n'.

CONFIG_RANDOM_INIT: initialise the pools with data from
/dev/urandom on the machine that compiles the kernel.
Comments for the generator program scripts/gen_random.c
have details.

The main change in random.c is adding conditionals
to make it use the random data if CONFIG_RANDOM_INIT
is set. There is also a trivial fix updating a reference to an
obsoleted in a comment, and I added some sanity-check
#if tests for odd #define parameter values.

This is a fairly simple change. I do not think it needs a config
variable; it should just be the default. However I put it under
config control for testing.

CONFIG_RANDOM_GCM controls a much larger and
less clearly desirable set of changes. It switches
compilation between random.c and and a heavily
modified version random_gcm.c

This uses the hash from AES-GCM instead of SHA-1,
and that allows a lot of other changes. The main
design goal was to decouple the two output pools
so that heavy use of the nonblocking pool cannot
deplete entropy in the input pool. The nonblocking
pool usually rekeys from the blocking pool instead.
random_gcm.c has extensive comments on both
the rationale for this approach & the details of my
implementation.

random_gcm.c is not close to being a finished
product, in particular my code is not yet well
integrated with existing driver code.

Most of the code was developed and has been
fairly well tested outside the kernel.
Test program is at:
https://github.com/sandy-harris/random.test

I just dropped a large chunk of that code into
a copy of random.c, made modifications to
make the style match better & to get it to
compile in the kernel context, then deleted
a few chunks of existing driver code and
replaced them with calls to my stuff.

Proper integration would involve both
replacing more of the existing code with
new and moving a few important bits of
the existing code into some of my functions.
In particular, my stuff does not yet block
in the right places.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 1/7] A couple of generated files

[Sandy Harris]

On Sat, Nov 7, 2015 at 12:01 PM, Jason Cooper  wrote:
> On Sat, Nov 07, 2015 at 09:30:36AM -0500, Sandy Harris wrote:
>> Signed-off-by: Sandy Harris 
>> ---
>>  .gitignore | 3 +++
>>  1 file changed, 3 insertions(+)
>>
>> diff --git a/.gitignore b/.gitignore
>> index fd3a355..dd80bfd 100644
>> --- a/.gitignore
>> +++ b/.gitignore
>> @@ -112,3 +112,6 @@ all.config
>>
>>  # Kdevelop4
>>  *.kdev4
>> +
>> +certs/x509_certificate_list
>> +scripts/gen_random
>
> Is there a .gitignore file in scripts/ ?
>

Yes, though I wasn't aware of that.
I guess gen_random should be there instead of in the global file.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 7/7] Create generated/random_init.h, used by random driver

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 Kbuild   | 21 +
 scripts/Makefile |  1 +
 2 files changed, 22 insertions(+)

diff --git a/Kbuild b/Kbuild
index f55cefd..494c665 100644
--- a/Kbuild
+++ b/Kbuild
@@ -5,6 +5,7 @@
 # 2) Generate timeconst.h
 # 3) Generate asm-offsets.h (may need bounds.h and timeconst.h)
 # 4) Check for missing system calls
+# 5) Generate random_init.h
 
 # Default sed regexp - multiline due to syntax constraints
 define sed-y
@@ -98,3 +99,23 @@ missing-syscalls: scripts/checksyscalls.sh $(offsets-file) 
FORCE
 
 # Keep these three files during make clean
 no-clean-files := $(bounds-file) $(offsets-file) $(timeconst-file)
+
+#
+# 5) Generate random_init.h
+
+ifdef CONFIG_RANDOM_INIT
+init-file := include/generated/random_init.h
+used-file := scripts/gen_random
+source-file := $(used-file).c
+always  += $(init-file)
+targets  += $(init-file)
+$(init-file) : $(used-file)
+   $(Q) $(used-file) > $(init-file)
+ifdef CONFIG_RANDOM_GCM
+$(used-file) : $(source-file)
+   $(CC) $< -DCONFIG_RANDOM_GCM -o $@
+else
+$(used-file) : $(source-file)
+   $(CC) $< -o $@
+endif
+endif
diff --git a/scripts/Makefile b/scripts/Makefile
index 1b26617..3cea546 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -18,6 +18,7 @@ hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
 hostprogs-$(CONFIG_ASN1)+= asn1_compiler
 hostprogs-$(CONFIG_MODULE_SIG)  += sign-file
 hostprogs-$(CONFIG_SYSTEM_TRUSTED_KEYRING) += extract-cert
+hostprogs-$(CONFIG_RANDOM_INIT) += gen_random
 
 HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include
 HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 2/7] Two new CONFIG options for the random(4) driver

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 drivers/char/Kconfig | 23 +++
 1 file changed, 23 insertions(+)

diff --git a/drivers/char/Kconfig b/drivers/char/Kconfig
index a043107..0e0e6b5 100644
--- a/drivers/char/Kconfig
+++ b/drivers/char/Kconfig
@@ -603,5 +603,28 @@ config TILE_SROM
 
 source "drivers/char/xillybus/Kconfig"
 
+
+config RANDOM_INIT
+   bool "Initialise random(4) pools with random data (NEW)"
+   default n
+   help
+ Use /dev/urandom on development machine to set
+ up pools, different for each compile.
+ Compiles scripts/gen_random_init.c
+ Creates include/generated/random_init.h
+
+config RANDOM_GCM
+   bool "modified random(4) driver (EXPERIMENTAL)"
+   depends on RANDOM_INIT
+   default n
+   help
+ New version using the hash from AES-GCM.
+ Main goal decoupling so that heavy use of
+ /dev/urandom cannot deplete entropy for
+ /dev/random.
+ Should not be used in production before much
+ more analysis and testing is done.
+ When in doubt, say "N".
+
 endmenu
 
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 6/7] Produces generated/random_init.h for random driver

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 scripts/gen_random.c | 260 +++
 1 file changed, 260 insertions(+)
 create mode 100644 scripts/gen_random.c

diff --git a/scripts/gen_random.c b/scripts/gen_random.c
new file mode 100644
index 000..07b447f
--- /dev/null
+++ b/scripts/gen_random.c
@@ -0,0 +1,260 @@
+/*
+ * Program to select random numbers for initialising things
+ * in the random(4) driver.
+ *
+ * A different implementation of basically the same idea is
+ * one of several kernel security enhancements at
+ * https://grsecurity.net/
+ *
+ * This program:
+ *
+ *limits the range of Hamming weights
+ *every byte has at least one bit 1, one 0
+ *different every time it runs
+ *
+ * data from /dev/urandom
+ * results suitable for inclusion by random.c
+ * writes to stdout, expecting makefile to redirect
+ *
+ * makefile should also delete the output file after it is
+ * used in compilation of random.c. This is more secure; it
+ * forces the file to be rebuilt and a new version used in
+ * every compile. It also prevents an enemy just reading an
+ * output file in the build directory and getting the data
+ * that is in use in the current kernel. This is not full
+ * protection since they might look in the kernel image,
+ * but it seems to be the best we can do.
+ *
+ * This falls well short of the ideal initialisation solution,
+ * which would give every installation (rather than every
+ * compiled kernel) a different seed. For that, see John
+ * Denker's suggestions at:
+ * http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image
+ *
+ * On the other hand, neither sort of seed is necessary if
+ *either  you have a trustworthy hardware RNG
+ *or  you have secure stored data
+ * In those cases, the device can easily be initialised well; the
+ * only difficulty is to ensure this is done early enough.
+ *
+ * Inserting random data at compile time can do no harm and may
+ * sometimes make attacks harder. It is not an ideal solution, and
+ * not always necessary, but cheap and probably the best we can do
+ * during the build (rather than install) process.
+ *
+ * This is certainly done early enough and the data is random
+ * enough, but it is not necessarily secret enough.
+ *
+ * In some cases -- for example, a firewall machine that compiles
+ * its own kernel -- this alone might be enough to ensure secure
+ * initialisation, since only an enemy who already has root could
+ * discover this data. Of course even in those cases it should not
+ * be used alone, only as one layer of a defense in depth.
+ *
+ * In other cases -- a kernel that is compiled once then used in
+ * a Linux distro or installed on many devices -- this is likely
+ * of very little value. It complicates an attack somewhat, but
+ * it clearly will not stop a serious attacker and may not even
+ * slow them down much.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+/*
+ * Configuration information
+ * moved from random.c
+ */
+#define INPUT_POOL_SHIFT   12
+#define INPUT_POOL_WORDS   (1 << (INPUT_POOL_SHIFT-5))
+#define OUTPUT_POOL_SHIFT  10
+#define OUTPUT_POOL_WORDS  (1 << (OUTPUT_POOL_SHIFT-5))
+
+#define TOTAL_POOL_WORDS  (INPUT_POOL_WORDS + 2*OUTPUT_POOL_WORDS)
+
+typedef uint32_t u32 ;
+
+int accept(u32) ;
+int hamming(u32);
+void do_block( int, char * ) ;
+void usage(void) ;
+
+int urandom ;
+
+int main(int argc, char **argv)
+{
+   if( (urandom = open("/dev/urandom", O_RDONLY)) == -1 )  {
+   fprintf(stderr, "gen_random_init: no /dev/urandom, cannot 
continue\n") ;
+   exit(1) ;
+   }
+   printf("/* File generated by gen_random_init.c */\n\n") ;
+   /*
+* print our constants into output file
+* ensuring random.c has the same values
+*/
+   printf("#define INPUT_POOL_WORDS %d\n", INPUT_POOL_WORDS) ; 
+   printf("#define OUTPUT_POOL_WORDS %d\n", OUTPUT_POOL_WORDS) ;
+   printf("#define INPUT_POOL_SHIFT %d\n\n", INPUT_POOL_SHIFT) ; 
+ 
+   /*
+* Initialise the pools with random data
+* This is done unconditionally
+*/
+   do_block( TOTAL_POOL_WORDS, "pools" ) ;
+
+#ifdef CONFIG_RANDOM_GCM
+
+#define ARRAY_ROWS  8  /* 4 pools get 2 constants each 
   */
+#define ARRAY_WORDS(4 * ARRAY_ROWS)/* 32-bit words, 128-bit 
constants */
+
+/*
+ * If we are using the GCM hash, set up an array of random
+ * constants for it.
+ *
+ * The choice of 32 words (eight 128-bit rows, 1024 bits) for
+ * this is partly arbitrary, partly reasoned. 256 bits would
+ * almost certainly be enough, but 1024 is convenient.
+ *
+ * The AES-GCM hash initialises its accumulator all-zero and uses
+ * a 128-bit multiplier, H. I chose instead to use two constants,
+ * one to initialise the accumulator and one in the role of H.

[PATCH 5/7] Conditionals for CONFIG_RANDOM_INIT and CONFIG_RANDOM_GCM

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 drivers/char/Makefile | 25 -
 1 file changed, 24 insertions(+), 1 deletion(-)

diff --git a/drivers/char/Makefile b/drivers/char/Makefile
index d8a7579..7d095e5 100644
--- a/drivers/char/Makefile
+++ b/drivers/char/Makefile
@@ -2,7 +2,30 @@
 # Makefile for the kernel character device drivers.
 #
 
-obj-y  += mem.o random.o
+obj-y  += mem.o
+
+ifeq ($(CONFIG_RANDOM_GCM),y)
+  random_c = random_gcm.c
+  random_o = random_gcm.o
+  random_no= random.o
+else
+  random_c = random.c
+  random_o = random.o
+  random_no= random_gcm.o
+endif
+obj-y  += $(random_o)
+
+# remove the generated file after use so that
+# a fresh one is built (by scripts/gen_random)
+# for every compile
+# remove random_no so it will not get linked
+ifeq ($(CONFIG_RANDOM_INIT),y)
+init-file = include/generated/random_init.h
+$(random_o): $(random_c) $(init-file)
+   $(CC) $< -o $@
+   $(Q) rm --force $(init-file) $(random_no)
+endif
+
 obj-$(CONFIG_TTY_PRINTK)   += ttyprintk.o
 obj-y  += misc.o
 obj-$(CONFIG_ATARI_DSP56K) += dsp56k.o
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 4/7] Different version of driver using hash from AES-GCM Compiled if CONFIG_RANDOM_GCM=y

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 drivers/char/random_gcm.c | 3716 +
 1 file changed, 3716 insertions(+)
 create mode 100644 drivers/char/random_gcm.c

diff --git a/drivers/char/random_gcm.c b/drivers/char/random_gcm.c
new file mode 100644
index 000..360fbe3
--- /dev/null
+++ b/drivers/char/random_gcm.c
@@ -0,0 +1,3716 @@
+/*
+ * random.c -- A strong random number generator
+ *
+ * Copyright Matt Mackall , 2003, 2004, 2005
+ *
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  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.
+ */
+
+/*
+ * (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 using a CRC-like function.
+ * This is not cryptographically strong, but it is adequate assuming
+ * the randomness is not chosen maliciously, and it is fast enough that
+ * the overhead of doing it on every interrupt is very reasonable.
+ * 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.
+ *
+ * When random bytes are desired, they are obtained by taking the SHA
+ * hash of the contents of the "entropy pool".  The SHA hash avoids
+ * exposing the internal state of the entropy pool.  It is believed to
+ * be computationally infeasible to derive any useful information
+ * about the input of SHA from its output.  Even if it is possible to
+ * analyze SHA in some clever way, as long as the amount of data
+ * returned from the generator is less than the inherent entropy 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

[PATCH 1/7] A couple of generated files

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 .gitignore | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/.gitignore b/.gitignore
index fd3a355..dd80bfd 100644
--- a/.gitignore
+++ b/.gitignore
@@ -112,3 +112,6 @@ all.config
 
 # Kdevelop4
 *.kdev4
+
+certs/x509_certificate_list
+scripts/gen_random
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 3/7] Initialise pools randomly if CONFIG_RANDOM_INIT=y

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 drivers/char/random.c | 50 ++
 1 file changed, 46 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d0da5d8..e222e0f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -231,7 +231,7 @@
  * not be attributed to the Phil, Colin, or any of authors of PGP.
  *
  * Further background information on this topic may be obtained from
- * RFC 1750, "Randomness Recommendations for Security", by Donald
+ * RFC 4086, "Randomness Requirements for Security", by Donald
  * Eastlake, Steve Crocker, and Jeff Schiller.
  */
 
@@ -275,13 +275,19 @@
 /*
  * Configuration information
  */
+#ifdef CONFIG_RANDOM_INIT
+
+#include 
+
+#else
 #define INPUT_POOL_SHIFT   12
 #define INPUT_POOL_WORDS   (1 << (INPUT_POOL_SHIFT-5))
 #define OUTPUT_POOL_SHIFT  10
 #define OUTPUT_POOL_WORDS  (1 << (OUTPUT_POOL_SHIFT-5))
-#define SEC_XFER_SIZE  512
-#define EXTRACT_SIZE   10
+#endif
 
+#define EXTRACT_SIZE   10
+#define SEC_XFER_SIZE  512
 #define DEBUG_RANDOM_BOOT 0
 
 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
@@ -296,6 +302,27 @@
 #define ENTROPY_SHIFT 3
 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
 
+/* sanity checks */
+
+#if ((ENTROPY_SHIFT+INPUT_POOL_SHIFT) >= 16)
+#ifndef CONFIG_64BIT
+#error *_SHIFT values problematic for credit_entropy_bits()
+#endif
+#endif
+
+#if ((INPUT_POOL_WORDS%16) || (OUTPUT_POOL_WORDS%16))
+#error Pool size not divisible by 16, which code assumes
+#endif
+
+#if (INPUT_POOL_WORDS < 32)
+#error Input pool less than a quarter of default size
+#endif
+
+#if (INPUT_POOL_WORDS < OUTPUT_POOL_WORDS)
+#error Strange configuration, input pool smalller than output
+#endif
+
+
 /*
  * The minimum number of bits of entropy before we wake up a read on
  * /dev/random.  Should be enough to do a significant reseed.
@@ -442,16 +469,23 @@ struct entropy_store {
 };
 
 static void push_to_pool(struct work_struct *work);
+
+#ifndef CONFIG_RANDOM_INIT
 static __u32 input_pool_data[INPUT_POOL_WORDS];
 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
 static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
+#endif
 
 static struct entropy_store input_pool = {
.poolinfo = _table[0],
.name = "input",
.limit = 1,
.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
-   .pool = input_pool_data
+#ifdef CONFIG_RANDOM_INIT
+   .pool = pools,
+#else
+   .pool = input_pool_data,
+#endif
 };
 
 static struct entropy_store blocking_pool = {
@@ -460,7 +494,11 @@ static struct entropy_store blocking_pool = {
.limit = 1,
.pull = _pool,
.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
+#ifdef CONFIG_RANDOM_INIT
+   .pool = pools + INPUT_POOL_WORDS,
+#else
.pool = blocking_pool_data,
+#endif
.push_work = __WORK_INITIALIZER(blocking_pool.push_work,
push_to_pool),
 };
@@ -470,7 +508,11 @@ static struct entropy_store nonblocking_pool = {
.name = "nonblocking",
.pull = _pool,
.lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock),
+#ifdef CONFIG_RANDOM_INIT
+   .pool = pools + INPUT_POOL_WORDS + OUTPUT_POOL_WORDS,
+#else
.pool = nonblocking_pool_data,
+#endif
.push_work = __WORK_INITIALIZER(nonblocking_pool.push_work,
push_to_pool),
 };
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 1/7] A couple of generated files

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 .gitignore | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/.gitignore b/.gitignore
index fd3a355..dd80bfd 100644
--- a/.gitignore
+++ b/.gitignore
@@ -112,3 +112,6 @@ all.config
 
 # Kdevelop4
 *.kdev4
+
+certs/x509_certificate_list
+scripts/gen_random
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 3/7] Initialise pools randomly if CONFIG_RANDOM_INIT=y

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 drivers/char/random.c | 50 ++
 1 file changed, 46 insertions(+), 4 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d0da5d8..e222e0f 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -231,7 +231,7 @@
  * not be attributed to the Phil, Colin, or any of authors of PGP.
  *
  * Further background information on this topic may be obtained from
- * RFC 1750, "Randomness Recommendations for Security", by Donald
+ * RFC 4086, "Randomness Requirements for Security", by Donald
  * Eastlake, Steve Crocker, and Jeff Schiller.
  */
 
@@ -275,13 +275,19 @@
 /*
  * Configuration information
  */
+#ifdef CONFIG_RANDOM_INIT
+
+#include 
+
+#else
 #define INPUT_POOL_SHIFT   12
 #define INPUT_POOL_WORDS   (1 << (INPUT_POOL_SHIFT-5))
 #define OUTPUT_POOL_SHIFT  10
 #define OUTPUT_POOL_WORDS  (1 << (OUTPUT_POOL_SHIFT-5))
-#define SEC_XFER_SIZE  512
-#define EXTRACT_SIZE   10
+#endif
 
+#define EXTRACT_SIZE   10
+#define SEC_XFER_SIZE  512
 #define DEBUG_RANDOM_BOOT 0
 
 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
@@ -296,6 +302,27 @@
 #define ENTROPY_SHIFT 3
 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
 
+/* sanity checks */
+
+#if ((ENTROPY_SHIFT+INPUT_POOL_SHIFT) >= 16)
+#ifndef CONFIG_64BIT
+#error *_SHIFT values problematic for credit_entropy_bits()
+#endif
+#endif
+
+#if ((INPUT_POOL_WORDS%16) || (OUTPUT_POOL_WORDS%16))
+#error Pool size not divisible by 16, which code assumes
+#endif
+
+#if (INPUT_POOL_WORDS < 32)
+#error Input pool less than a quarter of default size
+#endif
+
+#if (INPUT_POOL_WORDS < OUTPUT_POOL_WORDS)
+#error Strange configuration, input pool smalller than output
+#endif
+
+
 /*
  * The minimum number of bits of entropy before we wake up a read on
  * /dev/random.  Should be enough to do a significant reseed.
@@ -442,16 +469,23 @@ struct entropy_store {
 };
 
 static void push_to_pool(struct work_struct *work);
+
+#ifndef CONFIG_RANDOM_INIT
 static __u32 input_pool_data[INPUT_POOL_WORDS];
 static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
 static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
+#endif
 
 static struct entropy_store input_pool = {
.poolinfo = _table[0],
.name = "input",
.limit = 1,
.lock = __SPIN_LOCK_UNLOCKED(input_pool.lock),
-   .pool = input_pool_data
+#ifdef CONFIG_RANDOM_INIT
+   .pool = pools,
+#else
+   .pool = input_pool_data,
+#endif
 };
 
 static struct entropy_store blocking_pool = {
@@ -460,7 +494,11 @@ static struct entropy_store blocking_pool = {
.limit = 1,
.pull = _pool,
.lock = __SPIN_LOCK_UNLOCKED(blocking_pool.lock),
+#ifdef CONFIG_RANDOM_INIT
+   .pool = pools + INPUT_POOL_WORDS,
+#else
.pool = blocking_pool_data,
+#endif
.push_work = __WORK_INITIALIZER(blocking_pool.push_work,
push_to_pool),
 };
@@ -470,7 +508,11 @@ static struct entropy_store nonblocking_pool = {
.name = "nonblocking",
.pull = _pool,
.lock = __SPIN_LOCK_UNLOCKED(nonblocking_pool.lock),
+#ifdef CONFIG_RANDOM_INIT
+   .pool = pools + INPUT_POOL_WORDS + OUTPUT_POOL_WORDS,
+#else
.pool = nonblocking_pool_data,
+#endif
.push_work = __WORK_INITIALIZER(nonblocking_pool.push_work,
push_to_pool),
 };
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 4/7] Different version of driver using hash from AES-GCM Compiled if CONFIG_RANDOM_GCM=y

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 drivers/char/random_gcm.c | 3716 +
 1 file changed, 3716 insertions(+)
 create mode 100644 drivers/char/random_gcm.c

diff --git a/drivers/char/random_gcm.c b/drivers/char/random_gcm.c
new file mode 100644
index 000..360fbe3
--- /dev/null
+++ b/drivers/char/random_gcm.c
@@ -0,0 +1,3716 @@
+/*
+ * random.c -- A strong random number generator
+ *
+ * Copyright Matt Mackall <m...@selenic.com>, 2003, 2004, 2005
+ *
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  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.
+ */
+
+/*
+ * (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 using a CRC-like function.
+ * This is not cryptographically strong, but it is adequate assuming
+ * the randomness is not chosen maliciously, and it is fast enough that
+ * the overhead of doing it on every interrupt is very reasonable.
+ * 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.
+ *
+ * When random bytes are desired, they are obtained by taking the SHA
+ * hash of the contents of the "entropy pool".  The SHA hash avoids
+ * exposing the internal state of the entropy pool.  It is believed to
+ * be computationally infeasible to derive any useful information
+ * about the input of SHA from its output.  Even if it is possible to
+ * analyze SHA in some clever way, as long as the amount of data
+ * returned from the generator is less than the inherent entropy in
+ * the pool, the output data is totally unpredictable.  For this
+ * reason, the routine decreases its inter

[PATCH 6/7] Produces generated/random_init.h for random driver

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 scripts/gen_random.c | 260 +++
 1 file changed, 260 insertions(+)
 create mode 100644 scripts/gen_random.c

diff --git a/scripts/gen_random.c b/scripts/gen_random.c
new file mode 100644
index 000..07b447f
--- /dev/null
+++ b/scripts/gen_random.c
@@ -0,0 +1,260 @@
+/*
+ * Program to select random numbers for initialising things
+ * in the random(4) driver.
+ *
+ * A different implementation of basically the same idea is
+ * one of several kernel security enhancements at
+ * https://grsecurity.net/
+ *
+ * This program:
+ *
+ *limits the range of Hamming weights
+ *every byte has at least one bit 1, one 0
+ *different every time it runs
+ *
+ * data from /dev/urandom
+ * results suitable for inclusion by random.c
+ * writes to stdout, expecting makefile to redirect
+ *
+ * makefile should also delete the output file after it is
+ * used in compilation of random.c. This is more secure; it
+ * forces the file to be rebuilt and a new version used in
+ * every compile. It also prevents an enemy just reading an
+ * output file in the build directory and getting the data
+ * that is in use in the current kernel. This is not full
+ * protection since they might look in the kernel image,
+ * but it seems to be the best we can do.
+ *
+ * This falls well short of the ideal initialisation solution,
+ * which would give every installation (rather than every
+ * compiled kernel) a different seed. For that, see John
+ * Denker's suggestions at:
+ * http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image
+ *
+ * On the other hand, neither sort of seed is necessary if
+ *either  you have a trustworthy hardware RNG
+ *or  you have secure stored data
+ * In those cases, the device can easily be initialised well; the
+ * only difficulty is to ensure this is done early enough.
+ *
+ * Inserting random data at compile time can do no harm and may
+ * sometimes make attacks harder. It is not an ideal solution, and
+ * not always necessary, but cheap and probably the best we can do
+ * during the build (rather than install) process.
+ *
+ * This is certainly done early enough and the data is random
+ * enough, but it is not necessarily secret enough.
+ *
+ * In some cases -- for example, a firewall machine that compiles
+ * its own kernel -- this alone might be enough to ensure secure
+ * initialisation, since only an enemy who already has root could
+ * discover this data. Of course even in those cases it should not
+ * be used alone, only as one layer of a defense in depth.
+ *
+ * In other cases -- a kernel that is compiled once then used in
+ * a Linux distro or installed on many devices -- this is likely
+ * of very little value. It complicates an attack somewhat, but
+ * it clearly will not stop a serious attacker and may not even
+ * slow them down much.
+ */
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+/*
+ * Configuration information
+ * moved from random.c
+ */
+#define INPUT_POOL_SHIFT   12
+#define INPUT_POOL_WORDS   (1 << (INPUT_POOL_SHIFT-5))
+#define OUTPUT_POOL_SHIFT  10
+#define OUTPUT_POOL_WORDS  (1 << (OUTPUT_POOL_SHIFT-5))
+
+#define TOTAL_POOL_WORDS  (INPUT_POOL_WORDS + 2*OUTPUT_POOL_WORDS)
+
+typedef uint32_t u32 ;
+
+int accept(u32) ;
+int hamming(u32);
+void do_block( int, char * ) ;
+void usage(void) ;
+
+int urandom ;
+
+int main(int argc, char **argv)
+{
+   if( (urandom = open("/dev/urandom", O_RDONLY)) == -1 )  {
+   fprintf(stderr, "gen_random_init: no /dev/urandom, cannot 
continue\n") ;
+   exit(1) ;
+   }
+   printf("/* File generated by gen_random_init.c */\n\n") ;
+   /*
+* print our constants into output file
+* ensuring random.c has the same values
+*/
+   printf("#define INPUT_POOL_WORDS %d\n", INPUT_POOL_WORDS) ; 
+   printf("#define OUTPUT_POOL_WORDS %d\n", OUTPUT_POOL_WORDS) ;
+   printf("#define INPUT_POOL_SHIFT %d\n\n", INPUT_POOL_SHIFT) ; 
+ 
+   /*
+* Initialise the pools with random data
+* This is done unconditionally
+*/
+   do_block( TOTAL_POOL_WORDS, "pools" ) ;
+
+#ifdef CONFIG_RANDOM_GCM
+
+#define ARRAY_ROWS  8  /* 4 pools get 2 constants each 
   */
+#define ARRAY_WORDS(4 * ARRAY_ROWS)/* 32-bit words, 128-bit 
constants */
+
+/*
+ * If we are using the GCM hash, set up an array of random
+ * constants for it.
+ *
+ * The choice of 32 words (eight 128-bit rows, 1024 bits) for
+ * this is partly arbitrary, partly reasoned. 256 bits would
+ * almost certainly be enough, but 1024 is convenient.
+ *
+ * The AES-GCM hash initialises its accumulator all-zero and uses
+ * a 128-bit multiplier, H. I chose instead to use two constants,
+ * one to initialise the accumulator 

[PATCH 5/7] Conditionals for CONFIG_RANDOM_INIT and CONFIG_RANDOM_GCM

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 drivers/char/Makefile | 25 -
 1 file changed, 24 insertions(+), 1 deletion(-)

diff --git a/drivers/char/Makefile b/drivers/char/Makefile
index d8a7579..7d095e5 100644
--- a/drivers/char/Makefile
+++ b/drivers/char/Makefile
@@ -2,7 +2,30 @@
 # Makefile for the kernel character device drivers.
 #
 
-obj-y  += mem.o random.o
+obj-y  += mem.o
+
+ifeq ($(CONFIG_RANDOM_GCM),y)
+  random_c = random_gcm.c
+  random_o = random_gcm.o
+  random_no= random.o
+else
+  random_c = random.c
+  random_o = random.o
+  random_no= random_gcm.o
+endif
+obj-y  += $(random_o)
+
+# remove the generated file after use so that
+# a fresh one is built (by scripts/gen_random)
+# for every compile
+# remove random_no so it will not get linked
+ifeq ($(CONFIG_RANDOM_INIT),y)
+init-file = include/generated/random_init.h
+$(random_o): $(random_c) $(init-file)
+   $(CC) $< -o $@
+   $(Q) rm --force $(init-file) $(random_no)
+endif
+
 obj-$(CONFIG_TTY_PRINTK)   += ttyprintk.o
 obj-y  += misc.o
 obj-$(CONFIG_ATARI_DSP56K) += dsp56k.o
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 7/7] Create generated/random_init.h, used by random driver

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 Kbuild   | 21 +
 scripts/Makefile |  1 +
 2 files changed, 22 insertions(+)

diff --git a/Kbuild b/Kbuild
index f55cefd..494c665 100644
--- a/Kbuild
+++ b/Kbuild
@@ -5,6 +5,7 @@
 # 2) Generate timeconst.h
 # 3) Generate asm-offsets.h (may need bounds.h and timeconst.h)
 # 4) Check for missing system calls
+# 5) Generate random_init.h
 
 # Default sed regexp - multiline due to syntax constraints
 define sed-y
@@ -98,3 +99,23 @@ missing-syscalls: scripts/checksyscalls.sh $(offsets-file) 
FORCE
 
 # Keep these three files during make clean
 no-clean-files := $(bounds-file) $(offsets-file) $(timeconst-file)
+
+#
+# 5) Generate random_init.h
+
+ifdef CONFIG_RANDOM_INIT
+init-file := include/generated/random_init.h
+used-file := scripts/gen_random
+source-file := $(used-file).c
+always  += $(init-file)
+targets  += $(init-file)
+$(init-file) : $(used-file)
+   $(Q) $(used-file) > $(init-file)
+ifdef CONFIG_RANDOM_GCM
+$(used-file) : $(source-file)
+   $(CC) $< -DCONFIG_RANDOM_GCM -o $@
+else
+$(used-file) : $(source-file)
+   $(CC) $< -o $@
+endif
+endif
diff --git a/scripts/Makefile b/scripts/Makefile
index 1b26617..3cea546 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -18,6 +18,7 @@ hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
 hostprogs-$(CONFIG_ASN1)+= asn1_compiler
 hostprogs-$(CONFIG_MODULE_SIG)  += sign-file
 hostprogs-$(CONFIG_SYSTEM_TRUSTED_KEYRING) += extract-cert
+hostprogs-$(CONFIG_RANDOM_INIT) += gen_random
 
 HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include
 HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 2/7] Two new CONFIG options for the random(4) driver

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 drivers/char/Kconfig | 23 +++
 1 file changed, 23 insertions(+)

diff --git a/drivers/char/Kconfig b/drivers/char/Kconfig
index a043107..0e0e6b5 100644
--- a/drivers/char/Kconfig
+++ b/drivers/char/Kconfig
@@ -603,5 +603,28 @@ config TILE_SROM
 
 source "drivers/char/xillybus/Kconfig"
 
+
+config RANDOM_INIT
+   bool "Initialise random(4) pools with random data (NEW)"
+   default n
+   help
+ Use /dev/urandom on development machine to set
+ up pools, different for each compile.
+ Compiles scripts/gen_random_init.c
+ Creates include/generated/random_init.h
+
+config RANDOM_GCM
+   bool "modified random(4) driver (EXPERIMENTAL)"
+   depends on RANDOM_INIT
+   default n
+   help
+ New version using the hash from AES-GCM.
+ Main goal decoupling so that heavy use of
+ /dev/urandom cannot deplete entropy for
+ /dev/random.
+ Should not be used in production before much
+ more analysis and testing is done.
+ When in doubt, say "N".
+
 endmenu
 
-- 
2.5.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 1/7] A couple of generated files

[Sandy Harris]

On Sat, Nov 7, 2015 at 12:01 PM, Jason Cooper <ja...@lakedaemon.net> wrote:
> On Sat, Nov 07, 2015 at 09:30:36AM -0500, Sandy Harris wrote:
>> Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
>> ---
>>  .gitignore | 3 +++
>>  1 file changed, 3 insertions(+)
>>
>> diff --git a/.gitignore b/.gitignore
>> index fd3a355..dd80bfd 100644
>> --- a/.gitignore
>> +++ b/.gitignore
>> @@ -112,3 +112,6 @@ all.config
>>
>>  # Kdevelop4
>>  *.kdev4
>> +
>> +certs/x509_certificate_list
>> +scripts/gen_random
>
> Is there a .gitignore file in scripts/ ?
>

Yes, though I wasn't aware of that.
I guess gen_random should be there instead of in the global file.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 1/7] A couple of generated files

[Sandy Harris]

Jason Cooper <ja...@lakedaemon.net> wrote:

> I know we talked  about this series offlist, but we need to fill in
> folks who are seeing it for the first time.  Usually, this is done with
> a coverletter (--coverletter for git format-patch).

Yes, your help plus the O'Reilly book got me using git without
too many errors, but I'm still getting things wrong & missing
the cover letter was one.

> No need to resend
> before receiving feedback, but would you mind replying with a
> description of the problem you're attempting to solve and how the series
> solves it?

There are two groups of changes, each controlled by a config
variable. Default for both is 'n'.

CONFIG_RANDOM_INIT: initialise the pools with data from
/dev/urandom on the machine that compiles the kernel.
Comments for the generator program scripts/gen_random.c
have details.

The main change in random.c is adding conditionals
to make it use the random data if CONFIG_RANDOM_INIT
is set. There is also a trivial fix updating a reference to an
obsoleted in a comment, and I added some sanity-check
#if tests for odd #define parameter values.

This is a fairly simple change. I do not think it needs a config
variable; it should just be the default. However I put it under
config control for testing.

CONFIG_RANDOM_GCM controls a much larger and
less clearly desirable set of changes. It switches
compilation between random.c and and a heavily
modified version random_gcm.c

This uses the hash from AES-GCM instead of SHA-1,
and that allows a lot of other changes. The main
design goal was to decouple the two output pools
so that heavy use of the nonblocking pool cannot
deplete entropy in the input pool. The nonblocking
pool usually rekeys from the blocking pool instead.
random_gcm.c has extensive comments on both
the rationale for this approach & the details of my
implementation.

random_gcm.c is not close to being a finished
product, in particular my code is not yet well
integrated with existing driver code.

Most of the code was developed and has been
fairly well tested outside the kernel.
Test program is at:
https://github.com/sandy-harris/random.test

I just dropped a large chunk of that code into
a copy of random.c, made modifications to
make the style match better & to get it to
compile in the kernel context, then deleted
a few chunks of existing driver code and
replaced them with calls to my stuff.

Proper integration would involve both
replacing more of the existing code with
new and moving a few important bits of
the existing code into some of my functions.
In particular, my stuff does not yet block
in the right places.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH] Update reference to obsolete RFC

[Sandy Harris]

Signed-off-by: Sandy Harris 
---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d0da5d8..90c472b 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -231,7 +231,7 @@
  * not be attributed to the Phil, Colin, or any of authors of PGP.
  *
  * Further background information on this topic may be obtained from
- * RFC 1750, "Randomness Recommendations for Security", by Donald
+ * RFC 4086, "Randomness Requirements for Security", by Donald
  * Eastlake, Steve Crocker, and Jeff Schiller.
  */
 
-- 
2.1.4

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[PATCH] Update reference to obsolete RFC

[Sandy Harris]

Signed-off-by: Sandy Harris <sandyinch...@gmail.com>
---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index d0da5d8..90c472b 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -231,7 +231,7 @@
  * not be attributed to the Phil, Colin, or any of authors of PGP.
  *
  * Further background information on this topic may be obtained from
- * RFC 1750, "Randomness Recommendations for Security", by Donald
+ * RFC 4086, "Randomness Requirements for Security", by Donald
  * Eastlake, Steve Crocker, and Jeff Schiller.
  */
 
-- 
2.1.4

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH v5 06/14] crypto: marvell/CESA: add DES support

[Sandy Harris]

On Tue, Jun 16, 2015 at 5:59 AM, Boris Brezillon
 wrote:

> Add support for DES operations.

Why on Earth should we do that? DES is demonstrably insecure. The only
possible excuse for allowing it anywhere in a modern code base is that
you need it to implement triple DES, and even that should by now be
deprecated in favour of more modern ciphers which are much faster and
thought to be  more secure.

Here's documentation from around the turn of the century
http://www.freeswan.org/freeswan_trees/freeswan-1.5/doc/DES.html

Moore's Law applies, so the $200,000 FPGA machine that broke DES in
days in 1998 might be dirt cheap today. Certainly breaking DES on one
of today's clusters would be fast and cheap as well, given that it
took only a few months in 1998 using the Internet as the Conectio
fabric.
http://www.interhack.net/pubs/des-key-crack/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH v5 06/14] crypto: marvell/CESA: add DES support

[Sandy Harris]

On Tue, Jun 16, 2015 at 5:59 AM, Boris Brezillon
boris.brezil...@free-electrons.com wrote:

 Add support for DES operations.

Why on Earth should we do that? DES is demonstrably insecure. The only
possible excuse for allowing it anywhere in a modern code base is that
you need it to implement triple DES, and even that should by now be
deprecated in favour of more modern ciphers which are much faster and
thought to be  more secure.

Here's documentation from around the turn of the century
http://www.freeswan.org/freeswan_trees/freeswan-1.5/doc/DES.html

Moore's Law applies, so the $200,000 FPGA machine that broke DES in
days in 1998 might be dirt cheap today. Certainly breaking DES on one
of today's clusters would be fast and cheap as well, given that it
took only a few months in 1998 using the Internet as the Conectio
fabric.
http://www.interhack.net/pubs/des-key-crack/
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] random: add random_initialized command line param

[Sandy Harris]

On Mon, May 18, 2015 at 6:58 PM, Herbert Xu  wrote:

> Stephan Mueller  wrote:
>>
>> I hear more and more discussions about recommendations to use AES 256 and not
>> AES 128.

Or perhaps other ciphers with 256-bit keys. Salsa, ChaCha and several of
the Caesar candidates support those.

>> These kind of recommendations will eventually also affect the entropy
>> requirements for noise sources. This is my motivation for the patch: allowing
>> different user groups to set the minimum bar for the nonblocking pool to
>> *higher* levels (the examples for 80 to 112 bits or 100 to 125 bits shall 
>> just
>> show that there are active revisions of entropy requirements).
>
> Does anyone need to raise this from 128 today? If not then this
> patch is pointless.

There is an RFC for ChaCha in IETF protocols
https://www.rfc-editor.org/rfc/rfc7539.txt
That RFC is new, issued this month, so it will probably be a while
before we need to worry about it.

I do think finding a way to support changing the init requirement from
128 to 256 bits will be useful at some point. However, I doubt it is
urgent since few protocols need it now. On the other hand, IPsec and
TLS both include AES-256, I think.

When we do do it, I see no reason to support anything other than 128
and 256, and I am not sure about retaining 128. Nor do I see any
reason this should be a command-line option rather than just a
compile-time constant.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] random: add random_initialized command line param

[Sandy Harris]

On Mon, May 18, 2015 at 6:58 PM, Herbert Xu herb...@gondor.apana.org.au wrote:

 Stephan Mueller smuel...@chronox.de wrote:

 I hear more and more discussions about recommendations to use AES 256 and not
 AES 128.

Or perhaps other ciphers with 256-bit keys. Salsa, ChaCha and several of
the Caesar candidates support those.

 These kind of recommendations will eventually also affect the entropy
 requirements for noise sources. This is my motivation for the patch: allowing
 different user groups to set the minimum bar for the nonblocking pool to
 *higher* levels (the examples for 80 to 112 bits or 100 to 125 bits shall 
 just
 show that there are active revisions of entropy requirements).

 Does anyone need to raise this from 128 today? If not then this
 patch is pointless.

There is an RFC for ChaCha in IETF protocols
https://www.rfc-editor.org/rfc/rfc7539.txt
That RFC is new, issued this month, so it will probably be a while
before we need to worry about it.

I do think finding a way to support changing the init requirement from
128 to 256 bits will be useful at some point. However, I doubt it is
urgent since few protocols need it now. On the other hand, IPsec and
TLS both include AES-256, I think.

When we do do it, I see no reason to support anything other than 128
and 256, and I am not sure about retaining 128. Nor do I see any
reason this should be a command-line option rather than just a
compile-time constant.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH v4 2/6] random: Async and sync API for accessing kernel_pool

[Sandy Harris]

On Sun, May 3, 2015 at 11:33 AM, Stephan Mueller  wrote:

> The kernel_pool is intended to be the in-kernel equivalent to the
> blocking_pool, i.e. requests for random data may be blocked if
> insufficient entropy is present.

I cannot see any reason this would be useful, let alone necessary.

Of course /dev/random should block and it seems to me there is a good
argument for making both /dev/urandom and get_random_bytes() block
until there is emough entropy to seed them well. For everything else,
though, a properly seeded PRNG seems adequate so there is no reason to
block.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH v4 2/6] random: Async and sync API for accessing kernel_pool

[Sandy Harris]

On Sun, May 3, 2015 at 11:33 AM, Stephan Mueller smuel...@chronox.de wrote:

 The kernel_pool is intended to be the in-kernel equivalent to the
 blocking_pool, i.e. requests for random data may be blocked if
 insufficient entropy is present.

I cannot see any reason this would be useful, let alone necessary.

Of course /dev/random should block and it seems to me there is a good
argument for making both /dev/urandom and get_random_bytes() block
until there is emough entropy to seed them well. For everything else,
though, a properly seeded PRNG seems adequate so there is no reason to
block.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Read/write file from random(4) driver

[Sandy Harris]

I realise that in general reading files from kernel space is a bad
idea, and understand at least some of the reasons. I have read Greg
K-H's article on the topic (http://www.linuxjournal.com/article/8110)
and some other discussion. However, I think I see a specific exception
and am looking for opinions here before I create a patch that may be
rejected out-of-hand.

The random device really needs secure initialisation and a number of
mechanisms have been proposed or are in use for that.

The default is a saved entropy file read & written by shellscripts
called by init. Details are in the comments in the random driver. This
works well in many cases but not on first boot or on a device such as
a router with little writable storage. Or if a router vendor or distro
builder omits the scripts. There have been well-publicised failures in
the field based on such problems; we clearly need something better.

John Denker suggests that every install needs a unique key provisioned; see
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image
This would indeed solve the problem if implemented correctly, but it
complicates install scripts some and getting this right relies on the
same people who conspicuously got the existing mechanism wrong.

It is straightforward to initialise arrays in the  driver at compile
time from /dev/urandom on the development machine. I have an
implementation of this idea and another is at https://grsecurity.net/
This is almost useless for a kernel that is compiled once then used in
many installs, but quite effective for machines that just compile
their own kernels.

What I'd like to add is a small (128 to 512 bits) file that the driver
tries to read during initialisation and writes periodically later.
This would not completely solve the problem but by moving the
read/write into the kernel it avoids the risk that vendors bungling
the scripts will break the driver.

This looks secure in all cases except first boot or an enemy who gets
root and reads the putatively secret data. Use a variant of Denker's
proposal to create a unique initial version of the file for each
install and it handles first boot as well.

Comment? Criticism?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Read/write file from random(4) driver

[Sandy Harris]

I realise that in general reading files from kernel space is a bad
idea, and understand at least some of the reasons. I have read Greg
K-H's article on the topic (http://www.linuxjournal.com/article/8110)
and some other discussion. However, I think I see a specific exception
and am looking for opinions here before I create a patch that may be
rejected out-of-hand.

The random device really needs secure initialisation and a number of
mechanisms have been proposed or are in use for that.

The default is a saved entropy file read  written by shellscripts
called by init. Details are in the comments in the random driver. This
works well in many cases but not on first boot or on a device such as
a router with little writable storage. Or if a router vendor or distro
builder omits the scripts. There have been well-publicised failures in
the field based on such problems; we clearly need something better.

John Denker suggests that every install needs a unique key provisioned; see
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image
This would indeed solve the problem if implemented correctly, but it
complicates install scripts some and getting this right relies on the
same people who conspicuously got the existing mechanism wrong.

It is straightforward to initialise arrays in the  driver at compile
time from /dev/urandom on the development machine. I have an
implementation of this idea and another is at https://grsecurity.net/
This is almost useless for a kernel that is compiled once then used in
many installs, but quite effective for machines that just compile
their own kernels.

What I'd like to add is a small (128 to 512 bits) file that the driver
tries to read during initialisation and writes periodically later.
This would not completely solve the problem but by moving the
read/write into the kernel it avoids the risk that vendors bungling
the scripts will break the driver.

This looks secure in all cases except first boot or an enemy who gets
root and reads the putatively secret data. Use a variant of Denker's
proposal to create a unique initial version of the file for each
install and it handles first boot as well.

Comment? Criticism?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: crypto: zeroization of sensitive data in af_alg

[Sandy Harris]

On Sun, Nov 9, 2014 at 5:33 PM, Stephan Mueller  wrote:

> while working on the AF_ALG interface, I saw no active zeroizations of memory
> that may hold sensitive data that is maintained outside the kernel crypto API
> cipher handles. ...

> I think I found the location for the first one: hash_sock_destruct that should
> be enhanced with a memset(0) of ctx->result.

See also a thread titled "memset() in crypto code?" on the linux
crypto list. The claim is that gcc can optimise memset() away so you
need a different function to guarantee the intended results. There's a
patch to the random driver that uses a new function
memzero_explicit(), and one of the newer C standards has a different
function name for the purpose.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: crypto: zeroization of sensitive data in af_alg

[Sandy Harris]

On Sun, Nov 9, 2014 at 5:33 PM, Stephan Mueller smuel...@chronox.de wrote:

 while working on the AF_ALG interface, I saw no active zeroizations of memory
 that may hold sensitive data that is maintained outside the kernel crypto API
 cipher handles. ...

 I think I found the location for the first one: hash_sock_destruct that should
 be enhanced with a memset(0) of ctx-result.

See also a thread titled memset() in crypto code? on the linux
crypto list. The claim is that gcc can optimise memset() away so you
need a different function to guarantee the intended results. There's a
patch to the random driver that uses a new function
memzero_explicit(), and one of the newer C standards has a different
function name for the purpose.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

RFC: Alternative to systemd?

[Sandy Harris]

I've been reading the debates around systemd, haven't reached any firm
conclusion but the criticism that Unix programs should "do one thing
and do it well" certainly resonates with me.

On the other hand, this may be one of those cases where theory and
practice need to differ; more-or-less all the arguments against
systemd's complexity and overly broad scope have been used in debates
over monolithic vs. message-passing kernels. I'd say that in theory
message-passing and smaller programs are obviously better in some
ways, but in practice other considerations may be more important. That
is certainly the case for the kernel; I do not know if it is for
systemd.

All that said, I don't want to re-open the debate here. I would,
though, like to solicit comment on what seems to me a possible simple
alternative that deals with only one of the problems systemd claims to
solve; expressing dependencies that the init process needs to deal
with. There seems to be fairly widespread agreement that the way
sysvinit does this rather clumsy.

We already have a well-established way of dealing with some types of
dependency, in makefiles. Would something with roughly that syntax
work for expressing the dependencies here? Sample lines might be
things like:

sshd: random

!random:
   cat /var/run/random_seed >/dev/urandom

The first line says sshd depends on random; "init sshd" will first
deal with dependencies, so it does the command for random before
starting sshd. Since no command is given for sshd, it defaults to
"sshd &". If arguments are needed, put in a command line. If some
other process depends on sshd it just checks whether it is running via
"ps -C sshd" and, if not, starts it.

"!random:" says, via the "!", that random is not a process that can be
checked with ps -C. We would need to add a data structure to support
another way to check if the process had been run. In actual use' we'd
also have a more complex command than just the cat.

It seems to me this could handle everything needed for init's startup
activities. Adding simple run levels is straightforward; just define
!runlevel3 or !network or whatever with appropriate dependencies. I am
not certain whether or how it might be extended to stop processes when
reducing run level, though.

Comments?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

RFC: Alternative to systemd?

[Sandy Harris]

I've been reading the debates around systemd, haven't reached any firm
conclusion but the criticism that Unix programs should do one thing
and do it well certainly resonates with me.

On the other hand, this may be one of those cases where theory and
practice need to differ; more-or-less all the arguments against
systemd's complexity and overly broad scope have been used in debates
over monolithic vs. message-passing kernels. I'd say that in theory
message-passing and smaller programs are obviously better in some
ways, but in practice other considerations may be more important. That
is certainly the case for the kernel; I do not know if it is for
systemd.

All that said, I don't want to re-open the debate here. I would,
though, like to solicit comment on what seems to me a possible simple
alternative that deals with only one of the problems systemd claims to
solve; expressing dependencies that the init process needs to deal
with. There seems to be fairly widespread agreement that the way
sysvinit does this rather clumsy.

We already have a well-established way of dealing with some types of
dependency, in makefiles. Would something with roughly that syntax
work for expressing the dependencies here? Sample lines might be
things like:

sshd: random

!random:
   cat /var/run/random_seed /dev/urandom

The first line says sshd depends on random; init sshd will first
deal with dependencies, so it does the command for random before
starting sshd. Since no command is given for sshd, it defaults to
sshd . If arguments are needed, put in a command line. If some
other process depends on sshd it just checks whether it is running via
ps -C sshd and, if not, starts it.

!random: says, via the !, that random is not a process that can be
checked with ps -C. We would need to add a data structure to support
another way to check if the process had been run. In actual use' we'd
also have a more complex command than just the cat.

It seems to me this could handle everything needed for init's startup
activities. Adding simple run levels is straightforward; just define
!runlevel3 or !network or whatever with appropriate dependencies. I am
not certain whether or how it might be extended to stop processes when
reducing run level, though.

Comments?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

Theodore Ts'o  wrote:

> Fundamentally, what worries me about this scheme (actually, causes the
> hair on the back of my neck to rise up on end) is this statement in
> your documentation[1]:
>
>When looking at the sequence of time deltas gathered
>during testing [D] , no pattern can be detected. Therefore, the
>fluctuation and the resulting distribution are not based on a
>repeating pattern and must be considered random.
>
> [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html
>
> Just because we can't detect a pattern does **not** mean that it is
> not based on a repeating pattern, and therefore must be considered
> random.  We can't detect a pattern in RDRAND, so does that mean it's
> automatically random?  Why, no.
> ...
> It may be that there is some very complex state which is hidden inside
> the the CPU execution pipeline, the L1 cache, etc., etc.  But just
> because *you* can't figure it out, and just because *I* can't figure
> it out doesn't mean that it is ipso facto something which a really
> bright NSA analyst working in Fort Meade can't figure out.  (Or heck,
> a really clever Intel engineer who has full visibility into the
> internal design of an Intel CPU)
>
> Now, it may be that in practice, an adversary won't be able to carry
> out a practical attack ...

It seems worth noting here that Ted's reasons for skepticism
apply not just to Stephan's Jitter generator, but to others such
as Havege (already in Debian) which are based on differences
in speed of arithmetic operations, presumably due to cache
& TLB misses, pipeline stalls, etc. Also to ones based on
variations in delays from timer calls such as my maxwell(8).

It is also worth mentioning that, while Stephan has done
thorough testing on a range of CPUs, others have test
& rationale info as well. The Havege papers have a lot,
my maxwell paper has a little, and there's:
McGuire, Okech & Schiesser,
Analysis of inherent randomness of the Linux kernel,
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

I know my stuff is not an adequate answer to Ted, but
I suspect some of the others may be.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

Theodore Ts'o ty...@mit.edu wrote:

 Fundamentally, what worries me about this scheme (actually, causes the
 hair on the back of my neck to rise up on end) is this statement in
 your documentation[1]:

When looking at the sequence of time deltas gathered
during testing [D] , no pattern can be detected. Therefore, the
fluctuation and the resulting distribution are not based on a
repeating pattern and must be considered random.

 [1] http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html

 Just because we can't detect a pattern does **not** mean that it is
 not based on a repeating pattern, and therefore must be considered
 random.  We can't detect a pattern in RDRAND, so does that mean it's
 automatically random?  Why, no.
 ...
 It may be that there is some very complex state which is hidden inside
 the the CPU execution pipeline, the L1 cache, etc., etc.  But just
 because *you* can't figure it out, and just because *I* can't figure
 it out doesn't mean that it is ipso facto something which a really
 bright NSA analyst working in Fort Meade can't figure out.  (Or heck,
 a really clever Intel engineer who has full visibility into the
 internal design of an Intel CPU)

 Now, it may be that in practice, an adversary won't be able to carry
 out a practical attack ...

It seems worth noting here that Ted's reasons for skepticism
apply not just to Stephan's Jitter generator, but to others such
as Havege (already in Debian) which are based on differences
in speed of arithmetic operations, presumably due to cache
 TLB misses, pipeline stalls, etc. Also to ones based on
variations in delays from timer calls such as my maxwell(8).

It is also worth mentioning that, while Stephan has done
thorough testing on a range of CPUs, others have test
 rationale info as well. The Havege papers have a lot,
my maxwell paper has a little, and there's:
McGuire, Okech  Schiesser,
Analysis of inherent randomness of the Linux kernel,
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

I know my stuff is not an adequate answer to Ted, but
I suspect some of the others may be.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

Stephan Mueller  wrote:

> [quoting me]

>> ...your code is basically, with 64-bit x:
>>
>>   for( i=0, x = 0 ; i < 64; i++, x =rotl(x) )
>>x |= bit()
>
> Why not declare some 64-bit constant C with a significant
>>number of bits set and do this:
>>
>>   for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) // same loop control
>>  if( bit() ) x ^= C ;
>>
>>This makes every output bit depend on many input bits
>>and costs almost nothing extra.

> Ok, let me play a bit with that. Maybe I can add another flag to the
> allocation function so that the caller can decide whether to use that.
> If the user is another RNG, you skip that mixing function, otherwise you
> should take it.

I'd say just do it. It is cheap enough and using it does no harm
even where it is not strictly needed. Adding a flag just gives the
calling code a chance to get it wrong. Better not to take that risk
if you don't have to.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Mon, Oct 14, 2013 at 11:26 AM, Stephan Mueller  wrote:

>>Why not declare some 64-bit constant C with a significant
>
> Which constant would you take? The CRC twist values? The SHA-1 initial
> values? Or the first few from SHA-256?

The only essential requirement is that it not be something stupidly
regular like a 64-bit string 0x.

I'd pick an odd number so the low bit always changes, and a
constant with about half the bits set, maybe 24 < n < 40 or
some such. I'm not certain either of those is strictly required
but I'd do them anyway.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Mon, Oct 14, 2013 at 10:40 AM, Stephan Mueller  wrote:

> Another thing: when you start adding whitening functions, other people
> are starting (and did -- thus I added section 4.3 to my documentation)
> to complain that you hide your weaknesses behind the whiteners. I simply
> want to counter that argument and show that RNG produces white noise
> without a whitener.

Yes, you absolutely have to test the unwhitened input entropy, and
provide a way for others to test it so they can have confidence in your
code and it can be tested again if it is going to be used on some new
host. You do a fine job of that; your paper has the most detailed
analysis I have seen. Bravo.

However, having done that, I see no reason not to add mixing.
Using bit() for getting one bit of input and rotl(x) for rotating
left one bit, your code is basically, with 64-bit x:

   for( i=0, x = 0 ; i < 64; i++, x =rotl(x) )
x |= bit()

Why not declare some 64-bit constant C with a significant
number of bits set and do this:

   for( i=0, x = 0 ; i < 64; i++, x =rotl(x) ) // same loop control
  if( bit() ) x ^= C ;

This makes every output bit depend on many input bits
and costs almost nothing extra.

In the unlikely event that the overhead here matters,
your deliberately inefficient parity calculation in bit()
could easily be made faster to compensate.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris  wrote:

> Stephan Mueller  wrote:

>> Can you please help me understand why you think that a whitening
>> function (cryptographic or not) is needed in the case of the CPU Jitter
>> RNG, provided that I can show that each individual bit coming from the
>> folding operation has one bit of entropy?
>
> Basically, sheer paranoia. I'd mix and whiten just on general
> principles. Since efficiency is not a large concern, there is little
> reason not to.
>
> On the other hand, most RNGs use a hash because they need
> to distill some large amount of low-entropy input into a smaller
> high-entropy output. With high input entropy, you do not need
> the hash and can choose some cheaper mixer.

You could use strong mixing/whitening:

Feed into random(4) and let it do the mixing.

Use some early outputs from your RNG to key an AES
instance. Then encrypt later outputs; this gives a 64 in 64
out mixer that is cryptographically strong but perhaps a bit
slow in the context.

Alternately, quite a few plausible components for fast cheap
mixing are readily available.

The Aria cipher has one that is 128 in 128 out. It multiplies
a 128-bit object by a fixed Boolean matrix, makes every
output bit depend on many input bits. It is fairly cheap,
used in every round and the cipher is acceptably fast.

The column transform from AES is 32 in 32 out and makes
every output byte depend on every input byte. It is fast; has
to be since it is used four times in every round.

A two-way pseudo-Hadamard transform (PHT) is 2n bits in
and 2n out, requires only two additions, makes both n-bit
outputs depend on both inputs.

PHT can be applied recursively to mix 4n, 8n, ...

My QHT is 32 in 32 out, makes every /bit/ of output
depend on every bit of input. It is a tad expensive;
two multiplications & two modulo operations. File
qht.c at:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

To mix 64 bits, I'd use two qht() calls to mix the 32-bit
halves then a two-way PHT.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

Stephan Mueller  wrote:

>>Paper has:
>>
>>" the time delta is partitioned into chunks of 1 bit starting at the
>>lowest bit "  The 64 1 bit chunks of the time value are XORed with
>>each other to " form a 1 bit value.
>>
>>As I read that, you are just taking the parity. Why not use that
>>simpler description & possibly one of several possible optimised
>>algorithms for the task:
>>http://graphics.stanford.edu/~seander/bithacks.html
>
> I am fully aware that the bit operation is inefficient. Yet it is
> deliberately inefficient, because that "folding loop" performs actual
> work for the RNG (the collapse of 64 bits into one bit) and at the very
> same time, it is the fixed instruction set over which I measure the time
> variations.
>
> Thus, the folding loop can be considered as the entropy source ...
>
> As the RNG is not primarily about speed, the folding operation should
> stay inefficient.

OK, that makes sense.

>>If what you are doing is not a parity computation, then you need a
>>better description so people like me do not misread it.
>
> It is not a parity computation that the folding loop performs. The code
> XORs each individual bit of the 64 bit stream with each other, whereas
> your cited document implies an ANDing of the bits (see section
> "Computing parity the naive way" of the cited document).

No. The AND is used in a trick; x&(x-1) gives a value with exactly
one bit set, the lowest bit set in x. The code there just counts that
way for efficiency.

Parity asks whether the number of set bits is odd or even. For
example this is another way to find the parity of x.

   for( p = 0; x ; x >>= 1 )
 p ^= (x&1) ;

>From your description (I haven't looked at the code) you are
computing parity. If so, say that. If not, explain.

>>This appears to be missing the cryptographically strong
>>mixing step which most RNG code includes. If that is
>>what you are doing, you need to provide some strong
>>arguments to justify it.
>
> The key here is that there is no cryptographic function needed for
> mixing as in fact I am not really mixing things. I am simply
> concatenating the new bit to the previously obtained bits. That is it.
>
> The argument for doing that is that the time deltas are independent of
> each other. ...

> ... each bit from the folding operation therefore contains
> one bit of entropy. So, why should I mix it even further with some
> crypto function?

That does make sense, but in security code I tend to prefer a
belt-and-suspenders approach. Even believing that each
individual bit is truly random, I'd still mix some just in case.

> Can you please help me understand why you think that a whitening
> function (cryptographic or not) is needed in the case of the CPU Jitter
> RNG, provided that I can show that each individual bit coming from the
> folding operation has one bit of entropy?

Basically, sheer paranoia. I'd mix and whiten just on general
principles. Since efficiency is not a large concern, there is little
reason not to.

On the other hand, most RNGs use a hash because they need
to distill some large amount of low-entropy input into a smaller
high-entropy output. With high input entropy, you do not need
the hash and can choose some cheaper mixer.

>>> I will present the RNG at the Linux Symposium in Ottawa this year.
>>> 
>>
>>I live in Ottawa, ...
>
> As mentioned before, I would really like to meet you there to have a cup
> of coffee over that matter.

Sounds good. Ted, will you be around?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Fwd: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

Stephan Mueller smuel...@chronox.de wrote:

Paper has:

 the time delta is partitioned into chunks of 1 bit starting at the
lowest bit   The 64 1 bit chunks of the time value are XORed with
each other to  form a 1 bit value.

As I read that, you are just taking the parity. Why not use that
simpler description  possibly one of several possible optimised
algorithms for the task:
http://graphics.stanford.edu/~seander/bithacks.html

 I am fully aware that the bit operation is inefficient. Yet it is
 deliberately inefficient, because that folding loop performs actual
 work for the RNG (the collapse of 64 bits into one bit) and at the very
 same time, it is the fixed instruction set over which I measure the time
 variations.

 Thus, the folding loop can be considered as the entropy source ...

 As the RNG is not primarily about speed, the folding operation should
 stay inefficient.

OK, that makes sense.

If what you are doing is not a parity computation, then you need a
better description so people like me do not misread it.

 It is not a parity computation that the folding loop performs. The code
 XORs each individual bit of the 64 bit stream with each other, whereas
 your cited document implies an ANDing of the bits (see section
 Computing parity the naive way of the cited document).

No. The AND is used in a trick; x(x-1) gives a value with exactly
one bit set, the lowest bit set in x. The code there just counts that
way for efficiency.

Parity asks whether the number of set bits is odd or even. For
example this is another way to find the parity of x.

   for( p = 0; x ; x = 1 )
 p ^= (x1) ;

From your description (I haven't looked at the code) you are
computing parity. If so, say that. If not, explain.

This appears to be missing the cryptographically strong
mixing step which most RNG code includes. If that is
what you are doing, you need to provide some strong
arguments to justify it.

 The key here is that there is no cryptographic function needed for
 mixing as in fact I am not really mixing things. I am simply
 concatenating the new bit to the previously obtained bits. That is it.

 The argument for doing that is that the time deltas are independent of
 each other. ...

 ... each bit from the folding operation therefore contains
 one bit of entropy. So, why should I mix it even further with some
 crypto function?

That does make sense, but in security code I tend to prefer a
belt-and-suspenders approach. Even believing that each
individual bit is truly random, I'd still mix some just in case.

 Can you please help me understand why you think that a whitening
 function (cryptographic or not) is needed in the case of the CPU Jitter
 RNG, provided that I can show that each individual bit coming from the
 folding operation has one bit of entropy?

Basically, sheer paranoia. I'd mix and whiten just on general
principles. Since efficiency is not a large concern, there is little
reason not to.

On the other hand, most RNGs use a hash because they need
to distill some large amount of low-entropy input into a smaller
high-entropy output. With high input entropy, you do not need
the hash and can choose some cheaper mixer.

 I will present the RNG at the Linux Symposium in Ottawa this year.
 

I live in Ottawa, ...

 As mentioned before, I would really like to meet you there to have a cup
 of coffee over that matter.

Sounds good. Ted, will you be around?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Mon, Oct 14, 2013 at 9:38 AM, Sandy Harris sandyinch...@gmail.com wrote:

 Stephan Mueller smuel...@chronox.de wrote:

 Can you please help me understand why you think that a whitening
 function (cryptographic or not) is needed in the case of the CPU Jitter
 RNG, provided that I can show that each individual bit coming from the
 folding operation has one bit of entropy?

 Basically, sheer paranoia. I'd mix and whiten just on general
 principles. Since efficiency is not a large concern, there is little
 reason not to.

 On the other hand, most RNGs use a hash because they need
 to distill some large amount of low-entropy input into a smaller
 high-entropy output. With high input entropy, you do not need
 the hash and can choose some cheaper mixer.

You could use strong mixing/whitening:

Feed into random(4) and let it do the mixing.

Use some early outputs from your RNG to key an AES
instance. Then encrypt later outputs; this gives a 64 in 64
out mixer that is cryptographically strong but perhaps a bit
slow in the context.

Alternately, quite a few plausible components for fast cheap
mixing are readily available.

The Aria cipher has one that is 128 in 128 out. It multiplies
a 128-bit object by a fixed Boolean matrix, makes every
output bit depend on many input bits. It is fairly cheap,
used in every round and the cipher is acceptably fast.

The column transform from AES is 32 in 32 out and makes
every output byte depend on every input byte. It is fast; has
to be since it is used four times in every round.

A two-way pseudo-Hadamard transform (PHT) is 2n bits in
and 2n out, requires only two additions, makes both n-bit
outputs depend on both inputs.

PHT can be applied recursively to mix 4n, 8n, ...

My QHT is 32 in 32 out, makes every /bit/ of output
depend on every bit of input. It is a tad expensive;
two multiplications  two modulo operations. File
qht.c at:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

To mix 64 bits, I'd use two qht() calls to mix the 32-bit
halves then a two-way PHT.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Mon, Oct 14, 2013 at 10:40 AM, Stephan Mueller smuel...@chronox.de wrote:

 Another thing: when you start adding whitening functions, other people
 are starting (and did -- thus I added section 4.3 to my documentation)
 to complain that you hide your weaknesses behind the whiteners. I simply
 want to counter that argument and show that RNG produces white noise
 without a whitener.

Yes, you absolutely have to test the unwhitened input entropy, and
provide a way for others to test it so they can have confidence in your
code and it can be tested again if it is going to be used on some new
host. You do a fine job of that; your paper has the most detailed
analysis I have seen. Bravo.

However, having done that, I see no reason not to add mixing.
Using bit() for getting one bit of input and rotl(x) for rotating
left one bit, your code is basically, with 64-bit x:

   for( i=0, x = 0 ; i  64; i++, x =rotl(x) )
x |= bit()

Why not declare some 64-bit constant C with a significant
number of bits set and do this:

   for( i=0, x = 0 ; i  64; i++, x =rotl(x) ) // same loop control
  if( bit() ) x ^= C ;

This makes every output bit depend on many input bits
and costs almost nothing extra.

In the unlikely event that the overhead here matters,
your deliberately inefficient parity calculation in bit()
could easily be made faster to compensate.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Mon, Oct 14, 2013 at 11:26 AM, Stephan Mueller smuel...@chronox.de wrote:

Why not declare some 64-bit constant C with a significant

 Which constant would you take? The CRC twist values? The SHA-1 initial
 values? Or the first few from SHA-256?

The only essential requirement is that it not be something stupidly
regular like a 64-bit string 0x.

I'd pick an odd number so the low bit always changes, and a
constant with about half the bits set, maybe 24  n  40 or
some such. I'm not certain either of those is strictly required
but I'd do them anyway.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

Stephan Mueller smuel...@chronox.de wrote:

 [quoting me]

 ...your code is basically, with 64-bit x:

   for( i=0, x = 0 ; i  64; i++, x =rotl(x) )
x |= bit()

 Why not declare some 64-bit constant C with a significant
number of bits set and do this:

   for( i=0, x = 0 ; i  64; i++, x =rotl(x) ) // same loop control
  if( bit() ) x ^= C ;

This makes every output bit depend on many input bits
and costs almost nothing extra.

 Ok, let me play a bit with that. Maybe I can add another flag to the
 allocation function so that the caller can decide whether to use that.
 If the user is another RNG, you skip that mixing function, otherwise you
 should take it.

I'd say just do it. It is cheap enough and using it does no harm
even where it is not strictly needed. Adding a flag just gives the
calling code a chance to get it wrong. Better not to take that risk
if you don't have to.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Fri, Oct 11, 2013 at 2:38 PM, Stephan Mueller  wrote:

I like the basic idea. Here I'm alternately reading the email and the
page you link to & commenting on both.

A nitpick in the paper is that you cite RFC 1750. That was superceded
some years back by RFC 4086
http://tools.ietf.org/html/rfc4086

(Ted's comments in the actual driver had the same problem last
I looked. That is excusable since they were written long ago.)

I think you may be missing some other citations that should be
there, to previous work along similar lines. One is the HAVEGE
work, another:
McGuire, Okech & Schiesser,
Analysis of inherent randomness of the Linux kernel,
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

Paper has:

" the time delta is partitioned into chunks of 1 bit starting at the lowest bit
"  The 64 1 bit chunks of the time value are XORed with each other to
" form a 1 bit value.

As I read that, you are just taking the parity. Why not use that simpler
description & possibly one of several possible optimised algorithms
for the task: http://graphics.stanford.edu/~seander/bithacks.html

If what you are doing is not a parity computation, then you need a
better description so people like me do not misread it.

A bit later you have:

" After obtaining the 1 bit folded and unbiased time stamp,
" how is it mixed into the entropy pool? ... The 1 bit folded
" value is XORed with 1 bit from the entropy pool.

This appears to be missing the cryptographically strong
mixing step which most RNG code includes. If that is
what you are doing, you need to provide some strong
arguments to justify it.

Sometimes doing without is justified; for example my
code along these lines
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/
does more mixing than I see in yours, but probably
not enough overall. That's OK because I am just
feeding into /dev/random which has plenty of
mixing.

It is OK for your code too if you are feeding into
/dev/random, but it looks problematic if your code
is expected to stand alone.

Ah! You talk about whitening a bit later. However,
you seem to make it optional, up to the user. I
cannot see that that is a good idea.

At the very least I think you need something like
the linear transform from the ARIA cipher -- fast
and cheap, 128 bits in & 128 out and it makes
every output bit depend on every input bit. That
might not be enough, though.

You require compilation without optimisation. How does
that interact with kernel makefiles? Can you avoid
undesirable optimisations in some other way, such as
volatile declartions?

> I am asking whether this RNG would good as an inclusion into the Linux
> kernel for:
>
> - kernel crypto API to provide a true random number generator as part of
> this API (see [2] appendix B for a description)

My first reaction is no. We have /dev/random for the userspace
API and there is a decent kernel API too. I may change my
mind here as I look more at your appendix & maybe the code.

> - inclusion into /dev/random as an entropy provider of last resort when
> the entropy estimator falls low.

Why only 'of last resort'? If it can provide good entropy, we should
use it often.

> I will present the RNG at the Linux Symposium in Ottawa this year. There
> I can give a detailed description of the design and testing.

I live in Ottawa, don't know if I'll make it to the Symposium this
year. Ted; I saw you at one Symposium; are you coming this
year?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] CPU Jitter RNG: inclusion into kernel crypto API and /dev/random

[Sandy Harris]

On Fri, Oct 11, 2013 at 2:38 PM, Stephan Mueller smuel...@chronox.de wrote:

I like the basic idea. Here I'm alternately reading the email and the
page you link to  commenting on both.

A nitpick in the paper is that you cite RFC 1750. That was superceded
some years back by RFC 4086
http://tools.ietf.org/html/rfc4086

(Ted's comments in the actual driver had the same problem last
I looked. That is excusable since they were written long ago.)

I think you may be missing some other citations that should be
there, to previous work along similar lines. One is the HAVEGE
work, another:
McGuire, Okech  Schiesser,
Analysis of inherent randomness of the Linux kernel,
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

Paper has:

 the time delta is partitioned into chunks of 1 bit starting at the lowest bit
  The 64 1 bit chunks of the time value are XORed with each other to
 form a 1 bit value.

As I read that, you are just taking the parity. Why not use that simpler
description  possibly one of several possible optimised algorithms
for the task: http://graphics.stanford.edu/~seander/bithacks.html

If what you are doing is not a parity computation, then you need a
better description so people like me do not misread it.

A bit later you have:

 After obtaining the 1 bit folded and unbiased time stamp,
 how is it mixed into the entropy pool? ... The 1 bit folded
 value is XORed with 1 bit from the entropy pool.

This appears to be missing the cryptographically strong
mixing step which most RNG code includes. If that is
what you are doing, you need to provide some strong
arguments to justify it.

Sometimes doing without is justified; for example my
code along these lines
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/
does more mixing than I see in yours, but probably
not enough overall. That's OK because I am just
feeding into /dev/random which has plenty of
mixing.

It is OK for your code too if you are feeding into
/dev/random, but it looks problematic if your code
is expected to stand alone.

Ah! You talk about whitening a bit later. However,
you seem to make it optional, up to the user. I
cannot see that that is a good idea.

At the very least I think you need something like
the linear transform from the ARIA cipher -- fast
and cheap, 128 bits in  128 out and it makes
every output bit depend on every input bit. That
might not be enough, though.

You require compilation without optimisation. How does
that interact with kernel makefiles? Can you avoid
undesirable optimisations in some other way, such as
volatile declartions?

 I am asking whether this RNG would good as an inclusion into the Linux
 kernel for:

 - kernel crypto API to provide a true random number generator as part of
 this API (see [2] appendix B for a description)

My first reaction is no. We have /dev/random for the userspace
API and there is a decent kernel API too. I may change my
mind here as I look more at your appendix  maybe the code.

 - inclusion into /dev/random as an entropy provider of last resort when
 the entropy estimator falls low.

Why only 'of last resort'? If it can provide good entropy, we should
use it often.

 I will present the RNG at the Linux Symposium in Ottawa this year. There
 I can give a detailed description of the design and testing.

I live in Ottawa, don't know if I'll make it to the Symposium this
year. Ted; I saw you at one Symposium; are you coming this
year?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][RFC] CPU Jitter random number generator (resent)

[Sandy Harris]

Stephan Mueller  wrote:

> Ted is right that the non-deterministic behavior is caused by the OS
> due to its complexity. ...

>> >  For VM's, it means we should definitely use
>> > paravirtualization to get randomness from the host OS.
>> ...
>
> That is already in place at least with KVM and Xen as QEMU can pass
> through access to the host /dev/random to the guest. Yet, that approach
> is dangerous IMHO because you have one central source of entropy for
> the host and all guests. One guest can easily starve all other guests
> and the host of entropy. I know that is the case in user space as well.

Yes, I have always thought that random(4) had a problem in that
area; over-using /dev/urandom can affect /dev/random. I've never
come up with a good way to fix it, though.

> That is why I am offering an implementation that is able to
> decentralize the entropy collection process. I think it would be wrong
> to simply update /dev/random with another seed source of the CPU
> jitter -- it could be done as one aspect to increase the entropy in
> the system. I think users should slowly but surely instantiate their own
> instance of an entropy collector.

I'm not sure that's a good idea. Certainly for many apps just seeding
a per-process PRNG well is enough, and a per-VM random device
looks essential, though there are at least two problems possible
because random(4) was designed before VMs were at all common
so it is not clear it can cope with that environment. The host
random device may be overwhelmed, and the guest entropy may
be inadequate or mis-estimated because everything it relies on --
devices, interrupts, ... -- is virtualised.

I want to keep the current interface where a process can just
read /dev/random or /dev/urandom as required. It is clean,
simple and moderately hard for users to screw up. It may
need some behind-the-scenes improvements to handle new
loads, but I cannot see changing the interface itself.

> I would personally think that precisely for routers, the approach
> fails, because there may be no high-resolution timer. At least trying
> to execute my code on a raspberry pie resulted in a failure: the
> initial jent_entropy_init() call returned with the indication that
> there is no high-res timer.

My maxwell(8) uses the hi-res timer by default but also has a
compile-time option to use the lower-res timer if required. You
still get entropy, just not as much.

This affects more than just routers. Consider using Linux on
a tablet PC or in a web server running in a VM. Neither needs
the realtime library; in fact adding that may move them away
from their optimisation goals.

>> > What I'm against is relying only on solutions such as HAVEGE or
>> > replacing /dev/random with something scheme that only relies on CPU
>> > timing and ignores interrupt timing.
>>
>> My question is how to incorporate some of that into /dev/random.
>> At one point, timing info was used along with other stuff. Some
>> of that got deleted later, What is the current state? Should we
>> add more?
>
> Again, I would like to suggest that we look beyond a central entropy
> collector like /dev/random. I would like to suggest to consider
> decentralizing the collection of entropy.

I'm with Ted on this one.

--
Who put a stop payment on my reality check?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][RFC] CPU Jitter random number generator (resent)

[Sandy Harris]

Stephan Mueller smuel...@chronox.de wrote:

 Ted is right that the non-deterministic behavior is caused by the OS
 due to its complexity. ...

   For VM's, it means we should definitely use
  paravirtualization to get randomness from the host OS.
 ...

 That is already in place at least with KVM and Xen as QEMU can pass
 through access to the host /dev/random to the guest. Yet, that approach
 is dangerous IMHO because you have one central source of entropy for
 the host and all guests. One guest can easily starve all other guests
 and the host of entropy. I know that is the case in user space as well.

Yes, I have always thought that random(4) had a problem in that
area; over-using /dev/urandom can affect /dev/random. I've never
come up with a good way to fix it, though.

 That is why I am offering an implementation that is able to
 decentralize the entropy collection process. I think it would be wrong
 to simply update /dev/random with another seed source of the CPU
 jitter -- it could be done as one aspect to increase the entropy in
 the system. I think users should slowly but surely instantiate their own
 instance of an entropy collector.

I'm not sure that's a good idea. Certainly for many apps just seeding
a per-process PRNG well is enough, and a per-VM random device
looks essential, though there are at least two problems possible
because random(4) was designed before VMs were at all common
so it is not clear it can cope with that environment. The host
random device may be overwhelmed, and the guest entropy may
be inadequate or mis-estimated because everything it relies on --
devices, interrupts, ... -- is virtualised.

I want to keep the current interface where a process can just
read /dev/random or /dev/urandom as required. It is clean,
simple and moderately hard for users to screw up. It may
need some behind-the-scenes improvements to handle new
loads, but I cannot see changing the interface itself.

 I would personally think that precisely for routers, the approach
 fails, because there may be no high-resolution timer. At least trying
 to execute my code on a raspberry pie resulted in a failure: the
 initial jent_entropy_init() call returned with the indication that
 there is no high-res timer.

My maxwell(8) uses the hi-res timer by default but also has a
compile-time option to use the lower-res timer if required. You
still get entropy, just not as much.

This affects more than just routers. Consider using Linux on
a tablet PC or in a web server running in a VM. Neither needs
the realtime library; in fact adding that may move them away
from their optimisation goals.

  What I'm against is relying only on solutions such as HAVEGE or
  replacing /dev/random with something scheme that only relies on CPU
  timing and ignores interrupt timing.

 My question is how to incorporate some of that into /dev/random.
 At one point, timing info was used along with other stuff. Some
 of that got deleted later, What is the current state? Should we
 add more?

 Again, I would like to suggest that we look beyond a central entropy
 collector like /dev/random. I would like to suggest to consider
 decentralizing the collection of entropy.

I'm with Ted on this one.

--
Who put a stop payment on my reality check?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][RFC] CPU Jitter random number generator (resent)

[Sandy Harris]

On Tue, May 21, 2013 at 3:01 PM, Theodore Ts'o  wrote:

> I continue to be suspicious about claims that userspace timing
> measurements are measuring anything other than OS behaviour.

Yes, but they do seem to contain some entropy. See links in the
original post of this thread, the havege stuff and especially the
McGuire et al paper.

>  But that
> doesn't mean that they shouldn't exist.  Personally, I believe you
> should try to collect as much entropy as you can, from as many places
> as you can.

Yes.

>  For VM's, it means we should definitely use
> paravirtualization to get randomness from the host OS.

Yes, I have not worked out the details but it seems clear that
something along those lines would be a fine idea.

> For devices like Linux routers, what we desperately need is hardware
> assist;  [or] mix
> in additional timing information either at kernel device driver level,
> or from systems such as HAVEGE.
>
> What I'm against is relying only on solutions such as HAVEGE or
> replacing /dev/random with something scheme that only relies on CPU
> timing and ignores interrupt timing.

My question is how to incorporate some of that into /dev/random.
At one point, timing info was used along with other stuff. Some
of that got deleted later, What is the current state? Should we
add more?

--
Who put a stop payment on my reality check?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][RFC] CPU Jitter random number generator (resent)

[Sandy Harris]

I very much like the basic notion here. The existing random(4) driver
may not get enough entropy in a VM or on a device like a Linux router
and I think work such as yours or HAVEGE
(http://www.irisa.fr/caps/projects/hipsor/) are important research.
The paper by McGuire et al of "Analysis of inherent randomness of the
Linux kernel" (http://lwn.net/images/conf/rtlws11/random-hardware.pdf)
seems to show that this is a fine source of more entropy.

On the other hand, I am not certain you are doing it in the right
place. My own attempt (ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/)
put it in a demon that just feeds /dev/random, probably also not the
right place. haveged(8) (http://www.issihosts.com/haveged/) also puts
it in a demon process. It may, as you suggest, belong in the kernel
instead, but I think there are arguments both ways.

Could we keep random(4) mostly as is and rearrange your code to just
give it more entropy? I think the large entropy pool in the existing
driver is essential since we sometimes want to generate things like a
2 Kbit PGP key and it is not clear to me that your driver is entirely
trustworthy under such stress.

On Tue, May 21, 2013 at 2:44 AM, Stephan Mueller  wrote:
> Hi,
>
> [1] patch at http://www.chronox.de/jent/jitterentropy-20130516.tar.bz2
>
> A new version of the CPU Jitter random number generator is released at
> http://www.chronox.de/ . The heart of the RNG is about 30 lines of easy
> to read code. The readme in the main directory explains the different
> code files. A changelog can be found on the web site.
>
> In a previous attempt (http://lkml.org/lkml/2013/2/8/476), the first
> iteration received comments for the lack of tests, documentation and
> entropy assessment. All these concerns have been addressed. The
> documentation of the CPU Jitter random number generator
> (http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html and PDF at
> http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf -- the graphs and
> pictures are better in PDF) offers a full analysis of:
>
> - the root cause of entropy
>
> - a design of the RNG
>
> - statistical tests and analyses
>
> - entropy assessment and explanation of the flow of entropy
>
> The document also explains the core concept to have a fully
> decentralized entropy collector for every caller in need of entropy.
>
> Also, this RNG is well suitable for virtualized environments.
> Measurements on OpenVZ and KVM environments have been conducted as
> documented. As the Linux kernel is starved of entropy in virtualized as
> well as server environments, new sources of entropy are vital.
>
> The appendix of the documentation contains example use cases by
> providing link code to the Linux kernel crypto API, libgcrypt and
> OpenSSL. Links to other cryptographic libraries should be straight
> forward to implement. These implementations follow the concept of
> decentralized entropy collection.
>
> The man page provided with the source code explains the use of the API
> of the CPU Jitter random number generator.
>
> The test cases used to compile the documentation are available at the
> web site as well.
>
> Note: for the kernel crypto API, please read the provided Kconfig file
> for the switches and which of them are recommended in regular
> operation. These switches must currently be set manually in the
> Makefile.
>
> Ciao
> Stephan
>
> Signed-off-by: Stephan Mueller 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majord...@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Who put a stop payment on my reality check?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][RFC] CPU Jitter random number generator (resent)

[Sandy Harris]

I very much like the basic notion here. The existing random(4) driver
may not get enough entropy in a VM or on a device like a Linux router
and I think work such as yours or HAVEGE
(http://www.irisa.fr/caps/projects/hipsor/) are important research.
The paper by McGuire et al of Analysis of inherent randomness of the
Linux kernel (http://lwn.net/images/conf/rtlws11/random-hardware.pdf)
seems to show that this is a fine source of more entropy.

On the other hand, I am not certain you are doing it in the right
place. My own attempt (ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/)
put it in a demon that just feeds /dev/random, probably also not the
right place. haveged(8) (http://www.issihosts.com/haveged/) also puts
it in a demon process. It may, as you suggest, belong in the kernel
instead, but I think there are arguments both ways.

Could we keep random(4) mostly as is and rearrange your code to just
give it more entropy? I think the large entropy pool in the existing
driver is essential since we sometimes want to generate things like a
2 Kbit PGP key and it is not clear to me that your driver is entirely
trustworthy under such stress.

On Tue, May 21, 2013 at 2:44 AM, Stephan Mueller smuel...@chronox.de wrote:
 Hi,

 [1] patch at http://www.chronox.de/jent/jitterentropy-20130516.tar.bz2

 A new version of the CPU Jitter random number generator is released at
 http://www.chronox.de/ . The heart of the RNG is about 30 lines of easy
 to read code. The readme in the main directory explains the different
 code files. A changelog can be found on the web site.

 In a previous attempt (http://lkml.org/lkml/2013/2/8/476), the first
 iteration received comments for the lack of tests, documentation and
 entropy assessment. All these concerns have been addressed. The
 documentation of the CPU Jitter random number generator
 (http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html and PDF at
 http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf -- the graphs and
 pictures are better in PDF) offers a full analysis of:

 - the root cause of entropy

 - a design of the RNG

 - statistical tests and analyses

 - entropy assessment and explanation of the flow of entropy

 The document also explains the core concept to have a fully
 decentralized entropy collector for every caller in need of entropy.

 Also, this RNG is well suitable for virtualized environments.
 Measurements on OpenVZ and KVM environments have been conducted as
 documented. As the Linux kernel is starved of entropy in virtualized as
 well as server environments, new sources of entropy are vital.

 The appendix of the documentation contains example use cases by
 providing link code to the Linux kernel crypto API, libgcrypt and
 OpenSSL. Links to other cryptographic libraries should be straight
 forward to implement. These implementations follow the concept of
 decentralized entropy collection.

 The man page provided with the source code explains the use of the API
 of the CPU Jitter random number generator.

 The test cases used to compile the documentation are available at the
 web site as well.

 Note: for the kernel crypto API, please read the provided Kconfig file
 for the switches and which of them are recommended in regular
 operation. These switches must currently be set manually in the
 Makefile.

 Ciao
 Stephan

 Signed-off-by: Stephan Mueller smuel...@chronox.de
 --
 To unsubscribe from this list: send the line unsubscribe linux-crypto in
 the body of a message to majord...@vger.kernel.org
 More majordomo info at  http://vger.kernel.org/majordomo-info.html



-- 
Who put a stop payment on my reality check?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH][RFC] CPU Jitter random number generator (resent)

[Sandy Harris]

On Tue, May 21, 2013 at 3:01 PM, Theodore Ts'o ty...@mit.edu wrote:

 I continue to be suspicious about claims that userspace timing
 measurements are measuring anything other than OS behaviour.

Yes, but they do seem to contain some entropy. See links in the
original post of this thread, the havege stuff and especially the
McGuire et al paper.

  But that
 doesn't mean that they shouldn't exist.  Personally, I believe you
 should try to collect as much entropy as you can, from as many places
 as you can.

Yes.

  For VM's, it means we should definitely use
 paravirtualization to get randomness from the host OS.

Yes, I have not worked out the details but it seems clear that
something along those lines would be a fine idea.

 For devices like Linux routers, what we desperately need is hardware
 assist;  [or] mix
 in additional timing information either at kernel device driver level,
 or from systems such as HAVEGE.

 What I'm against is relying only on solutions such as HAVEGE or
 replacing /dev/random with something scheme that only relies on CPU
 timing and ignores interrupt timing.

My question is how to incorporate some of that into /dev/random.
At one point, timing info was used along with other stuff. Some
of that got deleted later, What is the current state? Should we
add more?

--
Who put a stop payment on my reality check?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

[Sandy Harris]

On Thu, Feb 21, 2013 at 9:17 AM, Stephan Mueller  wrote:

> There is no state between calls. Of course, you need a scratchpad to do
> calculations.

But in general you need a buffer. It is quite easy to construct scenarios where
several K bits of entropy are needed very -- for example, reboot an IPsec
gateway the supports a few dozen tunnels and needs a few hundred bits
to rekey each. Without state, it is quite difficult to demonstrate that you can
meet such requirements. Given a reasonable size of buffer, some saved
random data and the assumption that the enemy does not already have
root on your server, it is trivial.

> ... I am working on showing that the jitter has entropy. I
> will come back.

I think that has already been shown. See the McGuire et al. paper
I cited earlier in the thread and the HAVEGE papers. Of course it
needs more analysis to be sure we have really good estimates of
that entropy, but it seems clear there is some at any rate.

>> Entropy harvesting is quite hard - entropy estimation is unimaginably harder.

Yes.

> This is a statement that does not make sense. You CANNOT per definition
> calculate entropy!

The question is not /calculating/ it, but /estimating/ it. That is a perfectly
reasonable thing to do, and it is done in most generators. It is a hard
problem, though, and requires care in both design and implementation.

Also, in some designs it is possible to get very close to calculating
entropy. The Turbid generator, for example, uses physical measurements
of sound card properties plus arguments from standard circuit physics to
prove a lower bound on the Johnson noise that must exist in the circuit.
>From that plus some quite moderate assumptions about properties of
the hash, you get a provable lower bound on output entropy.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

[Sandy Harris]

On Thu, Feb 21, 2013 at 9:17 AM, Stephan Mueller smuel...@chronox.de wrote:

 There is no state between calls. Of course, you need a scratchpad to do
 calculations.

But in general you need a buffer. It is quite easy to construct scenarios where
several K bits of entropy are needed very -- for example, reboot an IPsec
gateway the supports a few dozen tunnels and needs a few hundred bits
to rekey each. Without state, it is quite difficult to demonstrate that you can
meet such requirements. Given a reasonable size of buffer, some saved
random data and the assumption that the enemy does not already have
root on your server, it is trivial.

 ... I am working on showing that the jitter has entropy. I
 will come back.

I think that has already been shown. See the McGuire et al. paper
I cited earlier in the thread and the HAVEGE papers. Of course it
needs more analysis to be sure we have really good estimates of
that entropy, but it seems clear there is some at any rate.

 Entropy harvesting is quite hard - entropy estimation is unimaginably harder.

Yes.

 This is a statement that does not make sense. You CANNOT per definition
 calculate entropy!

The question is not /calculating/ it, but /estimating/ it. That is a perfectly
reasonable thing to do, and it is done in most generators. It is a hard
problem, though, and requires care in both design and implementation.

Also, in some designs it is possible to get very close to calculating
entropy. The Turbid generator, for example, uses physical measurements
of sound card properties plus arguments from standard circuit physics to
prove a lower bound on the Johnson noise that must exist in the circuit.
From that plus some quite moderate assumptions about properties of
the hash, you get a provable lower bound on output entropy.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

[Sandy Harris]

On Sun, Feb 10, 2013 at 2:32 PM, Stephan Mueller  wrote:

> On 10.02.2013 19:50:02, +0100, Theodore Ts'o  wrote:

> Given all your doubts on the high-precision timer, how can you
> reasonably state that the Linux kernel RNG is good then?
>
> The data from add_timer_randomness the kernel feeds into the input_pool
> is a concatenation of the event value, the jiffies and the get_cycles()
> value. The events hardly contains any entropy, the jiffies a little bit
> due to the coarse resolution of 250 or 1000 Hz. Only the processor
> cycles value provides real entropy.

There are multiple sources of entropy, though. There are reasons
not to fully trust any -- key strike statistics can be predicted if the
enemy knows the language, the enemy might be monitoring the
network. there is no keyboard or mouse on a headless server, a
diskless machine has no disk timing entropy and one with an
SSD or intelligent RAID controller very little,  However, with
multiple sources and conservative estimates, it is reasonable
to hope there is enough entropy coming in somewhere.

It is much harder to trust a system with single source of
entropy, perhaps impossible for something that is likely to
be deployed on the whole range of things Linux runs on,
from a cell phone with a single 32-bit CPU all the way to
beowulf-based supercomputers with thousands of
multicore chips.

Moeove, random(4) has both a large entropy pool (or
three, to be more precise) and strong crypto in the
mixing. If it /ever/ gets a few hundred bits of real
entropy then no-one without the resources of a
major government and/or a brilliant unpublished
attack on SHA-1 can even hope to break it.

In the default Linux setup, it gets few K bits of
reasonably good entropy from the initialisation
scripts, so attacks look impossible unless the
enemy already has root privileges or has
physical access to boot the machine from
other media & look at Linux storage.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

[Sandy Harris]

On Sun, Feb 10, 2013 at 1:50 PM, Theodore Ts'o  wrote:

> On Sun, Feb 10, 2013 at 01:46:18PM +0100, Stephan Mueller wrote:
>>
>> However, the CPU has timing jitter in the execution of instruction. And
>> I try to harvest that jitter. The good thing is that this jitter is
>> always present and can be harvested on demand.
>
> How do you know, though, that this is what you are harvesting?
> ...
> And what's your proof that your entropy source really is an entropy
> source?

One paper that seems to show there is some randomness in
such measurements is McGuire, Okech & Schiesser
"Analysis of inherent randomness of the Linux kernel",
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

They do two clock calls with a usleep() between, take the
low bit of the difference and pack them unmixed into
bytes for testing. Their tests show over 7.5 bits of entropy
per byte, even with interrupts disabled. The same paper
shows that simple arithmetic sequences give some
apparent entropy, due to TLB misses, interrupts, etc.

There are lots of caveats in how this should be used and
it is unclear how much real entropy it gives, but is seems
clear it gives some.

My own program to feed into random(4) is based on
such things:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

HAVEGE also uses them
http://www.irisa.fr/caps/projects/hipsor/
& there is a havegd daemon for Linux
http://www.issihosts.com/haveged/

random(4) also mixed in timer data at one point,
which seems the correct thing for it to do. Later
I heard something about that code having been
removed. What is the current status?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

[Sandy Harris]

On Sun, Feb 10, 2013 at 1:50 PM, Theodore Ts'o ty...@mit.edu wrote:

 On Sun, Feb 10, 2013 at 01:46:18PM +0100, Stephan Mueller wrote:

 However, the CPU has timing jitter in the execution of instruction. And
 I try to harvest that jitter. The good thing is that this jitter is
 always present and can be harvested on demand.

 How do you know, though, that this is what you are harvesting?
 ...
 And what's your proof that your entropy source really is an entropy
 source?

One paper that seems to show there is some randomness in
such measurements is McGuire, Okech  Schiesser
Analysis of inherent randomness of the Linux kernel,
http://lwn.net/images/conf/rtlws11/random-hardware.pdf

They do two clock calls with a usleep() between, take the
low bit of the difference and pack them unmixed into
bytes for testing. Their tests show over 7.5 bits of entropy
per byte, even with interrupts disabled. The same paper
shows that simple arithmetic sequences give some
apparent entropy, due to TLB misses, interrupts, etc.

There are lots of caveats in how this should be used and
it is unclear how much real entropy it gives, but is seems
clear it gives some.

My own program to feed into random(4) is based on
such things:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

HAVEGE also uses them
http://www.irisa.fr/caps/projects/hipsor/
 there is a havegd daemon for Linux
http://www.issihosts.com/haveged/

random(4) also mixed in timer data at one point,
which seems the correct thing for it to do. Later
I heard something about that code having been
removed. What is the current status?
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC][PATCH] Entropy generator with 100 kB/s throughput

[Sandy Harris]

On Sun, Feb 10, 2013 at 2:32 PM, Stephan Mueller smuel...@chronox.de wrote:

 On 10.02.2013 19:50:02, +0100, Theodore Ts'o ty...@mit.edu wrote:

 Given all your doubts on the high-precision timer, how can you
 reasonably state that the Linux kernel RNG is good then?

 The data from add_timer_randomness the kernel feeds into the input_pool
 is a concatenation of the event value, the jiffies and the get_cycles()
 value. The events hardly contains any entropy, the jiffies a little bit
 due to the coarse resolution of 250 or 1000 Hz. Only the processor
 cycles value provides real entropy.

There are multiple sources of entropy, though. There are reasons
not to fully trust any -- key strike statistics can be predicted if the
enemy knows the language, the enemy might be monitoring the
network. there is no keyboard or mouse on a headless server, a
diskless machine has no disk timing entropy and one with an
SSD or intelligent RAID controller very little,  However, with
multiple sources and conservative estimates, it is reasonable
to hope there is enough entropy coming in somewhere.

It is much harder to trust a system with single source of
entropy, perhaps impossible for something that is likely to
be deployed on the whole range of things Linux runs on,
from a cell phone with a single 32-bit CPU all the way to
beowulf-based supercomputers with thousands of
multicore chips.

Moeove, random(4) has both a large entropy pool (or
three, to be more precise) and strong crypto in the
mixing. If it /ever/ gets a few hundred bits of real
entropy then no-one without the resources of a
major government and/or a brilliant unpublished
attack on SHA-1 can even hope to break it.

In the default Linux setup, it gets few K bits of
reasonably good entropy from the initialisation
scripts, so attacks look impossible unless the
enemy already has root privileges or has
physical access to boot the machine from
other media  look at Linux storage.
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[speculation] Partitioning the kernel

[Sandy Harris]

I'm wondering whether we have or need a formalisation of how work might be
divided in future kernels.

The question I'm interested in is how the work gets split up among various
components at different levels within a single box (not SMP with many at
the same level, or various multi-box techniques), in particular how you
separate computation and I/O given some intelligence in devices other than
the main CPU (or SMP set). 

There are a bunch of examples to look at:

IBM mainframe
  "channel processors" do all the I/O
  main CPU sets up a control block, does an EXCP instruction
  there's an interrupt when operation completes or fails

VAX 782: basically two 780s with a big cable between busses
  one has disk controllers, most of the (VMS) kernel
  other has serial I/O, runs all user processes

various smart network or disk controllers
and really smart ones that do RAID or Crypto

I2O stuff on newer PCs

Larry McVoy's suggestion that the right way to run, say, a 32-CPU
  box is with something like 8 separate kernels, each using 4 CPUs
If one of those runs the file system for everyone, this somewhat
  overlaps the techniques listed above.

All of these demonstrably work, but each partitions the work between processors
in a somewhat different way.

What I'm wondering is whether, given that many drivers have a top-half
vs. bottom-half split as a fairly basic part of their design, it would
make sense to make it a design goal to have a clean partition at that
boundary.

On well-endowed systems, you then have the main CPUs running the top half
of everything, while I2O processors handle all the bottom halves and the
I/O interrupts. On lesser boxes, the CPU does both halves.

It seems to me this might give a cleaner design than one where the work
is partitioned between devices at some other boundary.

If the locks you need between top and bottom halves of the driver are also
controlling most or all CPU-to-I2O communication, it might go some way
toward avoiding the "locking cliff" McVoy talks of.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[speculation] Partitioning the kernel

[Sandy Harris]

I'm wondering whether we have or need a formalisation of how work might be
divided in future kernels.

The question I'm interested in is how the work gets split up among various
components at different levels within a single box (not SMP with many at
the same level, or various multi-box techniques), in particular how you
separate computation and I/O given some intelligence in devices other than
the main CPU (or SMP set). 

There are a bunch of examples to look at:

IBM mainframe
  "channel processors" do all the I/O
  main CPU sets up a control block, does an EXCP instruction
  there's an interrupt when operation completes or fails

VAX 782: basically two 780s with a big cable between busses
  one has disk controllers, most of the (VMS) kernel
  other has serial I/O, runs all user processes

various smart network or disk controllers
and really smart ones that do RAID or Crypto

I2O stuff on newer PCs

Larry McVoy's suggestion that the right way to run, say, a 32-CPU
  box is with something like 8 separate kernels, each using 4 CPUs
If one of those runs the file system for everyone, this somewhat
  overlaps the techniques listed above.

All of these demonstrably work, but each partitions the work between processors
in a somewhat different way.

What I'm wondering is whether, given that many drivers have a top-half
vs. bottom-half split as a fairly basic part of their design, it would
make sense to make it a design goal to have a clean partition at that
boundary.

On well-endowed systems, you then have the main CPUs running the top half
of everything, while I2O processors handle all the bottom halves and the
I/O interrupts. On lesser boxes, the CPU does both halves.

It seems to me this might give a cleaner design than one where the work
is partitioned between devices at some other boundary.

If the locks you need between top and bottom halves of the driver are also
controlling most or all CPU-to-I2O communication, it might go some way
toward avoiding the "locking cliff" McVoy talks of.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] Prevent OOM from killing init

[Sandy Harris]

Kurt Garloff wrote:

> Kernel related questions IMHO are:
> (1) Why do we get into OOM?

There was a long thread about this a few months back. We get into OOM because
malloc(), calloc() etc. can allocate more memory than is actually available.

e.g. Say you have machine with 64 RAM + 64 swap = 128 megs with 40 megs in use,
so 88 free. Now two processes each malloc() 80 megs. Both succeed. If both
processes then use that memory, someone is likely to fail later.

> Can we avoid it?

The obvious solution is to consider the above behaviour a bug and fix it.
The second malloc() should fail. The process making that call can then look
at the return value and decide what to do about the failure.

However, this was extensively discussed here last year, and that solution was
quite firmly rejected. I never understood the reasons. See the archives.

Someone did announce they were working on patches implementing a sane malloc().
What happened to that project?
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] Prevent OOM from killing init

[Sandy Harris]

Kurt Garloff wrote:

 Kernel related questions IMHO are:
 (1) Why do we get into OOM?

There was a long thread about this a few months back. We get into OOM because
malloc(), calloc() etc. can allocate more memory than is actually available.

e.g. Say you have machine with 64 RAM + 64 swap = 128 megs with 40 megs in use,
so 88 free. Now two processes each malloc() 80 megs. Both succeed. If both
processes then use that memory, someone is likely to fail later.

 Can we avoid it?

The obvious solution is to consider the above behaviour a bug and fix it.
The second malloc() should fail. The process making that call can then look
at the return value and decide what to do about the failure.

However, this was extensively discussed here last year, and that solution was
quite firmly rejected. I never understood the reasons. See the archives.

Someone did announce they were working on patches implementing a sane malloc().
What happened to that project?
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/