プログラム系統備忘録ブログ

記事中のコードは自己責任の下でご自由にどうぞ。

kurenaif Valentine Problems write-up

CTF

「kurenaif Valentine Problems」(ハッシュタグ #kurenaifChallenge)とは、IT系魔女VTuberとして活動なさっているkurenaifさんによるCrypto5問の問題集です。問題一覧や説明等はGithubにあります。またYoutubeにて説明動画の【1000人記念】Cryptoの問題を5問作りました！【kurenaifChallenge】 - YouTubeを公開なさっています。

解けた問題

p_p_rsa

N := p*pであるためNの平方根からpを算出し、後は普段どおりのRSA復号、だと思っていたらドツボにはまっていました。普段のRSA暗号ではpとqは異なる素数であるためphi == (p-1)(q-1)となりますが、今回はphiの計算式が変わってきます。その点に気付けたらphiの定義通りに計算して復号してやれば解けます:

#!/usr/bin/env python3.8

import Crypto.Util.number

e = 65537
N = 7504521114311153672308826977564891107288058227100173341193360340321176562970983694756086045753375611733443716948010092176135133045533366956059169702726409
c = 3120246791506259955679234385495683489853187127801200033777823093969698684663885288175101358075188702658492281935014546035799989917015048182861857825663454

def my_sqrt(x):
    lower = 0
    upper = x
    while lower < upper:
        mid = (lower + upper)//2
        if mid*mid == N: return mid
        if mid*mid < N:
            lower = mid+1
        else:
            upper = mid
    return None

p = my_sqrt(N)
print(f"{(p*p)-N=}")

phi = N-p # 普段のRSAとは変わってくる式
d = pow(e, -1, phi)
print(f"{p=}")
print(f"{e=}")
print(f"{d=}")
print(f"{phi}=")
print(f"{(e*d)%phi=}")
m = pow(c, d, N)
print(f"{m=}")
print(f"{pow(m,e,N)-c=}")
print(Crypto.Util.number.long_to_bytes(m))

実行してフラグを得ました: kurenaifCTF{phi_is_not_p-1_p-1} 教育的で非常に良い問題だと思います。

redundant_rsa

この問題ではm^3とm^65537が与えられます。(m^3)^21846すなわちm^c65538を計算し、m^65537の逆数を掛けることで平文を計算できます:

#!/usr/bin/env python3.8

import Crypto.Util.number

N = 8208175638972200577186038102634114258848486365767463332763957381946985480397227219800325703361508208728778216773973313756762762324416016301819271949512427
c3 = 510199524103978915755062119293765889950938959100085136114101960072728304594090942964306874023123457091885387418124063977610496306587745044542739034336862
c65537 = 4673531855283872496727093452348048121242854682829577660566947295656149440028839210065857595110277181842297946378296819272562912619683355333762343087859186

c65538 = pow(c3, 21846, N)
m = pow(c65537, -1, N) * c65538 % N
print(Crypto.Util.number.long_to_bytes(m))

実行してb'd\x0c\xa9\xd3\xa4\xca\xe1\xed\x08)\x82:kurenaifCTF{you_4re_redundant_master}\xe6\x00\xe9M{\x17\x16\xfb\xcd\x8c\x97\xa3'を得ました。この中に含まれるkurenaifCTF{you_4re_redundant_master}がフラグです。

the_big_five

問題概要にある通り、以前のkurenaifさん問題の発展版となる問題です。以前に書いたプログラムを思い出したり、参考動画を見返したりしました:

#!/usr/bin/env python3.8

import math
import Crypto.Util.number
from Crypto.Cipher import AES

X = [171988490999968958074461906163126253991,
     149759767375550138601832127658924300851,
     21392649857558566532141954695914673807,
     52236160143411890255640980579270361316,
     22081153611165744867415455406756477578]
# これら5個に続く線形合同法の値がkeyになる
# x_next = (((A * x_prev) + B) % M
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 = [t[0]-t[1] for t in zip(X, X[1:])]
print(f"{len(Y)=}") # 4

Z20 = Y[0]*Y[2] - Y[1]*Y[1]
Z21 = Y[1]*Y[3] - Y[2]*Y[2]
Z30 = Y[0]*Y[3] - Y[1]*Y[2]
M = abs(math.gcd(math.gcd(Z20, Z21), Z30))
print(f"{M=}")
print(f"{Crypto.Util.number.isPrime(M)=}")

Y = [(y+M)%M for y in Y]
print(Y)
A = Y[1] * pow(Y[0], -1, M) % M
B = (X[1] - (A*X[0]%M) + M) % M
for i in range(len(X)-1):
    assert (A*X[i]+B)%M == X[i+1]

key = (A*X[-1]+B)%M
cipher_dec = AES.new(Crypto.Util.number.long_to_bytes(key), AES.MODE_CTR, nonce=nonce)
print(cipher_dec.decrypt(ct_bytes))

実行してkurenaifCTF{Less_numbers_are_better}を得ました。 ちなみに最初はZ21を省いてZ20とZ30だけでgcdを取っていましたが、それだとM*4の合成数が出てきました。Z21もgcd対象に加えるとMそのものが出てくれました。

なお手元環境では、当初from Crypto.Cipher import AES箇所にてImportError: cannot import name '_AES' from 'Crypto.Cipher'エラーが発生していました。思ってもいなかった箇所でコケて慌てていましたが、公式ドキュメントにpycryptodomeの文字を発見し、python3.8 -m pip install pycryptodomeでインストールすることで問題なく実行できるようになりました。

解けなかった問題

the_onetime_pad

平文よりも50bit余分に線形合同法で出力しているのでそこから状態を逆算して残り約14bitを全探索する問題に思えたのですが、状態逆算がさっぱり分かりませんでした。無念……。

嘘解法で解いた問題

three_values_twister

参考ブログ記事の内容で解読するコードがhttps://github.com/ambionics/mt_rand-reverseにあったので意気揚々と実行してみました。

$ ./reverse_mt_rand.py 1355541750 602658525 624 1
Traceback (most recent call last):
  File "./reverse_mt_rand.py", line 224, in <module>
    main(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]), int(sys.argv[4]))
  File "./reverse_mt_rand.py", line 179, in main
    seed = undo_php_mt_reload(S000, S227, offset, flavour)
  File "./reverse_mt_rand.py", line 161, in undo_php_mt_reload
    if not (S000 == state[offset]):
