Symmetric Key Encryption

Here, we will explore the theory behind symmetric key encryption. This is encryption, where both parties can send secure messages to each other with some shared (and private) key.

Sometimes, we call symmetric key encryption schemes ciphers.

By the end, we will have built the theory behind the symmetric key schemes used in the internet today.

One of the driving principles behind symmetric key encryption is as follows:

Kerckhoffs' Principle

A good cipher scheme should be able to be public, without adversaries being able to use it to decrypt messages. To do this, both parties share a secret key for encryption / decryption which adversaries are assumed to not know.

Secure schemes do not get their security from being poorly defined.

We always have to assume that the crypto designs are public! This is more suitable for large-scale usage of cryptography, and exposes schemes to the public eye so that they can be revised and strengthened.

Historical Ciphers §

Let’s first examine some historical schemes before going into the theory.

For each of the following historical schemes, we will discuss the encryption algorithm, the decryption algorithm, the key-space (set of all possible keys) and secret key, and how to break the scheme.

Atbash Cipher §

The Atbash Cipher substitutes the first letter with the last, the 2nd with the 2nd last, and so on. To encrypt and decrypt, simply swap the letters.

Because there is nothing that is secret, there is no key for this algorithm.

Shift / Caesar Cipher §

The Caeser Cipher replaces each letter by the letter which is $n$ positions away in the alphabet. On a message, this has the effect of “shifting” every letter $n$ positions in the alphabet.

As there are 26 letters in the alphabet, there are 26 possible shifts we could do. Thus, our key-space has a size of 26.

Because the key-space is so small, we can easily brute-force this cipher by trying all possible shifts! Thus, this cipher is suspectible to a brute-force search.

For a secure scheme, it’s necessary that the key space is large! However, a large key space does not imply security.

Scytale Cipher §

The Scytale Cipher stacks letters of the message into $n$ equal-sized rows. Reading the message column-by-column will give you the ciphertext (encryption), and reading the message row-by-row will give you the plain-text (decryption).

As we could have a nearly infinite number of rows, the key-space is arbitrarily large!

That does not make this cipher secure however, as we may be able to recover the key! Starting from the first letter, we can take letters that are offset $i$ positions from the start, to try to form a word. Once we get something that makes sense, we’ll have recovered our key!

Information about our ciphertext can let us reverse engineer the key!

Monoalphabetic Substitution §

The Monoalphabetic Substitution maps every plaintext letter to a different ciphertext character, and substitutes them as so. Using this map, we can encrypt and decrypt our message.

The size of our key-space is $26!$, which is really large! So, brute force search is not possible, but because of the 1-1 mapping, we could do a frequency analysis to recover the key!

Frequency Analysis

Frequency analysis is based off the fact that letters in (gramatically correct) English generally have different usage frequencies. If we know the frequencies of the ciphertext characters, we can guess what the mappings are.

Symmetric Key Encryption §

Formal Definition §

A symmetric encryption scheme is defined by 3 algorithms: Gen, Enc, Dec. Let $M$ be our message space, with $|M|>1$.

1. Gen: The key-generation algorithm (typically probabilistic), which creates a key $k$ according to some distribution (must be probabilistic).
   • $K$ denotes the keyspace, the set of all possible keys.
2. Enc: The encryption algorithm, which takes an input key $k\in K$ and message $m\in M$ to create ciphertext $c\leftarrow En{c}_k(m)$ (could be probabilitic).
   • $C$ denotes the ciphertext space, the set of all possible ciphertexts.
3. Dec: The decryption algorithm, which takes an input key $k\in K$ and ciphertext $c\in C$ to create message $m:=De{c}_k(c)$ (must be deterministic).

Correctness mandates that $De{c}_k(En{c}_k(m))=m$. If this does not hold, our encryption scheme won’t be very practical.

Each of the spaces $K,M,C$ can be given as random variables with probability distributions. Let $Pr[...]$ denote the probability function. Then:

• $Pr[K=k],k\in K$ denotes the probability that the key output by Gen yields $k$.

  Typically, we will assume that $K$ has the uniform probability distribution (each key is of equal probability)

• $Pr[M=m],m\in M$ denotes the probability that the message is equal to $m$, modeling some prior knowledge the adversary may have about the message.
• $Pr[C=c],c\in C$ denotes the probability that the ciphertext is $c$, which is fully determined by the distribution on $K$, $M$, and Enc.
  • $C=En{c}_K(M)$

We assume that the distributions over $K$ and $M$ are independent.

Perfect Secrecy §

We say an encryption scheme over a message space $M$ is perfectly secret if $\forall$ probability distributions over $M$, $\forall m\in M,\forall c\in C$ such that $Pr[C=c]>0$,

$$Pr[M=m|C=c]=Pr[M=m]$$

In other words, the probability that our message is $m$ does not change even if we know what the ciphertext $c$ is. Sometimes, we denote $Pr[M=m]$ as the a priori distribution, and $Pr[M=m|C=c]$ as the a posteriori distribution.

This means that seeing $c$ does not give us any information about the message space!

There are a few equivalent definitions to perfect secrecy.

Equivalence 1

An encryption scheme over a message space $M$ is perfectly secret if and only if $\forall$ probability distribution over $M$, $\forall m\in M$, $\forall c\in C$,

$$Pr[C=c|M=m]=Pr[C=c]$$

In other words, this is saying that the ciphertext is independent of the message (as we can still vary the key $k$).

Proof (One-Way)

Suppose that we have a perfectly secret scheme. We wish to show that $Pr[C=c|M=m]=Pr[C=c]$ is also true.

Fix message distribution $M$, $m\in M$, $c\in C$. By definition, we know that the following must hold by perfect secrecy.

$$Pr[M=m|C=c]=Pr[M=m]$$

and by Baye’s Rule,

$$\begin{array}{r}Pr[M=m|C=c]=Pr[M=m]\\ \frac{Pr[C=c|M=m]P[M=m]}{Pr[C=c]}=Pr[M=m]\\ Pr[C=c|M=m]=Pr[C=c]\end{array}$$

Equivalence 2: Perfect Indistinguishability

An encryption scheme over a message space $M$ is perfectly secret if and only if $\forall$ probability distribution $M$, $\forall m_0,m_1\in M$, and $\forall c\in C$,

$$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$$

Example: Perfect Secrecy Example

An encryption scheme with message space $M$ is perfectly secret if and only if $\forall$ probability distribution over $M$, $\forall m,m^{\prime }\in M$ and $\forall c\in C$, we have

$$Pr[M=m|C=c]=P[M=m^{\prime }|C=c]$$

Prove or refute this.

This is false. For every perfectly secret encryption scheme, we can always choose a distribution on $M$ for which this is false.

By way of contradiction, suppose this is true. Now, choose a distribution such that

$$Pr[M=m]>Pr[M=m^{\prime }]$$

Then, by definition of perfect secrecy,

$$Pr[M=m|C=c]=Pr[M=m]>Pr[M=m^{\prime }]=Pr[M=m^{\prime }|C=c]$$

Which is a contradiction!

Example: Perfect Secrecy Example (2)

An encryption scheme with message space $M$ is perfectly secret if and only if $\forall$ probability distribution over $M$, $\forall m,m^{\prime }\in M$ and $\forall c\in C$, $Pr[C=c]>0$,

$$Pr[K=k|C=c]=Pr[K=k]$$

1. Explain this definition in English.
2. Why is this a bad definition? Describe an encryption scheme that leaks information about the message but still satisfies the definition.

Seeing the ciphertext does not tell us any information about the key.

This is bad, because we could just choose an encryption scheme with only one key, so it’s completely deterministic! For example, we do a shift cipher with only possible key $k=13$. Then, for any ciphertext, $Pr[K=k|C=c]=1=Pr[K=k]$, but we can easily reverse the encryption scheme.

Another solution is, this definition says nothing about the message! So, we could have a scheme that doesn’t do anything to the message (leaves it unencrypted), and generates a random key!

Example: Perfect Secrecy Example (3)

$M=\{0,1,\dots n-1\}$, $K=\{0,1,\dots n-1\}$. Gen() chooses a key at random from $K$, $En{c}_k(m)=m+k$, $De{c}_k(c)=c-k$. Is this perfectly secret?

No. BWOC, suppose it is. Let $n=20$, and let $M$ have the uniform distribution, and let $m=10,c=5$. Then,

$$Pr[M=10|C=5]=0\ne Pr[M=10]=\frac{1}{20}$$

The One-Time Pad §

Here, we describe a perfectly secret symmetric encryption scheme — the One-Time Pad. It works as so:

1. Fix integer $\ell >0$. $M,K,C$ are all equal to $\{0,1{\}}^{\ell }$.
2. Gen: Choose a string from $K=\{0,1{\}}^{\ell }$ according to the uniform distribution
3. Enc: Given $k\in \{0,1{\}}^{\ell }$, $m\in \{0,1{\}}^{\ell }$, output $c:=k\oplus m$.
4. Dec: Given $k\in \{0,1{\}}^{\ell }$, $c\in \{0,1{\}}^{\ell }$, output $m:=k\oplus c$.

