就在这瞬间，黎明的晨星躲到云中了。
# Stream Ciphers
# What is a Cipher?
Definition: A cipher defined over $(\mathcal{K},\mathcal{M},\mathcal{C})$ is a pair of “efficient” algorithms $(E,D)$ where:
$E:\mathcal{K}\times\mathcal{M}\rightarrow\mathcal{C}\\ D:\mathcal{K}\times\mathcal{C}\rightarrow\mathcal{M}\\ s.t.\;\forall m\in\mathcal{M},k\in\mathcal{K},D(k,E(k,m))=m$
where $\mathcal{K}$ is referred as key space, $\mathcal{M}$ is referred as message space, $\mathcal{C}$ is referred as cipher space.
Sometimes we also use notation PT
(Plain Text) and CT
(Cipher Text).
The function $E$ is called encryption and $D$ is called decryption. While $D(k,E(k,m))=m$ means the consistency that given a key $k$, then for any message $m$, the decryption of the encryption of $m$ is $m$.
What is also important that we always assume that the function $E$ and $D$ are open to the public, while only the key $k$ is kept secret.
 Example:The One Time Pad
OTP
(Vernam 1917)
$\begin{aligned} & \mathcal{M}=\{0,1\}^n\\ & \mathcal{K}=\{0,1\}^n\\ & \mathcal{C}=\{0,1\}^n\\ & E(k,m)=k\oplus m\\ & D(k,c)=k\oplus c \end{aligned}$
Where $\oplus$ is bitwise xor. The One Time Pad is fast and secure if we choose the $k$ randomly. However, it needs as long keys as the plain text.
# What is a secure cipher?
Let’s assume that the attacker only have the CT
, and the secruity requirement is that the attacker cannot get any information from it.
Definition (Information Theoretic Security, Shannon 1949): A cipher $(E,D)$ over $(\mathcal{K},\mathcal{M},\mathcal{C})$ is perfect secrecy if:
$\begin{aligned} &\forall m_0,m_1\in\mathcal{M},c\in\mathcal{C},\\ &\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[E(k,m_0)=c]=\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[E(k,m_1)=c]\\ \end{aligned}$
where $k\stackrel{R}{\leftarrow}\mathcal{K}$ means that $k$ subjects to the uniform distribution over $\mathcal{K}$.
The definition indicates that given CT
can’t tell if the message is $m_0$ or $m_1$, in other words, the attacker cannot get any information about PT
from the CT
.
However, other attacks (not only from CT
) may be possible.
Lemma: OTP
is a perfect secrecy cipher, it reveals nothing about PT
.(except possible maximum length, from wikipedia).
Proof: First given a message, we can pad it with 0 to the maximum length of $m$. Then:
$\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[E(k,m)=c]=\frac{\#k,k\in\mathcal{K},E(k,m)=c}{\mathcal{K}}=\frac{1}{\mathcal{K}}$
because $E(k,m)=c \Rightarrow k=m\oplus c$, so the number of keys satisfying this condition is $1$.
Then the proof is selfevident, since for any PT
and CT
, the probability of encryption is all the same.
Theorem: If a cipher $(E,D)$ over $(\mathcal{K},\mathcal{M},\mathcal{C})$ is perfect secrecy, then:
$\mathcal{K}\geq\mathcal{M}$
Which indicates that if we want a cipher to be perfect secrecy, we need to have at least as many keys as messages, which is impractical.
# Pseudorandom Generators
How to make OTP
more practical?
 Idea: to replace the “random” key by “pseudorandom” key, which is much smaller.
Definition: A pseudorandom generator PRG
is a “efficient” function:
$G:\{0,1\}^s\rightarrow\{0,1\}^n,n>>s$
where $\{0,1\}^s$ is called the seed space.
Then $E(k,m)=m\oplus G(k),D(k,c)=c\oplus G(k)$.
Now since the length of $k$ is much smaller than plain text, so it’s impossible to be perfect secure. However, we will define other security requirements later.
Definition: A PRG
$G$ is predictable if there exists an “efficient” algorithm $A$ such that:
$\exists 0\leq i\leq n1,\\s.t.\; \mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\{0,1\}^s}[A(G(k)_{1,...,i})=G(k)_{i+1}]>\frac{1}{2}+\varepsilon$
where $\varepsilon$ is a nonnegligible const.
The definition says that, the PRG
is predictable if there exists an algorithm, which is able to predict the $i+1$ bit of the output given the first $i$ bits of the output. And $A$ works well in most cases.
 Example: random() function if glibc:
$r[i]:=(r[i3]+r[i31])\%2^{32}\\ return\;r[i]>>1;$
is a typical weak PRG
and should NOT be used for crypto.
# Negligible vs. Nonnegligible
 In practice: Whether $\varepsilon$ is negligible is defined as a scalar, e.g. $\varepsilon\geq\frac{1}{2^{30}}$ is nonnegligible since it is likely to happen in 1GB data.
 In theory: $\varepsilon$ is a function $\varepsilon(\lambda)$. $\varepsilon(\lambda)$ is negligible if $\forall d,$ $\varepsilon(\lambda)$ congruent to 0 faster than $\frac{1}{\lambda^d}$. While is nonnegligible otherwise.
# Attacks to OTP
# Two time pad is insecure!
If we use the cipher key more than once:
$c_1\leftarrow m_1\oplus PRG(k)\\ c_2\leftarrow m_2\oplus PRG(k)\\$
then the attacker can get $m_1\oplus m_2$ by xoring $c_1,c_2$.
There are enough redundancy in English and ASCII to recover $m_1,m_2$ by knowing $m_1\oplus m_2$.
 Real world examples:Project Venona, MSPPTP
# OTP
is malleable and provides no integrity!
which means that tha attacker can easily modify the plain text even don’t need to know about it.
If the attacker get a CT
$c=m\oplus k$, then he can modify it by $c\oplus p$, and send it back. The receiver will decrypt it as $m\oplus p$, which is modified by the attacker.
# What is a secure PRG
?
Definition: A statistical test on $\{0,1\}^n$ is an “efficient” algorithm $A$, s.t. $A(x)$ outputs “0” or “1”.
 Example: $A(x)$ outputs “1” iff $\#0(x)\#1(x)<10\sqrt{n}$. Meaning that if the number of 0 and 1 is not too different, then the test $A$ believes that the string is random.
