Ir al contenido principal

Criptografía (CXV): Solución Reto Cybercamp "Redundancia innecesaria"

En este post la solución a uno de los retos de criptografía de Cybercamp 2018 Online.

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

Su enunciado dice lo siguiente:


Nuestros expertos han capturado un pendrive que contenía estos dos ficheros, pero parece que uno de ellos ha sufrido daños... (Respuesta: flag{X})


Como recursos asociados al retnos dan los archivos key.pem y secret.txt.


El primero de ellos (key.pem) contiene una clave privada RSA, pero está dañada:

-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAMSwf+/I42wFwNpDQiGuv0fb9w5Ria2JJAjzrYEYKp4HAKB8nXxmyGx6O
WAhI+4PYFYT3pf95J/mg5buCvP19fMCAwEAAQJAKuxRnyR57PL8eSVAY1VdTPNF4QwO
PZ62DHYRISEC++UtRemqE1eBPkRgswiJ91+r9y8EnVw/SvL4GYQmeovSsQIhAOq8Heinx
e4udriNOd35SgJV9e87YglCCIfCoAirR0qtAiEA1oIMcKaiRiUj2S/Q4YFTNySdT+fH16huoS
QrEapD9x8*********************************************************************
************************************************************************
-----END RSA PRIVATE KEY-----

Mientras que el segundo (secret.txt) parece ser un archivo cifrado mediante el algoritmo de cifrado asimétrico RSA.

Por el título del reto deduzco que la parte de la clave privada RSA que está dañada es redundante, es decir, puede obtenerse a partir de la parte que no está dañada y, por tanto, es posible reconstruir la clave original. Veamos qué podemos obtener.

Para ello, en primer lugar sustituimos todos los "*" de la clave que nos dan por "0", es decir:

-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAMSwf+/I42wFwNpDQiGuv0fb9w5Ria2JJAjzrYEYKp4HAKB8nXxmyGx6O
WAhI+4PYFYT3pf95J/mg5buCvP19fMCAwEAAQJAKuxRnyR57PL8eSVAY1VdTPNF4QwO
PZ62DHYRISEC++UtRemqE1eBPkRgswiJ91+r9y8EnVw/SvL4GYQmeovSsQIhAOq8Heinx
e4udriNOd35SgJV9e87YglCCIfCoAirR0qtAiEA1oIMcKaiRiUj2S/Q4YFTNySdT+fH16huoS
QrEapD9x8000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000
-----END RSA PRIVATE KEY-----

A este archivo lo llamo key_2.pem.

Antes que nada decir que el archivo PEM de clave privada RSA PKCS#1 comienza y termina con las etiquetas:

-----BEGIN RSA PRIVATE KEY-----
BASE64 ENCODED DATA
-----END RSA PRIVATE KEY-----

y que dentro de los datos codificados en base64 está presente la siguiente estructura:

