博多電光

技術ブログ

SECCON 2017 Quals Writeup - z80, SHA-1 is dead, Qubic Rube

※この記事は TSG Advent Calendar 2017 11日目の記事です。

SECCON 2017 予選にチーム「TSG」として参加した。結果は世界23位、日本5位

SHA-1 is dead (Crypto100)

http://sha1.pwn.seccon.jp/

Upload two files satisfy following conditions:

file1 != file2

SHA1(file1) == SHA1(file2)

SHA256(file1) <> SHA256(file2)

2017KiB < sizeof(file1) < 2018KiB

2017KiB < sizeof(file2) < 2018KiB

1KiB = 1024 bytes

解法

やるだけ。Google様の力を借りる。

$ wget https://shattered.io/static/shattered-1.pdf
--2017-12-11 21:27:40--  https://shattered.io/static/shattered-1.pdf
Resolving shattered.io (shattered.io)... 216.239.36.21, 216.239.38.21, 216.239.34.21, ...
Connecting to shattered.io (shattered.io)|216.239.36.21|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 422435 (413K) [application/pdf]
Saving to: 'shattered-1.pdf'

shattered-1.pdf                   100%[===============================================================>] 412.53K   342KB/s   in 1.2s

2017-12-11 21:27:42 (342 KB/s) - 'shattered-1.pdf' saved [422435/422435]

$ wget https://shattered.io/static/shattered-2.pdf
--2017-12-11 21:27:47--  https://shattered.io/static/shattered-2.pdf
Resolving shattered.io (shattered.io)... 216.239.36.21, 216.239.38.21, 216.239.34.21, ...
Connecting to shattered.io (shattered.io)|216.239.36.21|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 422435 (413K) [application/pdf]
Saving to: 'shattered-2.pdf'

shattered-2.pdf                   100%[===============================================================>] 412.53K   312KB/s   in 1.3s

2017-12-11 21:27:49 (312 KB/s) - 'shattered-2.pdf' saved [422435/422435]

$ dd if=/dev/zero of=dummy bs=1643000 count=1
1+0 レコード入力
1+0 レコード出力
1643000 バイト (1.6 MB) コピーされました、 0.006498 秒、 253 MB/秒

$ cat shattered-1.pdf dummy > sha1-1.dat

$ cat shattered-2.pdf dummy > sha1-2.dat

$ ls -la sha1*.dat
-rwxrwxrwx 1 root root 2065435 12月 11 21:30 sha1-1.dat
-rwxrwxrwx 1 root root 2065435 12月 11 21:30 sha1-2.dat

$ sha1sum sha1*.dat
fa004512dad796e9e5f7958e497166c4df54eb7a  sha1-1.dat
fa004512dad796e9e5f7958e497166c4df54eb7a  sha1-2.dat

評価

な~~にがcryptoじゃ。

評価: ★★☆☆☆

z80 (Binary300)

Reverse it.

BuggyCPUBoard-82e40efd036ae8e87e149de07e6b99f5e01e389a537bf1d630b5af84d8f2b10a.ino

Pictures.tar.gz

本日のメイン。Arduinoスケッチファイルと、Arduinoマイコンが接続されたブレッドボードを360度から撮影した22枚の写真が与えられる。

2年前のSECCONでTSGを混乱に陥れた Reverse-Engineering Hardware の再来か⋯⋯と思われたが、実際にはそれ以上に頭のおかしい問題だった。

解法

前半部分は主に@Joe氏が担当した。まず写真を見ながら回路を検分する。ボードのほうは Arduino Mega だと分かる。マイコンのほうは (嫌らしいことに) わざわざSECCONステッカーが上に貼ってあり、型番がわからないが、問題のタイトルがz80なので、十中八九z80マイコンであると思われる。

@Joe氏がマイコンのデータシートと写真をにらめっこしながら、以下のように手書きの回路図を作成した。(お疲れ様です⋯⋯)

f:id:hakatashi:20171211191450j:plain

ここからは主に僕が担当した。とりあえずArduinoスケッチファイルのほうを読んでみる。とても長いのでざっと眺めるくらいしかしてないが、一番気になるのはmemという怪しい変数。

