Re: Real-World Impact of Hash DoS in Lua

[Natanael Copa <natanael.copa@...>]

On Thu, Jan 19, 2012 at 2:47 PM, John Graham-Cumming <jgc@jgc.org> wrote:
> I've been following the discussion about the hash DoS attack that is quite
> serious in Lua because of the fact that strings > 32 bytes are not fully
> hashed and because the hashing algorithm is not randomly seeded.  I need to
> protect against this attack in a real world situation.  I am working with an
> unnamed (because I don't want to see an attack on it) very, very large
> Internet company that uses Lua and this attack would have serious
> consequences for them.

FWIW, I also use Lua in networking services and would very msuch like
to see an official patch for this fairly soon.

> Having looked into building a patched Lua for this the solution would seem
> to be the following:
>
> 1. Randomize the hash seed.  In the patch I developed I generate a new
> unsigned int using rand() and store it in the global state and then use it
> to initialize the hash value instead of the string length (as is done
> today).

agree.

> 2. Don't hash large strings.  In this situation a value of 128 bytes can be
> counted as large.  Any strings above this can be stored in a simple
> GCObject** list.  The hash value of the large strings (which may be needed
> if the string is to be inserted into a table) could just be a random 32 bit
> number.  Given that eqstr assumes the same pointer for the same string a
> different operation would need to be defined is len(string)>128.
>
> 3. Fully hash short strings.  For strings less than 128 bytes all bytes need
> to be used.  This will protect against the DoS attack when combined with (1)
> above.

How about randomizing which bytes that are skipped? That would be less
intrusive but would it be good enough?

something like this:

(hash_seed and random_skip are initialized at startup from
/dev/urandom or similar)

--- ./lstring.c.orig
+++ ./lstring.c
@@ -74,10 +74,10 @@

 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
   GCObject *o;
-  unsigned int h = cast(unsigned int, l);  /* seed */
+  unsigned int h = hash_seed;  /* seed */
   size_t step = (l>>5)+1;  /* if string is too long, don't hash all
its chars */
   size_t l1;
-  for (l1=l; l1>=step; l1-=step)  /* compute hash */
+  for (l1=l - (random_skip % step); l1>=step; l1-=step)  /* compute hash */
     h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
   for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
        o != NULL;


> I'm willing to work on a patch for Lua if folks are likely to be interested.
>
> John.
>


-- 
Natanael Copa