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

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

Prerequisite §

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

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

対角化可能な場合 §

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

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

ここで$G$が対角化可能な場合は$G = PBP^{-1}$と表すことが出来、これを両辺$k$乗すると次のようになる。

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

ここで$B$は対角行列であり、$B^k$は対角成分が固有値の$k$乗である対角行列になる。ここで対角化によって$P$は判明し、$A$も分かっている為、$B^k = P^{-1}AP$によって$B^k$が判明する。

すると固有値を$\lambda_i$とおくと、$B^k$の対角成分$\lambda_i^k \bmod p$から$k$を求めよ、という問題になるためいつもの$\mathbb{Z}/p\mathbb{Z}^*$上の離散対数問題に帰着する。

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

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

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

ちなみに$p$も安全素数であるため、仮に出来たとしても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$のべき乗を計算すると次のようになる。

$$ 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のジョルダン細胞を持つ行列$J$に行列$P$を用いて$G = PJP^{-1}$のように変換する事が出来る。

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

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

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

$$ 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}