Definition(Advantage):let $G$ be a PRG
and $A$ a statistical test on $\{0,1\}^n$, then the advantage is defined as:
$Adv_{PRG}[A,G]=\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[A(G(k))=1]\mathop{Pr}\limits_{r\stackrel{R}{\leftarrow}\{0,1\}^n}[A(r)=1]$
which says given a stat. test $A$, whether $A$ can tell the difference between PRG
and a real random.
Definition: We say a PRG
$G$ is a secure PRG
if $\forall$ “efficient” statistical test $A$, $Adv_{PRG}[A,G]$ is negligible.
Lemma: a predictable PRG
is insecure.
Proof: if $G$ is a predictable PRG
, then there exists a predict algorithm $A$ satisfying:
$\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\{0,1\}^s}[A(G(k)_{1,...,i})=G(k)_{i+1}]>\frac{1}{2}+\varepsilon$
Now we can define a statistical test $B$ separating $G$ and random:
$B(x)=\begin{cases} 1 & A(x_{1,...,i})=x_{i+1}\\ 0 & otherwise \end{cases}$
For real random, we have:
$\mathop{Pr}\limits_{r\stackrel{R}{\leftarrow}\{0,1\}^n}[B(r)=1]=\frac{1}{2}$
because in real random, $A(r_{1,...,i})=r_{i+1}$ and $A(r_{1,...,i})\neq r_{i+1}$ are of the same probability.
and we have:
$\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[B(G(k))=1]>\frac{1}{2}+\varepsilon$
then:
$Adv[B,G]>\varepsilon$
QED.
Theorem(Yao’82): an unpredictable PRG
is secure.
Definition: Let $P_1,P_2$ be two distributions over $\{0,1\}^n$, then we say $P_1,P_2$ are computationally indistinguishable if for any “efficient” statistical test $A$,
$\mathop{Pr}\limits_{x\stackrel{R}{\leftarrow}P_1}[A(x)=1]\mathop{Pr}\limits_{x\stackrel{R}{\leftarrow}P_2}[A(x)=1]$
is negligible. Denoted as $P_1\approx_P P_2$
# Semantic security
Definition: We say a cipher $(E,D)$ over $(\mathcal{K},\mathcal{M},\mathcal{C})$ is semantically secure if:
$\forall m_1,m_2\in\mathcal{M},\\ k\stackrel{R}{\leftarrow}\mathcal{K}\\ \{E(k,m_1)\}\approx_P\{E(k,m_2)\}$
where $\{E(k,m_1)\}$ is a probability distribution over $\mathcal{C}$.
Given $b=0,1$ and an “efficient” algorithm $A$, we can define two experiments:
Adversary $A$ give two messages to the challenger, then the challenger will give back the cipher text determined by $b$ and randomly chosen $k$. But $A$ don’t know $b$, then $A$ will guess the value of $b$.
Let $Pr[W_0]$ is "when $b=0$ and $k$ is randomly chosen, the probability that $A$ guess $b=1$".
And let $Pr[W_1]$ is "when $b=1$ and $k$ is randomly chosen, the probability that $A$ guess $b=1$".
Let’s define:
$Adv_{SS}[A,E]=Pr[W_0]Pr[W_1]$
then $E$ is semantically secure if for any $A$,$Adv_{SS}[A,E]$ is negligible.
 Example: Given a cipher, which we can guess the last bit of
PT
byCT
. Then we can construct a $A$: choose two messages $m_0,m_1$ with different last bit.
 pass $m_0,m_1$ to the challenger.
 after receive the
CT
, guess the last bit ofPT
byCT
.  output the guess.
in this case, $Adv_{SS}[A,E]=1$. Since $A$ can always guess right. So it’s not semantically secure.
Lemma: Perfect secure $\Rightarrow$ Semantically secure.
Proof:obviously,
$\{E(k,m_1)\}=\{E(k,m_2)\}\Rightarrow \{E(k,m_1)\}\approx_P\{E(k,m_2)\}$
# Stream ciphers are semantically secure
Theorem: Let $G:\mathcal{K}\rightarrow\{0,1\}^n$ be a PRG
, then $G$ is a secure PRT
$\Rightarrow$ stream cipher OTP
$E$ derived from $G$ is semantically secure.
Proof: we just need to prove that, $\forall$ adversary $A$, $\exists B$ s.t.
$Adv_{SS}[A,E]\leq 2 Adv_{PRG}[B,G]$
Given an adversary $A$, we can construct two experiments:
one using $G(k)$ and one using real random $r$ to crypt.
Let $W_0$ is when $b=0$, the guess of first exp is 1.
Let $W_1$ is when $b=1$, the guess of first exp is 1.
Let $R_0$ is when $b=0$, the guess of second exp is 1.
Let $R_1$ is when $b=1$, the guess of second exp is 1.
Since OTP
is perfect secrecy when real random:
$Pr[R_0]Pr[R_1]=0$
Next we need to construct an adversary $B$ to PRG
, and prove:
$Pr[W_0]Pr[R_0]\leq Adv_{PRG}[B,G]$
We can construct $B$ as follows:
then
$\mathop{Pr}\limits_{r\stackrel{R}{\leftarrow} \{0,1\}^n}[B(r)=1]=Pr[R_0]\\ \mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[B(G(k))=1]=Pr[W_0]$
then:
$Adv_{PRG}[B,G]=\mathop{Pr}\limits_{r\stackrel{R}{\leftarrow} \{0,1\}^n}[B(r)=1]\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[B(G(k))=1]\\ =Pr[R_0]Pr[W_0]$
So:
$Adv_{PRG}[B,G]=Pr[R_0]Pr[W_0]=Pr[R_1]Pr[W_1]$
Since $Pr[R_0]=Pr[R_1]$, so:
$Pr[W_0]Pr[W_1]\leq 2 Adv_{PRG}[B,G]$
So if PRG
is secure, then $Adv_{PRG}[B,G]$ is negligible, then $Adv_{SS}[A,E]$ is negligible.
QED.
# Block cipher
# What is a block cipher?
 Example: 3DES,n=64,k=168
 Example: AES,n=128,k=128 or 192 or 256
