Writeup for Crypto Problem in 2022春秋杯

抽时间打了一波i春秋的比赛，赛题出的都挺不错的，两组都有一道比较难的题，把wp写一下也算是学习一波了

Train

题目本意是找到自定义哈希函数的一个碰撞，但是出题人忘了过滤相同字符的情况，hhh

hash

def TrainHash(msg):
    n = n0
    msg = map(ord,msg)
    for i in msg :
        n = g * (n+i)
        n = n & (1<<383)
    return n - 0xf5e33dabb114514

collision

if TrainHash(string1) == TrainHash(string2):
    self.send(b'\nJust do it!~ You can do more!')
    if string2.encode()[-50:] == string1.encode()[-50:]:
        self.send(flag)

我们考虑将hash函数展开，设碰撞明文ascii码序列为及

最简单的想法肯定是明文长度一致设为l

只需满足

还需使得最后50位的t和s相同

最后一列把权重加上优先规约即可

找LLL规约后前50各分量绝对值不大于80的就差不多够了

n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 64146569863628228208271069055817252751116365290967978172021890038925428672043
mod=2^383
A=[]
for i in range(50):
    A.append(pow(g,50+i,mod))

L=Matrix(51,51)
for i in range(50):
    L[i,50]=2^50*A[i]
    L[i,i]=1
L[50,50]=2^50*2^383
L=L.LLL()
print(L[1])

ascii码范围搜索碰撞对

deta=(-62, -28, 6, 54, 62, 65, 8, 15, -27, -13, -55, -15, 34, 34, -46, 0, 0, 33, -4, -70, -30, 54, -10, -50, 33, -55, -73, 76, -5, -31, 17, 36, 77, -37, -35, -9, 53, -27, -42, 26, 24, 18, -55, -5, -17, 55, -42, 14, 17, 0, 0)
s1=''
s2=''
for i in range(len(deta)):
    for j in range(40,126):
        if 40<(j+deta[i])<126:
            s1+=chr(j)
            s2+=chr(j+deta[i])
            break
t1=s1+'a'*50
t2=s2+'a'*50
print(t1)
print(t2)

bob’s enc

简单求解矩阵和简单lwe

虽然网上脚本一堆，赛后还是自己写了一个，这里稍微说一下格的构造，实际上和求解GGH的时候差不多只是最后带了个模p

对于

A为m×n矩阵，构造P为m×m对角阵(对角元素为p)

对进行规约

再对L求gram正交基，调babai算法即可

解矩阵方程

key = 
q=
c1=
A=Matrix(Zmod(q),key)
print(bytes(list(A.solve_right(c1))))

求解lwe

由于系数都比较小我直接用的最朴素的babai算法，更糟糕的情况下可以考虑使用最近平面算法

m = 64
n = 21
q = 2141

A = 
A=Matrix(GF(q),A)
c2 = 

L=Matrix(ZZ,m+n,m)
for i in range(m):
    for j in range(n):
        L[j,i]=A[i][j]
for i in range(m):
    L[n+i,i]=q

def babai(A, w):
    A = A.LLL()[21:]
    G = A.gram_schmidt()[0]
    t = w
    for i in reversed(range(A.ncols())):
        c = ((t * G[i]) / (G[i] * G[i])).round()
        t -= A[i] * c
    return w - t

v_e=vector(ZZ,c2)
v=babai(L,v_e)
print(bytes(list(A.solve_right(v))))

notKnapsack

比赛的时候想偏了，因为之前记得RCTF2019也出过一个乘法背包通过代数系统的同构转化为加法背包

实际上不能原封不动地按照之前乘法背包的想法进行解决，因为此处题目给了多组利用同一私钥的加密结果，但是我们可以利用rctf那题取生成元的想法，只不过我们取的生成元生成的乘法群的阶不需要太大因为我们有足够的方程组约束出正确的解

赛后询问Hermes最简单的方式是直接采用勒让德符号也就是找二阶的乘法群即可

from Crypto.Util.number import *
def add(a,p):
    if pow(a,(p-1)//2,p)==1:
        return 1
    else:
        return 0

f=open('output.txt','rb')
q = 210767327475911131359308665806489575328083
out=eval(f.read())

A=Matrix(GF(2),len(out))
v=vector(GF(2),len(out))
for i in range(len(out)):
    t1,t2=out[i]
    for j in range(len(t1)):
        A[i,j]=add(t1[j],q)
        v[i]=add(t2,q)+1

m=A.solve_right(v)
m=''.join(map(str,m))
print(long_to_bytes(int(m,2)))

TrainPlus

魔改了md5过程的哈希长度拓展攻击，之前CCTF也有一道只不过那个就是用的md5和sha1，直接扔hash_extender里解了，这里还得审计代码，比赛的时候以为只是改了md5幻数，结果dbt出题目的时候把padding也改了

原本md5在padding成512k+448时是10…00式的padding现在是11…11式padding，┭┮﹏┭┮

在具有MD结构的散列函数上都会存在长度扩展攻击

举个例子就是在已知md5(key)以及key长度的情况下计算md5(key||message)，这里message可控

这似乎一眼看上去是不太可能实现的，因为我们知道md5是具有单向性的也就是我们没法通过md5(key)还原key，那如何得到md5(key||message)，那就得利用md5的padding过程以及它的md结构实现在已经计算好key+padding+len的基础上接着计算我们的message

因为本人太懒了就不自己实现了~~太菜了写不好~~

最后贴上dbt的代码

exp