Oven

1. Puzzle Description
2. Analysis
- 小技巧
3. EXP

1. Puzzle Description¶

题目地址： https://github.com/paradigmxyz/paradigm-ctf-2023/tree/main/oven

源码如下：

#!/usr/bin/env python3
from Crypto.Util.number import *
import random
import os
import hashlib

FLAG = os.getenv("FLAG", "PCTF{flag}").encode("utf8")
FLAG = bytes_to_long(FLAG[5:-1])
assert FLAG.bit_length() < 384

BITS = 1024


def xor(a, b):
    return bytes([i ^ j for i, j in zip(a, b)])


# This doesn't really matter right???
def custom_hash(n):
    state = b"\x00" * 16
    for i in range(len(n) // 16):
        state = xor(state, n[i : i + 16])

    for _ in range(5):
        state = hashlib.md5(state).digest()
        state = hashlib.sha1(state).digest()
        state = hashlib.sha256(state).digest()
        state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()

    value = bytes_to_long(state)

    return value


def fiat_shamir():
    p = getPrime(BITS)
    g = 2
    y = pow(g, FLAG, p)

    v = random.randint(2, 2**512)

    t = pow(g, v, p)
    c = custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))
    r = (v - c * FLAG) % (p - 1)

    assert t == (pow(g, r, p) * pow(y, c, p)) % p

    return (t, r), (p, g, y)


while True:
    resp = input("[1] Get a random signature\n[2] Exit\nChoice: ")
    if "1" in resp:
        print()
        (t, r), (p, g, y) = fiat_shamir()
        print(f"t = {t}\nr = {r}")
        print()
        print(f"p = {p}\ng = {g}\ny = {y}")
        print()
    elif "2" in resp:
        print("Bye!")
        exit()

代码功能：用户可以获取 FLAG 随机签名，生成随机签名的逻辑就在 fiat-shamir 函数里。使用了自定义的hash函数 custom_hash 来生成哈希，这个函数分别调用了四种不同的hash算法，因此想要破解其随机性目前是不可能的。

另外， Fiat Shamir 变换是密码学中非常重要的工具，它的核心在于使用hash算法来生成随机数，为密码协议添加了随机性。FS变换一个典型应用就是为零知识证明系统系统引入了非交互性，进而构造出 snark、stark 等协议。

从上述源码，我们可获得的信息有 t, r, p, g, y ，其实 c 是可以求出，即使用题目条件中的 custom_hash 函数。那么可能发生的漏洞点集中在 fiat_shamir 函数中，它是对 FLAG 进行签名的函数功能部分，重点关注： r = (v - c * FLAG) % (p - 1) 。对于这个式子，目前我们可以获得的信息有： r, c, p 均是已知值，且 FLAG 的位数已经确定： assert FLAG.bit_length() < 384 。可以联想到 Dan Boneh 在 1996 年提出的 HNP 问题（模数可变），可使用标准的格算法进行攻击。更加详细基于格攻击的密码分析请参考论文。

2. Analysis¶

问题就出在代码： \(r = (v - c * FLAG) % (p - 1)\) 上，由于 r，c，p均是已知值，于是：

首先对上述式子进行数学变形： \(r-v+c*FLAG=0\mod (p-1)\) ，只有 v 和 FLAG 是未知数。
我们可以根据上述式子构建 Lattice:

\[ M = \begin{pmatrix}(q_1-1)&&&&\\ &(q_2-1)&&&\\ &&(q_3-1)&&\\ c_1&c_2&c_3&1&\\ r_1&r_2&r_3&0&K\\ \end{pmatrix} \]

其中：

K 是 FLAG 的一个上界；
空白处均为 0 。
根据 Babai 的CVP解决算法，一定存在一个解向量 \(\pmb{j}=(l_1,l_2,l_3,FLAG,1)\) ，使得 \(\pmb{j}M=\pmb{j_k}\) 成立。
注意到 \(\pmb{j_k}\) 在格中是一个短向量，于是我们可以采用 LLL 算法在多项式时间内找到这个短向量。注意，短向量的每一个元素用 64bit 可以表示，于是确定上界 \(K=2^{64}\) 。

