流密码立方攻击(基于图算法)

流密码常见概念

流密码(Stream cipher)是对称加密的一种。流密码将明文(Plaintex)看成二进制数据流，通过初始密钥生成加密密钥流ziz_izi​与明文流pip_ipi​做异或操作获得密文流cic_ici​，即ci=pi⊕zic_i=p_i\oplus{z_i}ci​=pi​⊕zi​。由于异或操作是可逆的，则解密操作可以由相同的ziz_izi​获得，即pi=ci⊕zip_i=c_i\oplus{z_i}pi​=ci​⊕zi​。

反馈位移寄存器

位移寄存器是利用有限长度的密钥生成任意长度的密钥流zzz的重要工具，其工作原理是每生成一位加密密钥比特ziz_izi​，都利用寄存器自身的某些比特对寄存器的第1位进行更新，其他比特位则右移。下图展示了一个反馈位移寄存器的工作原理，寄存器的第1到4位直接右移，空出来的第1位由寄存器上一步状态的第4,5位做乘法运算并与第1位做异或运算得到。

如果寄存器的更新操作中涉及非线性运算(上图中的乘法操作就是非线性的)，则称为非线性反馈位移寄存器(Non-Linear feedback shift register，NFSR)，否则称为线性反馈位移寄存器(Linear feedback shift register，LFSR)。

轮函数

轮函数实际上是反馈位移寄存器更新操作的数学表达式，如上图展示的寄存器的表达式为：s1r=s1r−1⊕s4r−1s5r−1s_1^r=s_1^{r-1}\oplus{s_4^{r-1}s_5^{r-1}}s1r​=s1r−1​⊕s4r−1​s5r−1​，其中上标rrr表示轮数，下标iii表示寄存器的第iii位。通常，为了使流密码足够复杂，在输出第1位加密密钥比特之前要进行RRR次轮函数迭代。

Ancry

现实使用的流密码为了密码强度都设计得非常复杂(密钥多达几十甚至几百位，初始轮数RRR也非常大)，因此几乎只能从数学上对密码进行立方攻击，而实际上的破解过程需要交由计算机，这对初学者学习立方攻击造成了一定的困扰。为此本文设计了一个名为Ancry的密码算法，该算法只包含5个密钥比特，初始轮数R=10R=10R=10，每一个工作步骤都十分简洁明了。Ancry流密码的工作流程如下图所示。

Ancry的第1个寄存器的初始状态存放5bit的密钥，第2个寄存器的初始状态存放5bit的公开变量，这些变量是公开可控的。令s=(x,v)s=(x,v)s=(x,v)，则Ancry的轮函数的数学表达式为：s1r=s8r−1+s7r−1s10r−1,(1)s_1^r=s_8^{r-1}+s_7^{r-1}s_{10}^{r-1},(1)s1r​=s8r−1​+s7r−1​s10r−1​,(1)s6r=s2r−1+s4r−1s5r−1,(2)s_6^r=s_2^{r-1}+s_4^{r-1}s_5^{r-1},(2)s6r​=s2r−1​+s4r−1​s5r−1​,(2)zi=s3i+9+s9i+9z_i=s_3^{i+9}+s_9^{i+9}zi​=s3i+9​+s9i+9​
由上述第3个表达式可以得出，输出第一位加密密钥比特之前进行了10次初始化迭代，即R=10R=10R=10。以下为Ancry的Python实现代码。

