Victor Stinner writes:
> Let's try to summarize this "vulnerability".
>
> The creation of a Python dictionary has a complexity of O(n) in most
> cases, but O(n^2) in the *worst* case. The attack tries to go into the
> worst case. It requires to compute a set of N keys having the same hash
Am 31.12.2011 13:03, schrieb Stephen J. Turnbull:
> I don't know the implementation issues well enough to claim it is a
> solution, but this hasn't been mentioned before AFAICS:
>
> While the dictionary probe has to start with a hash for backward
> compatibility reasons, is there a reason the over
Zitat von Victor Stinner :
The current implementation of dict uses a linked-list.
[...]
Tell me if I am wrong.
At least with this statement, you are wrong: the current
implementation does *not* use a linked-list. Instead, it
uses open addressing.
Regards,
Martin
On Sat, Dec 31, 2011 at 7:03 AM, Stephen J. Turnbull wrote:
> While the dictionary probe has to start with a hash for backward
> compatibility reasons, is there a reason the overflow strategy for
> insertion has to be buckets containing lists? How about
> double-hashing, etc?
>
This won't help,
On Wed, Dec 28, 2011 at 5:37 PM, Jesse Noller wrote:
>
>
> On Wednesday, December 28, 2011 at 8:28 PM, Michael Foord wrote:
>
>> Hello all,
>>
>> A paper (well, presentation) has been published highlighting security
>> problems with the hashing algorithm (exploiting collisions) in many
>> progra
On Sat, Dec 31, 2011 at 4:04 PM, Jeffrey Yasskin wrote:
> Hash functions are already unstable across Python versions. Making
> them unstable across interpreter processes (multiprocessing doesn't
> share dicts, right?) doesn't sound like a big additional problem.
> Users who want a distributed has
On 12/31/2011 4:43 PM, PJ Eby wrote:
Here's an idea. Suppose we add a sys.hash_seed or some such, that's
settable to an int, and defaults to whatever we're using now. Then
programs that want a fix can just set it to a random number,
I do not think we can allow that to change once there are h
ISTM the only reasonable thing is to have a random seed picked very early
in the process, to be used to change the hash() function of
str/bytes/unicode (in a way that they are still compatible with each other).
The seed should be unique per process except it should survive fork() (but
not exec()).
On Sat, Dec 31, 2011 at 4:56 PM, Guido van Rossum wrote:
> PS. I would propose a specific fix but I can't seem to build a working
> CPython from the trunk on my laptop (OS X 10.6, Xcode 4.1). I get this
> error late in the build:
>
> ./python.exe -SE -m sysconfig --generate-posix-vars
> Fatal Pyt
> I'm not too concerned about a 3rd party being able to guess the random seed
> -- this would require much more effort on their part, since they would have
> to generate a new set of colliding keys each time they think they have
> guessed the hash
This is incorrect. Once an attacker has guessed th
(Well, technically, you could use trees or some other O log n data
structure as a fallback once you have too many collisions, for some value
of "too many". Seems a bit wasteful for the purpose, though.)
I don't think that would be wasteful. You wouldn't just use the tree for
the case of too man
On Sat, 31 Dec 2011 16:56:00 -0700
Guido van Rossum wrote:
> ISTM the only reasonable thing is to have a random seed picked very early
> in the process, to be used to change the hash() function of
> str/bytes/unicode (in a way that they are still compatible with each other).
Do str and bytes stil
On Sat, Dec 31, 2011 at 9:11 PM, Antoine Pitrou wrote:
> On Sat, 31 Dec 2011 16:56:00 -0700
> Guido van Rossum wrote:
> > ISTM the only reasonable thing is to have a random seed picked very early
> > in the process, to be used to change the hash() function of
> > str/bytes/unicode (in a way that
On Sat, Dec 31, 2011 at 8:29 PM, Paul McMillan wrote:
> > I'm not too concerned about a 3rd party being able to guess the random
> seed
> > -- this would require much more effort on their part, since they would
> have
> > to generate a new set of colliding keys each time they think they have
> >
> Still, it would represent an effort for the attacker of a much greater
> magnitude than the current attack. It's all a trade-off -- at some point
> it'll just be easier for the attacker to use some other vulnerability. Also
> the class of vulnerable servers would be greatly reduced.
I agree that
15 matches
Mail list logo
