Rolled my own Crypto

3 minutes to read

We are given the source code of a server that runs a Digital Signature Algorithm (DSA):

from Crypto.Util.number import getPrime, isPrime, inverse
from hashlib import sha256
from random import randrange

q, g = 0, 2
while not isPrime(p := 2 * q + 1) or pow(g, q, p) != 1:
    q = getPrime(256)

x = randrange(2, q)
y = pow(g, x, p)

def H(m):
    return int.from_bytes(sha256(m).digest(), 'big')

def sign(m):
    k = randrange(2, q)
    r = pow(g, k, p) % q
    s = (H(m) + r * x) * inverse(k, q) % q
    return r, s

def verify(m, r, s):
    u = inverse(s, q)
    return pow(g, u * H(m), p) * pow(y, u * r, p) % p % q == r

def main():
    print("Hello admin, here are the parameters!")
    print('p =', p)
    print('y =', y)

    print("Please sign a message to retrieve your flag:")
    m = bytes.fromhex(input('m = '))
    r = int(input('r = '))
    s = int(input('s = '))

    if not verify(m, r, s):
        print("I've called the cops!")
        exit()

    if m != b"I'm the admin and I'd like to get my flag.":
        print("Who are you??")
        exit()

    print("Verification successful! Here is your flag: ", end='')  
    with open('flag.txt', 'r') as file:
        print(file.read(), flush=True)

if __name__ == '__main__':
    main()

We are only able to enter a message $m$ and its signature $(r, s)$. However, we can’t get a legitimate $(r, s)$ signature because we don’t know the private key $x$.

The DSA implementation is correct but for the use of inverse from Crypto.Util.number. In fact, inverse(0, q) and inverse(q, q) return 0, which is mathematically incorrect since $0^{-1} \mod{q}$ is not defined ($0$ does not belong to $Z_q^*$, the multiplicative group modulo $q$):

$ python3 -q
>>> from Crypto.Util.number import inverse
>>> q = 17
>>> inverse(0, q)
0
>>> inverse(q, q)
0
>>> pow(0, -1, q)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: base is not invertible for the given modulus  
>>> pow(q, -1, q)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: base is not invertible for the given modulus

With this issue of inverse (instead of using the built-in pow function), we can set s = 0 so that:

u = inverse(s, q) = 0
Then pow(g, u * H(m), p) is pow(g, 0, p) = 1
As well as pow(y, u * r, p) is pow(y, 0, p) = 1
So pow(g, u * H(m), p) * pow(y, u * r, p) % p % q = 1

Therefore, we must send r = 1.

In order to get the flag, we must send the message "I'm the admin and I'd like to get my flag." in hexadecimal format. Let’s do it:

$ echo -n "I'm the admin and I'd like to get my flag." | xxd -p | tr -d \\n
49276d207468652061646d696e20616e6420492764206c696b6520746f20676574206d7920666c61672e

$ nc 031337.xyz 42050
Hello admin, here are the parameters!
p = 130075297914599005878561792472990971963858978284996116362111109771454513001167
y = 84075133818892653193774942063986755752314541683015608384614923289226921999657
Please sign a message to retrieve your flag:
m = 49276d207468652061646d696e20616e6420492764206c696b6520746f20676574206d7920666c61672e  
r = 1
s = 0
Verification successful! Here is your flag: ictf{TH15_I5_TH3_R34S0N}