On Mon, Jun 13, 2016 at 4:04 AM Matt Caswell via RT <r...@openssl.org> wrote:
> On Thu Jun 02 23:24:44 2016, paul.d...@oracle.com wrote: > > The DTLS packet reassembly code has a performance problem that could > > result in a DoS attack being possible. > > > > > > > > The DTLS packet reassembly uses the data structure defined in > > ssl/pqueue.c for the purpose (it is the only user of this data > > structure that I can find). This source file implements a priority > > queue using a singly linked list. This means O(n^2) worst case > > complexity, where n is the number of fragments. A better, and in fact > > optimal, solution would be to use a heap for the purpose giving O(n > > log n) worst case complexity. Doing this would prevent a potential > > DoS attack. > > > > > > > > The attack would consist of fragmenting the DTLS stream into as many > > small packets as possible and sending them in sequential order. Each > > fragment will require a complete traversal of the list to be added. > > Continue sending these as long as the DoS is wanted. For reference, > > changing the list search method or ordering won't prevent such an > > attack, it just means a different packet ordering is required. > > > > > > > > Tim Hudson suggested I submit this even though I haven't been able to > > find time to craft a patch. > Were you able to reproduce this performance problem? Note that N is at most 10 here. Assuming the DTLS packet reassembly code manages its queue correctly (It's rather buggy, but I forget if this was one of its problems. I eventually gave up trying to digest it and rewrote it from scratch on our end.), this check will ensure the queue size is tightly bounded: https://git.openssl.org/gitweb/?p=openssl.git;a=blob;f=ssl/statem/statem_dtls.c;h=d75483af6d40ad4c6ed9137eba8a7382a3b0ef0a;hb=HEAD#l634 It could probably be brought down a hair further too. There's no need to buffer more than the maximum number of messages in a supported handshake flight. (pqueue is still a silly data structure to be using here. A fixed-size ring buffer would be better. Or just a boring array since memmove on 10 pointers is cheap. But it's not hugely important.) David -- Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4558 Please log in as guest with password guest if prompted -- openssl-dev mailing list To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev
