読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

CTF for ビギナーズ Writeup & 参加記

ctf

CTF for ビギナーズに参加してきました。
解けない問題も多かったのですが運よく優勝しました。


Tシャツと本をいただきました。感謝

Writeup

Misc 100 Welcome

問題文のflagそのまんま

Misc 200 CountUp Game

21を言ってはいけないので常に4の倍数を言うようにすれば勝てる。
一度ミスすると相手は4の倍数をずっと言ってくるのでそこからでも推測できる。

Misc 200 てけいさん for ビギナーズ

計算結果を送信しようとするとindex.phpにPOSTされるので送信先php_math.phpに変更してから送信する。ただ、100回やらないといけないのでスクリプトを組んでやるべき。自分はスクリプトが書けず、問題名通り手計算しました。つらかった。。
渡された環境でやるならF12押して変えたいところをダブルクリックすれば送信先を変更できる。

Web 100 Classical Injection

ユーザ名に「' or 1 -- 」と入れればOK。単純なSQL Injection

Web 100 May the extensions be with you.

問題を忘れましたがCookieのfalseをtrueに変えるだけだった気がします。

Web 200 もぐもぐ(・~・)

シングルクォーテーションを入れるとエラーを吐くのでSQL Injectionだと当たりをつける。「' union select 1,1,1,1 -- 」などとするとカラム数は4つだとわかる。あとは講義でやったようにテーブル名、カラム名を取得し、怪しげなsecret_umasugiテーブルを出力するとflagが得られる。

Forensics 100 みつけてみよう

pcapファイルをWiresharkで開くとHTTP requestが20個あるので、一つ一つ中身をみてflagがあるか確認する。右下のStreamの値をいじれば楽。「tcp matches "ctf4b{(.)*(.)}"」だと一発らしい。

Forensices 200 あけてみよう

pcapファイルをWiresharkで開きHTTPでfilterをかけるとzipファイルを受け取っていることがわかる。File->Export Objects->HTTP...->Saveでzipファイルを保存できる。中には2.pcapがあり、Wiresharkで開くとFTP通信を行っていて、secret.zipを受け取っている。FTP-DATAでfilterをかけてFollow->TCP Streamとするとファイルの中身が表示されるのでShow data asをRawにしてから保存。unzipするとflagが得られる。

Binary 100 HiddenFlag

stringsするだけ

strings bin100_1 | grep ctf4b

Binary 200 復習

講義のようにコードを順に追っていく。どういうコードだったかは忘れました。

Binary 200 Unused Function

objdumpするといかにもな部分がある。
f:id:h_noson:20170130213754p:plain
0x63=c,0x74=t,0x66=fなのでこれですね。vimで開けば矩形選択できるのでいらない部分をそぎ落として次のコードを実行すればflagが得られます。

#include <stdio.h>

int main(void) {
  int c;
  while (scanf("%x",&c) != EOF) {
    printf("%c",c);
  }
  return 0;
}

問題名通りにいくとIDAで開いて条件分岐を操作するのだろうか。

最後に

自分が解けなかった問題を解いてる人が何人もいたのでほんとに運がよかった。
頂いた本を読んで勉強しようと思います。

Amazon Dash ButtonでAC数をカウントする

その他

巷で流行りのAmazon Dash Buttonで何かしようということで,競プロのAC数を数えてみたいと思います.

環境

ボタンが押されたことを検知

ボタンが押されたことを検知できないと何も始まらないのでまず検知を行う.
参考:Amazon Dash ButtonをただのIoTボタンとして使う - Qiita

  • Amazon Dash Buttonはボタンが押される度に,IPアドレスを取得するためDHCPサーバにリクエストを行っている
  • DHCPリクエストはブロードキャストで行われる
  • ほとんどのデバイスは,IPアドレスを受け取った後IPアドレスが重複していないか確認するため,ARPプローブを行う(これもブロードキャスト)

DHCPリクエストかARPプローブを監視すればボタンが押されたことを検知できる.
ほとんどの方がARPプローブの監視をしていたけど,自分の場合はARPプローブが行われずARPリクエストが2回行われていたため2回検知することを避けてDHCPリクエストを監視することにした.
scapyに関しては
Scapyで作る・解析するパケットUsage — Scapy v2.1.1-dev documentation
を参考にした.

