始めに

防衛省サイバーコンテスト2024にて出題されたcryptoジャンルのwriteupです。

目次

Information of Certificate
Missing IV
Short RSA Public Key
Cryptographically Insecure PRNG

Information of Certificate

問題文

Easy.crt ファイルは自己署名証明書です。証明書の発行者 (Issuer) のコモンネーム (CN) 全体を flag{} で囲んだものがフラグです。
配布ファイル：Easy.crt

解法

CNというのはサイトを訪れる際に入力するURLのサブドメインまでを含んだドメイン部分に該当するものらしいです。
例：https://example.com/のCNはexample.com

Windowsであればダウンロードしたファイルをダブルクリックすることで発行者を確認できます。
以下のコマンドでも可能です。

openssl x509 -in Easy.crt -noout -issuer

Missing IV

問題文

NoIV.bin ファイルは、128bit AES の CBC モードで暗号化した機密ファイルですが、困ったことに IV (初期化ベクトル) を紛失してしまいました。このファイルからできる限りのデータを復元し、隠されているフラグを抽出してください。

暗号鍵は 16 進数表記で 4285a7a182c286b5aa39609176d99c13 です。
配布ファイル：NoIV.bin

解法

AES-CBCは一つ前の暗号文ブロックと平文ブロックのxorを計算したのち、AESで暗号化したものを新たな暗号化ブロックにするという暗号です。（IVは0番目の暗号文ブロックと解釈することができます。）

復号はこの逆操作になるので、暗号文ブロックをAESで復号した後に一つ前の暗号文ブロックとのxorを取ればよいです。

今回の問題ではAESの秘密鍵が分かっており、NoIV.binの先頭16バイト以外は暗号文ブロックを利用することで復号できるので、IVの推測をすればよいことが分かります。

次のようなスクリプトで一度ファイルの復元を試みます。

test.py

from Crypto.Util.number import *
from Crypto.Cipher import AES
import os

KEY = long_to_bytes(0x4285a7a182c286b5aa39609176d99c13)
cipher = AES.new(KEY, AES.MODE_ECB)
data = open('NoIV.bin', 'rb').read()
IV =b'0'*16

buffer = b''

