2024 数字中国积分争夺赛预赛

import os
from gmssl import sm3, func

with open('flag') as f:
    flag = f.read()

MySecretInfo = os.urandom(64)
HashValue = sm3.sm3_hash(func.bytes_to_list(MySecretInfo))
print('MySecretInfo Hash:', HashValue)

AppendData = bytes.fromhex(input('Input AppendData: '))
assert len(AppendData) == 64
NewSecretInfo = MySecretInfo + AppendData

GeneratedHash = input('Input NewSecretInfo Hash: ')
NewHashValue = sm3.sm3_hash(func.bytes_to_list(NewSecretInfo))
print(NewHashValue)

if GeneratedHash == NewHashValue:
    print(flag)
else:
    print('Nope')

看到赛题名字就能知道大概是一个哈希拓展攻击了，攻击原理这里就不赘述了，sm3 和 md5 都是分组哈希，所以对 md5 的哈希拓展攻击同样适用于 sm3。

回到题目，这里首先给出了一个64字节的 MySecretInfo 的 sm3 哈希，记为 Hash = sm3(secret)

然后要求我们给过去一个 64 字节的 AppendData，并计算 NewHash = sm3(secret||append)

由于 MySecretInfo 未知，所以 NewHash 无法直接计算，但是我们把上面的两个值完整的表示一下，带入 padding，于是我们有

Hash = sm3(secret)=sm3(secret||padding1)

NewHash = sm3(secret||append||padding2)

sm3 的一个分组是 128 字节，由于 MySecretInfo  是 64 字节，所以  padding1 就是 64 字节，padding2 就是 128 字节

那么解题思路就显而易见了：

由于 MySecretInfo 的 AppendData 长度都是 64，我们就可以根据 sm3 的填充规则分别计算出 padding1 和 padding2。

我们将 AppendData 设为 padding1，于是题目给出的 Hash 就是计算  sm3(secret||append||padding2) 第一组消息的哈希结果，同时也是第二组的 IV。第二组的明文即 padding2 我们也是已知的，于是也就能计算出 NewHash 了。

如果各位找到了 sm3 哈希拓展攻击的轮子，记为

def sm3_hash_ext(salt_len,known_msg,known_hash,append_msg):
 ...
 return newmmsg,newhash

那么只需要如此运行

newmsg,newhash = (sm3_hash_ext(64,"",known_hash,""))

已知消息和附加消息留空即可

交互里给到服务端的 AppendData 就是本地计算出的 padding1=80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200

（PS：针对哈希拓展攻击，有一个比较简单的防御方法，就是将盐值加在消息后面计算哈希，即 value=hash(msg+salt)）

trivial_RSA

from Crypto.Util.number import * 
from sage.all import *
from random import randrange
from secret import flag

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
r = bin(getPrime(len(flag)))[2:]
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
a = randrange(1, n)
c = (pow(m-pow(a,e,n), d, n)) % n
z = sum([int(r[i])*a**i for i in range(len(r))])
assert z < a**15 + 1
z = z % n

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f'z = {z}')

# n = 18958523822965779912899827783107438587572040487657111002474465900654251879648263776126782079490757516910092179229455697277114063200369560902566011503634573360990937108599191248791849618222649751050364361142600937548721273695606870531223115536894668583705065413241189513987778142820106936724774404027632297204326276900214510048550175919812310454623719455076518243383150380368352788245272891910180838780789265307926922228219671680149003036378499914252991087458570463044465887439954979441914227099761352286375336573082314068827094531345166273341200406447201114205915685170884295487124853039513234346915988003083904836693
# e = 65537
# c = 7686325199783272501572663174944755197791969370073187592251283865295440441060782400934009069787663356292165611134077915144925528467882885709675333515694288666120491594067996922521358065728072307779844654129380190278856814240484104370146630764792937658249106660318159393183856951836389587053477192829545069963314314238475766679268156189975051160344008244559582485586459952479020733368116753984144655302562187636209261364527605350759877694549049990708347877181830797691918826618366455511891171006294630191265136416467827504525021358151857386350805405256624532016401764802206666925927135797484939694162365798975882694400
# z = 17950614509301690602331343526239959553361375297339190587035556501079164302293518648188343348695236634911677063321150112475964510884955885124571880690217875346815645822477251375686977571543320490617041697266656309287159844665671440176711392792168744385352881631876228518237664899306901002781611277601364328780219360646320253657773434189290477727573012009061692650151046975693283805592667681572001657620919743316515115813954895134531216761690636659433546138824119350927121917046759668488138718761936764212549027785798985119280676435812256960695225986500366400430644284664200908678552035575318170314847737926483287943789

短短的代码，大大的折磨。

根据题目信息，我们有已知两个等式

一个直观的想法是，通过爆破 ，然后使用 把 给求出来，然后计算 就可以得到 了。

可惜，这个 并不小，似乎没有什么办法能求出来。

那么，能消了它么？

可以参考之前公众号的这道题目 ，

我们爆破 ，然后对两个式子做一个结式，即式子

把变量 给消除。由于 是一个比较小的值，只有 15 个字节，除去 flag{} 就只剩 9 个字节了，走一个 coppersmith 兴许就行了。（不过由于 比较大，所以得先求一个 才方便做结式）

理论成立，实践开始。

