【IMCTF 2021】公式writeup crypto編（static random👽除く）

はじめに

IMCTFは名古屋大学CTF・競プロサークル(非公認) Ir0nMaiden が開催する初心者向けのCTFです。
IMCTF 2021は12/18 12:00〜12/19 12:00(JST)にわたって開催されました。
私は「static random👽」を除くcrypto 5問を作問したので、そのwriteupを以下に記します。

• 【crypto】 oreore
• 【crypto】 love letter
• 【crypto】 common
• 【crypto】 pxkemxn
• 【crypto】 origin

【crypto】 oreore

28 Solves

問題

太郎君は天才なので独自暗号を発明しました。彼によると最も安全な暗号らしいですが...

gen.py

import base64

flag = b"FLAG"

def oreore_crypto(flag):
    encoded = base64.b64encode(flag)
    enc = encoded.hex()
    return enc

print("ciphertext =", oreore_crypto(flag))

output.txt

ciphertext = 6157316a64475a374d484a6c4d484a6c58324e79655842304d4639706331397a6458426c636c397a5a574e31636d5639

解答

gen.pyをみるとflagがbase64でエンコードされた後に16進数に変換されていることがわかります。16進数の暗号文をバイト列に戻し, base64でデコードしてあげればflagが手に入ります。

solve.py

import base64

ciphertext = "6157316a64475a374d484a6c4d484a6c58324e79655842304d4639706331397a6458426c636c397a5a574e31636d5639"

def decrypt(enc):
    dec = bytes.fromhex(enc)
    flag = base64.b64decode(dec)
    return flag

print(decrypt(ciphertext)) # b'imctf{0re0re_crypt0_is_super_secure}'

flag

imctf{0re0re_crypt0_is_super_secure}

【crypto】 love letter

27 Solves

問題

クリスマスのエモいエピソードを解読してフラグをゲットしましょう。

ewvnuwjq wlte b cupl cleelx eu ibtbiu rux fjxqwehbw. ewvnuwjq cqilw fer, wu jl vwlk ejl rcbz eu ldgxlww hn brrlfequt. ejl cupl cleelx mbw qhfer{lnl_cupl_nuv_ibtbiu_nlbbbbj}. ibtbiu mbw wjufilk btk euwwlk ejl cupl cleelx.

解答

単一換字式暗号の問題です。wikipediaの説明を引用します。

単一換字式暗号（たんいつかえじしきあんごう、Simple substitution cipher）とは、換字式暗号の一種で、平文の文字に対して、暗号文の文字が常に同じ文字に変換されるような暗号のこと。例えば、平文の“d”が、暗号文で必ず“a”になるならば、それは単一換字式暗号である。

flagらしき部分qhfer{lnl_cupl_nuv_ibtbiu_nlbbbbj}などから頑張って推測すると（雑）、以下のような対応で元のアルファベットが変換されていることがわかります。 aがb、bがs、cがf...のように変換されています。

abcdefghijklmnopqrstuvwxyz
bsfklrzjqoichtugaxwevpmdny

あとは、対応の通りに暗号文をもとに戻してあげるとflagを含んだ平文が手に入ります。

solve.py

def decrypt(input_text):
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    cipher_alphabet = 'bsfklrzjqoichtugaxwevpmdny'
    encryption = ''

    for i in input_text:
        if i == " ":
            encryption += " "
            continue
        if i in [".", ",", "{", "}", "_"]:
            encryption += i
            continue
        index = cipher_alphabet.index(i)
        encryption += alphabet[index]
    return encryption

input_text = "ewvnuwjq wlte b cupl cleelx eu ibtbiu rux fjxqwehbw. ejqw qw b cupl cleelx mxqeelt sn ewvnuwjq uplx b cutz glxquk ur eqhl. ewvnuwjq cqilw fer, wu jl vwlk ejl rcbz eu ldgxlww hn brrlfequt. ejl cupl cleelx mbw qhfer{lnl_cupl_nuv_ibtbiu_nlbbbbj}. ibtbiu mbw wjufilk btk euwwlk ejl cupl cleelx."
result = decrypt(input_text)
print(result)

# 出力結果
# tsuyoshi sent a love letter to kanako for christmas. tsuyoshi likes ctf, so he used the flag to express my affection. the love letter was imctf{eye_love_you_kanako_yeaaaah}. kanako was shocked and tossed the love letter.

また、quipqiupのようなツールを使用して復号することもできます。

flag

imctf{eye_love_you_kanako_yeaaaah}

【crypto】 common

25 Solves

問題

flagが2回暗号化されているようです。

gen.py

from Crypto.Util.number import *

