SekaiCTF 2024 Writeup

Sanity Check (Misc)

Discordに入り、#announcementチャネルのトピックを見ると、フラグが書いてあった。

SEKAI{I'm_thinking_Miku,_Miku_(oo-ee-oo)}

Some Trick (Cryptography)

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

・CIPHER_SUITE: 2**256未満のランダム整数
・CIPHER_SUITEを表示
・CIPHER_SUITEをシードとして乱数設定
・GSIZE = 8209
・GNUM = 79
・LIM = GSIZE**GNUM
・G: 79個のgen(GSIZE)の配列
　・p, i = [0] * n, 0
　・1以上n未満の値からランダムにn - 1個選択した値のそれぞれjに対して以下を実行
　　・p[i], i = j, j
・FLAG: フラグの数値化したもの
・left_pad: (LIMのビット長 - FLAGのビット長)未満のランダム整数のビット長のランダム整数
・FLAG: FLAGをleft_padのビット長分左シフトし、left_padをプラスしたもの
・FLAG: (LIMのビット長 - FLAGのビット長)未満のランダム整数のビット長のランダム整数を
　          フラグのビット長だけ左シフトし、FLAGをプラスしたもの
・bob_key: LIM未満のランダム整数
・bob_encr = enc(FLAG, bob_key, G)
・bob_encrを表示
・alice_key: LIM未満のランダム整数
・alice_encr = enc(bob_encr, alice_key, G)
・alice_encrを表示
・bob_decr = enc(alice_encr, bob_key, [inverse(i) for i in G])
・bob_decrを表示

パディング後のFLAGは以下のようなイメージ

XXXFLAGXXXXXXXXXXXXXXXXXXXXXXXXX

enc関数は以下のように定義されている。

def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod

modで割ったあまりは、gexp(G[0], k % mod)[m % mod]の値になると考えられる。
bob_decr = enc(alice_encr, bob_key, [inverse(i) for i in G])において、alice_encrとbob_decrがわかっている。
kのブルートフォースでk % modの値がわかるので、これを繰り返しbob_keyを求める。
その後同様にしてbob_keyからFLAGを求める。あとは8ビット未満でシフトすればフラグが含まれているはず。

$ ncat --ssl sometrick.chals.sekai.team 1337                                          
oPUN_SASS_SASS_l version 4.0.27341864582601706122776768871743338973868949617062934512131880087398729099814
bob says 949466149013684769194106007085907150483179679883657963650373826780536359740002968990531772218497898792820189533496801635127997651332930433378150145536678650605630574982483885527918725111097957346602404856351824107789280538305441009593751460809038204504074506452852780479977817878535709573256789394567447379299
alice says 1544648505151744161945707074785466501514735116544469276942998571927605788637573335136142527144706626077605305544981378031763827248247815794325909642974628021235544768486634918639813509385366833766797430695976565243715370305635128031518083593625736829965705480534702513367046280184451132276780764689328019739659
bob says 1636856621831750800171484397508521251119605278869638004037184206519293828900709675159877130651027764989077774936886036039201359220822752590803350053644557946184732063186901191800113791055178015797009263719807198774079244840118610635369334310552469744958081927231303488581996787808657216275456787045070732936532

#!/usr/bin/env python3
import random
import re
from Crypto.Util.number import *

def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)

def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res

def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod

def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res

CIPHER_SUITE = 27341864582601706122776768871743338973868949617062934512131880087398729099814
random.seed(CIPHER_SUITE)
GSIZE = 8209
GNUM = 79
LIM = GSIZE**GNUM

mod = GSIZE

bob_encr = 949466149013684769194106007085907150483179679883657963650373826780536359740002968990531772218497898792820189533496801635127997651332930433378150145536678650605630574982483885527918725111097957346602404856351824107789280538305441009593751460809038204504074506452852780479977817878535709573256789394567447379299
alice_encr = 1544648505151744161945707074785466501514735116544469276942998571927605788637573335136142527144706626077605305544981378031763827248247815794325909642974628021235544768486634918639813509385366833766797430695976565243715370305635128031518083593625736829965705480534702513367046280184451132276780764689328019739659
bob_decr = 1636856621831750800171484397508521251119605278869638004037184206519293828900709675159877130651027764989077774936886036039201359220822752590803350053644557946184732063186901191800113791055178015797009263719807198774079244840118610635369334310552469744958081927231303488581996787808657216275456787045070732936532

G = [gen(GSIZE) for i in range(GNUM)]
inv_G = [inverse(i) for i in G]

p = alice_encr
c = bob_decr
bob_key = 0
for i in range(GNUM):
    tmp_k = p % mod
    tmp_c = c % mod
    v = gexp(inv_G[i], tmp_k)
    k = v.index(tmp_c)
    bob_key += k * mod**i

    p = p // mod
    c = c // mod

assert bob_decr == enc(alice_encr, bob_key, [inverse(i) for i in G])
print('[+] bob_key =', bob_key)

k = bob_key
c = bob_encr
FLAG = 0
for i in range(GNUM):
    tmp_k = k % mod
    tmp_c = c % mod
    for m in range(mod):
        v = gexp(G[i], m)
        if v[tmp_k] == tmp_c:
            FLAG += m * mod**i
            break

    k = k // mod
    c = c // mod

FLAG = 76871779340382930140364082757893725756670997815507682187668114174006880171225340702701255553385668286759346086135363375731222723054246191618744264257000352085156951772305939671354711346576566087526062731546315319135351757201681066892582015960616637478287036538363003504778622319600379848866575123241982098906

assert bob_encr == enc(FLAG, bob_key, G)
print('[+] FLAG =', FLAG)

pattern = b'(EKAI{.+})'
for i in range(8):
    flag = long_to_bytes(FLAG >> i)
    m = re.search(pattern, flag)
    if m:
        flag = 'S' + m.group(1).decode()
        print('[+] flag =', flag)
        break

実行結果は以下の通りで、結果的には少しフラグを調整している。

[+] bob_key = 387039031009491100913746228307005179296502369387440550285145808740164902896831222150574522393258643711048824890863353406345391064507558964955812772343064882418049096949766525832482162637052838062946705289388066809272024728533423986001253383027276291217299036558193464077538490409172800440512799741986015757076
[+] FLAG = 76871779340382930140364082757893725756670997815507682187668114174006880171225340702701255553385668286759346086135363375731222723054246191618744264257000352085156951772305939671354711346576566087526062731546315319135351757201681066892582015960616637478287036538363003504778622319600379848866575123241982098906
[+] flag = SEKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}

SEKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}