スプーキーズのちょっとTech。

SPOOKIES社内のより技工的な、専門的なブログページです。

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.cassert(strlen(plaintext) == strlen(one_time_pad)); は、

plaintextone_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_padNULL(0x00) は含まれないということが分かります。

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

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

一般的なワンタイムパッドであれば、 0x00~0xFF との XOR の結果が出力されるのに対して、今回の chall.cstrlen のアサートを挟んでしまったために、 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()

そして、この結果をスプレッドシートで集計したのが下の画像。

少しわかりにくいかもしれませんが、出現数が0の場合にセルが赤くなるようにしています。

1文字目について見てみると、文字コード「116( t )」が3000回のデータを取ったにもかかわらず、出現数が0である!

2文字目については文字コード「99( c )」が出現数0だ!

f:id:ishiyamacocoa:20191108214637p:plain
スプレッドシートで集計した結果(赤が出現数0を示す)

集計結果を見ると、全部で37文字、出現数0の文字コードが必ず1つずつ存在していたのだ!

すごい! これは上手く行った!

早速、全37文字について、1つ1つ現れていないのを取り出していくと、、、

tctf{p1z_us3:4ll-t3h_by7e5>0n3_tim3}

フラグをゲットすることに成功しました。

ワンタイムパッド攻略完了!

6. 感想

ということで、無事解けました。

ありがとうございます!

ワンタイムパッド、 random urandom について知ることが出来ました、良かった良かった。

ちなみに、あとあと考えると、スプレッドシートで集計しなくても、プログラム上で配列用意してってやれば集計する必要なく答えが出たんだよなぁ。 まあ、ブログに張り付ける画像が1枚増えたという意味では、スプレッドシートに集計して良かったと言えるでしょう!

ということで、

TastelessCTF 2019[Crypto] babypad についてお話しました。

長々と書き連ねましたが、読んでくださりありがとうございました。

皆さんも、CTFやりましょう!