The process of encryption is:
for 3DES,n=48; for AES,n=10.
Definition: Pseudo Random Function PRF
defined over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ :
$F:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}$
such that exists an “efficient” algorithm to evaluate $F$.
Pseudo Random Permutation PRP
defined over $(\mathcal{K},\mathcal{X})$ :
$E:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{X}$
such that :
 Exists “efficient” deterministic algorithm to evaluate $E$.
 The function $E(k,\cdot)$ is onetoone.
 Exists “efficient” inversion algorithm $D(k,y)$.
 Example: 3DES, where $\mathcal{X}=\{0,1\}^{64},\mathcal{K}=\{0,1\}^{168}$.
Definition: Let $F:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}$ be a PRF
and $S_F=\{F(k,\cdot),k\in\mathcal{K}\}$. Then the PRF
is secure if a random function in $S_F$ is indistinguishable from a random function in $\mathcal{Y}^\mathcal{X}$.
 An easy application: let $F:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n$ be a secure
PRF
, then we can construct a securePRG
:
$G:\mathcal{K}\rightarrow\{0,1\}^{nt}\\ G(k)=F(k,0)F(k,1)\cdotsF(k,t1)$
the PRG
is parallelizable and is secure.
# Data encryption standard (DES)
The core idea of DES
is Feistel Network: Given functions $f_1,...,f_d:\{0,1\}^n\rightarrow\{0,1\}^n$, build an invertible function $F:\{0,1\}^{2n}\rightarrow\{0,1\}^{2n}$:
where
$\begin{cases} R_i=f_i(R_{i1})\oplus L_{i1}\\ L_i=R_{i1} \end{cases}$
It’s easy to construct the inverse network:
where
$\begin{cases} R_{i1}=L_i\\ L_{i1}=f_i(L_i)\oplus R_i \end{cases}$
Theorem(LubyRackoff’85): if $f:\mathcal{K}\times \{0,1\}^n\rightarrow\{0,1\}^n$ is a secure PRF
, then 3round Feistel Network $F:\mathcal{K}^3\times\{0,1\}^{2n}\rightarrow \{0,1\}^{2n}$ is a secure PRP
.
The DES
is a 16round Feistel Network, the Key size is 56 bits and block size is 64 bits, in other word, $DES:\{0,1\}^{56}\times\{0,1\}^{64}\rightarrow\{0,1\}^{64}$:
where $F(k_i,x)$ works as follows:
where half block is $x$ and subkey is $k_i$. “E” stands for some shifts and expand tricks, “P” is for permutation, while the “S” SBox are functions $\{0,1\}^6\rightarrow\{0,1\}^4$. The choice of SBox function matters a lot.
If the SBox is linear, like:
$S_i(x_1,x_2,x_3,x_4,x_5,x_6)=(x_2\oplus x_3,x_1\oplus x_4\oplus x_5,x_1\oplus x_6,x_2\oplus x_3\oplus x_6)$
then we can rewrite it in matrix as $S_i(\textbf{x})=A_i\cdot \textbf{x}(mod\;2)$.
Then the DES
is entirely linear, and we have:
$DES(k,m_1)\oplus DES(k,m_2)\oplus DES(k,m_3)=DES(k,m_1\oplus m_2\oplus m_3)$
which is insecure.
Choosing SBox and PBox randomly would result in an insecure block cipher, the key would recover after $\approx 2^{24}$ outputs [BS’89]
There are several rules to choose PBox and SBox, the most important one is never choose any linear function.
# Exhaustive Search for block cipher key
Goal: given a few input output pairs $(m_i,c_i=E(k,m_i),i=1,2,3$, find the key $k$.
Lemma: Suppose DES
is an ideal cipher (indistinguishable from a random $2^{56}$ permutation function $\pi(k,\cdot)$), then $\forall m,c$, there is at most one $k$ such that $c=DES(k,m)$ with probability $\geq \frac{255}{256}\approx 99.5\%$.
Proof:
$Pr[\exists k'\neq k,DES(k',m)=DES(k,m)]\leq\sum_{k'\in\{0,1\}^{56}}Pr[DES(k',m)=DES(k,m)]\\ =2^{56}\cdot\frac{1}{2^{64}}=\frac{1}{2^8}$
so the probability that there does not exists $k'$ is $1\frac{1}{2^8}\approx 99.5\%$.
QED.
For two DES pairs $(m_1,c_1),(m_2,c_2)$, the prob. that key is unique is $\approx 1\frac{1}{2^{71}}$.
So with exhaustive searching method, we can find the key in time $2^{56}$.
We can strengthen DES
against exhaustive search.
Method 1: TripleDES, let $3E:\mathcal{K}^3\times \mathcal{M}\rightarrow\mathcal{M}$ as
$3E((k_1,k_2,k_3),m)=E(k_1,D(k_2,E(k_3,m)))$
for 3DES, key size=168 bits.
Why we don’t use Double DES
? like $2E((k_1,k_2),m)=E(k_1,E(k_2,m))$?
We will introduce a Meet in the middle attack:
since
$E(k_1,m)=D(k_2,c)$
Then we can construct a table:
$k^0=00\cdots 00$  $E(k^0,m)$ 

$k^1=00\cdots 01$  $E(k^1,m)$ 
$\cdots$  $\cdots$ 
$k^N=11\cdots 11$  $E(k^N,m)$ 
and sort the table by the second column $E(k^i,m)$.
Then we can enumerate $k_2$, and binary search $D(k_2,c)$ in the table, to find $D(k_2,c)=E(k^i,m)$.
So the total time is $O(2^{56}log(2^{56}))$ which is not large enough.
Method 2: DESX
Define $EX((k_1,k_2,k_3),m)=k_1\oplus E(k_2,m\oplus k_3)$
It’s noteworthy that if DESX is defined as $k_1\oplus E(k_2,m)$ or $E(k_2,k_1\oplus m)$, then it does nothing, it’s as vunerable to exhaustive search as DES.
# AES block cipher
Advanced Encryption Standard AES
Key size: 128 or 192 or 256 bits
Block size: 128 bits
where the input is 4x4=16 bytes and the key is 16 bytes.
each round contains 3 function:
 Bytes substitution: a nonlinear function 1 byte $\rightarrow$ 1 byte. The SBox is a 256size table.
 Shift rows:
 Mix columns: the four bytes of each column of the state are combined using an invertible linear transformation.
