No, I didn't create an exploit. If the number of packets is limited to something that small, there won't be an issue. It still seems like pqueue out to be excised from the source base and replace with something simpler.
Regards, Pauli -- Oracle Dr Paul Dale | Cryptographer | Network Security & Encryption Phone +61 7 3031 7217 Oracle Australia -----Original Message----- From: David Benjamin via RT [mailto:r...@openssl.org] Sent: Tuesday, 14 June 2016 2:16 AM To: Paul Dale <paul.d...@oracle.com> Cc: openssl-dev@openssl.org Subject: Re: [openssl-dev] [openssl.org #4558] Performance issue with DTLS packet reassembly 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 -- 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
