martes, 28 de mayo de 2019

Criptografía (CXXXIV): Reto 30

En esta ocasión un reto de dificultad media que combina la esteganografía con una función hash criptográfica.

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 30: "John the Ripper".

Por el título de este reto y la imagen que ilustra este post, ya sabes que el popular software de 'crackeo' de contraseñas mediante la fuerza bruta puede jugar un papel importante en la resolución de este desafío, pero: ¿Para qué y cómo utilizarlo?.

Dificultad:
Tipo:           Esteganografía, Hash.

Recursos:   reto_30.png, solución.zip.

******** 31/05/2019
Pista 1:    Por el nombre del segundo archivo asociado al reto, solucion.zip, parece evidente que contiene la respuesta a este desafío, pero, al menos yo, no consigo 'crackear' la contraseña con la que está protegido, ni utilizando 'John the Ripper'Por tanto, creo que es un buena idea centrarse en el primero de los ficheros, reto_30.png.

******** 01/06/2019

Pista 2:    Si ya has extraído el archivo comprimido password.txt habrás visto que éste contiene una serie de valores que comienzan por $1$. ¿Qué significan?. Son valores de hash generados utilizando el algoritmo crypt(3)-MD5, y es aquí donde nuestro amigo 'John the Ripper' puede ayudarte.

******** 02/06/2019
Solución.

******** PRÓXIMO RETO
Reto 31:  "Empecemos por... ¿el final?".

viernes, 24 de mayo de 2019

Criptografía (CXXXIII): Solución Reto 29

En este post la solución a otro de los retos de criptografía sobre el criptosistema RSA que he puesto recientemente. Su enunciado decía lo siguiente:

"En el archivo asociado al reto (reto_29.txt) nos dan los valores decimales correspondientes a: p, q, dp y dq, ¿puedes descifrar el criptograma (c)?".

Solución: tras la pista dada en el post en el que enuncié este reto, para aquellos que sepan algo sobre RSA, descifrar el criptograma (c) es tan fácil como aplicar el teorema chino del resto.


Nos dan los dos factores primos (p y q) del módulo (n), dp y dq. Los dos últimos son el resultado del siguiente cálculo (en la práctica se calculan una única vez y así no deben obtenerse para cada descifrado):
dp = d mod(p-1)
dq = d mod(q-1)

Asimismo, también se precalcula (para no tener que obtenerlo cada vez que vamos a descifrar) el siguiente valor:
p-1 mod q

Y, a partir del critograma (c) que también se nos proporciona en el archivo asociado al reto, procedo al descifrado de la siguiente manera:

1.- Calculo cp = c mod p; cq = c mod q

2.- Calculo m1 = cpdp mod p; m2 = cqdq mod q

3.- El mensaje en claro (m) es: m1 + (((m2 - m1) (p-1 mod q))mod q) p

Dicho lo anterior, para obtener el mensaje en claro (m) creo el siguiente script en python:

import Crypto.Util.number

p  = 106173580239682931389627142547722999257831171755485751420548914984291463023277
q  = 97024725573258981352721169214486148772531836683230815123426383547032318244639
dp = 82768637783929703292736175179870424829982980072138899248910448548872405600793
dq = 46253925280152133213346163079911969514933734737540326180649259214793638996555
c  = 5903986077375251213373364128743214754255438662482522592294836805989467960938886932522824278823967144102657348495540833028246856934662323247888340774059845

cp = c%p
cq = c%q
m1 = pow(cp,dp,p)
m2 = pow(cq,dq,q)
m  = m1+(((m2-m1)*Crypto.Util.number.inverse(p,q))%q)*p

print''
print'*** Solucion'
print 'm (ascii) ...:', Crypto.Util.number.long_to_bytes(m)

tras ejecutar este script:
Ya puedo ver la solución al reto: Y4_3574_D35c1fl4d0_:).

******** PRÓXIMO RETO
Reto 30:   "John the Ripper".

jueves, 23 de mayo de 2019

Criptografía (CXXXII): Solución Reto 28

El  enunciado del reto de criptografía que formulé en este post era el siguiente:

"Dados (ver archivo asociado al reto) los valores en decimal correspondientes al módulo (n) y al exponente público (e), ¿puedes descifrar el criptograma (c)?".

Solución: E
n el archivo asociado al reto (reto_28.txt) no veo nada raro en los valores decimales que se proporcionan y que me pueda dar una pista sobre utilizar un ataque concreto, lo único que el tamaño del módulo es pequeño con respecto a lo habitual. Por tanto, en primer lugar intento factorizar n. Para ello utilizo una herramienta online y obtengo lo siguiente:
Es decir, frente a lo habitual, que es que el módulo sea el producto de dos número primos, en este caso hay 5 factores primos.

Esto es raro, ya que en RSA el módulo (n) es el producto de dos números primos (p y q), pero, en principio, podría serlo de más (en este reto, tal y como digo, hay cinco: p, q, r, s, t):

p = 13;
q = 557;
r  = 58163923;
s = 31509957423978419;
t = 508221080740664699289019787936896001840798152657080678401919878890044322662379008195318884737419792416128150567708788354217048821519803

