LINE CTF 2021 writeup

Writer:b1uef0x / Webページ建造途中

概要

CRY - babycrypto1

AES-CBCの問題。次のプログラムがnc 35.200.115.41 16001で走る。

#!/usr/bin/env python
from base64 import b64decode
from base64 import b64encode
import socket
import multiprocessing

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
import hashlib
import sys

class AESCipher:
    def __init__(self, key):
        self.key = key

    def encrypt(self, data):
        iv = get_random_bytes(AES.block_size)
        self.cipher = AES.new(self.key, AES.MODE_CBC, iv)
        return b64encode(iv + self.cipher.encrypt(pad(data, 
            AES.block_size)))

    def encrypt_iv(self, data, iv):
        self.cipher = AES.new(self.key, AES.MODE_CBC, iv)
        return b64encode(iv + self.cipher.encrypt(pad(data, 
            AES.block_size)))

    def decrypt(self, data):
        raw = b64decode(data)
        self.cipher = AES.new(self.key, AES.MODE_CBC, raw[:AES.block_size])
        return unpad(self.cipher.decrypt(raw[AES.block_size:]), AES.block_size)

flag = open("flag", "rb").read().strip()

COMMAND = [b'test',b'show']

def run_server(client, aes_key, token):
    client.send(b'test Command: ' + AESCipher(aes_key).encrypt(token+COMMAND[0]) + b'\n')
    client.send(b'**Cipher oracle**\n')
    client.send(b'IV...: ')
    iv = b64decode(client.recv(1024).decode().strip())
    client.send(b'Message...: ')
    msg = b64decode(client.recv(1024).decode().strip())
    client.send(b'Ciphertext:' + AESCipher(aes_key).encrypt_iv(msg,iv) + b'\n\n')
    while(True):
        client.send(b'Enter your command: ')
        tt = client.recv(1024).strip()
        tt2 = AESCipher(aes_key).decrypt(tt)
        client.send(tt2 + b'\n')
        if tt2 == token+COMMAND[1]:
            client.send(b'The flag is: ' + flag)
            client.close()
            break

if __name__ == '__main__':
    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    server.bind(('0.0.0.0', 16001))
    server.listen(1)

    while True:
        client, address = server.accept()

        aes_key = get_random_bytes(AES.block_size)
        token = b64encode(get_random_bytes(AES.block_size*10))[:AES.block_size*10]

        process = multiprocessing.Process(target=run_server, args=(client, aes_key, token))
        process.daemon = True
        process.start()

class AESCipherは128bitのAES-CBCを計算している。ランダムなバイトからなるAES鍵(128bit)を毎回生成し、同じくランダムなバイトからなるtoken(1280bit)を毎回生成する。これらは知ることができない。

COMMAND = [b'test',b'show']として2種類のCOMMANDが定義されており、まずtoken+COMMAND[0]を暗号化した結果を出力して、次に1度だけ任意のIVと平文を同じAES鍵で暗号化することができる。最後に暗号文を入力して、復号化した結果がtoken+COMMAND[1]になっていればflagを得ることができる。

CBC mode encryption
CBC mode decryption

暗号利用モードCBCは上記のように前の暗号化結果を次のIVとして入力していくため、1度だけ任意のIVと平文を暗号化できる今回の問題では、直前のブロックの暗号文をIVとして設定すれば次のブロックを自由に作ることができる。

AESブロックの末尾を別のブロックに変更する

よって、AES鍵とtokenを知らなくても、testの暗号ブロックをshowの暗号ブロックに置き換えることで、token+COMMAND[1]に復号化される暗号文を作成できる。次のPythonコードは、最初に与えられた暗号文から、1度だけ実行できる暗号化に使用する_ivと_msgを生成。これらの暗号文をadd_chpに入れると、showコマンドの入った新しい暗号文new_chpを作ってくれるものになる。

from base64 import b64decode
from base64 import b64encode
from Crypto.Cipher import AES

COMMAND = [b'test',b'show']