flag = b"FLAG"
m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = 65536
e2 = 65538

print("n =", n)
print("e1 =", e1)
print("c1 =", pow(m, e1, n))
print("e2 =", e2)
print("c2 =", pow(m, e2, n))

output.txt

n = 21141157755370440356159016558867591002795131037765353220781763950242197787546988623583333748613811615876039600044067795582387314625044873018261912055648316947575307397145571269092683237196318163742534102252564452361648000741215145961263035358948910750394941304616916013217678630294578579032413375393774307079767343057241805957456859330160131811246961956716626217712879502367810458962663138839207104998925545962808329297100387478763021607429645752111666523372296094568288414788741918520918522347389517685977356020153749161423831061236785869435119648010372663034476232600939002450611487244980761240697255092515294619063
e1 = 65536
c1 = 3791139181938569737398685036032381737646987513051659017777895787043616313081106838760662536132081707503545049439606032069727376790572333643094529595081085118571506461893089039469054703087386815141490544138726142314337827447061522144729907408053083672097701520947030283539764963562701091579919487153984526052282424975277999492006498441654336183574233720547915500793830555227254993335348447191157770264921144000194606354966874727918714437428556969904356868934618577114911104025392029907939301331113924863412657322707967483351467004854177190395076310650546542866389721479249039989850401261446124771193559166329619972412
e2 = 65538
c2 = 9479987054301003593696498729807102589604512322454236806662495038269939932383233766107579478386705533651017857595249113906203900757985576318399557582785561924440535008414598465159052407108648112038858687677552218404377633749009339690058222162908839308847763582094729669124528370642665466262258176588951705959922822288462616323273663488143476234490690202535922260303842658128571121608034815328952318543895796544411651444423903851422043107669054499710424643274879906277104856140792871842468587164924689276336292808339852752054246714774764674969279059667783378523996744567909634744703888058392004064096159069736198607229

解答

RSA暗号の問題です。RSA暗号の詳細はwikipediaからご覧ください。

RSA暗号において、平文 $m$ を $n$ が同一かつ $e$ が異なる公開鍵 $(n, e_1),(n,e_2)$ でそれぞれ暗号化した暗号文 $c1, c2$ がある時、$n, e_1, e_2, c_1, c_2$ から平文 $m$ を導出することができます。この攻撃手法はCommon Modulus Attackと呼ばれています（詳細はこちら）。

今回も、$n$ が同一かつ $e$ が異なる公開鍵 $(n, e_1),(n,e_2)$ でそれぞれ暗号化した暗号文 $c_1, c_2$ があたえられているため、この攻撃が有効になります。

solve.py

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

n = 21141157755370440356159016558867591002795131037765353220781763950242197787546988623583333748613811615876039600044067795582387314625044873018261912055648316947575307397145571269092683237196318163742534102252564452361648000741215145961263035358948910750394941304616916013217678630294578579032413375393774307079767343057241805957456859330160131811246961956716626217712879502367810458962663138839207104998925545962808329297100387478763021607429645752111666523372296094568288414788741918520918522347389517685977356020153749161423831061236785869435119648010372663034476232600939002450611487244980761240697255092515294619063
e1 = 65536
c1 = 3791139181938569737398685036032381737646987513051659017777895787043616313081106838760662536132081707503545049439606032069727376790572333643094529595081085118571506461893089039469054703087386815141490544138726142314337827447061522144729907408053083672097701520947030283539764963562701091579919487153984526052282424975277999492006498441654336183574233720547915500793830555227254993335348447191157770264921144000194606354966874727918714437428556969904356868934618577114911104025392029907939301331113924863412657322707967483351467004854177190395076310650546542866389721479249039989850401261446124771193559166329619972412
e2 = 65538
c2 = 9479987054301003593696498729807102589604512322454236806662495038269939932383233766107579478386705533651017857595249113906203900757985576318399557582785561924440535008414598465159052407108648112038858687677552218404377633749009339690058222162908839308847763582094729669124528370642665466262258176588951705959922822288462616323273663488143476234490690202535922260303842658128571121608034815328952318543895796544411651444423903851422043107669054499710424643274879906277104856140792871842468587164924689276336292808339852752054246714774764674969279059667783378523996744567909634744703888058392004064096159069736198607229

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, x, y = gmpy2.gcdext(e1, e2)
    if x < 0:
        x = -x
        c1_inv = gmpy2.invert(c1, n)
        c1x = pow(c1_inv, x, n)
        c2y = pow(c2, y, n)
    else:
        y = -y
        c2_inv = gmpy2.invert(c2, n)
        c1x = pow(c1, x, n)
        c2y = pow(c2_inv, y, n)
    mroot = (c1x * c2y)%n # mのgcd(e1, e2)乗
    m, ok = gmpy2.iroot(mroot, math.gcd(e1, e2)) # mのgcd(e1, e2)乗根
    return m

m = common_modulus_attack(c1, c2, e1, e2, n)
flag = long_to_bytes(int(m))
print(flag) # b'imctf{y0u_are_an_rsa_exp0rt}'

flag

imctf{y0u_are_an_rsa_exp0rt}

【crypto】 pxkemxn

17 Solves

問題

太郎くんはクリスマスプレゼントにpxkemxnのゲームをもらいました。pxkemxnのゲームで使われている乱数生成方法ではどうやら生成される乱数を予測できるらしいです。乱数を予測して、いろんな裏技を実行してみましょう！

flagはimctf{X[100]}となります。

gen.py

import secrets
import random

# 参考 : https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

class LCG:
    def __init__(self, S):
        self.A = secrets.randbits(256)
        self.B = secrets.randbits(256)

        while True:
            self.M = secrets.randbits(256)
            if is_prime(self.M):
                break
        
        self.x = S % self.M

    def next(self):
        self.x = ((self.A * self.x) + self.B) % self.M
        return self.x

lcg = LCG(secrets.randbits(256))
print("M : " + str(lcg.M))

cnt = 100
for i in range(cnt):
    x = lcg.next()
    if i in [0, 1, 2]:
        print("X[{}] : {}".format(i, x))

print("X[{}] : ?".format(cnt))

output.txt

M : 54354118932293738974277735009690054672438569183669264435593776508452144737651
X[0] : 27562969846242726464849700066934036402432300755063353950289314180737804494366
X[1] : 53881790667921922669270635160364649792695336386197364717009941696103524473701
X[2] : 18353049655762832365359178635985811169156727614439565352194778213695599906765
X[100] : ?

解答

乱数を予測する問題です。乱数生成には線形合同法のアルゴリズムが使用されています。
線形合同法は以下の漸化式で、擬似乱数を生成します。

X_{n+1}=(A\times X_n+B)\bmod M

$A, B, M$ は定数であり、$M>A, M>B, A>0, B\geq0$ を満たします。

線形合同法では $A, B, M$と現在の乱数 $X_n$ がわかっていれば、次の乱数 $X_{n+1}$ を予測できます。今回の場合、$M$が既知で、$A, B$ が未知なので、$A, B$ を求める必要があります。今、$X_0, X_1, X_2$が分かっているので、以下のようにして$A, B$を求めることができます。

まず、連立方程式を立てます。

X_1 = (A\times X_0+B)\bmod M \\
X_2 = (A\times X_1+B)\bmod M

次に、$X_1$と$X_2$の差分をとり $B$ を消去し、式変形をして $A$ を求めます。

X_2 - X_1 = A \times (X_1-X_0)\bmod M

A = (X_2 - X_1) \times (X_1-X_0)^{-1} \bmod M

$B$ は求まった $A$ を用いて、求めることができます。

B = (X_1 - A \times X_0) \bmod M

あとは $X_4, X_5, ..., X_{100}$ と求めていくだけです。
プログラムにするとこんな感じになります。

solve.py

M = 54354118932293738974277735009690054672438569183669264435593776508452144737651
X = [0] * 3
X[0] = 27562969846242726464849700066934036402432300755063353950289314180737804494366
X[1] = 53881790667921922669270635160364649792695336386197364717009941696103524473701
X[2] = 18353049655762832365359178635985811169156727614439565352194778213695599906765

def modinv(a, m):
    return pow(a, m-2, m)

class LCG:
    def __init__(self, x, A, B, M):
        self.x = x
        self.A = A
        self.B = B
        self.M = M

    def next(self):
        self.x = ((self.A * self.x) + self.B) % self.M
        return self.x

Y1 = X[2] - X[1]
Y0 = X[1] - X[0]
inv_Y0 = modinv(Y0, M)
A = (Y1 * inv_Y0) % M
B = (X[1] - A * X[0]) % M

lcg = LCG(X[0], A, B, M)
cnt = 100
for i in range(cnt):
    x = lcg.next()
    if i+1 == 100:
        print("flag = X[{}] : {}".format(i+1, x)) # flag = X[100] : 41406001562898874001864598429475444818799641840147213206874340730032400227277

flag

imctf{41406001562898874001864598429475444818799641840147213206874340730032400227277}

【crypto】 origin

3 Solves

問題

秘密鍵の持ち主しか署名チェックを通過できないはずですが...

app.py

#!/usr/bin/env python3

from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key, Signature, ellipticcurve
from flag import flag
import random
import hashlib
import sys

