lunes, 30 de julio de 2018

Criptografía (CVIII): Solución Reto 21

El  enunciado del vigésimoprimer reto que puse en este post era el siguiente:

"Al igual que en el famoso Western, en el Departamento de Sistemas de mi empresa cometieron dos errores a la hora de generar las claves RSA de los empleados y enviarles mensajes cifrados, posibilitando que un criptoanalista en ciertas circunstancias pueda descifrar algunos de estos últimos sin necesidad de conocer la clave privada de los usuarios que los reciben. ¿Puedes descifrar sin factorizar el módulo los dos criptogramas interceptados a sendos usuarios?".

Este reto es de criptografía y su solución es:

1.- Ya decía en las pistas que puse para facilitar la resolución de este reto que podemos considerar que el "primer error" que cometió el Departamento de Sistemas de mi empresa fue utilizar el mismo módulo para diversos usuarios, aunque con diferente exponente público para cada uno de ellos, y que el "segundo error" se produciría si, además, se envían a varios de ellos criptogramas correspondientes al mismo texto en claro, ya que ello facilitaría el ataque mediante módulo común. Ver este post donde lo explico.

2.- Pues bien, vamos a ver si esto es así y para ello creo un script en Python (no soy ningún experto y seguro que se puede hacer mucho mejor):

#   Solucion Reto 21

def inv(num1, num2):
global r0, s0, t0

r0 = num1
r1 = num2
s0 = 1
t0 = 0
s1 = 0
t1 = 1

while r1 != 0:
q = r0//r1
r = r0%r1
s = s0 - q * s1
t = t0 - q * t1
r0 = r1
r1 = r
s0 = s1
s1 = s
t0 = t1
t1 = t

return  r0, s0, t0

e1 = int(input('Introduzca el exponente de la clave publica del usuario 1 (e1) ... : '))
e2 = int(input('Introduzca el exponente de la clave publica del usuario 2 (e2) ... : '))
n = int(input('Introduzca el modulo (n) comun a ambos usuarios .................. : '))
c1 = int(input('Introduzca el criptograma enviado al usuario 1 (c1) .............. : '))
c2 = int(input('Introduzca el criptograma enviado al usuario 2 (c2) .............. : '))

inv(e1, e2)

print ""
if r0 != 1:
print "No existe inverso"
m =""
elif s0 < 0:
s = t0
t = s0
inv(c1, n)
          m = ((c2 ** s)%n)*(s0 ** (-t))%n
else:
s = s0
t = t0
inv(c2, n)
m = ((c1 ** s)%n)*(s0 ** (-t))%n

print "Mensaje en claro enviado a ambos usuarios ........................ :", m

3.- Ejecuto el script anterior:
Como se observa el mensaje en claro en decimal enviado a ambos usuarios es 388768887412929781326699.

4.- Convierto el mensaje anterior a hexadecimal, lo que me da: 5253342034373734636B.

5.- Obtengo la representación ASCII y ya puedo ver la clave del reto: "RS4 4774ck":

******** PRÓXIMO RETO
Reto 22: "LO RD PL AY FA IR".

miércoles, 18 de julio de 2018

Criptografía (CVII): Reto 22

Otro reto de dificultad media sobre criptografía. En esta ocasión se trata de descifrar un criptograma obtenido mediante un criptosistema consistente en la sustitución de pares de letras o digramas empleando una tabla o matriz generada por una clave.

Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 22: "LO RD PL AY FA IR".

Evidentemente, ya sabes a qué criptosistema me refiero (ver este post en el que lo explico), pero lo importante en este reto es descifrar el criptograma asociado al mismo, cosa que entiendo no es fácil sin conocer la clave. Para facilitar esta tarea te proporciono, también como recurso asociado al reto, texto en claro conocido correspondiente al criptograma. ¿Puedes descifrarlo?.

Dificultad:
Tipo:           Criptografía.

RecursosCriptogramaQE QT DW XN QT PT CW TP AW CH NG KL WB LY TP AT QD YT LZ BE WT LY TN NB WA ZE NS QW MC SN BN BK FS WY BS QK RE NF QT QH BK KM WI NS NB WP PH HC FS GW QM BA IH KQ SN BN JQ AW SF TP TN NB CW LZ KQ QW WT SQ TA PQ PW WI BA MN WG QT BD NC WA GN PT MP NG BW GA NG SR TQ NV

