就在这瞬间,黎明的晨星躲到云中了。

# Stream Ciphers

# What is a Cipher?

Definition: A cipher defined over (K,M,C)(\mathcal{K},\mathcal{M},\mathcal{C}) is a pair of “efficient” algorithms (E,D)(E,D) where:

E:K×MCD:K×CMs.t.  mM,kK,D(k,E(k,m))=mE:\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 K\mathcal{K} is referred as key space, M\mathcal{M} is referred as message space, C\mathcal{C} is referred as cipher space.
Sometimes we also use notation PT (Plain Text) and CT (Cipher Text).

The function EE is called encryption and DD is called decryption. While D(k,E(k,m))=mD(k,E(k,m))=m means the consistency that given a key kk, then for any message mm, the decryption of the encryption of mm is mm.

What is also important that we always assume that the function EE and DD are open to the public, while only the key kk is kept secret.

  • Example:The One Time Pad OTP (Vernam 1917)

M={0,1}nK={0,1}nC={0,1}nE(k,m)=kmD(k,c)=kc\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 kk 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)(E,D) over (K,M,C)(\mathcal{K},\mathcal{M},\mathcal{C}) is perfect secrecy if:

m0,m1M,cC,PrkRK[E(k,m0)=c]=PrkRK[E(k,m1)=c]\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 kRKk\stackrel{R}{\leftarrow}\mathcal{K} means that kk subjects to the uniform distribution over K\mathcal{K}.

The definition indicates that given CT can’t tell if the message is m0m_0 or m1m_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 mm. Then:

PrkRK[E(k,m)=c]=#k,kK,E(k,m)=cK=1K\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)=ck=mcE(k,m)=c \Rightarrow k=m\oplus c, so the number of keys satisfying this condition is 11.

Then the proof is self-evident, since for any PT and CT , the probability of encryption is all the same.

Theorem: If a cipher (E,D)(E,D) over (K,M,C)(\mathcal{K},\mathcal{M},\mathcal{C}) is perfect secrecy, then:

KM|\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{0,1}n,n>>sG:\{0,1\}^s\rightarrow\{0,1\}^n,n>>s

where {0,1}s\{0,1\}^s is called the seed space.

Then E(k,m)=mG(k),D(k,c)=cG(k)E(k,m)=m\oplus G(k),D(k,c)=c\oplus G(k).
Now since the length of kk 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 GG is predictable if there exists an “efficient” algorithm AA such that:

0in1,s.t.  PrkR{0,1}s[A(G(k)1,...,i)=G(k)i+1]>12+ε\exists 0\leq i\leq n-1,\\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 non-negligible const.

The definition says that, the PRG is predictable if there exists an algorithm, which is able to predict the i+1i+1 bit of the output given the first ii bits of the output. And AA works well in most cases.

  • Example: random() function if glibc:

r[i]:=(r[i3]+r[i31])%232return  r[i]>>1;r[i]:=(r[i-3]+r[i-31])\%2^{32}\\ return\;r[i]>>1;

is a typical weak PRG and should NOT be used for crypto.

# Negligible vs. Non-negligible

  • In practice: Whether ε\varepsilon is negligible is defined as a scalar, e.g. ε1230\varepsilon\geq\frac{1}{2^{30}} is non-negligible since it is likely to happen in 1GB data.
  • In theory: ε\varepsilon is a function ε(λ)\varepsilon(\lambda). ε(λ)\varepsilon(\lambda) is negligible if d,\forall d, ε(λ)\varepsilon(\lambda) congruent to 0 faster than 1λd\frac{1}{\lambda^d}. While is non-negligible otherwise.

# Attacks to OTP

# Two time pad is insecure!

If we use the cipher key more than once:

c1m1PRG(k)c2m2PRG(k)c_1\leftarrow m_1\oplus PRG(k)\\ c_2\leftarrow m_2\oplus PRG(k)\\

then the attacker can get m1m2m_1\oplus m_2 by xoring c1,c2c_1,c_2.

There are enough redundancy in English and ASCII to recover m1,m2m_1,m_2 by knowing m1m2m_1\oplus m_2.

  • Real world examples:Project Venona, MS-PPTP

# 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=mkc=m\oplus k, then he can modify it by cpc\oplus p, and send it back. The receiver will decrypt it as mpm\oplus p, which is modified by the attacker.

# What is a secure PRG ?

Definition: A statistical test on {0,1}n\{0,1\}^n is an “efficient” algorithm AA, s.t. A(x)A(x) outputs “0” or “1”.

  • Example: A(x)A(x) outputs “1” iff #0(x)#1(x)<10n|\#0(x)-\#1(x)|<10\sqrt{n}. Meaning that if the number of 0 and 1 is not too different, then the test AA believes that the string is random.

Definition(Advantage):let GG be a PRG and AA a statistical test on {0,1}n\{0,1\}^n, then the advantage is defined as:

AdvPRG[A,G]=PrkRK[A(G(k))=1]PrrR{0,1}n[A(r)=1]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 AA, whether AA can tell the difference between PRG and a real random.

Definition: We say a PRG GG is a secure PRG if \forall “efficient” statistical test AA, AdvPRG[A,G]Adv_{PRG}[A,G] is negligible.

Lemma: a predictable PRG is insecure.

Proof: if GG is a predictable PRG , then there exists a predict algorithm AA satisfying:

PrkR{0,1}s[A(G(k)1,...,i)=G(k)i+1]>12+ε\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 BB separating GG and random:

B(x)={1A(x1,...,i)=xi+10otherwiseB(x)=\begin{cases} 1 & A(x|_{1,...,i})=x_{i+1}\\ 0 & otherwise \end{cases}

For real random, we have:

PrrR{0,1}n[B(r)=1]=12\mathop{Pr}\limits_{r\stackrel{R}{\leftarrow}\{0,1\}^n}[B(r)=1]=\frac{1}{2}

because in real random, A(r1,...,i)=ri+1A(r|_{1,...,i})=r_{i+1} and A(r1,...,i)ri+1A(r|_{1,...,i})\neq r_{i+1} are of the same probability.
and we have:

PrkRK[B(G(k))=1]>12+ε\mathop{Pr}\limits_{k\stackrel{R}{\leftarrow}\mathcal{K}}[B(G(k))=1]>\frac{1}{2}+\varepsilon

then:

Adv[B,G]>εAdv[B,G]>\varepsilon

QED.

Theorem(Yao’82): an unpredictable PRG is secure.

Definition: Let P1,P2P_1,P_2 be two distributions over {0,1}n\{0,1\}^n, then we say P1,P2P_1,P_2 are computationally indistinguishable if for any “efficient” statistical test AA,

PrxRP1[A(x)=1]PrxRP2[A(x)=1]|\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 P1PP2P_1\approx_P P_2

# Semantic security

Definition: We say a cipher (E,D)(E,D) over (K,M,C)(\mathcal{K},\mathcal{M},\mathcal{C}) is semantically secure if:

m1,m2M,kRK{E(k,m1)}P{E(k,m2)}\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,m1)}\{E(k,m_1)\} is a probability distribution over C\mathcal{C}.

Given b=0,1b=0,1 and an “efficient” algorithm AA, we can define two experiments:
1
Adversary AA give two messages to the challenger, then the challenger will give back the cipher text determined by bb and randomly chosen kk. But AA don’t know bb, then AA will guess the value of bb.
Let Pr[W0]Pr[W_0] is "when b=0b=0 and kk is randomly chosen, the probability that AA guess b=1b=1".
And let Pr[W1]Pr[W_1] is "when b=1b=1 and kk is randomly chosen, the probability that AA guess b=1b=1".
Let’s define:

AdvSS[A,E]=Pr[W0]Pr[W1]Adv_{SS}[A,E]=|Pr[W_0]-Pr[W_1]|

then EE is semantically secure if for any AA,AdvSS[A,E]Adv_{SS}[A,E] is negligible.

  • Example: Given a cipher, which we can guess the last bit of PT by CT . Then we can construct a AA:
    1. choose two messages m0,m1m_0,m_1 with different last bit.
    2. pass m0,m1m_0,m_1 to the challenger.
    3. after receive the CT , guess the last bit of PT by CT .
    4. output the guess.
      in this case, AdvSS[A,E]=1Adv_{SS}[A,E]=1. Since AA can always guess right. So it’s not semantically secure.

Lemma: Perfect secure \Rightarrow Semantically secure.

Proof:obviously,

{E(k,m1)}={E(k,m2)}{E(k,m1)}P{E(k,m2)}\{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:K{0,1}nG:\mathcal{K}\rightarrow\{0,1\}^n be a PRG , then GG is a secure PRT \Rightarrow stream cipher OTP EE derived from GG is semantically secure.

Proof: we just need to prove that, \forall adversary AA, B\exists B s.t.

AdvSS[A,E]2AdvPRG[B,G]Adv_{SS}[A,E]\leq 2 Adv_{PRG}[B,G]

Given an adversary AA, we can construct two experiments:
2
3

one using G(k)G(k) and one using real random rr to crypt.
Let W0W_0 is when b=0b=0, the guess of first exp is 1.
Let W1W_1 is when b=1b=1, the guess of first exp is 1.
Let R0R_0 is when b=0b=0, the guess of second exp is 1.
Let R1R_1 is when b=1b=1, the guess of second exp is 1.
Since OTP is perfect secrecy when real random:

Pr[R0]Pr[R1]=0|Pr[R_0]-Pr[R_1]|=0

Next we need to construct an adversary BB to PRG , and prove:

Pr[W0]Pr[R0]AdvPRG[B,G]|Pr[W_0]-Pr[R_0]|\leq Adv_{PRG}[B,G]

We can construct BB as follows:
4
then

PrrR{0,1}n[B(r)=1]=Pr[R0]PrkRK[B(G(k))=1]=Pr[W0]\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:

AdvPRG[B,G]=PrrR{0,1}n[B(r)=1]PrkRK[B(G(k))=1]=Pr[R0]Pr[W0]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:

AdvPRG[B,G]=Pr[R0]Pr[W0]=Pr[R1]Pr[W1]Adv_{PRG}[B,G]=|Pr[R_0]-Pr[W_0]|=|Pr[R_1]-Pr[W_1]|

Since Pr[R0]=Pr[R1]Pr[R_0]=Pr[R_1], so:

Pr[W0]Pr[W1]2AdvPRG[B,G]|Pr[W_0]-Pr[W_1]|\leq 2 Adv_{PRG}[B,G]

So if PRG is secure, then AdvPRG[B,G]Adv_{PRG}[B,G] is negligible, then AdvSS[A,E]Adv_{SS}[A,E] is negligible.
QED.

# Block cipher

# What is a block cipher?

5

  • Example: 3DES,n=64,k=168
  • Example: AES,n=128,k=128 or 192 or 256

The process of encryption is:
6
for 3DES,n=48; for AES,n=10.

Definition: Pseudo Random Function PRF defined over (K,X,Y)(\mathcal{K},\mathcal{X},\mathcal{Y}) :

F:K×XYF:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}

