CO487

Professor: Alfred Menezes | Term: Fall 2024

Chapter 1: Introduction to Cryptography

Cryptography is about securing communications in the presence of malicious adversaries.

Alice and Bob are communicating via an unsecured channel. Eve is eavesdropping (malicious). Communication should be

• Confidential: Keep data secret from everyone not authorized to see it.
• Data Integrity: Ensure data is not altered by others.
• Data Origin Authentication: Corroborating the source of data.
• Non-Repudiation: Preventing an entity from denying previous commitments or actions.

Transport Layer Security (TLS): The cryptographic protocol used by web browsers to securely communicate with websites (e.g. Facebook, Gmail).

TLS is used to assure an individual user of the authenticity of the website and establish a secure communications channel.

Symmetric-Key Cryptography: The client and server a priori share some secret information $k$ called a key.

They can encrypt their messages with AES and authenticate the resulting ciphertexts with HMAC.

Question

How do Alice and Bob share the shared secret $k$?

Public-key cryptography: The client and server a priori share some authenticated (but non-secret) information.

To establish a secret key, Alice selects the secret session key $k$, and encrypts it with Bob’s RSA public key. Then only Bob can decrypt the resulting ciphertext with its RSA private key to recover $k$.

Question

How does Alice obtain an authentic copy of Bob’s RSA public key?

Bob cannot send it to Alice over the internet because it can be intercepted.

Signature scheme: Bob’s RSA public key is signed by a Certification Authority (CA) using its secret signing key with the RSA signature scheme.

Alice can verify the signature using the CA’s RSA public verification key. In this way, Alice obtains an authentic copy of Bob’s RSA public key.

The CA’s RSA public key is embedded in Alice’s browser.

TLS potential vulnerabilities:

• The cryptography is weak
• Cryptography can be broken using quantum computers
• Weak random number generation
• Issuance of fraudulent certificates
• Software bugs
• Phishing attacks
• TLS only protects data during transit. It does not protect data stored at the server

Definition

Cybersecurity is comprised of the concepts, technical measures, and administrative measures used to protect networks, computers, programs and data from deliberate or inadvertent unauthorized access, disclosure, manipulation, or use.

Cryptography $\ne$ Cybersecurity. Cryptography provides some mathematical tools that can assist with the provision of cybersecurity services. It is a small part of a complete security solution.

Security is a chain; weak links become targets.

Chapter 2: Symmetric-Key Encryption

Fundamental Concepts

Definition

Asymmetric-key encryption scheme (SKES) consists of:

• $M$ - the plaintext space,
• $C$ - the ciphertext space,
• $K$ - they key space,
• a family of encryption functions $E_k:M\to C,\forall k\in K$,
• a family of decryption functions $D_k:C\to M,\forall k\in K$,

such that $D_k(E_k(m))=m$ for all $m\in M,k\in K$.

1. Alice and Bob agree on a secret $k\in K$ communicating over the secured channel
2. Alice computes $c=E_k(m)$ and sends the ciphertext $c$ to Bob over the unsecured channel.
3. Bob retrieves the plaintext by computing $m=D_k(c)$

Note: The secret key $k$ might be used for a fixed time interval, or it might be used a fixed number of times.

Called symmetric-key encryption since the same key is used for encryption and decryption.

The Enigma and Lorenz Machines are examples.

Substitution Cipher

• $M=$ all English messages
• $C=$ all encrypted messages
• $K=$ all permutations of the English alphabet.
• $E_k(m):$ Apply permutation $k$ to $m$, one letter at a time
• $D_k(c):$ Apply the inverse permutation $k^{-1}$ to $c$, one letter at a time

Security Model: Defined the computational abilities of the adversary, and how she interacts with the communicating parties.

Convention: We will always strive to model maximal adversary capabilities and minimal adversary goals.

Basic assumption: The adversary knows everything about the SKES, except the particular key $k$ chosen by Alice and Bob. Avoid security by obscurity.

Computational power of the adversary:

• Information-theoretic security: Eve has infinite computational resources
• Complexity-theoretic security: Eve is a “polynomial-time Turing machine”
• Computational security: Eve has a bounded amount of computational power. We say Eve is computationally bounded.

Passive Attacks:

• Ciphertext-only attack: The adversary knows some ciphertext
• Known-plaintext attack: The adversary also knows some plaintext and the corresponding ciphertext. Active Attacks:
• Chosen-plaintext attack: The adversary can also choose some plaintext and obtains the corresponding ciphertext
• Clandestine attacks: bribery, blackmail (not covered in this course)

Adversary’s goal

1. Recover the secret key $k$
2. Systematically recover plaintext from ciphertext, without necessarily learning $k$.
3. Learn some partial information about the plaintext from the ciphertext, other than its length

If the adversary can achieve 1 or 2, the SKES is said to be totally insecure.

If the adversary cannot learn any partial information about the plaintext from the ciphertext, the SKES is said to be partially secure.

Definition

A symmetric-key encryption scheme is said to be secure if it is semantically secure against chosen-plaintext attack by a computationally bounded adversary.

To break a symmetric-key encryption scheme, the adversary has to accomplish the following:

1. The adversary is given a challenge ciphertext $c$
2. During its computation, the adversary can select arbitrary plaintext and obtain the corresponding ciphertexts
3. After a feasible amount of computation, the adversary obtains some information about the plaintext $m$ corresponding to $c$.

Desirable properties of a SKES

1. Efficient algorithms should be known for computing $E_k$ and $D_k$.
2. The secret key $k$ should be small, but large enough to render exhaustive key search infeasible.
3. The scheme should be secure.
4. The scheme should be secure even against the designer of the system.

The simple substitution cipher is totally insecure against a chosen-plaintext attack.

