Algorithmic complexity attacks and libc qsort()
calmerthanyouare.org
Algorithmic complexity attacks and libc qsort()
1–10 of 55 posts
Re: Algorithmic complexity attacks and libc qsort()
#2Was anyone able to view the linked research paper on Hash Table exploits?
Re: Algorithmic complexity attacks and libc qsort()
#3Was anyone able to view the linked research paper on Hash Table exploits?
[deleted]
Re: Algorithmic complexity attacks and libc qsort()
#4Was anyone able to view the linked research paper on Hash Table exploits?
You gotta dig a bit. But here:
https://www.usenix.org/legacy/publications/library/proceedin...
Re: Algorithmic complexity attacks and libc qsort()
#5Was anyone able to view the linked research paper on Hash Table exploits?
[deleted]
Re: Algorithmic complexity attacks and libc qsort()
#6Quite nifty. Imagine how you could seed a service with data over a very long period of time knowing and then at the wrong moment you make a single request causing the server to fall over.
This sort of thing might even work where the target comes to you for data (such as a search engine crawling you).
Re: Algorithmic complexity attacks and libc qsort()
#7Re: Algorithmic complexity attacks and libc qsort()
#8I'm surprised the article does not point out more directly that it's usually pretty simple to mitigate this attack vector by switching to mergesort. The worst case is O(n log n) so there's no real "killer input".
I think it's a good rule of thumb to say "if you need to sort large quantities of untrusted data you should probably use mergesort".
Re: Algorithmic complexity attacks and libc qsort()
#9As someone who implemented an open source quicksort (http://www.mqseries.net/phpBB2/viewtopic.php?p=273722) which is used by many in production:
Now this is very interesting, but could also be prevented with a random number generator (which influences the selection of the pivot element). If this would have been exploited, people would have looked into mitigating this.
Edit: You can detect recursion-tree-degeneration (just check the depth) and react to it (pivot selection)
Re: Algorithmic complexity attacks and libc qsort()
#10I'm surprised the article does not point out more directly that it's usually pretty simple to mitigate this attack vector by switching to mergesort. The worst case is O(n log n) so there's no real "killer input". I think it's a good rule of thumb to say "if you need to sort large quantities of untrusted data you should probably use mergesort".
I've always liked mergesort for this reason. It's easier to understand and there's no wondering about complexity.