InterKosenCTF2020 writeup

CTF

InterKosenCTF2020へチームetherknotとして参加しました。
本番で解いた問題はciphertextsだけでしたが、1問でもチームに貢献できたのは少しだけ成長を感じました。
他の問題は手も足も出なかったので復習しつつwriteupを書こうと思います。

出題された問題まとめ

GitHub - theoremoon/InterKosenCTF2020-challenges

No pressure

問題
from Crypto.Cipher import ARC4
from hashlib import sha256
from base64 import b64encode
import zlib
import os

flag = open("./flag.txt", "rb").read()

nonce = os.urandom(32)
while True:
    m = input("message: ")
    arc4 = ARC4.new(sha256(nonce + m.encode()).digest())
    c = arc4.encrypt(zlib.compress(flag + m.encode()))
    print("encrypted! :", b64encode(c).decode())
解法

この問題はzlibの圧縮方式とRC4暗号がストリーム暗号のため暗号文の長さ==平文の長さというところに注目するらしいです。
zlibではgzip互換の圧縮を行います。
gzipではハフマン符号を使っているので同じ文字があると圧縮後の長さが短くなります。
圧縮する文字列はflag+mです。
そのためflagと同じ文字をmに入力すると圧縮結果が他のものと比べ短くなります。
それを利用して以下のようにブルートフォースをしてflagを求めます。

