Authenticated Encryption

Combine confidentiality and integrity to for encryption secure against tampering.

The attacker can divert the package by update the IV, and let the server to decrypt the message for him! Without integrity, no confidentiality is protected.

Chosen Ciphertext Attack, thereafter CCA: The attacker craft the cipher text, such as tTt \oplus T and encrypted data, such as DsD \oplus s, and observe the ack from the server, it can find the D: checksum(hdr,D)=tchecksum(hdr,Ds)checksum(hdr, D) = t \oplus checksum(hdr, D \oplus s ).

Authenticated Encryption

A cipher(E, D) where:

E:K×M×NCD:K×C×NM{}\begin{align} E &: K \times M \times N \to C \\ D &: K \times C \times N \to M \cup \{\perp\} \end{align}

Note: M\perp \notin M. It is claimed to be authenticated encryption(AE) if it is:

  • semantically secure under CPA, aka negligible information about the plaintext can be feasibly extracted from the ciphertext
  • has ciphertext integrity, aka hacker cannot craft arbitrary ciphertext not from intercepted ciphertext.

Chosen Ciphertext Security

Adversary’s power: both CPA and CCA Adversary’s goal: break semantic security

Chosen Ciphertext Ssecurity attack
Chosen Ciphertext Ssecurity attack

The goal is for Adv. to determined whether it is in experiment 0 or 1. If the probably is “negligible”, we call E is CCA secure.

AE is CCA secure.

For any q-query eff. A, there exists eff. adversaries B1,B2B_1, B2, s.t:

AdvCCA2qAdvCI[B1,E]+AdvCPA[B2,E]Adv_{CCA} \le 2q \cdot Adv_{CI}[B_1, E] + Adv_{CPA}[B_2, E]


  • does not prevent replay attacks.
  • does not prevent side channels attack.

Constructions form ciphers and MACs.

Assume we have encryption key: kEk_{E} and MAC key, kIk_{I}:

  • SSL: E(kE,mS(kI,m)E(k_E, m||S(k_I, m), aka MAC-then-encrypt.
  • IPSec: E(kE,m)S(kI,E(kE,m))E(k_E, m) || S(k_I, E(k_E, m)), aka encrypt-then-mac
  • SSH: E(kE,m)S(kI,m)E(k_E, m)||S(k_I, m), aka encrypt, then MAC on the message, enc-and-mac. ⛔

MAC-then-encrypt: when E,D is rand-CTR mode or rand CBC, then AE. For rand-CTR mode, one-time MAC is sufficient.


  • Galois/Counter Mode, GCM, CTR mode encryption then CW-MAC.
  • CCM: CBC-MAC then CTR mode encryption. All based on AES.
  • EAX: CTR mode encryption then CMAC.

All are nonce-based, aka (key, nonce) cannot be repeated. All support AEAD(authenticated, encrypted with associated data)

Direct construction from PRP, aka OCB:


  • Parallelizable
  • Use P(N,k,0)P(N, k, 0), for Nonce, key, and counter.

It is not widely-used due to the patent.

TLS 1.2

Use MAC-then-encrypt scheme with CTR to avoid replay attack.

Prior to TLS1.1

  • BEAST attack: IV for CBC is predictable.
  • Padding Oracle: leaking information about plaintext during encryption due to illegal padding.

CRC is not secure as the CRC is linear: CRC(mp)=CRC(m)CRC(p)CRC(m \oplus p) = CRC(m) \oplus CRC(p). For WEP, attacker can modify the ciphertext with mpm\oplus p, then use CRCCRC(mp)CRC \oplus CRC(m\oplus p) to get a valid CRC checksum!

Before OpenSSL 0.9.7a, attacker can launch timing attack to differentiate the padding error vs. decryption error.

Key Derivation

A single uniform source key, SK to generate many keys with KDF(Key Derivation Function):

KDF(SK,CTX,L)=F(SK,(CTX0))...F(SK,(CTXL))KDF(SK, CTX, L)= \\ F(SK, (CTX||0)) || ... || F(SK, (CTX||L))

Use kHKDF(salt,SK)k \leftarrow HKDF(salt, SK) from HMAC.

The password-based source key does not sufficient entropy. DO NOT use HKDF, use PKCS#5, aka PBKDF1: H(c)(pwdsalt)H^{(c)}(pwd || salt) with slow hash function.

Deterministic Encryption

The determined encryption may not be CPA secure due to that the same messages yield same ciphertexts.

The solution is to never encrypt the same message twice:

  • use primary key for uniqueness.

CBC with fixed IV is not deterministic CPA secure.

Synthetic IV (SIV)

Let (E, D) be a CPA-secure encryption, and F:K×MRF: K \times M \to R be a secure PRF, Define

Edet((k1,k2),m)=rF(k1,m)ckE(k2,m;r)outputc\begin{align*} E_{det}((k_1, k_2), m) = r \leftarrow F(k_1, m) \\ c \leftarrow kE(k_2, m; r) \\ output c \end{align*}

The det. CPA security + ciphertext integrity \to DAE: deterministic authenticated encryption.

Synthetic IV
Synthetic IV


Synthetic IV Decryption
Synthetic IV Decryption

Then use message with PRF to validate the IV.

Thm: if F is secure PRF, and CTR from FctrF_{ctr} is CPA secure, then SIV-CTR from F, FctrF_{ctr} provides DAE.


Let (E, D) be a securfe PRP. E:K×XXE: K \times X \to X. (E, D) is semantical secure under det. CPA.

Construct EME
Construct EME

Can be 2x slower than SIV.

The Det. Authenticated Enc:

  • Just appends n(e.g 80) bits zeros
  • Verify the decrypted text has n bits zeros.

The idea is to invert the permutation function to get the last n bits with zero. If the PRF is secure, which means the probability to achieve this goal is 12n\frac{1}{2^n}. The encode is secure if 12n\frac{1}{2^n} is negligible.

Tweakable Encryption

Disk encryption:

  • M = C
  • Must be deterministic encryption.

Thus the encryption is a PRP. We can construct the PRP directly from the key: E,D:K×T×XXE, D: K \times T \times X \to X, E(k,t,)E(k, t, \cdot) is an invertible function on X, indistinguishable from random. More concretely using the sector number as T(Tweak).

XTS tweakable block cipher

Let (E, D) be a secure PRP. Define XTS:

Etweak((k1,k2),(t,i),x)=E(k1,mP(N,i))P(N,i)E_{tweak}((k_1, k_2), (t, i), x) = E(k_1, m \oplus P(N, i)) \oplus P(N, i) and NE(k2,t)N \leftarrow E(k_2, t), so we can encrypt

Formatting Preserving Encryption

CC format: bbbb bbnn nnnn nnnc (roughly 42 bits)

  • 6 digit: issuer ID
  • last digit checksum.

Pick 2t1<s2t2^{t - 1} < s \le 2^t, in our case t = 42. Use Luby-Rackoff with F:K×{0,1}t/2{0,1}t/2F': K \times \{0, 1\}^{t/2} \to \{0, 1 \}^{t/2}.

Formatting preserved encryption
Formatting preserved encryption

Better to use 7 rounds.

Given (E, D): K×{0,1}t{0,1}tK \times \{0, 1\}^t \to \{0, 1\}^t, we build (E’, D’): K×{0,...s1}{0,...,s1}K \times \{0, ... s-1\} \to \{0,..., s-1\} Repeat the yE(k,y)y \leftarrow E(k, y) until y{0,..s1}y \in \{0, .. s-1\}.