DHCPリクエストはUDP port 67なので

sniff(filter="udp port 67", prn=lambda x: x.show())

を実行した状態でボタンを押すと以下のようにMACアドレスがわかる.

###[ Ethernet ]###
  dst= ff:ff:ff:ff:ff:ff
  src= xx:xx:xx:xx:xx:xx
  type= 0x800
###[ IP ]###
....

これでMACアドレスによるfilterも行える.

sniff(filter="ether src xx:xx:xx:xx:xx:xx and udp port 67", prn=count)

パケットを受け取った際にprnに設定した関数が呼ばれるので,そこでカウントが行えるようにした.このプログラムではjsonを読み込んでその日のAC数をインクリメントしている.

from scapy.all import sniff
import json
import time
from datetime import date,timedelta,datetime

def count(_):
    try:
        with open("ACcount.json", "r") as fp:
            data = json.load(fp)
    except IOError:
        data = json.loads('{}');

    d = date.today()
    year = str(d.year)
    month = str(d.month)
    day = str(d.day)
    if not year in data:
        data.update({year:{month:{day:0}}})
    elif not month in data[year]:
        data[year].update({month:{day:0}})
    elif not day in data[year][month]:
        data[year][month].update({day:0})
    data[year][month][day] += 1

    print "AC!" + " (" + str(time.ctime()) + ")"
    print "today's AC: " + str(data[year][month][day])
    with open("ACcount.json", "w") as fp:
        json.dump(data, fp)

sniff(filter="ether src xx:xx:xx:xx:xx:xx and udp port 67", prn=count)

これでAC数を数えることができるようになった.

数えただけだとつまらないので一日のAC数をtweetさせてみようと思う.先ほど作ったjsonファイルを読み込んでその内容を23:59にtweetするように調整した.

from requests_oauthlib import OAuth1Session
from datetime import date,timedelta,datetime
import json
import time
import sched

CK = 'XXXXXXXXXXXXXXXXXXXXXXXXX'                          # Consumer Key
CS = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' # Consumer Secret
AT = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' # Access Token
AS = 'XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX'      # Access Token Secret
twitter = OAuth1Session(CK,CS,AT,AS)

def get_msg_for_day(data):
    d = date.today()
    year = str(d.year)
    month = str(d.month)
    day = str(d.day)
    if year in data and month in data[year] and day in data[year][month]:
        return u"今日のAC数: " + str(data[year][month][day])
    else:
        return ""

def get_msg_for_month(data):
    d = date.today()
    nd = date.today() + timedelta(days=1)
    if d.month == nd.month: return ""
    year = str(d.year)
    month = str(d.month)
    if year in data and month in data[year]:
        sm = 0
        for day in data[year][month]:
            sm += data[year][month][day]
        return u"今月のAC数: " + str(sm)
    else:
        return ""

def get_msg_for_year(data):
    d = date.today()
    nd = date.today() + timedelta(days=1)
    if d.year == nd.year: return ""
    year = str(d.year)
    if year in data:
        sm = 0
        for month in data[year]:
            for day in data[year][month]:
                sm += data[year][month][day]
        return u"今年のAC数: " + str(sm)
    else:
        return ""

def get_msg():
    try:
        with open("ACcount.json","r") as fp:
            data = json.load(fp)
    except IOError:
        data = json.loads("{}")
    msgs = []
    msgs.append(get_msg_for_day(data))
    msgs.append(get_msg_for_month(data))
    msgs.append(get_msg_for_year(data))
    return '\n'.join(filter(lambda s: s != "",msgs))

def tweet():
    message = get_msg()
    if message == "":
        print("no AC")
    else:
        print("Sending message...")
        print(message)
        url = "https://api.twitter.com/1.1/statuses/update.json"
        params = {'status': message}
        res = twitter.post(url, params = params)
        if res.status_code == 200:
            print("OK")
        else:
            print("Error: %d" % res.status_code)
    add_event()

