# Presentation: 524416

## The XCBC-XOR, XECB-XOR and XECB-MAC Modes

**Virgil D. Gligor****	****	****Pompiliu Donescu**
**VDG Inc**
**6009 Brookside Drive**
**Chevy Chase, Maryland 20815**
**{gligor, pompiliu}@eng.umd.edu**
**August 24, 2001**

## 		Outline 

- 1. Security Claims
- 2. Operational Claims
- 3. Examples: XCBC-XOR, XECB-XOR, XECB-MAC modes
- 4. Conclusions

## 1. Security Claims for Authenticated Encryption 

- 1. *Security ****Claim*** = a security *notion* supported by
- 				a mode or scheme of encryption
- 2. ***Secrecy Notion***** **= < Indistinguishability, adaptive Chosen Plaintext Attacks>
- 3. ***Integrity (Authenticity) Notion*** = < Existential Forgery protection,
- 				          (adaptive) Chosen Plaintext Attacks>

## 2. Operational Claims for Modes of Encryption 

***Operational Notion***** **= < operational goal, mode characteristics >
-  Operational ***Goals:  ***cost-performance, simplicity, usability
-  cost-performance:
-  power consumption
-  speed (no. of  block-cipher invocations, latency)
-  implementation cost (e.g., hardware “real-estate’’)
-  simplicity
-  single key
-  specifications (e.g., simple operations)
-  same basic structure for
- 	- authenticated encryption
- 	- ciphertext authentication (two-pass, two keys)
- 	- plaintext authentication (MAC)
-  usability in different environments
-  various keying-state protection mechanisms needed
-  availability of random number generators,
-  error recovery (ECC, no recovery vs. partial recovery)

## 		Operational Characteristics of Modes

***State***: stateless, stateful-sender, stateful
***Degree of parallelism***
-  none (sequential)
-  interleaved (known/negotiated no. of processing units for parallel operation)
-  architecture-independent
-   independent of no. of processing units
-   same overhead for parallel, pipelined or sequential operation
-   out-of-order processing, incremental
***Error recovery***
-  interleaving provides some support on a per-segment basis
***Separation of Confidentiality and Integrity protection (e.g., two-pass, two keys)***

***Padding***
-  avoid added block-cipher invocation if** **message length is a multiple no. of blocks.
-  avoid added latency (1 block-cipher invocation) caused by “ciphertext stealing”

## Examples of  State Characteristics of a Mode

**Stateless**
**	****- needs good, secure source of randomness *****per message***
**	****- no state to maintain across messages (other than key)**
**	****- Execution: ******** n+3 block cipher invocations; **
**	****- Latency: ******** 2 block cipher invocations  in parallel ****	****execution**

**Stateful Sender**
**	****- state (e.g., message counter) maintained by sender**
**	****- protection of sender state (e.g., counter integrity) across messages **
**	****- Execution:  n+2 block cipher invocations**
**	****- Latency:  2 block cipher invocations in parallel  execution**

**Stateful **
**	****- state : shared variables (other than key)**
**	****- protection of state secrecy, integrity across messages**
**	****- more susceptible to failures, intrusion **
**	****- Execution: *****n+1***** block cipher invocations****	****- ****	****- Latency: ******** *****1***** block cipher invocation in parallel execution**

**robustness**
**increase**

**speed**
**increase**

## .

- x1

- x2

- x3

- x4

**.**

- K

- x =

**.**

- E1

- E2

- E3

- E4

**.**

- E5

**.**

**.**

**.**

- y2

- y3

- y4

- y =

- y1

- y5

**.**

**MDC(x)**

**.**

**.**

**.**

- x5

- IND-CPA
- Secure Mode

- z1

- z2

- z3

- z4

- z5

- Sender
- Initialization

**F****K**

**. . . **

**. . . **

- Receiver
- Initialization

**3. Authenticated Encryption Modes **

**op**

**op**

**op**

**op**

**op**

**1.  IND-CPA secure mode: **processes block** x****i****, 1 ******** i ******** n+1, **and inputs result to **block cipher F****K**
**2.  “op” **has an inverse** “op****-1****”**
**3.  **Elements **E****i **are unpredictable**, 1 ******** i ******** n+1,  ***and*
**	**** ****E****p****i ****op****-1 ****E****q****j**** **are unpredictable**, **where** (p, i) ******** (q, j) **
**	****	****	****  **messages **p,q **are encrypted with same** key K. **

- Unpredictable
-    vector z0

## .

- z1

- z2

- z3

- z4

**K’**

- z =

**.**

**.**

- IND-CPA
- Secure Mode

- w1

- w2

- w3

- w4

- Sender
- Initialization

**F****K**

**. . . **

**. . . **

- Receiver
- Initialization

