https://score-quals.seccon.jp/team/115
チーム Bluemermaid として参加しました。総合17位、国内6位だったようです。
私がsubmitしたフラグは1つでした。（2つ解けたのだけど、1つは少し前に他の方が解いていた…。はやい。）
解けた問題
Special Device File
毎度おなじみ謎アーキでした。
$ file runme_8a10b7425cea81a043db0fd352c82a370a2d3373
runme_8a10b7425cea81a043db0fd352c82a370a2d3373: ELF 64-bit LSB executable, ARM aarch64, version 1 (SYSV), statically linked, not stripped
と言ってもaarch64ですが。
まずは毎度おなじみ環境構築をします。私はUbuntu 18.04でやりました。（事前にやっておけ。）
全部のアーキをビルドしていると試合が終わってしまうので、必要なアーキだけtargets.shに書いておくとよいでしょう。
そんなわけで、とりあえずシミュレータで実行してみると
/usr/local/cross2-gcc494/bin/aarch64-elf-run runme_8a10b7425cea81a043db0fd352c82a370a2d3373
トラップで落ちます。まあきっと未実装なのでしょう。
みんな大好きobjdumpをみてみると、
000000000000140c <__exit>:
140c: d4200000 .word 0xd4200000
1410: d65f03c0 ret
0000000000001414 <__read>:
1414: d28000c8 mov x8, #0x6 // #6
1418: d45e0000 .word 0xd45e0000
141c: d65f03c0 ret
0000000000001420 <__write>:
1420: d28000a8 mov x8, #0x5 // #5
1424: d45e0000 .word 0xd45e0000
1428: d65f03c0 ret
000000000000142c <__open>:
142c: d2800028 mov x8, #0x1 // #1
1430: d45e0000 .word 0xd45e0000
1434: d65f03c0 ret
0000000000001438 <__close>:
1438: d2800048 mov x8, #0x2 // #2
143c: d45e0000 .word 0xd45e0000
1440: d65f03c0 ret
1444: d503201f nop
1448: d503201f nop
こんな感じでたいへん怪しいです。きっと0xd45e0000という命令を実装しないといけないのでしょう。
ここで、シミュレータをトレース付きで実行してみると、
/usr/local/cross-gcc494/aarch64-elf/bin/run --trace-syscall=on runme_8a10b7425cea81a043db0fd352c82a370a2d3373
どこでこけているのかわかるようになります。
具体的には、cross-gcc494/toolchain/gdb-7.12.1/sim/aarch64/simulator.cの中のhandle_halt関数内です。（このソースは1万5000行くらいあって、ファイル分けてほしかったなあという気持ちになった。）
static void
handle_halt (sim_cpu *cpu, uint32_t val)
{
....
switch (aarch64_get_reg_u32 (cpu, 0, NO_SP))
{
case AngelSVC_Reason_HeapInfo:
...
case AngelSVC_Reason_Rename:
case AngelSVC_Reason_Elapsed:
default:
TRACE_SYSCALL (cpu, " HLT [Unknown angel %x]",
aarch64_get_reg_u32 (cpu, 0, NO_SP));
sim_engine_halt (CPU_STATE (cpu), cpu, NULL, aarch64_get_PC (cpu),
sim_stopped, SIM_SIGTRAP);
}
aarch64_set_reg_u64 (cpu, 0, NO_SP, result);
}
この関数の下方、AngelSVC_XXXでswitch-caseのdefaultで落ちていました。ということで、適当にここにハンドラを作ってあげればよさそうです。
syscall番号は、先のobjdump disasより、x8レジスタに代入されていることがわかっているので、引数はレジスタ0から入ると仮定していろいろみてみたところ、なんと/dev/xorshift64といういかにもなデバイスをopenしていることがわかりました。
最初のwriteはシードを設定するのでしょう。そして、後続のreadで乱数を取得すると予想できます。
というわけで、こんな感じで書いてみるとよさそうです。
default:
{
static uint64_t seed = 0;
uint64_t syscall_id = aarch64_get_reg_u64 (cpu, 8, SP_OK);
if(syscall_id == 1) {
uint64_t pathname = aarch64_get_reg_u64 (cpu, 0, SP_OK);
uint64_t flags = aarch64_get_reg_u64 (cpu, 1, SP_OK);
uint64_t mode = aarch64_get_reg_u64 (cpu, 1, SP_OK);
printf("open \n");
printf("pathname:%s \n", aarch64_get_mem_ptr (cpu, pathname));
break;
} else if(syscall_id == 2) {
printf("close\n");
break;
} else if(syscall_id == 5) {
printf("write\n");
uint64_t buf = aarch64_get_reg_u64 (cpu, 1, SP_OK);
uint64_t size = aarch64_get_reg_u64 (cpu, 2, SP_OK);
printf("buf:%lX \n", buf);
printf("size:%lX \n", size);
seed = aarch64_get_mem_u64 (cpu, buf);
printf("seed:%lX \n", seed);
break;
} else if(syscall_id == 6) {
uint64_t buf = aarch64_get_reg_u64 (cpu, 1, SP_OK);
uint64_t size = aarch64_get_reg_u64 (cpu, 2, SP_OK);
printf("read\n");
printf("seed:%lX \n", seed);
printf("buf:%lX \n", buf);
printf("size:%lX \n", size);
aarch64_set_mem_u64(cpu, buf, xorshift64_2(&seed));
printf("seed:%lX \n", seed);
break;
}
printf("not implemented syscall %lX\n", syscall_id);
}
TRACE_SYSCALL (cpu, " HLT [Unknown angel %x]",
aarch64_get_reg_u32 (cpu, 0, NO_SP));
sim_engine_halt (CPU_STATE (cpu), cpu, NULL, aarch64_get_PC (cpu),
sim_stopped, SIM_SIGTRAP);
注意しておきたいのは、readは戻り値ではなく、メモリに読み込んだ値を書き込んで返すということです。当たり前なのですが、私はうっかり戻り値に収まる大きさだったので戻り値として乱数を返してしまっており、時間を少し無駄にしました。（そのぶんaarch64のアセンブリを読めるようになったのでよしとしよう）。
ちなみにxorshift64_2は、試行錯誤の結果以下のコードでうまくいきました。（試行錯誤の過程が関数名に現れている。）
uint64_t xorshift64_2(uint64_t *state) {
uint64_t x = *state;
x = x ^ (x << 13);
x = x ^ (x >> 7);
x = x ^ (x << 17);
*state = x;
return x;
}
xorshiftは、よい周期性をもつシフトパラメータがいくつも存在するので、どれが選ばれるかは実装依存なのですが、このパラメータはxorshiftの論文内で例として用いられていたものでした。
Xorshift RNGs George Marsaglia ∗The Florida State University
余談ですが、論文内のxorshift32の実装例のところに
It uses one of my favorite choices, [a, b, c] = [13, 17, 5]
と書いてあって、めっちゃわかるー、ってなっていました。64bit版もきれいでよい。
まあ、こんな感じでデバイスの実装自体は終わりですが、文字出力のほうも既存のsyscallの実装にかぶっていたのでよしなにしてあげます。（同関数の上方です。）
case AngelSVC_Reason_Open:
{
/* Get the pointer */
/* uint64_t ptr = aarch64_get_reg_u64 (cpu, 1, SP_OK);. */
/* FIXME: For now we just assume that we will only be asked
to open the standard file descriptors. */
static int fd = 0;
result = fd ++;
//TRACE_SYSCALL (cpu, " AngelSVC: Open file %d", fd - 1);
uint64_t p0 = aarch64_get_reg_u64 (cpu, 0, SP_OK);
uint64_t p1 = aarch64_get_reg_u64 (cpu, 1, SP_OK);
uint64_t p2 = aarch64_get_reg_u64 (cpu, 2, SP_OK);
uint64_t p19 = aarch64_get_reg_u64 (cpu, 19, SP_OK);
//printf("p0:%lx p1:%lx p2:%lx sp:%lx p19:%lx\n", p0, p1, p2, aarch64_get_reg_u64 (cpu, 31, SP_OK), p19);
printf ("%c", aarch64_get_mem_u8(cpu, p1));
}
break;
（いろいろdeadcodeがありますが気にしないでください。）
これでシミュレータをコンパイルして再度実行してあげるとフラグを得られました。
SECCON{UseTheSpecialDeviceFile}
Special Instructions
これも謎アーキです。cross-gccのサンプルをfileしたときの出力と、与えられたファイルのfileを比較した結果、アーキはmoxieとわかりました。
$ file runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be
runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be: ELF 32-bit MSB executable, *unknown arch 0xdf* version 1 (SYSV), statically linked, not stripped
*unknown arch 0xdf* いい響きだ。
さて、というわけで適当に実行してみると、
This program uses special instructions.
SETRSEED: (Opcode:0x16)
RegA -> SEED
GETRAND: (Opcode:0x17)
xorshift32(SEED) -> SEED
SEED -> RegA
と出てから、SIGILLで落ちてしまいます。
cross-gcc494/toolchain/gdb-7.12.1/sim/moxie/interp.c にソースがあるので適当に読むと、該当する命令番号にご丁寧にも/*bad*/と書かれているのがわかりました。というわけで、適当に実装しちゃいましょう。
case 0x16: /* bad */
{
int a = (inst >> 4) & 0xf;
xorstate = cpu.asregs.regs[a];
//printf("SETRSEED(%X)\n", xorstate);
}
break;
case 0x17: /* bad */
{
int a = (inst >> 4) & 0xf;
//printf("GETRAND SEED=%X\n", xorstate);
cpu.asregs.regs[a] = XorShift(&xorstate);
}
break;
変数 xorstate は適当に関数sim_engine_runの先頭でstatic宣言しておきます。
void
sim_engine_run (SIM_DESC sd,
int next_cpu_nr, /* ignore */
int nr_cpus, /* ignore */
int siggnal) /* ignore */
{
word pc, opc;
unsigned short inst;
sim_cpu *scpu = STATE_CPU (sd, 0); /* FIXME */
address_word cia = CPU_PC_GET (scpu);
static int xorstate = 0;
で、問題はxorshiftです。論文で示されているパラメータは64セットあるのですが、十数個試しても引っかかりません。こまった。
というわけで、適当にパラメタ化してソルバを書いてやりました。
int shift_table[9 * 9 * 3] = {
1, 3,10, 1, 5,16, 1, 5,19, 1, 9,29, 1,11, 6, 1,11,16, 1,19, 3, 1,21,20, 1,27,27,
2, 5,15, 2, 5,21, 2, 7, 7, 2, 7, 9, 2, 7,25, 2, 9,15, 2,15,17, 2,15,25, 2,21, 9,
3, 1,14, 3, 3,26, 3, 3,28, 3, 3,29, 3, 5,20, 3, 5,22, 3, 5,25, 3, 7,29, 3,13, 7,
3,23,25, 3,25,24, 3,27,11, 4, 3,17, 4, 3,27, 4, 5,15, 5, 3,21, 5, 7,22, 5, 9,7 ,
5, 9,28, 5, 9,31, 5,13, 6, 5,15,17, 5,17,13, 5,21,12, 5,27, 8, 5,27,21, 5,27,25,
5,27,28, 6, 1,11, 6, 3,17, 6,17, 9, 6,21, 7, 6,21,13, 7, 1, 9, 7, 1,18, 7, 1,25,
7,13,25, 7,17,21, 7,25,12, 7,25,20, 8, 7,23, 8,9,23 , 9, 5,1 , 9, 5,25, 9,11,19,
9,21,16,10, 9,21,10, 9,25,11, 7,12,11, 7,16,11,17,13,11,21,13,12, 9,23,13, 3,17,
13, 3,27,13, 5,19,13,17,15,14, 1,15,14,13,15,15, 1,29,17,15,20,17,15,23,17,15,26,
};
uint32_t XorShift(uint32_t *state)
{
*state ^= *state << shift_table[SHIFT_INDEX * 3 + 0];
*state ^= *state >> shift_table[SHIFT_INDEX * 3 + 1];
*state ^= *state << shift_table[SHIFT_INDEX * 3 + 2];
return *state;
}
SHIFT_INDEXを定義してビルド&実行をぶん回すスクリプトを用意して
for i in {0..80}
do
echo index=$i
touch ~/repo/cross-gcc494/toolchain/gdb-7.12.1/sim/moxie/interp.c && \
make -s -C ~/repo/cross-gcc494/build/gdb/moxie-elf/sim CFLAGS+="-DSHIFT_INDEX=$i " &> /dev/null && \
cp ~/repo/cross-gcc494/build/gdb/moxie-elf/sim/moxie/run /usr/local/cross-gcc494/moxie-elf/bin/ && \
/usr/local/cross-gcc494/moxie-elf/bin/run runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be | grep SECCON && exit
done
実行すると
$ ./solve.sh
index=0
...
index=74
SECCON{MakeSpecialInstructions}
74番目は...13,17,15でしたね。うつくしい…。
ということで、フラグを得ました。（ところが十数分前にsrupさんがsubmitしていたのでした。きっとソルバを書き始めようとしていた頃でしょう。ちょっとくやしい。）
解けなかった問題
q-escape
megumishさんから教えていただいた
あたりを参考にしつつ、情報収拾をしている段階で時間切れでした。
$ ./qemu-system-x86_64 -device help 2>&1 | grep cydf
name "cydf-vga", bus PCI, desc "Cydf CLGD 54xx VGA"
name "isa-cydf-vga", bus ISA
$ nm qemu-system-x86_64 | grep cydf | grep ' d '
0000000000f5a580 d isa_cydf_vga_properties
0000000000f5a460 d pci_vga_cydf_properties
$ nm qemu-system-x86_64 | grep mmio | grep cydf
000000000068da40 t cydf_mmio_blt_read
000000000068ec70 t cydf_mmio_blt_write
0000000000a99bc0 r cydf_mmio_io_ops
000000000068dd90 t cydf_mmio_read
000000000068f9f0 t cydf_mmio_write
00:02.0 Class 0300: 1234:1111
/ # cat /proc/iomem | grep 00:02.0
fc000000-fcffffff : 0000:00:02.0
febc0000-febc0fff : 0000:00:02.0
これはがんばれば解けそうな気がするのでぜひやりたい。
Needle in a haystack
場所の特定はした。大阪の梅田ですね。（「新梅田研修センター」という看板が目立っていた。）
画面中央のビルは実在しなさそうなので怪しかったのですが、動画処理は得意ではないので撤退しました。
まとめ
今回は謎アーキ問題がそんなに多くなかったし、そこまで頭をひねるというわけでもなかったのは少し残念かもしれない。
とはいえ、単純なところで引っかかって時間を無駄にしてしまったり、そもそも準備不足で環境構築に時間を浪費する場面が多かったので、本戦に行く際には改善してゆきたい。
あと風邪を引いてしまったようなので、きちんと休んで回復したい。
運営の皆さん、面白い問題をありがとうございました！
