[Omake] Lm_hash

[Jason Hickey]

Aleksey,

In libmojave rev 10253, you wrote:

> ---------------------------------------------------------------------- 
> --
> r10253 | nogin | 2007-03-20 12:40:53 -0700 (Tue, 20 Mar 2007) | 8  
> lines
>
> With the current hash_data approach, even a simple
>
> let new_digest = old_digest lxor (Array.unsafe_get hash_data code)
>
> is good enough; there is no need for
>
> let new_digest = (old_digest lsl 3) lxor (old_digest lsr 1) lxor  
> (Array.unsafe_get hash_data code)

I've always been a bit troubled by this, but let me give an  
argument.  Suppose I am an adversary and I want to produce hash  
collisions.

1. You hash some string "abc"
2. I figure out some characters "xyz" that brings the hash_code back  
to zero
3. I hash the string "xyzabcxyz"

The resulting hash is always zero.  Here is a real example that  
hashes to zero.

       let state = HashCode.create () in
       HashCode.add_string state  
"abczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz 
\027abczzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz\027";
       assert (HashCode.code state = 0)

I can't say that the old style is provably better, but it seems to me  
that using a commutative operation is too simpleminded.

Jason

--
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257