先日ちょっとだけ取り組んだUnion CTFで行列でDH鍵共有をしている問題が出て結構面白かったのでそのWriteupを兼ねて行列の離散対数問題について書きます。

なお、この問題は当日、私がオンライン飲み会に興じている最中にチームメイトが解いていたのをCTF終了後に解き直したものなので私が加点した問題ではありません。

Prerequisite §

下記事項を知っている読者を対象としています。

  • 離散対数問題と典型的な解き方
    • Pohlig-Hellmanアルゴリズム(今回の問題に直接関係はしない)
  • 線形代数に関する知識
    • 対角化
    • ジョルダン標準形

対角化可能な場合 §

Writeupの前に対角化可能な行列の場合を考える。また、以下では各要素がの要素であるような行列を考える。ただしは素数とする。

問題設定としては行列とそれを乗した行列が与えられてこの2つからを求めるという問題である。

ここでが対角化可能な場合はと表すことが出来、これを両辺乗すると次のようになる。

$$ G^k = A = PB^kP^{-1} $$

ここでは対角行列であり、は対角成分が固有値の乗である対角行列になる。ここで対角化によっては判明し、も分かっている為、によってが判明する。

すると固有値をとおくと、の対角成分からを求めよ、という問題になるためいつもの上の離散対数問題に帰着する。

つまりが安全素数でないならPohlig-Hellmanアルゴリズムが有効な為、このような行列が対角化可能なら離散対数問題は解けてしまう事になる。

対角化不可能な場合(Writeupはここから) §

今回扱うUnion CTF - neo-classical key exchangeではの対角化は出来ない。そこで登場するのがジョルダン標準形である。

ちなみにも安全素数であるため、仮に出来たとしてもPohlig-Hellmanアルゴリズムを使うのは難しい(対角化不可能なことを知るより先にこっちからジョルダン標準形が出てきた)。

Challenges §

次のようなスクリプトとその実行結果をくれる。

import os
from hashlib import sha1
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

FLAG = b"union{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

