task4233のめも

書きたいことをつらつらと

CyberRebeatCTF - WriteUp

参加記録 CTF
もくじ

問題リンク(ログインしてください)

https://cyberrebeat.adctf.online/en/contests/2/problems

はじめに

この記事では、今回の参加記録および解けた問題の簡単な解説が書かれています。

上に目次があるのでご活用ください。  

結果

1677点で72位でした。

結果(Binary〜Programming)

Binary Crypto Exercise Misc Programming
0/3 1/3 1/1 1/2 2/3

f:id:task4233:20180909160921p:plain

結果(Recon〜Web)

Recon Stegano Trivia Web
2/3 1/3 2/2 2/3

f:id:task4233:20180909160925p:plain

解説

Crypto

Rotation

問題文からシーザー暗号らしきことがわかります。

しかし、単純にずらすだけでは先頭の文字列がCRCTFではありません。

数字の部分だけずらしてCRCTFにすればFLAGを得られます。

Excercise

やるだけです。

Misc

Readme

f:id:task4233:20180909163600j:plain

最初の文がCAN YOU READ JAPANESE?と読めます。

したがって、それに従い最後の文を訳せばFLAGを得られます。

Programming

Calculation

提示されたコマンドを叩くと四則演算の問題が出てきます。

それを単純に解いて答えていけばFLAGを得られます。

Prime Factor

提示されたコマンドを叩くと問題が与えられます。

問題の内容は数字を素因数分解して最大の素因数を返すというものです。

エラストテネスの篩を用いて素因数分解分解してmaxを返す関数を作れば良いです。

単純に解いていけばFLAGを得られます。

Recon

Tweet

Twitterのアカウントを見ると以下のツイートからFLAGを得られます。

CyberRebeatScripts

GitHubのhistoryから差分を見るとFLAGを得られます。

github.com

Stego

Secret.pdf

与えられたpdfを確認して、文字列をコピーするとFLAGを得られます。 f:id:task4233:20180909170145p:plain

Trivia

Monero

Monero関係の事件を調べれば問題が答えがすぐに得られました。

xn--eck3a9bu7culw30roe4arcdo69l1ja456a.xyz

Crossword

問題を解くだけです。 ググれば解けます。 調べている途中で答えが予測できたので、それをFLAGとして提出しました。

f:id:task4233:20180909171103j:plain

Web

White Page

hidden要素を消してログインすればFLAGが得られました。

f:id:task4233:20180909171418p:plain

Let's Tweet

投稿してリンクをPOSTするとFLAGが得られる。

感想

初の常設でないCTFでした。

簡単な問題は大分解けた気がします。

ProgrammingのVisual Novelsは手入力で解けたらしいので、もう少し粘っていれば解けたのかも。残念。

Binaryはほとんど解けなかったので、他の方のWriteUpを見てしっかりと復習します。

ABC109 - 参加記録

参加記録 競プロ AtCoder
もくじ

問題リンク

Tasks - AtCoder Beginner Contest 109

はじめに

この記事では、今回の参加記録およびABC109の問題・解説が書かれています。

上にもくじがあるので、ご活用ください。

結果

全完で57位でした。

f:id:task4233:20180909115202p:plain

なぜかエスパーで解法が降ってきたので速く解けたのだと思います。

以下、各問題と解説です。

A - ABC333

問題

1以上3以下の整数A, Bについて、A \times B \times Cが奇数となるような1以上3以下の整数Cが存在するか判定せよ。

制約

  • 入力は全て整数

  • 1 ≦ A, B ≦ 3

解説

以前のABCでも似たような問題が出ていました。
(問題名を忘れました。申し訳ないです。)

積が奇数となるのはかけられる数が全て奇数の時なので、
A, Bが共に奇数の時に「Yes」それ以外の時に「No」を出力すれば良いですね。

提出コード

Submission #3151300 - AtCoder Beginner Contest 109

B - Shiritori

問題

N個の単語について、以下のルールを満たしている時に「Yes」を、そうでない時に「No」を出力せよ。

ルール

  • 同じ言葉を2回以上使っていないこと。

  • 1つ前の最後の文字と今発言する最初の文字が同じであること。

