# Presentation: 500760

## PMAC: A ParallelizableMessage Authentication Code 

**Phillip Rogaway**
- Department of Computer Science
- UC Davis + CMU
- rogaway@cs.ucdavis.edu
- http://www.cs.ucdavis.edu/~rogaway
- +66 1 530 7620   +1 530 753 0987

- NIST Modes of Operation Workshop 2 – Aug 24, 2001 - Santa Barbara, California

**John Black**
- Department of Computer Science
- University of Nevada, Reno
- jrb@cs.unr.edu
- http://www.cs.unr.edu/~jrb

## What is a MAC

- A

**B**

- M  .  ****

- K

- K

**MAC****G**:  generate
- authentication tag
**** = MAC**K **( [IV], M)

**MAC****V**:  verify
- authentication tag:
- MAC**K **(M, ****)

**G**

**V**

-  Security addresses an adversary’s **inability** to forge a **valid** authentication tag
-   for some **new** message.
-  Most MACs are **deterministic–**they need no nonce/state/IV/$.
-   In practice, such MACs are preferable.  Deterministic MACs are usually PRFs.

## CBC MAC

- Inherently sequential

## PMAC’s Goals

-   A fully parallelizable alternative to the CBC MAC
-   But without paying much for parallelizability in terms of
-     serial efficiency
-   While we’re at it, fix up other “problems” of the CBC MAC
- 	- Make sure PMAC applies to any bit string
-  	- Make sure it is correct across messages of different lengths

## What is PMAC ?

-  A **variable-input-length pseudorandom function** (VIL PRF):
-         PMAC: {0,1}k {0,1}*   {0,1}n
-  That you make from
-    a **fixed-input-length pseudorandom function** (FIL PRF) –
-    invariably a block cipher such as E=AES:
-         E: {0,1}k   {0,1}n  {0,1}n

- E

- P

- C

- n

- n

- K

- PMAC

**M**

- Tag

- *

- n

- K

## PMAC’s Properties

-  Functionality: **VIL PRF**:  {0,1}* {0,1}n
-        Can’t distinguish PMACK () from a random function **R**()
-  Customary use of a VIL PRF:
-        A (stateless, deterministic) **Message Authentication Code** (MAC)
-  PRFs make the most pleasant MACs because they are deterministic
-    and stateless.
-  Few block-cipher calls**:  ******|M| / n** ******to PMAC message M
-  Low session-setup cost: about **one block-cipher call**
** ****Fully parallelizable**
* *No n-bit addition or mod p operations – just xors and shifts
-  Uses a **single block-cipher key**
-  **Provably secure**: If E is a secure block cipher
-                               then PMAC-E is a good PRF

## PMAC

**PMAC**

-  K   z [-1]
-            z [1]  z [2]  z [3]  **...**
-  as implicit on next slide

## Definition of PMAC [E, t]

**a****lgorithm**  PMAC K ( M )
- L(0)   = EK (**0**)
- L(-1) = lsb(L(0))?  (L(0) >> 1)   Const43  :  (L(0) >>1)
**for** i = 1, 2, ... **do** L(i)  = msb(L(i-1))?  (L(i-1) << 1)   Const87 : (L(i-1) <<1)
- Partition M into M[1] ... M[m]            // each 128 bits,  except M[m] may be shorter
- Offset = **0**
**for** i=1 **to** m-1 **do **
**        **Offset = Offset  L(ntz(i))**	****	**
-         **  = **    EK (M[i]    Offset)
**   = **     pad (M[m])
**if**  |M[m]| = n **then**  **  = **   L(-1)
- FullTag = EK ( **  )
- Tag = first t bits of  FullTag
**return** Tag

## Related Work

-  [Bellare, Guerin, Rogaway 95]** **–** **the** **XOR MAC.
-            Not a PRF, but introduced central element of the construction
* *[Bernstein 99] – A PRF-variant of the XOR MAC
-  [Gligor, Donescu 00, 01] – Another descendent of the XOR MAC.
***          ***Introduced the idea of combining message blocks with a
-           sequence of offsets as an alternative to encoding.  Not a PRF
*** ***[Black, Rogaway 00] – Tricks for optimal handing of arbitrary
-           input lengths (XCBC method you have just seen)
-  [Carter-Wegman 79, 81] – A completely different approach that can
-           achieve the same basic goals.
-  Tree MAC (a la Merkle) – Another approach, not fully parallelizable.

