Crypto Badness 100 - Análisis de frecuencias

Junio 30, 2009

Actualizado: Resumen del análisis de frecuencia y reto para el lector.

Esta es la resolución no oficial del reto Crypto Badness 100 de las clasificatorias para "Captura la bandera" de la DefCon

Al ingresar a este reto nos muestran el siguiente texto:
ASI JL DUJZTED SA J EJZD JVV NBTODI, VDD FOD AHB VBFD: OFFT://YYY.AHB.MSK/TJMD2/CDN08/NSCD_122908.OFZE, PSQD GSW MWDVV? LS, JNFWJE AHB RWBX.

En este texto podemos observar lo que parece ser una HTTP URL "OFFT://YYY.AHB.MSK", y su respectivo recurso "/TJMD2/CDN08/NSCD_122908.OFZE", así que deducimos que se trata de una cifrado por sustitución simple, quiere decir que cada letra del alfabeto se sustituye por otra única letra del alfabeto.

Empezamos con un análisis de frecuencias común y corriente, extraemos las frecuencias en que aparecen los carácteres en el cifrado, y las comparamos con frecuencias ya realizadas, así que el carácter con mayor frecuencia en el texto que nos dieron, lo reemplazamos con el carácter con mayor frecuencia en el inglés (Inglés porque en todos los retos se vió este idioma)

El resultado del análisis es este:
Histograma Análisis de <crypto.txt>. Tamaño del archivo 142 bytes.
Ordenados descendentemente por frecuencia.

Nº      Subcadena    Frequencia (en %)    Frecuencia
1              D            13.5417              13
2              J             8.3333               8
3              S             7.2917               7
4              B             6.2500               6
5              F             6.2500               6
6              V             6.2500               6
7              A             5.2083               5
8              E             4.1667               4
9              N             4.1667               4
10             O             4.1667               4
11             T             4.1667               4
12             W             4.1667               4
13             H             3.1250               3
14             M             3.1250               3
15             Y             3.1250               3
16             Z             3.1250               3
17             C             2.0833               2
18             I             2.0833               2
19             L             2.0833               2
20             G             1.0417               1
21             K             1.0417               1
22             P             1.0417               1
23             Q             1.0417               1
24             R             1.0417               1
25             U             1.0417               1
26             X             1.0417               1

Si comparamos la anterior tabla con el porcentaje de frecuencia de los carácteres en el idioma inglés:

Y extraemos los carácteres del mas común al menos común: "etaoinshrdlcumwfgypbvkjxqz"

Estamos casi seguros que, el carácter que corresponde al carácter "D" en el cifrado es "E", así que reemplazamos todas las "D" en el cifrado por una "E", y queda así:
ASI JL eUJZTEe SA J EJZe JVV NBTOeI, Vee FOe AHB VBFe: OFFT://YYY.AHB.MSK/TJMD2/CDN08/NSCD_122908.OFZE, PSQe GSW MWDVV? LS, JNFWJE AHB RWBX.

Ahora reemplazamos el siguiente carácter "J" por su respectiva frecuencia que es "T", pero al hacer esto observamos que no pueder ser la "T", ya que en el texto aparecería ésta en un lugar que no es común
ASI tL eUtZTEe SA t EtZe tVV NBTOeI, Vee FOe AHB VBFe: OFFT://YYY.AHB.MSK/TtMD2/CDN08/NSCD_122908.OFZE, PSQe GSW MWDVV? LS, tNFWtE AHB RWBX.

Así que escogemos el siguiente carácter el cual es "A", reemplazamos la "J" por la "A":
ASI aL eUaZTEe SA a EaZe aVV NBTOeI, Vee FOe AHB VBFe: OFFT://YYY.AHB.MSK/TaMD2/CDN08/NSCD_122908.OFZE, PSQe GSW MWDVV? LS, aNFWaE AHB RWBX.

