1. はじめに
2022/6/4(土)14:00JST ～ 6/5(日)14:00:00JST に開催された「SECCON Beginners CTF CTF 2022」にチーム「N30Z30N」でソロ参加し、1169 点（得点を得た 891 チーム中 60 位）を獲得しました。Crypto のボス問でリソースを使い果たし、最後はフラフラになりながらのゴールインでした（問題は総じて楽しかったですので、積み残しは後日改めて。。。）
Crypto問は 5 問ありましたが、記事映えするような「綺麗な解き方」をしたものは一つもなかったので、ブログに参戦記だけ書こうかと思っていたのですが、問題を解くときの思考過程は人によって異なるので、（特にCTFを始めたばかりの方などにとっては）些細なことであっても案外新鮮な気づきになるのではないかと思い、Writeup の形でも残すことにしました。
2. Writeup
2-1. CoughingFox (難易度:beginner, 55 points, 443 solves)
☆設問
きつねさんが食べ物を探しているみたいです。
problem.py
from random import shuffle
flag = b"ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"
cipher = []
for i in range(len(flag)):
f = flag[i]
c = (f + i)**2 + i
cipher.append(c)
shuffle(cipher)
print("cipher =", cipher)
output.txt
cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]
☆方針・解法
暗号化は、flag の各文字の Ascii コード $f$ に対し、$c:=(f+i)^2+i$ を計算することで行います。但し、最後にシャッフルしているので cipher の中の各値 $c$ が平文の何番目の文字に対応しているか（見ただけでは）わかりません。
しかし、$c-i$ が平方数であった場合、それは「$i$ 番目の文字であり Ascii コードは $\sqrt{c-i}$ であった」可能性が極めて濃厚（実際には特定可能）です。
そこで、各 $c$ と $i$ に対して $c-i$ が平方数であるかどうかを計算し、平方数であればフラグの $i$ 番目の文字として復号します。
競技中は Python のコンソールに直接入力してカタカタやっていましたが、ソルバの形にまとめると以下のようになります。
☆ソルバ
solve.py
import gmpy2
cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]
flag = ""
for i in range(0, len(cipher)):
for c in cipher:
x = gmpy2.iroot(c-i, 2)
if x[1]:
flag += chr(x[0]-i)
break
print(flag)
☆フラグ
ctf4b{Hey,Fox?YouCanNotTearThatHouseDown,CanYou?}
教養がないので、狐がどう絡んでいるのか分かりませんでした（いつか元ネタがわかればと思っています）。サーセン。
2-2. PrimeParty (難易度:easy, 127 points, 58 solves)
☆設問
Primeパーティへようこそ！！！
（サーバ接続先が提示されます）
server.py
from Crypto.Util.number import *
from secret import flag
from functools import reduce
from operator import mul
bits = 256
flag = bytes_to_long(flag.encode())
assert flag.bit_length() == 455
GUESTS = []
def invite(p):
global GUESTS
if isPrime(p):
print("[*] We have been waiting for you!!! This way, please.")
GUESTS.append(p)
else:
print("[*] I'm sorry... If you are not a Prime Number, you will not be allowed to join the party.")
print("-*-*-*-*-*-*-*-*-*-*-*-*-")
invite(getPrime(bits))
invite(getPrime(bits))
invite(getPrime(bits))
invite(getPrime(bits))
for i in range(3):
print("[*] Do you want to invite more guests?")
num = int(input(" > "))
invite(num)
n = reduce(mul, GUESTS)
e = 65537
cipher = pow(flag, e, n)
print("n =", n)
print("e =", e)
print("cipher =", cipher)
☆方針・解法
RSA 暗号の問題です。modulus を構成するため、サーバ側が 256bit の素数を 4 つ準備し、プレイヤー側は任意の 3 つの素数を指定でき、これら 7 つの素数の積が $n$ となります。一見鬱陶しいのですが、平文（フラグ）の長さは 455bit なので、それ以上の長さのもの（以下、$p$ とする）を 1 つ指定し、残り 2 つはテキトーに投げておけば十分です。
$n$ の他の約数は無視して $p$ だけに着目し、全てを $\mod{p}$ で考えれば容易に復号できます。
☆ソルバ（解答の記録）
512bit の素数を取得
>>> from Crypto.Util.number import getPrime
>>> getPrime(512)
7506213847014317744187832802681469862950253815512058315859572619051355964437912370637437561566334625497526318403203410062169403470204121297526374857451919
サーバ接続時のコンソール
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] Do you want to invite more guests?
> 3
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] Do you want to invite more guests?
> 5
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
[*] Do you want to invite more guests?
> 7506213847014317744187832802681469862950253815512058315859572619051355964437912370637437561566334625497526318403203410062169403470204121297526374857451919
[*] We have been waiting for you!!! This way, please.
-*-*-*-*-*-*-*-*-*-*-*-*-
n = 5800015454981838525357767585129642551317573218528105316640107169731666825794582136854374317812774473814611554159513486139625012059877333952315038490743465748859651078827917856006270358657182198181400135087265029991007892874660665740162350045921721698387027848404618707392233731787864667408160796329969537730050670360391813655833048019468001908267962761083204206520413554421570563807841539916014563047068343678993160672706643675536962535305916558789901842221482415
e = 65537
cipher = 4860786810482752103637825622416355492123347317435748320242640761956376643651096926836104804500328579228715196133216945409879342141406638055963242208250144397184148608059351897250543813237968035303413915056289963639399259278542513387715859428277960626342263888833011251674479989002420000768656145066850983814071675301086706625748099724935291494580797907802461134352497118102575361565557441637169263169801175742373640906872270097560709286160491823581792604932816152
solve.py
from Crypto.Util.number import *
p = 7506213847014317744187832802681469862950253815512058315859572619051355964437912370637437561566334625497526318403203410062169403470204121297526374857451919
e = 65537
d = inverse(e, p-1)
ct = 4860786810482752103637825622416355492123347317435748320242640761956376643651096926836104804500328579228715196133216945409879342141406638055963242208250144397184148608059351897250543813237968035303413915056289963639399259278542513387715859428277960626342263888833011251674479989002420000768656145066850983814071675301086706625748099724935291494580797907802461134352497118102575361565557441637169263169801175742373640906872270097560709286160491823581792604932816152
print(long_to_bytes(pow(ct,d,p)))
☆フラグ
ctf4b{HopefullyWeCanFindSomeCommonGroundWithEachOther!!!}
2-3. Command (難易度:easy, 106 points, 88 solves)
☆設問
安全なコマンドだけが使えます
（サーバ接続先が提示されます）
chall.py
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import isPrime
from secret import FLAG, key
import os
def main():
while True:
print('----- Menu -----')
print('1. Encrypt command')
print('2. Execute encrypted command')
print('3. Exit')
select = int(input('> '))
if select == 1:
encrypt()
elif select == 2:
execute()
elif select == 3:
break
else:
pass
print()
def encrypt():
print('Available commands: fizzbuzz, primes, getflag')
cmd = input('> ').encode()
if cmd not in [b'fizzbuzz', b'primes', b'getflag']:
print('unknown command')
return
if b'getflag' in cmd:
print('this command is for admin')
return
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
enc = cipher.encrypt(pad(cmd, 16))
print(f'Encrypted command: {(iv+enc).hex()}')
def execute():
inp = bytes.fromhex(input('Encrypted command> '))
iv, enc = inp[:16], inp[16:]
cipher = AES.new(key, AES.MODE_CBC, iv)
try:
cmd = unpad(cipher.decrypt(enc), 16)
if cmd == b'fizzbuzz':
fizzbuzz()
elif cmd == b'primes':
primes()
elif cmd == b'getflag':
getflag()
except ValueError:
pass
def fizzbuzz():
for i in range(1, 101):
if i % 15 == 0:
print('FizzBuzz')
elif i % 3 == 0:
print('Fizz')
elif i % 5 == 0:
print('Buzz')
else:
print(i)
def primes():
for i in range(1, 101):
if isPrime(i):
print(i)
def getflag():
print(FLAG)
if __name__ == '__main__':
main()
☆方針・解法
概要
この問題では、サーバは３つの実行可能コマンド（fizzbuzz、primes、getflag）を持ち、
（１）AES-CBC によるコマンドの暗号化機能（ただしプレイヤーは getflag の暗号化ができない）
（２）プレイヤーが送信した暗号化済コマンドを（同じ鍵で復号して）実行する機能
という機能をを備えています。また、（１）の暗号化結果はIV（Initial Vector）とともに提示され、（２）のコマンド実行時には（１）と同一の鍵で復号が行われますが、IVはプレイヤー側から送ることができます。
以上の条件下で、プレイヤーはどうにかしてを getflag コマンドを暗号化したうえで実行させる必要があります。
方針
AES-CBC に対する攻撃ですが、やりたいこと・やれることによって、攻撃の方法が変わってきます。対 CBC モードで典型的なのは Bit Flipping Attack と Padding Oracle Attack ですが、この問題には前者を適用できます。
CBC モードでは、前ブロックの暗号文と XOR（排他的論理和）した平文が暗号化処理されますは、最初の平文ブロックは前ブロックの暗号文がないので代わりに IV と XOR したものが暗号化処理の input となります。※詳しく知りたい方は、暗号化利用モード(CBC)等をご確認ください。
ここで逆の視点から見ると、「最初の暗号化ブロックを復号処理後 IV と XOR したもの」が「最初の平文ブロック」になるということになります。つまり IV をうまく差し替えておくことで、最初のブロック（平文）を改ざんすることが可能となるわけです。
具体的な手立て
fuzzbuzz でも primes でもどちらでも良いので、サーバの（１）の機能を通じ暗号化要求を出します。IV（16バイト）の後ろに暗号文が続いたデータが返されるので、以下のように IV の部分を差し替えます。
[新IV] = [入手したIV] XOR ["primes"の平文ブロック] XOR ["getflag"の平文ブロック]
※1 ブロック 16byte となるよう PAD を忘れずに。。。
最初のブロックを復号処理した結果は、[入手したIV] XOR ["primes"の平文ブロック] と一致値していますが、これを [新IV] とXOR すると、["getflag"の平文ブロック] が残り
ます（XOR 処理の中に偶数回登場したものは打ち消されます。例；A XOR B XOR A = B）。つまり、これをサーバの（２）の機能を通じ復号・実行させればフラグをゲットすることが可能です。
今回、新 IV の算出は python（pwntools の xor）を使って実施しています。
☆ソルバ（解答の記録）
サーバ接続時のコンソール（前半）
----- Menu -----
1. Encrypt command
2. Execute encrypted command
3. Exit
> 1
Available commands: fizzbuzz, primes, getflag
> primes
Encrypted command: be03169270e8bfefd1763c90ddba3484d3d65851423ac6e0529635c3136f5b1f
サーバに送るivとptの計算
>>> from Crypto.Util.Padding import pad
>>> from pwn import xor
>>> ivct = "be03169270e8bfefd1763c90ddba3484d3d65851423ac6e0529635c3136f5b1f"
>>> iv = bytes.fromhex(ivct[:32])
>>> pt = pad(b"primes",16)
>>> pt2 = pad(b"getflag",16)
>>> iv2 = xor(iv,xor(pt,pt2))
>>> input = iv2.hex() + ivct[32:]
>>> print(input)
a9140b9979fad2ecd2753f93deb93787d3d65851423ac6e0529635c3136f5b1f
サーバ接続時のコンソール（つづき）
----- Menu -----
1. Encrypt command
2. Execute encrypted command
3. Exit
> 2
Encrypted command> a9140b9979fad2ecd2753f93deb93787d3d65851423ac6e0529635c3136f5b1f
ctf4b{b1tfl1pfl4ppers}
----- Menu -----
1. Encrypt command
2. Execute encrypted command
3. Exit
> 3
☆フラグ
ctf4b{b1tfl1pfl4ppers}
2-4. Unpredictable Pad (難易度:medium, 159 points, 35 solves)
☆設問
CSPRNGじゃなければ予想できるって聞きました。
（サーバ接続先が提示されます）
chall.py
import random
import os
FLAG = os.getenv('FLAG', 'notflag{this_is_sample_flag}')
def main():
r = random.Random()
for i in range(3):
try:
inp = int(input('Input to oracle: '))
if inp > 2**64:
print('input is too big')
return
oracle = r.getrandbits(inp.bit_length()) ^ inp
print(f'The oracle is: {oracle}')
except ValueError:
continue
intflag = int(FLAG.encode().hex(), 16)
encrypted_flag = intflag ^ r.getrandbits(intflag.bit_length())
print(f'Encrypted flag: {encrypted_flag}')
if __name__ == '__main__':
main()
☆方針・解法
スタート時点での考え
サーバからは、入力したデータを乱数で XOR 暗号化した出力を 3 回得られ、その後 XOR で暗号化されたフラグを得られます。プレーヤーはこれだけの情報からフラグを復号しなければなりません。
手掛かりとして、Python の random モジュールで使用されている乱数生成器を調べると、（公式ドキュメント等から）「メルセンヌ・ツイスター法」が使用されていることが分かります。
一見すると、サーバから得られる出力は 64bit 以下のもの 3 つだけで到底ここから復元は出来そうもないので（実はこれは見立て違いだったのですが）、seed 値に現在日時が使われているものと想定して $1/10000000$ 秒くらいのレベルで Brute Force するなどいろいろ試してみたもののラチがあかず、途方に暮れていました。
方針転換（軌道修正）
しかし、暫くたってから落ち着いてスクリプトを眺めてみると、評価しているのは大小関係であってビット数ではないことに気付き、負の数を送り込めば十分長い出力を得られることが分かりました。
メルセンヌ・ツイスタは、32bit の連続した 624 個の出力を得られれば内部状態を復元でき、その先の出力を推測できることが知られているため、まずは必要な出力を収集する手段を考えました。
具体的な方法
サーバからは、3 回に分けて (32bit × 624 個) 分の出力のデータ（1回あたり32bit × 208個 = 6656bit）を入手することとしました。
6656bit の入力としてはシンプルに $(2^{6656}-1)=$ を渡すこととし、入手したものを再度 XOR して出力を得ることとしました。
あと、長い乱数の中に 32bit の乱数がどのような形で連結されるのか分からなかったので、手元の Python でとりあえずテストをしてみると、下位から順に埋まっていくようだったので、その想定で進めることとしました。
メルセンヌ・ツイスタの復元の部分は、ももいろテクノロジーさんのMersenne Twisterの出力を推測してみるを全面的に参考にさせていただきました。
☆ソルバ
サーバ接続時のコンソール
Input to oracle: -452533921925114549416501081502688749909130594297896758339130731392079681293955674231909653926849047043890944192030098030983970722224651186732833952092540397935341592005519907608726024126580740733491014939497838331894167306213172988968580244094247022727149701121981368975796106955586784967938491474285993911817901672430926468744258915347193617627614364235259987618304543282709929437741414591399642995381869326149637988346997708776793308767643775636807276716724735715124419869659937659924498086793282465824758783561509605306795476023303645037099991197287500811570779215393060394649632707260385884696471729659153185724345540100814275555697752928513887904502354927434117961291154597264497854392687532891486956356835169731219044055776809727257112252407621593176919841709260038390313164134349479099144691531223564615225923380974830315039019576599821124598162718039647378516855643483417012744746639322427379251152765267485241346052049139614829003983963023709551868926380893609347289448293716499081220634697615174812638003148423278946351050534171976205410394889049885188914158292385728119471695577517310549406183147714173317690596958507371530899753679612060321705279017744031675230944407926866728428135398952309843244241577728716681990731871689364986506617544277046766638061208728146171993440359904021093086647619690554332100546654965909568070626542772319853696922981593395191350295076650614971698020972990849017418431836304435472927187702278399001760278669810976721884241518821079439591530333584452284517493789282530046151997590167087764930295887914308503350136663616604790667768084002442986725969827357944041618007015326686930197292553262351527402447681407665664594899664775193644710890458780784399961787599510849628335432827998712093558974088146231885468708329818271456132292866958122165983019804353557169145076533187603812358038836017187247306286824810824586303447790811827489765075690527458827250360935412177872550824299473911088505182254427348189569097905188554378523698027624051093923572264421055776423935
The oracle is: -339653493153104472182169686533258416336086067633408766817549978606897487068991364321308993400753401717588313400477683005887560743348576364011690687620193591678921503645815442589607289629411835032995233842860455649248184003540768186249900877947117716425004314126984488154290280732349799248419414515419712079659363638711583084875606438226569309535184957586117550991999461147552681374566051852875886391106257780335568599120288842176359085312732482451623783500446560358509372235096349562925093849986653098547837162186510167924594723010692965060180377665399665896994778283448835318777214808034928066344927549475253394319038633009985313418572601786745878889566874321858388833026060863612982057735931659765261432964228264643972512477255327294324146930141439577499957970699574639550720475012636664503475517054941642430639634166974726593706356094976198232147203180215505533555522314802424813933204153214982243273710097468319475874923995279183277948749232821885475113452598314365759240344665498640505306596160485772490533892009377481917948958509922646192047110809779562532602797194168142394054027395124109800207841642981073357453593670742169857729926055170066655070844835123632372594814768462296969953955130554325735804428051714791244992805528587533562976585401911774369128556997765280520431843060025798611245234560708624892339280173983556990860660996989640883302332521833136433550855869998494164357493991629575579147486392865647295612668350475199324019433839106934077319680553683587607068647435234324391735406824387700703911303851404156836757398517462445591198685666525533417517354858416600583106338535480292962226152614462230413628722598004683417957196675671309895312385193729471467005392284844583210468626024131686790463171343451912763976350640922235432231299051800918854235113664710982982869485249627881797988397396982375688882966940598586988741496505397396153940496522400400298475621484570545379964806733660677310708260750203766417473062225053059128621784197534902402610125948213064819921394611259253749650439
Input to oracle: -452533921925114549416501081502688749909130594297896758339130731392079681293955674231909653926849047043890944192030098030983970722224651186732833952092540397935341592005519907608726024126580740733491014939497838331894167306213172988968580244094247022727149701121981368975796106955586784967938491474285993911817901672430926468744258915347193617627614364235259987618304543282709929437741414591399642995381869326149637988346997708776793308767643775636807276716724735715124419869659937659924498086793282465824758783561509605306795476023303645037099991197287500811570779215393060394649632707260385884696471729659153185724345540100814275555697752928513887904502354927434117961291154597264497854392687532891486956356835169731219044055776809727257112252407621593176919841709260038390313164134349479099144691531223564615225923380974830315039019576599821124598162718039647378516855643483417012744746639322427379251152765267485241346052049139614829003983963023709551868926380893609347289448293716499081220634697615174812638003148423278946351050534171976205410394889049885188914158292385728119471695577517310549406183147714173317690596958507371530899753679612060321705279017744031675230944407926866728428135398952309843244241577728716681990731871689364986506617544277046766638061208728146171993440359904021093086647619690554332100546654965909568070626542772319853696922981593395191350295076650614971698020972990849017418431836304435472927187702278399001760278669810976721884241518821079439591530333584452284517493789282530046151997590167087764930295887914308503350136663616604790667768084002442986725969827357944041618007015326686930197292553262351527402447681407665664594899664775193644710890458780784399961787599510849628335432827998712093558974088146231885468708329818271456132292866958122165983019804353557169145076533187603812358038836017187247306286824810824586303447790811827489765075690527458827250360935412177872550824299473911088505182254427348189569097905188554378523698027624051093923572264421055776423935
The oracle is: -145354862911792346160076469754924605058748901321956976414025110494300870498150770834875756168440565799849307756933888397825564956453795350779447817508625968335316914069847297428588156293304835862617870465227139051611653161185589250840010145049585137257002182391654808926460534424404733015698199950313696661572328048147618886076928229770997092606021789833713940828081159906227716246529406039902683914882744266611626945838341246018070593646813814945644224994058071495569110529912644158415958666065011597102998227924850330601052059229341521855190678989265093287380136901003751082096635933573199055545834725181798513499867732520078233477921950003885871703138616619089864756698549546354671131669662854787394216222658261544968769811697615708247161463777717243338706810074388083517698291930849354335117518860288317577099427824855767802149787428072539310853731446117058936215576391781694713337181485489220077246048261915206802164910500763350142841184297842983612760915646052604710144951224749683643484493963002716025854050970027427197418542571547804885066055323422009101510103386959708195977976787693158936819451666719111181799553158367946979718707422087843696345983361719763608563478106571894862306045748180534255756474927542837997730347739537210173527270053290572534333165193209031681240729727884256875789331731581202621854118082580116326304900600645271499145660992551193630227734973098466706856335791307321961955196558739960815343654846356101867101051343766289945659240640291403951714002345426629725063386571502480484624187113332202767232986776404590261486368597579920499333185179484495390343314228954144206112475674035960756539961862381399935271472965186271865847373984865200909994467629933039140864374321175257338781641646918263515938154331254638998295489683596165737394198178806844283905767598398610058905647477809426897033782574840905652206475469020699986437289125701633865494041700555165826799295750925232956690597927936838278983243276401078746018034833550519768621576808585258844398842277693547666723961
Input to oracle: -452533921925114549416501081502688749909130594297896758339130731392079681293955674231909653926849047043890944192030098030983970722224651186732833952092540397935341592005519907608726024126580740733491014939497838331894167306213172988968580244094247022727149701121981368975796106955586784967938491474285993911817901672430926468744258915347193617627614364235259987618304543282709929437741414591399642995381869326149637988346997708776793308767643775636807276716724735715124419869659937659924498086793282465824758783561509605306795476023303645037099991197287500811570779215393060394649632707260385884696471729659153185724345540100814275555697752928513887904502354927434117961291154597264497854392687532891486956356835169731219044055776809727257112252407621593176919841709260038390313164134349479099144691531223564615225923380974830315039019576599821124598162718039647378516855643483417012744746639322427379251152765267485241346052049139614829003983963023709551868926380893609347289448293716499081220634697615174812638003148423278946351050534171976205410394889049885188914158292385728119471695577517310549406183147714173317690596958507371530899753679612060321705279017744031675230944407926866728428135398952309843244241577728716681990731871689364986506617544277046766638061208728146171993440359904021093086647619690554332100546654965909568070626542772319853696922981593395191350295076650614971698020972990849017418431836304435472927187702278399001760278669810976721884241518821079439591530333584452284517493789282530046151997590167087764930295887914308503350136663616604790667768084002442986725969827357944041618007015326686930197292553262351527402447681407665664594899664775193644710890458780784399961787599510849628335432827998712093558974088146231885468708329818271456132292866958122165983019804353557169145076533187603812358038836017187247306286824810824586303447790811827489765075690527458827250360935412177872550824299473911088505182254427348189569097905188554378523698027624051093923572264421055776423935
The oracle is: -242332670284802154496224815988398583606797713611273114863857184971947040245427417716756634045918516267595017464540084175957801334005449677067987743057200934824272399673306416608057389471142469748193903281046820468025802996798794253517003482614363006361921612369018203945343351520071278635888439596260104127293859397308298163928355643135784995661435928851842570878942623590668937710125660422936217086269562600175804271340414403162173759699444252462709954073265098356551999888771541723673086092610686728501291508053798052507557070602738704989356072484199219570984254960777989032950905887916283530111240986548852410340470478562093131905344886930952779570312804406256524992756342389636750809609966583603777582354068751760891997987641464358143201550847220275079366515282883261380377943593994399036069491218576328431869711416873961907225510604577038142610355053697143896537066387988759238699795640296743338599088053476821304279355508627571706039171230601944891313103283827102457381173474857306618433161990203081748233668179202126894573096860294131676643810210277307153204948750394568193616398602830015199996103621141297960136483406091860441926752183473141835190626932507488409970133863487338144053778106395919734923148760259786620802203271311439770408286499551215727974584279018084369568757035278969680946494384275479100484183267111413851611832576242432915639138960822761319591044381122692617232312832689311456955674180067971856441076980015776977278229730868855209003735601489713481164172171808538855543118185571178895733674541202848848295844287038135198725056577513008768953645025144671157596554907036857505927395710352512281263853930148827871275287679645455055545340112906232737764174950359299767789228794180421550470213238584542113654424940276650110829118212096847706865661504421065454812466124811447243835662207617661479843008129327232764827408745419546617386977487206955650540660399905856777179956893319000329950521514235844136767325456721461486045372681003443984469718242364363178757680529408227688324358
Encrypted flag: 166734554398008115898809543086752630636666431187591419756940556941077057
solve.py
from Crypto.Util.number import *
import random
r = random.Random()
x = -452533921925114549416501081502688749909130594297896758339130731392079681293955674231909653926849047043890944192030098030983970722224651186732833952092540397935341592005519907608726024126580740733491014939497838331894167306213172988968580244094247022727149701121981368975796106955586784967938491474285993911817901672430926468744258915347193617627614364235259987618304543282709929437741414591399642995381869326149637988346997708776793308767643775636807276716724735715124419869659937659924498086793282465824758783561509605306795476023303645037099991197287500811570779215393060394649632707260385884696471729659153185724345540100814275555697752928513887904502354927434117961291154597264497854392687532891486956356835169731219044055776809727257112252407621593176919841709260038390313164134349479099144691531223564615225923380974830315039019576599821124598162718039647378516855643483417012744746639322427379251152765267485241346052049139614829003983963023709551868926380893609347289448293716499081220634697615174812638003148423278946351050534171976205410394889049885188914158292385728119471695577517310549406183147714173317690596958507371530899753679612060321705279017744031675230944407926866728428135398952309843244241577728716681990731871689364986506617544277046766638061208728146171993440359904021093086647619690554332100546654965909568070626542772319853696922981593395191350295076650614971698020972990849017418431836304435472927187702278399001760278669810976721884241518821079439591530333584452284517493789282530046151997590167087764930295887914308503350136663616604790667768084002442986725969827357944041618007015326686930197292553262351527402447681407665664594899664775193644710890458780784399961787599510849628335432827998712093558974088146231885468708329818271456132292866958122165983019804353557169145076533187603812358038836017187247306286824810824586303447790811827489765075690527458827250360935412177872550824299473911088505182254427348189569097905188554378523698027624051093923572264421055776423935
o1 = -339653493153104472182169686533258416336086067633408766817549978606897487068991364321308993400753401717588313400477683005887560743348576364011690687620193591678921503645815442589607289629411835032995233842860455649248184003540768186249900877947117716425004314126984488154290280732349799248419414515419712079659363638711583084875606438226569309535184957586117550991999461147552681374566051852875886391106257780335568599120288842176359085312732482451623783500446560358509372235096349562925093849986653098547837162186510167924594723010692965060180377665399665896994778283448835318777214808034928066344927549475253394319038633009985313418572601786745878889566874321858388833026060863612982057735931659765261432964228264643972512477255327294324146930141439577499957970699574639550720475012636664503475517054941642430639634166974726593706356094976198232147203180215505533555522314802424813933204153214982243273710097468319475874923995279183277948749232821885475113452598314365759240344665498640505306596160485772490533892009377481917948958509922646192047110809779562532602797194168142394054027395124109800207841642981073357453593670742169857729926055170066655070844835123632372594814768462296969953955130554325735804428051714791244992805528587533562976585401911774369128556997765280520431843060025798611245234560708624892339280173983556990860660996989640883302332521833136433550855869998494164357493991629575579147486392865647295612668350475199324019433839106934077319680553683587607068647435234324391735406824387700703911303851404156836757398517462445591198685666525533417517354858416600583106338535480292962226152614462230413628722598004683417957196675671309895312385193729471467005392284844583210468626024131686790463171343451912763976350640922235432231299051800918854235113664710982982869485249627881797988397396982375688882966940598586988741496505397396153940496522400400298475621484570545379964806733660677310708260750203766417473062225053059128621784197534902402610125948213064819921394611259253749650439
o2 = -145354862911792346160076469754924605058748901321956976414025110494300870498150770834875756168440565799849307756933888397825564956453795350779447817508625968335316914069847297428588156293304835862617870465227139051611653161185589250840010145049585137257002182391654808926460534424404733015698199950313696661572328048147618886076928229770997092606021789833713940828081159906227716246529406039902683914882744266611626945838341246018070593646813814945644224994058071495569110529912644158415958666065011597102998227924850330601052059229341521855190678989265093287380136901003751082096635933573199055545834725181798513499867732520078233477921950003885871703138616619089864756698549546354671131669662854787394216222658261544968769811697615708247161463777717243338706810074388083517698291930849354335117518860288317577099427824855767802149787428072539310853731446117058936215576391781694713337181485489220077246048261915206802164910500763350142841184297842983612760915646052604710144951224749683643484493963002716025854050970027427197418542571547804885066055323422009101510103386959708195977976787693158936819451666719111181799553158367946979718707422087843696345983361719763608563478106571894862306045748180534255756474927542837997730347739537210173527270053290572534333165193209031681240729727884256875789331731581202621854118082580116326304900600645271499145660992551193630227734973098466706856335791307321961955196558739960815343654846356101867101051343766289945659240640291403951714002345426629725063386571502480484624187113332202767232986776404590261486368597579920499333185179484495390343314228954144206112475674035960756539961862381399935271472965186271865847373984865200909994467629933039140864374321175257338781641646918263515938154331254638998295489683596165737394198178806844283905767598398610058905647477809426897033782574840905652206475469020699986437289125701633865494041700555165826799295750925232956690597927936838278983243276401078746018034833550519768621576808585258844398842277693547666723961
o3 = -242332670284802154496224815988398583606797713611273114863857184971947040245427417716756634045918516267595017464540084175957801334005449677067987743057200934824272399673306416608057389471142469748193903281046820468025802996798794253517003482614363006361921612369018203945343351520071278635888439596260104127293859397308298163928355643135784995661435928851842570878942623590668937710125660422936217086269562600175804271340414403162173759699444252462709954073265098356551999888771541723673086092610686728501291508053798052507557070602738704989356072484199219570984254960777989032950905887916283530111240986548852410340470478562093131905344886930952779570312804406256524992756342389636750809609966583603777582354068751760891997987641464358143201550847220275079366515282883261380377943593994399036069491218576328431869711416873961907225510604577038142610355053697143896537066387988759238699795640296743338599088053476821304279355508627571706039171230601944891313103283827102457381173474857306618433161990203081748233668179202126894573096860294131676643810210277307153204948750394568193616398602830015199996103621141297960136483406091860441926752183473141835190626932507488409970133863487338144053778106395919734923148760259786620802203271311439770408286499551215727974584279018084369568757035278969680946494384275479100484183267111413851611832576242432915639138960822761319591044381122692617232312832689311456955674180067971856441076980015776977278229730868855209003735601489713481164172171808538855543118185571178895733674541202848848295844287038135198725056577513008768953645025144671157596554907036857505927395710352512281263853930148827871275287679645455055545340112906232737764174950359299767789228794180421550470213238584542113654424940276650110829118212096847706865661504421065454812466124811447243835662207617661479843008129327232764827408745419546617386977487206955650540660399905856777179956893319000329950521514235844136767325456721461486045372681003443984469718242364363178757680529408227688324358
ct = 166734554398008115898809543086752630636666431187591419756940556941077057
m1 = o1 ^ x
m2 = o2 ^ x
m3 = o3 ^ x
assert m1 ^ x == o1
assert m2 ^ x == o2
assert m3 ^ x == o3
ms = []
for m in [m1, m2, m3]:
mask = 2**32 - 1
for i in range(208):
ms.append((m & mask) >> (32*i))
mask = mask << 32
assert len(ms) == 624
#special thanks: https://inaz2.hatenablog.com/entry/2016/03/07/194147
def untemper(x):
x = unBitshiftRightXor(x, 18)
x = unBitshiftLeftXor(x, 15, 0xefc60000)
x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
x = unBitshiftRightXor(x, 11)
return x
def unBitshiftRightXor(x, shift):
i = 1
y = x
while i * shift < 32:
z = y >> shift
y = x ^ z
i += 1
return y
def unBitshiftLeftXor(x, shift, mask):
i = 1
y = x
while i * shift < 32:
z = y << shift
y = x ^ (z & mask)
i += 1
return y
mt_state = tuple([untemper(x) for x in ms] + [624])
r.setstate((3, mt_state, None))
key = r.getrandbits(239)
print(long_to_bytes(key^ct))
☆フラグ
ctf4b{M4y_MT19937_b3_w17h_y0u}
乱数問題には苦手意識があったのですが、やってみると面白そうなのでやれて良かったです。出題者に感謝。
2-5. omni-RSA (難易度:hard, 240 points, 14 solves)
☆設問
極めて"omni"なRSAを作りました！
problem.py
from Crypto.Util.number import *
from flag import flag
p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)
flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)
s = d % ((q - 1)*(r - 1)) & (2**470 - 1)
assert q < r
print("rq =", r % q)
print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)
output.txt
rq = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666
☆方針・解法
最初の方針
$d_0:=d \mod{(q-1)(r-1)}=2^{470}x+s$ と置くと、$x$ は $2^{42}$ 程度で総当たりは難しいですが small_roots の雰囲気 MAX です。$ed_0-1\equiv0\mod{(q-1)(r-1)}$ ですから、$e(2^{470}x+s)-1=k(q-1)(r-1)$と書け、$k$ は $2000$ 程度なので総当たり可能です。
$r=q+r_q$であることが分かっているので、$q$ を $y$ と置いた式で defund Coppersmith を試みることにしました。
この試行ではパラメータをキツめにしたせいもあって相当な時間を溶かすこととなりました。
軌道修正
defund Coppersmith が刺さらないので途方に暮れていたのですが、変数を減らすことと次数を減らす（増やさない）ことを念頭に式を再検討し、そもそも $q$ は $n$ の約数だから $\mod{q}$ で考えた式を small_roots してみようと思いなおしました。この時点でソルバの最終系に近い形が出来ていたのですが、beta=0.25、epsilon=0.01 という「刺さらないけど時間がかかる」パラメータでやってしまい、さらに時間を溶かしてしまいました。
最終系
small_roots のパラメータを見直すため、テストスクリプトを書いてどのあたりなら刺さるのかを検討していたところ、beta = 0.20～0.22 くらいでうまくいきそうだったので、それを採用することにしました。
$k$ と$d_0$ が決まれば、関係式から $2$ 次方程式を解いて $q$ の値を算出できます。$q$ が出れば残りの未知数も芋づる式に判明しますが、面倒だったので $r$ だけ計算したらそれで事足りてしまいました。
こんな具合に試行錯誤のうえ、最終的には以下のようなソルバとなりました。
☆ソルバ
solve.sage
from Crypto.Util.number import *
rq = 7062868051777431792068714233088346458853439302461253671126410604645566438638
e = 2003
n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666
PR.<x> = PolynomialRing(Zmod(n))
for k in range(1,2002):
#print(k)
f = e * x * 2^470 + e * s - 1 - k * (1 - rq)
f = f.monic()
roots = f.small_roots(X=2^42, beta = 0.2)
if roots != []:
print(roots)
d0 = roots[0]
break
_d = int(d0 * 2^470 + s)
_phi = int((e * _d -1) // k)
assert int(e * _d - 1) % int(_phi) == 0
D = ((rq-2)^2-4*(1-rq-_phi)).nth_root(2)
q = (-(rq-2)+D)//2
r = q + rq
print(long_to_bytes(pow(int(cipher),_d, int(q*r))))
☆フラグ
ctf4b{GoodWork!!!YouAreTrulyOmniscientAndOmnipotent!!!}
「script や output が短いけど、手応えのある問題」が大好きなので、この問題は☆５つです（個人の感想です）。
3 おわりに
今年は Crypto 全完したものの、「食べ残し」が多数発生して不本意な出来でした（その分、参戦記ネタは尽きないのですが・・・）。来年は Crypto + あと 1 種目全完を目指します。