aes.py: #!/usr/bin/env python """ Copyright ...

Question

aes.py:
#!/usr/bin/env python

"""
Copyright (C) 2012 Bo Zhu http://about.bozhu.me

text
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the "Software"),
to deal in the Software without restriction, including without limitation
the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.

"""

Sbox = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCC, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

learnt from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c

xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

Rcon = (
0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)

def text2matrix(text):
matrix = [[] for _ in range(4)]
for i in range(16):
byte = (text >> (8 * (15 - i))) & 0xFF
matrix[i % 4].append(byte)
return matrix

def matrix2text(matrix):
text = 0
for i in range(4):
for j in range(4):
text |= (matrix[j][i] << (120 - 8 * (4 * i + j)))
return text

class AES:
def init(self, master_key):
if not isinstance(master_key, (bytes, bytearray)) or len(master_key) != 16:
raise ValueError("master_key must be 16 bytes for AES-128")
self.change_key(int.from_bytes(master_key))

text
def change_key(self, master_key):
    self.round_keys = text2matrix(master_key)
    for i in range(4, 4 * 11):
        self.round_keys.append([])
        if i % 4 == 0:
            temp = [
                self.round_keys[i - 4][0] ^ Sbox[self.round_keys[i - 1][1]] ^ Rcon[i // 4],
                self.round_keys[i - 4][1] ^ Sbox[self.round_keys[i - 1][2]],
                self.round_keys[i - 4][2] ^ Sbox[self.round_keys[i - 1][3]],
                self.round_keys[i - 4][3] ^ Sbox[self.round_keys[i - 1][0]],
            ]
        else:
            temp = [
                self.round_keys[i - 4][j] ^ self.round_keys[i - 1][j] for j in range(4)
            ]
        self.round_keys[i] = temp

def encrypt(self, plaintext):
    state = text2matrix(plaintext)
    self.add_round_key(state, self.round_keys[:4])
    for i in range(1, 10):
        self.sub_bytes(state)
        self.shift_rows(state)
        self.mix_columns(state)
        self.add_round_key(state, self.round_keys[4*i:4*(i+1)])
    self.sub_bytes(state)
    self.shift_rows(state)
    self.add_round_key(state, self.round_keys[16:20])
    return matrix2text(state)

def add_round_key(self, s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]

def sub_bytes(self, s):
    for i in range(4):
        for j in range(4):
            s[i][j] = Sbox[s[i][j]]

def shift_rows(self, s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

def mix_columns(self, s):
    for i in range(4):
        t = s[i][0] ^ s[i][1] ^ s[i][2] ^ s[i][3]
        u = s[i][0]
        s[i][0] ^= t ^ xtime(s[i][0] ^ s[i][1])
        s[i][1] ^= t ^ xtime(s[i][1] ^ s[i][2])
        s[i][2] ^= t ^ xtime(s[i][2] ^ s[i][3])
        s[i][3] ^= t ^ xtime(s[i][3] ^ u)


def encrypt_ecb(self, data: bytes) -> bytes:
    if not isinstance(data, (bytes, bytearray)):
        raise TypeError("data must be bytes-like")
    if len(data) % 16 != 0:
        raise ValueError("data length must be multiple of 16 when pad=False")
    out = b''
    for i in range(0, len(data), 16):
        out += self.encrypt(int.from_bytes(data[i : i + 16])).to_bytes(16)
    return out

task.py:
from Crypto.Util.number import bytes_to_long
from random import shuffle
from base64 import b64encode
from hashlib import md5
from secret import flag

def is_valid_uuid(u, v=4):
from uuid import UUID
try:
m = UUID(u, version=v)
except ValueError:
return False
return str(m) == u

def en(m, key):
if isinstance(m, str):
m = m.encode()
return b64encode(m).decode().translate(str.maketrans(table, key))

def decision(t):
from os import urandom
from aes import AES

text
key = urandom(16)
aes = AES(key)
m = urandom(16 * 4500)
return [m, aes.encrypt_ecb(m)][t]

assert flag.startswith(b'flag{') and flag.endswith(b'}') and is_valid_uuid(flag[5:-1].decode())

table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
k = [*table]
shuffle(k)
key = ''.join(k)

print(md5(flag).hexdigest())

ec2783d8262e2621eece6e9e236479dc

c = en(en(flag, key), key).encode()
c = bin(bytes_to_long(c))[2:]
p = [decision(int(i)) for i in c]

import lzma

open('output', 'wb').write(lzma.compress(str(p).encode()))
手里有output，帮我写脚本解出flag

Answer 1

我先给结论：按你贴出来的这两份源码，只有 output 是解不出 flag 的。
不是脚本没想到，而是这题这版源码本身不泄露任何关于 c 的信息。

核心原因很简单：

decision(t) 里两种返回值分别是：

t = 0：m = urandom(16 * 4500)，也就是均匀随机的 72000 字节。
t = 1：aes.encrypt_ecb(m)，其中 m 仍然是均匀随机的 72000 字节。

而这个 AES.encrypt_ecb，虽然实现里有明显 bug（例如最后一轮 round key 用错了，shift_rows/mix_columns 的方向也不标准），但它仍然是一个置换：
SubBytes 可逆，ShiftRows 可逆，MixColumns 这个线性变换也可逆，AddRoundKey 更可逆。ECB 只是把这个 16 字节置换独立作用到每个 block 上。

所以：

m ~ U
E_k(m) ~ U

两边分布完全一样。
也就是说，p[i] 对应的是 bit 0 还是 bit 1，在统计上不可区分。

因此：

output 里每个元素都只是“一个均匀随机 72000 字节串”
整个 output 对 c 的信息量是 0
后面的 md5(flag) 只是一个 UUIDv4 格式 flag 的 MD5，单独也没法回原像

也就是这题按你贴的版本，信息论上不可解。

下面这个脚本不是“解 flag”，而是帮你本地验证这题为什么不可解：

python
#!/usr/bin/env python3
import ast
import lzma
from pathlib import Path
from collections import Counter
import math

def shannon_entropy(bs: bytes) -> float:
    cnt = Counter(bs)
    n = len(bs)
    return -sum((v / n) * math.log2(v / n) for v in cnt.values())

def main():
    raw = Path("output").read_bytes()
    dec = lzma.decompress(raw)
    p = ast.literal_eval(dec.decode())

    assert isinstance(p, list)
    assert all(isinstance(x, (bytes, bytearray)) for x in p)

    print(f"[+] samples = {len(p)}")
    print(f"[+] sample length = {len(p[0])} bytes")

    ents = [shannon_entropy(x) for x in p]
    print(f"[+] entropy avg = {sum(ents)/len(ents):.6f} bits/byte")
    print(f"[+] entropy min = {min(ents):.6f} bits/byte")
    print(f"[+] entropy max = {max(ents):.6f} bits/byte")

    # 看看前几个样本的字节频率是否都像纯随机
    for idx, x in enumerate(p[:5]):
        cnt = Counter(x)
        most = cnt.most_common(5)
        print(f"[+] sample[{idx}] top-5 byte counts: {most}")

    print()
    print("[!] 结论：按题面源码，decision(0) 返回 U，decision(1) 返回 Pi_k(U)。")
    print("[!] 因为 Pi_k 是置换，所以 Pi_k(U) 与 U 同分布。")
    print("[!] 这意味着 output 不携带任何关于秘密比特串 c 的信息。")
    print("[!] 所以无法从 output 唯一恢复 flag。")

if __name__ == "__main__":
    main()

你这题要想“能做”，题面至少得改成下面这类之一才行：

m 不是均匀随机，而是低熵/有结构的数据
给出的是 m 和 E_k(m) 的某种配对关系
AES 真正写坏成了非置换
或者 output 里除了 p 还泄了别的信息

你贴的这版里，最可能是题目漏贴了某个关键条件，或者原题源码跟你现在这份不一致。
把 output 文件和完整题面一起贴出来，我可以直接帮你判断到底是漏条件，还是源码抄错了。

aes.py: #!/usr/bin/env python """ Copyright ...

Frage

learnt from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c

ec2783d8262e2621eece6e9e236479dc

Python

Python

Python

Gedanke

Gedanke

Gedanke

Gedanke

Antwort

Diesen Q&A teilen