Ahora que tiene sentido (es mejor una "a" que signifca "un" que una "t" que no significa nada), continuamos con el análisis de frecuencias, el turno es para el carácter "S" que tiene un porcentaje de aparición del 7.2917%, como ya usamos los carácteres "D" y "A", el turno es de la "T", reemplazando nos queda:
AtI aL eUaZTEe tA a EaZe aVV NBTOeI, Vee FOe AHB VBFe: OFFT://YYY.AHB.MtK/TaMD2/CDN08/NtCD_122908.OFZE, PtQe GtW MWDVV? Lt, aNFWaE AHB RWBX.
Ahora vemos que reemplazando la "S" por la "T", hay una inconsistencia en el texto,
especificamente en lo que suponemos es el nombre de un dominio "YYY.AHB.MtK", si buscamos en la lista de dominios de internet, encontramos que ni en el dominio de internet genérico (gLTD) ni en el dominio de nivel superior geográfico (ccTLD), aparece un ".XtX", así que descartamos la letra "T" como reemplazo a la "S", y escogemos la siguiente letra en la frecuencia, la cual es la "O", reemplazando nos queda:
AoI aL eUaZTEe oA a EaZe aVV NBTOeI, Vee FOe AHB VBFe: OFFT://YYY.AHB.MoK/TaMD2/CDN08/NoCD_122908.OFZE, PoQe GoW MWDVV? Lo, aNFWaE AHB RWBX.

Haciendo un resumen para no perdernos, llevamos esto:
AoI aL eUaZTEe oA a EaZe aVV NBTOeI, Vee FOe AHB VBFe: OFFT://YYY.AHB.MoK/TaMD2/CDN08/NoCD_122908.OFZE, PoQe GoW MWDVV? Lo, aNFWaE AHB RWBX.
Los carácteres que hemos usado han sido: "E", "A", "O"
Los que hemos reemplazado: "D", "J", "S"
etaoinshrdlcumwfgypbvkjxqz

Como hemos supuesto que la cadena "OFFT://YYY.AHB.MoK/TaMD2/CDN08/NoCD_122908.OFZE" corresponde a un HTTP URL, entonces nos concentramos en tal cadena para sacar la respuesta mas fácil, así que empezamos a decodificar de una vez.

Letra en el Cifrado    Reemplazo
O                          H
F                          T
T                          P
Y                          W

Y el texto nos va quedando así:
AoI aL eUaZpEe oA a EaZe aVV NBpheI, Vee the AHB VBte: http://www.AHB.MoK/paMD2/CDN08/NoCD_122908.htZE, PoQe GoW MWDVV? Lo, aNtWaE AHB RWBX.

Vamos avanzando, y vemos como lentamente el cifrado va llegando a su texto en plano
Ye hemos usado: "E", "A", "O", "H", "T", "P", "W"
etaoinshrdlcumwfgypbvkjxqz
Y hemos reemplazado en el cifrado: "D", "A", "S", "O", "F", "T", "Y"

La siguiente letra en la tabla, que no hemos reemplazado corresponde a la "B" con un porcentaje de frecuencia de 6.2500%, la reemplazamos por la siguiente letra mas frecuente en el inglés, y el turno es de la letra "I"
AoI aL eUaZpEe oA a EaZe aVV NipheI, Vee the AHi Vite: http://www.AHi.MoK/paMD2/CDN08/NoCD_122908.htZE, PoQe GoW MWDVV? Lo, aNtWaE AHi RWiX.

El siguiente carácter en la tabla es "F", pero ya lo hemos reemplazado, así que el siguiente es el carácter "V", el cuál reemplazamos por el siguiente carácter mas frecuente el cuál es "N"
AoI aL eUaZpEe oA a EaZe ann NipheI, nee the AHi nite: http://www.AHi.MoK/paMD2/CDN08/NoCD_122908.htZE, PoQe GoW MWDnn? Lo, aNtWaE AHi RWiX.