小技巧¶

这里解释一下数据量的问题，如何知道需要多少组数据可以恢复出 FLAG 呢？这个需要使用到 gaussian heuristic 估计最短向量长度，要求的目标向量范数小于这个长度即可。【但是由于这是CTF比赛背景，所以一般情况下可以先用三四五组数据，如果不行，在用上述方法精确计算。这里我先收集了5组数据备用，实际上用了3组数据，就可解出FLAG】。

3. EXP¶

完整EXP（需要sage-python环境）：

from Crypto.Util.number import *
import hashlib

def xor(a, b):
    return bytes([i ^^ j for i, j in zip(a, b)]) // 注意你的sage环境的异或操作运算符，这个sage10.0版本

def custom_hash(n):
    state = b"\x00" * 16
    for i in range(len(n) // 16):
        state = xor(state, n[i : i + 16])

    for _ in range(5):
        state = hashlib.md5(state).digest()
        state = hashlib.sha1(state).digest()
        state = hashlib.sha256(state).digest()
        state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()

    value = bytes_to_long(state)

    return value



g = 2

t, r, p, y = [0] * 5 , [0] * 5, [0] * 5, [0] * 5
t[0] = 77203516334611379622052884088061339907818193440975523438325956774518601252973654146535129884349539724229562993644509567711307331031087898034347437358013492439542334272757402388064753335866738748958633246857368058563448192261648964749496750146315450540579452655462143813022469489449782882109182150142188348915
r[0] = 116220687218790216091346463439819557695309512176282372943331613053767874084111192169275378671194392846117055362014832383093646731110903547936340541580638231783076185430700045752799252596702505486227877656990705143138976716233681199944248043915239678537679463030334043412573684866623347545004904612417007327217
p[0] = 120199526136097511651530856988060166616679725925744594620901500430819054365226668422844742178771316732438545888088210068701212930988908604238682153307940417480817112540019257024703372145496636861112290091005527647339212358159274475077103689996624113678044891963676612334769162753166782062809526104431258739517
y[0] = 113120257926989954605307518460817169666869094087243249194566086300779837721481071230484420555504633839932263287201776945834030877253212748181186108770595676114564711457140738635967367144272960236148346810327070118837330648022676963528356209004524421455348155068637534190736042536625876773755044593606026293621

t[1] = 41870694301936832255997763505666386906032641226067235004722895066736677752643938706563985367861597477876358530714740119529535551345537670465925209944735777464498665457291484991606280197421907773811941255514802343059520166452091324746732103649911088736843268706303230993742963740287185306251052313964374872878
r[1] = 12006544761341621619143613218949584457040818188588282396732221317912350712975184254483346994199077889478797005980544401923303196850089656891130607887735812677733676744158835380723268515678724429529904080449565289532493612340517128773817940478185157405384294596975266141639161297056291778600404606940053392754
p[1] = 144976418899543143198454834264506179459614866666312385853989423989111679486891620786778481577472101748200328617607483446519049911023390427543308348494008425688855119367843479385647790189753163858970088620586505610840306212549243890107847423807556106192434514110736278569625282073529181653986405771513594134987
y[1] = 115167386542298909971939136044531943159982371048242494889745996527683250097061534781946312891817534916886291355204474301571862159042350976750824212346443402817552375266223638549309886922860921533308382456941718605370216473858986207878047206914813902333192745354148659984602740644345120423788258359941122554440

t[2] = 87583398382601313926735945950364130572816213989909728661491063393166341618362097121819023078210854251839415225428442334046015192711593400640556960974162962105001700930842075200923675422451049033428478754684678493480503204152097382431043129863362081278994409790477935899740897031656629902670114002180266872266
r[2] = 102934065416140965550261549535302192284582871606378190882003659362832329206469482926448881926648454509204767788745574969527319053553977362277660636749471357711849435384231867496681956889560719871615670691536165668156919285052370364456208767031233707532145718791283351837119192545712583721765194876277656314501
p[2] = 148550372281025138704553107737801144273208690400094973764375300381759456124146034135721454543469874579375457504983315183916592877731262163382903701414433532933994780412246010260680217160047355295328211970740422311833479381733781665221952277321615395653804905426059251551309558237245071919868160643681548296643
y[2] = 140198181685722792932050421128846820269664976993249152496309458637445728558822919357043381776927596511506695168631000635135982453895569864162220417018046902591680662347467431250148020323787868422484882819040766008876291088199475630773774170507517261352416744218315033367149608507518388781373699289693595499544

t[3] = 84522638373733120165414722745998118253921972157096808350845007682435315263298662575419222718886673005893479175168776223733676055437884841441137160382376309254755315837431162807596684224207280410300146602535834124511928134257346386899792746556440632650091111389088724071203568000188430042064500145669267026805
r[3] = 18194520459417696159241442307764982202112775710358263541565999857475375951014745782344717997571109484480490257320469370655821185611675102820226656623202547826938945675557174044055104570245311622199906030109190773202049867448625926033119474090713737736579814394048548084259404911639299693897437586858871472420
p[3] = 103592121279236435866010649601463899558315038309765463516665073413464806869884601040096405354399740035138081866812671953467986059509640644754973422603659825874707510675199511411437487386173194105311776020901134014680450244319046258962912483163270496586124101308664731409973532774829535980996775736651508448187
y[3] = 14795900031448786771559087453548388682769488350377145090464794455644462363656204398769939585810191748312766604278524960492756615478207654208905403516432929452543777164921589629460212814049479518397521600744701463005793924336243982001830978693343863219168046923285752069874971698699611717027496799587761203398

t[4] = 137831113158715069584199906447354477289195801883097400523644937444161950367086728510388467524069532778534704803863447302183665431906725284462350375136938902398115607751357373983532375894744842377064414618294084293556345908653608825144019924463160996581138334794345538184522294219836499291245958693984828705682
r[4] = 3997479613798995088324714249284251759517244566415954213469045459939167234231804927756343425727094668124791771030709612850292188541459113635924389128360073088700133564458353848851347410209029075825332791761713207287049093830610503236793718093861017715600469118069736180200062407135030791797264421955154056362
p[4] = 138872772594377036406739890812487312629206229880091799534033353266413752242871671695030657233827552372256865312690361457743622953282647882392520626248323032818493170021525093526571072858177665184977821075559705014261503440906447428819858532553737164369106583570452357928945241596555378143414688075425304805029
y[4] = 26528279589882510502916765470759890048295757018825608100058824483278181810141819962488106009190787416456734047325734614749916264837565765983213768504298640943869226245566784325431289650031372028094050672872660334951958006567067601586551947694563576820491204290496425885685101313332190690230962899252834723225

i = 0
C = [0]
R = [0]
while i < 5:
    C.append(custom_hash(long_to_bytes(g) + long_to_bytes(y[i]) + long_to_bytes(t[i])))
    R.append(r[i])
    i += 1

C = C[1:]
R = R[1:]
# print(C)
# print(R)

M = matrix(ZZ, 5, 5)
for i in range(3):
    M[i, i] = p[i]
    M[3, i] = C[i]
    M[4, i] = R[i]
    M[i, 3] = M[i, 4] = 0
M[3, 3] =  1
M[4, 4] = 2^64
M[3, 4]= 0

v = M.LLL()[0]
print(v)
flag = v[3] % p[3]
print(long_to_bytes(flag))

最终的结果为： pctf{F1at_shAm1R_HNP_g0_Cr4ZyyYy_m0rE_1iK3_f4T_Sh4mIr}