for example:
$\begin{pmatrix} S_{0,c}'\\ S_{1,c}'\\ S_{2,c}'\\ S_{3,c}' \end{pmatrix}= \begin{pmatrix} 2 & 3 & 1 & 1\\ 1 & 2 & 3 & 1\\ 1 & 1 & 2 & 3\\ 3 & 1 & 1 & 2 \end{pmatrix} \begin{pmatrix} S_{0,c}\\ S_{1,c}\\ S_{2,c}\\ S_{3,c} \end{pmatrix}$
where the addition is XOR, multiplication is the multiplication of polynomials module $x^8+x^4+x^3+x+1$, which is the minimal irreducible polynomial of degree 8.
Example:
$\begin{aligned} 02H*87H&=00000010*10000111\\ &=X*(X^7+X^2+X+1)=X^8+X^3+X^2+X\\ X^8+X^3+X^2+X&\equiv X^4+X^2+1\quad (mod\; X^8+X^4+X^3+X+1)\\ 02H*87H&=00010101=15H \end{aligned}$
[BK’09] Given $2^{99}$ pairs of input and output from 4 related keys in AES256, can recover keys in time $\approx 2^{99}$.
# Block ciphers from PRG
Can we build a PRF
from a PRG
?
Let $G:K\rightarrow K^2$ be a secure PRG
, then Define 1bit PRF
:
$F:K\times\{0,1\}\rightarrow K\\ F(k,x\in\{0,1\})=G(k)[x]$
Theorem: if $G$ is a secure PRG
, then $F$ is a secure PRF
.
Similarly, we can construct nbit PRF
:
$F(k,x)=G_n(k)[x]\\ where\;G_n:K\rightarrow K^{2^n}\\ G_n(k)=G(G_{n1}(k)[0])\;\;G(G_{n1}(k)[1])\;\;...\;\;G(G_{n1}(k)[2^{n1}1])$
We can prove that $F$ is a secure PRF
with the theorem given above:
where $r$ stands for the real random number.
Lemma:We can build a secure PRP
by a secure PRG
with the Luby theorem and construction mentioned above.
# More discussion about PRF
and PRP
Firstly we introduce the equivalent definition of secure PRF
:
Let’s make a brief explaination.
 $b$ is fixed and the adversary don’t know.
 Adversary can make several queries to challenger, each query can be modified according to the response of the last query.
 For the query $x$, if $b=0$, then the challenger should randomly choose a $k$, then respond $F(k,x)$ to the adversary.
If $b=0$, then the challenger should randomly choose a function $f\in\mathcal{Y}^\mathcal{X}$ and respond $f(x)$ to the adversary.  After $q$ queries, the adversary will give the guess that $b=0$ or $b=1$.
 EXP(0)=1 means that $b=0$ and the adversary guess $b=1$. EXP(1)=1 means that $b=1$ and the adversary guess $b=1$.
 Obviously, for a fixed adversary algorithm, due to the random choice of $f, k$, the guess of adversary may vary. So we have the probability.
Similarly, we can define the secure PRP
:
Noticing that the only difference is randomly choose $f$ in Permutations on $\mathcal{X}$.
 Example: all $2^{80}$ times algorithm $A$ have $Adv_{PRP}[A,AES]<2^{40}$.
Lemma: Let $E$ be a PRP
over $(\mathcal{K},\mathcal{X})$, then for any qqeury adversary $A$, we have:
$Adv_{PRF}[A,E]Adv_{PRP}[A,E]<\frac{q^2}{2X}$
So if $\mathcal{X}$ is large enough, then a secure PRP
is also a secure PRF
.
# Use block cipher: one time key
Don’t use the block cipher in Electronic Code Book( ECB
):
The problem is that if $m_1=m_2$, then $c_1=c_2$.
 Example:
Then we can introduce the semantic security of the cipher:
$Adv_{SS}[A,OTP]=Pr[EXP(0)=1]Pr[EXP(1)=1]$
should be negligible.
Lemma: ECB
is not semantic secure.
Proof: Construct an adversary $A$ such that:
then $Adv_{SS}[A,ECB]=1$.
One secure construction is Deterministic counter mode from a secure PRF
$F:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n$:
where $m,c\in\{0,1\}^{nL}$.
Theorem: For any $L>0$, if $F$ is a secure PRF
over $(\mathcal{K},\mathcal{X},\mathcal{X})$, then $E_{DETCTR}$ is a semantic secure cipher over $(\mathcal{K},\mathcal{X}^L,\mathcal{X}^L)$.
In particularly, for any efficient adversary $A$ attacking $E_{DETCTR}$, there exists an efficient PRF adversary $B$ such that:
$Adv_{SS}[A,E_{DETCTR}]=2Adv_{PRF}[B,F]$
# Use block cipher: many times key
Key used more than once $\Rightarrow$ adversary can see many CT
s with same key.
Adversary’s power: Chosen Plain text Attack( CPA
):
 Adversary can choose a
PT
and obtain itsCT
.CPA
is quite a conservative abstract of the reality.
Adversary’s goal: To break semantic security.
Since the adversary can choose PT
, then we can introduce the semantic security over manytime key:
explaination:
 After the random choice of $k$, $k$ is fixed for the $q$ queries.
 Adversary can modify query according to the response of the last query.
 If the adversary just want to know $E(k,m)$, then he can query with $m_{j,0}=m_{j,1}=m$.
 Other stuff is similar to the previous definition.
 Example: if the key is used more than once, and for fixed $k,m$, $E(k,m)$ is always the same, then it is not semantic secure. We can construct:
So we need to solve the problem that manytime key cipher is not semantic secure.
Solution 1: randomized encryption, where $E(k,m)$ is a randomized function:
roughly speaking, CT
size= PT
size+#random bits.
Solution 2: nounce based encryption:
so that $(k,n)$ pairs are used only once.
# Use block cipher: Cipher Block Chaining( CBC
)
Let $E$ be a PRP
, then we can construct a chain of $E_{CBC}$:
where IV stands for initial vector, and is chosen randomly in $\mathcal{X}$.
The decryption circuit is:
Theorem: If $E$ is a secure PRP
over $(\mathcal{K},\mathcal{X})$ then $E_{CBC}$ is semantic secure under CPA
over $(\mathcal{K},\mathcal{X}^L,\mathcal{X}^{L+1})$.
In particular, for a qquery adversary $A$ attacting $E_{CBC}$,there exists a PRP
adversary $B$ such that
$Adv_{CPA}[A,E_{CBC}]\leq 2Adv_{PRP}[B,E]+\frac{2q^2L^2}{X}$
 Example, suppose we want $Adv\leq 2^{32}$, then for AES $\mathcal{X}=2^{128}$, we should guarantee $qL<2^{48}$. So after encrypting $2^48$ blocks, we should change the key.
