「Cryptography-Dan」:Block Cipher 1

「Cryptography-Dan」:Block Cipher 1

这篇文章介绍了块密码。

文中主要分为四个部分。

第一个部分解释了块密码的基础概念,包括抽象概念PRF(伪随机函数)和PRP(伪随机置换)的定义及其安全定义。

第二个部分介绍了经典块密码DES,包括DES的Feistel网络,支撑Feistel网络的Luby-Rackoff定理,triple-DES和对DES的一些攻击方法。特别是有效的中间相遇攻击。

第三个部分介绍了目前流行的块密码AES,包括AES的结构和一些攻击方法等。

最后一小部分介绍了用PRG构造PRF,再利用Feistel网络变成块密码。

Overview

块密码,简单来说,就是在给定密钥 (k bits)下,将输入块(n bits)映射到输出块(n bits)。

block ciphers

比如,在3DES中,n = 64 bits, k = 168 bits;在AES中,n = 128 bits, k = 128, 192, 256 bits。

块密码算法一般是通过迭代(iteration)实现的,如下图的结构:

block ciphers built by iteration

密钥k通过密钥扩展(key expansion)得到一系列轮密钥。

明文块m通过迭代运算,得到最终的密文c,其中每一次运算称为轮函数R(k, m)。

对于3DES来说,轮数为n = 48,对于AES-128来说,轮数为n = 10。

虽然迭代运算会让块密码比流密码慢很多,但块密码有很多应用。

block ciphers performance

PRPs and PRFs

这里介绍两个抽象的概念,伪随机置换(PRP)和伪随机函数(PRF)。

Pseudo Random Function(PRF):

defined over(K, X, Y): $F:K\times X \rightarrow Y$ such that exists “efficient” algorithm to evaluate F(k, x)

【伪随机函数定义在(K, X, Y)上,只要求是可计算的,没有要求是可逆的】

Pseudo Random Permutations(PRP):

defined over(K, X): $E:K\times X\rightarrow X$ such that:

  1. Exists “efficient” deterministic algorithm to evaluate E(k, x)
  2. The function E(k, ·) is one to one
  3. Exists “efficient” inversion algorithm D(k, y)

【而伪随机置换定义在(K, X)上,除了要求是可计算的,还要求是一对一映射(单射),即存在可逆运算】

块密码都是PRPs(不然怎么解密),常见的PRP有3DES,AES等:

  • AES: $K \times X \rightarrow X$ where K = X = $\{0, 1\}^{128}$

  • 3DES: $K\times X \rightarrow X$ where X = $\{0, 1\}^{64}$ , K = $\{0, 1\}^{168}$

从定义上来说,任何PRP都是PRF;但一个PRF是PRP的充分条件是X=Y,且存在可逆运算(efficiently invertible)。

Secure PRFs

在介绍PRF的安全性之前,先定义一些符号:

$F: K \times X \rightarrow Y$ is a PRF.

  • Funs[X, Y]: the set of all functions from X to Y

    【X到Y的所有映射关系】

  • $S_F={ F(k, \cdot)}$ s.t. $k\in K$ $\subseteq$ Funs[X, Y]

    【确定k就确定了一种X到Y的映射关系】

Funs and SF

直觉上来说,当从Funs[X, Y]中随机采样的函数与从 $S_F$ 中随机采样的函数不可区分时,PRF是安全的。

Intuition: a PRF is secure if a random function in Funs[X, Y] is indistinguishable from a random function in $S_F$ .

定义下图的游戏:

attack PRF

云从Funs[X, Y]中随机选取一个函数f,并随机选择一个k,即确定了一个在 $S_F$ 中函数。

攻击者向云多次询问x的计算结果,对云来说,如果是b = 0,他返回f(x),如果b = 1,他返回F(k, x)。

当攻击者输入任意输入x时,都无法区分计算结果是f(x)计算的还是F(k, x)计算的,PRF是安全的。

Secure PRPs/Block Ciphers

块密码都是PRP,所以这里也在定义什么是安全的块密码。

同样定义一些符号:

