# 中间人

## 花絮

这道题创意的来源是，我之前出过一个 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。

[第一问解题代码](src/mitm_exp1.py)

### 不安全的 CRC（1）

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 即可。

[第二问解题代码](src/mitm_exp2.py)

如果 IV 被限制成固定的，此时我们用密文来替换 block 对 CRC 产生的改变是可以预测的，但我们并不能按我们想要的方式对明文产生特定的改变（就像改变 IV 那样）。

这时，我们可以发送比较长的明文，然后对 >=128 种替换密文 block 的位置分别计算其对 CRC 的影响。对于每一种替换的位置，我们可以选择替换与不替换，这样相当于选择对 CRC 的影响要还是不要。我们希望总的影响互相抵消，此时问题转化为求解一个 GF(2) 上的线性方程组。我们解出来线性方程组的一个解，就意味着我们如此组合每一个替换与不替换，能够让所有替换对 CRC 产生的影响互相抵消，CRC 保持不变。

此时，如果我们对 flag 中字符的假设是正确的，服务器就可以成功验证我们的密文。

然后重复这个过程即可得到完整的 flag。

[第三问解题代码](src/mitm_exp3.py) （需要使用 SageMath 运行）
