DubheCTF 2024 Crypto Writeups

2024-03-19

字数统计: 2.6k字 | 阅读时长≈ 14分

DubheCTF 2024 中 MDH（基于矩阵群的 DH 密钥交换）和 ezcrc （CRC 的代数表达式）的题解。

MDH

题目信息

from sage.all import *
from secret import flag
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import getPrime
from random import getrandbits


p = getPrime(256)
G = Zmod(p**3)
M = Matrix(G,[G.random_element() for i in range(64)],ncols=8)
a = getrandbits(560)
b = getrandbits(560)
S = M ** (a * b)


key = sha256(S.str().encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()


with open("output.txt", "w") as f:
    f.write('p = ' + str(p) + '\n')
    f.write('M = ' + str(list(M)) + '\n')
    f.write('Ma =' + str(list(M**a)) + '\n')
    f.write('Mb = ' + str(list(M**b)) + '\n')
    f.write('ct = 0x' + ct)

题解

基于矩阵群的 DH 密钥交换，只要能求解矩阵离散对数，这题就迎刃而解了。可以参考 The Discrete Logarithm Problem in Matrix Groups 以及 The Discrete Logarithm Problem in GL(n, q) 两篇文献。它们详细阐述了如何基于若尔当标准型分解 $M = P J P^{-1}$ 将矩阵离散对数问题转换为有限域上的离散对数问题。

本题矩阵未定义在有限域上，而是 $\mathbb{Z}_{p^3}$ 上，并且矩阵不可逆，部分特征值未定义在 $\mathbb{Z}_{p^3}$ 上，这就导致了这题不能直接用若尔当标准型来做。了解若尔当标准型中的数学内核，这题可以直接从矩阵特征多项式的根来做。给定矩阵 $A \in \mathbb{F}^{n \times n}$ ，其特征多项式的本质就是：

$\rm p_A(x) = \bf{det} (xI - A)$

从定义不难得到：特征多项式的根就是矩阵的特征值，而根据若尔当标准型在扩域上的分解形式，矩阵特征值会保持幂同态，即 $M$ 的一个特征值 $\lambda$ ，在 $M^x$ 中对应的特征值就是 $\lambda^x$ 。因此我们同样可以把矩阵离散对数降级到它元素有限域上的离散对数问题。而 $\mathbb{Z}_{p^3}$ 上的离散对数在本题的场景下是简单的（ $x \le 2^{590}, p.nbits() = 256$ ），详细请参考笔者另外两篇博客：

矩阵离散对数规约问题可以参考博客基于特征值的矩阵 DLP。
整数环 $\mathbb{Z}_{p^3}$ 上的离散对数问题可以参考博客 Discrete-Logarithm-Over-Z-p-r。

Exp

Sage EXP

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from output import p, M, Ma, Mb, ct
p = 79008119711208495443423312926395331665944721527891616265679009115440018598629
Gp3 = Zmod(p^3)
M = matrix(Gp3, M)
t = randint(1, 2^560)
Mt = M^t
Ma = matrix(Gp3, Ma)
Mb = matrix(Gp3, Mb)

print(t)
print(f"f[x] := {M.charpoly()};")
print(f"g[x] := {Ma.charpoly()};")
print(f"h[x] := {Mb.charpoly()};")
print(f"ft[x] := {Mt.charpoly()};")

def binomial_dlog_sub(y,g,p,q,r=2):
    C = ZZ(pow(y, q, p^r))
    B = ZZ(pow(g, q, p^r))
    kx = (C - 1)//p^(r-1)
    k =  (B - 1)//p^(r-1)
    x = ZZ(kx * pow(k, -1, p) % p)
    return x

def binomial_dlog(y,g,p,q,r):
    # solve y = g^x \mod p^r where q=phi(p) such that g^q = 1 \mod p
    assert r >= 2
    y = ZZ(y)
    g = ZZ(g)
    xs = []
    for i in range(r-1):
        xi = binomial_dlog_sub(y, g, p, q, i + 2)
        xs.append(xi)
        y = ZZ(y * pow(g,-xi,p^r) % p^r)
        g = ZZ(pow(g,p,p^r))
    return ZZ(xs, p)

x0 = 371400036118087873423099736623135345907801208559021371167756375819427925457040761043671101071645449151098283672036345482928921105303474546205199698226967922594539121528410724439325649997319457455755409700098207768114873790937028312
x1 = 407962438778688190907253749251184015390900029410795727241330663524055399813222240683911556296466108640007883599111746506669376054290340161271688994440216754019475823593004413780334836609175487467226663558545269470313125327004442075
y0 = 0
y1 = 94677558707295712242090997386462549942626176729545589690797827556684121785602596433846894851887708797985968631940880045924727539798391064801973678296817051938196633805006754526493164114864007544162629920939963968396975696320276490

a0 = binomial_dlog(y1, x1, p, p-1, 3)

Zp = GF(p)
Zp3 = Zmod(p^3)

p1 = 2^2 * 11 * 1399 * 576647 * 707717 * 31455197 * 99986015309131554073222673357191122700463502810799771
mul = 99986015309131554073222673357191122700463502810799771

Y = Zp(Zp3(y1)**(p^2))^mul
base = Zp(Zp3(x1)**(p^2))^mul

a1 = Y.log(base)
a = crt([int(a0), int(a1)], [p^2, base.multiplicative_order()])
mod = ZZ(p^2 *  base.multiplicative_order())
print(ZZ(a).nbits())
while M^a != Ma and a <= 2** 590:
    a += mod
print(M^a == Ma)

S = Mb^a
key = sha256(S.str().encode()).digest()
ct = AES.new(key, AES.MODE_ECB)
print(ct.decrypt(bytes.fromhex("b7df98ace3796355c2a3a9230760569b53814889e975fe2f50992b3e1683898d918ab7f392f80628b7a0dc3a43e854b7")))

其中 x0, x1, y0, y1 分布是矩阵 $M,M_a$ 的特征值，即 $f(x),g(x)$ 在 $\mathbb{Z}_{p^3}$ 上的两个根。可以在 sage 上先求 $f(x),g(x)$ 在有限域 $\mathbb{F}_{p}$ 上的根，再用 hensel lift 提升到 $\mathbb{Z}_{p^3}$ 上。这里我直接用 mathematica求解了：

mma 脚本

(* Define the coefficients and modulus *)
p := 79008119711208495443423312926395331665944721527891616265679009115440018598629;
(* Define the polynomial f in Z/pZ *)
f[x] := x^8 + 4093721904954649749606358934675410877292635281608771685862726636369665899324049086150200562854544440601246934938901527213598536175425903260985087743234878654868746038343801085190715017197498882769768591199871359795327990234738452*x^7 + 367404874475222387519073916907607961923077180133950813993464335269572747847813029278054827018133545487170438196450169909581908989309791181552180719538770868379479610175045121045846011951922292965503309708454446782292865326354321912*x^6 + 177334381872630257189629062824772654460770746386380579458039259995516290683569877558372571466169688824767087952270911510631825690238016500401661685288325571920772075384649686856653423431074103598988709403801098205856723623333681089*x^5 + 25191499168181107412437851008691236552090785169335778784797321829257870553430277472174832165558853630912648697448537008692742793725787528623900341901945473720349046980767934257022002486292212825598159144175849009096073120750110708*x^4 + 396146105968377561971413800203188312165286560688315616565875611261869359828317850466464787734547459646930894335610514896816087180411289857829908664253281532555182805130150257075264952976931524355114878698659788787262594603835518672*x^3 + 381138907203975870155852768799735039151665548460274957357873912957626986007659000764914336251584929202433067073068146179092633270125307617583862079189344893760630090246984172008202072467706057674857651545098447363477781867327938364*x^2 + 161260580627308331569341352068126494754224600502498963925722554030645210124389434053266166051019415845959899110109398619984901663335528783735605538278492621074006336756950889394251274080252889880009127570263041624925038033523029421*x + 413764393906813184792095848510130371922881920023911304091412811929182653159775620076043917208494157146619150259903492673279265236497447469592287019273944349330530789050819605174812787757614659885026798291564621732946375926375006296;
g[x] := x^8 + 357903988503903976310732651031359779456379849522196653774615909583867474471617134302475726478216182145155130774807507683294704460917948858573155532471596800225612292578085080007681631917945693197958570787234880779035256523087088146*x^7 + 311636578648508530239910773146241316877102755967447686380563068290147162450253521576340879246066824085062939261435498362155810709871154439293375633684590378626012386323072575201423052458514067266623020807167337805350680795210821820*x^6 + 117015207887053032786663797141866564004058600362253644593264858884056606550611109995332728807188414704268152220580397456546906528851625435103021586071494073587676639916393933478813286647474108554658766482331742501554836405007837375*x^5 + 224342411932397217007619412289303423058762311626908283822307925570940590311213986659094339000758599105468045261488350030708622179712449074336442353775805174995452840694623971152908201182742816937866830213548088951630800788388434305*x^4 + 120930329003423380859670636895907754542373341576407870509476998443806299696140859040711832644377542687558553388824898864820174969990871338388950173774587014914485784415193477275448997602686307946551403726070084852772327563262527597*x^3 + 292404292222921897311799124254162395717600857119035716250294527741379227387404311920192136651670934332110659439794535284287560732288202548526736358648929391394032305758746184927511154299606281729777193145022853760459605761534879020*x^2 + 74454489175073809641153530871664457671827845767468333147461996707841855013367595906893910316935518792989091887399143758486348371790431082934982081896791848607332034660255575899354011412205783713075301952880726144940039361979930166*x + 393416694638142524750100170140458906208125208258700143703725549348274340236036132161116111232336035596971628675984584198222395607679769778561975324755324699674486626508048092414419036308362221567055058235620849947595976046717007123;
h[x] := x^8 + 368269120925204307841638327556948738248008244125731087147105096669170482412087584298762137907624773157798580984866033842606103477082252536842968503239061956145574790452327950261552851529507422848613945044288042613453545261800562362*x^7 + 449987731040989555283524165593813556898401269388580458721035665656162896969629741000855251321475075461109798893240439786954837572392778981054303607758928730006332187648539734391205404883529617372296489142105170402913366290591589740*x^6 + 315418547499633345392692344954180275019174677207144238359964877611104826486726937454748921493980865657816511973367329719661631627946866276458657425622819251228387377192666567121428717314596169496731742858824534979717357335840613607*x^5 + 357909544837229707057359443484388962909430770601278015707741754050659433117950318750953725540033131359803951561263608761005282602211766593615790673519145241570540678883082397165755590201315385600689712763058785708012630927021015442*x^4 + 246061747288761165012261995041917910935269117055506858418748004180811864382219533116850701514640182362058341780787561524646475327973898671496575181095377907905327250509728812525313338583849889563081405382561891702685518251045293274*x^3 + 430601056189771169060473697251681998594583340481523396377723692328240124694720819648643889047576099881196198137600199015062592272307653394226275979208399274531789071358322469832950513437823717746685529911962147299510394594413915175*x^2 + 234403107081945116834803895162301189269956100903518622544423778907405517401924750605427807243208280024444940995702993946139220601976517221891377752705109832132861241029489979063069092260272670419957488928327202997129512498577024243*x + 68949233104895068629161700695057239723772333765445437619294192398176878421690981871123893501268425231806444217667529637506709676576508980597776877826088053142809878710778128740433510685977745515942737195019639799393230028795807852;
ft[x] := x^8 + 383920099870381608102679618015482807080034657997477982984847489791362980720311960947351862170344930551152208389149649138480137028957261298482739170415206382617500078007029408290585464942078921851408987667043010665525967029978688463*x^7 + 394206684508048240243624297535915526066956374553945445983903555429057896585449749758395637144584707372879613230391062687618298449282731229616040337707834909712506476603365161874078410555211280633951945940401970857623218200671827883*x^6 + 312801951513663194322507779483868062445057002572750198980778949177011830144159407278276789689965006295366754231046802568030645268550994304076780844150544812512495802058735488405413107938517891583814469390245800499624339536286374855*x^5 + 304207453426368455507260187000259161680797949568419015777394807234726874491379008905558121156820132438483555233884493383223568543054633212003192558809097263287599578337744519127944876767224257734103877638998768798162729742751991334*x^4 + 488562390330112251478434104913270615058262148137982246783050632672662540547064271508604551022541383243304829441148248777045421518613585806618630339151672406292309796942570399832915255125641579770361241189535652893809636997439785322*x^3 + 144489347592968678787407504351401235198915423461420719116662121544104535471631682422539775209665816346826052055939971260908543461450841862957774694172584169701114788733704140536189258575554047116698068261490832372692955989354174512*x^2 + 124336184705752994134771898031783603840671691645039515066329721578664551092115390224225361135813467825526051625152503952305596009438928297445789596850098467564702395014816196405236987961824640971073471825540280490658060513628382584*x + 336520107435644163849838386892958313265970888242623423350900283498518657722601397840454302187254724581953043560858119852844556859641614596148559146300448856496199110834310343477209142710586778061610864993369700792617629390271865950;


(* Find the roots of f in Z/pZ *)
froots = Roots[f[x] == 0, x, Modulus -> p^3];
groots = Roots[g[x] == 0, x, Modulus -> p^3];
hroots = Roots[h[x] == 0, x, Modulus -> p^3];
ftroots = Roots[ft[x] == 0, x, Modulus -> p^3];

For [i = 1, i <= Length[froots], i++,
  Print["Solution of f(x): ", froots[[i, 2]]];
]

For [i = 1, i <= Length[groots], i++,
  Print["Solution of g(x): ", groots[[i, 2]]];
]

For [i = 1, i <= Length[hroots], i++,
  Print["Solution of h(x): ", hroots[[i, 2]]];
]

For [i = 1, i <= Length[ftroots], i++,
  Print["Solution of ft(x): ", ftroots[[i, 2]]];
]

ezcrc

题目源码

#!/usr/bin/env python3
from socketserver import BaseRequestHandler,ThreadingTCPServer
import random
import os
import string
from hashlib import sha256
import signal
import json
from flag import flag

assert len(flag) == 42 and flag.startswith(b"DubheCTF{")

with open("polys.txt","r") as f:
    polys = json.load(f)

def random_poly():
    return polys[random.randint(0,len(polys)-1)]

N = 256

BANNER = br'''
 CCCCC  RRRRRR   CCCCC       GGGG    AAA   MM    MM EEEEEEE 
CC    C RR   RR CC    C     GG  GG  AAAAA  MMM  MMM EE      
CC      RRRRRR  CC         GG      AA   AA MM MM MM EEEEE   
CC    C RR  RR  CC    C    GG   GG AAAAAAA MM    MM EE      
 CCCCC  RR   RR  CCCCC      GGGGGG AA   AA MM    MM EEEEEEE 
 '''

class Task(BaseRequestHandler):

    def send(self, msg,newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def _recv(self, sz):
        try:
            r = sz
            res = b""
            while r > 0:
                res += self.request.recv(r)
                if res.endswith(b"\n"):
                    r = 0
                else:
                    r = sz - len(res)
            res = res.strip()
        except:
            res = b""
        return res.strip(b"\n")

    def recv(self, sz,prompt=b"> "):
        self.send(prompt,newline=False)
        return self._recv(sz)

    def _recvall(self):
        BUFF_SIZE = 1024
        data = b''
        while True:
            _recv = self.request.recv(BUFF_SIZE)
            data += _recv
            if len(_recv) < BUFF_SIZE:
                break
        return data

    def recvall(self,prompt=b"> "):
        self.send(prompt,newline=False)
        return self._recvall()

    def close(self):
        self.send(b'see you next time~~')
        self.request.close()



    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recvall(prompt=b'Give me XXXX: ')
        if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def crc256(self,msg,IN,OUT,POLY):
        crc = IN
        for b in msg:
            crc ^= b
            for _ in range(8):
                crc = (crc >> 1) ^ (POLY & -(crc & 1))
        return (crc ^ OUT).to_bytes(32,'big')

    def setup(self):
        self.send(BANNER)

    def handle(self):
        signal.alarm(120)
        if not self.proof_of_work():
            return
        # initial
        IN = random.getrandbits(N)
        OUT = random.getrandbits(N)
        POLY = random_poly()

        for i in range(5):
            self.send(b"what do you want to do?")
            self.send(b"1.calculate crc")
            self.send(b"2.getflag")
            self.send(b"3.exit")
            try:
                choice = self.recv(5).decode()
                if choice == '1':
                    self.send(b"Give me your message")
                    msg = self.recv(100)
                    crc_hex = self.crc256(msg,IN,OUT,POLY).hex()
                    self.send(b"Here is your crc: "+crc_hex.encode())
                elif choice == '2':
                    flag_crc = self.crc256(flag,IN,OUT,POLY).hex()
                    self.send(b"Here is your flag: "+flag_crc.encode())
                else:
                    self.close()
                    return
            except:
                self.send(b"error")
                pass


if __name__ == '__main__':
    HOST, PORT = "0.0.0.0", 10000
    server = ThreadingTCPServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

题解

五次交互从 flag 的 crc256 的值中恢复出 flag。flag 中未知字节数为 32，从 crc256 中恰好能够恢复出完整的 flag。crc 是线性的，更具体来说， crc256 可以表示为，输入为 $m \in \mathbb{F}_2^{256}$ , 编码成多项式记为 $M(x) \in \mathbb{F}_2[x]$ ：

仿射函数： $f(m) = A m + b$ ， $A \in \mathbb{F}_2^{256 \times 256}, m,b \in \mathbb{F}_2^{256}$ （参考 HackerGame 2022）
多项式函数： $R(x) = M(x) x^{256} \mod G(x) \in \mathbb{F}_2[x]$ , 其中 $G(x)$ 为模多项式，次数为 256，且一般是不可约多项式； $M(x)$ 是消息输入多项式， $R(x)$ 是 CRC 值输出多项式。

这里我们考虑多项式的表达形式，加入输入多项式 $A(x)$ 、输出多项式 $B(x)$ 后，整个 CRC 函数表达式为：

$R(x) = ((M(x) + A(x)) * x^{256} \mod G(x)) + B(x)$

简单构造两个输入多项式 $M_1(x) + M_2(x) = 1$ ，则：

$\begin{aligned} R_1(x) + R_2(x) &= (M_1(x) + M_2(x)) * x^{256} \mod G(x) \\ & = x^{256} \mod G(x) \end{aligned}$

记 $G(x) = x^{256} + g(x)$ 其中 $g(x)$ 是一个次数小于 256 的多项式。因此

$R_1(x) + R_2(x) = g(x) \mod G(x)$

即我们可以通过两次 CRC256 的 oracle 恢复出模多项式 $G(x)$ .

恢复出 $G(x)$ 后，对于任意给定的次数小于 256 的输入多项式 $M(x)$ 对应的 crc 值 $R(x)$ ，我们都可以简单通过差分方式消去 $A(x), B(x)$ 的影响，然后解出原始消息多项式 $M(X)$ 。从而这题最少交互次数应该是 3 。

Exp

from pwn import remote, context
from tqdm import tqdm
import random
import os
import string
from hashlib import sha256
import json
from Crypto.Util.number import long_to_bytes,bytes_to_long
from sage.all import PolynomialRing, GF, ZZ, inverse_mod
# context.log_level = "DEBUG"

PR = PolynomialRing(GF(2), "x")
x = PR.gen()
N = 256

def int2poly(n, padlen=N):
    return PR(ZZ(n).digits(base=2, padto=padlen)[::-1])

def poly2int(p, padlen=N):
    L = p.list()
    L += [0] * (padlen - len(L))
    return int(ZZ(L[::-1], base=2))


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

def solve_poly(m1, m2, c1, c2):
    assert m1^m2 == 0x80
    mpoly = int2poly(c1^c2)
    return x**N + mpoly

# 1.95.38.136 8888
io = remote("1.95.38.136",8888)

def crc256(msg,IN,OUT,POLY):
    crc = IN
    for b in msg:
        crc ^= b
        for _ in range(8):
            crc = (crc >> 1) ^ (POLY & -(crc & 1))
    return (crc ^ OUT).to_bytes(32,'big')

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


def solve_pow(io:remote):
    from itertools import product
    table = string.ascii_letters + string.digits
    io.recvuntil(b"sha256(XXXX+")
    proof = io.recv(16)
    io.recvuntil(b"== ")
    _hexdigest = io.recvline().decode().strip()
    print(f"[+] proof: {proof} {len(proof)}")
    print(f"[+] target hash: {_hexdigest}")
    for _ in product(table,repeat=4):
        prefix = "".join(_).encode()
        if sha256(prefix + proof).hexdigest() == _hexdigest:
            io.sendafter(b'Give me XXXX: ', prefix)
            print("[+] solved pow")
            return
    return

def calc_crc(io:remote, msg:bytes):
    io.sendlineafter(b"3.exit\n> ", b"1")
    io.sendlineafter(b"> ", msg)
    io.recvuntil(b"Here is your crc: ")
    crc_hex = io.recvline().strip().decode()
    return int(crc_hex,16)

def get_flag(io:remote):
    io.sendlineafter(b"3.exit\n> ", b"2")
    io.recvuntil(b"flag: ")
    flag_crc_hex = io.recvline().strip().decode()
    return flag_crc_hex

solve_pow(io)

m1 = b"\x00" * 32
m2 = b"\x00" * 31 + b"\x80"
c1 = calc_crc(io, m1)
c2 = calc_crc(io, m2)
poly = solve_poly(bytes_to_long(m1), bytes_to_long(m2), c1, c2)
print(f"[+] solved poly: {poly}")
print(f"[+] {poly.is_irreducible() = }")
Gfk = GF(2**256, 'x', poly)

flag_crc = int(get_flag(io),16)
flag_format = b"DubheCTF{" + b"\x00" * 32 + b"}"
flag_format_crc = calc_crc(io, flag_format)
cf1 = int2poly(flag_format_crc)
cf2 = int2poly(flag_crc)

# flag_crc ^ flag_format_crc = (flag ^ flag_format) * x^128 % poly
flag_poly = PR(inverse_mod(x**(N + 8), poly)) * (cf1 - cf2) % poly
print(f"[+] flag_poly: {flag_poly}")
flag = poly2int(flag_poly)
print(f"[+] flag: DubheCTF{'{'}{long_to_bytes(flag)[::-1].decode()}{'}'}")