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

From: broyds@rogers.com
Date: 10/18/02


From: <broyds@rogers.com>
To: Miles Sabin <miles@milessabin.com>, <firewall-wizards@honor.icsalabs.com>
Date: Fri Oct 18 13:47:01 2002

Most hash functions are based on arithmetic modulo a large prime. Most often this prime is chosen to be close to a power of 2 to optimize address space (often a Mersenne prime), but there is not neccessity for it so the secret would be the prime used as hash base. Guessing prime used is non trivial so it provides some security.

>
> From: Miles Sabin <miles@milessabin.com>
> Date: 2002/10/18 Fri AM 02:45:26 EDT
> To: firewall-wizards@honor.icsalabs.com
> Subject: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd)
>
> 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
> _______________________________________________
> firewall-wizards mailing list
> firewall-wizards@honor.icsalabs.com
> http://honor.icsalabs.com/mailman/listinfo/firewall-wizards
>



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: Hashing of short fixed length messages
    ... You actually have 55 bytes of useful payload before MD5 requires a 2nd ... to present a traditional hash interface since the ... The input itself is a hash too, so I can ignore related key attack, ... to a speed-up factor of two, but I don't think it's secure. ...
    (sci.crypt)