Ruby and Crypto

Hace poco comencé un curso de criptografía en Coursera.org, la verdad ha sido todo un desafío encontrar el tiempo para ver los videos y hacer las tareas. Pero no obstante si bien estoy terminando cansadísimo he logrado más o menos entender e incorporar algunos conocimientos. Ayer por la noche terminé una de las tareas de programación que consistía en implementar un algoritmo para descifrar códigos de un One Time Pad mal utilizado . Decidí implementarlo en Ruby que es uno de los lenguajes que estoy aprendiendo.

One Time Pad

El One Time Pad es un método de criptografía que asegura perfect secrecy (secreto perfecto) entendiéndose por esto que si alguien tiene el texto cifrado no puede llegar al texto original. El One Time Pad es relativamente simple y se basa en generar una llave del mismo largo que el mensaje original y luego realizar una operación XOR entre el el texto original y la llave generada. El one time pad es rara vez implementado de manera pura en soluciones, ya que el componente teórico faltante es un verdadero generador de números aleatorios ( por lo cual recurrimos a los números pseudoaleatorios) en la vida real, por esto y por que generar llaves del mismo tamaño que el contenido original es en muchos casos poco práctico.

Errores en la implementación

Un error fatal en la implementación del One Time Pad es el uso de la misma llave generada para más de un mensaje, dado que siendo T el texto original y K la llave T XOR K da como resultado CT (mensaje cifrado), suponiendo que tenemos T1 y T2 cifrado con la misma llave por las propiedades de la operación XOR damos que:

T1 XOR K = CT1
T2 XOR K = CT2

CT1 XOR CT2 = T1 XOR T2

Esto no nos da de por si el mensaje original pero si el XOR de los mensajes originales, a partir de allí utilizaremos un método denominado cribbing que consiste en realizar una operación XOR con una frase que presupongamos se encuentra en el mensaje. ¿Que frase? es recomendable utilizar las más frecuentes en el idioma original del lenguaje, es así como si es inglés podremos probar utilizando “the” o “with” que son palabras frecuentemente encontradas en el idioma, si presuponemos que el mensaje se trata de un reporte del clima por ejemplo utilizaremos palabras relacionadas a esto.

Entonces utilizando esta palabra  denominada CRIB tenemos que al hacer ( CT1 XOR CT2 ) XOR CRIB (en cualquiera de las posiciones de CT1 XOR CT2) si la palabra existe en el segmento del mensaje original, se revelara el fragmento de carateres originales de uno de los mensajes.

source: imgur.com

Para realizar esto cree un pequeño programita que pueden ver en mi página de github. Estoy casi seguro que este programa contiene algunos errores, pero ya los depuraré y de momento me sirvió para descubrir el mensaje original.

Para realizar el programa aprendi bastante sobre arrays, y sobre la operación pack/unpack de Ruby que permite convertir cadenas ASCII a distintos formatos (binario, hex, etc), la operación zip, el operador XOR ^ y varias otras cosas, entre ellas que no se debe utilizar nunca más de una vez la misma llave de OTP.

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket