How does Gilbert, MacWilliams, and Sloane's solution to “perfect integrity” work?

Question

Gilbert, MacWilliams, and Sloane defined a solution to "perfect integrity" in Codes Which Detect Deception, unconditionally secure message authentication, not vulnerable to any cryptanalysis on its own even by an adversary with unbounded computational power, provided you have a key chosen uniformly at random the same length as the message. It sounds counter-intuitive that a MAC could have perfect integrity, any hash function can be broken with enough computational power. How does their solution have "perfect integrity"?

Answer 1

Let $r, s$ be uniform random nonnegative integers below $2^{130} - 5$, shared by Alice and Bob but kept secret from the adversary Mallory. If Alice wants to send a single message $m \in \{0,1\}$ to Bob (this is a yes-or-no message—only two possible messages, with no secrecy of the message, the simplest scenario imaginable), she can compute the authenticator or authentication tag or MAC $$t = (r \cdot m + s) \bmod (2^{130} - 5)$$ along with $m$. Suppose Mallory intercepts $(m, t)$, and wants to find $(m', t')$ for $m' \ne m$—that is, Mallory wants to find another message/authenticator pair whose message is any message other than $m$, in order to fool Bob. Bob will accept the forgery $(m', t'$) only if $$t' = (r \cdot m' + s) \bmod (2^{130} - 5).$$ No matter what the real message $m$ and the real authenticator $t$ are, and no matter what forgery $m'$ and $t'$ Mallory attempts, and no matter how much computation Mallory can do, the probability that Mallory's forgery attempt succeeds—i.e., the probability that Bob accepts Mallory's forgery—is at most $1/(2^{130} - 5)$. Why?

Consider Mallory's perspective: they don't know the real key; they only know a real message $m$ and its real authenticator $t$. For any particular message $m$ and authenticator $t$, there are $2^{130} - 5$ different pairs of values $(r, s)$ satisfying $t = (r \cdot m + s) \bmod (2^{130} - 5)$: for each possible $r$ there is exactly one $s$ satisfying the equation, namely $s = (t - r \cdot m) \bmod (2^{130} - 5)$. But only one of those $(r, s)$ pairs also satisfies $t' = (r \cdot m' + s) \bmod (2^{130} - 5)$ for any $m' \ne m$ and $t'$ (see below for more formal proof).

So—no matter what computation Mallory does!—given only $m$, $t$, and the knowledge that $t = (r \cdot m + s) \bmod (2^{130} - 5)$, Mallory can't narrow the candidate keys $(r, s)$ down to fewer than $2^{130} - 5$ possibilities, all with the same probability $1/(2^{130} - 5)$. And since Mallory doesn't know which of the $2^{130} - 5$ values of $(r, s)$ Alice and Bob are actually using, Mallory has no hope of finding any $m'$ and $t'$ that will fool Bob, by satisfying $t' = r \cdot m' + s$, with probability higher than $1/(2^{130} - 5)$.

And this bound on forgery probability is the best you can hope for when there are $2^{130} - 5$ distinct authenticators on any given message: for any attempted forgery, the adversary could guess what the right authenticator is uniformly at random with probability $1/(2^{130} - 5)$. In general, as long as there are only $n$ times as many possible authenticated messages as there are messages, whether the authenticator is tacked onto the end or the message is otherwise transformed to authenticate it, the best bound on forgery probability you can hope for is $1/n$.

I don't recommend the term ‘perfect integrity’, which is value-laden and ripe for confusion, but attaining this bound is the most reasonable interpretation of the term, and the theorem that the GMS authenticator attains this bound is unconditional in a specific technical sense.

---

We can write this a little more formally in the language of fields. Since $p = 2^{130} - 5$ is a prime number, the integers modulo $p$ form a field, sometimes called $\mathbb Z/p\mathbb Z$ or $\mathbb F_p$. If we understand the arithmetic to be done modulo $p$, we can write these equations in the event of a forgery a little more simply as

\begin{align*} t &= r m + s, \tag{$*$} \\ t' &= r m' + s. \tag{$**$} \end{align*}

Mallory knows $m$ and $t$, and assumes the equation $(*)$ is true—i.e., that Alice is computing the authenticator correctly. Mallory succeeds at forgery in the event that the equation $(**)$ is also true, given that $(*)$ is true—that is, Mallory's forgery probability is the conditional probability

\begin{equation*} \Pr[\text{forgery} \mid \text{message/authenticator}] = \Pr[t' = r m' + s \mid t = r m + s]. \end{equation*}