制約

  • 2 ≦ N ≦ 100

  • w_{i}は英小文字からなる1以上10以下の長さの文字列である。

解説

制約からN2でも問題なさそうなので、ルールを守っているかを愚直に確認すれば良いですね。

提出コード

Submission #3152586 - AtCoder Beginner Contest 109

C - Skip

問題

数直線上にあるN個の都市があり、 i番目の都市は座標x_{i}にある。

あなたはある整数Dを設定すると以下の移動が行える。

  • 1: 座標yから座標y + Dに移動する

  • 2: 座標yから座標y - Dに移動する

ここで、あなたが座標Xから出発した時の全ての都市を回れるDの最大値を求めよ。

解説

この問題はごちゃごちゃしていますが、
重要なのは「座標yから座標y ± Dにのみ移動出来る」ということですね。

例えば、1と5という座標があったとき、

この時のDの最大値は4ですね。

この例を観察すると「4」という数字について、
「5 ≡ 1 (mod 4)」すなわち「5 % 4 == 1 % 4」という性質があり、
「座標間の距離についてDを法として合同(mod D)」であることが分かります。

この問題ではDの最大値を求めるため、
各点との距離の最大公約数を求めれば「座標間の距離についてDを法として合同(mod D)」を満たし、かつ最大のDを求められますね。

したがって、各点間の距離のgcd(最大公約数)を取れば良いです。

余談ですが、RADの最大公約数って曲いいですよね。

提出コード

Submission #3153766 - AtCoder Beginner Contest 109

D - Make Them Even

問題

H \times Wのマス目について、マス(i, j)にa_{i,j}枚のコインが置かれている。

以下の操作を何度でも行える時、偶数枚のコインが置かれたマスの数を最大化せよ。

操作

  • 選んだことのないマスのコインを1枚選び、そのマスの上下左右のマス1つに移動する

制約

  • 入力は全て整数

  • 1 ≦ H, W ≦ 500

  • 0 ≦ a_{i, j} ≦ 9

解説

各マスの数をmod 2で考えれば良いです。

言い換えれば、2進数の最下位の数にのみ注目すれば良いです。

なぜなら、下2桁以上はどのような数であろうと必ず偶数になるからです。

したがって、全てのマスを% 2で置き換えて以下のように操作すれば良いでしょう。

  • (見たマスの枚数 % 2) が「1」である。

    • 見たマスが右下の端である(座標が(H, W)のとき)。

      • スルー。

    • 見たマスが右端である(座標が(*, W)のとき)。

      • そのマスのコインを下に移動し、下のマスの枚数を+1する。

    • それ以外

      • そのマスのコインを右に移動し、右のマスの枚数を+1する。

  • (見たマスの枚数 % 2)が「0」である。

    • スルー。

ジグザグ解いているContestantもいましたが、そちらの方が良いんでしょうかね？

提出コード

Submission #3156056 - AtCoder Beginner Contest 109

感想

今回は上手くいったので満足しています。

次回のAGCもうまいこと行くと良いな。

それと現在開催中のCRCTFですが、全完チームはやはり凄いなぁという気持ちです。

ハリネズミ本を買おうかどうか悩んでいるのですが、毎回Amazonカードを買うのを忘れて帰宅してしまうんですよね。

ARC102 - 参加記録

参加記録 AtCoder 競プロ
もくじ

問題リンク

Tasks - AtCoder Regular Contest 102

はじめに

結果

今回は1完で594位だった。

f:id:task4233:20180902102249p:plain

1完を目的としていたので、それは達成できて良かった。

あと2分速く解けていれば水色パフォだった……

C - Triangular Relationship

問題

問題リンク →　

C - Triangular Relationship

考察と解法

a + b, b + c, c + aが全てKの倍数であることから、
(a + b) % K=(b + c) % K=(c + a) % K = 0 - (1) がわかる。

さらに、aを固定すると、
(a + b) % K = 0 より b % K = (K - a) % K. - (2)
(c + a) % K = 0 より c % KK = (K - a) % K. - (3)

