Zenn
🦔

kurenaif valentine problems writeup

2021/02/21に公開
math
#
CTF
#
crypto
tech

全体としてのテーマ 作問意図

よかったらチャンネル登録してね！
https://www.youtube.com/watch?v=-0AizwBzVDc&t=1s

僕の普段の動画の5割程度を理解できる人を対象として問題を作っています。
なので、「典型的なアルゴリズムを理解してそのとおりに実装する」の次の段階の「典型的なアルゴリズムを変形して適用する」をテーマとして全問題作問しました。

あくまでも「変形する」ことを目標としているので、論文や記事を調べる技術はこの問題の対象外としています。

また、あらゆるところに気を抜いたりコードを何も考えずにコピペしたりすると落ちる悪意のある問題設計になっています。

p_p_rsa

問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/p_p_rsa

「RSA暗号を素因数分解すると秘密鍵を作ることができる」というとても有名な攻撃方法を使った問題になります。
素因数分解をしたらなぜ秘密鍵を作れるのか？に関しては https://youtu.be/HKDyUELFdXs こちらの動画で説明をしているので省略します。

p = \sqrt{p^2} は二分探索を利用することで O(\log N) で求めることができるため、現実的な時間でp^2 から p を求めることが可能です。
今回のコードでは gmpy2 を使って平方根を求めています。

ここで1点気をつけないといけないことがあり、RSA暗号で必要なオイラーのphi関数はいつもと違う形になります。p^2 の中に、p^2と互いに素の数は pの倍数以外なので、

\phi(p^2) = p^2 - p^2/p = p^2 - p = p(p-1)

となります。これさえ気をつければあとはいつもの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暗号のオイラーの\phi関数がなにかちゃんとわかって使ってますか？といった趣旨の問題を作りました。
僕はRSA暗号を \phi(pq) = (p-1)(q-1) と丸暗記していた時期があったので、そのときにこの問題を解くと詰まると思いますw
皆さんは引っかからずに解けましたか？

CTFの暗号初心者には「1問頑張って解けた！」という気持ちを
暗号を普段からやっている人は「この問題集はただの典型セットではないな…？」といった気持ちを持ってもらえることを目指して作問しました。

動画ではオイラーの\phi関数の求め方も説明しているので、ぜひ見てみてください

redundant_rsa

問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/redundant_rsa

初心者向けCTFのRSA暗号の問題では、m^3 の三乗根を求めることで解くことができるものがよくあります。今回はそれに見せかけた common modulus attack (簡単版) です。

解き方は2通り存在しています。

  1. common moduls attackをする
  2. m^{65537} / (m^3)^{21845} = m^2 \mod pq を求める。

common moduls attackに関しては、もしこの解き方を試していない方はググって試してみてください。

2番に関して、「あれ？逆数が存在するのってNが素数のときだけでは？」と思う方がいらっしゃるかもしれませんが、それはすべての数に対して逆数が存在するために必要な条件で、 X \mod Y で XとYが互いに素であれば、X^{-1} \mod Y は求めることが可能です。

逆数がわからない人は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を最初の問題に持っていきました。
それぞれの復号は難しいのに、２つ情報を与えちゃうと簡単に復号できちゃうって面白いですね。

the_big_five

問題: https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/the_big_five

線形合同法なのですが、Mが素数であることが保証されています。

