yoshi-gcc log - ふるつき

もう随分昔の話ですが、私がGCCに落ちたので、チームinsecure内での勉強会、yoshi-gccが開催されました*1。やっと宿題を片付けたので記録とwriteupを書きます。

他の参加者のブログ

yoshiking.hatenablog.jp

ptr-yudai.hatenablog.com

私の発表
yoshikingの発表
ptr-yudaiの発表

私の発表

「CTFではLLLを、格子の非零な最小ベクトルを求めるための道具として使う」ということや「求めたい最小ベクトルがMinkowskiの不等式やGaussian Heuristic Assumptionに従いそうなことを確かめよう」などといったことを紹介しつつ、一部のMarkle-Hellman knapsack暗号に対するLLLを用いたアプローチ、Rolling Hashを衝突させる入力をLLLで作る、Approximate GCDっぽい問題をLLLで解くといった例を紹介しました。いま改めて資料を見返したら何言ってるのか全然わからなくて笑っちゃった。

発表中に「行列の各行の大きさを大体揃えておくことが大事っぽいね」みたいな話がでたのですが、これの根拠もよくわかってないです（格子の基底ができるだけ直交した感じになると良さそう？　よくわからんね）。

他にも、LLLを適用する際には縦型・横型の行列のどちらを使うべきかといったことについても触れましたが、これは正直なぜこうなるのか全然わかっていないので曖昧に流してしまいました*2。わかる人がいたら教えてください。

yoshikingの発表

yoshikingもLLLについてでしたが、こちらはHITCON 2019のnot so hard RSAという問題の解説ベースという感じでした。要するに mikowskiの定理に従うように行列のサイズを調節してLLLで殴れという問題だと解釈して自分なりにサイズを調節していたのですが、結局私は解けず仕舞いでした。こんなの解けるわけ無いだろ

ptr-yudaiの発表

楕円曲線に関して、過去のCTFで出題された問題を例に、どういうケースで脆弱になるのかを紹介してくれました。過去に取り組んだけど解けなかった問題などが取り上げられていてとても勉強になりました。ここでは取り組んだ問題とその解答スクリプトを列挙してみます。

watevr-CTF 2019 ECC-RSA

本番では「いやー解けね〜〜〜」って言ってやつ(1)です。RSAのp, qが、ある楕円曲線上の点のx, y座標になっているだけ、という問題で、解けなかったときはsageのsolve（方程式を解くやつ）でやっていたのですが、PolynomialRingのrootsを使う手法を教えてもらったので解けました。解いた後、こういう点をどうやって見つけてるのか作問者に聞いたのですが、「マシンパワーで長時間殴った」らしいです。

from sage.all import *
from Crypto.Util.number import *

n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
a =  -0x3
b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00

PRIME = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
PR, x = PolynomialRing(FiniteField(PRIME), name="x").objgen()
f = (n**2) - (x**5) - a * (x**3) - b * (x**2)
polys = f.roots()

for ans in polys:
    if isPrime(int(ans[0])):
        p = int(ans[0])
        break

q = n // p
c =  0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e

phi = (p-1)*(q-1)
e = 65537
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(bytes.fromhex(hex(m)[2:]))

ASIS CTF Quals 2019 Halloween Party

本番で解けなかった問題(2)です。ちなみにそのあとwriteupを読んでも解けなかったりしていました。楕円曲線上のいくつかの点から楕円曲線のパラメータを求めるパートと、楕円曲線上の点の方程式を解くパートがあります。楕円曲線上の点に定数 $x$ の逆数 $x^{-1}$ をかけるときは楕円曲線の位数の逆数をとります。こういう基礎的な知識も抜けがち

from sage.all import *

y1 = 467996041489418065436268622304855825266338280723
y2 = 373126988100715326072483107245781156204485119489
y3 = 245091091146774561796627894715885724307214901148

# p = factor(2 * (y1**2) - (y2**2) - (y3**2) + 24) from factordb
p = 883097976585278660619269873521314064958923370261

