[Cryptography] Creating a Parallelizeable Cryptographic Hash Function
bear at sonic.net
Wed Oct 8 12:20:24 EDT 2014
On Sat, 2014-10-04 at 17:11 -0700, Christian Huitema wrote:
> > To a programmer a good hash table is not the same as a good crypto hash.
> > A programmer simply wants a fast lookup with a minimum miss, collision.
> > Most programmers do not care if a collision is moderately easy to fabricate
> > because they want to get close enough not exactly and will walk their way to
> > the desired data (short walk).
> Actually, it is a bit more complex than that. In many applications, you
> have to be concerned about denial of service attacks. If an outsider
> can manufacture hash collisions, then you can end up with a serious
> issue, the hash resolution moving for example from O(1) to O(N). Think
> for example of a hash table going from TCP headers to TCP context, and
> a SYN attack amplifying the damage by picking combinations of address
> and ports that result in hash collisions.
True, but he has a point. In most programming applications a hash
drives a hash table in a context where we aren't at all worried about
For example, in a program that's keeping track of the actors in a
simulation, where each actor is assigned a GUID number when it's
created. Then as the simulation continues, old actors are removed and
new actors are created, and the program keeps track of them with a
hash table. This app doesn't even communicate over any network and
(if it's, eg, a single-player game) probably doesn't compute
anything that any attacker cares about. All the programmer cares
about for the hash function on that table is that
a) you want aliasing (accidental collisions) to be minimized.
b) you want the hash to be fast to compute.
c) you want "random" distribution of GUID's in the hash table
(ie, no single part of your hash table should be *more*
full than the other parts, or at least not by any margin
distinguishable from statistical noise on random numbers).
I have in fact solved this problem in the past by using a counter
viewed through a linear congruential transformation to assign the
GUID's, and then using the GUID modulo the size of the hash table
as a hash function. And that's considered to be an elegant and
completely standard solution.
Table hashes, usually, are not cryptographic hashes.
More information about the cryptography