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

WriteUp 5个月前 admin
217 0 0

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


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 字节

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

由于 MySecretInfoAppendData 长度都是 64,我们就可以根据 sm3 的填充规则分别计算出 padding1padding2

我们将 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 就是表,我们这里就是 Rlength 应该是取表的几个元素,我们这里就是 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 314in _bootstrap
    self.run()
  File "/usr/lib/python3.11/multiprocessing/process.py", line 108in 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 849in _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 827in 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')

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

可行!

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

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)

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

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


原文始发于微信公众号(Van1sh):2024 数字中国积分争夺赛预赛

版权声明:admin 发表于 2024年5月8日 上午10:38。
转载请注明:2024 数字中国积分争夺赛预赛 | CTF导航

相关文章