Author tim.peters
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, georg.brandl, gvanrossum, haypo, jcea, lemburg, merwok, pitrou, skrah, terry.reedy, tim.peters, v+python
Date 2012-01-07.23:24:48
SpamBayes Score 1.38541e-05
Marked as misclassified No
Message-id <1325978689.22.0.415333730698.issue13703@psf.upfronthosting.co.za>
In-reply-to
Content
[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 :-)
History
Date User Action Args
2012-01-07 23:24:49tim.peterssetrecipients: + tim.peters, lemburg, gvanrossum, barry, georg.brandl, terry.reedy, jcea, pitrou, haypo, christian.heimes, benjamin.peterson, merwok, Arfrever, v+python, alex, skrah, dmalcolm, Arach, Mark.Shannon, Zhiping.Deng, Huzaifa.Sidhpurwala, PaulMcMillan
2012-01-07 23:24:49tim.peterssetmessageid: <1325978689.22.0.415333730698.issue13703@psf.upfronthosting.co.za>
2012-01-07 23:24:48tim.peterslinkissue13703 messages
2012-01-07 23:24:48tim.peterscreate