# 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$:

The adversary computes $m_0,m_1 \in \mathcal{M}$, of the same length, and sends them to the challenger.

The challenger computes $k \xleftarrow[]{R} \mathcal{K}, c \xleftarrow[]{R} E(k,m_b)$ and sends $c$ to the adversary.

The adversary outputs a bit $\hat{b} \in {0,1}$.

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:

SHA256 - ${0,1}^{\leq L} \rightarrow {0,1}^{256}$

SHA384 - ${0,1}^{\leq L} \rightarrow {0,1}^{384}$

SHA512 - ${0,1}^{\leq L} \rightarrow {0,1}^{512}$

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 $m*i \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$.

$Z_p = {0,1,2,…,p-1}$

$Z_p^* = {1,2,…,p-1}$ (the set of invertible elements $\in Z_p$)

$Z_p^

*$ is cyclic, i.e. $\exists g \in Z_p^*s.t. {1,g,g^2,g^3,…,g^{p-2}} = Z_p^*$$Z_p^*$ is a

**cyclic finite group**The order of $Z_p^*$ is $p - 1$

## 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 binary function always returns a result in the group.

One element in the set is the identity element. If the identity element is one of the arguments to the function, the function always returns the other argument unmodified.

Every element of the set has an inverse element. For every element $p$ in group $G$, there exists another element $q$ such that $p\ op\ q = q\ op\ p = e$.

The group operation is associative: $(a\ op\ b)\ op\ c = a\ op\ (b\ op\ c)$.

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:

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

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