This is a note of week 4 of the Coursera course Cryptography I. The topic is authenticated encryption against **tampering**: encryption methods that ensure both confidentiality and integrity.

## 1 Introduction

**Chosen Plaintext Attach (CPA)** security cannot guarantee secrecy under active attack. It shouldn’t be used by itself. Only use one of two modes:

- If a message needs integrity but not confidentiality, use a MAC
- If a message needs both integrity and confidentiality, use
**Authenticated Encryption (AE)**.

An authenticated encryption system `(E, D)`

is a cipher where: `E: K * M * N -> C`

as usual but `D: K * C * N -> M union bottom`

where `bottom`

is a unique symbol not in `M`

and says the message is invalid and should be rejected.

Security means that the system provides semantic security under a CPA attack and ciphertext integrity. There are two implications:

- Attacker cannot fool Bob into thinking a message was sent from Alice (but message could be replay).
- It provides security against
**Chosen Ciphertext Attacks(CCA)**.

In chosen ciphertext attack, adversary can choose ciphertext to learn some information about the plaintext. In **chosen ciphertext security**, adversary can do both CPA and CCA:

- can obtain the encryption of any chosen messages
- can decrypt any choosen ciphertext, other than challenge. This is a conservative modeling of real life because in real life, the attacker can decrpty some cipthertext, but not any ciphertext.

## 2 Construction

Before 2000, Cryto libs provide seperate APIs for CPA-secure encryption and MAC (such as HMAC). It is not clear how to combine the two to get AE. For example:

- SSL (MAC-then-encrypt):
`E(ke, m || S(ki, m)`

, create a MAC tag, then encrypt the message and tag. It is vulnerable to CCA for some cipher. - IPsec (encrypt-then-MAC):
`E(ke, m), S(E(ke, m), ki)`

, encrypt first, then add tag of the ciphertext. It provides AE. - SSH (encrypt-and-MAC):
`E(ke, m), S(ki, m)`

, ciphertext and the tag of message. It is insecure because the tag of plaintext is insecure – MAC is designed for integrity, not confidentiality.

The AE theorems are: encrypt-then-MAC always provides AE. MAC-then-encrypt provides AE when the cipher is rand-CTR or rand-CBC mode. For rand-CTR mode, one-time MAC is sufficient.

Some AE standards are `GCM`

, `CCM`

and `EAX`

. All are nonce-based and support **AEAD**. AEAD stands for authenticated encryption with associated data: there are some plaintext but MAC is applied to entire data.

**MAC security** implies that for a given `(m, t)`

, it is impossible to create another `(m, t')`

, i.e., diffrent tags for the same data.

OCB is a direct construction from a PRP that combines CPA secure encryption with a MAC for each block. It is more efficient than the encryption-then-MAC that has two phases for each block.

## 3 Key Derivation

Suppose `F`

is a PRF and a source key `SK`

is uniform in its key space `K`

, then **Key Derivation Function (KDF)** is defined as: `KDF(SK, CTX, L) = F(SK, (CTX||0)) || F(SK, (CTX||1)) || ... || F(SK, (CTX||L))`

. The `CTX`

is a string that uniquely identifies the application so each application has a different set of derived keys. `L`

is the number of generated keys.

In real applications, the source key may not be uniform. The KDF uses an **Extract-then-Expand** paradigm to extract a pseudo-random key from a source key. The extractor uses a **salt** that is a fixed non-secret string choosen at random. An example KDF is `HKDF`

that uses `HMAC(salt, SK)`

as the key to HMAC (the PRF).

A special KDF is **Password-Based KDF (PBKDF)**. Don’t use HKDF because passwords have low entropy that are vulnerable to dictionary attacks. PBKDF defenses attacks using salt and a slow hash function. A standard approach is `PKCS#5`

also called `PBKDF1`

. It iterate hash function many times.

## 4 Credit Card Encryption

A credit card has `16`

digits: `bbbb bbnn nnnn nnnc`

, about `42`

bits. The first 6-digits is the bin(issuer) id. The next 9-digits is the account number. The last digit is a checksum.

The application is an end-to-end encryption the requires the encrypted data looks like a credit card (format-presereving). We need to build a PRP on `{0, ..., s-1}`

where `s`

is the total number of credit cards. It has three steps:

- map given CC# to
`{0, ..., s-1}`

: use Luby-Rackoff with`3`

or`7`

rounds. - apply PRP to get an output in
`{0, ..., s-1}`

: encrypt data repeatly untill the output falls in the target range, the average is two iterations. - map output back to a CC#.