# Presentation: 025265

## OCB Mode

**Phillip Rogaway**
- Department of Computer Science
- UC Davis + Chiang Mai Univ
- 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**
- UNR
- jrb@cs.unr.edu

**Mihir Bellare**
- UCSD
- mihir@cs.ucsd.edu

**Ted Krovetz**
- Digital Fountain
- tdk@acm.org

- Looking—
- contact Ted!

## Two Cryptographic Goals 

- Privacy    What the Adversary sees tells her nothing of significance
-                 about the underlying message M that the Sender sent
- Authenticity 	The Receiver is sure that the string he receives was
- 		sent (in exactly this form) by the Sender
- Authenticated Encryption    Achieves both privacy and authenticity

## Why Authenticated Encryption?

-  **Efficiency**
-        By merging privacy and authenticity one can achieve
-        efficiency difficult to achieve if handling them separately
-  **Easier-to-correctly-use abstraction**
-       By delivering strong security properties one may
-        minimize encryption-scheme misuse

## What does Encryption Do?

- What does Encryption **Do**?

- No meaningful notion of privacy

*ECB*

- IND under CPA

*CTR, CBC$*

- IND under CCA  =  NM under CCA

- Authenticated encryption: IND under CPA +
-                                            auth of ciphertexts

*OCB*

- Idealized encryption

- Security community’s
- favored view

- Cryptographic community’s
- favored view: sym encryption is for
- IND-CPA (and nothing more)

- [Bellare,
- Nampremre],
- [Katz, Yung]

**Strong**

**Weak**

- [Bellare, Desai,  Jokipii, Rogaway]

## Right or Wrong?

- A

- B

- K

- K

- A  .  R**A**

- R**B** .  E**K** (A . B . R**A** . R**B ** .** **** **sk)

-  E**K** (R**B**)

- It depends on what definition E satisfies

## Generic Composition 

- Glue together an encryption scheme  ( E )
-                   and a Message Authentication Code (MAC)

- Traditional approach to authenticated encryption

- Folklore approach. See
- [Bellare, Namprempre]
- and [Krawczyk]
- for analysis.

- Preferred way to do generic composition:

## Generic Composition

- + Versatile, clean architecture
- + Reduces design work
- + Quick rejection of forged messages if use optimized MAC
-     (eg., UMAC)
- + Inherits the characteristics of the modes one builds from
-  Cost   (cost to encrypt) + (cost to MAC)
-        For CBC Enc + CBC MAC, cost   2   (cost to CBC Enc)
- - Often misused
-  Two keys
-  Inherits characteristics of the modes one builds from

## Trying to do Better

-  Numerous attempts to make privacy + authenticity cheaper
-  One approach: stick with generic composition, but find cheaper
-   privacy algorithm and cheaper authenticity algorithms
-  Make authenticity an “incidental” adjunct to privacy within a
-    conventional-looking mode
-   CBC-with-various-checksums      (wrong)
-   PCBC in Kerberos                         (wrong)
-   PCBC of [Gligor, Donescu  99]    (wrong)
-   [Jutla - Aug 00]    First correct solution
-   Jutla described two modes, IACBC and IAPM
-   A lovely start, but many improvements possible
-   OCB: inspired by IAPM, but many new characteristics

## What is OCB?

-  Authenticated-encryption scheme
-  Uses any block cipher (eg. AES)
-  Computational cost  cost of CBC
-  OCB-AES good in SW or HW
-  Lots of nice characteristics designed in:
-  Uses  |M| / n  + 2 block-cipher calls
-  Uses any nonce (needn’t be unpredictable)
-  Works on messages of any length
-  Creates minimum-length ciphertext
-  Uses a single block-cipher key,  each block-cipher keyed with it
-  Quick key setup – suitable for single-message sessions
-  Essentially endian-neutral
-  Fully parallelizable
-  No n-bit additions
** **Provably secure:  if you  break OCB-AES you’ve broken AES
-  In IEEE 802.11 draft.    Paper to appear at ACM CCS ’01

- Checksum = M[1]  M[2]  ...   M[m-1]  C[m]0*  Pad

- Z[i] = Z[i-1]  L(**ntz**(i))
- L(0) = EK(**0**)  and each  L(i) obtained from L(i-1) by a shift and conditional xor

## Definition of OCB[E, t]

