TSG CTF 2019 Writeup - Recorded

tl;dr

/dev/input/event1の記録が与えられ、そこからflagをどのように暗号化したかを特定し、復号する問題。/dev/input/event1を見ていくと暗号化は最弱になるように改変されたOpenSSLによって行われており、少しのブルートフォースで解くことができる。

問題

何が起こった?

注意 これらのコマンドはJISキーボードのパソコンで実行されました。

$ sudo docker build -t problem .
$ sudo docker run -it --device=/dev/input/event1:/dev/input/event1 problem "/bin/bash"
root@hogehuga:/tmp# cat /dev/input/event1 > input &

Difficulty Estimate: Medium

与えられたファイル: Dockerfile, encrypted, input

解き方

input/dev/input/event1を記録したものなので、キーボードの入力の情報が書かれている。encryptedはflagを暗号化したものだと想定される。また、Dockerfileは次の内容であった。

FROM ubuntu:18.04
RUN apt update

RUN apt install make -y
RUN apt install vim -y
RUN apt install gcc -y
RUN apt install curl -y
RUN apt install libperl5.26 -y

COPY flag.txt /tmp/
WORKDIR /tmp/

キー入力の復元

まずはinputを調べてどのようなキー入力が行われたかを調べる。

ググるとちょうど良さそうなコードが見つかった。

stackoverflow.com

このページに書かれているコードは全てのイベントをキーコードで表示しているため、見やすくするために必要な情報だけを表示するのとキーコードを実際の文字に変換する処理を追加したコードがこちら*1

import struct
import time
import sys

import evdev


infile_path = "input"

# long int, long int, unsigned short, unsigned short, unsigned int
FORMAT = "llHHI"
EVENT_SIZE = struct.calcsize(FORMAT)

# open file in binary mode
in_file = open(infile_path, "rb")
event = in_file.read(EVENT_SIZE)

while event:
    (tv_sec, tv_usec, type, code, value) = struct.unpack(FORMAT, event)
    if type == 1 and value == 1:
        k = evdev.ecodes.KEY[code].replace("KEY_", "")
        if k == "ENTER":
            print(" [%d.%d]" % (tv_sec, tv_usec))
        else:
            if k == "SLASH":
                k = "/"
            elif k == "SPACE":
                k = "⎵"
            elif k == "MINUS":
                k = "-"
            elif k == "DOT":
                k = "."
            print(k.lower(), end=" ")

    event = in_file.read(EVENT_SIZE)

in_file.close()

そしてその出力がこちら。USキーボードの表示になっているので一部読み替える必要があることに注意。また、各入力の末尾の数字はエンターキーが押されたunix timeでこの情報も後に重要になってくる。

r m ⎵ / d e v / u r a tab  [1556368653.762255]
r m ⎵ / d e v / r a tab  [1556368657.67882]
leftshift l a n g - c ⎵ d a t e ⎵ - - u t c ⎵ leftshift . ⎵ / d e v / r a n d o m  [1556368668.52704]
e c h o ⎵ n y a n ⎵ leftshift . . ⎵ / d e v / r a tab  [1556368675.376979]
c u r l ⎵ - leftshift o ⎵ h t t p s apostrophe / / w w w . o p e n s s l . o r g / s o u r c e / o p e n s s l - 1 . 1 . 1 b . t a r . g z  [1556368702.814038]
t a r ⎵ x z v f ⎵ o p e tab  [1556368713.694218]
c d ⎵ o p e tab tab  [1556368722.29127]
v i m ⎵ c r y tab r a tab r a n d leftshift ro u n i x . c  [1556368737.298092]
6 3 7 leftshift g d 1 7 d 6 2 1 leftshift g d 2 d 6 0 3 leftshift g d d 4 8 0 leftshift g d 3 0 d apostrophe w q  [1556368782.395446]
v i m ⎵ c r tab r a tab r a tab leftshift ro l i tab  [1556368793.777170]
2 5 0 leftshift g d 2 d apostrophe w q  [1556368806.93882]
. / c o tab  [1556368808.372191]
m a k e ⎵ - j ⎵ 4  [1556368813.732588]
c d ⎵ . .  [1556368856.711424]
leftshift l d ro l i b r a r y ro p a t h - . / o p e tab ⎵ . / o p e tab a p p tab o p e tab g e n r s a ⎵ 1 0 2 4 ⎵ leftshift . ⎵ k e y . p e m  [1556368884.121900]
leftshift l d ro l i b r a r y ro p a t h - . / o p e tab ⎵ . / o p e tab a p tab o p e tab r s a u t l ⎵ - e n c r y p t ⎵ - i n k e y ⎵ k e y . tab - i n ⎵ f l tab - o u t ⎵ e n c r y p t e d  [1556368926.779365]
f d backspace g ⎵ 1  [1556368930.934979]

