🐕

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]]

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:
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'))))
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.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):
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):
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:
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

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



# 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'))))

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'))


ログインするとコメントできます