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 $t \oplus T$ and encrypted data, such as $D \oplus s$, and observe the ack from the server, it can find the D: $checksum(hdr, D) = t \oplus checksum(hdr, D \oplus s )$.

Authenticated Encryption

A cipher(E, D) where:

Note: $\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

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 $B_1, B2$, s.t:

However:

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

Constructions form ciphers and MACs.

Assume we have encryption key: $k_{E}$ and MAC key, $k_{I}$:

• SSL: $E(k_E, m||S(k_I, m)$, aka MAC-then-encrypt.
• IPSec: $E(k_E, m) || S(k_I, E(k_E, m))$, aka encrypt-then-mac ✅
• SSH: $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.

Standards

• 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)$, 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(m \oplus p) = CRC(m) \oplus CRC(p)$. For WEP, attacker can modify the ciphertext with $m\oplus p$, then use $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):

Use $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)}(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 \times M \to R$ be a secure PRF, Define

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

Decryption:

Then use message with PRF to validate the IV.

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

Use PRP

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

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 $\frac{1}{2^n}$. The encode is secure if $\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 \times T \times X \to X$, $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:

$E_{tweak}((k_1, k_2), (t, i), x) = E(k_1, m \oplus P(N, i)) \oplus P(N, i)$ and $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 $2^{t - 1} < s \le 2^t$, in our case t = 42. Use Luby-Rackoff with $F': K \times \{0, 1\}^{t/2} \to \{0, 1 \}^{t/2}$.

Better to use 7 rounds.

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