2020-06-06

HSCTF 7 (2020) Writeup

CTF_Writeup

2020年6/1 ~ 6/6に開催されたHSCTF 7 にm1z0r3として参加しました。Crypto問はあと1問で全完だったので悔しかったです..

自分が解いたCrypto問題のWriteupを書きます。

Chonky E
Randomization 1
Randomization 2
Extremely Complex Challenge
その他

Chonky E

問題文をみると、AlleyはRSA、JasonはSchmidt-Samoaという暗号化手法でメッセージを暗号化を行った。ただし、2人とも同じ素数の組（p, q）を用いているとのこと。

解法

明らかにAlleyが使用した公開鍵eの値が大きいため、wiener's attackによって秘密鍵dは直ぐに計算できる。

問題は次のJasonが使用したSchmidt-Samoa暗号を破ること。

Schmidt-Samoa暗号は次のように鍵生成、暗号化、復号を行う。

鍵生成

$$ N = p^2*q\\ d = N^{-1} \;mod \;lcm(p-1,q-1) $$

暗号化

$$ c = m^N\;mod\;N $$

復号

$$ m = c^d\;mod\;pq $$

したがって、復号するためにはp, qを求める必要がある。

d, e, Nが分かってるので、ここから素因数分解する方法があるんじゃないかと考えて調べてみると、次の記事を見つけた。

https://www.di-mgt.com.au/rsa_factorize_n.html

ここにあるとおりに実装をするとp, qの組が得られる。あとは上に示した通りにSchmidt-Samoa暗号の復号を行う。

#solver.py
from RSAwienerHacker import *
from Crypto.Util.number import *
import random
e = 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717
n = 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313
c_j = 16267540901004879123859424672087486188548628828063789528428674467464407443871599865993337555869530486241139138650641838377419734897801380883629894166353225288006148210453677023750688175192317241440457768788267270422857060534261674538755743244831152470995124962736526978165448560149498403762447372653982922113772190234143253450918953235222315161964539311032659628670417496174123483045439359846360048774164337257829398345686635091862306204455687347443958931441225500856408331795261329035072585605404416473987280037959184981453888701567175803979981461050532113072292714696752692872526424122826696681194705563391161137426703690900733706866842363055967856443765215723398555522126909749236759332964873221973970368877565410624895160438695006432021529071866881905134494489266801004903504121740435965696128048690741210812963902631391765192187570107372453917327060678806282122942318369245760773848604249664378721970318257356486696764545 

d = hack_RSA(e, n)
print(d)

## calc p,q from e, n, d
k = e*d - 1
Is_Finish = False
while True:
    t = k
    g = random.randint(2, n-1)
    #t= k
    while t%2 == 0: 
        t = t//2
        x = pow(g, t, n)
        y = GCD(x-1, n)
        if x > 1 and  y > 1:
            print("Finish!")
            q = y
            p = n//q
            Is_Finish = True
            break
    if Is_Finish:
        break
print("p: {}".format(p))
print("q: {}".format(q))

n_j = pow(p,2)*q
phi = (p-1)*(q-1)
d_j = inverse(n_j, phi)
m = pow(c_j, d_j, p*q)
print(long_to_bytes(m))

Flag: flag{remarkably_superb_acronym}

Randomization 1

アセンブラを読むと、Guess してほしい数字は前の数字をprev_numとすると 0x25*prev_num+0x41)&0xff

とわかるので、その計算をするようにコードを書く。

#solver.py
from pwn import *
#nc crypto.hsctf.com 6001

io = remote("crypto.hsctf.com", 6001)

def Guess(prev_num):
    print(io.recvuntil("Guess my number:"))
    next_num = (0x25*prev_num+0x41)&0xff
    print("next_num: {}".format(next_num))
    io.sendline(str(next_num))
    return next_num


print(io.recvuntil("free number:"))
free_num = int(io.recvline())
print("free_num: {}".format(free_num))
prev_num = free_num
for _ in range(10):
    prev_num = Guess(prev_num)

