카테고리: Write-up (Page 2 of 3)

Write-up을 업로드합니다.

[PlaidCTF 2019] Project Eulernt

Guys, guys, don’t fight. I’m sure we’ll be able to come up with something roughly equal.

source

eulernt.pwni.ng:5555

NOTE: We originally uploaded the wrong version. It is still available here if you really want it: wrong version.


How to solve

We need to get a divisor of 333! that is close to (333!)^{1/2}.

Just factorize with factorDB. There are some p^ks of which k is odd. Let’s define a product of those ps as v := \prod p.

So, we can easily get (333! / v) ^ {1/2}. The next step is to calculate a value which is similar to v ^ {1/2}.

Let’s just guess we can make the value with primes {2, 3, 5, 7, 11, 13, 17, 19, 23}. Then try all possible values nearby v ^ {1/2}. If you can get from this set, just add more primes.

import gmpy2

primes = [3, 5, 7, 19, 29, 37, 43, 47,
          59, 61, 89, 97, 101, 103, 107,
          109, 167, 173, 179, 181, 191,
          193, 197, 199, 211, 223, 227,
          229, 233, 239, 241, 251, 257,
          263, 269, 271, 277, 281, 283,
          293, 307, 311, 313, 317, 331]

v = 1
for p in primes:
    v *= p

N = 1
for i in range(2, 333):
    N *= i

