2019-05-28

duckが送るBeginners CTF 2019 Go RSA（Crypto)の解説

どうもduckです。今日はGo RSAについて書くよ。
名前から見てわかる通り、公開鍵暗号の１種であるRSA暗号がわからないと解けない。
公開鍵暗号については↓を見るかググって。
公開鍵暗号方式とは？初心者でもわかる公開鍵暗号方…｜Udemy メディア

まずはざっくりRSAについて数式部分を書くよ。アタックするからには理解しておきたい。
平文を $m$ ,暗号文を $c$ ,公開鍵 $N,e$ ,秘密鍵 $d$ とする。
具体的なアルゴリズムの流れを見よう。
（１）受信側： $p,q$ (十分大きな素数)を選び $N=p*q$ とする。（任意）
（２）受信側： $\phi(N) = (p-1)*(q-1)$ を計算する。（ $\phi(N)$ はオイラーのトーシェント関数と呼ばれ、定義があるが今はこの形のみ知っていれば十分）
（３）受信側： $\phi(N)$ と互いに素な整数 $e$ をもってくる。（任意）
（４）受信側： $e * d \equiv 1 (mod \phi(N))$ となる $d$ を求める。（拡張ユークリッドの互除法を用いる）
（５）受信側：公開鍵 $N,e$ を公開。
（６）送信側： $c = m ^{e} (mod N)$ と暗号文を作成し、送り付ける。
（７）受信側： $m = c ^{d} (mod N)$ で復号でき平文をゲットできる。

通常RSAへのアタックは秘密鍵dを求め、暗号文を解読することが考えられる。
正しく運用されていれば安全であるが、以下のサイト（おすすめ）に挙げられるようなパラメータの設定ミスをすると解読されうる。
CTFではそう言った問題がでるのだろうか？（ちなみにCryptoのBitFlipではその中の脆弱性を突く問題が出た）

RSA暗号運用でやってはいけない n のこと #ssmjp from sonickun

www.slideshare.net

さて、では実際に問題を見よう。
Server: nc 133.242.17.175 1337と問題文に書かれている。
Linuxのnc(ネットキャット？)コマンドで接続しよう。

f:id:falconctf:20190528203001p:plain — GoRSA

まずEncypted　flag is~と書いてあるから、これを複合すればよいことがわかる。問題文でNを忘れたといっていたからNがわかれば解けそうと思っておく。
次に最後の行を見よう。The D was~と書いてある。おそらくこれが秘密鍵だろう。
真ん中部分はユーザー入力である。こちらが入れた数字に対し、謎の数字が返ってくるようだ。
Encyptedflag,D,ユーザー入力により返ってくる値は再接続のたびに変わるようだ。
つまり我々は、３回までのユーザー入力からヒントを得てNを計算すればよいのだろう。
頑張ろう。

ユーザー入力が何を返しているのかがよくわからないのでまずは実験してみる。
その結果、
(a)いつでも１に対しては１が返ってくる。
(b)同じ接続の中で同じ数字を入れると同じ値が返ってくる。
(c)1を除いた入力に対して、大体同じ桁数の値が返ってくる。
などの特徴があることが分かった。

(b)から乱数などは使われていなそうだし,(a)から何かのべき乗計算をしているのではないかと推測できる。
また(c)からmodを取っているのではという推測もたつ。

これらの推測と上で説明したRSAの式たちを見比べると
$m ^{e} (mod N)$ とかか？と勘繰る。
つまり
$（ユーザー入力）^{e} (mod N)$ が返ってきてそうである。

この仮定の下でNを求めに行こう。
我々が入手できるのは以下の３本の式をみたすinput,rの組である。
$r1 \equiv \mathit{input1} ^{e} (mod N)$
$r2 \equiv \mathit{input2} ^{e} (mod N)$
$r3 \equiv \mathit{input3} ^{e} (mod N)$
input1,2,3:ユーザー入力、r1,r2,r3:サーバーから返ってくる値

inputを操作してNを顕現させたい。
こういう任意で入力できる問題は大体小さい数字をinputとするとか、２のべきをinputとするとかだとうまくいくことが多い。
またmodで悩んだときは $=$ を使った形に直すとうまくいくことも多い。（特に数学よくわからないという人にお勧めする）
なんともひどい誘導だが以下のようにすればNが求まる。

inputとして2,3を与える。
$r1 \equiv 2 ^{e} (mod N)$
$r2 \equiv 3 ^{e} (mod N)$
これは適当な整数 $k,k'$ を用いて
$r1 = N * k + 2 ^ e$
$r2 = N * k' + 3 ^ e$
と書ける。 $2^e,3^e$ を移項すると
$r1 - 2 ^ e= N * k$
$r2 - 3 ^ e= N * k'$
となる。お分かりだろうか？これでNが求まるのだと。我々は勝利したのだと。
公約数を思い出してほしい。
$r1 - 2 ^ e$ と $r2 - 3 ^ e$ の約数に明らかにNがある！やったぜ。
追記：
書き忘れていましたが、RSAでは一般的に $e=65537$ が用いられることが一般的です。
それを使いましょう。

