Pwn College Cryptography 学习笔记

XOR

A ^ B ^ B = A

A ^ B ^ C ^ B = A ^ C

原理很简单，没什么好说的。

使用 PyCryptoDome 库进行相关操作。

from Crypto.Util.strxor import strxor
strxor("a".encode(), "a".encode()); # b'\x00''

One-time Pad

实际上就是一个异或加密，但是满足两个就绝对安全：

• key 的传输是安全的
• 只使用一次这个 key

但是不满足这两个就不安全。第一道 key 泄露了，后两道题的 key 重复使用。

AES

AES，全称 Advance Encryption Standard 好敷衍的名字，是一个比较流行的对称加密算法。

算法总体思路是：

• 将明文分组为 128 位，16 字节，并将剩余部分通过一定方法处理为整。这是因为算法只能加密整的 16 字节
• 对若干 16 字节组成的 4*4 方阵，同 key 一起进行若干轮加密操作，得到密文
• 通过一定方法将若干 16 字节拼接

虽然分组只能是 16 字节 128 位，但是密钥 key 的长度不定，可以是 128 位、192 位、256 位，分别为 AES-128、AES-192、AES-256，不同长度的密钥推荐加密轮数不一样，分别为 10、12、14。

接下来详细说说加密算法。因为解密都是很显然的将加密反过来，就不赘述了）

因为每一轮的加密算法是一样的，我们就来关注第一轮的加密。

明文矩阵填充

AES 需要对一个 4*4 的 Bytes 矩阵来进行操作，我们已经有了 16 字节的明文数据，现在要填充成一个矩阵。

将 16 个字节称为 $P_0,P_1,...,P_{15}$，那么 AES 这样排列 16 个字节：

$$\begin{bmatrix} P_0 & P_4 & P_8 & P_{12} \\ P_1 & P_5 & P_9 & P_{13} \\ P_2 & P_6 & P_{10} & P_{14} \\ P_3 & P_7 & P_{11} & P_{15} \end{bmatrix}$$

即一列一列走。

密钥矩阵填充

密钥 $K$ 使用同样方式填充。

$$\begin{bmatrix} K_0 & K_4 & K_8 & K_{12} \\ K_1 & K_5 & K_9 & K_{13} \\ K_2 & K_6 & K_{10} & K_{14} \\ K_3 & K_7 & K_{11} & K_{15} \end{bmatrix}$$

但是不止这样。通过一定扩充算法，密钥会被扩充成 44 个 4 Bytes 的序列 $W_0,W_1,...,W_{43}$，每四个元素用于一轮「轮密钥加」。

其中，$W$ 中前四个就是原始的 key，比如 $W_2=K_8 \ K_9 \ K_{10} \ K_{11}$，后面会讲怎么计算出剩余的 $W$。

加密过程

一轮加密有以下流程：

• 轮密钥加
• 字节代换
• 行位移
• 列混合

其中，在所有轮开始之前，会使用 $W_0$ 到 $W_3$ 进行一次轮密钥加。因此 AES-128 十轮加密刚好 11 次轮密钥加，44 个 $W$。

加密过程中的矩阵将用 $S$ 表示。

字节代换

这名字挺高级，但实际上就是对 Bytes 执行一次全排列变换。具体怎么变换存在一个固定的 S 盒。虽然我也不知道为什么要固定变换（解密存在一个逆 S 盒）

行位移

方阵第 $i$ 行左移 $i-1$ 位。

$$\begin{bmatrix} S_{0} & S_{4} & S_{8} & S_{12} \\ S_{1} & S_{5} & S_{9} & S_{13} \\ S_{2} & S_{6} & S_{10} & S_{14} \\ S_{3} & S_{7} & S_{11} & S_{15} \end{bmatrix} \xrightarrow{} \begin{bmatrix} S_{0} & S_{4} & S_{8} & S_{12} \\ S_{5} & S_{9} & S_{13} & S_{1} \\ S_{10} & S_{14} & S_{2} & S_{6} \\ S_{15} & S_{3} & S_{7} & S_{11} \end{bmatrix}$$

