nullcon Goa HackIM CTF 2022 Writeup

この大会は2022/8/13 15:00(JST)～2022/8/14 15:00(JST)に開催されました。
今回もチームで参戦。結果は 701点で393チーム中42位でした。
自分で解けた問題をWriteupとして書いておきます。

FREE POINTS! (sanity)

問題にフラグが書いてあった。

ENO{ENJOY_PLAYING}

cookie_lover_reloaded (crypto)

サーバの処理概要は以下の通り。

・P-256パラメータ設定
　p, a, b, n, curve, G
・target = b'I still love cookies.'
・d_a = ランダム32バイトの数値化したもの
・P_a = G * d_a
・r, s = sign(target, True)
・P_a表示
・以下繰り返し
　・cmd: 入力
　・cmdの先頭2バイトが"1:"の場合
　　・cmdの3バイト目以降のsignの結果を表示
　・cmdの先頭2バイトが"2:"の場合
　　・r, s: cmdの3バイト目以降の","区切りの2つ
　　・verify(r, s, target, P_a)がTrueの場合、フラグを表示

ECDSAの問題。ただし、kは65536未満のランダム整数のため。衝突の可能性が高い。何度かsignを繰り返していくと、rが同じケースが出るはず。異なるメッセージでrが同じsignature(r, s1), (r, s2)を入手できた場合、以下のような計算ができる。

z1 = int(hashlib.md5(msg1).hexdigest(), 16)
z2 = int(hashlib.md5(msg2).hexdigest(), 16)
k = (z1 - z2) * inverse(s1 - s2, n) % n
d_a = (s1 * k - z1) * inverse(r1, n) % n

以上から、targetのsignatureを算出できるので、その結果を渡せば、フラグが得られる。

#!/usr/bin/env python3
import socket
import hashlib
from ec import *
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
curve = EllipticCurve(p,a,b, order = n)
G = ECPoint(curve, 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
target = b'I still love cookies.'

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('52.59.124.14', 10005))

data = recvuntil(sock, b'\n').rstrip()
print(data)
data = recvuntil(sock, b'\n').rstrip()
print(data)
data = recvuntil(sock, b'\n').rstrip()
print(data)

rs = []
ss = []
for i in range(65536):
    data = recvuntil(sock, b'check]\n').rstrip()
    print(data)
    data = recvuntil(sock, b'\n').rstrip()
    print(data)
    msg = str(i).zfill(5)
    cmd = '1:' + msg
    print(cmd)
    sock.sendall(cmd.encode() + b'\n')
    data = recvuntil(sock, b'\n').rstrip()
    print(data)
    r , s1 = eval(data)
    if r in rs:
        index = rs.index(r)
        s2 = ss[index]
        z1 = int(hashlib.md5(msg.encode()).hexdigest(), 16)
        z2 = int(hashlib.md5(str(index).encode().zfill(5)).hexdigest(), 16)
        break

    rs.append(r)
    ss.append(s1)

    i += 1

k = (z1 - z2) * inverse(s1 - s2, n) % n
d_a = (s1 * k - z1) * inverse(r, n) % n

R = G * k
x, y = R.x, R.y
r = x % n
s = inverse(k, n) * (int(hashlib.md5(target).hexdigest(),16) + r * d_a) % n

data = recvuntil(sock, b'check]\n').rstrip()
print(data)
data = recvuntil(sock, b'\n').rstrip()
print(data)
msg = str(r) + ',' + str(s)
cmd = '2:' + msg
print(cmd)
sock.sendall(cmd.encode() + b'\n')
data = recvuntil(sock, b'\n').rstrip()
print(data)

実行結果は以下の通り。

My public key is:
Point(69148073155886016179332475534481076967664728224629186908130713787937845616903, 41205214553766042760762537386801131157236938074525904309997914590961437731806)
I will sign anythin as long as it does not talk about cookies.
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00000
(103620037724456292160909247152603324037826675844129306051494527318824828844006, 65063951920621117425767992893200443175794900191455570011670777683558191341196)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00001
(97239160500360134845055152773408738160270561567541735499373976486205564710901, 97386882204750183894385144659843539660020781774836909016577052347033624980268)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00002
(13561070049808612158968862888819425964767030164164811857583918316359145562717, 38143796610128049740960902429412425503998067340174211968359647782831125671044)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00003
(72555067614363078064235738641918081170060536255630967891212814493092360010667, 29405572946442923511433356951427467391193522786329957441241552381361965788352)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00004
(91066673070387237528868579256042690888957486523197874909256675595985858672697, 30918506023288548125678798103504853303114727453602529423249588483686830654548)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00005
(36125549519596618782586016339635904235140843613611402659347197692296912569322, 19995491879891482303036287330389391139859738018411024133729407826881939227495)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

　　　　　　　　：
　　　　　　　　：

