CS255 Theorems, Definitions, and Proofs

Foundations

In real-world cryptography, a negligible amount (commonly denoted as $\epsilon$), depending on context is usually something below $2^{-80}$. Being negligible strongly relates to how efficiently computable an algorithm is.

An encryption scheme $(Enc,Dec,Gen)$ with message space $\mathcal{M}$ is perfectly secure if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$ and every ciphertext $c \in \mathcal{C}$, where $Pr[\mathcal{C}=c] > 0$:

$$Pr[\mathcal{M} = m | \mathcal{C} = c] = Pr[\mathcal{M} = m]$$

In other words, the probability of $m$ being a certain $m \in \mathcal{M}$ is conditionally independent of the same probability once you know which ciphertext $c \in \mathcal{C}$ is. Being given the ciphertext of a message doesn’t change at all the probability distribution of which $m \in \mathcal{M}$ is.

Semantic security

Semantic security is defined as the inability for a probabilistic polynomial-time adversary to derive any partial information from the ciphertext with probability above non-negligibility. The advantage is defined as:

$$Adv_{SS}[\mathcal{A},E] := |Pr[W_0]-Pr[W_1]| \in [0,1]$$

Definition: $E$ is semantically secure if for all “efficient” algorithms $\mathcal{A}$, $Adv_{SS}[\mathcal{A},E]$ is negligible.

$$\forall m_0,m_1 \in \mathcal{M}, \exists k \stackrel{R}{\longleftarrow} \mathcal{K} \mid {E(k,m_0)} \approx_p {E(k,m_1)}$$

Semantic security applies to only one key, defines security on multiple-use keys.

Attack Game 2.1 (semantic security). For a given cipher $\mathcal{E} = (E,D)$, defined over $\mathcal{K},\mathcal{M},\mathcal{C}$, and for a given adversary $\mathcal{A}$, we define two experiments, Experiment 0 and Experiment 1. For $b = 0,1$, we define experiment $b$:

For $b = 0,1$, let $W_b$ be the event that $\mathcal{A}$ outputs 1 in Experiment $b$. We define $\mathcal{A}$’s semantic security advantage with respect to $\mathcal{E}$ as:

$$SS\textsf{adv}[\mathcal{A},\mathcal{E}] := | Pr[W_0] - Pr[W_1] |$$.

Definition 2.2 (semantic security). *A cipher $\mathcal{E}$ is semantically secure if* $\forall ``eff” \mathcal{A},\ \textsf{adv}[\mathcal{A},\mathcal{E}] < \epsilon$.

Attack Game 2.2 (message recovery) is defined on AC p.18.

Attack Game 2.3 (parity prediction) is defined on AC p.21.

Attack Game 2.4 (semantic security: bit-guessing version) is defined on AC p.25. It’s different from the semantic security attack game because it doesn’t involve two experiments. Instead there’s only one experiment and the challenger picks $b \xleftarrow[]{R} {0,1}$ at the beginning of the game. The advantage is defined as:

$$SS\textsf{adv}[\mathcal{A},\mathcal{E}] = 2 \cdot \textsf{adv}*[\mathcal{A},\mathcal{E}]$$

Stream Ciphers

Attack Game 3.1 (PRG). [@ac p.46].

Attack Game 3.2 (Unpredictable PRG). [@ac p.64]. Salsa and ChaCha are examples of unpredictable PRGs used in practice.

Attack Game 3.3 (Distinguishing $P_0$ from $P_1$). Widening the definition of a PRG to a wider definition of computational indistinguishability [@ac p.81].

A hybrid argument is a proof technique used pervasively throughout cryptography. If you construct two stream ciphers, one containing an efficient PRG and one containing a truly random deterministic generator function, if it’s impossible to distinguish between the output of the PRG and truly random output, then the cipher must also be secure. An example of hybrid argument begins on AC p.54.

If a PRG maps an $n$-bit seed to an $m$-bit output, its PRG expansion rate is $\frac{m}{n}$.

Block Ciphers

Attack Game 4.1 (block cipher). [@ac p.95] is where an adversary $\mathcal{A}$ attempts to distinguish between the output of a keyed permutation in a block cipher $f \leftarrow E(k \xleftarrow[]{R} \mathcal{K}, \cdot)$ and a completely random permutation $f \xleftarrow[]{R} Perms[\mathcal{X}]$.

