On Fri, Aug 07, 2020 at 03:45:48PM -0700, Marc Plumb wrote: > Willy, > > > On 2020-08-07 3:19 p.m., Willy Tarreau wrote: > > On Fri, Aug 07, 2020 at 12:59:48PM -0700, Marc Plumb wrote: > > > > > > If I can figure the state out once, > > Yes but how do you take that as granted ? This state doesn't appear > > without its noise counterpart, > > Amit has shown attacks that can deduce the full internal state from 4-5 > packets with a weak PRNG. If the noise is added less often than that, an > attacker can figure out the entire state at which point the partial > reseeding doesn't help. If the noise is added more often than that, and it's > raw timing events, then it's only adding a few bits of entropy so its easy > to guess (and it weakens dev/random). If the noise is added more often, and > it's from the output of a CPRNG, then we have all the performance/latency > problems from the CPRNG itself, so we might as well use it directly. His attacks is based on the fact that internal state bits leak as-is. So it is possible to collect them and perform the inverse operation to reconstruct the input. Here the output is made by mixing two input bits with two noise bits and produce one single output bit. So for each output bit you see, you don't have just one possible input bit, but 16 possibilities. That's 128 bits of internal changing states that once combined result in 32 bits. For each 32-bit output you still have 2^96 possible internal (x,noise) states producing it. And that's without counting on the 64-bit seed that you still don't know but can be deduced from two guessed 128 bit states (assuming that can be brute-forced at all, of course). For sure there are plenty of number theories allowing you to significantly reduce the space you need to work on to brute-force this but it will definitely remain above 2^32 attempts for each iteration, which is the floor you have without the noise part, while the whole internal state will be reseeded every minute anyway. I mean, I'm not trying to sell this thing, I'm just trying to defend that we use a reasonable tool for a reasonable protection level. And yes, probably that 15 years from now, someone will say "hey look, I can brute-force this thing in less than a minute on my 1024-core 39th gen core i7 machine with 2^60 operations per second, why don't we use our CPU's native 10 picosecond AES1024 instruction instead ?" and we'll say "well, it's an old story and it's probably about time to change it again". I don't see anything wrong with evolving this way, matching concrete needs more than pure theory. Regards, Willy
