[AlpacaHack] Leaked Flag Checker Writeup

ひとこと

XORっていいよね

問題

情報

ジャンル: Rev
難易度: Easy 2.0
問題リンク: https://alpacahack.com/challenges/leaked-flag-checker

問題文

みんなだいすきフラグチェッカー

与えられたプログラム

// gcc -o challenge challenge.c
#include <stdio.h>
#include <string.h>

int main(void) {
    char input[32];
    const char xor_flag[] = "REDACTED";
    size_t flag_len = strlen(xor_flag);

    printf("Enter flag: ");
    fflush(stdout);
    scanf("%31s", input);

    if(strlen(input) != flag_len) {
        printf("Wrong length\n");
        return 1;
    }
    for(size_t i = 0; i < flag_len; i++) {
        if((input[i] ^ 7) != xor_flag[i]) {
            printf("Wrong at index %zu\n", i);
            return 1;
        }
    }
    printf("Correct\n");
    return 0;
}

XORとは何か?

XOR演算とは、2つのビットにおいて「同じなら0」「違ったら1」を返す演算です。

入力1	入力2	出力
0	0	0
0	1	1
1	0	1
1	1	0

またこれは整数に対しても行うことができます。
整数$a,b$があるとき、まずは$a,b$を二進数に直し、各ビットごとにXOR演算を行うことで任意の整数に対するXORができます。とはいえこんなこと言われてもわからないと思うので、例を見てみましょう。

4ビット符号なし整数である$2$と$11$のXORをするとします。
2を二進数に直すと$0010$、11を二進数に直すと$1011$になります。
これを表に並べて、各ビットごとにXORを適用すると以下のようになります。

$2^3$bit	$2^2$bit	$2^1$bit	$2^0$bit
0	0	1	0
1	0	1	1
1	0	0	1

これで出力の方を読んで$1001$を得て、十進法に直すと$9$を得ます。すなわち$2$と$11$のXORは$9$だとわかりました。

これの大きな特徴として、ある値に対してある値を二回XORすると元に戻るというのがあります。
なので、XORの演算を$\oplus$とすると、$a\oplus b\oplus b=a$ということです。
ためしに先ほど$2\oplus11$をして得た$9$にまた$11$をXORしてみると、$2$を得て、元に戻るということが分かります。

こういう性質があるから、XORを使った暗号とかがかなり普及してるわけですね。
で今回のコードもXORを使っています。

コードは何をしている?

#include <stdio.h>
#include <string.h>

int main(void) {
    char input[32];
    const char xor_flag[] = "REDACTED";
    size_t flag_len = strlen(xor_flag);

    printf("Enter flag: ");
    fflush(stdout);
    scanf("%31s", input);

    if(strlen(input) != flag_len) {
        printf("Wrong length\n");
        return 1;
    }
    for(size_t i = 0; i < flag_len; i++) {
        if((input[i] ^ 7) != xor_flag[i]) {
            printf("Wrong at index %zu\n", i);
            return 1;
        }
    }
    printf("Correct\n");
    return 0;
}

xor_flagという、何かでXORされたflagがここにあるわけです。

    for(size_t i = 0; i < flag_len; i++) {
        if((input[i] ^ 7) != xor_flag[i]) {
            printf("Wrong at index %zu\n", i);
            return 1;
        }
    }

^というのはXORの演算なので、
「すべての文字を7でXORしている」
ということが分かりました。しかし、XORされたflagがわかりません。

データの取得

実はGhidraというものを使うと、バイナリ(今回は実行ファイルのこと)に埋め込まれているデータを見ることができます。それをゲットしてXOR 7していけばいいですが、しかしそれでは面白くありません。
Ghidraで解析したい場合、authorさんのwriteupをご覧ください。

データはそこにある

データは(今回のケースの場合)絶対にどこかに埋め込まれていて、それはたいてい連続した領域です。だから与えられたバイナリを全部XOR 7して、意味のある文字列を検索するコマンド(stringsというもの)

$ python3 -c '
    import sys
    data = sys.stdin.buffer.read()
    sys.stdout.buffer.write(bytes(b ^ 7 for b in data))
' < challenge > output.bin
$ strings output.bin

そうするとなんかでてきます。

Alpaca{lO
{lucky}

ただなんか変なものとくっついている気がする(終端文字がなくなっちゃってるからかな?)ので、Alpacaと{lucky}をくっつけると、通りました。

絶対正攻法じゃないので、よいこの皆さんはちゃんとしたツールを使いましょう。