1. # Author: AngieJC
2. # Date: 2022/01/17
3. # Mail: htk90uggk@outlook.com
5. import sys
7. def Ancry(vec_x, vec_v, plaintext): # 流密码，vec_x为密钥x，vec_v为公开参数v，plaintext为明文
8. z = [] # z为输出的密钥比特
10. # 初始轮数r=10
11. R = 10
12. x = vec_x.copy()
13. v = vec_v.copy()
14. for i in range(R):
15. for j in range(len(vec_x) - 1):
16. x[j + 1] = vec_x[j]
17. x[0] = vec_v[2] ^ (vec_v[1] * vec_v[4])
18. for j in range(len(vec_v) - 1):
19. v[j + 1] = vec_v[j]
20. v[0] = vec_x[1] ^ (vec_x[3] * vec_x[4])
21. vec_x = x.copy()
22. vec_v = v.copy()
24. # 计算z
25. cyphertext = []
26. for i in range(len(plaintext)):
27. # 添加一位密钥比特
28. z.append(vec_x[2] ^ vec_v[3])
29. cyphertext.append(z[-1] ^ plaintext[i])
31. # 更新x与v
32. for j in range(len(vec_x) - 1):
33. x[j + 1] = vec_x[j]
34. x[0] = vec_v[2] ^ (vec_v[1] * vec_v[4])
35. for j in range(len(vec_v) - 1):
36. v[j + 1] = vec_v[j]
37. v[0] = vec_x[1] ^ (vec_x[3] * vec_x[4])
38. vec_x = x.copy()
39. vec_v = v.copy()
41. return cyphertext
43. if __name__ == "__main__":
44. x = input("密钥：")
45. if(len(x) != 5):
46. print("密钥长度应当为5！")
47. sys.exit()
48. vec_x = []
49. for i in range(len(x)):
50. vec_x.append(int(x[i]))
51. # vec_x = [int(x[0]), int(x[1])]
52. v = input("公开参数：")
53. if (len(v) != 5):
54. print("公开参数长度应当为5！")
55. sys.exit()
56. vec_v = []
57. for i in range(len(v)):
58. vec_v.append(int(v[i]))
59. # vec_v = [int(v[0]), int(v[1])]
60. p = input("明文：")
62. plaintext = []
63. for i in range(len(p)):
64. plaintext.append(int(p[i]))
66. cyphertext = Ancry(vec_x, vec_v, plaintext)
67. print("明文：", plaintext)
68. print("密文：", cyphertext)

复制代码

Ancry简要分析

在介绍立方攻击之前先对Ancry进行一些简单的分析，以方便理解立方攻击的工作原理。
由于流密码的加密模式为ci=pi⊕zic_i=p_i\oplus{z_i}ci​=pi​⊕zi​，因此攻击者知道明文ppp和明文ccc就相当于知道密钥流zzz。
Ancry第1位加密密钥比特zzz(在不引起歧义的情况下，以下使用zzz代替z1z_1z1​)的表达式为：z=s310+s910z=s_3^{10}+s_9^{10}z=s310​+s910​根据反馈位移寄存器的特点我们知道，一个比特生成并保存到寄存器的第一个位置后，一直在做右移操作，直到右移到寄存器的最右边被丢弃，而值并不发生任何变化，因此有s310=s18s_3^{10}=s_1^8s310​=s18​，s910=s67s_9^{10}=s_6^7s910​=s67​。再根据等式(1)和等式(2)，有z=s87+s77s107+s26+s46s56z=s_8^7+s_7^7s_{10}^7+s_2^6+s_4^6s_5^6z=s87​+s77​s107​+s26​+s46​s56​。对zzz一直进行递归分解，最终可以得到：z=v1+x5v3+x1v3+x1v2v5+x5v3+x5v2v5+x2x3x5+x4v2v3+x4v2v5+x2x3x4v2+v2v3+x2x3v2v3+v2v5+x2x3v2v5+v1v3v4+x2x3v1v3v4+v1v2v4v5+x2x3v1v2v4v5+x4+x3v1+v1v2+v1v4+x5v2v3+x5v1v3v4z=v_1+x_5v_3+x_1v_3+x_1v_2v_5+x_5v_3+x_5v_2v_5+x_2x_3x_5+x_4v_2v_3+x_4v_2v_5\\+x_2x_3x_4v_2+v_2v_3+x_2x_3v_2v_3+v_2v_5+x_2x_3v_2v_5+v_1v_3v_4+x_2x_3v_1v_3v_4\\+v_1v_2v_4v_5+x_2x_3v_1v_2v_4v_5+x_4+x_3v_1+v_1v_2+v_1v_4+x_5v_2v_3+x_5v_1v_3v_4z=v1​+x5​v3​+x1​v3​+x1​v2​v5​+x5​v3​+x5​v2​v5​+x2​x3​x5​+x4​v2​v3​+x4​v2​v5​+x2​x3​x4​v2​+v2​v3​+x2​x3​v2​v3​+v2​v5​+x2​x3​v2​v5​+v1​v3​v4​+x2​x3​v1​v3​v4​+v1​v2​v4​v5​+x2​x3​v1​v2​v4​v5​+x4​+x3​v1​+v1​v2​+v1​v4​+x5​v2​v3​+x5​v1​v3​v4​这个表达式称为zzz的代数范式(Algebraic Normal Form, ANF)。以上表达式是z1z_1z1​的代数表达式，理论上来说，如果我们能够推出所有ziz_izi​的代数表达式，那么在实际加密过程中，也可以完全抛弃反馈位移寄存器而直接使用代数表达式计算密钥流。