print(io.recvall())

Flag: flag{l1n34r_c0n6ru3n714l_63n3r470r_f41lur3_4b3bcd43}

Randomization 2

次は計算が0x5DEECE66D*prev_num+0xB)&0xffffffffffffffffになっただけなので、この部分だけRandomization 1のスクリプトから変えればよい。

#solver.py
from pwn import *

io = remote("crypto.hsctf.com", 6002)

def Guess(prev_num):
    print(io.recvuntil("Guess my number:"))
    next_num = (0x5DEECE66D*prev_num+0xB)&0xffffffffffffffff
    print("next_num: {}".format(next_num))
    io.sendline(str(next_num))
    return next_num

print(io.recvuntil("free numbers\n"))

free_num_1 = int(io.recvline())
free_num_2 = int(io.recvline())
print("free_num_1: {}".format(free_num_1))
print("free_num_2: {}".format(free_num_2))

prev_num = free_num_2
for _ in range(10):
    prev_num = Guess(prev_num)

print(io.recvall())

Flag: flag{1n53cur3_r4nd0m_46b8861b}

Extremely Complex Challenge

楕円曲線暗号の問題。まずは与えられたp = 404993569381, b = 54575449882, 生成元となる点 (g_x, g_y) = (391109997465, 167359562362)の情報から、y² = x³ + ax + b における a の値を求める。ここは単純に a = (g_y^2 - g_x^3 - b)g_x^-1 mod p を計算する。

これによって楕円曲線の式が求まるが、ここから公開鍵 (209038982304, 168517698208)を使ってどうやって秘密鍵を求められるのか？

楕円曲線上における公開鍵は生成元Gよりx倍された点 (xG)を示しており、通常であればこの (xG)からxの値を求めることはできない（楕円曲線上の離散対数問題）。

しかし今回は数字が小さいため、SageMathを用いて次のように簡単に解くことができる。

#solver.sage.py
from sage.all_cmdline import *
from Crypto.Util.number import *

p= 404993569381
b = 54575449882
g_x = 209038982304
g_y = 168517698208
# Calc a
a = ((pow(g_y, 2, p)  - pow(g_x, 3, p) - b  )* inverse(g_x, p))%p
print("a: {}".format(a))
#a = 316508952642

# Calc d
R=Zmod(p)
E=EllipticCurve(R, [a,b])

Pk = E(g_x, g_y)
G= E(391109997465, 167359562362)

d = G.discrete_log(Pk)
print("flag{{{}}}".format(d))

Flag: flag{17683067357}

その他

Affina and the Quadratics は暗号文をみて「Affine_is_interestingじゃね？」と思ってリートにして入力したら通ってしまいました。これどうやるんだろう。。26 character charsetってアルファベットじゃないのかな。。

2020-06-01

RCTF 2020 Writeup easy_f(x)

CTF_Writeup

2020年5/30 ~ 6/1 に開催されたRCTF 2020に参加して、なんとか1問（easy_f(x) ）解けたのでそのWriteupを書きます.

easy_f(x)

Proof of Work

124.156.140.90 2333につないでみると、次のような応答が返ってくる。

sha256(XXXX+ydl3MyCipSFFKKAl) == 7be4d6e89b8c5d6c33cade48c8bff97bb1670c340536d660f47dc99b835d97df
Give me XXXX:

よく登場するProof of Workですね。この例ではydl3MyCipSFFKKAlを加えた後のsha256ハッシュ値が

7be4d6e89b8c5d6c33cade48c8bff97bb1670c340536d660f47dc99b835d97df となる最初の4文字を見つけろというもの。

server.pyを見ると、英数字のみ（string.ascii_letters+string.digits）が使用されているため、それらを用いて総当たりするだけ。最悪の場合でもそこまで時間はかからない。

Calculating Check

ここがかなり大変な部分。。

まず、情報を整理するとKはランダムな数値が513（check+ Pbits）格納されているリスト。そしてここでの目標はこのランダムな数値checkを求めること。