首先我们假设 已知，然后先测一下什么要的参数能够 copper 出 来

from Crypto.Util.number import * 
from random import randrange

flag = b"flag{" + b"a"*9 + b"}"
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
r = bin(getPrime(len(flag)))[2:]
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
a = randrange(1, n)
c = (pow(m-pow(a,e,n), d, n)) % n
z = sum([int(r[i])*a**i for i in range(len(r))])
assert z < a**15 + 1
z = z % n

# test_exp
R.<a,m>=PolynomialRing(Zmod(n))   

# assume r is known
r = r 

# construct g
g = sum([int(r[i])*a**i for i in range(len(r))]) - z

# cuz f = m - a^e - c^e 
# fast pow calc a^e % g 

asist = a
a_e = 1
for i in bin(65537)[2:][::-1]:
    if i == '1':
        a_e = (a_e*asist)%g
    asist = (asist*asist)%g


# construct f
f = m*256 + bytes_to_long(b"flag{x00x00x00x00x00x00x00x00x00}") - a_e - pow(c,e,n)

# calc resultant using sylvester_matrix
h = f.sylvester_matrix(g, a).det().univariate_polynomial().monic()
tmp = h.small_roots(X=2**72,epsilon=0.07)
if tmp:
        print(tmp[0])

经过测试当调到 epsilon = 0.07 时我们能求出 来，

然后我们拿题目的参数，爆破一下 就行。为了减小爆破复杂度，我们注意到 是一个 15 比特的素数，所以我们打一个表

from sympy import nextprime
R = []
r = 2**14
while r<2**15:
    r = nextprime(r)
    R.append(r)
    

估计一下运行时间

from tqdm import *
for each in tqdm(R):
    r = bin(each)[2:]

    # construct g
    g = sum([int(r[i])*a**i for i in range(len(r))]) - z

    # cuz f = m - a^e - c^e 
    # fast pow calc a^e % g 

    asist = a
    a_e = 1
    for i in bin(65537)[2:][::-1]:
        if i == '1':
            a_e = (a_e*asist)%g
        asist = (asist*asist)%g

    # construct f
    f = m*256 + bytes_to_long(b"flag{x00x00x00x00x00x00x00x00x00}") - a_e - pow(c,e,n)

    # calc resultant using sylvester_matrix
    h = f.sylvester_matrix(g, a).det().univariate_polynomial().monic()
    tmp = h.small_roots(X=2**72,epsilon=0.07)
    if tmp:
            print(tmp[0])

得到

  0%|          | 2/1613 [00:24<5:38:17, 12.60s/it]

麻了呀，由于 epsilon 太小，copper 太慢了，一个都要 12 秒，一千多个得要五个小时。

比赛的时候是直接暴力开了多个窗口，手动多进程的在爆破。赛后想想看看怎么写一个多进程呢，每次都手动也不是个事儿。

突然想起来有一些交互题目会有一个 PoW，然后我每次都会用下面的板子去过

from pwn import *
sh=remote("","")
from pwnlib.util.iters import mbruteforce
from hashlib import sha256


def proof_of_work(sh):
    sh.recvuntil("XXXX+")
    suffix = sh.recvuntil(')').decode("utf8")[:-1]
    log.success(suffix)
    sh.recvuntil("== ")
    cipher = sh.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==  cipher, string.ascii_letters + string.digits, length=4, method='fixed')
    sh.sendlineafter("Give me XXXX:", proof)

proof_of_work(sh)
sh.interactive()

那能不能用这个 pwntools 带的 mbruteforce 呢？翻一下源码

根据函数 def mbruteforce(func, alphabet, length, method = 'upto', start = None, threads = None)

func 应该是要爆破的函数，我们这里把 for 循环下面的代码打包一下；alphabet 就是表，我们这里就是 R ；length 应该是取表的几个元素，我们这里就是 1 ；method 应该是 fixed，因为我们的表固定的。于是有

def burce_r(each):
    r = bin(each)[2:]

    # construct g
    g = sum([int(r[i])*a**i for i in range(len(r))]) - z

    # cuz f = m - a^e - c^e 
    # fast pow calc a^e % g 

    asist = a
    a_e = 1
    for i in bin(65537)[2:][::-1]:
        if i == '1':
            a_e = (a_e*asist)%g
        asist = (asist*asist)%g

    # construct f
    f = m*256 + bytes_to_long(b"flag{x00x00x00x00x00x00x00x00x00}") - a_e - pow(c,e,n)

    # calc resultant using sylvester_matrix
    h = f.sylvester_matrix(g, a).det().univariate_polynomial().monic()
    tmp = h.small_roots(X=2**72,epsilon=0.07)
    return tmp != []

proof = mbruteforce(burce_r, R, length=1, method='fixed')

可惜报错了

def sm3_hash_ext(salt_len,known_msg,known_hash,append_msg):
 ...
 return newmmsg,newhash
0

看样子表里的元素需要是字符串，为了不改源码，我们改一下自己的数据叭

def sm3_hash_ext(salt_len,known_msg,known_hash,append_msg):
 ...
 return newmmsg,newhash
1

可行！

跑一下题目数据，看看用时如何

def sm3_hash_ext(salt_len,known_msg,known_hash,append_msg):
 ...
 return newmmsg,newhash
2

4 核虚拟机仅耗时 15 分钟！