全国大学生信息安全竞赛-SM1 Writeup

源码分析

解压附件后其中有加密算法源码，内容如下：

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
from random import randint
def gen512num():
    order=[]
    while len(order)!=512:
        tmp=randint(1,512)
        if tmp not in order:
            order.append(tmp)
    ps=[]
    for i in range(512):
        p=getPrime(512-order[i]+10)
        pre=bin(p)[2:][0:(512-order[i])]+"1"
        ps.append(int(pre+"0"*(512-len(pre)),2))
    return ps

def run():
    choose=getPrime(512)
    ps=gen512num()
    print("gen over")
    bchoose=bin(choose)[2:]
    r=0
    bchoose = "0"*(512-len(bchoose))+bchoose
    for i in range(512):
        if bchoose[i]=='1':
            r=r^ps[i]
    flag=open("flag","r").read()

    key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
    aes_obj = AES.new(key, AES.MODE_ECB)
    ef=aes_obj.encrypt(flag).encode("base64")

    open("r", "w").write(str(r))
    open("ef","w").write(ef)
    gg=""
    for p in ps:
        gg+=str(p)+"\n"
    open("ps","w").write(gg)

run()

其他的附件内容就不一一展示了；

Key：这是一个基于线性代数和异或运算的加密系统，核心是利用GF(2)上的线性方程组。

gen512num()函数

def gen512num():
    order=[]
    while len(order)!=512:
        tmp=randint(1,512)
        if tmp not in order:
            order.append(tmp)
    ps=[]
    for i in range(512):
        p=getPrime(512-order[i]+10)
        pre=bin(p)[2:][0:(512-order[i])]+"1"
        ps.append(int(pre+"0"*(512-len(pre)),2))
    return ps

功能：生成512个特殊的512位数字

关键点：

• order 是1-512的随机排列，每个数字只出现一次
• 对于每个 order[i]：
  • 生成一个素数 p，位数为 512 - order[i] + 10
  • 取 p 的前 (512 - order[i]) 位，后面拼接一个”1”
  • 最后用0填充到512位

实例：

如果 order[i] = 100，则：

• 素数位数：512 - 100 + 10 = 422 位
• 取前 512 - 100 = 412 位，加”1” → 413位
• 后面补 512 - 413 = 99 个0

重要特性：每个 ps[i] 的二进制表示中，最低位的1出现在不同的位置（由order决定）。

run函数 - 主要加密逻辑

def run():
    choose=getPrime(512)  # 随机512位素数
    ps=gen512num()        # 生成512个特殊数字
    
    bchoose=bin(choose)[2:].zfill(512)  # 512位二进制
 
    r=0
    for i in range(512):
        if bchoose[i]=='1':
            r=r^ps[i]     # 异或运算

加密过程：

• choose 的每个二进制位决定是否选择对应的 ps[i]
• r 是所有被选中的 ps[i] 的异或结果

Flag加密部分

key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef=aes_obj.encrypt(flag).encode("base64")

流程：

1. choose → MD5哈希 → AES密钥
2. 用AES-ECB模式加密flag
3. 结果Base64编码

漏洞分析与攻击原理

关键漏洞点：

每个 ps[i] 的二进制形式具有独特的结构，对于每个 ps[i]，可以表示为：

$$
ps[i] = A_i × 2^(k_i + 1) + 2^(k_i)
$$
例如：

ps[0] = xxxxxxxxx1 000...000  (最低位1在位置511)
ps[1] = xxxxxxxx1 000...000   (最低位1在位置510)  
ps[2] = xxxxxxx1 000...000    (最低位1在位置509)
...

攻击方法：从低位到高位逐步恢复

由于异或运算在GF(2)上是线性的，我们可以从最低位开始逐位恢复 choose：

1. 找到最低位的1：在 r 中找最低的为1的位
2. 确定对应的 ps[i]：该位必须来自某个 ps[i]，其最低位1正好在这个位置
3. 标记 choose[i] = 1：说明这个 ps[i] 被选中了
4. 消除影响：从当前 r 中异或掉这个 ps[i]
5. 重复：处理更高位

为什么这样可行？

• 因为每个 ps[i] 的最低1位位置唯一
• 异或操作是线性的，没有进位影响
• 从低位开始处理，高位不会影响低位

Exploit

# for python3
import base64
import hashlib
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.backends import default_backend

def read_files():
    with open("r", "r") as f: r = int(f.read())
    with open("ef", "r") as f: ef = base64.b64decode(f.read())
    with open("ps", "r") as f: ps = [int(line) for line in f]
    return r, ef, ps

def recover_choose(r, ps):
    positions = [(bin(p)[2:].zfill(512).rfind('1'), i) for i, p in enumerate(ps)]
    positions.sort(reverse=True)
    
    bchoose, current_r = [0]*512, r
    for pos, idx in positions:
        if (current_r >> (511-pos)) & 1:
            bchoose[idx] = 1
            current_r ^= ps[idx]
    
    return int(''.join(map(str, bchoose)), 2)

def decrypt_flag(choose, ef):
    key = hashlib.md5(choose.to_bytes(64, 'big')).digest()
    cipher = Cipher(algorithms.AES(key), modes.ECB(), default_backend())
    return cipher.decryptor().update(ef) + cipher.decryptor().finalize()

if __name__ == "__main__":
    r, ef, ps = read_files()
    choose = recover_choose(r, ps)
    flag = decrypt_flag(choose, ef)
    print(f"Flag: {flag.decode()}")