Someone's Intermediate Representation

0%

All info comes from Manuel’s slides on Lecture 2.

# Block Cipher

A block cipher is composed of 2 co-inverse functions:
\begin{aligned} E:\lbrace 0,1\rbrace^n\times\lbrace0,1\rbrace^k&\to\lbrace 0,1\rbrace^n& D:\lbrace 0,1\rbrace^n\times\lbrace0,1\rbrace^k&\to\lbrace 0,1\rbrace^n\\ (P,K)&\mapsto C&(C,K)&\mapsto P \end{aligned}
where $n,k$ means the size of a block and key respectively.

The goal is that given a key $K$ and design an invertible function $E$ whose output cannot be distinguished from a random permutation over $\lbrace 0, 1\rbrace^n$.

## Mode ECB

Electronic Codebook mode has the basic principle that

• Splits the plaintext in blocks of size $n$.
• Encrypt each block with a function $E$ and a key $K$.

\begin{aligned} b_1&&b_2&&b_3&&\dots&&b_n\\ \Bigg\downarrow&&\Bigg\downarrow&&\Bigg\downarrow&&&&\Bigg\downarrow\\ E_k&&E_k&&E_k&&\dots&&E_k\\ \Bigg\downarrow&&\Bigg\downarrow&&\Bigg\downarrow&&&&\Bigg\downarrow\\ c_1&&c_2&&c_3&&\dots&&c_n \end{aligned}

The limitation of ECB mode is that, consider a block is repeated several times over the message, then it is easy to guess what is happening since they share same $K$.

## Mode CBC

Cipher Block Chaining mode has the following structure of encryption

and the structure of decryption of
It have to be done in a sequential way, so it cannot be parallelized. So we can introduce a new method next.

## Mode CTR

$$\newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}} \begin{array}{ccccccccc} ct &&&& ct+1 &&&& ct+2 &&&& \dots &&&& ct+n\newline &&&& \da{E_k} &&&& \da{E_k} &&&& &&&& \da{E_k}\newline &&b_1\longrightarrow&&\oplus&&b_2\longrightarrow&&\oplus&&&&&&b_n\longrightarrow&&\oplus\newline &&&&\da{}&&&&\da{}&&&&&&&&\da{}\newline &&&&c_1&&&&c_2&&&&&&&&c_n \end{array}$$

CT stands for counter, for a new block, it generates new counter value then XOR with block value. It can be run in parallel.

# Randomness Definition

We apply the Kolmogorov randomness definition here, with $x$ be a string

• We way that $x$ is random $\iff$ it is not shorter than any program that can produce it in any language.
• The entropy of $x$ is the minimum number of bits necessary to describe $x$.

Thus, a random string of length $k$ cannot be composed in any way, therefore it has entropy $k$.

# Fermat’s Little Theorem

Let $p\in\mathbb{N}, a\in\mathbb{Z}$. If $p$ is prime and $p\nmid a$, then $a^{p-1}\equiv1\text{ mod }p$.

We can try the proof like that:

Consider $S=\lbrace 1,2,\dots,p-1\rbrace$, then $S\equiv S\text{ mod }p$. If we do $a\cdot S=\lbrace 1\cdot a,2\cdot a,\dots,(p-1)\cdot a\rbrace$, then if $a\cdot S\equiv S\text{ mod }p$ ?

If this was the case, we can have $a\cdot v_0\equiv a\cdot v_1\text { mod }p$ for some $1 \le v_0 < v_1\le p-1$. Since $\text{gcd}(a,p)=1$, then $v_0\equiv v_1\text{ mod }p$, which means $v_0=v_1$, leading to contradiction.

Thus $a\cdot S\equiv S\text{ mod }p$. In this way, we can have
$$\prod (a\cdot S)=(\prod_{i=1}^{p-1}i)\cdot a^{p-1}\equiv (\prod^{p-1}_{i=1}i)\text{ mod }p$$
But we know that $\forall i \in S, i \nmid p$, thus $a^{p-1}\equiv 1\text{ mod }p$.

# Chinese Remainder Theorem

Let $m_1, \dots,m_k\in\mathbb{N}\backslash\lbrace 0\rbrace$ be pairwise relatively prime and $a_1,\dots,a_k\in\mathbb{Z}$. Then the system of congruences
$$\begin{cases} x&&\equiv && a_1\text{ mod }m_1,\newline x&&\equiv && a_2\text{ mod }m_2,\newline &&\vdots\newline x&&\equiv && a_k\text{ mod }m_k. \end{cases}$$
has a unique solution modulo $M= \prod\limits^{k}_{i=1} m_i$.