1:00256
(42210713867248392276539395550506078877212977557299451415846602848958266345520, 99109191007301880737226383457129568359070924368687824328550677883040976032932)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00257
(67027935531475083361562190519297509405012686631840502833869662290751204121547, 19371069395261191283890135461379564969854264027226559949068158910488030220597)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00258
(20570865741513900968029214814394535007423062856754389580734061856369277346145, 78286257782349415685100297855765444293485859886046253615739553289233042443812)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00259
(103344774071497076257173493732650640012438704416369268955810336705703160817093, 8205101630170098140806410181348152742391214074585705539576744488192760971870)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00260
(72862377221958341026740269167283287471654671456870194354146029775860161925628, 61035458095966007876682459033695188692032698094072784988093012000614720792881)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00261
(97239160500360134845055152773408738160270561567541735499373976486205564710901, 7738636678726030723109117715512575150734350618348491018646381788474571261046)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

2:97239160500360134845055152773408738160270561567541735499373976486205564710901,107492483321193936228761501238728921223795430681283172434744697644787267097847
ENO{gr33tings_fr0m_the_PS3}

ENO{gr33tings_fr0m_the_PS3}

cookie_lover_reloaded2 (crypto)

何がcookie_lover_reloadedと違うのかわからない。cookie_lover_reloadedで使ったスクリプトを通信先だけ変更して実行する。

#!/usr/bin/env python3
import socket
import hashlib
from ec import *
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
curve = EllipticCurve(p,a,b, order = n)
G = ECPoint(curve, 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
target = b'I still love cookies.'

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(('52.59.124.14', 10014))

data = recvuntil(sock, b'\n').rstrip()
print(data)
data = recvuntil(sock, b'\n').rstrip()
print(data)
data = recvuntil(sock, b'\n').rstrip()
print(data)

rs = []
ss = []
for i in range(65536):
    data = recvuntil(sock, b'check]\n').rstrip()
    print(data)
    data = recvuntil(sock, b'\n').rstrip()
    print(data)
    msg = str(i).zfill(5)
    cmd = '1:' + msg
    print(cmd)
    sock.sendall(cmd.encode() + b'\n')
    data = recvuntil(sock, b'\n').rstrip()
    print(data)
    r , s1 = eval(data)
    if r in rs:
        index = rs.index(r)
        s2 = ss[index]
        z1 = int(hashlib.md5(msg.encode()).hexdigest(), 16)
        z2 = int(hashlib.md5(str(index).encode().zfill(5)).hexdigest(), 16)
        break

    rs.append(r)
    ss.append(s1)

    i += 1

k = (z1 - z2) * inverse(s1 - s2, n) % n
d_a = (s1 * k - z1) * inverse(r, n) % n

R = G * k
x, y = R.x, R.y
r = x % n
s = inverse(k, n) * (int(hashlib.md5(target).hexdigest(),16) + r * d_a) % n

data = recvuntil(sock, b'check]\n').rstrip()
print(data)
data = recvuntil(sock, b'\n').rstrip()
print(data)
msg = str(r) + ',' + str(s)
cmd = '2:' + msg
print(cmd)
sock.sendall(cmd.encode() + b'\n')
data = recvuntil(sock, b'\n').rstrip()
print(data)

実行結果は以下の通り。

My public key is:
Point(100740616534960168008987760212819415262067546803131055211017668534201640893133, 25569694084387678506576003322339001134016840470195962352798418659980066267578)
I will sign anythin as long as it does not talk about cookies.
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00000
(10405697512318034398231268585344122779172453324960143543047170445080223818348, 105310122580343474201286986309857888975056744543628810229824667862170332161838)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00001
(41435804264539253957040146542191076499348733412028466003420210277001876539386, 12829293370534208668234719233334171547070433621152096328933006129961453370778)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00002
(27550754613607026790075792905019829902780565867938838947585902228848168440627, 86120830937178321736093401328292446142648994225110853289586823864404389368459)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00003
(49213160857592820221236957894570198532591022430675231915172358378844215840608, 115047043967959511665951508262334715777435843877251544922268037898336227265094)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00004
(111151957300942186660381641324857065107935219153638116658513272746162302582291, 22464926841722385278835317093728726988956190922439898905863973263206204628899)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00005
(42689544016133835224620427415684513728559022294464056465793254737581457384759, 55415869869639343812323422025235688870543635126618287374850789024143116814783)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

　　　　　　　　：
　　　　　　　　：

1:00141
(83822374376017856480617233876851747027730645942375790017270342989929749964423, 51330874742827849326917201894380879942062945104961293945775119837437640869363)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00142
(41273579064045923821354322537350911500686147093101541326998799812080436747592, 114156141789185939980217593587233004304453323805040963570270984741323614242632)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00143
(105804237753942935971251712714551536782649891742674674987862872986566733096415, 49535344770716554994597611429072721671909697632410802535826669390878003209623)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00144
(13498642495041740317587055510078743620293737621696104080304432056943407930722, 94174414934266220521197021366399837050081854519590237454734892738812704929372)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

1:00145
(82683363102863919392024961160650299752222859055425926324444733332733873316756, 114773872962259985945195965238009840674754792157785035486974936308885397818236)
Choose an option:
1:[text to sign]
2:[number,number - signature to check]

2:82683363102863919392024961160650299752222859055425926324444733332733873316756,32926515776512730353806135342161900953805913367019922669080654402948119331343
ENO{Th1s_t1m3_1t_w0rks_h0p3fully}

ENO{Th1s_t1m3_1t_w0rks_h0p3fully}