def list_valid(l):
    x = l // 2
    checked = set([x])
    while x * x != l:
        x = (x + (l // x)) // 2
        if x in checked: return False
        checked.add(x)
    return True

def list_iter(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def list_mul(l1,l2,p):
    X, Y = len(l1), len(l2)
    Z = list_iter(X)
    assert X == Y
    assert list_valid(X)
    l3 = []
    for i in range(Z):
        for j in range(Z):
            prod_list = [x*y for x,y in zip(l1[Z*i:Z*(i+1)], l2[j::Z])]
            sum_list = sum(prod_list) % p
            l3.append(sum_list)
    return l3

def list_exp(l0, e, p):
    exp = bin(e)[3::]
    l = l0
    for i in exp:
        l = list_mul(l,l,p)
        if i == '1':
            l = list_mul(l,l0,p)
    return l

def gen_public_key(G,p):
    k = randint(2,p-1)
    B = list_exp(G,k,p)
    return B,k

def gen_shared_secret(M,k,p):
    S = list_exp(M,k,p)
    return S[0]

def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data

p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
G = [37474442957545178764106324981526765864975539603703225974060597893616967420393,59548952493843765553320545295586414418025029050337357927081996502641013504519, 31100206652551216470993800087401304955064478829626836705672452903908942403749, 13860314824542875724070123811379531915581644656235299920466618156218632047734, 20708638990322428536520731257757756431087939910637434308755686013682215836263, 24952549146521449536973107355293130621158296115716203042289903292398131137622, 10218366819256412940642638446599581386178890340698004603581416301746386415327, 2703573504536926632262901165642757957865606616503182053867895322013282739647, 15879294441389987904495146729489455626323759671332021432053969162532650514737, 30587605323370564700860148975988622662724284710157566957213620913591119857266, 36611042243620159284891739300872570923754844379301712429812256285632664939438, 58718914241625123259194313738101735115927103160409788235233580788592491022607, 18794394402264910240234942692440221176187631522440611503354694959423849000390, 37895552711677819212080891019935360298287165077162751096430149138287175198792, 42606523043195439411148917099933299291240308126833074779715029926129592539269, 58823705349101783144068766123926443603026261539055007453105405205925131925190, 5161282521824450434107880210047438744043346780853067016037814677431009278694, 3196376473514329905892186470188661558538142801087733055324234265182313048345, 37727162280974181457962922331112777744780166735208107725039910555667476286294, 43375207256050745127045919163601367018956550763591458462169205918826786898398, 21316240287865348172884609677159994196623096993962103476517743037154705924312, 7032356850437797415676110660436413346535063433156355547532408592015995190002, 3916163687745653495848908537554668396996224820204992858702838114767399600995, 13665661150287720594400034444826365313288645670526357669076978338398633256587,23887025917289715287437926862183042001010845671403682948840305587666551788353]
A,a = gen_public_key(G,p)
B,b = gen_public_key(G,p)
assert gen_shared_secret(A,b,p) == gen_shared_secret(B,a,p)

shared_secret = gen_shared_secret(B,a,p)
encrypted_flag = encrypt_flag(shared_secret)

print(f"Alice's public key: {A}") 
print(f"Bob's public key: {B}")
print(f"Encrypted flag: {encrypted_flag}")




list_.*系の関数はどれも行列に関するものであって次のようになっている。

  • list_valid(): リストの長さが平方数かを確認 -> 正方行列の形として表す事が出来るかを確かめている
  • list_iter(): 平方根を導出 -> 正方行列として表した時のサイズを返す
  • list_mul(): 行列積
  • list_exp(): 行列のべき乗

これらの関数を使ってDH鍵共有が行われており、共有した値から鍵が作られてAESで暗号化されている。なお、各行列は5x5のサイズである。

ジョルダン標準形のべき乗 §

ジョルダン標準形(やジョルダン細胞)が何かは他の資料に説明を譲るとしてこれのべき乗は簡単な形で表す事が出来る。例として2x2のジョルダン標準形のべき乗を計算すると次のようになる。

$$ J^k = \left( \begin{matrix} \lambda & 1 \cr 0 & \lambda \end{matrix} \right)^k = \left( \begin{matrix} \lambda^k & k \lambda^{k-1} \cr 0 & \lambda^k \end{matrix} \right) $$

この問題で出てくるGはある1つの固有値の重複度が2である事から2x2のジョルダン細胞を持つ行列に行列を用いてのように変換する事が出来る。

これを両辺乗すると、となり、左辺はlist_exp(G, a, p) = Aに等しくなる事から既知である。またこの変換によってが判明するため、が既知である。

ここではジョルダン標準形のべき乗であるため、その形は比較的簡単に表せる。詳しくはここ等を参考にしてほしいが、今回は5x5のジョルダン標準形の中に2x2のジョルダン細胞が含まれている事から先程の2x2の場合のような形がべき乗の中に現れて、重複している固有値をとおくと、が判明する。また、もジョルダン標準形へ変形する際に判明する。

したがって次のような式からを導出出来る。

$$ a = \frac{a \lambda^{k-1} \times \lambda}{\lambda^{k}} $$

これで行列の離散対数問題が解けたことになり、あとはスクリプトに記載の手順から復号手順が自明なので省略する。

Code §

from sage.all import matrix, GF
from hashlib import sha1
from Crypto.Cipher import AES
from xcrypto.result import Result
from list_utils import list_valid, list_iter, list_mul, list_exp

# challenge info
p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
G = [37474442957545178764106324981526765864975539603703225974060597893616967420393,59548952493843765553320545295586414418025029050337357927081996502641013504519, 31100206652551216470993800087401304955064478829626836705672452903908942403749, 13860314824542875724070123811379531915581644656235299920466618156218632047734, 20708638990322428536520731257757756431087939910637434308755686013682215836263, 24952549146521449536973107355293130621158296115716203042289903292398131137622, 10218366819256412940642638446599581386178890340698004603581416301746386415327, 2703573504536926632262901165642757957865606616503182053867895322013282739647, 15879294441389987904495146729489455626323759671332021432053969162532650514737, 30587605323370564700860148975988622662724284710157566957213620913591119857266, 36611042243620159284891739300872570923754844379301712429812256285632664939438, 58718914241625123259194313738101735115927103160409788235233580788592491022607, 18794394402264910240234942692440221176187631522440611503354694959423849000390, 37895552711677819212080891019935360298287165077162751096430149138287175198792, 42606523043195439411148917099933299291240308126833074779715029926129592539269, 58823705349101783144068766123926443603026261539055007453105405205925131925190, 5161282521824450434107880210047438744043346780853067016037814677431009278694, 3196376473514329905892186470188661558538142801087733055324234265182313048345, 37727162280974181457962922331112777744780166735208107725039910555667476286294, 43375207256050745127045919163601367018956550763591458462169205918826786898398, 21316240287865348172884609677159994196623096993962103476517743037154705924312, 7032356850437797415676110660436413346535063433156355547532408592015995190002, 3916163687745653495848908537554668396996224820204992858702838114767399600995, 13665661150287720594400034444826365313288645670526357669076978338398633256587,23887025917289715287437926862183042001010845671403682948840305587666551788353]
A = [28233100393684529817120826374704703970604351085347992179309675559635346595380, 29046194176577252146425228713999025714624645466020308483596362772799464421565, 51414757515365785106884177690982449232859118016584164030996802978303073832864, 32267784952174932165833922809968200325881642530032757218932833269493776228149, 13973793666546842231063337975335309683360495651176415377710477331321414420456, 5286615045753246138573595226543740641269173696296954823357812924414572937107, 43466342875687159863281474559075034075049932698505922755874901032656831073450, 47661605030033906449833071780503259530559725918766113764853049109959949029047, 29762627612115411002000295970517549686591898340299041949451816959553956035443, 49286580271478233284518064235175477517034865850564346192909446300261247213283, 7188366615080791208945602088806130718221011202809096314763875728464565550249, 32182006086354456048519258721570301235369694461013162635052191913678704872393, 21483240138613555020973495536958806124512132313438467660300656866733958284555, 32536424410469390868658830924897162415670475154843962198873348894987606529091, 45625096994113674714302106480828933542072238055815294252728640125290264970846, 24213002979296722993383462232491867853999792671040421022480792914763688570011, 20226375341521636699395168981434607973732973904867124197482261876438894251202, 35665173793762989154951727010732056807487002272231939587142706779138064036737, 44918569326474189030005211458487723881627056771470698141626869348302159144544, 55135331348727541614492445208303357763346452332141430109351274117544563056325, 3933992047445840422521143559241271788171754114229341734112783430664672779696, 21801264227118954504981594527645803342623213184399008070689042493499060756930, 36511317987578612540784999849026900531836613400317039182698008103871338654381, 26496131888936628842836360667203182676230332105839869360126226904814961091203, 30731439605443071877356819320867001660509853590875860716545460172180769908374]
B = [44377211427173233116979050195003801151862259928694524276865425496276215498972, 49241196843948436830587713696810940169354056619506533754073633670263404255961, 23492045323953392330208784813581654383480854895526105331150055254139460724192, 17080512298466023233312431592445586950706981939186458231843048823545276010215, 39604091535611342500963237243447065555062876641002877504522940232561620619318, 56960961102475075778327243487866255394103198246135548238726100230622806328438, 38217368372409493349493021940482885382608210497803407862232172289864983784622, 42335856751075392349376312407843682476509683741291872419641417363122382815132, 51941219313167868120916202016894056878767165096252120052547694800835266376234, 39291827760740007097926684492849490059616209795648655493766840810548112692299, 43135915013972209275982685899523579484981852752898836057210548592960639003728, 23595516638571580424735519959966735718018613005573597878458733582530644060888, 62827451288017543974020113222032392007291072051169612626408144208347674696867, 5592384352020377877919583422508787142347256068192656512514358468697868033175, 18051963256426258602161226818544125427525613549556239701594042609393802930037, 40958445768744523216077674511494171471872825559820257375045060058213312003099, 58717128055983851157674774153408247177039629801049962370399870689530231499322, 1037221856690142468199057506665941102592008657830329236867815734600280869030, 59376420054790038148696948468280202162475373720884110232519335695030684164414, 4151096619484839840558543718588323193224649180369287745679082104762052554517, 59388992954098787668810593349809442685161783884520951198437714884153766418952, 2963435422634311858110276357146679864581253927895056591004158165102829287371, 41537819812103905985231524610057365971827624339877580912325361702870004864439, 39640428648253591645759865709120529164727198669907353665694566732915196666123, 40517325937253252797947519549738947711994111971749366539987665346423972531224]
encrypted_flag = {'iv': 'f62c1400190702198a26c4f855030f8c', 'encrypted_flag': '9580af623a2427920469c31407f9cec7ccab2389cb3a120869106bf6c6f6fe09810172a1f0f3892c321237ac0e4b7d9a'}


def gen_shared_secret(M,k,p):
    S = list_exp(M,k,p)
    return S[0]


def exploit() -> Result:
    m_g = to_matrix(G, 5, 5)
    m_a = to_matrix(A, 5, 5)
    m_b = to_matrix(B, 5, 5)
    jordan_g, P = m_g.jordan_form(transformation=True)
    _lambda = jordan_g[3][3]
    j_k = P.inverse()*m_a*P
    k_lambda_k1 = j_k[3][4]
    lambda_k = j_k[4][4]
    k = k_lambda_k1 * _lambda * pow(lambda_k, -1, p) % p
    assert list_exp(G, k, p) == A
    s = gen_shared_secret(B, k, p)

    key = sha1(str(s).encode('ascii')).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, bytes.fromhex(encrypted_flag["iv"]))
    flag = cipher.decrypt(bytes.fromhex(encrypted_flag["encrypted_flag"]))
    return Result(flag)


def to_matrix(l, row_n, col_n):
    ret = []
    assert len(l) == row_n * col_n
    for i in range(row_n):
        row = []
        for j in range(col_n):
            row.append(l[i*row_n + j])

        ret.append(row)

    return matrix(GF(p), ret)


if __name__ == "__main__":
    res = exploit()
    if res.isSuccess():
        print(res.unwrap())

Flag §

union{high3r_d1m3n510ns_l0w3r_s3cur1ty}

感想 §

面白かったです。以外の離散対数問題を解くのは新鮮でした。

以前、ある問題を行列の対角化を利用して解いた事があり、今回はそれの強化版だったので対角化の場合と併せて取り上げました。

Union CTF自体はリアルの都合であまり参加出来ませんでしたが、チームメイトが解いているのを見る感じだと楽しそうなCTFだったのでフルコミットしたかったです。他のCryptoの問題も楕円曲線の高さの増加度合いが大きいことを利用していた問題だったり、超特異同種写像Diffie-Hellmanの問題が出ていたりと数学が好きな人が作ったような問題が多かったので(特に超特異同種写像Diffie-Hellmanの問題は)しっかりと復習しようと思います。

ここまで読んでいただきありがとうございました。次もネタがちょっとだけあるので形になったら近いうちに投稿します。