きゅうり。

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

Kaspersky CTF writeup

CTF crypto

遅くなりましたが、Kaspersky CTFのwriteupです。

Cryptoを2問だけ解いたので書きます。

（当初はあまり書く気がなかったものの、勉強会中解き終わって暇なので書きます）

 

Security home cameras (crypto 300)

謎の暗号化されたpngが渡される問題。問題文にヒントは特になし。

pngのマジックナンバーすら破壊されているため、なんとなくpngのマジックナンバー（0x89 50 4E 47）と暗号のxorをとってみると、どのバイトも0xffとなる。

したがって、暗号の全バイトと0xffでxorをとると画像が復号できる。

20171011160454

 

Bad computation (crypto 800)

やたら読みにくいスクリプトが渡される。（実はこれが暗号文だった説）

が、ある程度cryptoを（特に公開鍵暗号）解いたことのある人ならば、egcdやmod_invあたりは関数の中身を見ると判別できると思う。

結論から述べると、スクリプトを読むとpaillier暗号であることがわかる。

関数 L(x) = (x-1)/n や、暗号化の処理などが特徴的なので知っているとわかる。

さて、ここで暗号化の処理を詳しく追ってみる。

dcew \equiv g^b * r^n \pmod{n^2}

c \equiv g^m * r^n * dcew \pmod{n^2}

c \equiv L(c^{\lambda}) * L(g^{(p-1)(q-1)})^{-1} \pmod{n}

最初のcの計算でpaillier暗号における暗号化を行った後、次に復号処理をしていることがわかる。ここで暗号化の際に余計にくっついているdcewを見てみると、bを暗号化している。

つまり、平文mとb=22の暗号文の積をとった後、それについて復号を行う。

ここで、paillier暗号は平文について加法準同型性を持つ。

すなわち、Enc(m)*Enc(b) \equiv Enc(m+b)となる。

今回の問題ではこれについて復号を行っているため、与えられた暗号文はm+b = m + 22となっている。

したがって、暗号文の各文字から22を引くとフラグが得られる。

ソルバ

print "KLCTF{"+"".join(map(lambda x:chr(ord(x)-22),"hnd/goJ/e4h1foWDhYOFiIZ+f3l1e4R5iI+Gin+FhA==".decode('base64')))+"}"

フラグ

KLCTF{paillier_homomorphic_encryption}

あとがき

decrypt the message (crypto 700)が解けていないので誰か教えてください。

padding oracleかなぁと思ったら500しか返ってこなかったので諦めて投げました。

z3 を使ってみる

CTF crypto

SAT/SMTソルバであるz3を使ってCTFの問題を解いてみた、という記事。

m1z0r3内の勉強会でz3を取り扱ったものの、途中で資料作るのがめんどくさくなって問題の解説を放棄してたのでその分ここでwriteupを書きます。

 

z3pyは導入済みで、大まかな扱い方はわかっているという前提で行きます。

（細かい使い方はMMA wikiを読んでください）

 

今回扱う問題は以下の4問

  • HackIt 2017：crypto 150
  • CSAW CTF 2017：Another Xor (crypto 100)
  • CSAW CTF 2017：Almost Xor (crypto 200)
  • D-CTF 2017：Forgot my Key (misc 点数忘れた)
続きを読む

Backdoor CTF 2017 writeup

CTF crypto pwn

m1z0r3で出てました。2050点で21位、個人的には以下の6問を解きました。

ジャンルは適当につけて、実際に解いた順ではなくジャンルでソート。

・complex rsa (200, crypto)

・stereotypes (点数忘れた, crypto)

・imagerev (点数忘れた, crypto)

・baby-0x41414141 (150, pwn)

・just-do-it (250, pwn)

・funsignals (点数忘れた, pwn)

問題数が多いので雑にいきます。めんどくさいのでソルバも省略。

 

complex rsa

「RSAは破られることがあるらしいから2回も暗号化したったwww」みたいな問題文。

