Authenticated Encryption

Maria Eichlseder
Applied Cryptography – WT 2017/18
 [Link]

Authenticated Encryption – Goals

If your data is worth encrypting,

you almost certainly don’t want it modified!

Confidentiality
as provided by block cipher modes

Authenticity, integrity
as provided by message authentication codes

“it is very easy to accidentally combine secure encryption schemes

with secure MACs and still get insecure authenticated encryption
schemes”

– Kohno, Whiting, and Viega

1 / 43
 [Link]

Outline

Authenticated Encryption
Requirements
Generic compositions
Pitfalls
Dedicated modes

CAESAR
The competition
The candidates

2 / 43
 [Link]

Notation cheatsheet

M: Message, plaintext to be protected

C: Ciphertext, protected version of plaintext
K : Shared secret key of Alice and Bob
N: Nonce (number-used-once), a unique initial value (IV)

EK : block cipher encryption, EK : Fb2 → Fb2

EK∗ : block cipher mode, EK∗ : F∗2 → F∗2
MACK : MAC authentication MACK : F∗2 → Fb2
h: hash function h : F∗2 → Fb2

⊕: xor of bitstrings
k: concatenation of bitstrings
×: multiplication in a binary finite field
3 / 43
 [Link]

Reminder: Block cipher modes of operation EK∗

Cipher block chaining (CBC)

message M1 M2 M`
IV
M ∈ F∗2 N ∈ Fb2 N ···

EK EK EK

C1 C2 C`
EK∗
Counter (CTR)
Nk1 Nk2 Nk`

EK EK ··· EK
C ∈ F∗2
ciphertext M1 M2 M`

C1 C2 C`

4 / 43
 [Link]

Why doesn’t EK∗ provide authenticity?

original forgery
↓ ↓
streaming modes (OFB, CTR):
arbitrary modifications, not detectable
M ...000100... M0 ...011100...
C ...110011... C0 ...101011...

many modes (CBC, CFB):

arbitrary modifications, delayed detection
M ...000100... M0 ...0111??...
C ...110011... C0 ...101011...

any mode:
random modification of low-redundancy data
M ...000100... M0 ...??????...
C ...110011... C0 ...101011...

No authenticity without redundancy (any C will decrypt to a valid M)!

5 / 43
 [Link]

Why the fuss – can’t I send EK∗ (M kh(M ))?

No good idea – attacker can easily send (forge) chosen message M:

Known-plaintext attack for stream encryption (OFB, CTR, . . . )

Intercepts any C 0 = EK∗ (M 0 kh(M 0 ) with known M 0

Forges C = EK∗ (Mkh(M)) = C 0 ⊕ (M ⊕ M 0 kh(M) ⊕ h(M 0 ))

Chosen-plaintext attack for block encryption

Tricks user to send M 0 = Mkh(M)kx

Intercepts C 0 = EK∗ (Mkh(M)kxkh(M 0 ))
Forges C = EK∗ (Mkh(M)) by truncating end of C 0

6 / 43
 [Link]

Reminder: Message authentication codes MACK

CBC-MAC
M1 M2 M`
message
M ∈ F∗2 0 ···

EK EK EK

T
MACK
HMAC
(K ⊕ 0x3636..)kM1 · · · M`

(K ⊕ 0x5c5c..)k h
T ∈ Fb2
tag
h T

7 / 43
 [Link]

Authenticated Encryption – Ingredients

message M ∈ F∗2 (confidential and authentic)

associated data A ∈ F∗2 (authentic) (e.g., connection metadata)

ciphertext C ∈ F∗2

tag T ∈ Fb2

key K ∈ Fb2 (confidential)

nonce N ∈ Fb2 (rarely confidential) (like an IV, message number)

⊥ (error for invalid C, T )

8 / 43
 [Link]

Authenticated Encryption – Interface

AEAD: Authenticated Encryption with Associated Data

Authenticated Encryption E

Input: plaintext M, associated data A, key K , nonce N

Output: ciphertext C, tag T

Transmit A, C, T and (usually) N

Verified Decryption D

Input: ciphertext C, tag T , data A, key K , nonce N

Output: plaintext M or ⊥ if invalid

9 / 43
 [Link]

Generic compositions

How could block ciphers and MACs be combined?

E∗ ? C
?
M

?
MAC T
?

(And how to include A and N?)

10 / 43
 [Link]

Generic compositions

Encrypt-and-MAC (E&M)
E∗ C
∗ M
C = E (M), T = MAC(M)
MAC T

Encrypt-then-MAC (EtM)
M E∗ C
∗
C = E (M), T = MAC(C)
MAC T

MAC-then-Encrypt (MtE)
MAC
CkT = E ∗ (MkMAC(M)) M
E∗ CkT

11 / 43
 [Link]

Generic compositions

Encrypt-and-MAC (E&M)
e.g., in SSH
security depends on E ∗ and MAC details

Encrypt-then-MAC (EtM)
e.g., in IPSec; standard ISO/IEC 19772:2009
provably secure

MAC-then-Encrypt (MtE)
e.g., in SSL/TLS
security depends on E ∗ and MAC details

12 / 43
 [Link]

Pitfalls: Dependent Keys 1 (Authenticity)

Mac-then-Encrypt with CBC-MAC and CBC

CBC CBC-MAC
M1 M2 M` M1 M2 M`

N ··· N ···

EK EK EK EK EK EK

C1 C2 C` T