$E: K\times X\rightarrow Y$ is a PRP ( X = Y).

  • Perms[X, Y]: the set of all one-to-one functions from X to Y

    【X到Y的所有的一对一映射关系】

  • $S_F={ E(k, \cdot)}$ s.t. $k\in K$ $\subseteq$ Perms[X, Y]

    【确定k就确定了一种X到Y的一对一映射关系】

同样,当从Perms[X, Y]中随机采样的函数与从 $S_F$ 中随机采样的函数不可区分时,PRP是安全的。

Intuition: a PRP is secure if a random function in Perms[X, Y] is indistinguishable from a random function in $S_F$ .

定义下图的游戏:

attack PRP

云从Perms[X, Y]中随机选取一个函数 $\pi$ ,并随机选择一个k,即确定了一个在 $S_F$ 中函数。

攻击者向云多次询问x的计算结果,对云来说,如果是b = 0,他返回$\pi(x)$,如果b = 1,他返回F(k, x)。

当攻击者输入任意输入x时,都无法区分计算结果是$\pi(x)$计算的还是F(k, x)计算的,PRP是安全的。

注意:这里是对任意输入,如果对某一个输入,攻击者能区分,这个PRP都是不安全的。

PRF $\rightarrow$ PRG

PRF的一个简单应用是把它变成一个PRG。

Let $F: K\times \{0, 1\}^n\rightarrow \{0, 1\}^n$ be a secure PRF.

The following $G: K\rightarrow \{0,1\}^{nt}$ is a secure PRF:

$$ G(k) = F(k, 0)\mid\mid F(k, 1) \mid\mid \dots \mid\mid F(k, t-1) $$

这是一种计数器模式,计数器模式最显著的优点是可并行计算。

此外该PRG的安全性来自于PRF的安全性,即F(k, ·)与f(·)不可区分。

DES

Data Encryption Standard(DES)

DES的核心就是Feistel网络结构:

DES Feistel
  • $R_i = f_i(R_{i-1})\oplus L_{i-1}$
  • $L_i = R_{i-1}$

对于给定的函数的轮函数 f1, …, fd: $ \{0,1\}^n\rightarrow \{0,1\}$ ,Feistel网络结构都可以构造出2n bits的可逆函数: $ F: \{0,1\}^{2n}\rightarrow \{0,1\}^{2n}$

Claim: for all f1, …, fd: $ \{0,1\}^n\rightarrow \{0,1\}$ , Feistel network $ F: \{0,1\}^{2n}\rightarrow \{0,1\}^{2n}$ is invertible.

证明:构造出可逆函数即可

inverse
  • $R_{i-1} = L_i$
  • $L_{i-1}=R_i\oplus f_i(L_i)$

需要注意的是,在解密电路中,轮函数的使用如下图是逆序使用的。

decryption circuit

Luby-Rackoff’85 Thm

支撑Feistel Network安全性的一个理论是Luby-Rackoff的一个定理,这将安全的PRF变成安全的PRP,这也是块密码(使用Feistel结构的块密码)安全性的支撑。

Thm:

$f:K\times \{0,1\}^n\rightarrow \{0,1\}^n$ a secure PRF

then, 3-round Feistel $F: K^3\times{0,1}^{2n}\rightarrow {0,1}^{2n}$ a secure PRP.

3-round Feistel

DES Structure

DES的核心是一个16轮的Feistel的网络。

DES

DES的输入是64 bits块,通过一个初始置换(IP),该置换并不是为安全性服务的,只是DES标准里的要求。

然后再通过16轮的Feistel网络,在Feistel网络中依次调用轮函数,轮函数中的轮密钥是通过初试密钥扩展得到的16个不同密钥。

最后再通过逆置换得到64 bits的输出块。

The function F(ki, x)

DES的轮函数结构如下图:

round function

轮函数的输入是32 bits x和48 bits的密钥ki:

  1. 32 bits x通过expansion box,扩展为48 bits。扩展方式只是复制一些位。

  2. 扩展后的x与轮密钥ki进行异或运算。

  3. 异或运算后的结果为48 bits,再被划分为8组6 bits,每一组都通过一个S-box,每一个S-box实则是一个非线形映射 ${0,1}^6\rightarrow {0,1}^4$ ,在实现中往往使用查表的形式使用。

    S-box
  4. 通过S-box后,又得到了32 bits,最后通过一个置换(Permutation),得到该轮的最终输出。

