Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

SECCON CTF 2021 writeup

official URL : SECCON CTF 2021


pppp

Great research on witch has made it possible to split and duplicate messages.
ファイル : problem.sage, output.txt

# problem.sage
from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q

mid = len(flag) // 2

e = 65537

m1 = int.from_bytes(flag[:mid], byteorder='big')
m2 = int.from_bytes(flag[mid:], byteorder='big')

assert m1 < 2**256
assert m2 < 2**256

m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]

# add padding
for i in range(4):
    for j in range(4):
        m[i][j] *= getPrime(768)

m = matrix(Zmod(p*q), m)

c = m^e

print("n =", n)
print("e =", e)
print("c =", list(c))

#output.txt
n = 139167515668183984855584233262421636549219808362436809125322963984953234794207403032462532211718407628015534917936237180092470832870352873174416729863982860547330562153111496168661222608038945799305565324740297535609102402946273092600303759078983973524662838350143815732516927299895302494977521033451618509313
e = 65537
c = [(92641859227150025014514674882433433169736939888930400782213731523244191029744271714915087397818608658221982921496921528927873080896272971564627162670330785041427348269531449548757383647994986600796703130771466176972483905051546758332111818555173685323233367295631863710855125823503925281765070200264928761744, 1077078501560459546238096407664459657660011596619515007448272718633593622581663318232822694070053575817000584000976732545349394411037957356817674297166036371321332907845398174111343765006738074197964396832305908342965034091516961317164203682771449331094865994143953470394418754170915147984703343671839620070, 19878161032897109459692857500488708331148676837923170075630073845924376353394086221031683671854185288619608305138965881628353471119235227157715699650190844508727073649527735233175347600167954253143204293274253676829607434380971492999430389536409563073620686264607716424139208756197843637115228155976163983619, 122958657434560838063916316490126514822437273152981380647634868499620566657448363565613345650206126542999322277498960954804580159527199119604554047697342524367459283765958189416627623253226055220105627822118413649499651442079969872322463271891353808314530249098525814619479135297014148780695960117897387220659), (0, 85635304452753185796593135650704585992713419302092444931829191186284566226617686976975731459756968679710078670232999566062343743901469759277582454092882685887985731708244015567469990157564460035983017331880588783841581502687752495254387549274422591338211161917565559735193456411356422539814020979699927207024, 26528377397409932803048052918715873209845190225305139460936852681030879561522825277119360099719008486268731610926098705442795761739644784858085976938906030639986454157616558457541083641717564142619063815917161350343604401278251069255966146207538326575595944701499010180658631016268689550402326369924649514049, 17173480018007185616783556851363148729840100207266610547324632027095687866456613104465211034834604995290825437734467654701021261504226847008483339028335703977866796341754911432666568936460974103742649586111260163432789617417125379644939110280618415377202845096157056174169392363954229816964869557167190373166), (0, 0, 81417110160690915414859599923077760437964436481940074249510026432592954854440295980578313776441414052192070135409849396229653279814546498083873720679422968334818254076803899882280264290639872486915551889441082468560654475422089052988909565455596584407805229280743723696618903551087160338683566908533474596220, 88524270641123978066493517684012199807956329430551155649688209766850898125045959831704501988313531767120589113923546449704920649814085765896894870692227804052901254644766662594723181025793077392532746071480212649880063471693730914835259139038459097504431147211622052068997412540488201406879310193174863792764), (0, 0, 0, 130146806238985078905344376697263038970354607413027156915068014483770022716717215156189413217688976902906182579031431264733207976605553885314360422441780388319618199732296392330859801016851191010568169307878720202422104375360360029207688301496478751250969744747470242179561459045172707909287093959859681318497)]

上三角行列をe乗しているようです。上三角行列ってe乗すると、対角成分は元の行列の対角成分をe乗した値になるんですね。これで、(x11×p)e, (x22×m1)e, (x33×m2)e, (x44)e (全てにmod n) が対角成分であることが分かりました(xij はgetPrime(768)で得られる素数)。(x11×p)e mod n はpの倍数かつnの倍数ではないのでgcd取ればnを素因数分解できます。そしてそこから秘密鍵を求めて、x22×m1, x33×m2を導出しました。

ここからどうしよう、となりとりあえずfactorDBに投げるとどちらも768bitの素数とその他になるような素因数分解はできませんでした。素因数分解できなかった値のbit長を見てみると835, 881ともうちょっとがんばったら素因数分解できそう(自分じゃできない)と思いsageに投げるもダメ。チームメイトに他に素因数分解してくれるサイト知らない？と聞くとこちらを教えてくれました。