def add_event():
    d = datetime.today()
    nextd = datetime(d.year,d.month,d.day) + timedelta(days=1) - timedelta(seconds=30)
    print("supposed to tweet at " + str(nextd))
    s.enter((nextd-d).total_seconds(),1,tweet,())

print("Twitter client is running")
s = sched.scheduler(time.time,time.sleep)
add_event()
s.run()

面倒な点

  • ACする度にボタンを押さないといけない
  • tweetするときにノートPCを開いておく必要がある(サーバがほしい)

AC数をカウントすることで今後のモチベーションにつながることを期待してる

yukicoder No.429 CupShuffle

yukicoder

問題

No.429 CupShuffle - yukicoder
N個のコップについて交換の仕方・最終配置が与えられる.ただし,X回目の交換の仕方の情報が抜けている.どのコップを交換したかを求める問題.

解法

解説を見るとX-1回目までswapを行い,一方K回目からX+1回目まで逆順でswapを行って,その差を求める,という解法だった.しかし逆方向からswapを行う必要はなく,X回目を飛ばして最後までswapを行って最終配置と比較する.このとき間違っているコップは2つだけのはずなので,X回目での配置を覚えておけばどこを交換すべきだったかが求められる.

ソースコード

[n,k,x] = map(int,input().split(' '))
x -= 1
s = [i for i in range(1,n+1)]
for i in range(k):
    if i == x:
        input()
        tmp = s[:]
        continue
    [a,b] = map(int,input().split(' '))
    a -= 1
    b -= 1
    s[a],s[b] = s[b],s[a]
c = list(map(int,input().split(' ')))
t = [s[i] for i in range(n) if s[i] != c[i]]
for i in range(n):
    if tmp[i] in t:
        print(i+1,end=' ')
print("")

最近pythonを使い始めたけど,c++より全然書きやすい

CODE FESTIVAL 2016 qual B E - Lexicographical disorder

atcoder トライ木

問題

E: Lexicographical disorder - CODE FESTIVAL 2016 qual B | AtCoder
N個の文字列Siが与えられる.以下のクエリにQ回答える問題
整数kと{'a',...,'z'}を並び替えたp1,...,p26が与えられる.文字の順序がp1<p2<...<p26の時SkはN個の文字列の中で何番目か

解法

Skより小さい文字列の数を高速に求めたい.トライ木を構成して各ノードで文字列の数を覚えておけばいいことがわかる.しかし,とても長い文字列が来ることがあるのでトライ木では間に合わない.トライ木のノードを圧縮して得られるパトリシア木を使うことで無駄な探索がなくなる.
パトリシア木の解説は気が向いたら+もっと綺麗にかけるようになったら...

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

struct Patricia {
    int num;
    bool end;
    string str;
    vector<Patricia*> children;
    Patricia() {}
    Patricia(string s) : str(s), num(1), end(true) {}
};

Patricia root;

void add(string s) {
    Patricia* node = &root;
    bool down = true;
    while (down && s.size() > 0) {
        down = false;
        for (auto ch: node->children) {
            if (ch->str[0] == s[0]) {
                int i;
                for (i = 0; i < min(ch->str.size(),s.size()) && ch->str[i] == s[i]; i++);
                if (i < ch->str.size()) {
                    Patricia* nnode = new Patricia(ch->str.substr(0,i));
                    nnode->children.push_back(ch);
                    nnode->num = ch->num+1;
                    nnode->end = false;
                    node->children.erase(find(node->children.begin(),node->children.end(),ch));
                    node->children.push_back(nnode);
                    ch->str.erase(0,i);
                    if (i == s.size()) {
                        nnode->end = true;
                    }
                    node = nnode;
                }
                else {
                    ch->num++;
                    if (i == s.size()) {
                        ch->end = true;
                    }
                    node = ch;
                }
                s.erase(0,i);
                down = true;
                break;
            }
        }
        if (!down) node->children.push_back(new Patricia(s));
    }
}

int pri[26];

