tweak find_or_replace_uid storage algorithm

Per Nelson Elhage:
find_or_insert_uid sorts 'buffer' by the uid, which is a
remotely-provided field. However, in order to expire uids, it does:

    while (num && (now - buffer[start % size].t) > CLOCK_SKEW)
	start++, num--;
    start %= size;

i.e. starts from the start of the queue and goes until it finds
something sufficiently new. Since the queue ordering is
attacker-controlled, we can send an arbitrarily-long sequence of
decreasing uids, consuming memory and forcing the client into an
ever-growing quadratic loop to insert them at the beginning.
--
Solve this by not keeping the buffer sorted; just tack the incoming
uids on the end.    This way an attacker can make us keep five minutes
worth of UIDs, but only five minutes, and also anecdotally a client
under attack spends all of its CPU sort uids.

0 files changed, 0 insertions, 0 deletions