Is exhaustive key search possible?

Number of keys to try is $26!\approx 4\times 10^{26}\approx 2^{88}$. This will take too long, even with many computers.

In this course:

• $2^{40}$ operations is considered very easy.
• $2^{56}$ operations is considered easy.
• $2^{64}$ operations is considered feasible.
• $2^{80}$ operations is considered barely feasible.
• $2^{128}$ operations is considered infeasible.

The Bitcoin network is performing about $2^{80}$ hash operations per hour.

Definition

A cryptographic scheme is said to have a security level of $\ell$ bits if the fastest known attack on the scheme takes approximately $2^{\ell }$ operations. A security level of $128$ bits is desirable in practice.

Simple frequency analysis of ciphertext letters can be used to recover the secret key.

Vigenere Cipher

The secret key is an English word having no repeated letters, e.g. $k=$ CRYPTO. We sum each letter in $m$ by $k$ to get $c$. Here $A=0,B=1,\dots ,Z=25$, and addition of letters is module $26$. Decryption is subtraction module $26:m=c-k$.

The Vigenere cipher is totally insecure against a chosen-plaintext attack.

It is also insecure against a cipher-text only attack.

Stream Ciphers

A stream cipher is a SKES that encrypts the plaintext one bit at a time. A block cipher is a SKES that encrypts the plaintext one block at a time.

One-time Pad

The secret key is a random string of letters with the same length as the message. We use the same process as the Vigenere.

The key should not be reused. If $c_1=m_1+k$ and $c_2=m_2+k$, then $c_1-c_2=(m_1+k)-(m_2+k)=m_1-m_2$. So, $c_1-c_2$ depends only on the plaintext (and not on the key $k$), and hence can leak information.

Convention: From now on, messages and keys will be assumed to be bit (binary) strings.

Notation: $\oplus$ is bitwise exclusive-or (XOR) (bitwise addition mod $2$).

Example

$1011001011\oplus 1001001001=0010000010$

Note that $x\oplus x=0,x\oplus y=y\oplus x$

So, for the one-time pad, encryption is $c=m\oplus k$ and decryption is $m=c\oplus k$.

Perfect secrecy: The one-time pad is semantically secure against ciphertext-only attack by an adversary with infinite computational resources.

This can be formally proven using concepts from information theory. Shannon proved that if plaintexts are $\ell$-bit strings, then any symmetric-key encryption with perfect secrecy must have $|K|\ge 2^{\ell }$. So perfect secrecy is useless in practice.

Basic Idea: Instead of using a random key in the one-time pad, use a “pseudorandom” key.

Definition

A pseudorandom bit generator (PRBG) is a deterministic algorithm that takes as input a (random) seed, and outputs a longer “pseudorandom” sequence called the keystream.

Stream cipher: uses a PRGB for encryption. The seed is the secret key shared by Alice and Bob.

No more perfect secrecy - security depends on the quality of the PRBG.

For a stream cipher to be secure:

• Indistinguishability requirement: The keystream should be “indistinguishable” from a random sequence.
• Unpredictability requirement: Given portions of the keystream, it should be computationally infeasible to learn any information about the remainder of the keystream
  • If an adversary knows a portion $c_1$ of ciphertext and the corresponding plaintext $m_1$, then she can easily find the corresponding portion $k_1=c_1\oplus m_1$ of the keystream.

Aside: Don’t use UNIX random number generators rand and srand for cryptographic purposes.

Now we introduce the ChaCha20 stream cipher. Designed by Dan Bernstein in 2008, the ChaCha20 is conceptually very simple. It is extremely fast in software an does not require and special hardware. No security weaknesses have been found.

Notation:

• $256-$bit $k=(k_1,k_2,k_3,\dots ,k_8)$
• $128-$bit constant $f=(f_1,f_2,f_3,f_4)$
• $96-$bit nonce $n=(n_1,n_2,n_3)$
• $32-$bit counter $c$
• A hexadecimal digit is a $4-$bit number.
  • $f_1=0x61707865$
  • $f_2=0x3320646e$
  • $f_3=0x79622d32$
  • $f_4=0x6b206574$
• A nonce is a non-repeating quantity

The initial state is:

$$\begin{array}{r}\left[\begin{array}{cccc}{f}_1& f_2& f_3& f_4\\ k_1& k_2& k_3& k_4\\ k_5& k_6& k_7& k_8\\ c& n_1& n_2& n_3\end{array}\right]=\left[\begin{array}{cccc}{S}_1& S_2& S_3& S_4\\ S_5& S_6& S_7& S_8\\ S_9& S_{10}& S_{11}& S_{12}\\ S_{13}& S_{14}& S_{15}& S_{16}\end{array}\right]\end{array}$$

More Notation:

• $\oplus :$ xor
• $⊞:$ integer addition module $2^{32}$
• $<<<t:$ left-rotation by $t$ positions

Define $QR$: Quarter Round Function

Input: Four $32$-bit words $a,b,c,d$

$$\begin{array}{rl}& a\leftarrow a⊞b,d\leftarrow d\oplus a,d\leftarrow d<<<16\\ & c\leftarrow c⊞d,b\leftarrow b\oplus c,b\leftarrow b<<<12\\ & a\leftarrow a⊞b,d\leftarrow d\oplus a,d\leftarrow d<<<8\\ & c\leftarrow c⊞d,b\leftarrow b\oplus c,b\leftarrow b<<<7\end{array}$$

Output: $a,b,c,d$

ChaCha20 Keystream Generator

Select a nonce $n$ and initialize the counter $c$ to $0$. While keystream bytes are required do:

• Create the initial state $S$, and make a copy $S^{\prime }$ of $S$.
• Update $S$ by repeating the following $10$ times:
  • $QR(S_1,S_5,S_9,S_{13}),QR(S_2,S_6,S_{10},S_{14}),QR(S_3,S_7,S_{11},S_{15})$
  • $QR(S_4,S_8,S_{12},S_{16})QR(S_1,S_6,S_{11},S_{16}),QR(S_2,S_7,S_{12},S_{13})$
  • $QR(S_3,S_8,S_9,S_{14}),QR(S_4,S_5,S_{10},S_{15})$
• Output $S\oplus S^{\prime }$ ($64$ keystream bytes).
• Increment the counter $c$

Encryption: The keystream bytes are xored with the plaintext bytes to produce ciphertext bytes. The nonce is appended to the ciphertext.

Block Ciphers: DES

Definition

A block cipher is a symmetric-key encryption scheme that breaks up the plaintext into blocks of a fixed length (e.g. $128$ bits), and encrypts the blocks one at a time.

In contrast, a stream cipher encrypts the plaintext one character (usually a bit) at a time.

A historically important example of a block cipher is the Data Encryption Standard (DES):

flowchart LR
key
key -- 56 bits --> DES
plaintext -- 64 bits --> DES
DES -- 64 bits --> ciphertext

Key length: $56$ bits, size of key space: $2^{56}$, block length: $64$ bits.

Design principles articulated by Claude Shannon

Security:

1. Diffusion: Each ciphertext bit should depend on all plaintext bits.
2. Confusion: The relationship between key and ciphertext bits should be complicated.
3. Key length: Should be small, but large enough to preclude exhausting key search.

Efficiency:

1. Simplicity: Easier to implement and analyze.
2. Speed: High encryption and decryption rates.
3. Platform: Suitable for hardware and software.

The design principles of DES are still classified.

DES Problem #1: Small key size

Exhaustive search on the key space takes $2^{56}$ operations and can easily be parallelized.

DES Problem #2: Small block size

If plaintext blocks are distributed uniformly at random, then the expected number of ciphertext blocks observed before a collision occurs is $\approx 2^{32}$. This is by the birthday paradox.

Birthday paradox: Suppose that an urn contains $n$ numbered balls. Suppose that balls are drawn from the urn, one at a time, with replacement. The expected number of draws before a ball is selected for the second time (called a collision) is approximately $\sqrt{\pi n/2}\approx \sqrt{n}$.

Thus the ciphertext reveals some information about the plaintext.

Block Ciphers: Triple-DES

Recall: The only substantial weaknesses known in DES are the obvious ones: small key length and small block length.

Question

How can one construct a more secure block cipher from DES?

Multiple encryption: Re-encrypt the ciphertext one or more times using independent keys. Hope that this increases the effective key length.

Note: Multiple encryption does not necessarily result in increased security.

Example

If $E_{\pi }$ denotes the encryption function for the simple substitution cipher with the key $\pi$, then $E_{{\pi }_2}\circ E_{{\pi }_1}$ any more secure than $E_{\pi }$?

No, since $E_{{\pi }_2}\circ E_{{\pi }_1}=E_{{\pi }_2\circ {\pi }_1}$

Encryption is: $c=E_{k_2}(E_{k_1}(m))$, where $E=$ DES decryption.

The Double-DES key length is $\ell =112$ bits, so exhaustive key search takes $2^{112}$ operations.

Note: The block length is unchanged ($64$ bits).

Meet-in-the-middle Attack on Double-DES

Input: 3 plaintext/ciphertext pairs $(m_1,c),(m_2,c_2),(m_3,c_3)$ Output: The secret key $(k_1,k_2)$

1. For each $h_2\in \{0,1{\}}^{56}$ do: a. Compute $E_{h_2}^{-1}(c_1)$ and store $[E_{h_2}^{-1}(c_1),h_2]$
2. For each $h_1\in \{0,1{\}}^{56}$ do:
3. Compute $E_{h_1}(m_1)$
4. Search for $E_{h_1}(m_1)$ in the table
5. For each match $[E_{h_2}^{-1}(c_1),h_2]$ in the table:
   1. Check if $E_{h_2}(E_{h_1}(m_2))=c_2$; if so then:
      1. Check if $E_{h_2}(E_{h_1}(m_3))=c_3$; if so then:
         1. Output$(h_1,h_2)$ and STOP.

The main idea is that $c=E_{k_2}(E_{k_1}(m))⟺E_{k_2}^{-1}(c)=E_{k_1}(m)$

Question

How many plaintext/ciphertext pairs are needed for unique key determination?

Let $E$ be a block cipher with key space $K=\{0,1{\}}^{\ell }$, and plaintext and ciphertext space $\{0,1{\}}^L$.

Let $k^{\prime }\in K$ be the secret key chosen by Alice and Bob, and let $(m_i,c_i),1\le i\le t$, be known plaintext/ciphertext pairs where the plaintext $m_i$ are distinct.

Question

So how large should $t$ be to ensure that there is only one key $k\in K$ for which $E_k(m_i)=c_i$ for all $1\le i\le t$?

We select $t$ so that $FK\approx 0$ where $FK$ is the expected number of false keys.

For each $k\in K$, the encryption function $E_k:\{0,1{\}}^L\to \{0,1{\}}^L$ is a permutation (bijection).

We make the heuristic assumption that for each $k\in K,E_k$ is a random function, i.e. a randomly selected function. This assumption is certainly false since $E_k$ is not random, and because a random function is almost certainly not a permutation.

Now, fix $k\in K,k\ne k^{\prime }$.