int query(string s) {
    Patricia* node = &root;
    int ret = 0;
    while (s.size()) {
        Patricia* nxt;
        for (auto ch: node->children) {
            if (ch->str[0] == s[0]) {
                ret += ch->end;
                nxt = ch;
            }
            else if (pri[ch->str[0]-'a'] < pri[s[0]-'a']) {
                ret += ch->num;
            }
        }
        s.erase(0,nxt->str.size());
        node = nxt;
    }
    return ret;
}

string str[100000];

int main(void) {
    int i, n;
    scanf("%d\n",&n);
    REP (i,n) {
        char c;
        while (scanf("%c",&c), c != '\n') str[i] += c;
        add(str[i]);
    }
    int q;
    scanf("%d",&q);
    while (q--) {
        int k;
        scanf("%d ",&k);
        k--;
        char c;
        REP (i,26) {
            scanf("%c",&c);
            pri[c-'a'] = i;
        }
        printf("%d\n",query(str[k]));
    }
    return 0;
}

yukicoder No.416 旅行会社

yukicoder Union-Find

問題

No.416 旅行会社 - yukicoder
N個の点とM本の辺が与えられ,CiとDiの間の辺を壊すというクエリがQ個与えられる.それぞれの点は何回目のクエリで点1から到達できなくなるか答える問題.

解法

辺を繋いで(この問題では壊して)ある点から到達できるかを求めたいので,UnionFindが使えることがわかる.まず,最後まで破壊されない辺を結合させる.そしてクエリを逆から読んで辺を繋いでいき初めて点1に到達できたときが,この問題でいうと点1から到達できなくなるときになる.点1を含む集合と結合したときに点1に到達できた点を列挙したいのだが,単純にvectorなどで集合を管理しているとマージするときに最悪O(n)必要で,全体の計算量がO(n^2)になってしまう.一般的なマージテクを使うとO(nlogn)に抑えられるらしいのだが(小さい方の集合を大きい方の集合に足す,というやり方なのだろうか),ここでは木をマージさせていくことでO(n)に抑えた.UnionFindでは親への辺を張り替えていくことで集合の結合を行っている.このとき同時に親から子への辺を繋ぐことでどの点が親に繋がっているか管理できる.

ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

int par[200000], ans[200000];
vector<int> child[200000];

int find(int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
}

void dfs(int x, int event) {
    ans[x] = event;
    for (auto y: child[x]) dfs(y,event);
}

void unite(int x, int y, int event) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (x == 0) {
        dfs(y,event);
        par[y] = x;
    }
    else if (y == 0) {
        dfs(x,event);
        par[x] = y;
    }
    else {
        par[x] = y;
        child[y].push_back(x);
    }
}

vector<int> e[200000];
set<int> del[200000];
int C[200000], D[200000];

int main(void) {
    int i, n, m, q;
    scanf("%d%d%d",&n,&m,&q);
    REP (i,m) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--; b--;
        e[a].push_back(b);
    }
    REP (i,q) {
        scanf("%d%d",&C[i],&D[i]);
        C[i]--; D[i]--;
        del[C[i]].insert(D[i]);
    }

    REP (i,n) par[i] = i;

    REP (i,n) for (auto x: e[i]) if (!del[i].count(x)) {
        unite(i,x,-1);
    }
    RREP (i,q) {
        unite(C[i],D[i],i+1);
    }
    REP (i,1,n-1) printf("%d\n",ans[i]);
    return 0;
}

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset

codeforces トライ木 二分探索

問題

Problem - D - Codeforces
3つのクエリに答える.
1. xをmultiset Aに加える
2. xをmultiset Aから取り除く
3. \displaystyle{\max_{y\in A}}(x\oplus y)を出力する

解法1

c++のmultisetを使って二分探索をする.
xorをとった値が大きくなるように上位のbitから0か1か決めていけばいい.xを反転したものがAに含まれていればいいのだが,あるとは限らないので上位のbitからそのbitが1(または0)である値が存在するかどうかをlower_boundを使って調べる.見つかればその後はそのbitはその値に固定して探索を行う.見つからなければ,そのbitは妥協して次のbitに移る.計算量はO(Q\log Q\log X_{max}).
実装しているときに<algorithm>で定義されているlower_boundをsetで使うとO(N)かかってしまうことを知った.

解法2