We can rearrange this a little bit to eliminate the independent random variable $s$ by observing that $s = t - r m$, so we're interested in the probability that $t' = r m' + t - r m$, or equivalently $r = \frac{t' - t}{m' - m}$, since $m' \ne m$ and we're working in a field in which we can divide by any nonzero element. In other words,

\begin{equation*} \Pr[t' = r m' + s \mid t = r m + s] = \Pr[r = {\textstyle\frac{t' - t}{m' - m}}]. \end{equation*}

Since $r$ was a random variable with uniform distribution among $2^{130} - 5$ possibilities, and $m$, $m'$, $t$, and $t'$ were arbitrary (i.e., there's a for all quantifier here—the reasoning works for all values of $m$, $m'$, $t$, and $t'$, except when $m = m'$), we can conclude, irrespective of Mallory's computational powers,

\begin{equation*} \Pr[\text{forgery} \mid \text{message/authenticator}] = \Pr[r = {\textstyle\frac{t' - t}{m' - m}}] = 1/(2^{130} - 5). \end{equation*}

This bound on forgery probability applies even if Mallory gets to choose the original message $m$ in an attempt to make the task of forging the authenticator for a different $m'$ even easier.

---

This one-time authenticator is the basis for one of the most popular message authentication codes on the planet, Poly1305, widely used in the authenticated cipher ChaCha/Poly1305 by TLS and in the related authenticated cipher crypto_secretbox_xsalsa20poly1305. I left out many practical details:

• extending it to longer messages by interpreting the 128-bit chunks of a message $m$ as a polynomial $m_1 x^\ell + m_2 x^{\ell - 1} + \dotsb + m_\ell x$ over $\mathbb F_{2^{130} - 5}$ and evaluating it at the point $r$;
• restricting the space of the evaluation points $r \in \mathbb F_{2^{130} - 5}$ for efficient software implementation; and
• extending it to many messages by deriving $r$ and $s$ pseudorandomly with ChaCha or XSalsa20 for each message.

With these practical details sorted out, the forgery probability is still no more than $8\ell/2^{106}$ where $\ell$ is the number of 128-bit blocks in a message, plus whatever advantage the adversary can get by attacking the pseudorandom key derivation.

---

This might look very different from the Gilbert–MacWilliams–Sloane paper (paywall-free). But actually, it is precisely (an instance of) the scheme described by Gilbert, MacWilliams, and Sloane, just without the language of projective space from algebraic geometry.

The geometric picture of the GMS scheme is that:

• a $\text{message}$ is a line (drawn in solid black) through the origin that hits the equator (drawn in grey at $z = 0$),
• a $\color{blue}{\text{key}}$ is a line (dashed blue) through the origin that doesn't hit the equator, and
• an $\color{red}{\text{authenticated message}}$ is a line (dotted red) through the origin perpendicular to both message and key.

For any fixed message, every corresponding authenticated message under any key passes through the great circle perpendicular to that message (solid black)—but to know which line through that great circle requires knowledge of the key. For any fixed key, every authenticated message under that key passes through the great circle perpendicular to that key (dashed blue)—but knowing one line through that great circle doesn't help to find any other line through that great circle for a forgery because there are many great circles that the authenticated message passes through and any one of them could correspond to the true key.

How do we compute this, though? We won't actually work in real projective space; we'll work in the projective plane of a finite field, which is a little trickier to draw but easier to compute with, from algebraic geometry.

Fix a prime power $q$ and consider the finite field $k = \operatorname{GF}(q)$ of $q$ elements. The projective plane $\mathbb P^2(k)$ over $k$ is (by one of several equivalent constructions) the set of lines in $k^3$ through the origin, with each line typically represented by any nonzero point on that line—the projective coordinates $(x : y : z)$ represent the same line as $(\lambda x : \lambda y : \lambda z)$ for any nonzero $\lambda \in k$, as long as $x, y, z \in k$ are not all zero. (This rules out ‘$(0 : 0 : 0)$’ as a point on the projective plane.) There are $q^2 + q + 1$ points on the projective plane, which can be counted in various different ways—for example, $q^2$ points of the form $(x : y : 1)$, $q$ points of the form $(x : 1 : 0)$, and the remaining point $(1 : 0 : 0)$.

In the GMS one-time authenticator, a message is a point $(1 : s : 0)$ on the ‘equator’ for some $s \in k$, and a key is a point $(i : j : 1)$ off the ‘equator’ for some $i, j \in k$ chosen uniformly at random. An authenticated message is a line in the projective plane through the message and the key—equivalently, the set of all lines in $k^3$ through the origin that intersect the great circle on the unit sphere between the points where the message and key intersect the unit sphere (the dotted red circle in the diagram above).

Now, as the set of all lines in $k^3$ through a particular great circle on the unit sphere, a ‘line’ in projective space $\mathbb P^2(k)$ corresponds to a plane in the enclosing space $k^3$, so we can characterize it by a normal vector $L \in k^3$ to that plane: that is, the plane representing a projective line is the space of all vectors $v \in k^3$ perpendicular to $L$ so that $L \cdot v = 0$. Any such normal vector $L = (x, y, z)$ is perpendicular to both $(1, s, 0)$ and $(i, j, 1)$, so it must solve the linear system

\begin{align*} 0 &= L \cdot (1, s, 0) = x + y s, \tag{$\dagger$} \\ 0 &= L \cdot (i, j, 1) = x i + y j + z. \tag{$\ddagger$} \end{align*}

Note, of course, that if $(x, y, z)$ is a solution then so is $(\lambda x, \lambda y, \lambda z)$ for any nonzero $\lambda \in k$. Hence we can also view an authenticated message as a projective point which is ‘perpendicular’ to both $(1 : s : 0)$ and $(i : j : 1)$; such a point is given by $(-s : 1 : c)$ where $$s i - j = c,$$ which is Eq. $(17)$ of the paper. (Eq. $(\dagger)$ implies $x = -y s$, and Eq. $(\ddagger)$ implies $z = y s i - y j$; dividing the coordinates by $y$ gives the form $$(x : y : z) = (x/y : y/y : z/y) = (-s : 1 : c)$$ for $c = z/y = s i - j$.)

Of course, rather than drawing out doodles of lines and planes on a napkin, we can represent a message by the element $s \in \operatorname{GF}(q)$ alone, a key by a pair of elements $i, j \in \operatorname{GF}(q)$, and an authenticator by an element $c \in \operatorname{GF}(q)$, and then encode those in bit strings to transmit on a conventional medium like ethernet. And if you pick $q = 2^{130} - 5$, you wind up with exactly the scheme this post started with. The correspondence with the GMS notation is:

\begin{equation*} \begin{array}{r|c|c} \text{role} & \text{this post} & \text{GMS} \\ \hline \text{prime power modulus} & 2^{130} - 5 & q \\ \text{message} & m & s \\ \text{key} & (r, s) & (i, -j) \\ \text{authentication tag} & t & c \\ \text{authentication equation} & t = rm + s & si - j = c \end{array} \end{equation*}

---

Appendix: Asymptote code for the diagram

import three;

size(10cm, 0);

triple msg = (1, 4, 0);         // (1 : s : 0)
triple key = (1/2, 1/5, 1);     // (i : j : 1)
real tag = ypart(msg)*xpart(key) - ypart(key);
triple authmsg =                // (-s : 1 : si - j)
  (-ypart(msg), 1, tag);

void
drawaxis(triple A, string text, align align)
{
  Label L = Label(text, position=EndPoint, align=align);
  draw(O--1.5A, arrow=Arrow3(TeXHead2), L=L);
}

drawaxis(X, "$x$", align=W);
drawaxis(Y, "$y$", align=E);
drawaxis(Z, "$z$", align=N);

draw(circle(c=O, r=1, normal=Z), p=gray(0.5));

draw(1.5 unit(msg) -- 1.5 unit(-msg), arrow=Arrows3, p=black,
  L=Label("\noindent msg:\\$(1 : s : 0)$", position=BeginPoint, align=SE));
dot(unit(msg), p=black);
dot(unit(-msg), p=black);

draw(1.5 unit(key) -- 1.5 unit(-key), arrow=Arrows3, p=blue + dashed,
  L=Label("\noindent key:\\$(i : j : 1)$", position=BeginPoint, align=NW));
dot(unit(key), p=blue);
dot(unit(-key), p=blue);

draw(1.5 unit(authmsg) -- 1.5 unit(-authmsg), arrow=Arrows3, p=red + dotted,
  L=Label("\noindent auth msg:\\$(-s : 1 : c)$", position=EndPoint, align=S));
dot(unit(authmsg), p=red);
dot(unit(-authmsg), p=red);

draw(circle(c=O, r=1, normal=msg), p=black);
draw(circle(c=O, r=1, normal=key), p=blue + dashed);
draw(circle(c=O, r=1, normal=authmsg), p=red + dotted);
draw(
  0.2 unit(key) -- 0.2 (unit(key) + unit(-authmsg))
    -- 0.2 unit(-authmsg),
  p=gray(0.5));
draw(
  0.2 unit(msg) -- 0.2 (unit(msg) + unit(-authmsg))
    -- 0.2 unit(-authmsg),
  p=gray(0.5));

draw(unitsphere,
     surfacepen=material(white + opacity(0.5), ambientpen=white));