Mirage — Daily AlpacaHack

TL;DR

• 入力 19 文字を判定するルーチンが、内部 state を毎回 step() で進めながら下位 7bit と XOR して固定の enc[] と比較する
• step() は state にだけ依存する
• 初期 state (0xACE1) も多項式もハードコードされているので state の進み方は毎回固定
• buf[i] = enc[i] ^ (step したあとの state & 0x7F) を順に計算すればOK

ソースから

uint16_t step(uint16_t s) {
    uint16_t bit = ((s >> 0) ^ (s >> 2) ^ (s >> 3) ^ (s >> 5)) & 1;
    return (s >> 1) | (bit << 15);
}

// ...

uint16_t state = 0xACE1;
for (int i = 0; i < N; i++) {
    state = step(state);
    if (((uint8_t)buf[i] ^ (state & 0x7F)) != enc[i]) {
        printf("wrong\\n");
        return 1;
    }
}

step() はなんだか難しい話をしているが、出力が s に依存している以外に、特に気にしなくてよい。

今回の if 文の式 (buf[i] ^ (state & 0x7F)) == enc[i] は buf[i] について解けば

buf[i] = enc[i] ^ (state & 0x7F)

になるので、あとは state の変わり方がわかれば良さそう。初期の state と、毎回の state に対する操作 uint16_t state = 0xACE1 が既知なので、これを利用すればよい。

細かく

1. 先頭バイトで答え合わせ

ところで、AlpacaHack のフラグは Alpaca{...} から始まる。だから buf[0] = 'A' = 0x41 になるはずで、これと enc[0] = 0x31 から、step(0xACE1) & 0x7F == 0x41 ^ 0x31 == 0x70 になっていればよい。

試しに手計算で step(0xACE1) を計算すると以下になる。

0xACE1 = 1010 1100 1110 0001
bit = b0 ^ b2 ^ b3 ^ b5 
    = 1 ^ 0 ^ 0 ^ 1 
    = 0
new_state = (0xACE1 >> 1) | (0 << 15) 
          = 0x5670

0x5670 & 0x7F = 0x70

よって 'A' (0x41) ^ 0x70 = 0x31 = enc[0] が成り立つ。この方針でよいことがわかる。

2. 同じ計算をする

あとは C の step() と同じ操作をする。各 i について state を 1回計算してから enc[i] ^ (state & 0x7F) を取ることを繰り返せばよい。