Seguridad - ENCRYPT 1.5

Este es el inicio de una discusión sobre un programa freeware de encriptación, el Encrypt 1.5.
En la discusión hay hasta ahora dos partes:

1) El autor del programa (Kepa): Afirma (con razón) que su algoritmo es bueno hasta que no se pruebe lo contrario. Está bastante satisfecho de su programa.

2) Daryl Reebok (yo): Afirma que ha roto varios ficheros encriptados con Encrypt 1.5, incluyendo uno mandado por el autor. Está dispuesto a romper los que hagan falta (dentro de lo razonable) para probar sus afirmaciones. Lamentablemente Daryl tiene problemas de socialización así que aveces se muestra muy irritante.

Vean las notas siguientes para seguir la discusión.

NOTA: Por favor, colaboren en la discusión SOLO si tienen algo importante que decir.

Kepa me desafió a desencriptar el siguiente texto (una vez eliminada la cabecera). Naturalmente yo ignoro la clave:

Mc#vdpcie"fs!srm!gqer"rf!eqao"b{uwginqh(eg#l`"ji ugqi`8'Mojlr``rmoc/ lcil`of tl'e `ko `"l}skbrugGm tqhamlb|/lft

Bueno, está en ASCII pero luego incluyo un volcado hexadecimal. Las notas que siguen detallan el crackeo de este fichero.

Lo primero que hice fue obtener un volcado hexadecimal del fichero. Lo que se obtiene es toda una sorpresa:

