miércoles, julio 03, 2013

Un reto criptográfico con RSA para aprender este verano

Los autores del libro de criptografía "Cifrado de comunicaciones digitales: De la cifra clásica a RSA", Jorge Ramió y Alfonso Muñoz, han preparado un reto de criptografía RSA para animaros a aprender cosas de seguridad. El tema elegido ha tenido que ver con el escándalo de espionaje de la NSA y GCHQ  a los miembros del G8 y G20 publicados por las filtraciones de Edward Snowden. Un tema de espionaje que lo hace aún más divertido. ¡Disfrútalo!

Figura 1: Texto de Jorge Luís Borges que sirve de introducción al cripto-reto

En la cumbre anual del G8 un grupo de agentes de inteligencia del servicio GCHQ interceptan las comunicaciones privadas del presidente ruso Vladimir Putin realizadas a través de su dispositivo móvil.

Una información de un agente doble permite a los analistas del GCHQ conocer las características del dispositivo de comunicación. Entre estas características es conocido que dispone de dos algoritmos/protocolos criptográficos, uno el que se utiliza habitualmente, diseñado por el FSB y desconocido, y otro el algoritmo RSA (deshabilitado) que solo se utilizó en pruebas de compatibilidad/conexión cuando se probó el dispositivo en Rusia (por defecto, con un módulo clave de 300 bits). Por suerte, el agente doble mediante la red de espionaje desplegada en Rusia ha conseguido la clave pública RSA del dispositivo:

e = 010001
n = CD942ACE3C9390EC39AA4433E505B47E59DB5D2ADB5ABEE1F5E8A1FE7372D00B2A1A91D40B9

Los analistas de GCHQ conocedores de un fallo hardware del dispositivo consiguen inyectar código ejecutable pudiendo habilitar exclusivamente el uso del algoritmo RSA. Seguidamente, se consigue denegar el servicio al algoritmo/protocolo por defecto (el desconocido y diseñado por el FSB) de forma que el dispositivo cifre/descifremediante el algoritmo RSA. Por suerte, los servidores del FSB no deshabilitaron el uso del RSA inseguro, mientras que en los terminales sí lo hicieron.

En esta situación y mientras se pueda forzar al uso del algoritmo RSA, se podrán criptoanalizar los datos capturados, como por ejemplo este mensaje secreto:

C = C033F149B9D4455597F3502AA9015819C05EA31D3084E216801F44C7CA52E2DBE63226C04D5

¿Qué dijo el presidente? El tiempo corre en su contra…

Figura 2: Obama esperando la respuesta para saber lo que dijo Putin
Contacto: cryptoreto@gmail.com
Reconocimientos:
1. El ganador/a del reto será la primera persona que obtenga el mensaje en claro y documente brevemente el procedimiento seguido. 
2. El ganador/a del reto obtendrá un ejemplar gratuito del libro “Cifrado de las comunicaciones digitales. De la cifra clásica al algoritmo RSA” publicado por la editorial 0xWORD, gastos de envío por cuenta de los autores del libro. Será además considerado/a para futuros proyectos de la red Criptored.
Figura 3: Libro premio para el ganador

Si ya tienes el libro, es momento de poner en práctica todo lo aprendido, si no lo tienes, es momento de aprender para ganar el ejemplar, y si no ganas, siempre puedes comprarte un ejemplar para aprender y ganar en el futuro cualquier reto de criptografía.

Saludos Malignos!

Actualización: El reto lo resolvió Alfredo Beaumont, y aquí tienes su solución. Enhorabuena

11 comentarios:

  1. El mensaje oculto es: Save Edward Snowden!

    ¿Algún interesado en la solución? mi información de contacto: http://computacion.cs.cinvestav.mx/~mruiz

    ResponderEliminar
  2. Chema el mensaje cifrado en hexadecimal me esta volviendo loco. Ya tengo la clave privada pero no hay manera de saber que hacer con ese mensaje en hex :_D Alguna pista?

    ResponderEliminar
  3. El presidente no sé, yo digo que así de primeras el que hizo la interceptación se ha comido un carácter... o a lo mejor sólo es por joder :P

    ResponderEliminar
  4. Yo estoy igual, ya tengo la clave privada, y cuando descifro el mensaje obtengo un chorro de decimales que no logro convertir a ningún formato legible.

    ResponderEliminar
  5. Buenos días caballeros, pues nada, ahí nos hemos quedado en la clave privada... Cuéntanos algo Michel! :P

    ResponderEliminar
  6. La descomposición de n es:

    p--->
    39190636737150939411204087073921663586710519

    q--->
    41740216257595498333580872443988938561454154959

    el exponente privado es:

    d--->
    769800307144257428679204493063292313183363763711833429560923248203815674548704584781387409

    Por tanto el mensaje debe ser:

    1529391496484151717714706370839823084035376623140316388043797583794050740876833571562325205

    Invirtiendo el padding scheme debe ser:

    Save Edward Snowden!

    como han dicho.

    ResponderEliminar
  7. La parte que sigue sin quedarme clara es lo que comentas de "invirtiendo el padding scheme" ¿Como lo haces?

    ResponderEliminar
  8. cuando dice "invirtiendo el padding scheme" me imagino se refieren a desencriptar la información con lo siguiente

    m = c^d (mod n)

    ResponderEliminar
  9. No hay ningun "padding scheme". Una vez descifrado (c^d%n), pasas el numeraco a hexadecimal y ya tienes los bytes de la string.

    ResponderEliminar
  10. Solamente se tiene que codificar el número en hexadecimal como una cadena de caracteres, yo hice el reto en Mathematica y una de sus funciones base es FromCharacterCode, en C/C++ usar el tipo *char.

    Si hay algún interesado acá esta mi solución

    ResponderEliminar
  11. una forma muy sencilla de decodificar el resultado hexadecimal resultante 536176652045647761726420536e6f7764656e21, es separando en pares de 2 el resultado: 53,61,76,65,20,45,64,77,61,72,64,20,53,6e,6f,77,64,65,6e,21 de tal modo que con excel podamos ubicar cada uno de esos valores por celda. para poder luego aplicar la formula "=hex2dec(celdaX)" lo cual nos dara el nro correspondiente a cada hexa y a ese nro le aplicamos la formula "=char(celdaY)" lo cual nos dira la letra del codigo ASCII que corresponde a ese nro. Quedando algo asi (deje un espacio entre filas de excel):

    53 61 76 65 20 45 64 77 61 72 64 20 53 6e 6f 77 64 65 6e 21

    83 97 118 101 32 69 100 119 97 114 100 32 83 110 111 119 100 101 110 33

    S a v e E d w a r d S n o w d e n !

    Saludos!
    Miguel

    ResponderEliminar