RSAPrivateKey ::= SEQUENCE {
  version                 Version,
  modulus               INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1                  INTEGER,  -- p
  prime2                  INTEGER,  -- q
  exponent1            INTEGER,  -- d mod (p-1)
  exponent2            INTEGER,  -- d mod (q-1)
  coefficient            INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

El comando asn1parse es una utilidad de diagnóstico que puede analizar estas estructuras y que también se puede utilizar para extraer los datos con este formato, por lo que probamos con:

openssl asn1parse -in key_2.pem

Y obtenemos lo siguiente:
Como se observa en la figura anterior hemos obtenido (parte no dañada de la clave), lo siguiente:

Módulo (hexadecimal):
n = C4B07FEFC8E36C05C0DA434221AEBF47DBF70E5189AD892408F3AD81182A9E0700A07C9D7C66C86C7A39602123EE0F605613DE97FDE49FE68396EE0AF3F5F5F3

Exponente de la clave pública (hexadecimal):
e = 010001

Exponente de la clave privada (hexadecimal):
d = 2AEC519F2479ECF2FC79254063555D4CF345E10C0E3D9EB60C7611212102FBE52D45E9AA1357813E4460B30889F75FABF72F049D5C3F4AF2F81984267A8BD2B1

Primer factor primo del módulo (hexadecimal):
p = EABC1DE8A7C5EE2E76B88D39DDF94A0255F5EF3B6209420887C2A008AB474AAD

Segundo factor primo del módulo (hexadecimal):
q = D6820C70A6A2462523D92FD0E1815337249D4FE7C7D7A86EA1242B11AA43F71F

Los datos que faltan (parte dañada de la clave) son: d mod (p-1), d mod (q-1), (inverse of q) mod p, que se pueden obtener a partir de los anteriores y, de esta forma, reconstruir la clave privada RSA original. Tal y como dije en este postjunto con su clave privada (d, n), el receptor debe guardar los números primos p y q, y, además, para aplicar de forma óptima el teorema chino del resto en el descifrado y así simplificar los cálculos, los tres valores que faltan.

Para reconstruir la clave privada RSA original y, posteriormente, poder obtener la flag creo el siguiente script de python:

#!/usr/bin/python

from egcd import egcd
import pyasn1.codec.der.encoder
import pyasn1.type.univ
import base64

def inv(a, m):
    gcd, x, y = egcd(a, m)
    if gcd != 1:
        return None
    else:
        return x % m

def generar_pem(n, e, d, p, q, dp, dq, q1):
    key = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for x in [0, n, e, d, p, q, dp, dq, q1]:
        seq.setComponentByPosition(len(seq), pyasn1.type.univ.Integer(x))
    der = pyasn1.codec.der.encoder.encode(seq)
    return key.format(base64.encodestring(der).decode('ascii'))

# Valores de la clave correspondientes a modulo (n), exponente clave publica (e), exponente clave privada (d) y factores primos del modulo (p y q)
n = 0xC4B07FEFC8E36C05C0DA434221AEBF47DBF70E5189AD892408F3AD81182A9E0700A07C9D7C66C86C7A39602123EE0F605613DE97FDE49FE68396EE0AF3F5F5F3
e = 0x010001
d = 0x2AEC519F2479ECF2FC79254063555D4CF345E10C0E3D9EB60C7611212102FBE52D45E9AA1357813E4460B30889F75FABF72F049D5C3F4AF2F81984267A8BD2B1
p = 0xEABC1DE8A7C5EE2E76B88D39DDF94A0255F5EF3B6209420887C2A008AB474AAD
q = 0xD6820C70A6A2462523D92FD0E1815337249D4FE7C7D7A86EA1242B11AA43F71F

print('')

# Calculo de los valores que faltan en la clave: d mod (p-1), d mod (q-1), (inverse of q) mod p
print('Los valores que faltan en la clave privada RSA son:')
dp = d%(p-1)
print('dp = ', dp)
dq = d%(q-1)
print('dq = ', dq)
q1 = inv(q, p)
print('q1 = ', dq)

print('')

# Generacion de la clave privada RSA original
key = generar_pem(n, e, d, p, q, dp, dq, q1)
print('La clave privada RSA original es:')
print('key = ', key)
f = open("key_3.pem", "w")
f.write(key)
f.close()

Tras ejecutar este script obtenemos la clave privada RSA original, que se graba en el archivo key_3.pem:
Y ya sólo nos queda descifrar el contenido del archivo secret.txt:

openssl rsautl -decrypt -in secret.txt -inkey key_3.pem
Por tanto, la Flag es: flag{gk83h280fwlo2}.

Comentarios

Entradas populares de este blog

Criptografía (I): cifrado Vigenère y criptoanálisis Kasiski

Hace unos días mi amigo Iñaki Regidor ( @Inaki_Regidor ), a quien dedico esta entrada :), compartió en las redes sociales un post titulado "Criptografía: el arte de esconder mensajes"  publicado en uno de los blogs de EiTB . En ese post se explican ciertos métodos clásicos para cifrar mensajes , entre ellos el cifrado de Vigenère , y , al final del mismo, se propone un reto consistente en descifrar un mensaje , lo que me ha animado a escribir este post sobre el método Kasiski  para atacar un cifrado polialfabético ( conociendo la clave descifrar el mensaje es muy fácil, pero lo que contaré en este post es la forma de hacerlo sin saberla ). El mensaje a descifrar es el siguiente: LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC Como ya he dicho el método de Vigenère es un sistema de sustitución polialfabético , lo que significa que, al contrario que en un sistema de

Criptografía (XXIII): cifrado de Hill (I)

En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill , propuesto por el matemático Lester S. Hill , en 1929, y que se basa en emplear una matriz como clave  para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente . Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice  Dani , amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasat

¿Qué significa el emblema de la profesión informática? (I)

Todas o muchas profesiones tienen un emblema que las representa simbólicamente y en el caso de la  informática: " es el establecido en la resolución de 11 de noviembre de 1977  para las titulaciones universitarias superiores de informática, y  está constituido por una figura representando en su parte central  un  núcleo toroidal de ferrita , atravesado por  hilos de lectura,  escritura e inhibición . El núcleo está rodeado por  dos ramas : una  de  laurel , como símbolo de recompensa, y la otra, de  olivo , como  símbolo de sabiduría. La  corona  será la  de la casa real  española,  y bajo el escudo se inscribirá el acrónimo de la organización. ". Veamos los diferentes elementos tomando como ejemplo el emblema del COIIE/EIIEO (Colegio Oficial de Ingenieros en Informática del País Vasco/ Euskadiko Informatikako Ingeniarien Elkargo Ofiziala ) . Pero no sólo el COIIE/EIIEO adopta el emblema establecido en dicha resolución, sino que éste se adopta también como im