HITCON CTF 2014 Write-up - kusano-k’s blog

HITCON CTF 2014にチームfuzzi3で参加した。総勢24人。結果は1位。以下、私が解いた問題。

mid (ACM) 250点

ジャンルがACMで、まさにいわゆる競技プログラングの問題。整数nとn個の整数A₀, A₁, …, A_n-1が与えられ、Aの中央値を答える。nは1<=n<1000000を満たす奇数、A_iは符号付き64bit整数。実行時間制限は16秒、メモリ制限は4MB。
選択アルゴリズムをk=n/2として用いれば良い。単純にソートしてO(n log n)、頑張るとO(n)。簡単な問題かと思いきや、メモリの制限が厳しい。Aを全て配列に格納するには8MBのメモリが必要。
まあ、Aが一様ランダムに分布しているのならば、中央値は0付近になるはずで、abs(A_i)<=0x2000000000000000LLとなるA_iだけ真面目に記録しておいて、他はこの範囲の下か上かだけ覚えておけば良い。

Executing...
  ...Correct!
All correct! Here's your flag: HITCON{7hiS_1s_1soL4te_8rEaK}

HITCON{7hiS_1s_1soL4te_8rEaK}

終了。かと思いきや、しばらく後になぜか正解していない扱いになってしまった。

2014-08-16 18:47:10 UTC: Flag of mid updated
Since the judge server has some bug, the flag may be capture in wrong way.
We have change the flag. Please resubmit your source code to get the new one.

なるほど。ずるいことをする人もいるものだ。でもCTFの問題って普通はチートして解くものだし、正解扱いで良いのでは？とか思いながら再投稿。

HITCON{7hiSeS_aR1_Eso14tE_raK8r}

これが28時くらいだったので寝ようとしたところで、また正解が無効になる。

2014-08-16 19:02:57 UTC: Memory limit of 'mid' has changed.
The origin limit is too easy (and boring) so it becomes harder.

問題を見てみたらメモリ制限が2MBになっていた。まあ、保存しておく値の範囲を適当に変えれば良いよねと、abs(A_i)<=0x0800000000000000LLにしたら通った。

HITCON{W1_Ar_S0rry_7hiSeS_Ar1_1so14te_rAkB2_aGn}

朝起きたら、またまた正解が無効にされていた。

2014-08-16 19:23:57 UTC: Last update of mid
This is the last time. Sorry for the inconvenience. We will not change judge or test cases anymore.

We promise that this time is the last update
Since the test cases are too weak, we enhanced them and rejudge

@winesap | ytoku: You're right. We want 'mid' be a CTF challange, not ACM problem.

（CTF的に）ずるをしていたのは私のほうだったらしいw
問題にヒントが追加されていた。

You need to STEAL MORE MEMORY, but how? where?

運営としてはメモリの制限を回避してほしいらしい。最初は不正解と出てくるだけだったけど、途中から実行時間が出るようになった。これを使うと情報が得られる。例えば

if (n%2==0)
    while (clock()/CLOCKS_PER_SEC<1)
        ;
else
    while (clock()/CLOCKS_PER_SEC<2)
        ;

とすると、実行時間が1秒か2秒かでnが偶数か奇数かが分かる。これを使って調べると、

テストケースは固定ではない
1個目のテストケースは符号付き64bit整数の中でランダム
2個目のテストケースは狭い範囲でランダム、この範囲も毎回変わる

ということが分かった。
保存する値の範囲を動的に変化させるようにしたら通った。結局正攻法では解いていない。今回は正解のままだった。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int comp(const void *a, const void *b)
{
    if (*(long long *)a < *(long long *)b)
        return -1;
    else if (*(long long *)a > *(long long *)b)
        return 1;
    else
        return 0;
}

#define N 100000

int main()
{
    int n, i, j, vn, ln, hn, p, limit;
    static long long v[N];
    long long t;

    scanf("%d", &n);

    long long low  = -0x0100000000000000LL;
    long long high = +0x0100000000000000LL;

    vn = ln = hn = 0;
    
    for (i=0; i<n; i++)
    {
        scanf("%lld", &t);

        if (t<low)
            ln++;
        else if (t>high)
            hn++;
        else
            v[vn++] = t;

        if (vn==N)
        {
            qsort(v, vn, sizeof (long long), comp);
            low = v[vn/4];
            high = v[vn*3/4];

            ln += vn/4;
            hn += vn - vn*3/4 - 1;

            p = 0;
            for (j=vn/4; j<=vn*3/4; j++)
                v[p++] = v[j];

            vn = vn*3/4 - vn/4 + 1;
        }
    }

    if (ln<=n/2 && n/2<ln+vn)
    {
        qsort(v, vn, sizeof (long long), comp);
        printf("%lld\n", v[n/2-ln]);
    }
    else
    {
        if (!(ln<=n/2))
            limit = 14;
        else if (!(n/2<ln+vn))
            limit = 15;
    
        while (clock()/CLOCKS_PER_SEC<limit)
            ;
    }
}

HITCON{S_Ar4t1_Ar_S1_1so10rAkB2_rry_7hiSee_aGn}

hop (Reverse) 350点

入力した文字列が正解かどうかを判定する64bit exeの解析。このデバッガが使いやすかった。文字列長は40文字で、入力文字列と0x00をスタックに積んだあと、

00000000004591C0 | 58                       | pop rax                                 |
00000000004591C1 | 48 69 C0 C2 21 00 00     | imul rax,rax,21C2                       |
00000000004591C8 | 8B 84 02 1C 01 00 00     | mov eax,dword ptr ds:[rdx+rax+11C]      |
00000000004591CF | 48 98                    | cdqe                                    |
00000000004591D1 | 48 01 C2                 | add rdx,rax                             |
00000000004591D4 | FF E2                    | jmp rdx                                 |

このようなコードを実行していく。こころぴょんぴょん。答えに辿り着く経路を探索すれば良い。最短経路ではなくちょうど40回で答えに辿り着かないといけない。

# coding: utf-8

import struct

D = open("hop-62fa7ade9a1fa9254361e69d70e7a7e3.exe", "rb").read()
def read(p):
    return struct.unpack("<i", D[p:p+4])[0]

offset = 0x44f491-0x4e891
start  = 0x44f491-offset
goal   = 0x4015b9-offset

E = [{start: {}}]   # 順方向
R = [{}]            # 逆方向

for i in range(41):
    E += [{}]
    R += [{}]
    for p in E[i]:
        m = read(p+4)
        a = read(p+11)
        for c in range(0x20, 0x7f) if i<40 else [0]:
            t = p+read(p+m*c+a)
            E[i][p][c] = t
            E[i+1][t] = {}
            R[i+1][t] = (p, c)

p = goal
flag = ""
for i in range(41)[::-1]:
    t = R[i+1][p]
    p = t[0]
    flag += chr(t[1])
print flag[::-1]

C:\documents\ctf\hitcon2014\hop>.\hop-62fa7ade9a1fa9254361e69d70e7a7e3.exe
Key: HITCON{Cap7ur3 Wh1t3 F1ag 0f Us@ 5hr1n3}
Correct!

HITCON{Cap7ur3 Wh1t3 F1ag 0f Us@ 5hr1n3}