列混合

列混合使用到了有限域 $GF(2^8)$ 的运算，即运算结果会落在 0~255 内。

有限域将每个二进制映射成多项式，如 $13=x^3+x^2+1$。

加法：异或

乘法：多项式乘法，并取模数保持值在域内

AES 指定的模数：$m(x)=x^8+x^4+x^3+x^1+1$

在以上运算基础上，列混合即对每列进行以下运算：

$$\begin{bmatrix} S'_{0,j} \\ S'_{1,j} \\ S'_{2,j} \\ S'_{3,j} \end{bmatrix} = \begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix} \begin{bmatrix} S_{0,j} \\ S_{1,j} \\ S_{2,j} \\ S_{3,j} \end{bmatrix}$$

意外发现，S 盒并不是随便选取的全排列变换，而是有限域下的乘法逆元。
我发现如果深究算法和原因 AES 比我想象的复杂多了。后面可能不会过多考虑这些了）

轮密钥加

将 S 按列组成一个 4 Bytes 数，与对应轮次 $W$ 异或得到 $S'$，如 $S'_0 \ S'_1 \ S'_2 \ S'_3 = S_0 \ S_1 \ S_2 \ S_3 \oplus W_{4i}$

$$\begin{bmatrix} S_{0} & S_{4} & S_{8} & S_{12} \\ S_{1} & S_{5} & S_{9} & S_{13} \\ S_{2} & S_{6} & S_{10} & S_{14} \\ S_{3} & S_{7} & S_{11} & S_{15} \end{bmatrix} \oplus \begin{bmatrix} W_{4i} & W_{4i+1} & W_{4i+2} & W_{4i+3} \end{bmatrix} = \begin{bmatrix} S'_{0} & S'_{4} & S'_{8} & S'_{12} \\ S'_{1} & S'_{5} & S'_{9} & S'_{13} \\ S'_{2} & S'_{6} & S'_{10} & S'_{14} \\ S'_{3} & S'_{7} & S'_{11} & S'_{15} \end{bmatrix}$$

密钥扩展

先将 128 位的 key 存入 $W_0$ 到 $W_4$。接下来按如下方式拓展密钥：

• $i$ 模四不为零，$W_i=W_{i-4} \oplus W_{i-1}$
• $i$ 模四为零，$W_i=W_{i-4} \oplus T(W_{i-1})$

$T$ 函数由以下三步组成：

• 字循环：循环左移一字节，即 $b_0 b_1 b_2 b_3 \rightarrow b_1 b_2 b_3 b_0$
• 字节代换，用 S 盒替换每字节
• 轮常量异或：与轮常量 $Rcon_j$ 异或，$j$ 是轮数。

$j$	1	2	3	4	5
$Rcon_j$	01 00 00 00	02 00 00 00	04 00 00 00	08 00 00 00	10 00 00 00
$j$	6	7	8	9	10
$Rcon_j$	20 00 00 00	40 00 00 00	80 00 00 00	1B 00 00 00	36 00 00 00

分组加密的工作模式

到现在只解决了单组的加密问题，对于其他内容有更多的处理方法。

ECB

即 Electronic Code Book，将明文直接分割，分别 AES 后拼接。

PKCS7

处理 padding 的标准，若最后一组只有 13 Bytes，明文最后三字节填为 0x03 0x03 0x03。

但是万一明文刚好整分组，且最后一字节是 0x01 怎么办？那就多开一个 0x10 组成的分组。

CBC

CBC 即 Cipher Block Chaining，ECB 的缺点是每一个分组之间相对没有影响，比如有一张较大的图片，加密后的密文排列依旧可以看出形状。CBC 解决了这个问题，使得分组之间产生联系。

具体来说，每个块加密前，异或上上一个块的密文。第一个则异或上随机串 Initialization Vector(IV)，这个随机串随后会附在密文开头。解密即所有块解密后异或上一块的密文。因为 IV 每次都是是随机的，这也使得 CPA 失效。

此外，CBC 异或前一块的密文而不是明文的好处还在于：

