ICPC 国内予選 2014
チーム kyutOUki(@__math, @mitaki28, @ustimaw) で出ていました． 6完，6位 でした．
続きを読む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では動かない、コンパイル大変などの理由で諦めて自力で書くことに。
実際に手に入るアセンブラ短歌はこんな感じ。
他の画像も同じ位置に文字が書いてあるので、頑張れば自力で実装出来そうと考えた。
その場で書いた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"に変更になったそうな。
懇談会で幻の"竹田氏"画像を頂いた、ありがとうございます。
ICPC Asia 2013 Problem G: Longest Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1341
通りませんでした、辛い
2014/01/05 00:22 通りました
投げたコード(AC)
O((m+n) log (m+n))?
#include <map> #include <iostream> #include <vector> #include <algorithm> using namespace std; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) int m, n, a, b; struct P { int x, y, z; P() {} P(int x, int y, int z) : x(x), y(y), z(z) {} bool operator< (const P& l) const { if (x != l.x) return x < l.x; if (y != l.y) return y > l.y; return z > l.z; } }; int r() { const int C = ~(1 << 31), M = (1 << 16) - 1; a = 36969 * (a & M) + (a >> 16); b = 18000 * (b & M) + (b >> 16); return (C & ((a << 16) + b)) % 1000000; } bool C(map<int, P>& polyline, const P& p) { map<int, P>::iterator it = polyline.lower_bound(p.y); if (it == polyline.begin()) return true; it--; return it->second.z >= p.z; } void insert_polyline(vector<map<int, P> >& polyline, const P& p) { int l = -1, r = sz(polyline); while (r - l != 1) { int md = (l + r) / 2; bool ok = C(polyline[md], p); if (ok) r = md; else l = md; } if (sz(polyline) == r) polyline.emplace_back(); if (polyline[r].find(p.y) != polyline[r].end() && polyline[r][p.y].z <= p.z) return; polyline[r][p.y] = p; map<int, P>::iterator it = polyline[r].find(p.y); ++it; while (it != polyline[r].end()) { if (it->second.z < p.z) break; polyline[r].erase(it++); } } int main() { int cnt = 0; while (cin >> m >> n >> a >> b, m || n || a || b) { cnt++; vector<P> v; FOR(i, m) { int x, y, z; cin >> x >> y >> z; v.emplace_back(x, y, z); } FOR(i, n) { int x = r(); int y = r(); int z = r(); v.emplace_back(x, y, z); } sort(v.begin(), v.end()); vector<map<int, P> > polyline; FOR(i, sz(v)) { insert_polyline(polyline, v[i]); } cout << sz(polyline) << "\n"; } return 0; }
追記
入出力が公式から公開されていました http://sparth.u-aizu.ac.jp/icpc2013/r_overview.php