What happens?
C`+1 = EK (T ⊕ C` ) = EK (0), no authenticity!

(Keys for) E ∗ and MAC must be independent!

13 / 43
 [Link]

Pitfalls: Dependent Keys 2 (Confidentiality)

Encrypt-and-MAC with CBC-MAC and CTR

CTR CBC-MAC
Nk1 Nk2 Nk` M1 M2 M`

··· 0 ···
EK EK EK
EK EK EK
M1 M2 M`

C1 C2 C` T

What can an attacker do?

Query tags for messages Nk1, Nk2, . . . to read M

(Keys for) E ∗ and MAC must be independent!

14 / 43
 [Link]

Pitfalls: MtE or E&M with Encoding

Assume super-secure1 MACK and stream cipher2 EK∗ 0

Build another super-secure2 cipher E++∗K 0 as follows:

(
0 0 to 00
1 Encode M to M : expand
1 to 01 or 10
2 Apply EK∗0 to M 0

Use MACK and E++∗K 0 in MtE or E&M

How can an attacker break confidentiality?

1 SUF
2 IND-CPA. . . more in a moment
15 / 43
 [Link]

Pitfalls: MtE or E&M with Encoding – Attack

Padding Oracle Attack

Attacker intercepts ciphertext C

Repeats for each bit i of M:

1 Toggle bit 2i, 2i + 1 of C (= of M 0 )
e (i) to recipient
2 Send this modified C
3 If rejected: bit i was 0, else 1

Encoding may seem contrived, but

many similar examples in the real world!

The good news: MtE, E&M secure under some conditions,

for some specific E ∗ (e.g., CBC) – but not in general!

16 / 43
 [Link]

Security notions – Block cipher modes

Confidentiality

IND-CPA (indistinguishable under chosen plaintexts):

infeasible for an attacker to find out which message M or M 0 was
encrypted to C, even if he can query encryptions of any chosen
messages (including M, M 0 !).

IND-CCA2 (indistinguishable under adaptive chosen ciphertexts):

like IND-CPA, but the attacker can additionally query the
decryption of any ciphertext except C.

Most block cipher modes are IND-CPA.

17 / 43
 [Link]

Why is CBC not IND-CCA2?

CBC
M1 M2 M`
N ···

EK EK EK

C1 C2 C`

attacker lets some M, M 0 be encrypted to challenge C

receives challenge ciphertext C with N

can query decryption of adaptive chosen ciphertext:

C with some modified N ⊕ ∆, or. . .
C with some modified C1 ⊕ ∆, or. . .

18 / 43
 [Link]

Security notions – MACs

Authenticity/integrity

WUF-CMA (weak unforgeability):

infeasible for an attacker to find tag T for any new message M,
even if he can request tags for any chosen messages M 0 6= M.

SUF-CMA (strong unforgeability):

like WUF-CMA, but even a new T 0 for a previously queried M
counts.

Most MACs are SUF.

19 / 43
 [Link]

Security notions – Authenticated encryption

Confidentiality
IND-CPA and IND-CCA2

Authenticity/integrity

INT-PTXT (integrity of plaintext):

infeasible for an attacker to construct ciphertext C (with T ) for
any new message M, even if he can query encryption of chosen
messages M 0 6= M.
INT-CTXT (integrity of ciphertext):
like INT-PTXT, but even a new ciphertext C 0 6= C for a previously
queried M counts.

20 / 43
 [Link]

Security of Generic Compositions

If E ∗ is IND-CPA and MAC is WUF/SUF:

Type Confidentiality Authenticity

IND-CPA IND-CCA INT-PTXT INT-CTXT
E&M × × X ×
MtE X × X ×
EtM X ×/X∗ X ×/X∗
×insecure Xsecure ×/X∗ secure only for SUF MACs

21 / 43
 [Link]

Security of Generic Compositions – Revisited

The theoretic generic model so far doesn’t really match practice:

Makes implicit assumptions about nonce N, no metadata A, . . .

Adding explicit inputs N, A makes the situation more complicated

We didn’t say anything about the “exact” security level (birthday!)

Not so efficient: Need to process data twice (“two-pass scheme”)

We need dedicated authenticated encryption schemes

AEAD: Authenticated Encryption with Associated Data
We also need a suitable, concise security notion

22 / 43
 [Link]

All-in-one security notion for AEAD scheme

Real AEAD oracle Ideal AEAD oracle

Implements the scheme Behaves like an ideal AEAD

E executes scheme with K E returns a random string∗

D executes scheme with K D always returns ⊥ ∗
∗
except consistency with previous queries

Attacker’s goal: Decide if she is talking to real or ideal oracle

Can send queries (N, A, M) to E and (N, A, C, T ) to D
She is not allow to cheat (reuse nonce, . . . )

23 / 43
 [Link]

Standardized and popular schemes

Popular AEAD schemes (ISO/IEC standards, TLS v1.3 ciphers, . . . ):

AES-GCM (the TLS default)

AES-CCM
OCB 3.0 (very fast)
SIV (nonce-misuse resistance)
ChaCha20-Poly1305 (not based on AES)
...

AEAD modes are expected to provide a security proof

(assuming an ideal block cipher and a nonce-respecting adversaries)

24 / 43
 [Link]

CCM – CTR and CBC-MAC

MtE with CTR encryption mode and CBC-MAC:

Nk16 · ` EK EK EK ··· EK

A1 · · · As
M1 M2 M` T

Nk1 Nk2 Nk` Nk`+1

EK EK EK EK

C1 C2 C` C`+1

25 / 43
 [Link]

CCM – Properties

+ Secure for ideal cipher EK

+ Needs no DK (decryption)

− Two block cipher calls per block

− Two-pass, not online (need length in advance)

− CBC-MAC not parallellizable

26 / 43
 [Link]

GCM – Galois/CTR Mode

EtM with CTR and Carter-Wegman MAC (in “Galois field” F2128 )

0 Nk1 Nk2 Nk` Nk0

EK EK EK ··· EK EK

H M1 M2 M`

A1 · · · As C1 C2 C` `ks

···

×H ×H ×H ×H ×H T

27 / 43
 [Link]

GCM – Properties

AES-GCM is very popular

+ Fast
EK parallellizable
one block cipher call per block

− Harder to implement (nasty multiplications)

− Security: some weak keys due to MAC properties

28 / 43
 [Link]

OCB – Offset Codebook Mode

∆0←initK (N)

∆1←inc1K (∆0) ∆2←inc2K (∆1) ∆`←inc`K (∆`−1) ∆$←inc`K (∆`)

M
Mi
M1 M2 M` 1≤i≤`

∆1 ∆2 ∆` ∆$

EK EK ··· EK EK
M
∆1 ∆2 ∆` EK (Ai ⊕ ∆
e i)
1≤i≤s

C1 C2 C` T

29 / 43
 [Link]

OCB – Properties

Faster and easier to implement than GCM

Shows how useful tweakable block ciphers (TBCs) can be

Patented!
Can be used under some conditions, but. . . complicated.

30 / 43
 [Link]

SIV – Synthetic Initialization Vector (aka Key Wrap)

Previous schemes lose security if N is reused

SIV is a nonce-free (deterministic) scheme:

T = MACK (A, M)
use T as IV for C = EK∗0 (M)
send T kC

Not as efficient, data processed twice, offline

inherently not IND-CPA (since deterministic), but security proofs

for other strong properties

Suitable for encrypting “high entropy” messages like keys

31 / 43
 [Link]

Duplex sponge constructions

Sponges became popular with SHA-3 winner Keccak

Can be transformed to AEAD mode: duplex sponges

Based on permutation p instead of block cipher EK

A1 As M1 C1 M ` C`
r r
K kN T
p p p p p
c c
0

32 / 43
 [Link]

Potential features of AEAD designs

Nonce misuse resistance

Release under unverified plaintext
Parallelizable
Fewer block cipher calls per block
Key size = security level
Online, single-pass
Inverse-free
Hardware/software optimization
Lightweight
Cheaper security against side-channel/fault attacks
Simplicity
...

33 / 43
 [Link]

The CAESAR competition

CAESAR – Competition for Authenticated Encryption: Security,

Applicability, and Robustness

Inspired by AES, SHA-3 (NIST), NESSIE, eStream (EU)

Co-funded by NIST
Goal: Portfolio of great AEAD designs

Currently ongoing

34 / 43
 [Link]

CAESAR – Timeline

Mar 15, 2014: First-round submissions

Jul 07, 2015: Announcement of round 2 candidates

Aug 15, 2016: Announcement of round 3 candidates

??? ??, 2017: Announcement of finalists

Dec 15, 2017: Announcement of final portfolio (??)

35 / 43
 [Link]

CAESAR – Submissions
ACORN ++AE AEGIS AES-CMCC
AES-COBRA AES-COPA AES-CPFB AES-JAMBU
AES-OTR AEZ Artemia Ascon
AVALANCHE Calico CBA CBEAM
CLOC Deoxys ELmD Enchilada
FASER HKC HS1-SIV ICEPOLE
iFeed[AES] Joltik Julius Ketje
Keyak KIASU LAC Marble
McMambo Minalpher MORUS NORX
OCB OMD PAEQ PAES
PANDA π-Cipher POET POLAWIS
PRIMATEs Prøst Raviyoyla Sablier
SCREAM SHELL SILC Silver
STRIBOB Tiaoxin TriviA-ck Wheesht
YAES

36 / 43
 [Link]

Advertisement: IAIK design :-)

ACORN ++AE AEGIS AES-CMCC
AES-COBRA AES-COPA AES-CPFB AES-JAMBU
AES-OTR AEZ Artemia Ascon
AVALANCHE Calico CBA CBEAM
CLOC Deoxys ELmD Enchilada
FASER HKC HS1-SIV ICEPOLE
iFeed[AES] Joltik Julius Ketje
Keyak KIASU LAC Marble
McMambo Minalpher MORUS NORX
OCB OMD PAEQ PAES
PANDA π-Cipher POET POLAWIS
PRIMATEs Prøst Raviyoyla Sablier
SCREAM SHELL SILC Silver
STRIBOB Tiaoxin TriviA-ck Wheesht
YAES

37 / 43
 [Link]

CAESAR – Round 2 Candidates

ACORN ++AE AEGIS AES-CMCC
AES-COBRA AES-COPA AES-CPFB AES-JAMBU
AES-OTR AEZ Artemia Ascon
AVALANCHE Calico CBA CBEAM
CLOC/SILC Deoxys ELmD Enchilada
FASER HKC HS1-SIV ICEPOLE
iFeed[AES] Joltik Julius Ketje
Keyak KIASU LAC Marble
McMambo Minalpher MORUS NORX
OCB OMD PAEQ PAES
PANDA π-Cipher POET POLAWIS
PRIMATEs Prøst Raviyoyla Sablier
SCREAM SHELL SILC Silver
STRIBOB Tiaoxin TriviA-ck Wheesht
YAES

39 / 43
 [Link]

CAESAR – Round 3 Candidates

ACORN ++AE AEGIS AES-CMCC
AES-COBRA COLM AES-CPFB AES-JAMBU
AES-OTR AEZ Artemia Ascon
AVALANCHE Calico CBA CBEAM
CLOC/SILC Deoxys ELmD Enchilada
FASER HKC HS1-SIV ICEPOLE
iFeed[AES] Joltik Julius Ketje
Keyak KIASU LAC Marble
McMambo Minalpher MORUS NORX
OCB OMD PAEQ PAES
PANDA π-Cipher POET POLAWIS
PRIMATEs Prøst Raviyoyla Sablier
SCREAM SHELL SILC Silver
STRIBOB Tiaoxin TriviA-ck Wheesht
YAES

41 / 43
 [Link]

Summary

Most applications need Confidentiality and Integrity

Many pitfalls when combining cryptographic primitives

Need for better authenticated ciphers → CAESAR

42 / 43
 [Link]

Questions

1 What interface and security services does AEAD provide?

2 Describe possible generic compositions.

Which are secure? What can go wrong?

3 Define security notions for confidentiality and integrity.

4 Describe a secure AEAD mode (GCM, CCM, . . . ).

5 Describe desirable properties of an AEAD mode.

6 Be able to identify and attack typical weaknesses

(redundancy-only integrity, dependent keys, . . . )

43 / 43