<html>
  <head>
    <meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#330033">
    On 1/23/2012 12:53 AM, Frank Sievertsen wrote:
    <blockquote cite="mid:4F1D1FF2.4030701@sievertsen.de" type="cite"><br>
      What if we use a second (randomized) hash-function in case there
      <br>
      are many collisions in ONE lookup. This hash-function is used only
      <br>
      for collision resolution and is not cached.
    </blockquote>
    <br>
    So this sounds like SafeDict, but putting it under the covers and
    automatically converting from dict to SafeDict after a collision
    threshold has been reached.  Let's call it fallback-dict.<br>
    <br>
    Compared to SafeDict as a programmer tool, fallback-dict has these
    benefits:<br>
    <br>
    * No need to change program (or library) source to respond to an
    attack<br>
    * Order is preserved until the collision threshold has been reached<br>
    * Performance is preserved until the collision threshold has been
    reached<br>
    <br>
    and costs:<br>
    <br>
    * converting the dict from one hash to the other by rehashing all
    the keys.<br>
    <br>
    Compared to always randomizing the hash, fallback-dict has these
    benefits:<br>
    <br>
    * hash (and perfomance) is deterministic: programs running on the
    same data set will have the same performance characteristic, unless
    the collision threshold is reached for that data set.<br>
    * lower probability to leak secrets, because each attacked set/dict
    can have its own secret, randomized hash seed<br>
    * patch would not need to include RNG initialization during startup,
    lowering the impact on short-running programs.<br>
    <br>
    What is not clear is how much SafeDict degrades performance when it
    is used; non-cached hashes will definitely have an impact.  I'm not
    sure whether an implementation of fallback-dict in C code, would be
    significantly faster than the implementation of SafeDict in Python,
    to know whether comparing the performance of SafeDict and dict would
    be representative of the two stages of fallback-dict performance,
    but certainly the performance cost of SafeDict would be an upper
    bound on the performance cost of fallback-dict, once conversion
    takes place, but would not measure the conversion cost.  The
    performance of fallback-dict does have to be significantly better
    than the performance of dict with collisions to be beneficial, but
    if the conversion cost is significant, triggering conversions could
    be an attack vector.<br>
  </body>
</html>