Universal hashing.

[mLib] / man / unihash.3

.\" -*-nroff-*-
.de VS
.sp 1
.RS
.nf
.ft B
..
.de VE
.ft R
.fi
.RE
.sp 1
..
.de hP
.IP
.ft B
\h'-\w'\\$1\ 'u'\\$1\ \c
.ft P
..
.ie t \{\
.  ds ss \s8\u
.  ds se \d\s0
.  ds us \s8\d
.  ds ue \u\s0
.  ds *d \(*d
.  ds >= \(>=
.\}
.el \{\
.  ds ss ^
.  ds se
.  ds us _
.  ds ue
.  ds *d \fIdelta\fP
.  ds >= >=
.\}
.TH unihash 3 "5 July 2003" "Straylight/Edgeware" "mLib utilities library"
.SH NAME
unihash \- simple and efficient universal hashing for hashtables
.\" @unihash_setkey
.\" @UNIHASH_INIT
.\" @unihash_hash
.\" @UNIHASH
.\" @unihash
.SH SYNOPSIS
.nf
.B "#include <mLib/unihash.h>"

.BI "void unihash_setkey(unihash_info *" i ", uint32 " k );
.BI "uint32 UNIHASH_INIT(const unihash_info *" i );
.BI "void unihash_hash(const unihash_info *" st ", uint32 " a ,
.BI "                  const void *" p ", size_t " sz );
.BI "uint32 unihash(const unihash_info *" i ", const void *" p ", size_t " sz );
.BI "uint32 UNIHASH(const unihash_info *" i ", const void *" p ", size_t " sz );
.fi
.SH DESCRIPTION
The
.B unihash
system implements a simple and relatively efficient
.IR "universal hashing family" .
Using a such a universal hashing family means that it's provably
difficult for an adversary to choose input data whose hashes collide,
thus guaranteeing good average performance even on maliciously chosen
data.
.PP
Unlike, say,
.BR crc32 (3),
the
.B unihash
function is
.I keyed
\- in addition to the data to be hashed, the function takes as input a
32-bit key.  This key should be chosen at random each time the program
runs.
.SS "Preprocessing a key"
Before use, a key must be
.I preprocessed
into a large (16K) table which is used by the main hashing functions.
The preprocessing is done by
.BR unihash_setkey :
pass it a pointer to a
.B unihash_info
structure and the 32-bit key you've chosen, and it stores the table in
the structure.
.PP
Objects of type
.B unihash_info
don't contain any pointers to other data and are safe to free when
you've finished with them; or you can just allocate them statically or
on the stack if that's more convenient.
.SS "Hashing data"
The function
.B unihash_hash
takes as input:
.TP
.BI "const unihash_info *" i
A pointer to the precomputed tables for a key.
.TP
.BI "uint32 " a 
An accumulator value.  This should be
.BI UNIHASH_INIT( i )
for the first chunk of a multi-chunk input, or the result of the
previous
.B unihash_hash
call for subsequent chunks.
.TP
.BI "const void *" p
A pointer to the start of a buffer containing this chunk of data.
.TP
.BI "size_t " sz
The length of the chunk.
.PP
The function returns a new accumulator value, which is also the hash of
the data so far. So, to hash multiple chunks of data, do something like
.VS
uint32 a = UNIHASH_INIT(i);
a = unihash_hash(i, a, p_0, sz_0);
a = unihash_hash(i, a, p_1, sz_1);
/* ... */
a = unihash_hash(i, a, p_n, sz_n);
.VE
The macro
.B UNIHASH
and function
.B unihash
are convenient interfaces to
.B unihash_hash
if you only wanted to hash one chunk.
.SS "Theoretical issues"
The hash function implemented by
.B unihash
is
.RI ( l \ +\ 1)/2\*(ss32\*(se-almost
XOR-universal, where
.I l
is the length (in bytes) of the longest string you hash.  That means
that, for any pair of strings
.I x
and
.I y
and any 32-bit value \*(*d, the probability taken over all choices of the
key
.I k
that
.IR H\*(usk\*(ue ( x )\  \c
.BR xor \c
.RI \  H\*(usk\*(ue ( y )\ =\ \*(*d
is no greater than
.RI ( l \ +\ 1)/2\*(ss32\*(se.
.PP
This fact is proven in the header file, but it requires more
sophisticated typesetting than is available here.
.PP
The function evaluates a polynomial over GF(2\*(ss32\*(se) whose
coefficients are the bytes of the message and whose variable is the key.
Details are given in the header file.
.PP
For best results, you should choose the key as a random 32-bit number
each time your program starts.  Choosing a different key for different
hashtables isn't necessary.  It's probably a good idea to avoid the keys
0 and 1.  This raises the collision bound to
.RI ( l \ +\ 1)/(2\*(ss32\*(se\ \-\ 2)
(which isn't a significant increase) but eliminates keys for which the
hash's behaviour is particularly poor.
.PP
In tests,
.B unihash
actually performed better than
.BR crc32 ,
so if you want to just use it as a fast-ish hash with good statistical
properties, choose some fixed key
.IR k \ \*(>=\ 2.
.PP
We emphasize that the proof of this function's collision behaviour is
.I not
dependent on any unproven assumptions (unlike many `proofs' of
cryptographic security, which actually reduce the security of some
construction to the security of its components).  It's just a fact.
.SH SEE ALSO
.BR crc32 (3),
.BR mLib (3).
.SH AUTHOR
Mark Wooding (mdw@nsict.org).