Texto en claro conocido (se corresponde con el inicio del criptograma)PA RA SU PE RA RE ST ER ET OT EN DR AS QU ER EA LI ZA RU NA TA QU EC ON TE XT OC LA RO CO NO CI DO

******** 18/07/2018
Pista 1:     La persona que aparece en el retrato que ilustra este post no es Lyon Playfair. ¿Quién es?. No me acuerdo si esto puede ser relevante, incluso un atajo, para resolver este reto, pero centrémonos en el enunciado, se trata de realizar un ataque con texto claro conocido :).

******** 13/08/2018
Solución.


******** PRÓXIMO RETO
Reto 23:   Por publicar.

martes, 10 de julio de 2018

Criptografía (CVI): Reto 21

En esta ocasión un reto de dificultad media sobre criptografía en el que se vuelve a ver involucrado el algoritmo de cifrado asimétrico más utilizado en la actualidad, RSA.


Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 21: "Cometieron dos errores".

Al igual que en el famoso Western, en el Departamento de Sistemas de mi empresa cometieron dos errores a la hora de generar las claves RSA de los empleados y enviarles mensajes cifrados, posibilitando que un criptoanalista en ciertas circunstancias pueda descifrar algunos de estos últimos sin necesidad de conocer la clave privada de los usuarios que los reciben. ¿Puedes descifrar sin factorizar el módulo los dos criptogramas interceptados a sendos usuarios?.

Dificultad:
Tipo:          Criptografía.

Recursos:

- Usuario 1

n1 = 914039536398826027489480416793
e1 = 91961
c1 = 783300346788555042820201093433

- Usuario 2:

n2 = 914039536398826027489480416793
e2 = 65537
c2 = 64793720050488099891420398272


******** 12/07/2018
Pista 1:     He utilizado un módulo (n) de un tamaño muy pequeño para facilitar los cálculos a realizar y, por tanto, que se puede factorizar muy fácilmente. Sin embargo, en el enunciado del reto ya digo que debe resolverse sin factorizarlo.

Si no se trata de atacar este cifrado mediante factorización, ¿cuál puede ser el ataque a emplear?. Fijándonos un poco (he dicho módulo y no módulos) vemos que n es igual en ambas claves públicas (n, e), aunque el exponente público (e) es diferente. Esto, en principio, no compromete el cifrado (aunque en este reto podemos considerar que se trata del "primer error" cometido por el Departamento de Sistemas de mi empresa). Sólo si adicionalmente se comete un "segundo error" los criptogramas quedarían expuestos sin necesidad de que el atacante conozca la clave privada de los usuarios a los que se envían éstos. ¿Cuál es ese "segundo error"?. 

******** 13/07/2018
Pista 2:     El "segundo error" se produce si, además de utilizar el mismo módulo para diversos usuarios, se mandan a varios de ellos criptogramas correspondientes al mismo texto en claro, ya que ello facilitaría el ataque mediante módulo común. Ver este post donde lo explico.

******** 30/07/2018
Solución.

******** PRÓXIMO RETO
Reto 22:   "LO RD PL AY FA IR".

viernes, 6 de julio de 2018

Criptografía (CV): Solución Reto Hackerfire "Weak Primes"

En este post la solución a uno de los retos de criptografía de la plataforma HackerFire.

Este reto tiene el título "Weak Primes", mi valoración sobre su dificultad es: ☆☆☆, y tras su resolución se obtienen 300 puntos.

Su enunciado dice lo siguiente:


It looks like our flag.txt file was encrypted with this an RSA public key. We were able to save the public key key.pub though.


For some reason the public key file looks a little small...

Can we potentially decrypt the flag file even though we don't have the private key?.

Y nos dan los ficheros mencionados: flag.txt y key.pub.

Solución: utilizo openssl para obtener el módulo (n) y el exponente público (e) de la clave pública:
Por tanto, el módulo (n) en hexdecimal es:
9a4810d098b1cbff75682a0a9dda84315197eb4daa58186256274c0361dce60d
Y en decimal es (para ello utilizo uno de los muchos conversores de base online disponibles):
69783507722178132619820485783352049428969858299739616863075072996637000132109

