[Mesa-dev] Hash Collision Risk Maths with Salt values.

[Peter Dolding]

> Peter,
>
> While there may be things of value in your replies I would kindly ask
> you [again] to try and keep your replies brief.
> If one is to choose between working on a feature/bug and reading a
> 900+ (word) email I'd imagine they'll choose the former.
>
> I'm saying this for your own good - hopefully you'll consider it as
> such and adjust accordingly.
>
> Thanks
> Emil

That is reduced down from 10000 pages of cryptography PHD document.

If you are scared off by a email the size I posted you most likely
should stay way from any bug with a cryptography side because you will
not be willing to read enough to understand what you have done..

At least the following section needs to be read:

> With SHA1 you start with 160 bits of unique values for items hashed.

> Lets say we add a build_id into the mix.   This changes per version.
>  So you have released 2 different build ids how many unique hashed
> values do you have if you place them all in one directory.  The answer
> is now 159 of course you have just lost 1 bit of uniqueness.  Or
> instead of 6.6 million years only 3.3 million years.

> It is luckily linear  so take numbers number of salts factor by 2 take
> that number of bits off your hash then calculate your probability of
> collision.   So using a 512 bit hash really makes this hard using a
> shorter hash getting down into thousand of years might not take that
> ong at all.

> Not putting different salted hashes in the same location also reduces
> odds of collision due to avoiding salt effect.   So we give the
> build_id and gpu_id  their own directory this means the build_id and
> gpu_id salts have not effected the outcome as much. The result is you
> still have have all the hash bits of uniqueness.  So build_id and
> gpu_id has not resulted in subtracting bits off the hash by giving
> them directories.
This is slightly wrong worded.  Should not be "avoid salt effects."
but  "Reduced salt effects to collisions caused by minor variations in
data"

> So build_id and gpu_id values would be salts.

> The fastest way to really undermine a hash you are depending being
> unique is to be careless with salt effects.   Add enough salt effects
> when you run the maths your hash might have no bits left so making a
> collision likely.   It is possible to add enough salts to consume up a
> 512 bit hash example being.  32 salts with 256(16^2) unique values
> each you have just made collisions likely with a 512bit hash.    A
> hash like SHA1 failure point due to salting  10 salts with 256(16^2)
> unique values each.   So each of the individual salts damage to the
> hash does not have to be that much but accumulative can be quite a
> large problem.

The bits after that cover how the git example is wrong for the case at
hand and operational considerations and and what kind of attack and
what classification the current work around are.   This first bit
covers you basic working maths like newton model of gravity for risk
of hash collisions by adding salts.  Like its not 100 percent right
but it takes less than 1000 pages mathematics to know if the hash is
at possible risk or not from the salts you have added in the worst
possible case.

In a lot of ways I have over compacted this already and lost a lot of
the finer details but in this use case I don't think the finer details
are important.  I have already compacted to the point I have lost 1 or
2 finer details that might be important.   So I was not expecting to
be told this needs to be shorter to be completely correct it need to
be longer.

Peter Dolding