for 3DES, $\mathcal{X}=2^{64}$, so $qL<2^{16}$.
Warning: the IV must be chosen randomly each time of encryption!
Lemma: CBC
where attacker can predict IV is not CPA
secure.
Proof: if given IV0, then IV1 is predictable, then we can construct the adversary:
explaination:
 Since IV is in the head of
CT
so the adversary can obtain IV.  Once obtained IV0, the attacker will predict IV1.
 The blue box is $m_0\oplus IV_1=IV_0$, which is the same
PT
in the first query $0\oplus IV_0$.
A obvious modification is that we won’t give the adversary IV, that is we encrypt IV into a nounce:
# Use block cipher: Counter Mode ( CTR
)
Construction 1: rand CTR
, randomly choose an Initial Vector(IV):
Construction 2: nounce CTR
, we choose IV with counter:
Theorem: If $F$ is a secure PRF
over $(\mathcal{K},\mathcal{X},\mathcal{X})$, then $E_{CTR}$ is semantic secure under CPA
over $(\mathcal{K},\mathcal{X}^L,\mathcal{X}^L)$.
In particular, for a qquery adversary $A$ attacking $E_{CTR}$, there exists a PRF
adversary $B$ such that
$Adv_{CPA}[A,E_{CTR}]\leq 2Adv_{PRF}[B,F]+\frac{2q^2L}{\mathcal{X}}$
 Example: q=#messages encrypted with k, L=length of max messages, suppose we want $Adv_{CPA}\leq 2^{32}$, then for AES $\mathcal{X}=2^{128}$, we should guarantee $q\sqrt{L}<2^{48}$. So after encrypting $2^32$
CT
s each len of $2^{32}$, we must change the key.
Comparson: CTR
vs. CBC
:
feature  CBC 
CTR 

uses  PRP 
PRF 
parallel processing  No  Yes 
security  $q^2 L^2$<<$\\mathcal{X}\$  $q^2L$<<$\\mathcal{X}\$ 
# Message integrity
# Message Authentication Code( MAC
)
The goal in this section is integrity while no confidentiality.
Definition: MAC $I=(S,V)$ defined over $(\mathcal{K},\mathcal{M},\mathcal{T})$ is a pair of algorithms:
 $S(k,m)$ outputs $t\in \mathcal{T}$.
 $V(k,m,t)$ outputs ‘yes’ or ‘no’.
Let’s make a brief explaination. Alice uses message and generate function to generate a tag, and sends both message and tag to Bob. Bob uses the verification to verify if the message’s integrity.
 Example: generate function is $S(k,m)=CRC(m)$, then the attacker could easily modify the message without being noticed.
The essence behind the example is that CRC is designed to detect random, but not malicious errors.
Let’s define a MAC
game:
which means that the attacker’s power is Chosen Message Attack, he can choose and query several times, and the challenge would response the tag.
Then the attacker’s goal is to construct a pair of message and its corresponding tag not in the queries.
If the attacker can construct such a pair, then the MAC
is not secure.
Definition: A MAC
$I=(S,V)$ is a secure MAC
if forall “efficient” adversary A:
$Adv_{MAC}[A,I]=Pr[challenger\;outputs\;1]$
is negligible.
 Example: In operating systems, every file and its filname is signed by a
MAC
to ensure the integrity of the file. So the virus can’t modify the file without being detected.
# MAC
based on PRF
For a PRF
$F:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}$, we can construct a MAC
$I=(S,V)$:
 $S(k,m)=F(k,m)$.
 $V(k,m,t)$: outputs ‘yes’ if $t=F(k,m)$ and ‘no’ otherwise.
notice that when $\mathcal{Y}$ is too small, then the attacker can guess the tag easily.
Theorem: If $F:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}$ is a secure PRF
and $1/\\mathcal{Y}\$ is negligible, then $I=(S,V)$ constructed as above is a secure MAC
.
In particular, for every efficient adversary $A$ attacking $I$, there exists an efficient PRT
adversary $B$ such that:
$Adv_{MAC}[A,I]\leq Adv_{PRF}[B,F]+\frac{1}{\\mathcal{Y}\}$
Proof:
 Example: AES, A
MAC
for 16byte messages.
How to convert small MAC
to big MAC
? We just need to convert small PRF
to big PRF
. Methods:
 CBCMAC
 HMAC
# CBCMAC
and NMAC
Construction 1. encrypted CBCMAC
:
where $\mathcal{X}^{\leq L}=\bigcup_{i=1}^L \mathcal{X}^i$.
Let $F:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{X}$ be a PRF
, then the construction above defines $F_{ECBC}:\mathcal{K}^2\times\mathcal{X}^{\leq L}\rightarrow\mathcal{X}$.
Construction 2. NMAC
(nested MAC)
Let’s consider why the last encryption step in CBCMAC
is necessary?
Suppose we just define $I_{raw}=(S,V)$, where $S=rawCBC(k,m)$.
Then $I_{raw}$ could be easily broken by chosen message attack:
 Choose an arbitrary oneblock message $m\in\mathcal{X}$.
 Request tag for $m$, get $t=F(k,m)$.
 Ouput put t as MAC forgery for the twoblock message $m\;\\;m\oplus t$. since:
$rawCBC(k,m\;\\;m\oplus t)=F(k,F(k,m)\oplus t\oplus m)=F(k,m)=t$
so tag $t$ and message $m\;\\;m\oplus t$ can be constructed and verified.
Theorem: For any $L>0$, for every efficient qquery PRF
adversary $A$ attacking $F_{ECBC}$ or $F_{NMAC}$, there exists an efficient adversary $B$ such that:
$Adv_{PRF}[A,F_{ECBC}]\leq Adv_{PRF}[B,F]+\frac{2q^2}{\\mathcal{X}\}\\ Adv_{PRF}[A,F_{NMAC}]\leq qL\cdot Adv_{PRF}[B,F]+\frac{q^2}{2\\mathcal{K}\}$
CBCMAC
is secure as long as $q<<\\mathcal{X}\^{1/2}$.NMAC
is secure as long as $q<<\\mathcal{K}\^{1/2}$.
 Example: For AES, if we want $Adv_{PRF}[A,F_{ECBC}]\leq 2^{32}$, then $q^2/\\mathcal{X}\<2^{32}$, since $\\mathcal{X}\=2^{128}$, so after $q=2^{48}$ messages must change the key.