Con mi poco inglés, palabras como "ann", "nee", "nite" no son lógicas para un texto, así que pasamos a reemplazar por el siguiente carácter más frecuente el cual es el carácter "S", quedando el texto así:
AoI aL eUaZpEe oA a EaZe ass NipheI, see the AHi site: http://www.AHi.MoK/paMD2/CDN08/NoCD_122908.htZE, PoQe GoW MWDss? Lo, aNtWaE AHi RWiX.
Prefiero palabras como "ass", "see" y "site" que "ann", "nee" y "nite"

Antes de empezar con el buscador de coincidencias podemos hacer unos últimos reemplazos, si ven en esta cadena: "http://www.AHi.MoK/paMD2/CDN08/NoCD_122908.htZE", encontramos el recurso de la supuesta página el cual es "/NoCD_122908.htZE", así que vemos que la extensión termina en htXX, podemos suponer que la extensión es de un archivo "html", así que reemplazamos la "Z" por la "M" y la "E" por la "L", dando como resultado el siguiente texto:
AoI aL eUample oA a lame ass NipheI, see the AHi site: http://www.AHi.MoK/paMD2/CDN08/NoCD_122908.html, PoQe GoW MWDss? Lo, aNtWal AHi RWiX.

Como las frecuencias que siguen son muy similares, no podemos continuar con el análisis de frecuencias, así que lo que podemos hacer es un pequeño script en PHP que lea un diccionario de palabras comunes del inglés y según el patrón que le demos, nos muestre las posibles coincidencias.
El script es este, pueden ver el código online en: Code: wordmatcher.php

Las palabras que nos quedan por descubrir son: "AoI", "aI", "eUample", "oA", "NipheI", "AHi", "MoK", "paMD", "CDN", "NoCD", "PoQe", "GoW", "MWDss", "Lo", "aNtWal", "RWiX".
El uso del wordmatcher es el siguiente: tenemos una expresión en la que no conocemos alguno de sus carácteres, por ejemplo la palabra "h__se", ingresamos vía GET la variable "patron" con los carácteres desconocidos marcados por un interrogante, así la palabra "h__se" se llevaría a la forma "h??se", y esta la enviamos via GET:
http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=h??se
Resultado: hawse,hoise,horse,house

Así que empezamos con las palabras mas largas de nuestro cifrado
http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=?iphe?
Nos muestra una sola palabra la cual es "cipher", y como tiene que ver mucho con el reto entonces reemplazamos la "N" por la "C" y la "I" por la "R":
Aor aL eUample oA a lame ass cipher, see the AHi site: http://www.AHi.MoK/paMD2/CDc08/coCD_122908.html, PoQe GoW MWDss? Lo, actWal AHi RWiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=e?ample
Resultado: example
Reemplazamos la "U" por la "X"
Aor aL example oA a lame ass cipher, see the AHi site: http://www.AHi.MoK/paMD2/CDc08/coCD_122908.html, PoQe GoW MWDss? Lo, actWal AHi RWiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=?o?
Resultado: Larga lista
De la larga lista podemos decir que el dominio es ".gov", ya que ".com" usa la letra "C" y "M" que ya estan siendo usadas, reemplazamos la "M" por la "G" y la "K" por la "V"
Aor aL example oA a lame ass cipher, see the AHi site: http://www.AHi.gov/pagD2/CDc08/coCD_122908.html, PoQe GoW gWDss? Lo, actWal AHi RWiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=act?al
Resultado: actual
Reemplazamos la "W" por la "U"
Aor aL example oA a lame ass cipher, see the AHi site: http://www.AHi.gov/pagD2/CDc08/coCD_122908.html, PoQe Gou guDss? Lo, actual AHi RuiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=gu?ss
Resultado: guess
Reemplazamos la "D" por la "E"
Aor aL example oA a lame ass cipher, see the AHi site: http://www.AHi.gov/page2/Cec08/coCe_122908.html, PoQe Gou guess? Lo, actual AHi RuiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=co?e
Resultado:code,coke,cole,come,cone,cope,core,cote,cove
Usamos la mas obvia que es code, y reemplazamos la "C" por la "D"
Aor aL example oA a lame ass cipher, see the AHi site: http://www.AHi.gov/page2/dec08/code_122908.html, PoQe Gou guess? Lo, actual AHi RuiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=?or
Resultado: for, hor, nor, tor
Al igual que la anterior sustitución, nos vamos por la más común, en este caso "for" es la mas apropiada, así que reemplazamos la "A" por la "F"
for aL example of a lame ass cipher, see the fHi site: http://www.fHi.gov/page2/dec08/code_122908.html, PoQe Gou guess? Lo, actual fHi RuiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=a?
Resultado: ab,ac,ad,ah,ai,al,am,an,as,at,aw,ax,ay
Podemos usar "ab", "an", "ay", pero en la expresión "for ax example", es ilógico usar las frases "for ab example" o "for ay example", al contrario de "for an example" que es la frase correcta, procedemos a reemplazar:
for an example of a lame ass cipher, see the fHi site: http://www.fHi.gov/page2/dec08/code_122908.html, PoQe Gou guess? no, actual fHi RuiX.

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=f?i
Resultado: fbi
Reemplazamos de nuevo, la "H" por la "B"
for an example of a lame ass cipher, see the fbi site: http://www.fbi.gov/page2/dec08/code_122908.html, PoQe Gou guess? no, actual fbi RuiX.