g = SECP256k1.generator
order = int(SECP256k1.order) 
secret = random.randrange(2, order - 1)
pubkey = Public_key(g, g * secret)
privkey = Private_key(pubkey, secret)

print("""
            _       _       
  ___  _ __(_) __ _(_)_ __  
 / _ \| '__| |/ _` | | '_ \ 
| (_) | |  | | (_| | | | | |
 \___/|_|  |_|\__, |_|_| |_|
              |___/         

Can you hack signature verification system?
public key : ({}, {})
""".format(pubkey.point.x(), pubkey.point.y()))

try:
    R = int(input("R: "))
    S = int(input("S: "))
    G_x = int(input("G_x: "))
    G_y = int(input("G_y: "))
except ValueError as e:
    print("Please input number to R, S, G_x, G_y.")
    sys.exit()

signature = Signature(R, S)

# 参考 : https://github.com/tlsfuzzer/python-ecdsa/blob/ee8fea3e5615b54bc6662d5461f481cb584b8bc7/src/ecdsa/ecdsa.py
_a = 0x0000000000000000000000000000000000000000000000000000000000000000
_b = 0x0000000000000000000000000000000000000000000000000000000000000007
_p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
_Gx = G_x
_Gy = G_y

curve_secp256k1 = ellipticcurve.CurveFp(_p, _a, _b, 1)
generator_secp256k1 = ellipticcurve.PointJacobi(
    curve_secp256k1, _Gx, _Gy, 1, order, generator=True
)

new_g = generator_secp256k1 
new_pubkey = Public_key(new_g, pubkey.point)
msg = "Christmas"
h = hashlib.sha256(msg.encode()).digest()

# 署名が正しいか検証
if new_pubkey.verifies(int.from_bytes(h, byteorder='big'), signature):
    print("verification successed!")
    print(flag)
else:
    print("verification failed.")

解答

楕円曲線DSA（ECDSA）の問題です。ECDSAは署名生成・検証アルゴリズムです。

ECDSAについて

まず、ECDSAについて説明をします。ECDSAによる署名生成では $R$ と $S$ の2つの値を生成します。 署名生成は secp256k1 という楕円曲線上での有限体演算を用いて行われます。 まず、楕円曲線上の1点をベースポイント $G$ として定め、$n$ を法とします。また、$[1, n-1]$の範囲内でランダムに決定した秘密鍵 $d$ と 公開鍵 $Q = d * G$ を生成します。

メッセージ $m$ に対する署名は以下のように生成します。

1. $h = HASH(m)$ を計算する。
2. $[1, n-1]$の範囲から整数 $k$ を任意に選択する。
3. 曲線上の点 $(x_1, y_1)=k*G$ を計算する。
4. $R=x_1 \bmod n$ を計算する。
5. $S=\frac{h+dR}{k} \bmod n$ を計算する。
6. $(R, S)$ が $m$ に対する署名となる。

メッセージ $m$ と 署名 $(R, S)$ の検証は以下のように行われます。

1. $R$ および $S$ がいずれも$[1, n-1]$の範囲にある整数であることを確認する。
2. $h = HASH(m)$を計算する。
3. 曲線上の点 $(x_1, y_1)=\frac{hG+RQ}{S} \bmod n$ を計算する。
4. $R \equiv x_1 (\bmod n)$ であれば、署名は正しい。

3、4の証明はこちらです。

\frac{hG+RQ}{S}\bmod n \\
= \frac{k}{h+dR}(hG+RQ) \bmod n \\
= \frac{k(h+dR)}{h+dR}G \bmod n \\
= k * G \bmod n

$k * G$ は $R$と一致するため、署名は正しいです。

CVE-2020-0601について

この問題はCVE-2020-0601のコンセプトをベースに作成しています。この脆弱性はベースポイント $G$ を自由に変更できることを利用し、公開鍵 $Q$ に対応した秘密鍵を攻撃者が自由に設定できるというものでした。ここでも詳細に説明しますが、こちらの記事でわかりやすい説明がなされています。

この問題でも実際に署名$R, S$に加え、新たなベースポイント $G'$ を使用することができます。

$ nc 18.181.165.199 54321      

            _       _       
  ___  _ __(_) __ _(_)_ __  
 / _ \| '__| |/ _` | | '_ \ 
