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(とその他諸々)を引数とする
・暗号化