To be incorporated into author’s High-speed cryptography book.

FLOATING-POINT ARITHMETIC AND MESSAGE AUTHENTICATION

DANIEL J. BERNSTEIN

Abstract. There is a well-known class of message authentication systems guaranteeing that attackers will have a negligible chance of successfully forging a message. This paper shows how one of these systems can hash messages at extremely high speed—much more quickly than previous systems at the same security level—using IEEE floating-point arithmetic. This paper also presents a survey of the literature in a unified mathematical framework.

1. Introduction

Let m = (m_{0}, m_{1}, …, m_{ℓ−1}) be a sequence of integers in [−2^{31}, 2^{31} − 1]. For any integer r define h_{r}(m) = (r^{ℓ+1} + m_{0}r^{ℓ} + m_{1}r^{ℓ−1} + ⋯ + m_{ℓ−1}r) mod (2^{127} − 1).

The point of this paper is an extremely fast method to compute h_{r}(m), given m, after some precomputation depending only on r. The method is described in a bottom-up fashion in Sections 2 through 6. A variant appears in Section 7. My current implementation achieves the following speeds in cache:

ℓ 16 32  64 128 256 512
Bytes in m 64 128 256 512 1024 2048
Pentium cycles 550 825 1340 2480 4667 9275
Pentium-II cycles 566 792 1303 2406 4527 8850
Alpha-21264 cycles 600 864 1375 2561 4814 9432
≈ UltraSPARC-I cycles 570 762 1148 2111 3818 7438
≈ HP-8200 cycles  5000

Message authentication. One can authenticate a single message m as follows. The sender and receiver share secret integers r and k. The sender computes an authenticator s = (k+h_{r}(m)) mod (2^{127} −1) and sends (m, s). The receiver verifies (m, s) by recomputing s. An attacker, given (m, s), has a negligible probability of successfully forging a different message. See Section 8 for further discussion.

One can authenticate many messages by combining h_{r} with a block cipher such as Rijndael: the authenticator of a message m is Rijndael_{k}(h_{r}(m)). An attacker who can break this system can break Rijndael with similar success and similar speed. See Section 9 for further discussion.

There are many functions that can be used in place of h_{r}. Section 10 presents a survey of the literature in a unified mathematical framework. What distinguishes h_{r} is its speed: it is the first high-security system that offers better speed than the MD5-based systems in common use today.

Date: 2004.09.18. Permanent ID of this document: dabadd3095644704c5cbe9690ea3738e.

2000 Mathematics Subject Classification. Primary 11Y16; Secondary 65G50, 94A60.

The author was supported by the National Science Foundation under grant DMS–9600083.

Other applications. Checking a public-key signature in the system described in [21] means checking that a^{2} = bc+de, given integers a, b, c, d, e. One way to do this, much faster than computing a^{2} −bc−de, is to select a prime number p in [2^{120}, 2^{128}] and see whether ((a mod p)^{2} − (b mod p)(c mod p) − (d mod p)(e mod p)) mod p is zero; if p is kept secret then there is a negligible chance of anyone else being able to find a, b, c, d, e with a^{2} − bc − de nonzero but divisible by p. The algorithm described in this paper can easily be adapted to the problem of reducing large integers to (reasonably) small integers modulo p. Similar comments apply to other applications in which one must check the result of a series of ring operations.

The same techniques can be applied to other problems in multidigit arithmetic, including high-precision multiplication and modular exponentiation.

Priority dates. I published hash127 0.50, the first software achieving speeds better than MD5, in April 1999, and described it in [19].

Black, Halevi, Krawczyk, Krovetz, and Rogaway independently observed that similar functions could be computed at high speed. They published this observation in [24] in August 1999.

I published hash127 0.70, which achieved the speeds stated above, in March 2000. See http://cr.yp.to/hash127.html. I also published a complete version of this paper at that time.

  I announced a better function in http://cr.yp.to/talks.html#2002.06.15,

using 128-bit coefficients modulo 2^{130} − 5. The larger coefficient size allows fast computation without precomputation. This paper will be revised accordingly.

Acknowledgments. Thanks to Theodorus J. Dekker for sending me copies of [1] and [2]; Thomas Johansson for sending me a copy of [25]; David A. Molnar for sending me a copy of [50]; and Donald E. Knuth for his comments.

2. Fixed-precision floating-point arithmetic

A b-bit floating-point number is a real number of the form 2^{e}f where e and f are integers with |f| < 2^{b}.

Theorem 2.1. Let b be a nonnegative integer, and let k be an integer. Let x be a b-bit floating-point number. If |x| > 2^{k−1}(2^{b} − 1) then x ∈ 2^{k}Z.

Proof. By hypothesis x = 2^{e}f for some integers e, f with |f| ≤ 2^{b} − 1. If e ≥ k then x ∈ 2^{k}Z. If e ≤ k − 1 then |x| ≤ 2^{e}(2^{b} − 1) ≤ 2^{k−1}(2^{b} − 1). □

Addition and multiplication. Modern computers can quickly perform several operations upon 53-bit floating-point numbers (under minor restrictions that are not relevant to this paper):

• Given 53-bit floating-point numbers x, y, compute fp_{53}(x + y).

• Given 53-bit floating-point numbers x, y, compute fp_{53}(x − y).

• Given 53-bit floating-point numbers x, y, compute fp_{53}(xy). Here fp_{b} z is, for each real number z, a b-bit floating-point number close to z. Specifically, if |z| ≤ 2^{e+b} then |z − fp_{b} z| is guaranteed to be at most 2^{e−1}.

Theorem 2.2. Let b be a positive integer. Let z be a b-bit floating-point number. Then z = fp_{b} z.

Therefore, given 53-bit floating-point numbers x and y, modern computers can quickly compute x + y if x + y is a 53-bit floating-point number, and x − y if x − y is a 53-bit floating-point number, and xy if xy is a 53-bit floating-point number.

Proof. Suppose fp_{b} z ≠ z. Find an integer e such that 2^{e−1} < |z − fp_{b} z| ≤ 2^{e}. Then |z| > 2^{e+b} by the fp_{b} guarantee, so |fp_{b} z| > 2^{e}(2^{b} − 1). Both z and fp_{b} z are in 2^{e+1}Z by Theorem 2.1, so |z − fp_{b} z| is in 2^{e+1}Z; contradiction. □

Theorem 2.3. Let b be a positive integer, and let k be an integer. Let z be a real number in [2^{k+b−1}, 2^{k+b}]. Then fp_{b} z ∈ 2^{k}Z and fp_{b} z ∈ [2^{k+b−1}, 2^{k+b}].

Proof. Write x = fp_{b} z. Then |z − x| ≤ 2^{k−1} by the fp_{b} guarantee; so L ≤ x ≤ R where L = 2^{k−1}(2^{b} − 1) and R = 2^{k−1}(2^{b+1} + 1).

Observe that x > L. (If not then z ≤ L + 2^{k−1} = 2^{k+b−1}, so |z − x| ≤ 2^{k−2} by the fp_{b} guarantee, so z ≤ L + 2^{k−2} < 2^{k+b−1}, contradiction.) Thus x ∈ 2^{k}Z by Theorem 2.1. The multiples of 2^{k} between L and R are all between 2^{k+b−1} and 2^{k+b} inclusive. □

Rounding. Define top_{k,b} x = fp_{b}(fp_{b}(x+3·2^{k+b−2})−3·2^{k+b−2}) and bottom_{k,b} x = fp_{b}(x − top_{k,b} x). Note that 3 · 2^{k+b−2} is a b-bit floating-point number for b ≥ 2.

Theorem 2.4. Let b be an integer with b ≥ 2, and let k be an integer. Let x be a b-bit floating-point number with |x| ≤ 2^{k+b−2}. Then x = top_{k,b} x + bottom_{k,b} x; top_{k,b} x ∈ 2^{k}Z; and |bottom_{k,b} x| ≤ 2^{k−1}.

Proof. Write z = x + 3 · 2^{k+b−2} and y = fp_{b} z − 3 · 2^{k+b−2}, so that top_{k,b} x = fp_{b} y. I will show that top_{k,b} x = y and bottom_{k,b} x = x − y.

First 2^{k+b−1} ≤ z ≤ 2^{k+b}. Thus |x − y| = |z − fp_{b} z| ≤ 2^{k−1}. Furthermore, by Theorem 2.3, fp_{b} z ∈ 2^{k}Z, and 2^{k+b−1} ≤ fp_{b} z ≤ 2^{k+b}. Thus y ∈ 2^{k}Z, and |y| ≤ 2^{b−2}2^{k}; so y is a b-bit floating-point number. By Theorem 2.2, y = fp_{b} y = top_{k,b} x.

If y = 0 then x − y = x so x − y is a b-bit floating-point number. Otherwise |y| ≥ 2^{k} so |x| ≥ 2^{k−1}. By Theorem 2.1, x ∈ 2^{k−b}Z. Thus x − y ∈ 2^{k−b}Z, and |x − y| ≤ 2^{b−1}2^{k−b}; so x − y is a b-bit floating-point number.

Finally bottom_{k,b} x = fp_{b}(x − top_{k,b} x) = fp_{b}(x − y) = x − y by Theorem 2.2. □

Rounding down. Now define topleft_{k,b} z = top_{k,b} fp_{b}(z − (2^{k−1} − 2^{k−33})) and bottomleft_{k,b} z = fp_{b}(z − topleft_{k,b} z). Note that 2^{k−1} − 2^{k−33} is a b-bit floatingpoint number for b ≥ 32.

Theorem 2.5. Let b be an integer with b ≥ 34, and let k be an integer. Let z be a real number with z ∈ 2^{k−32}Z and |z| ≤ 2^{k+b−34}. Then topleft_{k,b} z = 2^{k} ⌊z/2^{k}⌋ and bottomleft_{k,b} z = z mod 2^{k}.

Proof. Write x = z −(2^{k−1} −2^{k−33}). Then x ∈ 2^{k−33}Z, and |x| < 2^{k+b−34} +2^{k−1} < 2^{b}2^{k−33}, so x is a b-bit floating-point number. Thus fp_{b} x = x by Theorem 2.2.

Write y = topleft_{k,b} z. Then y = top_{k,b} fp_{b} x = top_{k,b} x. By Theorem 2.4, y ∈ 2^{k}Z and |x − y| ≤ 2^{k−1}. Now y ≤ x + 2^{k−1} = z + 2^{k−33}, and both y and z are in 2^{k−32}Z, so y ≤ z; and z < x + 2^{k−1} ≤ y + 2^{k}. Hence y = 2^{k} ⌊z/2^{k}⌋.

Finally, z − y is a multiple of 2^{k−32} between 0 and 2^{b−2}2^{k−32}, so it is a b-bit floating-point number. By Theorem 2.2, z − y = fp_{b}(z − y) = bottomleft_{k,b} z. □

Notes. IEEE in [4] encouraged computer manufacturers to provide hardware for certain operations on 24-bit (“single-precision”) and 53-bit (“double-precision”) floating-point numbers. It is now generally safe to assume that, for example, a C compiler will interpret the addition of two double variables as the operation x, y ↦ fp_{53}(x + y). Exception: On x86 chips, such as the Pentium, addition of double variables is sometimes interpreted as x, y ↦ fp_{64}(x + y). Here’s the story:

• The Pentium handles 64-bit (“extended-precision”) addition at the same speed as 53-bit addition. Unfortunately, it uses the same instruction for 24bit addition, 53-bit addition, and 64-bit addition; there is a global variable (“precision control”) that selects the precision of subsequent additions.