| (_) | |  | | (_| | | | | |
 \___/|_|  |_|\__, |_|_| |_|
              |___/         

Can you hack signature verification system?
public key : (7772005205631024160237412306138791373167168241033904214721983173059867257971, 32805201142879411567672123163601502609883546526800899196682548064758826368493)

R: 1
S: 1
G_x: 1
G_y: 1
verification failed.

ここで、新たなベースポイントを $G'=\frac{Q}{d} \bmod n$ とすると有効な署名を作成できます。$d'$はこちらで適当に作成した秘密鍵です。

メッセージ $m$ に対する署名を生成します。

1. $h = HASH(m)$ を計算する。
2. $[1, n-1]$の範囲から整数 $k'$ を任意に選択する。
3. 曲線上の点 $(x_1', y_1')=k'*G’$ を計算する。
4. $R'=x_1' \bmod n$ を計算する。
5. $S'=\frac{h+d'R'}{k'} \bmod n$ を計算する。
6. $(R', S')$ が $m$ に対する署名となる。

メッセージ $m$ と 署名 $(R', S')$ の検証は以下のように行われます。

1. $R'$ および $S'$ がいずれも$[1, n-1]$の範囲にある整数であることを確認する。
2. $h = HASH(m)$を計算する。
3. 曲線上の点 $(x_1', y_1')=\frac{hG'+R'Q}{S}\bmod n$ を計算する。
4. $R' \equiv x_1' (\bmod n)$ であるので、署名は正しいとされる。

3、4の証明はこちらです。

\frac{hG'+R'Q}{S}\bmod n \\
= \frac{k'}{h+d'R'}(hG'+R'Q) \bmod n \\
= \frac{k'}{h+d'R'}(h\frac{Q}{d'}+R'Q) \bmod n \\
= \frac{k'(h+d'R')}{d'(h+d'R')}Q \bmod n \\
= \frac{k'}{d'}Q \bmod n = k'*G' \bmod n 

$k' * G'$ は $R'$と一致するため、署名は正しいことになります。

プログラムにするとこんな感じになります。

solve.py

from ecdsa import SECP256k1
from ecdsa.ecdsa import Public_key, Private_key, Signature, numbertheory, ellipticcurve
import random
import hashlib

# 参考 : https://github.com/tlsfuzzer/python-ecdsa/blob/ee8fea3e5615b54bc6662d5461f481cb584b8bc7/src/ecdsa/ecdsa.py
# Certicom secp256-k1
_a = 0x0000000000000000000000000000000000000000000000000000000000000000
_b = 0x0000000000000000000000000000000000000000000000000000000000000007
_p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
_Gx = <与えられた公開鍵のx座標>
_Gy = <与えられた公開鍵のy座標>
_r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

curve_secp256k1 = ellipticcurve.CurveFp(_p, _a, _b, 1)
point_secp256k1 = ellipticcurve.PointJacobi(
    curve_secp256k1, _Gx, _Gy, 1, _r, generator=False
)

point = point_secp256k1 # 公開鍵
n = point.order()

secret = random.randrange(2, n - 1) # 攻撃者が作成した秘密鍵
G = numbertheory.inverse_mod(secret, n) * point # 新たに設定するベースポイント
pubkey = Public_key(G, G * secret)
privkey = Private_key(pubkey, secret)
msg = "Christmas"
h = hashlib.sha256(msg.encode()).digest()
k = random.randrange(2, n - 1) # 攻撃者が作成する乱数
signature = privkey.sign(int.from_bytes(h, byteorder='big'), k)

print("R:",signature.r)
print("S:",signature.s)
print("G_x:",G.x())
print("G_y:",G.y())

与えられた公開鍵を入力としてsolve.pyに与え、生成される$R, S, G_x', G_y'$を入力すると署名チェックを通過できます。

melon@melonnoMacBook-Pro ctf-problems % nc 18.181.165.199 54321     

            _       _       
  ___  _ __(_) __ _(_)_ __  
 / _ \| '__| |/ _` | | '_ \ 
| (_) | |  | | (_| | | | | |
 \___/|_|  |_|\__, |_|_| |_|
              |___/         

Can you hack signature verification system?
public key : (22380726021290159112034475839476399585381009148551707449553522910990013973364, 10341398130041140040536083752493084343121743623992436953218575582797179738644)

R: 46584088300310749739983745805557578525210031444982338010251645421282865599068
S: 48962895937845766772862474741288619585486253857625555499816445153006279181318
G_x: 85856583058147621080956237313523191433016438273769271146099304819542049554822
G_y: 23737237673163369225450233635385425144978953959363369173435334549644759750596
verification successed!
imctf{funny_516n_v3r1f1c4710n_5y573m}

flag

imctf{funny_516n_v3r1f1c4710n_5y573m}

最後に

IMCTF 2021はいかがでしたでしょうか？ 楽しんで頂けたなら幸いです！
IMCTF2021を遊んでいただきありがとうございました！