The probability that $E_k(m_i)=c_i$ for all $1\le i\le t$ is $\underset{t}{\underbrace{\frac{1}{2^L}\cdot \frac{1}{2^L}\cdots \frac{1}{2^L}}}=\frac{1}{2^{Lt}}$ Thus, the expected number of false keys $k\in K$ for which $E_k(m_i)=c_i$ for all $1\le i\le t$ is $FK=\frac{2^{\ell }-1}{2^{Lt}}$

Time: The number of DES operations is $\approx 2^{56}+2^{56}+2\cdot 2^{48}+2(1+\frac{1}{2^{16}})\approx 2^{57}$

The security level of Double-DES is 57 bits, so Double-DES is not much more secure than DES.

A Triple-DES secret key is $k=(k_1,k_2,k_3)$, where $k_1,k_2,k_3{\in }_R\{0,1{\}}^{56}$

Encryption is: $c=E_{k_3}(E_{k_2}(E_{k_1}(m)))$, where $E=$ DES encryption.

flowchart LR
k1
k2
k3
id1[DES]
id2[DES]
id3[DES]
k1 --> id1
k2 --> id2
k3 --> id3
m -- 64 bits --> id1
id1 -- 64 bits --> id2
id2 -- 64 bits --> id3 
id3 -- 64 bits --> c

Decryption is: $m=E_{k_1}^{-1}(E_{k_2}^{-1}(E_{k_3}^{-1}(c)))$, where $E^{-1}=$ DES decryption.

The Triple-DES key length is $\ell =168$ bits, so exhaustive key search takes $2^{168}$ operations (infeasible).

Meet-in-the-middle attack takes $\approx 2^{112}$ operations. So the security level of Triple-DES is 112 bits.

Block Ciphers: AES

The Advanced Encryption Standard (AES)

Key lengths: $128$, $192$ and $256$ bits.

Block length: $128$ bits

2024: No attacks have been found on AES that are faster than exhaustive key search.

AES is an example of a substitution-permutation network.

Definition

A substitution-permutation network (SPN) is an iterated block cipher where a round consists of a substitution operation followed by a permutation operation

Components of an SPN cipher:

• $n$: the block length (in bits)
• $\ell$: the key length (in bits)
• $h$: the number of rounds
• A fixed invertible function $S:\{0,1{\}}^b\to \{0,1{\}}^b$ called substitution, where $b$ is a divisor of $n$.
• A fixed permutation $P$ on $\{1,2,\dots ,n\}$.
• A key scheduling algorithm that determines subkeys $k_1,k_2,\dots ,k_h,k_{h+1}$ from a key $k$. Note: $n,\ell ,h,S,P$ and the key scheduling algorithm are public.

The encryption looks like: $A\leftarrow$ plaintext for $i=1,2,\dots ,h$ do $A\leftarrow A\oplus k_i$ $A\leftarrow S(A)$ $A\leftarrow P(A)$ $A\leftarrow A\oplus k_{h+1}$ ciphertext $\leftarrow A$

Decryption is the reverse of encryption.

AES is an SPN, where the permutation operation is comprised of two invertible linear transformations.

All operations are byte oriented, e.g., $b=8$ so the $S-$box maps $8$ bits to $8$ bits. This facilitates fast implementations on software platforms.

The block length of AES is $n=128$. Each subkey is $128$ bits.

AES accepts three key lengths. The number of rounds $h$ depends on the key length.

Each round updates a variable called State which consists of a $4\times 4$ array of bytes (note $4\times 4\times 8=128$, the block length).

State is initialized with the plaintext.

Add AES round uses four invertible operations:

1. AddRoundKey (key-mixing)
2. SubBytes (S-box)
3. ShiftRows (permutation)
4. MixColumns (linear transformation)

After $h$ rounds are completed, a final subkey is XORed with State, the result being the ciphertext.

Definition

The elements of the finite filed $GF(2^8)$ are the polynomials of degree at most $7$ in ${\mathbb{Z}}_2[y]$, with addition and multiplication performed module the irreducible polynomial $f(y)=y^8+y^4+y^3+y+1$ (${\mathbb{Z}}_2[y]$ is the set of polynomials in $y$ with coefficients from ${\mathbb{Z}}_2$). We interpret an $8-$bit string $a=a_7{a}_6{a}_5\cdots a_1{a}_0$ as coefficients of the polynomial $a(y)=a_7{y}^7+a_6{y}^6+a_5{y}^5+\cdots +a_{1}y+a_0$ and vice versa.

Example

Let $a=11101100=ec$ and $b=00111011=3b$, so $a(y)=y^7+y^6+y^5+y^3+y^2$ and $b(y)=y^5+y^4+y^3+y+1$.

Addition: $a(y)+b(y)=y^7+y^6+y^4+y^2+y+1$, so $ec+3b=d7$.

Multiplication: $a(y)\cdot b(y)=y^{12}+y^{10}+y^8+y^4+y^2$, which leaves a remainder of $r(y)=y^7+y^6+y^3$ upon division by $f(y)$. Hence $a\cdot b=$ $11001000$ in $GF(2^8)$, or $ec\cdot 3b=c8$.

Inversion: $e{c}^{-1}=5d,$ since $ec\cdot 5d=01$.

Definition (S-box)

Let $p\in \{0,1{\}}^8$, and consider $p$ as an element of $GF(2^8)$.

1. Let $q=p^{-1}$ if $p\ne 0$, and $q=p$ if $p=0$
2. Define $q=(q_7{q}_6{q}_5\cdots q_1{q}_0)$
3. Compute

$$\begin{array}{r}S(p)=r=\left(\begin{array}{c}{r}_0\\ r_1\\ r_2\\ r_3\\ r_4\\ r_5\\ r_6\\ r_7\end{array}\right)=\left(\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right)=\left(\begin{array}{c}{q}_0\\ q_1\\ q_2\\ q_3\\ q_4\\ q_5\\ q_6\\ q_7\end{array}\right)+\left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right)\end{array}$$

