Authenticators and signatures

hash127

Compute the **authenticator**
*t* = (*h*_*r*(*m*)+*k*[*n*]) mod *p* where

*n*is a public**nonce**, i.e., unique message number;*r*=*r*[0] + 2^32*r*[1] + 2^64*r*[2] + 2^96*r*[3], where each*r*[*i*] is a secret random signed 32-bit integer;*k*[*n*] =*k*[*n*][0] + 2^32*k*[*n*][1] + 2^64*k*[*n*][2] + 2^96*k*[*n*][3], where each*k*[*n*][*i*] is a secret random signed 32-bit integer;*p*is the prime number 2^127-1; and*h*_*r*(*m*) = (*r*^(*l*+1) +*m*[0]*r*^*l*+*m*[1]*r*^(*l*-1) + ... +*m*[*l*-1]*r*) mod*p*.

Now you can transmit *n*,*m*,*t*
through an untrusted channel
to a receiver who also knows *k* and *r*.
The receiver checks whether
*t* = (*h*_*r*(*m*)+*k*[*n*]) mod *p*
and discards *n*,*m*,*t* otherwise.

The hash127 library
computes ` t`
given

*C*is the number of messages for which the attacker has seen your valid authenticators;*D*is the number of forgery attempts; and*L*is the maximum message length, i.e., each message is at most 4*L*bytes long.

For example, if messages are at most 4 gigabytes long, and the attacker tries 1000000000000000 forgeries, then his chance of success is at most 0.0000000000000063.

As an alternative,
you can use the authenticator
*F*_*k*(*n*,*h*_*r*(*m*)),
where ` F` is your favorite
256-bit-to-128-bit cryptographic function,
using a secret (uniform random) key

Here are some good choices for *F*:

*F*_*k*(*x*) = MD5(*k*,*x*), with a 256-bit*k*;*F*_*k*(*x*) = MD5C(*k*,*x*), with a 384-bit*k*, where MD5C is the MD5 compression function;*F*_*k*(*x*) = first 128 bits of SHA(*k*,*x*), with a 256-bit*k*;*F*_*k*(*n*,*u*) =*E*_*k*(*u*xor*E*_*k*(*n*)) where*E*is your favorite 128-bit-to-128-bit cryptographic function.

A standard cryptographic assumption about *E*,
used throughout the cryptographic literature to justify a variety of
secret-key constructions,
is that *E* is **unpredictable**,
i.e., epsilon_*E* is negligible.
Beware that
*proving* such an assumption is far beyond the state of the art
in theoretical computer science;
it is possible that epsilon_*E* is actually nonnegligible
for every easily computable low-entropy function *E*.
On the other hand,
the best known attacks on widely used functions *E*
have not achieved a noticeable value of epsilon_*E*.

The attacker's forgery chance for
*F*_*k*(*n*,*h*_*r*(*m*))
is at most
*D*(2*L*+5)/2^128 + epsilon_*F*,
where epsilon_*F* is the attacker's chance of
distinguishing *x* |-> *F*_*k*(*x*)
from a uniform random 256-bit-to-128-bit function.
See Theorem 9.3 of
my paper on *h*_*r*.

Note that many protocols already need unique message numbers
for other purposes,
such as replay prevention.
Those message numbers can be used directly as *n*'s.

*h*_*r*is easy to parallelize. Its inherent latency is extremely low.*h*_*r*is easy to vectorize. It performs the same operations on many separate chunks of input.*h*_*r*can be implemented using integer multiplication, 53-bit floating-point multiplication, 64-bit floating-point multiplication, MMX multiplication, SSE multiplication, etc. The 127-bit quantities*r*^(*l*-*i*) mod (2^127-1) can be decomposed in many different ways.

CBC MACs and XOR MACs differ from
*E*_*k*(*h*_*r*(*m*))
in that they apply the cryptographic function to every block of *m*.
This is much slower than applying *h*_*r*.

Compare my
performance measurements for *h*_*r*
with the best available results for MD5 and SHA:
for 2048-byte messages,
currently about

- 1.35 times faster than MD5 on a Pentium,
- 1.44 times faster than MD5 on a Pentium-III,
- 2.52 times faster than MD5 on an Alpha 21264,
- 2.68 times faster than MD5 on an UltraSPARC I,
- 2.97 times faster than SHA on a Pentium-III,
- 3.00 times faster than SHA on an Alpha 21264, and
- 4.47 times faster than SHA on an UltraSPARC I.

What distinguishes *h*_*r* is its speed.
*h*_*r* is the first high-security system
to break the MD5 speed barrier.

All of these ``universal hash functions''
live in the pleasant world of mathematically guaranteed security.
Other parts of a cryptographic system may fail and need replacement,
but *h*_*r* can be used forever; it will never be broken.
Effort invested in *h*_*r* will not be wasted.