Crypto challenges Writeups

Thu Sep 26 2024

记录一下现代密码学课程第二次实验的题解，（主要还是反转课堂演示用

# Part 1

纯纯的读文档题，烂活

根据文档，计算校验位，补全机读区的缺失部分

# %%
import base64
import hashlib
from Crypto.Cipher.AES import new as aes
 
# %%
encoded = "9MgYwmuPrjiecPMx61O6zIuy3MtIXQQ0E59T3xB6u0Gyf1gYs2i3K9Jxaa0zj4gTMazJuApwd6+jdyeI5iGHvhQyDHGVlAuYTgJrbFDrfB22Fpil2NfNnWFBTXyf7SDI"
ciphertext = base64.b64decode(encoded)
 
 
# mrz = "12345678<8<<<1110182<111116?<<<<<<<<<<<<<<<4"
def checksum(ks):
    def mapped():
        for i, v in enumerate(ks):
            o = ord(v)
            if 48 <= o <= 57:
                yield i, o - 48
            if 65 <= o <= 90:
                yield i, o - 55
 
    w = [7, 3, 1]
    return sum(k * w[i % len(w)] for i, k in mapped()) % 10
 
 
assert checksum("111116") == 7
 
mrz = "12345678<8<<<1110182<1111167<<<<<<<<<<<<<<<4"

根据文档，从机读区计算k_seed

k_seed = hashlib.sha1((mrz[:10] + mrz[13:20] + mrz[21:28]).encode()).digest()[:16]

根据文档，从k_seed计算 AES key

def gen_key(k_seed, c):
    return bytes(
        ((v & 0b11111110) | ((v & 0b11111110).bit_count() & 1) ^ 1)
        for v in hashlib.sha1(k_seed + bytes([0, 0, 0, c])).digest()[:16]
    )
 
 
k = gen_key(k_seed, 1)
ctx = aes(k, 2, b"\x00" * 16)
print(ctx.decrypt(ciphertext))

# Part 2

## Implement PKCS#7 padding

原题链接

根据 PKCS#7 标准，直接写

def pad(raw:bytes, block_size:int) -> bytes:
    padding = block_size - len(raw) % block_size
    return raw + bytes([padding] * padding)

## Implement CBC mode

原题链接

这里要先实现一个 AES ECB 算法

根据 CBC Mode 的定义，令 AES ECB 加密一个 block 的算法为 transform，可以得到 CBC Mode 的实现如下

def strxor(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))
 
 
def cbc_encrypt(
    blocks: list[bytes], iv: bytes, transform: Callable[[bytes], bytes]
) -> list[bytes]:
    result = [iv]
    for block in blocks:
        result.append(transform(strxor(block, result[-1])))
    return result
 
 
def cbc_decrypt(
    blocks: list[bytes], iv: bytes, transform: Callable[[bytes], bytes]
) -> list[bytes]:
    result = [strxor(transform(blocks[0]), iv)]
    for index, block in enumerate(blocks[1:]):
        result.append(strxor(transform(block), blocks[index]))
    return result

我们还需要把密文分块

def split_blocks(message, block_size=16):
    assert len(message) % block_size == 0
    return [message[i:i+16] for i in range(0, len(message), block_size)]

已知 iv 为 b"\x00"*16，key 为 b"YELLOW SUBMARINE"，可进行解密：

import base64
from aes import context as aes_context
 
ciphertext = base64.b64decode("""
/* omitted */
""")
key = b"YELLOW SUBMARINE"
ctx = aes_context(key)
 
print(b"".join(cbc_decrypt(split_blocks(ciphertext), b"\x00"*16, ctx.decrypt_block)))

## An ECB/CBC detection oracle

原题链接

先生成随机的 key 和 padding，可以直接用urandom

import os
import random
 
 
def random_key():
    return os.urandom(16)
 
 
def random_padding():
    return os.urandom(random.randint(5, 10))

编写一个函数，根据给定的 key 和 msg，在进行随机 padding 之后，随机采用 ECB 或者 CBC 加密

import Crypto.Cipher.AES as AES
import Crypto.Util.Padding as padding
 
def encryption_oracle(key, msg):
    mode = random.choice([AES.MODE_ECB, AES.MODE_CBC])
    plaintext = random_padding() + msg + random_padding()
    plaintext = padding.pad(plaintext, 16)
    match mode:
        case AES.MODE_ECB:
            return AES.new(key, mode).encrypt(plaintext), mode
        case AES.MODE_CBC:
            iv = random_key()
            return AES.new(key, mode, iv).encrypt(plaintext), mode
    assert False, "unreachable"

