きゅうり。

主にCTF関係のことを書いていく気がします

Tokyo Westerns CTF 3rd 2017 writeup

CTF crypto

最近全然記事書いてませんでしたが、久しぶりのwriteupです。

（研究やら他の趣味やらで単純にCTF以外のことを色々していたというだけ）

m1z0r3として参加して、479点で68位でした。

自分としては以下の4問を解き、204点を入れました。

・Palindromes Pairs - Coding Phase -（PPC/warmup, 24pts）

・My Simple Cipher （Crypto/warmup, 25pts）

・Baby DLP （Crypto, 64pts）

・Baby RSA （Crypto, 91pts）

それぞれのwriteupです。

Palindrome Pairs - Coding Phase -

単語がいくつか渡されて、それをくっつけて回文が何組作れるか？という問題。

pythonを使っているので、単語の組み合わせはitertoolsを使い、回文判定はスライス記法でやるだけ。

TWCTF{find_favorite_smell}

My Simple Cipher

オレオレ暗号っぽいもの（名前とかあるのかはよくわからない）

フラグの先頭が「TWCTF{」で始まることから逆算するとkeyの頭6文字がわかる。

更に、暗号文の最後の方はフラグが使われておらず、keyとkeyから暗号文が作られているので残りのkeyも逆算可能。

TWCTF{Crypto-is-fun!}

Baby DLP

こちらから数を送ると、 $2^{m \oplus input} \pmod{p}$ が返ってくるシステム。

ここで、0と1を送った場合を考える。

・0を送った場合

返ってくるのは、 $2^{m} \pmod{p}$

・1を送った場合

mの最下位ビットが0のとき、 $2^{m+1} \pmod{p}$

mの最下位ビットが1のとき、 $2^{m-1} \pmod{p}$

となる。

したがって、この関係性を見ることでmの最下位ビットを推測することができる。

同様にして、最下位ビットだけでなく各ビットについても求めていくことができる。

一種のLSB oracle Attack？

TWCTF{0f97c1c3ac2aedbd7fb8cd39d50f2b561d31f770}

Baby RSA

$p = rand(2^{1024})$

$q = 19*p + rand(2^{512})$

$p = nextprime(p)$

$q = nextprime(q)$

となっているRSA暗号。

まず結論だけ言うと、19*n をフェルマー法で素因数分解するだけで解けたらしい。

そんなことには気づかずに頑張って解いたので、せっかくなのでその方法を載せておきます。

素数p, q を以下のように表す。

$p' = rand(2^{1024}), r = rand(2^{512})$

$p = p' + \alpha$

$q = 19p' + r + \beta$

ここで、qがだいたいpの19倍ぐらいという考えから以下のように置き換え。

$q = 19p + x$ ただし $x = r + \beta - 19\alpha$

さてこのとき、

$n = p*q = 19p^2 + xp$ であるため、pを変数とした二次方程式として見ることができる。これをpについて解くと、

$p = \frac{-x + \sqrt{x^2+76n}}{38}$ となる。なおpは必ず正なので√の係数が負の場合は省略した。

つまり、このような整数pが求まるxを総当たりで探せば良いことに帰着する。

しかし、 $x=r+\beta-19\alpha$ であり、rは512ビットの範囲であるため愚直にxを総当たりしても探しきれない。そこで、平方数判定は容易に行えることを利用して以下のように解いた。

・ $\sqrt{76n}$ を超えるギリギリの整数を探す。（rnと置く）

・rnを1ずつ増やしつつ、 $rn^2-76n$ が平方数となっているか確認

・平方数となっている場合xが求まるので、pが計算可能か確認

nが2052ビットであり、 $x^2$ はせいぜい1024ビットであることを考えると、rnのスタートさえしっかりしていれば大した回数は試行せずとも当たるはずである。

rnのスタートについては、以下のような愚直な方法で計算した。

・76nは10進で619桁なので、まずは $rn=10^{309}$ とする

・1~9について、rn*iが76nを超えない限界を探し、 $rn=i*10^{309}$ と更新

・同様に1桁ずつ下げていきながら76nを超えない限界を求めていく

このようにして求めたrnを元に先の方法を試したところ、1足しただけですぐに答えが求まった。

TWCTF{secretly_cherry-blossom-viewing}

まとめ

Babyは全然Babyじゃなかった。

pwnはswapやsimple noteもちょろっと見たものの、全然解けなかったので解けるようになりたい。

あと、The Worstはおそらくやることは合ってるはずなんだけどglibcのバージョンが違うのかなんなのか、たぶんrandの出力結果が正しいものが得られてない気がして解けてないのでつらい。