[openssl-dev] [openssl.org #4558] Performance issue with DTLS packet reassembly

[David Benjamin via RT]

On Mon, Jun 13, 2016 at 4:04 AM Matt Caswell via RT <rt at openssl.org> wrote:

> On Thu Jun 02 23:24:44 2016, paul.dale at 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