Home Rolled Crypto(Writeup)

問題

https://2021.angstromctf.com/challenges

Aplet made his own block cipher! Can you break it?
nc crypto.2021.chall.actf.co 21602

source

#!/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. ")

解法

sourceの解釈

１６バイト毎に、３ラウンドの暗号化を行う
↑を実現させるために４８バイトの鍵をランダムに生成
暗号化するメッセージはパディングされる
暗号化はビット毎に行われる

考え方

xorとandを３度繰り返していることから、暗号文から元の秘密鍵を見つけることはできない。
しかし、ビット毎に{0,1}->{0,1}の暗号化が分かれば手元で同じ暗号化の結果が得られる。
６４バイトの平文に対する暗号文を当てればフラグが得られるので、
６４バイトの0b0...0,0b1...1を質問し、得られた暗号文テーブルを用いて手元で暗号化を行う。
　

コード

solution

from pwn import *
from base64 import b64decode, b64encode

BLOCK_SIZE = 16
ROUNDS = 3
io = remote("crypto.2021.chall.actf.co",21602)

table=[]

for b in ("00","ff"):
    io.sendlineafter("[2]? ", "1")
    io.sendlineafter("encrypt: ", b*BLOCK_SIZE*2)
    rcv = io.recvline().decode().strip()
    i = int(rcv,16)
    print('{:0256b}'.format(i))
    table.append('{:0256b}'.format(i))

io.sendlineafter("[2]? ", "2")
for _ in range(10):
    io.recvuntil("this:")
    rcv = io.recvline().decode().strip()
    i = int(rcv,16)
    ans = ""
    for i, c in enumerate('{:0256b}'.format(i)):
        ans += table[int(c)][i]
    rcv=('{:064x}'.format(int(ans,2)))
    io.sendline(rcv)

io.recvline()
print(io.recvline().decode().strip()) # flag

ans

[+] Opening connection to crypto.2021.chall.actf.co on port 21602: Done
1100101000100101000000000011011100001101010011010001100001010111101010001000110010000000010111000101100101000011000001100001000011001010001001010000000000110111000011010100110100011000010101111010100010001100100000000101110001011001010000110000011000010000
0000101000000101000000000001011000001100010001010000000001010101101000001000010000000000010011000101100101000010000001100001000000001010000001010000000000010110000011000100010100000000010101011010000010000100000000000100110001011001010000100000011000010000
actf{no_bit_shuffling_is_trivial}