[Omake] Lm_hash

[Jason Hickey]

On Aug 22, 2007, at 12:48 PM, Aleksey Nogin wrote:

> On 22.08.2007 12:08, Jason Hickey wrote:
>
>> 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.
> If we are concerned about intelligent adversaries, then we need to  
> use something cryptographically strong like SHA1. If not, then we  
> only need to care about:
> - speed
> - probability of getting too many collisions in a "regular" usage  
> scenario that does not involve an attacker.

I'm using the term "adversary" in the algorithmic sense, without malice.

It isn't easy to come up with an English sentence that hashes to 00...
It isn't easy to come up with an English sentence that hashes to 00...

You'll see that the text of the previous two sentences (including the  
'\n's) hashes to 0, so you can pump on them without affecting the  
hash of this message.

Granted, I'm being a little adversarial, but any English sentence  
where the ASCII codes+1 sum up to 6229 will cause a collision when  
doubled.  Line doubling isn't even unusual, especially in program text.

> I believe that my change increases the speed, has little chances of  
> introducing too many _accidental_ collisions, so it's a reasonable  
> change to make.

How much of a difference did it make to performance?  Was it really  
bad?  Maybe there is something simple we can do.

Jason

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