A = (((y1**2) - (y2**2) - 2 ) // 2) % p
B = (((y1**2) + (y2**2)) // 2) % p


iQy = 621803439821606291947646422656643138592770518069
_, x = PolynomialRing(GF(p), name="x").objgen()
f = x**3 + A*x + B - iQy**2
iQx = int(f.roots()[0][0])

EC = EllipticCurve(GF(p), [A, B])
P2 = EC((iQx, iQy))
P = inverse_mod(2, EC.order())  * P2
print(P)

CSAW CTF Qualification Round 2019 Supercurve

楕円曲線の位数が小さいのでsageのdiscrete_logで殴ると解けます。はい

from sage.all import *
from ptrlib import *



EC = EllipticCurve(GF(14753), [1, -1])
G = EC((1, 1))

sock = Socket("jctf.tk", 12345)
sock.recvuntil("ublic key: ")
x, y = eval(sock.recvline().decode())
Q = EC((x, y))

s = G.discrete_log(Q)
print(s)
print(s * G)
print(Q)
sock.sendline(str(s))
sock.interactive()

picoCTF 2017 ECC2

楕円曲線の位数が素因数分解できる場合に、Pohlig-Hellman attackができるよ、という問題です。この問題も楕円曲線のパラメータbを求めるステップがあり、PolynomialRingのrootsで殴ります

#  Elliptic Curve: y^2 = x^3 + A*x + B mod M
#  M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
#  A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
#  B = *You can figure this out with the point below :)*
#
#  P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
#  n = *SECRET*
#  n*P = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)
#
#  n < 400000000000000000000000000000
#
#  Find n.

from sage.all import *

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
Px, Py = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)

_, b = PolynomialRing(GF(M), name="b").objgen()
f = Px**3 + Px*A + b - Py**2
B = Integer(f.roots()[0][0])

EC = EllipticCurve(GF(M), [A, B])
P = EC((Px, Py))
Q = EC((61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440))

order = EC.order()
factors = list(factor(order))
mods = []
zs = []
cur = 1

bound = 400000000000000000000000000000

for factor in factors:
    p, e = factor
    pe = p**e
    Pi = (order // pe) * P
    Qi = (order // pe) * Q
    zi = Pi.discrete_log(Qi)

    zs.append(zi)
    mods.append(pe)

    cur *= pe
    if cur > bound:
        break

print(CRT(zs, mods))

nullcon HackIM 2019 Singular

Singularな楕円曲線は準同型なほかの構造にうつして解ける、という問題です。なんとこの問題は以前に勉強したことがあったのでスクリプトぺっってすると解けました。が、何が起こっているのかをちゃんと知れてありがたかったです。ところでsupersingularな曲線ってもっと簡単に解けないんですかね……。

from sage.all import *
from Crypto.Cipher import AES
from hashlib import sha256

def c4(a1, a2, a3, a4, a6, p):
    b2 = pow(a1,2) + 4*a2
    b4 = 2*a4 + a1*a3

    return (pow(b2, 2) - 24*b4) % p

PRIME = 785482254973602570424508065997142892171538672071
Field = GF(PRIME)
_, (x, y) = PolynomialRing(Field, 2, names=["x", "y"]).objgens()
A2 = 330762886318172394930696774593722907073441522749
A1 = 6688528763308432271990130594743714957884433976
A0 = 759214505060964991648440027744756938681220132782

f = x**3 + x**2 * A2 + x * A1 + A0 - y**2
C = Curve(f)
Dx, Dy = C.singular_points()[0]
print("[+] singular poinrt: ({}, {})".format(Dx, Dy))

if c4(0, A2, 0, A1, A0, PRIME) == 0:
    print("[+] curve is cusp")
else:
    print("[+] curve is node")

f2 = f.subs(x=x - Dx, y = y - Dx)

G = (1, 68596750097555148647236998220450053605331891340)
P = (453762742842106273626661098428675073042272925939, 680431771406393872682158079307720147623468587944)
Q = (353016783569351064519522488538358652176885848450, 287096710721721383077746502546881354857243084036)

# map from elliptic curve to finite field
Fg = Field(G[0] - Dx) / Field(G[1] - Dy)
Fp = Field(P[0] - Dx) / Field(P[1] - Dy)
Fq = Field(Q[0] - Dx) / Field(Q[1] - Dy)

# solve discrete log
d1 = Fp / Fg
d2 = Fq / Fg
print("d1: {}".format(d1))
print("d2: {}".format(d2))

# find K
Fk = d1 * d2 * Fg

# reverse map from finite field to elliptic curve
K = (Fk**(-2) + Dx, Fk**(-3) + Dy)
key = sha256(str(K[0]).encode()).digest()

c = bytes.fromhex('480fd106c9a637d22fddd814965742236eb314c1b8fb68e70a7c7445ff04476082f8b9026c49d27110ba41b95e9f51dc')
m = AES.new(key, AES.MODE_ECB).decrypt(c)
print(m)

TJCTF 2016 Curvature2

Anomalousな曲線は脆弱だよね、という問題です。SSSA Attack万歳、ecpy万歳。ところでanomalousな曲線どうやって見つけるんでしょう？　知ってる人いらっしゃいませんか……。

from sage.all import PolynomialRing, GF
from ecpy import *


P = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
Gx = 0xcf634030986cf41c1add87e71d638b9cc723c764059cf4c9b8ed2a0aaf5d51dc770372503ebfaad746ab9220e992c09822916978226465ad31d354a3efee51da
Gy = 0x65eaad8848b2787103fce02358b45d8a61420031989eb6b4b70d82fe20d85583ae542eb8f76749dc640b0f13f682228819b8b2f04bd7a5a17a4c675540fe1c90

_, b = PolynomialRing(GF(P), name="b").objgen()
f = Gx**3 + A*Gx + b - Gy**2
B = int(f.roots()[0][0])

F = FiniteField(P)
EC = EllipticCurve(F, int(A), B)

G = EC(Gx, Gy)

Q = EC(10150325274093651859575658519947563789222194633356867789068177057343771571940302488270622886585658965620106459791565259790154958179860547267338437952379763, 6795014289013853849339410895464797184780777251924203530417684718894057583288011725702609805686960505075072642102076744937056900144377846048950215257629102)
s = SSSA_Attack(F, EC, G, Q)
print(bytes.fromhex(hex(s)[2:]))

TJCTF 2015 Curvature

宿題になっていた問題です。ある点を与えて何かしらの演算をしてもらう時、与えた点が楕円曲線上にあるかどうかのチェックがないと、invalid curve attackが可能になります。という問題で、しかしinvalid curve attackをする際にどうやって良いBを求めるのかがわからず放置していたのですが、De1CTF 2020のECDHという問題のwriteup を見てこれがわかったので解けました。ちなみにECDHは本番中に「うわ〜〜invalid curve attackじゃん」って言って放り投げました。

どうやら、楕円曲線の位数がある程度小さい数を含むように素因数分解できる場合に、楕円曲線のgenerator * (order / factor)をやると、位数がfactorな部分群のgeneratorが求まるようです。確かに……。これで位数が小さい楕円曲線上での演算に持ち込めば、あとはCRTで復元、という感じで解けます。

from sage.all import *
from timeout_decorator import timeout
from ptrlib import *

generators = [
    {'generator': (75018829908334641135287907832364588376392648394852697956512464620901439399091, 59310606686882497582859801487472084112791104513525809772271515095232323519002), 'order': 17, 'b': 2} ,
    {'generator': (14108366122805723625020075750179082265774395778849335024217582787861312312270, 48131724537792101564129626030579998631347236213771248503484807671517428824779), 'order': 11871421, 'b': 3} ,
    {'generator': (10219791296939476446978405667751432187697243109108209712110403172731476918598, 29956495008696010243175913739747719779132987433052330275148912122314390288669), 'order': 137, 'b': 5} ,
    {'generator': (42777940522922357350677116116779112965460458338266309438879684299889046092060, 55153724152154375167247217363093302126821206645660100074296996339252760370913), 'order': 32633, 'b': 7} ,
    {'generator': (10831563407297415859788486867917312379445005544125515905759465100401482164790, 83673279217201573271136390602924299332268405981527089175622432592003182193), 'order': 2192629, 'b': 9} ,
    {'generator': (21866291018291769753200219006065902052302271116278780675505468066315056034667, 26320854338400571929354338120932758767766121454452318420674426177401484895077), 'order': 1146083, 'b': 11} ,
    {'generator': (70477946629836528396820075171089472321695231503572908556028599471720495852914, 45359043459356443396911931469603778921737175440775125150426057614649863769381), 'order': 557693197, 'b': 12} ,
    {'generator': (3067625162943157588017556490906306538160163692852525289213976752118141691559, 70135860004395620803901190886933054437366829947624865529920703668208548865169), 'order': 4787, 'b': 13} ,
    {'generator': (20453887951492396382116635373156816246787390607186046864442208295254950706353, 41374043013134953199326755315280127177100264339162100449295591769938446808604), 'order': 120528059, 'b': 14} ,
    {'generator': (63860357017578264591074151267679315831331582854780010735294147152111534385449, 7787790211631466170916931897483087919405908652838124300647908802622489289322), 'order': 167, 'b': 15} ,
    {'generator': (28266681978198457092812065766219275154917100817596733107392104751238123037180, 25375345042438509641710766829984998144411914831489524239691171315736258149744), 'order': 433981, 'b': 17} ,
    {'generator': (30194731389043602783690419048124763865168292379437069881181109836251172351228, 40665116364724631324900157788568397943144157820689726966949666425146455719977), 'order': 370871, 'b': 18} ,
    {'generator': (24936471025919082430845657538468506580791307884831801991879227749137995844519, 63816116169864815848466423976585822530331789272863018928197180972927927939612), 'order': 259177, 'b': 21} ,
    {'generator': (41876169769492810135683621405650315114043483742421946397396849624969605627524, 62374885101651406800250293984653592947701957841184358843280066067652148661439), 'order': 9804344863, 'b': 22} ,
    {'generator': (45845934232875157717087534318790345406363949403587257916077210108373946981911, 10876312240831805735749936927491976773415927845336159631890752995764740480225), 'order': 11, 'b': 23} ,
]

A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
F = GF(P)

sock = Socket("localhost", 12345)
sock.recvuntil('"x y"\n')

pairs = []

for i, g in enumerate(generators):
    print("[+] {}/{}".format(i+1, len(generators)))
    E = EllipticCurve(F, [A, g['b']])
    P = E(g['generator'])

    sock.sendline("{} {}".format(*g['generator']))
    sock.recvuntil("point:\n")
    x,y = [int(xy) for xy in sock.recvline()[1:-1].split(b", ")]

    Q = E((x,y))
    z = P.discrete_log(Q)

    pairs.append((z,g['order']))

print(bytes.fromhex(hex(crt(pairs)[0])[2:]))

いい感じのgeneratorを見つけるスクリプト

from sage.all import *
from timeout_decorator import timeout


A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
F = GF(P)
size = EllipticCurve(F, [A, B]).order()


@timeout(10, timeout_exception=Exception, use_signals=False)
def factorize(n):
    return prime_factors(n)

cur = 1
b = 2
while cur < size:
    EC = EllipticCurve(F, [A, b])
    order = EC.order()

    try:
        factors = factorize(order)
    except Exception:
        b += 1
        continue

    suborder = 1
    for f in factors:
        if f < 10**10:
            suborder = f
        else:
            break
    g = EC.gen(0) * int(order // suborder)
    print({
        "generator": g.xy(),
        "order": suborder,
        "b": b,
    }, ",")

    cur *= suborder
    b += 1

この他にもまだ解けてない問題はあったりしますがまあそれはそれ。勉強になりました

*1:僕はyoshi-gccと認識してるけど、他の２人はyoshi-campって書いてるのでyoshi-campかもしれないです

*2:この資料 http://jant.jsiam.org/006-shimizu.pdf の42ページ〜を参照していたと思います