Tal y como decía en este post, para descifrar el criptograma (c) necesito conocer el exponente de la clave privada (d), que se calcula como el inverso mutiplicativo del exponente la clave pública (e) módulo j(n).

Por tanto, si calculo j(n) o phi(n) podré calcular el exponente de la clave privada (d) y descifrar el criptograma (c) sin ningún problema, pero ¿cómo calculo phi(n)?.

La función phi(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n, es decir, el número de dichos enteros cuyo máximo común divisor con n es igual a 1.

En la primera pista que puse para ayudar a resolver este reto decía que si p es primo entonces phi(p) = p-1, ya que un número primo no tiene más divisores comunes con ninguno de sus anteriores que el número 1, es decir, un número primo es coprimo con todos sus anteriores.

Sabemos también que para dos números primos (p, q) phi(pq) = phi(p) phi(q) = (p-1) (q-1), lo que podemos generalizar, ya que phi es una función multiplicativa, es decir, si varios números (en nuestro caso p, q, r, s, t) son coprimos (en nuestro caso al ser primos, evidentemente, son también primos entre sí), entonces phi(pqrst) = phi(p) phi(q) phi(r) phi(s) phi(t) = (p-1) (q-1) (r-1) (s-1) (t-1).

Dicho todo lo anterior, para obtener el mensaje en claro (m) creo el siguiente script en python:

import Crypto.Util.number

print''
print'*** Calcular phi(n)'

phi = 1
factores = [13, 557, 58163923, 31509957423978419,  508221080740664699289019787936896001840798152657080678401919878890044322662379008195318884737419792416128150567708788354217048821519803]

for primo in factores:
      phi *= primo - 1

print 'phi(n) .......:', phi

print''
print'*** Calcular d'

e = 65537

d = Crypto.Util.number.inverse(e,phi)

print 'd ...........:', d

print''
print'*** Descifrado'

n = 6744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451
c = 4981417018549801962431447642124325650931495730884909753071458271804946544002258604206443185260750428256778937027399957032405875914321337784313001520933520120133065

m = pow(c, d, n)

print 'c ...........:', c
print''
print 'm ...........:', m

print''
print'*** Solucion'
print 'm (ascii) ...:', Crypto.Util.number.long_to_bytes(m)

tras ejecutar este script:
Ya puedo ver la solución al reto: Mu17ip13_Prim3_R54.

******** PRÓXIMO RETO
Reto 29: "¡Descíflalo!".

lunes, 20 de mayo de 2019

Criptografía (CXXXI): Reto 29

Otro reto en el que se ve involucrado el criptosistema RSA. En esta ocasión un poco más fácil que el anterior.

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 29: "¡Descíflalo!".

En el archivo asociado al reto (reto_29.txt) nos dan los valores decimales correspondientes a: p, q, dp y dq, ¿puedes descifrar el criptograma (c)?.

Dificultad:
Tipo:           Criptografía.

Recursos:   reto_29.txt.

******** 21/05/2019
Pista 1:     Por el título y la imagen que ilustra este post :), creo que queda claro que algo tienen que ver los chinos con este reto.

Por otra parte, como sabemos los que hemos intentado aprender algo sobre el criptosistema RSA, el teorema chino del resto se utiliza para ganar eficiencia en el descifrado, es decir, para reducir el número de operaciones del cálculo de cd mod n.

******** 24/05/2019
Solución.

******** PRÓXIMO RETO
Reto 30:   "John the Ripper".

domingo, 19 de mayo de 2019

Criptografía (CXXX): Reto 28

Otro reto de dificultad media sobre criptografía en el que se ve involucrado el criptosistema 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 28: "¿Más seguro cuantos más primos?".

Dados (ver archivo asociado al reto) los valores en decimal correspondientes al módulo (n) y al exponente público (e), ¿puedes descifrar el criptograma (c)?.

Dificultad:
Tipo:           Criptografía.

Recursos:   reto_28.txt.

******** 20/05/2019
Pista 1:     Si p es primo, phi(p) = p-1. Además, phi es una función multiplicativa, es decir, si p, q, r, ... son primos relativos o coprimos, entonces phi(pqr...) = phi(p) phi(q) phi(r) ...

******** 21/05/2019
Pista 2:     Si has probado a factorizar el módulo (n) te habrás encontrado con que en lugar de dos hay cinco factores primos. Raro, ¿no?. En RSA el módulo (n) es el producto de dos números primos (p y q), pero, en principio, podría serlo de más (p, q, r, ...). Si no entendiste la primera pista que puse quizás ahora sí lo hagas.

******** 22/05/2019
Pista 3:     Si calculamos phi de la forma indicada en la pista 1 para los cinco factores primos del módulo (n), es decir, phi(pqrst) = phi(p) phi(q) phi(r) phi(s) phi(t) = (p-1) (q-1) (r-1) (s-1) (t-1), podremos calcular el exponente privado (d) y descifrar el criptograma.

******** 23/05/2019
Solución.

******** PRÓXIMO RETO
Reto 29:   "¡Descíflalo!".