Then we setup a table here to see what is required:
$$\begin{array}{c|c|c|c} a_i & m_i & M_i & t_i\newline & & \dfrac{M}{m_i} & t_i\cdot M_i\equiv 1\mod a_i \end{array}$$
The solution space is $\lbrace kM+\sum\limits^n_{i=1}a_i t_iM_i\rbrace$ where $k\in\mathbb{Z}$.

# Squares Modulo Prime

Lemma: If $p\equiv 3\mod 4$ is prime, then equation $x^2\equiv -1\pmod p$ has no solution.

Proof: Suppose $x$ exists, then by Fermat’s Little Theorem, $(x^2)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod p$.

But the $p\equiv 3\mod 4$, implies $\frac{p-1}{2}$ odd and $(-1)^{\frac{p-1}{2}}\equiv -1\pmod p$.

## Proposition

Let $p\equiv 3 \mod 4$ be prime, $y$ be an integer and $x\equiv y^{\frac{p+1}{4}}\pmod p$.

• If $y$ has a square root mod $p$, then its square roots are $\pm x\pmod p$.
• If $y$ has no square root mod $p$, then the square roots of $-y$ are $\pm x\pmod p$.

Proof: According to Fermat’s Little Theorem, we get $x^4 \equiv y^{p+1}\equiv y^2\pmod p$.

According to Bezout Theorem, since $p$ prime, then for all non zero elements, there exists multiplicative inverse.

Therefore we rewrite previous eq into $(x^2 - y)(x^2+y)\equiv 0\pmod p$ implies $x^2\equiv\pm y\pmod p$.

Consider exists $a$ and $b$ satisfying at the same time that $y\equiv a^2\pmod p$ and $-y\equiv b^2\pmod p$.

Then $(b^{-1} a)^2\equiv -1\pmod p$, then this contradicts lemma.

Hence exactly only one of $y$ and $-y$ has square roots $\pm x\pmod p$.

# BBS Generator

BBS Generator is a Pseudo-Random Bits Generator.

• Let $p,q$ be 2 large primes with $p\equiv q\equiv 3\pmod 4$.
• Set $n=p\cdot q$.
• Choose a random integer $x$ coprime to $n$.
• Define $\begin{cases}x_0&\equiv x^2\pmod n\\\vdots\\x_{i+1}&\equiv x^2_{i+1}\pmod{n}\end{cases}$
• At each iteration, choose the least significant bit of $x_i$.

## Proposition

Let $n=p\cdot q$ with $p,q$ follow BBS Generator requirements.

Let $x\equiv \pm a,\pm b\pmod n$ be the four solutions to $x^2\equiv y\pmod n$.

Then $\gcd(a-b,n)$ is a non-trivial factor of $n$.

## Building Block Cipher

A random oracle is a “black box” that returns a truly uniform random output on an input.

Submitting same input leads to same output.

Pseudorandom function emulates a random oracle.

A pseudorandom function that cannot be distinguished from a random permutation is pseudo random permutation. A blockcipher is a pseudorandom permutation.

# Feistel Network - DES

This is just one node of Feistel network.
$$\require{AMScd} \begin{CD} L_0 @. R_0\newline @V VV @V VV\newline \oplus@<F_K<< R_0\newline @V VV @V VV\newline R_1 @.L_1 \end{CD}$$

• The size of a block: $2n$ bits
• Split the block into 2 blocks of $n$ bits each
• $F:\lbrace 0,1\rbrace^n\times\lbrace 0,1\rbrace^k\to\lbrace 0, 1\rbrace^n$

Then we define function \begin{aligned}\Psi_F: \lbrace 0,1\rbrace^{2n}&\to\lbrace 0,1\rbrace^{2n}\newline \lbrack L, R\rbrack&\mapsto\lbrack R, L\oplus F(R,K)\rbrack\end{aligned}

## Inverse Function

$\forall F$, $\Psi_F$ is a bijection and $\Psi_F^{-1}=\sigma\circ\Psi_F\circ\sigma$, with \begin{aligned}\sigma:\lbrace 0,1\rbrace^{2n}&\to\lbrace 0,1\rbrace^{2n}\newline\lbrack L,R\rbrack&\mapsto\lbrack R,L\rbrack\end{aligned}

