Re: Algorimic Complexity Attacks

From: Götz Babin-Ebell (babin-ebell_at_trustcenter.de)
Date: 06/24/03

  • Next message: Eric Lawrence: "RE: [Symantec Security Advisor] Symantec Security Check ActiveX Buffer Overflow" 
    Date: Tue, 24 Jun 2003 20:45:56 +0200
To: Nicholas Weaver <nweaver@CS.berkeley.edu>

    Hello Nicolas

    Nicholas Weaver wrote:
    > On Sun, Jun 08, 2003 at 06:17:38PM +0200, Pavel Kankovsky composed:
    >
    >>We need a function having a (relatively) small set of results in order to
    >>build a hash table. We can also assume the information about collisions
    >>leaks out via a timing channel. Ergo, a persistent attacker can find
    >>enough collisions by trial and error.
    >
    > IF the hash is good, FINDING collisions doesn't necessarily help the
    > attacker, as the attacker really needs to generate lots of collisions
    > to make the searches O(n) instead of O(1), since that is teh key
    > behind this attack.

    You could do some improvement if you store the collisions
    not in a list, but in a new hash table.

    In that 2nd hash table you add a salt.

    So the attacker must find many sets of data that result not only
    in a collistion, but additional result in collisions in the
    2nd hash table.

    If the salt is some on the spot generated random data,
    that should be nearly impossible...

    Generating the 2nd hash table only if there at least n collissions
    should keep the load on the system low...

    Bye

    Goetz 

    -- 
Goetz Babin-Ebell, TC TrustCenter AG, http://www.trustcenter.de
Sonninstr. 24-28, 20097 Hamburg, Germany
Tel.: +49-(0)40 80 80 26 -0,  Fax: +49-(0)40 80 80 26 -126

  • Next message: Eric Lawrence: "RE: [Symantec Security Advisor] Symantec Security Check ActiveX Buffer Overflow"

    Relevant Pages

    • Re: Algorimic Complexity Attacks
      ... let us observe the attacker needs no less than Oinserts (where ... > h is the size of the hash table) to find a collision of an unknown hash ... > a universal hash function using a secret parameter) is changed every ... In that case, for a smaller table size, collisions WILL occur, but as ...
      (Bugtraq)
    • Re: When will md5crk complete?
      ... and in that case birthday attack ... > His core message is correct however: you shouldn't be using MD5. ... Collisions DO exist for every hash algorithm... ...
      (sci.crypt)
    • Re: Hashing
      ... Computing the hash function, which is handled by the instructions: ... reserved word/identifier when searching through the reserved words ... collisions and four slots that have four collisions. ...
      (alt.lang.asm)
    • Re: Hashing
      ... A good hash ... > greater is it better performance due to less collisions". ... then the probability that you need a rehash on any scan is something ... > 'hash method' simply because they use hash codes, ...
      (alt.lang.asm)
    • Re: CHECKSUM() question
      ... Let's assume for a moment that you use CHECKSUM and that there are hash collisions. ... If you stage the answer in a temporary table, you can use that to join to your source table, then filter out the few collisions. ... Remember absolutely no hash that reduces the size of data for searching can be guaranteed to avoid a collision. ... However, from a private discussion, Steve Kass pointed out that HASHBYTES with MD5 for 300 million rows probably has a lower chance of collision than the the possibility that some bit will get randomly changed by some other influence. ...
      (microsoft.public.sqlserver.programming)