Tags: dsa crypto rev

Rating:

## Gene

I played this CTF as part of the team Organisers. These challenges were solved as a big group effort including British EBFE, Esrever, Robin and V01d. The crypto challenges of this competition were really interesting and challening. I feel lucky to have been able to play with such a talented team, who helped show me how these more advanced challenges can be interpreted and solved.

### Step Zero: Guessing

Before the crypto side of this challenge can begin the first thing we needed to do was reverse the binary file given with the challenge. While the team worked on the reversing side I played around with the socket and tried to start guessing what might be going on.

Connecting to the server nc pwnable.org 23334 we are given three options:


1. Sign message
2. Verify message
3. Get flag


When we want to sign a message, we are asked to supply a length 78 hex string which is refered to as m0. Then we are asked for the length of the message we want to sign and finally the message we want to send m1. Signing the message we get a tuple back from the server. As an example, signing the message m1 = "testmessage" with a value of m0 = '12'*39, we obtain the tuple:




So now we know where the name gene comes from. If we sign the same pair (m0, m1) the reply from the server is the same, but if we disconnect we find that both of the values from the signing process change, suggesting a global random number is set on connection.

Futhermore signing two different messages on the same connection with the same m0 returns the same codon string. This is starting to feel like (EC)DSA, where m0 is some kind of nonce generating an r value from the base point. For it to be randomised on connection suggests that the basepoint itself is randomised.

Even assuming we are working in DSA, we have many unknowns:

- Is this ECDSA or DSA?
- What are the parameters?
- How is the base point randomised?
- Why is the r value encoded into a codon, and how do we reverse this

Even with these hunches I really couldnt make any progress on the challenge without understanding the binary. Luckily for me my team is much better at rev than I am, and they made big progress in understanding what is happening!

### Step One: Reversing

Analysing the binary, it is found that there are some globally defined constants:

- 43955934961951833386625799
- 33428203490603515565240058682678165019167410746025906092519187676
- ACAGCTUACTAUCAUTTAUTGGCAATUUAAAGGGGTUAATATTTCACTAGAACAAGTATGUACUGTGTUTUGGUUACACAUAGTGGATCGACTATUUCCCCGTAUCGATCUCGAGGTTGCUGGACUCGTA
- UUCAUGUACGTUTUCCCTAUAACGAUTUUCUUTCCATAGCUCCTUCGUCAGTAGGCUUCACCATUUAAUATAATUTCACAATAUCUCTAUAGCCUUGATUTCUGUGTAATCCUGCUUTAGTACUTTTAC

There also seems to be the implementation of sha256 and a multiplication table using UAGCT that looks like it is used to perform arithmetic over $GF(5^n)$. Note that the first of the two integers is prime.

With out assumption that this cryptosystem is some variant of DSA, we started to think that $q = 43955934961951833386625799$ would be some large prime factor of the group order. Looking at $GF(5^n)$, which would have order $5^n - 1$, we find that $(5^{129} - 1) \mod q \equiv 0$, suggesting that the group we are working with is $GF(5^{129})$.

If this is indeed a DSA variant, the hash function would appear to be sha256, the group $GF(5^{129})$ and the codon strings would then be an encoding of the elements of $GF(5^{129})$. Futher study of the multiplicaton table allows us to realise the relationship

python
codon_vals = {'U' : 0, 'A' : 1, 'G' : 2, 'C' : 3, 'T' : 4}


and we can imagine the codon string as the concat of the coefficients of a polynomical in $GF(5^{129})$, where the integers 01234 are simply represented by the letters UAGCT.

Robin quickly found a way to do this in sage

python
# Convert from codon string to polynomical coeffs
I = lambda s: list(map(int, s.translate("".maketrans("UAGCT", "01234"))))

# CODON_MOD
m = I("ACAGCTUACTAUCAUTTAUTGGCAATUUAAAGGGGTUAATATTTCACTAGAACAAGTATGUACUGTGTUTUGGUUACACAUAGTGGATCGACTATUUCCCCGTAUCGATCUCGAGGTTGCUGGACUCGTA")

# CODON_BASE
base = J('UUCAUGUACGTUTUCCCTAUAACGAUTUUCUUTCCATAGCUCCTUCGUCAGTAGGCUUCACCATUUAAUATAATUTCACAATAUCUCTAUAGCCUUGATUTCUGUGTAATCCUGCUUTAGTACUTTTAC')

