Writeup EZDSA from Midnightsun CTF 2019 (Quals)

Ezdsa | crypto
Points: 223
Solves: 57

Someone told me not to use DSA, so I came up with this.
Service: nc ezdsa-01.play.midnightsunctf.se 31337
Download: EZDSA.tar.gz (containing ezdsa.py)

We are presented with a service. When connecting with the service we can choose to sign some data or to quit. Quitting does exactly what you’d think it does. When choosing to sign some data you must encode them as base 64 and are given back two numbers. Nothing that catches the eye so far.

Welcome to Spooners’ EZDSA
Options:

1. Sign protocol
2. Quit
   1
   Enter data:

Hello World

Not valid Base64.
Options:

1. Sign protocol
2. Quit

1

Enter data:

SGVsbG8gV29ybGQ=

(143710366199943404966739454024519272676492758552L, 811797476990494291705986835424401544027436960478L)
Options:

1. Sign protocol
2. Quit

2

KBye.
Quitting…

Taking a look at DSA

Due to the title containing DSA, us being able to sign a value and getting back two numbers one could assume that this is standard DSA. Let’s take a look at ezdsa.py, which contains the DSA implementation.

from hashlib import sha1
from Crypto import Random
from flag import FLAG

class PrivateSigningKey:

    def __init__(self):
        self.gen = 0x44120dc98545c6d3d81bfc7898983e7b7f6ac8e08d3943af0be7f5d52264abb3775a905e003151ed0631376165b65c8ef72d0b6880da7e4b5e7b833377bb50fde65846426a5bfdc182673b6b2504ebfe0d6bca36338b3a3be334689c1afb17869baeb2b0380351b61555df31f0cda3445bba4023be72a494588d640a9da7bd16L
        self.q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4bL
        self.p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5L
        self.key = int(FLAG.encode("hex"), 16)

    def sign(self, m):

        def bytes_to_long(b):
            return long(b.encode("hex"), 16)

        h = bytes_to_long(sha1(m).digest())
        u = bytes_to_long(Random.new().read(20))
        assert(bytes_to_long(m) % (self.q - 1) != 0)

        k = pow(self.gen, u * bytes_to_long(m), self.q)
        r = pow(self.gen, k, self.p) % self.q
        s = pow(k, self.q - 2, self.q) * (h + self.key * r) % self.q
        assert(s != 0)

        return r, s

Now we can see how the service computes the signature. At first the parameters gen (henceforth $g$), $q$, $p$ and key (henceforth $x$) are initialized. Note that the $x$ is the flag. So our goal is to recover the key $x$. In DSA $p,q,p$ are the public parameters and $x$ is the private key. Thus we should not be able to recover the key just from signatures. Due to this, we need to compare this implementation with the normal DSA. The following is what the code does.

\[
\mathsf{Sign}(\highlight{m}): \nl
\highlight{h} \leftarrow \mathsf{sha1}(\highlight{m}) \nl
u \leftarrow \mathsf{20\ Bytes} \nl
\mathsf{assert}\ m\not\equiv 0 \bmod {q-1} \nl
k \leftarrow \highlight{g}^{u \cdot \highlight{m}} \bmod {\highlight{q}} \nl
\highlight{r} \leftarrow (\highlight{g}^k \bmod \highlight{p}) \bmod {\highlight{q}} \nl
\highlight{s} \leftarrow (k^\highlight{q-2} \bmod \highlight{q}) \cdot (\highlight{h} + \mathbf{x} \cdot \highlight{r}) \bmod {\highlight{q}} \nl
\mathsf{assert}\ s\neq 0 \nl
\mathsf{return}\ \highlight{r},\highlight{s}
\]

So which variables do we know or can compute and which are unknown? We have highlighted all variables known to us after signing. As we can see, the private key $x$ is only used once, and we only have one other unknown there. Namely $k$, if we were to know it, we could compute $x$.

So there has to be a way to find out the value for k. For this we take a look at how this implementation differs from the normal DSA.

Firstly $k^{q-2} \bmod q$ seems weird. But this is the same as $k^{-1} \bmod q$ as we (implicitely) have $\bmod q-1$ in the exponent (cf. Fermat’s little theorem). So we can write $s\leftarrow k^{-1}(h+xr)$ which is as in the normal DSA.