最大公約数はユークリッドの互除法というアルゴリズムで高速に求まる。
わからない人は学習指導要領が改定されて高校生でも知ってるからなんとか学んで。

一つだけ注意しておくと、場合によってはNの整数倍が出てきてしまうことだ。
具体的には $k$ と $k'$ が互いに素ではない場合である。

でてきたN で
$flag = (\mathit{encryptedflag}) ^{d} (mod N)$
をしてもうまくFLAGが出ないときは、違うペアで試してみるとよい。

まあ私もまだやってないんだけどな！！
おつかれさま！また明日！！！！！

追記：いままでずっとFLAG書くの忘れてた。この回のだけ残ってたので貼っておく。
ctf4b{f1nd_7he_p4ramet3rs}

コード

from Crypto.Util.number import long_to_bytes
import math

c=17085620552658351183335544500690226272875422158935145341165358891244918062440861767294934344129747923141668732715787177751203261627026230386846774546801758980449060209320668104704097944761232115359564279944744011306082649286738268431655969673959744882964166437946605686952999392726525064814877455046451725768410312677212123398538560508582810195854081569284454616942253143100785505524167586197713206797113052644900411469422688939261982981855377987421758621965591995651651907064794890066406751092949615529766196252331712555809200696136040227513088824530815886117265362591775970066168663851386432407675346081685681927303
r1=12308943287801278381602271020636811688003973209453971581897097872964067773128210282456593395262732270249597048332555708886509308319520920180598650511766799712167512259642431520797141790111692065487078128961600689554367757339155513577144978675218793446249701301839641500569661759646423276187542173318171335382960662774233945196912603079740368273195927210668950566249353140103271649493388077952820446391920593020564832067217333892843371485574515498385351718470670460084994536203053240439442202272531830723505883179658297522435407455008248311187789781960113589834827112974168260506676775743411648452439899496100115579052
r2=2266282824131486468448037400097649751436638343554890873042053537566051913016220134485956663087061113434331598112257987671237397919781153037511303664236178026024200716300256313054976795440759304679065940565652927875017851134819722783392228160931697899128129053901710489789174445944014043443083527638965765809070488225452982880922703011627801716957978130236512493237537609220292483693697781504935020101279551815050569381943159352285456791072657310654958418397051221153029472723065900747600963890428868830367126410421411370704517816919980344041449903545200031548407512798483005492350803089508282331827149736642020562720
d=1814452580735375349943862720618828918630139915423974587850653785462197560999774344107135368454555043491667375552314392616309506004814918478288708383302285286685970221339255810252747773103059121031264059575772453212207545840235008436247634620933941004726742219846507737410336486611203816257479343986488367114011777255284708000213494879044090517505540067938866432994071508106192379566964836729181005004378702445684759533988544066532056379172318125748705772688436663116204079306930926328994293354010739696046248305808409576809006078527713033315527061213274532299699148742370572758989921371532108833619290755313406817153

e=65537
N = math.gcd(r1-pow(2,e),r2-pow(3,e))
m = pow(c,d,N)
print(long_to_bytes(m))

2019-05-27

duckが送るBeginners CTF 2019 Party（Crypto)の解説

初心者向け writeup duck Beginners CTF 2019 Crypto

どうもduckです。唯一自力で解いたPartyについて解説したい。

さて、問題をDLしたらparty.tar.gzというファイルだったので、
tar -zxvf party.tar.gzコマンドで解凍する。
tarはLinuxの標準的な圧縮形式で、windowsでいうzipみたいなファイルらしい（よくわからん）。
解凍するとencrypt.pyというファイルとencryptedというファイルが出てきた。
encryptedをcatするとなんか数字がめちゃくちゃ出てくる。
encrypt.pyを読めば意味がわかるはず。

さて、ここからは大きく二つのフェイズに分けて説明しようと思う。
１．pythonファイルの解析。これによりflagを得るためにやるべきことがわかる。
２．実際にflagをゲットしてみる。（３元１次連立方程式を解くことになるんだけれどね）
頑張っていこう。

1.pythonを読む

f:id:falconctf:20190527201912p:plain

python party
1,2行目：モジュールのimportだ。Cでいうインクルードだ。
5~9行目：関数の定義だ。関数が呼ばれた時に見ればいい。
12,13行目：変数の定義。放っておこう。

14行目からコードをしっかり見ていくことになる。
が、先に15行目について一言触れておく。assert文と呼ばれるもので、普通デバッグのときに使われる。（はず）
assert(条件式)のように書き、条件式がFalseのときにのみ処理を停止させる。
今の例だと $secret < 2^N$ を満たせば動くが、それ以外はプログラムが落ちる。
（一応補足。pythonではa**bで $a^b$ をあらわす。）
気になる方は試すべし。この先の説明では無視する。