IndexError: list index out of range

エラーです。ずっこけました。ソースをよく読んでみると、どうやらreverse_mt_rand.pyの第3引数のoffsetが624未満を前提としているようです。今回の問題ではoffsetが624であるため、このスクリプトでは残念ながら復号できません。 PHPのメルセンヌツイスターAPI関係でググっていると、PHPのmt_rand()/rand()問題 – yohgaki's blogにて以下の興味深い記述を見つけました:

しかし、現在のPHPのMT randはたった232のシードしかサポートしておらず、初期状態は232しかありません。本来のMT randに比べ遥かに簡単に予測できます。

上記記事は2019/01/29が最終更新の記事ですので現在のPHPでも同様かは分かりませんが、とりあえず232全探索することにしました。製作者側のphpversion()は7.4.3で、手元環境のphpversion()は7.2.24と差はありますが、mt_randのドキュメントには7.2.0以降変更はないようなので問題は無さそうです。 そんな発想で書いたのが下のコードです:

#!/usr/bin/env php
<?php
echo "phpversion: " . phpversion() . "\n";
echo "PHP_INT_MAX: " . PHP_INT_MAX . "\n";
echo "PHP_INT_SIZE: " . PHP_INT_SIZE . "\n";

$rands = array();
function check_seed($seed)
{
    mt_srand($seed);
    for($i=0;$i<2049;$i++)
    {
        $rands[$i] = mt_rand();
        if($i == 624) { if($rands[$i] != 1355541750) { return false; }}
        if($i == 851) { if($rands[$i] != 602658525) { return false; }}
        if($i == 1078) { if($rands[$i] != 173373131) { return false; }}
    }
    echo "FOUND! seed: " . $seed . "\n";

    $key = $rands[2048];
    $cipher_text = "FEAjLtaf9bQ7oJCY53mV3IJOWDVi7donm6KEb9yjsxkCjuz0gpluD1vczeQGb8Pg";
    $plain_text = openssl_decrypt($cipher_text, 'AES-128-ECB', $key);
    echo $plain_text;
    return true;
}

for($i=-2147483648; $i<=2147483647; $i++)
{
    if($i%100000==0){echo $i."\n";}
    if(check_seed($i)){break;}
}

?>

とりあえずしばらく動かして様子を見たところ、10万回ループに2秒ちょっとかかるぐらいの計算時間でした。そのペースでしたら全探索も24時間ほどで終わるので動かし続けました。 intが64bitになっているのでもしかしたらmt_rand()呼び出し時の暗黙的なシード設定も64bit幅である可能性を危惧していましたが、一晩寝て起きる頃には無事に復号成功していました:

phpversion: 7.2.24-0ubuntu0.18.04.7
PHP_INT_MAX: 9223372036854775807
PHP_INT_SIZE: 8
-2147400000
(中略)
-1294800000
FOUND! seed: -1294795481
kurenaifCTF{twice_reloaded_mersenne_twister}