• C compilers could set 24-bit precision before float additions, 53-bit precision before double additions, and 64-bit precision before long double additions; but that would take time and effort. Many compilers, notably gcc, leave the precision alone, under the incorrect theory that anyone asking for 53-bit precision will be just as happy with 64-bit precision.

• Some operating systems, notably Linux, set 64-bit precision by default.

Programs that need fp_{53}, and not fp_{64}, must set 53-bit precision manually.

For each real number z, the number of choices of fp_{b} z meeting the fp_{b} guarantee is either 1 or 2. IEEE specified a particular choice of fp_{b} z, following the “roundto-even” rule discussed in [44, page 221].

The idea of Theorem 2.4 is known in numerical analysis as “loss of precision from cancellation”; see, e.g., [44, exercise 4.2.2–25]. The fact that precision loss can be useful—that, in particular, one can extract the high bits from a floatingpoint number by adding and then subtracting a larger number—was pointed out by Kahan in [39]. The use of a constant for the larger number, for example to round a floating-point number to an integer, appears in, e.g., [44, page 209].

Bit extraction is easy in hardware. Computers offer bit-extraction operations that are faster than the addition and subtraction in top_{k,b}. Unfortunately, these bit-extraction operations work with numbers stored in one format, and floatingpoint operations work with numbers stored in another format; it takes time to convert numbers from one format to the other.

3. Carries modulo 2^{127} − 1

One can write an integer modulo 2^{127} −1 in many ways as a sum t_{7} +t_{6} +⋯+t_{0} where t_{j} is a 53-bit floating-point number with t_{j} ∈ 2^{16j}Z. Theorem 3.2 starts from a sum t_{7} + t_{6} + ⋯ + t_{0} with |t_{j}| ≤ 0.98 · 2^{53}2^{16j} and constructs an equivalent sum v_{7} + v_{6} + ⋯ + v_{0} with |v_{j}| ≤ 1.01 · 2^{15}2^{16j}.

Define carry_{i}(t_{0}, …, t_{7}) and carrybound_{i}(T_{0}, …, T_{7}) for i ∈ {0, 1, 2, 3, 4, 5, 6} as follows: carry_{i}(t_{0}, …, t_{7}) = (u_{0}, …, u_{7}) where u_{i} = bottom_{16+16i,53} t_{i}, u_{i+1} = fp_{53}(t_{i+1} + top_{16+16i,53} t_{i}), and u_{j} = t_{j} otherwise; and carrybound_{i}(T_{0}, …, T_{7}) = (U_{0}, …, U_{7}) where U_{i} = 2^{15+16i}, U_{i+1} = T_{i+1} +T_{i} +2^{15+16i}, and U_{j} = T_{j} otherwise.

Also define carry_{i}(t_{0}, …, t_{7}) and carrybound_{i}(T_{0}, …, T_{7}) for i = 7 as follows: carry_{7}(t_{0}, …, t_{7}) = (u_{0}, …, u_{7}) where u_{0} = fp_{53}(t_{0} + 2^{−127} top_{127,53} t_{7}), u_{7} = bottom_{127,53} t_{7}, and u_{j} = t_{j} otherwise; carrybound_{7}(T_{0}, …, T_{7}) = (U_{0}, …, U_{7}) where U_{0} = T_{0} + 2^{−127}T_{7} + 2^{−1}, U_{7} = 2^{126}, and U_{j} = T_{j} otherwise.

Finally define squeeze = carry_{1} carry_{0} carry_{7} carry_{6} … carry_{1} carry_{0}.

Theorem 3.1. Let T_{0}, …, T_{7} be real numbers with T_{j} ≤ 0.99·2^{53}2^{16j}. Let t_{0}, …, t_{7} be real numbers with t_{j} ∈ 2^{16j}Z and |t_{j}| ≤ T_{j}. Fix i ∈ {0, …, 7}. Define (u_{0}, …, u_{7}) = carry_{i}(t_{0}, …, t_{7}) and (U_{0}, …, U_{7}) = carrybound_{i}(T_{0}, …, T_{7}). Then u_{7} + ⋯ + u_{0} ≡ t_{7} + ⋯ + t_{0} (mod 2^{127} − 1); u_{j} ∈ 2^{16j}Z; and |u_{j}| ≤ U_{j}.

Proof. For i = 7: Write y = top_{127,53} t_{7}. By Theorem 2.4, bottom_{127,53} t_{7} = t_{7} − y; y ∈ 2^{127}Z; and |t_{7} − y| ≤ 2^{126}. Thus u_{7} = t_{7} − y ∈ 2^{112}Z and |u_{7}| ≤ 2^{126} = U_{7}. Furthermore, t_{0} + 2^{−127}y ∈ Z, and

|t_{0} + 2^{−127}y| ≤ T_{0} + 2^{−127}T_{7} + 2^{−1} ≤ 0.99(1 + 2^{−15})2^{53} + 2^{−1} < 2^{53},

so u_{0} = fp_{53}(t_{0} + 2^{−127}y) = t_{0} + 2^{−127}y by Theorem 2.2. Hence u_{0} ∈ Z and |u_{0}| ≤ T_{0} +2^{−127}T_{7} +2^{−1} = U_{0}. Also u_{7} +⋯+u_{0} −t_{7} −⋯−t_{0} = (1−2^{127})2^{−127}y ∈ (2^{127} − 1)Z.

For i < 7: Write y = top_{16+16i,53} t_{i}. By Theorem 2.4, bottom_{16+16i,53} t_{i} = t_{i} −y; y ∈ 2^{16+16i}Z; and |t_{i} − y| ≤ 2^{15+16i}. Thus u_{i} = t_{i} − y ∈ 2^{16i}Z and |u_{i}| ≤ 2^{15+16i} = U_{i}. Furthermore, t_{i+1} + y ∈ 2^{16+16i}Z, and

|t_{i+1} + y| ≤ T_{i+1} + T_{i} + 2^{15+16i} ≤ (0.99(1 + 2^{−16})2^{53} + 2^{−1})2^{16+16i} < 2^{53}2^{16+16i},

so u_{i+1} = fp_{53}(t_{i+1} + y) = t_{i+1} + y by Theorem 2.2. Hence u_{i+1} ∈ 2^{16+16i}Z and |u_{i+1}| ≤ T_{i+1} + T_{i} + 2^{15+16i} = U_{i+1}. Also u_{7} + ⋯ + u_{0} = t_{7} + ⋯ + t_{0}. □

Theorem 3.2. Let t_{0}, …, t_{7} be real numbers with t_{j} ∈ 2^{16j}Z and |t_{j}| ≤ 0.98 · 2^{53}2^{16j}. Define (v_{0}, …, v_{7}) = squeeze(t_{0}, …, t_{7}). Then v_{j} ∈ 2^{16j}Z; |v_{j}| ≤ 1.01 · 2^{15}2^{16j}; and v_{7} + ⋯ + v_{0} ≡ t_{7} + ⋯ + t_{0} (mod 2^{127} − 1).

Proof. Write T_{j} = 0.98 · 2^{53}2^{16j}. The reader may check that

carrybound_{1} carrybound_{0} carrybound_{7} … carrybound_{0}(T_{0}, T_{1}, …, T_{7})

is (2^{15}, 2^{31}, (1.001 …)2^{47}, 2^{63}, 2^{79}, 2^{95}, 2^{111}, 2^{126}), and that each of the intermediate carrybound results is at most (0.99 · 2^{53}, 0.99 · 2^{53}2^{16}, …, 0.99 · 2^{53}2^{112}). Apply Theorem 3.1 repeatedly. □

Notes. There are many variants of Theorem 3.2. One can replace squeeze with carry_{6} carry_{5} carry_{4} carry_{3} carry_{2} carry_{1} carry_{0} carry_{7} carry_{6} carry_{5} to obtain a more pleasant bound 1 · 2^{15}2^{16j}. Or one can replace squeeze with

carry_{5} carry_{1} carry_{4} carry_{0} carry_{7} carry_{3} carry_{6} carry_{2} carry_{5} carry_{1} carry_{4} carry_{0};

this involves more floating-point operations but allows much better parallelization on typical computers.

Section 4 explains how to find a unique representative for each integer modulo 2^{127} − 1. In the computation of h_{r}, however, I do not find unique representatives until the end; instead I use Theorem 3.2 to find small representatives, sufficiently small to carry out further operations. This idea was published by Robertson in [52] as a way to speed up division circuitry, and expanded by Avizienis in [11] to other arithmetic operations.

6 DANIEL J. BERNSTEIN

4. Complete reduction modulo 2^{127} − 1

Define freeze(t_{0}, t_{1}, t_{2}, t_{3}) = (x_{0}, x_{1}, x_{2}, x_{3}) where

q_{0} = topleft_{0,53} fp_{53}(2^{−127}t_{3} + 2^{−1}),
q_{1} = topleft_{32,53} fp_{53}(t_{0} + q_{0}),
q_{2} = topleft_{64,53} fp_{53}(t_{1} + q_{1}),
q_{3} = topleft_{96,53} fp_{53}(t_{2} + q_{2}),
q_{4} = topleft_{127,53} fp_{53}(t_{3} + q_{3}),
u_{0} = fp_{53}(t_{0} + 2^{−127}q_{4}),
u_{1} = fp_{53}(t_{1} + topleft_{32,53} u_{0}),
u_{2} = fp_{53}(t_{2} + topleft_{64,53} u_{1}),
x_{0} = bottomleft_{32,53} u_{0},
x_{1} = bottomleft_{64,53} u_{1},
x_{2} = bottomleft_{96,53} u_{2}, and
x_{3} = fp_{53}(fp_{53}(t_{3} − q_{4}) + topleft_{96,53} u_{2}).

Theorem 4.2 shows that if t = t_{3} + t_{2} + t_{1} + t_{0}, with t_{j} ∈ 2^{32j}Z and t_{j} not too large, then the base-2^{32} representation of t mod (2^{127} − 1) is 2^{−96}x_{3}, 2^{−64}x_{2}, 2^{−64}x_{1}, x_{0}. Theorem 4.1. Let u and v be integers with |u| ≤ 2^{120} and |v| ≤ 2^{120}. Define t = 2^{96}v + u. Then ⌊t/(2^{127} − 1)⌋ = ⌊2^{−127}(t + 2^{−31}v + 2^{−1})⌋. Proof. Write p = 2^{127} − 1 and q = ⌊t/p⌋. Then |q| ≤ 2^{90} since |t| ≤ (2^{96} + 1)2^{120} ≤ 2^{90}p; so |2^{−127}q + 2^{−127}u| ≤ 2^{−37} + 2^{−7}; so 0 < 2^{−1} − 2^{−127}q − 2^{−127}u < 1.

Now write r = t − pq and x = r + 2^{−127}r + 2^{−1} − 2^{−127}q − 2^{−127}u. Observe that 2^{−127}(t+2^{−31}v+2^{−1}) = q+2^{−127}x. But 0 ≤ r ≤ p−1 < 2^{127}, so 0 ≤ r+2^{−127}r < p, so 0 < x < p + 1 = 2^{127}, so ⌊q + 2^{−127}x⌋ = q. □ Theorem 4.2. Let t_{0}, t_{1}, t_{2}, t_{3} be real numbers with t_{j} ∈ 2^{32j}Z and |t_{j}| ≤ 2^{49}2^{32j}. Define (x_{0}, x_{1}, x_{2}, x_{3}) = freeze(t_{0}, t_{1}, t_{2}, t_{3}). Then x_{j} ∈ 2^{32j}Z; 0 ≤ x_{j} < 2^{32}2^{32j}; and (t_{3} + t_{2} + t_{1} + t_{0}) mod (2^{127} − 1) = x_{3} + x_{2} + x_{1} + x_{0}. Proof. Write p = 2^{127} − 1, t = t_{3} + t_{2} + t_{1} + t_{0}, and ϵ = 2^{−127}t_{3} + 2^{−1}. Then ⌊t/p⌋ = ⌊2^{−127}(t + ϵ)⌋ by Theorem 4.1.

