9447 CTF 2015: crypto310 "Fibbed" writeup

In this challenge, we were given the source code of a server and client along with a network dump generated from letting those communicate. The description reads:

Some secret communication was captured, and we’re having trouble decrypting it. Can you help?

The protocol consists of a Diffie-Hellman-style key agreement, only the underlying operation seems to have been changed. Carefully reading the code shows that the computation is performed in the ring of 2×2 matrices over a finite field using a Montgomery ladder algorithm, so we have to find a way to solve the Diffie-Hellman problem in these (in fact, we will even compute logarithms).

The description of the protocol reads typical for a Diffie-Hellman-style system:

  • Upon receiving a new connection, the server generates a prime p of 64 bits and sends it to the client.
  • The server generates a keypair: The private key is a randomly generated integer x; the corresponding public key is the xth power of the matrix A:=(0111)(Z/p)2×2 over the residue field Z/p. As usual, the public key is sent to the client. (In fact, only the first row (ab) of the matrix is transmitted, but due to the structure of A, the second row is easily seen to be (ba+b), hence is redundant. This is tied to the fact that A is chosen in such a way that its powers’ coefficients are just the Fibonacci numbers reduced modulo p.)
  • The client then proceeds analogously, using the same p but a different randomly generated exponent y.
  • Raising the received public key to the xth or yth power, respectively, yields a shared “secret” Axy which is then used by the server to derive an AES key under which the flag is encrypted and sent to the client.

For completeness, here’s the relevant excerpts from the server code:

# fibCrypt.py

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)

# --------------------------------

# server.py

        def handle(self):
                p = fibCrypt.genPrime(8);

                self.request.sendall(str(p) + "\n")
                (key, secret) = fibCrypt.genKey(p)
                self.request.sendall(str(key[0][0]) + "," + str(key[0][1]) + "\n")

                parts = self.request.recv(200).split(",")
                theirKey = (int(parts[0]), int(parts[1]))

                shared = fibCrypt.calcM(p, secret, theirKey)
                mess = encrypt(FLAG, str(shared))
                self.request.sendall(mess + "\n")
                self.request.close()

Hence, if we are able to compute the private exponent x from the public (i.e. contained in the network dump) matrix Ax, we can simply compute the shared secret Axy and decrypt the flag. We let B(Z/p)2×2 denote the matrix Ax obtained from the packet dump, hence our task is to compute the logarithm logAB in (Z/p)2×2.

If we could diagonalize the matrix A, that is, obtain an invertible matrix S(Z/p)2×2 such that S1AS is a diagonal matrix, then also S1BS is a diagonal matrix and the exponentiation acts coefficient-wise, so we could compute the logarithm on the coefficients of the diagonalized matrices. By “exponentiation acts coefficient-wise”, we mean that for all 2×2 diagonal matrices and exponents e, (a00b)e=(ae00be). Moreover, if S is an invertible 2×2 matrix such that S1AS is diagonal (hence S1BS is), then Ax=B if and only if S1AxS=S1BS if and only if (S1AS)x=S1BS, and this means we can compute the logarithm on the diagonalized matrices’ coefficients.

However, this is not immediately possible: A’s characteristic polynomial χA=ξ2ξ1 is irreducible over Z/p, hence A has no eigenvalues in that field. But we can transition to an extension field in which A is diagonalizable: Over the field F:=(Z/p)[ξ]/χAFp2, the matrix A does have distinct eigenvalues, namely the images of ξ and ξp in F.

Using the canonical injection Z/pF, we may now consider A and B as matrices over F and compute an invertible matrix SF2×2 along with diagonal matrices DA,DBF2×2 such that DB=S1BS=S1AxS=(S1AS)x=DAx, therefore we can now compute x component-wise as the logarithm of a pair of corresponding diagonal entries of DA and DB: If DA’s upper left entry is a and DB’s upper left entry is b, then x=logab. Since a,bZ/p and p is so small, this is very much feasible.

Here’s sage code that performs that computation:

#!/usr/bin/env sage

p = 981725946171163877
pubkey = 58449491987662952, 704965025359609904

A = matrix(Zmod(p), [[0,1],[1,1]])
B = matrix(Zmod(p), [pubkey, [pubkey[1], sum(pubkey)]])

# transition to a field extension over which A (hence B) is diagonalizable
K = PolynomialRing(Zmod(p), 'x').residue_field(A.charpoly(), 'y'); y = K.gen()
A, B = A.change_ring(K), B.change_ring(K)

# diagonalize A and B over K
DA, S = A.jordan_form(transformation = True)
DB = S.inverse() * B * S

print(DA); print(DB)

# finally compute the logarithm
print('\x1b[32m{}\x1b[0m'.format(int(DB[0][0].log(DA[0][0]))))
print('\x1b[32m{}\x1b[0m'.format(int(DB[1][1].log(DA[1][1]))))

Patching the obtained output

[                       y|                       0]
[------------------------+------------------------]
[                       0|981725946171163876*y + 1]
[ 704965025359609904*y + 58449491987662952                                         0]
[                                        0 276760920811553973*y + 763414517347272856]
155959985731300133
155959985731300133

(the last two lines are the secret exponent x!) along with the other information from the network dump into the given client code and running it yields the flag!

9447{Pisan0_mU5t_nEv3r_hAve_THougHt_0f_bruTe_f0rce5}