Note that the notation $\{0,1{\}}^{\ell }$ stands for binary numbers (digits 0 or 1) of length $\ell$.

Example: One-Time Pad Example

Let’s see an example of the one-time pad. Let $\ell =3$, and suppose we have message $m=011$, key $k=101$.

One time pad encrypts the ciphertext by XORing the binary numbers.

011 XOR 101 = 110

$c=110$! To decrypt, we XOR the ciphertext with our key again.

110 XOR 101 = 011

Theorem: OTP Secrecy

The one-time pad encryption scheme is perfectly secret.

Proof

Recall that a scheme is perfectly secret if for all distributions on $M$, $\forall c\in C$, $\forall m_0,m_1\in M$,

$$Pr[C=c|M=m_0]=Pr[C=c|M=m_1]$$

Fix distribution over $M$, $c\in C$, $m_0,m_1$.

For $c,m$,

$$\begin{array}{rlr}Pr[C=c|M=m]& =Pr[M\oplus K=c|M=m]& \text{OTP Scheme}\\ & =\frac{Pr[M\oplus K=c\wedge M=m]}{Pr[M=m]}& \text{Conditionals}\\ & =\frac{Pr[m\oplus K=c\wedge M=m]}{Pr[M=m]}& \\ & =\frac{Pr[K=c\oplus m\wedge M=m]}{Pr[M=m]}& \\ & =\frac{Pr[K=c\oplus m]Pr[M=m]}{Pr[M=m]}& \text{K, M Independent}\\ & =Pr[K=m\oplus c]=\frac{1}{2^{\ell }}& \end{array}$$

Thus,

$$Pr[C=c|M=m_0]=\frac{1}{2^{\ell }}=Pr[C=c|M=m_1]$$

By perfect indistinguishability, OTP is perfectly secret.

The one-time pad is one of the few perfectly secret algorithms, and in fact, many schemes are variants / equivalent to the one-time pad. Thus, for proofs it’s often a good idea to start from the OTP and modify the scheme from there.

Example: Perfectly Secret Example

Prove or refute: An encryption scheme with message space $M$ is perfectly secret if and only if for every probability distribution over $M$ and every $c_0,c_1\in C$ we have $Pr[C=c_0]=Pr[C=c_1]$.

Not true. To show why, we will construct a perfectly secret scheme that violates this. To do this, we will start from the one-time-pad (this is a good technique).

For message of length $\ell$, let’s take a key of length $\ell +1$, $k||b$ where $k\in \{0,1{\}}^{\ell }$, $b=0,1$ with varying probabilities. Then,

$$c=(m\oplus k)||b$$

$||$ stands for the concatenating of binary strings together.

Because of the biased bit, our ciphertexts do not have the same probability, but no information is released!

Formally, choose any distribution over $M$, $c_0,c_1$, where $c_0=c||0,c_1=c||1$. Then,

$$Pr[C=c||0]=Pr[C=c]\ast Pr[B=0]\ne Pr[C=c]\ast Pr[B=1]=Pr[C=c||1]$$

The one-time pad is a powerful scheme, but it doesn’t come without its flaws:

1. The key length is the same as the message length, so for every bit communicated over a public channel, a bit must be shared privately.
   • This is an inherent problem in perfectly secret encryption schemes! We prove this in the following theorem.
2. Key can only be used once.

This makes it very difficult to use the one-time pad in practice.

Theorem: Limitations of Perfect Secrecy

Let us have a perfectly secret encryption scheme over message space $M$, key space $K$. Then, it must be true that $|K|\ge |M|$.

In most cases, this means that the lengths of the keys must be the same or longer than the lengths of our messages!

Proof

By way of contradiction, assume we have a perfectly secret encryption scheme where $|K|<|M|$.

To obtain our contradiction, we must show that there exists a probability distribution $M$, message $m\in M$, and ciphertext $c\in C$ such that

$$Pr[M=m|C=c]\ne P[M=m]$$

Often, when contradicting perfect secrecy, we use the uniform distribution on $M$.

Let $M$ have the uniform distribution. By perfect secrecy, for $m\in M$, $c\in C$,

$$Pr[M=m|C=c]=P[M=m]$$

Let’s do a brute force search over the key-space. Let $\mathbb{M}(c)$ be the set of all messages $De{c}_K(c)$. Because the decryption is deterministic, we have that $|\mathbb{M}(c)|\le |K|<|M|$ (it can be smaller if multiple keys decrypt to the same message).

So, there exists some message $m^{\ast }\in M$ that is contained in $M$ but not $\mathbb{M}(c)$. Choose this message instead. Then,

$$Pr[M=m^{\ast }|C=c]=0\ne P[M=m^{\ast }]=\frac{1}{|M|}$$

This is a contradiction! So, our scheme cannot be perfectly secret.

Shannon's Theorem

Let Gen, Enc, Dec be an encryption scheme with message space $M$, for which $|M|=|K|=|C|$. Then, the scheme is perfectly secret if and only if:

1. Every key $k\in K$ is chocsen with equal probability $1/|K|$ by Gen.

2. For every $m\in M,c\in C$, there exists a unique key $k\in K$ such that $En{c}_k(m)\to c$.

Note that this only applies when $|M|=|K|=|C|$! If this condition is not true, then we cannot use Shannon’s Theorem.

Example: Shannon's Theorem Example

Let $M=\{0,\dots n-1\},K=\{0,\dots n-1\}$. Let $Gen()$ choose a key at random.

• $En{c}_k(m)=m+k\mathrm{mod}n$
• $De{c}_k(c)=c-k\mathrm{mod}n$

Shannon’s theorem applies here! First, we know by assumption that all keys are chosen uniformly.

We also show that for $m,c$, we explicitly can solve for a single $k$ such that $En{c}_k(m)\to c$. We find

$$m+k\mathrm{mod}n=c⟹k=c-m\mathrm{mod}n$$

The Computational Approach §

Motivation §

Shannon’s Theorem asserts that for correct schemes that are perfectly secret, $|K|=|M|$. Thus, achieving perfect secrecy is, in many cases, unpractical for many real world situations.

Here, we explore a more relaxed definition for security, known as the computational approach. The computational approach only requires the following:

• Security is only guaranteed against efficient adversaries that run for some feasible amount of time.
  • Efficient adversaries are adversaries that can run in polynomial time (we also call them PPT adversaries).
• Adversaries can potentially succeed with some very small probability.
  • Adversaries can succeed, but they would need to run in non-polynomial time— they would run out of time if they were running in non-polynomial time.

We formally define these notions below.

Formal Definitions §

Under the computational approach, schemes now have an additional parameter called the security parameter ($n$).

Prior to running our scheme, we can set our security parameter, which tells us the run time of the adversary and its success probability as functions of $n$. This gives a sort of guarantee against adversaries running in polynomial time.

We can think of the security parameter as the length of the key.

Efficient Adversaries §

An adversary is efficient if they are in polynomial time (PPT). To be in polynomial time means that there exists some polynomial $p$, such that the adversary runs for time at most $p(n)$ when the security parameter is $n$.

Example: Polynomial Time Functions

• $2n^2+3n+5$ is a polynomial function in $n$

• $\log n^{\log n}$ is not a polynomial function in $n$

• $2^{\sqrt{\log n}}$ is a polynomial function in $n$

To know if a function is polynomial, it may help to take the log, and see if this is bounded below or above by $\log (n)$ (this is the logarithm of a polynomial!)

Given a security parameter $n$, to say an adversary is running in time $p(n)=n^2$ means that for $n$, the adversary has that amount of time to run.

Negligible Probability §

A small probability of success means we have a negligible probability. A function $f$ is negligible if for every polynomial $p$, and sufficienly large $n$, it holds that

$$f(n)<\frac{1}{p(n)}$$

In other words, as $n\to \infty$, the function is smaller than all polynomial functions.

$$f(n)<\frac{1}{n^c}\forall c\in \mathbb{R}$$

The product of any polynomial with a negligible function is a negligible function!

To know if a function is negligible, take its reciprocal and see if its super-polynomial or not! If its reciprocal is a super-polynomial, then $f$ is negligible.

Example: Negligible Functions

• $1/2^n$ is negligible
• $1/\log n$ is not negligible
• $1/2^{\sqrt{n}}$ is negligible
• $1/n^2$ is not negligible

Practical Implications of Computational Security

Why do we define computational security as so?

Let’s say for key size $n$, any adversary running in time $2^{n/2}$ breaks the scheme with probability $1/2^{n/2}$. Meanwhile, Gen, Dec, Enc take time $n^2$.

If $n=128$, then

• Gen,Enc,Dec take time $16,384$
• Adversary runs in time $2^{64}=10^{18}$!

If $n=256$, then

