math314のブログ

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

最近開催された大会

  • ICPC アジア地区予選 日本地区 2014
    • チーム kyutOUki で出ていました．11位でした．入賞だそうです．
  • CODE FESTIVAL2014
    • 21位でした，賞金が20位からだったので悔しかった．
    • しかしアジア決勝(!?)に出場できるとの事なので，そこで賞金を得たい．
    • Tシャツ2枚，パーカーを貰いました
  • CODE RUNNER 2014
    • 8位でした． 初の賞金だったので嬉しかったのですが，交通費の関係で赤字になりました．
    • もう少し戦略を練れば3位は取れていたので，次回があれば3位以上を目指したい．
    • Tシャツ，パーカーを貰いました

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)