kurenaif valentine problems writeup
全体としてのテーマ 作問意図
よかったらチャンネル登録してね!
僕の普段の動画の5割程度を理解できる人を対象として問題を作っています。
なので、「典型的なアルゴリズムを理解してそのとおりに実装する」の次の段階の「典型的なアルゴリズムを変形して適用する」をテーマとして全問題作問しました。
あくまでも「変形する」ことを目標としているので、論文や記事を調べる技術はこの問題の対象外としています。
また、あらゆるところに気を抜いたりコードを何も考えずにコピペしたりすると落ちる悪意のある問題設計になっています。
p_p_rsa
問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/p_p_rsa
「RSA暗号を素因数分解すると秘密鍵を作ることができる」というとても有名な攻撃方法を使った問題になります。
素因数分解をしたらなぜ秘密鍵を作れるのか?に関しては https://youtu.be/HKDyUELFdXs こちらの動画で説明をしているので省略します。
今回のコードでは gmpy2 を使って平方根を求めています。
ここで1点気をつけないといけないことがあり、RSA暗号で必要なオイラーの
となります。これさえ気をつければあとはいつものRSA暗号です。
import gmpy2
from Crypto.Util.number import *
e = 65537
N = 125937874126566553468562637085007486585009882198900471346124970700745139850601406389278102858547591316951732836339 c = 292169253602099717389467291437705800285793920113220996672745325567386286497731934259841036885889537360542062895429
p = gmpy2.isqrt(N)
phi = p*(p-1)
d = pow(e, -1, phi)
m = pow(c, d, N)
print(long_to_bytes(m))
あとがき✍
RSA暗号のオイラーの
僕はRSA暗号を
皆さんは引っかからずに解けましたか?
CTFの暗号初心者には「1問頑張って解けた!」という気持ちを
暗号を普段からやっている人は「この問題集はただの典型セットではないな…?」といった気持ちを持ってもらえることを目指して作問しました。
動画ではオイラーの
redundant_rsa
問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/redundant_rsa
初心者向けCTFのRSA暗号の問題では、
解き方は2通り存在しています。
- common moduls attackをする
-
を求める。m^{65537} / (m^3)^{21845} = m^2 \mod pq
common moduls attackに関しては、もしこの解き方を試していない方はググって試してみてください。
2番に関して、「あれ?逆数が存在するのって
逆数がわからない人はRSA暗号の動画を見てください。
from Crypto.Util.number import *
N = 7532904180440030654260493057657103859993725657728495972755544617610160369455769190335661292730910646082991508
c3 = 563340900698456316900537359639886888285055778145077383160630708921451011888649807530242455540267197887360354
c65537 = 38705304820414947382865343742907200779438743999129766672960688937006421767320338031107752520811978838180
cinv3 = pow(c3, -1, N)
c2 = c65537 * pow(cinv3, 65537//3, N) % N
cinv2 = pow(c2, -1, N)
m = c3 * cinv2 % N
print(long_to_bytes(m))
あとがき✍
実はこの問題が最初の問題の想定でした。しかし、p_p_rsaを思いついてしまい、「RSA暗号は素因数分解ができること」のほうが有名そうな気がしたのでp_p_rsaを最初の問題に持っていきました。
それぞれの復号は難しいのに、2つ情報を与えちゃうと簡単に復号できちゃうって面白いですね。
the_big_five
問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/the_big_five
線形合同法なのですが、
以前動画出した内容のhardバージョンです。(https://www.youtube.com/watch?v=DVZnJG76wdg&feature=youtu.be)
実は以前動画を出したタイミングで6つじゃなくて5つでも行けることは気づいていたのですが、話がややこしくなるので説明しませんでした。
動画のココ https://youtu.be/DVZnJG76wdg?t=857 で説明した式
は、以下のようにすると添字を一つ減らすことが可能です。
あとは動画と同じ流れなので省略します。
しかし、実は output.txt
に悪意が込められており、この式だけでは
になるのですが、動画内でボソッと言っている通り時々失敗します。
しかし、 ランダムな数字を2つ取り出したとき、その数字のgcdが大きくなることは考えにくく、
このことから、雑に素因数分解のツールをかければ
あとは動画の通り各種パラメータを復元してください。
from Crypto.Util.number import *
from Crypto.Cipher import AES
# M is prime number!
X = [0] * 5
# M is prime number!
# M is prime number!
X[0] = 171988490999968958074461906163126253991
X[1] = 149759767375550138601832127658924300851
X[2] = 21392649857558566532141954695914673807
X[3] = 52236160143411890255640980579270361316
X[4] = 22081153611165744867415455406756477578
# X[5] = ?
nonce = b'\x0b:\xce<\xb0\xe8@,'
ct_bytes = b'\\\x8f\xfayc\xce\xfc<`\xc7\xe1\x91Jh\x0c6 \x8a\xd8\x0f\xdc^\xa3\xb9\xa1Kv\x96O<\xbcx\x8e\xea\xc3&'
Y = []
Y.append(X[1] - X[0])
Y.append(X[2] - X[1])
Y.append(X[3] - X[2])
Y.append(X[4] - X[3])
Z = []
Z.append(Y[0] * Y[3] - Y[1] * Y[2])
Z.append(Y[0] * Y[2] - Y[1] * Y[1])
M = GCD(Z[0], Z[1])
for x in factor(M):
print(x)
if isPrime(x[0]):
M = x[0]
A = Y[1] * pow(Y[0], -1, M)
B = X[1] - A * X[0]
key = (X[-1] * A + B) % M
print(key)
# decrypt
cipher_dec = AES.new(long_to_bytes(key), AES.MODE_CTR, nonce=nonce)
print(cipher_dec.decrypt(ct_bytes))
# X[3] = 133298764071615439652590352531856533694
あとがき✍
最初は output.txt はgcdを取るときれいに
楽しようとしてz3を使い、求まらずに困る様子を想像しながらイジワルなoutput.txtが生成されるのを待ちながら何回か乱数生成を繰り返しました。
the_onetime_pad
問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/the_onetime_pad
鍵がわからないと理論上解読不可能なワンタイムパッドですが、鍵がわかると当然復元可能です。
鍵は乱数で生成した値の1bit目だけを連結したもので、平文+50bitの長さがあります。
平文とxorをとっているので、以下のようになります。
|--------------------------key----------------------|
|-------------plain_text-------------|
|--key(50bit)--|-------------key^plain_text---------|
plain_text
がわからない以上 key^plain_text
を知る手段はありませんが、key(50bit) の部分は鍵がそのまま出力されています。ここから鍵を頑張って復元しましょう。
鍵は、今回は線形合同法で求められていますが、以下のようなちょっと特殊なパラメータになっています。
x1 = 2 * x0 % m // mは奇数であることが保証されている
さて、通常であれば2倍すると偶数になってしまいますが、奇数であまりをとっているので、必ずしも偶数になるとは限りません。ではどのようなケースで
| x -----> 2x (2xの1bit目は0)
| x ----------------> 2x (2xの1bit目は1)
|----------------------------|----------------------------|
0 m 2m
// (m未満の数を2倍して2m以上になることはない。)
このことから、x1の1bit目が0か1かを知ることによって、
LCGを2回すすめると、
x2 = 2 * x1 = 4 * x0 % m
となります。
同じ要領で考えると、
となります。わけわかりませんね。図で整理しましょう
x0の値を知りたいとき
- x1の値が偶数なら左半分、奇数なら右半分
- x2の値が偶数なら赤色、奇数なら緑色
- x3の値が偶数なら赤色、奇数なら緑色
といった形で、偶数か奇数かの情報でx0を半分半分に削っていくことができます。
1回あたり1bitの情報が得ることができるので、
が、残念ながら与えられている値は上位50bitの50個だけです。
先程のアルゴリズムを思い出すと、
あとは出てきた文字列に対して kurenaifCTF
が含まれていれば、それがフラグです。
from fractions import Fraction
from Crypto.Util.number import *
def get_x(cipher, pos, m, length):
hoge = []
while cipher > 0:
hoge.append(cipher % 2)
cipher >>= 1
while(len(hoge) < length):
hoge.append(0)
hoge = hoge[pos+1:]
low = Fraction(0, 1)
high = Fraction(m, 1)
for i in range(len(hoge)):
mid = (low+high)/2
if hoge[i] == 0:
high = mid
else:
low = mid
return low.__ceil__(), high.__floor__()
def challenge(cipher, length, m, x):
inv2 = pow(2, -1, m)
xs = [0] * (length+1)
xs[length] = x
for i in range(length, 0, -1):
xs[i-1] = xs[i] * inv2 % m
rand = 0
for i in range(length):
rand += (xs[i] & 1) << i
num = ((1 << length) - 1) & (cipher ^ rand)
print(long_to_bytes(num))
m = 16411099384203967235
length = 311
cipher = 258578933248047129070234127076818734931906736562394908260192233729045538766864090271939203007290696772322321
low, high = get_x(cipher, length, m, length + 50)
print(high - low)
for x in range(low, high+1):
challenge(cipher, length, m, x)
あとがき✍
実はこの問題はRSA暗号でよくある攻撃方法としてで有名な LSB decryption oracle attack という攻撃手法をLCGに落とし込んだ問題です。
正直ブルートフォースパートは入れるかどうかかなり悩みましたが、二分探索パートは世の中にソースコードがたくさんあり、コピペするだけで解かれそうな気がしたのでそれだけでは解けなくしました。
RSAの準同型パートがなくなった分、思いつきやすくはなっていると思いますが、皆さんはいかがでしたか?
他の人のwriteupを見ていたたところ、平文が kurenaifCTF
で始まることを前提としたwriteupがたくさんありましたが、大変解き方が美しく正直そちらを想定解放にしたい気持ちになりました。
three_values_twister
問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/three_values_twister
625番目、851番目、1078番目のphpのメルセンヌツイスターの値が与えられるので、seed値を求めてくださいといった問題です。
実はブログの記事を読み進めていくと、https://github.com/ambionics/mt_rand-reverse こちらのソースコードがあり、これを実行するだけでseed値がわかるように見えます!!
が、残念ながらこのスクリプトでは解けません。このスクリプトで解けるためには、624番目以下の乱数でなければならないからです。
詳細の説明はAMBIONICS SECURITYのブログ記事を参照していただくとして、phpのメルセンヌツイスターは以下のような流れになっています。
- state(長さ624の配列)を初期化する (ブログ内の php_mt_initialize)
- state(長さ624の配列)をリロードする (ブログ内の php_mt_reload)
-
とする。i = 0 -
mt_rand()
が呼ばれたらstate[i]
を返し、i += 1
する (実際にはちょっと加工されたstate[i]
が返されます) -
になったタイミングで、i >= 624 php_mt_reload
を行い、i=0 に初期化する。
php_mt_initializeは https://www.ambionics.io/blog/php-mt-rand-prediction の記事より、(
となっているので、一つ値がわかれば、すべての
s'[227] ^ s'[0] = (((s[227] & 0x80000000) | (s[228] & 0x7FFFFFFF)) >> 1) ^ (s[227] & 1 ? 0x9908b0df : 0)
s'[227]
と s'[0]
と s[227]
がわかれば s[228]
が求まりそうに見えますが、実は s[227]
は上位1bitと下位1bitしか使われていないことから、4回ループを回せば全探索できることがわかります。これで未知数が s[228]
だけになるので、復元できます。
実際にはもう少し一般化できて、s'[i]
とs'[i+227]
の2つの値がわかれば復元できます。
あとは php_mt_initialize の逆計算で s[0]
まで遡ればOKです。
ここまでがブログの内容の概要です。
ここで、先程のphpのmt_randのアルゴリズムを思い出してみると、一つ疑問が生じます。
「mt_reloadが二回呼び出された場合はどうなるのでしょうか?」
このケースは実は先程のgithubのコードでは考慮されておらず、復号に失敗していしまいます。
今回のoutput.txtはmt_reloadがギリギリ2回呼ばれているので、残念ながら seed値 を求めることができないんですね。
s'
からさらに mt_reloadした値を s''
としましょう。先程のアルゴリズムで
-
s''[624]
とs''[851]
からs'[228]
(s''[852]相当の位置) -
s''[851]
とs''[1078]
からs'[455]
(s''[1079]相当の位置)
を求めることができるので、ここで一度mt_initializeの計算を我慢して更にもう位置段階ここからmt_reloadの
-
s'[228]
とs'[445]' から
s[446]`
を求めて、mt_inializeの逆の計算を行えばこの問題を解くことができます。
もともとのコードにライセンスが明記されておらず、よくわからないので部分的に公開します。呼び出した関数はだいたい元のコードと同じです。変えた部分はコメント参照で。
def main(_R000, _R227, flavour):
_R000 <<= 1
_R227 <<= 1
res = []
for R000_0 in range(2):
for R227_0 in range(2):
R000 = _R000 | R000_0
R227 = _R227 | R227_0
S000 = undo_php_mt_rand(R000)
S227 = undo_php_mt_rand(R227)
res += undo_php_mt_reload(S000, S227, flavour) # undo_php_mt_reloadはseed値まで求めず、s228を返す
return res
R624 = 1209301904
R851 = 1698721275
R1078 = 1614541112
# R2048 = ?
flag = "f3kUS0bNpRycf48xdlMhL1R3qlKYkV6X2L0td7gJTaov0HSjOwSLMiSqCKU6I9A9"
S228_candidate = main(R624, R851, 1)
S455_candidate = main(R851, R1078, 1)
seed_candidate = []
for S228 in S228_candidate:
for S455 in S455_candidate:
seed = get_seed(S228, S455, 228, 1) # get_seedは元コードのundo_php_mt_reloadと同じ。
if seed:
seed_candidate.append(seed)
print(seed_candidate)
seed = seed_candidate[0]
print(seed)
あとがき✍
この問題の作文は6時間くらいかかりました。原案は2つの値で復元できる→ランダムに値が欠落したメルセンヌ・ツイスタでもかんたんに復元できる
といったものだったのですが、思いの他条件が厳しかったのでせっかくなのでブログに書いているコードより厳しい条件で求められるものを考えてみました。
が、phpのメルセンヌ・ツイスターのseedは2^32程度のパターン数しかないため、マシンパワーで殴られてしまいました。。。
2^32は競技プログラミング感覚だと絶対ムリなんですけど、CTF感覚だと行けちゃうのが辛いですね。僕の目に入ったwriteupではほとんどブルートフォースで説かれちゃっていました。
一番効率の良いブルートフォースがおそらくこれで、メルセンヌツイスターに触れずにAESに直接打ち込んでkurenaifCTFでgrepしていました。これは賢い。
hakatashiさんが、自分の想定解放で解いてくれていました。
終わりに
ここまでよんでいただきありがとうございました。
3日程度で突貫で作った問題なのですが楽しんでいただければ嬉しいです
たくさんwrite upもいただけて本当に嬉しいです!
誘っていただければcrypto作問お手伝いするので気軽に声かけてください!
楕円曲線暗号や格子がテーマの問題集も考えてるので、また機会があればご参加ください!
Discussion