Integer factorization calculator

x22×m1の素因数分解は5分程でできたので、x33×m2もすぐか？と思いましたが結局9時間かかりました。けど開始9時間以内に解いているチームもあったので、これは想定解ではないようです。

結局、あの行列をd乗すれば元に戻るみたいです。なんで？ そこからx22×m1とx23×m1をgcd取ればm1が出てきて同じ方法でm2も算出できるみたいです。


SECCON{C4n_y0u_prov'b'e_why_decryptable?}



cerberus

Cerberus is guarding a secret text.
nc cerberus.quals.seccon.jp 8080
ファイル：problem.py

#problem.py
import base64
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from flag import flag
import signal

key = get_random_bytes(16)
block_size = 16

# encrypt by AES-PCBC
# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
def encrypt(m):
    cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
    m = pad(m, 16)
    m = [m[i : i + block_size] for i in range(0, len(m), block_size)]

    iv = get_random_bytes(16)

    c = []
    prev = iv
    for m_block in m:
        c.append(cipher.encrypt(strxor(m_block, prev)))
        prev = strxor(c[-1], m_block)

    return iv, b"".join(c)


# decrypt by AES-PCBC
# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
def decrypt(iv, c):
    cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
    c = [c[i : i + block_size] for i in range(0, len(c), block_size)]

    m = []
    prev = iv
    for c_block in c:
        m.append(strxor(prev, cipher.decrypt(c_block)))
        prev = strxor(m[-1], c_block)

    return b"".join(m)


# The flag is padded with 16 bytes prefix
# flag = padding (16 bytes) + "SECCON{..."
signal.alarm(3600)
ref_iv, ref_c = encrypt(flag)
print("I teach you a spell! repeat after me!")
print(base64.b64encode(ref_iv + ref_c).decode("utf-8"))

while True:
    c = base64.b64decode(input("spell:"))
    iv = c[:16]
    c = c[16:]

    if not c.startswith(ref_c):
        print("Grrrrrrr!!!!")
        continue

    m = decrypt(iv, c)

    try:
        unpad(m, block_size)
    except:
        print("little different :(")
        continue

    print("Great :)")

PCBCモードなるものがあるんですね。unpadが成功したかどうかでサーバから送られる文字列が変わるのでPadding Oracle Attackのようです。

Padding Oracle Attack 分かりやすく解説したい - Attack All Around (最近こちらの記事がよく読まれているようで感謝しかありません)

けどこれはCBCモードとは異なり、暗号文と平文のxorがkeyによってdecryptされた値とxorしています。なので暗号文を変えてPadding Oracle Attackをしようとすると、それに対応する平文も変わりxorされる値がごっちゃになります。かつ問題ファイルにあるif文から貰った暗号文から始まる暗号文でないとdecryptしてくれないようです。そこで、ivを変えてPadding Oracle Attackすることを思いつきますが、その値をどうしたらいいのだろうとなりタイムアップ…。


暗号文は64バイトであることから4ブロックあることが分かります。それぞれc0, c1, c2, c3とすると、c0~c3+c3を送った際の第4ブロック(1つ目のc3)の復号でdec(c3)とxorする値をAとします。第5ブロック(2つ目のc3)の復号処理が終わると、その平文ブロックと暗号文ブロックをxorするとAになります。

p3 = A xor dec(c3)
p4 = dec(c3) xor c3 xor p3 = dec(c3) xor c3 xor A xor dec(c3) = c3 xor A
c3 xor p4 = c3 xor c3 xor A = A


同様に、c0~c3+c3+c2を送ると、最後の平文及び暗号文ブロックをxorした値は第3ブロック(1つ目のc2)の復号でdec(c2)とxorする値と同じになります。

これを繰り返して考えます。c0~c3+c3~c0を送ると、最後の平文及び暗号文ブロックをxorした値はivとなります。c0~c3+c3~c0+c0を送ると、最終ブロックの復号処理でこちらが送ったivとdec(c0)をxorした値が最終平文ブロックとなります。Padding Oracle Attackで最終平文ブロックがb"\x10"*16となるよう頑張ってivを変えていくと、dec(c0)の値が分かります。それを元のivとxorするとp0が分かります。以降piを求める場合、dec(ci)の値を求めて元のIVではなくc(i-1)とp(i-1)をxorした値とxorすればOKです。


SECCON{v._.^v-_-v^._.^_S0und_oF_0rpHeUs_Aha~~}