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

Mon Jun 13 22:10:05 UTC 2016

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:rt at openssl.org] 
Sent: Tuesday, 14 June 2016 2:16 AM
To: Paul Dale <paul.dale at oracle.com>
Cc: openssl-dev at 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 <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

-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4558
Please log in as guest with password guest if prompted