[Python-Dev] "Sort attacks" (was Re: Hash collision security issue (now public))
Tim Peters
tim.peters at gmail.com
Sat Jan 7 04:05:46 CET 2012
I can't find it now, but I believe Marc-Andre mentioned that CPython's
list.sort() was vulnerable to attack too, because of its O(n log n)
worst-case behavior.
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 :-)
still-solving-problems-not-in-need-of-attention-ly y'rs - tim
More information about the Python-Dev
mailing list