Cryptography

Symmetric Key Cryptography

Goal: secure communication

1. Protect data on-the-go: no eavesdropping, no tampering
2. Protect data at-rest: encrypted files.

Thoughts

• salt in hashing password is similar to nonce.

Protecting confidentiality (no eavesdropping)

Note that you should use AEAD format if you require the message to be encrypted. Don't use any of the following techniques alone.

Block ciphers are a pair of function $(E,D)$ that takes in $n$ bits of plaintext block and $k$ bits of key, and outputs $n$ bits of ciphertext block and satisfies $D(k,E(k,m))=m$.

Abstract Block Ciphers

1. Pseudo-random function (PRF) $F:K\times X\to Y$. Doesn’t guarantee one-to-one ness
2. Pseudo-random permutation (PRP) $E:K\times X\to X$.
   • The function $E$ is one-to-one.
   • There exists efficient algorithm to evaluate $E(k,x)$ and its inverse $D(k,x)=E^{-1}(k,x)$
   • A block cipher is a PRP.
   • A PRP is a PRF.

Security definition

• Attacker’s power: query our system with ciphered inputs $x$ and observes its output.
• Attacker’s goal: be able to pattern match based on the output to guess the plaintext input.
• A PRF is secure if it is indistinguishable from a random function.
• A PRP is secure if it is indistinguishable from a random permutation.

There are two ways of using keys

• Single-use keys
  • no need for nonce
  • example: OTP (one-time pad)
  • When used correctly, OTP is secure against one-time eavesdropping.
• Multi-use keys
  • need a random nonce or a unique nonce

Two approaches to symmetric encryption

• stream ciphers: $PRG(k\parallel n)\oplus m$.
  • Transmitting a key of the same length as $m$ is a waste of bandwidth. Instead, we use a short key (e.g. 128 bits) and stretch it using a pseudo-random generator.
  • Example: Salsa20/12, Sosemanuk
  • The same key used twice is totally insecure. See how the US deciphered Russia’s encrypted message because of the reuse of OTP. To reuse keys, we concatenate (and transmit) a unique nonce $n$ together with the key. This will ensure that $k\parallel n$ is unique and didn’t violate the OTP guarantee.
• block ciphers:
  • Building block: a secure PRP $E$ which relies on
    1. a key expansion function, which takes the original key $k$, and pass it through a weak pseudo-random function, and produces $n$ variations of key $k_i$.
    2. a round function. On each round, we do $r_{i+1}=R(k_i,r_i)$ where $r_0=m$ and $r_n$ is taken to be our cipher text. $r_i$ all have the same length.
  • General idea: break up the message $m$ into blocks, and encrypt them using our key.
  • Modes:
    • ECB (Electronic Code Book):
      • Perform $E(k,m_i)$ for each block $m_i$.
      • Insecure, because if two blocks are the same in the plaintext, it will result in the same ciphertext.
    • CBC (Chaining-Based Cipher)
      • Take a nonce (IV) and for each plaintext block $m_{i+1}$, we produce ciphertext block $c_{i+1}=E(k_i,c_i\oplus m_{i+1})$ where $c_0=n$.
      • Very sequential.
    • CTR (Control)
      • Perform $m_i\oplus E(k,n\parallel i)$ for each block $m_i$. Essentially, running an OTP encryption for each block.
      • This algorithm is embarassingly parallel.
  • A good way to choose an IV for multi-use keys is to use a fresh random IV. In practice, an encrypted unique IV (e.g. encrypted counter) can be used as a counter might be readily available, e.g. in SSL where it assumes that the underlying network guarantee in-order delivery.
    • Fixed IV can be used for one-time keys.

Protecting integrity (no tampering)

MAC (Message Authentication Code) is a pair of function $(S,V)$ for signing and verification. $S(k,m)$ produces a tag and $V(k,m,tag)$ verifies whether message $m$ has been tampered.