4. Then $S(p)=r=(r_7{r}_6{r}_5\cdots r_1{r}_0)$

ShiftRows: Permute the bytes of State by applying a cyclic shift to each row.

MixColumns:

1. Read column $i$ of State as a polynomial $(a_{0,i},a_{1,i},a_{2,i},a_{3,i})=a_{0,i}+a_{1,i}x+a_{2,i}{x}^2+a_{3,i}{x}^3$ (interpret the coefficients as elements of the finite field $GF(2^8)$.
2. Multiply this polynomial with the constant polynomial with the constant polynomial $c(x)=02+01x+01x^2+03x^3$ and reduce module $x^4-1$. This gives a new polynomial $b_{0,i}+b_{1,i}x+b_{2,i}{x}^2+b_{3,i}{x}^3$

The $\oplus c(x)$ operation.

Let $a(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3$, where each $a_i\in GF(2^8)$.

Let $c(x)=02+01x+01x^2+03x^3$, where 01, 02, 03 are elements in $GF(2^8)$ (written in hex).

To compute $a(x)\oplus c(x)$ do:

• Compute $d(x)=a(x)\times c(x)$ (polynomial multiplication where coefficient arithmetic is in $GF(2^8)$).
• Divide by $x^4-1$ to find the remainder polynomial $r(x)$. Equivalently, replace $x^4$ by $1$, $x^5$ by $x$, and $x^6$ by $x^2$, and simplify.
• Then $a(x)\oplus c(x)=r(x)$

AES Encryption

From the key $k$ derive $h+1$ subkeys $k_0,k_1,\dots k_h$.

State $\leftarrow$ plaintext

State $\leftarrow$ State $\oplus k_0$

for $i=1,2,\dots ,h-1$ do

	State ← SubBytes(State)
	State ← ShiftRows(State)
	State ← MixColumns(State)
	State ← State ⊕ k_i

State $\leftarrow$ SubBytes(State)

State $\leftarrow$ ShiftRows(State)

State $\leftarrow$ State $\oplus k_h$

ciphertext $\leftarrow$ State

AES Decryption

From the key $k$ derive $h+1$ subkeys $k_0,k_1,\dots ,k_h$

State $\leftarrow$ ciphertext

State $\leftarrow$ State $\oplus k_h$

State $\leftarrow$ InvShiftRows(State)

State $\leftarrow$ InvSubBytes(State)

for $i=h-1,\dots ,2,1$ do

	State ← State ⊕ k_i
	State ← InvMixColumns(State)
	State ← InvShiftRows(State)
	State ← InvSubBytes(State)

State $\leftarrow$ State $\oplus k_0$

plaintext $\leftarrow$ State

For 128-bit keys, AES has 10 rounds, so we need 11 subkeys.

• The first subkey is $k_0=(r_0,r_1,r_2,r_3)$ is the actual AES key.
• The second subkey is $k_1=(r_4,r_5,r_6,r_7)$
• The third subkey is $k_2=(r_8,r_9,r_{10},r_{11})$
• The eleventh subkey is $k_{10}=(r_{40},r_{41},r_{42},r_{43})$

The function $f_i:\{0,1{\}}^{32}\to \{0,1{\}}^{32}$ are defined as follows:

1. The input is divided into four bytes: $(a,b,c,d)$
2. Left-rotate the bytes: $(b,c,d,a)$
3. Apply the AES S-box to each byte: $(S(b),S(c),S(d),S(a))$
4. XOR the leftmost byte with the constant ${\ell }_i$, and output the result: $(S(b)\oplus {\ell }_i,S(c),S(d),S(a))$

The constants ${\ell }_i$ (in hex): ${\ell }_1=01,{\ell }_2=02,{\ell }_3=04,{\ell }_4=08,{\ell }_5=10,{\ell }_6=20,{\ell }_7=40,{\ell }_8=80,{\ell }_9=1b,{\ell }_{10}=36$

Modes of Operation

In practice, one usually wishes to encrypt a large quantity of data. The plaintext message is $m=m_1,m_2,\dots ,m_t$ where each $m_i$ is an $L-$bit block.

Question

How should we use a block cipher $E_k:\{0,1{\}}^L\to \{0,1{\}}^L$ to encrypt $m$?

Some modes of operation: ECB, CBC, CTR, GCM, CCM.

Suppose that the plaintext message is $m=m_1,m_2,\dots ,m_t$

Electronic Codebook Mode (ECB): encrypts the blocks independently, one at a time. Drawback: Identical plaintext result in identical ciphertext blocks.

Cipher Block Chaining (CBC) mode:

Encryption: Select $c_0{\in }_R\{0,1{\}}^L$ ($c_0$ is a random non-secret IV), and then compute $c_i=E_k(m_i\oplus c_{i-1})$ for $i=1,2,\dots ,t$. The ciphertext is $(c_0,c_1,c_2,\dots ,c_t)$.

Decryption: $m_i=E_k^{-1}(c_i)\oplus c_{i-1},$ for $i=1,2,\dots t$.

Identical plaintexts with different IVs result in different ciphertexts.

Chapter 3: Hash Functions

Fundamental Concepts

Hash functions play a fundamental role in cryptography. They are used in a variety of cryptographic primitives and protocols.

They are very difficult to design because of stringent security and performance requirements.

The most commonly used hash functions are:

• SHA-1
• SHA-2 family: SHA-224, SHA-256, SHA-384, SHA-512
• SHA-3 family

SHA-256

SHA-256: $\{0,1{\}}^{\ast }\to \{0,1{\}}^{256}$ SHA-256(“Hello there”) = $\text{0x4e47826698bb4630fb4451010062fadbf85d61427cbdfaed7ad0f23f239bed89}$

Definition

A hash function is a mapping $H$ such that:

1. $H$ maps binary messages of arbitrary lengths $\le L$ to outputs of a fixed length $n$: $H:\{0,1{\}}^{\le L}\to \{0,1{\}}^n$. ($L$ is usually large, e.g., $L=2^{64}$, whereas $n$ is small, e.g. $n=256$)
2. $H(x)$ can be efficiently computed for all $x\in \{0,1{\}}^{\le L}$

$H$ is called an $n-$bit hash function. $H(x)$ is called the hash or message digest of $x$.

Notes:

• The description of a hash function is public; there are no secret keys.
• For simplicity, we will usually write $\{0,1{\}}^{\ast }$ instead of $\{0,1{\}}^{\le L}$
• More generally, a hash function is an efficiently computable function from a set $S$ to a set $T$.

Consider $H:\{0,1{\}}^{\le 4}\to \{0,1{\}}^2$ to be a hash function mapping a bitstring to its last two digits.

$1001$ is a preimage of $01$.

$H(01,1001)$ is a collision. $01$ is a second preimage of $1011$.

Hash functions are used in all kind of applications. One reason for the widespread use of hash functions is speed.

Definition

A hash function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is preimage resistant if, given a hash value $y{\in }_R\{0,1{\}}^n$, it is computationally infeasible to find (with non-negligible success probability) any $x\in \{0,1{\}}^{\ast }$ with $H(x)=y$. ($x$ is called a preimage of $y$.)

Password protection on a multi-user computer system:

• The server stores $[$userid, $H$(password)$]$
• If the attacker obtains a copy of the password file, they do not learn any passwords.
• This requires preimage resistance.

Definition

A hash function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is 2nd preimage resistant if, given $x{\in }_R\{0,1{\}}^{\ast }$, it is computationally infeasible to find (with non-negligible success probability) any $x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$

Modification Detection Codes (MDC’s):

• To ensure that a message $m$ is not modified by unauthorized means, one computes $H(m)$ and protects $H(m)$ from unauthorized modification.
• This is useful protection and requires 2nd preimage resistance.

Definition

A hash function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is collision resistant if it is computationally infeasible to find $x,x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$. Such a pair $(x,x^{\prime })$ is called a collision for $H$.

Message digests for digital signature schemes:

• For reasons of efficiency, instead of signing a long message $x$, the (much shorter) message digest $h=H(x)$ is signed.
• This application requires preimage-resistance, 2nd preimage resistance, and collision resistance.
• To see why collision resistance is required, suppose that the legitimate signer Alice can find a collision $(x_1,x_2)$ for $H$. Alice can sign $x_1$ and later claimed to have signed $x_2$.

Other applications:

• Message Authentication Codes
• Pseudorandom bit generation
• Key derivation functions
• Proof-of-work
• Quantum-safe signature schemes

Relationships between PR, 2PR, CP

Breaking preimage resistance (PR):

Given: $y{\in }_R\{0,1{\}}^n$

Required: $x\in \{0,1{\}}^{\ast }$ with $H(x)=y$.

Breaking 2nd preimage resistance (2PR):

Given: $x \in_{R} {0,1}^*

Required: $x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$

Breaking collision resistance (CR):

Given: $-$

Required: $x,x^{\prime }\in \{0,1{\}}^{\ast }$ with $x^{\prime }\ne x$ and $H(x^{\prime })=H(x)$

Claim $1$: If $H$ is CR, then $H$ is 2PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }to\{0,1{\}}^n$ is not 2PR.

We’ll show that $H$ is not CR.

Select $x{\in }_R\{0,1{\}}^{\ast }$. Since $H$ is not 2PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast },x\ne x$, with $H(x^{\prime })=H(x)$.