Ya casi estamos por terminar, nos falta sólo seis letras por descubir, como podemos observar, la sustitución contiene todas las letras del abecedario (a-z), entonces podemos averiguar fácilmente cuales son las que faltan. Tenemos las letras "abcdefghilmnoprstuvwxy", entonces las que faltan son: "jkyqz"

http://www.sinfocol.org/archivos/scripts/wordmatcher.php?patron=?ui?
Resultado: quia,quid,quip,quit,quiz,ruin,suit
Descartamos las que no podemos usar (Descartamos las que usen letras que ya fueron usadas anteriormente para reemplazar), y nos queda la única palabra por usar "quiz", volvemos a reemplazar, la "R" por la "Q" y la "X por la "Z"
for an example of a lame ass cipher, see the fbi site: http://www.fbi.gov/page2/dec08/code_122908.html, PoQe Gou guess? no, actual fbi quiz.

Falta por usar únicamente las letras "jky", así que probemos nosotros mismos a armar palabras:
Para la palabra "Gou", las posible combinaciones son "you", "kou", "jou", acá no se discute nada, así que usamos "you"
for an example of a lame ass cipher, see the fbi site: http://www.fbi.gov/page2/dec08/code_122908.html, PoQe you guess? no, actual fbi quiz.

Y para la última palabra "PoQe", las dos posibles combinaciones son "joke" y "koje", así que por ahora nos olvidamos de kojer porque la palabra correcta es "joke", decodificando los dos últimos carácteres que quedaban en el mensaje:
for an example of a lame ass cipher, see the fbi site: http://www.fbi.gov/page2/dec08/code_122908.html, joke you guess? no, actual fbi quiz.

El mapa de sustitución de carácteres es el siguiente:

FIDELTYBRAVNGCHJKQOPXSUZWM
ABCDEFGHIJKLMNOPQRSTUVWXYZ

El anterior mapa nos dice que: El carácter F se reemplaza por el carácter A, la I por la B, la D por la C, sucesivamente hasta cubrir todos los carácteres.
Si ciframos el texto plano que obtuvimos con el anterior mapa, llegamos al texto cifrado que nos dieron:

for an example of a lame ass cipher, see the fbi site: http://www.fbi.gov/page2/dec08/code_122908.html, joke you guess? no, actual fbi quiz
ASI JL DUJZTED SA J EJZD JVV NBTODI, VDD FOD AHB VBFD: OFFT://YYY.AHB.MSK/TJMD2/CDN08/NSCD_122908.OFZE, PSQD GSW MWDVV? LS, JNFWJE AHB RWBX.

