[Dailydave] Algorithmic Bugs

[Randy Smith]

Linearizing hash tables is a trick that has been known about for a 
while.  I do believe it could be considered the "classic attack", as you 
suggest.

Of course, in our paper we showed the same kinds of effects (denial of 
service) using entirely different techniques (excessive backtracking). 
We also proposed and implemented a solution that fairly effectively 
neutralizes the attack.

--Randy

Thomas Ptacek wrote:
> Tim Newsham worked on this in 1997-1998 (and in that respect the paper
> gets its cites a bit wrong; I'm pretty sure there are published hash
> table results prior to 2003). My sense is that the "classic" attack
> here is "turn chaining hash tables into linked lists with a collision
> extension function".
> 
> On 1/10/07, Dave Aitel <dave at immunityinc.com> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Best paper at a conference I went to recently here in Miami Beach.
>>
>>
>> http://www.cs.wisc.edu/~smithr/pubs/acsac2006.pdf
>>
>> Summery:
>> You can send a remarkably small stream of data at a NIDS and cause it
>> to go to 100% CPU and stop doing analysis if you send the RIGHT stream
>> of data. This is basically undetectable (i.e. does not crash snort).
>> Was fixed in Snort 2.6.1 (I believe). Some snort rules have a 1
>> million to 1 expansion if you do it right (from what I read - I
>> haven't tested this out yet - but it would make a great CANVAS module!)
>>
>> The presentation is clearer than the paper. I hope they put it online.
>>
>> Similar bugs exist in major commercial Python exploitation frameworks
>> (i.e. you can tartrap CANVAS if you do it right). The more high level
>> the language, the easier it is to get caught by something like this.
>>
>> - -dave
>> -----BEGIN PGP SIGNATURE-----
>> Version: GnuPG v1.4.6 (GNU/Linux)
>>
>> iD8DBQFFpSRFB8JNm+PA+iURAg/UAKDa+8OfY4AKO5lZnpvmoO9QqnQ5BQCghwWK
>> VCbaxHVE4JImfXyaKqyVsN4=
>> =6bSm
>> -----END PGP SIGNATURE-----
>>
>> _______________________________________________
>> Dailydave mailing list
>> Dailydave at lists.immunitysec.com
>> http://lists.immunitysec.com/mailman/listinfo/dailydave
>>
> _______________________________________________
> Dailydave mailing list
> Dailydave at lists.immunitysec.com
> http://lists.immunitysec.com/mailman/listinfo/dailydave