static unsigned char mem[memsize] = {
  0x22, 0x47, 0x00, 0x3d, 0x53, 0x77, 0x23, 0x3d, 0x45, 0x77, 0x23, 0x3d, 0x43, 
  0x77, 0x23, 0x77, 0x23, 0xc5, 0x0c, 0x77, 0x23, 0xc5, 0xfd, 0x77, 0x23, 0x3d, 
  0x7b, 0x77, 0x23, 0x39, 0x44, 0x00, 0x47, 0xc5, 0x46, 0x31, 0x44, 0x00, 0x78, 
  0x31, 0x46, 0x00, 0xfd, 0x22, 0xf9, 0x1e, 0x00, 0xfd, 0x7b, 0xf1, 0x1e, 0x00, 
  0x77, 0x23, 0x39, 0x45, 0x00, 0x3e, 0x31, 0x45, 0x00, 0xc1, 0x1e, 0x00, 0x3d, 
  0x7d, 0x77, 0x75, 0x03, 0x0b, 0x09, 
};

読むと、memReadやmemWriteという関数がこのmemにバイト単位の読み書きを行っているらしい事がわかる。そしてZ80マイコンがHALTした時、dispWork(0x47);でmemの0x47以降の内容をシリアルポートに書き出している。この時点でどうやらmem変数をZ80マイコンを動作させるためのプログラムメモリとして利用しているのではないかと当たりをつけた。

となるとmem変数の中身はZ80バイナリということになる。データを適当に整形してyazdに投げると、以下のように逆アセンブルできた。

        LD      (L0046+1),HL    ; reference not aligned to instruction
        DEC     A
        LD      D,E
        LD      (HL),A
        INC     HL
        DEC     A
        LD      B,L
        LD      (HL),A
        INC     HL
        DEC     A
        LD      B,E
        LD      (HL),A
        INC     HL
        LD      (HL),A
        INC     HL
        PUSH    BC
        INC     C
        LD      (HL),A
        INC     HL
        PUSH    BC
        LD      (IY+23h),A
        DEC     A
        LD      A,E
        LD      (HL),A
        INC     HL
        ADD     HL,SP
        LD      B,H
        NOP
        LD      B,A
        PUSH    BC
        LD      B,(HL)
        LD      SP,0044h
        LD      A,B
        LD      SP,0046h
        LD      (1EF9h),IY
        NOP
        LD      A,E
        POP     AF
        LD      E,00h
        LD      (HL),A
        INC     HL
        ADD     HL,SP
        LD      B,L
        NOP
        LD      A,31h           ; '1'
        LD      B,L
        NOP
        POP     BC
        LD      E,00h
        DEC     A
        LD      A,L
        LD      (HL),A
        LD      (HL),L
        INC     BC
        DEC     BC
L0046:  ADD     HL,BC

アセンブルできたものの、肝心のHALT命令もないし、いまいち意味の分からない内容である。実際にZ80エミュレーターで動かしてみても特に何も起きないし、0x47以降のアドレスにも意味のある内容が書き出されない。ここでずいぶん悩まされた。

立ち返ってArduinoスケッチファイルのファイル名を確認してみる。ファイル名にはBuggyCPUBoardとある。実は@Joe氏が回路の解析を行った際に、気になった部分があった。写真の赤丸の部分に注目して欲しいのだが、

f:id:hakatashi:20171209224300j:plain

よく見ると、他のピンはツイストされたケーブルの白色のジャンパが手前に刺さっているところが、この部分だけ白色のジャンパが奥になっている。この部分を辿っていくと、.inoに書かれたピン配置の配線と食い違っていることがわかる。

@@ -1,5 +1,5 @@
-unsigned D0=22;
-unsigned D1=23;
+unsigned D0=23;
+unsigned D1=22;
 unsigned D2=24;
 unsigned D3=25;
 unsigned D4=26;

D0ピンとD1ピンが入れ替わっている。Dピンはマイコンへのデータの書き出し/読み出しに対応しているので、ここが間違っているとZ80に入力されるデータの中身が違ってくる。おそらくこの間違いがBuggyCPUBoardの「Bug」なのだと思われる。