such that exists an “efficient” algorithm to evaluate FF.

Pseudo Random Permutation PRP defined over (K,X)(\mathcal{K},\mathcal{X}) :

E:K×XXE:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{X}

such that :

  1. Exists “efficient” deterministic algorithm to evaluate EE.
  2. The function E(k,)E(k,\cdot) is one-to-one.
  3. Exists “efficient” inversion algorithm D(k,y)D(k,y).
  • Example: 3DES, where X={0,1}64,K={0,1}168\mathcal{X}=\{0,1\}^{64},\mathcal{K}=\{0,1\}^{168}.

Definition: Let F:K×XYF:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y} be a PRF and SF={F(k,),kK}S_F=\{F(k,\cdot),k\in\mathcal{K}\}. Then the PRF is secure if a random function in SFS_F is indistinguishable from a random function in YX\mathcal{Y}^\mathcal{X}.

  • An easy application: let F:K×{0,1}n{0,1}nF:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n be a secure PRF , then we can construct a secure PRG :

G:K{0,1}ntG(k)=F(k,0)F(k,1)F(k,t1)G:\mathcal{K}\rightarrow\{0,1\}^{nt}\\ G(k)=F(k,0)||F(k,1)||\cdots||F(k,t-1)

the PRG is parallelizable and is secure.

# Data encryption standard (DES)

The core idea of DES is Feistel Network: Given functions f1,...,fd:{0,1}n{0,1}nf_1,...,f_d:\{0,1\}^n\rightarrow\{0,1\}^n, build an invertible function F:{0,1}2n{0,1}2nF:\{0,1\}^{2n}\rightarrow\{0,1\}^{2n}:
7
where

