fr33f0r4ll

自分用雑記

TokyoWesterns CTF 2018 mixed-cipher 復習

ctf crypto

Writeupとか見ながら復習したので、その解説。 参考にしたWriteupはhttps://github.com/GabiTulba/Tokyo-Westerns-2018-Mixed-Cipher-Crypto-Write-up/blob/master/README.mdのやつ。

問題自体の解説はしないでその中で使われていた手法、特にLSB Decryption Oracle Attackの解説をメインに書く。

mixed-cipher

問題で渡されるスクリプト

from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes

import random
import signal
import os
import sys

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', 0)
privkey = RSA.generate(1024)
pubkey = privkey.publickey()
flag = open('./flag').read().strip()
aeskey = os.urandom(16)
BLOCK_SIZE = 16

def pad(s):
    n = 16 - len(s)%16
    return s + chr(n)*n

def unpad(s):
    n = ord(s[-1])
    return s[:-n]

def aes_encrypt(s):
    iv = long_to_bytes(random.getrandbits(BLOCK_SIZE*8), 16)
    aes = AES.new(aeskey, AES.MODE_CBC, iv)
    return iv + aes.encrypt(pad(s))

def aes_decrypt(s):
    iv = s[:BLOCK_SIZE]
    aes = AES.new(aeskey, AES.MODE_CBC, iv)
    return unpad(aes.decrypt(s[BLOCK_SIZE:]))

def bulldozer(s):
    s = bytearray(s)
    print('Bulldozer is coming!')
    for idx in range(len(s) - 1):
        s[idx] = '#'
    return str(s)

def encrypt():
    p = raw_input('input plain text: ').strip()
    print('RSA: {}'.format(pubkey.encrypt(p, 0)[0].encode('hex')))
    print('AES: {}'.format(aes_encrypt(p).encode('hex')))

def decrypt():
    c = raw_input('input hexencoded cipher text: ').strip().decode('hex')
    print('RSA: {}'.format(bulldozer(privkey.decrypt(c)).encode('hex')))

def print_flag():
    print('here is encrypted flag :)')
    p = flag
    print('another bulldozer is coming!')
    print(('#'*BLOCK_SIZE+aes_encrypt(p)[BLOCK_SIZE:]).encode('hex'))

def print_key():
    print('here is encrypted key :)')
    p = aeskey
    c = pubkey.encrypt(p, 0)[0]
    print(c.encode('hex'))

signal.alarm(300)
while True:
    print("""Welcome to mixed cipher :)
I heard bulldozer is on this channel, be careful!
1: encrypt
2: decrypt
3: get encrypted flag
4: get encrypted key""")
    n = int(raw_input())

    menu = {
        1: encrypt,
        2: decrypt,
        3: print_flag,
        4: print_key,
    }

    if n not in menu:
        print('bye :)')
        exit()
    menu[n]()

簡単に動作を説明すると、CBCモードのAESと1024bitのRSAを使って暗号化とかする感じ。 ただし、bulldozerが来て復号化したメッセージなどはほとんど取得できないようになっている。 おそらく、このbulldozerで復号化したメッセージの下位1バイトが取得できるところからLSB Decryption Oracle Attackを発想できるんだと思う。

解読手順 概略

Writeupで示されていた手順だと、だいたい以下のようになる。

  1. 暗号文と平文が入手できることとgcdを利用してNを入手 (2~4回の試行)
  2. Nを使って、暗号化されたASE Keyの下位1バイトが分かるので、RSA LSB oracle AttackでAES Keyを入手
  3. PythonのrandomモジュールのメルセンヌツイスターをクラックしてIVを入手
  4. 鍵とIVが分かるのでAESのフラグを復号する

print_keyによってRSAで暗号化されたAES Keyを手に入れ、decryptでそれを復号することができる。 ただし、bulldozerで下位1バイトしか分からないようにされてしまう。 ここでRSAに対する攻撃のひとつであるLSB Decryption Oracle Attackが使える。 この攻撃は任意の暗号文を復号した結果の下位1ビットが分かれば、元の平文を復元することができるというものである、詳しくは後で。 これを利用してAES Keyを復号できる。

これでprint_flagが解読できるかというとそうでもない。 print_flagでは先頭にあるIVがbulldozerで潰されるため、鍵があっても復号できないようになっている。 そのためこのIVを取得する必要があるが、一見すると手に入らなそうに思える。 しかし、疑似乱数を推測することでこれを突破することができる。 IVの生成に使っているPythonのrandomモジュールはメルセンヌツイスターというアルゴリズムで疑似乱数を生成しているが、モジュール内部の状態であるPRNGを取得できるために予測が可能になってしまう。 推測のためのツール、randcrackがある。 推測といっても何度か(Writeupでは156回)乱数を取得する必要がある。

これで、AESの鍵とIVが入手できたのでprint_flagによって出力されるAESで暗号化されたフラグを解読することができるようになった。

RSAの解読

LSB Decryption Oracle Attack

この攻撃は、任意の暗号文の平文の下位1ビットが分かれば平文を求めることができてしまうというものである。 だいたい以下の条件を満していれば使える。

  • 任意の暗号文を復号でき、その結果の下位1ビットが分かる
  • 公開鍵(N, e)が分かっている