**Motivation for Confidentiality-Centric View **

**w**

- z

- 1

- z

- 2

- z

- 3

- z

- 4

***Observation (1998):*****  secure message authentication modes (in chosen message attacks) can be **
**	****	****obtained from certain IND-CPA secure modes**
***Implication*****: same mode structure can be used for **
**	****(1) authenticated encryption (one pass, single cryptographic primitive)**
**	****(2) ciphertext authentication (two-pass, single cryptographic primitive, **
**	****	****	****	****two-key separation of confidentiality and integrity)**
**	****(3) plaintext authentication (MAC) **
***Implementation:***** with only little added control logic we get (1), (2) and (3)  **

## .

- K

- Random-number generator

- r0

**.**

- y0

**F****K**

**.**

**IND-CPA **
**   ****mode**

**stateless mode**

- r0

- ctr

- ctr’ = ctr+1

**F****K**

- K

**.**

**.**

**.**

**IND-CPA **
**   ****mode**

**E****i ****= i x **r0

- ctr

**stateful-sender mode**

- K

**.**

**R*, R**

**E****i**** = ctr x R* +  i x R**

**R*, R**

**E****i**** = ctr x R* +  i x R**

- ctr

- ctr’ = ctr+1

- ctr

**.**

**stateful mode**

**Examples of Mode Initialization**

**1 ******** i ******** n+1**

**1 ******** i ******** n+1**

**E*****n+1**** = ctr x R***

**E*****n+1**** = ctr x R***

**sender**

**sender**

**sender**

**receiver**

**receiver**

**receiver**

**R*, R = random, uniformly distributed,**
**              ****independent ****l****-bit variables**

**E****i ****= i x **r0

## .

- x

- 1

- x

- 2

- z

- 1

- y

- 2

- x

- 3

- x

- 4

- y

- 3

- y

- 4

- x =

- y =

- y

- 1

- z

- 2

-  E

- 1

- z

- 3

- z

- 4

**CBC Encrypt with F****K**

-  E

- 2

-  E

- 3

-  E

- 4

**.**

**.**

- z

- 5

-  E

- 5

**.**

**.**

- y

- 5

**.**

**.**

**.**

**.**

- MDC(x)

- 

-   z

- 0

- z

- 0

**F**

**K**

**F**

**K**

- K

- Random-number

- generator

**.**

- y

- 0

**.**

- r

- 0

**.**

- r

- 0

- +c

**.**

**Stateless XCBC-XOR**

**op**

**op**

**op**

**op**

**op**

**MDC = ********, E****i**** = r****0**** x  i, op = +, **and others;  **Padding **= 10* pattern, use z0 if padding is needed,
-  					           z0 if padding is not needed

**Stateful-Sender** (e.g., r0 = **F****K**(ctr)) and **Stateful** (e.g., per-key shared VI, z0 = r0+VI) XCBC-XOR are also defined
- Stateless Performance: **> n+3**  blk. cipher invocations,  **> 2** blk. cipher invocations latency
- Stateful-Sender Performance: **n+3**  blk. cipher invocations,  **2** blk. cipher invocations latency
- Stateful Performance: **n+2**  blk. cipher invocations, **2** blk. cipher invocations latency

## .

- x1

- x2

- x3

- x4

- E1

- K

- E2

- E3

- E4

**.**

- E*5

**.**

**.**

- x =

**.**

**F****K**

**F****K**

**F****K**

**F****K**

**F****K**

- K

- K

- K

- K

- K

**.**

- E1

- E2

- E3

- E4

**.**

- E5

**.**

**.**

**.**

- y2

- y3

- y4

- y =

- y1

- y5

**.**

- MDC(x)

**.**

**.**

**.**

- x5

- z1

- z2

- z3

- z4

- z5

- v1

- v2

- v3

- v4

- v5

- ctr

- ctr x R*

- ctr

**.**

- ctr’ = ctr+1

- R*

- R

**.**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**1 ******** i ******** n+1**

**E****i**** = ctr x R* +  i x R**

**E*****n+1**** = ctr x Z***

**Stateful XECB-XOR**

***Performance Optimized***
**- n+1 block-cipher invocations**
**- ******** 1 block-cipher latency**

***           ******Padding***
**- Z* = ********R* **if unpadded
**- Z* =  R* **if padded
- - padding pattern: 10*

- IND-CPA Secure Mode

## .

- x1

- x2

- x3

- x4

- E1

**.**

- K

- E2

- E3

- E4

**.**

- E*5

**.**

**.**

- x =

**.**

- Random-number generator

- r0

**F****K**

**F****K**

**F****K**

**F****K**

**F****K**

- K

- K

- K

- K

- K

**.**

- E1

- E2

- E3

