Hi Kirill,
On Fri, Sep 25, 2020 at 12:34:16PM +0200, Kirill A. Korinsky wrote:
> I've extracted a pice of code from lrandom and put it here:
> https://gist.github.com/catap/bf862cc0d289083fc1ccd38c905e2416
> <https://gist.github.com/catap/bf862cc0d289083fc1ccd38c905e2416>
>
> You can see that object generator contains N words (and here it is 624), and
> I use an assumption that Maciej's code doesn't create a new generator for
> each request and share lrandom.
>
> Idea of this RNG is initialize each N words via init_genrand and it checking
> that all of them are used, and after one generated a new ones.
>
> Let assume that we called genrand_int32 at the same moment from two threads.
> If condition at lines 39 and 43 are true we start to initialize the next
> words at both threads.
>
> You can see that we can easy move outside of v array at line 21 because two
> threads are increasing i field, and put some random number to i field.
Till here your analysis is right but:
- the overflow would only be at most the number of extra threads running
init_genrand() concurrently, or more precisely the distance between
the most upfront to the latest thread, so in the worst case nbthread-1
hence there's no way to write a single location into a totally unrelated
structure without writing the nbthread-2 words that are between the end
of the MT array and the overwritten location ;
- the lua code is not threaded (there's a "big lock" around lua since
stacks cannot easily be protected, though Thierry has some ideas for
this).
> Ans when the second thread is going to line 27 and nobody knows where it put
> 0xffffffff
Actually init_genrand() doesn't actually *write* 0xffffffff but only writes
*something* of 64 bits size and applies a 32-bit mask over it, so it would
have written 32 bits pseudo-random bits followed by 4 zero bytes.
> How can it be proved / solved?
>
> I see a few possible options:
> 1. Switch off threads inside haproxy
> 2. Use dedicated lrandom per thread
> 3. Move away from lrandom
>
> As I understand lrandom is using here because it is very fast and secure, and
> reading from /dev/urandom isn't an option.
>
> Here I can suggest to implement Yarrow PRGN (that is very simple to
> implement) with some lua-pure cryptographic hash function.
In fact I know it's possible to call haproxy's internal sample fetch
functions from Lua (I never can figure how to do that, I always need
to lookup an example for this unfortunately). But once you figure how
to do it, you can call the "rand()" sample fetch that will call the
internal thread-safe random number generator.
Regards,
Willy