(1), (2), (3)より、
(b + c) % K = (((K - a) % K) \times 2) % K) = 0
を満たしていればa + b, b + c, c + aが全てKの倍数であることを満たす。

そして、(2),(3)を満たすようなb, cは余りが (K - a) % Kとなるものなので、その個数はそれぞれ (N + K + a) / Kである。

最後に、aを1からNまで回すと答えが導出できる。

以下、提出コード。

Submission #3116072 - AtCoder Regular Contest 102

D - All Your Paths are Different Lengths

問題

問題リンク →　

D - All Your Paths are Different Lengths

考察

頂点数がN≦20, L≦ 106 であるから220 が関連していそうなことは見通しがついた。

ただし、実際にグラフを作ってみると、この解法だと頂点数が21無ければならず、辺の数が足りないことに気づく。

さらに、大きい方の重みから作っていけば辺の数を減らしていくことができそうだが、明らかに足りないことにも気づく。

ここでARC終了。

感想

1完できて良かったが、Cはもう少し速く解ければ良かったかな……

Dもただ重みをつけるだけでなく、重みのつけかたを工夫する必要があった。

逆に言えばもう少しでACできそうだったので、次こそDを解きたい。

ABC106 - 参加記録

参加記録 競プロ AtCoder
もくじ

問題リンク

Tasks - AtCoder Beginner Contest 106

はじめに

この記事では、各問題の考えの流れが大まかに書かれている。 後述するが、3完だったためD問題のみ少し深めに書いた。

問題へのリンクは上の目次等を活用してほしい。

結果

今回は3完2WAで788位だった。

f:id:task4233:20180819112825p:plain

最近のコンテストはダメダメなので、悲しくなってくる。

それはさておき、改めて問題を見直してみると双子コンとしてはそこまで邪悪でなかったように感じた。

このコンテストは全完したかった……

問題

A - Garden

算数の問題。
(A - 1) * (B - 1) で、解が求められる。

ちなみに、灰色の部分の面積は
A * B - (A - 1) * (B - 1) と書くとバグが少なそう。

B - 105

「N以下の奇数oに対して、約数をちょうど8つ持つoの数を求めよ」という問題。

「奇数oが約数をちょうど8つ持つこと」は、
「\sqrt{o}以下に、oを割り切れる数がちょうど4つ存在すること」と同義である。

したがって、oという奇数をforループで回し、
\sqrt{o}までで割り切れる数を数えるために更にforループで回すので、
O(N\sqrt{N})で解くことができた。

C - To Infinity

問題を見て、非常に大きな回数だけ変化することから、 K文字目までに1があるか否かを判定すれば良いということはすぐにわかった。

ただし、K文字目までを探索範囲にしてしまうと範囲外アクセスをしかねないので、右端の要素はstd::max(K, S.size())とした。

D - AtCoder Express 2

ACできなかった問題。
少し詳しめに書く。

問題文

N個の都市とM本の電車が存在している。
M本の電車のうちの電車iはL_iからR_iの閉区間を走っている。
ここで、都市番号pと都市番号qが与えられた時、走る区間が完全に含まれる列車の本数、
言い換えればp_i ≦ L_jかつR_j≦q_iが成立するような列車の本数について、Q個の質問にそれぞれ答えよ。

制約

  • 1 ≦ N ≦ 5 \times 102
  • 1 ≦ M ≦ 2 \times 105
  • 1 ≦ Q ≦ 1 \times 105
  • 1 ≦ L_i ≦ R_i ≦ N (1 ≦ i ≦ M)
  • 1 ≦ p_i ≦ q_i ≦ N (1 ≦ i ≦ Q)

方針決め

厄介なのは、「1 ≦ Q ≦ 1 \times 105」であること。
すなわち、クエリを受け取ってからできる操作は高々「102〜103程度」しかないということである。

したがって、事前に与えられたデータに処理を加えて、O(1)からO(103)程度で解を求められるようにする必要がある。

事前に行うデータ処理の方針を立てる

前処理の1つとして、累積和を取るという方法がある。
累積和を取れば、O(1)で区間[p_i, q_i]に含まれる列車の本数を求めることが可能となる。

