Este paper se me ocurrio escribirlo cuando encontre por internet un reto que planteaba el FBI, el cual se cifraba un determinado mensaje, con un algoritmo clasico. Ademas de que tambien he visto un reto similar llamado Crypto Badness el cual fue usado para la clasificacion de CTF en la DefCon.
Antes de comenzar me gustaria introducir sobre el Criptoanalisis, algo muy breve, aunque ya he escrito una introduccion a lo que respecta la Criptografia y sus comienzos en [http://confused.vndv.com/?cat=15].
Introduccion a Criptoanalisis: El criptoanalisis es un poco de ingenio y metodos de estudio, que se puede emplear ante un ‘texto cifrado’ para intentar obtener dicha informacion sin acceso. Podemos decir que es la forma de romper un codigo o sortear la seguridad.
El criptoanalisis clasico, en el cual me voy a basar en este paper, surgio aproximadamente por el siglo IX, X, el cual tomo mayor valor cuando un arabe llamado Sabbah Al-kindi, expuso en un manuscrito varias formas de descifrar mensajes criptograficos. Una de esos metodos se lo conoce como el Análisis de Frecuencias.
El Análisis de Frecuencia: Es una de los metodos criptograficos mas clasicos. Hay algo que tienen en comun muchos idiomas, muchos lenguajes, y es que estadisticamente, dependiendo cual sea este, ciertas letras del abecedario se repiten o tienen una frecuencia mayor que otras.
Veamoslo con un grafico sacado de Wikipedia el cual plantea perfectamente lo que estoy diciendo, sobre el idioma español:
Como podemos ver, hay una frecuencia de letras que varian y sacan mucha ventaja entre unas y otras. Por ejemplo, vemos como la “E” es la letra que mas frecuencia se tiene en un texto y posibilidades de que se repita, le sigue la “A”, luego la “O”, la “S” y asi…
En un algoritmo como por ejemplo el de “sustitucion simple”, cada letra que conforme la palabra sera reemplazada por otra en todas sus veces que aparezca. Y esto supone que si en un texto tenemos una gran cantidad de frencuencia de letras “F” podemos deducir que representa a la letra E.
Si bien parece ‘facil’ no siempre lo es, con esto quiero decir que el analisis de frecuencia consiste en calcular la frecuencia de las letras que van aparenciendo en un texto, pero no quiere decir que si por ejemplo tenemos cinco letras “X” de forma frecuente sean realmente una letra “e”, tambien podria ser la “a” o la “o”, que tienen un porentaje alto de frecuencia en el idioma, pero lo que si sabriamos es que una ‘w’, o ‘z’, o ‘y’, no serian, debido a que la frecuencia es menor.. en estas letras. Por lo tanto con un poco de combinaciones podriamos revelar el mensaje mediante este metodo.
Mini Workshop de Análisis de Frecuencia.
Bueno veamos un ejemplo de cómo podemos ‘criptoanalizar’ un texto cifrado con un algoritmo clasico.
=================================================
[ Al pie de esta pagina, posteo un codigo .c que hice, para analizar y contar con que frecuencia se repiten las palabras. Compilenlo con DevC++ en Windows o GCC en Linux ]
=================================================
El texto cifrado es el siguiente:
“sghs sg ib awbw asbgoxs”
Si lo insertamos en el programa que hice, veremos que nos informa lo siguiente lo ordeno de mayor a menor para que se comprenda mejor:
s —-> 5
g —-> 3
b —-> 3
w —-> 2
a —-> 2
x —-> 1
o —-> 1
h —-> 1
i —-> 1
————
c —-> 0
d —-> 0
e —-> 0
f —-> 0
j —-> 0
k —-> 0
l —-> 0
m —-> 0
n —-> 0
p —-> 0
q —-> 0
r —-> 0
t —-> 0
u —-> 0
v —-> 0
y —-> 0
z —-> 0
Si intentamos deducir ”sghs sg ib awbw asbgoxs” podriamos decir que la letra “S” aparece varias veces, y si recordamos el grafico que puse mas arriba de frecuencia, podriamos decir que seria la letra “E” la mas frecuentada en el idioma español..
Por lo tanto suplantamos y quedaria asi..
EghE Eg ib awbw aEbgoxE
Si nos fijamos la que se repite es la G 3 veces, y si nos fijamos la tabla la segunda mas frecuente es la A..pero una palabra que empieze con EA.. no nos dice nada, si probamos otra combinacion con la tercer letra frecuente seria laO y tampoco nos diria nada logico una palabra que empiece con EO*E..si probamos con la cuarta mas frecuente en el grafico seria la S. Esta si nos dice algo…por lo tanto sustituimos todas las G por S y vemos como va quedando:
EShE ES ib awbw aEbSoxE
Bien por el momento esta quedando asi, ahora sigamos… la siguiente letra que se repite 3 veces es la “B”.. y si nos fijamos en el grafico de idioma español, veremos que la siguiente letra frecuente es la R y la N muy seguida.. si analizamos el texto, tenemos un monosilabo “ib” en el texto cosa que nos da la pauta de que si aplicamos la b por la R nos quedaria mal dicho ya que el mensaje diria ES iR y no nos diria nada “ES xR” queda mal hablado.. asique creo yo que es conveniente poner la letra N quedando asi al reemplazar las b: EShE ES iN awNw aENSoxE de a poco va tomando color la cosa y coherencia.. pero ahora como es un mensaje corto el mio, la frecuencia de letras es muy dificil de sacar..pero sigamos.
La siguiente es la “w” que aparece 2 veces… y en el grafico luego de la N la mas frecuentada es la “i”, asique si reemplazamos las w por las i quedaria:
EShE ES iN aINI aENSoxE, bien sigamos… ya falta menos… luego de la ‘w’ la que aparece 2 veces en nuestro texto cifrado es la ‘a’…y si miramos el grafico de frecuencia, vemos que le siguen a la I las letras: D y C, pero si nos fijamos en la palabra “aINI” del texto cifrado si reemplazamos por D o por C no nos quedaria nada logico,“DINI”, o “CINI”..asique seguimos con la que le sigue a D y C…y encontramos la letra L y la letra T.. pero vemos que tampoco queda nada logico… LINI o TINI…. Sigamos, no es tan malo fracasar con las combinaciones porque tambien permiten eliminar letras inservibles.
Luego de la L y la T podemos ver en el grafico de frecuencias que la que le sigue es la letra U..y tampoco daria nada logico UINI, seguimos y encontramos la letra M.. Cosa que si daria algo logico, ya que si reemplazamos las‘a’ por la ‘M’ el mensaje quedaria:
EShE ES iN MINI MENSoxE, uf ahora si va quedando… nadie dijo que seria facil esto eh, por eso aclare ‘ingenio y estudio’ al criptoanalisis.
Sigamos con nuestro mensaje casi descifrado.. aunque no hay mucho mas que hacer debido a que hay que usar la logica, esto se debe tambien a la poca frecuencia de las letras, pero aparecen las 4 letras faltantes 1 sola vez…
Podremos sacarlo por deduccion…. por ejemplo la EShE podriamos reemplazar la h por la T quedando ESTE ES iN MINI MENSoxE y luego podriamos reemplazar la ‘i’ de iN por ‘UN’ y quedaria ESTE ES UN MINI MENSoxE y por logica final…….a menos que muchos tengan dudas reemplazaria la ox por AJ quedando el texto descifrado ->
“ESTE ES UN MINI MENSAJE”.
Bueno, se que no fue LO MEJOR explicado, pero espero que la idea del Analisis de Frecuencia se haya entendido.. y con un poco de practica y de otras webs especializadas en criptografia y criptoanalisis comprenderan de una mejor manera.
Saludos.
ConfusedMind.
http://confused.vndv.com
#include <stdio.h>
/* Analizador de Frecuencia: Simple programa que al ingresar un determinado texto, lo recorre y analiza
la frecuencia en la que aparecen las letras.
By ConfusedMind
*/
int main(int argc, char *argv[])
{
char diccionario[26] = { ‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’};
char INPUT[1000];
int letra;
int i;
char *p;
printf (”Ingresa la cadena a analizar en MINUSCULA: “);
fgets (INPUT, 999, stdin);
printf (”nLetratFrecuencia de Repeticionn”);
for (i=0;i<26;i++) {
p = INPUT;
letra =0;
while (*p != ‘′) {
if (*p== diccionario[i]) letra++;
p++;
}
printf (”%c —-> %i n”, diccionario[i],letra);
}
system(”PAUSE”);
return 0;
}
Fuente: http://foro.portalhacker.net/index.php/topic,88597.0.html