ångstromCTF 2021 - Home Rolled Crypto

問題概要

Aplet made his own block cipher! Can you break it?

nc crypto.2021.chall.actf.co 21602
Source

chall.py

#!/usr/bin/python
import binascii
from random import choice

class Cipher:
    BLOCK_SIZE = 16
    ROUNDS = 3
    def __init__(self, key):
        assert(len(key) == self.BLOCK_SIZE*self.ROUNDS)
        self.key = key

    def __block_encrypt(self, block):
        enc = int.from_bytes(block, "big")
        for i in range(self.ROUNDS):
            k = int.from_bytes(self.key[i*self.BLOCK_SIZE:(i+1)*self.BLOCK_SIZE], "big")
            enc &= k
            enc ^= k
        return hex(enc)[2:].rjust(self.BLOCK_SIZE*2, "0")


    def __pad(self, msg):
        if len(msg) % self.BLOCK_SIZE != 0:
            return msg + (bytes([0]) * (self.BLOCK_SIZE - (len(msg) % self.BLOCK_SIZE)))
        else:
            return msg
    
    def encrypt(self, msg):
        m = self.__pad(msg)
        e = ""
        for i in range(0, len(m), self.BLOCK_SIZE):
            e += self.__block_encrypt(m[i:i+self.BLOCK_SIZE])
        return e.encode()

key = binascii.unhexlify("".join([choice(list("abcdef0123456789")) for a in range(Cipher.BLOCK_SIZE*Cipher.ROUNDS*2)]))

with open("flag", "rb") as f:
    flag = f.read()

cipher = Cipher(key)


while True:
    a = input("Would you like to encrypt [1], or try encrypting [2]? ")
    if a == "1":

        p = input("What would you like to encrypt: ")
        try:
            print(cipher.encrypt(binascii.unhexlify(p)).decode())
        except:
            print("Invalid input. ")
    elif a == "2":
        for i in range(10):
            p = "".join([choice(list("abcdef0123456789")) for a in range(64)])
            print("Encrypt this:", p)
            e = cipher.encrypt(binascii.unhexlify(p)).decode()
            c = input()
            if e != c:
                print("L")
                exit()
        print("W")
        print(flag.decode())            

    elif a.lower() == "quit":
        print("Bye")
        exit()
    else:
        print("Invalid input. ")

解説

プログラムの問題点

このプログラムはBLOCK_SIZE * ROUND長の鍵を使って暗号化をしていますが、同じ鍵に対して任意の暗号化結果を知ることが出来ます。よくこのソースコードを読むと分かるのですが、暗号化は&及び^のみを用いていることからビット別に処理が完全に分かれてしまっています。

このことから、各ビット独立に0の時の暗号化結果と1の時の暗号化結果が分かった場合、その結果を他の暗号化処理でも流用が出来ます。よって、暗号機をコピーすることが出来ます。

実際に実装する際に、関数をBLOCK_SIZE * 8個用意するのは実装の都合上面倒なので、1文字=8byte（正確には16進数として渡されるため、16通り）毎に出力結果をまとめる形で問題ないです。

solve.pyfrom pwn import *

import binascii

context.log_level = "debug"

r = remote("crypto.2021.chall.actf.co", 21602)
r.recvuntil(b"Would you like to encrypt [1], or try encrypting [2]? ")

# got encryption system
r.sendline(b"1")
r.recvuntil(b"What would you like to encrypt: ")
chars = "0123456789abcdef"
payload = b""
for c in chars:
    payload += c.encode() * 32
r.sendline(payload)
result = r.recvline().decode().strip()

encrypt = [{} for _ in range(32)]
for i in range(len(chars)):
    for j in range(32):
        encrypt[j][chars[i]] = result[32 * i + j]

test = ""
payload = payload.decode()
for i in range(len(payload)):
    test += encrypt[i % 32][payload[i]]
assert test == result

# solve it
r.recvuntil(b"Would you like to encrypt [1], or try encrypting [2]? ")
r.sendline(b"2")
for _ in range(10):
    r.recvuntil("Encrypt this: ")
    p = r.recvline().decode().strip()
    while len(p) % 32 != 0:
        p += "0"
    payload = ""
    for i in range(len(p)):
        payload += encrypt[i % 32][p[i]]
    r.sendline(payload.encode())
r.interactive()