• 若明文有一大串 0，可能会泄露数据
• 可以从任意一个位置开始解密。若异或的是明文则需要递归依赖到开头

缺点就是加密无法并行，效率低了不少。

Pwn College 题

AES

from Crypto.Cipher import AES

key=bytes.fromhex("5b710801526c8550a8e406d8e3419aeb")
ciphertext = bytes.fromhex("1b6bf22abced36d03eb5c2111e8fecc0622b022d80140dae8e7e50349adf3ce3b0b10223078e10a7cbf6fc4b21f60c1d5b21d59aa5bdcdef21a3aa01d82991b7")

cipher = AES.new(key,AES.MODE_ECB)
plaintext = cipher.decrpt(ciphertext)

# >>> plaintext
# b'pwn.college{wQqefBC_RvNWsUVh9tyuqiTjd09.QX2czMzwCOzADOzEzW}\n\x04\x04\x04\x04'

AES-ECB-CPA

CPA 即 Chosen Plaintext Attack，这里可以选择以任意 index 开始长度 length 来 AES 加密。提前打表一份每个字符即可。

from pwn import *

p = process("/challenge/run")
p.recvuntil("? ")

list = {}
def restor(c):
    p.sendline("1".encode())
    p.recvuntil("? ")
    p.sendline(c.encode())
    list[c] = p.recvline()
    p.recvuntil("? ")

restor("-")
restor(".")
restor("{")
restor("}")
restor("_")
for i in range(26):
    restor(chr(ord("a") + i))
    restor(chr(ord("A") + i))
    if i < 10:
        restor(chr(ord("0") + i))


flag = "p"
i = 0
while flag[-1] != "}":
    i = i + 1
    for c, cip in list.items():
        p.sendline("2".encode())
        p.recvuntil("? ")
        p.sendline(str(i).encode())
        p.recvuntil("? ")
        p.sendline("1".encode())
        rr = p.recvline();
        p.recvuntil("? ")
        if rr == cip:
            flag += c
            break

print(flag)

AES-ECB-CPA-Suffix

hacker@cryptography~aes-ecb-cpa-suffix:~$ /challenge/run 
Choose an action?
1. Encrypt chosen plaintext.
2. Encrypt the tail end of the flag.
Choice? 2
Length? 1
Result: 60e5c9dea2c3041932d06bde00b5dd71
Choose an action?
1. Encrypt chosen plaintext.
2. Encrypt the tail end of the flag.
Choice? 2
Length? 17
Result: 60da0f925bdee3cbdfc1a364a40f7c9560e5c9dea2c3041932d06bde00b5dd71

能够取后缀 同样打表就行 懒得写了。

AES-ECB-CPA-Prefix

hacker@cryptography~aes-ecb-cpa-prefix:~$ /challenge/run 

Choose an action?
1. Encrypt chosen plaintext.
2. Prepend something to the flag.
Choice? 1
Data? aaaaaaaaaaaaaaap
Result: 40b54eecd42d65c6e145f26e83a20324b
I'm here to help!
For the first 10, I will split them into blocks for you!
After this, you'll have to split them yourself.
# of blocks: 1.
Block 1: 40b54eecd42d656e145f26e83a20324b

Choose an action?
1. Encrypt chosen plaintext.
2. Prepend something to the flag.
Choice? 2
Data? aaaaaaaaaaaaaaa
Result: 40b54eecd42d656e145f26e83a20324b45841f5d0ff52e7530909f68470f8afa158c9891f1d9d628a7bda9f51e473e38e03525fddbe6ebeebff88622c9d48ee705dcdc44b440d6d5c6c214992f1475d2
# of blocks: 5.
Block 1: 40b54eecd42d656e145f26e83a20324b
Block 2: 45841f5d0ff52e7530909f68470f8afa
Block 3: 158c9891f1d9d628a7bda9f51e473e38
Block 4: e03525fddbe6ebeebff88622c9d48ee7
Block 5: 05dcdc44b440d6d5c6c214992f1475d2

可以加一个前缀进行加密。如给的一样，一位一位移就行。不写了。

