[Crypto] Halffeed - xfiles

xp0int Posted on Feb 11 2020

English: https://github.com/xf1les/ctf-writeups/tree/master/Codegate_2020/Halffeed

```
Codegate CTF 2020 Preliminary

Challenge : Halffeed

Description :
nc 110.10.147.44 7777

DOWNLOAD :
http://ctf.codegate.org/099ef54feeff0c4e7c2e4c7dfd7deb6e/9a7f846af14e09f6b32cff3a648b80f5

point : 670 (43 team solved)
```

mixFeed 算法 Nonce 误用攻击

## 流程

伪造`AAAAAAAAAAAAAAAA;cat flag;AAAAAA`的密文和认证码：

1. 泄漏 $T_0$、$T_1$、$T_1'$：依次加密`'\x00' * 16 `、`'A' * 16 + '\x00' * 16`、`'B' * 16 + '\x00' * 16`，取密文最后16字节。
2. 计算中间 Tag $t_2$：`t2 , _ = feed_plus(T1, ';cat flag;AAAAAA')`
3. 构造*forge_tag*： 加密`"B" * 16 + xor(T1_[:8], t2[:8]) + t2[8:]`，取认证码。
2. 构造*forge_ciphertext*：`forge_ciphertext = xor('AAAAAAAAAAAAAAAA;cat flag;AAAAAA', T0 + T1)`
3. 提交*nonce*、*forge_ciphertext*和*forge_tag*，get flag。

所有的加密使用同一个的*nonce*。

## 说明

**mixFeed**是一种基于 Nonce 和 AES 的认证加密算法。加密时，生成密文和对应的认证码，通过认证码可以检验密文的完整性。

程序实现了一个化简版的 mixFeed 加密算法，并允许加密任何不包含`cat flag`的字符串。获取 flag，需要提交包含`cat flag`的合法密文和认证码。

Nonce 是一个加密参数。在整个加密过程中，同一个 Nonce  值应当只能使用一次，否则产生**Nonce 误用（Nonce Misuse）问题**。在本程序中，初始 Nonce 是一个固定值 0，故能够使用相同的 Nonce 加密不同的明文。

当明文长度是16的倍数时，加密代码化简为如下：
```
def feed_plus(self, tag, data):
    enc_data = bytes(b1 ^ b2 for b1, b2 in zip(tag, data))
    tag = enc_data[:8] + data[8:]

return tag, enc_data

def encrypt(self, nonce, plaintext):
    Kn, _ = aes_encrypt(self.key, nonce)
    T, K = aes_encrypt(Kn, nonce) # T0, K0

ciphertext = b''
    for i in range(0, len(plaintext), 16):
        T, block = self.feed_plus(T, plaintext[i:i+16]) # tn
        ciphertext += block
        T, K = aes_encrypt(K, T) # Tn, Kn

T, _ = aes_encrypt(K, T)

return ciphertext, T
```

加密流程：
1. 主密钥和*nonce*参数经过 AES 加密，生成$T_0$、$K_0$。
2. 明文块$P_0$与$T_0$异或，生成密文块$C_0$。
3. 密文块$C_0$前8字节和明文块$P_0$后8字节组成中间 Tag $t_1$。
4. $K_0$ AES 加密$t_1$、$K_0$，生成$T_1$、$K_1$。
5. 重复2-4步，遍历所有的明文块。
6. $K_n$AES加密$T_n$，生成$T$，返回所有的密文块和$T$。

***

主要思路是伪造包含`cat flag`明文的密文和认证码。

**密文**：将某个明文块$P_n$设置为全零，得到密文块$C_n$即为$T_n$。得到$T_n$后，就能计算任意明文块$P_n$对应的密文$C_n$。

**认证码**：从加密流程中可知，$T_n$是$t_n$经AES加密后的密文，而$t_n$是由密文块$C_{n-1}$前8字节和明文块$P_{n-1}$后8字节组成。通过构造明文$P_{n-1}$、控制$t_n$，我们可以输出任意明文对应的认证码。假设我们有两个明文块$P_0$、$P_1$，其中$P_1$包含`cat flag`。已知$T_1$，可以当计算下一个明文块为$P_1$时对应的$t_2$。取另一个不同的明文块$P_0'$。已知$T_1'$和$t_2$，就能构造一个不包含`cat flag`的明文块$P_1'$，使$t_2'$ == $t_2$。加密$P_0'$$P_1'$，就能得到与$P_0$$P_1$相同的认证码。

## 脚本

```
#!/usr/bin/env python2
from pwn import *

context(log_level="debug")

def xor(j, k):
    return ''.join([chr(b1 ^ b2) for b1, b2 in zip(map(ord, j), map(ord, k))])

def feed_plus(tag, data):
    enc_data = xor(tag, data)
    tag = enc_data[:8] + data[8:]

return tag, enc_data

def enc(P):
    p = remote("110.10.147.44", 7777)
    p.sendlineafter("> ", '1')
    p.sendlineafter("plaintext =", P.encode('hex'))
    p.recvuntil("ciphertext = ")
    c = p.recvline().strip().decode('hex')
    p.recvuntil("tag = ")
    t = p.recvline().strip().decode('hex')
    p.close()

return c, t

def getflag(n, c, t):
    n = p64(n, endian="big").rjust(16, '\x00')

p = remote("110.10.147.44", 7777)
    p.sendlineafter("> ", '3')
    p.sendlineafter("nonce =", n.encode('hex'))
    p.sendlineafter("ciphertext =", c.encode('hex'))
    p.sendlineafter("tag =", t.encode('hex'))

p.interactive()

def leak_tag(p):
    c, _ = enc(p + '\x00' * 16)
    return c[-16:]

plaintext = "A" * 16 + ';cat flag;AAAAAA'

T0 = leak_tag('')
T1 = leak_tag("A" * 16)
T1_ = leak_tag("B" * 16)

forge_ciphertext = xor(plaintext, T0 + T1)

t2, _ = feed_plus(T1, ';cat flag;AAAAAA')
P = "B" * 16 + xor(T1_[:8], t2[:8]) + t2[8:]
_, forge_tag = enc(P)

# CODEGATE2020{F33D1NG_0N1Y_H4LF_BL0CK_W1TH_BL0CK_C1PH3R}
getflag(0, forge_ciphertext, forge_tag)
```

打赏还是打残，这是个问题