🐕

SECCON CTF 2021 Writeup (author's)

2021/12/27に公開

pppp

problem

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q

mid = len(flag) // 2

e = 65537

m1 = int.from_bytes(flag[:mid], byteorder='big')
m2 = int.from_bytes(flag[mid:], byteorder='big')

assert m1 < 2**256
assert m2 < 2**256

m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]

# add padding
for i in range(4):
    for j in range(4):
        m[i][j] *= getPrime(768)

m = matrix(Zmod(p*q), m)

c = m^e

print("n =", n)
print("e =", e)
print("c =", list(c))

outline

given:

\begin{align*} n &= pq \\ e &= 65537 \\ c &= \begin{bmatrix} r_1 p & r_2 p & r_3 p & r_4 p \\ 0 & r_5 m_1 & r_6 m_1 & r_7 m_1 \\ 0 & 0 & r_8 m_2 & r_9 m_2 \\ 0 & 0 & 0 & r_{10} 1 \end{bmatrix}^e \end{align*}

target:

m_1, m_2

solution

\begin{align*} c_{00} &= (r_1 p)^e \\ \therefore p &= \mathrm{GCD}(c_{00}, n) \\ q &= n / p \\ M = \begin{bmatrix} r_1 p & r_2 p & r_3 p & r_4 p \\ 0 & r_5 m_1 & r_6 m_1 & r_7 m_1 \\ 0 & 0 & r_8 m_2 & r_9 m_2 \\ 0 & 0 & 0 & r_{10} 1 \end{bmatrix} &= c^d \because \mathrm{diagonalization} \\ m_1 &= \mathrm{GCD}(M_{11}, M_{12}) \\ m_2 &= \mathrm{GCD}(M_{22}, M_{23}) \end{align*}

code

from Crypto.Util.number import *

with open('output.txt') as f:
    lines = f.readlines()
    n = eval(lines[0].split()[-1])
    e = eval(lines[1].split()[-1])
    c = eval("".join(lines[2].split()[2:]))

c = matrix(Zmod(n), c)

p = int(gcd(int(c[0][0]), n))
assert int(n) % p == 0
q = n // p

phi = (p-1) * (q-1)
d = int(pow(e, -1, phi))
m = c^d

m1 = long_to_bytes(gcd((int(m[1][2]), int(m[1][3]))))
m2 = long_to_bytes(gcd((int(m[2][2]), int(m[2][3]))))
print((m1+m2).decode('utf-8'))

oOoOoO

problem

import signal
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random
from flag import flag

message = b""
for _ in range(128):
    message += b"o" if random.getrandbits(1) == 1 else b"O"

M = getPrime(len(message) * 5)
S = bytes_to_long(message) % M

print("M =", M)
print('S =', S)
print('MESSAGE =', message.upper().decode("utf-8"))

signal.alarm(600)
ans = input('message =').strip().encode()

if ans == message:
    print(flag)
else:
    print("🧙")

outline

secret:

\begin{align*} m &= \sum_{i=0}^{127} 256^i \cdot r_i \\ \mathrm{where} \\ r_i &= \mathrm{0x6f\ or\ 0x4f} \end{align*}

given:

\begin{align*} M&: \mathrm{640\ bits\ prime\ number} \\ S &= m \mod M \end{align*}

target:

m

solution

