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:   Por publicar.

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:   Por publicar.

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!".

domingo, 7 de abril de 2019

Reversing(XVII): Solución Retos "Android CrackMe" (II)

En esta entrada la solución a un reto de 'reversing' de una aplicación para el sistema operativo Android que aparece en https://www.hackplayers.com/2010/12/reto-android-crackme1.html

Este reto tiene el título "Android crackme#1"mi valoración sobre su dificultad es:  ☆☆☆.

Nos dan un archivo APK (crackme1hpys.apk) y tenemos que conseguir completar el proceso de login con un usuario y contraseña correctos.

Solución: ejecuto la aplicación en un emulador de Android y se me pide que introduzca un usuario y una contraseña. Introduzco dos valores cualesquiera, pulso "Login" y se muestra un mensaje de error:

Para el análisis de la APK utilizo jadx, un decompilador de archivos APK.

Examinando las clases enseguida veo que la validación del usuario y de la contraseña que se introducen se realiza en la clase "
crackme1hpys":
Tal y como se observa en el código de la figura anterior, para pasar el proceso de login con éxito el campo "Usuario" debe contener el valor "admin3" y, además, la contraseña introducida debe ser igual al resultado de la función "doConvert", a la que se le pasa como parámetro la cadena "PBAGENFRAN456", pero ¿qué se hace en esta función?. Pues fijándome bien, enseguida reconozco que para carácter alfabético en mayúsculas de la cadena que se le pasa como parámetro (códigos ASCII en decimal del 65 al 90) se realiza ROT13, es decir, se sustituye cada letra mayúscula de la cadena por la letra mayúscula que está trece posiciones por delante en el alfabeto.

Ejemplo: para la primera letra mayúscula de la cadena que se pasa como parámetro a la función, "P" (código ASCII 80 en decimal):

(resto ((80 - 65) + 13) / 26) + 65 = (resto 28 / 26) + 65 = 2 + 65 = 67 (código ASCII en decimal de "C").

Por tanto, para obtener la contraseña correcta creo un pequeño script en python:

secreto_enc = 'PBAGENFRAN456'
secreto = ''
for i in range(len(secreto_enc)):
    if ord(secreto_enc[i]) < 65 or ord(secreto_enc[i]) > 90:
       secreto=secreto+secreto_enc[i]
    else:
       secreto=secreto+chr((((ord(secreto_enc[i])- 65) + 13) % 26) + 65)

print 'password:', secreto

Ejecuto este script:
Por tanto, la contraseña correcta es:  "CONTRASENA456".

Para comprobar si lo he hecho bien ejecuto la APK en el emulador de Android, introduzco los campos "Usuario" y "Contraseña" hallados y pulso "Login":
Y, tal y como se puede ver en la figura anterior, se muestra el mensaje de éxito.