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#.