m1z0r3CTF2022 作った問題&writeup

お久しぶりです。

社会人にはなりましたが、m1z0r3CTFには参加できたらなと思い問題を作ってみました(解く方には参加できず)。

• • borderline
• • prime connect
  • borderline 解法
• • prime connect 解法

※目次が変な感じになってしまい、どう直せばいいか分からず

borderline

めんどくさい計算盛りだくさん
添付ファイル：borderline.zip

#chall1.py
from Crypto.Util.number import long_to_bytes
import random

secret = open("secret.png","rb").read()

a = random.randrange(256)
b = random.randrange(256)
r = random.randrange(256)
x = random.randrange(256)

enc = 0
for s in secret:
    enc <<= 8
    x = (a*x+b)%r
    enc += s^x

f = open("encrypted_data.dat","wb")
f.write(long_to_bytes(enc))

prime connect

prime + prime = prime
添付ファイル：prime_connect.py

from Crypto.Util.number import *

def encrypt(st_len,go_len,prime,message):
    s = 0
    l = 1
    c = []
    while st_len <= go_len:
        while True:
            q = getPrime(st_len)
            qbin = bin(q)[2:]
            while len(qbin) < st_len: qbin = "0" + qbin
            next_prime = int(bin(prime)[2:] + qbin,2)
            if isPrime(next_prime):
                N = prime * q
                m = bytes_to_long(message[s:s+l])
                e = 101
                if prime%e != 1 and q%e != 1:
                    c.append(pow(m,e,N))
                    prime = next_prime
                    break
        st_len *= 2
        s += l
        l *= 2
    assert len(message) == s
    return c,N

flag = open("flag.txt","rb").read()
gen_p = getPrime(16)
c,N = encrypt(gen_p.bit_length(),256,gen_p,flag)
print(c)
# [923347949, 7382279973222128877, 122962146306170765837908848551223454567, 3549519152212014068083700234235160186300219130505299139696292306205464039799, 1527384673643022720120101064151977796913895264858932377772580237410767118686969106391529500139242897405662607203540127567551879700554668904837212450683883]
print(N)
# 6159034900797898425838526763919325877394844976323736393192254250464963575156530328240421294138007406960476709427205843365628191563244980986067184889098833

borderline 解法

encrypt.pyについて、PNG画像を1バイトずつ暗号化しています。XORを使って暗号化しており、XORするもう一つの値は線形合同法にて決定されます。

ご存知の方も多いとは思いますが、線形合同法には特定の場合において脆弱性が生まれます。 こちらのサイトをよく見るのですが、線形合同法は連続した6個ほどの出力値が分かると、パラメータを算出でき出力値の予想が可能となります。

線形合同法のパラメータを乱数列から求めてみる。 – みつのCTF精進記録

PNGファイルは先頭8バイトが固定であるので、そこから連続した8個の出力値を暗号文とその固定バイトでXORして得られます。 そこから上記のサイトの方法を使って、パラメータを復元します。
その後、他の出力値を計算することで、secret.pngが復元できます。

ということで出題者(私)のgithubに次の問題があります。

GitHub – ksbowler/m1z0r3CTF_2022

import random
from Crypto.Util.number import *

secret = open("secret.png","rb").read()
flag = open("flag.txt","rb").read().strip()
assert len(flag)%3 == 0
ex = random.randrange(len(secret)-1)
e = bytes_to_long(secret[ex:ex+2])
p = getPrime(256)
q = getPrime(256)
n = p*q
c = []
for i in range(0,len(flag),3):
    m = bytes_to_long(flag[i:i+3])
    c.append(pow(m,e,n))
print(c)
# [6298113965475853786056847106208713300642945466885637995557170104494725950616074542425506023987217363886529665397919957618261581053133941027535155746435321, 135028125411958273916880824261545147614327725922209748340303390558194571689687977032589044265126382565916547879777234892642296715526896605761082569309957, 1321747274929612152457518915168588918356514442679554382787182364164828302372180029740168631933681540647333144180952171045221159999310072594994307374026397, 2918560933591924342981380338403848413183651470512194619662681532592047008257668515013412096463534685052633599782673614961906361066771670231196673146753898, 5775447489821919812656223325306418654099675333689382733144673190079859607549709791366025032709099098614570746711061453405145141567455154943434221193937600, 1274850466517264624838781305598541289691584629758963818109637778738466734330749252973718909288129468236472225834841856001947077472220670167226069634313329, 1303782230905842229285244210919421873678385109856332605169575017604438212677510463647334165086069519414714376999894517045356733235945921910952902514007317]

3文字ごと暗号化しており、eはsecret.pngのどこかの連続した2バイト、Nは256bitの素数2つの積となっています。

e, Nは非公開なので、特定していきます。 eはbrute forceしていきつつ、Nを探していきます。 3文字ごと暗号化しており、先頭6文字は”m1z0r3″であるので、

"m1z"^e - 対応した暗号文
"0r3"^e - 対応した暗号文

がNの倍数となります。 この2つのGCDを取ります。GCDの結果、500bit以上になる場合がNの候補となり、今回は1通りしか出ません。

あとはその求めたe, Nを使って、暗号文と同じになる平文をbrute forceで見つけます。

m1z0r3{Time_i5_m0ney}

思いついた経緯

コナンファンなのでtime is moneyは入れたいなと思い、brute force系の問題にしました。 m1z0r3CTF恒例の時間かかる＆段階をいくつか踏む問題を作りました。 どこかでPNGファイルの固定8バイトと、線形合同法を組み合わせる問題を見たのでパクりました。 あとは、e, Nすら非公開のRSAがあっても面白いのでは？となり、brute forceできるギリギリのラインで作りました。

prime connect 解法

encrypt関数は以下のような挙動となっています。

・16bitの素数pとflag(とその他諸々)を引数とする
・暗号化?回目
1. pと同じ大きさの素数qを生成する
2. binaryでpとqを繋ぎ合わせた値が素数であれば3に、そうでないなら1に進む
3. e = 101, N = pqとしてRSAで暗号化
4. 暗号化するmはflagの先頭2^(?−1)文字。一度暗号化した文字は暗号化しない。
5. pが256bitとなれば暗号化終わり。
6. p = pとqを繋ぎ合わせた値
7. 暗号化?回目終了、1へ。
・最後のNと暗号文のリストを公開

ここで、暗号化の3回目まではなんとかなります。 というのも、flagの先頭7文字までは分かっているので、そこから引数で渡された16bitの素数や、1で生成した素数が求められます。 (m^e-(対応した暗号文) )がNの倍数=p,qの倍数となるので素因数分解すれば分かります。

3回目までのp,qが求まると、4回目での暗号化のpが求まります。また、最後の暗号化におけるpの半分が分かります。 あとは、coppersmith’s attack を使って解いていきます。

SageMathを使ってCoppersmith’s Attackをやってみる – ももいろテクノロジー

17bitほどbrute forceしないといけないので、時間かけてください笑

m1z0r3{My_1st_coppersmith_quiz}

思いついた経緯

ふと、2進数で素数を繋いでみたらそれも素数になるのかな、なるとしたらどれくらいあるのかな、と思いちょっと動かしてみたらまあまあありそう。 そして、それでNを作ったらなんか脆弱性あるのかなーと考えていたら、pの上位ビット知られちゃいけないのを思い出し今の形を思いつきました。 素数を大きくしていくのでそれに合わせて、暗号化する文字数を増やしていこうと思い、1+2+4=7で”m1z0r3{“のヘッダーが上手く使えるのでは？と。 久しぶりの割には良い問題ができたつもりです笑