<blockquote>
  <p>Do you know of other resource consumption vulnerabilities that were caused by flawed algorithms?</p>
</blockquote>

<p>this can be a subtle issue because basically any algorithm that processes requests with responses is subject to a <a href="http://en.wikipedia.org/wiki/Denial_of_service" rel="nofollow">Denial of Service</a> attack vulnerability due to being overwhelmed with requests, such that even efficient algorithms can be overwhelmed. in a sense the algorithms are not considered "flawed" until an attacker exploits them, during an ongoing, adaptive race between hackers and researchers employing countermeasures. </p>

<p>one famous example from history is the so-called <a href="http://en.wikipedia.org/wiki/Ping_of_death" rel="nofollow">Ping of Death</a> which led to large attacks in 2000 against Yahoo, CNN, eBay, Dell, &amp; Amazon by the hacker "mafiaboy". ref [1] lists the 10 most famous attacks of the past 25 years several of which are DoS attacks. however, some other algorithms are not discovered to be inefficient until hackers find methods/attack vectors for "bogging them down" and the Apache vulnerability you mention apparently fits into that category. </p>

<p>there are large amounts of research into DoS prevention techniques eg refs below.</p>

<p>[1] <a href="http://www.thedailybeast.com/articles/2010/12/11/hackers-10-most-famous-attacks-worms-and-ddos-takedowns.html" rel="nofollow">Hackers’ Most Destructive Attacks</a>, DailyBeast</p>

<p>[2] <a href="http://nms.lcs.mit.edu/HotNets-II/papers/netcap.pdf" rel="nofollow">Preventing Internet Denial-of-Service with Capabilities</a> Anderson, Roscoe, Wetherall</p>

<p>[3] <a href="http://www.csl.mtu.edu/cs6461/www/Reading/Razmov00.pdf" rel="nofollow">Denial of service attacks and how to defend against them</a> Razmov</p>

<p>[4] <a href="http://people.cs.pitt.edu/~mehmud/docs/abliz11-TR-11-178.pdf" rel="nofollow">Internet denial of service attacks and defense mechanisms</a> Abliz</p>

CC BY-SA 3.0
2012-12-22T00:00:09.133Z
2012-12-22T00:00:09.133Z
vzn
<p>I am studying algorithm construction and weaknesses to resource consumption.  One vulnerability that really caught my eye was the <a href="http://httpd.apache.org/security/CVE-2011-3192.txt" rel="nofollow">Apache Range Header DoS Vulnerability</a>.  The following quote was taken from Apache developers <a href="http://www.gossamer-threads.com/lists/engine?do=post_view_flat;post=401638;page=1;sb=post_latest_reply;so=ASC;mh=25;list=apache" rel="nofollow">discussing the flaw</a>:</p>

<blockquote>
  <p>From looking at the code, I think the problem is the bucket structs.<br>
  With N the number of requested ranges, the initial brigade is<br>
  partitioned into 2*N buckets at the maximum. Then those buckets are<br>
  copied into the output brigade N times, which means that O(N^2)<br>
  buckets are created. The data is not copied, and only N "A-B" strings<br>
  are allocated from the pool.</p>
</blockquote>

<p>Does anyone else know of other resources about building algorithms that are resistant to resource exhaustion attacks?   Does anyone of interesting papers related to Algorithmic analysis and susceptibility to resource exhaustion?  Do you know of other resource consumption vulnerabilities that where caused by flawed algorithms?</p>

CC BY-SA 3.0
2012-12-18T15:47:38.967Z
I recently heard a nice talk about work on password protection (salt/pepper stuff) that proposed adding "garlic" to enforce a certain level of non-parallelism for the attacker. The security argument was via a pebbling game that showed that processor parallelism required high memory (which defeats, e.g., highly parallel GPU attacks on password databases). **The point being:** the intuitive (though informal) contrapositive would be "Highly parallel algorithms are more resistant to resource consumption attacks." It's unclear how generally this can be applied, but it's a starting thought. =)
Daniel Apon
CC BY-SA 3.0
2012-12-18T17:07:14.063Z
@Daniel Apon  that is a good point.
The Rook
<ds.algorithms><cr.crypto-security><security><availability>
Algorithmic Complexity Attacks
The Rook
# Algorithmic Complexity Attacks