14行目：

secret = bytes_to_long(FLAG)

2行目でimportしたCrypto.Util.numberの関数bytes_to_longを使っている。
Crypto.Util.numberを詳しく調べたわけではないが、FLAGの文字列を数字列に直してsecretに代入しているのだろう。
ちなみに数字列を文字列に直すのにはlong_to_bytesを使えばいけた。単純。

つまりsecretという数字列が求まれば

FLAG = bytes_to_long(secret)

でFLAGが求まる。

17行目：

coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]

[]はpythonではリストを表す。
リストの結合は＋でかける。

[2,3] + [1,1,2,4]
#[2,3,1,1,2,4]

例はこんな感じ。

次に

[getRandomInteger(N) for i in range(M-1)]

がわからない方。python内包表記で調べると幸せになれる。
超簡単な例↓
リスト内包表記の活用と悪用 - Qiita

結局こうなる。

coeff = [secret,getRandomInteger(N) ,getRandomInteger(N) ]

getRandomIntegerも2行目でimportしたCrypto.Util.numberの関数。
Nまでの乱整数を取ってくるのだろう。（調べてないけど）
長い変数はうざったいので短い名前にする。getRandomIntegerは毎回結果が異なることに注意。

coeff = [s,r1,r2 ]

18行目：

party =  [getRandomInteger(N) for i in range(M)]

つまり

party = [getRandomInteger(N),getRandomInteger(N),getRandomInteger(N)]

というリスト。
だるいので短い名前にする。

party = [p1,p2,p3]

20行目:

val = map(lambda x: f(x, coeff), party)

無名関数（lambdaのこと）とかmapについて説明するのは面倒になので、わからない方は
Python2,3での比較！map関数を使う方法【初心者向け】 | TechAcademyマガジン
ここら辺を参照いただきたく。
結局valはこうなる。

val = [f(party[0],coeff),f(party[1],coeff),f(party[2],coeff)]

やっと関数fが出てきたので５行目に戻ろう

5行目：

def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i)
    return y

len(list)はlistの長さを返す関数で、
pow(a,b)は $a^b$ を表す関数である。
よってf(x,coeff)は今、len(coeff)=3だったことに注意すると
$f(x,coeff) = coeff[0] + coeff[1] * x + coeff[2] * x ^{2}$ を表す。

coeff = [s,r1,r2 ]
party = [p1,p2,p3]

としていたから、結局
$f(x,coeff) = s+ r1 * x + r2 * x ^{2}$
であり

val = [s+ r1 * p1 + r2 * (p1 ** 2),s+ r1 * p2+ r2 * (p2 ** 2),s+ r1 * p3 + r2 * (p3**2)]

である。
長いので

val = [v1,v2,v3]

としておく。

21行目：

output = list(zip(party, val))

これがencryptedの中身である（続く22行目でoutputで出力されているから）。結局encryptedにはpartyとvalが格納されていることが分かった。
つまりp1,p2,p3,v1,v2,v3が与えられたということだ。

partyとvalからsecret(=sとおいていた)を復元しよう。

val = [s+ r1 * p1 + r2 * (p1 ** 2),s+ r1 * p2+ r2 * (p2 ** 2),s+ r1 * p3 + r2 * (p3**2)]

なのだから
$v1 = s+ r1 * p1 + r2 * p1 ^{2}$
$v2 = s+ r1 * p2 + r2 * p2 ^{2}$
$v3 = s+ r1 * p3 + r2 * p3 ^{2}$
となる。
v1,v2,v3,p1,p2,p3はencryptedに書いてある。残りはs(secret),r1,r2だけだ。
未知数３個。式３つ。中学生でも解ける連立方程式だ。

２．flagをゲットする
詰まったところだけ書く。
・numpy（数学ライブラリ、有名）をつかって解いてみる
　v1,v2,v3,p1,p2,p3が大きすぎて解けない。おそらく中でCコードが動いてるからかと予想。

・自力で解く
連立方程式を解くと以下のようになる。
　 $r2 = \frac{(v1-v2)(p2-p3)-(v2-v3)(p1-p2)}{(p1-p3)(p1-p2)(p2-p3)}$
$r1 = \frac{v1-v2}{p1-p2} -r2*(p1+p2)$
$s = v1 - r1 * p1 - r2 * p1 ^2$

それをpythonに（四則演算のみ、もはや電卓として使う）解かせる。コードを書くのはsupereggに任せる。
python慣れも兼ねて頑張って。
python2だと問題なくとけるが、python3の場合は
Python3の割り算は切り捨てではない - Qiita
のため解けない。
計算途中で小数に変換されることによる誤差のせい。
/じゃなく//を使えば３でも解ける。r2をわざわざ通分した表示にしているのもそのためである。

出てきた答えを