**a****lgorithm**  OCB-Encrypt K (Nonce,  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 n bits,  except M[m] may be shorter
- Offset = EK (Nonce  L(0))
**for** i=1 **to** m-1 **do **
**        **Offset = Offset  L(ntz(i))**	****	**
-         C[i] = EK (M[i]  Offset)  Offset
- Offset = Offset  L(ntz(m))
- Pad  = EK (len(M[m])  Offset    L(-1))
- C[m] = M[m]   (first |M[m] |   bits of  Pad)
- Checksum = M[1]  ...  M[m-1]  C[m]0*  Pad
- Tag = first  bits of EK(Checksum  Offset)
**return** C[1] ... C[m] || Tag

## Assembly Speed

- Data from **Helger Lipmaa**    www.tcs.hut.fi/~helger     helger@tcs.hut.fi

-  OCB-AES                	 16.9 cpb    (271 cycles)
-  CBC-AES                	 15.9 cpb    (255 cycles)
-  ECB-AES                	 14.9 cpb    (239 cycles)
-  CBCMAC-AES       	 15.5 cpb    (248 cycles)

- 6.5 % slower

- The above data is for 1 Kbyte messages.  Code is  pure Pentium 3 assembly.
- The block cipher is AES128.  Overhead so small that AES with a C-code CBC
- wrapper is slightly more expensive than AES with an assembly OCB wrapper.

**// Best Pentium AES code known.  Helger’s code is for sale, btw.**

**C Speed**

-  OCB-AES                	 28.1 cpb    (449 cycles)
-  CBCMAC-AES       	 26.8 cpb    (428 cycles)

- 4.9 % slower

- Data from **Ted Krovetz** . Compiler is MS VC++.   Uses rijndael-alg-fst.c ref code.

## Why I like OCB

**Ease-of-correct-use**.  Reasons: all-in-one approach; any type of
- 	nonce; parameterization limited to block cipher and tag length
**Aggressively optimized**:  optimal in many dimensions:
-       key length, ciphertext length, key setup time, encryption time,
-       decryption time,  available parallelism; SW characteristics;
-       HW characteristics; ...
**Simple but highly non-obvious**
- Ideal setting for **practice-oriented** **provable security**

## What is 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
-   Eg:
-       **If** AES is a secure block cipher
-       **then** OCB-AES is a secure authenticated-encryption scheme
-   Equivalently:
-       **If** some adversary **A** does a good job at breaking OCB-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.

## The Power of Definitions

- (

- )

-  Let’s you carry on an intelligent conversation
-  Let’s you investigate the “space” of goals and
-    how they are related
-  Often let’s you easily see when protocols are **wrong**
-  Let’s you prove when things are right, to the extent
-   that we know how to do this.

- It took about an hour to break the NSA’s “Dual Counter Mode”.
- What did I have that the NSA authors didn’t?  Just an understanding
- of a good **definition** for the goal.

## PrivacyIndistinguishability from Random Bits

- A

- EK ( Noncei , Mi )

**Real**
- EK oracle

- Noncei  Mi

**Rand**
- bits oracle

- $ |Mi| + 

**Adv****priv** (**A**) = Pr[**A****Real**** **= 1] – Pr[**A****Rand**** **= 1]

- [Goldwasser, Micali]
- [Bellare, Desai,
- Jokipii, Rogaway]

- Noncei  Mi

## Authenticity: Authenticty of Ciphertexts

- A

- Noncei   Mi

- EK ( Noncei , Mi )

**Real **
- EK oracle

**Adv****auth** (**A**) = Pr[**A** forges]

- Nonce  C

**A** forges if she outputs
- forgery attempt Nonce  C  s.t.
-  C is **valid** (it decrypts
-    to a message, not to **invalid**)
-  there was no EK query
-    Nonce  Mi that returned C

- [Bellare, Rogaway]
- [Katz, Yung]
- this paper

## Block-Cipher SecurityPRP and Strong PRP

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

- B

- EK (xi)

**Real**
- EK oracle

- xi

**Rand** perm
- oracle

-  (xi)

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

- xi

**Adv****sprp** (**B**)= Pr[**B**EK EK-1 = 1] – Pr[**B** = 1]

## OCB Theorems

- Suppose  an adversary **A**
- that breaks **OCB-****E**  with:
*time* =  t
*total-num-of-blocks* = 
*adv * = **Adv****priv** (**A**)

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

**Privacy theorem:**

- Suppose  an adversary **A**
- that breaks **OCB-****E**  with:
*time* =  t
*total-num-of-blocks* = 
*adv * = **Adv****auth** (**A**)

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

**Authenticity theorem:**

## What Provable Security Does, and Doesn’t, Buy You

- + Strong evidence that scheme does what was intended
- + Best assurance cryptographers know how to deliver
- + Quantitative usage guidance
-  An absolute guarantee
-  Protection from issues not captured by our abstractions
-  Protection from usage errors
-  Protection from implementation errors

## Parallelizable Authenticated-Encryption Schemes

**XECB-XOR**

**OCB**

| 
({0,1}n)+ | 
 | nonce (Jutla’s presentation gave rand version) | 
|M| /n + 2
 | 
0 | 2k
(2) | 1 xor
2 add
1 addp | 
2 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 
{0,1}* | 
|M| / n+ n
 | 
ctr | 
|M| /n
 | 
0 | k+2n
(1) | 1 xor
3 add | 
1 |
| 
{0,1}* | 
|M| + 
 | 
nonce | 
|M| /n | 
1 | k
(1) | 
4 xor | 
3 |

**IAPM**

- [R+ 00,01]

- [GD 01]

- Domain

- Calls / keysetup

- / blk overhead

- | Ciphertext |

**(lazy mod p)**

- [Jutla 00,01]

- IV rqmt

- Calls / msg

- E circuit depth

- Key length  (#E-keys)

## For More Information

-   OCB web page   www.cs.ucdavis.edu/~rogaway
-     Contains FAQ, papers, reference code, licensing info...
-   Feel free to call or send email
-   Upcoming talks: MIT (Oct 26), ACM CCS (Nov 5-8), Stanford (TBA)
-   Or grab me now!

**Anything Else ??**