Rolled my own Crypto

3 minutos de lectura

Se nos proporciona el código fuente de un servidor que ejecuta un Algoritmo de Firma Digital (DSA, Digital Signature Algorithm):

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()

Solamente podemos introducir mensajes $m$ con su correspondiente firma $(r, s)$. Sin embargo, no podemos obtener una firma válida $(r, s)$ porque no tenemos la clave privada $x$.

La implementación de DSA es correcta salvo por el uso de la función inverse de Crypto.Util.number. De hecho, inverse(0, q) e inverse(q, q) devuelven 0, que es matemáticamente incorrecto ya que $0^{-1} \mod{q}$ no está definido ($0$ no pertenece a $Z_q^*$, el grupo multiplicativo módulo $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

Con este problema de inverse (en lugar de usar la función pow), podemos hacer que s = 0 de manera que:

u = inverse(s, q) = 0
Luego pow(g, u * H(m), p) es pow(g, 0, p) = 1
Y también pow(y, u * r, p) es pow(y, 0, p) = 1
Por tanto, pow(g, u * H(m), p) * pow(y, u * r, p) % p % q = 1

Y entonces, tenemos que mandar r = 1.

Para obtener la flag, tenemos que enviar el mensaje "I'm the admin and I'd like to get my flag." en formato hexadecimal. Vamos a hacerlo:

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