> Here I can suggest to implement Yarrow PRGN (that is very simple to > implement) with some lua-pure cryptographic hash function.
We're using lrandom because of the algorithm Mersenne Twister and its well known weaknesses and strengths. > 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 out how > to do it, you can call the "rand()" sample fetch that will call the > internal thread-safe random number generator. Rand() sample fetch cannot be seeded (at the time we checked) so on HAProxy servers with nbproc > 1 we got multiple sequences of the same random numbers - it was one of the reasons we couldn't use it. I was mailing outside the list with Willy and Christopher but it's worth sharing that the problem occurs even with nbthread = 1. I've managed to confirm it today. pt., 25 wrz 2020 o 15:06 Willy Tarreau <[email protected]> napisał(a): > 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 >