## Speed

- Data courtesy of **Ted Krovetz**

-  PMAC-AES              	 **18.4** cpb
-  CBCMAC-AES       	 **17.1** cpb

- 8 % slower

- The CBC MAC is in its “raw” form.  Code is  Pentium 3 assembly under gcc.
- This CBC MAC figure is **inferior** to Lipmaa’s **OCB** results, indicating that
- PMAC and OCB add so little overhead that quality-of-code differences contribute
- more to measured timing differences than algorithmic differences across
- CBC – CBCMAC – PMAC – OCB.
- Since Lipmaa obtained **15.5** cpb for the CBC MAC,
- adding 8% to this,         **16.7** cpb,
- is a conservative estimate for well-optimized Pentium code.

## Provable Security

-  Provable security begins with [Goldwasser, Micali 82]
-  Despite the name, one doesn’t really *prove* security
-  Instead, one gives *reductions*: theorems of the form
-       **If** a certain primitive is secure
-       **then** the scheme based on it is secure
-   For us:
-       **If** AES is a secure block cipher
-       **then** PMAC-AES is a secure authenticated-encryption scheme
-   Equivalently:
-       **If** some adversary **A** does a good job at breaking PMAC-AES
-       **then** some comparably efficient **B** does a good job to break AES
-  Actual theorems quantitative: they measure how much security is
-    “lost” across the reduction.

## Block-Cipher Security

- [Goldreich, Goldwasser, Micali]
- [Luby, Rackoff]
- [Bellare, Kilian, Rogaway]

- B

- EK (xi)

- Enciphering
- oracle EK

- xi

- Rand perm
- oracle, 

-  (xi)

**Adv****prp** (**B**) = Pr[**B**EK = 1] – Pr[**B** = 1]

- xi

**Block-Cipher Security**

## PMAC’s Security

- [Goldreich, Goldwasser, Micali]
- [Bellare, Kilian, Rogaway]

- A

- PMACK (xi)

- PMACK
- oracle

- xi

- Rand func
- oracle, R

- R (xi)

- xi

**PMAC’s Security**

**Security as a VIL PRF**

**Adv****prf** (**A**) = Pr[**A****PMAC****K** = 1] – Pr[**A**R = 1]

## PMAC Theorem

- Suppose  an adversary **A**
- that breaks **PMAC-****E**  with:
*time* =  t
*total-num-of-blocks* = 
*adv * = **Adv****prf** (**A**) 2 / 2n

- Then  an adversary **B**
- that breaks block cipher **E** with:
*time*   t
*num-of-queries*  
**Adv****prp **(**B**)  **Adv****prf **(**A**) –  2 / 2n-1

- (  To wrap up,
-    it is a standard result that any -bit-output PRF
-    can be used as a MAC, where the forging probability
-    will be at most **Adv****prf** (**A**)  + 2-  )

- [Goldreich, Goldwasser, Micali]
- [Bellare, Kilian, Rogaway])

## Comparisons

**PMAC**

**XCBC**

**XECB-MAC**

| ({0,1}n)m |  |  |  | |M| / n
 | k | 1 xor |
| --- | --- | --- | --- | --- | --- | --- |
| {0,1}* |  |  |  | |M| / n
 | k + 2n | 1 xor |
| {0,1}* |  |  |  | |M| / n
varies | varies | 1 xor
2 add |
| {0,1}*
 |  |  |  | |M| / n
 | k | 3 xor |

**CBCMAC**

- [BR 00]

- [GD 00,01]

- [BR 00,01]

- Domain

- PRF

- #calls

- Parallelizable

- Key bits

- / blk overhead

- MAC length

**(3 versions)**

## For More Information

-   PMAC web page   www.cs.ucdavis.edu/~rogaway
-     Contains FAQ, papers, reference code, test vectors...
-   Feel free to call or send email
-   Or grab me now!