Vida de un Programador

Experiencias, ideas y programas

Challenge 14 – Ovine Cryptography: Use Google, my friend

Extracto de la descripción del reto

Extracto de la descripción del reto



Tras el lenguaje Bee del año pasado, la imagen de este reto ya me era familiar. La autora de estos dos retos es @Rosapolis.

En este caso, las ovejas, tras aprender programación, diseñaron su propio sistema criptográfico. Tras unos mensajes encriptados, nos dice al final:

Ya sabes, las ovejas son muy ecológicas, reciclando y reusando cosas, pero… no puedes reusar ciertas cosas, ¿cierto?

Bueno, bueno. Eso nos indica que han reusado alguna parte importante, y si no puede ser el mensaje original… sera la clave🙂

En este caso se uso XOR en la encriptación, y tras comprobar que la clave era mas larga que el texto, me puse manos a la obra.

Primero, pase varios cifrados a bits, para identificar ciertos “patrones”. Con esto, y debido a la propiedad de XOR, comprobé que en la mayoría, serian valores mayores que 0x40 en el primer carácter. Buscando en la tabla ASCII, esos valores corresponden a las letras (mayusculas y minúsculas). Esto me sirve luego para realizar un ataque estadístico.

Lo próximo que realizé fue mezclar dos textos encriptados entre sí. ¿Por qué?
Tal como se describe en Ataques a cifrados de flujos, en caso de reutilización de clave, mezclar dos textos cifredos, y debido a las propiedades de XOR, elimina la clave y nos devuelve los dos textos mezclados entre si. Con esto podemos realizar un anális estadístico de este mensaje, buscando texto, que al mezclarlo con este mensaje, aparezca texto “legible”.

En el caso del texto cifrado, supuse que seria inglés. Por eso mismo, empecé a buscar con mi solución la palabra “the “, una bastante usual en inglés.

Cual fué mi sorpresa al encontrar al inicio de una frase “some”. Probe con el resto, y encontré, por ejemplo, “i don”, “there” y “a com”. Con eso iba completando las frases, ya que, podia añadirle espacios, o, completar la frase palabra a palabra, que me devolvía mas letras del resto de frases.

Entonces, vi esta frase:

the story so far: In the beginning the Universe was created

“Eso me suena”, dije. Claro, es parte de la cita de Adam Douglas con la que empieza La Guía del autoestopista intergaláctico (uno de mis libros favoritos). Completé la cita, y… me apareció el resto de las citas😀

Ahora, ya que se que todo son citas conocidas… busquemos la mas larga en Google. Bueno, ya la tengo.

Cambié el primer carácter a mayúscula, para que encajara con alguna cita, ya que por las propiedades de XOR, la primera letra aparecía como minúscula al producirse la mezcla.

Lo próximo a realizar era, con la frase mas larga, mezclarla con la cifrada, obteniendo asi la clave XOR utilizada. Con ella, y como curiosidad, se descifran el resto de citas completamente:

  • I don’t want to achieve immortality through my work; I want to achieve immortality through not dying. I don’t want to live on in the hearts of my countrymen; I want to live on in my apartment.
  • Interestingly, according to modern astronomers, space is finite. This is a very comforting thought, particularly for people who can never remember where they have left things.
  • A fast word about oral contraception. I was involved in an extremely good example of oral contraception two weeks ago. I asked a girl to go to bed with me, she said ‘no.’
  • – Is there any point to which you would wish to draw my attention? – To the curious incident of the dog in the night-time. – The dog did nothing in the night-time. – That was the curious incident, remarked Sherlock Holmes.
  • Lady Glossip: Mr. Wooster, how would you support a wife? Bertie Wooster: Well, I suppose it depends on who’s wife it was, a little gentle pressure beneath the elbow while crossing a busy street usually fits the bill.
  • It’s a funny thing about looking for things. If you hunt for a needle in a haystack you don’t find it. If you don’t give a darn whether you ever see the needle or not it runs into you the first time you lean against the stack.
  • Some humans would do anything to see if it was possible to do it. If you put a large switch in some cave somewhere, with a sign on it saying ‘End-of-the-World Switch. PLEASE DO NOT TOUCH’, the paint wouldn’t even have time to dry.
  • There is a rumour going around that I have found God. I think this is unlikely because I have enough difficulty finding my keys, and there is empirical evidence that they exist.
  • In fact, the mere act of opening the box will determine the state of the cat, although in this case there were three determinate states the cat could be in: these being Alive, Dead, and Bloody Furious.
  • Scientists have calculated that the chances of something so patently absurd actually existing are millions to one. But magicians have calculated that million-to-one chances crop up nine times out of ten.
  • The story so far: In the beginning the Universe was created. This has made a lot of people very angry and been widely regarded as a bad move.
  • A common mistake that people make when trying to design something completely foolproof is to underestimate the ingenuity of complete fools.
  • My doctor says that I have a malformed public-duty gland and a natural deficiency in moral fibre and that I am therefore excused from saving universes.

La solución entonces, usa la clave XOR para descifrar la entrada, y la devuelve. Según mi experiencia en la vida real, esta clave puede provenir del algoritmo RC4. Asi que, si @Rosapolis me puede aclarar esta parte, quedaría muy contento @Rosapolis lo aclaró en los comentarios😉

3 Respuestas a “Challenge 14 – Ovine Cryptography: Use Google, my friend

  1. Pingback:Tuenti Challenge 3 finalizado + Soluciones | Vida de un Programador

  2. Rosa (@Rosapolis) 10/05/2013 en 11:31

    Un estupendo write-up!🙂 Para la key, hice algo tan simple como esto:
    open(“/dev/urandom”).read(size)
    creo que la vez que generé los ciphertexts lo hice en mi Mac, que según dice el man:
    OPERATION
    The random device implements the Yarrow pseudo random number generator algorithm and maintains its entropy pool. Additional entropy is fed to the generator regularly by the SecurityServer daemon from random jitter measurements of the kernel. SecurityServer is also responsible for periodically saving some entropy to disk and reloading it during startup to provide entropy in early system operation.

    Enhorabuena por la posición en el ranking de la primera fase y muchas gracias por participar! ^^

    • shoghicp 10/05/2013 en 12:38

      Gracias!

      Segun la idea de frikismo de las pruebas, supuse que habríais generado la clave poniendole alguna clave curiosa a RC4 (https://en.wikipedia.org/wiki/RC4). Pero bueno, eso es aún mas simple (y seguro, aunque las ovejas no saben de eso).

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: