We were provided with several python files and a pcap dump. Part of the relevant logic is given below.

def mult(m1, m2, p):
    r = [[0,0], [0,0]]
    for i in range(2):
        for j in range(2):
            t = 0
            for k in range(2):
                t += m1[i][k] * m2[k][j]
            r[i][j] = t % p
    return r

def calcM(p, l, base):
    if l == 0:
        return [[base[1], base[0]], [base[0], base[1]]]
    x1 = [[base[0], base[1]], [base[1], (base[0] + base[1]) % p]]
    x2 = mult(x1, x1, p)
    for i in bin(l)[3:]:
        if i == '1':
            x1 = mult(x1, x2, p)
            x2 = mult(x2, x2, p)
        else:
            x2 = mult(x1, x2, p)
            x1 = mult(x1, x1, p)
    return x1

def genKey(p):
    numBytes = int(math.ceil(math.log(p, 256)))
    exp = int(os.urandom(numBytes).encode('hex'), 16) % p
    r = calcM(p, exp, (0, 1))
    return (r, exp)

A generated key is given as a pair of a random exponent \(e \in \mathbb{Z}_p\) and a matrix

$$M = \begin{pmatrix}0&1\\1&1\end{pmatrix}^e \in \mathbb{Z}_p^{2 \times 2}.$$

Based on this a server and client will agree on a shared key using a Diffie Hellman scheme.

From the pcap dump we can find the parameters exchanged:

s: 981725946171163877
s: 58449491987662952,704965025359609904
c: 453665378628814896,152333692332446539
s: 59719af4dbb78be07d0398711c0607916dd59bfa57b297cd220b9d2d7d217f278db6adca88c9802098ba704a18cce7dd0124f8ce492b39b64ced0843862ac2a6

There are several ways to solve this problem, we can directly try to break the discrete logarithm in the matrix group, we can diagonalize the matrix and solve in some extension field or we can play smart. First we recognize the exponentiated matrix as generator of Fibonacci numbers in \(\mathbb{Z}_p\). By looking at how the matrix behaves when exponentiated we can actually derive a closed formula for the \(n\)-th Fibonacci number [1]

$$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right].$$

This formula actually works over \(\mathbb{Z}_p\) (or if \(\sqrt{5}\) does not exist there, over \(\mathbb{Z}_p\left(\sqrt{5}\right)\)). We may solve above formula for \(n\), yielding

$$n = \log_\varphi \left( \frac{F_n \sqrt{5} + \sqrt{5F_n^2 \pm 4}}{2} \right)$$

where \(\varphi = \left(1 + \sqrt{5}\right)/2\). Great, we now have reduced the problem to solving a single discrete logarithm over \(\mathbb{Z}_p\) (or \(\mathbb{Z}_p\left(\sqrt{5}\right)\)).

We can easily do this using SageMath

F = GF(981725946171163877)

def fib_idx(f):
    x = sqrt(F(5))
    phi = (1 + x)/F(2)
    n = (f*x + sqrt(F(5)*f*f + F(4)))/F(2) # +/- 4
    return n.log(phi)

print "n =", fib_idx(152333692332446539)
#n = 152106608687469950

and then decrypt the flag using

p = 981725946171163877
secret = 152106608687469950
server_key = (58449491987662952, 704965025359609904)
shared = calcM(p, secret, server_key)
print decrypt(msg, str(shared))
# 9447{Pisan0_mU5t_nEv3r_hAve_THougHt_0f_bruTe_f0rce5}

References:

  1. Binet's Fibonacci Number Formula http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html

Plaid CTF 2015 - Lazy Writeup

21 April 2015 by nwert

Writeup for crypto/Lazy.

read more

BkPctf 2015 - Bowdoin Writeup

03 March 2015 by nwert

Writeup for crypto/Bowdoin.

read more

31C3 CTF - pin Writeup

30 December 2014 by nwert

Writeup for pwn/pin.

read more