InterKosenCTF 2020 Writeup

09-01-2021 - 1 minute, 35 seconds -
Crypto CTF Writeup 2020

InterKosenCTFにWani Hackaseで参戦して13位でした。

scoreboard

今回Discordにログが流れていましたが、自分のログが流れると達成感があるので結構好きです。

ciphertexts [crypto, 33 solves]

一目Common Modulus Attackが効きそうだが、\(n\)が異なるのでうまく行かない。

\[ \begin{eqnarray*} c_1 &=& m^{e_1} + k_1pq \\ c_2 &=& m^{e_2} + k_2pqr \end{eqnarray*} \]

となっているので、無理やり揃える方法として \(r^{e_1} c_1\), \(r^{e_2} c_2\) を考えてみると、

\[ \begin{eqnarray*} r^{e_1}c_1 = (rm)^{e_1} + k_1pqr^{e_1}\\ r^{e_2}c_2 = (rm)^{e_2} + k_1pqr^{e_2+1} \end{eqnarray*} \]

となる。2式に対して \(\mod n_2\) をとると、

\[ \begin{eqnarray*} r^{e_1}c_1 \equiv (rm)^{e_1} \mod n_2 = pqr \\ r^{e_2}c_1 \equiv (rm)^{e_2} \mod n_2 = pqr \end{eqnarray*} \]

となる。これでCommon Modulus Attackが適用できる。 \(rm\) の値が得られるので、\(r\) で割ってFlagゲット。

Flag: KosenCTF{HALDYN_D0M3}

padding oracle [crypto, 17 solves]

padding oracle attackやるだけだと思いきや、paddingの方法が少し違う。 とはいえ先頭にあるか末尾にあるかだけの違いなので、そこだけ直していけば良い。

Flag: KosenCTF{0r4c13_5urviv35_57i11_n0w}

bitcrypto [crypto, 17 solves]

復号する際に、legendre symbolの値に応じてbitを確定している。 最初のクエリでlegendre symbolが 1 or -1 になるような値が分かるので、これを並べ替えることで復号結果が目的のキーワードになるようなtokenを作ることができる。しかし、8バイト分しか手に入らないためキーワードを作るには不足している。 そこで \(\left( \frac{x}{p} \right) \equiv x^{\frac{p-1}{2}} \equiv -1 \mod p\) のとき、

\[ \left( \frac{x^{2k}}{p} \right) \equiv x^{k(p-1)} \equiv 1 \mod p \\ \left( \frac{x^{2k+1}}{p} \right) \equiv x^{k(p-1)} x^{\frac{p-1}{2}} \equiv x^{\frac{p-1}{2}} \equiv -1 \mod p \]

であることを利用してtokenに利用できる値を増やすことができる。

Flag: KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

ochazuke [crypto, 11 solves]

署名の際の \(k\) の値の決め方がランダムではないので、これを固定できれば秘密鍵が復元できそう。\(k\) はSHA1適用後のメッセージに依存しているので、衝突させれば固定できそうなことがわかる。 署名 \((r_i, s_i)\) は、秘密鍵\(d\)、署名するメッセージ \(m_i\)、SHA1後のメッセージ \(z_i = {\rm SHA1}(m_i)\) とすると、

\[ s_1 \equiv k_1^{-1}(m_1 + r_1 d) \equiv (dz_1)^{-1}(m_1 + r_1 d) \mod n \\ s_2 \equiv k_2^{-1}(m_2 + r_2 d) \equiv (dz_2)^{-1}(m_2 + r_2 d) \mod n \]

となる。ここでSHA1が衝突する場合、すなわち \(z = z_1 = z_2\) となる場合を考える。 \(s_1, s_2\) の式から \(z\) を消去すると、

\[ d \equiv (s_1m_2-s_2m_1)(r(s_2-s_1))^{-1} \mod n\]

と変形できる。ただし、 \(r = kG = dzG\)であるから \(r\) は等しくなる。\((r = r_1 = r_2)\) \(d\) が分かったので手元で署名すればOK。SHA1の衝突にはSHAtteredのpdfを使った。

Flag: KosenCTF{ahhhh_ochazuke_oisi_geho!geho!!gehun!..oisii...}

No pressure [misc, 16 solves]

zlibの性質を利用する。同じパターンが現れると圧縮されるので暗号化後に得られる文字列が短くなる。 KosenCTF{ で始まるはずなので、直後の文字を総当たりして暗号化結果が短くなる文字で確定していく。

from pwn import *
from base64 import b64decode
from string import ascii_letters, digits, punctuation 

s = remote('misc.kosenctf.com', 10002)

pts = ascii_letters + digits + punctuation
flag = 'KosenCTF{'

def encrypt(message):
    s.recvuntil('message: ')
    s.sendline(message)
    encrypted = s.recvline().split(b' : ')[-1].strip()
    encrypted = b64decode(encrypted)
    return encrypted

while True:
    candidate = None
    shortest, longest = 10000, -1
    for c in pts:
        check = flag + c
        length = len(encrypt(check))
        if length < shortest:
            shortest = length
            candidate = c
        longest = max(longest, length)
    if shortest == longest:
        break

    flag += candidate
    print(flag)
print('Result:', flag)

Flag: KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}