[Cryptography] randomness +- entropy

[Ray Dillinger]

Is there any functionality now in the linux system that provides a
"pure" PRNG?  ie, if I know or have set the complete state, I can
then read from it an infinitely-long stream of bits which can be
repeated by initializing it with the same state (and which will
repeat after some finite but very long output stream) but which
is otherwise unpredictable?  Obviously this would be per-process;
sharing state would allow other processes to draw outputs and
therefore alter the sequence visible to the current process. This
used to be random(3). I believe this is still what random(3) does.

And,

Is there any functionality now in the linux kernel that provides
a "pure" Random Number Generator?  IE, it would trap, or set an
'invalid' flag, or suspend the caller, or something, but won't!
ever! return a number when there is insufficient entropy to be
sure that that number is less than completely unpredictable?
This is what /dev/random was supposed to be, right?

Because, honestly, the 'hybrid' state of both of /dev/random and
/dev/urandom right now is giving me some concern.  There was a
time when /dev/random was supposed to deliver NOTHING but hard
randomness you could absolutely rely on for keying material, and
/dev/urandom was supposed to be a best-efforts approximation to
the latter but would rather return a (possibly somewhat)
predictable result than fail or slow down your process. Knowing
for sure which was what made designing robust and secure systems
straightforward, if sometimes hard.

The discussion here makes me want to craft something that gives
two simultaneous results; first, the "random number", and second,
a "confidence score" that indicates how certain I can be that the
"random number" is unpredictable.

				Bear


On 11/08/2013 01:12 PM, Theodore Ts'o wrote:
> On Fri, Nov 08, 2013 at 12:23:57PM -0700, John Denker wrote:
>> It turns out that:
>>   1a) /dev/random is "supposed" to be a TRNG.
>>   1b) However, it can operate as a PRNG in exceptional
>>    circumstances, when it is recovering from a compromise.
>
> (1b) is true for all RNG's which has any kind of batching in their
> design, and that tends to be all RNG's.  Even a design which is using
> a noise diode and generating bits on demand, still has to batch bits
> until it sends back a byte or a set of bytes to the requester.
>
> Also note that you may not know when you've suffered from a
> compromise; so part of a good design is to have ways to limit damage
> after a state compromise.
>
>>   2a) /dev/urandom is some sort of hermaphroditic chimera.
>>    That is to say, I don't know what it is.  Under a
>>    wide range of "typical" conditions it functions as
>>    a PRNG.
>>   2b) However, it also tries to approximate a TRNG if
>>    it can.
>
> 2b) was historically true, but after the 2.13 kernel, it will be
> moving much more towards the PRNG.  The main reason for this is that
> if you have processes such as the Chrome browser which is using
> /dev/urandom very aggressively, to make more entropy available in the
> input pool for use by /dev/random.  The reason why I made this change
> was a user complaining to me that generating a new 2048 GPG key was
> taking over ten minutes on his desktop, and I started taking a closer
> look at how the entropy was getting used.
>
>> Also note that this printk warning is in one person's
>> "development" branch and has not been incorporated into
>> any released version of the kernel.
>>    http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/log/?h=dev
>
> It's my (the /dev/random maintainer's) development tree, and so it's
> already in test integration builds in the linux-next tree, and it's
> scheduled to go into the mainline linux when the merge window opens
> next week.  Linus and I will be both be in Korea giving at the
> LinuxCon Korea conference (my talk is going to be about security
> requirements for Linux, and it's going to include discussion about
> /dev/random), but I expecgt to send the git PULL request to Linus
> while I am in Seoul, and I expect that he'll pull it in, do his test
> build, and push it to the official mainline tree, while he is in
> Korea.
>
>>> One of the reasons why we don't attempt to extract "true random bits"
>>> and save them across a reboot is that even we had such bits that were
>>> secure even if the underlying crypto primitives were compromised to a
>>> fare-thee-well, once you write them to the file on the hard drive and
>>> the OS gets shut down, there's no guarantee that an adversary might
>>> not be able to read the bits while the OS is shut down.  Even if you
>>> don't do something truly stupid (such as leaving your laptop
>>> unattended in a hotel room while visiting China), the risk of having
>>> your "true random bits" stolen is probably higher than the
>>> cryptographic primitives getting compromised.
>>
>> That reason doesn't make much sense.  There is a better reason,
>> as discussed below, but first we should observe that at present
>> Linux stores only a pseudo-random seed and then relies entirely
>> on the PRNG!  This is in no way more trustworthy than storing
>> some real entropy.  Any attacker who could steal the hypothetical
>> random-seed file can also steal the urandom-seed file.
>
> That's what we are doing *today*.  I'm explaining why it doesn't
> really make sense to extract out however many bits of entropy we have
> out of /dev/random, and then push it into the input pool.  This is
> something that is within my power to change, but as I've described
> above, I don't really think it's that great of an idea.
>
>> Here's a better reason why at present it would make no sense to
>> take the obvious approach to storing real entropy across reboots:
>> The /dev/urandom quasi-PRNG would immediately waste the entropy.
>> The device apparently assumes that a steady supply of new raw
>> entropy will always be available.  In situations where entropy
>> is scarce -- e.g. when there is a finite stored supply -- normal
>> operation of /dev/urandom is tantamount to a denial-of-service
>> attack on the entropy supply.
>
> With the changes that are in the random.git tree, which are in the
> linux-next tree, and will probably be in Linus's tree by the end of
> the next week, if there are heavy users of /dev/urandom, the amount of
> entropy consumed out of the input pool has been significantly reduced.
>
> There are some further changes that could be made, and which I am
> thinking about.  Part of this includes using AES for /dev/urandom,
> since we now have CPU's with AES acceleration, and we no longer need
> to worry as much about export control laws (the current design was
> implemented in 1994, back when crypto export was a real issue).  One
> of the things that is holding me back is that currently the Crypto
> layer in Linux is optional, and can be compiled as a module, and I've
> always wanted to make sure /dev/random was something user progams
> could always count on being there.  So there are some negotiations I
> need to make with the maintainers of the Crypto subsystem about how to
> make this all work, since it would require making such changes in how
> the Crypto layer is configured.
>
> It is true that part of the current design relies on the fact we can
> sample interrupt timings and storage timing issues, so we do get a
> continuous stream of incoming entropy.  We want to make sure that this
> entropy is used wisely, but not using it all is, at the end of the
> day, just as wasteful as using it too profligately.  One of the ways
> that we do use these bits is to limit the damage in the unlikely case
> of internal state compromise.
>
> Regards,
>
> 					- Ted
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>
>