-
题目分类：math
-
题目分值：不安全的消息认证码（200）+ 不安全的 CRC（1）（250）+ 不安全的 CRC（2）（300）
为了避开 Eve 同学的干扰，某一天 Alice 悄悄找到了你，想让你帮忙传送一些加密消息给 Bob。当然，出于一些安全方面的考虑，Alice 想了几种方法在消息里加入了一些校验。
点击下载 源代码
除了网页终端，你也可以通过 nc 202.38.93.111 10041 来连接
这道题创意的来源是，我之前出过一个 poodle attack 的题目，然后应该放 HMAC 的地方我直接放了一个 sha256，被某同学（就是 114514 那道题的出题人）非预期了。
（然而，这道题也被非预期了。）
如果你对 block cipher 的这类攻击不熟悉，建议先去了解一下 AES 的 CBC 模式，还有 padding oracle 和 poodle attack 的原理，然后再继续阅读，否则你可能看不懂我在讲什么。
后来，我思考了一个问题，如果 HMAC 的 Hash 算法选择了（明显不安全的）CRC，那么题目还能解出来吗？
经过很久的思考之后，我和那位同学发现，是可以解的！但是需要替换大量的 block，还要解线性方程组，比较麻烦。
然后我把这道题发给了另一位同学（就是数理模拟器的出题人），让他试试看，结果他发现只需要替换第一个 block 就行了，因为 IV 是可以随便改的。为了让大家不能这么方便解题，我又出了第三问，也就是限制了 IV 不能改变。
我出题的时候万万没想到这道题会有时间侧信道的问题，长教训了。
后两问都可以用非预期的解法求解，原理就是发送大量数据的时候，CRC 的计算太慢了，于是可以通过测量时间来判断有没有计算 CRC。只有当 unpad 没有出错时，CRC 才会计算，所以这就是一个 padding oracle。
我没有把这个非预期的解法实现出来，所以蹲一个用这个方法的 write-up。
还是那句老话：不要自己实现密码学算法。
我需要写 10 道题的 write-up，太多了，所以这里就不画图了，简略说一下解题思路。如果有不理解的欢迎讨论，发 Issue、提 PR、私聊找我都可以。
加密的消息的内容排布是这样的：
IV text name text flag extra sha256 padding
当 padding 和 sha256 都正确的时候，程序会输出 Thanks。
对于 CBC 模式，我们把中间的一部分切出来（去掉开头和结尾的一些 block），第一个 block 当 IV，那么解密出来的明文也会是原始明文的一部分。
我们可以控制 name 和 extra，首先我们可以通过不断让输入的长度增加，找到密文恰好变长一个 block 的时刻，就能推算出 flag 的长度。
然后我们控制 name 是特定的长度，让 flag 的最后一个字符在一个 block 的起始处，把 extra 设置成 flag 最后一个字符猜测值的 sha256，再补上我们自己的 padding，让排布变成这个样子：
IV text name text fla|g our_sha256 our_padding | sha256 padding
然后按照我划线的地方把密文切开，我们就可以得到明文中那一部分对应的密文。
这时候，我们把切出来的密文发给服务器验证，如果我们对 flag 最后一个字符的猜测是正确的，就会得到 Thanks。
接下来，我们对所有可能的字符进行穷举，就可以找到 flag 的最后一个字符是什么。
我们可以让 name 变长，flag 向右移动，这样就可以每次猜测 flag 的一个字符，直到获得整个 flag。
HMAC 的结构并不重要，我们只需要知道，CRC128 相同的时候 HMAC 一定相同就可以了。
设想我们把密文中的一个 block i 替换掉密文中另一处的一个 block j 会发生什么？
根据 CBC 模式的计算规则，j 和 j+1 处明文的改变相当于是异或了一些东西：
C[i] = encrypt(C[i-1] ^ P[i])
C[j] = encrypt(C[j-1] ^ P[j])
C[j+1] = encrypt(C[j] ^ P[j+1])
替换之后
C[i] = encrypt(C[j-1] ^ P'[j])
C[j+1] = encrypt(C[i] ^ P'[j+1])
所以
P'[j] = P[i] ^ C[i-1] ^ C[j-1]
P'[j+1] = P[j+1] ^ C[i] ^ C[j]
在知道原本的明文中 P[i] 和 P[j] 的情况下，我们可以计算出明文的改变（即异或了哪个字符串）。
CRC 是对原文所有 bit 的一个线性运算，也就是说，在明文中改变一些特定的 bit（异或一个特定的字符串），CRC 变化的 bit 也是确定的。
我们可以假定 flag 的最后一个字符，然后把包含它的密文 block 替换掉另一个已知明文的 block，这时明文变化引起的 CRC 改变是可以预测的，即使我们并不知道明文中的一部分（flag）。
我们通过改变 IV 来影响明文第一个 block，把刚才对 CRC 的影响抵消掉，此时原来的 HMAC-CRC128 会保持不变。
如果我们对 flag 中字符的假设是正确的，服务器就可以成功验证我们的密文。
然后跟第一问一样，我们一直重复这个过程直到获得整个 flag 即可。
如果 IV 被限制成固定的，此时我们用密文来替换 block 对 CRC 产生的改变是可以预测的，但我们并不能按我们想要的方式对明文产生特定的改变（就像改变 IV 那样）。
这时，我们可以发送比较长的明文，然后对 >=128 种替换密文 block 的位置分别计算其对 CRC 的影响。对于每一种替换的位置，我们可以选择替换与不替换，这样相当于选择对 CRC 的影响要还是不要。我们希望总的影响互相抵消，此时问题转化为求解一个 GF(2) 上的线性方程组。我们解出来线性方程组的一个解，就意味着我们如此组合每一个替换与不替换，能够让所有替换对 CRC 产生的影响互相抵消，CRC 保持不变。
此时，如果我们对 flag 中字符的假设是正确的，服务器就可以成功验证我们的密文。
然后重复这个过程即可得到完整的 flag。
第三问解题代码 （需要使用 SageMath 运行）