以前動画出した内容のhardバージョンです。(https://www.youtube.com/watch?v=DVZnJG76wdg&feature=youtu.be)
実は以前動画を出したタイミングで6つじゃなくて5つでも行けることは気づいていたのですが、話がややこしくなるので説明しませんでした。

動画のココ https://youtu.be/DVZnJG76wdg?t=857 で説明した式

\begin{aligned} Y_1 Y_4 - Y_2 Y_3 &\equiv 0 \mod M \\ Y_2 Y_5 - Y_3 Y_4 &\equiv 0 \mod M \end{aligned}

は、以下のようにすると添字を一つ減らすことが可能です。

\begin{aligned} Y_1 Y_3 - Y_2 Y_2 &\equiv 0 \mod M \\ Y_1 Y_4 - Y_2 Y_3 &\equiv 0 \mod M \end{aligned}

あとは動画と同じ流れなので省略します。
しかし、実は output.txt に悪意が込められており、この式だけでは M が求められないようになっています。

\mathrm{gcd}(Z_1, Z_2) = nM

になるのですが、動画内でボソッと言っている通り時々失敗します。
Z_1 / M と Z_2 / M が互いに素である保証がないからですね。

しかし、 ランダムな数字を２つ取り出したとき、その数字のgcdが大きくなることは考えにくく、Mにひっついているnも大きな素因数を持つことは考えにくいです。
このことから、雑に素因数分解のツールをかければ Mnからnを取り出すことができ、最終的にMを得ることができると考えられます。

あとは動画の通り各種パラメータを復元してください。

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を取るときれいにMが取り出せる形になっていたのですが、そのようなケースだとz3使うと一撃で復元できてしまうので、あえてイジワルなケースにしました。(Mが素数という情報を与えないと解きにくい条件になってます。)
楽しようとして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 >= m となるタイミングです。

|   x -----> 2x (2xの1bit目は0)
|                  x ----------------> 2x (2xの1bit目は1)
|----------------------------|----------------------------|
0                            m                            2m
// (m未満の数を2倍して2m以上になることはない。)

このことから、x1の1bit目が0か1かを知ることによって、x0が m/2 未満か以上かを調べることができます。

LCGを2回すすめると、

x2 = 2 * x1 = 4 * x0 % m

となります。
同じ要領で考えると、

x2\mathrm{の1bit目} = \begin{aligned} \left\{ \begin{array}{l} 0\ (0 < x_0 < \frac{m}{4}) \\ \\ 1\ (\frac{m}{4} < x_0 < \frac{m}{2}) \\ \\ 0\ (\frac{m}{2} < x_0 < \frac{3m}{4}) \\ \\ 1\ (\frac{3m}{4} < x_0 < m) \end{array} \right. \end{aligned}

となります。わけわかりませんね。図で整理しましょう

x0の値を知りたいとき

  1. x1の値が偶数なら左半分、奇数なら右半分
  2. x2の値が偶数なら赤色、奇数なら緑色
  3. x3の値が偶数なら赤色、奇数なら緑色

といった形で、偶数か奇数かの情報でx0を半分半分に削っていくことができます。

1回あたり1bitの情報が得ることができるので、mが2^{64}程度であることを考えると64個前後あればxを復元することが可能になります。
が、残念ながら与えられている値は上位50bitの50個だけです。

先程のアルゴリズムを思い出すと、2^{64}を50回半分にすると、2^{64} / 2^{50} = 2^{14} = 16384 程度になるので、十分ブルートフォース可能な領域になります。

あとは出てきた文字列に対して 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がたくさんありましたが、大変解き方が美しく正直そちらを想定解放にしたい気持ちになりました。

https://project-euphoria.dev/blog/15-kurenaif-valentine/
https://gist.github.com/hakatashi/67d04f55e29b44982da4db260fe17757

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のメルセンヌツイスターは以下のような流れになっています。

  1. state(長さ624の配列)を初期化する (ブログ内の php_mt_initialize)
  2. state(長さ624の配列)をリロードする (ブログ内の php_mt_reload)
  3. i = 0 とする。
  4. mt_rand() が呼ばれたら state[i] を返し、 i += 1 する (実際にはちょっと加工された state[i] が返されます)
  5. i >= 624 になったタイミングで、php_mt_reload を行い、i=0 に初期化する。

php_mt_initializeは https://www.ambionics.io/blog/php-mt-rand-prediction の記事より、(sはstateの配列を表しています。)

s_i = 1812433253 (s_{i-1} \oplus (s_{i-1} \gg 30)) + 1

となっているので、一つ値がわかれば、すべての s を復元可能です。しかし、僕たちが得られるのは s の値ではなく、reloaded値です。reloadedされたs を s' とします。

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していました。これは賢い。
https://mystiz.hk/posts/2021-02-21-kurenaif-challenges/

hakatashiさんが、自分の想定解放で解いてくれていました。
https://gist.github.com/hakatashi/67d04f55e29b44982da4db260fe17757

終わりに

ここまでよんでいただきありがとうございました。
3日程度で突貫で作った問題なのですが楽しんでいただければ嬉しいです
たくさんwrite upもいただけて本当に嬉しいです！
誘っていただければcrypto作問お手伝いするので気軽に声かけてください！
楕円曲線暗号や格子がテーマの問題集も考えてるので、また機会があればご参加ください！

Discussion