Attack Game 4.2 (PRF). [@ac p.130] is the same as the block cipher game but $\mathcal{A}$ is trying to distinguish between the output of a randomly chosen function and the output of the PRF $F$. The random function is implemented by a faithful gnome.

Attack Game 4.2 (permutation vs. function). [@ac p.133].

Attack Game 4.4 (key-recovery). [@ac p.153] an adversary $\mathcal{A}$ queries the challenger $i$ times and gets the encryption under a fixed random key $k$. Then $\mathcal{A}$ tries to guess $k$.

Attack Game 4.5 (domain separation). [@ac p.158].

CPA Security

The CPA security game goes as follows: TODO

A cipher is CPA-secure if under a Chosen Plaintext Attack, pairs of ciphertexts produced by the cipher are indistinguishable from one another to a probabilistic polynomial time attacker. If a cipher is CPA-secure under one encryption, then by definition it is CPA-secure for multiple encryptions using the same key. CPA security is the same as where the key is used more than once. CPA security does not provide any integrity.

Proof that the One-Time Pad is not CPA Secure

We can construct an adversary that can win the CPA Security game against the OTP with non-negligible advantage. The adversary submits one ciphertext to the challenger, $m_0 \in \mathcal{M}$ and receives $c_0 = E(k, m_0)$. Then the adversary submits two more messages, one that’s the same, $m_1 = m_0$, and one that’s different $m_2 \neq m_0$. The adversary then receives $c$. Because the OTP is deterministic, if $c = c_1$, we know with probability 1 that $c = E(k, m_1)$, breaking CPA security.

Attack Game 5.1 (multi-key semantic security). [@ac p.176] is just like the semantic security game (2.1) but the challenger picks a new key for each $i$th message.

Attack Game 5.2 (CPA security). [@ac p.176] is just like game 5.1 but now $\mathcal{A}$ can pick the pair of messages to send (and they receive the encryption of only one of them back).

Attack Game 5.3 (nonce-based CPA security). [@ac p.176] is just like game 5.3 but now $\mathcal{A}$ picks a nonce $\mathcal{N}_i \in \mathcal{N}$ and sends it along with the pair of messages.

Block Ciphers

A block cipher is a cipher that takes a fixed-length input and transforms it into a ciphertext of the same length. A block cipher can be viewed as two functions: $E : \mathcal{X} \rightarrow \mathcal{Y}$ and $D : \mathcal{Y} \rightarrow \mathcal{X}$. Examples of block ciphers are DES and AES.

Block cipher modes of operation

When the block cipher input is great than its block size (pretty much always), you use a mode of operation. Each mode comes with different security properties.

ECB or Electronic Code Book mode is the simplest mode. You split up the message into blocks and encrypt each block. ECB is ridiculously insecure. It is not CPA secure. Do not use it!

CBC or Cipher Block Chaining mode is where the output of a block is XOR’d with the input of the next block. Its use is not recommended, since its not parallelizable it’s much slower than the other modes.

GCM or Galois Counter Mode A nonce-based AEAD cipher that provides data encryption and authenticity. One thing to watch out for is that GCM doesn’t have any nonce-reuse resistance. If you accidentally re-use a nonce, all secrecy guarantees vanish.

Real-world Block Ciphers

The Data Encryption Standard uses a Feistel network converts any arbitrary function into a one-to-one function (a.k.a. an invertible function, or a bijection) on twice the domain. The algorithm inverts itself, so the same hardware can be used for encryption and decryption. Researchers Luby and Rackoff proved that a Feistel network with 3 or more rounds is a secure block cipher. A Feistel network is sometimes called a Luby-Rackoff construction.

The Advanced Encryption Standard is the most widely deployed block cipher in the world. It was created by two Belgian cryptographers as Rijndael, standardized by NIST in 2000. It has a 128-bit block size and comes with 3 key lengths: 128 bits, 192 bits, and 256 bits. It is constructed around an Iterated Even-Mansour Cipher.

When your message isn’t an exact multiple of your block size, what do you do? You apply padding. Padding functions are carefully designed because they must be invertible (so that messages can be encrypted and decrypted) and also one-to-one (so that no two messages when padded become the same message).

