sábado, 19 de enero de 2019

Criptografía (CXXIV): Reto 25

Continúo con un reto fácil sobre criptografía. En esta ocasión se ve involucrado el criptosistema moderno de cifrado asimétrico más utilizado actualmente, 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 25: "El tamaño sí importa (II)".

El primer reto que puse en este blog con este mismo título, "El tamaño sí importa", era un reto de esteganografía, pero como en él decía creo que el tamaño importa en muchos ámbitos de nuestra vida, y la criptografía no es una excepción. Dados los archivos asociados al reto, con la clave pública y el criptograma, ¿puedes descifrar este último?.

Dificultad:
Tipo:           Criptografía.

Recursos:   public_key.pem.
                   criptograma.enc.

******** 20/01/2019
Pista 1:     Como habrás observado el exponente de la clave pública (e) es igual a 3. Un número muy pequeño cuya utilización presenta como ventaja el agilizar el tiempo de cifrado de los mensajes en claro (m), pero que tiene claros inconvenientes. Por ejemplo: ¿Qué ocurre cuando e = 3 y m < n^(1/3)?. 

******** __/__/____
Pista 2:    Por publicar

******** __/__/____
Pista 3:     Por publicar.

******** __/__/____
Solución:  Por publicar.

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

Criptografía (CXXIII): Solución Reto 24

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

"Para descifrar el contenido del archivo asociado al reto y así obtener la solución necesitarás la clave: U0FNVUVM".

SoluciónEn la primera pista que puse para ayudar a resolver este reto decía que si sabías o averiguabas quién es la persona que aparece en la imagen que ilustra este post entonces también sabrías el criptosistema involucrado en este reto. Pues bien, busco con Google imágenes y obtengo: "Consulta más probable para esta imagen: Georges Painvin"y la Wikipedia nos cuenta que éste fue un criptoanalista francés cuyo principal logro fue romper el cifrado ADFGVX utilizado por el ejército alemán durante la Primera Guerra Mundial.
Con lo que, como también decía, puedo concluir que el criptosistema involucrado en este reto es el ADFGVX (ya escribí en su día varios posts sobre él en este blog. Ver primero de ellos).

Además, en el post en el que planteé el enunciado de este reto decía que el criptosistema involucrado está muy relacionado con el código morse (las letras ADFGVX, que son las únicas que aparecen en los criptogramas cifrados mediante este método, fueron elegidas porque son muy diferentes entre sí en código morse y ésto evitaba errores en la transmisión de los mensajes), mientras que en la segunda pista decía que el archivo de audio asociado al reto (reto24.wav) contiene precisamente una señal en código morse.

Esto último es fácilmente comprobable escuchando el archivo de audio y viendo el espectrograma de la señal:
Si decodifico esta señal enseguida reconozco y, por tanto, se confirma que el criptosistema empleado es el ADFGVX, y obtengo el criptograma.
Ahora ya, mediante la clave que se proporciona en el enunciado del reto ("U0FNVUVM"), debería estar en disposición de revertir la fase de transposición de columnas realizada en el cifrado del texto en claro, pero ésta ni parece ser muy adecuada para este criptosistema (en principio debería contener sólo letras y ésta contiene el número 0) ni parece tener nada que ver con el código morse, tal y como se afirma en la primera pista dada para ayudar a resolver este reto.

Veo si la clave dada está codificada de alguna manera, para lo que, en primer lugar, pruebo a ver si está codificada en base64:
Bastante mejor :) (ver Samuel Morse).

Utilizando como clave "SAMUEL" revierto la fase de transposición de las columnas realizada en el cifrado del texto en claro, de la siguiente manera:

1.- El criptograma tiene 442 caracteres de largo y la clave 6. Divido 442 entre 6 y obtengo que el cociente es 73 y el resto 4, por lo que tendría una tabla de 6 columnas, 4 de ellas con 74 caracteres y 2 con 73.

2.- El orden de las 6 columnas de la tabla (de izquierda a derecha) se correspondería con el orden alfabético de los 6 caracteres de la clave, es decir, sería: "A", "E", "L", "M", "S", "U".

