Cryptohack-SYMMETRIC CIPHERS
Cryptohack-SYMMETRIC CIPHERS
SYMMETRIC CIPHERS
对称密钥密码是使用相同密钥加密和解密数据的算法。目标是使用短密钥安全有效地发送长消息。
最著名的对称密钥密码是2001年标准化的高级加密标准(AES)。它如此普遍,以至于现代处理器甚至包含了执行AES操作的特殊指令集。这里的第一系列挑战将指导您了解AES的内部工作原理,向您展示其单独的组件如何协同工作,使其成为一个安全的密码。到最后,您将构建自己的AES解密代码!
我们可以将对称密钥密码分为两类,分组密码和流密码。分组密码将明文分解为固定长度的块,并将每个块与密钥一起通过加密函数发送。同时,流密码通过将伪随机密钥流与数据进行异或运算,一次加密一个字节的明文。AES是一种分组密码,但可以使用CTR等操作模式转换为流密码。
分组密码仅指定如何加密和解密单个块,必须使用一种操作模式将密码应用于较长的消息。这就是现实世界的实现经常失败的地方,因为开发人员不理解使用特定模式的微妙含义。在剩下的挑战中,您将攻击各种模式的常见滥用。
How AES WORKS
Keyed Permutations
AES和所有好的分组密码一样,执行“密钥置换”。这意味着它将每个可能的输入块映射到一个唯一的输出块,并使用密钥确定要执行的置换。
“块”只是指固定数量的比特或字节,可以表示任何类型的数据。AES处理一个块并输出另一个块。我们将具体讨论AES的变体,它适用于128位(16字节)块和128位密钥,称为AES-128。
使用相同的密钥,可以反向执行置换,将输出块映射回原始输入块。重要的是,输入和输出块之间有一对一的对应关系,否则我们将无法依赖密文解密回我们开始时的明文。
题目:一对一对应关系的数学术语是什么?
bijection
Resisting Bruteforce
如果分组密码是安全的,那么攻击者就没有办法将AES的输出与比特的随机排列区分开来。此外,没有比简单地强制执行每个可能的密钥更好的方法来撤消排列。这就是为什么学者们认为,如果他们能找到一种比粗暴破解密钥所需步骤更少的攻击,即使这种攻击实际上是不可行的,那么从理论上讲,密码就是“被攻破的”。
强制执行128位密钥空间有多难?有人估计,如果你用整个比特币挖矿网络的力量来对抗AES-128密钥,破解密钥将需要100多倍于宇宙年龄的时间。
事实证明,对AES的攻击比bruteforce好,但只是稍微好一点——它将AES-128的安全级别降低到126.1位,并且已经8年多没有改进了。鉴于128位提供的巨大“安全裕度”,以及尽管进行了广泛的研究,但仍缺乏改进,因此它不被认为是对AES安全的可信风险。但是,是的,从非常狭义的意义上讲,它“打破”了AES。
最后,虽然量子计算机有可能通过Shor的算法完全破解RSA等流行的公钥密码系统,但据认为,通过Grover的算法,它们只能将对称密码系统的安全级别降低一半。这就是为什么人们建议使用AES-256的原因之一,尽管它的性能较差,因为它在量子未来仍然可以提供非常足够的128位安全性。
题目:针对AES的最佳单密钥攻击的名称是什么?
biclique
Structure of AES
为了实现在没有密钥的情况下无法反转的密钥置换,AES对输入应用了大量的ad-hoc混合操作。这与RSA等公钥密码系统形成鲜明对比,后者基于优雅的独立数学问题。AES的优雅程度要低得多,但速度非常快。
在较高层次上,AES-128从“密钥编排”开始,然后在一个状态矩阵上运行10轮。起始状态矩阵就是我们想要加密的明文块,表示为4x4字节矩阵。在10轮的过程中,状态矩阵被多次可逆变换反复修改。
每个转换步骤都有一个明确的目的,基于Claude Shannon在20世纪40年代建立的安全密码的理论性质。在接下来的挑战中,我们将更仔细地研究其中的每一个步骤。
以下是AES加密阶段的概述:
密钥扩展/密钥编排
从128位密钥中,导出11个单独的128位“轮密钥”:一个用于每个轮密钥添加步骤。
初始密钥添加
轮密钥添加 - 第一轮密钥的字节与状态矩阵的字节进行XOR运算。
循环 - 此阶段循环10次,包括9个主循环和一个“最后一轮”
- 字节代换 - 根据查找表(”S-box”),每个规定的字节被替换为不同的字节。
- 行移位 - 状态矩阵的最后三行被转置——在一列、两列或三列上移动。
- 列混淆 - 对状态矩阵的列执行矩阵乘法,将每列中的四个字节组合在一起。这在最后一轮中被跳过。
- 轮密钥添加 - 当前轮密钥的字节与状态矩阵的字节进行XOR运算。
题目:代码中包括一个bytes2matrix函数,用于将初始明文块转换为状态矩阵。编写一个matrix2bytes函数将该矩阵转换回字节,并将生成的明文作为flag提交。
源码:
1 | # matrix.py |
EXP:
1 | from Crypto.Util.number import * |
Round Keys
现在我们将跳过密钥扩展阶段的细节。关键在于,它接收我们的16字节密钥,并从我们的初始密钥中生成11个4x4矩阵,称为“轮密钥”。这些轮密钥允许AES从我们提供的单个密钥中获得额外的里程。
下一个初始密钥添加阶段有一个轮密钥添加步骤。轮密钥添加步骤很简单:它将当前状态矩阵与当前轮密钥进行异或。
轮密钥添加也是每一轮的最后一步。轮密钥添加使AES成为一种“密钥置换”,而不仅仅是一种置换。这是AES中唯一将密钥混合到状态矩阵中的部分,但对于决定发生的置换至关重要。
正如您在之前的挑战中所看到的,如果您知道密钥,XOR是一个很容易反转的操作,但如果您不知道密钥,则很难撤消。现在想象一下,尝试恢复用11个不同密钥XOR的明文,并且在每个XOR操作之间用一系列替换和转置密码严重混淆。AES就是这么做的!我们将在接下来的几次挑战中看到这种联合的有效性。
题目:完成add_round_key
函数,然后使用matrix2bytes
函数获取下一个flag。
EXP:
1 | from Crypto.Util.number import * |
Confusion through Substitution
每个AES轮的第一步是字节替换。这一步包含获取状态矩阵的每个字节,并将其替换为预设16x16查找表中的不同字节。查找表被称为“替换盒”或简称为“S盒,乍一看可能会令人困惑。让我们把它分解一下。
1945年,美国数学家Claude Shannon发表了一篇关于信息论的开创性论文。它将“混淆”确定为安全密码的基本属性。“混淆”意味着密文和密钥之间的关系应该尽可能复杂。只要有一个密文,就不应该有办法了解任何关于密钥的信息。
如果密码的混淆性较差,则可以将密文、密钥和明文之间的关系表示为线性函数。例如,在凯撒密码中,ciphertext = plaintext + key
。这是一个显而易见的关系,很容易逆转。更复杂的线性变换可以使用高斯消元等技术来解决。即使是低阶多项式,例如x^4 + 51x^3 + x
这样的方程,也可以使用代数方法有效地求解。然而,多项式的次数越高,通常就越难求解——它只能用越来越多的线性函数来近似。
S盒的主要目的是以一种不易被线性函数近似的方式转换输入。S盒的目标是高非线性,虽然AES的S盒并不完美,但它非常接近。S盒中的快速查找是对输入字节执行极其非线性函数的快捷方式。该函数涉及在伽罗瓦域 2**8中取模逆,然后应用仿射变换,该变换已被调整以最大程度地混淆。表达函数的最简单方法是通过以下高次多项式:
$$
f(x) = 05x^{fe} + 09x^{fd} + f9x^{fb} + 25x^{f7} + f4x^{ef} + 01x^{df} + b5x^{bf} + 9fx^{7f} + 63
$$
为了制作S盒,该函数已根据从0x00到0xff的所有输入值以及查找表中的输出进行了计算。
题目:实现sub_bytes
函数,通过逆S盒传递状态矩阵,然后将其转换为字节以获得flag。
EXP:
1 | from Crypto.Util.number import * |
Diffusion through Permutation
我们已经看到S盒替代是如何造成混淆的。Shannon描述的另一个关键性质是“扩散”。这与输入密码的每个部分如何传播到输出的每个部分有关。
替代本身会产生非线性,但它不会将其分布在整个状态矩阵上。如果没有扩散,同一位置的同一字节在每一轮都会得到相同的转换。这将允许密码分析员分别攻击状态矩阵中的每个字节位置。我们需要通过对状态矩阵进行置乱(以可逆的方式)来交替替换,以便对一个字节应用的替换会影响状态矩阵中的所有其他字节。然后,下一个S盒的每个输入都变成了多个字节的函数,这意味着随着每一轮的进行,系统的代数复杂性都会大大增加。
理想的扩散量会导致明文中一比特位的变化,从而导致密文中一半比特位的统计变化。这一理想的结果被称为雪崩效应。
行移位和列混淆步骤相结合可以实现这一点。它们协同工作,确保每个字节在两轮内影响状态矩阵中的其他每个字节。
行移位是AES中最简单的转换。它使状态矩阵的第一行保持不变。第二行环绕向左移动一列。第三行移动了两列,第四行移动了三列。维基百科说得很好:“这一步的重要性是避免独立加密列,在这种情况下,AES会退化为四个独立的分组密码。”
该图(和AES规范)显示了以列主符号表示的
行移位
操作。然而,下面的示例代码使用行主符号表示状态矩阵,因为它在Python中更自然。只要每次访问矩阵时使用相同的符号,最终结果就是相同的。由于访问模式和缓存行为,使用一种符号可以带来更好的性能。
列混淆更复杂。它在Rijndael的伽罗瓦域中在状态矩阵的列和预设矩阵之间执行矩阵乘法。因此,每列的每个字节都会影响结果列的所有字节。实施细节细致入微;这个页面和维基百科很好地覆盖了它们。
题目:我们提供了执行列混淆和正向行移位操作的代码。实现inv_shift_rows
后,获取状态矩阵,在其上运行inv_mix_columns
、inv_shift_rows
,然后转换为字节,您将得到您的flag。
EXP:
1 | from Crypto.Util.number import * |
Bringing It All Together
除了KeyExpansion阶段,我们还概述了AES的所有部分。我们已经展示了SubBytes如何提供混淆,ShiftRows和MixColumns如何提供扩散,以及这两个属性如何协同工作,在状态矩阵上反复循环非线性转换。最后,AddRoundKey将密钥种子放入这个替换置换网络中,使密码成为密钥置换。
解密涉及反向执行“AES结构”挑战中描述的步骤,应用反向操作。请注意,仍然需要先运行KeyExpansion,并且将以相反的顺序使用轮密钥。由于XOR具有自逆特性,所以AddRoundKey及其逆是相同的。
题目:我们提供了KeyExpansion的代码,以及由AES-128正确加密的密文。复制到目前为止您编写的所有代码块,并完成实现图中所示步骤的decrypt
函数。解密后的明文就是flag。
这些练习中使用的代码取自Bo Zhu的超简单Python AES实现,因此我们在这里复制了许可证。
EXP:
1 | from Crypto.Util.number import * |
SYMMETRIC STARTER
Modes of Operation Starter
hint
前面的一组挑战展示了AES如何对单个数据块执行密钥置换。在实际中,我们需要加密比单个块长得多的消息。操作模式描述了如何在较长的消息上使用类似AES的密码。
如果使用不当,所有模式都有严重的弱点。这个挑战将带您进入网站的不同部分,在那里您可以与API交互并利用这些弱点。熟悉界面,并用它来拿下你的下一个flag!
SOURCE
1 | from Crypto.Cipher import AES |
WriteUp
由starter页点击ENCRYPT_FLAG()的SUBMIT按钮,在OUTPUT中得到json数据:
1 | {"ciphertext":"0bf3da3fce245ce6bd6c9a9abaaef49945bbf20ec314ca38b341707c36bd00b9"} |
将OUTPUT中的ciphertext扔到DECRYPT(CIPHERTEXT)中,点击SUBMIT按钮,在json中得到解密后的hex值:
1 | {"plaintext":"63727970746f7b626c30636b5f633170683372355f3472335f663435375f217d"} |
再放入HEX ENCODER/DECODER中,HEX转为TEXT得到flag。
Passwords as Keys
hint
对称密钥算法中的密钥必须是随机字节,而不是密码或其他可预测的数据。随机字节应使用加密安全的伪随机数生成器(CSPRNG)生成。如果密钥在任何方面都是可预测的,那么密码的安全级别就会降低,并且访问密文的攻击者可能会对其进行解密。
仅仅因为密钥看起来像是由随机字节组成的,并不意味着它一定是。在这种情况下,密钥是使用哈希函数从简单密码中导出的,这使得密文是可破解的。
对于此挑战,您可以将HTTP请求编写到端点,或者离线攻击密文。祝你好运!
SOURCE
1 | from Crypto.Cipher import AES |
WriteUp
同上题一样,通过ENCRYPT_FLAG()获得ciphertext的json数据:
1 | {"ciphertext":"c92b7734070205bdf6c0087a751466ec13ae15e6f1bcdd3f3a535ec0f4bbae66"} |
通过SOURCE提示得到密码本,本地调用网站函数来解密。
EXP
1 | from Crypto.Cipher import AES |
BLOCK CIPHERS 1
ECB CBC WTF
hint
在这里,您可以在CBC中加密,但只能在ECB中解密。这不应该是一个弱点,因为它们是不同的模式…对吗?
SOURCE
1 | from Crypto.Cipher import AES |
WriteUp
同前几题,得到密文:
1 | {"ciphertext":"f14003406962ed9760ac5af1a8423677f05c7b58f9f99d8301ab42a138018c419d0af6c6c0a6a526db3eb816e943b1c7"} |
EXP
1 | from Crypto.Util.number import * |
ECB ORACLE
hint
ECB是最简单的模式,每个明文块都完全独立加密。在这种情况下,您的输入将被添加到秘密flag之前并加密,仅此而已。我们甚至不提供解密功能。也许当你有一个“ECB的预言者”时,你就不需要填充预言了?
SOURCE
1 | from Crypto.Cipher import AES |
WriteUp
本题为一道典型的ECB加密解密问题,首先,我们既不知道明文也不知道密文,由题目所给的加密算法,先尝试得到加密块大小和flag长度(?是要求的明文,F是ECB模式填充的字节,p是已求出的明文)。
先用一个字符”a”去encrypt返回32个字节的数据(64位16进制),再依次用”aa”,”aaa”,…去encrypt,代码如下:
1 | import requests |
可见6个”a”的时候返回32个字节的数据,7个”a”的时候返回48个字节的数据,22个”a”的时候返回64个字节的数据,23个”a”的时候返回48个字节的数据。所以块大小就是16字节(22-6),明文(flag)大小就是26个字节(32-6)。接着暴力破解求明文。
aaaaaaaaaaaaaaa? ??????????????? ?????????FFFFFFF
aaaaaaaaaaaaaa?? ??????????????? ????????FFFFFFFF
aaaaaaaaaaaaa??? ??????????????? ???????FFFFFFFFF
aaaaaaaaaaaa???? ??????????????? ?????FFFFFFFFFFF
求第一位:
15个”a”时返回的前16个字节只有最后一个字节未知,可以暴力遍历出第一个字节,也就是用15*”a”+flag第一个字节的加密密文与暴力遍历的加密密文去匹配。2-15位同理。
16-26位:
与上述方法同理。
aaaaaaaaaaaaaaaa ppppppppppppppp? ??????????FFFFFF
aaaaaaaaaaaaaaap ppppppppppppppp? ?????????FFFFFFF
aaaaaaaaaaaaaapp ppppppppppppppp? ????????FFFFFFFF
aaaaaaaaaaaaappp ppppppppppppppp? ???????FFFFFFFFF
aaaaaaaaaaaapppp ppppppppppppppp? ??????FFFFFFFFFF
EXP
1 | import requests |
Flipping Cookie
hint
你可以在我的网站上得到一个cookie,但它不会帮助你获得flag…我想。
SOURCE
1 | from Crypto.Cipher import AES |
WriteUp
这是一道典型的CBC字节反转攻击。
题目给出了两个函数check_admin(cookie, iv)
和get_cookie()
。
第一个函数将输入的cookie
和IV
进行AES-BCB模式解密
,当解密得到的字符串满足以;
为分割后存在admin=True
的字符串的时候就会把flag输出出来。
1 | if b"admin=True" in unpadded.split(b";"): |
第二个函数会将 cookie
这个字符串和一个IV
经过AES-BCB模式加密
后的结果同加密所用到的IV
输出出来。
1 | expires_at = (datetime.today() + timedelta(days=1)).strftime("%s") |
我们可以通过构造新的IV
同原来的密文进行解密从而更改解密后的内容最终拿到flag。
$$
IV⊕Old=T\T⊕IV=Old\T⊕(IV⊕New⊕Old)=Old⊕Old⊕New=New\IV_new=IV⊕New⊕Old\
$$
由上面的推导式
$$
IV_new=IV⊕New⊕Old
$$
所以可得EXP。
EXP
1 | import requests |
附
本题需要修改的内容刚好在第一组里,如果修改内容在其他组,如第二组,则需要构造新的第一组的密文,构造规则与推导式相同:
$$
新的密文=前一组的密文⊕原来的明文⊕新的明文
$$
只不过可能会需要同时构造新的IV
,使新的密文同新的IV
解密结果同以前相同。
Lazy CBC
hint
我只是一个懒惰的开发人员,希望我的CBC加密能够正常工作。这些关于初始化向量的讨论是什么?听起来并不重要。
SOURCE
1 | from Crypto.Cipher import AES |
WriteUp
CBC的生成思路如下:
$$
m_1=decrypt(c_1)\oplus{IV}\m_2=decrypt(c_2)\oplus{m_1}\m_3=decrypt(c_3)\oplus{m_2}
$$
本题给出了密文的生成代码,密文的解密代码以及flag的获得代码,且密文明文都可以由自己设置,我们不妨设如下特殊情况
$$
c_2=0,c_1=c_3\m_1\oplus{m_3}=decrypt(c_1)\oplus{IV}\oplus{decrypt(c_1)}\oplus{m_2}=IV
$$
即可得到IV
,在本题中,IV
即为所求KEY
。
EXP
1 | import requests |
Triple DES
hint
数据加密标准(DES)是AES的前身,目前仍广泛应用于支付卡行业等一些发展缓慢的领域。这一挑战展示了DES的一个奇怪弱点,而安全分组密码不应该有这个弱点。
SOURCE
1 | from Crypto.Cipher import DES3 |
WriteUp
DES有几个特定的弱密钥和半弱密钥,会使DES的加密模式和解密模式完全相同,本题给出了encrypt_flag(key)
和encrypt(key, plaintext)
两个函数,key使用弱密钥,得到flag的密文,然后用key和flag的密文再一次加密,由于使用了弱密钥,加密与解密一致,对flag的密文用同样的key再加密一次即为解密,得到明文。
EXP
1 | import requests |