まず、累積和を取る下準備として二次元配列d[MAX_N][MAX_N]を用意する。
各要素の意味は、
d[列車jの停車駅の左端 L_j ][列車jの停車駅の右端 R_j ] である。

そして、この配列の累積和を取っていく。
累積和の取り方については、親切にも問題文にヒントが書かれていた。
それは、

都市 p_iから都市q_iまでの区間に, 走る区間が 完全に含まれる 列車の本数.
言い換えれば, p_i ≤ L_jとR_j ≤ q_iが両方成りたつような列車jの本数.

という部分である。

ここから、累積和の取り方は、

  • L_jについて、前に積み上げる
    (なぜなら、L_jがp_i ≤ L_jを満たしているとき、同時に L_j+1 もp_i ≤ L_j+1を満たしているため)

  • R_jについて、後ろに積み上げる
    (なぜなら、R_jがR_j ≤ q_iを満たしているとき、同時にR_j-1もR_j-1 ≤ q_iを満たしているため)

という方針が立つ。

実装する

以上の内容を実装すると、以下のようになる。

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)

const int MAX_N = 575;

// d[l][r]
int d[MAX_N][MAX_N];

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  CIN(N, M, Q);
  REP(i, M) {
    CIN(L, R);
    L--; R--;
    d[L][R]++;
  }

  // 後ろから前に積み上げる(iはNから0に下がっていく)
  RREP(i, N + 1) {
    REP(j, N + 1) {
      d[i][j] += d[i + 1][j];
    }
  }

  // 前から後ろに積み上げる(jは0からNに上がっていく)
  REP(i, N + 1) {
    REP(j, N + 1) {
      if (j > 0) {
    d[i][j] += d[i][j - 1];
      }
    }
  }

  REP(qi, Q) {
    CIN(p, q);
    p--; q--;
    cout << d[p][q] << endl;
  }

  return 0;
}

別解法(BIT)

BITを二次元で持つことでもっと簡単にかける。
BITについては蟻本やslideshareを漁れば良いと思う。

以下、ソースコード。

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

template< class Abel > class BIT {
public:
  BIT(int _n) : N(_n) { init(); }

  void init() {
    // [1, N]の範囲なので、+1する必要がある
    bit.clear();
    bit.resize(N + 1, 0);
  }

  void add(int i, Abel x) {
    while (i <= N) {
      bit[i] += x;
      i += i & -i;
    }
  }

  Abel sum(int i) {
    Abel sm = 0;
    while (i > 0) {
      sm += bit[i];
      i -= i & -i;
    }
    return sm;
  }

  Abel getSum(int _x, int _y) {
    return sum(_y) - sum(_x - 1);
  }

private:
  int N;
  vector< Abel > bit;
};



int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  CIN(N, M, Q);
  vector< BIT< int > > bit(N + 1, BIT< int >(N + 1));

  REP(i, M) {
    CIN(L, R);
    REP(j, L + 1) {
      bit[j].add(R, 1);
    }
  }

  REP(qi, Q) {
    CIN(p, q);
    cout << bit[p].sum(q) << endl;
  }
  
  return 0;
}

感想

コンテスト中のコードを見てきたが、方針は正しかったのに、実装でiとjの添字を逆にしたり、ループの向きを逆にしたりしていた。

先ほど見たときは割とすぐに見つけられたので、コンテスト中の焦りで目が曇ったのだろうと思う。

本番に弱いというよりかは、場数が少ないことによるものだと思うので、今後は積極的に海外コンにも参加しようと思う。

ABC076-D : AtCoder Express

競プロ AtCoder
もくじ

D問題 AtCoder Express

はじめに

