[issue13703] Hash collision security issue

[Dave Malcolm]

Dave Malcolm <dmalcolm at redhat.com> added the comment:

On Sat, 2012-01-21 at 22:20 +0000, Antoine Pitrou wrote:

> Sounds a bit overkill, and it shouldn't be a public API (which
> __methods__ are). Even a private API on dicts would quickly become
> visible, since dicts are so pervasive.

Fair enough.

> > > > Caveats:
> > > > * no overflow handling (what happens after 2**32 modifications to a
> > > > long-lived dict on a 32-bit build?) - though that's fixable.
> > > 
> > > How do you suggest to fix it?
> > 
> > If the dict is heading towards overflow of these counters, it's either
> > long-lived, or *huge*.
> > 
> > Possible approaches:
> > (a) use 64-bit counters rather than 32-bit, though that's simply
> > delaying the inevitable
> 
> Well, even assuming one billion lookup probes per second on a single
> dictionary, the inevitable will happen in 584 years with a 64-bit
> counter (but only 4 seconds with a 32-bit counter).
> 
> A real issue, though, may be the cost of 64-bit arithmetic on 32-bit
> CPUs.
> 
> > (b) when one of the counters gets large, divide both of them by a
> > constant (e.g. 2).  We're interested in their ratio, so dividing both by
> > a constant preserves this.
> 
> Sounds good, although we may want to pull this outside of the critical
> loop.

OK; I'll look at implementing (b).

Oops, yeah, that was a typo; I meant 0 to disable.

> - 0 to disable it
> - 1 to enable it and use the default scaling factor
> - >= 2 to enable it and set the scaling factor

You said above that it should be hardcoded; if so, how can it be changed
at run-time from an environment variable?  Or am I misunderstanding.

Works for me.

> > BTW, presumably if we do it, we should do it for sets as well?
> 
> Yeah, and use the same env var / sys function.

Despite the "DICT" in the title?  OK.

Thanks for the feedback.

----------

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