Hash table Collision Attack

[mvmarkus]

Hi Rick et all,

Considering the huge impact and potential danger of the newly discovered Hash table collision attacks (DoS) in PHP, Python, Java, Ruby, ASP.NET, Javascript, Lua, Objective C and other languages, do you know if Empresa is affected by that or does Empresa use randomized hash tables?

More information here in the detailed presentation: http://www.youtube.com/user/28c3#p/u/22/R2Cq3CLI6H8

Thanks,

Markus

(Perl fixed this issue already in 2003 (!), since then Ruby is so far the only language that came up with a fix after they were informed last November)

[burch]

Re: Hash table Collision Attack

Thanks for bringing this to our attention.


The hash algorithm we use is significantly different than the djb hash functions mentioned in the presentation and does not appear to be susceptible to the equivalent substring or meet in the middle collision generation methods they describe. However, an attack could still be generated using brute force (or another, faster method could be developed that works with the algorithm we use).


Once you had a dataset that produced a large number of collisions this type of DOS attack would certainly work against MivaScript--we do not enforce the global timeout when parsing POSTed form data and do not have a limit on the number of variables or total size of POSTed content, and our hash table does handle collisions with a linked list.


Generated hash values are stored in the compiled .mvc files so it would be difficult for us to randomize the hash function, but we should be able to implement one or more of the preventative measures (variable limit, timeout). We'll take some steps to mitigate this issue in 5.14.

[mvmarkus]

Re: Hash table Collision Attack

Hi Burch et all,

thanks for your detailed answer and explanation and for looking into this issue.

Markus