この記事は、解説のeditorial
(https://img.atcoder.jp/abc076/editorial.pdf)
および
AtCoder Beginner Contest 076 解説放送 - YouTube
を参考にして執筆した。
理解の助けになると思われるので、それぞれのリンクを参照されたい。

また、紹介するソースコードのforループは以下のようなマクロを使用している。

書き方 意味
REP(i, N) for (int i = 0; i < N; ++i)と同義
RREP(i, N) for (int i = N - 1; i >= 0; --i)と同義

考え方

本記事では、この問題を以下の4段階(+1)の考察で解説している。

1. 列車の総走行時間を考える。
2. t[s]からt+1[s]の間の変化を考える。
3. 0.5[s]間隔で考えた時の列車の移動距離を考える。
4. (0 ≦ t ≦ T)の範囲のv[t][m/s]の求め方を考える。
5. 以上の考察をまとめてコーディングする。

順を追って説明する。

1. 列車の総走行時間を考える

列車の総走行時間をT[s]としたとき、文章中に書いてある通り
T = (t_1 + t_2 + t_3 + ... + t_N)[s]である1。

したがって、以下のようにforループで総和を求めれば良い。

// 全体のT秒を求める
int T = 0;
REP(i, N) {
  T += t[i];
}

2. t[s]からt+1[s]の間の変化を考える

1.で総走行時間Tを求めた。
t[s] (0 ≦ t ≦ T)について、t[s]からt+1[s]までの変化を考える。

しかし、入力例4から分かる通り、t[s]からt+1[s]の変化は単調増加、もしくは単調減少ではない。

したがって、時間の区切りをt[s]からt+0.5[s]までの変化を考える。

ここで、t[s] (0 ≦ t ≦ T)について、0.5[s]間隔のt[s]ををmaxV[t]として保持する。
0.5秒間隔であることから、配列の要素数は2 * T + 1である2。

今回は、t[s]の時の最大速度をmaxV[t][m/s]とする。
このmaxVは0.5秒間隔なので、t[s]のv[t]に対してt * 2個目とt * 2 + 1個目の配列の要素と対応している。

また、最後に閉区間の重なっている部分は2つの要素の最小値を求める必要があることに留意したい。
これらは、以下のように実装できる3。

const int INF = 1e9 + 1;

vector< double > maxV(2 * T + 1, (double)INF);

// maxVのスピードをv[i]で初期化
int nowT = 0;
REP(i, N) {
  REP(ti, t[i]) {
    int t1 = nowT + ti * 2;
    int t2 = nowT + ti * 2 + 1;
    maxV[t1] = min(maxV[t1], v[i]);
    maxV[t2] = min(maxV[t2], v[i]);
  }
  nowT += t[i] * 2;
  maxV[nowT] = min(maxV[nowT], v[i]);
}

3. 0.5[s]間隔で考えた時の列車の移動距離を考える

2.で示した0.5秒間隔の移動を考えると以下の図のようになる。

f:id:task4233:20180816220436j:plain

この図において、移動距離は台形の面積S_tとして表せるため、
S_t = {\displaystyle {\frac{1}{2}} ({上底} + {下底}) \times {高さ}}
として表せる。

したがって、総移動距離はtsの範囲でS_tの総和を求めれば良い。
これを求めるためには、以下のようにforループを用いれば容易に実装できる。

double ans = 0.0;
REP(i, 2 * T + 1) {
  // (上底 + 下底) * 高さ / 2
  ans += (maxV[i] + maxV[i + 1]) * 0.5 / 2.0;
}

4. (0 ≦ t ≦ T)の範囲のmaxV[t][m/s]の求め方を考える

まず、問題文の

走行開始時と走行終了時には列車は止まっていなければならない

という記述から、
0[s]およびT[s]の時のmaxVは0[m/s]である。

次に、問題文の

加速度±1[m/s2]以内でなければならない

という記述から、
v[t]からv[t+1]の変化は±1以内に収まることが分かる。

ただし、2.でmaxV[m/s]は0.5[s]間隔としたので、
maxV[t]からmaxV[t + 1]の変化は0.5以内に収まるはずである。

これが成り立つようにするには、
0[s]からT[s]までの変化について、
maxV[t] = min(maxV[t], maxV[t - 1] + 0.5)
であり、
T[s]から0[s]までの変化について、
maxV[t] = min(maxV[t], maxV[t + 1] + 0.5)
と表せる。

したがって、(0 ≦ t ≦ T)の範囲のmaxV[t][m/s]は以下のように2つのforループで求められる。

// 0秒とT秒は0(静止)
maxV[0] = maxV[T * 2] = 0.0;
  
// 前から比較
REP(ti, 2 * T + 1) {
  maxV[ti + 1] = min(maxV[ti + 1], maxV[ti] + 0.5);
} 
  
// 後ろから比較
RREP(ti, 2 * T + 1) {
  maxV[ti] = min(maxV[ti], maxV[ti + 1] + 0.5);
}

5. 以上の考察をまとめてコーディングする

まとめたものがこちらになります(提出コード)。
Submission #3017041 - AtCoder Beginner Contest 076

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)

