[issue13703] Hash collision security issue

[Antoine Pitrou]

Antoine Pitrou <pitrou at free.fr> added the comment:

> >  There were three discussed issues with it:
> >
> > a) Code assuming a stable ordering to dictionaries
> > b) Code assuming hashes were stable across runs.
> > c) Code reimplementing the hashing algorithm of a core datatype that is now
> > randomized.
> >
> > I don't think any of these are realistic issues
> 
> I'm fairly certain that code will break in massive ways, despite any
> argumentation that it should not. The question really is
> 
> Do we break code in a massive way, or do we fix the vulnerability
> for most users with no code breakage?
> 
> I clearly value compatibility much higher than 100% protection against
> a DoS-style attack (which has many other forms of protecting against
> available also).

If I your read patch correctly, collisions will produce additional
allocations of one distinct PyObject (i.e. AVL node) per colliding key.
That's a pretty massive change in memory consumption for string dicts
(and also in memory fragmentation and cache friendliness, probably). The
performance effect in most situations is likely to be negative too,
despite the better worst-case complexity.

IMO that would be a rather controversial change for a feature release,
let alone a bugfix or security release.

It would be nice to have the release managers' opinions on this issue.

----------

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