• Gen,Enc,Dec take time $65,536$

• Adversary runtime is multiplied by $2^{64}$! Becomes $2^{128}\approx 10^{38}$.

This makes it really easy to adjust schemes to the adversary time! As adversary capabilities increase, we can shift our security parameter so that they will continue to be unable to break our scheme!

Private Key Encryption §

A private-key encryption scheme is a tuple of probabilistic polynomial-time algorithms Gen, Enc, Dec such that:

1. Gen takes security parameter $1^n$ (1 repeated $n$ times), and outputs a key $k$ denoted $k\leftarrow Gen(1^n)$. WLOG, assume $|k|\ge n$.
2. Enc takes a key $k$, message $m\in \{0,1{\}}^{\ast }$, and outpus a ciphertext $c$, $En{c}_k(m)\to c$.
3. Dec takes a key $k$, ciphertext $c$, and outputs a message $De{c}_k(c)\to m$.

By correctness, we mandate that for every $n$, every $k$, and every $m$, it holds that $De{c}_k(En{c}_k(m))=m$ (the scheme must be deterministic).

Security in the Presence of an Eavesropper (EAV) §

To define security under the computational approach, we think of an experiment.

Consider a private-key encryption scheme $\Pi =(Gen,Enc,Dec)$, any adversary $A$, and any value $n$ for the security parameter. We define a random variable experiment

$$\text{Experiment}Priv{K}_{A,\Pi }^{eav}(n)$$

Where the adversary and our challenger play the following game:

1. The adversary chooses two messages $m_0,m_1$ from the message space.
2. The challenger will generate a key $Gen(1^n)\to k$ and choose $b=0\text{or}1$ randomly. Based on $b$, the challenger then encrypts one of the messages $En{c}_k(m_b)\to c$.
3. The adversary receives the ciphertext $c$, and now has to guess $b^{\prime }\in \{0,1\}$, denoting which message they think was encrypted.
4. We check if the adversary was right, and set the random variable to 1 if the adversary was right ($b^{\prime }=b$), 0 if wrong ($b^{\prime }\ne b$).

We say $\Pi$ has indistinguishable encryptions in the presence of an eavesdropper (EAV-secure) if $\forall$ PPT adversaries $A$, $\exists$ a negligible function $negl$ such that

$$Pr[Priv{K}_{A,\Pi }^{eav}(n)=1]\le \frac{1}{2}+negl(n)$$

In other words, the adversary has close to a 50/50 chance of correctly guessing the message (as there are only 2 messages to choose from), with some negligible offset that drops to 0 quickly as $n\to \infty$! This tells us that they don’t really get any information about the message!

This is a weak notion of security and is not very useful in practice!

Similar to the different definitions of perfect secrecy, computational security also has equivalent definitions— though these other definitions are outside of the scope of this class.

Pseudorandom Generator (PRG) §

Here, we define a pseudorandom generator. These can be used to create schemes that are computationally secure, with $|K|<|M|$ (making the scheme more practical).

Recall that this wouldn’t be possible for perfect secrecy!

A pseudorandom generator (PRG) is a deterministic algorithm $G$, that takes as input a short random seed $s$, and outputs a longer string $G(s)$. It has the property that no polynomial time algorithm can “distinguish” $G(s)$ from a truly random string $r$, despite being a deterministic function.

What this generator essentially does is “stretch” a small amount of true randomness ($s$) to a larger amount of pseudorandomness, without compromising on security.

To have a PRG, we also define a game.

• Ideal World: We sample a truly random bit string $r$ of length $\ell (n)$, $r\in \{0,1{\}}^{\ell }$. It must hold that $\ell (n)>n$, where $\ell (n)$ is called the expansion factor ($G$’s output must be longer than the input).
• Real World: We sample a truly random bit string $s$ of length $n$, and compute $G(s)$.
• We give either the ideal world or real world bit string to $D$, the distinguisher. For a PRG, any efficient distinguisher cannot tell which “world” the string is from (if it got $r$ or $G(s)$).

Formally, the probability that the distinguisher guesses the ideal world is about the same in either case.

$$\left|Pr[D(r)=1]-Pr[D(G(s))=1]\right|\le \text{Negligible}$$

This means that the distinguisher has no way of really knowing which is the ideal world!

Here, $G$ only gets $n$ bits of true randomness, but need to “stretch” that randomness to $\ell (n)$ bits!

Given a PRG, we can only assume the following:

• If our input random string is uniform, the PRG’s output will also be uniform.

Example: PRG Proof (1)

Let $G$ be a PRG where $|G(s)|=|s|+1$.

Let $G^{\prime }(s)=G(s||\bar{s})$, where $\bar{s}$ is the negation of $s$. Is $G^{\prime }$ a PRG?

We know that $s||\bar{s}$ is not uniformly random, as $\bar{s}$ depends on $s$. Because the input is not random, we cannot assume $G^{\prime }$ is a PRG.

Let’s construct a pathological example. Let’s construct $G$ from another PRG, $\tilde{G}$, which is a function from $\{0,1{\}}^n\to \{0,1{\}}^{2n+1}$ as so:

$$G(s_1||s_2):=\tilde{G}(s_1)||\tilde{G}({\bar{s}}_2)$$

We must show that $G$ is a PRG, and $G^{\prime }$ is not a PRG. Let’s start with $G$.

1. $G$ is a PRG, as if $s_1||s_2$ forms a truly random string, then $s_1,s_2$ are random, and ${\bar{s}}_2$ is also random. So, $\tilde{G}$, being a PRG on a uniformly random input, outputs a uniformly random output.
2. $G^{\prime }(s)=G(s||\bar{s})=\tilde{G}(s)||\tilde{G}(s)$, but by the deterministic nature of PRGs, we have the same string concatenated with itself! So, the output does not have a uniform distribution.

Formally, define a distinguisher $D$, which get some input $w$. We choose a polynomial time algorithm for $D$ which lets it distinguish randomness from the PRG with non-negligible probability.

One algorithm $D$ could do is split the string in half, return 1 (PRG output) if the halves are the same, 0 otherwise. With this algorithm, we have the following probabilities:

• $Pr[D(G^{\prime }(s))=1]=1$, as we will always be able to tell the PRG as its two halves are always the same (shown above)
• $Pr[D(r)=1]=\frac{1}{2^{2n+1}}$, as for any string in the first half we need to match it in the second half.

So,

$$|Pr[D(G^{\prime }(s))=1]-Pr[D(r)=1]|=1-\frac{1}{2^{2n+1}}\ge \frac{1}{2}$$

This is not a negligible function, as when $n$ increases this goes to 1! So, we can define a constant function $1/2$ which this is greater than as $n\to \infty$.

So, we have a $D$ that breaks the security of $G^{\prime }$

Using PRGs, we can create a secure fixed-length encryption scheme that is secure, and breaks the Shannon bound. Let $G$ be a PRG taking $\{0,1{\}}^n\to \{0,1{\}}^{\ell (n)}$, $\ell (n)>n$, and let $K=\{0,1{\}}^n,M=\{0,1{\}}^{\ell (n)}$.

• Gen outputs a random key $k\in K$.
• Enc takes the key, runs it through the pseudo-random generator to get a pad $G(k)\to p\in \{0,1{\}}^{\ell }$. It then XORs the output with the message to get our ciphertext $c$.
• Dec reverses this by XORing the same pad with the ciphertext.

This is a computationally-secure scheme, and $|K|<|M|$, breaking the Shannon bound! We can prove this below.

Proof

We wish to show that given $G$ is a PRG, our scheme is EAV-secure. So, $\forall$ PPT adversaries, $\exists negl$ such that

$$Pr[Priv{K}_{A,II}^{eav}(n)=1]\le \frac{1}{2}+negl(n)$$

In many cryptographic proofs, we cannot prove the definition directly. So, we prove by contradiction or contrapositive.

So, we will show that if $\exists$ PPT adversaries such that $\forall negl$,

$$Pr[Priv{K}_{A,II}^{eav}(n)=1]>\frac{1}{2}+negl(n)$$

Then $G$ cannot be a PRG.

Let $A$ be this adversary. Then, $\exists$ PPT distinguisher such that there exists a non-negligible function ${\ell }^{\prime }(n)$, where

$$|Pr[D(r)=1]-Pr[D(G(s))=1]|\ge {\ell }^{\prime }(n)$$

Given this distinguisher, we will contruct another distinguisher against the PRG, that uses $A$ as a subroutine.

This is based off proof reduction! The idea that if one algorithm solves the boolean satisfiability problem, then it can be used to solve all NP-complete problems in polynomial time!

• $D$ is a distinguisher that needs to take a string $w\in \{0,1{\}}^{\ell (n)}$, and needs to return 0, 1 guessing what world the string came from. It contains and can use $A$
• $A$ is an adversary that will first send $m_0,m_1$ to the challenger ($D$). It expects a ciphertext, and guesses if $c$ is an encryption of $m_0$ or $m_1$.