\begin{align*} m &= \sum_{i=0}^{127} 256^i \cdot r_i \\ \rightarrow m &= \sum_{i=0}^{127} 256^i \cdot (79 + 32 \cdot r'_i) \\ &= \sum_{i=0}^{127} 79 \cdot 256^i + \sum_{i=0}^{127} 32 \cdot 256^i \cdot r'_i \\ \rightarrow m' &= \sum_{i=0}^{127} 32 \cdot 256^i \cdot r'_i \\ \mathrm{where} \\ r'_i &= \mathrm{0\ or\ 1} \\ m' &= m - \sum_{i=0}^{127} 79 \cdot 256^i \end{align*}

for subset sum problem, I want to get

S_{\mathrm{want}} = \sum_{i=0}^{127} \left( 32 \cdot 256^i \cdot r'_i \mod M \right)

but given parameter is $S$

\begin{align*} S_{\mathrm{given}} &= \left( \sum_{i=0}^{127} 32 \cdot 256^i \cdot r'_i \right) \mod M \\ \mathrm{where} \\ S_{\mathrm{given}} &= \left(S - \sum_{i=0}^{127} 79 \cdot 256^i \right) \mod M \end{align*}

Note that the mod M has only been done 128 times.

\begin{align*} S_{\mathrm{want}} &= S_{\mathrm{given}} + x M \\ \mathrm{where} \\ x &< 128 \\ \because S_{\mathrm{want}} &< 128 M \\ \end{align*}

The only thing that became a famous subsum problem is to do LLL.

code

import os
import socket

def solve(FLAG, S, M, v, counter):
    mat = []
    for i in range(len(v)):
        vv = []
        for j in range(len(v)+1):
            vv.append(2 if i == j else 0)
        vv[-1] = v[i] * boost
        mat.append(vv)
    vv = []
    for i in range(len(v)+1):
        vv.append(-1)
    vv[-1] = -(S + counter * M) * boost
    # print("value:", S + counter * M)
    # vv[-1] = -cheet * boost
    mat.append(vv)

    mat = matrix(ZZ, mat).LLL()
    # print(mat)

    ans = ""
    for v in mat:
        res = []
        if v[-1] != 0:
            continue
        f = True

        for i in range(len(v)-1):
            if v[i] != 1 and v[i] != -1:
                f = False
            if v[i] == -1:
                res.append(i)

        if not f:
            continue

        ans = ""
        for j in reversed(range(len(FLAG))):
            if j in res:
                ans += chr(FLAG[j]).upper()
            else:
                ans += chr(FLAG[j]).lower()
    return ans

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((os.getenv('SECCON_HOST'), int(os.getenv('SECCON_PORT'))))
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
msg = s.recv(1024).split()

M = int(msg[2])
S = int(msg[5])
FLAG = msg[8]

N = len(FLAG)
boost = 100

S = ((S - (int.from_bytes(FLAG, 'little') % M)) % M)

v = [1]
while len(v) < len(FLAG):
    v.append((v[-1] * 256) % M)

v = list(map(lambda x: (x * (ord('o') - ord('O')) % M), v))

for i in range(N):
    ans = solve(FLAG, S, M, v, i)
    if ans != "":
        s.send(ans.encode() + b"\n")
        break

print(s.recv(1024).decode('utf-8')[:-1])

cerberus

problem

import base64
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from flag import flag
import signal

key = get_random_bytes(16)
block_size = 16

# encrypt by AES-PCBC
# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
def encrypt(m):
    cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
    m = pad(m, 16)
    m = [m[i : i + block_size] for i in range(0, len(m), block_size)]

    iv = get_random_bytes(16)

    c = []
    prev = iv
    for m_block in m:
        c.append(cipher.encrypt(strxor(m_block, prev)))
        prev = strxor(c[-1], m_block)

    return iv, b"".join(c)


# decrypt by AES-PCBC
# https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
def decrypt(iv, c):
    cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
    c = [c[i : i + block_size] for i in range(0, len(c), block_size)]

    m = []
    prev = iv
    for c_block in c:
        m.append(strxor(prev, cipher.decrypt(c_block)))
        prev = strxor(m[-1], c_block)

    return b"".join(m)


# The flag is padded with 16 bytes prefix
# flag = padding (16 bytes) + "SECCON{..."
signal.alarm(3600)
ref_iv, ref_c = encrypt(flag)
print("I teach you a spell! repeat after me!")
print(base64.b64encode(ref_iv + ref_c).decode("utf-8"))

while True:
    c = base64.b64decode(input("spell:"))
    iv = c[:16]
    c = c[16:]

    if not c.startswith(ref_c):
        print("Grrrrrrr!!!!")
        continue

    m = decrypt(iv, c)

    try:
        unpad(m, block_size)
    except:
        print("little different :(")
        continue

    print("Great :)")

outline

Padding Oracle Attack with PCBC mode

But, The first 3 blocks must not be changed. (Adding block is valid.)

assume these variables:

plain text blocks: m1, m2, m3, ...
AES applyed blocks: a1, a2, a3, ...
cipher text blocks: c1, c2, c3, ...
initial vector: iv

decryption Algorithm

solution

Repeating the ciphertext twice cancels each other out, so the last block has the same meaning as:

All you have to do is Padding Oracle Attack :)

code

import socket
import base64
from Crypto.Util.strxor import strxor
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import bytes_to_long, long_to_bytes
import copy
import os

block_size = 16

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((os.getenv("SECCON_HOST"), int(os.getenv("SECCON_PORT"))))
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
msg = s.recv(1024)

msg = msg.split()[-2]  # base64

ref_c = base64.b64decode(msg)

res = b""

prev = copy.deepcopy(ref_c[:16])
for k in range(4):
    ans = []
    for j in range(16):
        for i in range(len(ans)):
            ans[i] ^= (j) ^ (j + 1)

        for i in range(256):
            c = copy.deepcopy(ref_c)

            iv = c[:16]
            iv = iv[: (15 - j)] + bytearray([i]) + bytearray(ans)

            c = c[16:]
            c = [c[i : i + block_size] for i in range(0, len(c), block_size)]

            c.append(c[0])
            c.append(c[1])
            c.append(c[2])
            c.append(c[3])

            c.append(c[k])
            c = b"".join(c)
            s.send(base64.b64encode(iv + c) + b"\r\n")

            r = s.recv(1024)
            if b"Great" in r:
                ans = [i] + ans
                break

    m = strxor(strxor(bytes(ans), b"\x10" * 16), prev)
    res += m

    c = copy.deepcopy(ref_c)

    iv = c[:16]
    c = c[16:]
    c = [c[i : i + block_size] for i in range(0, len(c), block_size)]
    prev = strxor(m, c[k])

print(unpad(res, 16)[16:].decode())

case insensitive

problem

#!/usr/bin/env python3

from flag import flag
import signal
import bcrypt

def check_and_upper(message):
    if len(message) > 24:
        return None
    
    message = message.upper()

    for c in message:
        c = ord(c)
        if ord("A") > c or c > ord("Z"):
            return None
    
    return message

signal.alarm(600)
while True:
    mode = input(
        """1. sign
2. verify
mode: """
    ).strip()

    ## sign mode ##
    if mode == "1":
        message = check_and_upper(input("message: ")) # case insensitive

        if message == None:
            print("invalid")
            continue

        salt = bcrypt.gensalt(5)
        print("mac:", bcrypt.hashpw((message + flag).encode(), salt).decode("utf-8"))

    ## verify mode ##
    else:
        mac = input("mac: ")
        message = check_and_upper(input("message: ")) # case insensitive

        if message is None:
            print("invalid")
            continue

        print("result:", bcrypt.checkpw((message + flag).encode(), mac.encode()))

outline

# encryption: 
S = input()
len(S) <= 24
'A' < ord(S[i]) <= 'Z'
return bcrypt(S.upper() + flag)

solution

Due to the trait of the algorithm, bcrypt omits more than 72 characters.
bypass the length of string: 'ﬃ'.upper() -> 'ffi', 'ß'.upper() -> 'ss'

code

import os
import socket 
import string
import bcrypt

def make_letters(cnt):
    res = 'ﬃ' * (cnt // 3)
    if cnt % 3 == 1:
        res += "s"
    elif cnt % 3 == 2:
        res += "ß"
    return (res.encode(), res.upper().encode())

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((os.getenv('SECCON_HOST'), int(os.getenv('SECCON_PORT'))))
s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

msg = s.recv(1024) # ~~~ mode:

ans = b""

for i in range(71, -1, -1):
    s.send(b"1" + b"\n")
    s.recv(1024) # message: 

    msg1 = ''
    msg2 = ''

    msg1, msg2 = make_letters(i)
    s.send(msg1 + b"\n")
    res = s.recv(1024).split()
    mac = res[1]

    res = False

    for c in string.printable[:-5]:
        c = c.encode()
        if bcrypt.checkpw(msg2 + ans + c, mac):
            res = True
            ans += c
            break

    if not res:
        break

print(ans.decode('utf-8'))

pppp

problem

outline

solution

code

oOoOoO

problem

outline

solution

code

cerberus

problem

outline

decryption Algorithm

solution

code

case insensitive

problem

outline

solution

code

Discussion