This can be shown by definition that $\Psi_F\lbrack L_0,R_0\rbrack = \lbrack R_0,L_0\oplus F(R_0,K)\rbrack=\lbrack L_1,R_1\rbrack$.

Thus \begin{aligned} \sigma\circ\Psi_F\circ\sigma \lbrack L_1,R_1\rbrack &=\sigma\circ \Psi_F\lbrack R_1,L_1\rbrack\newline &= \sigma\circ\Psi_F\lbrack L_0\oplus F(R_0,K),R_0\rbrack\newline &=\sigma\lbrack R_0, L_0\oplus F(R_0,K)\oplus F(R_0,K)\rbrack\newline &=\lbrack R_0, L_0\rbrack \end{aligned}

## Attack

Setting up 2 black boxes, a random oracle and a Feistel network, the goal for an attack is to distinguish them.
$$\begin{array}{c|rrr} \text{Rounds} & \text{KPA} & \text{CPA} & \text{CPCA} \newline \hline 1 & 1 & 1 & 1 \newline 2 & O(\sqrt{2^n}) & 2 & 2 \newline 3 & O(\sqrt{2^n}) & O(\sqrt{2^n}) & 3\newline 4 & O(2^n) & O(\sqrt{2^n}) & O(\sqrt{2^n}) \end{array}$$

### Two rounds - CPA

For simplify, we donate $\Psi_{F_{K_2}}\circ\Psi_{F_{K_1}}$ by $\Psi_{F_{K_1},F_{K_2}}^2$. $\Psi_{F_{K_1},F_{K_2}}^2\lbrack L_0, R_0\rbrack = \lbrack L_2, R_2\rbrack$ with $\begin{cases} L_2 &=L_0\oplus F_{K_1}(R_0)\newline R_2&= R_0\oplus F_{K_2}(L_2)\end{cases}$ ($L_2 = R_1$ which can be seen in previous part).

Thus the inverse of $\Psi_{F_{K_1},F_{K_2}}^2$ is $\Psi_{F_{K_1},F_{K_2}}^{-2} = \Psi_{F_{K_1}}^{-1}\circ\Psi_{F_{K_2}}^{-1} = \sigma\circ\Psi_{F_{K_2},F_{K_1}}^2\circ\sigma$.

If we use $m_1 = \lbrack m_{1_L}, m_{1_R}\rbrack$ and $m_2=\lbrack m_{2_L},m_{2_R}\rbrack$ such that $\begin{cases} m_{1_L}\neq m_{2_L}\newline m_{1_R}=m_{2_R}\end{cases}$, we can see $\begin{cases}m_1 &\Rightarrow \begin{cases} R_2 &= m_{1_R}\oplus F_{K_2}(L_2)\newline L_2 &=m_{1_L}\oplus F_{K_1}(m_{1_R})\end{cases}\newline m_2 &\Rightarrow \begin{cases}R_2 &= m_{2_R}\oplus F_{K_2}(L_2)\newline L_2 &=m_{2_L}\oplus F_{K_1}(m_{2_R})\end{cases}\end{cases}$.

It is easy to see $\begin{cases}m_{1_{R_2}}\oplus m_{2_{R_2}} &=m_{1_R}\oplus m_{2_R}\newline m_{1_{L_2}}\oplus m_{2_{L_2}} &=m_{1_L}\oplus m_{2_L}\end{cases}$, which only requires 2 test for 2 round Feistel network.

### Two rounds - KPA

Find a collision over $m_{i_R}$, where $1 \le i \le 2^n$. By birthday paradox, this requires $O(\sqrt{2^n})$ message.

If a collision is found for $m_j$ and $m_i$, check if $m_{j_{L_2}}\oplus m_{l_{L_2}}=m_{j_{L_0}}\oplus m_{l_{L_0}}$.

The collision on $m_{i_{L_2}}=m_{i_{L_0}}\oplus F_{K_1}(m_{i_{R_0}})$ for 2 messages, just like what is mention in previous 2-round CPA part.

Fix $m_{i_{L_2}}$, $m_{i_{L_0}}$ and $m_{i_{R_0}}$, then the uncertain outcome is $m_{j_{L_2}}$. Since it depends on $F_{K_1}$, which maps variables to $2^n$ different values.