Después, utilizo diverso software para factorizar el módulo (n), y, en este caso, el más eficiente es una herramienta online (factordb):
Como se observa los dos factores primos del  módulo son los siguientes:

208032399874738495835162222153730872959


335445381412686320307419854821396116851

Como en el post anterior, una vez factorizado el módulo (n), ya estamos en disposición de obtener el exponente de la clave privada (d). Para ello utilizo el software "ExpoCrip" (Criptosistemas > RSA):
El exponente de la clave privada (d) es:

35967729791529290961821813468359077736893887537311695609401294089983649127573

Y, también como en el post anteriorya podemos descifrar el criptograma. Para ello pulso el botón "Cifrar/Descifrar", en "Texto a cifrar/descifrar" incluyo el criptograma contenido en flag.txt y pulso el botón "Descifrar":
El resultado obtenido en formato texto esflag{bad_primes_are_best_primes}.

jueves, 5 de julio de 2018

Criptografía (CIV): Solución Reto CTFLearn "RSA Twins!"

En este post la solución a uno de los retos de criptografía de la plataforma CTFLearn.

Este reto tiene el título "RSA Twins!" y mi valoración sobre su dificultad es: ☆☆☆.

Su enunciado dice lo siguiente:


Aww, twins :). They’re so cute! They must be (almost) identical because they’re the same except for the slightest difference. Anyway, see if you can find my flag.

Hint: This is just math. You're probably not going to find any sort of specialized attack.


Y nos dan los siguientes datos:

n =  14783703403657671882600600446061886156235531325852194800287001788765221084107631153330658325830443132164971084137462046607458019775851952933254941568056899

e = 65537

c =  684151956678815994103733261966890872908254340972007896833477109225858676207046453897176861126186570268646592844185948487733725335274498844684380516667587

Solución: Evidentemente, los datos que nos dan se corresponden con los valores decimales del módulo (n), el exponente público (e) y un criptograma (c) obtenido mediante el algoritmo de cifrado asimétrico RSA.

Además, por el título del reto, parece claro que el módulo se ha obtenido mediante el producto de dos números primos muy cercanos entre sí ("They must be - almost - identical because they’re the same except for the slightest difference") y ya decía en este post que es muy importante que en RSA los números primos aleatorios (p y q) elegidos como factores del módulo (n) se encuentren separado entre sí una cierta distancia, ya que en caso contrario existen algoritmos que pueden ser muy eficientes en la factorización del módulo.

Vamos a ver si conseguimos factorizar el módulo (n) de forma eficiente. Para ello, utilizo el software "Fortaleza de Cifrados" (Problemas > Factorización). Ya adelanto que, de los tres disponibles, el algoritmo más eficiente para estos caso es "Dixon":
Como se observa en la figura anterior el software nos proporciona de forma prácticamente inmediata los dos factores primos del  módulo:

121588253559534573498320028934517990374721243335397811413129137253981502291629

121588253559534573498320028934517990374721243335397811413129137253981502291631

Y, también como se ve, estos dos factores son número primos consecutivos.

Evidentemente, a partir de aquí, ya estamos en disposición de obtener el exponente de la clave privada (d). Para ello utilizo el software "ExpoCrip" (Criptosistemas > RSA):
El exponente de la clave privada (d) es:

3299077807627652338114863077706564002547334263707346215942099900219591350764767217923375522666515173826485305312906020038550943028182565335370471054378473

Y ya podemos descifrar el criptograma (c). Para ello pulso el botón "Cifrar/Descifrar" y selecciono "Cifrar números":
Obteniéndose el siguiente texto en claro (m):

2511413510841857968238260398011789038678337904998872216445

Pasamos este resultado obtenido (valor decimal) a hexadecimal. Para ello utilizo un conversor de base online y obtengo que:

2511413510841857968238260398011789038678337904998872216445 escrito en base diez es igual a 666C61677B695F6C3076335F7477314E5F7072316D33737D en base dieciséis.

Y ya para obtener el resultado de este reto únicamente tenemos que obtener la cadena de caracteres que corresponde a ese código ASCII en hexadecimal mediante otro conversor online al efecto. 

Por tanto, la solución es: flag{i_l0v3_tw1N_pr1m3s}.