Re: Real-World Impact of Hash DoS in Lua

[Matthew Wild <mwild1@...>]

On 26 January 2012 10:29, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Roberto Ierusalimschy:
>
>>> OK.  Cool.  This is a showstopper for the company I am working with for
>>> rolling out embedded Lua with nginx.  Is there anything I can do to help?
>>
>> what it is still missing now is how to create the initial per-state
>> random seed. Suggestions included some address and arc4random. I am
>> afraid that, for the backup ANSI implementation, we cannot do much
>> better than something like this:
>>
>>   seed = (unsigned int)time() + (unsigned int)L;
>
> Addresses of a stack variable and a public Lua function should provide
> a few bits of randomness, too.
>
> Instead of addition, you should use one of Bob Jenkin's mixing
> functions.  This means that it's not important where the randomness is
> inside the initial values (sometimes, it's in the lower bits,
> sometimes, somewhere in the middle).
>
> Reading from /dev/urandom might be problematic because drains entropy
> from the whole system.
>
>> We can have better implementations for particular system. For
>> instance, we can use arc4random if present, but how to detect it?
>> Are there any other suggestions?
>
> Have you tried using PATRICIA and similar trie structures for
> interning strings?  I'm just curious how large the performance impact
> would be.  I suspect it's so large that it's not worth it.
>

I'm personally wondering what the downsides are to using a tree to
store conflicting keys. It doesn't seem to be the popular approach to
fixing this problem. Is the code complexity deemed too great? Too much
(runtime) overhead? Laziness?

Regards,
Matthew