Not so random

Secondly $k\leftarrow g^{u\cdot m} \bmod q$. Normally, $k$ is chosen randomly per message with $1<k<q$, but here we somehow compute k. At first this looks random, as $u$ is chosen at random, so $k^{u\cdot m} \bmod q$ should be somewhat random. But we can control $m$ so that the resulting $k$ is predictable for us. Initially we thought about setting $m=0 \bmod {q-1}$. Unfortunately, this is forbidden due to the assert. Nonetheless, let’s go over what this would cause.

\[
k\leftarrow g^{0 \cdot u} \equiv 1 \bmod q \nl
r\leftarrow (g^1 \bmod p) \bmod q \nl
s\leftarrow 1^{-1} (h+x\cdot r) \equiv h+xr \bmod q \nl
\]

So our signature would consist of $g\bmod p \bmod q$ and $h+xr \bmod q$. As we have highlighted earlier, as we know $h$ and $r$, we can recover $x \pmod q$. But the assert is still there, so this is not possible. However, we can choose $m=(q-1)/2$. Then we have $k\leftarrow g^{u \cdot (q-1)/2} \bmod q$. This always (for this parameters) leads to $k=1$ as above.

But why does this result in $k=1$? If $u$ is even, this can be easily explained using Fermat’s little theorem. If $u$ is odd, we need to take a very small step into group theory. First we need to know that if we use $\bmod n$ we are calculating in a (finite) Cyclic group $\mathbb{Z}_n$. This group has an order of $n-1$. For $k$ the group is $\mathbb{Z}_q$, with an order of $q-1$. Next we need to know that $g$ generates a subgroup of $\mathbb{Z}_q$ with a possibly smaller order. As per Lagrange’s theorem the order of the subgroup must divide the order of the parent group. The order of $\mathbb{Z}_q$ ($=q-1$) is even. Thus 2 and $(q-1)/2$ divide it and are possible orders for $g \pmod q$. In our case $g$ has an order of $(q-1)/2$ or an order that divides $(q-1)/2$. So we have $k\leftarrow g^{n \cdot (q-1)/2} \equiv g^{n \cdot k\cdot \ord(g)} \equiv (g^{\ord(g)})^{nk} \equiv 1^{nk} \equiv 1\bmod q$ for some $n$ and $k$.

Code

So now we need to code this. In the beginning, we have some conversion functions and a function to compute a modular inverse. Then we set the constants $g,p,q$ and set $m=(q-1)/2$. After this we connect to the server, send $m$ base64 encoded and read the signature. We know that $s=h+xr$, so we subtract $h$ and divide by $r$. Well, we don’t really divide but we multiply by the inverse of $r\bmod q$. Then we convert $x$ back to ascii and our flag falls out th4t_w4s_e4sy_eh?.

#!/usr/bin/env python2
from pwn import *
from base64 import b64encode, b64decode
import binascii
import re
from hashlib import sha1

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def long_to_bytes(l):
    hx = hex(l)[2:]
    if len(hx)%2 !=0:
        hx = '0'+hx
    return binascii.unhexlify(hx)

def bytes_to_long(b):
    return long(b.encode("hex"), 16)

g = 0x44120dc98545c6d3d81bfc7898983e7b7f6ac8e08d3943af0be7f5d52264abb3775a905e003151ed0631376165b65c8ef72d0b6880da7e4b5e7b833377bb50fde65846426a5bfdc182673b6b2504ebfe0d6bca36338b3a3be334689c1afb17869baeb2b0380351b61555df31f0cda3445bba4023be72a494588d640a9da7bd16
q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4b
p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5
m = (q-1)//2

c = remote('ezdsa-01.play.midnightsunctf.se',31337)
c.sendlineafter('Quit','1')#sign
c.sendlineafter('Enter data:',b64encode(long_to_bytes(m)))
sig = c.readline_contains('L)')
sig = re.search(r'\(([0-9]+)L, ([0-9]+)L\)',sig)
r = long(sig.group(1))
s = long(sig.group(2))
assert r==(g%p%q)
#s=h+x*r
h = bytes_to_long(sha1(long_to_bytes(m)).digest())
x = ((s-h)*modinv(r,q)) %q
print(long_to_bytes(x))