# 5.3.9, Hash DoS, release - Thread: https://externals.io/message/57291 - Original archive: https://news-web.php.net/php.internals/57291 - Started by Pierre Joye on 2012-01-09T15:41:51+00:00 - Messages: 25 - Reply by email to internals@lists.php.net - More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt --- ## #57291 — Pierre Joye — 2012-01-09T15:41:51+00:00 URL: https://externals.io/message/57291#57291 hi, Moving this discussion here as it makes little to non sense to discuss that any longer on security@ We are now very late behind an acceptable delay to provide a fix for the hash DoS, to say it nicely. I'd strongly suggest to release 5.3.9 (RC5 has been tested now) final this week using the max_input_vars fix, with the modification from Laruence (but with a larger limit). Laruence addition also fixes serialize or json, which are parts that need this fix as well as it is impossible to valid a string manually (length check only is not enough or cannot work in all cases). But 1st of all, the fix addition has to be applied and fully tested. But if the addition is not desired yet, then we must at least release 5.3.9 with Dmitry's fix only and we can fix json&serialize later, ideally within 2 weeks max. Cheers, -- Pierre @pierrejoye | http://blog.thepimp.net | http://www.libgd.org --- ## #57292 — Nikita Popov — 2012-01-09T16:01:28+00:00 URL: https://externals.io/message/57291#57292 · In reply to: #57291 > hi, > > Moving this discussion here as it makes little to non sense to discuss > that any longer on security@ > > We are now very late behind an acceptable delay to provide a fix for > the hash DoS, to say it nicely. > > I'd strongly suggest to release 5.3.9 (RC5 has been tested now) final > this week using the max_input_vars fix, with the modification from > Laruence (but with a larger limit). Laruence addition also fixes > serialize or json, which are parts that need this fix as well as it is > impossible to valid a string manually (length check only is not enough > or cannot work in all cases). By laruence addition you mean this patch: https://bugs.php.net/patch-display.php?bug_id=60655&patch=max_input_vars.patch&revision=latest ? If so, two questions: 1. Why should all POST variables be counted into the limit, not only the ones in one nesting level? 2. How high would the limit for seriliaze() and `json_decode()` be approximately? I think that few applications will use more than 1000 POST vars but I could well imagine that they have large serialized arrays. Putting the limit too high on the other hand will pretty much defeat the purpose of the fix. > But 1st of all, the fix addition has to be applied and fully tested. > But if the addition is not desired yet, then we must at least release > 5.3.9 with Dmitry's fix only and we can fix json&serialize later, > ideally within 2 weeks max. I'd prefer that. Don't think that it's wise to apply a different fix shortly before the release. --- ## #57293 — Stefan Esser — 2012-01-09T16:18:38+00:00 URL: https://externals.io/message/57291#57293 · In reply to: #57292 Dear Pierre and others, > I'd strongly suggest to release 5.3.9 (RC5 has been tested now) final > this week using the max_input_vars fix, with the modification from > Laruence (but with a larger limit). Laruence addition also fixes > serialize or json, which are parts that need this fix as well as it is > impossible to valid a string manually (length check only is not enough > or cannot work in all cases). Why do you advocate a patch from Laruence that randomizes the size of the HashTable, which does not fix the HashDOS security problem at all? It seems that the majority of people working on this HashDOS stuff do not understand the actual mathematical problem and try to exploit it by using numerical indices. In case of numerical indices a collision is trivial: 0x00010000, 0x00020000,0x00030000, … 0xFFFF0000 will all collide because n mod 2^x is always 0 for x<=16. This is however just the cheap way to cause HashTable collisions in PHP. The actual HashDOS exploit the nruns guys were talking about *DOES NOT* involve numerical indices at all. The nruns guys are speaking about collisions in the DJB hash function, which is used for alpha numerical indices. This cannot be fixed by random HashTable size increments. Random HashTable size increments will only lead to tricky debugging situations, because due to the randomness the PHP memory layout/usage for the same script will be totally different with each run. Just one of the possible consequences: the same script, running on the same server, called 2 times with the same parameters can e.g. cause memory limit violations in totally different places. Or sometimes does not violate the memory limit at all. And this all ignores the fact that the patch by Laruence is broken and performs dangerous operations on the size field that could introduce further problems. *** The only way to fix the HashTable implementation is by using a randomized HashFunction (not a randomized HashTable) *** *** And of course resource limits are always a good addition to protect against this and future different vulnerabilities. *** Regards, Stefan Esser --- ## #57294 — Stefan Esser — 2012-01-09T16:34:43+00:00 URL: https://externals.io/message/57291#57294 Hey, > I think you accidentially sent this to me, not to the list ;) By the > way, I think you and Pierre are talking about different patches. We do > know that the hash size randomization will not work. Pierre is > referring to another patch that extends max_input_vars to > unserilized() and `json_decode()`. ah okay. I see now that there is a different patch, but it is not clear if Pierre meant this or the HashTable randomization patch, because both were advocated to fix the `unserialize()` and `json_decode()`, too. Just a quick look at it tells me that I don't like this patch either. It adds code to each POST handler. The POST handler interface is something extensions can extend. With Laurence's patch: suddenly all extensions that implement their own POST handlers must add the max_input_vars check. Of course I am biased, because suhosin is one of the affected extensions. But that said suhosin has a limit similar to max_input_vars for 7 years now. Regards, Stefan Esser --- ## #57295 — Xinchen Hui — 2012-01-09T16:36:39+00:00 URL: https://externals.io/message/57291#57295 · In reply to: #57291 Hi: I have a new idea, which is simple and also works for Jason/serialized etc. That is Restricting a max length of a buckets list in a hash table. If a bucket's length exceed 1024, any insertion into this bucket will return failure and a warning will be generated. What do you think? Sent from my iPhone 在 2012-1-9，23:42，Pierre Joye 写道： > hi, > > Moving this discussion here as it makes little to non sense to discuss > that any longer on security@ > > We are now very late behind an acceptable delay to provide a fix for > the hash DoS, to say it nicely. > > I'd strongly suggest to release 5.3.9 (RC5 has been tested now) final > this week using the max_input_vars fix, with the modification from > Laruence (but with a larger limit). Laruence addition also fixes > serialize or json, which are parts that need this fix as well as it is > impossible to valid a string manually (length check only is not enough > or cannot work in all cases). > > But 1st of all, the fix addition has to be applied and fully tested. > But if the addition is not desired yet, then we must at least release > 5.3.9 with Dmitry's fix only and we can fix json&serialize later, > ideally within 2 weeks max. > > Cheers, > -- > Pierre > > @pierrejoye | http://blog.thepimp.net | http://www.libgd.org --- ## #57297 — Stefan Esser — 2012-01-09T16:39:56+00:00 URL: https://externals.io/message/57291#57297 · In reply to: #57295 Hey, > That is Restricting a max length of a buckets list in a hash table. > > If a bucket's length exceed 1024, any insertion into this bucket > will return failure and a warning will be generated. > > What do you think? very bad idea. Especially when it comes to numerical indices a legitimate application might put data into a big array and have legitimate colliding keys. Regards, Stefan Esser --- ## #57296 — johannes@schlueters.de — 2012-01-09T16:40:51+00:00 URL: https://externals.io/message/57291#57296 · In reply to: #57291 I was under the impression that somebody worked on the information disclosure issue in the error message and the error message spamming. This seems not to be the case. If you, Pierre, are ready for Windows builds tomorrow morning I'd like to release tomorrow as is. johannes > hi, > > Moving this discussion here as it makes little to non sense to discuss > that any longer on security@ > > We are now very late behind an acceptable delay to provide a fix for > the hash DoS, to say it nicely. > > I'd strongly suggest to release 5.3.9 (RC5 has been tested now) final > this week using the max_input_vars fix, with the modification from > Laruence (but with a larger limit). Laruence addition also fixes > serialize or json, which are parts that need this fix as well as it is > impossible to valid a string manually (length check only is not enough > or cannot work in all cases). > > But 1st of all, the fix addition has to be applied and fully tested. > But if the addition is not desired yet, then we must at least release > 5.3.9 with Dmitry's fix only and we can fix json&serialize later, > ideally within 2 weeks max. > > Cheers, --- ## #57298 — Pierre Joye — 2012-01-09T16:48:31+00:00 URL: https://externals.io/message/57291#57298 · In reply to: #57293 > Dear Pierre and others, > > > […] > > Why do you advocate a patch from Laruence that randomizes the size of the HashTable, which does not fix the HashDOS security problem at all? I do not, I refer to his other patch which does exactly what Dmitry's one does and uses the same limit for json and serialize. I'm actually against the randomize version of the fix as we have not yet enough clue about how good (or bad) it is. Cheers, -- Pierre @pierrejoye | http://blog.thepimp.net | http://www.libgd.org --- ## #57299 — Xinchen Hui — 2012-01-09T16:50:11+00:00 URL: https://externals.io/message/57291#57299 · In reply to: #57297 Hi: I am not sure whether you have understood my point. If an array have more than 1024 buckets in an same bucket list(same index), there must already be an performance issue. Sent from my iPhone 在 2012-1-10，0:41，Stefan Esser 写道： > Hey, > > > […] > > very bad idea. Especially when it comes to numerical indices a legitimate application might put data into a big array and have legitimate colliding keys. > > Regards, > Stefan Esser --- ## #57300 — Pierre Joye — 2012-01-09T16:50:32+00:00 URL: https://externals.io/message/57291#57300 · In reply to: #57294 > Of course I am biased, because suhosin is one of the affected extensions. But that said suhosin has a limit similar to max_input_vars for 7 years now. Not really the same, but yes. While the reasons you did it was not the same. Also the length check is not related or cannot be used for this fix. But nice self promotion ;-) -- Pierre @pierrejoye | http://blog.thepimp.net | http://www.libgd.org --- ## #57301 — Nikita Popov — 2012-01-09T16:54:18+00:00 URL: https://externals.io/message/57291#57301 · In reply to: #57295 > Hi: >   I have a new idea, which is simple and also works for Jason/serialized etc. > >  That is Restricting a max length of a buckets list in a hash table. > >   If a bucket's length exceed 1024, any insertion into this bucket > will return failure and a warning will be generated. > >   What do you think? That seems like a very good approach (until we have randomization). It would fix the issue in a generic way so not all functions need to be patched one by one. It also will not hurt legit uses of many POST variables (or large serialized arrays). --- ## #57302 — Pierre Joye — 2012-01-09T16:57:34+00:00 URL: https://externals.io/message/57291#57302 · In reply to: #57295 hi, No time for new ideas yet. We cannot afford to implement, test and valid new propositions and provide a fix as soon as possible (read: in the next days). What's the status of your patch? The max input var one, not the random (or derived version), can you post it in this thread again for the record please? If not, we will go final with the current fix in 5.3. > Hi: >   I have a new idea, which is simple and also works for Jason/serialized etc. > >  That is Restricting a max length of a buckets list in a hash table. > >   If a bucket's length exceed 1024, any insertion into this bucket > will return failure and a warning will be generated. > >   What do you think? > > Sent from my iPhone > > 在 2012-1-9，23:42，Pierre Joye 写道： > > > […] -- Pierre @pierrejoye | http://blog.thepimp.net | http://www.libgd.org --- ## #57303 — Xinchen Hui — 2012-01-09T17:02:17+00:00 URL: https://externals.io/message/57291#57303 · In reply to: #57302 Sent from my iPhone 在 2012-1-10，0:57，Pierre Joye 写道： > hi, > > No time for new ideas yet. We cannot afford to implement, test and > valid new propositions and provide a fix as soon as possible (read: in > the next days) That idea will only need one hour to be implemented. :) Anyone who have time now can do that ? > > What's the status of your patch? The max input var one, not the random > (or derived version), can you post it in this thread again for the > record please? Sorry, can't now, it's 01:00am here. > > If not, we will go final with the current fix in 5.3. > > > > […] > > > > -- > Pierre > > @pierrejoye | http://blog.thepimp.net | http://www.libgd.org --- ## #57304 — Stefan Esser — 2012-01-09T17:03:08+00:00 URL: https://externals.io/message/57291#57304 · In reply to: #57300 Hello Pierre, > Not really the same, but yes. While the reasons you did it was not the > same. Also the length check is not related or cannot be used for this > fix. But nice self promotion ;-) Considering the fact that the HashDOS problem was originally discussed in a paper 2003, someone discussed HashDOS vs. PHP originally somewhen in 2004 and Hardened-PHP came out in 2004 it is funny that you believe to know, why I added variable count restrictions. Regards, Stefan Esser --- ## #57305 — Stefan Esser — 2012-01-09T17:05:58+00:00 URL: https://externals.io/message/57291#57305 · In reply to: #57299 Hello, > I am not sure whether you have understood my point. I understood your point: you want to break HashTables because 1024 colliding entries could have an performance impact. This could break thousands of scripts. for ($i=0; $i<2000; $i++) $arr[$i<<16] = 1; would stop working, while it should not. Regards, Stefan Esser --- ## #57306 — Xinchen Hui — 2012-01-09T17:12:49+00:00 URL: https://externals.io/message/57291#57306 · In reply to: #57305 Sent from my iPhone 在 2012-1-10，1:07，Stefan Esser 写道： > Hello, > > > […] > I understood your point: you want to break HashTables because 1024 colliding entries could have an performance impact. This could break thousands of scripts. > > for ($i=0; $i<2000; $i++) $arr[$i<<16] = 1; > > would stop working, while it should not. Sure, but why do you want to do this? Kill your own pc? So I can not agree with you on "*thousands* scripts". And if 1024 is not enough, then 2048, 4096 at most. Thanks > > Regards, > Stefan Esser --- ## #57307 — Rasmus Lerdorf — 2012-01-09T17:14:57+00:00 URL: https://externals.io/message/57291#57307 · In reply to: #57299 > Hi: > I am not sure whether you have understood my point. > > If an array have more than 1024 buckets in an same bucket > list(same index), there must already be an performance issue. The problem is you really need to consider the source. There are many places where people deal with huge datasets. If they assign it directly they shouldn't hit any limits or we would need some sort of "large array" hint which would be nasty. -Rasmus --- ## #57308 — Xinchen Hui — 2012-01-09T17:18:38+00:00 URL: https://externals.io/message/57291#57308 · In reply to: #57307 Sent from my iPhone 在 2012-1-10，1:14，Rasmus Lerdorf 写道： > > > […] > > The problem is you really need to consider the source. There are many > places where people deal with huge datasets. If they assign it directly > they shouldn't hit any limits or we would need some sort of "large > array" hint which would be nasty. Rasmus: Large array ! = Large list An array can have million elements withou exceed the limit ion of max length of list. Thanks > > -Rasmus --- ## #57309 — Xinchen Hui — 2012-01-09T17:22:10+00:00 URL: https://externals.io/message/57291#57309 · In reply to: #57308 Sent from my iPhone 在 2012-1-10，1:18，Xinchen Hui 写道： > Sent from my iPhone > > 在 2012-1-10，1:14，Rasmus Lerdorf 写道： > > > […] > Rasmus: > > Large array ! = Large list > > An array can have million elements withou exceed the limit ion of max > length of list. > > Thanks And sorry I can not do it now ,since it's really later here now and I have getup early tomorrow to work. So anyone who have time can try to implement it, just remember also do limit in resize hash logic. Thanks very much. > > […] --- ## #57310 — Rasmus Lerdorf — 2012-01-09T17:51:45+00:00 URL: https://externals.io/message/57291#57310 · In reply to: #57308 > Sent from my iPhone > > 在 2012-1-10，1:14，Rasmus Lerdorf 写道： > > > […] > Rasmus: > > Large array ! = Large list > > An array can have million elements withou exceed the limit ion of max > length of list. I understand the difference. But large arrays are obviously the ones that are prone to hitting the collision limits. -Rasmus --- ## #57311 — John Crenshaw — 2012-01-09T19:00:16+00:00 URL: https://externals.io/message/57291#57311 · In reply to: #57301 > -----Original Message----- > From: Nikita Popov [mailto:nikita.ppv@googlemail.com] > Sent: Monday, January 09, 2012 11:54 AM > To: Xinchen Hui > Cc: Pierre Joye; PHP internals; Johannes Schlüter; Laruence > Subject: Re: [PHP-DEV] Re: 5.3.9, Hash DoS, release > > > > […] > > That seems like a very good approach (until we have randomization). It would > fix the issue in a generic way so not all functions need to be patched one by > one. It also will not hurt legit uses of many POST variables (or large > serialized arrays). > > -- > Yuck. Bad idea. Collisions happen, and for most hash algorithms there are plenty of perfectly likely key sequences that will collide badly. There are two problems here: 1. Large data sets have the potential to behave poorly if things collide badly 2. An attacker may initiate a DoS attack by supplying a large set of data that is known to collide badly To mitigate the impact of collisions, how about using a dynamic bucket behavior? Use a flat list for small/medium buckets, switch to a second level of hashing if the bucket grows beyond a certain size. Something like md5 could be used as part of the hash key calculation at deeper levels to ensure that the buckets don't infinitely collide. This covers the basic performance implications. To prevent DoS, it has to be impossible for a malicious user to compute a problematic sequence of data. If the bucket level key computation includes an additional cryptographic transformation of any sort using a secret value unique to the machine (or unique to the process) that is handling the request, it would be impossible for an attacker to compute a problematic sequence of keys, which should close the door on DoS. John Crenshaw Priacta, Inc. --- ## #57313 — Xinchen Hui — 2012-01-10T01:28:20+00:00 URL: https://externals.io/message/57291#57313 Sent from my iPhone 在 2012-1-10，1:51，Rasmus Lerdorf 写道： > > > […] > > I understand the difference. But large arrays are obviously the ones > that are prone to hitting the collision limits. Yes, but don't you think this is at least better than restricting number of elements? :) Thanks > > -Rasmus --- ## #57314 — Rasmus Lerdorf — 2012-01-10T01:48:55+00:00 URL: https://externals.io/message/57291#57314 · In reply to: #57313 > > […] > Yes, but don't you think this is at least better than restricting > number of elements? :) The difference is the source. If, for example, I have a huge array cached in APC's user cache which I built up over time and I apc_fetch() it directly, I would not expect to run into any such limits. However, if I hit an external source and parse untrusted xml/json data then I would appreciate being able to protect myself from this sort of attack. -Rasmus --- ## #57316 — Xinchen Hui — 2012-01-10T03:12:41+00:00 URL: https://externals.io/message/57291#57316 · In reply to: #57302 > hi, > > No time for new ideas yet. We cannot afford to implement, test and > valid new propositions and provide a fix as soon as possible (read: in > the next days). > > What's the status of your patch? The max input var one, not the random > (or derived version), can you post it in this thread again for the > record please? Hi, FYI thanks > > If not, we will go final with the current fix in 5.3. > > > > […] > > > > -- > Pierre > > @pierrejoye | http://blog.thepimp.net | http://www.libgd.org -- 惠新宸        laruence Senior PHP Engineer http://www.laruence.com --- ## #57322 — jpauli — 2012-01-10T10:06:50+00:00 URL: https://externals.io/message/57291#57322 · In reply to: #57316 2012/1/10 Xinchen Hui > On Tue, Jan 10, 2012 at 12:57 AM, Pierre Joye > wrote: > > […] > Hi, FYI > > thanks > > […] > Jason/serialized etc. > > […] > > > > -- > 惠新宸 laruence > Senior PHP Engineer > http://www.laruence.com > > > -- > > > Why not double hashing (http://en.wikipedia.org/wiki/Double_hashing) somelike John Crenshaw proposed ? Julien