今年もDEF CON CTFの予選にyharimaとしてではなくYOKARO-MONのゲストとして参加しました。
自分は fountain-ooo-reliving をほぼ解いたのでそのwriteupを書き残します。
問題
ライフゲームのパターンファイルが用意されている。
これをGollyというライフゲームシミュレータに食わせる。
めちゃめちゃな巨大なパターンでジェネレーション処理をスタートしてもどこが変化しているかわからない。。。
部分部分を拡大していくと「ROM」、「RAM」、「ALU」とかが書いてありおそらく「ちっちゃなコンピュータを再現したライフゲームのパターン」だということが何となくわかってくる。（変態だろ）
ジェネレーションのステップ数を8^8ぐらいにすると、マス目の白い部分が徐々に動いていきRAMに該当するマスに値が書き込まれていく様子を確認。マジでライフゲームで動いてるのすごいなーと眺めてました。
最後まで動かすとRAMに変化がなくなり、データが16bitで格納されてそうなのでそれを読み取ってもフラグにならず。
解答の起点
いろいろ検索をかけているとBuild a working game of Tetris in Conway's Game of Lifeなる「ライフゲームでテトリスしてみた」的なページを発見。
このページに書いてあるライフゲームのパターンが問題のものと酷似。なんならこの処理系の仕様がガッツリ書かれている。「これが元ネタか！」と思いこのページを読み進めていく。
この問題のカテゴリがreversing、そして発見したページに命令セットの説明もあるので、この問題は「ROM部分を解析してアセンブリに落とす」という方針で取り組むことにしました。
ROMの解析
解析を試みるもパターンファイルは何が書いてあるかさっぱりで、目視で読み取ろうにも大量のマス目が0なのか1なのか判断するのが難しかったので、ROMの部分だけ画像として切り抜いて0, 1判定をするスクリプトを組みました。
切り抜いた画像が以下。
何が0でどれが1なのかは見ただけではさっぱりだと思いますが微妙に違います。
#!/usr/bin/env python3.7
import numpy as np
import cv2
cell_w = 8
cell_h = 7
start_x = 1258
start_y = 4
result = []
img = cv2.imread('rom.png')
for pos_x in range(0, 115):
r = []
for pos_y in range(0, 58):
sum = 0
for x in range(0, cell_w):
for y in range(0, cell_h):
xx = start_x + x - pos_x * 11; yy = start_y + y + pos_y * 11
c = img[yy][xx]
sum += c[0] + c[1] + c[2]
# img[yy][xx] = (255, 0, 0)
b = '0' if sum == 8064 else '1'
#print(pos_x, pos_y, b)
r.append(b)
result.append(r)
print('\n'.join(map(lambda r: ''.join(r), result)))
#cv2.imshow('image', img)
#cv2.waitKey(0)
#cv2.destroyAllWindows()
1つ1つセルを切り抜きRGBをすべて足し算して特定の値になれば0みたいなことをしてました。実行すると以下のデータが取得できます。
0000000000001010110000000000001011000011111111111111110001
0000000000000000100000000000000000000000000000000000000110
0000000000000000100001100101011100110011111111111111110001
0000000000000000110000111000110110100011111111111111110001
0000000000000001000001010111101011010011111111111111110001
0000000000000001010001100011010000110011111111111111110001
0000000000000001100000001110100111110011111111111111110001
0000000000000001110000110100010011110011111111111111110001
0000000000000010000000101111000110110011111111111111110001
0000000000000010010000001001111110100011111111111111110001
0000000000000010100000111101110011110011111111111111110001
0000000000000010110000010111001000010011111111111111110001
0000000000000011000001000110010110010011111111111111110001
0000000000000011010000111001111001110011111111111111110001
0000000000000011100000010010100101010011111111111111110001
0000000000000011110000011110010010100011111111111111110001
0000000000000100000001010111110100000011111111111111110001
0000000000000100010000100000101100110011111111111111110001
0000000000000100100000110000100000100011111111111111110001
0000000000000100110001011000110100100011111111111111110001
0000000000000101000001000000011100110011111111111111110001
0000000000000101010000011011110111000011111111111111110001
0000000000000101100001011001000010010011111111111111110001
0000000000000101110001010111001000110011111111111111110001
0000000000000110000000110000110001010011111111111111110001
0000000000000110010000011111000000000011111111111111110001
0000000000000110100001101000000001100011111111111111110001
0000000000000110110000111100011110110011111111111111110001
0000000000000111000000011001010001110011111111111111110001
0000000000000111010000000111000011100011111111111111110001
0000000000000111100001011000101100010011111111111111110001
0000000000000111110001100001101110110011111111111111110001
0000000000001000000001000000001110100011111111111111110001
0000000000001000010000010100000110010011111111111111110001
0000000000001000100000111100111010010011111111111111110001
0000000000001000110001011101001110110011111111111111110001
0000000000001001000001011100101110100011111111111111110001
0000000000001001010000110111000001100011111111111111110001
0000000000001001100001011010010100110011111111111111110001
0000000000001001110000000000000000000011111111111111110001
0000000000001001110010010101110101010100000000000000010110
0000000000000000100100000000000000100100000000001001110011
0000000000001001110011001001001111100100000000000000010110
0000000000000000110100000000000000110100000000001001110011
0000000000001001110010100111111010110100000000000000010110
0000000000000001000100000000000001000100000000001001110011
0000000000001001110010010011101010010100000000000000010110
0000000000000001010100000000000001010100000000001001110011
0000000000001001110011111111000111110100000000000000010110
0000000000000001100100000000000001100100000000001001110011
0000000000001001110011000100101010100100000000000000010110
0000000000000001110100000000000001110100000000001001110011
0000000000001001110011011111011011010100000000000000010110
0000000000000010000100000000000010000100000000001001110011
0000000000001001110011111010011110010100000000000000010110
0000000000000010010100000000000010010100000000001001110011
0000000000001001110011001110001000000100000000000000010110
0000000000000010100100000000000010100100000000001001110011
0000000000001001110011100111100111010100000000000000010110
0000000000000010110100000000000010110100000000001001110011
0000000000001001110010110110110110110100000000000000010110
0000000000000011000100000000000011000100000000001001110011
0000000000001001110011001010010100010100000000000000010110
0000000000000011010100000000000011010100000000001001110011
0000000000001001110011100011000101100100000000000000010110
0000000000000011100100000000000011100100000000001001110011
0000000000001001110011101110101001000100000000000000010110
0000000000000011110100000000000011110100000000001001110011
0000000000001001110010101000001000010100000000000000010110
0000000000000100000100000000000100000100000000001001110011
0000000000001001110011010001000011110100000000000000010110
0000000000000100010100000000000100010100000000001001110011
0000000000001001110011000000111101100100000000000000010110
0000000000000100100100000000000100100100000000001001110011
0000000000001001110010101001001001100100000000000000010110
0000000000000100110100000000000100110100000000001001110011
0000000000001001110010110000110001010100000000000000010110
0000000000000101000100000000000101000100000000001001110011
0000000000001001110011101100010000100100000000000000010110
0000000000000101010100000000000101010100000000001001110011
0000000000001001110010101001011011110100000000000000010110
0000000000000101100100000000000101100100000000001001110011
0000000000001001110010100111100011110100000000000000010110
0000000000000101110100000000000101110100000000001001110011
0000000000001001110011000001001000000100000000000000010110
0000000000000110000100000000000110000100000000001001110011
0000000000001001110011101111011100100100000000000000010110
0000000000000110010100000000000110010100000000001001110011
0000000000001001110010011000011100100100000000000000010110
0000000000000110100100000000000110100100000000001001110011
0000000000001001110011001100111111010100000000000000010110
0000000000000110110100000000000110110100000000001001110011
0000000000001001110011101001101000100100000000000000010110
0000000000000111000100000000000111000100000000001001110011
0000000000001001110011110111011110100100000000000000010110
0000000000000111010100000000000111010100000000001001110011
0000000000001001110010101001001111010100000000000000010110
0000000000000111100100000000000111100100000000001001110011
0000000000001001110010010010001111010100000000000000010110
0000000000000111110100000000000111110100000000001001110011
0000000000001001110010110000101110000100000000000000010110
0000000000001000000100000000001000000100000000001001110011
0000000000001001110011100100100111000100000000000000010110
0000000000001000010100000000001000010100000000001001110011
0000000000001001110011001101010111110100000000000000010110
0000000000001000100100000000001000100100000000001001110011
0000000000001001110010101101101111010100000000000000010110
0000000000001000110100000000001000110100000000001001110011
0000000000001001110010101101001001100100000000000000010110
0000000000001001000100000000001001000100000000001001110011
0000000000001001110011000111011000110100000000000000010110
0000000000001001010100000000001001010100000000001001110011
0000000000001001110010101010110001110100000000000000010110
0000000000001001100100000000001001100100000000001001110011
0000000000000000000011111111111111100011111111111111110001
0000000000000000000000000000000000000000000000000000000001
目視じゃ絶対無理ですね。
アセンブリにする
上記のデータはQFTASM(Quest For Tetris Assembly)という謎のアセンブリに変換できるようなので、この辺を参考にしながら変換する作業をしました。
#!/usr/bin/env python3.7
from bitstring import BitArray
inst_table = {
'0000': 'MNZ',
'0001': 'MLZ',
'0010': 'ADD',
'0011': 'SUB',
'0100': 'AND',
'0101': 'OR',
'0110': 'XOR',
'0111': 'ANT',
'1000': 'SL',
'1001': 'SRL',
'1010': 'SRA',
}
modes = {'00': '', '01': 'A', '10': 'B', '11': 'C'}
def conv_8bit_int(s):
a = BitArray('0b' + s)
return a.uint
with open('rom.txt') as f:
i = 1
for l in f:
l = l.strip()
# opcode
print('{}. {} '.format(i, inst_table[l[54:58]]), end='')
# val1
#print('{}{}({}) '.format(modes[l[36:38]], conv_8bit_int(l[38:54]), l[38:54]), end='')
print('{}{} '.format(modes[l[36:38]], conv_8bit_int(l[38:54]), l[38:54]), end='')
# val2
# print('{}{}({}) '.format(modes[l[18:20]], conv_8bit_int(l[20:36]), l[20:36]), end='')
print('{}{} '.format(modes[l[18:20]], conv_8bit_int(l[20:36]), l[20:36]), end='')
# val3
# print('{}{}({})'.format(modes[l[0:2]], conv_8bit_int(l[2:18]), l[2:18]))
print('{}{}'.format(modes[l[0:2]], conv_8bit_int(l[2:18]), l[2:18]))
i += 1
1. MLZ -1 44 43
2. XOR 0 0 2
3. MLZ -1 25971 2
4. MLZ -1 14554 3
5. MLZ -1 22445 4
6. MLZ -1 25411 5
7. MLZ -1 3743 6
8. MLZ -1 13391 7
9. MLZ -1 12059 8
10. MLZ -1 2554 9
11. MLZ -1 15823 10
12. MLZ -1 5921 11
13. MLZ -1 18009 12
14. MLZ -1 14823 13
15. MLZ -1 4757 14
16. MLZ -1 7754 15
17. MLZ -1 22480 16
18. MLZ -1 8371 17
19. MLZ -1 12418 18
20. MLZ -1 22738 19
21. MLZ -1 16499 20
22. MLZ -1 7132 21
23. MLZ -1 22793 22
24. MLZ -1 22307 23
25. MLZ -1 12485 24
26. MLZ -1 7936 25
27. MLZ -1 26630 26
28. MLZ -1 15483 27
29. MLZ -1 6471 28
30. MLZ -1 1806 29
31. MLZ -1 22705 30
32. MLZ -1 25019 31
33. MLZ -1 16442 32
34. MLZ -1 5145 33
35. MLZ -1 15593 34
36. MLZ -1 23867 35
37. MLZ -1 23738 36
38. MLZ -1 14086 37
39. MLZ -1 23123 38
40. MLZ -1 0 39
41. XOR A1 -27179 39
42. SUB A39 A2 2
43. XOR A1 -14018 39
44. SUB A39 A3 3
45. XOR A1 -22549 39
46. SUB A39 A4 4
47. XOR A1 -27735 39
48. SUB A39 A5 5
49. XOR A1 -225 39
50. SUB A39 A6 6
51. XOR A1 -15190 39
52. SUB A39 A7 7
53. XOR A1 -8339 39
54. SUB A39 A8 8
55. XOR A1 -1415 39
56. SUB A39 A9 9
57. XOR A1 -12768 39
58. SUB A39 A10 10
59. XOR A1 -6243 39
60. SUB A39 A11 11
61. XOR A1 -18725 39
62. SUB A39 A12 12
63. XOR A1 -13743 39
64. SUB A39 A13 13
65. XOR A1 -7402 39
66. SUB A39 A14 14
67. XOR A1 -4444 39
68. SUB A39 A15 15
69. XOR A1 -22495 39
70. SUB A39 A16 16
71. XOR A1 -12017 39
72. SUB A39 A17 17
73. XOR A1 -16138 39
74. SUB A39 A18 18
75. XOR A1 -22234 39
76. SUB A39 A19 19
77. XOR A1 -20283 39
78. SUB A39 A20 20
79. XOR A1 -5054 39
80. SUB A39 A21 21
81. XOR A1 -22161 39
82. SUB A39 A22 22
83. XOR A1 -22641 39
84. SUB A39 A23 23
85. XOR A1 -16096 39
86. SUB A39 A24 24
87. XOR A1 -4238 39
88. SUB A39 A25 25
89. XOR A1 -26510 39
90. SUB A39 A26 26
91. XOR A1 -13059 39
92. SUB A39 A27 27
93. XOR A1 -5726 39
94. SUB A39 A28 28
95. XOR A1 -2182 39
96. SUB A39 A29 29
97. XOR A1 -22211 39
98. SUB A39 A30 30
99. XOR A1 -28099 39
100. SUB A39 A31 31
101. XOR A1 -20296 39
102. SUB A39 A32 32
103. XOR A1 -7012 39
104. SUB A39 A33 33
105. XOR A1 -12961 39
106. SUB A39 A34 34
107. XOR A1 -21059 39
108. SUB A39 A35 35
109. XOR A1 -21210 39
110. SUB A39 A36 36
111. XOR A1 -14493 39
112. SUB A39 A37 37
113. XOR A1 -21817 39
114. SUB A39 A38 38
115. MLZ -1 -2 0
116. MLZ 0 0 0
上記のアセンブリをQFTASM Interpreterに食わせて動作させ実際にライフゲームで動作させたときと同様の結果になっていることを確認しました。
プログラムの内容は「A1(メモリの1番地)の値を利用して計算」しているようなので、このA1の値を変化させてあげるとフラグになる文字列が浮かび上がってきそう。
シミュレートする
C言語に落としてA1の値を探りました。
#include <stdio.h>
short b[44];
int main() {
// for (short s = -32768; s < 32767; s++) {
b[43] = 44;
b[1] = 28951; // s;
b[2] = 0 ^ 0;
b[2] = 25971;
b[3] = 14554;
b[4] = 22445;
b[5] = 25411;
b[6] = 3743;
b[7] = 13391;
b[8] = 12059;
b[9] = 2554;
b[10] = 15823;
b[11] = 5921;
b[12] = 18009;
b[13] = 14823;
b[14] = 4757;
b[15] = 7754;
b[16] = 22480;
b[17] = 8371;
b[18] = 12418;
b[19] = 22738;
b[20] = 16499;
b[21] = 7132;
b[22] = 22793;
b[23] = 22307;
b[24] = 12485;
b[25] = 7936;
b[26] = 26630;
b[27] = 15483;
b[28] = 6471;
b[29] = 1806;
b[30] = 22705;
b[31] = 25019;
b[32] = 16442;
b[33] = 5145;
b[34] = 15593;
b[35] = 23867;
b[36] = 23738;
b[37] = 14086;
b[38] = 23123;
b[39] = 0;
b[39] = b[1] ^ -27179;
b[2] = b[39] - b[2];
b[39] = b[1] ^ -14018;
b[3] = b[39] - b[3];
b[39] = b[1] ^ -22549;
b[4] = b[39] - b[4];
b[39] = b[1] ^ -27735;
b[5] = b[39] - b[5];
b[39] = b[1] ^ -225;
b[6] = b[39] - b[6];
b[39] = b[1] ^ -15190;
b[7] = b[39] - b[7];
b[39] = b[1] ^ -8339;
b[8] = b[39] - b[8];
b[39] = b[1] ^ -1415;
b[9] = b[39] - b[9];
b[39] = b[1] ^ -12768;
b[10] = b[39] - b[10];
b[39] = b[1] ^ -6243;
b[11] = b[39] - b[11];
b[39] = b[1] ^ -18725;
b[12] = b[39] - b[12];
b[39] = b[1] ^ -13743;
b[13] = b[39] - b[13];
b[39] = b[1] ^ -7402;
b[14] = b[39] - b[14];
b[39] = b[1] ^ -4444;
b[15] = b[39] - b[15];
b[39] = b[1] ^ -22495;
b[16] = b[39] - b[16];
b[39] = b[1] ^ -12017;
b[17] = b[39] - b[17];
b[39] = b[1] ^ -16138;
b[18] = b[39] - b[18];
b[39] = b[1] ^ -22234;
b[19] = b[39] - b[19];
b[39] = b[1] ^ -20283;
b[20] = b[39] - b[20];
b[39] = b[1] ^ -5054;
b[21] = b[39] - b[21];
b[39] = b[1] ^ -22161;
b[22] = b[39] - b[22];
b[39] = b[1] ^ -22641;
b[23] = b[39] - b[23];
b[39] = b[1] ^ -16096;
b[24] = b[39] - b[24];
b[39] = b[1] ^ -4238;
b[25] = b[39] - b[25];
b[39] = b[1] ^ -26510;
b[26] = b[39] - b[26];
b[39] = b[1] ^ -13059;
b[27] = b[39] - b[27];
b[39] = b[1] ^ -5726;
b[28] = b[39] - b[28];
b[39] = b[1] ^ -2182;
b[29] = b[39] - b[29];
b[39] = b[1] ^ -22211;
b[30] = b[39] - b[30];
b[39] = b[1] ^ -28099;
b[31] = b[39] - b[31];
b[39] = b[1] ^ -20296;
b[32] = b[39] - b[32];
b[39] = b[1] ^ -7012;
b[33] = b[39] - b[33];
b[39] = b[1] ^ -12961;
b[34] = b[39] - b[34];
b[39] = b[1] ^ -21059;
b[35] = b[39] - b[35];
b[39] = b[1] ^ -21210;
b[36] = b[39] - b[36];
b[39] = b[1] ^ -14493;
b[37] = b[39] - b[37];
b[39] = b[1] ^ -21817;
b[38] = b[39] - b[38];
// printf("s = %d: ", s);
for (size_t i = 3; i < 40; i++ ){
printf("%c", b[i-1] & 0xFF);
}
printf("\n");
// }
}
そしてフラグをゲット。
OOO{in_this_life___youre_on_your_own}
ただアセンブリのファイルをチームのSlackに上げたまま席を離れていたら、その間にほかのメンバーが先にフラグを見つけて回答してしまったためフラグを送れなかったのがちょっと悔しかったですｗ
そのほかの問題は全く手も足も出ず。バイナリーーーーーーーー
あと今年のDEFCONはSECCONっぽいなーと感じました。変な問題は好きなので個人的は好印象ですｗ