Write q_{0} = topleft_{0,53} fp_{53} ϵ. Note that ϵ ∈ 2^{−32}Z and |ϵ| ≤ 2^{19}; so q_{0} = topleft_{0,53} ϵ by Theorem 2.2. Thus q_{0} = ⌊ϵ⌋ by Theorem 2.5.

Similarly write q_{1} = topleft_{32,53} fp_{53}(t_{0} + q_{0}), q_{2} = topleft_{64,53} fp_{53}(t_{1} + q_{1}), q_{3} = topleft_{96,53} fp_{53}(t_{2} + q_{2}), and q_{4} = topleft_{127,53} fp_{53}(t_{3} + q_{3}). Then q_{1} = 2^{32} ⌊2^{−32}(t_{0} + ϵ)⌋; q_{2} = 2^{64} ⌊2^{−64}(t_{1} + t_{0} + ϵ)⌋; q_{3} = 2^{96} ⌊2^{−96}(t_{2} + t_{1} + t_{0} + ϵ)⌋; and q_{4} = 2^{127} ⌊2^{−127}(t_{3} + t_{2} + t_{1} + t_{0} + ϵ)⌋ = 2^{127} ⌊t/p⌋.

Hence t mod p = t − q_{4} + 2^{−127}q_{4}. Also |2^{−127}q_{4}| ≤ 2^{19} since |t| ≤ 2^{19}p.

Write w = fp_{53}(t_{3} − q_{4}) and u_{0} = fp_{53}(t_{0} + 2^{−127}q_{4}). Note that t_{3} − q_{4} ∈ 2^{96}Z and |t_{3} − q_{4}| ≤ 2^{51}2^{96}. Thus w = t_{3} − q_{4} by Theorem 2.2. Similarly, note that t_{0} + 2^{−127}q_{4} ∈ Z and |t_{0} + 2^{−127}q_{4}| ≤ 2^{50}. Thus u_{0} = t_{0} + 2^{−127}q_{4} by Theorem 2.2. Hence t mod p = w + t_{2} + t_{1} + u_{0}.

Now write y_{0} = topleft_{32,53} u_{0}, u_{1} = fp_{53}(t_{1} + y_{0}), y_{1} = topleft_{64,53} u_{1}, u_{2} = fp_{53}(t_{2} + y_{1}), and y_{2} = topleft_{96,53} u_{2}. Then x_{0} = bottomleft_{32,53} u_{0} = u_{0} mod 2^{32} and y_{0} = 2^{32} ⌊2^{−32}u_{0}⌋ by Theorem 2.5. Apply Theorem 2.2 to see that u_{1} = t_{1} + y_{0} ∈ 2^{32}Z. Hence t mod p = w + t_{2} + u_{1} + x_{0}.

Similarly x_{1} = bottomleft_{64,53} u_{1} = u_{1} mod 2^{64}; y_{1} = 2^{64} ⌊2^{−64}u_{1}⌋; u_{2} = t_{2} + y_{1} ∈ 2^{64}Z; t mod p = w + u_{2} + x_{1} + x_{0}; x_{2} = bottomleft_{96,53} u_{2} = u_{2} mod 2^{96}; y_{2} = 2^{96} ⌊2^{−96}u_{2}⌋; x_{3} = fp_{53}(w+y_{2}) = w+y_{2} ∈ 2^{96}Z; and t mod p = x_{3}+x_{2}+x_{1}+x_{0}. □

Notes. Theorem 4.1 is a special case of the well-known fact that approximate 2bbit division suffices for correctly rounded b-bit division. This is often used in the design of hardware for the operation x, y ↦ fp_{b}(x/y) required by [4].

5. Multiplication modulo 2^{127} − 1

This section explains how to find a representative for the product of two integers modulo 2^{127} − 1.

Define prod(r_{0}, r_{1}, r_{2}, r_{3}, u_{0}, u_{1}, …, u_{7}) = (t_{0}, t_{1}, …, t_{7}) where

(\begin{matrix}t_{0} & t_{1} \\ t_{2} & t_{3} \\ t_{4} & t_{5} \\ t_{6} & t_{7} \end{matrix}) = (\begin{matrix}r_{0} & 2^{−127}r_{3} & 2^{−127}r_{2} & 2^{−127}r_{1} \\ r_{1} & r_{0} & 2^{−127}r_{3} & 2^{−127}r_{2} \\ r_{2} & r_{1} & r_{0} & 2^{−127}r_{3} \\ r_{3} & r_{2} & r_{1} & r_{0} \end{matrix}) (\begin{matrix}u_{0} & u_{1} \\ u_{2} & u_{3} \\ u_{4} & u_{5} \\ u_{6} & u_{7} \end{matrix}) .

Define power_{1}(r_{0}, r_{1}, r_{2}, r_{3}) = (c_{1,0}, …, c_{1,7}) where c_{1,2j} = bottom_{16+32j,53} r_{j} and c_{1,2j+1} = top_{16+32j,53} r_{j}. For i ≥ 1 define recursively power_{i+1}(r_{0}, r_{1}, r_{2}, r_{3}) = squeeze(prod(r_{0}, r_{1}, r_{2}, r_{3}, power_{i}(r_{0}, r_{1}, r_{2}, r_{3}))).

Theorem 5.1. Let r_{0}, r_{1}, r_{2}, r_{3} and u_{0}, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, u_{7} be real numbers with r_{i} ∈ 2^{32i}Z, |r_{i}| ≤ 1.1 · 2^{32}2^{32i}, u_{j} ∈ 2^{16j}Z, and |u_{j}| ≤ 1.01 · 2^{15}2^{16j}. Define (t_{0}, t_{1}, …, t_{7}) = prod(r_{0}, r_{1}, r_{2}, r_{3}, u_{0}, u_{1}, …, u_{7}). Then t_{j} ∈ 2^{16j}Z; |t_{j}| ≤ 2^{50}2^{16j}; and t_{7} + ⋯ + t_{0} ≡ (r_{3} + r_{2} + r_{1} + r_{0})(u_{7} + ⋯ + u_{0}) (mod 2^{127} − 1).

Proof. Observe that

(\begin{matrix}t_{0} & 2^{−16}t_{1} \\ 2^{−32}t_{2} & 2^{−48}t_{3} \\ 2^{−64}t_{4} & 2^{−80}t_{5} \\ 2^{−96}t_{6} & 2^{−112}t_{7} \end{matrix}) = (\begin{matrix}r_{0} & 2^{−95}r_{3} & 2^{−63}r_{2} & 2^{−31}r_{1} \\ 2^{−32}r_{1} & r_{0} & 2^{−95}r_{3} & 2^{−63}r_{2} \\ 2^{−64}r_{2} & 2^{−32}r_{1} & r_{0} & 2^{−95}r_{3} \\ 2^{−96}r_{3} & 2^{−64}r_{2} & 2^{−32}r_{1} & r_{0} \end{matrix}) (\begin{matrix}u_{0} & 2^{−16}u_{1} \\ 2^{−32}u_{2} & 2^{−48}u_{3} \\ 2^{−64}u_{4} & 2^{−80}u_{5} \\ 2^{−96}u_{6} & 2^{−112}u_{7} \end{matrix}) .

A column in the u matrix consists of four integers bounded in absolute value by 1.01 · 2^{15}. A row in the r matrix consists of four integers bounded in absolute value by 1.1 · 2^{32}, 2.2 · 2^{32}, 2.2 · 2^{32}, 2.2 · 2^{32}. Thus each entry in the t matrix is an integer bounded in absolute value by 1.01(1.1 + 2.2 + 2.2 + 2.2)2^{32}2^{15} < 2^{50}.

The difference between (∑ r_{i})(∑ u_{j}) and ∑ t_{j} is 2^{128} − 2 times the integer 2^{−96}r_{3}2^{−32}(u_{2}+u_{3})+2^{−64}(r_{2}+r_{3})2^{−64}(u_{4}+u_{5})+2^{−32}(r_{1}+r_{2}+r_{3})2^{−96}(u_{6}+u_{7}). □

Theorem 5.2. Let r_{0}, r_{1}, r_{2}, r_{3} and u_{0}, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}, u_{6}, u_{7} be real numbers with r_{i} ∈ 2^{32i}Z, |r_{i}| ≤ 1.1 · 2^{32}2^{32i}, u_{j} ∈ 2^{16j}Z, and |u_{j}| ≤ 1.01 · 2^{15}2^{16j}. Define (t_{0}, t_{1}, …, t_{7}) = prod(r_{0}, r_{1}, r_{2}, r_{3}, u_{0}, u_{1}, …, u_{7}). Then

t_{0} = fp(fp(fp(fp(r_{0}u_{0}) + fp(2^{−127}r_{3}u_{2})) + fp(2^{−127}r_{2}u_{4})) + fp(2^{−127}r_{1}u_{6})),
t_{1} = fp(fp(fp(fp(r_{0}u_{1}) + fp(2^{−127}r_{3}u_{3})) + fp(2^{−127}r_{2}u_{5})) + fp(2^{−127}r_{1}u_{7})),
t_{2} = fp(fp(fp(fp(r_{1}u_{0}) + fp(r_{0}u_{2})) + fp(2^{−127}r_{3}u_{4})) + fp(2^{−127}r_{2}u_{6})),
t_{3} = fp(fp(fp(fp(r_{1}u_{1}) + fp(r_{0}u_{3})) + fp(2^{−127}r_{3}u_{5})) + fp(2^{−127}r_{2}u_{7})),
t_{4} = fp(fp(fp(fp(r_{2}u_{0}) + fp(r_{1}u_{2})) + fp(r_{0}u_{4})) + fp(2^{−127}r_{3}u_{6})),
t_{5} = fp(fp(fp(fp(r_{2}u_{1}) + fp(r_{1}u_{3})) + fp(r_{0}u_{5})) + fp(2^{−127}r_{3}u_{7})),
t_{6} = fp(fp(fp(fp(r_{3}u_{0}) + fp(r_{2}u_{2})) + fp(r_{1}u_{4})) + fp(r_{0}u_{6})), and
t_{7} = fp(fp(fp(fp(r_{3}u_{1}) + fp(r_{2}u_{3})) + fp(r_{1}u_{5})) + fp(r_{0}u_{7}))

where fp = fp_{53}.

Thus, in the situation of Theorem 5.1, prod can be computed with a series of floating-point operations. Note that the order of summation here is not relevant: for example, t_{7} = fp(fp(fp(fp(r_{0}u_{7}) + fp(r_{1}u_{5})) + fp(r_{2}u_{3})) + fp(r_{3}u_{1})).

Proof. Apply Theorem 2.2 repeatedly. All the products such as r_{0}u_{0} and partial sums such as r_{0}u_{0} + 2^{−127}r_{3}u_{2} are 53-bit floating-point numbers; the reader may check this directly, or apply Theorem 5.1 after strategically replacing various u’s with 0. □

Theorem 5.3. Let r_{0}, r_{1}, r_{2}, r_{3} be real numbers with r_{j} ∈ 2^{32j}Z and |r_{j}| ≤ 2^{31}2^{32j}. Define (c_{i,0}, c_{i,1}, …, c_{i,7}) = power_{i}(r_{0}, r_{1}, r_{2}, r_{3}). Then c_{i,j} ∈ 2^{16j}Z; |c_{i,j}| ≤ 1.01 · 2^{15}2^{16j}; and (r_{3} + r_{2} + r_{1} + r_{0})^{i} ≡ c_{i,7} + ⋯ + c_{i,0} (mod 2^{127} − 1).

