TastelessCTF 2019 に参加したので、[Crypto] babypad という問題をどう解いたかを解説します。

こんにちは。ロックです。

先日、TastelessCTF 2019に参加しました。この記事では、なんとか解くことが出来た問題 [Crypto] babypadについてお話します。

ctftime.org

TastelessCTF 2019 の所感

f:id:ishiyamacocoa:20191108162603p:plain — 終わった後の問題毎のスコア表。

いやー、難しかったです。

この後解説する予定の [Crypto] babypad もそこそこ手こずりましたが、他の問題については全く手も足も出ない結果になってしまいました。

CTFが終わってから各問題のスコアを見た時に「やはり難しかったのか」と感じて、嬉しいような悲しいような。

f:id:ishiyamacocoa:20191108164502p:plain — 157チーム中48位でした！

順位自体は48位。

精進して頑張っていきたいと思います。

というわけで、なんとか解くことが出来た問題 [Crypto] babypadについて話していきます！！

[Crypto] babypad

f:id:ishiyamacocoa:20191108164643p:plain — [Crypto] babypad の問題

実は、別の問題 [misc] sanity にてPoWファイルが渡されています。 ./pow connect hitme.tasteless.eu 10401 のようにアクセスして、いろいろできる感じです。

さて、さっそく、 chall.c の中身を見てみましょうか。

chall.c

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

int main() {
    char *plaintext = NULL;
    char *one_time_pad = NULL;
    char *ciphertext = NULL;
    size_t flag_length = 0;
    FILE *flag = fopen("flag.txt", "r");
    FILE *urandom = fopen("/dev/urandom", "r");
    assert(flag && urandom);

    /*
     * Get flag length, and allocate memory for the plaintext,
     * one-time pad and ciphertext.
     */
    fseek(flag, 0, SEEK_END);
    flag_length = ftell(flag);
    rewind(flag);

    plaintext = malloc(flag_length + 1);
    one_time_pad = malloc(flag_length + 1);
    ciphertext = malloc(flag_length + 1);
    assert(plaintext && one_time_pad && ciphertext);

    /* Read the plaintext and the one-time-pad */
    fread(plaintext, flag_length, 1, flag);
    fread(one_time_pad, flag_length, 1, urandom);
    plaintext[flag_length] = '\0';
    one_time_pad[flag_length] = '\0';

    /* Make sure that the one-time-pad isn't too short. */
    assert(strlen(plaintext) == strlen(one_time_pad));

    for (int i = 0; i < flag_length; i++) {
        ciphertext[i] = plaintext[i] ^ one_time_pad[i];
    }

    fwrite(ciphertext, flag_length, 1, stdout);
    return 0;
}

1. [観察] とりあえず怪しいところは。。。

ciphertext[i] = plaintext[i] ^ one_time_pad[i];

ここの部分で暗号文を作っているようですね。

^ は XOR演算を示しています。

one_time_pad が何者かと見てみると、

fread(one_time_pad, flag_length, 1, urandom);

urandom を読み込んでいますね。

urandom は、

FILE *urandom = fopen("/dev/urandom", "r");

これですね。

ということで分かったことは、平文と one_time_pad 即ち urandom (ランダムに生成された文字列) をXORしているということです。

2. [調査] そもそも one_time_pad ってなんだ。あと urandom お前もだ。

ワンタイムパッドについて

ワンタイムパッド - Wikipedia

理論的には、正しく運用された場合に解読不可能となる。たとえ総当たりで解読しようとしても、総当たりで生成される多数の文章(文字列)の中には、送信者が暗号化した文章以外にも、人間が意味を読み取れる文章（文字列）が生成されてしまう。

解読できないらしい、無理だ、敗北か。

urandomについて

random - スペシャルファイル (デバイス)の説明 - Linux コマンド集一覧表

/dev/random はワンタイムパッド (one-time pad) や鍵の生成のような非常に高い品質を持った無作為性が必要になる場合に適切であろう。エントロピー・プールが空の時は、/dev/random からの読み出しは、更なる環境ノイズが得られるまで、ブロックされる。