2つの公開鍵と暗号文が渡される。公開鍵のパラメータを見てみると、nの値が等しくeの値は異なる。RSA暗号の性質上、同じ法の元でe1,e2を用いて暗号化するということは、e = e1 × e2 % n を用いて暗号化したに等しい。

そこでeを計算してみるとそこそこ大きな値になるので、wiener's attackをして終了。

 

stereotypes

以下の3つのファイルが渡される

・plaintext：文末がちょっとだけ伏せられた平文

・ciphertext：暗号文

・pubkey：RSA公開鍵

明らかにstereotyped message attackなのでやるだけ。

 

imagerev

encrypt.pyを見ると読む気がなくなるほどめんどくさそう。

が、怪しげな数字のリストが目に付くのでググると、SHA256の実装っぽいことがわかる。つまり、画像のpixel毎にRGB値を SHA256(chr(R)+chr(G)+chr(B))としている暗号もどき。

通常ハッシュの逆算は不可能だが、今回は平文空間が256^3程度しかないので計算可能。予めテーブルを作っておき、暗号文を64バイトずつ切り出していけば平文が求まる。

あとは、全ピクセル数からいい感じの縦横比をguessして画像に起こせばフラグが書いてある。

 

baby-0x41414141

buf = read();

printf(buf);

exit();

という感じのプログラム。

ご丁寧にフラグ出力用の関数が用意されているので、書式文字列攻撃によってexitのGOTをフラグ出力関数に書き換えて終了。

フラグ出力関数がある問題が久々すぎて、どっかに/bin/sh用意してsystem呼んでってやろうとしてて30分くらい無駄にした。

 

just-do-it

自明なbofがあるので、writeへret2pltして適当にlibcのアドレスをリークさせた後、ret2libcでsystemを呼んでおしまい。

やるだけ。

 

funsignals

readを呼んだ後、読み込んだものを引数にsigreturnを呼ぶ。

sigreturnの引数は自由に操れるので、いわゆるSROPの簡単なバージョン。

フラグは実行ファイル中に書かれているので、sigreturnでwriteを呼べばフラグが出力される。

しばらくなぜかraxだけうまくセットされずに悩み、結局よくわからないところに積んだ値がraxになったのでそれで解いた。

 

 

まとめ

（有名どころと比べると）レベル感としては比較的易しめだった。24hで5人制限と考えればこんなものかも？

extend meも手をつけていたものの、ナンチャラアタックすらいらないとは思わなかった。とはいえlength extensionしても解けるはずなのに解けてなくてつらい...

ローカルでは解けたんや... リモートじゃ解けないけど...

 

あとがき

解いたけどwriteup書いてない問題が5問ぐらい溜まってるのでそのうち消化します

 

ASIS CTF Finals 2017 Mary Motion writeup

9/9~9/11に行われていたASIS CTFにソロ参戦していました。

といっても研究室の合宿中でほぼ時間がとれなかったので、Warm upを２問と一番簡単なpwnだけ解きました。

Mary Motion (pwn, 43pts)のwriteupだけ書きます。

 

Mary Motion

FSBのある関数とBoFのある関数をそれぞれ呼び出せるプログラム。

脆弱性は見ての通りなので、やるだけ問。

FSBでcanaryをleakし、BoFでret2pltをしてsystemを呼んでやる方針。

/bin/shの確保のためにいったんret2pltでreadして適当な所に置いてます。

まとめ

ただでさえ久しぶりのpwnで色々忘れてるのに、寝不足やら集中できない環境やらで１問解くのが精一杯だった。

pwnとcryptoは色々復習します。

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の出力結果が正しいものが得られてない気がして解けてないのでつらい。

ubuntuでapt-getが名前解決できなかった

しばらく何も書いてなかったの、たまにはCTF関係ないことも書きます。

カテゴリー的には、「技術的に苦戦したことの覚書」

 

内容的に多くなったので、2つの記事にわけて書きます。

続きを読む