math314のブログ

主に競技プログラミング，CTFの結果を載せます

tkbctf4 簡易writeup

rcrypto

M2 + MB_1 = x, M2 + MB_2 = y (mod N)

という式があるので，Mを求めよという問題．

(１つ目の式)y - (2つ目の式)x = 0 より

(y-x)M2 + (B_1 * y - B_2 * x) M = 0 (mod N)

gcd(M,N) = 1 じゃないと困るので(複合できないし)

\[ (y-x)M + (B_1 * y - B_2 * x) = 0 \]

また， gcd(y-x,N) = 1 だったので

\[ M = (B_2 * x - B_1 * y) * (y-x)^{-1} (mod N) \]

後は代入するだけ．

high-low

次の手が分からないと仮定した場合，最適な戦略で挑んだとすると，1回でもクリア出来る確率が63.2%を超えるのに必要な試行回数は132020回程です．頑張ってください．

amida

これでstage20まで行きました．

https://gist.github.com/math314/24a458d0ffc006d151ff

最後のフラグを投げる前に終わってしまいました．

The flag is "Gh057 in the 1egs, not 5hell!"

天下一プログラマーコンテスト 2014 本戦

先週ですが，id math で出ていました，17位で残念．

公式ページ : http://tenka1.klab.jp/2014/

コンテストページ : http://tenka1-2014-final-open.contest.atcoder.jp/

六本木ヒルズの建物はそれ自体で迷路として完成しており楽しかった．

Tシャツを貰ったので先週から今週にかけて開催されていた ICPC夏合宿 に着て行きました．結果，さわり心地が良く寝間着するとよいのではと感じた．

人の写真だけどこんなの

来年も開催されたら賞金getしたい．

続きを読む

SECCON 2014 オンライン予選(日本語) Writeup

SECCON 2014 オンライン予選(日本語) Writeup

チーム Mr.Takeda で，5人(@aki33524,@chibiegg,@haru2036,@misodengaku,@__math) で出ていました． 結果としては4位で全国大会出場決定，すごい．

誰かわからないけど竹田さんに迷惑じゃないか心配になってきた．

f:id:math314:20140720152945p:plain

私は あみだくじ(プログラミング 300),ダンプを追え！(バイナリ 300)と,箱庭XSSリターンズ(Web 300)の部分点を取りました． 箱庭はみんなでワイワイしながら得点しました．

続きを読む

Heavy-Light Decomposition

最近アツイ*1、木を分解する手法の一つ。 重軽分解 とか、HL-decompositionとか呼ばれている。

アルゴリズム

  1. edgeを"Heavy"と"Light"に分けて
  2. "Heavy"edgeで繋がれた頂点を一つにまとめる

の2段構成。

ここに書いてあるedgeの分け方は元のHeavy Light Decompositionと違うかも

*1:[要出典]

続きを読む

SECUINSIDE 2014 prequal writeup

竹田氏 500pt 52th でした

pillow_reader crypto 200pt

唯一のcryptoだった。

ファイルをダウンロードすると python3.2aのコンパイル済みのpycが来る。

pillow_reader.pycにPrimeUtilが必要との事なので、要求される関数を実装することで、import出来る状態にする。

デコンパイル出来ないかなーと探していたら unpyc3.py というモジュールが合ったので、それを使った。

さてデコンパイルと思いきや、PKIがデコンパイル出来ない。 調べてみると PKI.PKI.encryptの中間コード -> .py への変換が失敗していた 仕方ないのでここだけ手動で直す

p,q = 256bit以下のランダムな素数
n = p * q
l = (p-1) * (q-1) # l = phi(n)
m = l^-1 (mod n)
g = n+1

となっている。 ここで暗号化は

def encrypt(plain):
    # r はランダムな素数
    cipher = pow(g,plain,n**2) * pow(r,n,n**2) % n**2

となっている。 phi(n2) = n*l であるから、 cipherl = gplain * l (mod n2) が成り立つ g = n+1 より、 gplain * l % n**2 = plain * l * n + 1 式変形して (cipherl - 1) / n = plain * l (mod n) l^-1 = m より、 plain = (cipherl - 1) / n * m これがdecryptの式

パケットを見ると こっちの82byteのkey 0x5cb94b9d25716136c6b880bf791f743ecfdf5a383b3aa27093c1673599cbd8a1c160e4a06f777c5b163f0fec50405944d9764bed8c7dd9eb19abc1225b322ed むこうも0x83byteくらいのキーを渡しているのが分かる 0x86e05276d3c364cd6157e23cd972e0a662dff9ebf9ade83eae022c292c767bcd6cf528c7f6ae98af2f7811d99c9e45e7e4e6f1b9841aabf89a84dd0673099b61

向こうから送られてくる鍵が同じなので、pcapからこちらの送るcipherを真似してやれば、adminkeyを調べる必要がなくなる

恐らく raw = 'cat secret\n' を送った時のcipherが

