2024VNCTF

crypto

basiccry

import random 
from Crypto.Util.number import *
flag = b'********************************'
m = bytes_to_long(flag)

rr = matrix(ZZ,[random_vector(ZZ,256,0,2) for _ in range(256)])
mm = matrix(GF(2),[list(bin(m)[2:].rjust(256,'0'))]*256)
cc = mm+rr
ii = vector(ZZ,input("Undoubtedly, this is a backdoor left for you: ").split(","))
dd = rr*ii

print(cc)
print(dd)

根据题目中给的向量矩阵关系，dd=rr * ii，由于rr是01矩阵，ii是向量，那么可以看作是一个背包，ii作为公钥，得到256组加密结果，因此传一组超递增序列后即可通过一个dd得到一行rr，和cc对应行做减法就可得mm。

from Crypto.Util.number import *
r0 = ""
dd0 = 57899155721916261937717848836826880284444156537796259966393107788286965549457
ii = [pow(2, i) for i in range(256)]
for each in ii[::-1]:
    if dd0 >= each:
        r0 += '1'
        dd0 -= each
    else:
        r0 += '0'

r = [int(x) for x in r0[::-1]]
c=[]
cc="1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0"
for i in range(0,len(cc),2):
    c.append(int(cc[i]))
for i in range(256):
    print((c[i]-r[i]) % 2, end="")

x=0b0101011001001110010000110101010001000110011110110100100000110100010111110101111100110001011011100110011101110111010111110101111101100111011010000111010001011111011100110110100101101101011100000011000001011111010111110011010001101110011101000010000101111101
print(long_to_bytes(x))
# VNCTF{H4__1ngw__ght_simp0__4nt!}

SignAhead

from secrets import token_bytes
from hashlib import md5
from secret import flag

ROUNDS = 100

successful_forge = 0

for i in range(ROUNDS):
    print(f'Round {i}')

    key = token_bytes(32)
    msg = token_bytes(64)

    sign = md5(key + msg).hexdigest()

    print('msg:', msg.hex())
    print('sign:', sign)

    print('FORGE ME!!!!')

    newmsg = bytes.fromhex(input('msg: '))
    newsign = input('sign: ').strip()

    assert msg != newmsg

    if md5(key + newmsg).hexdigest() == newsign:
        print('GREAT JOB')
        successful_forge += 1
    else:
        print('you failed!')

if successful_forge == ROUNDS:
    print('Here is your reward:', flag)
else:
    print('try harder next time !')

哈希长度扩展攻击，用hashpumpy库(python3.10报error，3.9报warning>_<)

import hashpumpy
from hashlib import md5
from pwn import *
import re

io=remote("manqiu.top","21247")
context.log_level = 'debug'
for i in range(100):
    content=io.recvuntil(b'FORGE ME!!!!').decode()
    msg=re.findall(r'msg\: ([0-9a-f]*?)\n',content)[0]
    sign=re.findall(r"sign\: ([0-9a-f]*?)\n",content)[0]
    data1=bytes.fromhex(msg)
    result=hashpumpy.hashpump(sign,data1,b'\x01',32)
    io.recv()
    io.sendline(result[1].hex().encode())
    io.recv()
    io.sendline(result[0].encode())
print(io.recv())

basiclog

import signal
import os
import sys
import random
flag = "************************"


def timeout(*args):
    sys.exit(0)


q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2
assert q*2+1 == p

x = random.getrandbits(48)
y = pow(g, pow(g, x, q), p)
print(y)
print(x)
try:
    _x = int(input('> '))
    if x == _x:
        print(flag)
    else:
        print("Error...")
except:
    exit(0)

题目给的p、q都比较安全，结合题目关键点y = pow(g, pow(g, x, q), p)考虑进行BSGS拆分。 \[ y = g^{g^x}\;mod\;p \] \[ g^{g^x} \equiv g^{g^{i+j*\sqrt{n}}}\;mod\;p \] \[ y^{g^{-i}} \equiv g^{g^{j*\sqrt{n}}}\;mod\;p \] 也是根据常规dlp的思路进行的推导，接下来就分别遍历i、j求得左右集合，从而找到满足等式的i、j。

在实际操作时，求一个集合需要大概15min，但是发现右集合与y无关，可以先求出右集合后再去连接远程求左集合。

from tqdm import tqdm
from pwn import *
g = 2
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
q = (p-1) // 2
rr = {}
for j in tqdm(range(2**24)):
    r = pow(g, pow(g, j * 2**24, q), p)
    rr[r] = j
print("finish")

io=remote("manqiu.top","20203")
context.log_level = 'debug'
y=int(io.recvline().decode())
io.recvuntil(b'> ')
print(y)

for i in tqdm(range(2**24)):
    l = pow(y, pow(g, -i, q), p)
    j = rr.get(l)
    if j is None:
        continue
    x=j * 2**24 + i
    break
print(x)
io.sendline(str(x))
print(io.recvline())