const int INF = 1e9 + 1;

int main()
{
  int N;
  scanf("%d", &N);
  vector< double > t(N);
  vector< double > v(N);
  REP(i, N) {
    scanf("%lf", &t[i]);
  }
  REP(i, N) {
    scanf("%lf", &v[i]);
  }

  // 全体のT秒を求める
  int T = 0;
  REP(i, N) {
    T += t[i];
  }
  
  vector< double > maxV(2 * T + 1, (double)INF);

  // maxのスピードをv[i]で初期化
  int nowT = 0;
  REP(i, N) {
    REP(ti, t[i]) {
      int t1 = nowT + ti * 2;
      int t2 = nowT + ti * 2 + 1;
      maxV[t1] = min(maxV[t1], v[i]);
      maxV[t2] = min(maxV[t2], v[i]);
    }
    nowT += t[i] * 2;
    maxV[nowT] = min(maxV[nowT], v[i]);
  }

  // 0秒とT秒は0(静止)
  maxV[0] = maxV[T * 2] = 0.0;
  
  // 前から比較
  REP(ti, 2 * T + 1) {
    maxV[ti + 1] = min(maxV[ti + 1], maxV[ti] + 0.5);
  } 
  
  // 後ろから比較
  RREP(ti, 2 * T + 1) {
    maxV[ti] = min(maxV[ti], maxV[ti + 1] + 0.5);
  }
  
  double ans = 0.0;
  REP(i, 2 * T + 1) {
    // (上底 + 下底) * 高さ / 2
    ans += (maxV[i] + maxV[i + 1]) * 0.5 / 2.0;
  }

  printf("%.4f\n", ans);

  return 0;
}

感想

以前見た時はeditorialを見たのに意味がわからなかったが、
順序立てて考えたら割とスッキリしたコーディングができた。

求めたいものは何なのか？
そして、それをそれを求めるためには何が必要なのか？
ということを考えるのが重要だと感じた。

  1. [秒]のこと。↩

  2. T = 1.0[s]の時を考えれば、0.0[s], 0.5[s], 1.0[s]であるので要素数は2 * T + 1個必要なことが分かる。 ↩

  3. INFは1.0 * 109 + 1とした(非常に大きな数)。↩

CpawCTF Level2 メモ

CTF

問題一覧

CpawCTF - Main page

Q13. [Stego] 隠されたフラグ

問題文に書かれている通り、隅を見ると.と-の文字列を発見。
トンツーだと思い、モールス信号の変換サイトに打ち込んでみるとビンゴだった。
しかし、cpaw{変換した文字列}を打ち込むものの何故か通らない……
色々と打ち込んで見ると、変換した文字列の頭についているcpawを消したら通った。
どうやら頭のcpawは除去して良いらしい。

Q15. [Web] Redirect

とりあえずデベロッパーツールを開く。
案の定、NetworkのHeadersにX-flagがあった。
余談だが、Firebugって開発終了してたのね。
知らなかった。

Q16. [Network + Forensic] HTTP Traffic

.pcapファイルなので、Level1で使用したwiresharkで開いてみる。 すると、ところどころにhtmlの断片らしきものが確認できた。
しかし、肝心のflagが見つからないため解法を調べる。
すると、wiresharkにはオブジェクトをエクスポートできる機能があるので、それを使用すればよいとのこと1。
エクスポートしてファイルを1つずつ見ていくと、network100(1)のファイルの中に

フラグが欲しかったら下のボタンを押すんだ！！

とある。
そのため、拡張子を.htmlにして開いてみると、ボタンが表示されていない。
ソースコードを確認すると、OnButtonClickの処理が ./js/button2.js に書かれているようなので、button2.jsを指定された場所に配置。
クリックするとcpaw{***}が描画されている画像が表示されるため、終了。