関数fではKの長さである513回r = (r + k[i] * pow (x, i, m)) % mの処理が行われているため、

f(x) = rは次の式で表せられる。

$$ f(x) = check + K_1*x+K_2*x^2 + .. + K_{512}*x^{512} \;mod \;m $$

ここで、未知数は $K_i (i = 1,2,..,512)$ であるため、 checkがなければ、512個の式をもらえれば全てのKの値が求まる。しかし、checkが邪魔となる。そこで式を$512*2 = 1024$個受け取り、互いに引いてcheckを消して$K_1$から$K_{512}$の値を求めれば、

$$ check = f(x) - K_1*x - K_2*x^2 .. \;mod \;m $$

という計算式でcheckの値を求められる。

以上の説明を式にすると次のようになる。

$$ f_1(x_1) - f_{513}(x_{513}) = K_1(x_1- x_{513}) + K_2(x_1^2 - x_{513}^2) + .. + K_{513}(x_1^{512} - x_{513} ^ {512}) \; mod \;m\\ f_2(x_2) - f_{514}(x_{514}) = K_1(x_2- x_{514}) + K_2(x_2^2 - x_{514}^2) + .. + K_{513}(x_2^{512} - x_{514} ^ {512}) \; mod \;m\\ ..\\ ..\\ f_{512}(x_{512}) - f_{1024}(x_{1024}) = K_1(x_{512}- x_{1024}) + K_2(x_{512}^2 - x_{1024}^2) + .. + K_{513}(x_{512}^{512} - x_{1024} ^ {512}) \; mod \;m $$

これによって、未知数 $K_i$ が512個である連立方程式となったため、解くことが可能である。

ただ、自分はpythonでmod上での連立方程式（特に今回のような大規模なもの）を解く方法を知らなったので、ローカルにインストールしていたSageMathを使って解きました。それでも解くのに4分くらいかかったので、ミスがあった時に修正して試すのにかなり時間がかかってしまって大変でした。。

solverは以下。

from sage.all_cmdline import * 
import os,random,sys,string
from hashlib import sha256
from Crypto.Util.number import *
from minipwn import *
from tqdm import tqdm
import time

Pbits = 512

def Get_Hash():
    recv_m = io.recvline().strip()
    print(io.recvuntil("Give me XXXX:"))
    str_4_ = recv_m[recv_m.find(b"+")+1:recv_m.find(b")")].strip()
    sha256_hash = recv_m.split(b"==")[1].strip()
    print("str_4_: {}".format(str_4_))
    print("sha256_hash: {}".format(sha256_hash))
    return str_4_, sha256_hash


def Proof(str_4_, sha256_hash):
    Cand_list = list(string.ascii_letters+string.digits)
    for i in tqdm(range(len(Cand_list))):
        c_1 = Cand_list[i]
        for c_2 in Cand_list:
            for c_3 in Cand_list:
                for c_4 in Cand_list:
                    cand_4 = c_1 + c_2 + c_3 + c_4
                    cand =  cand_4.encode() + str_4_
                    sha_hex = sha256(cand).hexdigest()
                    if sha_hex == sha256_hash:
                        print("Find! cand: {}".format(cand))
                        print("sha_hex: {}".format(sha_hex))
                        print("send: {}".format(cand_4))
                        io.sendline(cand_4)
                        return 
    print("Fail to find..")
    return 0

def Get_Values(times):
    recv_m = io.recvline()
    print("recv_m: {}".format(recv_m))
    M = int(recv_m.split(b"=")[1].strip())
    print("M: {}".format(M))
    print(io.recvuntil("How many f(x) do you want?"))
    io.sendline(str(times))
    print(io.recvline())
    x_list_1 = []
    x_list_2 = []
    r_list_1 = []
    r_list_2 = []
    half_times = times//2
    for i in tqdm(range(times)):
        recv_m = io.recvline().strip()
        x = int(recv_m[recv_m.find(b"(")+1: recv_m.find(b")")].strip())
        r = int(recv_m.split(b"=")[1].strip())
        #print("x: {}".format(x))
        #print("r: {}".format(r))
        if i < half_times:
            x_list_1.append([pow(x, j, M) for j in range(1, Pbits+1)])
            r_list_1.append(r)
        else:
            x_list_2.append([pow(x, j, M) for j in range(1, Pbits+1)])
            r_list_2.append(r)
    return M, x_list_1, x_list_2, r_list_1, r_list_2