つまり、mem変数のデータと、実際にZ80が読み出すデータは異なっているものと思われる。mem変数のデータを適当なスクリプトでビットをswapして、再度逆アセンブルすると、

        LD      HL,0047h
        LD      A,53h           ; 'S'
        LD      (HL),A
        INC     HL
        LD      A,46h           ; 'F'
        LD      (HL),A
        INC     HL
        LD      A,43h           ; 'C'
        LD      (HL),A
        INC     HL
        LD      (HL),A
        INC     HL
        ADD     A,0Ch
        LD      (HL),A
        INC     HL
        ADD     A,0FEh
        LD      (HL),A
        INC     HL
        LD      A,7Bh           ; '{'
        LD      (HL),A
        INC     HL
L001D:  LD      A,(L0044)
        LD      B,A
        ADD     A,45h           ; 'E'
        LD      (L0044),A
        LD      A,B
        LD      (L0045),A
        CP      21h             ; '!'
        JP      M,L001D
        CP      7Bh             ; '{'
        JP      P,L001D
        LD      (HL),A
        INC     HL
        LD      A,(L0046)
        DEC     A
        LD      (L0046),A
        JP      NZ,L001D
        LD      A,7Eh           ; '~'
        LD      (HL),A
        HALT
L0044:  INC     BC
L0045:  DEC     BC
L0046:  LD      A,(BC)

かなり意味の通った逆アセンブル結果になる。特にSECCONのフラグ形式であるSECCON{~}らしき文字列のようなものも見える。

実際にエミュレーターで実行させると、ちゃんとHALT命令で停止して終了する。ちなみにエミュレーターTSGコードゴルフ大会で使用したz80golfというアプリケーションを使っている。以下のようなパッチを入れるとステップ実行でデバッグできるようになって便利。

