In http://mail.python.org/pipermail/python-dev/2012-January/115715.html
Frank Sievertsen wrote:
Am 20.01.2012 13:08, schrieb Victor Stinner:
>>> I'm surprised we haven't seen bug reports about it from users
>>> of 64-bit Pythons long ago
>> A Python dictionary only uses the lower bits of a hash
Interesting idea, and I see it would avoid conversions. What happens
if the data area also removed from the hash? So you enter 20
colliding keys, then 20 more that get randomized, then delete the 18
of the first 20. Can you still find the second 20 keys? Takes two
sets of probes, somehow?
On 1/23/2012 1:25 PM, Glenn Linderman wrote:
On 1/23/2012 12:53 AM, Frank Sievertsen wrote:
What if we use a second (randomized) hash-function in case there
are many collisions in ONE lookup. This hash-function is used only
for collision resolution and is not cached.
So this sounds like SafeD
Frank Sievertsen wrote:
> Hello,
>
> I'd still prefer to see a randomized hash()-function (at least for 3.3).
>
> But to protect against the attacks it would be sufficient to use
> randomization for collision resolution in dicts (and sets).
>
> What if we use a second (randomized) hash-function
On 1/23/2012 10:58 AM, Frank Sievertsen wrote:
On 23.01.2012 19:25, Glenn Linderman wrote:
So this sounds like SafeDict, but putting it under the covers and
automatically converting from dict to SafeDict after a collision
threshold has been reached. Let's call it fallback-dict.
and costs:
On 23.01.2012 19:25, Glenn Linderman wrote:
So this sounds like SafeDict, but putting it under the covers and
automatically converting from dict to SafeDict after a collision
threshold has been reached. Let's call it fallback-dict.
and costs:
* converting the dict from one hash to the othe
On 1/23/2012 12:53 AM, Frank Sievertsen wrote:
What if we use a second (randomized) hash-function in case there
are many collisions in ONE lookup. This hash-function is used only
for collision resolution and is not cached.
So this sounds like SafeDict, but putting it under the covers and
aut
Hello,
I'd still prefer to see a randomized hash()-function (at least for 3.3).
But to protect against the attacks it would be sufficient to use
randomization for collision resolution in dicts (and sets).
What if we use a second (randomized) hash-function in case there
are many collisions in ON
On 23 January 2012 16:49, Lennart Regebro wrote:
> On Mon, Jan 23, 2012 at 06:02, Paul McMillan wrote:
> >> We may use a different salt per dictionary.
> >
> > If we're willing to re-hash everything on a per-dictionary basis. That
> > doesn't seem reasonable given our existing usage.
>
> Well, i
Lennart Regebro writes:
> On Mon, Jan 23, 2012 at 06:02, Paul McMillan wrote:
> >> We may use a different salt per dictionary.
> >
> > If we're willing to re-hash everything on a per-dictionary basis. That
> > doesn't seem reasonable given our existing usage.
>
> Well, if we get crazy amou
On Mon, Jan 23, 2012 at 06:02, Paul McMillan wrote:
>> We may use a different salt per dictionary.
>
> If we're willing to re-hash everything on a per-dictionary basis. That
> doesn't seem reasonable given our existing usage.
Well, if we get crazy amounts of collisions, re-hashing with a new
salt
> We may use a different salt per dictionary.
If we're willing to re-hash everything on a per-dictionary basis. That
doesn't seem reasonable given our existing usage.
___
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listin
I think this thread is approaching the recursion limit.
Be careful not to blow the stack :)
Regards
Antoine.
On Sun, 22 Jan 2012 20:53:41 +0100
Lennart Regebro wrote:
> On Sun, Jan 22, 2012 at 11:11, Victor Stinner
> wrote:
> >> This seed is chosen randomly at runtime, but cannot
> >> change
On Sun, Jan 22, 2012 at 11:11, Victor Stinner
wrote:
>> This seed is chosen randomly at runtime, but cannot
>> change once chosen.
>
> The hash is used to compare objects: if hash(obj1) != hash(obj2),
> objects are considered different. So two strings must have the same
> hash if their value is th
> This seed is chosen randomly at runtime, but cannot
> change once chosen.
The hash is used to compare objects: if hash(obj1) != hash(obj2),
objects are considered different. So two strings must have the same
hash if their value is the same.
> Salt could also be an appropriate term here, but sin
> I may have a terminology problem here. I expect that a random seed must
> change every time it is used, otherwise the pseudorandom number generator
> using it just returns the same value each time. Should we be talking about a
> salt rather than a seed?
You should read the several other threads,
Paul McMillan wrote:
On Sat, Jan 21, 2012 at 4:19 PM, Jared Grubb wrote:
I agree; it sounds really odd to throw an exception since nothing is actually
wrong and there's nothing the caller would do about it to recover anyway.
Rather than throwing an exception, maybe you just reseed the random
On Sat, Jan 21, 2012 at 4:19 PM, Jared Grubb wrote:
> I agree; it sounds really odd to throw an exception since nothing is actually
> wrong and there's nothing the caller would do about it to recover anyway.
> Rather than throwing an exception, maybe you just reseed the random value for
> the h
On 20 Jan 2012, at 10:49, Brett Cannon wrote:
> Why can't we have our cake and eat it too?
>
> Can we do hash randomization in 3.3 and use the hash count solution for
> bugfix releases? That way we get a basic fix into the bugfix releases that
> won't break people's code (hopefully) but we go wi
On Fri, 2012-01-20 at 16:55 +0100, Frank Sievertsen wrote:
> Hello,
>
> I still see at least two ways to create a DOS attack even with the
> collison-counting-patch.
[snip description of two types of attack on the collision counting
approach]
> What to do now?
> I think it's not smart to reduce
On Sat, Jan 21, 2012 at 7:50 AM, Matthew Woodcraft
wrote:
> Victor Stinner wrote:
>> I propose to solve the hash collision vulnerability by counting
>> collisions [...]
>
>> We now know all issues of the randomized hash solution, and I
>> think that there are more drawbacks than advantages. IMO
Victor Stinner wrote:
> I propose to solve the hash collision vulnerability by counting
> collisions [...]
> We now know all issues of the randomized hash solution, and I
> think that there are more drawbacks than advantages. IMO the
> randomized hash is overkill to fix the hash collision issue.
On Fri, Jan 20, 2012 at 6:33 PM, Steven D'Aprano wrote:
> Guido van Rossum wrote:
>>
>> It should derive from BaseException.
> RuntimeError meets that requirement, and it is an existing exception so
> there are no issues with introducing a new built-in exception to a point
> release.
>
> py> issu
2012/1/20 Steven D'Aprano :
> Guido van Rossum wrote:
>>
>> It should derive from BaseException.
>
>
> RuntimeError meets that requirement, and it is an existing exception so
> there are no issues with introducing a new built-in exception to a point
> release.
>
> py> issubclass(RuntimeError, BaseE
Guido van Rossum wrote:
It should derive from BaseException.
RuntimeError meets that requirement, and it is an existing exception so there
are no issues with introducing a new built-in exception to a point release.
py> issubclass(RuntimeError, BaseException)
True
--
Steven
Terry Reedy wrote:
On 1/20/2012 11:17 AM, Victor Stinner wrote:
There is no perfect solutions, drawbacks of each solution should be
compared.
Amen.
One possible attack that has been described for a collision counting
dict depends on knowing precisely the trigger point. So let
MAXCOLLISIONS
It should derive from BaseException.
--Guido van Rossum (sent from Android phone)
On Jan 20, 2012 4:59 PM, "Steven D'Aprano" wrote:
> Guido van Rossum wrote:
>
>> On Fri, Jan 20, 2012 at 11:51 AM, Donald Stufft
>> **wrote:
>>
>> On Friday, January 20, 2012 at 2:36 PM, Tres Seaver wrote:
>>>
>
Guido van Rossum wrote:
On Fri, Jan 20, 2012 at 11:51 AM, Donald Stufft wrote:
On Friday, January 20, 2012 at 2:36 PM, Tres Seaver wrote:
On 01/20/2012 02:04 PM, Donald Stufft wrote:
Even if a MemoryException is raised I believe that is still a
fundamental change in the documented contract o
On Fri, Jan 20, 2012 at 2:35 PM, Frank Sievertsen wrote:
> Am 20.01.2012 16:33, schrieb Guido van Rossum:
>
>> (I'm thinking that the original attack is trivial once the set of 65000
>> colliding keys is public knowledge, which must be only a matter of time.
>
>
>
> I think it's very likely that t
On Fri, Jan 20, 2012 at 2:33 PM, Ben Wolfson wrote:
> On Fri, Jan 20, 2012 at 2:11 PM, Terry Reedy wrote:
>> On 1/20/2012 2:51 PM, Donald Stufft wrote:
>>
>>> I think the counting collision is at best a bandaid and not a proper fix
>>> stemmed from a desire to not break existing applications on a
Am 20.01.2012 16:33, schrieb Guido van Rossum:
(I'm thinking that the original attack is trivial once the set of
65000 colliding keys is public knowledge, which must be only a matter
of time.
I think it's very likely that this will happen soon.
For ASP and PHP there is attack-payload publicl
I believe that either solution has the potential to break existing applications
so to ensure that no applications are broken there will need to be a method of
disabling it. I also believe that to maintain the backwards compatibility that
Python has traditionally had in bug fix releases that eith
On Fri, Jan 20, 2012 at 2:11 PM, Terry Reedy wrote:
> On 1/20/2012 2:51 PM, Donald Stufft wrote:
>
>> I think the counting collision is at best a bandaid and not a proper fix
>> stemmed from a desire to not break existing applications on a bugfix
>> release ...
>
> My opinion of counting is better
On 1/20/2012 2:51 PM, Donald Stufft wrote:
I think the counting collision is at best a bandaid and not a proper fix
stemmed from a desire to not break existing applications on a bugfix
release ...
My opinion of counting is better than yours, but even conceding the
theoretical, purity argument
On Fri, Jan 20, 2012 at 11:51 AM, Donald Stufft wrote:
> On Friday, January 20, 2012 at 2:36 PM, Tres Seaver wrote:
>
> On 01/20/2012 02:04 PM, Donald Stufft wrote:
>
> Even if a MemoryException is raised I believe that is still a
> fundamental change in the documented contract of dictionary API.
Donald Stufft wrote:
Even if a MemoryException is raised I believe that is still a
fundamental change in the documented contract of dictionary API. I don't
believe there is a way to fix this without breaking someones
application. The major differences I see between the two solutions is
that co
On Friday, January 20, 2012 at 2:36 PM, Tres Seaver wrote:
> -BEGIN PGP SIGNED MESSAGE-
> Hash: SHA1
>
> On 01/20/2012 02:04 PM, Donald Stufft wrote:
>
> > Even if a MemoryException is raised I believe that is still a
> > fundamental change in the documented contract of dictionary API
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
On 01/20/2012 02:04 PM, Donald Stufft wrote:
> Even if a MemoryException is raised I believe that is still a
> fundamental change in the documented contract of dictionary API.
How so? Dictionary inserts can *already* raise that error.
> I don't be
On 1/20/2012 10:55 AM, Frank Sievertsen wrote:
Hello,
I still see at least two ways to create a DOS attack even with the
collison-counting-patch.
2. The second attack actually attacks that 1000 allowed string
comparisons are still a lot of work.
First I added 999 strings that collide with a o
On Fri, Jan 20, 2012 at 8:17 AM, Victor Stinner
wrote:
>> So I still think we should ditch the paranoia about dictionary order
>> changing,
>> and fix this without counting.
>
> The randomized hash has other issues:
>
> - its security is based on its secret, whereas it looks to be easy to
> comp
Even if a MemoryException is raised I believe that is still a fundamental
change in the documented contract of dictionary API. I don't believe there is a
way to fix this without breaking someones application. The major differences I
see between the two solutions is that counting will break peopl
On 1/20/2012 11:17 AM, Victor Stinner wrote:
There is no perfect solutions, drawbacks of each solution should be compared.
Amen.
One possible attack that has been described for a collision counting
dict depends on knowing precisely the trigger point. So let
MAXCOLLISIONS either be configure
On Fri, Jan 20, 2012 at 13:15, Guido van Rossum wrote:
> On Fri, Jan 20, 2012 at 5:10 AM, Barry Warsaw wrote:
>
>> On Jan 20, 2012, at 01:50 PM, Victor Stinner wrote:
>>
>> >Counting collision doesn't solve this case, but it doesn't make the
>> >situation worse than before. Raising quickly an ex
Am 20.01.2012 19:15, schrieb Guido van Rossum:
> OTOH, if you change dictionary order and *that* breaks the application,
> then
> the bugs submitted to the application's tracker will be legitimate bugs
> that
> have to be fixed even if nothing else changed.
>
>
> There are lots of
This is the first objection I have seen against collision-counting that
might stand.
On Fri, Jan 20, 2012 at 7:55 AM, Frank Sievertsen wrote:
> Hello,
>
> I still see at least two ways to create a DOS attack even with the
> collison-counting-patch.
>
> I assumed that it's possible to send ~500KB
On Fri, Jan 20, 2012 at 5:20 AM, Barry Warsaw wrote:
> Let's just be clear about it: this exception is new public API. Changing
> dictionary order is not.
>
Not if you raise MemoryError or BaseException.
--
--Guido van Rossum (python.org/~guido)
___
On Fri, Jan 20, 2012 at 5:10 AM, Barry Warsaw wrote:
> On Jan 20, 2012, at 01:50 PM, Victor Stinner wrote:
>
> >Counting collision doesn't solve this case, but it doesn't make the
> >situation worse than before. Raising quickly an exception is better
> >than stalling for minutes, even if I agree
On Fri, Jan 20, 2012 at 1:57 AM, Frank Sievertsen wrote:
> The main issue with that approach is that it allows a new kind of attack.
>
>
> Indeed, I posted another example: http://bugs.python.org/msg151677
>
> This kind of fix can be used in a specific application or maybe in a
> special-purpose
On Thu, Jan 19, 2012 at 8:06 PM, Ivan Kozik wrote:
> No, I wasn't happy with termination. I wanted to treat it just like a
> JSON decoding error, and send the appropriate response.
>
So was this attack actually being mounted on your service regularly? I'd
think it would be sufficient to treat i
On Fri, Jan 20, 2012 at 01:48, Victor Stinner
wrote:
> - the limit should be configurable: a new function in the sys module
> should be enough. It may be private (or replaced by an environment
> variable?) in stable versions
I'd like to see both. I would like both the programmer and the "user"
t
On Fri, 20 Jan 2012 17:17:24 +0100
Victor Stinner wrote:
> > So I still think we should ditch the paranoia about dictionary order
> > changing,
> > and fix this without counting.
>
> The randomized hash has other issues:
>
> - its security is based on its secret, whereas it looks to be easy to
> So I still think we should ditch the paranoia about dictionary order changing,
> and fix this without counting.
The randomized hash has other issues:
- its security is based on its secret, whereas it looks to be easy to
compute it (see more details in the issue)
- my patch only changes hash(s
> (I'm thinking that the original
> attack is trivial once the set of 65000 colliding keys is public knowledge,
> which must be only a matter of time.)
I have a program able to generate collisions: it takes 1 second to
compute 60,000 colliding strings on a desktop computer. So the
security of the
Hello,
I still see at least two ways to create a DOS attack even with the
collison-counting-patch.
I assumed that it's possible to send ~500KB of payload to the
application.
1. It's fully deterministic which slots the dict will lookup.
Since we don't count slot-collisions, but only hash-value-c
On Fri, Jan 20, 2012 at 1:34 AM, "Martin v. Löwis" wrote:
> > The last solution is very simple: count collision and raise an
> > exception if it hits a limit. The path is something like 10 lines
> > whereas the randomized hash is more close to 500 lines, add a new
> > file, change Visual Studio pr
On Fri, 20 Jan 2012 13:50:18 +0100
Victor Stinner wrote:
> > The main issue with that approach is that it allows a new kind of attack.
> >
> > An attacker now needs to find 1000 colliding keys, and submit them
> > one-by-one into a database. The limit will not trigger, as those are
> > just datab
On Jan 20, 2012, at 03:15 PM, Nick Coghlan wrote:
>With the 1000 collision limit in place, the attacker sends their
>massive request, the affected dict quickly hits the limit, throws an
>unhandled exception which is then caught by the web framework and
>turned into a 500 Error response (or whateve
On Jan 20, 2012, at 03:18 PM, Nick Coghlan wrote:
>On Fri, Jan 20, 2012 at 2:54 PM, Carl Meyer wrote:
>> I don't have the expertise to speak otherwise to the alternatives for
>> fixing the collisions vulnerability, but I don't believe it's accurate
>> to presume that Django would not want to fix
On Jan 20, 2012, at 01:50 PM, Victor Stinner wrote:
>Counting collision doesn't solve this case, but it doesn't make the
>situation worse than before. Raising quickly an exception is better
>than stalling for minutes, even if I agree than it is not the best
>behaviour.
ISTM that adding the possib
> The main issue with that approach is that it allows a new kind of attack.
>
> An attacker now needs to find 1000 colliding keys, and submit them
> one-by-one into a database. The limit will not trigger, as those are
> just database insertions.
>
> Now, if the applications also as a need to read t
2012/1/20 Frank Sievertsen :
> No, that's not true.
> Whenever a collision happens, other bits are mixed in very fast.
Oh, I didn't know that. So the dict order is only the same if there is
no collision.
Victor
___
Python-Dev mailing list
Python-Dev@pyt
No, that's not true.
Whenever a collision happens, other bits are mixed in very fast.
Frank
Am 20.01.2012 13:08, schrieb Victor Stinner:
I'm surprised we haven't seen bug reports about it from users
of 64-bit Pythons long ago
A Python dictionary only uses the lower bits of a hash value. If you
> I'm surprised we haven't seen bug reports about it from users
> of 64-bit Pythons long ago
A Python dictionary only uses the lower bits of a hash value. If your
dictionary has less than 2**32 items, the dictionary order is exactly
the same on 32 and 64 bits system: hash32(str) & mask == hash64(s
2012/1/20 Ivan Kozik :
> I'd like to point out that an attacker is not limited to sending just
> one dict full of colliding keys. Given a 22ms stall ...
The presented attack produces a stall of at least 30 seconds (5
minutes or more if there is no time limit in the application), not
0.022 second.
On Fri, Jan 20, 2012 at 7:34 PM, "Martin v. Löwis" wrote:
> The main issue with that approach is that it allows a new kind of attack.
>
> An attacker now needs to find 1000 colliding keys, and submit them
> one-by-one into a database. The limit will not trigger, as those are
> just database insert
The main issue with that approach is that it allows a new kind of attack.
Indeed, I posted another example: http://bugs.python.org/msg151677
This kind of fix can be used in a specific application or maybe in a
special-purpose framework, but not on the level of a general-purpose
language.
Frank
> The last solution is very simple: count collision and raise an
> exception if it hits a limit. The path is something like 10 lines
> whereas the randomized hash is more close to 500 lines, add a new
> file, change Visual Studio project file, etc. First I thaught that it
> would break more applica
On 1/19/2012 8:54 PM, Carl Meyer wrote:
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Hi Victor,
On 01/19/2012 05:48 PM, Victor Stinner wrote:
[snip]
Using a randomized hash may
also break (indirectly) real applications because the application
output is also somehow "randomized". For example,
On Fri, Jan 20, 2012 at 2:54 PM, Carl Meyer wrote:
> I don't have the expertise to speak otherwise to the alternatives for
> fixing the collisions vulnerability, but I don't believe it's accurate
> to presume that Django would not want to fix a dict-ordering dependency,
> and use that as a justifi
On Fri, Jan 20, 2012 at 2:00 PM, Steven D'Aprano wrote:
> With a limit of 35 collisions, it only takes 35 keys to to force a dict to
> raise an exception, if you are an attacker able to select colliding keys.
> We're trying to defend against an attacker who is able to force collisions,
> not one w
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Hi Victor,
On 01/19/2012 05:48 PM, Victor Stinner wrote:
[snip]
> Using a randomized hash may
> also break (indirectly) real applications because the application
> output is also somehow "randomized". For example, in the Django test
> suite, the HTML
On Fri, Jan 20, 2012 at 03:48, Guido van Rossum wrote:
> I think that's because your collision-counting algorithm was much more
> primitive than MAL's.
Conceded.
>> This,
>> combined with the second problem (needing to catch an exception), led
>> me to abandon this approach and write Securetypes
Victor Stinner wrote:
The last solution is very simple: count collision and raise an
exception if it hits a limit. ...
According to my basic tests, a limit of 35 collisions
requires a dictionary with more than 10,000,000 integer keys to raise
an error. I am not talking about the attack, but vali
On Thu, Jan 19, 2012 at 7:32 PM, Ivan Kozik wrote:
> On Fri, Jan 20, 2012 at 00:48, Victor Stinner
> wrote:
> > I propose to solve the hash collision vulnerability by counting
> > collisions because it does fix the vulnerability with a minor or no
> > impact on applications or backward compatibi
On Fri, Jan 20, 2012 at 00:48, Victor Stinner
wrote:
> I propose to solve the hash collision vulnerability by counting
> collisions because it does fix the vulnerability with a minor or no
> impact on applications or backward compatibility. I don't see why we
> should use a different fix for Pytho
On Thu, Jan 19, 2012 at 4:48 PM, Victor Stinner <
victor.stin...@haypocalc.com> wrote:
> Hi,
>
> I'm working on the hash collision issue since 2 or 3 weeks. I
> evaluated all solutions and I think that I have now a good knowledge
> of the problem and how it should be solved. The major issue is to
Hi,
I'm working on the hash collision issue since 2 or 3 weeks. I
evaluated all solutions and I think that I have now a good knowledge
of the problem and how it should be solved. The major issue is to have
a minor or no impact on applications (don't break backward
compatibility). I saw three major
77 matches
Mail list logo