Proof. By Theorem 2.4, r_{j} = c_{1,2j} + c_{1,2j+1}; c_{1,2j+1} ∈ 2^{16+32j}Z; and |c_{1,2j}| ≤ 2^{15+32j}Z. Thus c_{1,2j} = r_{j} − c_{1,2j+1} ∈ 2^{32j}Z; and |c_{1,2j+1}| ≤ 2^{15}2^{16+32j} since |r_{j}| ≤ 2^{31}2^{32j}. Also r_{3} + r_{2} + r_{1} + r_{0} = c_{1,7} + ⋯ + c_{1,0}.

For i ≥ 1, assume inductively that c_{i,j} ∈ 2^{16j}Z; |c_{i,j}| ≤ 1.01 · 2^{15}2^{16j}; and (r_{3} + r_{2} + r_{1} + r_{0})^{i} ≡ c_{i,7} + ⋯ + c_{i,0} (mod 2^{127} − 1).

Write (d_{0}, …, d_{7}) = prod(r_{0}, r_{1}, r_{2}, r_{3}, c_{i,0}, …, c_{i,7}). By Theorem 5.1, d_{j} ∈ 2^{16j}Z; |d_{j}| ≤ 2^{50}2^{16j}; and d_{7} + ⋯ + d_{0} ≡ (r_{3} + r_{2} + r_{1} + r_{0})(c_{i,7} + ⋯ + c_{i,0}).

Now (c_{i+1,0}, …, c_{i+1,7}) = squeeze(d_{0}, …, d_{7}). By Theorem 3.2, c_{i+1,j} ∈ 2^{16j}Z; c_{i+1,7} + ⋯ + c_{i+1,0} ≡ d_{7} + ⋯ + d_{0} ≡ (r_{3} + r_{2} + r_{1} + r_{0})^{i+1}; and |c_{i+1,j}| ≤ 1.01 · 2^{15}2^{16j}. □

Notes. In the language of [20], Theorem 5.1 maps the ring Z/(2^{127} − 1) to the isomorphic ring Z[x]/(x − 2^{16}, 2^{127} − 1), then lifts to Z[x]/(x^{8} − 2), then carries out arithmetic in Z[x]/(x^{8} − 2). Observe that ∑_{j} 2^{−16j}t_{j}x^{j} in Theorem 5.1 is the product of ∑_{j} 2^{−16j}u_{j}x^{j} and ∑_{i} 2^{−32i}r_{i}x^{2i} in Z[x]/(x^{8} − 2). Meanwhile, Theorem 3.2 reduces elements of Z[x]/(x^{8} − 2) modulo x − 2^{16} and 2^{15}x^{7} − 1.

The fact that one can build fast high-precision arithmetic from floating-point arithmetic, using floating-point additions and subtractions to split each floatingpoint number into two small pieces so that subsequent floating-point multiplications are exact, was pointed out by Gerhard W. Veltkamp in 1968—see [1], [2], and [44, exercise 4.2.2–21]—and independently by Dekker in [32]. The main improvement in this paper is that each floating-point number is in a range specified in advance; this eliminates all floating-point comparisons, many additions and subtractions, and some multiplications.

6. Computation of h_{r}

Let m_{0}, m_{1}, …, m_{ℓ−1} be integers with |m_{j}| ≤ 2^{31}. Let r_{0}, r_{1}, r_{2}, r_{3}, k_{0}, k_{1}, k_{2}, k_{3} be real numbers with r_{j} ∈ 2^{32j}Z, |r_{j}| ≤ 2^{31}2^{32j}, k_{j} ∈ 2^{32j}Z, and |k_{j}| ≤ 2^{48}2^{32j}.

Write r = r_{3} + r_{2} + r_{1} + r_{0}, k = k_{3} + k_{2} + k_{1} + k_{0}, and p = 2^{127} − 1. This section explains how to compute (r^{ℓ+1} + m_{0}r^{ℓ} + m_{1}r^{ℓ−1} + ⋯ + m_{ℓ−1}r + k) mod p using floating-point operations.

Precompute (c_{i,0}, …, c_{i,7}) = power_{i}(r_{0}, r_{1}, r_{2}, r_{3}) for 1 ≤ i ≤ 97. Then c_{i,j} ∈ 2^{16j}Z, |c_{i,j}| ≤ 1.01 · 2^{15}2^{16j}, and r^{i} ≡ c_{i,7} + ⋯ + c_{i,0} (mod p) by Theorem 5.3.

Short inputs. For ℓ ≤ 96: Define u_{j} = c_{ℓ+1,j} + m_{0}c_{ℓ,j} + ⋯ + m_{ℓ−1}c_{1,j}. Then u_{j} ∈ 2^{16j}Z; |u_{j}| ≤ 0.98 · 2^{53}2^{16j}; and r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−1}r ≡ u_{7} + ⋯ + u_{0}. Note that u_{j} = fp_{53}(… fp_{53}(c_{ℓ+1,j} + fp_{53}(m_{0}c_{ℓ,j})) + ⋯ + fp_{53}(m_{ℓ−1}c_{1,j})).

Define (v_{0}, …, v_{7}) = squeeze(u_{0}, …, u_{7}). By Theorem 3.2, |v_{j}| ≤ 1.01 · 2^{15}2^{16j}; v_{j} ∈ 2^{16j}Z; and r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−1}r ≡ v_{7} + ⋯ + v_{0}.

Next define w_{j} = v_{2j} + v_{2j+1}. Then w_{j} ∈ 2^{32j}Z; |w_{j}| ≤ 1.02 · 2^{31}2^{32j}; and r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−1}r ≡ w_{3} + w_{2} + w_{1} + w_{0}. Note that w_{j} = fp_{53}(v_{2j} + v_{2j+1}).

Next define t_{j} = k_{j} + w_{j}. Then r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−1}r + k ≡ t_{3} + t_{2} + t_{1} + t_{0}; t_{j} ∈ 2^{32j}Z; and |t_{j}| ≤ 2^{49}2^{32j}. Note that t_{j} = fp_{53}(k_{j} + w_{j}).

Finally define (x_{0}, x_{1}, x_{2}, x_{3}) = freeze(t_{0}, t_{1}, t_{2}, t_{3}). The result is the base-2^{32} representation of (r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−1}r + k) mod p by Theorem 4.2.

Long inputs. For ℓ ≥ 97: Apply the same method recursively to m_{0}, …, m_{ℓ−98} to construct real numbers w′_{0}, w′_{1}, w′_{2}, w′_{3} such that w′_{j} ∈ 2^{32j}Z; |w′_{j}| ≤ 1.02·2^{31}2^{32j}; and r^{ℓ−96} + m_{0}r^{ℓ−97} + ⋯ + m_{ℓ−98}r ≡ w′_{3} + w′_{2} + w′_{1} + w′_{0}.

Define a_{0} = w′_{0} + m_{ℓ−97}, a_{1} = w′_{1}, a_{2} = w′_{2}, and a_{3} = w′_{3}. Then a_{j} ∈ 2^{32j}Z; |a_{j}| ≤ 1.01·2^{32}2^{32j}; and r^{ℓ−96} +m_{0}r^{ℓ−97} +⋯+m_{ℓ−98}r +m_{ℓ−97} ≡ a_{3} +a_{2} +a_{1} +a_{0}. Note that a_{0} = fp_{53}(w′_{0} + m_{ℓ−97}).

Define (b_{0}, …, b_{7}) = prod(a_{0}, a_{1}, a_{2}, a_{3}, c_{97,0}, …, c_{97,7}). By Theorem 5.1, b_{j} ∈ 2^{16j}Z; |b_{j}| ≤ 2^{50}2^{16j}; and r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−98}r^{98} + m_{ℓ−97}r^{97} ≡ b_{7} + ⋯ + b_{0}.

Define u_{j} = b_{j} + m_{ℓ−96}c_{96,j} + ⋯ + m_{ℓ−1}c_{1,j}. Then u_{j} ∈ 2^{16j}Z; |u_{j}| ≤ 2^{50}2^{16j} + 96 · 1.01 · 2^{31}2^{15}2^{16j} ≤ 0.98 · 2^{53}2^{16j}; and r^{ℓ+1} + m_{0}r^{ℓ} + ⋯ + m_{ℓ−1}r ≡ u_{7} + ⋯ + u_{0}. Note that u_{j} = fp_{53}(… fp_{53}(b_{j} + fp_{53}(m_{ℓ−96}c_{96,j})) + ⋯ + fp_{53}(m_{ℓ−1}c_{1,j})).

Now construct (v_{0}, …, v_{7}) = squeeze(u_{0}, …, u_{7}), w_{j} = v_{2j} +v_{2j+1}, t_{j} = k_{j} +w_{j}, and (x_{0}, x_{1}, x_{2}, x_{3}) = freeze(t_{0}, t_{1}, t_{2}, t_{3}) as above.

Efficiency. The time spent on this computation has four major pieces:

• Time to multiply input vectors by the precomputed c_{i,j} matrix. This is the heart of the computation.

• Time to multiply by r^{97} after every 97 input components. One can save time here, at the expense of a larger matrix, by instead multiplying by (e.g.) r^{970} after every 970 input components.

• Time to squeeze the intermediate results after every 97 input components. One can save some time here by more carefully analyzing the actual size of ∑_{i} m_{ℓ−i}c_{i,j}. For example, ∑_{1≤i≤150} |c_{i,j}| is below 100 · 2^{15}2^{16j} for most choices of r_{0}, r_{1}, r_{2}, r_{3}.

• Time to squeeze and freeze the final result. This is negligible for long inputs.

In practice, for long inputs, the matrix-vector products account for most of the total time.

Beware that there are several easy ways to drastically slow down floating-point operations. The most obvious is failure to keep necessary data in registers. Less obvious is failure to parallelize independent operations. Implementors must not assume that the “optimizers” in typical compilers will avoid these hazards. For example, straightforward C code to compute h_{r} (with the improvement described in the next section), compiled for a Pentium by a widespread C compiler, is five times slower than the speed reported in Section 1.

7. The 64-bit variant

This section outlines a 64-bit variant of the algorithm described in Section 6. In this variant, one represents an integer modulo 2^{127} − 1 as a sum t_{4} + t_{3} + t_{2} + t_{1} + t_{0} where t_{j} is a 64-bit floating-point number with t_{j} ∈ 2^{26j}Z. This variant is useful on computers such as the Pentium and Pentium II, where five 64-bit floating-point operations are faster than eight 53-bit floating-point operations.

The analogue of Theorem 3.2 starts from a sum t_{4} + t_{3} + t_{2} + t_{1} + t_{0} with |t_{j}| ≤ 0.98 · 2^{64}2^{26j}. It uses six carries to produce a sum v_{4} + v_{3} + v_{2} + v_{1} + v_{0} with |v_{j}| ≤ 1.01 · 2^{25}2^{26j}.

The analogue of Theorem 5.1 starts from one sum r_{4} + r_{3} + r_{2} + r_{1} + r_{0} with |r_{i}| ≤ 1.1 · 2^{32}2^{26i} and another sum u_{4} + u_{3} + u_{2} + u_{1} + u_{0} with |u_{j}| ≤ 1.01 · 2^{25}2^{26j}. It produces a sum t_{4} + t_{3} + t_{2} + t_{1} + t_{0} with |t_{j}| ≤ 29 · 2^{56}2^{26j}.