随机选择一个密钥，再选择一个连续三个块内容一致的明文，用上面的函数加密

key = random_key()
msg = b"\x00" * 16 * 3
encrypted = [encryption_oracle(key, msg) for _ in range(100)]

因为选择的明文块有相同的内容，如果使用 ECB 模式得到的密文也是相同的，而 CBC 模式不会出现该问题，因此可以考虑统计有几个不同的密文块，如果存在相同密文块，则可以断定为 ECB 模式

def detect_mode(ciphertext):
    blocks = [ciphertext[i : i + 16] for i in range(0, len(ciphertext), 16)]
    if len(blocks) != len(set(blocks)):
        return AES.MODE_ECB
    return AES.MODE_CBC
 
 
accr = sum(detect_mode(ciphertext) == mode for ciphertext, mode in encrypted)
print(f"{accr / len(encrypted):.2%}")

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

原题链接

因为能在未知的明文前面进行填充，那就想办法将第一个未知的字符放在每个块的最后，这样我们就可以构造一个块进行碰撞（由15个已知的字符，和一个位置的字符）

先导入函数，并构造encryption_oracle

import base64
import os
import Crypto.Cipher.AES as AES
import Crypto.Util.Padding as padding
import string
 
 
def encryption_oracle(oracle):
    key = os.urandom(16)
    return AES.new(key, AES.MODE_ECB).encrypt(
        padding.pad(
            oracle
            + base64.b64decode("""
Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK"""),
            16,
        )
    )

因为我们不知道未知明文的长度，因此需要爆破明文长度

init_unk_strlen = len(encryption_oracle(b""))
unk_strlen = init_unk_strlen
assert unk_strlen % 16 == 0
for i in range(16):
    if len(encryption_oracle(b"A" * i)) != init_unk_strlen:
        unk_strlen = init_unk_strlen - i
        break

构造明文空间，构造dfs进行搜索，这里不能全部递归，可能会爆栈

plain_space = string.printable.encode()
 
