# 9447 CTF 2015 - fibbed Writeup

30 November 2015 by nwert

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, base], [base, base]]
x1 = [[base, base], [base, (base + base) % 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


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 

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