The result of the precomputation is a matrix of real numbers c_{i,j} with |c_{i,j}| ≤ 1.01 · 2^{25}2^{26j} and r^{i} ≡ c_{i,4} + ⋯ + c_{i,0} (mod 2^{127} − 1). In the main computation, 29·2^{56}2^{26j} +96·1.01·2^{31}2^{25}2^{26j} fits comfortably below 2^{64}2^{26j}. (In fact, it is below 2^{63}2^{26j}, so 63-bit floating-point arithmetic suffices.) The final reduction converts from radix 2^{26} to radix 2^{32} and then applies Theorem 4.2 with 53 changed to 64.

Notes. On many computers one can conveniently simulate 63-bit floating-point arithmetic using “64-bit integer arithmetic” or “32-bit integer arithmetic.” Some tinkertoy computers do not have any built-in hardware for fast multiplication; on these computers it helps to create small multiplication tables. Implementors should be careful to avoid variable-time multiplication hardware and software (including, as an extreme, out-of-cache table lookups indexed by secret data) in cryptographic applications where timing information may be available to an attacker.

8. Guaranteeing the integrity of one message

In this section, p is the prime number 2^{127} − 1; I is the set of integers in the interval [−2^{127} − 2^{95} − 2^{63} − 2^{31}, 2^{127} − 2^{95} − 2^{63} − 2^{31} − 1]; L is a fixed nonnegative integer; and a message is a sequence of length between 0 and L inclusive, consisting of integers in [−2^{31}, 2^{31} − 1].

Here is a protocol for authenticated transmission of a single message m through an untrusted channel. The sender and the receiver share a secret uniform random pair (r, k) in I × I. The sender computes an authenticator s = (k + h_{r}(m)) mod p and sends (m, s). At this point an attacker can feed arbitrary pairs (m′, s′) to the receiver. The receiver accepts (m′, s′) if s′ = (k + h_{r}(m′)) mod p.

Generating r and k. Let ρ_{0}, ρ_{1}, ρ_{2}, ρ_{3} be independent uniform random integers in [−2^{31}, 2^{31} − 1]. Write r = r_{3} + r_{2} + r_{1} + r_{0} where r_{j} = 2^{32j}ρ_{j}. Then r is a uniform random element of I. Note that r_{0}, r_{1}, r_{2}, r_{3} meet the hypotheses of Section 6. Similar comments apply to k.

Encoding byte strings. There are several standard ways to encode a sequence of 4ℓ integers b_{0}, b_{1}, …, b_{4ℓ−1} in [0, 255] as a sequence of ℓ integers m_{0}, m_{1}, …, m_{ℓ−1} in [−2^{31}, 2^{31} − 1]. For example, little-endian twos-complement defines

m_{j} = ((b_{4j} + 2^{8}b_{4j+1} + 2^{16}b_{4j+2} + 2^{24}b_{4j+3} + 2^{31}) mod 2^{32}) − 2^{31}.

One can encode an arbitrary-length sequence of integers in [0, 255] as a sequence of length 4ℓ for some ℓ by appending either 1 or 1, 0 or 1, 0, 0 or 1, 0, 0, 0.

Security. The rest of this section analyzes the attacker’s chance of deceiving the receiver. Theorem 8.2 shows that any possible forgery (m′, s′) with m′ ≠ m has negligible chance of being accepted by the receiver.

Theorem 8.1. Let m and m′ be distinct messages. Let δ be an integer. Then at most 2L + 4 integers r in I satisfy h_{r}(m) ≡ h_{r}(m′) + δ (mod p).

Proof. Say m = (m_{0}, m_{1}, …, m_{ℓ−1}) and m′ = (m′_{0}, m′_{1}, …, m′_{ℓ′−1}).

Define polynomials g, g′ ∈ Z[t] by g = t^{ℓ+1} + m_{0}t^{ℓ} + m_{1}t^{ℓ−1} + ⋯ + m_{ℓ−1}t and g′ = t^{ℓ′+1} + m′_{0}t^{ℓ′} + m′_{1}t^{ℓ′−1} + ⋯ + m′_{ℓ′−1}t + δ. Note that the polynomial g − g′ is not divisible by p. Otherwise ℓ = ℓ′, and each m_{i} − m′_{i} is divisible by p, so m_{i} = m′_{i} since |m_{i} − m′_{i}| < 2^{32} < p, so m = m′, contradiction.

If h_{r}(m)−h_{r}(m′)−δ is divisible by p then g(r)−g′(r) is divisible by p. Now p is prime, and g −g′ has degree at most L+1, so g −g′ has at most L+1 roots modulo p. Hence there are at most L + 1 choices for r in {V, …, V + p − 1}, and L + 1 choices for r in {V + p, …, V + 2p − 1}, and 2 choices for r in {V + 2p, V + 2p + 1}, where V = −2^{127} − 2^{95} − 2^{63} − 2^{31}; in short, at most 2L + 4 choices for r in {V, …, V + 2p + 1} = I. □

Theorem 8.2. Let m and m′ be distinct messages. Let s and s′ be integers in [0, p − 1]. Let r and k be independent uniform random elements of I. Then

Pr[s = (k + h_{r}(m)) mod p and s′ = (k + h_{r}(m′)) mod p] ≤ 3(L + 2)/2^{255}

and Pr[s = (k + h_{r}(m)) mod p] ≥ 1/2^{127}.

Thus the conditional probability that s′ = (k + h_{r}(m′)) mod p, given that s = (k + h_{r}(m)) mod p, is at most 3(L + 2)/2^{128}. It doesn’t matter how much time the attacker spends staring at (m, s); any choice of (m′, s′) with m′ ≠ m has chance at most 3(L + 2)/2^{128} of being accepted by the receiver. (See Theorem 9.1 for a slightly better bound that takes account of the distribution of s.)

Proof. For each of the 2^{128} choices of r, there are at least two choices of k satisfying s = (k + h_{r}(m)) mod p. Thus Pr[s = (k + h_{r}(m)) mod p] ≥ 2^{129}/2^{256}.

If s ≡ k + h_{r}(m) (mod p) and s′ ≡ k + h_{r}(m′) then h_{r}(m) ≡ h_{r}(m′) + s − s′. By Theorem 8.1, this happens for at most 2L + 4 choices of r; and, for each of those choices of r, there are at most three choices of k satisfying s ≡ k + h_{r}(m). Thus Pr[s ≡ k + h_{r}(m) and s′ ≡ k + h_{r}(m′)] ≤ 3(2L + 4)/2^{256}. □

Notes. When L is around (say) 2^{30}, the forgery probability in Theorem 8.2 is around 1/2^{96}. Carter and Wegman in [28, page 149] observed that one can compress the authenticator from 127 bits down to 96 bits with only a small increase in the forgery probability. For example, one can use π((k + h_{r}(m)u) mod (2^{127} − 1)) as an authenticator, where u is another uniform random element of I, and π is some public function from 127-bit strings to 96-bit strings. This may be useful in applications where every bit of storage is sacred. Beware that the simpler formula π((k + h_{r}(m)) mod (2^{127} − 1)) is not safe; it increases the forgery probability by another factor of 2^{31}, at least for some choices of π.

Some writers claim that forgery probabilities around 1/2^{32} are adequate for most applications. The attacker’s cost of 2^{32} forgery attempts, they say, is much larger than the attacker’s benefit from forging a single message. Unfortunately, even if all attackers acted on the basis of rational economic analyses, this argument would be wrong, because it wildly underestimates the attacker’s benefit. In a typical authentication system, as soon as the attacker is lucky enough to succeed at a few forgeries, he can immediately figure out enough secret information to let him forge messages of his choice. (This does not contradict the information-theoretic security expressed by Theorem 8.2; the attacker is gaining information from the receiver, not from the sender.) It is crucial for the forgery probability to be so small that attackers have no hope.

9. Guaranteeing the integrity of many messages

This section explains several protocols for authenticated transmission of at most N messages through an untrusted channel. Here N can be arbitrarily large. Each protocol uses the same hash function h_{r}; the protocols differ in how they hide h_{r}(m) from the attacker.

Notation and terminology. As in Section 8, p is the prime number 2^{127} −1; I is the set of integers in the interval [−2^{127} − 2^{95} − 2^{63} − 2^{31}, 2^{127} − 2^{95} − 2^{63} − 2^{31} − 1]; L is a fixed nonnegative integer; and a message is a sequence of length between 0 and L inclusive, consisting of integers in [−2^{31}, 2^{31} − 1]. Also C, D, N are fixed positive integers with C ≤ N.

A chosen-message attack is a (probabilistic) algorithm that makes C message queries to an oracle, and that then prints D triples (n′, m′, s′), where each m′ is a message different from any of the oracle queries. For any function g, the attack succeeds for g if, given an oracle that responds to the nth query m with g(n, m), the attack prints at least one (n′, m′, s′) such that s′ = g(n′, m′).

The reader is assumed to be comfortable with the concept of a random function, i.e., a random variable whose values are functions. For the definition of “random” see, e.g., [18, Appendix]. Note that random variables are not necessarily uniformly distributed.

Protocol 1: one-time pad. In this protocol, the sender and receiver share two independent secrets: a uniform random integer r in I, and a uniform random function f from {1, 2, …, N} to I. Given the nth message m, the sender computes an authenticator s = (f(n) + h_{r}(m)) mod p, and sends (n, m, s). The receiver accepts (n′, m′, s′) if s′ = (f(n′) + h_{r}(m′)) mod p.

Theorem 9.1. Let A be a chosen-message attack. Let f be a uniform random function from {1, 2, …, N} to I. Let r be a uniform random element of I. If r and f are independent then A succeeds for (n, m) ↦ (f(n) + h_{r}(m)) mod p with probability at most (C + D(L + 2))/2^{127}.

Proof. Let m_{1}, …, m_{C} be messages, and let s_{1}, …, s_{C} be integers in [0, p − 1]. Let X be the event that A’s oracle queries are m_{1}, …, m_{C} in that order; the oracle’s responses are s_{1}, …, s_{C} respectively; and f(1), …, f(C) ∈ [V, V + 2p − 1] where V = −2^{127} − 2^{95} − 2^{63} − 2^{31}.

Observe that the conditional distribution of r, given X, is uniform. Indeed, for each possible r, there are exactly two choices of f(n) in [V, V + 2p − 1] satisfying s_{n} = (f(n) + h_{r}(m_{n})) mod p.

For any (n′, m′, s′) with m′ ∉ {m_{1}, m_{2}, …, m_{C}}, the conditional probability that s′ = (f(n′) + h_{r}(m′)) mod p, given X, is at most (L + 2)/2^{127}. Indeed, if n′ ∈ {1, 2, …, C} then h_{r}(m_{n′})−s_{n′} ≡ h_{r}(m′)−s′ (mod p) with conditional probability at most (L + 2)/2^{127} by Theorem 8.1, since the conditional distribution of r is uniform. If n′ ∉ {1, 2, …, C} then s′ = (f(n′) + h_{r}(m′)) mod p with conditional probability at most 3/2^{128} < (L + 2)/2^{127}, since the conditional distribution of f(n′) is uniform.

Thus A succeeds with conditional probability at most D(L + 2)/2^{127} given X. Now sum over all m_{1}, …, m_{C}, s_{1}, …, s_{C}: A succeeds with conditional probability at most D(L + 2)/2^{127} given that all of f(1), f(2), …, f(C) are in [V, V + 2p − 1]. Finally, there is probability at most 2C/2^{128} that at least one of f(1), f(2), …, f(C) is in {V + 2p, V + 2p + 1}. □

