3 ms·
Lua's string hash function looks roughly like this: hash = length of string for each char c in string hash = hash ^ ((hash << 5) + (h >> 2) + (unsigned
by extension 15y ago
Lua's string hash function looks roughly like this:
hash = length of string
for each char c in string
hash = hash ^ ((hash << 5) + (h >> 2) + (unsigned char) c)
It folds up to 32 chars into the hash. If the string is longer, it skips some characters.
This is a well known hash function and it's very different from the one being used by all the other vulnerable languages, but I don't know how hard it is to find collisions for this one.
- silentbicycle 15y agoThe full source (as of 5.2) is here (http://www.lua.org/source/5.2/lstring.c.html#luaS_newlstr http://www.lua.org/source/5.2/lstring.c.html#luaS_newlstr).
- mikeash 15y agoIf it starts skipping characters in longer strings then I'd say it's trivial to find collisions by simply constructing strings that are identical in the bytes that are examined and differ in the bytes that aren't.
- colanderman 15y agoIt looks like it would be trivial to find collisions; all the functions used (xor, bitshifts, and addition) are trivially reversible. Just replace the nondeterminism of reversing the binary operators (xor and addition) with a random number generator and you've got yourself a collision generator.