Thus, $(x,x^{\prime })$ is a collision for $H$ that we have efficiently found, showing that $H$ is not CR.

Note: This proof established the contrapositive statement.

Claim $2$: CR does not guarantee PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is CR.

Consider the hash function $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^{n+1}$ defined by

$$\begin{array}{r}\overline{H}(x)=\{\begin{array}{ll}0||H(x),& \text{if }x\in \{0,1{\}}^n\\ 1||x,& \text{if }x\in \{0,1{\}}^n\end{array}\end{array}$$

Then $\overline{H}$ is CR (since $H$ is).

And $\overline{H}$ is not PR since preimages can be efficiently found for at least half of all $y\in \{0,1{\}}^{n+1}$, namely the hash values that begin with $1$.

Note: The hash function $\overline{H}$ is rather contrived. For somewhat uniform hash functions, i.e., hash functions for which all hash values have roughly the same number of preimages, CR does not guarantee PR.

Claim $2^{\ast }$: Suppose $H$ is somewhat uniform. If $H$ is CR, then $H$ is PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is not PR.

We’ll show that $H$ is not CR.

Select $x{\in }_R\{0,1{\}}^{\ast }$ and compute $y=H(x)$. Since $H$ is not PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast }$ with $H(x^{\prime })=y$. Since $H$ is somewhat uniform, we expect that $y$ has many preimages, and thus $x^{\prime }=x$ with very high probability. Thus, $(x,x^{\prime })$ is a collision for $H$ that we have efficiently found, so $H$ is not CR.

Claim $3$: PR does not guarantee 2PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is PR.

Define $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ by $\overline{H}(x_1,x_2,\dots ,x_t)=H(0,x_2,\dots ,x_t)$ for all $(x_1,x_2,\dots ,x_t)\in \{0,1{\}}^{\ast }$.