/dev/urandom デバイスから読み出しでは、エントロピーがより高くなるのを待つためのブロックは行われない。その結果、もしエントロピー・プールに十分なエントロピーが存在しない場合、返り値はこのドライバで使われているアルゴリズムに基づく暗号攻撃に対して、論理的には弱くなることになる。この攻撃をどのように行うかという事については、現在研究論文などの形で入手できる資料はない、しかし、そのような攻撃は論理的に存在可能である。もし、この事が心配なら、(/dev/urandom ではなく) /dev/random を利用すればいい。

なるほど、ワンタイムパッドでは通常、 random を用いるらしい。

3. [考察] 突破口を考える……まず押さえておくべき重要なことは？

ciphertext[i] = plaintext[i] ^ one_time_pad[i];

試しに、 plaintext[i] = 's' に対して 0x00から0xFF で XOR してみましょう。

この時に重要なのは、s XOR NULL(0x00) を計算すると s を示す、ということです。

以下は、「 plaintext[i] = 's' (0x73) に対する暗号化( 今回は XOR )結果」の表です。

one_time_pad[i]	ciphertext[i]
`0x00`	`0x73 ('s')`
`0x01`	`0x72`
...	...
`0xFF`	`0x8C`

ここからが本題です。

4. [さらに考察] 突破口を考える……そうだ、なるほど、もしかして？

chall.c をもう一度見てみましょう。

すると、気になる部分を発見しました。

    /* Make sure that the one-time-pad isn't too short. */
    assert(strlen(plaintext) == strlen(one_time_pad));

ついでに strlen についても調べてみましょう。

Man page of STRLEN

strlen() 関数は文字列 s の長さを計算する。このとき、終端ヌルバイト ('\0') は計算に含まれない。

これらを踏まえて考えると、chall.c の assert(strlen(plaintext) == strlen(one_time_pad)); は、

plaintext と one_time_pad の長さが合わない場合（つまり NULL(0x00) が one_time_pad に含まれている場合）はアサートで落とす、ということ意味しているのです！

    /* Make sure that the one-time-pad isn't too short. */
    assert(strlen(plaintext) == strlen(one_time_pad)); /* <--- ここで one_time_pad に NULL(0x00) が含まれていたら落とされる */

    for (int i = 0; i < flag_length; i++) {
        ciphertext[i] = plaintext[i] ^ one_time_pad[i]; /* <--- つまり、ここの one_time_pad にはどうやっても NULL(0x00) は含まれない！*/
    }

従って、 XORする時の one_time_pad に NULL(0x00) は含まれないということが分かります。

[考察] の「 plaintext[i] = 's' (0x73) に対する暗号化( 今回は XOR )結果」の表を更新してみましょう。

one_time_pad[i]	ciphertext[i]
~~`0x00`~~	~~`0x73 ('s')`~~
`0x01`	`0x72`
...	...
`0xFF`	`0x8C`

一般的なワンタイムパッドであれば、 0x00~0xFF との XOR の結果が出力されるのに対して、今回の chall.c は strlen のアサートを挟んでしまったために、 0x00 との XOR が出力されなくなっているという状況になります。

従って、どうやっても現れない文字が1つだけ存在すると断言できます。

余計なアサートさえ入れなければ安全だったのに……ということですね。

このことが今回の babypad という問題の本質だったわけです。

さて、このように、どうやっても現れない文字を探り当てて行けば、フラグに到達できそうな予感がします！

5. [実践] プログラムを書いて回して、答えよ出てこい！

今回、3000回アクセスして、3000種類のサンプルを取るコードを用意しました。

さすがに3000回も回せば、1度も出現しない文字コードを特定できるでしょう！

# 元のコードが雑過ぎて若干修正してました。多分動く（s.connectが出来ないので、そういう意味では今は動かないが）
import socket

for j in range(3000):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('hitme.tasteless.eu', 10401))

    text = s.recv(256)

    list = []
    for i in range(len(text)):
        list.append(ord(text[i]))

    print(list)
    s.close()