ori_chp = b64decode("lx57zPXa4n62EFowJGT7sYB+3x1tNedmErWYXWMMHT1EOzbim7E6q73kMy6Xy5/Qhr0ci+DItU+MJ/e9iuJ7Xl1Q/kmUZv+NDLEa4mi9PpEFeMePLv10Skb26C7MiMHzqMjyU83CFHIzZBNOWeY4OqjqegDBROBTtcI4BGDFbNGMY9gzeqoLtNndbKX6C/d42ZjcHGncmJbR56GWUfE5BpLZPR17KmtHUN6WoGuPwretoaH5WYGBBfQ5KhUq3Gp2")
_iv = ori_chp[-AES.block_size*2:-AES.block_size]
_msg = COMMAND[1]
print(b64encode(_iv))
print(b64encode(_msg))

add_chp = b64decode("ktk9HXsqa0dQ3paga4/Ct1Q8a4SwOEKmuOPkC64ce3w=")
new_chp = ori_chp[:-AES.block_size] + add_chp[-AES.block_size:]
print(b64encode(new_chp))

結果

solve

CRY - babycrypto2

同じくAES-CBCの問題。次のプログラムがnc 35.200.39.68 16002で走る。

#!/usr/bin/env python
from base64 import b64decode
from base64 import b64encode
import socket
import multiprocessing

from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
import hashlib
import sys

class AESCipher:
    def __init__(self, key):
        self.key = key

    def encrypt(self, data):
        iv = get_random_bytes(AES.block_size)
        self.cipher = AES.new(self.key, AES.MODE_CBC, iv)
        return b64encode(iv + self.cipher.encrypt(pad(data, 
            AES.block_size)))

    def encrypt_iv(self, data, iv):
        self.cipher = AES.new(self.key, AES.MODE_CBC, iv)
        return b64encode(iv + self.cipher.encrypt(pad(data, 
            AES.block_size)))

    def decrypt(self, data):
        raw = b64decode(data)
        self.cipher = AES.new(self.key, AES.MODE_CBC, raw[:AES.block_size])
        return unpad(self.cipher.decrypt(raw[AES.block_size:]), AES.block_size)

flag = open("flag", "rb").read().strip()

AES_KEY = get_random_bytes(AES.block_size)
TOKEN = b64encode(get_random_bytes(AES.block_size*10-1))
COMMAND = [b'test',b'show']
PREFIX = b'Command: '

def run_server(client):
    client.send(b'test Command: ' + AESCipher(AES_KEY).encrypt(PREFIX+COMMAND[0]+TOKEN) + b'\n')
    while(True):
        client.send(b'Enter your command: ')
        tt = client.recv(1024).strip()
        tt2 = AESCipher(AES_KEY).decrypt(tt)
        client.send(tt2 + b'\n')
        if tt2 == PREFIX+COMMAND[1]+TOKEN:
            client.send(b'The flag is: ' + flag)
            client.close()
            break

if __name__ == '__main__':
    server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    server.bind(('0.0.0.0', 16002))
    server.listen(1)

    while True:
        client, address = server.accept()

        process = multiprocessing.Process(target=run_server, args=(client, ))
        process.daemon = True
        process.start()

babycrypto1と同じくAES-CBCの問題。同じくランダム生成されたAES_KEYとTOKENを、今度はPREFIX+COMMAND[0]+TOKENの順で暗号化する。その後、繰り返し任意の暗号文を復号することができ、復号結果がPREFIX+COMMAND[1]+TOKENになればflagが表示される。PREFIX+COMMAND[0]は文字列でCommand: testと16文字未満のため、これが128bitの先頭の暗号ブロックになって暗号化されている。

暗号利用モードCBCの復号では、以下のように先頭のCiphertextはkeyで復号化されたあと、IVとXORされてPlaintextになる。よって、IVの値を変更すればCiphertextと無関係に任意のPlaintextを作ることができる。

AESブロックの先頭の復号結果を変更する

元のPlaintext0とIV0、新しいPlaintext1とIV1を考えたとき、それぞれXORするとblock chipher decryption直後の同じ値になればよいので、次のようにIV1を作成できる。

Plaintext1 XOR IV1 = Plaintext0 XOR IV0
IV1 = Plaintext0 XOR IV0 XOR Plaintext1

