Attack All Around

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

WaniCTF'21-spring Crypto Writeup


大阪大学のCTF サークル Wani Hackaseさんが開催してくださりましたWaniCTFのWriteupです！初心者向けのCTFということもあり、かなり面白かったです。

https://score.wanictf.org/#/

今回はCrypto問について書いていきます。他の分野も少しだけ解けたのですが、もう少し出来るようになりたいですね。

Crypto問のOUCSは解き方に加え証明も書いているので、是非とも読んでいただければと思います。分かりやすく書いたつもりですが、不明瞭な点がありましたら、コメントしていただけますと嬉しいです。

f:id:partender810:20210501004041p:plain
全完達成！

Simple conversion [Begineer]

戻し方を忘れました…
ファイル：cry-simple-conversion.zip

convert.pyを見るとバイト列を整数にしているようですね。とりあえずlong_to_bytesしてみたらflagが出てきました。little endianならto_bytesを使えば良さそうですね。

from Crypto.Util.number import *
x = 709088550902439876921359662969011490817828244100611994507393920171782905026859712405088781429996152122943882490614543229
print(long_to_bytes(x))

FLAG{7h1s_i5_h0w_we_c0nvert_m3ss@ges_1nt0_num63rs}

Easy [Easy]

手始めに
ファイル：cry-easy.zip

encrypt.pyを見ると、[A-Z]を[0-25]に対応させてそれをxに入れ、a*x+b mod 26の式で暗号化しています。それの結果がoutput.txtに入っています。

outputの先頭4文字は"FLAG"が暗号化された文字列なので、そこからa, bを求めていきます。

  • "H" = a×"F" + b
  • "L" = a×"L" + b
  • "I" = a×"A" + b
  • "M" = a×"G" + b

となるa, bを求めていきますが、複雑なことはしません。mod 26の世界なのでa, b共に0~25でbrute forceすればOKです。

enc = "HLIM{OCLSAQCZASPYFZASRILLCVMC}"
test = "FLAG"
ans = []
for i in range(len(test)):
    temp = []
    for a in range(26):
        for b in range(26):
            t = encrypt(test[i],a,b)
            if t == enc[i]:
                temp.append([a,b])

    ans.append(temp)


for i in range(len(ans[0])):
    #ans[0][i]が他にもあるか探索
    check = True
    for j in range(1,len(ans)):
        ch = False
        for k in range(len(ans[j])):
            if ans[0][i] == ans[j][k]:
                ch = True
                break
        if not ch:
            check = False
            break
    if check:
        print(ans[0][i])

上記の4つの式の内、一番上の式に当てはまるa, bはans[0]に記憶し、その下の式はans[1], ans[2], ans[3]に入っています。ans[0][i]がans[1~3]にも含まれているかをcheckします。もっといいコードありそう。

コードを走らせると、a=5, b=8と一意に決まりました。あとはencrypt関数の逆を作ればOKです。

def decrypt(ct,a,b):
    pt = ""
    for x in ct:
        if ord("A") <= ord(x) <= ord("Z"):
            x = ord(x) - ord("A")
            for i in range(26):
                if x == (a*i+b)%26:
                    x = chr(i + ord("A"))
                    pt += x
                    break
        else: pt += x
    return pt

FLAG{WELCOMETOCRYPTOCHALLENGE}

Extra [Normal]

いつものRSA？
ファイル：cry-extra.zip

RSAの公開鍵(e,N)に加えて、M = 2×p+qが公開されています。これは解と係数の関係を使って解けそうです。Mがp+qならx2-N×x+Mの解がp, qになりますが、M = 2×p+qなので2×p, qが解になる二次方程式を立てます。二つの解の積2×p×qはNを2倍すれば手に入るので、解と係数の関係を利用してp, qを求めます。

二次方程式における解と係数の関係 | 高校数学の美しい物語

from Crypto.Util.number import *
import gmpy2
import math

N = (省略)
M = (省略)
e = 65537
c = (省略)
n = 2*N
ro, check = gmpy2.iroot(M*M-4*n,2)
assert check
q = (M-ro)//2
assert math.gcd(N,q) != 1
p = N//q
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,N)
print(long_to_bytes(m))

FLAG{@n_ex7ra_param3ter_ru1n5_3very7h1n9}

Can't restore the flag? [Hard]

ちりつもですよ
nc crt.cry.wanictf.org 50000
ファイル：cry-cant-restore-the-flag.zip

server.pyを見るとbytes_to_longしたflagに対して、300以下の数値を送るとその数で割った余りを教えてくれます。これはもう中国剰余定理ですね。2~300を全て送ってその余りを記憶してライブラリで解きます。300! > 10103 なので確実にflagを復元できます。

from sympy.ntheory.modular import crt
mod = []
val = []
for i in range(2,301):
    print(i)
    read_until(f,"Mod > ")
    s.send(str(i).encode()+b"\n")
    recv = int(read_until(f).strip())
    mod.append(i)
    val.append(recv)
m,_ = crt(mod,val)
print(long_to_bytes(m))

FLAG{Ch1n3s3_r3m@1nd3r_7h30r3m__so_u5eful}

OUCS [Very hard]

OUによるHomomorphicなCryptoSystemです
nc oucs.cry.wanictf.org 50010
ファイル：cry-oucs.zip

この問題解けたの嬉しかったですね。

ではまず暗号化について。n = p×p×qとしgp-1 mod p2 != 1であるgを選び、h=gn mod nとした(n,g,h)が公開鍵となります。plaintextをmとすると暗号文cは、c=(gm mod n × hr mod n) mod nとなります(r : 乱数)。hの条件より上記の式は

c = (gm mod n × (gn)r mod n) = gm+n×r mod n ・・・①

となります。

