math314のブログ

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

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

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

期待値と条件付確率

前置き

これは、Competitive Programming Advent Calendar Div2013, 第 13 日の記事です。

みんな大好き期待値の問題の基礎について確率変数を使わない縛りで書きたいと思います。

1,2は非常に簡単な内容となっているので読み飛ばしても構いません。

続きを読む