Then $\overline{H}$ is PR. However $\overline{H}$ is not 2PR.

Claim $4$: Suppose $H$ is somewhat uniform. If $H$ is 2PR, then $H$ is PR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is not PR.

We will show that $H$ is not 2PR.

So, suppose we are given $x{\in }_R\{0,1{\}}^{\ast }$. We compute $y=H(x)$.

Since $H$ is not PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast }$ with $H(x^{\prime })=y$.

Since $H$ is somewhat uniform, we expect that $x^{\prime }\ne x$ with very high probability. Hence, $x^{\prime }$ is a second preimage of $x$ that we have efficiently found.

Thus $H$ is not 2PR.

Claim $5$: 2PR does not guarantee CR

Proof: Suppose that $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is 2PR.

Consider $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ defined by $\overline{H}(x)=H(x)$ if $x\ne 1$, and $\overline{H}(1)=H(0)$.

• Then $\overline{H}$ is not CR, since $(0,1)$ is a collision for $\overline{H}$
• Suppose now that $\overline{H}:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ is not 2PR. We’ll show that $H$ is not 2PR.

So, we are given $x{\in }_R\{0,1{\}}^{\ast }$. Since $\overline{H}$ is not 2PR, we can efficiently find $x^{\prime }\in \{0,1{\}}^{\ast },x^{\prime }\ne x$, with $\overline{H}(x^{\prime })=\overline{H}(x)$. With probability essentially $1$, we can assume that $x\ne 0,1$. Hence, $\overline{H}(x)=H(x)$.

Now, if $x^{\prime }\ne 1$, then $H(x^{\prime })=\overline{H}(x^{\prime })=\overline{H}(x)=H(x)$

And, if $x^{\prime }=1$, then $\overline{H}(x^{\prime })=\overline{H}(1)=H(0)=H(x)$.

In either case, we have efficiently found a second preimage for $x$ with respect to $H$.

Hence, $H$ is not 2PR, a contradiction. Thus, $\overline{H}$ is 2PR.

Generic Attacks

Definition

A generic attack on hash functions $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ does not exploit any properties that the specific hash function might have.

In the analysis of a generic attack, we view $H$ as a random function in the sense that for each $x\in \{0,1{\}}^{\ast }$, the hash value $y=H(x)$ was defined by selecting $y{\in }_R\{0,1{\}}^n$.

A random function is an ideal hash function (from a security point-of-view). However they are not practical.

Attack

Given $y{\in }_R\{0,1{\}}^n$, repeatedly select arbitrary $x\in \{0,1{\}}^{\ast }$ until $H(x)=y$.

The expected number of hash operations is $2^n$.

This generic attack is infeasible if $n\ge 128$.

Attack

Select arbitrary $x\in \{0,1{\}}^{\ast }$ and store $(H(x),x)$ in a table sorted by first entry. Repeat until a collision is found.

Analysis: By the birthday paradox, the expected number of hash operations is $\sqrt{\pi 2^n/2}\approx \sqrt{2^n}$

This generic attack is infeasible if $n\ge 256$.

This generic attack for finding collisions is optimal. The expected space required is $\sqrt{\pi 2^n/2}\approx \sqrt{2^n}$.

VW: van Oorschot & Wiener parallel collision search.

The expected number of hash operations: $\approx \sqrt{2^n}$. The expected space required is negligible.

It is easy to parallelize, $m$-fold speedup with $m$ processors.

The VW collision-finding algorithm can easily be modified to find meaningful collisions.

If collision resistance is desired, then use an $n$-bit hash function with $n\ge 256$.

Parallel Collision search (VW method)

Problem: Find a collision for $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$.

Assumption: $H$ is a random function.

Notation: Let $N=2^n$.

Define a sequence $\{x_i{\}}_{i\ge 0}$ by $x_0{\in }_R\{0,1{\}}^n,x_i=H(x_{i-1})$ for $i\ge 1$.

Let $j$ be the smallest index for which $x_j=x_i$ for some $i<j$; such a $j$ must exist. Then $x_{j+\ell }=x_{i+\ell }$ for all $\ell \ge 1$. By the birthday paradox, $E[j]\approx \sqrt{\pi N/2}\approx \sqrt{N}$. In fact, $E[i]\approx \frac{1}{2}\sqrt{N}$ and $E[j-i]\approx \frac{1}{2}\sqrt{N}$.

Now, $i\ne 0$ with overwhelming probability, in which event $(x_{i-1},x_{j-1})$ is a collision for $H$.

Question

How to find $(x_{i-1},x_{j-1})$ without using much storage?

We only store distinguished points.

Distinguished points: Select an easily-testable distinguishing property for elements of $\{0,1{\}}^n$, e.g. leading 32 bits are all 0.

Let $\theta$ be the proportion of elements of $\{0,1{\}}^n$ that are distinguished.

VW method: Compute the sequence $x_0,x_1,x_2,x_3,\dots$ and only store the points that are distinguished.

VW Collision Finding

Stage 1: Detecting a collision

1. Select $x_0{\in }_R\{0,1{\}}^n$
2. Store $(x_0,0,-)$ in a sorted table.
3. $LP\leftarrow x_0$ ($LP$ = last point stored)
4. For $d=1,2,3,\dots$ do:
5. Compute $x_d=H(x_{d-1})$
6. If $x_d$ is distinguished then
   1. If $x_d$ is already in the table, say $x_d=x_b$ where $b<d$, then go to Stage 2
   2. Store $(x_d,d,LP)$ in the table.
   3. $LP\leftarrow x_d$

Stage 2: Finding a collision

