vnctf2023

总的来说，basiccry是不难的，sign_ahead是比较套路化的，basiclog有点意思。
sign_in是没时间看而且看不懂的。

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)

$rr$和$mm$都是{0，1}数组,$cc=rr\oplus mm$

$ii$是你输入的一维数组，输出$rr*ii$

分析

很容易把这个联系到backpack问题，还是让我们构造backpack。

那我们可以构造很特殊的backpack

$ii=[1,2,4,8,…..]$

那么就有$rr$了，有$rr$之后$mm$也就出来了。

exp

from pwn import *

s = 0
a = []
# 这儿是将思路中构造的数组reverse了，本质一样
# 这样后续操作简单一点
for i in range(256):
    a.append(1 << (255 - i))
o = ",".join(map(str, a))

IP, PORT = "manqiu.top 20765".split()
conn = remote(IP, PORT)
print(conn.recvuntil(b"r left for you: "))
conn.sendline(o.encode())
print(conn.recvline().decode())

for i in range(255):
    conn.recvline().decode()
print(conn.recvline().decode())

将输出的$cc$第一行，和与之对应$rr*ii$的第一个答案拿出来。其实哪一行都一样，对应好就行

from Crypto.Util.number import *

a = "1 1 0 0 ....."
a = a.replace(" ", "")
a = int(a, 2)
m = ....

print(long_to_bytes(m ^ a))

basiclog

题意

q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2
y = pow(g,pow(g,x,p),q)
print(y)

求 x

分析

也就是$2^{2^x\ mod\ p}=y\ mol\ q$

首先注意$\phi(q) = 2*p$

然后就猜测指数处对p取模不影响结果，多选取几个x发现确实成立。

于是虽然距离证明差简单一步，但这个结论我就直接拿来用了。

猜测此处需要平方处理

$$y^2 = (2^{2^{x}})^2 = 2^{2^{x}*2} = 2^{2^{x+1}} $$

为方便叙述，我们设$y = f(x)$, $x = f^{-1}(y)$

由上面的式子我们就知道

$$f^{-1}(y) = f^{-1}(y^2)-1$$

然后这是可以一直迭代下去的

$$f^{-1}(y) = f^{-1}(y^2)-1=f^{-1}(y^4)-2=f^{-1}(y^8)-3=….$$

一直写下去什么时候结束呢。我们可以先打弄一个字典dic来打表，当y的值出现在表中的时候就结束，然后就能得到x

$x$是48bit的，那我们可以先均匀打$2^{24}$个点，然后那么y就大约需要迭代$2^{24}$次就可以出答案

exp

dic = {}

# 按照上面的思路应该是N1 = N2 = 2**24，但是实际
# 操作下来打表建立字典很慢，而其实迭代的过程相对
# 较快，于是就调整了N1，N2的大小，最后3min跑完。

N1 = 2**19 
N2 = 2**29
g1 = pow(g, N2, q)
print(q.bit_length())
print(p.bit_length())
for i in range(N1 - N1 // 1, N1):
    if i % (2**16) == 0:
        print(i)

    tmp1 = pow(g1, i, q)
    y = pow(g, tmp1, p)
    dic[y] = i * N2

def brute(y: int):
    for i in range(N2):
        if y in dic:
            x = dic[y] - i
            break
        y = (y * y) % p
    else:
        x = 0
        print("not found")
    print(x)

y =  ...

print(brute(y))

sign_ahead

题意

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
    

已知msg和md5(key+msg)，任意找一个newmsg和其对应的md5(key+newmsg)

分析

Sign in Please

前不久做的某题的题解，看懂那题的思路就可以直接拿来套这题，那题当时的加密是sha256,本题是md5，但本质是一样的。

首先要去找md5的py实现md5-implementation.py，然后和那题一样稍微修改一下，修改其中的my_md5函数，增加pads=False的选择和hash初始值的设置

def md5(message,pads = True,hash_pieces = None):
 
    message = bytearray(message) #copy our input into a mutable buffer
    orig_len_in_bits = (8 * len(message)) & 0xffffffffffffffff
    if pads:
        message.append(0x80)
        while len(message)%64 != 56:
            message.append(0)
        message += orig_len_in_bits.to_bytes(8, byteorder='little')
    else:
        while len(message)%64 != 0:
            message.append(0)
    if hash_pieces == None:
        hash_pieces = init_values[:]
    ...

然后其实基本已经出了，细节见下文注释

exp

def to_hash_array(m:str)->list:
    arr = [bytes.fromhex(m[i:i+8]) for i in range(0,len(m),8)]
    return list(map(lambda x:int.from_bytes(x, byteorder='little'),arr))

def attack_md5(msg:str,sign):
    key = b'\0'*32
    msg = bytes.fromhex(msg)
    hash = to_hash_array(sign)
    
    length1 = 96
    orig_len_in_bits = (8 * length1) & 0xffffffffffffffff
    message = bytearray(key + msg)
    message.append(0x80)
    while len(message)%64 != 56:
        message.append(0)
    message += orig_len_in_bits.to_bytes(8, byteorder='little')
    new_msg = bytes(message)[32:]
    # key + new_msg其实就是key + msg经过pad的结果

    # key + new_msg仍然需要经过pad。他有三个chunk。
    # 前两个chunk和key+msg的chunk一样，所以经过前两
    # 轮循环的hash_pieces其实就是sign。所以我们只需
    # 要对第三个chunk进行一轮循环就行，这里我将第三轮
    # chunk的内容放在message中，然后走一轮不要循环就
    # 行了。
    length1 = 128
    orig_len_in_bits = (8 * length1) & 0xffffffffffffffff
    message = bytearray(b"")
    message.append(0x80)
    while len(message)%64 != 56:
        message.append(0)
    message += orig_len_in_bits.to_bytes(8, byteorder='little')
    # print(message)
    new_sign = md5_to_hex(md5(bytes(message),False,hash))
    return new_msg.hex(),new_sign

# 这个有个坑是pwn和我找的md5函数里面都定义了constants
# 变量，直接import * 会有问题
from pwn import remote
IP,PORT = "manqiu.top:21072".split(":")
conn = remote(IP, PORT)
for i in range(100):
    conn.recvuntil("msg:")
    msg = conn.recvline().decode().strip()
    conn.recvuntil("sign:")
    sign = conn.recvline().decode().strip()
    new_msg,new_sign = attack_md5(msg,sign)
    conn.sendlineafter("msg: ",new_msg.encode())
    conn.sendlineafter("sign: ",new_sign.encode())
    print(conn.recvline())
print(conn.recvline())