If we take $l$ time same message with probably different $K$, then $\dfrac{l(l-1)}{2}$ pairs can be constructed and the possibility of collision is $\dfrac{l(l-1)}{2\cdot 2^n}$.

### Three rounds - CPCA

$\Psi^2_{F_{K_1},F_{K_2},F_{K_3}} \lbrack L_0, R_0\rbrack=\lbrack L_3,R_3\rbrack$ with $\begin{cases} L_3 &=R_0\oplus F_{K_2}(L_2)\newline R_3&=L_2\oplus F_{K_3}(L_3)\end{cases}$ and $L_2=L_0\oplus F_{K_1}(R_0)$.

Notice for a pair of messages $(m_a, m_b)$, $\begin{cases}m_{a_{R_0}} = m_{b_{R_0}} &\Rightarrow m_{a_{L_2}}\oplus m_{b_{L_2}} = m_{a_{L_0}}\oplus m_{b_{L_0}}\newline m_{a_{L_2}} = m_{b_{L_2}} &\Rightarrow m_{a_{L_3}}\oplus m_{b_{L_3}} = m_{a_{R_0}}\oplus m_{b_{R_0}}\newline m_{a_{L_3}} = m_{b_{L_3}} &\Rightarrow m_{a_{R_3}}\oplus m_{b_{R_3}} = m_{a_{L_2}}\oplus m_{b_{L_2}}\newline\end{cases}$ can be used to verify.

The attack strategy is constructed then by taking $m_1$, $m_2$, $m_3$ satisfying $\begin{cases} m_{2_{R_0}} &=m_{1_{R_0}}\newline m_{3_{L_3}} &=m_{2_{L_3}}\newline m_{3_{L_2}} &=m_{1_{L_2}} \end{cases}$ where a graph can be formed like

graph LR

subgraph attack
A((m1))
B((m2))
C((m3))
A ---|R0| B
B ---|L3| C
A ---|L2| C
end

From the previous equation sets we get $\begin{cases} m_{2_{R_0}} &=m_{1_{R_0}}\newline m_{3_{L_3}} &=m_{2_{L_3}}\newline m_{3_{R_3}} &=m_{2_{R_3}}\oplus m_{1_{L_0}} \oplus m_{2_{L_0}} \end{cases}$ ($m_{1_{L_2}}\oplus m_{2_{L_2}} = m_{1_{L_0}}\oplus m_{2_{L_0}} = m_{1_{R_3}}\oplus m_{2_{R_3}}$)

Finally, $m_{3_{R_0}} = m_{1_{L_3}} \oplus m_{3_{L_3}} \oplus m_{1_{R_0}}$.

# AES - Encryption

graph TD

style A fill:#87afff
B --> C
subgraph Rounds 1 to 9
C(Sub Bytes) --> D(Shift Rows)
D --> E(Mix Columns)
F -->|1 to 9| C
subgraph Round 10
C --> H(Shift Rows)
H --> F
end
end
F --> G(Ciphertext)
style G fill:#ffd700

There are 128 bits, grouped into 16 bytes, and arranged into a $4\times 4$ matrix: $\begin{bmatrix} a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3}\newline a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3}\newline a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \newline a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3}\end{bmatrix}$. (Plaintext is arranged in order $a_{0,0}, a_{1,0},a_{2,0},a_{3,0},a_{0,1}\dots$)

## Finite Field

Loosely speaking, a set where addition and multiplication operations are defined and such that non-zero element is invertible for multiplication is called a field.

For each prime $p$ and positive integer $n$ there exists a finite field with $p^n$ elements, donated as $\mathbb{F}_{p^n}$.

Polynomials can also be defined over finite fields. The main difference relies on the coefficients: their values are taken in the base field.

A polynomial, in a field, cannot be written as the product of two polynomials of lower degree is said to be irreducible.

So long it has some root, then it can not be irreducible.

$\mathbb{F}_2\lbrack X\rbrack$, $X^2+3X + 1 = X^2 + X + 1$.

$\mathbb{F}_5\lbrack X\rbrack$, $X^3 + X + 3 = (X + 4)(X ^ 2 + X + 2)$ is not irreducible.

$\mathbb{F}_{17}\lbrack X\rbrack$, $X^3 + X + 3$ is irreducible.

### Theorem on Non-Prime Fields

We can construct a non-prime field from prime field.

