Author lemburg
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Jim.Jewett, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.snow, fx5, georg.brandl, grahamd, gregory.p.smith, gvanrossum, gz, haypo, jcea, lemburg, mark.dickinson, merwok, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, zbysz
Date 2012-01-20.00:38:01
SpamBayes Score 1.79877e-08
Marked as misclassified No
Message-id <4F18B762.1000608@egenix.com>
In-reply-to <1326996353.21.0.0703813111949.issue13703@psf.upfronthosting.co.za>
Content
Frank Sievertsen wrote:
> 
> Frank Sievertsen <python@sievertsen.de> added the comment:
> 
>> The suffix only introduces a constant change in all hash values
>> output, so even if you don't know the suffix, you can still
>> generate data sets with collisions by just having the prefix.
> 
> That's true. But without the suffix, I can pretty easy and efficient guess the prefix by just seeing the result of a few well-chosen and short repr(dict(X)). I suppose that's harder with the suffix.

Since the hash function is known, it doesn't make things much
harder. Without suffix you just need hash('') to find out what
the prefix is. With suffix, two values are enough.

Say P is your prefix and S your suffix. Let's say you can get the
hash values of A = hash('') and B = hash('\x00').

With Victor's hash function you have (IIRC):

A = hash('')     = P ^ (0<<7) ^ 0 ^ S = P ^ S
B = hash('\x00') = ((P ^ (0<<7)) * 1000003) ^ 0 ^ 1 ^ S = (P * 1000003) ^ 1 ^ S

Let X = A ^ B, then

X = P ^ (P * 1000003) ^ 1

since S ^ S = 0 and 0 ^ Y = Y (for any Y), i.e. the suffix doesn't
make any difference.

For P < 500000, you can then easily calculate P from X
using:

P = X // 1000002

(things obviously get tricky once overflow kicks in)

Note that for number hashes the randomization doesn't work at all,
since there's no length or feedback loop involved.

With Victor's approach hash(0) would output the whole seed,
but even if the seed is not known, creating an attack data
set is trivial, since hash(x) = P ^ x ^ S.
History
Date User Action Args
2012-01-20 00:38:02lemburgsetrecipients: + lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, haypo, christian.heimes, benjamin.peterson, merwok, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5
2012-01-20 00:38:01lemburglinkissue13703 messages
2012-01-20 00:38:01lemburgcreate