La respuesta al reto era entonces "FIDELTYBRAVNGCHJKQOPXSUZWM".

Una curiosidad que encontramos en este reto, es que nos dan una página del FBI donde nos proponen un reto de criptoanálisis: http://www.fbi.gov/page2/dec08/code_122908.html, nos saludan diciendo si estamos preparados porque el código es ligeramente difícil, y que si somos jóvenes, nos recomiendan empezar con los códigos en la página de niños, luego de la breve introducción nos dan lo que parece ser otro de estos cifrados por sustitución simple:
VFWTDLCSWV. YD NSLMIJFWEJFD GSW SL NIJNQBLM FOBV EJFDVF DLNIGTFBSL. KBVBF YYY.AHB.MSK/NSCDC.OFZ FS EDF WV QLSY SA GSWI VWNNDVV
Si vemos bien, hay unas partes que parecen muy similares en el anterior texto cifrado, y es porque usaron la misma clave para cifrar el texto, así que manos a la obra, desciframos el mensaje del FBI con la clave obtenida anteriormente, y ganamos el premio al mejor estudiante de criptografía:
STUPENDOUS. WE CONGRATULATE YOU ON CRACKING THIS LATEST ENCRYPTION. VISIT WWW.FBI.GOV/CODED.HTM TO LET US KNOW OF YOUR SUCCESS

En resumen
Para realizar un análisis de frecuencias debemos tener:
1. Un texto cifrado por sustitución simple, y que tenga una buena cantidad de carácteres (Entre más carácteres se tenga, es mayor la posibilidad de encontrar el texto plano).
2. Conocer el idioma del texto plano.

Cómo se hace?
1. Del texto cifrado extraemos el porcentaje de frecuencia de cada carácter (Frecuencia de repetición del carácter a lo largo del texto).
Un ejemplo sencillo: "aaaabbbccd", en el anterior texto la "a" tiene una frecuencia de aparición del 40%, la "b" del 30%, la "c" del 20% y la "d" del 10%, para un total de 100%.
2. Buscamos la frecuencia común en que aparecen los carácteres en el idioma escogido. Las podemos encontrar acá: http://es.wikipedia.org/wiki/Frecuencia_de_aparición_de_letras, y acá: http://www.cryptogram.org/cdb/words/frequency.html
3. Reemplazamos en el texto cifrado, el carácter de mayor frecuencia de aparición con el carácter de mayor frecuencia del punto 2.
4. Opcional: Si no se conocen algunas palabras, o las frecuencias son muy similares se puede acudir a un buscador de coincidencias, se pueden usar las siguientes páginas:
http://www.puzzledepot.com/wordfinder2/
http://www.design215.com/toolbox/wordpattern.php
http://www.quinapalus.com/matcher.html