S-box

S-box也是DES中最重要的一部分,因为他是DES中唯一的非线性部分,它保证了整个DES的非线形映射关系。

来看一个糟糕的S-box的例子: $\mathrm{S}_{\mathrm{i}}\left(\mathrm{x}_{1}, \mathrm{x}_{2}, \ldots, \mathrm{x}_{6}\right)=\left(\mathrm{x}_{2} \oplus \mathrm{x}_{3}, \mathrm{x}_{1} \oplus \mathrm{x}_{4} \oplus \mathrm{x}_{5}, \quad \mathrm{x}_{1} \oplus \mathrm{x}_{6}, \quad \mathrm{x}_{2} \oplus \mathrm{x}_{3} \oplus \mathrm{x}_{6}\right)$

上式也可以写做: $\mathrm{S}{\mathrm{i}}(\mathbf{x})=\mathrm{A}{\mathrm{i}} \cdot x(\bmod 2)$

S-boxDES

我们称上面的S盒是一个线性函数。

这会带来什么影响呢?如果S盒是线性的,那么整个DES都会变成线性的,即存在一个确定的二元矩阵 $\mathbf{B}$ 满足:

DES

而该线性关系还有一个简单的检验方法:

test

Exhaustive Search Attacks

DES的密钥空间比较小,因此可以使用穷举密钥的方法攻击。

对于已知的一些明文-密文对,我们希望穷举攻击能得到唯一的一个密钥,而不是说对于一个明文-密文对,有多个密钥(映射关系)都符合。

因此支撑穷举攻击DES的一个定理是:

假设DES是一个理想的密码,即 $2^{56}$ 个密钥对应 $2^{56}$ 个不同的随机可逆函数,那么对于任意的明文-密文对($c = \mathrm{DES}(k,m)$) ,最多只有一个密钥的概率大于 99.5%。

证明:

假设存在一个密钥k’,不是真正的密钥k,但满足 $c = \mathrm{DES}(k’, m)=\mathrm{DES}(k,m)$ 。

这样的概率是小于 所有 $2^{56}$ 个密钥都满足该明文-密文对的概率。

Lemma

因此,如果已知两个明文-密文对,那么通过这两个DES pairs就可以以 $1-1/2^{71}$ 的概率确定出正确的密钥。

同样,对于AES-128来说,通过两个AES pairs就可以以 $1-1/2^{128}$ 的概率确定出正确的密钥。

因为DES的密钥空间实在是太小了,所以有一个DES challenge的挑战,随着计算能力的发展,破解DES的速度越来越快。

DES challenge

1: Triple-DES

一个抵御DES穷举攻击的算法是Triple- DES

  • Let $\mathrm{E}:\mathrm{K}\times \mathrm{M}\rightarrow \mathrm{M}$ be a block cipher.
  • Define $\mathrm{3E}: \mathrm{K}^3\times \mathrm{M}\rightarrow \mathrm{M}$ as $\mathrm{3E}((\mathrm{k_1},\mathrm{k_2},\mathrm{k_3}),\mathrm{m})=\mathrm{E}(\mathrm{k_1},\mathrm{D}(\mathrm{k_2},\mathrm{E}(\mathrm{k_3},\mathrm{m})))$

triple- DES为什么是E、D、E的运算顺序,而不是E、E、E的运算顺序?

因为对于Triple- DES来说,如果 $k_1=k_2=k_3$ ,就变成了single DES(虽然在运算速度上,没有什么必要)

Triple- DES的密钥空间大小是 $3\times 56=168$ bits,在运算上会比DES慢三倍,但攻击triple- DES只需要 $O(2^{118})$ 的时间复杂度。(下文介绍的中间相遇攻击)

Meet in the middle attack

为什么不用double DES?

因为有一种中间相遇攻击(meet in the middle attack),让攻击double DES的时间和穷举攻击single DES的时间差不多。

如果我们使用double DES,$\mathrm{2E}((\mathrm{k_1},\mathrm{k_2}),\mathrm{m})=\mathrm{E}(\mathrm{k_1},\mathrm{E}(\mathrm{k_2},\mathrm{m}))$