message: KosenCTF0
encrypted! : Y4CFC9swa7dx8K2rTBmb5YCrRGIRydbH+B8k2+wKNs49ZKSn6q/c0K+BVewfmxbh38Z48Ok4zrQVFuqTSsFuPOV0zUSAzy50FrV6Gf/1o2+P2Q==
message: KosenCTF1
encrypted! : WDXLybx1eLfLAecErH3bAOFBjOTFn60D0W4+L72R8DU3AqqoVes+inyIMdn0e9n/pQCSUsV/ps5uAL4PhYAP0lMU9fryBCK3hURmSSQXQ4gE0w==
message: KosenCTF{
encrypted! : IXIvFDbEHKCt0uzot+mUere+sAPka067nHBpjf+BEza1EAlD4XY5itNdQMOJ59uSqla9/L8vMq4XJFqMnFMCm7G7I+E9VlRJ5Ah8bhNEaQKq

flag形式はKosenCTF{hoge}なので{を入力した時だけ他と比べて暗号分が短くなっています。
このように先頭側から可能性のある文字列を総当たりで確かめていきます。

問題では圧縮後に暗号処理がかけられていますが、ストリーム暗号なので暗号化しても文字列長が変わらないためあまり気にしなくて良いみたいです(?)

これらを手動でやると死ぬほど時間がかかるのでスクリプトを書きます。

import string
from ptrlib import *
table = string.printable.strip()

sock = Socket('misc.kosenctf.com', 10002)
flag = 'KosenCTF'

while flag[-1] != '}':
    flags = []
    for c in table:
        s = flag + c
        sock.recvuntil('message: ')
        sock.sendline(s)
        sock.recvuntil('encrypted! : ')
        res = sock.recvline()
        flags.append((len(res), s))
        print(s)

    flag = sorted(flags)[0][1]
    print('flag:' + flag)

$ python3 solve.py
...

KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding|
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding~
flag:KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}

フラグが得られました。
KosenCTF{DEFLATE_is_an_algorithm_that_combines_LZ77_and_Huffman_coding}

ciphertexts

問題
from Crypto.Util.number import *
import gmpy2
from flag import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n1 = p * q
n2 = p * q * r

e1 = getPrime(20)
e2 = int(gmpy2.next_prime(e1))

m = bytes_to_long(flag)
c1 = pow(m, e1, n1)
c2 = pow(m, e2, n2)

print("n1 = {}".format(n1))
print("n2 = {}".format(n2))
print("e1 = {}".format(e1))
print("e2 = {}".format(e2))
print()
print("c1 = {}".format(c1))
print("c2 = {}".format(c2))

[output.txt]

n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709

c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546
r = 13153308347214003895808482482560134291168062759481395072905040534352582007414334817264912952166654018868070502935227685202993199880073486359721153499496448
解法

この問題ではe_1とe_2の値が近かったのでm^{e_2} \bmod n_2はm^{e_2} \bmod n_1と変わらないのではないかと仮定しました。
そう仮定するとn1==n2のため共通法攻撃が刺さります。

from Crypto.Util.number import *
from ptrlib import *

m = common_modulus_attack((c1, c2), (e1, e2), n1)
print(long_to_bytes(m))
$ python3 solve.py
b'KosenCTF{HALDYN_D0M3}'

完璧に勘でしたがflagが出ました。
KosenCTF{HALDYN_D0M3}

他の方のwriteupを参考に式を書くと

c_2=m^{e_2} \bmod n_2\\ (m^{e_2} \bmod n_2) \bmod n_1 = m^{e_2} \bmod n_1\\ c_2 \bmod n_1 = m^{e_2} \bmod n1\\

※数学弱弱なので式がおかしいかもしれません。マサカリお待ちしています。

n1|n2 (n2%n1==0)からこういった式が書け共通法攻撃が可能であると判断できます。
proは違いますね...

おまけ

この問題は簡単でしたが早めに取り組んでいたのでetherknotが4番目に解いたチームになっていました。嬉しい。
この並びに名前が入ることは今後あるのでしょうか。

(嬉しくて記念撮影)
f:id:kisaragi211:20200911182424p:plain

bitcrypto

問題
from Crypto.Util.number import *
from secret import flag

def legendre_symbol(x, p):
    a = pow(x, (p-1) // 2, p)
    if a == 0:
        return 0
    elif a == 1:
        return 1
    else:
        return -1

def key_gen(bits):
    p = getPrime(bits)
    q = getPrime(bits)
    n = p * q

    while True:
        z = getRandomRange(2, n)
        a, b = legendre_symbol(z, p), legendre_symbol(z, q)
        if a == -1 and b == -1:
            break

    return (n, z), (p, q)

def enc(pubkey, m):
    n, z = pubkey
    bits = [int(b) for b in "{:b}".format(m)]

    c = []
    for b in bits:
        while True:
            x = getRandomRange(2, n)
            if GCD(x, n) == 1:
                break
        c.append( ((z**b) * (x**2)) % n )
    return c

def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)

def main():
    pubkey, privkey = key_gen(256)

    keyword = "yoshiking, give me ur flag"
    m = input("your query: ")
    if any([c in keyword for c in m]):
        print("yoshiking: forbidden!")
        exit()

    if len(m) > 8:
        print("yoshiking: too long!")
        exit()

    c = enc(pubkey, bytes_to_long(m.encode()))
    print("token to order yoshiking: ", c)

    c = [int(x) for x in input("your token: ")[1:-1].split(",")]
    if len(c) != len(set(c)):
        print("yoshiking: invalid!")
        exit()

    if any([x < 0 for x in c]):
        print("yoshiking: wow good unintended-solution!")
        exit()

    m = long_to_bytes(dec(privkey, c))
    if m == keyword.encode():
        print("yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~")
        print(flag)
    else:
        print(m)
        print("yoshiking: ...?")


if __name__ == '__main__':
    main()

Goldwasser-Micali cryptosystemに関連した問題だそうです。
Goldwasser-Micali ...初耳だ。

解法

問題の流れとしては
1.テキトーな値を入力する.(keywordに含まれていない文字)
2.復号するとkeywordになるようなtokenを入力する。
3.復号結果が正しければflagが入手できる。

大まかに言えばこんな流れなのですが、道中とても難しかったです。

多分本来の動きとしてはkeywordと同じ文字を打って、帰ってきたtokenをもう一度入力すれば正しく動作する。
みたいなことだと思うのですが、もちろんそれはできません。
なのでとりあえず'b'などを入力して最初の2つのif文を突破します。

keyword = "yoshiking, give me ur flag"
m = input("your query: ")
if any([c in keyword for c in m]):
    print("yoshiking: forbidden!")
    exit()

if len(m) > 8:
    print("yoshiking: too long!")
    exit()

次に入力した文字列に対するtokenが出力されるのですが、これも私は無視します。
proの方はこの値をうまく使うようですが私には無理でした。

で、いよいよここからが問題。
どうにかして復号したらkeywordのbitに対応するようなtokenを作らないといけません。

keyword = "yoshiking, give me ur flag"
target = '0111100101101111011100110110100001101001011010110110100101101110011001110010110000100000011001110110100101110110011001010010000001101101011001010010000001110101011100100010000001100110011011000110000101100111'

decをみてみると

def dec(privkey, c):
    p, q = privkey
    m = ""
    for b in c:
        if legendre_symbol(b, p) == 1 and legendre_symbol(b, q) == 1:
            m += "0"
        else:
            m += "1"
    return int(m, 2)

ルジャンドル記号(\frac{b}{p})=1,(\frac{b}{q})=1となるbを与えれば0,そうでなければ1が生成できることに気がつきます。
なのでこれらの条件を満たしそうなtokenを作成してtargetと同じbit列を作るようにします。

ここで使用するp,qは素数なので以下のような式が成り立ちそうです。

\displaystyle{ (\frac{a}{p}) \equiv a^{\frac{p-1}{2}} \bmod p\\ a = x^2\\ (\frac{x^2}{p}) \equiv {(x^2)}^{\frac{p-1}{2}} \bmod p\\ (\frac{x^2}{p}) \equiv {x^{p-1}} \bmod p\\ }

最後の{x^{p-1}} \bmod pはフェルマーの小定理より１になります。(なるそうです)
まあ何が言いたいかというとbを素数の二乗にすると1が生成できるということです。

１が無限に生成できるようになったのでbit列の0に対応する部分は大丈夫そうです。
あとは1の部分ですが、これもわかると実は簡単(?)
ルジャンドル記号には以下のような性質があります。

(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p})