• The shared secret key $k$ is crucial for solving this problem. Otherwise, the attacker can simply recompute the tag.

Security definition:

• Attacker’s power: chosen message attack. Gets the tag = $S(k,m_i)$ for any message $m_i$ sent by the attacker.
• Attacker’s goal: existential forgery. Produces a new, valid message/tag pair $(m,t)$ without asking our system.
• A MAC is secure if the attacker cannot produce a new, valid message/tag pair even allowing to observe any tag from any chosen message.

A secure PRF gives a secure MAC. The problem now is how to create a MAC for big plaintext messages. Three constructions of secure MAC:

• ECBC (encrypted CBC): Similar to CBC mode of block ciphers, but output $E(k^{\prime },c_{n+1})$ where $k^{\prime }$ is different from the original $k$ passed to block cipher, and $c_{n+1}$ is the last cipher text block.
  • The last step of encrypting the CBC output is important.
  • More used in banking and government institutions.
• HMAC (hash-MAC): use a collision-resistant hash function $H$, e.g. SHA-256, and output $H((k\oplus \text{opad})\parallel H(k\oplus \text{ipad}\parallel m))$ .
  • opad is the block-sized outer padding, consisting of repeated bytes of 0x5c, and ipad is the block-sized inner padding, consisting of repeated bytes of 0x36.
  • The hash function $H$ is built based on the Merkle-Damgard paradigm.
    • Basic Idea: break the messages into blocks (bigger than cipher blocks), and chain them through a compression function $h$.
    • Theorem 1: If $h$ is collision resistant, then so is $H$.
    • Theorem 2: If $h$ is a PRF, then HMAC is also a PRF, and therefore a secure MAC.
• PMAC (parallel MAC):
  • Basic Idea: Break the messages into blocks (with the same size as the cipher blocks), pass each of the blocks through a masking function $P$ before applying a secure PRF, i.e. $E(k,m_i\oplus P(k,i))$. XOR all the tags to obtain the tag and output $E(k^{\prime },\cdot )$ where $k^{\prime }$ is different than the original $k$ (like ECBC).
  • The masking function $P$ is important to maintain block order in the original message $m$. Otherwise PMAC will be insecure because attacker can forge $(m_1,m_0)$ given tag for $(m_0,m_1)$.

Combining confidentiality and integrity

Given encryption key $k_E$ and MAC key $k_I$, the correct way to combine them for any $k_E$ and $k_I$ is to send $E(k_E,m)\parallel MAC(k_I,E(k_E,m))$, i.e. encrypt-then-mac.

The following standards provides authenticated encryption with associated data (AEAD).

• CCM: CBC-MAC then CTR-mode encryption
• GCM: CTR-mode encryption then MAC
  • As input it takes a key K, some plaintext P, and some associated data AD and then encrypts the plaintext using the key to produce ciphertext C, and computes an authentication tag T from the ciphertext and the associated data (which remains unencrypted).
  • A recipient with knowledge of K, upon reception of AD, C and T, can decrypt the ciphertext to recover the plaintext P and can check the tag T to ensure that neither ciphertext nor associated data were tampered with.
  • security depends on choosing a unique IV.
• EAX: CTR-mode encryption then OMAC

---

CIA

• Confidentiality: no eavesdropping
• Integrity: no tampering, i.e. some piece of data has not been altered from some “reference version”
• Authenticity: making sure that a given entity (with whom you are interacting) is who you believe to be.
• Availability

Digital signatures (like HMAC) provides both authenticity and integrity.

• In the above section, provides integrity because it’s not possible to create a new valid (m, tag).
• provides authenticity because the only one who shares your symmetric key $k$ should be the (trusted) sender.

---

KDF, or Key derivation function, is $PRF(secret)$.

• secret can be master key, password or passphrase
• PRF can be a cryptographic hash function or block cipher.

Argon2, scrypt, bcrypt are examples of password-based key derivation functions. A key feature of this functions is that they need to be slow enough to defend against brute-force cracking.