D. J. Bernstein
Authenticators and signatures
hash127
Frequently asked questions
How can I securely authenticate messages?
Say you have a message m = (m[0],m[1],...,m[l-1])
consisting of signed 32-bit integers,
i.e., integers between -2^31 and 2^31-1.
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 m, r, and k[n].
Exactly how secure is this message authentication system?
If the secret numbers are independent and uniformly distributed,
then an attacker has chance at most
(C+D(L+2))/2^127
of successfully forging a message that you didn't authenticate, where
- 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 4L bytes long.
See Theorem 9.1 of
my paper on h_r.
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.
What if I can't afford to share 128 truly random bits per message?
You can use the authenticator
(h_r(m)+E_k(n)) mod p,
where E is your favorite
128-bit-to-128-bit cryptographic function,
using a secret (uniform random) key k of some length,
independent of r.
Nonces here can be up to 128 bits long.
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 k of some length,
independent of r.
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.
Exactly how secure are those systems?
The attacker's forgery chance for
(h_r(m)+E_k(n)) mod p
is at most
(C+D(L+2))/2^127 + epsilon_E,
where epsilon_E is the attacker's chance of
distinguishing x |-> E_k(x)
from a uniform random 128-bit-to-128-bit 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(2L+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.
What if I don't have unique message numbers?
You could use the authenticator
E_k(h_r(m)).
If you do,
the attacker's forgery chance is at most
(C(C-1+2D)(L+2)+D)/2^128 + epsilon_E.
See Theorem 9.2 of
my paper on h_r.
Beware that this chance grows quadratically with the number of messages.
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.
Are there machine-specific variants of h_r?
No.
There are several different implementations,
but they all compute the same function.
The mathematical structure of h_r
allows excellent performance on a wide variety of computer architectures:
- 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.
How does this authentication system compare to CBC MACs and XOR MACs?
CBC MACs and XOR MACs are like
E_k(h_r(m))
in that they can be built from
any 128-bit-to-128-bit cryptographic function E,
and have a proof of security
if E is unpredictable.
(Beware, however, that the security proof for CBC MACs
assumes fixed-length messages.
CBC MACs must be changed slightly for variable-length messages.
Beware also that security degrades quadratically
with the number of messages.)
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.
How does this authentication system compare to HMAC?
HMAC-MD5 and HMAC-SHA
are the same type of authenticator as
E_k(h_r(m)),
but using MD5(r,m) or SHA(r,m)
instead of h_r(m).
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.
h_r is very fast for short messages too.
Are there other functions that can be used in place of h_r?
Yes.
The crucial property of h_r
is that it has low collision probability:
for any two different inputs,
the outputs will collide with probability on the scale of 1/2^127
if you choose r randomly.
There are many other functions with the same property.
See section 10 of
my paper on h_r
for a survey of the literature.
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.