Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 01/17/2012 09:29 PM, "Martin v. Löwis" wrote: I(0) = H& MASK PERTURB(0) = H I(n+1) = (5*I(n) + 1 + PERTURB(n))& MASK PERTURN(n+1) = PERTURB(n)>> 5 So if two objects O1 and O2 have the same hash value H, the sequence of probed indices is the same for any MASK value. It will

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

2012/1/18 "Martin v. Löwis" : > For 3.3 onwards, I'm skeptical whether all this configuration support is > really necessary. I think a much smaller patch which leaves no choice > would be more appropriate. The configuration helps unit testing: see changes on Lib/test/*.py in my last patch. I hesit

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Am 18.01.2012 07:06, schrieb Gregory P. Smith: > > On Tue, Jan 17, 2012 at 12:52 PM, "Martin v. Löwis" > wrote: > > > I plan to commit my fix to Python 3.3 if it is accepted. Then write a > > simplified version to Python 3.2 and backport it to 3.1. > > I'm

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Tue, Jan 17, 2012 at 12:52 PM, "Martin v. Löwis" wrote: > > I plan to commit my fix to Python 3.3 if it is accepted. Then write a > > simplified version to Python 3.2 and backport it to 3.1. > > I'm opposed to any change to the hash values of strings in maintenance > releases, so I guess I'm op

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

If randomized hash cannot be turned on by default, an alternative is to switch them off by default, and add an option (command line option, environment variable, etc.) to enable it. That won't really fix the problem. If people install a new release because it fixes a vulnerability, it better doe

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

>> I plan to commit my fix to Python 3.3 if it is accepted. Then write a >> simplified version to Python 3.2 and backport it to 3.1. > > I'm opposed to any change to the hash values of strings in maintenance > releases, so I guess I'm opposed to your patch in principle. If randomized hash cannot b

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> I plan to commit my fix to Python 3.3 if it is accepted. Then write a > simplified version to Python 3.2 and backport it to 3.1. I'm opposed to any change to the hash values of strings in maintenance releases, so I guess I'm opposed to your patch in principle. See my next message for an alterna

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> I thought that the original problem was that with N insertions in the > dictionary, by repeatedly inserting different keys generating the same > hash value an attacker could arrange that the cost of finding an open > slot is O(N), and thus the cost of N insertions is O(N^2). > > If so, frequent

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Jeremy Sanders wrote: > Victor Stinner wrote: > >> If hash(str1)&DICT_MASK == hash(str2)&DICT_MASK but >> hash(str1)!=hash(str2), strings are not compared (this is a common >> optimization in Python), and the so the attack would not be successful >> (it would be slow, but not as slow as comparing

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Victor Stinner wrote: > If hash(str1)&DICT_MASK == hash(str2)&DICT_MASK but > hash(str1)!=hash(str2), strings are not compared (this is a common > optimization in Python), and the so the attack would not be successful > (it would be slow, but not as slow as comparing two strings). It's a shame th

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

I finished my patch transforming hash(str) to a randomized hash function, see random-8.patch attached to the issue: http://bugs.python.org/issue13703 The remaining question is which random number generator should be used on Windows to initialize the hash secret (CryptoGen adds an overhead of 10%,

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> I thought that the original problem was that with N insertions in the > dictionary, by repeatedly inserting different keys generating the same > hash value an attacker could arrange that the cost of finding an open > slot is O(N), and thus the cost of N insertions is O(N^2). > > If so, frequent r

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

mar...@v.loewis.de writes: > >> It doesn't change anything, you will still get collisions. > > > > > > That depends right? If the collision is because they all have the same > > hash(), yes. It might be different if it is because the secondary hashing > > (or whatever it's called :-) causes c

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

It doesn't change anything, you will still get collisions. That depends right? If the collision is because they all have the same hash(), yes. It might be different if it is because the secondary hashing (or whatever it's called :-) causes collisions. But Python deals with the latter case jus

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Mon, Jan 16, 2012 at 4:16 PM, Victor Stinner < victor.stin...@haypocalc.com> wrote: > 2012/1/17 Tim Delaney : > > What if in a pathological collision (e.g. > 1000 collisions), we > increased > > the size of a dict by a small but random amount? > > It doesn't change anything, you will still get

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

