All of lore.kernel.org
 help / color / mirror / Atom feed
From: George Spelvin <lkml@SDF.ORG>
To: "Theodore Y. Ts'o" <tytso@mit.edu>
Cc: linux-kernel@vger.kernel.org, lkml@sdf.org
Subject: Another batched entropy idea
Date: Mon, 30 Mar 2020 02:45:11 +0000	[thread overview]
Message-ID: <20200330024511.GB4206@SDF.ORG> (raw)
In-Reply-To: <20200329214214.GB768293@mit.edu>

Posting all those patches has depressurized my brain and let me think of 
additional ways to speed up batched random number generation, taking 
advantage of the fact that we don't have to anti-backtrack the key.

Rather than using the primary_crng and its lock, use a global 256-bit key, 
and give each CPU a disjoint 64-bit sequence number space.
(for (seq = raw_smp_processor_id(); ; seq += NR_CPUS).)

Then, when a CPU needs to refill its batched pool, copy over the constant, 
the global key, the per-cpu sequence number, do something TBD with the 
nonce, and run ChaCha on the result.

And voila, no global locking ever, unless a reseed interval has elapsed.

(We could also consider using 12 <= r < 20 ChaCha rounds for the batch.
After all, the best attack is <8 rounds and eSTREAM recommends 12.
16 might be reasonable.)

  reply	other threads:[~2020-03-30  2:45 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-10-03  9:51 [RFC PATCH v1 46/50] mm/shuffle.c: use get_random_max() George Spelvin
2020-03-28 18:23 ` Dan Williams
2020-03-28 18:28   ` [RFC PATCH v1 00/52] Audit kernel random number use George Spelvin
2020-03-29 12:21     ` David Laight
2020-03-29 17:41       ` George Spelvin
2020-03-29 21:42         ` Theodore Y. Ts'o
2020-03-30  2:45           ` George Spelvin [this message]
2020-03-30  5:54             ` [PATCH] random: reduce temporary buffers George Spelvin
2020-03-30  9:27           ` [RFC PATCH v1 00/52] Audit kernel random number use David Laight
2020-04-01  5:17           ` lib/random32.c security George Spelvin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200330024511.GB4206@SDF.ORG \
    --to=lkml@sdf.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=tytso@mit.edu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.