读者也可以自己推出zzz的代数表达式
注意：由于二进制中有以下特性
性质1：1n=1,0n=01^n=1,0^n=01n=1,0n=0
性质2：1+1=0,0+0=01+1=0,0+0=01+1=0,0+0=0

因此zzz的代数表达式中xnx^nxn可以简化成xxx，x+xx+xx+x可以直接约去

立方攻击

立方攻击由Dinur和Shamir在2009年的欧密会上提出，其中的Shamir就是设计了RSA算法的三位作者中的S。
立方攻击只关心输出的第1位加密密钥比特，其中心思想是：选取一个关于公开变量vvv的立方索引III，把zzz的代数表达式分解成：z=p(x,v)tI+q(x,v)z=p(x,v)t_I+q(x,v)z=p(x,v)tI​+q(x,v)其中tIt_ItI​为被III索引的公开变量的连乘，即tI=∏i∈Ivit_I=\prod_{i\in{I}}v_itI​=∏i∈I​vi​。说直白一点就是对zzz的代数表达式提取公因子tIt_ItI​，p(x,v)p(x,v)p(x,v)为提取tIt_ItI​之后的多项式，q(x,v)q(x,v)q(x,v)则为无法提取tIt_ItI​的多项式。

例子1：
x=(x1,x2,x3),v=(v1,v2,v3)x=(x_1,x_2,x_3),v=(v_1,v_2,v_3)x=(x1​,x2​,x3​),v=(v1​,v2​,v3​)
z=x1v1v3+x1v2+x2v1v2+x2x3v1v3+v1v3z=x_1v_1v_3+x_1v_2+x_2v_1v_2+x_2x_3v_1v_3+v_1v_3z=x1​v1​v3​+x1​v2​+x2​v1​v2​+x2​x3​v1​v3​+v1​v3​
令I={1,3}I=\{1,3\}I={1,3}
则z=(x1+x2x3+1)v1v3+x1v1+x2v1v2z=(x_1+x_2x_3+1)v_1v_3+x_1v_1+x_2v_1v_2z=(x1​+x2​x3​+1)v1​v3​+x1​v1​+x2​v1​v2​
其中p(x,v)=x1+x2x3+1,tI=v1v3,q(x,v)=x1v1+x2v1v2p(x,v)=x_1+x_2x_3+1,t_I=v_1v_3,q(x,v)=x_1v_1+x_2v_1v_2p(x,v)=x1​+x2​x3​+1,tI​=v1​v3​,q(x,v)=x1​v1​+x2​v1​v2​

将zzz分解成p(x,v)tI+q(x,v)p(x,v)t_I+q(x,v)p(x,v)tI​+q(x,v)后我们可以得到一个非常有趣的结论，即∑v∈Cz=p(x,v),(3)\sum_{v\in{C}}z=p(x,v),(3)v∈C∑​z=p(x,v),(3)其中CCC是III所代表的立方，即vi∈Iv_i\in{I}vi​∈I取遍所有的2∣I∣2^{|I|}2∣I∣个0-1组合，∣I∣|I|∣I∣代表集合III中元素的个数。