def Find_Check():
    R = IntegerModRing(M)
    r_diff_list = [r_list_1[i] - r_list_2[i] for i in range(len(r_list_1))]
    x_diff_list = [[x_list_1[i][j] - x_list_2[i][j] for j in range(len(x_list_1))] for i in range(len(x_list_1[0]))]
    
    r_Vec = vector(R, r_diff_list)
    x_Mat = Matrix(R, x_diff_list)

    print("Now Solving...")
    start = time.time()
    K_list = x_Mat.solve_right(r_Vec)
    end = time.time()
    print("Elapsed: {}".format(end - start))
    #print("K_list: {}".format(K_list))
    print("K_len: {}".format(len(K_list)))

    # check = f(x) - k1*x - k2*x^2 - k2*x^3 ..
    A = r_list_1[0]
    B = sum([(K_list[i]*x_list_1[0][i])%M for i in range(len(x_list_1))])%M
    print("A: {}".format(A))
    print("B: {}".format(B))

    check = (A - B)%M
    print("check: {}".format(check))
    io.sendline(check)


io = remote("124.156.140.90", 2333)

str_4_, sha256_hash = Get_Hash()
Proof(str_4_, sha256_hash.decode())
M, x_list_1, x_list_2, r_list_1, r_list_2 = Get_Values(times = 1024)
Find_Check()

while True:
    print(io.recvline())

Flag: RCTF{A_e4siest_sh4mlr_s3cr3t_sh4rIng!!}

2020-05-25

SECCON Beginners CTF 2020 Writeup

2020年 5/23 ~ 5/24 に開催されたSECCON Beginners CTF に m1z0r3の一員で参加してきたのでいくつかWriteup上げてみます。Crypto問を主に解いたのでそれについて。

R&D [52pts]
Noisy equation [261pts]
RSA Calc [319pts]
Encrypter [414pts]

※自分で解いた問題・・RSA Calc, Encrypter ※他のメンバーが先に解いて後追いして解いた問題・・R&B, Noisy equations

問題のスクリプト等は https://github.com/ys-5441/Seccon_Beginners_2020 を参照してください。

R&D [52pts]

唯一Beginnersっぽいと感じた問題

"R"または"B"というformatにしたがってrot-13とbase64によるエンコードを繰り返して先頭に"R"または"B"を加えているだけ。なので先頭がどちらかを見ながらrot-13とbase64デコードを繰り返すだけ。

#solver.py
from base64 import b64decode
import codecs
with open("encoded_flag", "r") as f:
    ct = f.read()
idx = 0
ct_tem = ct
flag = ""

while True:
    if ct_tem[0] == "R":
        ct_tem = codecs.decode(ct_tem[1:], "rot-13")
    else :
        ct_tem = b64decode(ct_tem[1:])
    print(ct_tem)
print(flag)

Flag: ctf4b{rot_base_rot_base_rot_base_base}

Noisy equation [261pts]

44次元の連立方程式の問題。

coeffs = [x11, x12, .., x1n], [x21, x22, .. ,xnn] , .. ], answers = [a1, a2, .., an], flag = [f0, f1, .., fn]とおくと、問題の式は次のようになる。Aはseedを加えた後の getrandbits(L) の値。

$$ \begin{pmatrix}a_{1}\\a_{2}\\\vdots\\a_{n}\end{pmatrix} = \begin{pmatrix} x_{11} & x_{12} &..& x_{1n} &A\\ \vdots & \vdots& \ddots& \vdots&\vdots\\ x_{n1} &x _{n2}&..& x_{nn} &A\end{pmatrix}\begin{pmatrix}f_{1}\\f_{2}\\\vdots\\f_{n}\end{pmatrix} $$