Protocol 2: scrambling. In this protocol, the sender and receiver share two independent secrets: a uniform random integer r in I, and a uniform random function f from {0, 1, …, p − 1} to {0, 1, …, 2^{128} − 1}. Given a message m, the sender computes an authenticator s = f(h_{r}(m)), and sends (m, s). The receiver accepts (m′, s′) if s′ = f(h_{r}(m′)).

Theorem 9.2. Let A be a chosen-message attack. Let f be a uniform random function from {0, 1, …, p − 1} to {0, 1, …, 2^{128} − 1}. Let r be a uniform random element of I. If r and f are independent then A succeeds for (n, m) ↦ f(h_{r}(m)) with probability at most (\binom{C}{2} + CD)(L + 2)/2^{127} + D/2^{128}.

Proof. Let Q = (m_{1}, m_{2}, …, m_{n}, m′_{1}, m′_{2}, …, m′_{D}) be a sequence of messages with n ≤ C, with m_{1}, m_{2}, …, m_{n} all different from each other, and with m_{1}, m_{2}, …, m_{n} different from m′_{1}, m′_{2}, …, m′_{D}. Let R = (s_{1}, s_{2}, …, s_{n}, s′_{1}, s′_{2}, …, s′_{D}) be a sequence of integers in [0, 2^{128} − 1].

Let X_{Q,R} be the event that s_{i} = f(h_{r}(m_{i})) for all i and s′_{j} ≠ f(h_{r}(m′_{j})) for all j. By Theorem 8.1, the chance that h_{r}(m_{1}), …, h_{r}(m_{n}) are different from each other and different from h_{r}(m′_{1}), …, h_{r}(m′_{D}) is at least 1−(\binom{n}{2}+nD)(L+2)/2^{127} ≥ 1−ϵ where ϵ = (\binom{C}{2} + CD)(L + 2)/2^{127}. In that case f(h_{r}(m_{1})), …, f(h_{r}(m_{n})) are independent of each other and independent of f(h_{r}(m′_{1})), …, f(h_{r}(m′_{D})). Hence Pr[X_{Q,R}] ≥ (1 − ϵ)(1 − D/2^{128})/2^{128n}.

Let Y_{Q,R} be the event that

• A’s distinct oracle queries are m_{1}, m_{2}, …, m_{n} in that order: the first oracle query is m_{1}, the first oracle query different from m_{1} is m_{2}, etc., and there are no oracle queries other than m_{1}, m_{2}, …, m_{n};

• the oracle responses to m_{1}, m_{2}, …, m_{n} are s_{1}, s_{2}, …, s_{n} respectively;

• the messages printed by A are m′_{1}, m′_{2}, …, m′_{D} in that order, with forged authenticators s′_{1}, s′_{2}, …, s′_{D} respectively; and

• A does not succeed: s′_{1} ≠ f(h_{r}(m′_{1})), s′_{2} ≠ f(h_{r}(m′_{2})), etc. Observe that the conditional probability of Y_{Q,R} given X_{Q,R} is some quantity α_{Q,R} predetermined by A: it is the chance that A decides to use query m_{1}, to use query m_{2} after query m_{1} and response s_{1}, to use query m_{3} after queries m_{1}, m_{2} and responses s_{1}, s_{2}, etc., and finally to stop after m_{1}, s_{1}, …, m_{n}, s_{n} and print m′_{1}, s′_{1}, . . .. Hence Pr[Y_{Q,R}] ≥ (1 − ϵ)(1 − D/2^{128})α_{Q,R}/2^{128n}.

If A were used with a uniform random oracle then the query-response-print sequence would be m_{1}, s_{1}, m_{2}, s_{2}, …, m_{n}, s_{n}, m′_{1}, s′_{1}, … with probability exactly α_{Q,R}/2^{128n}. Thus ∑_{n,Q,R} α_{Q,R}/2^{128n} = 1. Hence the chance that A does not succeed is ∑ Pr[Y_{Q,R}] ≥ (1−ϵ)(1−D/2^{128}) ∑ α_{Q,R}/2^{128n} = (1−ϵ)(1−D/2^{128}). □

Protocol 3: one-time scrambling. In this protocol, the sender and receiver share two independent secrets: a uniform random integer r in I, and a uniform random function f from {1, 2, …, N} × {0, …, p − 1} to {0, …, 2^{128} − 1}. Given the nth message m, the sender computes an authenticator s = f(n, h_{r}(m)), and sends (n, m, s). The receiver accepts (n′, m′, s′) if s′ = f(n′, h_{r}(m′)).

Theorem 9.3. Let A be a chosen-message attack. Let f be a uniform random function from {1, 2, …, N} × {0, 1, …, p − 1} to {0, 1, …, 2^{128} − 1}. Let r be a uniform random element of I. If r and f are independent then A succeeds for (n, m) ↦ f(n, h_{r}(m)) with probability at most D(2L + 5)/2^{128}.

Proof. Say the oracle queries are m_{1}, m_{2}, …, m_{C}. For each possible r, the pairs (1, h_{r}(m_{1})), (2, h_{r}(m_{2})), …, (C, h_{r}(m_{C})) are all different, so the oracle responses f(1, h_{r}(m_{1})), f(2, h_{r}(m_{2})), …, f(C, h_{r}(m_{C})) are independent and uniform. Thus the conditional distribution of r, given the oracle responses, is uniform.

Now consider any (n′, m′, s′) with m′ ∉ {m_{1}, …, m_{C}}. If n′ ∈ {1, 2, …, C} then, by Theorem 8.1, h_{r}(m′) = h_{r}(m_{n′}) with conditional probability at most (2L + 4)/2^{128}. If that does not happen then f(n′, h_{r}(m′)) is independent of the oracle responses, and thus has chance 1/2^{128} of equalling s′. The overall chance of success for (n′, m′, s′) is at most (2L + 4)/2^{128} + 1/2^{128}. □

Random numbers instead of counters. In Theorem 9.1 it is crucial that the sender never reuse a message number. In some applications it is more convenient to use a uniform random element of {1, 2, …, N} than to use a counter; then N must be chosen large enough that the chance of message-number repetition is negligible.

Similar comments apply to Theorem 9.3. On the other hand, f(n, h_{r}(m)) is much more tolerant of message-number repetition than (f(n) + h_{r}(m)) mod p. Even if the same number n is used again and again, the security of f(n, h_{r}(m)) is no worse than the security of f(h_{r}(m)) shown in Theorem 9.2.

Unpredictable random functions. The construction (f(n)+h_{r}(m)) mod p uses a shared secret containing 128 + 128N bits of entropy; the construction f(h_{r}(m)) uses 128+128p = 2^{134} bits; the construction f(n, h_{r}(m)) uses 128+128pN ≈ 2^{134}N bits. None of these protocols can be used in practice, except (f(n) + h_{r}(m)) mod p for small N. Fortunately, it seems that uniform random functions can be safely simulated by random functions of much lower entropy.

Consider, for example, the block cipher Rijndael. If k is a 128-bit string then Rijndael_{k} is a function from S to S, where S = {0, 1, …, 2^{128} − 1}. If k is a uniform random 128-bit string then Rijndael_{k} is a good simulation of a uniform random function from S to S; it seems very difficult for an attacker to tell the difference. More precisely: It seems that, for every practical algorithm A that uses an oracle and prints either 0 or 1, there is negligible difference between the average output of A using Rijndael_{k} as an oracle and the average output of A using a uniform random function as an oracle. In short, Rijndael_{k} seems to be unpredictable.

Consequently it seems safe to use, e.g., Rijndael_{k}(h_{r}(m)) as an authenticator of m, where k is a uniform random 128-bit string, r is a uniform random element of I, and r and k are independent. If Rijndael_{k} is, in fact, unpredictable, then there is no practical attack on this system that achieves significantly better success than the bound in Theorem 9.2.

Similar comments apply to (f(n) + h_{r}(m)) mod p and f(n, h_{r}(m)), where n is a unique message number as above. One variant of f(n, h_{r}(m)) is the authenticator Rijndael_{k}(Rijndael_{k}(n) xor h_{r}(m)); note that if f is unpredictable then (x, y) ↦ f(f(x) xor y) is unpredictable.

There are many other published examples of random functions that can be used instead of Rijndael_{k}. For example, it is convenient to use MD5(k, n, h_{r}(m)) as an authenticator, where k is a uniform random 256-bit string, and both n and h_{r}(m) are encoded as 128-bit strings. If the random function x ↦ MD5(k, x) on 256-bit inputs is unpredictable then there is no practical attack on this system achieving significantly better success than the bound in Theorem 9.3. Similar comments apply to the first 128 bits of the output of SHA-1.

Notes. Wegman and Carter in [66, Section 4] proposed the form f(n) + h(m) for an authenticator and observed that the forgery probability is proportional to the number of forgery attempts. The bound in Theorem 9.1 has an extra C/2^{127} term to account for the slight nonuniformity of f(n) mod p.

The idea of simulating a uniform random function with an unpredictable random function is now considered obvious. In the context of f(n) + h(m) it is usually credited to Brassard in [27]. See [18, Section 2] for further historical notes on the concept of unpredictability.

Bellare, Canetti, and Krawczyk in [13, Section 1.5] proposed the form f(h(m)) for an authenticator. They pointed out that, in fact, m ↦ f(h(m)) is unpredictable. For precise bounds on the level of predictability, see, e.g., [18]; my proof of Theorem 9.2 is based on my proof of [18, Theorem 3.1]. For precise bounds on the forgery probability given unpredictability, see, e.g., [17, Section 6]. This detour through unpredictability leads to a bound similar to Theorem 9.2 but involving \binom{C+D}{2} instead of \binom{C}{2} + CD.

For systems of the form f(n, h(m)), see, e.g., [13, Section 5] and [37, Section 2.3]. Shoup in [58, Section 2] analyzed the exact security of several other variants of the Wegman-Carter construction.

The unpredictability of (x, y) ↦ f(f(x) xor y) if f is uniform (and hence if f is unpredictable) was proven by Bellare, Kilian, and Rogaway in [17, Section 3]. For a simpler proof see [18, Theorem 3.1].

Rijndael was published by Daemen and Rijmen in [31]. MD5 was published by Rivest in [51]. SHA-1 was published in [3]. The apparent unpredictability of random functions such as x ↦ MD5(k, x), for fixed-length x, was pointed out in [15] but had already been used in other cryptographic constructions based on MD5.

There are many other examples in the literature of easily computable, lowentropy random functions that seem to be difficult to predict. Unfortunately, most of the examples were designed under constraints such as invertibility or collision resistance; these constraints distract attention from, and often interfere with, the crucial property of unpredictability. One exception is the Naor-Reingold system in [48], based directly on a difficult number-theoretic problem; unfortunately, this system is too slow for many applications. Another exception is SEAL 3.0, published by Coppersmith and Rogaway in [56]; unfortunately, SEAL’s 32-bit input size is too small for most applications.

10. Random hash functions with low collision probability

The crucial property of h_{r}, for random r, is that it has low collision probability: if m ≠ m′ then Pr[h_{r}(m) = h_{r}(m′)] is small. See Theorem 8.1.

The construction of h_{r} can be generalized as follows. Select a ring. Select a “large” subset of the ring as the set of messages, and a “small” subset of the ring as the set of hash outputs. Each hash function is determined by an ideal (typically a maximal ideal) of the ring; the hash function takes a message m to an output congruent to m modulo the ideal. Examples:

• Messages are elements of Z. The hash of a message m is m mod p where p is a uniform (or nearly uniform) random prime number in [2^{120}, 2^{128}].