1. Set ${\ell }_1\leftarrow b-a,{\ell }_2\leftarrow d-c$
2. Suppose ${\ell }_1\ge {\ell }_2$, and set $k \gets \ell_1 - \ell_2
3. Compute $x_{a+1},x_{a+2},\dots x_{a+k}$
4. For $m=1,2,3,\dots$ do:
5. Compute $(x_{a+k+m},x_{c+m})$
6. Until $x_{a+k+m}=x_{c+m}$
7. The collision is $(x_{a+k+m-1},x_{c+m-1})$

VW Analysis

Stage 1: Expected number of $H$-evaluations is:

$$\begin{array}{r}\sqrt{\pi N/2}+\frac{1}{\theta }\approx \sqrt{N}+\frac{1}{\theta }\end{array}$$

Stage 2: Expected number of $H-$evaluations is $\le \frac{3}{\theta }$

Overall expected running time: $\sqrt{N}+\frac{4}{\theta }$

Expected storage: $\approx 3n\theta \sqrt{N}$ bits

Example

Consider $n=128$. Take $\theta =1/2^{32}$. Then the expected run time of VW collision search is $2^{64}$ $H-$evaluations (feasible), and the expected storage is 192 gigabytes (negligible).

Iterated Hash Functions

Merkle's Meta Method

Components:

• Fixed initializing value $IV\in \{0,1{\}}^n$
• Efficiently-computable compression function $f:\{0,1{\}}^{n+r}\to \{0,1{\}}^n$

To compute $H(x)$ where $x$ has bitlength $b<2^r$ do:

1. Break up $x$ into $r-$bit blocks, $\overline{x}=x_1,x_2,\dots ,x_t$, padding the last block with $0$ bits as necessary.
2. Define $x_{t+1}$, the length-block, to hold the right-justified binary representation of $b$.
3. Define $H_0=IV$.
4. Compute $H_i=f(H_{i-1},x_i)$ for $i=1,2,\dots ,t+1$. (The $H_{i}‘s are called chaining variables).
5. Define $H(x)=H_{t+1}$

Theorem (Merkle)

If the compression function $f$ is collision resistant, then the iterated hash function $H$ is also collision resistant.

Merkle’s theorem reduces the problem of designing collision-resistant hash functions to that of designing collision-resistant compression functions.

A major theme in cryptographic research is to formula precise security definitions and assumptions, and then prove that a protocol is secure.

A proof of security is certainly desirable since it rules out the possibility of attacks being discovered in the future.

However, it isn’t always easy to asses the practical security assurances (if any) that a security proof provides).

• Assumptions might be unrealistic, or false, or circular.
• The security model might not account for certain kinds of realistic attacks.
• The security proof might be asymptotic.

Proof of Merkle’s Theorem ($f$ is CR $⟹H$ is CR)

Suppose that $H$ is not CR. We’ll show that $f$ is not CR.

Since $H$ is not R, we can efficiently find messages $x,x^{\prime }\in \{0,1{\}}^{\ast }$, with $x\ne x^{\prime }$ and $H(x)=H(x^{\prime })$.

Let $\overline{x}=x_1,x_2,\dots ,x_t$, $b$ = bit-length($x$), $x_{t+1}=$ length block.

Let $\overline{x^{\prime }}=x_1^{\prime },x_2^{\prime },\dots ,x_t^{\prime }$, $b^{\prime }$ = bit-length($x^{\prime }$), $x_{t+1}^{\prime }=$ length block.

We can efficiently compute:

$$\begin{array}{rl}{H}_0& =IV\\ H_1& =f(H_0,x_1)\\ H_2& =f(H_1,x_2)\\ & ⋮\\ H_{t-1}& =f(H_{t-2},x_{t-1})\\ H_t& =f(H_{t-1},x_t)\\ H(x)=H_{t+1}& =f(H_t,x_{t+1})\end{array}$$ $$\begin{array}{rl}{H}_0& =IV\\ H_1^{\prime }& =f(H_0,x_1^{\prime })\\ H_2^{\prime }& =f(H_1^{\prime },x_2^{\prime })\\ & ⋮\\ H_{t^{\prime }-1}^{\prime }& =f(H_{t^{\prime }-2}^{\prime },x_{t^{\prime }-1}^{\prime })\\ H_{t^{\prime }}^{\prime }& =f(H_{t^{\prime }-1}^{\prime },x_{t^{\prime }}^{\prime })\\ H(x^{\prime })=H_{t^{\prime }+1}^{\prime }& =f(H_{t^{\prime }}^{\prime },x_{t^{\prime }+1}^{\prime })\end{array}$$

Since $H(x)=H(x^{\prime })$, we have $H_{t+1}=H_{t^{\prime }+1}^{\prime }$

Case 1: Now, if $b\ne b^{\prime }$ then $x_{t+1}\ne x_{t^{\prime }+1}^{\prime }$. Thus, $(H_t,x_{t+1}),H_{t^{\prime }}^{\prime },x_{t^{\prime }+1}^{\prime }$ is a collision for $f$ that we have efficiently found.

Case 2: Suppose next that $b=b^{\prime }$. Then $t=t^{\prime }$ and $x_{t+1}=x_{t+1}^{\prime }$

• Let $i$ be the largest index, $0\le i\le t$, for which $(H_i,x_{i+1})\ne (H_i^{\prime },x_{i+1}^{\prime })$. Such an $i$ must exist since $x\ne x^{\prime }$.
• Then $H_{i+1}=f(H_i,x_{i+1})=f(H_i^{\prime },x_{i+1}^{\prime })=H_{i+1}^{\prime }$, so $(H_i,x_{i+1}),(H_i^{\prime },x_{i+1}^{\prime })$ is a collision for $f$ that we have efficiently found.

Thus, $f$ is not collision resistant $\square$