Aが邪魔なため、もう一度サーバからcoeffs, answersを受け取り、差分を取る。

差分を取った後の $a,x$ を $ad, xd$ とおくと

$$ \begin{pmatrix}ad_{1}\\ad_{2}\\\vdots\\ad_{n}\end{pmatrix} = \begin{pmatrix} xd_{11} & xd_{12} &..& xd_{1n} \\ \vdots & \vdots& \ddots& \vdots\\ xd_{n1} &xd_{n2}&..& xd_{nn} \end{pmatrix}\begin{pmatrix}f_{1}\\f_{2}\\\vdots\\f_{n}\end{pmatrix} $$

となり、簡単に計算できる形になる。

初めこれをsympyでローカルで解こうとしてみたらとんでもなく時間がかかるため（冷静に考えて値と次元数がこれだけ多いと厳しい..）、sageで次のようにして解いた。

Xd = matrix([ [xd11, xd12, .., xd1n], [xd21, xd22, .. ,xdnn] , .. ])
Ad = vector([ad1, ad2, .., adn])
F = Xd.solve_right(Ad)

あとはFの値を全て文字に変換すればFlagが得られる。

Flag: ctf4b{r4nd0m_533d_15_n3c3554ry_f0r_53cur17y}

※他の方のWriteupをみているとnumpyでfloat64型を使えばローカルで問題なくできるようです。

RSA Calc [319pts]

RSA署名の問題。 server.pyを読むと、"1337,F"という文字列の署名が得られれば勝ちなのが分かる。

しかし、当然その1337やFが文字列に入っていると署名をもらえない。

そこで、"1337,F"を素因数分解してそれぞれを署名してもらい、掛け合わせれば"1337,F"の署名が手に入る。

なぜこれでできるのかというと、次のことが成り立つから。

$X= a*b$とすると、

$$ (a^d\;mod \;N) * (b^d \;mod \;N) \\ = (a*b) ^d \;mod \;N\\ = X^d \;mod \;N $$

実装したsolverは以下。

#solver.py
from pwn import *
from Crypto.Util.number import *
import sympy
from functools import reduce
from operator import mul
from itertools import combinations
import sys

io = remote("rsacalc.quals.beginners.seccon.jp", 10001)
#io = remote("localhost", 10001)

def Get_N():
    recv_m = io.recvuntil("3) Exit").strip()
    print("recv_m: {}".format(recv_m))
    N = recv_m.split("\n")[0].split(":")[1].strip()
    print("N: {}".format(N))
    return int(N)


def Sign(data):
    io.sendline("1")
    print(io.recvuntil("data>"))
    io.sendline(data)
    recv_m = io.recvline().strip()
    print("recv_m: {}".format(recv_m))
    sig = recv_m.split()[1].strip()
    print("sig:{}".format(sig))
    print(io.recvuntil("3) Exit"))
    return sig


def Exec(data, sig):
    io.sendline("2")
    print(io.recvuntil("data>"))
    io.sendline(data)
    print(io.recvuntil("signature>"))
    io.sendline(sig)
    recv_m = io.recvline()
    print(recv_m)
    if "Error" in recv_m or "Invalid" in recv_m:
        io.close()
        return
    print(io.recvline())
    
N = Get_N()

payload  =  "1337,F"
#print(sympy.factorint(bytes_to_long(payload)))
#Factors: factors of payload 
Factors = [1081919446939, 2*5*5]

Sig = []
for i in range(len(Factors)):
    data = long_to_bytes(Factors[i])
    sig = Sign(data)
    Sig.append(int(sig, 16))
#print(Sig)
send_sig = hex(reduce(mul, Sig)%N)[2:]
assert send_sig < 0 or send_sig >= N
#print("send_sig: {}".format(send_sig))
Exec(payload, send_sig)
io.close()

Flag: ctf4b{SIgn_n33ds_P4d&H4sh}