(Asked by: username_0 on 2012-12-18)

I am studying algorithm construction and weaknesses to resource consumption. One vulnerability that really caught my eye was the [Apache Range Header DoS Vulnerability](http://httpd.apache.org/security/CVE-2011-3192.txt). The following quote was taken from Apache developers [discussing the flaw](http://www.gossamer-threads.com/lists/engine?do=post_view_flat;post=401638;page=1;sb=post_latest_reply;so=ASC;mh=25;list=apache):

> From looking at the code, I think the problem is the bucket structs.  
> With N the number of requested ranges, the initial brigade is  
> partitioned into 2\*N buckets at the maximum. Then those buckets are  
> copied into the output brigade N times, which means that O(N^2)  
> buckets are created. The data is not copied, and only N "A-B" strings  
> are allocated from the pool.

Does anyone else know of other resources about building algorithms that are resistant to resource exhaustion attacks? Does anyone of interesting papers related to Algorithmic analysis and susceptibility to resource exhaustion? Do you know of other resource consumption vulnerabilities that where caused by flawed algorithms?

**Tags:** ds.algorithms, cr.crypto-security, security, availability

> **Comments:**
> **username_1**: I recently heard a nice talk about work on password protection (salt/pepper stuff) that proposed adding "garlic" to enforce a certain level of non-parallelism for the attacker. The security argument was via a pebbling game that showed that processor parallelism required high memory (which defeats, e.g., highly parallel GPU attacks on password databases). **The point being:** the intuitive (though informal) contrapositive would be "Highly parallel algorithms are more resistant to resource consumption attacks." It's unclear how generally this can be applied, but it's a starting thought. =)  
> **username_0**: @username_1  that is a good point.  

---

## 1 answers

### Answer by username_2 on 2012-12-22. Score: 1

> Do you know of other resource consumption vulnerabilities that were caused by flawed algorithms?

this can be a subtle issue because basically any algorithm that processes requests with responses is subject to a [Denial of Service](http://en.wikipedia.org/wiki/Denial_of_service) attack vulnerability due to being overwhelmed with requests, such that even efficient algorithms can be overwhelmed. in a sense the algorithms are not considered "flawed" until an attacker exploits them, during an ongoing, adaptive race between hackers and researchers employing countermeasures.

one famous example from history is the so-called [Ping of Death](http://en.wikipedia.org/wiki/Ping_of_death) which led to large attacks in 2000 against Yahoo, CNN, eBay, Dell, & Amazon by the hacker "mafiaboy". ref [1] lists the 10 most famous attacks of the past 25 years several of which are DoS attacks. however, some other algorithms are not discovered to be inefficient until hackers find methods/attack vectors for "bogging them down" and the Apache vulnerability you mention apparently fits into that category.

there are large amounts of research into DoS prevention techniques eg refs below.

[1] [Hackers’ Most Destructive Attacks](http://www.thedailybeast.com/articles/2010/12/11/hackers-10-most-famous-attacks-worms-and-ddos-takedowns.html), DailyBeast

[2] [Preventing Internet Denial-of-Service with Capabilities](http://nms.lcs.mit.edu/HotNets-II/papers/netcap.pdf) Anderson, Roscoe, Wetherall

[3] [Denial of service attacks and how to defend against them](http://www.csl.mtu.edu/cs6461/www/Reading/Razmov00.pdf) Razmov

[4] [Internet denial of service attacks and defense mechanisms](http://people.cs.pitt.edu/~mehmud/docs/abliz11-TR-11-178.pdf) Abliz


---