Let $P(X)$ be an irreducible polynomial of degree $n$ in $\mathbb{F}_p\lbrack X \rbrack$, and $F$ be the set of all polynomial of degree less than $n$. Then $F$ is a finite field with $p^n$ elements.

Proof: $F$ has $p^n$ elements since $n$ monomials and $p$ different values taken.

Assume $A(X),B(X),C(X)$ be distinct non-zero polynomials such that $A(X)B(X)\equiv A(X)C(X)\pmod{P(X)}$, this implies $A(X)(B(X) - C(X))\equiv 0\pmod{P(X)}$.

Contradicting to $P(X)$ irreducible.

Hence, it applies for all polynomial $A(X)$ in $F$ such that there exists $B(X)$ satisfying $A(X)B(X)\equiv 1\pmod{P(X)}$.

We donate these non-prime fields as $\mathbb{F}_{p^n}\lbrack X\rbrack = \mathbb{F}_p\lbrack X\rbrack / \langle F(X)\rangle$.

## Finite Fields in AES

Finite fields in AES is used like:

• $P(X) = X^8+X^4+X^3+X+1$ is irreducible over $\mathbb{F}_2\lbrack X\rbrack$.
• The polynomial is described as a byte $a_7 a_6 a_5 a_4 a_3 a_2 a_1 a_0$.
• The sum of 2 polynomials is $b_0 \oplus b_1 = \prod\limits^7_{i=1} (a_{0i}\oplus a_{1i})$.
• Multiplying a polynomial $Q(X)$ by $X$:
• Shift left the byte representation of $Q(X)$ and append a $0$.
• If the first bit is $0$, then stop. Otherwise XOR with $P(X)$. (since $Q(X)$ left shift by 1 equals to $P(X) + Q’(X)$)
• Multiplying $Q(X)$ by $R(X)$:
• Split $R(X)$ into monomials $M_i(X), i\le\deg R(X)$.
• For $M_i(X)$ applying multiplication by $X\deg M_i(X)$ times.
• Add all results using XOR.

## S-Box SubBytes Layer

S-Box can be generated by:

• Compute $b = a^{-1}$ on $\mathbb{F}_{2^8}$ or set $b=0$ if $a=0$.

• Represent $b$ as a column vector $B = (b_0,\dots,b_7)$.

• Compute
$$\begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1\newline 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1\newline 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1\newline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1\newline 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\newline 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0\newline 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0\newline 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} b_0 \newline b_1 \newline b_2\newline b_3 \newline b_4 \newline b_5 \newline b_6 \newline b_7 \newline \end{pmatrix} + \begin{pmatrix} 1 \newline 1 \newline 0 \newline 0 \newline 0\newline 1 \newline 1 \newline 0 \end{pmatrix} = \begin{pmatrix} c_0 \newline c_1 \newline c_2\newline c_3 \newline c_4 \newline c_5 \newline c_6 \newline c_7 \newline \end{pmatrix}$$

## ShiftRows Layer

Cyclically shift to left row $i$ by offset $0 \le i \le 3$.

## Mix Columns Layer

Let the original matrix be $A$, then the output is $C(X)\cdot A$ where $C(X) =\begin{pmatrix} 2 & 3 & 1 & 1\newline 1& 2 & 3 & 1\newline 1 & 1 & 2 & 3\newline 3 & 1 & 1 & 2\end{pmatrix}$.

The inverse $C(X)^{-1} = \begin{pmatrix} 14& 11& 13& 9 \newline 9& 14& 11& 13 \newline13& 9&14& 11 \newline 11& 13& 9 & 14\end{pmatrix}$.

The roundkey is generated by a $4\times4$ matrix $K(X)$.

Label the first four columns $K(0),\dots,K(3)$ and add $40$ more:

• $K(i) = K(i-4)\oplus K(i-1)$ for $i\not\equiv 0\pmod 4$
• $K(i) = K(i-4)\oplus T(K(i-1))$ for $i\equiv 0\pmod 4$

The transformation $T(K(i-1))$ is defined over column $i$:

• Compute $r(i) = 00000010^{\frac{i-4}{4}}$
• Cyclically top shift elements of column by 1: $(a,b,c,d)^{T}\to(b,c,d,a)^{T}$
• Apply S-box to each byte of the column
• Finally the column vector $T(K(i-1))=(s(b)\oplus r(i),s(c),s(d),s(a))^{T}$