Algorithmic compexity attacks [LWN.net]

Scott Crosby and Dan Wallach have announced a paper describing a new class of security problem that they call "algorithmic complexity attacks." The basic idea is simple: predictable behavior in certain application algorithms can be exploited by attackers to create denial of service problems; these attacks can be easy to mount and require very low amounts of bandwidth. The full paper describes this sort of attack in detail, with a strong emphasis on hash tables. The authors promote a particular class of hashing algorithm ("universal hash") as a way of fixing the problem.

The networking hash vulnerability described here two weeks ago clearly falls into this category of problem. (This vulnerability, incidentally, is still unfixed by any distributors beyond Red Hat and EnGarde). Mr. Crosby has also found a similar problem in the Linux kernel directory entry cache code; an attacker who has control over file names can force behavior which slows the system to a crawl.

The interesting thing is that, once one starts looking, this sort of vulnerability is widespread. For example:

Languages like Perl and Python provide hashed data structures (associative arrays and dictionaries). If an application uses user input as a key for such a structure, that application can be vulnerable to attack. The paper demonstrates the degree to which Perl arrays can degrade with carefully chosen input.
Regular expressions are widely used in applications. Anybody who has programmed with non-trivial regular expressions knows that they can be hard to get right in the first place. But writing regular expressions which do not bring the application down in flames when confronted with the wrong input is even harder.

Chances are many applications suffer from this sort of vulnerability. It may soon be that distributed denial of service attacks pass out of favor; if an algorithmic complexity attack is available, there is no real point in going to the effort of assembling the attack network.

Sadly, it may well turn out that free software applications are uniquely vulnerable to algorithmic complexity attacks - at least, in the short term. Mounting such an attack requires a reasonably well advanced understanding of which algorithms an application is using, and how it is using them. Closed-source applications will certainly have (at least) as many algorithmic complexity vulnerabilities as free applications, but the lack of source will make those vulnerabilities hard to exploit. In the longer term, of course, the situation may reverse itself; the vulnerabilities in free programs will have been found and fixed, while those in proprietary code lurk on, waiting for an exploit to be developed.

(Log in to post comments)

Undergrads?

Posted Jun 5, 2003 7:02 UTC (Thu) by rfunk (subscriber, #4054) [Link]

Anyone else think this seems a bit amateurish?

I notice lots of spelling errors in the announcement, an apparent reluctance to
delve into Squid's "private/public keys" attributes that seem to affect its
vulnerability, a reluctance to admit that they're not the first to discover this
issue, and a patronizing attitude toward software authors, as well as other
problems.

This is an important issue to be aware of, and it's good that these guys are
making software authors aware of what the computer scientists already knew,
but I wish they could either be more professional about it or get rid of the
professional/academic facade completely.

Algorithmic compexity attacks

Posted Jun 5, 2003 10:12 UTC (Thu) by shane (subscriber, #3335) [Link]

"In the longer term, of course, the situation may reverse itself; the vulnerabilities in free programs will have been found and fixed, while those in proprietary code lurk on, waiting for an exploit to be developed."

This is certainly true. Claims of those who favor software patents notwithstanding, a skilled software developer can make a pretty good guess what algorithms are used for what purposes in an application - in the same way that one can guess where buffer overflows are likely to be a problem in programs. While having the source available makes it easier, it is not required.

Algorithmic compexity attacks

Posted Jun 5, 2003 11:00 UTC (Thu) by NRArnot (subscriber, #3033) [Link]

Surely an answer (if not the answer) is to make the hashes depend on an entropic random number generated within the subsystem at incarnation, and using an algorithm such that without the privilege to extract that number from the guts of the system in question, a vandal won't be able to work out the input data stream that breaks the system.

As an example (simplistic) if the hash were the XOR of the bytes of a string, a vandal could generate a list of inputs which yield the same hash. If the hash were of the concatenation of the string with a random byte, he'd have to try all 256 possibilities for that byte. If the hash were more sophisticated and the random number 64 bits (MD5 as an extreme) he'd not be able to try all possibilities, and knowing the algorithm (MD5) without knowing the 64 random bits would not help.

The problem then becomes one of keeping a secret secret from the attackers.