VE475 Cryptography Note 2

Posted on In Disqus:

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
$$
\newcommand{\ra}[1]{!!!!!!!!!!!!\xrightarrow{\quad#1\quad}!!!!!!!!}
\newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}}
\begin{array}{ccccccccc}
&&&&b_0&&&&b_1&&&&b_2&&&&\dots&&&&b_n\newline
&&&&\Big\downarrow&&&&\Big\downarrow&&&&\Big\downarrow&&&&&&&&\Big\downarrow\newline
IV&&\to&&\oplus&&&&\oplus&&&&\oplus&&&&&&&&\oplus\newline
&&&&\da{E_k}&&\nearrow&&\da{E_k}&&\nearrow&&\da{E_k}&&\nearrow&&&&\nearrow&&\da{E_k}\newline
&&&&c_0&&&&c_1&&&&c_2&&&&&&&&c_n
\end{array}
$$

and the structure of decryption of
$$
\newcommand{\ra}[1]{!!!!!!!!!!!!\xrightarrow{\quad#1\quad}!!!!!!!!}
\newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}}
\begin{array}{ccccccccc}
&&&&c_0&&&&c_1&&&&c_2&&&&\dots&&&&c_n\newline
&&&&\da{E_k^{-1}}&&\searrow&&\da{E_k^{-1}}&&\searrow&&\da{E_k^{-1}}&&\searrow&&&&\searrow&&\da{E_k^{-1}}\newline
IV&&\to&&\oplus&&&&\oplus&&&&\oplus&&&&&&&&\oplus\newline
&&&&\da{}&&&&\da{}&&&&\da{}&&&&&&&&\da{}\newline
&&&&b_0&&&&b_1&&&&b_2&&&&&&&&b_n
\end{array}
$$
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 m_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.
$$
\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

A(Plaintext) --> B(Add Round Key)
style A fill:#87afff
B --> C
subgraph Rounds 1 to 9
C(Sub Bytes) --> D(Shift Rows)
D --> E(Mix Columns)
E --> F(Add Round Key)
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}$.

Add Round Key Layer

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}$