次に復号について。なぜserver.pyのコードで復号できるのでしょうか。

a = ( (cp-1 mod p2) - 1) // p ・・・②
b = ( (gp-1 mod p2) - 1) // p ・・・③
m = a × b-1 mod p ・・・④

まず、フェルマーの小定理 ( xp-1 mod p = 1) を使います。cp-1 = k'×p+1 (k' : 整数)となるので、k' != pである限り、②より(cp-1 mod p2) = k'×p+1となり、a=k'となります。同様に、gp-1 = k×p+1 (k : 整数)となるので、b=kとなります。ここで④より、k'/k = mとなります。故に、k'=k×mと置くことが出来ます。

k×m = ( (cp-1 mod p2) - 1) // p
k×m×p+1 = cp-1 mod p2 ・・・⑤

⑤を証明していきます。式①と式⑤に代入しています。n = p×p×qであるので、mod nの式をmod p2 の式に落とし込むことが出来ます。

k×m×p+1 = (gm+n×r mod n)p-1 mod p2 = (gm+n×r )p-1 mod p2
= g (m+n×r)×(p-1) mod p2

となります。さらに展開していきます。

k×m×p+1 = g (m+n×r)×(p-1) mod p2 = gm×(p-1) × gn×r×(p-1) mod p2

ここで、オイラーの公式( x φ(n) = 1 mod n )を使います。φ(p2) = p×(p-1)となります(p2と互いに素ではないp2以下の自然数は、p, 2p, 3p, ... , (p-1)p, pp のp個)。

n×r×(p-1) = p×p×q×r×(p-1) = A×p×(p-1)

であるので、gn×r×(p-1) mod p2 = 1です。故に、k×m×p+1 = gm×(p-1) となります、これをgp-1 = k×p+1 (k : 整数) が出てくるようにします。

k×m×p+1 = gm×(p-1) mod p2 = gp-1m mod p2 = (k×p+1)m mod p2

となります。ここで二項係数とパスカルの三角形を考えると、

パスカルの三角形 - Wikipedia

(k×p+1)m = (k×p)m + m×(k×p)m-1 + mC2 × (k×p)m-2 + ... + mC(m-2) × (k×p)2 + m×(k×p) + 1

となります。これをmod p2すると、後ろ2項以外はp2が含まれるので0となるのでm×(k×p) + 1となり、式⑤が証明されました。

では、これを使ってどのようにmを求めればいいのでしょうか。ここまで長い証明を読んで下さった方には申し訳ないですが、答えはあっさりです。
a = ( (cp-1 mod p2) - 1) // p = k×mとなるのに対しa' = 2×k×mとなるa'があれば、
a'×b-1 mod p2= 2×m mod p2となり、復号結果がflagと異なるので復号後その値をサーバが教えてくれるはずです。2×m < p となるのは希望的観測です。このくらいは耐えるだろう。

c = gm+n×r mod n より、c2 mod n = (gm+n×r mod n) × (gm+n×r mod n) = g2×(m+n×r) mod n

c' = c2 mod nとして復号してもらうと、

a = ( (c'^(p-1) mod p2) - 1) // p = ( (g2×(m+n×r) )p-1 mod p2 - 1) // p = (g2×m×(p-1) mod p2 - 1) // p

b = ( (gp-1 mod p2) - 1) // p

gp-1 = k×p+1 (k : 整数) より、

b = ( ( k×p+1 mod p2) - 1) // p = (k×p) // p = k

a = (g2×m×(p-1) mod p2 - 1) // p = ( (k×p+1)2×m mod p2 - 1) // p = (先程のパスカルの三角形より) ( ( 2×m×k×p+1 ) - 1) // p = 2×m×k

よって、a×b-1 mod p = 2×m×k×k-1 = 2×m となり、a'×b-1 mod p2= 2×m mod p2が成り立つa'をサーバに計算させることが出来ました。

長ったらしい証明をしましたが、公開鍵とcを受け取ってc2 mod nを計算して復号させ、得られた平文の値を2で割ってlong_to_bytes()するだけです。solverは結構短めです。

HOST, PORT = "oucs.cry.wanictf.org", 50010
s, f = sock(HOST, PORT)
for _ in range(10): read_until(f)
for _ in range(7): read_until(f)
read_until(f,"> ")
s.send(b"1\n")
recv_m = read_until(f).split()
c = int(recv_m[-1][2:],16)
for _ in range(8): read_until(f)
read_until(f,"> ")
s.send(b"4\n")
recv_m = read_until(f).split()
n = int(recv_m[-1][2:],16)
recv_m = read_until(f).split()
g = int(recv_m[-1][2:],16)
for _ in range(9): read_until(f)
c2 = pow(c,2,n)
read_until(f,"> ")
s.send(b"3\n")
read_until(f)
read_until(f,"> ")
s.send(str(c2).encode()+b"\n")
recv_m = read_until(f).split()
m2 = int(recv_m[-1][2:],16)
print(long_to_bytes(m2//2))

FLAG{OU_d0es_n0t_repre53nt_Osaka_University_but_Okamoto-Uchiyama}

Problems & Solver

GitHub - ksbowler/waniCTF_2021spring

おわりに

今回はcrypto問について書いていきました。

OUCSにおいて、証明までしっかりして解いたのは久しぶりでしたしflagが出たときの爽快感が半端なかったです！解いた人の中で証明までした人と、たまたま見つけた人との割合が気になります。この問題ならたまたまの人はそれなりにいるんじゃないかな。

他の分野はまだまだ分からないことだらけで、今年から少しずつ勉強していきたいと思います。もう5月だけど…
m1z0r3として出場するコンテストならともかく、個人戦の初心者向けのCTFならある程度解けるようになりたいですね。