# Define structures
R.<x> = GF(5)['x']
m = R(m)
F = GF(5^129, 'x', modulus=m)
J = lambda s: F(I(s))

# From codon string to element of F
embed = lambda x: int(''.join(map(str, x.polynomial())), 5)

# From element of F to codon string
to_codon = lambda x: ''.join(map(str, x.polynomial())).translate("".maketrans("01234", "UAGCT"))

# Check convertion is working as intended
assert to_codon(base) == 'UUCAUGUACGTUTUCCCTAUAACGAUTUUCUUTCCATAGCUCCTUCGUCAGTAGGCUUCACCATUUAAUATAATUTCACAATAUCUCTAUAGCCUUGATUTCUGUGTAATCCUGCUUTAGTACUTTTAC'


We are futher motivated that we are going along the right line by noticing that the product of the two integers is

python
q = 43955934961951833386625799
n = 33428203490603515565240058682678165019167410746025906092519187676
assert n*q == 5^{129} - 1


This suggests that the group order used for the calculations in finding (r,s) is stored on the server in two factors.

All that remains is to identify the two codon strings which are global constants in the binary. If this is going to be DSA-like signing for $GF(5^{192})$ then we are going to need a modulus for the field, and a base point to perform our calculations. We find the constants strings should interpreted as the modulus and base point as

python
m = "ACAGCTUACTAUCAUTTAUTGGCAATUUAAAGGGGTUAATATTTCACTAGAACAAGTATGUACUGTGTUTUGGUUACACAUAGTGGATCGACTATUUCCCCGTAUCGATCUCGAGGTTGCUGGACUCGTA"
base = "UUCAUGUACGTUTUCCCTAUAACGAUTUUCUUTCCATAGCUCCTUCGUCAGTAGGCUUCACCATUUAAUATAATUTCACAATAUCUCTAUAGCCUUGATUTCUGUGTAATCCUGCUUTAGTACUTTTAC"


**Note**: we identify the base point as the lower degree polynomial in the pair of codon strings found in the binary.

Understanding the core of what we are working with, we now need to reverse the signing function to find out we can exploit it. We did this by opening up openssl 1.1.1 sources in one window and IDA in the other. Then going through functions looking for debug prints (which contain the source filename, line, and function name) we can start to identify each function. For those without prints, we make some guesses comparing decompilation with relevant source modules. The resulting python-interpretation for the signing function was found as

python
# g_randBn1 < g_bnFieldOrder
# g_randBn2 < g_bnFieldOrder

def sign(m0, m1):
bn0 = int(m0, 16) + g_randBn2
r = CODON_BASE ^ bn0 % CODON_MOD
h = sha256(str(m0) + m1).digest()
bn2 = bytes_to_long(h) * g_randBn1
bn2 = (bn2 + bn0) % g_bnFieldOrder
s = hex(bn2)
print("The signature is (%s, %s)\n" % (r, s))


We see that we control the input, obtain the output and that we have knowledge of CODON_BASE, CODON_MOD and g_bnFieldOrder. The only unknowns are g_randBn1 g_randBn2. In the following section we will use a pair of messages to recover these values, which we will refer to as $d_0$ and $d_1$ respectively.

### Step Two: Crypto

From our reversing of the binary, we now understand the signing server as an implementation of some sort of DSA over the finite field $GF(5^{129})$, with a tuple returned by the server: $(r,s)$.

As an attacker we have the ability to sign arbitary messages supplying a tuple $(m_0, m_1)$, where $m_0$ is a nonce-like value and $m_1$ is the message we wish to sign. The challenge is solved if given a random $m_0$, we are able to successful sign a fixed message $m_1 = \text{show_me_flag}$.

The unknowns preventing us from solving the challenge are two global secret integers $d_0$ and $d_1$, which are set randomly upon connection to the server. From the reversal of the signing, we see that these constants appear in the tuple $(r,s)$ in the form

$$r = g^{m_0 + d_0} \mod M$$

$$s = H(m_0 + m_1)*d_1 + m_0 + d_0 \mod M$$

As we have access to signing arbitary messages on the server, we can recover the global secrets by signing two messages $m_1$ and $m_1^\prime$, keeping $m_0$ fixed. To keep things short, we will denote the hash of the message as $h_1 = H(m_0 + m_1)$.