cipher = [0x80,0x00,0x00,0x00,0x1f,0x59,0x85,0x6d,0xbb,0xbe,0x90,0x99,0x5c,0xf9,0x49,0x75,
0xaf,0xd9,0x4d,0xcf,0x46,0xbf,0x2d,0x16,0xd8,0xb8,0xa3,0x75,0x46,0x85,0xd3,0xeb,
0x37,0x65,0xd6,0x91,0x84,0x62,0x37,0x8a,0x2f,0x7e,0x94,0x81,0x82,0xe8,0x4a,0x85,
0x7a,0x25,0xbe,0x05,0x7a,0x12,0x2e,0x9d,0x65,0xe3,0x2f,0xb0,0x1a,0x98,0x4f,0x44,
0x2e,0x78,0x1f,0xa0,0x2e,0x8a,0x4d,0x27,0x28,0xb1,0xa4,0xc3,0xea,0x39,0x05,0xaa,
0x95,0xab,0x9f,0xba,0x7b,0x7d,0xfa,0x3b,0x39,0x11,0x6d,0x49,0xc1,0x0d,0x16,0x17,
0x25,0xaa,0x0b,0xee,0xac,0x18,0xb7,0xa2,0xa9,0xc9,0xd5,0x5a,0x0b,0xf6,0xf1,0xa2,
0xb2,0xca,0x90,0x3e,0xb1,0x50,0x86,0x99,0x5b,0x2f,0x77,0xd7,0x7d,0x3f,0x01,0x67,
0x87,0x08,0xee,0x60]

である。 これを送ればsecretが見れる

'to get flag, just concat flag1 and flag2.' と帰ってくるので、 'cat secret\n flag1 flag2' と送れば良いことになる。 これはlength extension attack.

追加する文字列の長さを k = len(' flag1 flag2') とすれば additional_value = s2i(' flag1 flag2') として、

cipher_2 = pow(cipher,256 ** k,n ** 2) * pow(g,additional_value,n ** 2) % n ** 2

このcipher_2を送れば良いことが分かる

The flag is "7h053 wh0 bu1ld b3n347h 7h3 574r5 bu1ld 700 l0w."(without quote)

SECCON CTF 2013 全国大会 Druaga write-up

@misodengaku, @aki33524, @domitry と チーム Takedashi で出ていました、 17/20 位。

Druagaの2つ目のflagが取れなくて悔しかったので解いた。

1個目

80MB程の大き目のファイルがダウンロード出来る。 1日目の最後の方に問題がオープンされたので、ダウンロードしようとするも重くて誰もダウンロード出来ず。 何チームかダウンロード出来ていたらしい。

2日目はサクサクダウンロード出来た。なんのバイナリか悩んでたら @misodengakuが一瞬で解いてしまった。 聞いてみると"TrueCrypt"というヒントとそのパスが問題文に書いてあったらしい、全く見ていなかった…

中に ファイル名がflagのtxtと、tanka5t-50000.zipが入っていた。flagを投げて一つ目クリア

2個目

tanka5t-50000.zipを開くと50,000個のjpgが展開される、多すぎ。 全部アセンブラ短歌が書いてある。この中から実行すると"0609"と表示される短歌の画像のMD5がflag。 手では間に合わないのでOCRで短歌を読む事にした。

良さ気なOCRのコードを見つけるもののwinでは動かない、コンパイル大変などの理由で諦めて自力で書くことに。

実際に手に入るアセンブラ短歌はこんな感じ。

f:id:math314:20140303203518j:plain

他の画像も同じ位置に文字が書いてあるので、頑張れば自力で実装出来そうと考えた。

その場で書いたjpg->hex変換コードでは、"1文字の分に切り取った画像の黒いpixelの個数"を予め計算しておいて、完全に一致した場合その文字だと判定する方法を用いた。 しかしこの方法だと8割程度しか変換出来ず、精度にも問題があった。

そもそもアセンブラ短歌を実行出来る環境を作るのに手こずっていた、自分はwinしか持ってないので人に環境構築を任せるものの、短歌をdecodeした時点で時間もあまり残っておらず時間切れ。

リベンジ

家に帰ってちゃんと全部変換出来るプログラムを書いた。

"0" ~ "f"の画像を、それぞれ1つずつプログラムに与えておいて、画像から文字を読取る時に、"白黒が一致していないpixelの合計"が最も小さいものを採用するように。 横方向に1pixel位置がずれている場合があるみたい？なので、それにも対応。

zipから画像を全部読み取って、hexに変換してzipに詰め込むコードをc#で実装。 出来たzipをubuntuに持ってきて、短歌を実行出来るプログラムを作って全部試す。 2つ並列で1,2時間程回してたら答えが出てきた。 "3/93/73/taka.jpg" が答えのjpgっぽい。

flagは

929b66d3a90b804c1e3f7f2d7a084c19

書いたコード

tanka.csが、短歌画像が入ったzipを変換するプログラム、 1つのshellcodeを実行するプログラムはshellcode.c、 exe_shellcode.pyでこれを大量に回す。

反省

仮想環境でもいいので、みんなwindows,mac以外のOSも用意しましょう(チーム持ってきてる人はいた)。

余談

懇談会でDruagaについて聞いてみた。実はjpg圧縮にかなり工夫がされているとのこと、言われてみれば256 * 128のjpgなのに 1.1KBしかない、どう圧縮したんだ…

竹田氏

元々チーム名は"竹田氏"だったのだが、目立ちすぎるので"Takedashi"に変更になったそうな。

懇談会で幻の"竹田氏"画像を頂いた、ありがとうございます。

f:id:math314:20140303205923j:plain