Date:   Sun, 27 Mar 2022 15:05:09 -0700
From:   Michael Brooks <m@...etwater.ai>
To:     linux-kernel@...r.kernel.org
Subject: [PATCH] A Truly Lockless '/dev/random' and removal of 'try_to_generate_entropy()

Hey Everyone,

In the interest of a faster kernel, and saving some CO2 - I started
working on a truly non-blocking /dev/random implementation.  The patch
below is the culmination of three years of hard work, and has been
peer reviewed and passes the "die-harder" battery of tests.  This
patch is far from perfect, but it will help further the discussion,
and any help to massage this code to be better is welcome.

Why does this patch matter?
1. Benchmarks - if this patch did its job then every interrupt should be faster.
2. I am Old Yeller'ing try_to_generate_entropy() in favor of
find_more_entropy_in_memory().  The try_to_generate_entropy() function
is a mistake that is trying to correct a deeper mistake, and I think
we all see that.
3. This path should be a security improvement. Not only should we be
more resistant to DoS, but also the pool state should be less
predictable to any would-be attacker.

For a very detailed description, and mathematical
proofs-of-correctness, check out my repo here, this code supports both
/dev/random and /dev/urandom as well as internal kernel consumers:
https://github.com/TheRook/KeypoolRandom

The repo above is the software equivalent of a breakout board, it
isolates the random device driver so you can run it on the commandline
without having to build the whole kernel.  This development technique
saves development cycles, and makes it easier to verify and debug
locally. Feel free to run it and step through with a standard debugger
if you want to deep dive.

The attached patch is based on Jason A. Donenfeld's 'random' branch.
Jason's branch is a great step in the right direction so I used it as
my base: (https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/tree/drivers/char/random.c).

The attached patch is using Jason's crng_fast_key_erasure() instead of
AES and building the key material using the keypool as described on
github. If you are unsure as to what a 'gatekey' or a 'keypool' even
is - then I suggest reading my readme file on my github repo above as
these are clearly described, please read the documentation.

A speedtest shows that AES-NI is substantially faster than Chacha20 -
but this should be configurable as it is reasonable for someone to not
trust hardware implementations, and clearly not everyone has the
luxury of having AES-NI.  A good handset maker should prefer AES-NI as
this instruction set as this will improve battery life. If AES-NI were
to be backdoored, that kind of backdoor is unlikely to undermine the
keypool random's construction because it is in a constant state of
churn.  It is important to note that every cellphone sold in the US is
shipped with a backdoor by law because of CALEA - so that is the world
we live in.

I worked very hard on this code, and I have taken this as far as I can
on my own. I still need help getting it to work well and you can see
my todo's in the patch file.  I don't think this patch is stable, and
this is my first patch so please be kind.  We should all assume that I
am a spook and you should go over this with a fine tooth comb - I
would expect nothing less from this amazing community.  I expect that
you'll find additional performance improvements and ways to improve
stability.  I'm sure there are also ways of improving security - that
being said I don't expect there to be an exploitable condition here,
but I could be wrong.

To build:
git checkout https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git
git apply keypoolrandom.patch
make menu config
make

It looks like the 'random' branch is broken at the moment, this is
causing a build error that is not my doing, and is preventing me from
proceeding.  As of this morning I am getting errors in
net/netfilter/xt_TCPMSS.o' from a fresh checkout before I have even
applied the patch.

Feedback welcome, feel free to email me directly - I am here to be a
better engineer.

Your friendly neighborhood hacker,
Michael Brooks

Download attachment "keypoolrandom.patch" of type "application/octet-stream" (59858 bytes)

Powered by blists - more mailing lists