Q17. [Recon] Who an I?

書かれている情報をググって、画像を見て終了。

Q19. [Misc] Image

対象のzipファイルを解凍すると、いくつかのファイルが出てきた。
その中の meta.xml を開くと、

LibreOffice/4.2.8.2$Linux_X86_64 LibreOffice_project/420m0$Build-2

との記述があるため、LibreOfficeで開くと黒い長方形で隠された画像が表示された。
それをずらし、解答をコピーして終了。

Q20. [Crypto] Block Cipher

提示されたCファイルを見ると2つ目の引数の値によって復号が変わるようだったので、
ソースコードを以下の通りに書き換えた。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[]){
  int h, i, j;
  const char* flag = argv[1];
  for (h = 0; h < 40; ++h) {
    printf("cpaw{");
    for(i = h - 1; i <= strlen(flag); i+=h)
      for(j = i; j>= i - h + 1; j--)
    printf("%c", flag[j]);
    printf("}\n");
    
  }
  
  return 0;
}

コンパイルして実行し、意味の通るものを見つけて終了。

Q21. [Reversing] reversing easy!

fileコマンドで調べると、32bitのLinux実行ファイルらしい。
実行できないので、バイナリエディタで見てみると、cpawの文字はあるものの、その先が見れない……
解法をググると strings コマンドというものを使用するらしい[^1]。
先ほどcpawという文字列を見つけたので、
$ strings | grep -A 20 cpaw
を実行してflagを取得し、終了。

Q22. [Web] Baby's SQLi - Stage 1 -

提示されたページにアクセス。
SQL文を入れろとのことなので、調べて打ち込んで終了。
SELECT * FROM palloc_home

SELECT * (全ての行を表示)
FROM palloc_home (palloc_homeというテーブルにおける)

Q28. [Network] Can you login?

また.pcapファイルか……
と思いつつwiresharkで開き、一行ずつ目を通していく。
その中で、

USER cpaw_user

という記述を見つけたものの、
何をすれば良いのか分からず、解説を見る。 解説によると、
1. .pcapファイルからユーザ名とPASSを取得
2. それらを使用し、FTPサーバに接続
3. サーバ内にあるflagを取得
という流れのようだ。

順を追って試してみる。
1. .pcapファイルからユーザ名とPASSを取得
どうやら、USERの記述の後にPASSの記述もあったらしい。
ランダムな文字列だったので見逃していた。
2. それらを使用してFTPサーバに接続
FTPサーバへは$ ftp コマンドを使用するとのこと。
以下、接続の流れである。

ftp> open 157.7.52.186    
Connected to 157.7.52.186.  
220 Welcome to Cpaw CTF FTP service.  
Name (157.7.52.186:user_name): cpaw_user  
331 Please specify the password.  
Password:  
230 Login successful.  
Remote system type is UNIX.  
Using binary mode to transfer files.

このように、ユーザ名とPASSを入力して接続する。
3. サーバ内にあるflagを取得
接続できたようなので、早速ls -aを叩いてみる。
しかし、500 Illegal PORT commandと表示されてしまう。
解説を見ると、active modeからpassive modeというモードに変更する必要があるようだ。 ちなみに、active modeとpassive modeの違いはどちらが主導権を握っているからしい2。

名称 主導権
active mode サーバ側
passive mode クライアント側

それはさておき、passve modeにするためには単にpassiveと入力するだけで良いとのこと。
そして、ls -aを叩くと

227 Entering Passive Mode (157,7,52,186,234,111)
150 Here comes the directory listing.
drwxr-xr-x 2 ftp ftp 42 Sep 03 2017 .
drwxr-xr-x 2 ftp ftp 42 Sep 03 2017 ..
-rw-r--r-- 1 ftp ftp 39 Sep 01 2017 .hidden_flag_file
-rw-r--r-- 1 ftp ftp 36 Sep 01 2017 dummy

と表示された。
.hidden_flag_fileを開こうとcatコマンドを使用したが、何故か開けない……
仕方がないので、getコマンドでダウンロード。
ローカル環境で見るとflagが見つかり、終了。