double DES

double DES的密钥空间为112 bits,但在中间相遇攻击下,穷举范围可以少一半比特。

中间相遇攻击的核心思想是,我们希望找到 $(k_1, k_2)$ 满足 $E(k_1, E(k_2, M))=C$ ,即满足:$E(k_2,M)=D(k_1, C)$ 。

Attack: M = (m1, …, m10), C = (c1, …, c10)

  1. build table and sort on 2nd column.

    从double DES 的左边的明文开始,枚举 $k_2$ ,计算 $E(k^i, M)$ 的值,最后按照 $E(k^i, M)$ 的值排序。

    build table
  2. for all $k\in {0,1}^{56} do:$ test if $D(k,C)$ is in 2nd column.

    从double DES的右边的密文开始检测,是否 $D(k,C)$ 存在在上述表中,如果 $E(k^i, M)=D(k,C)$ ,那么就得到了 $(k^i, k)=(k_2, k_1)$

分析一下攻击时间,第一部分是建表排序,第二部分是计算二分查表的时间。

Time = $2^{56} \log \left(2^{56}\right)+2^{56} \log \left(2^{56}\right)<2^{63}<<2^{112}, \quad \text { space } \approx 2^{56}$

同样的,中间相遇攻击同样可以应用于3DES中:$\text{Time}=2^{118},\quad \text{space}\approx 2^{56}$

2: DESX

$\mathrm{E}: \mathrm{K} \times{0,1}^{n} \rightarrow{0,1}^{\mathrm{n}} \text { a block cipher }$

Define EX as $\operatorname{EX}\left(\left(\mathrm{k}{1}, \mathrm{k}{2}, \mathrm{k}{3}\right), \mathrm{m}\right)=\mathrm{k}{1} \oplus \mathrm{E}\left(\mathrm{k}{2}, \mathrm{~m} \oplus \mathrm{k}{3}\right)$

对于DESX来说,密钥空间长度为: 64+56+64 = 184 bits,但同样的通过中间相遇攻击,time = $2^{64+56}=2^{120}$ .

需要注意的一点是,在实际使用中,有人使用 $\mathrm{k}{1} \oplus \mathrm{E}\left(\mathrm{k}{2}, \mathrm{m}\right) \text { and } \mathrm{E}\left(\mathrm{k}_{2}, \mathrm{m} \oplus \mathrm{k}_{1}\right)$ 的设计,这样的设计和原始DES一样易收ex. search的攻击。(通过中间相遇攻击)

More attacks on block ciphers

Attacks on the implementation

对于DES,还有一些针对实现上的攻击。

第一种是侧信道攻击(Side channel attacks),通过测量加密解密时的时间差异、能源消耗差异来得到一些额外的信息。

side channel attacks

另一种是Fault attacks,通过最后一轮的计算错误可能会暴露密钥k。

对于实现上的攻击的经验教训是:除了不要自己设计密码学算法,甚至都不要自己去实现。

Linear and differential attacks

该攻击的目标是,给定许多inp/out pairs,希望能在比 $2^{56}$ 更少的时间内攻击成功。

Linear cryptanalysis (overview):

let c = DES(k, m), suppose for random k, m:

prob

第一部分是msg bits的子集合,第二部分是密文bits 的子集合,第三部分是key bits的子集合。

如果这些都是相互独立的,那么这个概率应该为1/2,但因为有slightly 线性的关系,所以这个概率会有一点bias。对于DES来说,因为第五个S-box的一点bug,$\varepsilon=1/2^{21}\approx 0.0000000477$ .

Thm:

Thm

基于上述线性的关系,该定理表示如果给了 $1/ \varepsilon^2$ 个随机明文密文对,大部分都满足上式比特集合的线性关系。

所以,对于DES来说,$\varepsilon=1/2^{21}$ ,通过 $2^{42}$ 个inp/out pairs能在 $O(2^{42})$ 时间内得到 $k[l_1,…,k_u]$ 比特集异或的结果。

但其实不止是xor of key bits,实际上: can find 14个key bits in time $2^{42}$ 。(todo)

这样就将穷举攻击的复杂度降低到56-14=42 bits in time $2^{42}$

