# stratum [InterKosenCTF 2020] ###### tags: `InterKosenCTF2020` `reversing` ## 概要 小さなELF。入力に対して加工をおこなった出力を返してくる。同じ入力に対しては同じ出力を返す。フラグ入力の出力が与えられているので入力を推測する。 みたことのない命令がいくつかあるけど、調べればなんとかわかる。`pshufb`だけ、個人的にかなりわかりにくかったのでpythonで書く。 `pshufb xmm0, xmm1, xmm2` は16バイトの入力`xmm1, xmm2`を受け取って次の通り ```python= def pshufb(xmm1, xmm2): output = [0 for _ in range(16)] for i in range(16): output[i] = xmm1[ xmm2[i] & 15 ] return output ``` ## 解法 さて処理だが、入力を16バイト毎に区切って`xmm`レジスタに入れて加工している。区切られた入力を `input[0], input[1], ...` と表すとして、次の処理がループしている 1. xmm1 = “asdfghjklzxcvbnm” 2. xmm2 = input[i] 3. xmm3 = input[i+1] 4. outbuf += pshufb(xmm1, xmm2) 5. for i in range(16): outbuf += (popcnt(xmm2[i]) << 4 | lzcnt(xmm2[i])) $\oplus$ xmm3[i] つまり16バイトの入力`input[i]`に対して、出力は`output[2*i] + output[2*i+1]`の32バイトになる。 `output[2]`、すなわち`input[1]`に対する`pshufb` の結果を逆算してやれば、`input[1]`の下位4bitずつが手に入る。この下位4bitを`output[1]`の下位4bitとXORすれば、`input[0]`のlzcntが手に入る。 `output[0]`の`pshufb`も逆算すれば、`input[0]`の下位4bitとlzcntが手に入るので、`input[0]`の入力の候補を列挙できる。組み合わせの数は大したことがないはずだし、フラグであることを考えて意味の有りそうな候補を選択すれば、 `input[0]` が決まる。 `input[i]`がわかっている時、`output[2*i+1]`から`input[i+1]`が簡単に求まる(`input[i]`のpopcntとlzcntを求めてXORするだけなので)。 以下のスクリプトではコメントで区切った前半が`input[0]`の決定パート、後半が`input[0]`がわかった前提での残りの入力の計算パートになる。 ```python= output = open("flag.enc", "rb").read() key = [ord(c) for c in "asdfghjklzxcvbnm"] input1_4bit = [0 for _ in range(16)] for i in range(16): input1_4bit[i] = key.index(output[i]) input2_4bit = [0 for _ in range(16)] for i in range(16): input2_4bit[i] = key.index(output[32 + i]) lzcnt1 = [0 for _ in range(16)] for i in range(16): lzcnt1[i] = (output[16 + i] & 15) ^ input2_4bit[i] for i in range(16): for c in range(0x20, 0x7f): if (c & 15) != input1_4bit[i]: continue lead_zero = 0 b = "{:08b}".format(c) while b[lead_zero] == "0": lead_zero += 1 if lead_zero != lzcnt1[i]: continue print(chr(c), end="|") print("") # --------------------- flag = "KosenCTF{h4v3_fu" last_input = flag for k in range(3): next_input = "" for i in range(16): b = "{:08b}".format(ord(last_input[i])) popcnt = b.count("1") lzcnt = 0 while b[lzcnt] == "0": lzcnt += 1 mask = (popcnt << 4) | lzcnt next_input += chr(output[16 + 32 * k + i] ^ mask) flag += next_input last_input = next_input print(flag) ```