Nv_root = gmpy2.isqrt(N // v)
v_root = gmpy2.isqrt(v)

# Rough upper limit
lim = v_root + v_root // 10000
primes = [3, 5, 7, 11, 13, 17, 19, 23]

def backtrack(idx, val):
    if idx == len(primes):
        lg = int(math.log(v_root, 2) - math.log(val, 2))
        final = val * (2 ** lg) * Nv_root
        fstr = str(final)
        if len(fstr) == 349 and fstr[:8] == '32147263':
            print(final)
        final *= 2
        fstr = str(final)
        if len(fstr) == 349 and fstr[:8] == '32147263':
            print(final)
        return

    while True:
        val *= primes[idx]
        if val > lim:
            return
        backtrack(idx + 1, val)

backtrack(0, 1)

From this, I was able to get a value:

3214726365718308699390009351051926320347863432801378170603206865184662872923685805900796110576640315841185356341136473888821110903341917546848786593096487214784202625564775154918631601168022399388653631105727651790627380050049166043926298612848761901579219048962836676642657563673663196096066312251333672960000000000000000000000000000000000000000000

The flag is PCTF{R3fr3sh1ngly_Sm00th}.

[PlaidCTF 2019] Horst

They say 3 rounds is provably secure, right? Download


How to solve

Permutations can be handled as matrices.

For given key k and plaintext (x, y), the result of one-round encryption is:

(x_1, y_1) = (y, xk^{-1}yk)

Let’s do this for three rounds!

(x_2, y_2) = (xk^{-1}yk, yk^{-1}xk^{-1}yk^2)
(x_3, y_3) = (y_2, xk^{-1}ykk^{-1}y_2k) = (y_2, xk^{-1}yy_2k)

If we define t = yy_2, we can say that

(yx_3, y_3) = (t, xk^{-1}tk)

So, the three-round encryption is not different from the one-round one!

From this, just run backtracking for x^{-1}y_3 = k^{-1}tk to get proper k that satisfies the both sets.

import random
from hashlib import sha1
from horst import Permutation

with open('data.txt', 'r') as f:
    data = eval(f.read())

(x1, y1), (t1, u1) = data[0]
(x2, y2), (t2, u2) = data[1]

# Left-hand side: l
l1, l2 = x1.inv() * u1, x2.inv() * u2
# Right-hand side: k^{-1} r k
r1, r2 = y1 * t1, y2 * t2

k = [-1 for _ in range(64)]
kinv = [-1 for _ in range(64)]
called = []

def backtrack(idx):
    if idx in called:
        st = set(range(64)) - set(called)
        if len(st) == 0:
            k_str = str(Permutation(k)).encode('ascii')
            print("PCTF{%s}" % sha1(k_str).hexdigest())
            exit(0)
        backtrack(min(st))
        return

    called.append(idx)
    p, q = l1[idx], l2[idx]

    # Running backtracking for: `l = k^{-1} r k`
    # If `l[idx] = p`, then `k[r[kinv[idx]]] = p`
    # Let's say `kinv[idx] = a, r[a] = b, k[b] = p`.
    # Just do possible all the (a, b) pairs for backtracking.

    # Possible `a` values
    if kinv[idx] != -1:
        arange = [kinv[idx]]
    else:
        # Values which are not used
        arange = list(set(range(64)) - set(kinv))

    for a in arange:

        # If k[a] is assigned, flag_ka is True.
        flag_ka = False
        if kinv[idx] == -1:
            flag_ka = True
            kinv[idx] = a
            k[a] = idx

        b = r1[a]
        c = r2[a]
        
        if ((k[b] != -1 and k[b] != p) or (kinv[p] != -1 and kinv[p] != b)
           or (k[c] != -1 and k[c] != q) or (kinv[q] != -1 and kinv[q] != c)):
            # Set back
            if flag_ka:
                kinv[idx] = -1
                k[a] = -1
            continue

        # If k[b] is assigned, flag_kb is True, and so on.
        flag_kb, flag_kc = False, False
        if k[b] == -1:
            flag_kb = True
            k[b] = p
            kinv[p] = b
        if k[c] == -1:
            flag_kc = True
            k[c] = q
            kinv[q] = c
            
        backtrack(p)
        
        # Set back
        if flag_kc:
            k[c] = -1
            kinv[q] = -1
        if flag_kb:
            k[b] = -1
            kinv[p] = -1
        if flag_ka:
            kinv[idx] = -1
            k[a] = -1

    called.pop()

backtrack(0)

The flag is PCTF{69f4153d282560cdaab05e14c9f1b7e0a5cc74d1}.

[TokyoWesterns CTF 4th] mixed cipher

I heard bulldozer is on this channel, be careful!
nc crypto.chal.ctf.westerns.tokyo 5643


  • Download the chal: here.

How to solve

To decrypt the flag, we need two things: the AES key and the IV when the flag is generated.

IV

IV is generated by random.getrandbits(). Python random uses Mersenne Twister, and it is able to recover the state of the Python random generator with 624 32-bit integers. See this link for detail.

You can check that [c]MT::untemper[/c] works normally with this code.

from pwn import *

r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
menu_str = '4: get encrypted key'
r.recvuntil(menu_str)

rand_values = []
def encrypt(t):
    r.sendline('1')
    r.sendline(t)
    l = r.recvuntil(menu_str)

    # Store random values to restore MT
    iv = int(l.split('AES: ')[1][:32], 16)
    for i in range(4):
        rand_values.append( (iv >> (32 * i)) & ((1 << 32) - 1) )

    rsa = int(l.split('RSA:')[1].split('AES:')[0], 16)
    return rsa

for i in xrange(256):
    encrypt('\x00')

# MT Untemper: http://mslc.ctf.su/wp-content/uploads/files/svalka/mt.py
from mt import untemper
mt_state = tuple(map(untemper, rand_values[:624]) + [0])
random.setstate((3, mt_state, None))

for i in xrange(1024):
    rnd = random.getrandbits(128)
    assert rnd == rand_values[i], "Failed"

AES Key

  • This part is unintended.

We can get aeskey^e (\textrm{mod}\ N) by the option 4, and we can decrypt x^e (\textrm{mod}\ N) with the option 2, but it only gives the length and the last one byte of the plain message.

The problem is that they give the length. AES key is 16byte, and the RSA is 1024bit. It is possible to get (aeskey \times t)^e (\textrm{mod}\ N) for any t. So we can recover the AES key one bit by one bit, from the MSB to the LSB, by multiplying a value t that makes a difference in the length of the decrypted message.

from pwn import *
# Using encrypt() defined above

# Calculate N of RSA
N = None
for i in range(2, 8): # 2 ~ 7, total 
    enc = encrypt( chr(i) )
    if N is None:
        N = pow(i, 0x10001) - enc
    else:
        N = GCD(N, pow(i, 0x10001) - enc)

# Get encrypted AES key
r.sendline('4')
l = r.recvuntil(menu_str)
aeskey_enc = l.split('here is encrypted key :)\n')[1][:256]
aeskey_enc = int(aeskey_enc, 16)

# Check whether the length is 128 bytes, or not.
def decrypt(t):
    r.sendline('2')
    r.sendline(t)
    l = r.recvuntil(menu_str)
    lsb = l.split('RSA: ')[1].split('\n')[0]
    return lsb

recovered = 0
two_1016 = 2 ** 1016
for i in xrange(127, -1, -1):
    threshold = recovered + 2 ** i
    tmp = (two_1016 + threshold - 1) // threshold
    assert tmp * (threshold - 1) < two_1016, "Failed"

    val = aeskey_enc * pow(tmp, 0x10001, N) % N
    res = decrypt( long_to_bytes(val).encode('hex') )
    if len(res) // 2 == 128:
        recovered += 2 ** i

aeskey = recovered
print('aeskey', aeskey)

Full exploit

from pwn import *
from Crypto.Util.number import long_to_bytes, GCD
from Crypto.Cipher import AES
import random

r = remote('crypto.chal.ctf.westerns.tokyo', 5643)
menu_str = '4: get encrypted key'
r.recvuntil(menu_str)

# === Stage 1: Recover Python MT ===

rand_values = []
def encrypt(t):
    r.sendline('1')
    r.sendline(t)
    l = r.recvuntil(menu_str)

    # Store random values to restore MT
    iv = int(l.split('AES: ')[1][:32], 16)
    for i in range(4):
        rand_values.append( (iv >> (32 * i)) & ((1 << 32) - 1) )

    rsa = int(l.split('RSA:')[1].split('AES:')[0], 16)
    return rsa

# Calculate N of RSA
N = None
for i in range(2, 8): # 2 ~ 7, total 
    enc = encrypt( chr(i) )
    if N is None:
        N = pow(i, 0x10001) - enc
    else:
        N = GCD(N, pow(i, 0x10001) - enc)

for i in xrange(156 - 6):
    encrypt('\x00')

# From http://mslc.ctf.su/wp/confidence-ctf-2015-rsa2-crypto-500/
# MT Untemper: http://mslc.ctf.su/wp-content/uploads/files/svalka/mt.py
from mt import untemper
mt_state = tuple(map(untemper, rand_values[:624]) + [0])
random.setstate((3, mt_state, None))

for i in xrange(156):
    rnd = random.getrandbits(128)

iv = random.getrandbits(128)
print('next iv', iv)

r.sendline('3')
l = r.recvuntil(menu_str)
flag = l.split('coming!\n')[1].split('\n')[0][32:]
print('flag', flag)

# === Stage 2: Recover AES key ===

def decrypt(t):
    r.sendline('2')
    r.sendline(t)
    l = r.recvuntil(menu_str)
    lsb = l.split('RSA: ')[1].split('\n')[0]
    return lsb

r.sendline('4')
l = r.recvuntil(menu_str)
aeskey_enc = l.split('here is encrypted key :)\n')[1][:256]
aeskey_enc = int(aeskey_enc, 16)

# Check whether the length is 128 bytes, or not.
recovered = 0
two_1016 = 2 ** 1016
for i in xrange(127, -1, -1):
    threshold = recovered + 2 ** i
    tmp = (two_1016 + threshold - 1) // threshold
    assert tmp * (threshold - 1) < two_1016, "Failed"

    val = aeskey_enc * pow(tmp, 0x10001, N) % N
    res = decrypt( long_to_bytes(val).encode('hex') )
    if len(res) // 2 == 128:
        recovered += 2 ** i

aeskey = recovered
print('aeskey', aeskey)

r.close()

# === Stage 3: Decrypt ===

flag = flag.decode('hex')
aeskey = long_to_bytes(aeskey, 16)
iv = long_to_bytes(iv, 16)

def unpad(s):
    n = ord(s[-1])
    return s[:-n]

aes = AES.new(aeskey, AES.MODE_CBC, iv)
print(unpad(aes.decrypt(flag)))

The flag is TWCTF{L#B_de#r#pti#n_ora#le_c9630b129769330c9498858830f306d9}. I need to study the LSB decryption oracle. 🙁

[SCTF 2018 Finals] MQ

Define Function M: M(x_0,\ldots,x_{n-1}) = \sum\limits_{i=0}^{n-1} \sum\limits_{j=i}^{n-1} q_{i, j}x_i x_j + \sum\limits_{i=0}^{n-1} u_ix_i + c . (q is for quad, u is for uni. Notice that q_{i,j}=q_{j,i})

The code gives M(input) and  M(input + flag). Let’s think about F(x, y)=M(x + y) – M(x).

F(x, y)=M(x + y) – M(x) = \sum\limits_{i=0}^{n-1} \sum\limits_{j=i}^{n-1} q_{i, j} (x_i y_j + y_i x_j + y_i y_j) + \sum\limits_{i=0}^{n-1} u_i y_i

For some integer k that 0 \leq k \leq n-1, define x’:

x’_i = \begin{cases}x_i + 1 (i = k),\\x_i (i \neq k)\end{cases}

Then,

F(x’, y)-F(x, y)=\sum\limits_{i=0}^{k} q_{i, k} y_i + \sum\limits_{j=k}^{n-1} q_{k, j} y_j = q_{k,k} y_k+\sum\limits_{i=0}^{n-1}q_{i, k}y_i (\because q_{i,j}=q_{j,i})

Note that q_{k,k} appears twice.

Therefore, we can get n linear equations of flag by getting a value of F(x’, flag)-F(x, flag) for each k, and it’s clear that they are solvable.

So, do the row reduction and get the flag. The code is here:

from pwn import *

r = remote('mq.eatpwnnosleep.com', 12345)

mq_str = r.recvuntil('\n')
mq_var_str = mq_str.replace(' ', '').split('+')

quad = [ [ 0 for _ in range(32) ] for _ in range(32) ]
uni = [ 0 for _ in range(32) ]
c = 0
p = 131

# Parse MQpoly
for var in mq_var_str:
    tmp = var.split('x')
    if len(tmp) == 1:
        c = int(tmp[0])
    elif len(tmp) == 2:
        uni[ int(tmp[1])-1 ] = int(tmp[0])
    else:
        x, y, z = int(tmp[0]), int(tmp[1]), int(tmp[2])
        quad[y-1][z-1] = x
        quad[z-1][y-1] = x

# Get values
def get_value(s):
    r.send(s)
    tmp = r.recv()
    print(tmp[:4])
    return (int(tmp[2:4], 16) - int(tmp[:2], 16)) % p

base_input = [ 'a' for _ in range(32) ]
base_value = get_value( ''.join(base_input) )
value = [ 0 for _ in range(32) ]

for i in range(32):
    base_input[i] = 'b'
    value[i] = get_value( ''.join(base_input) )
    value[i] = (value[i] - base_value) % p
    base_input[i] = 'a'

print("value:", value)

# Solve (Gauss Elimination)
def xgcd(b, a):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while a != 0:
        q, b, a = b // a, a, b % a
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def mulinv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n

def swap(i, j):
    for k in range(32):
        quad[i][k], quad[j][k] = quad[j][k], quad[i][k]

def mult(i, m):
    for k in range(32):
        quad[i][k] *= m
        quad[i][k] %= p

    value[i] *= m
    value[i] %= p

def reduc(i, j, m):
    for k in range(32):
        quad[j][k] -= quad[i][k] * m
        quad[j][k] %= p

    value[j] -= value[i] * m
    value[j] %= p

for i in range(32):
    quad[i][i] *= 2 # q_{k,k} added twice in the eq
    quad[i][i] %= p

for i in range(32):
    for j in range(i, 32):
        if quad[j][i] != 0:
            break
    if i != j:
        swap(i, j)

    pivot_inv = mulinv(quad[i][i], p)
    mult(i, pivot_inv)

    for j in range(i+1, 32):
        reduc(i, j, quad[j][i] % p)

for i in range(31, -1, -1):
    for j in range(i-1, -1, -1):
        reduc(i, j, quad[j][i] % p)

print(quad)
print(value)

flag = ''.join([ chr(v) for v in value ])
print(flag)

The flag is SCTF{Try_MQ_be_happy!}.

[SCTF 2018 Finals] LCG

It is quite simple PRNG with the equation (t = 0xdeadbeef): x_i = (k_1 – t) x_{i-1} + k_1 t x_{i-2} + k_2 (mod\ k_3)

We can define y_i as y_i = x_i + t x_{i-1}, then y_i = k_1 y_{i-1} + k_2 (mod\ k_3) . So, it’s just same as the normal LCG.

I used the method to break LCG described in this link, and the solver is here.

from pwn import *

def xgcd(b, a):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while a != 0:
        q, b, a = b // a, a, b % a
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

def mulinv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n

r = remote('lcg.eatpwnnosleep.com', 12345)
inputs = []

for i in range(16):
    r.sendline('1')
    inputs.append( int(r.recvuntil('\n')) )

print(inputs)

k = 0xdeadbeef
arr = []

for i in range(15):
    arr.append(inputs[i+1] + k*inputs[i])

# http://sandeepmore.com/blog/2012/03/23/breaking-linear-congruential-generator/
def d(i, j):
    t1 = arr[i] - arr[0]
    t2 = arr[i+1] - arr[1]
    t3 = arr[j] - arr[0]
    t4 = arr[j+1] - arr[1]

    return t1 * t4 - t2 * t3

t = d(2, 3)
for i in range(3, 13):
    t, _, _ = xgcd( t, d(i, i+1) )

k3 = t if t > 0 else -t

print("k3: ", k3)

g0_inv = mulinv( (arr[1] - arr[0]) % k3, k3)
k1 = ((arr[2] - arr[1]) * g0_inv) % k3
k2 = (inputs[2] - (k1 - k) * inputs[1] - k1 * k * inputs[0]) % k3

print("k1: ", k1)
print("k2: ", k2)

s0, s1 = inputs[-2], inputs[-1]

for i in range(16):
    s0, s1 = s1, ( (k1 - k) * s1 + k1 * k * s0 + k2 ) % k3
    r.sendline( str(s1) )

r.interactive()

The flag is SCTF{LCG_is_too_simple_to_be_a_good_CSPRNG}.

« Older posts Newer posts »

© 2020 RBTree.insert()

Theme by Anders NorenUp ↑