Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)

From: Miles Sabin (miles@milessabin.com)
Date: 10/18/02


From: Miles Sabin <miles@milessabin.com>
To: firewall-wizards@honor.icsalabs.com
Date: Fri Oct 18 11:10:01 2002

Mike Frantzen wrote,
> The problem with a hashed state table is that hash tables are very
> easy to attack. The use of collision chains (linked lists) would let
> an attack totally blow out the D$ and TLB. I've make a sun U10
> 440mhz w/ 2MB L2 grind to a halt w/ 5 packets a second after a long
> series of collisions.

Interesting ... the idea being that with knowledge of the hash function
an attacker could manufacture enough collisions to push the hash table
to the O(n) worst case?

Couldn't that attack be frustrated by a more sophisticated hash function
parameterized with a local secret (ie. the attacker would need to know
the secret as well as the function before they could reliably generate
collisions)? Or would that make the hash function too computationally
expensive?

Cheers,

Miles



Relevant Pages

  • Re: Re-secured Algorithm?
    ... i remember a time when the ability to find collisions with less ... >>work than a brute force search meant that the hash algorithm was broken... ... 6,000 machines would take 3 weeks to attack md5 with a complexity just ... > To get the desired results for just ONE SINGLE successful attack, ...
    (sci.crypt)
  • Re: Function Points
    ... scenario is one where the attacker knows the hash function and ... deliberately creates collisions. ... pre-computed dictionary attacks involving hash collisions. ... the use of XOR-ing is kept secret, is indeterminable, and the attacker ...
    (comp.lang.forth)
  • Re: Generate unique ID for URL
    ... depending on the needs. ... and there is always the possibility of collisions. ... A hash is the wrong answer to the issue as a hash is open to all sorts ... of attack vectors like length extension attack. ...
    (comp.lang.python)
  • Re: When will md5crk complete?
    ... >>existing certificates, and in that case birthday attack doesn't apply (it ... I have to conceed that JLC's attack is of little consequence ... > Once collisions are known to exist you're on tricky ground. ... > against the SSL certificate if you have a hash function for which a fair ...
    (sci.crypt)
  • Re: Simple Algorithm (Perfect Hashing?)
    ... a hash algorithm does something similar but in a one-way fashion and ... Collisions are naturally not permitted! ... In fixed hash tables you use a table whose length is a prime number. ... the hash function looks like ...
    (comp.programming)