- E4

**.**

- E5

**.**

**.**

**.**

- y2

- y3

- y4

- y =

- y1

- y5

- y0

**F****K**

**.**

**.**

- MDC(x)

**.**

**.**

**.**

- x5

- z1

- z2

- z3

- z4

- z5

- v1

- v2

- v3

- v4

- v5

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**Stateless XECB-XOR**

**MDC = ********, E****i**** = r****0**** x i, E*****n+1**** = (n+2) x Z*, op = +, **and others; **Z* = ******** r****0**** **or **r****0** depending upon padding

- IND-CPA Secure Mode

- Stateless Performance: **> n+2**  blk. cipher invocations,  **> 2** blk. cipher invocations latency

## .

- x1

- x2

- x3

- x4

- E1

- K

- E2

- E3

- E4

**.**

- E*5

**.**

**.**

- x =

**.**

- r0

**F****K**

**F****K**

**F****K**

**F****K**

**F****K**

- K

- K

- K

- K

- K

**.**

- E1

- E2

- E3

- E4

**.**

- E5

**.**

**.**

**.**

- y2

- y3

- y4

- y =

- y1

- y5

**.**

**.**

- MDC(x)

**.**

**.**

**.**

- x5

- z1

- z2

- z3

- z4

- z5

- v1

- v2

- v3

- v4

- v5

- ctr

- ctr’ = ctr+1

**F****K**

- ctr

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**op**

**Stateful-Sender XECB-XOR**

**MDC = ********, E****i**** = r****0**** x i, E*****n+1**** = (n+2) x Z*, op = +, **and others; **Z* = ******** r****0**** **or **r****0** depending upon padding

- IND-CPA Secure Mode

- Stateful-Sender Performance: **n+2**  blk. cipher invocations,  ** 2** blk. cipher invocations latency

## .

- x1

- x2

- x3

- x4

- y1

- y2

- y3

- y4

**K**

- y’5

- x5

- x6

- x7

- x8

- y5

- y6

- y7

- y8

**K**

- y’9

- x =

- x9

- x10

- x11

- x12

- y9

- y10

- y11

- y12

**K**

- y’13

- r01

- r02

- r03

- x1

- x2

- x3

- x4

- x5

- x6

- x7

- x8

- x9

- x10

- x11

- x12

- Plaintext
- Segment 1

**Plaintext Segment 1**
**Encryption **

**Plaintext Segment 2**
**Encryption**

**Plaintext Segment 3**
**Encryption**

- ctr

**F****K**

**K**

**.**

- Plaintext
- Segment 2

- Plaintext
- Segment 3

- Ciphertext
- Segment 1

- Ciphertext
- Segment 2

- Ciphertext
- Segment 3

**F****K**

**K**

**F****K**

**K**

- ctr

- ctr+1

- ctr+2

- ctr

- y1

- y2

- y3

- y4

- y’5

- y5

- y6

- y7

- y8

- y’9

- y9

- y10

- y11

- y12

- y’13

- y =

- ctr’ = ctr+3

**SEGMENTED Stateful-SenderMode***

** ****(*) per-segment error handling => error recovery**

## .

- x

- 1

- x

- 2

- x

- 3

- x

- 4

- w

- K

**.**

**.**

- x =

- R

**F**

**K**

**F**

**K**

**F**

**K**

**F**

**K**

- K

- K

- K

- K

- x

- 1

- x

- 2

- x

- 3

- x

- 4

- ctr

**     ****E****3**

**E****2**

**E****1**

- R*

**.**

**.**

**.**

**.**

**.**

**.**

**.**

- ctr

- ctr’

-  =

- ctr

- +1

- R*

- x

- ctr

**op**

**op**

**op**

**op**

**Stateful XECB-MAC**

**1 ******** i ******** n**

**E****i**** = ctr x Z* +  i x R,**

***Performance Optimized***
**- n+1 block-cipher invocations**
**- ******** 1 block-cipher latency**

***           ******Padding***
**- Z* = ********R* **if unpadded
**- Z* =  R* **if padded
- - padding pattern: 10*

**E****4**

- IND-CPA Secure Mode

## 4. Conclusions

-  stateful XECB-XOR and XECB-MAC are optimal (minimum block cipher invocations and latency);
-  XECB-XOR and XECB-MAC modes exhibit architecture-independent parallelism;
-  XCBC-XOR modes are simple extensions of the standard CBC mode
-  **Simplicity:**
-  same basic structure for
- 	- authenticated encryption
- 	- ciphertext authentication (two-pass, two keys)
- 	- plaintext authentication (MAC)
-  **Usability: **
-  stateless, stateful-sender, stateful modes for different environments.
-  **Security:**
-  good bounds.

**4. Conclusions**