この問題ではNも分かっていないので、その取得方法もこのあとで解説する。 ここではNは分かっているものとして話を進める。 eはPyCryptoのモジュールのデフォルト値0x10001が使われている。 普通RSAのeには0x10001が使われるので、分からなくてもこれを仮定して良い気はする。 eが極端に大きかったり小さかったりするとそれはそれで攻撃可能になりかねないので注意する必要がある。

求めたい平文をm、求めたい平文を暗号化した暗号文はc、公開鍵をNとeとする。 まず2^ecを復号させる。 このとき、mとcはm^e = c\ mod\ Nであるため、2^ecでは(2m)^e = 2^ec\ mod\ Nが成立する。 よって、2^ecを復号すると2m\ mod\ Nが得られる。

2m\ mod\ Nの値をrとすると、2m = kN + rと表すことができる(kは整数)。 また、m \lt Nであり(mがNより大きくなるとm\ mod\ Nが一意に定まらず解読不可能になるので、普通はそうならないようにする)、r \lt Nであるため、0 \leq kであるはず。
// TODO: ここの解釈は微妙、もう少しちゃんとした証明を探す。
要は、2m \lt 2Nなので、k \geq 2のときは2m \lt kN + rとなるというだけである。 ありえるのはk = 0, 1だけとなる。

ここで、2mの偶奇(下位1ビット)に着目する。 kN + rのNは、素数と素数の積なので奇数のはず(偶数なら素数2が選ばれているのでNから秘密鍵を求められる)。 rの偶奇は前提条件により復号した結果から分かる。 また、2mは偶数であるので、rによりkの偶奇が分かることになる。 もしr、つまり復号した結果が奇数(下位ビット1)なら、kも奇数である。 k = 0, 1なのでk = 1ということになる。 もしrが偶数(下位ビット0)なら、k = 0となる。

k = 0のとき、2m = rなので2m \leq Nということになる。
k = 1のとき、2m = N + rなので2m \gt Nということになる。
// FIXME: 等号が間違ってる気がする

結果を簡潔にまとめると、2^ecの復号した結果の下位ビットが

  • 0なら
    • 0 \leq m \leq \frac{N}{2}
  • 1なら
    • \frac{N}{2} \lt m

となる。 つまり、下位1ビットから平文mの範囲をNの半分に限定することができることになる。 4^ecも同じようにさらに半分にでき、8^ecでさらに半分にできる。 これをせいぜい鍵長のビット数回繰り返せば平文を定めることができる。

4^ecのときについて

同じような議論で、k = 0, 1, 2, 3に限定できる。 2^ecのときの範囲と合わせて考えて、さらに半分にすることができる。

Nの特定

LSB Decryption Oracle Attackで、任意の暗号文を解読した結果の下位1ビットを知ることができると平文全体を求めることができると分かった。 しかし、この問題では肝心のNが分からないようになっている。 そこでまずNを特定する必要がある。

任意の平文の暗号文を入手できると十分な確度で推測することができる。 これにはgcdを利用する。

暗号化処理m^e = c\ mod\ Nをm^e = kN + cと表す。 ある平文m_1, m_2, m_3, ...を用意し、暗号文c_1, c_2, c_3, ...を取得する。 暗号化処理により、m_i^e = k_iN + c_i, (i = 1, 2, 3, ...)となる。 k_iN = m_i^e - c_iによりk_iNが取得できる。

このとき、k_iN同士のgcdを計算することでNが取得できる。 k_iの値によっては失敗しそうだが、Nのビット長を利用することで確度を上げられる。 だいたい2つから4つくらいのgcdで大丈夫らしい。

AESの解読

AESの概略

RSAよりは浸透してないだろうと思うので、簡単に説明。 共通鍵暗号なので、暗号化と復号に使う鍵は同じものになる。 簡単に言えば、鍵から乱数列を作ってその乱数列を使い1ブロックずつを暗号化していく。

モードというものがあり、暗号化のされ方や強度に影響が出る。 この問題で使われているのはCBCモードというもので、前に暗号化されたブロックのデータが次のブロックの暗号化に使われるモードになる。 これにより、一部だけ解読したり改ざんしたりしにくくなる。 前のブロックを使うため、一番最初のブロックだけは初期化ベクトルという特別なブロックを前のブロックとして使う必要がある。 復号するためにはこの初期化ベクトルも必要になる。 この初期化ベクトルは暗号文と同時に送信される(そのはずだけど微妙に憶えてない)。

解読方法

RSAの解読することにより、print_keyからAESの鍵を取得することができた。 本来なら鍵され分かれば共通鍵暗号のAESは復号できるはずだが、IV(初期化ベクトル)をbulldozerに潰されてしまっているため復号できない。 そのため、IVをどうにかして取得する必要がある。

問題の処理ではIVをrandom.getrandbits(BLOCK_SIZE*8)で生成している。 このrandomでは、疑似乱数の生成にメルセンヌツイスターというアルゴリズムを使用している。 乱数の実装はたいていこのメルセンヌツイスターになってるはず、多分。 モジュールなので当然内部の初期状態などは分かっているため、これを解析して次の乱数を予想できるらしい。 randcrackでそれが可能、方法についても記載されているがまだ調べてない。

ともかく、これにより鍵とIVが手に入ったためprint_flagを解読することができ、フラグをゲットできる。

スクリプト

writeupの方のコードは汚なくて読みにくいので、できればあとで書きたい。