2019 VolgaCTF Blindの類題ですね。

Encrypter [414pts]

最初よく分からなかったが、メンバーの教えでPadding Oracleだと気づき、実装しました。

Decryptにbase64デコードに失敗するものや、16バイト長になっていないものを送るとerror:0606506D:digital envelope routines:EVP_DecryptFinal_ex:wrong final block length

と表示され、パディング処理に失敗するとerror:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decryptと表示されるっぽい。

なのでサーバ側ではAESのCBCモードで暗号/復号を行っていると仮定して、Encrypted Flagで暗号化されたフラグを手に入れ、Padding Oracle をする。

http://rintaro.hateblo.jp/entry/2017/12/31/174327 の記事を参考にさせて頂きました。

solverは以下（Python2系）

# -*- coding: utf-8 -*-
#solver.py
from tqdm import tqdm
import requests
import json
import time
from base64 import b64decode, b64encode
from Crypto.Util.number import isPrime, bytes_to_long, long_to_bytes
import sympy
from binascii import hexlify , unhexlify
from tqdm import tqdm
import sys

block_size = 16


def IsPadding_OK(c_t, Dec_ci, m_prime, c_prev_prime):
    
    attempt_byte = "\x11" * (block_size-m_prime) + chr(c_prev_prime)
    adjusted_bytes = ""
    for c in Dec_ci:
        adjusted_bytes += chr(ord(c) ^ m_prime)

    content = attempt_byte.encode('hex') + adjusted_bytes.encode('hex') + c_t
    #print(content)
    payload = {"mode": "decrypt", "content": content.decode("hex").encode("base64")}
    #print("payload: {}".format(payload))
    r = requests.post("http://encrypter.quals.beginners.seccon.jp/encrypt.php", data = json.dumps(payload))
    
    res = r.content
    #print("res: {}".format(res))
    if "ok" in res.decode():
        print("res: {}".format(res))
        return True
    else:
        return False


enc_flag = "bezb4nnncZqltGeA46QkrHbHHo/pUh3M+Zu/WxJE+wdglDFot1jmmxNycOKpoMSZTxyJxVMkKF3rBeCZrT6Ozw=="
cipher_text = b64decode(enc_flag).encode("hex")
cipher_text = cipher_text.zfill(len(cipher_text) + len(cipher_text) % block_size*2).decode('hex')
print("cipher_text: {}".format(cipher_text))


cipher_block = [cipher_text[i: i+block_size] for i in range(0, len(cipher_text), block_size)]
cipher_block.reverse()
plain_text = ""
print("cipher_block: {}".format(cipher_block))

for i in tqdm(range(len(cipher_block)-1)):
    c_t = cipher_block[0].encode('hex')
    c_p = cipher_block[1].encode('hex')
    cipher_block.pop(0)

    m_prime = 1
    c_prev_prime = 0
    m = Dec_ci = ""
    while True:
        if IsPadding_OK(c_t, Dec_ci, m_prime, c_prev_prime):
            print "0x{:02x}: ".format(c_prev_prime) + "{:02x}".format(m_prime) * m_prime
            m += chr(c_prev_prime ^ m_prime ^ ord(c_p.decode('hex')[::-1][m_prime-1]))
            Dec_ci = chr(c_prev_prime ^ m_prime) + Dec_ci
            m_prime += 1
            c_prev_prime = 0
            if m_prime <= block_size:
                continue
            break
        c_prev_prime += 1
        if c_prev_prime > 0xff:
            print "[-] Not Found"
            break
    print "Dec(c%d): %s" % (len(cipher_block), Dec_ci.encode('hex').zfill(block_size*2))
    print "m%d: %s" % (len(cipher_block), repr(m[::-1]))
    plain_text = m[::-1] + plain_text
    print "plain_text:", repr("*" * (len(cipher_text)-len(plain_text)-block_size) + plain_text) + '\n'

Flag: ctf4b{p4d0racle_1s_als0_u5eful_f0r_3ncrypt10n}