Y para el lector, una pequeña prueba de lo aprendido, el siguiente texto está cifrado con una sustitución simple:
RT JRQDH, TSJ WPTPNPSJ NRTRJKRJ x tmrad WRIPJKÓIRTRJ
TDJ KHRJ SHNÁQARTRJ jr sortsqksq
HSISRT
Rt Jdt, jraúq sqkpams mjsqzs, orus díh jm nsqkd rq ndwfrkrqnps ndq jmj lrhwsqsj tsj rjirhsj , x ndq ts hsfporz ort hsxd jpamr jm fhrjnhpkd nmhjd lsjks rt ipq. Jm bpjks pqimqor idhkstrzs s tdj áqartrj, smqgmr qpqamqd fmros fhdimqopzshtd. Tsj dehsj jmetpwrj lsjks td pqndqnrepetr jdq rjftéqoposj ndwd rq rt fhpwrh oís.
ASEHPRT
X háfpos, ndq pqndqnrepetr hsfporz, aphs rq orhhrodh ts wsaqpip-nrqnps or ts Kprhhs, stkrhqsqod tdj rjftrqodhrj fshsopjísndj ndq ts qdnlr fhdimqos ttrqs or rjfsqkdj. Jstks rjfmwsqkr rt wsh rq sqnlsj dtrsosj st eskph tdj fhdimqodj npwprqkdj or tsj hdnsj; x hdnsj x wsh jdq shhsjkhsodj rq rt hsmod nmhjd rkrhqd or tsj rjirhsj.
WPAMRT
X hmarq s fdhiís tsj kdhwrqksj orjor rt wsh s ts kprhhs x orjor ts kprhhs st wsh, idhwsqod imhpdjsj rq kdhqd mqs nsorqs or ts wáj fhdimqos snnpóq. Hrtmwehs rt hsxd orbsjksodh fhrnroprqod rq jm bís st rjkswfpod ort khmrqd. Wsj kmj wrqjsurhdj, Jrqdh, brqrhsq rt sfsnpetr nmhjd or km oís.
TDJ KHRJ
Kst rjfrnkánmtd pqimqor idhkstrzs s tdj áqartrj, smqgmr qpqamqd fmros fhdimqopzshkr; x kdosj tsj jmetpwrj dehsj kmxsj jdq rjftéqoposj ndwd rq rt fhpwrh oís.
WRIPJKÓIRTRJ
Xs gmr or qmrbd kr ttrasj sná, Jrqdh, x fhramqksj nówd sqosq tsj ndjsj rqkhr qdjdkhdj, x xs gmr rq dkhd kprwfd jdtísj brhwr ndq sahsod, sgmí wr brj kswepéq rqkhr ts jrhbpomwehr. Frhodqs, xd qd jé rcfhrjshwr ndq fstsehsj stkpjdqsqkrj, smqgmr wr rjnshqrzns rt ndhhd rqkrhd. Wp urhpadqzs kr wdbrhís nprhkswrqkr s hpjs jp qd lmeprhsj frhopod ts ndjkmwehr or hríhkr. Ort jdt x or tdj wmqodj, qsos jé xd gmr ornph, x, jótd brd ndwd jr iskpasq tdj wdhkstrj. Rt hsgmíkpnd opdj or ts kprhhs jpamr jprqod or pamst nstsqs x ksq rckhsbsasqkr ndwd rq rt fhpwrh oís. Mq fdnd wrudh bpbprhs jp qd tr lmeprjrj osod rjs bpjtmwehr or ts tmz nrtrjkr, s ts gmr os rt qdwehr or Hszóq x gmr qd mkptpzs jpqd fshs jrh wáj erjkpst gmr kdos erjkps. Jr wr ipamhs, opnld jrs ndq frhoóq or bmrjkhs Jrqdhís, mqd or rjdj npashhdqrj or tshasj fsksj, gmr jpq nrjsh bmrtsq x jstksq bdtsqod x nsqksq pqbshpsetrwrqkr rq ts lprhes jm bprus nsqkpqrts. ¡Wrqdj wst jp fmoprhs jprwfhr rjkshjr gmprkd rq ts lprhes! Qd lsx pqwmqopnps odqor qdwrks ts qshpz.
RT JRQDH
¿Qsos wáj kprqrj gmr ornphwr? ¿Lsj or brqph jprwfhr s pqnmtfsh? ¿Qmqns lsx fshs kp stad emrqd rq ts kprhhs?
WRIPJKÓIRTRJ
Qd, Jrqdh; rqnmrqkhd td or sttá orftdhsetr ndwd jprwfhr. Tájkpws wr osq tdj ldwehrj rq jmj oísj or wpjrhps, x lsjks jr wr gmpksq tsj asqsj or skdhwrqksh s rjs fdehr arqkr.
RT JRQDH
¿Ndqdnrj s Ismjkd?
WRIPJKÓIRTRJ
¿Rt odnkdh?

Archivado en: Criptografía |