Archive for March, 2007 Page 2 of 3

« Older Entries
Newer Entries »
Mar 15

Algorithmic Complexity Attacks

in In Publications, Security and Software. 0 Comments Printable version Printable version

Algorithmic complexity attack is a “new” class of DOS (denial  of service) attack. It is new in a sense that it has been unleash around 2003 whereas Deny that use flood and killer packets are around for more than a decade. This type of attack also deserve attention as it can be performed with very low bandwith and target underlying algorithm.

The key idea is to deny a software by exploiting algorithmic deficiencies found in many widespread algorithm. Frequently used data structures have “average-case” expected running time that’s far more efficient than the worst case. Hence the goal of the attack is to craft specific input data that will force the algorithm to operate at it worst case rather than in average case. In result with very low bandwith it is possible to disable NIDS or proxy.

The paper called Denial of Service via Algorithmic Complexity Attacks by Scott A Crosby and Dan S Wallach published at USENIX Security 2003 (Presentation slide) list many  algorithms suceptible to be vulnerable due to the difference between their average and worst case:

  • Hash tables – O(1) vs. O(n)
  • Binary trees – O(log n) vs. O(n)
  • Quicksort – O(n log n) vs. O(n2)
  • Regexp matchers – O(n) vs. O(2n)

This paper also list many application that was vulnerable at the time of writting including

  • Bro IDS
  • Squid Proxy
  • DjbDNS

Since this date new paper that focus on this type of attack are regulary publish. I still found that the USENIX paper remains the reference.

However I came accross a paper that I also recommand you to read if your are interesseted in this subject. This paper called Backtracking Algorithmic Complexity Attacks Against a NIDS was publish at ASAC 2006 by Randy Smith Cristian Estan Somesh Jha. I found it interessting because it has a clear related work and the attack description against Snort is very well presented. I also like the fact that the attack is effective against a widespread product and can be performs with only 4kbit/s of bandwith.

Denial of Service via Algorithmic Complexity Attack Local copy

Backtracking Algorithmic Complexity Attacks Against a NIDS Local copy

Mar 13

Bandwidth and Latency impact

in Analysis and production, In Internet, Internet and Quick Note. 0 Comments Printable version Printable version

Many DSL advertising focus on the bandwidht you can have to “make the web faster” . If for large file it is true that bandwith matter an under estimate criteria is the latency (also known as Lag). For interactive service such as VOIP (Skype, Msn…) and online game, It is the criteria to look for.

If you have try to play CounterStrike or make a e-call with a high latency you know what I mean. For the other there is a
perceivable delay between your action and the result. Getting more bandwith is easy, if you really needed it you can get an other line and loadbalance. For the latency there nothing you can do. That is probably why there is no advertising on it.

A really good article about it is It’s the Latency, Stupid. by S. Cheshire a Apple protocol expert. Even if the article get back to 2001 it still remains accurate.

In particular the idea that modem perform poorly is still so true. Latency is may be the key argument to deploy optic fiber as it will allow to reduce the latency drasticly. We can hope to have a latency around twice the speed of light in fiber which is 200 x 10^6 m/s. This will allow a new range of application that need reactivity such as controling remotely a car or improving Internet Call.

That is why the French operator Free intiative to deploy optic fiber, is a good idea to improve quality of service.

« Older Entries
Newer Entries »