3.- Dispongo debajo de cada una de estas columnas (por columna, de arriba a abajo y de izquierda de derecha) los caracteres del criptograma, ya he dicho que 4 de esas columnas tendrían 74 caracteres y las otras 2 tendrían 73, pero, ¿cuáles de ellas 74 y cuáles 73?. Si repaso el primer post que escribí sobre este método veo que las 4 columnas de 74 caracteres serían las correspondientes a los 4 primeros caracteres de la clave en su posición original ("S", "A", "M", "U"), mientas que la 2 columnas de 73 caracteres se corresponden con las del resto de ellos ("E" y "L"). Es decir:
4.- Y finalmente, ordeno las columnas conforme a la posición original de los caracteres de la clave utilizada (en este caso: "S","A","M","U","E", "L") y leo los caracteres de la tabla resultante por fila, de izquierda a derecha y de arriba a abajo:
Con lo que ya habría revertido la fase de transposición de columnas y lo único que faltaría para obtener el texto en claro es realizar un análisis de frecuencias de los pares de caracteres obtenidos con relación a los caracteres del idioma en el que esté escrito el mensaje en claro (en nuestro caso el español). De esta forma resolvería la fase de sustitución monoalfabética realizada como primera fase en el proceso de cifrado del texto en claro.  

Podríamos realizar el análisis de frecuencias manualmente, pero es mucho más cómodo y rápido hacerlo utilizando una herramienta on-line especializada. Para ello, sustituyo cada par de caracteres obtenido hasta ahora por un carácter arbitrario (da igual por cuál, pero yo voy a sustituir cada uno de ellos por la letra que más probablemente le correspondería conforme a la frecuencia de aparición de éstas en un texto en claro escrito en español):
Incluyo como texto cifrado en la herramienta el resultado de la sustitución realizada en el paso anterior:
Y obtengo el siguiente texto en claro (salvo pequeño error que es muy fácil de detectar y subsanar):

LOS ALEMANES CREIAN QUE EL CIFRADO ADFGVX ERA INVULNERABLE AL CRIPTOANALISIS YA QUE COMBINABA SUSTITUCION Y TRANSPOSICION Y NO ERA POSIBLE REALIZAR UN ANALISIS DE FRECUENCIAS SIN EMBARGO GEORGES PAINVIN CONSIGUIO ROMPERLO Y SU NOMBRE ES LA SOLUCION DE ESTE RETO

Por tanto, la solución es: "GEORGES PAINVIN".

******** PRÓXIMO RETO
Reto 25: "El tamaño sí importa (II)".

domingo, 13 de enero de 2019

Criptografía (CXXII): Solución Reto backdoor "rsalot"

En este post la solución a otro de los retos de criptografía de la plataforma backdoor.

Este reto tiene el título "rsalot" y mi valoración sobre su dificultad es: .

Su enunciado dice lo siguiente:


The flag is encrypted using a system that makes use of prime factorization of large numbers. Decrypt the flag from this.

Solución: lo primero que se me ocurrió fue crear un script en python para obtener el módulo y el exponente (n y e, respectivamente) de las 100 claves públicas que nos dan como recursos asociados al reto.

from Crypto.PublicKey import RSA

i = 1
print ''
print '[+] Obteniendo el modulo (n) y el exponente publico (e) de las 100 claves'
while i < 101:
    pubkeyi = open(str(i)+'.pem', 'r')
    publickeyi = RSA.importKey(pubkeyi.read())
    ni = publickeyi.n
    ei = publickeyi.e
    print ''
    print 'n'+str(i)+' ...', ni
    print 'e'+str(i)+' ...', ei
    pubkeyi.close()
    i+=1
Por lo que veo todas las claves dadas tienen el mismo exponente público, el número de Fermat para n = 4 (Fn = 22n + 1;  F4 = 224 + 1 = 65537), y a simple vista no veo nada que me pueda revelar alguna vulnerabilidad de estas claves que me permita intentar atacar el criptograma (c) que se nos proporciona como recurso asociado al reto en el archivo flag.enc.

Lo siguiente que se me ocurrió fue completar el script anterior para comprobar si algunos de los módulos (n) comparten factores primos, ya que si ésto es así podría factorizar muy fácilmente dichos módulos y obtener después las claves privadas correspondientes. Es decir, si el máximo común divisor (MCD) de los módulos (n) de dos claves públicas es diferente de 1 entonces dichos módulos comparten como factor ese  MCD y el otro factor de los respectivos módulos puede ser obtenido dividiendo cada uno de ellos entre este último, con lo que ya estaríamos en disposición de calcular el exponente privado (d) de ambas claves.

from fractions import gcd
from Crypto.PublicKey import RSA

primo_compartido = 0
i = 1
print ''
print '[+] Comprobando si los modulos de las claves publicas comparten algun factor primo'
while i < 100:
    pubkeyi = open(str(i)+'.pem', 'r')
    publickeyi = RSA.importKey(pubkeyi.read())
    ni = publickeyi.n
    ei = publickeyi.e
    j = i+1
    while j < 101:
        pubkeyj = open(str(j)+'.pem', 'r')
        publickeyj = RSA.importKey(pubkeyj.read())
        nj = publickeyj.n
        ej = publickeyj.e
        if gcd(ni,nj) != 1:
           primo_compartido = 1
           print '[+] Los modulos n'+str(i)+' y n'+str(j)+' comparten un factor primo'
        pubkeyj.close()
        j+=1
    pubkeyi.close()
    i+=1

if primo_compartido == 1:
   print '[+] Se han encontrado modulos que comparten algun factor primo'
else:
   print '[-] No se han encontado modulos que compartan algun factor primo.'
A la vista de los resultados sabemos que los módulos (n) de las claves públicas 64 y 87 (64.pem y 87.pem, respectivamente) comparten un factor primo, por lo que podemos calcular el exponente privado (d) de cada una de sus correspondientes claves privadas. Alguna de estas últimas puede ser que descifre el criptograma (c) que contiene el archivo flag.enc.

Para realizar todo ello, completo el script anterior de la siguiente manera:

from fractions import gcd
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from base64 import b64decode

def calcular_d(e, fi):
    a, b, u = 0, fi, 1
    while e > 0:
        q = b // e
        e, a, b, u = b % e, u, e, a - q * u 
    if b == 1:
       return a % fi
    print '[-] Error al calcular el exponente de la clave privada'

rsakeys = []

i = 1
print ''
print '[+] Comprobando si los modulos de las claves publicas comparten algun factor primo'
while i < 100:
    pubkeyi = open(str(i)+'.pem', 'r')
    publickeyi = RSA.importKey(pubkeyi.read())
    ni = publickeyi.n
    ei = publickeyi.e
    j = i+1
    while j < 101:
        pubkeyj = open(str(j)+'.pem', 'r')
        publickeyj = RSA.importKey(pubkeyj.read())
        nj = publickeyj.n
        ej = publickeyj.e
        if gcd(ni,nj) != 1:
           print '[+] Los modulos n'+str(i)+' y n'+str(j)+' comparten un factor primo'
           pi = ni/gcd(ni,nj)
           qi = gcd(ni,nj)
           di = calcular_d(ei, (pi-1)*(qi-1))
           print '[+] Construyendo clave privada a partir de n'+str(i)+', e'+str(i)+', d'+str(i)+', p'+str(i)+', q'+str(i)
           rsakeys.append(RSA.construct((ni, ei, di, pi, qi, )))
           pj = nj/gcd(ni,nj)
           qj = gcd(ni,nj)
           dj = calcular_d(ej, (pj-1)*(qj-1))
           print '[+] Construyendo clave privada a partir de n'+str(j)+', e'+str(j)+', d'+str(j)+', p'+str(j)+', q'+str(j)
           rsakeys.append(RSA.construct((nj, ej, dj, pj, qj, )))
        pubkeyj.close()
        j+=1
    pubkeyi.close()
    i+=1

if rsakeys != []:
   print '[+] Se han encontrado modulos que comparten algun factor primo'
   flag = open('flag.enc', 'rb')
   c = flag.read()
   flag.close()
   print '[+] Intentando el descifrado con las claves privadas construidas'
   for rsakey in rsakeys:
       try:
           rsakey = PKCS1_OAEP.new(rsakey)
           m = rsakey.decrypt(b64decode(c)) 
           print ""
           print 'texto en claro (m) ...', m
       except:
           pass
else:
   print '[-] No se han encontado modulos que compartan algun factor primo.'  

Y tras ejecutarlo ya podemos ver el texto en claro (m) y la flag contenida en él:
Por tanto, la flag es: b767b9d1fe02eb1825de32c6dacf4c2ef78c738ab0c498013347f4ea1e95e8fa.

domingo, 6 de enero de 2019

