카테고리: Crypto (Page 2 of 2)

[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}.

[PlaidCTF 2018] transducipher

At first, let’s define final_state(), which returns the last state of transduce(B, s) for input B.

def transduce(b, s=0):
    if len(b) == 0:
        return b
    d, t = T[s]
    b0, bp = b[0], b[1:]
    return [b0 ^ t] + transduce(bp, s=d[b0])

def final_state(b, s=0):
    if len(b) == 0:
        return s
    d, _ = T[s]
    b0, bp = b[0], b[1:]
    return transduce_state(bp, s=d[b0])

The problem of breaking the cipher is that there’s swapping action of left 32 bits & right 32 bits in each stage.

def swap(b):
    l = BLOCK_SIZE // 2
    m = (1 << l) - 1 return (b >> l) | ((b & m) << l)

class Transducipher:
    def __init__(self, k):
        self.k = [k]
        for i in range(1, len(T)):
            k = swap(transduceblock(k))
            self.k.append(k)

    def encrypt(self, b):
        for i in range(len(T)):
            b ^= self.k[i]
            b = transduceblock(b)
            b = swap(b)
        return b

Let’s say self.k[i] as Key_i, and block of the each stage as Data_i. (Data_0 is the input of the encrypt() function. The output of the encrypt() function is Data_6.)
Next, let’s say the left 32 bits of some block B_i as B_{i, 0}, and the right 32 bits as B_{i,1}.

From Key_i, we can write Key_{i+1, 0} and Key_{i+1, 1} like:

Key_{i+1, 1} = transduce(Key_{i, 0}, 0)
Key_{i+1, 0} = transduce(Key_{i, 1}, final\_state(Key_{i, 0}, 0))

From these, we can write out some relations of the Key_{i, j} blocks which are affected by Key_{0, 0}, with some unknown states.

Key_{1,1} = transduce(Key_{0,0}, 0)\newline Key_{3,1} = transduce(Key_{2,0}, 0)\newline Key_{5,1} = transduce(Key_{4,0}, 0)\newline Key_{2,0} = transduce(Key_{1,1}, final\_state(Key_{1,0}, 0) )\newline Key_{4,0} = transduce(Key_{3,1}, final\_state(Key_{3,0}, 0) )

Also, we can write out relations from Data_{0,0}.

Data_{1,1} = transduce(Data_{0,0} \oplus Key_{0,0}, 0)\newline Data_{3,1} = transduce(Data_{2,0} \oplus Key_{2,0}, 0)\newline Data_{5,1} = transduce(Data_{4,0} \oplus Key_{4,0}, 0)\newline Data_{2,0} = transduce(Data_{1,1} \oplus Key_{1,1}, final\_state(Data_{1,0} \oplus Key_{1,0}, 0) )\newline Data_{4,0} = transduce(Data_{3,1} \oplus Key_{3,1}, final\_state(Data_{3,0} \oplus Key_{3,0}, 0) )\newline Data_{6,0} = transduce(Data_{5,1} \oplus Key_{5,1}, final\_state(Data_{5,0} \oplus Key_{5,0}, 0) )

The key idea is that, if we just assume the unknown values from  final_state() in these relations, we can get Data_{6,0} from Key_{0,0} and Data_{0,0} immediately. There are five unknown states, so we can assume those states and get 6^5 settings for them.
From this, we can write a backtracking function for finding Key_{0,0}, from 0th bit to 31st bit.

def transduce_withstate(b, s=0): # Also returns the final state
    if len(b) == 0:
        return b, s
    d, t = T[s]
    b0, bp = b[0], b[1:]

    rb, fs = transduce_withstate(bp, s=d[b0])
    
    return [b0 ^ t] + rb, fs

# Backtracking function for first 32 bit of the first key
def backtrack_first32bit(idx, data_in, data_out, key_cand, states, data_num):
    a, b, c, d, e = states

    # First 32bits are filled
    if idx == 32:
        key_copy = [k for k in key_cand]
        data_copy = data_in[:32]
        next_states = []

        istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0) ]

        # Get states for calculating last 32bits of the key
        for i in range(5):
            i1, i2 = istates[i]
            for j in range(32):
                data_copy[j] ^= key_copy[j]
            key_copy, kstate = transduce_withstate(key_copy, i1)
            data_copy, dstate = transduce_withstate(data_copy, i2)

            if i%2 == 0:
                next_states.append(kstate)
                next_states.append(dstate)

        # Backtrack for remaining
        backtrack_last32bit(0, data_in, data_out, key_cand, next_states, states, data_num)

        return    

    for b0 in range(2): # Test the idx th bit as b0
        
        key_copy = [k for k in key_cand]
        key_copy.append(b0)
        data_copy = data_in[:idx+1]

        # Run the encryption
        istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0), (0, e) ]

        for i1, i2 in istates:
            for j in range(idx+1):
                data_copy[j] ^= key_copy[j]
            key_copy = transduce(key_copy, i1)
            data_copy = transduce(data_copy, i2)

        # Compare
        if data_copy[idx] != data_out[idx]:
            continue # Failed

        key_copy = [k for k in key_cand]
        key_copy.append(b0)
        backtrack_first32bit(idx+1, data_in, data_out, key_copy, states, data_num)

# Data of the problem
data = [[13079742441184578626, 15822063786926281121],
...
[10970386673164693022, 12683515533170128309]]

if __name__ == "__main__":
    # Change data to binary vector form
    for i in range(len(data)):
        data[i][0], data[i][1] = block2bin(data[i][0]), block2bin(data[i][1])

    # Test for each datum (total 16 data)
    for data_num in range(len(data)):
        
        # Assume five states
        for i in range(6**5):
            states = [(i // (6**j)) % 6 for j in range (5)]
            backtrack_first32bit(0, data[data_num][0], data[data_num][1], [], states, data_num)

            if i % 100 == 0:
                print(data_num, i)

        print(data_num, "end")

        if data_num > 0:
            pos_key[0].intersection_update(pos_key[data_num])

        print(len(pos_key[0]))
        if len(pos_key[0]) < 5:
            print(pos_key[0])

After finding candidates of Key_{0,0}, we can also get candidates of Key_{0,1} from Key_{0,0}. backtrack_last32bit() will do this.

Furthermore, we can re-calculate the five states, which are assumed at first, from Key_{0,1}. We can compare the value between the assumed ones and the re-calculated ones, and find out whether the assumed setting is right or not.

The key(Key_0) is 11424187353095200769, and the flag is PCTF{9e8adddea4bfe001}.

You can download the commented payload from here.

Newer posts »

© 2020 RBTree.insert()

Theme by Anders NorenUp ↑