/dev/random changes for 3.13

/dev/random changes for 3.13

[Theodore Ts'o]

The following changes since commit 6e4664525b1db28f8c4e1130957f70a94c19213e:

  Linux 3.11 (2013-09-02 13:46:10 -0700)

are available in the git repository at:

  git://git.kernel.org/pub/scm/linux/kernel/git/tytso/random.git tags/random_for_linus

for you to fetch changes up to 392a546dc8368d1745f9891ef3f8f7c380de8650:

  random: add debugging code to detect early use of get_random_bytes() (2013-11-03 18:24:08 -0500)

----------------------------------------------------------------
The /dev/random changes for 3.13 including a number of improvements in
the following areas: performance, avoiding waste of entropy, better
tracking of entropy estimates, support for non-x86 platforms that have
a register which can't be used for fine-grained timekeeping, but which
might be good enough for the random driver.

Also add some printk's so that we can see how quickly /dev/urandom can
get initialized, and when programs try to use /dev/urandom before it
is fully initialized (since this could be a security issue).  This
shouldn't be an issue on x86 desktop/laptops --- a test on my Lenovo
T430s laptop shows that /dev/urandom is getting fully initialized
approximately two seconds before the root file system is mounted
read/write --- this may be an issue with ARM and MIPS embedded/mobile
systems, though.  These printk's will be a useful canary before
potentially adding a future change to start blocking processes which
try to read from /dev/urandom before it is initialized, which is
something FreeBSD does already for security reasons, and which
security folks have been agitating for Linux to also adopt.

----------------------------------------------------------------
H. Peter Anvin (3):
      random: statically compute poolbitshift, poolbytes, poolbits
      random: allow fractional bits to be tracked
      random: account for entropy loss due to overwrites

Theodore Ts'o (17):
      random: run random_int_secret_init() run after all late_initcalls
      random: allow architectures to optionally define random_get_entropy()
      random: mix in architectural randomness earlier in extract_buf()
      random: fix the tracepoint for get_random_bytes(_arch)
      random: optimize spinlock use in add_device_randomness()
      random: optimize the entropy_store structure
      random: cap the rate which the /dev/urandom pool gets reseeded
      random: speed up the fast_mix function by a factor of four
      random: adjust the generator polynomials in the mixing function slightly
      random: drop trickle mode
      random: push extra entropy to the output pools
      random: convert DEBUG_ENT to tracepoints
      random: make add_timer_randomness() fill the nonblocking pool first
      random: printk notifications for urandom pool initialization
      random: don't zap entropy count in rand_initialize()
      random: initialize the last_time field in struct timer_rand_state
      random: add debugging code to detect early use of get_random_bytes()

 drivers/char/random.c         | 652 ++++++++++++++++++++++++++++++++-------------------
 include/linux/random.h        |   1 +
 include/linux/timex.h         |  14 ++
 include/trace/events/random.h | 183 ++++++++++++++-
 init/main.c                   |   2 +
 5 files changed, 608 insertions(+), 244 deletions(-)

Re: /dev/random changes for 3.13

[Theodore Ts'o]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On Wed, Nov 13, 2013 at 09:03:32PM -0500, Theodore Ts'o wrote:
> The following changes since commit 6e4664525b1db28f8c4e1130957f70a94c19213e:
> 
>   Linux 3.11 (2013-09-02 13:46:10 -0700)
> 
> are available in the git repository at:
> 
>   git://git.kernel.org/pub/scm/linux/kernel/git/tytso/random.git tags/random_for_linus
> 
> for you to fetch changes up to 392a546dc8368d1745f9891ef3f8f7c380de8650:
> 
>   random: add debugging code to detect early use of get_random_bytes() (2013-11-03 18:24:08 -0500)

There will be a merge conflict thanks to changes from the net tree.
Here is the proposed resolution:

commit 6b284fe1892e320a76145bdc421fc7222169c98b
Merge: 392a546 2821fe6
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Wed Nov 13 20:27:49 2013 -0500

    Merge /usr/projects/linux/base into merge-resolve
    
    Conflicts:
    	drivers/char/random.c

diff --cc drivers/char/random.c
index cdf4cfb,4fe5609..aa051ef
- --- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@@ -654,14 -601,12 +654,16 @@@ retry
  	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
  		goto retry;
  
- - 	r->entropy_total += nbits;
  	if (!r->initialized && nbits > 0) {
+ 		r->entropy_total += nbits;
  		if (r->entropy_total > 128) {
- - 			if (r == &nonblocking_pool)
- - 				pr_notice("random: %s pool is initialized\n",
- - 					  r->name);
  			r->initialized = 1;
 -			if (r == &nonblocking_pool)
 +			r->entropy_total = 0;
++			if (r == &nonblocking_pool) {
+ 				prandom_reseed_late();
++				pr_notice("random: %s pool is initialized\n",
++					  r->name);
++			}
  		}
  	}
  

I've pushed this merge resolution here:

http://git.kernel.org/cgit/linux/kernel/git/tytso/random.git/log/?h=trial_merge

git pull git://git.kernel.org/pub/scm/linux/kernel/git/tytso/random.git trial_merge

% git show-ref trial_merge
c0caa5d6dd21f115005a73311960d60172028047 refs/heads/trial_merge

Cheers,

							- Ted
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.14 (GNU/Linux)

iQIcBAEBCAAGBQJShHMcAAoJENNvdpvBGATwiLQP/2+zj0iAwkae2WCHgKEd5g0G
8iHzzQ23JJChoItJE/8OWs3HnsdiJsz+dTpe05ZFIfRWO0p3Niyrstr6Jc9Wk0eL
p9tA/VNGuCwOcqpTaKLNs3mSUlS6IgIDs2UoFnbAjzG5lddsPTfOuWRyqCpYWNWI
5Q1bz/zobvUcgVmNL/Crv5DHut4vyMH40O9LJZIREDwAXp8X6XzqNHNcbiESqgRg
K7MRD3mzX1Xojs07SIszmKEGoXhDxmWAbpLf3ulv3qS/FI7hPevUqqj4NWjnFppJ
iNFOcRCLfQpXBA3y+b2sj+EpLwG32WhX0fs4oT8cX4wpqEmymqAxM1Ek/+ZdZmkB
Aw9JX20JPQ4U8tdlQgSvZfg/B/gDFcysV2mTgjuME23qqZLRLfmWpwUrE8lpVolC
ZxRt4ouE7y5/gjUg1KM4ASLZzwYnSsnyLuWk6WGtF1YQcaAeTYjZEWJqAL3fuJdI
5JpDYO7givH9Sv6cFPnuoKVfZyQrQPkkshxBLBO1Vlhb2zxgRNmYGqMdAnnog7NG
4VF9j3WoG7NwynXy5iZyedpO8dF2HfL+Bk2hoepVyqiY/L36hciyjA+yAOpUDePq
QpcUqe7/YEucqvgPxHpy2UIR3w/LSkFGoLU3tqdF5bR95tSuU+XEEp5mZcBWPdA4
fHRXvUWN+eQya2PdWnoE
=IkXd
-----END PGP SIGNATURE-----

Re: /dev/random changes for 3.13

[Linus Torvalds]

On Wed, Nov 13, 2013 at 10:52 PM, Theodore Ts'o <tytso@mit.edu> wrote:
>
> There will be a merge conflict thanks to changes from the net tree.
> Here is the proposed resolution:

Ok, I finally got around to the random tree, but your proposed merge
resolution makes no sense, so I didn't end up applying it.

> - -     r->entropy_total += nbits;
>         if (!r->initialized && nbits > 0) {
> +               r->entropy_total += nbits;

This part undoes your commit 6265e169cd31 ("random: push extra entropy
to the output pools"), and the "entropy_total" field will now never be
non-zero when "r->initialized" is set. So then the rest of your
commit, which looks like this:

+ /* If the input pool is getting full, send some
+ * entropy to the two output pools, flipping back and
+ * forth between them, until the output pools are 75%
+ * full.
+ */
+ if (entropy_bytes > random_write_wakeup_thresh &&
+    r->initialized &&
+    r->entropy_total >= 2*random_read_wakeup_thresh) {
+ static struct entropy_store *last = &blocking_pool;
+ struct entropy_store *other = &blocking_pool;

can never trigger (because "r->initialized && r->entropy_total >=
2*random_read_wakeup_thresh" is never true).

So your merge resolution diff makes no sense to me.

That said, the networking change seems to be simpler and largely
equivalent to that commit, so maybe you meant to basically castrate
that commit 6265e169cd31? Or maybe the diff you posted was incomplete
and just doesn't show the undone part (because "git diff --cc" will
not show parts that match the other branch).

So I think the correct resolution is to basically take the code that
the networking tree added, and undo the "If the input pool is getting
full.." part of commit 6265e169cd31.

Hmm?

Just verifying that we're on the same page before merging this..

            Linus

Re: /dev/random changes for 3.13

[Theodore Ts'o]

On Fri, Nov 15, 2013 at 01:58:05PM -0800, Linus Torvalds wrote:
> Ok, I finally got around to the random tree, but your proposed merge
> resolution makes no sense, so I didn't end up applying it.
> 
> > - -     r->entropy_total += nbits;
> >         if (!r->initialized && nbits > 0) {
> > +               r->entropy_total += nbits;
> 
> This part undoes your commit 6265e169cd31 ("random: push extra entropy
> to the output pools"), and the "entropy_total" field will now never be
> non-zero when "r->initialized" is set....

You're right, I totally screwed that up.  Part of the problem is that
I should have cleaned up the if statement in commit 6265e169cd31 so
that it looked like this:

        r->entropy_total += nbits;
        if (!r->initialized && (r->entropy_total > 128)) {
                        r->initialized = 1;
                        r->entropy_total = 0;
                }
        }

... and so at the top of the dev branch, it should have looked like
this:

        r->entropy_total += nbits;
        if (!r->initialized && (r->entropy_total > 128)) {
		if (r == &nonblocking_pool)
			pr_notice("random: %s pool is initialized\n", r->name);
		r->initialized = 1;
		r->entropy_total = 0;
        }

Instead, I had a more complicated structure which confused me when I
cleaned up the merge.

So I'm going to propose the following merge resolution:

diff --cc drivers/char/random.c
index cdf4cfb,4fe5609..0000000
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@@ -654,14 -601,12 +654,13 @@@ retry
  	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
  		goto retry;
  
 -	if (!r->initialized && nbits > 0) {
 -		r->entropy_total += nbits;
 -		if (r->entropy_total > 128) {
 -			r->initialized = 1;
 -			if (r == &nonblocking_pool)
 -				prandom_reseed_late();
 +	r->entropy_total += nbits;
- 	if (!r->initialized && nbits > 0) {
- 		if (r->entropy_total > 128) {
- 			if (r == &nonblocking_pool)
- 				pr_notice("random: %s pool is initialized\n",
- 					  r->name);
- 			r->initialized = 1;
- 			r->entropy_total = 0;
++	if (!r->initialized && (r->entropy_total > 128)) {
++		r->initialized = 1;
++		r->entropy_total = 0;
++		if (r == &nonblocking_pool) {
++			prandom_reseed_late();
++			pr_notice("random: %s pool is initialized\n", r->name);
  		}
  	}

It does fold a cleanup in with the merge resolution, but it's not
actually changing anything in terms of code behavior, and it makes the
resulting merge much more obvious.

Are you OK with that?

						- Ted