Hi Willy,
On 2020-08-04 7:49 p.m., Willy Tarreau wrote:
Hi Marc,
On Tue, Aug 04, 2020 at 05:52:36PM -0700, Marc Plumb wrote:
Seeding two PRNGs with the same entropy causes two problems. The minor one
is that you're double counting entropy. The major one is that anyone who can
determine the state of one PRNG can determine the state of the other.
The net_rand_state PRNG is effectively a 113 bit LFSR, so anyone who can see
any 113 bits of output can determine the complete internal state.
The output of the net_rand_state PRNG is used to determine how data is sent
to the network, so the output is effectively broadcast to anyone watching
network traffic. Therefore anyone watching the network traffic can determine
the seed data being fed to the net_rand_state PRNG.
The problem this patch is trying to work around is that the reporter
(Amit) was able to determine the entire net_rand_state after observing
a certain number of packets due to this trivial LFSR and the fact that
its internal state between two reseedings only depends on the number
of calls to read it.
I thought net_rand_state was assumed to be insecure and that anyone
could determine the internal state. Isn't this Working as Designed? It's
a PRNG not a CPRNG. If some aspects of security depends on the sate
remaining secret then this is fundamentally the wrong tool.
(please note that regarding this point I'll
propose a patch to replace that PRNG to stop directly exposing the
internal state to the network).
I'm glad to hear that. A good option would be SFC32.
If you look closer at the patch, you'll see that in one interrupt
the patch only uses any 32 out of the 128 bits of fast_pool to
update only 32 bits of the net_rand_state. As such, the sequence
observed on the network also depends on the remaining bits of
net_rand_state, while the 96 other bits of the fast_pool are not
exposed there.
The fast pool contains 128 bits of state, not 128 bits of entropy. The
purpose of the large pool size is to make sure that the entropy is not
lost due to collisions. The non-linear mixing function (a simplified
version of a single round of the ChaCha mixing function so the entropy
diffusion is low) means that the 32 bits leaked are not independent from
the other 96 bits, and in fact you can reconstruct the entire pool from
a single reading of 32 bits (as long as there aren't more than 32 bits
of entropy added during this time -- which isn't the case, see below).
Please think harder about this part. I think you are misunderstanding
how this code works.
Since this is the same
seed data being fed to get_random_bytes, it allows an attacker to determine
the state and there output of /dev/random. I sincerely hope that this was
not the intended goal. :)
Not only was this obviously not the goal, but I'd be particularly
interested in seeing this reality demonstrated, considering that
the whole 128 bits of fast_pool together count as a single bit of
entropy, and that as such, even if you were able to figure the
value of the 32 bits leaked to net_rand_state, you'd still have to
guess the 96 other bits for each single entropy bit :-/
The code assumes that there is at least 1/64 bit of entropy per sample,
and at most 2 bits of entropy per sample (which is why it dumps 128 bits
every 64 samples). If you're extracting 32 bits every sample, which
means it's leaking 2048 bits in 64 samples (to net_random, how fast it
leaks to the outside world is a different issue). So the question is if
an attacker can reconstruct 128 bits of entropy from 2048 bits of
internal state -- this does not seem obviously impossible, since there
are no cryptographically vetted operations in this.
The other thing that this misses is that reseeding in dribs and drabs
makes it much easier to recover the new state. This is is explained well
in the documentation about catastrophic reseeding in the Fortuna CPRNG.
This entire approach is flawed. Throwing in single bits of entropy at a
time doesn't really help since an attacker can brute force a single bit
at a time. (There is a challenge in deriving the initial fast_pool
states which this makes more difficult, but there is no real
crytptographic guarantee about how difficult it is.)
Thanks,
Marc