これを利用すれば平方剰余と \displaystyle{ (\frac{a}{p})=-1 } (平方非剰余)となるような値をかけることでこれまた-1を量産することができます。
-1を量産できると何が良いかというと、else文の方に分岐できるので1を量産できます。

1が量産できると0が量産できて、って感じで逆になっているので少しこんがらがります。

1つ(\frac{a}{p})=-1となるようなxを見つければあとは、x32, x52, ..., とxと素数を二乗したものをかければいけそうです。

書いたコード

from ptrlib import *
from Crypto.Util.number import bytes_to_long
from random import randrange, choice
from sympy import nextprime

target = '0111100101101111011100110110100001101001011010110110100101101110011001110010110000100000011001110110100101110110011001010010000001101101011001010010000001110101011100100010000001100110011011000110000101100111'
zero_cnt = target.count("0")
one_cnt  = target.count("1")
cnt = max(zero_cnt, one_cnt)

print(zero_cnt)
print(one_cnt)
print(cnt)

r = remote("crypto.kosenctf.com", 13003)
r.sendline(b"@")


zeros = []
prime = 3
for i in range(zero_cnt):
    zeros.append(prime**2)
    prime = nextprime(prime)

print(len(zeros))
print(zeros)

ones = [2]
for i in range(0, one_cnt):
    ones.append(ones[0]*zeros[i])

print(len(ones))
print(ones)

payload = []
one_i = 0
zero_i = 0
for i in target:
    if i == '1':
        payload.append(ones[one_i])
        one_i += 1
    else:
        payload.append(zeros[zero_i])
        zero_i += 1

print(payload)

r.sendline(str(payload))

r.interactive()

平方非剰余は2にしました。
2だと上手くいきます。詳しくはわかりません。教えてください。
平方数の性質がうんちゃらかんちゃら、っていう感じなのではないかと予想していますが...
なのでプログラムでは2x素数2を計算しています。
素数の列挙にはsympyにnextprimeという便利な関数があったのでそれを使いました。

$ python3 solve.py
your token: yoshiking: hi!!!! flag!!!! here!!! wowowowowo~~~~~~
KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

フラグが入手できました。

KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}

感想

1問解けたのは良かったですが他が撃沈していたのでこれから頑張りたいです。
問題は難しかったですがとても楽しかったです。
まだ解いていない問題があるので、復習しながら随時writeup更新していきたいなと思っています。
数式が多分おかしなことになっていると思うので、指摘していただけるとありがたいです。

参考

writeup関連

InterKosenCTF 2020 で作問した - yoshikingのがんばる日記
InterKosenCTF 2020 の write-up - st98 の日記帳
ciphertexts [InterKosenCTF 2020] - HackMD
InterKosenCTF2020 writeup - みつみつみつですか？

補足知識関連

平方剰余とルジャンドル記号 - 美的数学のすすめ
ルジャンドル記号とオイラーの規準 | 高校数学の美しい物語