Let’s see an attack when the key is not changed.
It’s easy to prove that ECBC
and NMAC
have the extension property:
$\forall x,y,w,\;F_{BIG}(k,x)=F_{BIG}(k,y)\Rightarrow F_{BIG}(k,x\;\\;w)=F_{BIG}(k,y\;\\;w)$
let $F_{BIG}:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}$ be a big PRF
that has the extension property, then we can attack it as following:
 Issue $\\mathcal{Y}\^{1/2}$ messages queries randomly, and obtain responses $(m_i,t_t),i=1,2,...,\\mathcal{Y}\^{1/2}$.
 We can find collision $t_u=t_v$ with high probability, according to the birthday paradox.
 Choose arbitrary $w$ and query for $t=F_{BIG}(k,m_u\;\\;w)$.
 Output $(m_v\;\\;w, t)$.
So a better rand construct is Rand CBC RCBC
:
Security is:
$Adv_{MAC}[A,I_{RCBC}]\leq Adv_{PRF}[B, F]\cdot(1 + \frac{2q^2}{\\mathcal{X}\})$
Comparison between ECBC
and NMAC
:
ECBC
is commonly used as an AESbasedMAC
. e.g. CCM encryption mode(used in 802.11i).NMAC
not usually used withAES
or3DES
, the main reason is that it changes the key on every block, so it needs to do the key expansion several times.
# MAC
padding
When MAC
(e.g. constructed by ECBC
)'s message length is not a multiple of block size, we need to pad the message.
Construction 1.
Padding with all 0s.
Then the MAC
becomes insecure in that the attacker can obtain the tag of $m$ then output $m\;\\;0, m\;\\;00,...$, since $pad(m)=pad(m\;\\;0)=pad(m\;\\;00)=...$
For security, padding must be invertible, and secure:
$\forall m_0\neq m_1, pad(m_0)\neq pad(m_1)$
Construction 2. (ISO)
Pad with “100…00” and Add new block if needed.
 Example, if block size = 8, then $pad(10100)=10100100$, $pad(10100100)=1010010010000000$.
Obviouly the padding strategy is invertible since one can remove several 0s until a single 1, then get the original message. It is secure as well.
Construction 3. (CMAC NIST standard)
key = $(k,k_1,k_2)$, if we need padding then use the left circuit, otherwise use the right one.
 No final encrypton step, since extension attack is thwarted by last key xor.
 No dummy block, since we separate the cases with two different keys.
# PMAC and CarterWegman MAC
ECBC
and NMAC
are sequential, can we build a parallel MAC
from a small PRF
?
Of course, it is named PMAC
(Parallel MAC):
the function $P$ here is used to encrypt sequence, to avoid swap attack. Without $P$, the attacker could swap two blocks and get the same tag.
Theorem: For any $L>0$, If $F$ is a secure PRF
over $(\mathcal{K},\mathcal{X},\mathcal{X})$ then $F_{PMAC}$ is a secure PRF
over $(\mathcal{K},\mathcal{X}^{\leq L},\mathcal{X})$.
In particular, for any efficient qquery PRF
adversary $A$ attacking $F_{PMAC}$, there exists an adversary $B$ such that:
$Adv_{PRF}[A,F_{PMAC}]\leq Adv_{PRF}[B,F]+\frac{2q^2L^2}{\\mathcal{X}\}$
If only one block of PMAC
is changed, then the tag can be recomputed quickly.
One time MAC
is another kind of MAC
not based on PRF
.
If the key is changed on every message like OTP
, then the attacking game could be defined as:
so the attacker could only query 1 message.
 Example, one time
MAC
: let $q$ be a large prime (e.g. $q=2^{128}+51$)
 $key=(a,b)\in\{1,...,q\}^2$, two random int in $[1,q]$.
 $msg=(m[1],...,m[L])$ where each block is 128 bit int.