4D63237664706369652266732173726D Mc#vdpcie"fs!srm
2167716572227266216571616F22627B !gqer"rf!eqao"b{
757767696E7168286567236C60226A69 uwginqh(eg#l`"ji
756771696038274D6F6A6C726060726D ugqi`8'Mojlr``rm
6F632F206C63696C606F6620746C2765 oc/ lcil`of tl'e
606B6F2060226C7D736B62727567476D `ko `"l}skbrugGm
747168616D6C627C2F6C tqhamlb|/lft

En este fichero hay algo que no funciona: es enormemente parecido a un fichero de texto, salvo por una pequeña confusión. Esto es algoque he observado en todas las encriptaciones usando este algoritmo: El cifrado resulta poco confuso, es decir, recuerda mucho a la versión inicial. De aquí se deduce que la cadena que se XOR-fusiona al texto inicial es muy parecida a la cadena de todo ceros. Esta será nuestra hipótesis de partida.

Bien, un símbolo muy común en ASCII es el espaciador (hex. 20). Además, el espaciador es muy diferente de las minúsculas (hex. 61-7A), y de las mayúsculas (hex. 41-5A). Como el texto cifrado es una pequeña modificación del texto inicial, el espaciador destacará como valores próximos a 20h rodeados de valores muy diferentes. Además, las mayúsculas seguirán siendo mayúsculas, y las minúsculas minúsculas. De aquí deduje que el texto tenía una forma parecida a (esto está sacado de mis notas):

Xx xxxxxx xx xxx xxxx xx xxxx xxxxxxxxx xx
xxxxxx. Xxxxxxxxxxx, xxxxxxx xx xxxx x
xxxxxxxxxxxxxxxxxxxxxxx <---- !!!!

[este texto continua a Rompiendo...(1)]

Las admiraciones las puse porque la última palabra me parecía muy larga. Supuse que sería un e-mail (y acerté).

Ahora podemos sacar partido de lo que hemos obtenido: en cada lugar donde tiene que haber un espaciador, podemos deducir la cantidad que hace XOR (basta hacer XOR con 20h). Esto nos da:

POSICIÓN EN EL FICHERO: MÁSCARA:
. 3 3
. 10 2
. 13 1
. 17 1
. 22 2
. 25 1
. 30 2
. 40 8 (hmm...)
. 43 3
. 46 2
. 54 (38h = .?) (dudosa)
. 55 7
. 67 (,?) (dudosa)
. 68 0
. 76 0
. 79 7 (hmm...)
. 84 0
. 86 2
-----------------------------------------

De nuevo esto es un estracto de mis notas. Las máscaras de las que no estaba seguro las comenté como (dudosa) o (hmm...) De las demás estaba razonablemente seguro.

Si te fijas todas las máscaras (salvo unas pocas, dudosas) no sólo tienen pocos bits, si no que estos bits son además poco significativos. Esto reduce _enormemente_ la confusión del cifrado. Como puedes ver, a estas alturas había deducido casi todo lo relativo a la forma del mensaje. Si la clave no era demasiado larga, podría desencriptarse todo con lo que ya tenemos.

Así que hice un programa en C que agrupaba las máscaras de la tabla de arriba en grupos de longitud determinada (usando restos) y entonces los aplicaba (XOR) a todo el fichero. A este programa lo llamé fred.c y lo adjunto en otra nota, colgando de esta.

Tras probar con varios valores para la longitud de la clave (empecé con los más altos) acabé por ejecutar (al fichero encriptado lo había renombrado cifrado.enc):

$ ./fred cifrado.enc salida 4
Mascara: 01 02 03 00

y obtuve en el fichero salida:

La ver`id es qqm eres qf gran a{tudiosk(de la iiteria:$Mnhorabqmna, majlame un$eail a o}riarteDmuskalna|.netþ

Bien, a partir de aquí pude deducir ya la forma del mensaje, sin tener que inferir el resto de las máscaras XOR que me faltaban, ni tener que atender a casos particulares:

"La verdad es que eres un gran estudioso de la materia: Enhorabuena, mandame un mail a [email protected]"

El último caracter del mensaje era un EOF.

Este es el mensaje que me envió Kepa, una vez desencriptado. Como pueden ver, es realmente fácil romper textos cifrados con este programa, incluso sin necesidad de adivinar la clave. Basta con predecir las máscaras que se tienen que aplicar.

#include <stdio.h>
#include <stdlib.h>
static char mask[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
static int longitud; /* Longitud del password. */
static char umask[] = {3, 2, 1, 1, 2, 1, 2, 3, 2, 0, 0, 0, 2};
static unsigned int offset[] = {3,10,13,17,22,25,30,43,46,68,76,84,86};
#define TOT 13 // Total de indicios.
int main(int argc, char **argv)
{
register int n,m;
register char c;
FILE *entrada, *salida;

if (argc <= 3) {
puts("\nUso: fred entrada salida longitud 1-20 \n");
exit(0);
}
entrada = fopen(*++argv,"r");
salida = fopen(*++argv,"w");
longitud = atoi(*++argv); /* Longitud del password */
for (n=0; n < TOT; n++) mask[((offset[n] - 1) % longitud)] = umask[n];
printf("Mascara:");
for (n=0; n< longitud; n++) printf(" %2.2x ",mask[n]);
putchar('\n');
fseek(entrada, 47, 0); /* Ignora la cabecera. */
n = 0;
while (!feof(entrada)) {
c = getc(entrada);
putc(c ^ mask[n % longitud], salida);
n++;
}
fclose(entrada); /* Cerramos ficheros. */
fclose(salida);
}

Bien, espero que más o menos se haya entendido, pese al horrible formato que se da aquí a las notas. La idea básica es: el cifrado de Kepa -salvo algunas perturbaciones pequeñas - hace el xor de una cadena predecible con todo el fichero. Además esa cadena es muy parecida a la cadena cero (en todos los casos que he crackeado) así que basta encontrar un símbolo aislado (el espaciador 20h) y predecir las máscaras que se le han aplicado. Luego se agrupan para formar la cadena a testear. Se hace el testeo y se observa si es correcto (casi seguro que sí). Entonces se obtiene información en masa del fichero, de tal manera que podemos darle el toque de gracia.

NOTA: he tenido que eliminar de fred.c un monton de comprobaciones (ficheros mal abiertos, etc). Ojo. El formato es: fred <cifrado> <salida> <longitud de la clave>. La longitud debe estar entre 1 y 20 para evitar core dumps.

Por favor, mandadme comentarios y notas.

¿Son más seguras las claves largas que las cortas en Encrypt 1.5? Bien, cuanto más larga sea la clave mejor, pero a menos que la clave sea tan larga como el mensaje (literalmente), siempre existe una poderosa posibilidad de desencriptarlo por ataques como el de arriba, o por ataques estadísticos. Por eso le dije a Kepa que una clave tiene que ser muuuuy larga para dar seguridad total: Si me mandas un fichero de 20 bytes con una clave de 20 bytes me estás mandando una especie de "one-time-pad", que me costará muuuucho descifrar. Pese a todo recordemos que las máscaras son predecibles, al ser casi todas cero. Esto posibilita ataques de diccionario, aunque sólo recurriría a eso como último recurso. Hay realmente modos más fáciles, como el de arriba.
En fin, que si quieres mandar un mensaje de 1k sin que te lo descifren, usa una clave de 1k. ¡¡Y no la olvides !! ;-)

Daryl tu labor ha sido poco menos que perfecta, felicitaciones!... lo primero que me vino a la mente ni bien inferiste que la encriptacion se basaba en XOR es "no uso este programa de encriptacion nunca!" pues son las mas sencillas de romper, a proposito, no conozco ese programa y el autor deberia ponerle mas ganas a la hora de buscarse un algoritmo de encriptacion medianamente decente, digamos alguna variante de DES. Felicitaciones de nuevo.

Bien, bien, un trabajo estupendo Daryl, conseguiste extraer la info de un fichero ASCII. Pero SABIAS que era un fichero ASCII que solo contiene Caracteres y/o Numeros.

Te atreves a intentar desencriptar cualquier otro tipo de fichero ¿?¿?

Como bien he dicho en los comentarios, esto no es PGP, ni nada por el estilo, es un programa hecho por 1 sola persona y para uso personal ( por si no has leido la introduccion de mi pagina ).

1) Estoy dispuesto a desencriptar lo que sea, pero ten en cuenta que tendría que estudiar el tipo de fichero al que quiero atacar. Esto se debe a algo muy sencillo:
Si ignoro absolutamente todo sobre el fichero que me mandas, tengo que diseñar un ataque a medida: por ejemplo, si es un fichero .arj atacría al CRC y las tablas de Huffman.

2) Supongo que me diras ... bien, entonces mi algoritmo es seguro en tanto que el atacante se adapte al formato del fichero que ataque.
Te respondo: bien, pero es que una vez que tenga el formato los archivos cifrados caen como fichas de dominó. La seguridad entendida de esta manera no está en tu algorirmo, si no en la ignorancia del atacante acerca del fichero encriptado!!!
Por otro lado, las agencias de seguridad nacional ( y otras) tienen mecanismos de análisis adaptados a los tipos de ficheros mas comunes. Esa gente, una vez que analicen tu algoritmo, se pueden cargar casi cualquier cosa que se encuentren.

3) Muchos programadores individuales hacen paquetes criptológicos a prueba de bomba: basta que usen un algoritmo potente de dominio público. Conozco muchos buenos ejemplos de estos paquetes. El problema aparece cuando el que escribe el programa se inventa el algoritmo ... ¡Hay que saber muchas matemáticas para hacer eso! La criptología es una disciplina matemática, no lo olvidemos.

4) Equivocarse es humano. No querer reconocerlo también, Las versiones 1.5 exiten para hacer la 2.0.

El uso de XOR no es malo en los algoritmos criptológicos, Diego. Existen familias enteras de algoritmos (stream ciphers) basados en hacer XOR al mensaje. El problema de Encrypt 1.5 es que la máscara XOR es _tremendamente_ predecible. Puede considerarse el algoritmo de Encrypt 1.5 (¿REA?) como un stream cipher muy defectuoso.
Algunos buenos ejemplos de stream ciphers (que tan solo hacen XOR) son SEAL y RC4. Hasta donde yo puedo decirlo, son irrompibles.

Un saludo, y gracias, Diego.

Los algoritmos basados en XOR exclusivamente no son mas que variantes del metodo de sustitución, con solo probar todas las tablas ninguno se resiste, vos mismo lo dijiste, tablas de sustitucion mas grandes solo retrasan la rotura pero tarde o temprano llegan. Aun asi creo que los algoritmos basador en escalares MCM o por divisores de numeros primos son los mas eficientes pues no es posible hayar una correlación entre un lexema cifrado y el siguiente en el mismo mensaje..., claro que esto es una cuestion de opiniones (hasta de fé!), ciertamente, hace poco en una universidad de Israel lograron quebrar un mensaje cifrado con RSA de 512 bits... mal que me pese!!!!

Entiendo a lo que te refieres, pero si generas una cadena pseudoaleatoria tan larga como el mensaje a cifrar y luego la aplicas (XOR), el resultado es prácticamente indescifrable. Este es el funcionamiento de un stream cipher, y son fortísimos cuando están bien hechos. Si la cadena fuese aleatoria -no pseudo- el mensaje sería teóricamente irrompible. Lamentable generar aleatorios es difícil y las claves son molestas de transmitir.
En cuanto a RSA, tienes razón Diego, está más que roto (para claves cortas al menos). La primera clave que se rompió era de 429 bits (1994). En menos de 3 años le siguieron las de 435 y 512 bits (la última rota en 15 días con 300PCs y un mainframe). La cosa no deja de ser graciosa, porque el desafío que se lanzó era parecido al que me mandó Kepa: encriptaron un fichero de texto (sólo minúsculas) y desafiaron a todo el mundo a romperlo.
Y tienes razón, hoy hay mucha gente capaz de romper claves RSA. Tengo entendido que la NSA puede romper una clave de 512 bits en menos de 6 horas, claro que no es oficial.
Los métodos que usan teoría de números (como los que citas de divisores de números primos) son buenos para lograr una seguridad moderada, pero no te los sugeriría para aplicaciones ULTRAparanoides. Hoy existen algoritmos cuánticos [algoritmos de Shor] para factorizar números enteros en tiempo polinómico, lo que indica que tal vez puedan desarrollarse algoritmos para computadoras clásicas que hagan el trabajo en tiempo polinómico también (o al menos tan parecido al polinómico como se quiera). Yo en general confío en los cifrados de clave pública sólo para comunicaciones informales, o para intercambiar claves de cifrados de clave privada, pero para lo demá