hash_append
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
短短的代码，大大的折磨。
根据题目信息，我们有已知两个等式
一个直观的想法是，通过爆破 ，然后使用 把 给求出来，然后计算 就可以得到 了。
可惜，这个 并不小，似乎没有什么办法能求出来。
那么，能消了它么？
可以参考之前公众号的这道题目 好题分享系列 – 2023 江苏省数据安全竞赛 – hardrsa，
我们爆破 ，然后对两个式子做一个结式，即式子
把变量 给消除。由于 是一个比较小的值，只有 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')
可惜报错了
Process Process-8:
Traceback (most recent call last):
File "/usr/lib/python3.11/multiprocessing/process.py", line 314, in _bootstrap
self.run()
File "/usr/lib/python3.11/multiprocessing/process.py", line 108, in run
self._target(*self._args, **self._kwargs)
File "/home/kali/Desktop/sage-10.0/local/var/lib/sage/venv-python3.11/lib/python3.11/site-packages/pwnlib/util/iters.py", line 849, in _mbruteforcewrap
res = bruteforce(func, alphabet, length, method=method, start=start, databag=databag)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/kali/Desktop/sage-10.0/local/var/lib/sage/venv-python3.11/lib/python3.11/site-packages/pwnlib/util/iters.py", line 827, in bruteforce
cur = ''.join(e)
^^^^^^^^^^
TypeError: sequence item 0: expected str instance, int found
看样子表里的元素需要是字符串，为了不改源码，我们改一下自己的数据叭
def burce_r(each):
r = bin(int(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 != []
Rstr = [str(i) for i in R]
proof = mbruteforce(burce_r, Rstr, length=1, method='fixed')
可行！
跑一下题目数据，看看用时如何
from Crypto.Util.number import *
from random import randrange
from pwnlib.util.iters import mbruteforce
n = 18958523822965779912899827783107438587572040487657111002474465900654251879648263776126782079490757516910092179229455697277114063200369560902566011503634573360990937108599191248791849618222649751050364361142600937548721273695606870531223115536894668583705065413241189513987778142820106936724774404027632297204326276900214510048550175919812310454623719455076518243383150380368352788245272891910180838780789265307926922228219671680149003036378499914252991087458570463044465887439954979441914227099761352286375336573082314068827094531345166273341200406447201114205915685170884295487124853039513234346915988003083904836693
e = 65537
c = 7686325199783272501572663174944755197791969370073187592251283865295440441060782400934009069787663356292165611134077915144925528467882885709675333515694288666120491594067996922521358065728072307779844654129380190278856814240484104370146630764792937658249106660318159393183856951836389587053477192829545069963314314238475766679268156189975051160344008244559582485586459952479020733368116753984144655302562187636209261364527605350759877694549049990708347877181830797691918826618366455511891171006294630191265136416467827504525021358151857386350805405256624532016401764802206666925927135797484939694162365798975882694400
z = 17950614509301690602331343526239959553361375297339190587035556501079164302293518648188343348695236634911677063321150112475964510884955885124571880690217875346815645822477251375686977571543320490617041697266656309287159844665671440176711392792168744385352881631876228518237664899306901002781611277601364328780219360646320253657773434189290477727573012009061692650151046975693283805592667681572001657620919743316515115813954895134531216761690636659433546138824119350927121917046759668488138718761936764212549027785798985119280676435812256960695225986500366400430644284664200908678552035575318170314847737926483287943789
# test_exp
R.<a,m>=PolynomialRing(Zmod(n))
from sympy import nextprime
R = []
r = 2**14
while r<2**15:
r = nextprime(r)
R.append(r)
def burce_r(each):
r = bin(int(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 != []
Rstr = [str(i) for i in R]
import time
start = time.time()
print("Start mbruteforce...")
proof = mbruteforce(burce_r, Rstr, length=1, method='fixed')
print(time.time() - start)
4 核虚拟机仅耗时 15 分钟！
原文始发于微信公众号（Van1sh）：2024 数字中国积分争夺赛预赛