例子1续：
I={1,3}I=\{1,3\}I={1,3}
则C={(0,0,0)(0,0,1)(1,0,0)(1,0,1)C= \begin{cases} (\textcolor{red}0,0,\textcolor{red}0)\\ (\textcolor{red}0,0,\textcolor{red}1)\\ (\textcolor{red}1,0,\textcolor{red}0)\\ (\textcolor{red}1,0,\textcolor{red}1) \end{cases} C=⎩⎪⎪⎪⎨⎪⎪⎪⎧​(0,0,0)(0,0,1)(1,0,0)(1,0,1)​
由于v2v_2v2​并不是立方元素，可以是任意值或者直接置0

证明：
∑v∈Cz=∑v∈Cp(x,v)tI+∑v∈Cq(x,v)\sum_{v\in{C}}z=\sum_{v\in{C}}p(x,v)t_I+\sum_{v\in{C}}q(x,v)v∈C∑​z=v∈C∑​p(x,v)tI​+v∈C∑​q(x,v)
p(x,v)tI={p(x,v)所有的vi∈I均等于1(C中的最后一种情况)0C中其他三种情况p(x,v)t_I= \begin{cases} p(x,v)&&所有的v_i\in{I}均等于1(C中的最后一种情况)\\ 0&&C中其他三种情况 \end{cases} p(x,v)tI​={p(x,v)0​​所有的vi​∈I均等于1(C中的最后一种情况)C中其他三种情况​
则∑v∈Cp(x,v)tI=p(x,v)\sum_{v\in{C}}p(x,v)t_I=p(x,v)∑v∈C​p(x,v)tI​=p(x,v)

又由于v2=0v_2=0v2​=0，则q(x,v)=x1v1+x2v1v2=x1v1q(x,v)=x_1v_1+x_2v_1v_2=x_1v_1q(x,v)=x1​v1​+x2​v1​v2​=x1​v1​，∑v∈Cq(x,v)=0x1+0x1+1x1+1x1=x1+x1\sum_{v\in{C}}q(x,v)=0x_1+0x_1+1x_1+1x_1=x_1+x_1∑v∈C​q(x,v)=0x1​+0x1​+1x1​+1x1​=x1​+x1​，由性质2可知，∑v∈Cq(x,v)=0\sum_{v\in{C}}q(x,v)=0∑v∈C​q(x,v)=0
事实上，由于CCC中共有2∣I∣2^{|I|}2∣I∣个元素，即偶数个元素，根据性质2，∑v∈Cq(x,v)\sum_{v\in{C}}q(x,v)∑v∈C​q(x,v)必然为0

综上，∑v∈Cz=p(x,v)\sum_{v\in{C}}z=p(x,v)∑v∈C​z=p(x,v)得证

现在我们我们把目光再次聚焦到Ancry，zzz的表达式已经知道，根据立方III选取的不同，可以将zzz分解成一下几种形式(由于∑v∈Cq(x,v)=0\sum_{v\in{C}}q(x,v)=0∑v∈C​q(x,v)=0，我们并不关心其具体表达式，因此在下列例子中都没有显式给出q(x,v)q(x,v)q(x,v)的表达式)：

1. I={1,2,3,4,5},无法分解I=\{1,2,3,4,5\},无法分解I={1,2,3,4,5},无法分解
2. I={1,2,4,5},p(x,v)=x2x3+1I=\{1,2,4,5\},p(x,v)=x_2x_3+1I={1,2,4,5},p(x,v)=x2​x3​+1
3. I={1,3,4},p(x,v)=x2x3+x5+1I=\{1,3,4\},p(x,v)=x_2x_3+x_5+1I={1,3,4},p(x,v)=x2​x3​+x5​+1
4. I={2,3},p(x,v)=x2x3+x4+x5+1I=\{2,3\},p(x,v)=x_2x_3+x_4+x_5+1I={2,3},p(x,v)=x2​x3​+x4​+x5​+1
5. I={2,5},p(x,v)=x1+x2x3+x4+x5+1I=\{2,5\},p(x,v)=x_1+x_2x_3+x_4+x_5+1I={2,5},p(x,v)=x1​+x2​x3​+x4​+x5​+1
6. I只有1个元素分解意义不大I只有1个元素分解意义不大I只有1个元素分解意义不大

Ancry攻击实例

基本信息：
x=(1,0,0,1,0)x=(1,0,0,1,0)x=(1,0,0,1,0)
I={2,5}I=\{2,5\}I={2,5}
p(x,v)=x1+x2x3+x4+x5+1p(x,v)=x_1+x_2x_3+x_4+x_5+1p(x,v)=x1​+x2​x3​+x4​+x5​+1

根据实际加密结果，有:
z={1,v=(0,0,0,0,0)1,v=(0,0,0,0,1)1,v=(0,1,0,0,0)0,v=(0,1,0,0,1)z= \begin{cases} 1,v=(0,\textcolor{red}0,0,0,\textcolor{red}0)\\ 1,v=(0,\textcolor{red}0,0,0,\textcolor{red}1)\\ 1,v=(0,\textcolor{red}1,0,0,\textcolor{red}0)\\ 0,v=(0,\textcolor{red}1,0,0,\textcolor{red}1) \end{cases} z=⎩⎪⎪⎪⎨⎪⎪⎪⎧​1,v=(0,0,0,0,0)1,v=(0,0,0,0,1)1,v=(0,1,0,0,0)0,v=(0,1,0,0,1)​
则∑v∈Cz=p(x,v)=x1+x2x3+x4+x5+1=1+1+1+0=1\sum_{v\in{C}}z=p(x,v)=x_1+x_2x_3+x_4+x_5+1=1+1+1+0=1∑v∈C​z=p(x,v)=x1​+x2​x3​+x4​+x5​+1=1+1+1+0=1，即x1+x2x3+x4+x5=0,(4)\textcolor{red}{x_1+x_2x_3+x_4+x_5=0},(4)x1​+x2​x3​+x4​+x5​=0,(4)
在没有等式(4)之前，想要通过穷举的方式破解Ancry需要遍历25=322^5=3225=32种密钥可能的取值。而符合等式(4)的密钥取值为x={(0,0,0,0,0)(0,0,0,1,1)(0,0,1,0,0)(0,0,1,1,1)(0,1,0,0,0)(0,1,0,1,1)(0,1,1,0,1)(0,1,1,1,0)(1,0,0,0,1)(1,0,0,1,0),正确密钥(1,0,1,0,1)(1,0,1,1,0)(1,1,0,0,1)(1,1,0,1,0)(1,1,1,0,0)(1,1,1,1,1)x= \begin{cases} (0, 0, 0, 0, 0)\\ (0, 0, 0, 1, 1)\\ (0, 0, 1, 0, 0)\\ (0, 0, 1, 1, 1)\\ (0, 1, 0, 0, 0)\\ (0, 1, 0, 1, 1)\\ (0, 1, 1, 0, 1)\\ (0, 1, 1, 1, 0)\\ (1, 0, 0, 0, 1)\\ \textcolor{red}{(1, 0, 0, 1, 0)},正确密钥\\ (1, 0, 1, 0, 1)\\ (1, 0, 1, 1, 0)\\ (1, 1, 0, 0, 1)\\ (1, 1, 0, 1, 0)\\ (1, 1, 1, 0, 0)\\ (1, 1, 1, 1, 1) \end{cases} x=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​(0,0,0,0,0)(0,0,0,1,1)(0,0,1,0,0)(0,0,1,1,1)(0,1,0,0,0)(0,1,0,1,1)(0,1,1,0,1)(0,1,1,1,0)(1,0,0,0,1)(1,0,0,1,0),正确密钥(1,0,1,0,1)(1,0,1,1,0)(1,1,0,0,1)(1,1,0,1,0)(1,1,1,0,0)(1,1,1,1,1)​共16种情况，再加上遍历立方CCC的4种情况，一共需要20个步骤即可破解Ancry，比穷举破解Ancry的32种情况要优秀不少。

参考文献

[1] Delaune, S., Derbez, P., Gontier, A., & Prud’homme, C. (2021). A Simpler Model for Recovering Superpoly onTrivium. Cryptology ePrint Archive.