$S(key,msg)=P_{msg}(a)+b\;(mod\;p)$
where$P_{msg}(x)=x^{L+1}+m[L]x^L+...+m[1]x$
is a polynomial of degree $L+1$.
Theorem: the onetime MAC
in the last example, we have:
$\forall m_1\neq m_2,t_1,t_2,\;Pr_{a,b}[S((a, b),m_1)=t_1\;\;S((a,b),m_2)=t_2]\leq L/q$
So basicly given $S(key, msg_1)$ the adversary has no info about $S(key,msg_2)$.
By one time MAC
we can construct manytime MAC
with high speed:
Let $(S,V)$ be a secure onetime MAC
over $(\mathcal{K}_{I},\mathcal{M},\{0,1\}^n)$.
Let $F:\mathcal{K}_F\times\{0,1\}^n\rightarrow\{0,1\}^n$ be a secure PRF
.
CarterWegmen MAC
:
$CW((k_1,k_2),m)=(r,F(k_1,r)\oplus S(k_2,m))$
for random $r\leftarrow\{0,1\}^n$.
So given $t=F(k_1,r)\oplus S(k_2,m)$, we can run the verification function as:
$V(k_2,m,F(k_1,r)\oplus t)$
Theorem: If $(S,V)$ is a secure one time MAC
and $F$ is a secure PRF
then CW is a secure MAC
outputting tags in $\{0,1\}^{2n}$.
# Collision resistance
# Introduction
So far, four MAC
constructions:
Definition: Let $H:\mathcal{M}\rightarrow\mathcal{T}$ be a hash function ($\\mathcal{H}\>>\\mathcal{T}\$),
A collision for $H$ is a pair $m_0,m_1\in\mathcal{M}$ such that:
$H(m_0)=H(m_1)\;and\;m_0\neq m_1$
A function $H$ is collision resistant if for all explicit efficient $A$,
$Adv_{CR}[A,H]=Pr[A\;outputs\;collision\;for\;H]$
is negligible.
Let $I=(S,V)$ be a MAC
for short messages over $(\mathcal{K},\mathcal{M},\mathcal{T})$ (e.g. AES
).
Let $H:\mathcal{M}^{big}\rightarrow\mathcal{M}$.
Then we can construct a MAC
:
$S^{big}(k,m)=S(k,H(m))\\ V^{big}(k,m,t)=V(k,H(m),t)$
Theorem: If $I$ is a secure MAC
and $H$ is collision resistant then $I^{big}$ is a secure MAC
Suppose $H$ is not resistant, and the attacker can obtain collision $(m_0,m_1)$. Then after quering the tag for $m_0$, the attacker can output $(m_1,tag(m_0)$ since $H(m_0)=H(m_1)$.
# Generic birthday attack
Theorem (birthday paradox): Let $r_1,...,r_n\in\{1,...,B\}$ be independent identically distributed integers. Then when $n=1.2\times B^{1/2}$ then $Pr[\exists i\neq j:r_i=r_j]\geq 1/2$.
Proof: we only prove when $r_1,...,r_n$ are all subject to uniform distribution (it’s the worst case):
$\begin{aligned} Pr[\exists i,j,r_i=r_j] &=1Pr[\forall i\neq j,r_i\neq r_j]\\ &=1\frac{B1}{B}\times\frac{B2}{B}\times...\times\frac{Bn+1}{B}\\ &=1\prod_{i=1}^{n1}(1\frac{i}{B})\\ &\geq 1\prod_{i=1}^{n1}e^{i/B}\\ &=1e^{\frac{1}{B}\sum_{i=1}^{n1}i}\\ &\geq 1e^{\frac{n^2}{2B}}\\ &\geq 1e^{0.72}>1/2 \end{aligned}$
So a generic attack is randomly choose $2^{n/2}$ elements in $\mathcal{M}$, then with a high probabilty that we can find a collision. $O(2^{n/2})$.
# The MerkleDamgard Paradigm
Given a CR
(collision resistant) hash function for short messages, we can construct CR
hash function for long messages. That is MerkleDamgard iterated construction:
Give $h:\mathcal{T}\times\mathcal{X}\rightarrow\mathcal{T}$, we obtain $H:\mathcal{X}^{\leq L}\rightarrow\mathcal{T}$.
We say $h$ is compression function and $H_i$ is the chaining variables (the output of each $h$).
Padding block:
if no space for at least 65bits padding block, then add another block.
Theorem: If $h$ is collision resistant, then so is $H$ in MerkleDamgard paradigm.
Proof: We prove collision on $H\Rightarrow$ collision on $h$.
Suppose $H(m)=H(m')$, then we consider the chaining variables:
$IV=H_0,H_1,...,H_t,H_{t+1}=H(m)\\ IV=H_0',H_1',...,H_t',H_{t+1}'=H(m')$
And we have
$h(H_t,m_t\;\\;PB)=H_{t+1}=H_{t+1}'=h(H_t',m_t'\;\\;PB')$
If $H_t\neq H_t'$ or $m_t\neq m_t'$ or $PB\neq PB'$, then we obtain a collision for $h$.
Otherwise, we have $H_t=H_t'$, we can repeat the process above, since $m\neq m'$ (collision for $H$), then at least can we find $H_i\neq H_i'$, then the collision for $h$ is found.
QED.
# Constructing compression functions
Suppose $E:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n$ is a block cipher, then the DaviesMeyer compression function is:
$h(H,m) = E(m,H)\oplus H$
Theorem: Suppose $E$ is an ideal cipher (is a collection of $\\mathcal{K}\$ random permutations), then finding a collision $h(H,m)=h(H',m')$ takes $O(2^{n/2})$ evaluations of $(E,D)$, and it’s the best cost possible.
And there are other compression functions based on block cipher:
 MiyaguchiPreneel: $h(H,m)=E(m,H)\oplus H\oplus m$, and the hash function “Whirlpool” is constructed by this compression function.
 $h(H,m)=E(m,H)\oplus m$, this one is insecure!
# HMAC
: a MAC
from SHA256
We now talk about MAC
from a MerkleDamgard hash function.
If $H:\mathcal{X}^{\leq L}\rightarrow\mathcal{T}$ is a collision resistant hash function, then we construct MAC
with it.
Construction 1.
$S(k,m)=H(k\;\\;m)$
This one is insecure! Since MerkleDamgard iteration has the extension property, so given $H(k\;\\;m)$, we can compute $H(k\;\\;m\;\\;PB\;\\;w)$ for any $w$.
Construction 2. Standardized method: HMAC
(HashMAC)
$S(k,m)=H(k\oplus opad\;\\;H(k\oplus ipad\;\\;m))$
where ipad and opad are consts defined previously.
It’s quite similar to NMAC
:
if we view the output $k_1,k_2$ as the input two keys for NMAC
. However, in HMAC
, $k_1$ and $k_2$ are not independent.
HMAC
is assumed to be a secure PRF
, secure bounds are similar to NMAC
– need $q^2/\\mathcal{T}\$ to be negligible.
# Timing attack on MAC
verification
In the process of verification, if we need to compare two strings, actually it’s comparing chars one by one, and return immediately if find a inequality.
So there is a timing attacking strategy:
 Query server with the message and a random byte.
 Loop over all possible first byte of tag, and query server. If it takes a little longer time to respond than step 1, then we find the right first byte tag for the message.
 Repeat the process to find other bytes of the tag.
Defense:
instread of:
1 

we use:
1 

So the attacker would not know the values being compared.
# Authenticated Encryption
# Active attacks on CPAsecure encryption
In this module, we talk about encryption against tampering, to ensure both confidentiality and integrity.
Without integrity, the confidentiality is vunable to active attacks.
 Example: In IP packet, the attacker could just modify the beginning:
then the server will “help” to decrypt the packet and send it to the attacker. In this case, the lack of integrity causes the confidentiality to be vunable to active attacks.
We can conclude lessons:
CPA
security cannot guarantee secrecy under active attack.
We use only two modes:
 If message needs integrity while no confidentiality, use a
MAC
.  If message needs both integrity and confidentiality, use
authenticated encryption
(this module).
# Definition
Definition: An authenticated encryotion system $(E,D)$ is a cipher where
$\begin{aligned} & E:\mathcal{K}\times\mathcal{M}\times\mathcal{N}(optional)\rightarrow\mathcal{C}\\ & D:\mathcal{K}\times\mathcal{C}\times\mathcal{N}(optional)\rightarrow\mathcal{M}\cup\{\bot\}\\ \end{aligned}$
where $\mathcal{N}$ is the space of nounce, and is optional. $\bot$ stands for the state that the cipher text is rejected.
The system is supposed to provide semantic secure under a CPA
attack and ciphertext integrity. CPA
attack is introduced before, it means that the attacker should not be able to distinguish two experiments by just querying several $(m_0,m_1)$.
While for ciphertext integrity, it’s natural that the attacker should not construct a ciphertext that is accepted:
$(E,D)$ has ciphertext integrity if forall efficient $A$,
$Adv_{CI}[A,E]=Pr[challenger\;outputs\;1]$
is negligible.
Definition: cipher $(E,D)$ has authenticated encryption ( AE
) if:
 semantically secure under
CPA
.  has ciphertext integrity.
 Example:
CBC
with randIV
does not provideAE
, since it never outputs $\bot$ so the integrity is not guaranteed.
If the AE
is guaranteed, what intuition can we get?
 authenticity, which means that the attacker could not fool Bob into thinking a message is sent from Alice:
 Security against
CPA
.
# Chosen ciphertext attacks ( CCA
)
Adversary’s Power: both CPA
and CCA
:
 Can obtain the encryption of arbitrary messages of his choice.
 Can decrypt any ciphertext of his choice, other than chosen plaintext.
Again, this is quite a conservative modeling of real life.
A more formal definition is as following:
$E$ is CCA
secure if for all efficient $A$:
$Adv_{CCA}[A,E]=Pr[EXP(0)=1]Pr[EXP(1)=1]$
is negligible.
 Example:
CBC
with randomIV
is notCCA
secure.
The attacker could first do theCPA
with two 1block messages $m_0,m_1$, and get $(IV,c_b[0])$. Then the attacker can useCCA
, to query the decryption of $(IV\oplus 1,c_b[0])$, the decryption is $m_b\oplus 1$, then the attacker can learn $b$.
Theorem: Let $(E,D)$ be a cipher that provides AE
. then $(E,D)$ is CCA
secure.
In particular, for any qquery efficient $A$, there exists efficient $B_1,B_2$ such that:
$Adv_{CCA}[A,E]\leq 2q\cdot Adv_{CI}[B_1,E]+Adv_{CPA}[B_2,E]$
Proof sketch:
Step 1. Since AE
guarantees ciphertext integrity ( CI
), then the attacker shouldn’t be able to construct any acceptable ciphertext other than ones he challenged. So it would be indinstinguishable thath the challenger always outputs $\bot$ in CCA
queries:
Step 2. Since the challenger always outputs $\bot$, then the CCA
queries is useless, we can ignore it. And because AE
guarantees CPA
security, then it’s indistinguishable that the response to CPA
query is $m_0$ or $m_1$:
Step 3. Similar to step 1, we can get back to CCA
queries. So as a whole:
# Constructions from ciphers and MAC
It’s quite natural that since we need both CPA
secure and integrity, can we just combine the CPA
secure cipher and a secure MAC
? There are three choices:
MAC
thenencrypt (SSL), which means that tag forMAC
is also encrypted. encryptthen
MAC
(IPsec), which means that the tag is for the encrypted cipher text and not encrypted.  encryptand
MAC
(SSH), which means that the tag is for the plain text and not encrypted.
AE
theorems:
 encryptthen
MAC
always providesAE
. MAC
thenencrypt may be insecure againstCCA
attacks. However when $E$ is randCTR
mode or randCBC
mode, then it providesAE
.
Standards:
GCM
:CTR
mode encryption then CWMAC
(CarterWegmenMAC
).CCM
:CBC
MAC
thenCTR
mode encryption.EAX
:CTR
mode encryption thenCMAC
.
Instead of the combination of secure encryption and MAC
, can we construct the AE
mode directly? Yes, it’s OCB
mode:
where $E$ is a secure PRP
, and $P$ is similar to the one in PMAC
, the purpose of it is to emphasize the order. And $N$ is nouce, which should be distince between messages but does not need to be random, so a counter is sufficient.
# CBC
paddings attacks
Consider the MAC
thenencrypt mode, the decryption is three steps:
 Decrypt the cipher text.
 Check the padding to see if it’s valid.
 Check the tag to see the integrity.
So there are two petential erros: Padding error and MAC error.
Suppose the attacker can distinguish the two types of erros, then he can submit ciphertext and learns if last bytes of plaintext are a valid pad.
Let’s give an example for CBC
encryption:
If we want to know the very last byte of the plaintext, then we just iterate $g\in[0..255]$, and change the last byte of the second last block:
We know that $01H$ is a valid pad. So if and only if when the last byte of the last block is equal to $g$, then the decryption of it will be $01H$, and is a valid padding. Otherwise the attacker will get a padding error.
Similarly, by different length of padding, the attacker can get the bytes one by one.
However, encryptthen MAC
will completely avoid this problem.
# Special attack: attack on nonatomic decryption
Example: SSH
Binary Packet Protocol
The process of decryption is:
 decrypt packet length field only!
 read as many packets as length specifies.
 decrypt remaining ciphertext blocks.
 chech the
MAC
tag.
So if the attacker wants to know the plaintext of a given ciphertext $c$(Notice here the ciphertext is given but not constructed by attacker, so it’s not a CCA
attack), then it can repeat sending 1byte messages to the server until get a “ MAC
error”, then the left 32 bits of the plaintext (length field) will be learned by the attacker.
# Odds and ends
# Key derivation
Suppose the source key SK
is uniform in $\mathcal{K}$, and $F$ is a PRF
with key space $\mathcal{K}$ and outputs in $\{0,1\}^n$.
And we can construct a Key Derivation Function KDF
as:
$KDF(SK, CTX, L) := F(SK, (CTX\;\\;0))\;\\;F(SK, (CTX\;\\;1))\;\\;...\;\\;F(SK, (CTX\;\\;L))$
where $CTX$ is used to identify different applications, even two applications have the same SK
, they will get the different key.
What will happen if the SK
is not uniform?
We know that the PRF
's outputs will not look like random any more.
The solution is ExtractthenExpand paradigm:
where salt is a fixed nonsecret string chosen at random, and after the extraction, the distribution will be uniform.
The implemention of the extractor is not going to be discussed here, but we know that HKDF
is a KDF
based on HMAC
, which is widely used.
$k\leftarrow HKDF(salt,sk)\\$