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.
They have taken steps at the HTTP server level to mitigate the problem, but they would like to be able to handle arbitrary strings in Lua without having to worry about this attack. The nature of their business means that simple fixes (like reducing the number of POST parameters made to a server) won't totally fix the problem for them (because they process other arbitrary data that they don't control, and an attacker could, using Lua).
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).
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.
I'm willing to work on a patch for Lua if folks are likely to be interested.
John.
