<div class="gmail_quote">On 23 January 2012 16:49, Lennart Regebro <span dir="ltr"><<a href="mailto:regebro@gmail.com">regebro@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Mon, Jan 23, 2012 at 06:02, Paul McMillan <<a href="mailto:paul@mcmillan.ws">paul@mcmillan.ws</a>> wrote:<br>
>> We may use a different salt per dictionary.<br>
><br>
> If we're willing to re-hash everything on a per-dictionary basis. That<br>
> doesn't seem reasonable given our existing usage.<br>
<br>
</div>Well, if we get crazy amounts of collisions, re-hashing with a new<br>
salt to get rid of those collisions seems quite reasonable to me...</blockquote><div><br></div><div>Actually, this looks like it has the seed of a solution in it. I haven't scrutinised the following beyond "it sounds like it could work" - it could well contain nasty flaws.</div>
<div><br></div><div>Assumption: We only get an excessive number of collisions during an attack (directly or indirectly).</div><div>Assumption: Introducing a salt into hashes will change those hashes sufficiently to mitigate the attack (all discussion of randomising hashes makes this assumption).</div>
<div><br></div><div>1. Keep the current hashing (for all dictionaries) i.e. just using hash(key).</div><div><br></div><div>2. Count collisions.</div><div><br></div><div>3. If any key hits X collisions change that dictionary to use a random salt for hashes (at least for str and unicode keys). This salt would be remembered for the dictionary.</div>
<div><br></div><div>Consequence: The dictionary would need to be rebuilt when an attack was detected.</div><div>Consequence: Hash caching would no longer occur for this dictionary, making most operations more expensive.</div>
<div>Consequence: Anything relying on the iteration order of a dictionary which has suffered excessive conflicts would fail.</div><div><br></div><div>4. (Optional) in 3.3, provide a way to get a dictionary with random salt (i.e. not wait for attack).</div>
<div><br></div><div>Tim Delaney</div></div>