2012/1/17 Tim Delaney : > What if in a pathological collision (e.g. > 1000 collisions), we increased > the size of a dict by a small but random amount? It doesn't change anything, you will still get collisions. Victor ___ Python-Dev mailing list Python-

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 17 January 2012 10:14, Tim Delaney wrote: > On 17 January 2012 09:23, Paul McMillan wrote: > >> This is why the "simply throw an error" solution isn't a complete fix. >> Making portions of an interface unusable for regular users is clearly >> a bad thing, and is clearly applicable to other ty

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 17 January 2012 09:23, Paul McMillan wrote: > This is why the "simply throw an error" solution isn't a complete fix. > Making portions of an interface unusable for regular users is clearly > a bad thing, and is clearly applicable to other types of poisoned data > as well. We need to detect col

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> As I understand it, the way the attack works is that a *single* > malicious request from the attacker can DoS the server by eating CPU > resources while evaluating a massive collision chain induced in a dict > by attacker supplied data. Explicitly truncating the collision chain > boots them out a

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sun, Jan 15, 2012 at 9:44 AM, Guido van Rossum wrote: > On Sun, Jan 15, 2012 at 8:46 AM, Stefan Behnel wrote: > >> Guido van Rossum, 15.01.2012 17:10: >> > On Sun, Jan 15, 2012 at 6:30 AM, Stefan Behnel wrote: >> >> Terry Reedy, 14.01.2012 06:43: >> >>> On 1/13/2012 8:58 PM, Gregory P. Smith w

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sun, Jan 15, 2012 at 8:46 AM, Stefan Behnel wrote: > Guido van Rossum, 15.01.2012 17:10: > > On Sun, Jan 15, 2012 at 6:30 AM, Stefan Behnel wrote: > >> Terry Reedy, 14.01.2012 06:43: > >>> On 1/13/2012 8:58 PM, Gregory P. Smith wrote: > >>> > It is perfectly okay to break existing users w

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sun, 15 Jan 2012 17:46:36 +0100 Stefan Behnel wrote: > Guido van Rossum, 15.01.2012 17:10: > > On Sun, Jan 15, 2012 at 6:30 AM, Stefan Behnel wrote: > >> Terry Reedy, 14.01.2012 06:43: > >>> On 1/13/2012 8:58 PM, Gregory P. Smith wrote: > >>> > It is perfectly okay to break existing users

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sun, Jan 15, 2012 at 8:46 AM, Stefan Behnel wrote: > > It also seems to me that the wording "has a hash value which never changes > during its lifetime" makes it pretty clear that the lifetime of the hash > value is not guaranteed to supersede the lifetime of the object (although > that's a rat

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Guido van Rossum, 15.01.2012 17:10: > On Sun, Jan 15, 2012 at 6:30 AM, Stefan Behnel wrote: >> Terry Reedy, 14.01.2012 06:43: >>> On 1/13/2012 8:58 PM, Gregory P. Smith wrote: >>> It is perfectly okay to break existing users who had anything depending on ordering of internal hash tables.

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sun, Jan 15, 2012 at 6:30 AM, Stefan Behnel wrote: > Terry Reedy, 14.01.2012 06:43: > > On 1/13/2012 8:58 PM, Gregory P. Smith wrote: > > > >> It is perfectly okay to break existing users who had anything depending > >> on ordering of internal hash tables. Their code was already broken. > > >

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Terry Reedy, 14.01.2012 06:43: > On 1/13/2012 8:58 PM, Gregory P. Smith wrote: > >> It is perfectly okay to break existing users who had anything depending >> on ordering of internal hash tables. Their code was already broken. > > Given that the doc says "Return the hash value of the object", I d

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sun, Jan 15, 2012 at 2:42 PM, Steven D'Aprano wrote: > Victor Stinner wrote: > >> - Marc Andre Lemburg proposes to fix the vulnerability directly in >> dict (for any key type). The patch raises an exception if a lookup >> causes more than 1000 collisions. > > > > Am I missing something? How doe

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Guido van Rossum wrote: On Fri, Jan 13, 2012 at 5:58 PM, Gregory P. Smith wrote: It is perfectly okay to break existing users who had anything depending on ordering of internal hash tables. Their code was already broken. We *will*provide a flag and/or environment variable that can be set to t

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Victor Stinner wrote: - Marc Andre Lemburg proposes to fix the vulnerability directly in dict (for any key type). The patch raises an exception if a lookup causes more than 1000 collisions. Am I missing something? How does this fix the vulnerability? It seems to me that the only thing this d

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

FWIW the quick change i pastebin'ed is basically covered by the change already under review in http://bugs.python.org/review/13704/show. I've made my comments and suggestions there. I looked into Modules/expat/xmlparse.c and it has an odd copy of the old string hash algorithm entirely for its own

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

My patch example does change the bytes object hash as well as Unicode. On Jan 13, 2012 7:46 PM, wrote: > What an implementation looks like: >> >> http://pastebin.com/9ydETTag >> >> some stuff to be filled in, but this is all that is really required. >> > > I think this statement (and the patch)

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Am 14.01.2012 01:37, schrieb Benjamin Peterson: > 2012/1/13 Guido van Rossum : >> Really? Even though you came up with specifically to prove me wrong? > > Coming up with a counterexample now invalidates it? There are two concerns here: - is it possible to come up with an example of constructed va

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Am 13.01.2012 18:08, schrieb Mark Dickinson: > On Fri, Jan 13, 2012 at 2:57 AM, Guido van Rossum wrote: >> How >> pathological the data needs to be before the collision counter triggers? I'd >> expect *very* pathological. > > How pathological do you consider the set > >{1 << n for n in range

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

I think this statement (and the patch) is wrong. You also need to change the byte string hashing, at least for 2.x. This I consider the biggest flaw in that approach - other people may have written string-like objects which continue to compare equal to a string but now hash different. They're un

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sat, 14 Jan 2012 13:55:22 +1100 Steven D'Aprano wrote: > On 14/01/12 12:58, Gregory P. Smith wrote: > > > I do like *randomly seeding the hash*. *+1*. This is easy. It can easily be > > back ported to any Python version. > > > > It is perfectly okay to break existing users who had anything dep

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sat, 14 Jan 2012 04:45:57 +0100 mar...@v.loewis.de wrote: > > What an implementation looks like: > > > > http://pastebin.com/9ydETTag > > > > some stuff to be filled in, but this is all that is really required. > > I think this statement (and the patch) is wrong. You also need to change > the

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Jack Diederich writes: > On Thu, Jan 12, 2012 at 9:57 PM, Guido van Rossum wrote: > > Hm... I started out as a big fan of the randomized hash, but thinking more > > about it, I actually believe that the chances of some legitimate app having > >>1000 collisions are way smaller than the chances

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Sat, Jan 14, 2012 at 4:24 PM, Jack Diederich wrote: >> This is depending on how the counting is done (I didn't look at MAL's >> patch), and assuming that increasing the hash table size will generally >> reduce collisions if items collide but their hashes are different. > > The patch counts conf

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Thu, Jan 12, 2012 at 9:57 PM, Guido van Rossum wrote: > Hm... I started out as a big fan of the randomized hash, but thinking more > about it, I actually believe that the chances of some legitimate app having >>1000 collisions are way smaller than the chances that somebody's code will > break d

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 1/13/2012 8:58 PM, Gregory P. Smith wrote: It is perfectly okay to break existing users who had anything depending on ordering of internal hash tables. Their code was already broken. Given that the doc says "Return the hash value of the object", I do not think we should be so hard-nosed. T

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 5:58 PM, Gregory P. Smith wrote: > It is perfectly okay to break existing users who had anything depending on > ordering of internal hash tables. Their code was already broken. We > *will*provide a flag and/or environment variable that can be set to turn the > feature off

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

What an implementation looks like: http://pastebin.com/9ydETTag some stuff to be filled in, but this is all that is really required. I think this statement (and the patch) is wrong. You also need to change the byte string hashing, at least for 2.x. This I consider the biggest flaw in that app

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Jan 13, 2012, at 05:38 PM, Guido van Rossum wrote: >On Fri, Jan 13, 2012 at 5:17 PM, Antoine Pitrou wrote: > >> Breaking due to variable hashing is deterministic: you notice it as >> soon as you upgrade (and then you use PYTHONHASHSEED to disable >> variable hashing). That seems better than un

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 5:58 PM, Gregory P. Smith wrote: > > On Fri, Jan 13, 2012 at 5:38 PM, Guido van Rossum wrote: > >> On Fri, Jan 13, 2012 at 5:17 PM, Antoine Pitrou wrote: >> >>> On Thu, 12 Jan 2012 18:57:42 -0800 >>> Guido van Rossum wrote: >>> > Hm... I started out as a big fan of the ra

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 14/01/12 12:58, Gregory P. Smith wrote: I do like *randomly seeding the hash*. *+1*. This is easy. It can easily be back ported to any Python version. It is perfectly okay to break existing users who had anything depending on ordering of internal hash tables. Their code was already broken.

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

btw, Tim's commit message on this one is amusingly relevant. :) http://hg.python.org/cpython/diff/8d2f2cb9/Objects/dictobject.c On Fri, Jan 13, 2012 at 6:25 PM, Gregory P. Smith wrote: > >> Clearly these ideas are more complex than adding randomization, but >> adding randomization doesn't

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> > > Clearly these ideas are more complex than adding randomization, but adding > randomization doesn't seem to be produce immunity from attack, when data > about the randomness is leaked. > Which will not normally happen. I'm firmly in the camp that believes the random seed can be probed and de

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 1/13/2012 5:35 PM, Victor Stinner wrote: - Glenn Linderman proposes to fix the vulnerability by adding a new "safe" dict type (only accepting string keys). His proof-of-concept (SafeDict.py) uses a secret of 64 random bits and uses it to compute the hash of a key. We could mix Marc's collisio

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 5:38 PM, Guido van Rossum wrote: > On Fri, Jan 13, 2012 at 5:17 PM, Antoine Pitrou wrote: > >> On Thu, 12 Jan 2012 18:57:42 -0800 >> Guido van Rossum wrote: >> > Hm... I started out as a big fan of the randomized hash, but thinking >> more >> > about it, I actually believ

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 5:17 PM, Antoine Pitrou wrote: > On Thu, 12 Jan 2012 18:57:42 -0800 > Guido van Rossum wrote: > > Hm... I started out as a big fan of the randomized hash, but thinking > more > > about it, I actually believe that the chances of some legitimate app > having > > >1000 colli

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> - Glenn Linderman proposes to fix the vulnerability by adding a new > "safe" dict type (only accepting string keys). His proof-of-concept > (SafeDict.py) uses a secret of 64 random bits and uses it to compute > the hash of a key. We could mix Marc's collision counter with SafeDict idea (being ab

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Thu, 12 Jan 2012 18:57:42 -0800 Guido van Rossum wrote: > Hm... I started out as a big fan of the randomized hash, but thinking more > about it, I actually believe that the chances of some legitimate app having > >1000 collisions are way smaller than the chances that somebody's code will > brea

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

2012/1/13 Guido van Rossum : > Really? Even though you came up with specifically to prove me wrong? Coming up with a counterexample now invalidates it? -- Regards, Benjamin ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mail

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 10:13 AM, Mark Dickinson wrote: > On Fri, Jan 13, 2012 at 5:43 PM, Guido van Rossum > wrote: > >> How pathological do you consider the set > >> > >> {1 << n for n in range(2000)} > >> > >> to be? What about the set: > >> > >> ieee754_powers_of_two = {2.0**n for n in

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 5:43 PM, Guido van Rossum wrote: >> How pathological do you consider the set >> >>   {1 << n for n in range(2000)} >> >> to be?  What about the set: >> >>   ieee754_powers_of_two = {2.0**n for n in range(-1074, 1024)} >> >> ?  The > 2000 elements of the latter set have only

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 9:08 AM, Mark Dickinson wrote: > On Fri, Jan 13, 2012 at 2:57 AM, Guido van Rossum > wrote: > > How > > pathological the data needs to be before the collision counter triggers? > I'd > > expect *very* pathological. > > How pathological do you consider the set > > {1 <<

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 2:57 AM, Guido van Rossum wrote: > How > pathological the data needs to be before the collision counter triggers? I'd > expect *very* pathological. How pathological do you consider the set {1 << n for n in range(2000)} to be? What about the set: ieee754_powers_of

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On 2012-01-13 11:20, Lennart Regebro wrote: The vulnerability is basically only in the dictionary you keep the form data you get from a request. I'd have to disagree with this statement. The vulnerability is anywhere that creates a dictionary (or set) from attacker-provided keys. That would i

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Unfortunately it requires only a few seconds to compute enough 32bit collisions on one core with no precomputed data. Are you running the hash function "backward" to generate strings with the same value, or you are more trying something like brute forcing? If you try it brute force to hit a s

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

On Fri, Jan 13, 2012 at 02:24, Victor Stinner wrote: > - Glenn Linderman proposes to fix the vulnerability by adding a new > "safe" dict type (only accepting string keys). His proof-of-concept > (SafeDict.py) uses a secret of 64 random bits and uses it to compute > the hash of a key. This is my p

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

> Unfortunately it requires only a few seconds to compute enough 32bit > collisions on one core with no precomputed data. Are you running the hash function "backward" to generate strings with the same value, or you are more trying something like brute forcing? And how do you get the hash secret?

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Am 13.01.2012 02:24, schrieb Victor Stinner: My patch doesn't fix the DoS, it just make the attack more complex. The attacker cannot pregenerate data for an attack: (s)he has first to compute the hash secret, and then compute hash collisions using the secret. The hash secret is a least 64 bits lo

Re: [Python-Dev] Status of the fix for the hash collision vulnerability

Hm... I started out as a big fan of the randomized hash, but thinking more about it, I actually believe that the chances of some legitimate app having >1000 collisions are way smaller than the chances that somebody's code will break due to the variable hashing. In fact we know for a fact that the l

[Python-Dev] Status of the fix for the hash collision vulnerability

Many people proposed their own idea to fix the vulnerability, but only 3 wrote a patch: - Glenn Linderman proposes to fix the vulnerability by adding a new "safe" dict type (only accepting string keys). His proof-of-concept (SafeDict.py) uses a secret of 64 random bits and uses it to compute the h