def search(known):
    while True:
        partial = known[-15:] # 取明文的最后15字节（可能不足）
        partial = b"\x00" * (15 - len(partial)) + partial # 补齐到15字节
        current = []
        for i in plain_space:
            oracle = partial + bytes([i]) + b"\x00" * (15 - len(known) % 16) # 构造 oracle，让第一个未知明文在块的最后一个字节
            enc = encryption_oracle(oracle)
            if enc[15] == enc[len(known) // 16 * 16 + 31]: # 成功碰撞
                current.append(i)
        if len(current) == 1:
            known += bytes(current) # 不递归，用循环，防止爆栈
            print(known)
            if len(known) == unk_strlen: # 达到预期长度，成功退出
                return True
            continue
        elif len(current) == 0: # 没有成功碰撞，失败退出
            return False
        else:
            for c in current: # 对每一个碰撞
                if search(known + bytes([c])): # 递归搜索
                    return True # 找到结果就返回
 
 
search(b'')

## ECB cut-and-paste

原题链接

先随便模拟一下题目的环境

import Crypto.Cipher.AES as AES
import Crypto.Util.Padding as padding
 
key = b"\xc6\xfe\xe2/\x97r|/\xeaY\xc5C\xbfi\x99\x97"
 
 
def encrypt(userdata: bytes):
    data = (
        b"userdata="
        + userdata.replace(b"&", b"").replace(b"=", b"")
        + b"&uid=10&role=user"
    )
    return AES.new(key, AES.MODE_ECB).encrypt(padding.pad((b"\x00" * 16) + data, 16))
 
 
def decrypt(data: bytes):
    data = AES.new(key, AES.MODE_ECB).decrypt(data)
    data = padding.unpad(data, 16)[16:]
    return {
        (kv := item.split(b"=", maxsplit=1))[0].decode(): kv[1]
        for item in data.split(b"&")
    }
 
 
def is_admin(data: bytes):
    decrypted = decrypt(data)
    print(decrypted)
    return decrypted.get("role") == b"admin"

因为是 ECB 模式，所以只要复制整个块过去就行，但是要注意 padding

userdata = b"A" * 7 + b"admin" + b"\x0b" * 14
enc = encrypt(userdata)
enc = enc[:64] + enc[32:48]
assert is_admin(enc)

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

原题链接

我们暂时假定这题的意思是，每次实验的prefix_len随机但固定（不然真没法做了），所以直接求出prefix_len，然后把prefix补齐到整块，整个丢掉就好

修改 12 题代码

__MY_SUPER_SECRET_PREFIX_LENGTH__ = random.randint(0, 64)
 
 
def encryption_oracle(oracle):
    key = os.urandom(16)
    rand_pad = os.urandom(__MY_SUPER_SECRET_PREFIX_LENGTH__)
    return AES.new(key, AES.MODE_ECB).encrypt(
        padding.pad(
            rand_pad
            + oracle
            + base64.b64decode("""
Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg
aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq
dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg
YnkK"""),
            16,
        )
    )

求未知部分长度，以及前缀导致的偏移量和需要的补齐长度

def get_unklen():
    init_unk_strlen = len(encryption_oracle(b""))
    unk_strlen = init_unk_strlen
    assert unk_strlen % 16 == 0
    for i in range(16):
        if len(encryption_oracle(b"A" * i)) != init_unk_strlen:
            unk_strlen = init_unk_strlen - i
            break
    leftlen = 0
    while True:
        leftlen += 1
        enc = encryption_oracle(b"A" * leftlen)
        blocks = [enc[i : i + 16] for i in range(0, len(enc), 16)]
        for i in range(len(blocks) - 1):
            if blocks[i] == blocks[i + 1]:
                return unk_strlen - i * 16 + leftlen % 16, i * 16, leftlen % 16
 
 
unk_strlen, offset, leftpad = get_unklen()
leftpad = b"\x00" * leftpad

最后把补齐和移除前缀的操作加到search里面，直接搜就好

plain_space = string.printable.encode()
 
 
def search(known):
    while True:
        partial = known[-15:]
        partial = b"\x00" * (15 - len(partial)) + partial
        current = []
        for i in plain_space:
            oracle = leftpad + partial + bytes([i]) + b"\x00" * (15 - len(known) % 16)
            enc = encryption_oracle(oracle)[offset:]
            if enc[15] == enc[len(known) // 16 * 16 + 31]:
                current.append(i)
        if len(current) == 1:
            known += bytes(current)
            print(known)
            if len(known) == unk_strlen:
                return True
            continue
        elif len(current) == 0:
            return False
        else:
            for c in current:
                if search(known + bytes([c])):
                    return True
 
 
search(b"")

## PKCS#7 padding validation

原题链接

根据标准实现 PKCS#7 padding

def pad(raw: bytes, block_size: int) -> bytes:
    padding = block_size - len(raw) % block_size
    return raw + bytes([padding] * padding)
 
def unpad(data):
    padding_len = data[-1]
    payload, padding = data[:-padding_len], data[-padding_len:]
    assert all(x == padding_len for x in padding)
    return payload

随便写一个测试

try:
    unpad(pad(b"ICE ICE BABY", 16))
    print("Assert passed")
except AssertionError:
    print("Assert failed")
 
try:
    unpad(b"ICE ICE BABY\x05\x05\x05\x05")
    print("Assert passed")
except AssertionError:
    print("Assert failed")
 
try:
    unpad(b"ICE ICE BABY\x01\x02\x03\x04")
    print("Assert passed")
except AssertionError:
    print("Assert failed")

## CBC bitflipping attacks

原题链接

经典的比特反转攻击，这里的 key 是写死的，不然没法进行解密

# %%
import Crypto.Cipher.AES as AES
import Crypto.Util.Padding as padding
import os
 
key = b"\xc6\xfe\xe2/\x97r|/\xeaY\xc5C\xbfi\x99\x97"
 
 
def encrypt(userdata: bytes):
    data = (
        b"comment1=cooking MCs;userdata="
        + userdata.replace(b";", b"%3B").replace(b"=", b"%3D")
        + b";comment2= like a pound of bacon"
    )
    return AES.new(key, AES.MODE_CBC, os.urandom(16)).encrypt(
        padding.pad((b"\x00" * 16) + data, 16)
    )
 
 
def decrypt(data: bytes):
    data = padding.unpad(AES.new(key, AES.MODE_CBC, os.urandom(16)).decrypt(data), 16)[
        16:
    ]
    return {
        (kv := item.split(b"=", maxsplit=1))[0].decode(): kv[1]
        for item in data.split(b";")
    }
 
 
def is_admin(data: bytes):
    decrypted = decrypt(data)
    return decrypted.get("admin") == b"true"

由于已知加密后的结构，所以直接对 userdata 进行 padding，然后对 :(0b111010) 和 <(0b111100) 的最低位进行反转即可

padlen = 18
userdata = b"A" * padlen + b":admin<true"
enc = bytearray(encrypt(userdata))
enc[padlen + 30] ^= 1
enc[padlen + 36] ^= 1
assert is_admin(enc)