AES-ECB-CPA-Prefix-2

这里会出现即 PKCS7 多 padding 一组的情况 我是感觉对我上题的思路没什么影响）

AES-ECB-CPA-miniboss

hacker@cryptography~aes-ecb-cpa-prefix-miniboss:~$ /challenge/run 
Data? 0f
Ciphertext: e60b3c469d09473013bed71bec31ba22b926c3031c338e6ba634585b1762c6f0c27f7c7e29d3f84d5f00781b911ab908400d36d3cd6a9acfcf94ef5fae33e82e
Data? 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f70
Ciphertext: b46d128fbc5f9a0f7596b9a33a14037a3d0a22e2f17068aaa7a658cec84a5c3a5190b890b75bcc5973b3945124165be95c084b30da22a00fe40d87e1e6d460d838c8ef7607acedee12763c741b934287
Data? 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f  
Ciphertext: b46d128fbc5f9a0f7596b9a33a14037ac1ee223ca720ede0ca85ec20944bc2ddf28f70a2540c22e64f36ba9e3f21b2fb0ca8701544a6d5a11bed864df3fcbf12db758ffac612f25de06be5a86eeff03b
Data?

使用十六进制输入。没多大差别吧）

AES-CBC

from Crypto.Cipher import AES

key = bytes.fromhex("86f4204528b4c2cb1c83bce25e8b23dc")
ciphertext = bytes.fromhex("57cc6e947bc2f27efaab5f36a5df10903feb343928c55527ec16236c2cc021ddb9064df0baa6297b0fc6de1ee3bb3b522737c85c465dc585c639d852fb1713691671458da4e332e4271b42bdbea7edaa")

cipher = AES.new(key, AES.MODE_CBC)
plaintext = cipher.decrypt(ciphertext)

print(plaintext)

AES-CBC Tampering

通过中间劫持密文并针对 IV 修改达到修改明文的手段。

hacker@cryptography~aes-cbc-tampering:~$ cat /challenge/dispatcher 
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

import os

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes

key = open("/challenge/.key", "rb").read()
cipher = AES.new(key=key, mode=AES.MODE_CBC)
ciphertext = cipher.iv + cipher.encrypt(pad(b"sleep", cipher.block_size))

print(f"TASK: {ciphertext.hex()}")

hacker@cryptography~aes-cbc-tampering:~$ cat /challenge/worker 
#!/usr/bin/exec-suid -- /usr/bin/python3 -I

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Random import get_random_bytes

import time
import sys

key = open("/challenge/.key", "rb").read()

while line := sys.stdin.readline():
    if not line.startswith("TASK: "):
        continue
    data = bytes.fromhex(line.split()[1])
    iv, ciphertext = data[:16], data[16:]

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    try:
        plaintext = unpad(cipher.decrypt(ciphertext), cipher.block_size).decode('latin1')
    except ValueError as e:
        print("Error:", e)
        continue

    print(f"Hex of plaintext: {plaintext.encode('latin1').hex()}")
    print(f"Received command: {plaintext}")
    if plaintext == "sleep":
        print("Sleeping!")
        time.sleep(1)
    elif plaintext == "flag!":
        print("Victory! Your flag:")
        print(open("/flag").read())
    else:
        print("Unknown command!")

因为这里知道明文是 sleep，目标是 flag!，而且是第一个块，直接将 IV 替换为 IV ^ b'sleep' ^ b'flag!' 即可。

妙啊！

strxor 不支持长度不相同的异或。这里需要用到 Padding 来填充。

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor

task = "0fabaa552f79ee1c3a5b0620108e1256a32e8bb84b023732cc75b8371c9a026c"
task = bytes.fromhex(task)

iv, ci = task[:16], task[16:]
sleep = pad(b"sleep", AES.block_size)
flag_ = pad(b"flag!", AES.block_size)

print("TASK: " + strxor(iv, strxor(sleep, flag_)).hex() + ci.hex())

AES-CBC Resizing

前面 sleep 和 flag! 长度相同，这里不同。但是我已经用 padding 了就没有问题了。