This is almost an algorithm! We just need to fill it in with a few steps.

1. How does $D$ generate the challenger ciphertext for $A$?
   • $D$ randomly chooses a $b\in \{0,1\}$, and sends back $w\oplus m_b$.
2. After getting the response from $A^{\prime }$, $b^{\prime }$, what response does $D$ output?
   • If $b=b^{\prime }$, then return 1
   • If $b\ne b^{\prime }$, then return 0

We now analyze the probabilities to show that our PRG is not actually a PRG.

1. The probability $Pr[D(G(s))=1]$ is the probability $A$ guesses correctly if $w=G(s)$. This is
   $$Pr[Priv{K}_{A,II}^{eav}(n)=1]\ge \frac{1}{2}+negl$$
2. The probability $Pr[D(r)=1]$ is the probability that $A$ guesses the one-time pad, which (by perfect secrecy) is
   $$Pr[D(w)=1]=\frac{1}{2}$$
   As no matter what $A$ guesses, it cannot do better or worse by perfect secrecy.

So,

$$|Pr[D(G(s))=1]-Pr[D(r)=1]|\ge \frac{1}{2}+\rho (n)-\frac{1}{2}=\rho (n)$$

As $\rho (n)$ is non-negligible, $D$ breaks the security of the PRG. Because $A$ is a PPT, $D$ is also a PPT as it uses $A$, we are done.

However, this compuationally secure scheme is not very practical.

• The length of the message is fixed
• The scheme can only be used once, as if the same key is used twice, the scheme would no longer be secure!

Stream Ciphers §

To make something that can be used in practice, recall that for two PRGs, inputting the output of one into another will still yield a pseudo-random string! So, if we chain these PRGs together, we’ll get a “stream” of unique keys we can encrypt with.

This is the idea behind the stream cipher.

• Let $G$ be a PRG that takes as input $\{0,1{\}}^n$ and outputs $\{0,1{\}}^{n+1}$.
• Let $s_0$ represent some initial state, which is a truly random key.

Both the sender and receiver will store a state, which will let them generate a pseudorandom stream of 0s and 1s to use in a one-time pad. For every application of the PRG, the 1st bit will be used for the one-time pad, and the remaining bits will be used as the next state.

$$\begin{array}{r}{s}_0=k\\ s_{i+1}=G(s_i{)}_2,\dots G(s_i{)}_{n+1}\\ {\text{pad}}_{i+1}=G(s_i{)}_1\end{array}$$

Then, for some message, we can generate the ciphertext for the $i+1^{th}$ bit as

$$c_{i+1}=m_{i+1}\oplus {\text{pad}}_{i+1}$$

Both the sender and receiver are in sync (so long as they have the same initial key), so the receiver can decrypt the ciphertext with the same pad!

Because the stream cipher does not use the same key, we have a secure scheme that can be used to send multiple variable-length messages! However, this requires that the sender and receiver are in sync— if any bit is dropped, then they won’t be in sync and the decryption will fail.

Key Idea

It’s possible to use a PRG to create a practical encryption scheme, with the cavaet that the sender and receiver need to share a state!

Chosen Plain-Text Attack Security (CPA) §

Computational security was a bit of a weak and limited notion. Here, we define a notion that can actually be used in practice.

This notion can be used for multiple messages, and is a very standard notion of security!

Consider a private-key encryption scheme Gen, Enc, Dec, any adversary $A$, and any value $n$ for the security parameter.

We define the following experiment, $Priv{K}_{A,II}^{cpa}(n)$.

1. The challenger (sender / receiver) will generate some key $k=Gen(1^n)$.
2. The adversary gets oracle access to the encryption algorithm, denoted $A^{En{c}_k(\cdot )}$. This means that $A$ does not know $k$, but gets to use the encryption scheme. They’re allowed to choose a plaintext message $m$ and get back a ciphertext $c$, for as many messages as they want (in polynomial time).
3. When the adversary has sampled enough input-output pairs, it sends two messages $m_0,m_1$ to the challenger.
4. The challenger picks a bit $b=\{0,1\}$ at random, and based on this chooses one of the messages to encrypt $En{c}_k(m_b)=c$.
5. After receiving the ciphertext, $A$ gets oracle-access to the encrpytion scheme to query again.
6. When ready the adversary outputs $b^{\prime }$, guessing what message the challenger chose.
7. $Priv{K}_{A,II}^{cpa}(n)=1$ if $b^{\prime }=b$, and 0 if $b^{\prime }\ne b$.

We say our scheme has indistinguishable encryptions under a chosen-plaintext attack (CPA-secure) if for all PPT adversaries $A$, there exists a negligible function such that

$$Pr[Priv{K}_{A,II}^{cpa}(n)=1]\le \frac{1}{2}+negl(n)$$

While this is a one-shot game, we can prove that CPA-security gives us security for multiple encryptions!

Theorem

Any adversary $A$ that has indistinguishable encryptions under a CPA-attack also has indistinguishable multiple encryptions under a chosen plain-text attack!

This means that we can use CPA-secure schemes with the same key, as many times as we want while maintaining security!

Info

If the adversary $A$ is allowed to query the oracle, what is stopping the adversary from just querying $m_0,m_1$? They could just query $m_0,m_1$ and see what the ciphertext is!

Because of this, any scheme that satisfies CPA-security must necessarily be probabilistic, meaning when we call the oracle, the ciphertext for any given message will be different.

This motivates the following theorem.

Theorem

If $II$ is an encryption scheme where Enc is a deterministic function of the key and the message, then $II$ cannot be CPA-secure.

Proof

Let $A$ be an adversary.

1. $A$ chooses two messages $m_0,m_1,m_0\ne m_1$.
2. $A$ query its oracle $m_0$ to get $c_0$.
3. $A$ sends $m_0,m_1$ to the challenger and gets back $c$.
4. If $c_0=c$, $A$ predicts $b^{\prime }=0$. Otherwise, $A$ predicts $b^{\prime }=1$.

Clearly, $A$ is efficient as it only queries the oracle once, which is polynomial.

Furthermore, $A$ will always win the game with probability 1, which is greater than $1/2+negl(n)$.

Pseudorandom Functions §

We will use pseudorandom functions to create schemes that are CPA-secure! As it does not make sense for a fixed function to be pseudorandom, we will define pseudorandomness on our selection from a set of fixed functions.