考え方は解法1と同じなのだがトライ木を使ってO(Q\log X_{max})に抑える.トライ木のノードには1文字格納されており,根から葉までたどることで文字列を高速に検索できる.整数も01の文字列とみなせるのでトライ木を使うことができる.さらに今回は上位bitから探索を行いため非常に相性がいい.あるbitが1(または0)の値が含まれているかはその方向に枝が存在するか確認するだけなので先ほどの解法よりも計算量を抑えられる.

ソースコード1

#include <iostream>
#include <set>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

int main(void) {
    int q;
    scanf("%d",&q);
    multiset<unsigned int> st {0};
    while (q--) {
        char op;
        int x;
        scanf("\n%c %d",&op,&x);
        if (op == '+') st.insert(x);
        else if (op == '-') st.erase(st.find(x));
        else {
            int i;
            unsigned int l = 0, r = 1U<<31;
            RREP (i,30,0) {
                if (x & 1<<i) {
                    auto p = st.lower_bound(l);
                    if (*p < (l|1<<i))
                        r = l | 1 << i;
                    else
                        l = l | 1 << i;
                }
                else {
                    auto p = st.lower_bound(l|1<<i);
                    if (p != st.end() && *p < r)
                        l = l | 1 << i;
                    else
                        r = l | 1 << i;
                }
            }
            printf("%d\n",x^l);
        }
    }
    return 0;
}

ソースコード2

#include <iostream>
#include <set>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)

struct Trie {
    int num;
    struct Trie* parent;
    struct Trie* child[2];
};

struct Trie root;

void add(int val) {
    int i;
    struct Trie* node = &root;
    RREP (i,31) {
        int next = val>>i&1;
        if (node->child[next] == NULL) {
            node->child[next] = new Trie();
            node->child[next]->parent = node;
        }
        node = node->child[next];
    }
    node->num++;
}

void remove(int val) {
    int i;
    struct Trie* node = &root;
    RREP (i,31) {
        node = node->child[val>>i&1];
    }
    if (--node->num) return;
    bool end = false;
    while (node != &root && !end) {
        struct Trie* p = node->parent;
        REP (i,2) {
            if (p->child[i] == NULL || p->child[i] == node) p->child[i] = NULL;
            else end = true;
        }
        delete(node);
        node = p;
    }
}

int query(int val) {
    int i, ret = 0;
    struct Trie* node = &root;
    RREP (i,31) {
        int next = 1 - (val>>i&1);
        if (node->child[next] != NULL) {
            node = node->child[next];
            ret = ret * 2 + next;
        }
        else {
            node = node->child[1-next];
            ret = ret * 2 + 1 - next;
        }
    }
    return ret;
}

int main(void) {
    int q;
    scanf("%d\n",&q);
    add(0);
    while (q--) {
        char op;
        int x;
        scanf("%c %d\n",&op,&x);
        if (op == '+') add(x);
        else if (op == '-') remove(x);
        else printf("%d\n",x^query(x));
    }
    return 0;
}

Codeforces Round #365 (Div. 2) C. Chris and Road

codeforces 幾何

問題

Problem - C - Codeforces
N角形のバスがやってくる.幅Wの道路をバスにぶつからずに渡るとき,最短の渡る時間を求める問題

解法

バスを固定すると人が右上に向かって移動することと等しくなる.もしぶつからずにそのまま行けるのであればそのまま行く,そうでなければスタート地点を後ろにずらしていき直線がバスに接するようにすればいい.
移動後の直線をy=U/V*x-bとすると,すべての点に対してb=\max(b,U/V*x-y)を求めればよくなる.下図の緑の直線の場合,待つ必要はなくなる.
f:id:h_noson:20160805150303p:plain

ソースコード

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)

int main(void) {
    int i, N, W;
    double V, U;
    cin >> N >> W >> V >> U;
    double x = 0;
    bool go = true;
    REP (i,N) {
        int X, Y;
        cin >> X >> Y;
        x = max(x,U/V*X-Y);
        if (X / V < Y / U) go = false;
    }

    if (go) x = 0;
    cout << fixed << setprecision(7);
    cout << (W + x) / U << endl;
    return 0;
}