やっていることとは次の通り

  • /dev/urandom/dev/randomの削除
  • /dev/randomに現在時刻とnyanという文字列の書き込み
  • OpenSSL 1.1.1bのダウンロードとvimでコードの一部削除、ビルド
  • ビルドしたOpenSSLでrsa秘密鍵の生成、生成した鍵でflagの暗号化(これがencrypted

上記と全く同じ状態を作り出して鍵を生成すればflagを復号できそうである。/dev/urandomは削除されていて/dev/randomは固定されているので不可能ではなさそうな感じがする。

環境の再現

それではやっていく。なお、以降は全てDockerのubuntu:18.04イメージを使って行なっている。

まずはDockerfileと同じ状況を作る。

apt update; apt install -y make vim gcc curl libperl5.26

次にurandomの削除とrandomの書き換えを行う。ここで、inputによればrandomには現在時刻が書き込まれているがinputには時刻情報も入っているためここからrandomに書き込まれた時刻を推測できる。

rm /dev/urandom
rm /dev/random
LANG=C date --utc -d @1556368668 > /dev/random  # Sat Apr 27 12:37:48 UTC 2019
echo nyan >> /dev/random

OpenSSLの改変とビルド

適当な場所にOpenSSLをダウンロードして展開する。

curl -O https://www.openssl.org/source/openssl-1.1.1b.tar.gz
tar xf openssl-1.1.1b.tar.gz

展開したファイルをvimを使って編集していく。

crypto/rand/rand_unix.cに対して次の示す通り指定した行に移動していくつか行を削除して、、、という操作を行う。

637G d17d 621G d2d 603G dd 480G d30d :wq

crypto/rand/rand_lib.cに対しても同様にvimで次の操作を行う。

250G d2d :wq

変更を行った前と後のdiffはこんな感じ。全くよくわからないが、エラー処理と乱数生成処理の削除・変更をしているように見える。

diff --git a/crypto/rand/rand_lib.c b/crypto/rand/rand_lib.c
index d8639c4..cddfb39 100644
--- a/crypto/rand/rand_lib.c
+++ b/crypto/rand/rand_lib.c
@@ -247,8 +247,6 @@ size_t rand_drbg_get_nonce(RAND_DRBG *drbg,
     data.instance = drbg;
     CRYPTO_atomic_add(&rand_nonce_count, 1, &data.count, rand_nonce_lock);
 
-    if (rand_pool_add(pool, (unsigned char *)&data, sizeof(data), 0) == 0)
-        goto err;
 
     ret   = rand_pool_length(pool);
     *pout = rand_pool_detach(pool);
diff --git a/crypto/rand/rand_unix.c b/crypto/rand/rand_unix.c
index 9cbc9ad..e7a4759 100644
--- a/crypto/rand/rand_unix.c
+++ b/crypto/rand/rand_unix.c
@@ -477,36 +477,6 @@ size_t rand_pool_acquire_entropy(RAND_POOL *pool)
     unsigned char *buffer;
 
 #   if defined(OPENSSL_RAND_SEED_GETRANDOM)
-    {
-        ssize_t bytes;
-        /* Maximum allowed number of consecutive unsuccessful attempts */
-        int attempts = 3;
-
-        bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
-        while (bytes_needed != 0 && attempts-- > 0) {
-            buffer = rand_pool_add_begin(pool, bytes_needed);
-            bytes = syscall_random(buffer, bytes_needed);
-            if (bytes > 0) {
-                rand_pool_add_end(pool, bytes, 8 * bytes);
-                bytes_needed -= bytes;
-                attempts = 3; /* reset counter after successful attempt */
-            } else if (bytes < 0 && errno != EINTR) {
-                break;
-            }
-        }
-    }
-    entropy_available = rand_pool_entropy_available(pool);
-    if (entropy_available > 0)
-        return entropy_available;
-#   endif
-
-#   if defined(OPENSSL_RAND_SEED_LIBRANDOM)
-    {
-        /* Not yet implemented. */
-    }
-#   endif
-
-#   if defined(OPENSSL_RAND_SEED_DEVRANDOM)
     bytes_needed = rand_pool_bytes_needed(pool, 1 /*entropy_factor*/);
     {
         size_t i;
@@ -600,7 +570,6 @@ int rand_pool_add_nonce_data(RAND_POOL *pool)
      * different process instances.
      */
     data.pid = getpid();
-    data.tid = CRYPTO_THREAD_get_current_id();
     data.time = get_time_stamp();
 
     return rand_pool_add(pool, (unsigned char *)&data, sizeof(data), 0);
@@ -618,8 +587,6 @@ int rand_pool_add_additional_data(RAND_POOL *pool)
      * The thread id adds a little randomness if the drbg is accessed
      * concurrently (which is the case for the <master> drbg).
      */
-    data.tid = CRYPTO_THREAD_get_current_id();
-    data.time = get_timer_bits();
 
     return rand_pool_add(pool, (unsigned char *)&data, sizeof(data), 0);
 }
@@ -634,23 +601,6 @@ int rand_pool_add_additional_data(RAND_POOL *pool)
  */
 static uint64_t get_time_stamp(void)
 {
-# if defined(OSSL_POSIX_TIMER_OKAY)
-    {
-        struct timespec ts;
-
-        if (clock_gettime(CLOCK_REALTIME, &ts) == 0)
-            return TWO32TO64(ts.tv_sec, ts.tv_nsec);
-    }
-# endif
-# if defined(__unix__) \
-     || (defined(_POSIX_C_SOURCE) && _POSIX_C_SOURCE >= 200112L)
-    {
-        struct timeval tv;
-
-        if (gettimeofday(&tv, NULL) == 0)
-            return TWO32TO64(tv.tv_sec, tv.tv_usec);
-    }
-# endif
     return time(NULL);
 }

あとはこれをビルド(./config && make -j 4)して鍵を生成してみる。

LD_LIBRARY_PATH=./openssl-1.1.1b/ ./openssl-1.1.1b/apps/openssl genrsa 1024 > key.pem

何回か鍵を生成してみると毎回鍵が変わっており、作問者と同じ鍵を作れていないことに気づく。これではflagは復号できない。

コードを読んだり試行錯誤したり色々した結果、次の2つが鍵の生成に関わっていることがわかった。

  • 現在時刻
  • PID

現在時刻の固定

Dockerコンテナでは現在時刻の変更は基本的にできないのでどうしようかとググっていたところlibfaketimeというとんでもなく便利なものを見つけた。

github.com

これはコマンドの実行時に環境変数としてFAKETIME="YYYY-MM-DD hh:mm:ss"のように指定しておくと現在時刻を指定した時刻に固定することできる(他にも色々できる)。次のコマンドでインストールする。

curl -O https://github.com/wolfcw/libfaketime/archive/v0.9.7.tar.gz
tar xf v0.9.7.tar.gz
cd libfaketime-0.9.7
make install

これで以下のコマンドを試すと時刻が固定されていることがわかる。

FAKETIME="2019-04-27 12:41:24" LD_PRELOAD=/usr/local/lib/faketime/libfaketime.so.1 date
# Sat Apr 27 12:41:24 UTC 2019

時刻の固定ができたので鍵を再生成してみるが、前述の通りPIDも鍵の生成に関わっているので生成するたびに異なる鍵ができてしまう。なお、時刻はinputから取得した時刻を使っている。

FAKETIME="2019-04-27 12:41:24" LD_PRELOAD=/usr/local/lib/faketime/libfaketime.so.1 LD_LIBRARY_PATH=./openssl-1.1.1b/ ./openssl-1.1.1b/apps/openssl genrsa 1024 > key.pem

PIDの固定

OpenSSLのコードを眺めていたところnonceの生成にPIDが使われていることがわかった。

int rand_pool_add_nonce_data(RAND_POOL *pool)
{
    struct {
        pid_t pid;
        CRYPTO_THREAD_ID tid;
        uint64_t time;
    } data = { 0 };

    /*
     * Add process id, thread id, and a high resolution timestamp to
     * ensure that the nonce is unique with high probability for
     * different process instances.
     */
    data.pid = getpid();
    data.time = get_time_stamp();

    return rand_pool_add(pool, (unsigned char *)&data, sizeof(data), 0);
}

data.pidの値を1に書き換えてビルドし直し、時刻を固定して鍵を生成したところ何度生成しても同じ鍵が出来上がることがわかった。残念ながらflagの暗号化に使った鍵の生成時のPIDはわからない(推測はできる?)がLinuxのPIDのデフォルトの上限は32768なので総当たりで試せばflagが復号できそうだ。

PIDの取得処理を次のように書き換えて環境変数FAKEPIDからOpenSSL内で使われるPID番号を変更できるようにする。

data.pid = atoi(getenv("FAKEPID"));

flagの入手

あとはPIDをブルートフォースで見つけるだけ。以下のスクリプトをしばらく回しておいたらPID=8781でflagを復号することができた。

for i in {1..32768}; do
    echo $i
    FAKEPID=$i LD_PRELOAD=/usr/local/lib/faketime/libfaketime.so.1 FAKETIME="2019-04-27 12:41:24" LD_LIBRARY_PATH=./openssl-1.1.1b/ ./openssl-1.1.1b/apps/openssl genrsa 1024 > /tmp/key.pem 2>/dev/null
    cat encrypted | FAKEPID=1 LD_LIBRARY_PATH=./openssl-1.1.1b/ ./openssl-1.1.1b/apps/openssl rsautl -decrypt -inkey /tmp/key.pem -raw | grep -a TSGCTF && break
done
TSGCTF{openssl_genrsa_is_hardly_predictable}

どうやら一番最初に解けたっぽい。

f:id:iso0:20190505191356p:plain

*1:キーコードから実際のキーへの変換はpython-evdevを使っているが、MacにインストールできなかったのでDocker上で動かしている。