• Messages are elements of the polynomial ring (Z/2)[t]. The hash of a message m is m mod p where p is a uniform random irreducible degree-128 polynomial.

• Messages are elements of F [t] where F is a field of size around 2^{32}. The hash of a message m is m mod p where p is a uniform random monic irreducible degree-4 polynomial.

• Messages are elements of F [t] where F is a field of size around 2^{128}. The hash of a message m is m mod (t−r) where r is a uniform random element of F; in short, m(r). For example, the hash of t^{ℓ}+m_{0}t^{ℓ−1}+m_{1}t^{ℓ−2}+⋯+m_{ℓ−1} is r^{ℓ} + m_{0}r^{ℓ−1} + m_{1}r^{ℓ−2} + ⋯ + m_{ℓ−1}.

• Messages are elements of the multivariate polynomial ring F [t_{0}, t_{1}, …] over a field F of size around 2^{128}. The hash of m is m mod (t_{0} − r_{0}, t_{1} − r_{1}, …) where r_{0}, r_{1}, … are independent uniform random elements of F. For example, the hash of the homogeneous linear polynomial m_{0}t_{0} + m_{1}t_{1} + ⋯ + m_{ℓ−1}t_{ℓ−1} + t_{ℓ} is m_{0}r_{0} + m_{1}r_{1} + ⋯ + m_{ℓ−1}r_{ℓ−1} + r_{ℓ}. As another example, the hash of the multilinear polynomial m_{0} + m_{1}t_{0} + m_{2}t_{1} + m_{3}t_{0}t_{1} + ⋯ + m_{2^{ℓ}−1}t_{0}t_{1} … t_{ℓ−1} is m_{0} + m_{1}r_{0} + m_{2}r_{1} + m_{3}r_{0}r_{1} + ⋯ + m_{2^{ℓ}−1}r_{0}r_{1} … r_{ℓ−1}.

Each of these random functions can be used in place of h_{r} in the constructions f(h_{r}(m)) and f(n, h_{r}(m)) discussed in the previous section. Each function, under a small restriction on the set of messages, can also be used in a construction analogous to (f(n) + h_{r}(m)) mod (2^{127} − 1).

How to choose a ring. The hash h_{r} featured in this paper computes a polynomial modulo t − r in the ring (Z/(2^{127} − 1))[t]. I selected this ring for two reasons:

• Today’s computers support much faster multiplication in rings of large (or zero) characteristic, such as Z or (Z/(2^{31}−1))[t] or (Z/(2^{127}−1))[t], than in rings of characteristic 2, such as (Z/2)[t] or F_{2^{32}}[t] or F_{2^{128}}[t]. It is just as easy to build hardware for (Z/2)[t] as for Z, but there is much less market demand.

• It is easy to generate a degree-1 monic polynomial over a large field. It takes much more code (and a noticeable amount of time) to generate a higherdegree monic irreducible polynomial over a smaller field, or to generate a prime in Z. Karp and Rabin in [41] suggested allowing non-primes to save time, but that hurts the collision probability.

Higher-dimensional rings such as (Z/(2^{127} −1))[t_{0}, t_{1}] are as fast as (Z/(2^{127} −1))[t] but need more bits to specify a hash function. (They also offer a sublinear collision probability for long messages. However, this is generally not helpful for message authentication; sensible attackers will generate many short messages instead.)

Historical notes. Gilbert, MacWilliams, and Sloane in [36, Section 9] observed that a uniform random F -linear function (m_{0}, …, m_{ℓ−1}) ↦ m_{0}r_{0} + ⋯ + m_{ℓ−1}r_{ℓ−1} from F^{ℓ} to F has collision probability 1/#F. Some implementation results for F = Z/(2^{32} + 15), with a few changes in the function for the sake of simpler code, were published by Halevi and Krawczyk in [37]. Black, Halevi, Krawczyk, Krovetz, and Rogaway in [24] reported further implementation results, using Winograd’s dot-product algorithm in [68] to trade half the multiplications for additions.

Wegman and Carter in [66, Section 3] pointed out that a random hash function of entropy much smaller than L suffices for authentication of messages of length L. The hash m_{0} + m_{1}r_{0} + m_{2}r_{1} + m_{3}r_{0}r_{1} + ⋯ + m_{2^{ℓ}−1}r_{0}r_{1} … r_{ℓ−1} is Stinson’s improvement in [61, Section 6] of the Wegman-Carter construction.

Karp and Rabin in [41, Section 3], independently of Wegman and Carter, pointed out the low collision probability of large primes in Z. Rabin in [50] (which was written after [41]) made the analogous observation for (Z/2)[t]. Krawczyk in [47] later popularized (Z/2)[t] as “cryptographic CRCs” and “LFSR-based hashing”; implementation results for this “division hash” were published by Shoup in [58] and by Nevelsteen and Preneel in [49]. Krawczyk also proposed an “LFSR-based Toeplitz matrix” construction, which amounts to m ↦ ⌊(mv mod p)t^{128}/p⌋; here v is a nonzero polynomial of degree below 128.

The low collision probability of degree-1 irreducible polynomials in F [t], when F is a large field, was pointed out by den Boer in [25], independently by Taylor in [63, Section 3], and independently by Bierbrauer, Johansson, Kabatianskii, and Smeets in [22, Section 4]. (Taylor considered only prime fields F, and suggested several good possibilities, including Z/(2^{127} − 1). Beware that the distribution of polynomials in [63] was extremely far from uniform.) Some implementation results for this “evaluation hash,” with F of characteristic 2, were published by Shoup in [58]; by Afanassiev, Gehrmann, and Smeets in [9], reinventing a division algorithm published by Kaminski in [40]; and by Nevelsteen and Preneel in [49]. I published fast code for h_{r} in April 1999.

Shoup in [58] suggested the “generalized division hash”—irreducible polynomials of any degree over fields of any size—as a common generalization of the “division hash” and the “evaluation hash.” Shoup published some implementation results for a field of size 2^{8}.

Many of these articles follow the terminology of [28] and [66]: a random function f from A to B is “universal” if Pr[f(m) = f(m′)] ≤ 1/#B for all pairs of distinct inputs (m, m′). This is not a useful concept; one wants Pr[f(m) = f(m′)] to be small, and one wants #B to be small, but there is no reason to demand that the product be bounded by 1. Some authors say “f is ϵ-almost universal” to mean that the collision probability of f is at most ϵ.

Generalizations and variants. Let g be a random function on length-ℓ inputs with collision probability at most ϵ. Then (m_{1}, …, m_{k}) ↦ (g(m_{1}), …, g(m_{k})) is a random function on length-kℓ inputs with collision probability at most ϵ. If the output g(m_{1}), …, g(m_{k}) is too long then one can apply another hash function to it. This is the general idea of the Wegman-Carter construction in [66, Section 3]. If g is (Z/2)-linear then one can apply it to 32 inputs in parallel using the 32-bit exclusive-or operation in today’s computers; see, e.g., [54], [38], and [49].

Let g_{1}, g_{2}, …, g_{k} be independent random functions from length-ℓ inputs to some commutative group. If Pr[g_{j}(m) − g_{j}(m′) = δ] ≤ ϵ for all δ, j, m, m′ with m ≠ m′, then (m_{1}, m_{2}, …, m_{k}) ↦ g_{1}(m_{1})+g_{2}(m_{2})+⋯+g_{k}(m_{k}) has collision probability at most ϵ. This was pointed out by Zobrist in [69] for the special case of (j, m) ↦ g_{j}(m) being uniform; by Gilbert, MacWilliams, and Sloane in [36], as noted above, for the special case of each g_{i} being a uniform random linear function over a field; and finally by Carter and Wegman in [28, Proposition 8] for the general case. The “XOR hash” published many years later in [15] is the same as Zobrist’s hash, but with “unpredictable” in place of “uniform.”

Let g_{1}, g_{2}, …, g_{k} be independent random functions, each with collision probability at most ϵ. Then m ↦ (g_{1}(m), g_{2}(m), …, g_{k}(m)) has collision probability at most ϵ^{k}. For example, consider messages in F^{ℓ} where F = Z/2. A uniform random F -linear function from F^{ℓ} to F has collision probability 1/2 as noted above, so a uniform random F -linear function from F^{ℓ} to F^{k}—i.e., multiplication by a uniform random matrix—has collision probability (1/2)^{k}. This was pointed out by Carter and Wegman in [28, page 151]. Rogaway in [54] pointed out that multiplication by a random sparse matrix still has low collision probability if the output is large enough.

Alternate input encodings. Carter and Wegman in [28, page 151] suggested encoding a string of kℓ bits as a string of 2^{k}ℓ bits, exactly ℓ of which are 1’s.

Karp and Rabin in [41, Section 6] suggested encoding a string of bits b_{1}, …, b_{ℓ} as the matrix product M(b_{1}) … M(b_{ℓ}) in the ring of 2 × 2 matrices over Z, where M(0) = ( \begin{matrix}1 & 0 \\ 1 & 1 \end{matrix} ) and M(1) = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ); and then reducing the product modulo a big prime p. An improvement is the product (1 1)M(b_{1}) … M(b_{ℓ}) in Z^{2}; the simplest method of computing the image of this product in (Z/p)^{2} takes one addition modulo p for each bit of input.

Conjectural constructions and current practice. If p is a uniform random 512-bit string then m ↦ MD5(p, m) appears to have very low collision probability, as pointed out by Bellare et al. in [15] and in [13]. But there is no proof. Wang in [64] recently found collisions in m ↦ MD5(m); perhaps the techniques of [64] can be extended to find high-probability collisions in m ↦ MD5(p, m).

Authenticators based on MD5 are popular because they are very fast. The implementations of MD5 in [8] (including the careful Pentium implementation by Bosselaers in [26]) take about 5.3 Pentium cycles per byte, or about 5.9 Pentium-II cycles per byte, or about 9.4 UltraSPARC-I cycles per byte, for long messages. But h_{r} is even faster!

References

[1] —, Algolprocedures voor het berekenen van een inwendig product in dubbele precisie, RC-Informatie nr. 22, Technische Hogeschool Eindhoven (1968).

[2] —, ALGOL procedures voor het rekenen in dubbele lengte, RC-Informatie nr. 21, Technische Hogeschool Eindhoven (1969).

[3] —, Secure hash standard, Federal Information Processing Standard 180-1, National Institute of Standards and Technology, Washington, 1995.

[4] —, IEEE standard for binary floating-point arithmetic, Standard 754–1985, Institute of Electrical and Electronics Engineers, New York, 1985.

[5] —, 20th annual symposium on foundations of computer science, IEEE Computer Society, New York, 1979. MR 82a:68004.

[6] —, 37th annual symposium on foundations of computer science, Institute of Electrical and Electronics Engineers, New York, 1996. ISBN 0–8186–7594–2.

[7] —, 38th annual symposium on foundations of computer science, IEEE Computer Society Press, Los Alamitos, 1997. ISBN 0–8186–8197–7.

 [8] —, OpenSSL 0.9.3, available from http://www.openssl.org (1999).

[9] Valentine Afanassiev, Christian Gehrmann, Ben Smeets, Fast message authentication using efficient polynomial evaluation, in [23] (1997), 190–204. URL: http://cr.yp.to/bib/

    entries.html#1997/afanassiev.

[10] Ross Anderson (editor), Fast software encryption, Lecture Notes in Computer Science, 809, Springer-Verlag, Berlin, 1994. ISBN 3–540–58108–1. MR 97b:94004.

