martes, 1 de octubre de 2013

Really Simple Arithmetic - CTF ekoparty 2013

Nuevamente estuvimos en Buenos Aires en el CTF de la ekoparty.  En cuant pueda hare el post completo del evento. Pero esta es una nota cortita para resolver una duda sobre uno de los retos que me llego al correo.

"Really Simple Arithmetic" era un reto crypto, disfrazado de reto reversing. El problema era mas o menos este:

username = "ekoparty"
password = "dada50f87fd9bf5669112bec92dd"

n = 0x10ec6f04a1271aa993f663aa0a2cfL
d = 0x302d0d91c7b585df5257b0a59363bL

m = sum(ord(c) ** i for c in username for i in range(512)) % n
c = int(password, 16);

if pow(c, d, n) == m:
    print "correct :)"
else:
    print "incorrect :("

Una rutina de validacion con un usuario y su correspondiente password valido.  El reto consiste en generar el password para el usuario "ekoparty2013" ;)

No recuerdo bien donde vi este reto por primera vez, tal vez en un CSAW? buscare la referencia..

Por el codigo es obvio que se trata de RSA ( y tambien se insinua con las iniciales del nombre del reto) pero este es un RSA especial :)

Como n es relativamente pequeño, lo primero sera intentar factorizarlo. Mostrare el codigo en sage (puedes usar por ejemplo http://sagenb.org/ para evaluarlo en linea)

n = 0x10ec6f04a1271aa993f663aa0a2cfL
print factor(n)

Mas simple imposible, Obtenemos la siguiente salida:

420001 * 420029 * 420037 * 420041 * 420047 * 420073

Asi que se trata de un RSA multiprimo (ademas es el producto de primos consecutivos, pero esto es irrelevante para el reto)

Los que quieran pueden leer sobre RSA multiprimo, por ejemplo, en este paper donde se realiza el criptoanalisis de una forma de rsa multiprimo. Solo neecesitamos leer los preliminares para implementar la solucion.

En ese paper podemos leer la parte del algoritmo de generación de claves: la selección de claves se realiza garantizando que la clave y el totiente de n sean coprimos.  Entonces podemoss usar el totiente para regenerar la clave privada a partir de la publica, basta con calcular el inverso multiplicativo modular a d sobre el totiente de n:

e = inverse_mod(d, euler_phi(n))

y ya con eso el proceso es trivial.  Usamos la lógica típica de RSA para cifrar el mensaje. Aqui un ejemplo de como generar la clave:

username = "ekoparty2013"
n = 0x10ec6f04a1271aa993f663aa0a2cfL
d = 0x302d0d91c7b585df5257b0a59363bL
m = sum(ord(c) ** i for c in username for i in range(512)) % n
e = inverse_mod(d, euler_phi(n))
c = pow(m, e, n)
print hex(int(c))

Y al evaluarlo tenemos;

0xdea7152f1dbd3e7cc834182c5c0eL

y como tenemos un serial valido de ejemplo, concluimos que la flag es:  dea7152f1dbd3e7cc834182c5c0e




No hay comentarios:

Publicar un comentario