今回は暗号文を何度でも復号化できるため、最初に提示された暗号文をそのまま復号化させれば、TOKENの平文を得ることができる。ここからTOKENの最初3文字***を含めたCommand: show***を作るようなIVを求めればよい。

from base64 import b64decode
from base64 import b64encode
from Crypto.Cipher import AES


COMMAND = [b'test',b'show']

ori_chp = b64decode("oviIxWowSnHey0hQRrPFd06CK08IzNktjsOxiB69u9FWxU3d5wVT3QHUBjxFBzzLLCQGj46cZu1k/WN8oYKJOBwSv+vwLY4luZ1E+T4GCjfBl0LKFYb89/10yiWvw3Ae56ftIMraU/clgsOL5KVeO1zdPR0GL+T8Xvtw6SvLYPPAwlx+CpLcV40F73ReA3O76I65dXt2I7Q9AtYG5k8IK8mIC6fBqTq3A+RmEIl7DeKNef2vsYXEfHxnR1Ib1LMGd3Z2CUBSU17LrKRq4/g2bzufR1Cm+A3nDXJSaE6oLyu3o7C6+BT0tAnWTdAIAwIHyZpNUULGtPbQRF41460qng==")
ori_iv = ori_chp[:AES.block_size]
ori_pln = "Command: testZzTosTPcUnBu44roqYGeyIjyJ22OoYp66c67bitZZthoRjCwTC9sW5jOFkVqW7WlMwJqI5Y+eJtxCkY4lkVkX3vzdDSkPtwB1FOrfHWPeGq4jOeprbrqhtcQzRdUsukyF1YdRzzZ8ezm2g82ydjFYcDrkfzk3ZQOzx0CpVulL80HGbwsB6amUMsmmVsC4jULWpg66++vj30B6p/aKGbh"
ori_pln0 = ori_pln[:AES.block_size].encode()
new_pln = ("Command: showZzT").encode()

new_iv = b""

for i in range(16):
        new_iv += (ori_iv[i]^ori_pln0[i]^new_pln[i]).to_bytes(1, byteorder="little")

new_chp = new_iv + ori_chp[AES.block_size:]
print(b64encode(new_chp))

結果

solve

CRY - babycrypto3

RSAの問題。pub.pemとciphertext.txtが配布される。pub.pemの中身は394bitの公開鍵になっており、次のコマンドで展開できる。16進をつなげてINT型にすればpubkeyが得られる。

pub.pemの展開 
n:31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337

yafuを使って394bitの鍵を素因数分解する。

YAFUによる公開鍵の素因数分解1

小一時間で素因数分解される。

YAFUによる公開鍵の素因数分解2 
p:109249057662947381148470526527596255527988598887891132224092529799478353198637
q:291664785919250248097148750343149685985101

pub.pemの展開内容からe=65537、ciphertext.txtからcが揃ったので、拾ってきたRSAの復号化コードで復号する。

from math import gcd
from Crypto.Util.number import bytes_to_long, long_to_bytes


f = open("./ciphertext.txt","rb")
c = bytes_to_long(f.read())
f.close()

p = 109249057662947381148470526527596255527988598887891132224092529799478353198637
q = 291664785919250248097148750343149685985101
n = 31864103015143373750025799158312253992115354944560440908105912458749205531455987590931871433911971516176954193675507337
e = 65537

def lcm(p, q):
  return (p * q) // gcd(p, q)

def _etension_euclid(x,y):
  c0, c1 = x, y
  a0, a1 = 1, 0
  b0, b1 = 0, 1

  while c1 != 0:
     mm = c0 % c1
     qq = c0 // c1

     c0, c1 = c1, mm
     a0, a1 = a1, (a0 - qq * a1)
     b0, b1 = b1, (b0 - qq * b1)

  return c0, a0, b0

l = lcm(p - 1, q - 1)
_c, a, _b = _etension_euclid(e, l)
d = a % l

print((long_to_bytes(pow(c,d,n))))

実行結果

Python solver実行結果

復号結果はpaddingされており、抜き出すとQ0xPU0lORyBUSEUgRElTVEFOQ0UuCg==、base64デコードするとCLOSING THE DISTANCE.になる。

flagはLINECTF{CLOSING THE DISTANCE.}