Sending the server two sets of data: $(m_0, m_1)$ and $(m_0, m_1^\prime)$ we receive the following data:
$$s = h_1*d_1 + m_0 + d_0 \mod M \\ s^\prime = h_1^\prime*d_1 + m_0 + d_0 \mod M$$

By taking the difference of these two values, we see

$$s - s^\prime = h_1*d_1 - h_1^\prime*d_1 \mod M \\$$

allowing us to recover the global secret $d_1$

$$d_1 = \frac{s - s^\prime}{h_1 - h_1^\prime} \mod M,$$

getting us half way to the solve. As we have all the following data $(m_0, m_1, h_1, d_1, s)$ we can solve the first signed message to recover $d_0$:

$$d_0 = s - m_0 - h_1*d_1 \mod M$$

Equipped with both global secret values is enough to solve the challenge and grab the flag. A full implementation is given below.

### Implementation

python
# python script for socket interaction
from gene_interact import sign as rem_sig
from gene_interact import getflag, t as sock

from hashlib import sha256

# Convert from codon string to polynomical coeffs
I = lambda s: list(map(int, s.translate("".maketrans("UAGCT", "01234"))))

# CODON_MOD
m = I("ACAGCTUACTAUCAUTTAUTGGCAATUUAAAGGGGTUAATATTTCACTAGAACAAGTATGUACUGTGTUTUGGUUACACAUAGTGGATCGACTATUUCCCCGTAUCGATCUCGAGGTTGCUGGACUCGTA")

# CODON_BASE
base = J('UUCAUGUACGTUTUCCCTAUAACGAUTUUCUUTCCATAGCUCCTUCGUCAGTAGGCUUCACCATUUAAUATAATUTCACAATAUCUCTAUAGCCUUGATUTCUGUGTAATCCUGCUUTAGTACUTTTAC')

# Define structures
R.<x> = GF(5)['x']
m = R(m)
F = GF(5^129, 'x', modulus=m)
J = lambda s: F(I(s))

# From codon string to element of F
embed = lambda x: int(''.join(map(str, x.polynomial())), 5)

# From element of F to codon string
to_codon = lambda x: ''.join(map(str, x.polynomial())).translate("".maketrans("01234", "UAGCT"))

# Check convertion is working as intended
assert to_codon(base) == 'UUCAUGUACGTUTUCCCTAUAACGAUTUUCUUTCCATAGCUCCTUCGUCAGTAGGCUUCACCATUUAAUATAATUTCACAATAUCUCTAUAGCCUUGATUTCUGUGTAATCCUGCUUTAGTACUTTTAC'

FM = Zmod(5^129 - 1)

def H(a, b):
x = sha256((a + b).encode()).hexdigest()
return int(x, 16)

# Dummy variables for testing
global_d0 = 37
global_d1 = next_prime(314) + 37

def sign(m0, m1):
x = int(m0, 16) + global_d0
r = to_codon(pow(base, x))
y = H(m0, m1) * global_d1
s = hex((x + y) % (5^129 - 1))[2:].zfill(76).upper()
return (r, s)

def recover_d1(m0, m1, m11, s0, s1):
h0 = H(m0, m1)
h1 = H(m0, m11)
return FM(s1 - s0) / FM(h1 - h0)

def recover_d0(m0, m1, s, d1):
return FM(s - H(m0, m1) * d1 - int(m0, 16))

if __name__ == "__main__":
m0 = "d" * 78
m1 = "blahx"
m11 = "blahh"
r0, s0 = rem_sig((m0, m1))
print("s0", r0, s0)
r1, s1 = rem_sig((m0, m11))
print("s1", r1, s1)
s0, s1 = map(lambda x: int(x, 16), [s0, s1])
print("d1", d1 := recover_d1(m0, m1, m11, s0, s1))
print("d0", d0 := recover_d0(m0, m1, s0, d1))
global_d0 = d0
global_d1 = d1
A = sign("12" * 39, "purple")
B = rem_sig(("12" * 39, "purple"))
print(A == B)
print(getflag(sign))
sock.interact()


### Flag

flag{TTAUUTCAGUGUGGTTGAAUAUAT}

Original writeup (https://jack4818.github.io/0CTF/#gene).