def xor (a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

for i in range(0, len(data), 16):
    cipher_block_i = data[i:i+16]
    decoded_block_i = cipher.decrypt(cipher_block_i)
    plain_block_i = xor(decoded_block_i, IV)
    IV = cipher_block_i
    buffer += plain_block_i

open('out.bin', 'wb').write(buffer)

NoIV.binファイルの先頭16バイト以外を正しく復号したout.binがどのようなファイルなのか確認するためにstringsコマンドを実行すると以下のような出力が得られます。

mimetypeapplication/vnd.oasis.opendocument.textPK
Configurations2/toolpanel/PK
Configurations2/menubar/PK
Configurations2/toolbar/PK
    .
    .
    .

一行目を見る限り、out.binはどうやらOpen Document Text形式のファイルのようです。
よって、手元でwordを開いて適当なodtファイルを作成し、先頭16バイトをそこからコピーして貼り付けてあげたらOKです。

solve.py

from Crypto.Util.number import *
from Crypto.Cipher import AES
import os

KEY = long_to_bytes(0x4285a7a182c286b5aa39609176d99c13)
cipher = AES.new(KEY, AES.MODE_ECB)
data = open('NoIV.bin', 'rb').read()
IV = b'0'*16
buffer = b''

def xor (a, b):
    return bytes([x ^ y for x, y in zip(a, b)])

for i in range(0, len(data), 16):
    cipher_block_i = data[i:i+16]
    decoded_block_i = cipher.decrypt(cipher_block_i)
    plain_block_i = xor(decoded_block_i, IV)
    if i == 0:
        plain_block_i = long_to_bytes(0x504B03040A0000000800000021005EC6)
    IV = cipher_block_i
    buffer += plain_block_i

open('flag.odt', 'wb').write(buffer)

このflag.odtをwordやLibreOfficeなどで開いたらFLAGが得られます。

Short RSA Public Key

問題文

RSA-cipher.dat ファイルは RSA 公開鍵 pubkey.pem で暗号化されています。公開鍵から秘密鍵を割り出し、暗号を解読してください。なお、パディングは PKCS#1 v1.5 です。
配布ファイル：pubkey.pem, RSA-cipher.dat

解法

Short RSA Public Keyという名前から公開鍵が小さいRSAだろうなと推測できます。
RSAの安全性は大きな合成数の素因数分解が難しいという問題によって保障されているので、公開鍵が小さい場合は容易に復号が可能です。

get_public_key.py

from Crypto.PublicKey import RSA

key = RSA.importKey(open('pubkey.pem').read())
print(f'n = {key.n}')

n = 78479434358679743508116090024686132395246871443799969871485501232049475609313

公開鍵をfactordbに投げて得たp, qを用いると復号スクリプトは次のように書けます。

solve.py

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

key = RSA.importKey(open('pubkey.pem').read())
n = key.n
p = 1011146650909449935800449563521726151
q = 77614294907759846691928156982114516291863

phi = (p-1)*(q-1)
e = key.e
d = inverse(e, phi)

enc = open('RSA-cipher.dat', 'rb').read()
enc = bytes_to_long(enc)
dec = pow(enc, d, n)
print(long_to_bytes(dec))

以前まではpem形式のファイルはopensslで頑張ってたんですが、RSA.importKey()が使えることを知ってからこっちを使っています。とても便利...

Cryptographically Insecure PRNG

問題文

PRNG.bin ファイルは下記の式で表される線形合同法で生成された疑似乱数列で XOR をとって暗号化されています。なお、生成された 4 バイトの数を最下位ビットから近い順に 1 バイトずつ平文と XOR をとるものとします。例えば、Hello World を x_0 = 4294967295 = 0xFFFFFFFF の初期値で暗号化した場合、16 進ダンプで b7 9a 93 93 cb 21 57 6f a3 ec 65 となります。

x_{n+1} = (233 x_n + 653)\ mod\ 4294967296

鍵(初期値= x_0)を推定し、PRNG.bin に対応する平文からフラグを抽出してください。なお、平文は(内容に意味はありませんが) ASCII でエンコードされた英文であったことがわかっています。また、最初の単語は 4 文字以上です。

解法

線形合同法にありがちなのはパラメータ推測ですが、この問題ではパラメータがすべて与えられており、初期値を推測するという変則的なものになっています。

初期値は0以上4294967296未満の値を全探索することでも解けますが、10^9程度の計算になるのでC/C++, Rustなどの高速な言語でも結構な時間がかかりそうな気がします。
ということで他の方針を考えてみたいと思います。

まず、暗号化の際は、生成された4バイトの数の最下位ビットから近い順に1バイトずつ平文とxorを取るので、最初の4文字が分かっていたら逆算することで初期値が判明します。

そして、平文の最初の単語は4文字以上なので、最初の4文字はupper_case + lowercase*3であることを期待します。このようなアルファベットの並びを総当たりして、flagが含まれるような文章を探せば良さそうです。（この方針だと26^4=456976通り試せばよいので10^4倍速く終わりそうです）

これを踏まえて最初の4文字を全探索するようなスクリプトを書くと次のようになります。

solve.py

from Crypto.Util.number import *

M = 4294967296
A = 233
B = 653

alphabet_lower = 'abcdefghijklmnopqrstuvwxyz'
alphabet_upper = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

data = open('PRNG.bin', 'rb').read()
for first_letter in alphabet_upper:
    for second_letter in alphabet_lower:
        for third_letter in alphabet_lower:
            for fourth_letter in alphabet_lower:
                FLAG = (first_letter + second_letter + third_letter + fourth_letter).encode('ascii')
                l = []
                for i in range(4):
                    d = bytes_to_long(data[i:i+1])
                    l.append(d^FLAG[i])

                X_0 = 0x0
                for i in range(4):
                    X_0 |= l[i] << (i*8)
                X_1 = X_0
                prngs = []

                for i in range(len(data)):
                    num = X_1 & 0xFFFFFFFF
                    for j in range(4):
                        num2 = (num >> j*8) & 0x000000FF
                        prngs.append(num2)
                    X_1 = (A * X_0 + B) % M
                    X_0 = X_1

                FLAG = b''


                for i in range(len(data)):
                    FLAG += bytes([prngs[i] ^ data[i]])

                if b'flag' in FLAG:
                    print(FLAG)
                    exit()

実行すると手元では2秒ほどで終わりました。

当初は先頭の単語をエスパーするという方法を試していましたが普通にダメでした。今回は通りませんでしたが、たまに"These days"や"Today"などでいけたりするので機会があれば試してみてください。

感想

今回cryptoで一番難しかったのはMissing IVでした。
bytes型のxorをbytes_to_longでint型に変換してint同士でxor取ってlong_to_bytesでbytes型に戻してということをしていたら、必要なバイトがちょこちょこ抜け落ちてて結果、破損したファイルが出来上がりという惨状でした。

何か勘違いしてるのかと思ってヒント開いたら「平文ファイルは OpenDocument Text ファイルだったようです。」とのことで

そんなわけで今回得た一番の学びは
横着せずちゃんとbytes同士のxorを定義しよう
ということでした。
皆さんも気を付けましょう。