The acronym stands for *message authentication code*.
A (deterministic) message authentication code is a
function of two strings.
The first we'll call the *key* and the second we'll call the
*message*.
The value *Tag*= MAC(*K*,*M*)
is a string of some fixed length (e.g., 64 bits).
A MAC is usually used like this.
A sender and a receiver share a key *K*.
When the sender wants to send a message *M* to the receiver,
he sends along with *M* the string
*Tag*=MAC(*K*,*M*).
When the receiver receives a message *M** and
its tag *Tag**, the receiver
computes the "expected" tag
*Tag***=MAC(*K*,*M**) for *M**.
If the expected tag is identical to the received tag
then the receiver
assumes that the received message *M** really did originate with
the sender.
If the tags are different then the receiver regards the message *M**
as a forgery. In that case the receiver may want
to ignore the message, or close down
the connection, or take some other action.

The basic CBC MAC is usually "embellished" a bit.
**First**, the domain is extended to arbitrary bits strings,
usually by padding with a 1-bit and then the minimal
number of 0-bits to reach a multiple of 128 bits.
**Second**, a particular security problem is fixed.
The basic CBC MAC works correctly when all the
strings you want to MAC have one fixed length
(this is a well-known result of
[Bellare, Kilian, and Rogaway])) but
it does *not* work correctly
when message lengths may vary.
(For example, given the MAC (under some unknown key) of ZERO,
do you see how to forge the string ZERO||ZERO?)
To fix this problem extra processing is often done to
*C*[*m*] (as it was defined above), such
as enciphering it under a separate key.
**Third**, many standards allow you to take a prefix
of the full *n*-bit MAC (where *n* is the block length).
The three changes above represent one way to fix up the basic CBC MAC.
A more recent suggestion due to
[Black, Rogaway]
more efficiently deals with padding and length-variability.

We didn't want to gain parallel efficiency at the cost of serial efficiency, and PMAC is about as efficient as the CBC MAC in serial environments. In making a modern MAC, we were also careful to fix the limitations of the basic CBC MAC, giving a construction that works correctly across arbitrary bit strings.

PMAC was designed largely in response to NIST's modes-of-operation activities. In particular, we thought it would be nice to provide NIST with a parallelizable MAC that looked reasonably conventional. In particular, one route towards making a parallelizable MAC is the "Carter-Wegman approach" (which you can read about in the paper on UMAC, for example). But good MACs from the Carter-Wegman approach can be complicated to spec or implement well, and they don't look like conventional modes at all.

I did (Phil Rogaway). But I worked with John Black, and the academic paper on PMAC will authored by the two of us.

- PMAC is actually more than a MAC: its a
*pseudorandom function*. Roughly said, this means that if*K*is random and unknown to the adversary,*f*(*x*)=PMAC(*K*,*x*) will look like a random function. - PMAC is fully parallelizable, as we've explained.
- PMAC works on any bit string. In particular, you don't need to think about padding or issues of length-variability; it's been taken care of for you.
- PMAC works with any block cipher.
- PMAC provides a tag with as many bits as you want,
up to the block length
*n*of the underlying block cipher. - PMAC makes an optimal number of block-cipher calls for a conventional mode of operation, namely, roundup(|M|/n). (Actually, the formula is wrong for the empty string, which takes one block cipher call.)
- PMAC is deterministic: it uses no counter/IV/nonce and no random bits. This has been true in all traditional MACs.
- PMAC uses only a single block-cipher key, and every invocation of the block cipher is keyed by that one key.
- PMAC only use the forward direction of the underlying block cipher.
- PMAC key setup is very cheap: one block-cipher call and, if desired, a few XORs and conditional (128-bit) shifts.
- PMAC generates a sequence of offsets, which it does in a very cheap way. Each offset is computed from the previous one either by xoring the previous offset by a value looked up in a small table or by doing a few shifts and xors.
- PMAC is nearly endian-neutral: the scheme can be implemented just as fast on a big-endian machine or on a little-endian machine.
- PMAC doesn't need much memory to run (and a memory-minimal implementation doesn't give up much speed).
- PMAC avoids 128-bit addition (which is endian-biased and can be expensive in software or dedicated hardware). It uses xors instead.
- PMAC is incremental, in the sense of [Bellare, Goldreich, and Goldwasser], with respect to several common operations.
- PMAC is simple to understand and implement. It uses GF(2^128) arithmetic and a Gray code, but it all comes down to some xors and shifts. One doesn't have to understand the mathematics to implement the scheme.
- PMAC is provably secure. It provably meets its goals, as long as the underlying block cipher meet a standard cryptographic assumption.

Let *M* be the message you want to MAC, and let
*K* be the PMAC key, which is just an AES key.
Let *L* be AES(*K*, ZERO). Let
*L*(0) be *L* and, for *i*>0, let *L*(*i*) be *L*<<1 if
the first bit of *L*(*i*-1) is 0, and let *L*(*i*) be
(*L*(*i*-1)<<1) **xor** 0x00000000000000000000000000000087
otherwise. Let *L*(-1) be *L*>>1 if the last bit of *L* is
0, and let *L*(-1) be *L*>>1 **xor**
0x80000000000000000000000000000043 otherwise. Break the message *M* into
*m*≥1
blocks *M*[1]*M*[2]...*M*[*m*] where each block except the
last one has 128 bits. The last one may have fewer than 128 bits. Now we MAC
as follows.

functionpmac (K,M)beginOffset = ZERO Σ = ZEROfori= 1tom-1do beginOffset = OffsetxorL(ntz(i)) Σ = ΣxorAES(K, OffsetxorM[i])endΣ = Σxorpad(M[m])if|M[m]|=nthenΣ = ΣxorL(-1) FullTag = AES(K, Σ)returna prefix of FullTag (of the desired length)end

Here is a patent-assurance letter I wrote for the IEEE.

Back to the PMAC homepage.