[11] Algirdas A. Avizienis, Signed-digit number representations for fast parallel arithmetic, IRE Transactions on Electronic Computers 10 (1961), 389–400. ISSN 0367–9950. MR 24:B1263.

URL: http://cr.yp.to/bib/entries.html#1961/avizienis.

[12] Mihir Bellare, Ran Canetti, Hugo Krawczyk, Pseudorandom functions revisited: the cascade construction and its concrete security, in [6] (1996), 514–523; see also newer version [13].

[13] Mihir Bellare, Ran Canetti, Hugo Krawczyk, Pseudorandom functions revisited: the cascade construction and its concrete security (1996); see also older version [12]. URL: http://

www-cse.ucsd.edu/~mihir/papers/cascade.html.

[14] Mihir Bellare, Roch Guérin, Phillip Rogaway, XOR MACs: new methods for message authentication using finite pseudorandom functions, in [30] (1995), 15–28; see also newer version [15].

[15] Mihir Bellare, Roch Guérin, Phillip Rogaway, XOR MACs: new methods for message authentication using finite pseudorandom functions (1995); see also older version [14]. URL:

http://www-cse.ucsd.edu/~mihir/papers/xormacs.html.

[16] Mihir Bellare, Joe Kilian, Phillip Rogaway, The security of cipher block chaining, in [33] (1994), 341–358; see also newer version [17].

[17] Mihir Bellare, Joe Kilian, Phillip Rogaway, The security of the cipher block chaining message authentication code, Journal of Computer and System Sciences 61 (2000), 362–399; see also

older version [16]. ISSN 0022–0000. URL: http://www-cse.ucsd.edu/~mihir/papers/cbc.
html.

[18] Daniel J. Bernstein, How to stretch random functions: the security of protected counter sums, Journal of Cryptology 12 (1999), 185–192. ISSN 0933–2790. URL: http://cr.yp.to/

papers.html.

[19] Daniel J. Bernstein, Guaranteed message authentication faster than MD5 (abstract) (1999).

URL: http://cr.yp.to/papers.html#hash127-abs.

[20] Daniel J. Bernstein, Multidigit multiplication for mathematicians. URL: http://cr.yp.to/

papers.html.

[21] Daniel J. Bernstein, A secure public-key signature system with extremely fast verification, accepted by Journal of Cryptology, but withdrawn to be incorporated into author’s High-

speed cryptography book. URL: http://cr.yp.to/papers.html#sigs.

[22] Jürgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii, Ben Smeets, On families of hash functions via geometric codes and concatenation, in [62] (1994), 331–342. URL: http://

cr.yp.to/bib/entries.html#1994/bierbrauer.

[23] Eli Biham (editor), Fast Software Encryption ’97, Lecture Notes in Computer Science, 1267, Springer-Verlag, Berlin, 1997. ISBN 3–540–63247–6.

[24] John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz, Phillip Rogaway, UMAC: fast and secure message authentication, in [67] (1999), 216–233. URL: http://www.cs.ucdavis.edu/

~rogaway/umac/.

[25] Bert den Boer, A simple and key-economical unconditional authentication scheme, Journal of Computer Security 2 (1993), 65–71. ISSN 0926–227X. URL: http://cr.yp.to/bib/entries.

html#1993/denboer.

[26] Antoon Bosselaers, Even faster hashing on the Pentium (1997). URL: http://www.esat.

kuleuven.ac.be/~bosselae/publications.html.

[27] Gilles Brassard, On computationally secure authentication tags requiring short secret shared

keys, in [29] (1983), 79–86. URL: http://cr.yp.to/bib/entries.html#1983/brassard.

[28] J. Lawrence Carter, Mark N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences 18 (1979), 143–154. ISSN 0022–0000. URL: http://cr.yp.to/

bib/entries.html#1979/carter.

[29] David Chaum, Ronald L. Rivest, Alan T. Sherman (editors), Advances in cryptology: proceedings of Crypto 82, Plenum Press, New York, 1983. ISBN 0–306–41366–3. MR 84j:94004.

[30] Don Coppersmith (editor), Advances in cryptology—CRYPTO ’95, Lecture Notes in Computer Science, 963, Springer-Verlag, Berlin, 1995. ISBN 3–540–60221–6.

[31] Joan Daemen, Vincent Rijmen, The design of Rijndael: AES—the advanced encryption standard, Springer-Verlag, 2002. ISBN 3–540–42580–2. MR 1986943.

[32] Theodorus J. Dekker, A floating-point technique for extending the available precision, Numerische Mathematik 18 (1971), 224–242. ISSN 0029–599X. MR 45:8056. URL: http://

cr.yp.to/bib/entries.html#1971/dekker.

[33] Yvo Desmedt (editor), Advances in cryptology—CRYPTO ’94, Lecture Notes in Computer Science, 839, Springer-Verlag, Berlin, 1994.

[34] Joan Feigenbaum (editor), Advances in cryptology—CRYPTO ’91, Lecture Notes in Computer Science, 576, Springer-Verlag, Berlin, 1992. ISBN 3–540–55188–3.

[35] Walter Fumy (editor), Advances in cryptology: EUROCRYPT ’97, Lecture Notes in Computer Science, 1233, Springer-Verlag, Berlin, 1997. ISBN 3–540–62975–0.

[36] Edgar N. Gilbert, F. Jessie MacWilliams, Neil J. A. Sloane, Codes which detect deception, Bell System Technical Journal 53 (1974), 405–424. ISSN 0005–8580. MR 55:5306. URL: http://

cr.yp.to/bib/entries.html#1974/gilbert.

[37] Shai Halevi, Hugo Krawczyk, MMH: software message authentication in the Gbit/second

rates, in [23] (1997), 172–189. URL: http://www.research.ibm.com/people/s/shaih/pubs/
mmh.html.

[38] Thomas Johansson, Bucket hashing with a small key size, in [35] (1997), 149–162. URL:

http://cr.yp.to/bib/entries.html#1997/johansson.

[39] William M. Kahan, Further remarks on reducing truncation errors, Communications of the ACM 8 (1965), 40. ISSN 0001–0782.

[40] Michael Kaminski, A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor, Journal of the ACM 34 (1987), 968–984. ISSN 0004–5411. MR 89f:68033.

[41] Richard M. Karp, Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development 31 (1987), 249–260. ISSN 0018–8646. URL: http://

cr.yp.to/bib/entries.html#1987/karp.

[42] Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 1st edition, 1st printing, Addison-Wesley, Reading, 1969; see also newer version [43]. MR 44:3531.

[43] Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 1st edition, 2nd printing, Addison-Wesley, Reading, 1971; see also older version [42]; see also newer version [44]. MR 44:3531.

[44] Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 2nd edition, Addison-Wesley, Reading, 1981; see also older version [43]; see also newer version [45]. ISBN 0–201–03822–6. MR 83i:68003.

[45] Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 3rd edition, Addison-Wesley, Reading, 1997; see also older version [44]. ISBN 0–201–89684–2.

[46] Neal Koblitz (editor), Advances in cryptology—CRYPTO ’96, Lecture Notes in Computer Science, 1109, Springer-Verlag, Berlin, 1996.

[47] Hugo Krawczyk, LFSR-based hashing and authentication, in [33] (1994), 129–139. URL:

http://cr.yp.to/bib/entries.html#1994/krawczyk.

[48] Moni Naor, Omer Reingold, Number-theoretic constructions of efficient pseudo-random func-

tions, in [7] (1997), 458–467. URL: http://www.wisdom.weizmann.ac.il/~naor/onpub.html.

[49] Wim Nevelsteen, Bart Preneel, Software performance of universal hash functions, in [59] (1999), 24–41.

[50] Michael O. Rabin, Fingerprinting by random polynomials, Harvard Aiken Computational

Laboratory TR-15-81 (1981). URL: http://cr.yp.to/bib/entries.html#1981/rabin.

[51] Ronald L. Rivest, The MD5 message-digest algorithm, Request For Comments 1321 (1992).

URL: http://theory.lcs.mit.edu/~rivest/rfc1321.txt.

[52] James E. Robertson, A new class of digital division methods, IRE Transactions on Electronic Computers 7 (1958), 218–222. ISSN 0367–9950. URL: http://cr.yp.to/bib/entries.html#

1958/robertson.

[53] Phillip Rogaway, Bucket hashing and its application to fast message authentication, in [30] (1995), 29–42; see also newer version [54].

[54] Phillip Rogaway, Bucket hashing and its application to fast message authentication, Journal of Cryptology 12 (1999), 91–115; see also older version [53]. ISSN 0933–2790. URL: http://

www.cs.ucdavis.edu/~rogaway/papers/.

[55] Phillip Rogaway, Don Coppersmith, A software-optimized encryption algorithm, in [10] (1994), 56–63; see also newer version [56].

[56] Phillip Rogaway, Don Coppersmith, A software-optimized encryption algorithm, Journal of Cryptology 11 (1998), 273–287; see also older version [55]. ISSN 0933–2790. URL: http://

www.cs.ucdavis.edu/~rogaway/papers/.

[57] Victor Shoup, On fast and provably secure message authentication based on universal hashing, in [46] (1996), 313–328; see also newer version [58].

[58] Victor Shoup, On fast and provably secure message authentication based on universal hashing (1996); see also older version [57]. URL: http://www.shoup.net/papers.

[59] Jacques Stern (editor), Advances in cryptology: EUROCRYPT ’99, Lecture Notes in Computer Science, 1592, Springer-Verlag, Berlin, 1999. ISBN 3–540–65889–0. MR 2000i:94001.

[60] Douglas R. Stinson, Universal hashing and authentication codes, in [34] (1992), 74–85; see also newer version [61].

[61] Douglas R. Stinson, Universal hashing and authentication codes, Designs, Codes and Cryptography 4 (1994), 369–380; see also older version [60]. ISSN 0925–1022. URL: http://

cr.yp.to/bib/entries.html#1994/stinson-mac.

[62] Douglas R. Stinson (editor), Advances in cryptology—CRYPTO ’93: 13th annual international cryptology conference, Santa Barbara, California, USA, August 22–26, 1993, proceedings, Lecture Notes in Computer Science, 773, Springer-Verlag, Berlin, 1994. ISBN 3–540– 57766–1, 0–387–57766–1. MR 95b:94002.

[63] Richard Taylor, An integrity check value algorithm for stream ciphers, in [62] (1994), 40–48.

URL: http://cr.yp.to/bib/entries.html#1994/taylor.

[64] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu, Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD (2004). URL: http://eprint.iacr.org/2004/199/.

[65] Mark N. Wegman, J. Lawrence Carter, New classes and applications of hash functions, in [5] (1979), 175–182; see also newer version [66]. URL: http://cr.yp.to/bib/entries.html#

1979/wegman.

[66] Mark N. Wegman, J. Lawrence Carter, New hash functions and their use in authentication and set equality, Journal of Computer and System Sciences 22 (1981), 265–279; see also older version [65]. ISSN 0022–0000. MR 82i:68017. URL: http://cr.yp.to/bib/entries.

html#1981/wegman.

[67] Michael Wiener (editor), Advances in cryptology—CRYPTO ’99, Lecture Notes in Computer Science, 1666, Springer-Verlag, Berlin, 1999. ISBN 3–5540–66347–9. MR 2000h:94003.

[68] Shmuel Winograd, A new algorithm for inner product, IEEE Transactions on Computers 17 (1968), 693–694. ISSN 0018–9340.

[69] Albert L. Zobrist, A hashing method with applications for game playing, Technical Report 88, Computer Sciences Department, University of Wisconsin (1970). URL: http://cr.yp.to/

bib/entries.html#1970/zobrist.

Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045

E-mail address: djb@cr.yp.to