{Ri=fi(Ri1)Li1Li=Ri1\begin{cases} R_i=f_i(R_{i-1})\oplus L_{i-1}\\ L_i=R_{i-1} \end{cases}

It’s easy to construct the inverse network:
8
where

{Ri1=LiLi1=fi(Li)Ri\begin{cases} R_{i-1}=L_i\\ L_{i-1}=f_i(L_i)\oplus R_i \end{cases}

Theorem(Luby-Rackoff’85): if f:K×{0,1}n{0,1}nf:\mathcal{K}\times \{0,1\}^n\rightarrow\{0,1\}^n is a secure PRF , then 3-round Feistel Network F:K3×{0,1}2n{0,1}2nF:\mathcal{K}^3\times\{0,1\}^{2n}\rightarrow \{0,1\}^{2n} is a secure PRP .
9

The DES is a 16-round Feistel Network, the Key size is 56 bits and block size is 64 bits, in other word, DES:{0,1}56×{0,1}64{0,1}64DES:\{0,1\}^{56}\times\{0,1\}^{64}\rightarrow\{0,1\}^{64}:
10
where F(ki,x)F(k_i,x) works as follows:
11
where half block is xx and subkey is kik_i. “E” stands for some shifts and expand tricks, “P” is for permutation, while the “S” S-Box are functions {0,1}6{0,1}4\{0,1\}^6\rightarrow\{0,1\}^4. The choice of S-Box function matters a lot.
12

If the S-Box is linear, like:

Si(x1,x2,x3,x4,x5,x6)=(x2x3,x1x4x5,x1x6,x2x3x6)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 Si(x)=Aix(mod  2)S_i(\textbf{x})=A_i\cdot \textbf{x}(mod\;2).
Then the DES is entirely linear, and we have:

DES(k,m1)DES(k,m2)DES(k,m3)=DES(k,m1m2m3)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 S-Box and P-Box randomly would result in an insecure block cipher, the key would recover after 224\approx 2^{24} outputs [BS’89]

There are several rules to choose P-Box and S-Box, the most important one is never choose any linear function.

# Exhaustive Search for block cipher key

Goal: given a few input output pairs (mi,ci=E(k,mi),i=1,2,3(m_i,c_i=E(k,m_i),i=1,2,3, find the key kk.

Lemma: Suppose DES is an ideal cipher (indistinguishable from a random 2562^{56} permutation function π(k,)\pi(k,\cdot)), then m,c\forall m,c, there is at most one kk such that c=DES(k,m)c=DES(k,m) with probability 25525699.5%\geq \frac{255}{256}\approx 99.5\%.

Proof:

Pr[kk,DES(k,m)=DES(k,m)]k{0,1}56Pr[DES(k,m)=DES(k,m)]=2561264=128Pr[\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 kk' is 112899.5%1-\frac{1}{2^8}\approx 99.5\%.
QED.

For two DES pairs (m1,c1),(m2,c2)(m_1,c_1),(m_2,c_2), the prob. that key is unique is 11271\approx 1-\frac{1}{2^{71}}.

So with exhaustive searching method, we can find the key in time 2562^{56}.


We can strengthen DES against exhaustive search.
Method 1: Triple-DES, let 3E:K3×MM3E:\mathcal{K}^3\times \mathcal{M}\rightarrow\mathcal{M} as

3E((k1,k2,k3),m)=E(k1,D(k2,E(k3,m)))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((k1,k2),m)=E(k1,E(k2,m))2E((k_1,k_2),m)=E(k_1,E(k_2,m))?
We will introduce a Meet in the middle attack:
since

E(k1,m)=D(k2,c)E(k_1,m)=D(k_2,c)

Then we can construct a table:

k0=0000k^0=00\cdots 00 E(k0,m)E(k^0,m)
k1=0001k^1=00\cdots 01 E(k1,m)E(k^1,m)
\cdots \cdots
kN=1111k^N=11\cdots 11 E(kN,m)E(k^N,m)

and sort the table by the second column E(ki,m)E(k^i,m).
Then we can enumerate k2k_2, and binary search D(k2,c)D(k_2,c) in the table, to find D(k2,c)=E(ki,m)D(k_2,c)=E(k^i,m).
So the total time is O(256log(256))O(2^{56}log(2^{56})) which is not large enough.

Method 2: DESX
Define EX((k1,k2,k3),m)=k1E(k2,mk3)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 k1E(k2,m)k_1\oplus E(k_2,m) or E(k2,k1m)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
13
where the input is 4x4=16 bytes and the key is 16 bytes.
each round contains 3 function:

  1. Bytes substitution: a non-linear function 1 byte \rightarrow 1 byte. The S-Box is a 256-size table.
    14
  2. Shift rows:
    15
  3. Mix columns: the four bytes of each column of the state are combined using an invertible linear transformation.
    for example:
    16

(S0,cS1,cS2,cS3,c)=(2311123111233112)(S0,cS1,cS2,cS3,c)\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 x8+x4+x3+x+1x^8+x^4+x^3+x+1, which is the minimal irreducible polynomial of degree 8.
Example:

02H87H=0000001010000111=X(X7+X2+X+1)=X8+X3+X2+XX8+X3+X2+XX4+X2+1(mod  X8+X4+X3+X+1)02H87H=00010101=15H\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 2992^{99} pairs of input and output from 4 related keys in AES-256, can recover keys in time 299\approx 2^{99}.

# Block ciphers from PRG

Can we build a PRF from a PRG ?
Let G:KK2G:K\rightarrow K^2 be a secure PRG , then Define 1-bit PRF :

F:K×{0,1}KF(k,x{0,1})=G(k)[x]F:K\times\{0,1\}\rightarrow K\\ F(k,x\in\{0,1\})=G(k)[x]

17

Theorem: if GG is a secure PRG , then FF is a secure PRF .

Similarly, we can construct n-bit PRF :

F(k,x)=Gn(k)[x]where  Gn:KK2nGn(k)=G(Gn1(k)[0])    G(Gn1(k)[1])    ...    G(Gn1(k)[2n11])F(k,x)=G_n(k)[x]\\ where\;G_n:K\rightarrow K^{2^n}\\ G_n(k)=G(G_{n-1}(k)[0])\;||\;G(G_{n-1}(k)[1])\;||\;...\;||\;G(G_{n-1}(k)[2^{n-1}-1])

18
We can prove that FF is a secure PRF with the theorem given above:
19
where rr 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 :
20
Let’s make a brief explaination.

  1. bb is fixed and the adversary don’t know.
  2. Adversary can make several queries to challenger, each query can be modified according to the response of the last query.
  3. For the query xx, if b=0b=0, then the challenger should randomly choose a kk, then respond F(k,x)F(k,x) to the adversary.
    If b=0b=0, then the challenger should randomly choose a function fYXf\in\mathcal{Y}^\mathcal{X} and respond f(x)f(x) to the adversary.
  4. After qq queries, the adversary will give the guess that b=0b=0 or b=1b=1.
  5. EXP(0)=1 means that b=0b=0 and the adversary guess b=1b=1. EXP(1)=1 means that b=1b=1 and the adversary guess b=1b=1.
  6. Obviously, for a fixed adversary algorithm, due to the random choice of f,kf, k, the guess of adversary may vary. So we have the probability.

Similarly, we can define the secure PRP :
21

Noticing that the only difference is randomly choose ff in Permutations on X\mathcal{X}.

  • Example: all 2802^{80} times algorithm AA have AdvPRP[A,AES]<240Adv_{PRP}[A,AES]<2^{-40}.

Lemma: Let EE be a PRP over (K,X)(\mathcal{K},\mathcal{X}), then for any q-qeury adversary AA, we have:

AdvPRF[A,E]AdvPRP[A,E]<q22X|Adv_{PRF}[A,E]-Adv_{PRP}[A,E]|<\frac{q^2}{2|X|}

So if X|\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 ):
22
The problem is that if m1=m2m_1=m_2, then c1=c2c_1=c_2.

  • Example:23

Then we can introduce the semantic security of the cipher:
24

AdvSS[A,OTP]=Pr[EXP(0)=1]Pr[EXP(1)=1]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 AA such that:
25
then AdvSS[A,ECB]=1Adv_{SS}[A,ECB]=1.


One secure construction is Deterministic counter mode from a secure PRF F:K×{0,1}n{0,1}nF:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n:
26
where m,c{0,1}nLm,c\in\{0,1\}^{nL}.

Theorem: For any L>0L>0, if FF is a secure PRF over (K,X,X)(\mathcal{K},\mathcal{X},\mathcal{X}), then EDETCTRE_{DETCTR} is a semantic secure cipher over (K,XL,XL)(\mathcal{K},\mathcal{X}^L,\mathcal{X}^L).
In particularly, for any efficient adversary AA attacking EDETCTRE_{DETCTR}, there exists an efficient PRF adversary BB such that:

AdvSS[A,EDETCTR]=2AdvPRF[B,F]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 its CT . 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 many-time key:
27
explaination:

  1. After the random choice of kk, kk is fixed for the qq queries.
  2. Adversary can modify query according to the response of the last query.
  3. If the adversary just want to know E(k,m)E(k,m), then he can query with mj,0=mj,1=mm_{j,0}=m_{j,1}=m.
  4. Other stuff is similar to the previous definition.
  • Example: if the key is used more than once, and for fixed k,mk,m, E(k,m)E(k,m) is always the same, then it is not semantic secure. We can construct:
    28

So we need to solve the problem that many-time key cipher is not semantic secure.

Solution 1: randomized encryption, where E(k,m)E(k,m) is a randomized function:
29
roughly speaking, CT -size= PT -size+#random bits.

Solution 2: nounce based encryption:
30
so that (k,n)(k,n) pairs are used only once.

# Use block cipher: Cipher Block Chaining( CBC )

Let EE be a PRP , then we can construct a chain of ECBCE_{CBC}:
31
where IV stands for initial vector, and is chosen randomly in X\mathcal{X}.
The decryption circuit is:
32

Theorem: If EE is a secure PRP over (K,X)(\mathcal{K},\mathcal{X}) then ECBCE_{CBC} is semantic secure under CPA over (K,XL,XL+1)(\mathcal{K},\mathcal{X}^L,\mathcal{X}^{L+1}).
In particular, for a q-query adversary AA attacting ECBCE_{CBC},there exists a PRP adversary BB such that

AdvCPA[A,ECBC]2AdvPRP[B,E]+2q2L2XAdv_{CPA}[A,E_{CBC}]\leq 2Adv_{PRP}[B,E]+\frac{2q^2L^2}{|X|}

  • Example, suppose we want Adv232Adv\leq 2^{-32}, then for AES X=2128|\mathcal{X}|=2^{128}, we should guarantee qL<248qL<2^{48}. So after encrypting 2482^48 blocks, we should change the key.
    for 3-DES, X=264|\mathcal{X}|=2^{64}, so qL<216qL<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:
33
explaination:

  1. Since IV is in the head of CT so the adversary can obtain IV.
  2. Once obtained IV0, the attacker will predict IV1.
  3. The blue box is m0IV1=IV0m_0\oplus IV_1=IV_0, which is the same PT in the first query 0IV00\oplus IV_0.

A obvious modification is that we won’t give the adversary IV, that is we encrypt IV into a nounce:
34

# Use block cipher: Counter Mode ( CTR )

Construction 1: rand CTR , randomly choose an Initial Vector(IV):
35

Construction 2: nounce CTR , we choose IV with counter:
36

Theorem: If FF is a secure PRF over (K,X,X)(\mathcal{K},\mathcal{X},\mathcal{X}), then ECTRE_{CTR} is semantic secure under CPA over (K,XL,XL)(\mathcal{K},\mathcal{X}^L,\mathcal{X}^L).
In particular, for a q-query adversary AA attacking ECTRE_{CTR}, there exists a PRF adversary BB such that

AdvCPA[A,ECTR]2AdvPRF[B,F]+2q2LXAdv_{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 AdvCPA232Adv_{CPA}\leq 2^{-32}, then for AES X=2128|\mathcal{X}|=2^{128}, we should guarantee qL<248q\sqrt{L}<2^{48}. So after encrypting 2322^32 CT s each len of 2322^{32}, we must change the key.

Comparson: CTR vs. CBC :

feature CBC CTR
uses PRP PRF
parallel processing No Yes
security q2L2q^2 L^2<<X\|\mathcal{X}\| q2Lq^2L<<X\|\mathcal{X}\|

# Message integrity

# Message Authentication Code( MAC )

The goal in this section is integrity while no confidentiality.

Definition: MAC I=(S,V)I=(S,V) defined over (K,M,T)(\mathcal{K},\mathcal{M},\mathcal{T}) is a pair of algorithms:

  • S(k,m)S(k,m) outputs tTt\in \mathcal{T}.
  • V(k,m,t)V(k,m,t) outputs ‘yes’ or ‘no’.

37

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)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:
38
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)I=(S,V) is a secure MAC if forall “efficient” adversary A:

AdvMAC[A,I]=Pr[challenger  outputs  1]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:K×XYF:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y}, we can construct a MAC I=(S,V)I=(S,V):

  • S(k,m)=F(k,m)S(k,m)=F(k,m).
  • V(k,m,t)V(k,m,t): outputs ‘yes’ if t=F(k,m)t=F(k,m) and ‘no’ otherwise.

notice that when Y|\mathcal{Y}| is too small, then the attacker can guess the tag easily.

Theorem: If F:K×XYF:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{Y} is a secure PRF and 1/Y1/\|\mathcal{Y}\| is negligible, then I=(S,V)I=(S,V) constructed as above is a secure MAC .
In particular, for every efficient adversary AA attacking II, there exists an efficient PRT adversary BB such that:

AdvMAC[A,I]AdvPRF[B,F]+1YAdv_{MAC}[A,I]\leq Adv_{PRF}[B,F]+\frac{1}{\|\mathcal{Y}\|}

Proof:
39

  • Example: AES, A MAC for 16-byte messages.

How to convert small MAC to big MAC ? We just need to convert small PRF to big PRF . Methods:

  1. CBC-MAC
  2. HMAC

# CBC-MAC and NMAC

Construction 1. encrypted CBC-MAC :
40
where XL=i=1LXi\mathcal{X}^{\leq L}=\bigcup_{i=1}^L \mathcal{X}^i.
Let F:K×XXF:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{X} be a PRF , then the construction above defines FECBC:K2×XLXF_{ECBC}:\mathcal{K}^2\times\mathcal{X}^{\leq L}\rightarrow\mathcal{X}.

Construction 2. NMAC (nested MAC)
41


Let’s consider why the last encryption step in CBC-MAC is necessary?
Suppose we just define Iraw=(S,V)I_{raw}=(S,V), where S=rawCBC(k,m)S=rawCBC(k,m).
Then IrawI_{raw} could be easily broken by chosen message attack:

  1. Choose an arbitrary one-block message mXm\in\mathcal{X}.
  2. Request tag for mm, get t=F(k,m)t=F(k,m).
  3. Ouput put t as MAC forgery for the two-block message m    mtm\;\|\;m\oplus t. since:

rawCBC(k,m    mt)=F(k,F(k,m)tm)=F(k,m)=trawCBC(k,m\;\|\;m\oplus t)=F(k,F(k,m)\oplus t\oplus m)=F(k,m)=t

so tag tt and message m    mtm\;\|\;m\oplus t can be constructed and verified.

Theorem: For any L>0L>0, for every efficient q-query PRF adversary AA attacking FECBCF_{ECBC} or FNMACF_{NMAC}, there exists an efficient adversary BB such that:

AdvPRF[A,FECBC]AdvPRF[B,F]+2q2XAdvPRF[A,FNMAC]qLAdvPRF[B,F]+q22KAdv_{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}\|}

  • CBC-MAC is secure as long as q<<X1/2q<<\|\mathcal{X}\|^{1/2}.
  • NMAC is secure as long as q<<K1/2q<<\|\mathcal{K}\|^{1/2}.
  • Example: For AES, if we want AdvPRF[A,FECBC]232Adv_{PRF}[A,F_{ECBC}]\leq 2^{-32}, then q2/X<232q^2/\|\mathcal{X}\|<2^{-32}, since X=2128\|\mathcal{X}\|=2^{128}, so after q=248q=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:

x,y,w,  FBIG(k,x)=FBIG(k,y)FBIG(k,x    w)=FBIG(k,y    w)\forall x,y,w,\;F_{BIG}(k,x)=F_{BIG}(k,y)\Rightarrow F_{BIG}(k,x\;\|\;w)=F_{BIG}(k,y\;\|\;w)

let FBIG:K×XYF_{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:

  1. Issue Y1/2\|\mathcal{Y}\|^{1/2} messages queries randomly, and obtain responses (mi,tt),i=1,2,...,Y1/2(m_i,t_t),i=1,2,...,\|\mathcal{Y}\|^{1/2}.
  2. We can find collision tu=tvt_u=t_v with high probability, according to the birthday paradox.
  3. Choose arbitrary ww and query for t=FBIG(k,mu    w)t=F_{BIG}(k,m_u\;\|\;w).
  4. Output (mv    w,t)(m_v\;\|\;w, t).

So a better rand construct is Rand CBC RCBC :
42

Security is:

AdvMAC[A,IRCBC]AdvPRF[B,F](1+2q2X)Adv_{MAC}[A,I_{RCBC}]\leq Adv_{PRF}[B, F]\cdot(1 + \frac{2q^2}{\|\mathcal{X}\|})

Comparison between ECBC and NMAC :

  1. ECBC is commonly used as an AES-based MAC . e.g. CCM encryption mode(used in 802.11i).
  2. NMAC not usually used with AES or 3DES , 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 mm then output m    0,m    00,...m\;\|\;0, m\;\|\;00,..., since pad(m)=pad(m    0)=pad(m    00)=...pad(m)=pad(m\;\|\;0)=pad(m\;\|\;00)=...
For security, padding must be invertible, and secure:

m0m1,pad(m0)pad(m1)\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)=10100100pad(10100)=10100100, pad(10100100)=1010010010000000pad(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)
43
key = (k,k1,k2)(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 Carter-Wegman MAC

ECBC and NMAC are sequential, can we build a parallel MAC from a small PRF ?
Of course, it is named PMAC (Parallel MAC):
44
the function PP here is used to encrypt sequence, to avoid swap attack. Without PP, the attacker could swap two blocks and get the same tag.

Theorem: For any L>0L>0, If FF is a secure PRF over (K,X,X)(\mathcal{K},\mathcal{X},\mathcal{X}) then FPMACF_{PMAC} is a secure PRF over (K,XL,X)(\mathcal{K},\mathcal{X}^{\leq L},\mathcal{X}).
In particular, for any efficient q-query PRF adversary AA attacking FPMACF_{PMAC}, there exists an adversary BB such that:

AdvPRF[A,FPMAC]AdvPRF[B,F]+2q2L2XAdv_{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 re-computed 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:
45
so the attacker could only query 1 message.

  • Example, one time MAC :
    • let qq be a large prime (e.g. q=2128+51q=2^{128}+51)
    • key=(a,b){1,...,q}2key=(a,b)\in\{1,...,q\}^2, two random int in [1,q][1,q].
    • msg=(m[1],...,m[L])msg=(m[1],...,m[L]) where each block is 128 bit int.

    S(key,msg)=Pmsg(a)+b  (mod  p)S(key,msg)=P_{msg}(a)+b\;(mod\;p)

    where

    Pmsg(x)=xL+1+m[L]xL+...+m[1]xP_{msg}(x)=x^{L+1}+m[L]x^L+...+m[1]x

    is a polynomial of degree L+1L+1.

Theorem: the one-time MAC in the last example, we have:

m1m2,t1,t2,  Pra,b[S((a,b),m1)=t1    S((a,b),m2)=t2]L/q\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,msg1)S(key, msg_1) the adversary has no info about S(key,msg2)S(key,msg_2).

By one time MAC we can construct many-time MAC with high speed:
Let (S,V)(S,V) be a secure one-time MAC over (KI,M,{0,1}n)(\mathcal{K}_{I},\mathcal{M},\{0,1\}^n).
Let F:KF×{0,1}n{0,1}nF:\mathcal{K}_F\times\{0,1\}^n\rightarrow\{0,1\}^n be a secure PRF .
Carter-Wegmen MAC :

CW((k1,k2),m)=(r,F(k1,r)S(k2,m))CW((k_1,k_2),m)=(r,F(k_1,r)\oplus S(k_2,m))

for random r{0,1}nr\leftarrow\{0,1\}^n.
So given t=F(k1,r)S(k2,m)t=F(k_1,r)\oplus S(k_2,m), we can run the verification function as:

V(k2,m,F(k1,r)t)V(k_2,m,F(k_1,r)\oplus t)

Theorem: If (S,V)(S,V) is a secure one time MAC and FF is a secure PRF then CW is a secure MAC outputting tags in {0,1}2n\{0,1\}^{2n}.

# Collision resistance

# Introduction

So far, four MAC constructions:
46

Definition: Let H:MTH:\mathcal{M}\rightarrow\mathcal{T} be a hash function (H>>T\|\mathcal{H}\|>>\|\mathcal{T}\|),
A collision for HH is a pair m0,m1Mm_0,m_1\in\mathcal{M} such that:

H(m0)=H(m1)  and  m0m1H(m_0)=H(m_1)\;and\;m_0\neq m_1

A function HH is collision resistant if for all explicit efficient AA,

AdvCR[A,H]=Pr[A  outputs  collision  for  H]Adv_{CR}[A,H]=Pr[A\;outputs\;collision\;for\;H]

is negligible.

Let I=(S,V)I=(S,V) be a MAC for short messages over (K,M,T)(\mathcal{K},\mathcal{M},\mathcal{T}) (e.g. AES ).
Let H:MbigMH:\mathcal{M}^{big}\rightarrow\mathcal{M}.
Then we can construct a MAC :

Sbig(k,m)=S(k,H(m))Vbig(k,m,t)=V(k,H(m),t)S^{big}(k,m)=S(k,H(m))\\ V^{big}(k,m,t)=V(k,H(m),t)

Theorem: If II is a secure MAC and HH is collision resistant then IbigI^{big} is a secure MAC

Suppose HH is not resistant, and the attacker can obtain collision (m0,m1)(m_0,m_1). Then after quering the tag for m0m_0, the attacker can output (m1,tag(m0)(m_1,tag(m_0) since H(m0)=H(m1)H(m_0)=H(m_1).

# Generic birthday attack

Theorem (birthday paradox): Let r1,...,rn{1,...,B}r_1,...,r_n\in\{1,...,B\} be independent identically distributed integers. Then when n=1.2×B1/2n=1.2\times B^{1/2} then Pr[ij:ri=rj]1/2Pr[\exists i\neq j:r_i=r_j]\geq 1/2.

Proof: we only prove when r1,...,rnr_1,...,r_n are all subject to uniform distribution (it’s the worst case):

Pr[i,j,ri=rj]=1Pr[ij,rirj]=1B1B×B2B×...×Bn+1B=1i=1n1(1iB)1i=1n1ei/B=1e1Bi=1n1i1en22B1e0.72>1/2\begin{aligned} Pr[\exists i,j,r_i=r_j] &=1-Pr[\forall i\neq j,r_i\neq r_j]\\ &=1-\frac{B-1}{B}\times\frac{B-2}{B}\times...\times\frac{B-n+1}{B}\\ &=1-\prod_{i=1}^{n-1}(1-\frac{i}{B})\\ &\geq 1-\prod_{i=1}^{n-1}e^{-i/B}\\ &=1-e^{-\frac{1}{B}\sum_{i=1}^{n-1}i}\\ &\geq 1-e^{-\frac{n^2}{2B}}\\ &\geq 1-e^{-0.72}>1/2 \end{aligned}

So a generic attack is randomly choose 2n/22^{n/2} elements in M\mathcal{M}, then with a high probabilty that we can find a collision. O(2n/2)O(2^{n/2}).

# The Merkle-Damgard Paradigm

Given a CR (collision resistant) hash function for short messages, we can construct CR hash function for long messages. That is Merkle-Damgard iterated construction:
47
Give h:T×XTh:\mathcal{T}\times\mathcal{X}\rightarrow\mathcal{T}, we obtain H:XLTH:\mathcal{X}^{\leq L}\rightarrow\mathcal{T}.
We say hh is compression function and HiH_i is the chaining variables (the output of each hh).
Padding block:
48
if no space for at least 65-bits padding block, then add another block.

Theorem: If hh is collision resistant, then so is HH in Merkle-Damgard paradigm.

Proof: We prove collision on HH\Rightarrow collision on hh.
Suppose H(m)=H(m)H(m)=H(m'), then we consider the chaining variables:

IV=H0,H1,...,Ht,Ht+1=H(m)IV=H0,H1,...,Ht,Ht+1=H(m)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(Ht,mt    PB)=Ht+1=Ht+1=h(Ht,mt    PB)h(H_t,m_t\;\|\;PB)=H_{t+1}=H_{t+1}'=h(H_t',m_t'\;\|\;PB')

If HtHtH_t\neq H_t' or mtmtm_t\neq m_t' or PBPBPB\neq PB', then we obtain a collision for hh.
Otherwise, we have Ht=HtH_t=H_t', we can repeat the process above, since mmm\neq m' (collision for HH), then at least can we find HiHiH_i\neq H_i', then the collision for hh is found.
QED.

# Constructing compression functions

Suppose E:K×{0,1}n{0,1}nE:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n is a block cipher, then the Davies-Meyer compression function is:

h(H,m)=E(m,H)Hh(H,m) = E(m,H)\oplus H

Theorem: Suppose EE is an ideal cipher (is a collection of K\|\mathcal{K}\| random permutations), then finding a collision h(H,m)=h(H,m)h(H,m)=h(H',m') takes O(2n/2)O(2^{n/2}) evaluations of (E,D)(E,D), and it’s the best cost possible.

And there are other compression functions based on block cipher:

  • Miyaguchi-Preneel: h(H,m)=E(m,H)Hmh(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)mh(H,m)=E(m,H)\oplus m, this one is insecure!

# HMAC : a MAC from SHA-256

We now talk about MAC from a Merkle-Damgard hash function.
If H:XLTH:\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)S(k,m)=H(k\;\|\;m)

This one is insecure! Since Merkle-Damgard iteration has the extension property, so given H(k    m)H(k\;\|\;m), we can compute H(k    m    PB    w)H(k\;\|\;m\;\|\;PB\;\|\;w) for any ww.

Construction 2. Standardized method: HMAC (Hash-MAC)

S(k,m)=H(kopad    H(kipad    m))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 :
49
if we view the output k1,k2k_1,k_2 as the input two keys for NMAC . However, in HMAC , k1k_1 and k2k_2 are not independent.

HMAC is assumed to be a secure PRF , secure bounds are similar to NMAC – need q2/Tq^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:

  1. Query server with the message and a random byte.
  2. 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.
  3. Repeat the process to find other bytes of the tag.

Defense:
instread of:

1
2

return HMAC(key,msg)==tag;

we use:

1
2

return HMAC(key, HMAC(key, msg))==HMAC(key, tag);

So the attacker would not know the values being compared.

# Authenticated Encryption

# Active attacks on CPA-secure 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:
    50
    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:

  1. If message needs integrity while no confidentiality, use a MAC .
  2. If message needs both integrity and confidentiality, use authenticated encryption (this module).

# Definition

Definition: An authenticated encryotion system (E,D)(E,D) is a cipher where

E:K×M×N(optional)CD:K×C×N(optional)M{}\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 N\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 (m0,m1)(m_0,m_1).
While for ciphertext integrity, it’s natural that the attacker should not construct a ciphertext that is accepted:
51

(E,D)(E,D) has ciphertext integrity if forall efficient AA,

AdvCI[A,E]=Pr[challenger  outputs  1]Adv_{CI}[A,E]=Pr[challenger\;outputs\;1]

is negligible.

Definition: cipher (E,D)(E,D) has authenticated encryption ( AE ) if:

  1. semantically secure under CPA .
  2. has ciphertext integrity.
  • Example: CBC with rand IV does not provide AE , since it never outputs \bot so the integrity is not guaranteed.

If the AE is guaranteed, what intuition can we get?

  1. authenticity, which means that the attacker could not fool Bob into thinking a message is sent from Alice:
    52
  2. Security against CPA .

# Chosen ciphertext attacks ( CCA )

Adversary’s Power: both CPA and CCA :

  1. Can obtain the encryption of arbitrary messages of his choice.
  2. 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:
53
EE is CCA secure if for all efficient AA:

AdvCCA[A,E]=Pr[EXP(0)=1]Pr[EXP(1)=1]Adv_{CCA}[A,E]=|Pr[EXP(0)=1]-Pr[EXP(1)=1]|

is negligible.

  • Example: CBC with random IV is not CCA secure.
    The attacker could first do the CPA with two 1-block messages m0,m1m_0,m_1, and get (IV,cb[0])(IV,c_b[0]). Then the attacker can use CCA , to query the decryption of (IV1,cb[0])(IV\oplus 1,c_b[0]), the decryption is mb1m_b\oplus 1, then the attacker can learn bb.

Theorem: Let (E,D)(E,D) be a cipher that provides AE . then (E,D)(E,D) is CCA secure.
In particular, for any q-query efficient AA, there exists efficient B1,B2B_1,B_2 such that:

AdvCCA[A,E]2qAdvCI[B1,E]+AdvCPA[B2,E]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:
54
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 m0m_0 or m1m_1:
55
Step 3. Similar to step 1, we can get back to CCA queries. So as a whole:
56

# 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:

  1. MAC -then-encrypt (SSL), which means that tag for MAC is also encrypted.
  2. encrypt-then- MAC (IPsec), which means that the tag is for the encrypted cipher text and not encrypted.
  3. encrypt-and- MAC (SSH), which means that the tag is for the plain text and not encrypted.
    57

AE theorems:

  1. encrypt-then- MAC always provides AE .
  2. MAC -then-encrypt may be insecure against CCA attacks. However when EE is rand- CTR mode or rand- CBC mode, then it provides AE .

Standards:

  • GCM : CTR -mode encryption then CW- MAC (Carter-Wegmen MAC ).
  • CCM : CBC - MAC then CTR -mode encryption.
  • EAX : CTR -mode encryption then CMAC .

Instead of the combination of secure encryption and MAC , can we construct the AE mode directly? Yes, it’s OCB -mode:
58
where EE is a secure PRP , and PP is similar to the one in PMAC , the purpose of it is to emphasize the order. And NN 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 -then-encrypt mode, the decryption is three steps:

  1. Decrypt the cipher text.
  2. Check the padding to see if it’s valid.
  3. 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[0..255]g\in[0..255], and change the last byte of the second last block:
59
We know that 01H01H is a valid pad. So if and only if when the last byte of the last block is equal to gg, then the decryption of it will be 01H01H, 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, encrypt-then- MAC will completely avoid this problem.

# Special attack: attack on non-atomic decryption

Example: SSH Binary Packet Protocol
60
The process of decryption is:

  1. decrypt packet length field only!
  2. read as many packets as length specifies.
  3. decrypt remaining ciphertext blocks.
  4. chech the MAC tag.

So if the attacker wants to know the plaintext of a given ciphertext cc(Notice here the ciphertext is given but not constructed by attacker, so it’s not a CCA attack), then it can repeat sending 1-byte 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.
61

# Odds and ends

# Key derivation

Suppose the source key SK is uniform in K\mathcal{K}, and FF is a PRF with key space K\mathcal{K} and outputs in {0,1}n\{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))KDF(SK, CTX, L) := F(SK, (CTX\;\|\;0))\;\|\;F(SK, (CTX\;\|\;1))\;\|\;...\;\|\;F(SK, (CTX\;\|\;L))

where CTXCTX 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 Extract-then-Expand paradigm:
62
where salt is a fixed non-secret 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.

kHKDF(salt,sk)k\leftarrow HKDF(salt,sk)\\


Another KDF is Password-Based Key Derivation Function PBKDF .
Since the passwords have insufficient entropy and are vunerable to the dictionary attack.
So we need a new paradigm: Password-Based Key Derivation Function, it improves salt and slow hash function. The standard approach is PKCS#5 , H(c)(pwd    salt)H^{(c)}(pwd\;\|\;salt) iterate hash function cc times.

# Deterministic encryption

The deterministic encryption is for the cases when there is nounce or other random stuff, so if the key and the plaintext is fixed, the ciphertext is also fixed.
One example is the server querying the database. Each data entry has a “index” (Alice, Bob,…) and is encrypted in the database. When the server want to query, it sends the encrypted index, and database compares the encrypted index and sends back the encrypted data. The database doesn’t learn anything about plaintext in the whole process.
63
However, determinism means that two same messages are encrypted into same ciphertext, which leaks information. It cannot be CPA secure:
64
The solution is quite simple, the message structure can be unique like UserID.
So in this case, we can define Deterministic CPA secure:
65
if for all efficient AA,

AdvdCPA[A,E]=Pr[EXP(0)=1]Pr[EXP(1)=1]Adv_{dCPA}[A,E]=|Pr[EXP(0)=1]-Pr[EXP(1)=1]|

is neglibigle.
The most different here is that mi,0m_{i,0} and mi,1m_{i,1} should all be distinct. Let’s see some examples:

  • Example: CBC with fixed IV is not deterministic CPA secure:
    66
  • Example: CTR -mode with fixed IV is not deterministic CPA secure:
    67

# Deterministic encryption constructions: SIV and wide PRP

Construction 1. Synthtic IV ( SIV )
Let (E,D),E(k,m;r)c(E,D),E(k,m;r)\rightarrow c be a CPA -secure encryption and F:K×MRF:\mathcal{K}\times\mathcal{M}\rightarrow\mathcal{R} be a secure PRF . Then we define:

Edet((k1,k2),m)=E(k2,m;F(k1,m))E_{det}((k_1,k_2),m)=E(k_2,m;F(k_1,m))

Since r=F(k1,m)r=F(k_1,m) is indistinguishable from a real random choice, EdetE_{det} is semantically secure under determinstic CPA .
In the previous discussion we know that confidentiality cannot be guaranteed without integrity, so we need to achieve Deterministic authenticated encryption ( DAE ).
Consider a SIV special case, SIV-CTR :
68
69

Theorem: if FF is a secure PRF and FctrF_{ctr} from CTR -mode is CPA secure, then SIV-CTR provides DAE .

Construction 2. just use a PRP
Let (E,D)(E,D) be a secure PRP , E:K×XXE:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{X}, then it is semantically secure under deterministic CPA .
In the game, the adversary would only see q different random values in X\mathcal{X} so he cannot learn anything about plaintext.


However, construction of PRP in a large message space is not easy. And we will introduce EME to construct a wide block PRP .
Goal: let E:K×{0,1}n{0,1}nE:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n be a secure PRP , we can construct a PRP on {0,1}N\{0,1\}^N where N>>nN>>n:
70
where key=(K,L)key=(K,L), M=MPMCM=MP\oplus MC, ipppi=ppp0...pppblocks1\sum_ippp_i=ppp_0\oplus...\oplus ppp_{blocks-1}, and PP function is similar in the previous construction.
Each EE function is E(K,)E(K,\cdot).


PRP -based deterministic CPA secure is quite simple, if (E,D)(E,D) is a secure PRP , then:
71
provides DAE .

# Tweakable encryption

An example that we need tweakable encryption is the disk encryption. Since the disk space is fixed, we need the ciphertext to have no expansion.
If we use PRP to encrypt:
72
then sector 1 and sector 3 may have the same context. So we improve:
73
in this case, the attacker can tell if a block is changed and then revert.
But the problem is quite troublesome to solve, so we just ignore it here.
Obviously in the construction we need to manage several keys.
Goal: construct many PRP s from a keyK\in\mathcal{K}.
E:K×T×XXE:\mathcal{K}\times\mathcal{T}\times\mathcal{X}\rightarrow\mathcal{X}, where t=1,2,...t=1,2,... is called tweak. We use the number of sectors as the tweak. We hope that E(k,t,)E(k,t,\cdot) is indistinguishable from a random permutation on X\mathcal{X}.
And we can define a secure block ciphers:
74
The trivial construction:
let (E,D)(E,D) be a secure PRP , E:K×XXE:\mathcal{K}\times\mathcal{X}\rightarrow\mathcal{X} and:

Etweak(k,t,x)=E(E(k,t),x)E_{tweak}(k,t,x)=E(E(k,t), x)

XTS tweakable block cipher:
let (E,D)(E,D) be a secure PRP , E:K×{0,1}n{0,1}nE:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n and:
75
ii and function PP are used to distinguish index and order,


Summary:

  1. Use tweakable encryption when you need many independent PRP s from one key.
  2. XTS is more efficient than the trivial construction, but both are narrow blocks.
  3. EME is a tweakable mode for wide blocks, but slower.

# Format preserving encryption

For example, the card number may have some fixed format: bbbb bbnn nnnn nnnc.
And the encrypted card should “look like” a credit card, so we need Format Preserving Encryption ( FPE ).
Suppose ss is the total # credit cards in the world. Then the encryption process is:

  1. map given card number to {0,1,...,s1}\{0,1,...,s-1\}.
  2. apply PRP and get an output in {0,1,...,s1}\{0,1,...,s-1\}.
  3. map out back to a card number.

Given a secure PRF F:K×{0,1}n{0,1}nF:\mathcal{K}\times\{0,1\}^n\rightarrow\{0,1\}^n, we can construct such PRP .
Step 1.: from {0,1}n\{0,1\}^n to {0,1}t\{0,1\}^t where 2t1<s2t2^{t-1}<s\leq 2^t. Here we can use the Luby-Rackoff with truncate F:K×{0,1}t/2{0,1}t/2F:\mathcal{K}\times\{0,1\}^{t/2}\rightarrow\{0,1\}^{t/2}:
76
Step 2.: from {0,1}t\{0,1\}^t to {0,1,...,s1}\{0,1,...,s-1\}. Since {0,1,...,s1}\{0,1,...,s-1\} is a subset of {0,1}t\{0,1\}^t, the construction of E:K×{0,1,...s1}{0,1,...,s1}E':\mathcal{K}\times\{0,1,...s-1\}\rightarrow\{0,1,...,s-1\} is quite simple: iterate EE until the output is inside the subset:
77
since s>2t1s>2^{t-1}, so it will not take too long to find the output.

Noticing: FPE guarantees no integrity.

# Basic Key exchange

# Trusted 3rd3^{rd} party

Problem: When a bunch of users need to communicate with each other, then for a user he may need to store several distinct keys for different opponents:
78

A better solution is to make an online Trusted 3rd party ( TTP ):
79

So that each user just needs to store one key with TTP .
A toy protocol: If Alice wants a shared secret key with Bob, then she asked the TTP , then TTP returns two messages:

E(kA,"A,B"    kAB)E(kB,"A,B"    kAB)E(k_A,"A,B"\;\|\;k_{AB})\\ E(k_B,"A,B"\;\|\;k_{AB})

the first message is for Alice who has kAk_A, so she could decrypt and learn kABk_{AB}. The second message will be sent to Alice, but Alice will send it to Bob who has kBk_B, so Bob will also learn kABk_{AB}.

If EE is CPA -secure, then the eavedropper will learn nothing about kABk_{AB}.

However the protocol is insecure against replay attack since the attacker can record the session between Alice and Bob, then replay it. So Bob may be fooled that Alice ordered the commodity twice.


Problem: Can we generate shared keys without TTP ? -Yes!

  • Merkle(1974)
  • Diffie-Hellman(1976)
  • RSA(1977)

# Merkle puzzles

Goal: Just by the communication between Alice and Bob, to generate a shared key safely.

Here is an easy but inefficient method: Merkle puzzles.

Here are what Alice and Bob should do:

  • Alice: prepare 2322^{32} puzzles,
    • For i=1,...,232i=1,...,2^{32} choose a random Pi{0,1}32P_i\in\{0,1\}^{32} and xi,ki{0,1}128x_i,k_i\in\{0,1\}^{128}, set:

    puzzlei=E(096    Pi,"Puzzle#xi"    ki)puzzle_i=E(0^{96}\;\|\;P_i,"Puzzle\#x_i"\;\|\;k_i)

    • Then send the 2322^{32} puzzles to Bob.
  • Bob: Choose a random puzzlejpuzzle_j, and solve it, obtain (xi,ki)(x_i,k_i), then send xjx_j back to Alice.
  • Alice: receive xjx_j, then get the shared key kjk_j.

For Alice, she needs to construct 2322^{32} puzzles, so the work is O(232)O(2^{32}) (If we think function EE and random function is O(1)O(1))

For Bob, he needs to solve a puzzle. The method is just to try every P{0,1}32P\in\{0,1\}^{32}, so it also takes time O(232)O(2^{32}).

But for an eavedropper, Although he can break the puzzle and get xjx_j, but he does not know which is puzzlejpuzzle_j, he needs to break all 2322^{32} puzzles to find puzzlejpuzzle_j. So the work is O(264)O(2^{64}).

The different effort needed for Alice, Bob and eavedropper is the key reason that the method is secure. However, it’s not that efficient.

# The Diffie-Hellman protocol

Goal: Just by the communication between Alice and Bob, to generate a shared key safely.

Protocol:

  • Fix a large prime number pp (e.g. 600 digits).
  • Fix an integer g{1,...,p}g\in\{1,...,p\}.
  • Alice: Choose a random a{1,...,p1}a\in\{1,...,p-1\}, send A=ga  (mod  p)A=g^a\;(mod\;p) to Bob.
  • Bob: Choose a random b{1,...,p1}b\in\{1,...,p-1\}, send B=gb  (mod  p)B=g^b\;(mod\;p) to Alice.
  • Then the shared key is gab  (mod  p)g^{ab}\;(mod\;p).

For Alice, she can computer the key by BaB^a, and for Bob he can compute by AbA^b.

However, for eavedropper who just knows A,BA,B, it’s quite difficult to computer gab  (mod  p)g^{ab}\;(mod\;p). The loglog function is much slower than powerpower function. The run time may be exp(O~(n3)exp(\tilde{O}(\sqrt[3]{n}) (GNFS algorithm, best known). If the operator is defined on elliptic curve group, then it takes more time to compute loglog, roughly exp(O~(n/2))exp(\tilde{O}(n/2)).


However, the protocol is insecure to Man-in-the-Middle MiTM attack:

  • Alice sends A=ga  (mod  p)A=g^a\;(mod\;p) to MiTM .
  • MiTM falsifies a aa', and sends A=ga(mod  p)A'=g^{a'}(mod\;p) to Bob.
  • Bob sends B=gb  (mod  p)B=g^b\;(mod\;p) to MiTM .
  • MiTM falsifies a bb', and sends B=gb(mod  p)B'=g^{b'}(mod\;p) to Alice.

So now, Alice thinks that the shared key is Ba=gab  (mod  p)B'^a=g^{ab'}\;(mod\;p), and Bob thinks that the shared key is Ab=gab  (mod  p)A'^b=g^{a'b}\;(mod\;p).
But the eavedropper knows a,b,A,Ba',b',A,B, so he can compute Ab=gab  (mod  p),Ba=gab  (mod  p)A^{b'}=g^{ab'}\;(mod\;p), B^{a'}=g^{a'b}\;(mod\;p).

An open problem: If several users what to communicate with each other, they all have a aia_i and share gai  (mod  p)g^{a_i}\;(mod\;p) on cloude or facebook, then can one generate a shared key with other users?
when the key is only shared by two users, we use DH protocol, but when the key is shared by four more users, the problem is not solved yet.

# Public-key encryption

Definition: a public-key encryption system is a triple of algorithms (G,E,D)(G,E,D):

  • G()G() outputs a random key pair (pk,sk)(pk,sk).
  • E(pk,m)E(pk,m) encrypts a message mm with public key pkpk.
  • D(sk,c)D(sk,c) decrypts a ciphertext cc with secret key sksk.

Consistency: D(sk,E(pk,m))=mD(sk, E(pk,m))=m.

The semantic secure of public-key encryption:
80
(G,E,D)(G,E,D) is semantic secure (a.k.a IND-CPA) if for all efficient AA,

AdvSS[A,E]=Pr[EXP(0)=1]Pr[EXP(1)=1]Adv_{SS}[A,E]=|Pr[EXP(0)=1]-Pr[EXP(1)=1]|

is negligigle.

Then we can establish a shared key:

  • Alice: use G()G() to generate (pk,sk)(pk,sk), and send "Alice, pkpk" to Bob.
  • Bob: Choose a random x{0,1}128x\in\{0,1\}^{128}, and send “Bob,E(pk,x)E(pk,x)” to Alice.
  • Alice: receive “Bob,E(pk,x)E(pk,x)”, then compute D(sk,E(pk,x))=xD(sk,E(pk,x))=x. xx is the shared key.

The adversary can only obtain pk,E(pk,x)pk, E(pk, x), and cannot learn about xx, since it’s indistinguishable from a real random number.

However, the encryption is still insecure against MiTM attack:
81

# Basic number theory

Lemma: xZNx\in\mathbb{Z}_N has an inverse if and only if gcd(x,N)=1gcd(x,N)=1.

Proof: gcd(x,N)=1gcd(x,N)=1, then exists a,ba, b s.t. ax+bN=1ax+bN=1, then ax=1  (mod  N)ax=1\;(mod\;N).

If gcd(x,N)>1gcd(x,N)>1, then a,ax1  (mod  N)\forall a, ax\neq 1\;(mod\;N). If ax=1  (mod  N)ax=1\;(mod\;N), then exists bb, such that ax=bN+1ax=bN+1, then axbN=1ax-bN=1, so gcd(a,N)=1gcd(a,N)=1.

We define ZN={xZN    gcd(x,N)=1}\mathbb{Z}_{N}^*=\{x\in \mathbb{Z}_N\;|\;gcd(x,N)=1\}.

Fermat’s Theorem: let pp be a prime, xZp\forall x\in\mathbb{Z}_p^* then xp1=1  (mod  p)x^{p-1}=1\;(mod\;p).

In contrast, if 2p1=1  (mod  p)2^{p-1}=1\;(mod\;p), then Pr[p  not  prime]<260Pr[p\;not\;prime]<2^{-60}.

Definition: For gZpg\in\mathbb{Z}_p^*, the set {1,g,g2,g3,...}\{1,g,g^2,g^3,...\} is called the group generated by gg, denoted as <g><g>.

The order of gZpg\in \mathbb{Z}_p^* is the smallest kk s.t. gk=1  (mod  p)g^k=1\;(mod\;p), denoted as ord(g)ord(g), also is the size of <g><g>.

Lagrange Theorem: gZp\forall g\in \mathbb{Z}_p^*, ord(g)ord(g) divides p1p-1.

Euler Theorem: let φ(N)=ZN\varphi(N)=\|\mathbb{Z}_N^*\|, then xZN\forall x\in \mathbb{Z}_N^*, xφ(N)=1  (mod  N)x^{\varphi(N)}=1\;(mod\;N).

Definition: let pp be an odd prime, xZpx\in\mathbb{Z}_p is a quadratic residue ( QR ) if it has a square root, that is, yZp,y2=x  (mod  p)\exists y\in \mathbb{Z}_p^*,y^2=x\;(mod\;p).

Theorem: xZpx\in\mathbb{Z}_p^* is a QR x(p1)/2=1\Leftrightarrow x^{(p-1)/2}=1 in Zp\mathbb{Z}_p, And x(p1)/2x^{(p-1)/2} is called the Legendre symbol of xx over pp. Then x=x(p+1)/4\sqrt{x}=x^{(p+1)/4}.

# Intractible problems

Dlog(gx)=xDlog(g^x)=x is a very complexed function.

So a CR hash function is defined as H(x,y)=gxhyH(x,y)=g^xh^y.
To find a collision for HH: H(x0,y0)=H(x1,y1)H(x_0,y_0)=H(x_1,y_1), then we need to compute h=g(x0x1)/(y0y1)h=g^{(x_0-x_1)/(y_0-y_1)}, we need to use DlogDlog function, which is quite hard.

Let Z(2)(N)={N=pq,  where  p,q  are  primes}\mathbb{Z}_{(2)}(N)=\{N=pq,\; where\;p,q\;are\;primes\}, then the problems are intractible:

  • Factor a random NN in Z(2)(N)\mathbb{Z}_{(2)}(N).
  • Given a polynomial f(x)f(x) and a random NZ(2)(N)N\in\mathbb{Z}_{(2)}(N), to find a xZNx\in\mathbb{Z}_N s.t. f(x)=0f(x)=0.

# Public Key Encryption from Trapdoor Permutations

# definitions and security

For symmetric ciphers we had two security notions:

  • One-time security.
  • Many-time security( CPA ).

and we showed that One-time security $\not\Rightarrow $ Many-time security, whichs means that a key should never be used more than once for one-time security.

However, for public key encryption, we need to guarantee that One-time security \Rightarrow Many-time security. Since the attacker can always use the public key to encrypt any message at his will. And we hope the public key encryption must seem like randomized.

The definition of (pub-key)Chosen Ciphertext Security is a bit different:
82

The difference is because a secure symmetric cipher must provide both security and integrity, roughly speaking to make sure that the attacker cannot construct ciphertext himself. However, for public key encryption, the attacker can always construct ciphertext himself, so we define and require the CCA secure directly.

Then EE is CCA secure (a.k.a IND-CCA) if for all efficient AA:

AdvCCA[A,E]=Pr[EXP(0)=1]Pr[EXP(1)=1]Adv_{CCA}[A,E]=|Pr[EXP(0)=1]-Pr[EXP(1)=1]|

is negligible.

  • Example, suppose an attacker has the ability to change the header of cipher text, and the corresponding plaintext is changed from “to: alice” to “to: david”, then the public key encryption is not secure:
    83
    The attacker query for the ciphertext for “(to:alice,0)” and “(to:alice,1)”, and modify the ciphertext for “(to:alice,b)” to “(to:david,b)”, and then send back the ciphertext.

# Constructions

Definition: A trapdoor function ( TDF ) XY\mathcal{X}\rightarrow\mathcal{Y} is a triple of efficient algorithms (G,F,F1)(G,F,F^{-1}):

  • G()G() is a randomized algorithm outputing a key pair (pk,sk)(pk,sk).
  • F(pk,)F(pk,\cdot) is a determined function XY\mathcal{X}\rightarrow\mathcal{Y}.
  • F1(sk,)F^{-1}(sk,\cdot) defines a function YX\mathcal{Y}\rightarrow\mathcal{X} that inverts FF.

More precisely, x,F1(F(x))=x\forall x,F^{-1}(F(x))=x.

Also, we define what is a secure trapdoor function:
84

To make sure that F(pk,)F(pk,\cdot) is a “one-way” function, which means it can be evaluated easily and cannot be inverted without sksk.


We can construct public-key encryption from TDF :

  • (G,F,F1)(G,F,F^{-1}) is a secure TDF .
  • (E,D)(E,D) is a symmetric authentication secure encryption.
  • H:XYH:\mathcal{X}\rightarrow\mathcal{Y} is a hash function.

We construct:

E(pk,m):{xrandomXyF(pk,x)kH(x)cE(k,m)output:(y,c),D(sk,(y,c)):{xF1(sk,y)kH(x)mD(k,c)output:mE(pk,m): \begin{cases} x\stackrel{random}{\longleftarrow} \mathcal{X}\\ y\leftarrow F(pk,x)\\ k\leftarrow H(x)\\ c\leftarrow E(k,m)\\ output: (y,c) \end{cases},\quad D(sk,(y,c)): \begin{cases} x\leftarrow F^{-1}(sk,y)\\ k\leftarrow H(x)\\ m\leftarrow D(k,c)\\ output: m \end{cases}

Theorem: If (G,F,F1)(G,F,F^{-1}) is a secure TDF , (E,D)(E,D) provides authentication security, and HH is collision resistant, then (G,E,D)(G,E,D) is CCAroCCA^{ro} secure.

Remark: the little “ro” indicates that the security is set in a random oracle model, but not important here.


Never encrypt by applying FF directly to plaintext!

cF(pk,m)mF1(sk,c)c\leftarrow F(pk,m)\\ m'\leftarrow F^{-1}(sk,c)\\

since it’s now deterministic and cannot be semantic secure, and has many attacks.

# The RSA trapdoor permutation

The RSA trapdoor permutation is first published on Scientific American in 1977, and is widely used in SSL/TLS, secure e-mail, secure file systems…

The RSA trapdoor permutation is:

  • G()G(): choose two random primes p,qp,q\approx 1024 bits, set N=pqN=pq. Choose integer e,de,d s.t. ed=1(mod  φ(N))e\cdot d=1(mod\;\varphi(N)). Output pk=(N,e),sk=(N,d)pk=(N,e),sk=(N,d).
  • F(pk,x)=xeF(pk,x)=x^e.
  • F1(sk,y)=ydF^{-1}(sk,y)=y^d.

Consistency:

F1(sk,F(pk,x))=xed=xkφ(N)+1=x  (mod  N)\begin{aligned} F^{-1}(sk,F(pk,x))&=x^{ed}\\ &=x^{k\varphi(N)+1}\\ &=x\;(mod\;N) \end{aligned}

The RSA is a one-way function is based on the assumption that given N,e,yN,e,y, it’s hard to find x=y1/ex=y^{1/e}.

Emphasize again: The RSA permutation is not an encryption scheme, so you never use it directly to encrypt messages.

Textbook RSA which is insecure:

  • public key (N,e)(N,e), encrypt: cmec\leftarrow m^e in ZN\mathbb{Z}_N.
  • secret key (N,d)(N,d), decrypt: mcdm\leftarrow c^d in ZN\mathbb{Z}_N.

An simple attack is that, given a 64-bits m{0,...,264}m\in\{0,...,2^{64}\}, there 20%\approx 20\% probability that m=k1k2m=k_1\cdot k_2 where k1,k2<234k_1,k_2<2^{34}. Then we have c/k1e=k2ec/k_1^e=k_2^e, so a man-in-the-middle attack will work. The total attack time is around 240<<2642^{40}<<2^{64}.

# PKCS 1

PKCS1 v1.5

In practice we often apply some preprocessing to the plaintext before encryption, and the most common one is called PKCS 1 .

For example, if we need to setup a session and transmit a shared key, then the message may be a 128 bits AES key, we would append it:
85

where the first 2 bits are used to indentify it’s PKCS 1 mode 2 widely used in HTTPS, and the random pad should not contain ‘FF’, the resulting 2048 bits is sent to RSA encryption.

A simple attack to PKCS1 is discovered by Bleichenbacher, since the server always check the first two 2 bits are ‘02’ and return different error message, so we can:

  • given a ciphertext cc and public key (N,e)(N,e), send cc to server to check if the plaintext most significant bit is ‘02’.
  • multiple the ciphertext by 4e4^e, then the plaintext is shifted by 2 bits, send to the server and we learn the next 2 bits:

4eme=(4m)e=E(pk,m<<2)4^e\cdot m^e=(4m)^e=E(pk,m<<2)

  • repeat the above process until we get the plaintext.

Attacks discovered by Bleichenbacher and Klima et al. can be
avoided by treating incorrectly formatted messages blocks in a manner indistinguishable from correctly formatted RSA blocks.


PKCS1 v2.0: OAEP
the message is padded with ‘01’ following several 0s, and followed by a randomized padding, H,GH,G are two collision resistant hash function (like random oracle):
86

Theorem[FOPS’01] indicates that if H,GH,G are random oracles then RSA-OAEP is CCA secure. In practice we use SHA-256 for the hash functions.

Also there is OAEP+[Shoup’01] if we substitute the ‘0100…0’ by W(m,r)W(m,r) which is a random oracle:
87
for any trapdoor permutation FF, F-OAEP+ is CCA secure if H,G,WH,G,W are all random oracles.

There is SAEP+[B’01]:
88
If RSA is a trapdoor permutation (e=3e=3) then RSA-SAEP+ is CCA secure if H,GH,G are all random oracles.

What is notice worthy is that OAEP may be vulnerable to timing attack if is implemented incorrectly, so never implement it yourself.

# Is RSA a one-way function?

[Wiener’87] if d<N0.25d<N^{0.25} then RSA is insecure.

Wiener’s attack:
since ed=1(mod  φ(N))e\cdot d=1(mod\;\varphi(N)), then we have:

ed=kφ(N)+1eφ(N)kd=1dφ(N)e\cdot d=k\cdot\varphi(N)+1\Rightarrow\\ |\frac{e}{\varphi(N)}-\frac{k}{d}|=\frac{1}{d\cdot\varphi(N)}

Since N=pqN=pq, then φ(N)=(p1)(q1)N\varphi(N)=(p-1)(q-1)\approx N, and d<N0.25d<N^{0.25},we have:

1dφ(N)1N\frac{1}{d\cdot\varphi(N)}\leq\frac{1}{\sqrt{N}}

the inequality here is quite loose. Then since Nφ(N)=p+q+13NN-\varphi(N)=p+q+1\leq 3\sqrt{N}, So we have:

eNkdeNeφ(N)+eφ(N)kde(Nφ(N))Nφ(N)+1N3Neφ(N)+1N\begin{aligned} |\frac{e}{N}-\frac{k}{d}|&\leq |\frac{e}{N}-\frac{e}{\varphi(N)}|+|\frac{e}{\varphi(N)}-\frac{k}{d}|\\ &\leq \frac{e(N-\varphi(N))}{N\cdot\varphi(N)}+\frac{1}{\sqrt{N}}\\ &\leq \frac{3}{\sqrt{N}}\cdot\frac{e}{\varphi(N)}+\frac{1}{\sqrt{N}}\\ \end{aligned}

Remember that d,eN,φ(N)Nd,e\approx\sqrt{N},\varphi(N)\approx N, so we have

eNkd4N|\frac{e}{N}-\frac{k}{d}|\leq \frac{4}{\sqrt{N}}

Because d<N0.25d<N^{0.25}, so 4N12d2\frac{4}{\sqrt{N}}\leq \frac{1}{2d^2}. So:

eNkd12d2|\frac{e}{N}-\frac{k}{d}|\leq \frac{1}{2d^2}

The two rationals are so close here, so we can just try to find k/dk/d. And since ed=1(mod  k)ed=1(mod\;k), so gcd(k,d)=1gcd(k,d)=1, so somehow find k/dk/d and k,dk,d.

# RSA in practice

The recommended value for ee is 216+12^{16}+1, then choose N=pqN=pq randomly, compute d=eφ(N)1d=e^{\varphi(N)-1}. There are many potential attacks:

  • Timing attack[Kocher et al. 1997]: the time to compute cd  (mod  N)c^d\;(mod\;N) can expose dd.
  • Power attack[Kocher at al. 1999]: The power consumption of a smartcard to compute cdc^d can expose dd.
  • Faults attack[BDL’97]: A computer error during cdc^d can expose dd.

Faults attack example:

A common implementation of RSA is to compute cd  (mod  p)c^d\;(mod\;p) and cd  (mod  q)c^d\;(mod\;q) seprarately, then use 中国剩余定理 (Chinese Remainder Theorem, CRT ) to combine them to compute x=cd  (mod  pq)x=c^d\;(mod\;pq). (Obviously we have x=cd  (mod  p)x=c^d\;(mod\;p) and x=cd  (mod  q)x=c^d\;(mod\;q))

So when cd  (mod  q)c^d\;(mod\;q) is computed incorrectly, the result is xcd  (mod  q)x\neq c^d\;(mod\;q), so we have:

x=cd  (mod  p)xe=c  (mod  p)xcd  (mod  q)xec  (mod  q)p    xec,q  ∤  xecx=c^d\;(mod\;p)\Rightarrow x^e=c\;(mod\;p)\\ x\neq c^d\;(mod\;q)\Rightarrow x^e\neq c\;(mod\;q)\\ \Rightarrow p\;|\;x^e-c,q\;\not |\;x^e-c

So:

gcd(xec,N)=pgcd(x^e-c,N)=p

which reveals pp.

Besides, If two Internet applications use the same pp but different qq, we can also use gcd(pq,pq)=pgcd(pq,pq')=p to find pp. The experiment result is that about 0.4%0.4\% of public HTTPS keys can be factored!.

# Public key encryption from Diffie-Hellman: ElGamal

ElGamal: Converting Diffie-Hellman protocol to publick key encryption:

  • G()G(): choose a random generator gGg\in G, and random aZna\in\mathbb{Z}_n, output sk=a,pk=(g,h=ga)sk=a,pk=(g,h=g^a).
  • H:G2KH:G^2\rightarrow \mathcal{K} is a hash function.

E(pk,m)={brandomZnugbvhbkH(u,v)cE(k,m)output:(u,c),D(sk,(u,c))={vuakH(u,v)mD(k,c)output:mE(pk,m)=\begin{cases} b\stackrel{random}{\longleftarrow} \mathbb{Z}_n\\ u\leftarrow g^b\\ v\leftarrow h^b\\ k\leftarrow H(u,v)\\ c\leftarrow E(k,m)\\ output:(u,c) \end{cases},\quad D(sk,(u,c))=\begin{cases} v\leftarrow u^a\\ k\leftarrow H(u,v)\\ m\leftarrow D(k,c)\\ output:m \end{cases}

Since g,hg,h is fixed before encryption, so we can pre-compute g,g2,g4,g8,...g,g^2,g^4,g^8,... to speed up the computation of gbg^b.

# ElGamal security

  • Computational DH assumption is for all efficient algorithm AA, Pr[A(g,ga,gb)=gab]Pr[A(g,g^a,g^{b})=g^{ab}] is negligible. In other words, it is hard to compute gabg^{ab} by g,ga,gbg,g^a,g^b.

  • Hash DH assumption is:

(g,ga,gb,H(gb,gab))p(g,ga,gb,R)(g,g^a,g^b,H(g^b,g^{ab}))\approx_p (g,g^a,g^b,R)

where gg is a random generator in GG, a,ba,b are random elements in Zn\mathbb{Z}_n, RR is a random element in K\mathcal{K}. We need the hash function to be indistinguishable from real random.*

Here HH acts as an extractor, (gb,gab)(g^b,g^{ab}) is not uniform on G2G^2 but H(gb,gab)H(g^b,g^{ab}) is a uniform distribution on K\mathcal{K}.

Since the hash function is indistinguishable from real random, the semantic security for Hash DH assumption ElGamal is quite easy:
90

  • Interactive HD assumption. To prove CCA security, we need stronger assumption- IDH . The game is:
    91
    IDH holds if for any efficient AA and several queries, Pr[A  outputs  gab]Pr[A\;outputs\;g^{ab}] is negligible.

Theorem: If IDH holds in group GG, (E,D)(E,D) provides authentication security and H:G2KH:G^2\rightarrow\mathcal{K} is a random oracle, then ElGamal is CCAroCCA^{ro} secure.

# ElGamal variants with better security

Can we achieve CCA security just with CDH instead of IDH ? --Yes!

Twin ElGamal:

  • G()G(): choose a random generator gGg\in G, and random a1,a2Zna_1,a_2\in\mathbb{Z}_n, output sk=(a1,a2),pk=(g,h1=ga1,h2=ga2)sk=(a_1,a_2),pk=(g,h_1=g^{a_1},h_2=g^{a_2}).

E(pk=(g,h1,h2),m)={brandomZnkH(gb,h1b,h2b)cE(k,m)output:(gb,c),D(sk=(a1,a2),(u,c))={kH(u,ua1,ua2)mD(k,c)output:mE(pk=(g,h_1,h_2),m)=\begin{cases} b\stackrel{random}{\longleftarrow} \mathbb{Z}_n\\ k\leftarrow H(g^b,h_1^b,h_2^b)\\ c\leftarrow E(k,m)\\ output:(g^b,c) \end{cases},\\ D(sk=(a_1,a_2),(u,c))=\begin{cases} k\leftarrow H(u,u^{a_1},u^{a_2})\\ m\leftarrow D(k,c)\\ output:m \end{cases}

Theorem: If CDH holds in group GG, (E,D)(E,D) provides authentication security, and HH is a random oracle, then twin ElGamal is CCAroCCA^{ro} secure.


Can we achieve CCA security without random oracle HH? --Yes!

  • Option 1. use HDH assumption in “bilinear group” --special elliptic curve with more structure. [CHK’04+BB’04]
  • Option 2. use Decision-DH assumption in any group. [CS’98]

# A unifying theme

One-way function(informal): for all efficient AA, if Pr[f(A(f(x)))=f(x)]Pr[f(A(f(x)))=f(x)] is negligible for xx random in X\mathcal{X}, then we think it as a one-way function.

Remark: why not just ask for A(f(x))=xA(f(x))=x? Because the funtion extentionality, we think f(x)=g(x)f=g\forall f(x)=g(x)\rightarrow f=g. e.g. f(x)=0f(x)=0 is not a one-way function.

  • PRG is one-way function. Let f:XY,Y>>Xf:\mathcal{X}\rightarrow\mathcal{Y},\|\mathcal{Y}\|>>\|\mathcal{X}\| be a secure PRG , then it is a one-way function. Proof: if exists AA inverts ff, then we can construct BB to distinguish PRG from real random:

B(y)={0f(A(y))=y1otherwiseB(y)=\begin{cases} 0&f(A(y))=y\\ 1&otherwise \end{cases}

  • Discrete log is a one-way function. Computation of power is much eaiser than log, and is widely used in key-exchange and public-key encryption. f(x)=gxf(x)=g^x.

  • RSA is a one-way function. f(x)=xef(x)=x^e is one-way function when N=pqN=pq, ed=1(mod  φ(N))ed=1(mod\;\varphi(N)). It’s hard to calculate e-th root.

Edited on Views times