# stratum [InterKosenCTF 2020]
###### tags: `InterKosenCTF2020` `reversing`

## 概要

小さなELF。入力に対して加工をおこなった出力を返してくる。同じ入力に対しては同じ出力を返す。フラグ入力の出力が与えられているので入力を推測する。

みたことのない命令がいくつかあるけど、調べればなんとかわかる。`pshufb`だけ、個人的にかなりわかりにくかったのでpythonで書く。 `pshufb xmm0, xmm1, xmm2` は16バイトの入力`xmm1, xmm2`を受け取って次の通り

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]`がわかった前提での残りの入力の計算パートになる。

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)