diff -r -u z80golf/src/main.c z80golf2/src/main.c
--- z80golf/z80golf/src/main.c  Sun Dec 10 04:34:03 2017
+++ z80golf2/z80golf/src/main.c Fri Nov 30 08:01:23 2007
@@ -147,7 +147,6 @@

 /// 1命令実行
 void step() {
+       DebugZ80(&z80);
        ExecZ80(&z80);

                // システムコールされた場合、その処理へ飛ばす
@@ -169,7 +168,7 @@
 void exec_loop(int maxstep) {
        int i;
        for (i=0; maxstep == 0 || i < maxstep; ++i) {
+               // if (is_halt()) break;
-               if (is_halt()) break;
                step();
        }
 }

で、HALTした時点でのメモリの状態を確認してみる。

$ z80golf fixed.dat
AF:0000 HL:0000 DE:0000 BC:0000 IX:0000 IY:0000 I:00
0000[21 - LD HL,0047h] SP:0000[4721] FLAGS:[........] IM0:DI
[Command,'?']->
AF:0000 HL:0047 DE:0000 BC:0000 IX:0000 IY:0000 I:00
0003[3E - LD A,53h] SP:0000[4721] FLAGS:[........] IM0:DI
[Command,'?']->
AF:5300 HL:0047 DE:0000 BC:0000 IX:0000 IY:0000 I:00
0005[77 - LD (HL),A] SP:0000[4721] FLAGS:[........] IM0:DI
[Command,'?']->
(中略)
AF:0043 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
003D[C2 - JP NZ,001Dh] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']->
AF:0043 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
0040[3E - LD A,7Eh] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']->
AF:7E43 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
0042[77 - LD (HL),A] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']->
AF:7E43 HL:0058 DE:0000 BC:4A00 IX:0000 IY:0000 I:00
0043[76 - HALT] SP:0000[4721] FLAGS:[.Z....NC] IM0:DI
[Command,'?']-> m 0

0000: 21 47 00 3E 53 77 23 3E 46 77 23 3E 43 77 23 77  | !G.>Sw#>Fw#>Cw#w
0010: 23 C6 0C 77 23 C6 FE 77 23 3E 7B 77 23 3A 44 00  | #..w#..w#>{w#:D.
0020: 47 C6 45 32 44 00 78 32 45 00 FE 21 FA 1D 00 FE  | G.E2D.x2E..!....
0030: 7B F2 1D 00 77 23 3A 46 00 3D 32 46 00 C2 1D 00  | {...w#:F.=2F....
0040: 3E 7E 77 76 8F 4A 00 53 46 43 43 4F 4D 7B 48 5C  | >~wv.J.SFCCOM{H\
0050: 2B 70 3F 53 22 67 36 4A 7E 00 00 00 00 00 00 00  | +p?S"g6J~.......
0060: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
0070: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
0080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
0090: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00A0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00B0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00C0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00D0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00E0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
00F0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  | ................
[Command,'?']->

0x47以降のアドレスに何やらflagらしきデータが書き込まれている。

0040:                      53 46 43 43 4F 4D 7B 48 5C  |        SFCCOM{H\
0050: 2B 70 3F 53 22 67 36 4A 7E                       | +p?S"g6J~

ピンのswapによる変更はデータの書き出し時にも影響するので、実際にここに書き込まれるデータを得るには再びこのデータのビットをswapすればよい。すると、

0040:                      53 45 43 43 4F 4E 7B 48 5C  |        SECCON{H\
0050: 2B 70 3F 53 21 67 35 49 7D                       | +p?S!g5I}

となり、flagはSECCON{H\+p?S!g5I}

評価

実際に組まれた回路のデバッグを要求される点や、ビットをswapすると正しいバイナリが得られる点は面白いと思った。が、SECCONステッカーや束ねられたコードなど理不尽な嫌がらせが多く、本質的でない部分で精神を消耗する点で決して良問とは言い難い。また動作に必要とはいえArduinoスケッチファイルが大きく、これがそもそも何をするコードなのか把握するのに時間がかかった。せめて問題文にフォローがあったほうが良かったのでは。

評価: ★★★☆☆

Qubic Rube (Programming300)

Please continue to solve Rubic's Cube and read QR code.

http://qubicrube.pwn.seccon.jp:33654/

2017年になって復活した唯一のQRコード枠。問題タイトルが「QR」をもじったものだと気付くのに時間がかかった。

サイトにアクセスすると、回転するルービックキューブが表示される。

f:id:hakatashi:20171211213613p:plain

6面の画像にはQRコードが表示されており、読み取るとそれぞれ以下のようなテキストになる。

SECCON 2017 Online CTF
Have fun!
Qubic Rube
Next URL is:
No. 1 / 50
http://qubicrube.pwn.seccon.jp:33654/02c286df1bbd7923d1f7

最後のURLにアクセスすると、今度は面が1つ回転したルービックキューブが表示される。

f:id:hakatashi:20171211222337p:plain

この回転を戻してQRコードを読み取って⋯⋯を繰り返していく。10回くらいで完全にスクランブルされたキューブになる。

f:id:hakatashi:20171211222654p:plain

解法

自動化問題。画像のURLはわかりやすく面の色も判別しやすいので、基本的にめんどくさいだけのやるだけ問題である。

肝心のルービックキューブの解法は、たぶん同じ色のピースを9つ集めてきて、並び替えを全探索して有効なQRコードを探すだけで十分に解ける問題だと思われる (うまくやれば探索総数は1面につき2000程度)。が、最近ルービックキューブにはまっていることもあって、ちゃんとルービックキューブを解くプログラムをわざわざ書いてみた。

3x3x3のルービックキューブは、1x1x1のパーツ26個に分けられ、スクランブルされてもそれぞれのパーツに塗られている色の組み合わせは変化しない。3x3x3のルービックキューブではそれぞれのパーツの配色がユニークなので、パーツごとの配色を調べて正しい位置に置き直すだけで解くことができる。

ただし、センターパーツ (3x3の真ん中の1個) の回転だけはルービックキューブの特性上確定しないので、この部分だけ全探索しなければいけない。

画像の取得やQRコードの読み取りなどの自動化は@Joe氏が、ルービックキューブのソルブは僕が担当した。ソースコードはこちら。

github.com

罠として、11問目からルービックキューブの配色が 白⇔青 緑⇔黃 赤⇔橙 の日本配色から、白⇔黃 緑⇔青 赤⇔橙 の国際配色に変化する (は?)。各面の色を決め打ちで解いているとここで躓いてしまう。というか躓いた。

なので、

これは訂正しなければならない。

評価

可もなく不可もなく。300点問題にしては簡単すぎるかと。4x4とか5x5のキューブにしたらさすがに全探索だと難しくなってちょうどよかったのでは?

評価: ★★★★☆

感想

初めてBinary問題を解いたのでもはや実質バイナリアンと言っても過言ではない (は?)

8人くらいで解いたので本戦出れるかは分からないです。