A keyed function $F:\{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ ($F_k(x)$) is a two-input function, where

1. The first input is the key, denoted $k$.
2. The second input is $x$.

We say $F$ is efficient if there is a polynomial-time algorithm that can compute $F(k,x)$ given $k$ and $x$. We will only be interested in efficient pseudo-functions.

$F(\cdot ,\cdot )$ is public and polynomial-time efficient.

Let $D$ be a PPT distinguisher. We define the following experiment:

1. $D$ gets access to an oracle $O$ which is either equal to $F_k$ ($k$ chosen at random) or $f:\{0,1{\}}^n\to \{0,1{\}}^n$, a uniformly chosen random function. ($D$ does not know which is the case).
   • $f$ is a function with input set $\{0,1{\}}^n$, and for each input one output in $\{0,1{\}}^n$. Then, to choose $f$ uniformly at random, uniformly assign one output from $\{0,1{\}}^n$ to each input. After being chosen, it then behaves deterministically.
2. $D$ may query the oracle for any $x$, at which point the oracle returns $O(x)$.
   • Because the oracle computes a deterministic function, it returns the same result if queried twice on the same input.
3. $D$ may interact freely with the oracle, denoted $D^{O(\cdot )}(1^n)$, choosing its queries based on the outputs (as long it runs in polynomial time).
4. $D$ returns 1 if it thinks the oracle is our pseudorandom function $F_k(x)$, 0 otherwise.

Then, a keyed function $F:\{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ is pseudorandom if for all PPT distinguishers $D$, there exists a negligible function such that

$$|Pr[D^{F_k(\cdot )}(1^n)=1]-Pr[D^{f(\cdot )}(1^n)=1]|\le negl(n)$$

In other words, for any polynomial-time distinguisher, the probability that the distinguisher guesses that our function is the pseudorandom function (1) is negligible.

$F_k$, for uniform key $k$, is indistinguishable from a function chosen uniformly at random from the set of all functions with the same domain and range ($f(\cdot )$).

To disprove that a function is a PRF, the question is: can we find a set of inputs whose outputs are correlated?

Example: Pseudo-Random Functions (Disproof)

Let $F$ be a PRF. For $F^{\prime }:\{0,1{\}}^{n-1}\to \{0,1{\}}^{2n}$, show if $F^{\prime }$ is a PRF.

$$F_k^{\prime }(x)=F_k(0||x)||F(x||1)$$

Suppose we plug in the following values of $x$.

$$\begin{array}{r}{F}_k^{\prime }(0^{n-1})=F_k(0^n)||F(0^{n-1}1)\\ F_k^{\prime }(0^{n-2}1)=F_k(O^{n-1}1)||F_k(O^{n-2}{1}^2)\end{array}$$

Notice how the second half of the first input, and first half of the second input are the same! Thus, these two inputs have correlated outputs, and the distinguisher could use this fact to determine if it has the PRF or not. It can query these two inputs, and return 1 if these halves are the same!

With this attack,

$$|Pr[D^{F_k(x)}(1^n)=1]-Pr[D^{f(x)}(1^n)=1]|=\left|1-\frac{1}{2^n}\right|$$

The probability for the truly random function comes from the fact that we need all $n$ bits of half of the second output to match the first, and under a uniform distribution, this is probability $1/2^n$.

Example: Pseudo-Random Functions (Proof)

Let $F$ be a PRF. For $F^{\prime }:\{0,1{\}}^{n-1}\to \{0,1{\}}^{2n}$, show if $F^{\prime }$ is a PRF.

$$F_k^{\prime }(x)=F_k(0||x)||F(1||x)$$

This is a PRF! To see why, think of the input/output table for $F_k^{\prime }$.

Because of the bit in front, we’re partitioning the input space of $F_k$! So, there will never be any collision where the same query $x$ yields correlated outputs. Thus, this PRF is secure.

Show that the space of inputs to $F$ are partitioned, and as $F$ is a PRF there will be no collisions. An intuitive argument is acceptable for this course.

CPA-Security with PRFs §

Like with PRGs, we will now use PRFs to construct a CPA-secure scheme.

Let Gen output a random key $k$, chosen uniformly randomly. Also, let $F_k(x)$ be a pseudorandom function.

1. Choose a random string $r\in \{0,1{\}}^n$.
2. Use the random string $r$ with $F_k(x)$ to create a pad, $F_k(r)=w$.
3. With this pad, XOR it with our message to get $c_2$. Let $c_1$ be our random string. Then, our ciphertext is given as $c=c_1||c_2$.
   • We need the random string in the ciphertext to be able to decrypt our message.

Intuitively, this is secure because despite knowing $r$, we don’t know $k$, and the security of PRFs guarantee that without knowing $k$, we cannot differentiate $F_k(x)$ from a random function!

Theorem

If $F$ is a pseudorandom function, then the construction above is a CPA-secure private-key encryption scheme for messages of length $n$.

Proof

We will prove this via contrapositive (as typical of these proofs). Suppose the construction above is not CPA-secure. Then, $\exists$ some PPT $A$ and non-negligible function $\rho$ such that

$$Pr[Priv{K}_{A,II}^{cpa}(n)=1]\ge \frac{1}{2}+\rho (n)$$

We wish to show that $F$ is not a pseudo-random function. In other words, that $\exists PPT$ distinguisher and non-negligible function $f^{\prime }$ such that

$$|Pr[D^{F_k^{\prime }(\cdot )}(1^n)=1]-Pr[D^{f^{\prime }(\cdot )}(1^n)=1]|\ge f^{\prime }(n)$$

Define a distinguisher $D$, who has $A$ within it. $D$ is playing a PRF game; $A$ is playing a CPA-security game.

• $D$ gets an oracle $O$, talks to the oracle, and returns 0/1 indicating if it thinks the oracle is the PRF.
• $A$ can make queries to the oracle, sends $m_0,m_1$ to get $c$, makes queries again, and then guesses 0/1 indicating what message it thinks $c$ is from.

So, $D$ would do the following:

1. First, $D$ gets an oracle $O$ which is either $F_k$ or $f$.
2. $D$ will now choose a random string $r\in \{0,1{\}}^n$.
3. $A$ will be allowed to query the encryption scheme as needed. To query, $D$ will take $A$’s message, query $O(r)$, and return $(r||m\oplus O(r))$ to $A$.
4. $A$ now take $m_0,m_1$, and send them to $D$.
5. $D$ will randomly choose $b\in \{0,1\}$, choose a random message based on this, and encrypt this as shown above. It sends this back to $A$.
6. $A$ will return an answer $b^{\prime }$. If $b^{\prime }=b$, then output 1. Otherwise, output 0.

In the case that $O=F_k$,

$$Pr[D^{F_k}(1^n)=1]=Pr[Priv{K}_{A,II}^{cpa}(n)=1]\ge \rho (n)$$

As it is the same probability as when $A$ guesses correctly.

In the case that $O=f$,

$$Pr[D^f(1^n)=1]=Pr[Bad]+(1-Pr[Bad])\frac{1}{2}\le Pr[Bad]+\frac{1}{2}\le \frac{q(n)}{2^n}+\frac{1}{2}$$

As this is the one-time pad game with probability 1/2, but there is exactly 1 case where $A$ can guess correctly, which is if the same $r$ is chosen when generating the challenger ciphertext and in a CPA-query. In this event, $A$ guesses correctly 100% of the time.

$q(n)$ stands for the number of CPA queries, and gives us a bound on this event happening.

$$|Pr[D^{F_k}(1^n)=1]-Pr[D^f(1^n)=1]|\le \frac{1}{2}+\rho (n)-\frac{1}{2}-negl$$

And as a non-negligible minus a negligible is non-negligible, this is $\le$ some non-negligible function. Thus, our function is not a PRF.

Pseudo-Random Permutations §

A pseudorandom permutation is exactly the same as a pseudorandom function, except that for every key $k$, $F_k$ must be a permutation and it must be indistinguishable from a random permutation.

Permutation means, every function $F_k$ is a bijection! So, on the truth table, every input $x$ has a 1-1 mapping to a unique output, where every output has an input!

So, for the input-output table, each output $y\in \{0,1{\}}^n$ appears exactly once!

This means that pseudo-random permutations are invertible! Furthermore, if you know the key, it should be possible to efficiently invert it!

Using pseudo-random permutations, we can define the following scheme.

1. The challenger chooses a random key $k$ from the key-space. This chooses a pseudo-random permutation.
2. The adversary gets oracle $O$, which is either the pseudo-ranodm permutation $F_k$, or a truly random permutation $f(x)$.
   • A truly random permutation is one where for each output $y$, it randomly gets assigned to one input $x$!
3. The adversary can query the oracle in the forward and backward direction, which is either $f(x),f^{-1}(y)$, or $F_k(x),f_k^{-1}(y)$.
4. The adversary guesses what function the oracle is.

A strong pseudo-random permutation (PRP) is one in which any efficient adversary cannot tell which world the oracle belongs to.

$$|Pr[A^f()=1]-Pr[A^{F_k()}()=1]|\le negl$$

There are $(2^n)!$ possible permutations from $\{0,1{\}}^n\to \{0,1{\}}^n$.

PRPs are also known as block ciphers.

Previously, we created a CPA-secure encryption scheme for 1 block messages. We can now use PRPs to create a scheme that can encrypt multiple blocks!

Let message $m$ have the following blocks $m_1,m_2,m_{\ell }$. How can we encrypt this message?

• One way we could do this is by running the 1-block scheme $\ell$ times! This is okay in terms of security, but wastes a lot of resources!
  • We need to generate a random key every time, which could be costly
  • Every block needs the random ciphertext concatenated with it, doubling the size of each ciphertext block! This uses a lot of data.

The various ways we can use PRPs to encrypt blocks of messages are known as modes of operation. They are described below.

1. Electronic Code Block (ECB): Encrypt each message block with the PRP, and concatenate them together.

   $$F_k(m_1)||F_k(m_2)||F_k(m_3)||\dots$$

   To decrypt, simply run the inverse of the function on each ciphertext block.

   $$F_m^{-1}(c_1)||F_m^{-1}(c_2)||F_m^{-1}(c_3)||\dots$$

   This is not a secure scheme, as it will give us the same output for the same input. However, it is intuitive and makes a lot of sense!

2. Cipher Block Chaining (CBC): Start with some initialization vector $IV$, a truly random bit-string. Then, for every block, we can compute its ciphertext as

   $$F_k(m_i\oplus c_{i-1})=c_i{c}_0=IV$$

   In other words, to get our next ciphertext, we XOR the block with the previous ciphertext and run it through the PRP.

   To decrypt, run the inverse on the ciphertext, and XOR it with the previous ciphertext.

   $$F^{-1}(c_i)\oplus c_{i-1}=m_i$$

3. Output Feedback (OFB): Start with some initialization vector $IV$. Then, to generate the ciphertext, we will first generate keys by repeatedly running the $IV$ through the PRP.

   $$F_k(z_{i-1})=z_i{z}_0=IV$$

   Then, we XOR the key with our message block to get our ciphertext.

   $$z_i\oplus m_i=c_i$$

   To decrypt, we repeat the key-stream and XOR each key with the ciphertext.

   $$z_i\oplus c_i=m_i$$

4. Counter (CTR): Start with some random number which will serve as a counter, $ctr$. Then, to generate the ciphertext, we will run $ctr+i$ through the PRP and XOR the output with the message. Increment counter after each message block.

   $$F_k(ctr+i)\oplus m_i=c_i$$

   To decrypt, we repeat the same process.

   $$F_k^{-1}(c_i)\oplus (ctr+i)=m_i$$

2,3,4 all achieve similar levels of security!

In looking at each mode, we should also think about if the mode is parallelizable!

Practical Constructions for Block Ciphers §

How do we construct strong PRPs (block ciphers) in practice?

Below, we’ll discuss some various ideas that were uesd to define PRPs. Suppose we’re working with a 128-bit input and 128-bit output.

By the end, we’ll end on how AES-128 works.

For each idea, we’ll ask the questions:

• Does the construction give us a permutation (does each input have a unique output)?
• Is the construction indistinguishable from a random permutation (secure)?

Substitution-Permutation Networks (SPNs) §

Here’s an idea:

Shannon Confusion Paradigm

Over small enough domains, random permutations are efficient. For example, if we only need to generate a random permutation table for an 8 bit output, we only need to generate $2^8=256$ entries!

So, what if we could extend this? For a 128-bit input, let our key $k$ specify 16 permutations $f_1,\dots f_{16}$ on 8-bit blocks. Then, for an input $x$, break it into 8-bit blocks $x_1{x}_2\dots x_{16}$, and generate ciphertext

$$c=f_1(x_1)||f_2(x_2)||\dots ||f_{16}(x_{16})$$

• This is a permutation, as we can invert ciphertext $c=y_1||y_2||\dots ||y_{16}$ by taking $f_1^{-1}(y_1)||\dots ||f_{16}(y_{16})$.

This is good, but is not indistinguishable from a truly random permutation. To see why, query two messages, where only one block $x_i$ is different. Then, every output block between the two messages should be the same except block $i$.

This fails because the order of the blocks is fixed which exposes information. We add an additional step to address this, where we permute the ordering of the blocks.

This is known as the Shannon Confusion-Diffusion Paradigm! The first step is known as confusion, and the block re-ordering step is known as diffusion.

A practical implementation of this paradigm is known as the Substitution-Permutation Network (SPN). An SPN applies the following operations, in what’s known as a round:

• Key Mixing: The message is XORed with key $k_i$, which is derived from the master key.
  • A different key is used each round, and is derived from the master key using a key schedule (which often just takes different subsets of the master key’s bits).
• Substitution: The message is split into blocks, and each block is ran through an S-Box, fixed and public permutations on some $n$-bit input and $n$-bit output.
• Permutation: The bits are permuted through a public mixing function.

The SPN runs multiple of these rounds to obtain an output that looks random. After running each round, the network will always finish by running one more final key-mixing step.

Note that the substitution and permutation functions are completely public! The security comes from the keys that are XORed with the message at the key mixing steps.

How many rounds are needed for this to be secure?

Theorem: The Avalanche Effect

For a random permutation, when a single input bit is changed, we should expect each bit of $f(x)$ should be changed with probability 1/2. So,

• We design S-boxes so that changing a single bit of the input to an S-box changes at least 2 bits in the output of the S-box
• We design the mixing function so that the output bits of any given S-box are used as input to multiple S-boxes in the next round

Because of this, on round $i$, if 1 bit of the input is changed, we can expect it to influence $2^i$ bits of the output. So, for AES-128, we need at least 7 rounds ($2^7=128$) for this to hold / give us the security we need!

In the case that we don’t have enough rounds, it’s possible to break SPN with a key-recovery attack. Suppose we have oracle access to our SPN.

Example: Key Recovery Attack vs. 1-Round SPN

Suppose we have a 1-round SPN on 16-bit messages, using 4-bit S-boxes, where our key is length 32-bit $k=k_1||k_2$ ($k_1$ used for the first mix, $k_2$ used for the second).

Using a brute-force approach, there are $2^{32}$ possible key values! However, we can actually significantly reduce this.

To understand why, suppose we queried the oracle to get input output pair $(x,y)$. For any $k_2$, there exists 1 unique $k_1$ that gives us $(x,y)$. So, an attacker could do the following:

1. Query the oracle for $(x,y)$.
2. For a 16-bit block of $k_2$, guess one of the $2^{16}$ combinations.
3. Invert the SPN for our message (XOR y with $k_2$, inverse mix, inverse S-box, then XOR with x) to find the corresponding $k_1$ for this $k_2$.
4. Now, query the oracle for another message, and see if our $(k_1||k_2)$ pair gives us the correct message.

This means we only need to evaluate the SPN $2\ast 2^{16}$ times! This is a lot more efficient than our original brute-force approach.

However, we could actually do even better than this! The key to this is realizing that we can actually compute our $(k_1,k_2)$ combinations for each S-box block at a time.

1. Take some S-box block, say the block for $x_1$ to $x_4$.
2. Figure out the bits of the output (and $k_2$) which are the output of this S-box block (XOR these bits of $y$ with the guess, inverse S-box, then XOR with the block for $x$).
3. Now, for any given block, we need to guess $2^4$ possible bit combinations of $k_2$ to find the corresponding $k_1$ for that block!

Repeating this for each of the 4 blocks, we now only evaluate our SPN $4\ast 2^4$ times to get 4 lists, which represent all possible outputs of $(k_1,k_2)$! We can run this on extra messages to determine which key combination is correct.

AES

Advanced Encryption Standard (AES) essentially uses the SPN paradigm for security.

Feistel Network §

Feistel Networks are another way we can generate block ciphers, though we will not cover it in the sake of time.

Feistel networks essentially take a PRF, and convert it into a secure PRP.

DES

Data Encryption Standard (DES) uses the Feistel Network.

Message Authentication Codes (MAC) §

In the previous section, we discussed how to create a secure encryption scheme. However, security is not everything! Even without knowing the original message in the previous schemes, attackers can still modify the message with no way for the sender / receiver to tell.

In other words, there’s secrecy, but not integrity! In this section, we will discuss how we can create schemes that maintain integrity.

Secure MACs §

Suppose we have a sender, receiver, and eavesdropper, where only the sender and receiver have knowledge of the $k$. Say the sender doesn’t care about security, and just wants the receiver to be able to verify that the message came from them, and was not modified in transit. How can they do this?

They do this using a message authentication code (MAC) scheme $\Pi =Gen,Mac,Vrfy$.

1. Both the sender and receiver share a key randomly generated with Gen.
2. The sender runs a MAC Algorithm $Ma{c}_k(m)$, which generates a tag $t$ that can be used for authentication.
3. The sender sends the message and tag together, $(m,t)$, to the receiver.
4. The receiver runs a Verification Algorithm $Vrf{y}_k(m,t)$, which returns 1 (valid) or 0 (invalid) indicating if the message was sent by the sender or not (based on if the tag matches the message).

Corectness guarantees that $Vrf{y}_k(m,Ma{c}_k(m))=1$. In other words, the verify algorithm should always work if the message truly wasn’t modified.

Like before, we will formalize this scheme with an experiment

$$\text{Experiment}MACforg{e}_{A,II}(n)$$

Let $\Pi$ be a MAC scheme, $A$ be an adversary, and $n$ be the security parameter. Let the challenger play the part of the sender / receiver.

1. The challenger first generates a random key $Gen(1^n)\to k$.
2. $A$ gets oracle access to the MAC algorithm, $A^{Ma{c}_k(\cdot )}$. In other words, they can query any message they want, and get back a tag for that message. Let $Q$ be the set of all messages $m^{\prime }$ queried by $A$.
3. $A$ tries to forge the message authenticity, by sending message and tag pair $(m,t)$ to the challenger.
4. The adversary wins, $Macforg{e}_{A,II}(n)=1$, if:
   • $m\notin Q$. In other words, the adversary did not query and get the tag for $m$ (if they queried $m$, this is known as a replay attack, which has to dealt with separately in practice).
   • $Vrfy(m,t)=1$. In other words, the challenger was tricked into finding the tag matches the message

We say $\Pi$ is existentially unforgeable under an adaptive chosen message attack if $\forall$ PPT $A$, $\exists$ negligible function $negl$ such that

$$Pr[Macforg{e}_{A,II}(n)=1]\le negl(n)$$

Note that unlike security, this probability must be less than negligible probability, not $\frac{1}{2}+negl$.

For shorthand, we will just say the scheme is secure in this case.

Strong Security

There’s also a stronger notion of security for MAC schemes, which we’ll call strong security. In this case, $Q$ is the set of all message, tag pairs $(m^{\prime },t^{\prime })$, and the adversary wins if

• $(m,t)\notin Q$
• $Vrf{y}_k(m,t)=1$

In other words, the adversary is allowed to replay a message, as long as the tag is different.

In practice, we don’t worry about this too much as the schemes we use are deterministic, so there’s only one valid tag per message (so strong security and normal security are the same).

Example: MAC Disproof

Suppose we have a MAC, where for mesage $m=m_1||\dots ||m_{\ell }$, $m_i\in \{0,1{\}}^n$, choose $r\in \{0,1{\}}^n$ at random and compute $t=r||F_k(m_1\oplus r)||\dots ||F_k(m_{\ell }\oplus r)$.

This is, in fact, not a secure MAC. We can show this below.

Let $A$ be an adversary which does the following:

1. Suppose we have some message $m$ we want to authenticate. Query the oracle to get the tag $t$.
2. From the tag $t$, take random bit-string $r$ in the beginning.
3. Now create forgery, where $m^{\prime }$ is the message where each block of the message is XORed with $r$ from above. Let $t^{\prime }$ be the tag where $0$ is our random bit-string, with $t$ after.

This is a valid forgery, which gives us a non-negligible probability of breaking the MAC!

Constructing Secure MACs (Fixed-Length) §

We can construct secure MACs using pseudorandom functions!

Let $F$ be a pseudorandom function. We define a fixed-length MAC for messages of length $n$ as follows:

• Gen: Outputs a random key $k$.
• Mac: For key $k$ and message $m$, output $F_k(m)=t$.
• Vrfy: For key $k$, message $m$, tag $t$, output 1 if and only if $t=F_k(m)$.

This only works for fixed-length messages. Later, we’ll use this to create schemes that work for variable length messages.

Theorem: MAC Security

If $F$ is a PRF, then the construction above is a secure fixed-length MAC for messages of length $n$.

Proof

By contrapositive, suppose the construction is not a secure MAC. So, there exists a PPT adversary $A$, non-negligible function $\rho$, such that

$$Pr[MACforg{e}_{A,\Pi }(n)=1]\ge \rho$$

We must show that there exists a distinguisher $D$ such that

$$|Pr[D^{f(\cdot )}(1^n)=1]-Pr[D^{F_k(\cdot )}(1^n)=1]|\ge {\rho }^{\prime }(n)$$

For non-negligible function ${\rho }^{\prime }(n)$.

Let $D$ do the following, playing the PRF experiment.

1. Let $D$ get the oracle, which is either random function $f$, or $F_k$.
2. $D$ gives $A$ oracle access. For any MAC query from $A$, $D$ forwards messgae $m$ to the oracle to get $t=O(m)$ and sends it back to $A$.
3. When ready, $A$ sends $(m^{\ast },t^{\ast })$ to $D$ as a forgery.
4. $D$ checks if $m^{\ast }\in Q$, output 0. If $m^{\ast }\notin Q$, forward $m^{\ast }$ to the oracle and check if $O(m^{\ast })=t^{\ast }$. If so, output 1, 0 otherwise.

Note that $D$ is running $A$, so $D$ is running in PPT. We have the following probabilities.

$$\begin{array}{r}Pr[D^{F_k(\cdot )}(1^n)=1]=Pr[MACforg{e}_{A,\Pi }(n)=1]\ge \rho (n)\\ Pr[D^{f(\cdot )}(1^n)=1]\le \frac{1}{2^n}\\ |Pr[D^{f(\cdot )}(1^n)=1]-Pr[D^{F_k(\cdot )}(1^n)=1]|\ge \left|\rho (n)-frac12^n\right|\end{array}$$

Which is non-negligible. Thus, $F$ is not a PRF.

Constructing Secure MACs (Variable-Length) §

Let’s see how we can extend MACs for variable-length MACs, known as domain extension for MACs.

Suppose we have a MAC $\Pi$, which works for fixed-length messages of length $n$. For a message of any length,

$$m=m_1{m}_2\dots m_{\ell }$$

How can we generate a tag for this message?

Naive Extension

One way we could do this is by running each block of the message through the MAC to get a tag for each block.

Unfortunately, this is not secure. This is because there’s nothing “tying” the blocks of the messages together— so, an adversary can easily reorder the blocks to break the security of the scheme.

Let’s see some ways we can extend the MAC.

CBC MAC §

CBC-MAC: We generate one tag by running each message through $F_k$, XORing the result with the next message, and repeating this process. Formally,

$$\begin{array}{rl}& c_1=F_k(m_1)\\ & c_2=F_k(m_2\oplus c_1)\\ & c_3=F_k(m_3\oplus c_2)\\ & ⋮\\ & t=c_{\ell }=F_k(m_{\ell }\oplus c_{\ell -1})\end{array}$$

This is secure only if the message and forgery are both required to have a fixed length $\ell$! If these conditions are relaxed, we can perform a length extension attack to break the security of the MAC— let’s see how below.

Example: Length Extension Attack

Suppose the message and forgery are not required to have block-length $\ell =6$. Then, let $A$ be the adversary who queries two messages $m_1,m_2$ of length 3 blocks each. $A$ will use these messages to then generate a forgery on a 6 block message $m^{\prime }=m_1^{\prime }{m}_2^{\prime }{m}_3^{\prime }{m}_4^{\prime }{m}_5^{\prime }{m}_6^{\prime }$.

1. $A$ can query $m_1=m_1^{\prime }||m_2^{\prime }||m_3^{\prime }$, to get tag $t_1$.
2. Then, $A$ can query $m_2=(m_4^{\prime }\oplus t_1)||m_5^{\prime }||m_6^{\prime }$ to get tag $t_2$.
3. This tag is our forgery! Return forgery $(m^{\prime },t^{\prime })$ where $t^{\prime }=t_2$.

This creates a forgery that breaks the security of our MAC!

This happens because we’re allowed to query the oracle on a prefix of the previous message. This relation breaks the security.

To fix CBC-MAC, we will first instead start the MAC not on $m_1$, but on some prefix-free encoding. This is a scheme that maps an input message into a space of valid code-words, where for any two valid code-words, one does not prefix the other.

One easy way to do this is by encoding the length of the message! So, CBC-MAC would do the following:

$$\begin{array}{rl}& c_0=F_k(\text{Length of m})\\ & c_1=F_k(m_1\oplus c_0)\\ & c_2=F_k(m_2\oplus c_1)\\ & ⋮\\ & t=c_{\ell }=F_k(m_{\ell }\oplus c_{\ell -1})\end{array}$$

The prefix-free encoding ensures that messages cannot prefix each other in the MAC scheme!

Essentially, what we are doing is prepending an extra message block to the message, which indicates its length.

Hash and MAC §

Hash-And-Mac: Using a hash function to compress messages of arbitrary lengths to the MAC input size. We use the hsah function to compress the message, then create a mac from the fixed-size output.

Formally, a hash function (with output length $\ell$) is a pair of PPT algorithms Gen, H satisfying the following:

• Gen takes input security parameter $1^n$ and outputs a key $s$.
• H takes input key $s$, string $x\in \{0,1{\}}^{\ast }$ and outputs a string $H^s(x)\in \{0,1{\}}^{\ell (n)}$

If $H^s$ is only defined for inputs $x\in \{0,1{\}}^{{\ell }^{\prime }(n)}$ and ${\ell }^{\prime }(n)>\ell (n)$, then we say that Gen, H is a fixed-length hash function for inputs of length ${\ell }^{\prime }$. In this case, $H$ is also called a compression function (shrinks the size of the input).

We define the following experiment, $Hashcol{l}_{A,II}(n)$.

1. Generate key $s$ by running $Gen(1^n)$.
2. The adversary $A$ is given $s$ and outputs $x,x^{\prime }$.
3. The output of the experiment is 1 if and only if $x\ne x^{\prime }$, and $H^s(x)=H^s(x^{\prime })$.

We say a hash function is collision resistant if for all PPT adversaries, there exists a negligible function such that

$$Pr[Hashcol{l}_{A,II}(n)=1]\le negl$$

With hash functions, we can easily create MACs for variable length messages! We first hash our message into the MAC input domain, and then run the MAC algorithm

$$Ma{c}_k(m)=F_k(H^s(m))$$

Theorem

If $\Pi$ is a secure MAC for messages of length $\ell$, and ${\Pi }_H$ is collision resistant, then the construction above is a secure MAC for arbitrary length messages.

Proof (Sketch)

Suppose by way of contradiction there is an adversary breaking Hash-And-Mac. We show that under this assumption, this adversary can break either the securei MAC or the hash function.

If $A$ can break the scheme, then it can produce $m,t=Ma{c}_k(H^s(m))$, $m\notin Q$.

1. Case 1: We can check the list of queries to find $m^{\prime }$, which will yield $H^s=H^s(m^{\prime })$ for some $m^{\prime }\in Q$ and $m\ne m^{\prime }$. This will break the collision resistant hahs function.
2. Case 2: In all the queries in $Q$, they all correspond to different inputs $\tilde{m}$ to $Ma{c}_k$. This will break the MAC.

But how do we create a compression function in practice?

Creating a Compression Function in Practice

One way we can create a compression function is by using the Davies-Meyer Construction.

Let $F$ be a block cipher with $n$-bit key and $\ell$-bit block length. Then, for $n+\ell$ bit message $k||m$, we can compress the message as

$$h(k||x)=F_k(m)\oplus m$$

Note that the XOR with $x$ is necessary, as without it, we could easily generate a collision ($F$’s key is known, so we can decrypt on a different key to find a different message, key pair).

Intuitively, this works because the output of $F_k(m)$ looks “random”, so it serves as a bit-mask on $m$. This will modify $m$ arbitrarily, giving us a “random” looking output.

Security is guaranteed only if we assume $F$ is not a PRP, but an ideal cipher, meaning that queries are allowed only on different keys that are not $k$.

Given a compression function with fixed input-output lengths, we can then extend it to accept variable-length inputs using the Merkle-Damgard Transform (used by SHA-1 and SHA-256):

1. Split the message into blocks of equal length: $X_1,X_2,\dots ,X_B$.
2. Take an initialization vector, $Z_0=IV$.
3. Hash $Z_i=H^s(Z_{i-1}||X_i)$ for every $1\le i\le B$ to get $Z_B$.
   $$Z_1=H^s(Z_0||X_1)Z_2=H^s(Z_1||X_0)\dots$$
4. Finally, hash $H^s(Z_B||L)$, where $L$ is the length of the message.

In practice, the initialization vector is something hard-set, like $0^n$.

This works as long as our function is a compression function (output is smaller than the input)!

We need to pad with the length, to distinguish messages that aren’t perfectly aligned with the blocks. If we were to pad these messages with 0s instead, we could easily create a collision.

Theorem: Security of Merkle-Damgard

If the underlying compression function $h$ is collision resistant, then so is $H$, the Merkle-Damgard Transform of this function.

Proof (Sketch)

We wish to show (by contrapositive) that if we can find a collision in $H$, say $x,x^{\prime }$, we can generate a collision for $h$.

1. Case 1: If the length of the two messages are not equal, we can easily create a collision on $h$ by taking the last inputs to $H^s$ in the transform. So, our collision is given by $Z_B||L$ and $Z_B^{\prime }||L^{\prime }$.

2. Case 2: If the lengths are equal, check if $Z_B=Z_B^{\prime }$. If they’re equal, repeat this case for $Z_{B-1}$ and $Z_{B-1}^{\prime }$. If they are not, we have two messages generating a collision.

There must be some $Z_i\ne Z_i^{\prime }$, as otherwise, the messages are the same (which is a contradiction).

Merkle-Damgard is not a secure MAC.

Constructing a $h$ for Merkle Damgard

For a hash function outputting $\ell$ bits, to get a collision with 100% probability, we need to try $2^{\ell }+1$ inputs (by pigeon hole principle).

However, we don’t need 100% probability of success to make the function insecure! By the birthday bound, we really only need $2^{\ell /2}$ to find a collision with a reasonable probability. So, regardless of how good our collision function is, an attacker only needs about $2^{\ell /2}$ samples to break the security!

The birthday bound states that for $q$ uniform, independent, random samples of $N$, we have collision probability bounded by

$$\frac{q(q-1)}{4N}\le \text{Coll}(q,N)\le \frac{q^2}{2N}$$

Because of this, $\ell$ has to be pretty large.

For example, as SHA-1 outputs length $\ell =160$, someone could break it in time $2^{160/2}$ queries.

Sponge Construction §

Sponge: Recently, a new paradigm has emerged for domain extension. Let $f$ be a completely random permutation on $\{0,1{\}}^{r+c}\to \{0,1{\}}^{r+c}$.

This is the paradigm used in SHA-3.

Using $f$, we will first absorb the input in one stage, then squeeze out the output in another (this is why it’s known as a sponge).

1. Absorb:
   1. Start with an internal state of all 0’s, split into an $r$ section and a $c$ section. In other words, our state starts as $0^r||0^c$.
   2. For every block of the message $p_i$, XOR it with $r$, and run $f(r\oplus p_i||c)$. The first $r$ bits is our new $r$ section, with the rest being the $c$ section.
   3. Repeat this for all blocks of the message, until the entire input is absorbed.
2. Squeeze:
   1. Take the first $r$ bits of the state, and output them.
   2. If more bits are needed, run the state through $f$ and output the next $r$ bits.

$r$ is our bitrate, how fast we can absorb / squeeze data; $c$ is our capacity, how secure our method is.

It can be shown that if $p_0$ is our key $k$, and the remaining are our message blocks, this sponge method can be used directly as a MAC; it is indifferentiable from a random oracle, if $f$ is a truly random permutation.

Authenticated Encryption §

CCA Security §

We’ve seen a secure way to encrypt our message for security, and a secure way to authenticate our message for integrity. Now, let’s tie the two together!

Chosen Ciphertext Attack (CCA) Security is a standard security notion, which is even stronger than CPA security. We define the following game.

Consider a private-key encryption scheme $\Pi$, some adversary $A$, and security parameter $n$. Define the following experiment

$$Priv{K}_{A,\Pi }^{cca}(n)$$

1. The challenger generates a key $Gen(1^n)=k$.
2. The adversary gets oracle access to both the encryption and decryption algorithm, $A^{En{c}_k,De{c}_k}$. They can query messages to get ciphertexts, and ciphertexts to get messages.
3. The adversary chooses 2 messages, $m_0,m_1$ and sends them to the challenger.
4. The challenger chooses one of the messages at random, $b\in \{0,1\}$, encrypts it, and sends the ciphertext $c$ of $m_b$ back.
5. The adversary can again query the encryption and decryption oracle. When ready, it returns $b^{\prime }$ guessing what message was encrypted.
   • To make sure this game is possible, in this step, the adversary is NOT allowed to query challenge ciphertext $c$ to the decryption oracle. It can query anything else though, as long as it is not $c$. We’ll denote this slight limitation as $A^{De{c}_k^{\ast }}$
6. The experiment is 1 if $b^{\prime }=b$, 0 otherwise.

We say $\Pi$ has indistinguishable encryptions under a chosen-ciphertext attack (CCA secure) if $\forall$ PPT adversaries $A$, $\exists$ a negligible function $negl$ such that

$$Pr[Priv{K}_{A,\Pi }^{cca}(n)=1]\le negl$$

This is a really strong notion of security!

Authenticated encryption schemes satisfy this type of security, by using MACs to tag the ciphertext for authentication. Then, $Dec$ throws an error (denoted $\perp$) if it detects an invalid ciphertext. By doing this, the adversary can only decrypt the ciphertexts its seen, and can’t make its own!

Unforgeability for Encryption §

To define an authenticated encryption scheme, we also need to define an additional experiment $EncForg{e}_{A,II}(n)$:

1. Run Gen to obtain key $k$
2. The adversary $A$ is given input $1^n$, and access to the encryption oraacle $En{c}_k(\cdot )$. The adversary outputs a ciphertext $c$.
3. Let $m=De{c}_k(c)$, and let $Q$ denote the set of all queries that $A$ queried from the oracle. The output of the experiment is 1 if and only if $m\ne \perp$ and $m\notin Q$.

We say a private-key encryption scheme is unforgeable if $\forall$ PPT adversaries $A$, there is a negligible function $negl$ such that

$$Pr[EncForg{e}_{A,II}(n)=1]\le negl(n)$$

Authenticated Encryption Schemes §

We say a private-key encryption scheme is an authenticated encryption scheme if it is CCA-secure and unforgeable.

This is essentially a secure way of combining CPA-security and MACs!

Here are some generic constructions.

Encrypt and Authenticate §

Encrypt-and-Authenticate: We run encryption and message authentication independently, in parallel.

$$En{c}_{k_E}(m)=cMa{c}_{k_M}(m)=t⟨c,t⟩$$

Do NOT use the same key for both schemes.

$c$ preserves security, and $t$ preserves privacy, but combining them does not guarantee both! This is because the tag $t$ can leak info on $m$, which will break the security of the message.

In fact, if the MAC is deterministic (which it often is in practice), then CPA-security does not hold for the combined $(c,t)$.

Authenticate then Encrypt §

Authenticate-then-Encrypt: We first generate a tag, then compute our ciphertext by combining our message with the tag.

$$Ma{c}_{k_M}(m)=tEn{c}_{k_E}(m||t)=cc$$

Now, because we’re putting our tag into the ciphertext, this can provide privacy. However, this will not provide CCA-security!

Encrypt then Authenticate §

Encrypt-then-Authenticate: We first encrypt the message, and then compute a tag on the result.

$$En{c}_{k_E}(m)=cMa{c}_{k_M}(c)=t⟨c,t⟩$$

This is secure as long as the MAC is strongly secure! Because only the encryption scheme sees the message, it provides CPA-security, and the use of the MAC preserves privacy, without compromising on security!

This also gives us CCA-security, as it renders the decryption oracle useless, as it will only return $\perp$ unless a known ciphertext from CCA-security is given (and we’re not allowed to query the challenge ciphertext $⟨c,⟩t$).

This is exactly what goes on in the internet after key establishment!