Total attack time $\approx 2^{43}<<2^{56}$ with $2^{42}$ random inp/out pairs.


Lesson:

A tiny bit of linearly in $S_5$ lead to a $2^{42}$ time attack.

So don’t design ciphers yourself.

Quantum attacks

另一个针对穷举攻击的解决方法是量子攻击。

对于一个一般的搜索问题:

generic search problem

一般计算机解决该类问题的最优时间是 $O(|X|)$ ,而量子计算机解决该类问题的最优时间是 $O(|X|^{1/2})$ 。

不过,量子计算机是否被实现还是一个疑问。

用量子计算机来穷举密钥空间,只需要 $O(|K|^{1/2})$ 的时间即可找到密钥。

AES

AES的发展过程如图:

The AES peocess

AES不是Feistel网络结构的密码,他是一个替换-置换类网络(Subs-Perm network):

Subs-Perm network

AES-128 schematic

AES-128的结构如下图:

AES-128

输入块是16 bytes的4*4矩阵,通过10轮运算得到最后的输出块。

每一轮都包括同样的操作(除了最后一轮不太一样),密钥加,字节替换(ByteSub),行移位(ShiftRow),列混淆(MixColumn)。其中每一轮的轮密钥是初始16 bytes的密钥通过密钥扩展得到的。

round function

轮密钥中的字节替换可以通过预计算查表的形式,也可以通过直接运算的形式。因此在实际应用中可以根据需求做出权衡。

tradeoff

AES in hardware

为了加快AES的运算速度,各公司有设计相关指令。

AES instructions in Intel Westmere:

  • aesenc, aesenclast: 执行AES中的一轮运算

    • 128-bit registers: xmm1=state, xmm2=round key
    • aesenc xmm1, xmm2 :执行一轮运算,并把计算结果放在xmm1中
  • aeskeygenassist: 执行AES的密钥扩展。

同样的硬件上,相对于OpenSSL的实现,可以快14倍。

同样,在 AMD Bulldozer上也有类似的指令设计。

Attacks

AES也存在比暴力搜索密钥空间更好的算法。

  • Best key recovery attack: four times better than ex. search [BKR’11]

  • Related key apack on AES-256: Given $2^{99}$ inp/out pairs from four related keys in AES-256 can recover keys in time ≈299[BK’09]

Block ciphers from PRGs

我们能否从PRG中构建PRF?

答案是:是的。

Let G: $K\rightarrow K^2$ be a secure PRG.

G: PRG

Define 1-bit PRF F: $K\times {0,1} \rightarrow K$ as
$$
F(k,x\in {0,1})=G(k)[x]
$$
根据定理,如果G是一个secure PRG,那么F就是一个secure PRF。

Thm: If G is a secure PRG then F is a secure PRF.

同样,我们可以通过这样的方式构建更大域的PRF。

对得到的结果再做一次G运算,得到的G1就是一个2-bit PRF:

2-bit PRF

Proof: G1 is a secure PRG

证明思路就是,因为G是安全的PRG,所以k通过G运算得到的结果与随机串不可区分,同样的,最后扩展出的在 $K^4$ 中的字符串与随机串是不可区分的。

G1 is a secure PRG

同样的,可以扩展出3-bit 的PRF,对于给定的比特输入,也是易于计算的:

3-bit PRF eval F(k, 101)

而扩展出更多bit时,就得到了GGM PRF。

GGM PRF就是通过上述的扩展方式得到 ${0,1}^n$ 域上的PRF:

GGM PRF

这种方式,PRF的安全性依赖于PRG的安全性。

但由于这样的方式运行效率较低,所以在实际应用中很少。

说到现在,我们好像还没有提到如何从PRG中构建块密码,因为块密码时PRPs。

如果记性比较好的读者应该还记得我们刚刚提到的Luby-Rackoff定理,将一个安全的PRF作为Feistel网络中的轮函数,3-round Feistel就可以构建一个安全的PRP,即安全的块密码。

Thm:

$f:K\times \{0,1\}^n\rightarrow \{0,1\}^n$ a secure PRF

then, 3-round Feistel $F: K^3\times{0,1}^{2n}\rightarrow {0,1}^{2n}$ a secure PRP.


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×