A nonce is a value with one constraint: it can never be repeated. For instance, if you use a nonce value in the encryption of a ciphertext, it must be guaranteed that nowhere in your cryptosystem will that nonce be used ever again in the life of the system.

Linear cryptanalysis: A tiny bit of linearity in a cipher can completely break it. For example, there’s a 12 or 16 bit wide part of that’s close to linear. Researchers can use that to recover 14 bits of the key and brute force the remaining $2^{42}$ possibilities.

Collision-resistant Hash Functions {#hash-functions}

Cryptographic Hash Functions

Cryptographic hash functions are similar to hash functions but come with stricter properties. Specifically, a cryptographic hash function must be collision resistant.

Preimage attack

A preimage attack on a is where, if $H : X \rightarrow Y$, for a given $y \in Y$, you can find a given $x \in X$ such that $H(x) = y$. If $x$ is already known, finding another $x’ \in X$ such that $H(x) = H(x’) = y$ is called a second preimage attack, and implies a collision.

SHA

A family of cryptographic hashing algorithms. They use the Merkle-Damgard construction, the Davies-Meyer compression function, and as a block cipher they use SHACAL-2. The SHA family comes in the following outputs:

Why does AES128 exist but there’s no SHA128? Because of the birthday paradox. To have a probability of a collision over $50\%$, you only need to sample at least $O(\sqrt{|\mathcal{T}|})$ hash digests (where $|T|$ is the size of the output space). That would mean an output space of $2^{128}$ would likely result in a collision after $\sqrt{2^{128}} = 2^{64}$ hashes, and $2^{64}$ is not .

[collision-resistance]

Collision resistance

A hash function is collision resistant if the following is true. Let $H : \mathcal{M} \rightarrow \mathcal{T}$ where $|\mathcal{M}| \gg |\mathcal{T}|$. A collision for $H$ is a pair of messages $m_0 \neq m_1$ such that $H(m_0) = H(m_1)$. The advantage is defined as:

$$CR_{ADV}[\mathcal{A},H] = Pr[\mathcal{A}\ \text{outputs collision for}\ H] < \epsilon$$

By the pidgeonhole principle, there must be a lot of collisions because $|\mathcal{T}| \ll |\mathcal{M}|$. However if there’s no uniform PPT algorithm to find the collisions, then H is collision resistant.

The Davies-Meyer compression function is a construction for creating a collision resistant compression function out of a known ideal block cipher. It is defined as: $h(H,m) = E(m,H) \oplus H$. Finding a collision $h(H,m) = h(H’,m’)$ takes $O(2^{n/2}$ evaluations of $(E,D)$.

The Merkle-Damgård transformation is a way of constructing collision-resistant out of fixed-length collision-resistant one-way compression functions. It’s used by most popular hashing algorithms, such as MD5, SHA1, and SHA2. It works by combining each message block first with an IV (initialization vector), then with the output of each previous invocation. The output of the last hashed block is fed to a finalization function, which outputs the hash.

Message Authentication Codes

A MAC, or Message Authentication Code, is a means of proving the authenticity of a message if the two communicating parties share a secret key.

Attack Game 6.1 (MAC security). [@ac p.176] is just like game 5.1 but now $\mathcal{A}$ can pick the pair of messages to send (and they receive the encryption of only one of them back).

HMAC is a MAC that utilizes a CRHF. It is defined as:

$$HMAC(K,m) = H\Big((K’ \oplus opad) \Vert H((K’ \oplus ipad) \Vert m)\Big)$$

CBC-MAC is a MAC that works very similarly to the CBC block cipher mode. It runs the input through a “Raw CBC” circuit, then at the final step runs the output through the PRF again, this time with a separate key. This second key is necessary because otherwise an adversary could get the value of the output of the penultimate block, and since they know both the last block of the plaintext and the output of the penultimate block, they can compute $mi \oplus F(k,m{i-1})$, which is the input to the last round function. The adversary can compute that output too, by submitting that input as a one-block encryption in a separate invocation. Therefore the adversary is able to predict the last block of the ciphertext, leading to a win in the MAC game. CBC-MAC is used heavily in banking and ACH. It is slow because it can’t be computed in parallel.

Authenticated Encryption

Authenticated Encryption combines both confidentiality–in the form of a cipher with CPA security–and integrity–in the form of a MAC. This is the only kind of symmetric cipher you should ever use!

Definition: A cipher provides authenticated encryption, or is AE-secure, if it is 1. semantically secure under a chosen plaintext attack, and 2. provides ciphertext integrity.

A cipher is CCA secure if it prevents a Chosen Ciphertext Attack.

An authenticated cipher fulfills the requirement of ciphertext integrity if an adversary cannot create new ciphertexts that decrypt properly. [@yhae]

MAC-then-encrypt: Not secure. MAC-and-encrypt: Not secure. Encrypt-then-MAC: Secure. Use this always.

Primes and Modular Arithmetic

Number theory is branch of mathematics that studies that properties of integers, primes, and modulo arithmetic. Number theory is the basis of: key exchange protocols, digital signatures, and public-key encryption.

A finite field consists of two groups. $\mathbb{Z}_p$ is the addition group and $\mathbb{Z}_p^*$ is the multiplication group. In a different way, $\mathbb{Z}_p^*$ is the set of nonzero elements in $\mathbb{Z}_p$.

The GCD of $a$ and $b$ is the largest number $k$ such that $k|a$ and $k|b$.

Repeated squaring algorithm

If we want to compute $g^x \in \mathbb{G}$ and $x$ is say $>3000$ digits, simply trying to compute that would take longer than the age of the universe. Fortunately some clever math enables us to compute this core crypto operation efficiently in time $O(log x)$ group operations. Example: to compute $g^{13}$:

$$g^{13} = g^{(1101)_2}$$ $$g^{8+4+1} = g^8+g^4+g^1$$

Miller-Rabin primality test states if $p$ is prime, then the Miller-Rabin test always outputs . If $p$ is composite, the algorithm outputs with confidence probability $1-2^{-t}$.

Abelian groups are groups that maintain commutativity under binary operators.

Bertrand’s postulate states for any $n > 1$, the fraction of n-bit integers that are prime is at least $1/3n$.

A number is composite if it is not prime. A cyclic group $\mathbb{G}$ is (sometimes) a group modulo a number. Two numbers $a$ and $b$ are coprime if their greatest common denominator is 1. This concept is also called relatively prime.

Lagrange’s Theorem states that: $\forall g \in Z_p^* : order_p(g)\ \text{divides}\ p - 1$

Euler’s $\phi$ function is the number of coprime numbers less than a number. For a prime $p$ is $\phi(p) = p - 1$. For a composite $N = pq$, $\phi(N) = N - p - q + 1 = (p-1)(q-1)$.

Euler’s has another theorem (Fermat’s theorem only applied to primes) which states:

$$\forall x \in \mathbb{Z}_N^*,\ x^{\phi(N)} \equiv 1 \in \mathbb{Z}_N$$

[group]

Group

A group is defined as a set of elements, together with an operation performed on pairs of elements (a binary function) such that:

The group operation is known as addition in some cases.

A transformation is injective if it is one-to-one, in other words it preserves distinctness. Every element in the input maps to a unique element in the output. An injective homomorphism is called a monomorphism.

$x \in Z_p$ such that $x^e = c$ in $Z_p$ is called the e’th root of $c$.

Fermat’s little theorem states $a^p \equiv a \mod{p}$ and $a^{p-1} \equiv 1 \mod{p}$.

For modular linear equations of the form:

$$a \cdot x + b = 0 \in \mathbb{Z}_N$$

The solution can be found by:

$$x = -b \cdot a^{-1} \in \mathbb{Z}_N$$

An element is invertible if and only if it is relatively prime (coprime) with $N$.

Trapdoor functions (or one-way functions)

One-way trapdoor functions are easy to compute but hard to invert. Public-key cryptography relies on the assumed difficulty of certain one-way functions, for example prime factorization (RSA) and the discrete logarithm problem. A trapdoor function scheme is a triple $(G,F,I)$, where $(pk,sk) \xleftarrow{R} G()$ is a probabilistic key generation algorithm, and $y \leftarrow F(pk,x)$ and $x \leftarrow F(sk,y)$ are deterministic algorithms. The correctness property is satisfied if:

$$\forall{(pk,sk) \leftarrow G()}, \forall{x \in \mathcal{X}}, I(sk,F(pk,x)) = x$$

In this scheme, $I$ is the trapdoor function. A trapdoor permutation is one in which the domain and range are the same set.

A function $f : {0,1}^n \rightarrow {0,1}^m$ is a $(t,\epsilon)$ one-way function if:

  1. There is an efficient algorithm that for any $x \in {0,1}^n$ outputs $f(x)$.

  2. The function is hard to invert. Meaning for any algorithm $\mathcal{A}$ whose running time is at most $t$:

$$\underset{x\in{0,1}^n}{Pr}\Big[f(\mathcal{A}(f(x))) = f(x)\Big] < \epsilon$$

In other words, when given $f(x)$ as input, algorithm $\mathcal{A}$ is unlikely to output a $y$ such that $f(y) = f(x)$.

Anonymous key exchange

The anonymous key exchange game

The anonymous key exchange game is as follows: you run the anonymous key exchange protocol to generate a shared key $k$ and transcript $T_P$. Then $T_P$ is given to $\mathcal{A}$. Winning the game means $\mathcal{A}$ can guess $\hat{k} = k$, known as the quantity $\textsf{AnonKEadv}[\mathcal{A}, P]$, with non-negligible probability. This is a very weak definition of security.

Plaintext-aware encryption

Encryption where it is impossible for a PPA to generate a valid ciphertext.

Diffie-Hellman Key Exchange

Diffie-Hellman was invented by Whitfield Diffie and Martin Hellman at Stanford in the 1970s. There are three different subtheorems for Diffie-Hellman. [@crypto-se-1493]

The discrete logarithm problem (Dlog): The discrete exponentiation function is a bijection whose inverse is named the discrete logarithm function, denoted $\textsf{Dlog}_g$. The discrete logarithm problem is essentially: given $y$, find $x$ such that $g^x = y$.

The computational Diffie-Hellman problem (CDH): This is the discrete logarithm problem applied to two parties. Essentially: given $y_1 = g^{x_1}$ and $y_2 = g^{x_2}$ (and the adversary does not know $x_1$ and $x_2$), find $g^{x_1 \cdot x_2}$.

The decisional Diffie-Hellman problem (DDH): This is the computational Diffie-Hellman problem applied to a real-world adversarial setting in a rigorous way in order to calculate the advantage. Essentially: given $y_1,y_2,y_3$, decide if they are of the form $y_1 = g^{x_1}$, $y_2 = g^{x_2}$, and $y_3 = g^{x_1 \cdot x_2}$ for some $x_1,x_2$. In two experiments where $y_1,y_2,y_3$ are either randomly selected numbers or results of the above computation, the adversarial advantage is defined as how much better an adversary can guess the correct experiment with chance better than random.

RSA

A problem introduced by Rivest, Shamir, and Adleman that relies on the difficulty of factoring large primes. RSA is “essentially the only known reasonable candidate trapdoor permutation scheme.” [@ac p.398] “Textbook” RSA is defined as $c = m^d \mod{\phi(n)}$.

Attacks on TLS

The Logjam and FREAK attacks were published in 2015 and demonstrated that it was possible to downgrade TLS connections into using export-grade crypto with 512-bit primes.

Random {#symmetric-cryptography-in-javascript}

Symmetric Cryptography in Javascript

A paper that introduces the Stanford JavaScript Crypto Library. I used this library at work a couple years ago in a payments SDK that encrypted payment details on various websites using our company’s public key. https://bitwiseshiftleft.github.io/sjcl/acsac.pdf

Padding oracle side-channel attack

SSL 3.0 was vulnerable to a side-channel attack using padding to guess the next byte of the plaintext.

9

Boneh, Shoup: A Graduate Course in Applied Cryptography,
https://crypto.stanford.edu/~dabo/cryptobook/

Huang: Authenticated Encryption
http://homes.soic.indiana.edu/yh33/Teaching/I433-2016/lec14-AE.pdf

Paŭlo Ebermann: What is the relation between Discrete Log, Computational Diffie-Hellman and Decisional Diffie-Hellman?
https://crypto.stackexchange.com/questions/1493/what-is-the-relation-between-discrete-log-computational-diffie-hellman-and-deci