[issue13703] Hash collision security issue

[Alex Gaynor]

Alex Gaynor <alex.gaynor at gmail.com> added the comment:

On Thu, Jan 26, 2012 at 4:00 PM, Martin v. Löwis <report at bugs.python.org>wrote:

>
> Martin v. Löwis <martin at v.loewis.de> added the comment:
>
> I'd like to propose an entirely different approach: use AVL trees for
> colliding strings, for dictionaries containing only unicode or byte strings.
>
> A prototype for this is in
> http://hg.python.org/sandbox/loewis/branches#avl
> It is not fully working yet, but I'm now confident that this is a feasible
> approach.
>
> It has the following advantages over the alternatives:
> - performance in case of collisions is O(log(N)), where N is the number of
> colliding keys
> - no new exceptions are raised, except for MemoryError if it runs out of
> memory for allocating nodes in the tree
> - the hash values do not change
> - the dictionary order does not change as long as no keys collide on hash
> values (which for all practical purposes should mean that the dictionary
> order does not change in all places where it matters)
>
> ----------
> nosy: +loewis
>
> _______________________________________
> Python tracker <report at bugs.python.org>
> <http://bugs.python.org/issue13703>
> _______________________________________
>

Martin,

What happens if, instead of putting strings in a dictionary directly, I
have them wrapped in something.  For example, the classes Antoine and I
pasted early.  These define hash and equal as being strings, but don't have
an ordering.

Alex

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13703>
_______________________________________