感想

Level1と比べて、難しくなったというよりかは専門的になってきたという印象が強い。
具体的には、wiresharkの使用法やstringsコマンド、ftpサーバへの繋ぎ方など様々だ。
だが、まだ理解できるレベルなので問題は無さそう。
明日はLevel3をやろう。

  1. CpawCTF write up(Level2) - Qiita↩

  2. FTPのアクティブモードとパッシブモードの違いは、データ転送の接続方向↩

CpawCTF Level1のメモ

CTF

CpawCTFを始めてみた

夏の長期休みで時間が空いているので始めることにした。

問題一覧

CpawCTF - Main page

Q1. [Misc] Test Problem

やるだけ。

Q6. [Crypto] Classical Cipher

解法は問題文に記載されている通りで、文字コードを3ずつずらせば良い。
ただし、_と中カッコ、大文字は書き換える必要があった。
C++で書いてみた。

#include <stdio.h>
#include <string>
using namespace std;

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); ++i)
    s[i] = tolower(s[i]);
  for (int i = 0; i < s.size(); ++i)
    printf("%c", ((s[i] - 97) - 3 + 26) % 26 + 97);
  printf("\n");
  return 0;
}

Q7. [Reversing] Can you execure?

$ file ./exec_me
を叩くと、

exec_me: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=663a3e0e5a079fddd0de92474688cd6812d3b550, not stripped

と表示された。
ELF 64-bit LSB1 excutableと書かれているので、64bitのlinux環境での実行ファイルであることが分かる。
使用している環境がLinuxだったため、
$ ./exec_me
を実行しようとしたが、権限が無いと言われた。
そのため、
$ chmod 755 ./exec_me | ./exec.me
を実行して終了。

Q8. [Misc] Can you open this file ?

$ file ./open_me
を叩くと、

open_me: Composite Document File V2 Document, Little Endian, Os: Windows, Version 10.0, Code page: 932, Author: v, Template: Normal.dotm, Last Saved By: v, Revision Number: 1, Name of Creating Application: Microsoft Office Word, Total Editing Time: 28:00, Create Time/Date: Mon Oct 12 04:27:00 2015, Last Saved Time/Date: Mon Oct 12 04:55:00 2015, Number of Pages: 1, Number of Words: 3, Number of Characters: 23, Security: 0

と表示された。
読んでいくと Name of Creating Application: Microsoft Office Word とあるため、LibreOfficeで開いて終了。

Q9. [Web] HTML Page

提示されたWebサイトにアクセス。
ソースコードを表示して、 cpaw で検索して終了。

Q10. [Forensics] River

river.jpgのプロパティを確認するが、情報は得られず……
ググると 、画像ファイルの詳細な情報を確認するには
$ identify
というコマンドを叩けば良いとのこと2。
$ identify -verbose ./river.jpg
を叩き、表示された中に位置情報(exif:GPSLatitude, exif:GPSLongtitude)が含まれていたため、GoogleMapsで検索。
川の名前が書かれていなかったので、川を辿って見つけて終了。

Q11. [Network] pcap

.pcapファイルを初めて目にしたのでググってみると、wiresharkというソフトウェアで解析できるようだ。
$ sudo apt install wireshark
で早速インストール。
インストールはこちらの記事を参考にした。
qiita.com
インストール後、wiresharkでnetwork10.pcapを開くと解答がすぐに見つかるので終了。

Q12. [Crypto] HashHashHash!

解法が問題文に記載されているため、その通りにデコードして終了。

Q14. [PPC] 並べ替えろ!

唯のソート。
C++で書くなり、ruby console使うなり、アナログでソートするなり、お好みのソートでどうぞ。

感想

.pcap以外はLevel 1ということもあってか、サクサク解けたと思う。
正直、Markdownで書くことの方が大変だった。
明日以降も続けていこうと思う。

  1. ELF(Executable and Linking Format)のこと。Linuxディストリビューションで標準バイナリ形式として使用されている。実行ファイル形式のELFって何？ - ITmedia エンタープライズ ↩

  2. Linux環境で画像ファイルの情報を確認する方法 - Qiita↩