CBCTF Writeups - aki33524’s blog

miyaji-labで参加した。これは暗号系研究室に所属している以上Cryptoを全完するという強い決意を表している（大嘘）。

結果としてはRandom RSAを時間中に解くことが出来なかった。悲しい。

Common Modulus Attackをする。

Common Modulus Attack 1と異なりeが3を最大公約数として持つので、m³ mod nが求まる。

mが十分に小さいのでm³ % n = m³となり、二分探索により3乗根を解けば良い。

平文mの後ろに0をpaddingするということが左にbitshiftする(_m * = m * 2^x)ということに気がつけば簡単。

これまでと同様にm¹⁷ mod nを得るが、m¹⁷ = (m * 2^x)¹⁷ = m¹⁷ * 2^17*xとなる。

xはこれまでのフラグから適当に定めて2^17*xの逆元を掛けてやるとm¹⁷ mod nを得る。

Common Modulus Attack 2と同様の考察から17乗根を求めると良い。

Pailler暗号に対する選択暗号文攻撃をする。得られる情報は復号した結果のLSBである。

Pailler暗号は加法準同型を満たす珍しい暗号である。

また、Pailler暗号は加法準同型だけで無く、mに対する暗号文cが得られている時、任意のrを選択しm*rの暗号文c'rを作成することが出来る。

これら2つの性質は今回の問題において平文に対する加減乗除が行えることを示唆する。

よってm-1とm/2の演算を行うことにより、mを右shiftした平文に対する暗号文を作成することが出来る。

つまり、LSBが0のときはm/2をし、1のときは(m-1)/2をする。これを繰り返すことで全てのbitをleakすることが出来る。

準同型性でLSBの情報がleakすると言えばRSAのBleichenbacher Attackの亜種が有名である。実はこの知識があったせいで変に勘ぐりすぎて時間が掛かった。

詳細は割愛するが、nが常に奇数なことによりLSBからmの範囲を限定する（上位1bitをleakする）。これを繰り返して二分探索のようにすることでmの全体を得る。

同じような攻撃が成り立つのだろうとしばらく複雑に考えてしまったが、Pailler暗号は加法準同型を満たすことを冷静に考えたら解けた。

ちなみに僕はまだPailler暗号が何故成立するのかを理解しておらず、式を眺めれば解けた。この理解の放棄は上手く行ったと思う。

あと、netcatで上手く整数を取得する方法が分からなくてかなり汚いコードになった。良いやり方を知ってる人は教えてください。

eが大きいと言えばWiener's attackというのが相場である。これはeが大きいことが本質ではなく、その時にdが小さくなり得るのが問題である（実際にはほとんどのdが小さくならないので余り気にしなくて良いのではないかと考えている。この点について詳しい人が居れば教えてください）。

実際、式中でd_が小さいことが保証されているのでWiener's attackを使うのがほぼ確定する。

まずコード中の式を変形するとd = (p-1) * (q-1) - dよりe * d = e * ((p-1) * (q-1) - d) = -e * d_ = 1 mod phi(n)である。

普通のWiener's attackはe * d = 1 mod phi(n)においてdが十分小さい時にn, eよりdが求まるというものである。

よって既存の手法のe * d - 1とある箇所をe * d + 1（ここにおけるdはd_なことに注意）と書き直せば良い。

これによって求まる d_を用いてc^d_ = m^-1 mod nを求め逆元を取ると良い。

Wiener's attackは名前と成立条件だけ知っていて、詳細を知らなかった。そこで既存のコードを変形することを軸に考えたのが上手く行った。問題を開いてから10分も掛からなかったと思う。

この問題は2つのフェイズに分かれる。乱数列を予測するフェイズとそれを元にmを復元するフェイズである。

乱数列予測で沼にハマったが、これはxorshift+と呼ばれるものでz3というSMT solverを用いれば簡単に解けるようだ。

そこからmを予測するフェイズであるが、これは実は2つの平文があれば解くことが出来る。

ある2つの暗号文c1 = (m + b1)^e, c2 = (m + b2)^eとb1, b2と公開鍵が得られている時、mを求めることが出来る（Franklin-Reiter related-message attack）。

これは(x + b1)^e - c1 = (x + b2)^e - c2 = 0において、2つの多項式が共通の多項式(x - m)を持つことを利用して多項式におけるgcdを解く。

ということを普段多変数多項式の研究をしている研究室の友人に言ってみたところMangaで解いてくれた。

実はSMT solverを使わなくても32個の出力列を使えば解けるのではないかと思う。ただかなり実装が面倒な上、もしかしたらSMT solverの再開発かも知れない（SMT solverの中身を知らない）。

Franklin-Reiter related-message attackのことを何も理解していないので理解したい。

久々のCTFの割に解けたほうだと思うが、勉強不足を痛感した。それに加えて下手に知識を得ていたせいで調べることを放棄して無駄に考えてしまう時間が長かった。この辺りはCTF慣れだろうか。