ångstrom CTF 2021 writeup
はじめに
取り急ぎcryptoのThunderboltだけ書きます。
初心者向けの問題も数多くあるので、そちらに関しては別途、より詳細に(本当の初心者向けに)書きます。
Thunderbolt
リード文はなし。challというファイルのみが与えられます。GitHubにあげる予定です。まずはサーバに接続してみます。
$ nc crypto.2021.chall.actf.co 21603 Enter a string to encrypt:
適当に入力すると、暗号化されたものが返ってきて終了します。
$ nc crypto.2021.chall.actf.co 21603 Enter a string to encrypt: 123 754e7a660e985cdd02b93048ea48a3a63d87957f98c5b16c946532b8ac7c8139fd69dc4213cab549612f3907c80cd10c7c88ffdcd6f30ddfe15c $ nc crypto.2021.chall.actf.co 21603 Enter a string to encrypt: 123 b20471de14ce8d195a47d8e664f87e2bddd265e97b1da3e04390008f27808d86a1f8e6229afaff738def39de46c68bb3b1504df7992d69708526
さすがにランダムです。では実行ファイルの方を覗きます。
自分はファイル名をthunderbolt_challにしています。皆さんは適宜読み替えてください。
$ file ./thunderbolt_chall ./thunderbolt_chall: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=20796fc93de5d7a1f441ff3f2900fc75f1ddf2ea, for GNU/Linux 3.2.0, not stripped
ELFファイルなのでgdbで動的解析することになりそうです。ちなみに、あまりバイナリは得意ではないのでチームメイトに色々と指南をいただきました。
あと、せっかくなのでghidraのデコンパイラも使ってみようと思います。最初はあまり役に立たないかなと思っていましたが、結果的にめちゃくちゃ便利でした。笑
導入方法はGhidraの使い方 | 初心者がリバースエンジニアリングツールGhidraを使ってみたからどうぞ。
ghidra起動～main関数解析
$ objdump -d ./thunderbolt_challでも分かりますが、main関数は.textのセクションにあるので、左のProgram Treesから.textをダブルクリック。
すると、左側のDecompileの部分にC言語らしきものが表示されます。
undefined8 main(void) { byte bVar1; size_t sVar2; FILE *pFVar3; size_t sVar4; void *__ptr; void *__ptr_00; byte *__ptr_01; undefined8 uVar5; byte *pbVar6; int iVar7; char *local_158; size_t local_150; undefined local_148 [16]; char local_138 [264]; setvbuf(stdout,(char *)0x0,2,0); local_158 = (char *)0x0; printf("Enter a string to encrypt: "); local_150 = 0; getline(&local_158,&local_150,stdin); sVar2 = strcspn(local_158,"\n"); pFVar3 = fopen("flag","rb"); if (pFVar3 == (FILE *)0x0) { puts("Could not open flag file."); uVar5 = 1; } else { fgets(local_138,0x100,pFVar3); sVar4 = strcspn(local_138,"\n"); iVar7 = (int)sVar4 + (int)sVar2; local_138[(int)sVar4] = '\0'; __ptr = realloc(local_158,(long)(iVar7 + 1)); sVar4 = SEXT48(iVar7); strcpy((char *)((long)(int)sVar2 + (long)__ptr),local_138); pFVar3 = fopen("/dev/urandom","rb"); fread(local_148,0x10,1,pFVar3); __ptr_00 = malloc(sVar4); fread(__ptr_00,sVar4,1,pFVar3); fgen(__ptr_00,local_148,sVar4,0x10); __ptr_01 = (byte *)malloc(sVar4); enc(__ptr,__ptr_01,sVar4); if (0 < iVar7) { pbVar6 = __ptr_01; do { bVar1 = *pbVar6; pbVar6 = pbVar6 + 1; printf("%02x",(ulong)bVar1); } while (pbVar6 != __ptr_01 + (ulong)(iVar7 - 1) + 1); } putchar(10); free(__ptr_00); free(__ptr); free(__ptr_01); uVar5 = 0; } return uVar5; }
setvbufやstrcspnなど分からないものは調べてください。
また、ここでは厳密な話は抜きにします。「そこはポインタだろ」みたいなツッコミはなしでお願いします。
要約すると、
if文直前まで :
local_158: stdinからの入力sVar2: stdinからの入力の長さ
if文 :
"flag"という名前のファイルが開けなければ終了else文,
sVar4 = SEXT48(iVar7);まで :sVar4: (flagの長さ) + (stdinからの入力の長さ)
else文,
fgen直前まで :__ptr: (stdinからの入力) + flaglocal_148:"/dev/urandom"から16 bytesのランダム値__ptr_00:"/dev/urandom"からsVar4bytesのランダム値
fgen: 引数は順に「sVar4bytesのランダム値、16 bytesのランダム値、sVar4、16」__ptr_01: 長さsVar4の空文字列enc: 引数は順に「 (stdinからの入力) + flag、__ptr_01、sVar4」残り :
__ptr_01出力
ghidraの真ん中のListingを見たらわかりますが、fgenとencだけピンク色になっているので、自作の関数ということです。
この詳細は後で追います。
ここまででもかなり分かりにくいので、Python風に例をあげると(めちゃくちゃ省略してますが)
import os _stdin = 'abcd' flag = 'actf{hogehoge}' sVar4 = len(_stdin + flag) fgen(os.urandom(sVar4), os.urandom(16), sVar4, 16) c = enc(_stdin+flag, sVar4) print(c)
こんな感じでしょうか。これだけ見るとシンプルです。
さて、if文でもある通り"flag"というファイルがないとローカル環境で動かないので、適当に作成しておきます。
$ echo "actf{hogehoge}" > ./flag
fgen解析
ここからはfgenを見ていきます。ghidraのListingの所のfgenをダブルクリックすると、fgenのデコンパイル結果が表示されます。
void fgen(long param_1,long param_2,ulong param_3,ulong param_4) { int iVar1; long lVar2; ulong uVar3; uint uVar4; ulong uVar5; ulong uVar6; ulong uVar7; /* (1) */ lVar2 = 0; do { *(int *)(f + lVar2 * 4) = (int)lVar2; lVar2 = lVar2 + 1; } while (lVar2 != 0x100); /* (2) */ uVar3 = (ulong)s; uVar6 = 0; do { uVar7 = uVar6 & 0xff; uVar5 = uVar6 + 1; iVar1 = (uint)*(byte *)(param_1 + uVar6 % param_3) + (int)uVar3 + *(uint *)(f + uVar7 * 4); uVar4 = (uint)(iVar1 >> 0x1f) >> 0x18; uVar3 = SEXT48(*(int *)(f + (long)(int)((iVar1 + uVar4 & 0xff) - uVar4) * 4)); uVar4 = *(uint *)(f + uVar7 * 4) ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar7 * 4) = uVar4; uVar4 = uVar4 ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar3 * 4) = uVar4; *(uint *)(f + uVar7 * 4) = *(uint *)(f + uVar7 * 4) ^ uVar4; uVar6 = uVar5; } while (uVar5 != 0x300); /* (3) */ uVar6 = 0; do { uVar5 = uVar6 & 0xff; uVar7 = uVar6 + 1; iVar1 = (uint)*(byte *)(param_2 + uVar6 % param_4) + (int)uVar3 + *(uint *)(f + uVar5 * 4); uVar4 = (uint)(iVar1 >> 0x1f) >> 0x18; s = *(uint *)(f + (long)(int)((iVar1 + uVar4 & 0xff) - uVar4) * 4); uVar3 = SEXT48((int)s); uVar4 = *(uint *)(f + uVar5 * 4) ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar5 * 4) = uVar4; uVar4 = uVar4 ^ *(uint *)(f + uVar3 * 4); *(uint *)(f + uVar3 * 4) = uVar4; *(uint *)(f + uVar5 * 4) = *(uint *)(f + uVar5 * 4) ^ uVar4; uVar6 = uVar7; } while (uVar7 != 0x300); return; }
こちらはどちらかというと数式演算処理がほとんどです。以下にPythonで書き直したコードをあげますが、結構似通っていると思います。
対応関係は上のC言語のコメントアウトの部分を参照してください。また、見やすさのためuVar6だけはPython内でiに書き換えています。
def fgen(__ptr_00, local_148, ptr_len): s = 0 f = [0] * 0x100 # (1) lVar2 = 0 while True: f[lVar2] = lVar2 lVar2 +=1 if lVar2 == 0x100: break # (2) uVar3 = s i = 0 while True: l = len(set(f)) uVar7 = i & 0xff uVar5 = i + 1 iVar1 = (__ptr_00[i % ptr_len]) + uVar3 + f[uVar7] # uVar4ほぼ0では？ uVar4 = (iVar1 >> 0x1f) >> 0x18 uVar3 = f[(iVar1 + uVar4 & 0xff) - uVar4] # ここからfの書き換え？ uVar4 = f[uVar7] ^ f[uVar3] f[uVar7] = uVar4 uVar4 = uVar4 ^ f[uVar3] f[uVar3] = uVar4 f[uVar7] = f[uVar7] ^ uVar4 i = uVar5 if uVar5 == 0x300: break # (3) i = 0 while True: l = len(set(f)) uVar5 = i & 0xff uVar7 = i + 1 iVar1 = local_148[i % 16] + uVar3 + f[uVar5] # uVar4ほぼ0では？ uVar4 = (iVar1 >> 0x1f) >> 0x18 s = f[(iVar1 + uVar4 & 0xff) - uVar4] uVar3 = s # ここからfの書き換え？ uVar4 = f[uVar5] ^ f[uVar3] f[uVar5] = uVar4 uVar4 = uVar4 ^ f[uVar3] f[uVar3] = uVar4 f[uVar5] = f[uVar5] ^ uVar4 i = uVar7 if uVar7 == 0x300: break return f, s
C言語の方を見て最初に思ったのが、「fとかsってどこから登場したの？ローカル変数じゃないの？」という事です。
main関数にもfgen関数にも特にint s;のような型定義が書かれていないので、おそらく初期値0のグローバル変数なんだろうと思って読み進めています(Pythonではローカル変数のように扱っていますがreturn f, sで察してください)。
さてさて、fgenの中身を見ていきます。
(1)は大丈夫だと思います。f = [0, 1, ..., 255]にしているだけです。(2)と(3)でfの値をちょくちょく変更しているようですね。
なお、(2)と(3)の違いですが、変数名は少し違うものの、
__ptr_00(os.urandom(sVar4))を使うかlocal_148(os.urandom(16))を使うかsを更新するか
しかありません。
関数の名前にもある通り、fとsをランダム値に基づいて生成しているようです。続いて、(2)の
uVar4 = f[uVar7] ^ f[uVar3]
f[uVar7] = uVar4
uVar4 = uVar4 ^ f[uVar3]
f[uVar3] = uVar4
f[uVar7] = f[uVar7] ^ uVar4
に注目します。これをもう少し分かりやすく書くと
val1 = f[i] ^ f[j] f[i] = val1 val2 = val1 ^ f[j] # val2 : 書き換え前のf[i] f[j] = val2 # f[j] : 書き換え前のf[i] f[i] = f[i] ^ val2 # f[i] : 書き換え前のf[j]
「ただスワップ」してるだけです。(3)も同じです。
この時点でfとsがどうなっているかをgdbで見てみましょう。
余談ですが、自分はgdb-pedaをいれています。導入の仕方はgdb-peda超入門をどうぞ。
操作としては、
$ gdb -q ./thunderbolt_chall # gdb起動 gdb-peda$ b main # main関数にブレークポイントを張る gdb-peda$ r # 実行 gdb-peda$ disas fgen # fgenをディスアセンブル
になります。結果はこんな感じです。
毎度見にくくて申し訳ないです。
fは0x5555555580c0に、sは0x5555555584c0に存在するようです(このアドレス情報はいらないですが、fとsが定義されていることを確認するために載せました)。
では改めて、中身を覗きます。
コマンドは
gdb-peda$ b *fgen+230 # fgenの最終行(disas fgenの結果からわかる)にブレークポイント gdb-peda$ c # 続行 (Enter a string to encrypt: が表示されるので、`abcd`など適当に文字を入力する) gdb-peda$ x/256wx &f # fの中身を表示 gdb-peda$ x/wx &s # sの中身を表示
です。x/256wxは(あまり自分がバイナリ分かってないのもあって)試行錯誤だったりします。
257にしたらsの中身も表示されたので、結果的に256にして「0~255までを各4 bytesのサイズで格納しているんだ」と分かった次第です。
結果はこんな感じ。いい感じにfがバラバラになっています。
ちなみにですが、(1)が終わってf = [0, 1, 2, ..., 255]と整列しているはずです。
これを念のため確認したい用心深い人は(自分です)
gdb-peda$ b *fgen+39 # (1)を抜けた直後にブレークポイント。disas fgenでjne命令が3つありますが、これが全てwhile文を抜ける条件です gdb-peda$ r # 再実行 gdb-peda$ c # fgen+39の直前まで再実行 (Enter a string to encrypt: が表示されるので、`abcd`など適当に文字を入力する) gdb-peda$ x/256wx &f # fの中身を表示
とすれば0からきれいに並んでいることが確認できます。リトルエンディアン(逆順)であることに注意です。
enc解析
さて、続いてencです。デコンパイル結果は以下のようです。
void enc(long param_1,long param_2,long param_3) { uint uVar1; int iVar2; long lVar3; ulong uVar4; uint uVar5; long lVar6; uint uVar7; if (param_3 != 0) { uVar4 = (ulong)s; lVar6 = 0; uVar5 = 0; do { lVar3 = (long)(int)uVar5; iVar2 = (int)uVar4 + *(int *)(f + lVar3 * 4); uVar5 = uVar5 + 1 & 0xff; uVar7 = (uint)(iVar2 >> 0x1f) >> 0x18; s = *(uint *)(f + (long)(int)((iVar2 + uVar7 & 0xff) - uVar7) * 4); uVar7 = (uint)(*(int *)(f + (long)*(int *)(f + (long)(int)s * 4) * 4) + 1 >> 0x1f) >> 0x18; *(byte *)(param_2 + lVar6) = (byte)*(undefined4 *) (f + (long)(int)((*(int *)(f + (long)*(int *)(f + (long)(int)s * 4) * 4) + 1 + uVar7 & 0xff) - uVar7) * 4) ^ *(byte *)(param_1 + lVar6); uVar4 = SEXT48((int)s); lVar6 = lVar6 + 1; uVar7 = *(uint *)(f + lVar3 * 4); uVar1 = *(uint *)(f + uVar4 * 4); *(uint *)(f + lVar3 * 4) = uVar7 ^ uVar1; uVar7 = uVar7 ^ uVar1 ^ *(uint *)(f + uVar4 * 4); *(uint *)(f + uVar4 * 4) = uVar7; *(uint *)(f + lVar3 * 4) = *(uint *)(f + lVar3 * 4) ^ uVar7; } while (param_3 != lVar6); return; } return; }
これも数式多めなのでPythonで似たように書けます。uVar6だけiに変換していて、引数にf, sを追加しています。
def enc(m, c, len_m, f, s): if len_m != 0: uVar4 = s i = 0 uVar5 = 0 while True: # (4) l = len(set(f)) lVar3 = uVar5 iVar2 = uVar4 + f[lVar3] uVar5 = uVar5 + 1 & 0xff uVar7 = (iVar2 >> 0x1f) >> 0x18 s = f[(iVar2 + uVar7 & 0xff) - uVar7] uVar7 = (f[f[s]] + 1 >> 0x1f) >> 0x18 c[i] = f[(f[f[s]] + 1 + uVar7 & 0xff) - uVar7] ^ m[i] uVar4 = s i += 1 # (5) # fgenと少し書き方が違うがスワップしてるだけ uVar7 = f[lVar3] uVar1 = f[uVar4] f[lVar3] = uVar7 ^ uVar1 uVar7 = uVar7 ^ uVar1 ^ f[uVar4] f[uVar4] = uVar7 f[lVar3] = f[lVar3] ^ uVar7 if len_m == i: break return c print('enc error') return [-1]
ここでもf, sの値を書き換えたりしていますが、暗号化フェーズは実はc[i] = f[(f[f[s]] + 1 + uVar7 & 0xff) - uVar7] ^ m[i]だけです。
さらに、(4)のuVar7についてはfgenと同じようにuVar7 = (iVar2 >> 0x1f) >> 0x18で(0x1f + 0x18) bits右シフトなのでよほどのことがない限り0だと思ってよいです。
心配性の人はassert(uVar7 == 0)としたらいいと思います((5)では成り立ちません。どこにassertを挿入するかは気を付けてください)。
なので、暗号化は実質c[i] = f[f[f[s]] + 1 & 0xff] ^ m[i]というXORです。
ここで1つ注意ですが、+の方が&より先に計算されます。これに気付かず自分は結構時間を溶かしました。
また、(5)のfの書き換えも実は「ただのスワップ」です。
ここまでをまとめると、
fgenもencもランダム値に基づいてfおよびsの値を変更している暗号化方式は
fテーブルをもとにXORをとっているだけ
攻撃方法の模索
さて、どう攻撃を仕掛けるかですが、
/dev/urandomの擬似ランダム性につけこむ → 無理。検索してもヒットせずどこがスワップされるかを見極める → 要は
/dev/urandomで生成される値を見破る必要がある。これも無理
(え、無理じゃん。)
ここで何度かgdbを動かしつつfを眺めていたわけですが、ある時こんなことが起きます。
telコマンドもx/256wxとほぼ変わらないと思ってもらってOKです。また、0x5555555580c0はfのアドレスです。
gdb-peda$ tel 0x5555555580c0 128
0000| 0x5555555580c0 --> 0xe70000001a
0008| 0x5555555580c8 --> 0x4a0000005f ('_')
0016| 0x5555555580d0 --> 0x6e0000009b
0024| 0x5555555580d8 --> 0x7c0000003b (';')
0032| 0x5555555580e0 --> 0x50000003c
0040| 0x5555555580e8 --> 0x8d000000c0
0048| 0x5555555580f0 --> 0x90000006c ('l')
0056| 0x5555555580f8 --> 0x180000001d
0064| 0x555555558100 --> 0xba00000025
0072| 0x555555558108 --> 0x50000000fd
0080| 0x555555558110 --> 0x45000000e1
0088| 0x555555558118 --> 0x7600000096
0096| 0x555555558120 --> 0xbb
0104| 0x555555558128 --> 0x6900000006
0112| 0x555555558130 --> 0x3f0000003e ('>')
0120| 0x555555558138 --> 0x8f000000d4
0128| 0x555555558140 --> 0xbd0000004e
...
0416| 0x555555558260 --> 0xa10000002a
0424| 0x555555558268 --> 0x90
0432| 0x555555558270 --> 0x65000000b8
0440| 0x555555558278 --> 0xcd0000005a
...
0xbbと0x90…？
これって0が省略されているから実質0x00000000_000000bbと0x00000000_00000090で、fの中に0が2回登場している…？
「ただのスワップ」ではなかった
というわけで、先ほどのコード
val1 = f[i] ^ f[j] f[i] = val1 val2 = val1 ^ f[j] # val2 : 書き換え前のf[i] f[j] = val2 # f[j] : 書き換え前のf[i] f[i] = f[i] ^ val2 # f[i] : 書き換え前のf[j]
をよく見ると、i != jなら「ただのスワップ」ですが、i == jの時はval1, val2とも0です。
つまり強制的にf[i] = 0にしているわけです。
ということは、乱数(あるいはstdinからの入力)をとても長くとれば、その分相対的にi == jとなる回数が多くなり、fの中身を0ばかりにできるのでは？
試しにやってみます。一旦gdb-peda$ qで終了して、余計なブレークポイントなどを消した後、以下を実行。
$ printf "%0*d\n" 10000 > gdb_in.txt # 10000文字の'0'をgdb_in.txtに保存 $ gdb -q ./thunderbolt_chall # gdb起動 gdb-peda$ b main # main関数にブレークポイントを張る gdb-peda$ r < gdb_in.txt # stdinに渡す文字列をgdb_in.txtからリダイレクトして実行 gdb-peda$ b *main+340 # encの直後にブレークポイントを張る。+340の値はdisas mainで確認可能 gdb-peda$ c # main+340まで続行 gdb-peda$ x/256wx &f
10000字だと全部とまではいかないものの、目視で複数確認できるくらいにはゼロが多くなりました。
fの要素がゼロになれば、暗号化フェーズc[i] = f[f[f[s]] + 1 & 0xff] ^ m[i]が実質c[i] = 0 ^ m[i] = m[i]になります。
これはほぼ勝ちです。
ソルバ
大枠は以下のようになります。
from pwn import * from Crypto.Util.number import long_to_bytes io = remote('crypto.2021.chall.actf.co', 21603) io.recvuntil(': ') io.sendline('A'*40000) print(long_to_bytes(int(io.recvline()[:-1], 16))) io.close()
40000字でも完全にfがゼロになる保証はないので、ここで表示されるものが100%正しいとは限りません(実際、一回弾かれました)。
しかし、ほぼ答えが表示されるうえに、flagの長さが55文字だとわかる(これは勘が良ければデコンパイルしなくても気付ける)ので5回ほど接続してラスト55 bytesだけを比較すればよいでしょう。
以下が最終的なソルバになります。
from pwn import * from Crypto.Util.number import long_to_bytes flag_ls = [] for _ in range(5): io = remote('crypto.2021.chall.actf.co', 21603) io.recvuntil(': ') io.sendline('A'*40000) flag_ls.append(long_to_bytes(int(io.recvline()[-111:-1], 16))) io.close() for flag in flag_ls: print(flag)
actf{watch_the_edge_cases_31b2eb7440e6992c33f3e5bbd184}
ソルバだけ見たら簡潔ですね…