Criptografía (CXXI): Solución Reto backdoor "complex-rsa"

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

Este reto tiene el título "complex-rsa" y mi valoración sobre su dificultad es: .

Su enunciado dice lo siguiente:


noob heard that single RSA encryption can be cracked sometimes due to bad implementation, so he encrypted the message twice. See if you can break it.

Y como recursos asociados al reto nos dan los siguientes:

- pubkey1.
- pubkey2.
- flag.enc.

Solución: creo un script en python para obtener el módulo y el exponente (n y e, respectivamente) de ambas claves públicas.

from Crypto.PublicKey import RSA

# Obtener parametros de ambas claves publicas

print ''
print 'pubkey1:'

pubkey1 = open('pubkey1', 'r')
param_pubkey1 = RSA.importKey(pubkey1.read())
n1 = param_pubkey1.n
e1 = param_pubkey1.e
print '   n1  ...:', n1
print '   e1  ...:', e1
pubkey1.close()

print ''
print 'pubkey2:'

pubkey2 = open('pubkey2', 'r')
param_pubkey2 = RSA.importKey(pubkey2.read())
n2 = param_pubkey2.n
e2 = param_pubkey2.e
print '   n2  ...:', n2
print '   e2  ...:', e2
pubkey2.close()

Ejecuto este script y obtengo lo siguiente:
Como se observa en la figura anterior el módulo (n) es el mismo en ambos casos, en decimal:

554264859105764813308660999731057971935100899008191382001838196926947542874512190874402841957978974562758951331436856029517893995971179950228409634742368823490858553015862605452077729540463185207987338059905256552215054036643656077780363670065154151957507791559734841291875379738678210733333998195096643491711

Mientras que el exponente público de la primera clave en decimal es:

37507589401

y el exponente público de la segunda clave en decimal es:

4268405784672563577566143285906824408738650526784746749170468318123056940297449811287105187623419766934370809781249030117023876215912795037797160740003478418767197450012472858547143622542113157392499087427939336504102036205305906052998841826136038160560099357503377453502865716581429205507834478651

Tal y como se puede ver el exponente público de la segunda clave es muy grande, por lo que el exponente de la clave privada (d) podría estar expuesto (ver ataque de Wiener), ya que en consecuencia éste sería pequeño.

Por otra parte, en el enunciado se nos dice que el mensaje en claro (m) se cifró dos veces, es decir, entiendo que el criptograma (c2) que contiene el archivo flag.enc se obtuvo de la siguiente manera:

c1 = m^e1 mod n

c2 = c1^e2 mod n

Por lo que:

c2 = (m^e1 mod n) ^e2 mod n = m^(e1*e2) mod n 

Dicho todo esto creo el siguiente script en python para obtener la flag:

import owiener
import hashlib

# Ataque de Wiener

print('')
print ('*** Ataque de Wiener')

e1 = 37507589401
e2 = 4268405784672563577566143285906824408738650526784746749170468318123056940297449811287105187623419766934370809781249030117023876215912795037797160740003478418767197450012472858547143622542113157392499087427939336504102036205305906052998841826136038160560099357503377453502865716581429205507834478651
e  = e1*e2
n  = 554264859105764813308660999731057971935100899008191382001838196926947542874512190874402841957978974562758951331436856029517893995971179950228409634742368823490858553015862605452077729540463185207987338059905256552215054036643656077780363670065154151957507791559734841291875379738678210733333998195096643491711
d  = owiener.attack(e, n)

print ('d ...........:', d)

# Descifrado

print('')
print ('*** Descifrado')

flag = open('flag.enc', 'rb')
c  = flag.read()
c  = int(c.hex(),16)

m  = pow(c, d, n)

print ('c ...........:', c)
print('')
print ('m ...........:', m)

mh = hex(m)

print('')
print ('m (hex) .....:', mh)

# Representacion ascii del texto en claro en hexadecimal

print('')
print ('*** Flag')

ma = bytearray.fromhex(mh[2:]).decode()

print('m (ascii) ...:', ma)

# Hash SHA256 de la flag

print('')
print ('*** Hash SHA256 de la flag')

ms = hashlib.sha256(ma.encode('utf-8')).hexdigest()

print('m (SHA256) ...:', ms)

Y tras ejecutarlo obtengo la flag y el hash SHA256 de la misma para introducirlo como solución al reto: