[issue13703] Hash collision security issue

Marc-Andre Lemburg report at bugs.python.org
Sun Jan 8 12:33:28 CET 2012

Marc-Andre Lemburg <mal at egenix.com> added the comment:

Tim Peters wrote:
> Tim Peters <tim.peters at gmail.com> added the comment:
> [Marc-Andre]
>> BTW: I wonder how long it's going to take before
>> someone figures out that our merge sort based
>> list.sort() is vulnerable as well... its worst-
>> case performance is O(n log n), making attacks
>> somewhat harder.
> I wouldn't worry about that, because nobody could stir up anguish
> about it by writing a paper ;-)
> 1. O(n log n) is enormously more forgiving than O(n**2).
> 2. An attacker need not be clever at all:  O(n log n) is not only
> sort()'s worst case, it's also its _expected_ case when fed randomly
> ordered data.
> 3. It's provable that no comparison-based sorting algorithm can have
> better worst-case asymptotic behavior when fed randomly ordered data.
> So if anyone whines about this, tell 'em to go do something useful instead :-)

Right on all accounts :-)


Python tracker <report at bugs.python.org>

More information about the Python-bugs-list mailing list