sábado, 3 de febrero de 2007

el código indescifrable

Encriptar y codificar es esconder y ¿cuál es la mejor forma de esconder algo?: mostrarlo sin señalarlo ni acotarlo.

Se ha cometido un asesinato, varios testigos vieron a una única persona cometer el crimen.
La persona que lo cometió se confiesa como autora... pero no puede ser condenada... porque además, otras 20 personas más se han autoidentificado como autoras materiales. Me suena que hubo un caso verídico con unos gemelos, ante la imposibilidad de determinar cuál de ellos fue el autor, ante la posibilidad de condenar a un inocente, no se condenó a ninguno.

La mejor forma de esconder una palabra es esconderla en medio de más palabras, así nadie puede determinar cuál de las palabras es la palabra. Y ni si quiera que ese conjunto de palabras esconde algo que es importante para algo.
Aplicado a encriptación, supongamos que queremos codificar una letra, una letra secreta. Y tenemos una clave de desencriptación que mismamente es otra letra.

Para este ejemplo será un algoritmo de encriptación muy básico: una transposición. Cada letra tiene un valor numérico basado en su orden alfabético (a=1, b=2, c=3,...).
La letra secreta es la "E". La clave de desencriptación es "B" y la letra encriptada aplicando la clave sería:
E+B... (E+2) >>> G

Para desenciptar bastaría con hacer la operación inversa:
G-B... (G-2) <<<>

Bien, el espía se encuentra con el código: "G", y empieza a probar claves, y se da cuenta de que aun conociendo el algoritmo, cualquier clave que introduzca ofrece una desencriptación válida: una letra del alfabeto. Por tanto le es imposible saber cual es la letra secreta.

Vamos a ampliar ahora a dos letras. Aquí la cosa se complica un poco. Se supone que encriptamos un par de letras, pero ese par de letras debe de tener sentido en algún lenguaje, humano o cibernético (pueden ser datos de un programa o de un fichero interpretable por un programa).
Pongamos que es una palabra en castellano; algunos resultados válidos serían: es, el, lo, un, as, yo, tu, su, do, re, mi, fa, la, si, no... etc y resultados no válidos serían: ww, gh, ia, rr, vz... etc.
Por tanto, aquí el espía podría acotar un poco más, separando entre claves que devuelven resultados lógicos, y claves que devuelven basura desechable. Pero tampoco resolvería nada, si el conjunto de claves válidas le devolviera múltiples resultados válidos, infinitos resultados válidos, palabras con sentido. Nuevamente... ¿cuál de ellas es la palabra de dos letras secreta?

A medida que crece la cadena, la combinatoria válida se reduce y es más fácil acotar, a menos que la clave crezca con la cadena.
Para una palabra secreta de dos caracteres bastaría una clave de mismamente dos caracteres para obtener resultados válidos infinitos, y por tanto inútiles. Para 3 letras, clave de 3 caracteres; para 4 letras, clave de 4 caracteres... para 5678 letras, clave de 5678 caracteres... por muy simple que sea el algoritmo de cifrado.
Como nuestra memoria no es infinita, pero la de los ordenadores sí, mejor idear un sistema que mantenga la clave de descifrado pequeñita, aun a costa de aumentar la longitud del archivo encriptado... pero no de cualquier forma, los caracteres de relleno deberían de generarse bajo algún criterio que no delatase lo que es relleno y lo que es fundamental.

¿Y si es archivo encriptado estuviera preparado para obtener infinitos resultados válidos con las infinitas posibles claves independientemente de la longitud de la cadena secreta?

Para empezar vamos a esconder la longitud verdadera de la cadena, vamos a introducir código basura: falsos culpables.
La palabra secreta de 2 caracteres de longitud sería encriptada, por ejemplo, en un fichero de 8 caracteres de longitud, de los cuales 6 serían inservibles para obtener la palabra secreta correcta, pero útiles para obtener multitud de palabras "secretas" incorrectas. Hemos aumentado el caos, hemos escondido un grano de arena en una playa. Nadie puede diferenciar nuestro grano del resto de los granos.

Como gracias a la tecnología, cada vez los problemas de espacio son menores, y la seguridad de los datos bien merece espacio extra, este sistema de esconder lo válido dentro de un caos capaz de aumentar la probabilidad de resultados legibles falsos y disminuir la posibilidad de concretizar entre ellos, es bastante interesante. Estenografía + criptografía.

La tecnología avanza, y algoritmos que al día de hoy pudieran parecer inquebrantables, podrían descifrarse con los ordenadores y nuevas técnicas del futuro. La idea sería: muy bien, que los ordenadores del futuro resuelvan y desencripten lo que quieran... pero que cuando resuelvan, obtengan infinitos resultados válidos. Tenerlo todo es como no tener nada, podría el ordenador disponer de todos los textos posibles en todos los idiomas posibles, como en la Biblioteca de Babel de Borges, pero a ver qué criterio sigue para saber cual de esos textos es el que estaba oculto.

Además, que lo que he dicho un poco más arriba sobre que para una palabra secreta de 3 caracteres basta una clave de 3 caracteres para hacerla indescifrable es falso. Cuando se disponen de varios archivos codificados con el mismo algoritmo y la misma clave, se puede acotar más el conjunto de claves válidas, descartando aquellas que ofrezcan resultados no legibles en cualquiera de los ficheros codificados del repertorio, y en función del número de "muestras" para comparar, se podría llegar a hacer peligrar la inquebrantabilidad de la encriptación.
Claro que, esto también se puede neutralizar mediante juego sucio, nuevamente usando la información basura: si tenemos un directorio con todos nuestros ficheros de información codificada, bastaría introducir alevosamente entre ellos una proporción de ficheros con contenido ilegible codificado, ficheros basura que llevarían al espía a descartar -sin saberlo- claves válidas.

No, acceder a la información secreta no puede ser tan simple como en las películas: entrar en el ordenador del enemigo usando como clave el nombre de su mascota, para que a continuación aparezcan todos los ficheros secretos abiertos en el escritorio.
La información bien escondida puede estar a la vista, pero nunca acotada ni recuadrada con un marco que diga "TOP SECRET". Estará en cambio rodeada de datos falsos y posibilidades infinitas. Y la mayor falla de cara a la seguridad es el propio sistema operativo: la posibilidad de recuperar datos borrados del disco duro (los ficheros originales antes de la encriptación), datos temporales desencriptados que fueron almacenados mismamente como temporales en el disco duro, la posibilidad de consultar la fecha de acceso a archivos para saber cuales son los importantes...

NOTA: Cuando hablo de infinito, se entienda en sentido práctico, no real ni absoluto. Los resultados posibles de descifrado son siempre finitos, pero en la medida en la que abarquen todas las posibilidades y por tanto no concreticen en una única, dentro de su micromundo de posibilidades significan el todo, el infinito relativo.

[ampliación Martes 6 de Febrero]
La utopía de una clave corta que genere infinitas soluciones válidas aun a costa de aumentar el tamaño del código cifrado es inviable, a priori.
Las combinaciones están limitadas por la interacción con los elementos de la clave, por combinatoria.
Si tenemos una clave basada en 25 posibles letras, para generar infinitas soluciones de encriptación-desencriptación sobre un archivo que también contiene exclusivamente 25 caracteres, necesitaríamos una clave tan larga como el propio texto a encriptar.

Por ejemplo, un texto de 10 caracteres, escrito con 25 posibles valores.
Los posibles textos que se pueden generar con estas bases son 25^10 es decir... 9,5367E13
Para interaccionar con cada uno de esos caracteres y producir un nuevo caracter independiente de los demás, y por tanto obtener los infinitos resultados posibles (todos los resultados posibles por combinación), harían falta otros 10 caracteres con 25 posibles valores.
De otro modo no se podría generar la totalidad de posibilidades, y por tanto cabría el riesgo de que el cifrado fuera frágil.

12 comentarios:

javier dijo...

Veo que te mola bastante el tema de la criptografía... eres informático o matemático?

César dijo...

No lo puedo creer. Desde diciembre he estado preparando un artículo sobre criptografía (el software, realmente), y pienso publicarlo el lunes... juro por los dedos de Linus que es coincidencia :)

El concepto que mencionas tiene nombre... y a lo mejor lo conoces, en cuyo caso disculpa que me ponga todo pedagógico aquí :) ... "Cifrado negable" o refutable (deniable encryption), una forma de "esteganografía". En la vida real es un tanto impráctico, pues con los algoritmos comúnes hoy en día (AES, DES, esas cosas) no se conoce una forma trivial de producir un texto cifrado que pueda descifrarse de dos o más maneras plausibles. Pero con un "one-time pad", que es el procedimiento que describes (si lo entendí bien) es fácil de lograr; y es posible conseguir un efecto similar por otros medios.

Cifrar de esta manera es especialmente útil para hacer frente a lo que yo llamo "criptoanálisis de tehuacanazo". "Tehuacán" es una marca de agua mineral carbonatada, aquí en México. Y "tehuacanazo" es un término popular para referirse a la acción de sacudir una botella de tehuacán y luego dirigir el chorro de agua a presión dentro de las fosas nasales de un individuo inmovilizado. Una forma de tortura, pues.

El punto es que una forma de recuperar la información en un mensaje cifrado es capturar a alguien que conozca la llave, y torturarlo hasta que la divulgue. Si el mensaje fue cifrado de una manera negable, en esta situación se puede entregar la llave que descifra un mensaje plausible, lo cual puede satisfacer al inquisidor, mientras el mensaje real permanece oculto.

Personalmente, yo creo que la mejor manera práctica de conseguir este efecto es como sigue. Primero, escribes el mensaje secreto, y también uno o más mensajes "señuelo", que contengan información plausible pero incorrecta. Luego cifras cada mensaje con un algoritmo fuerte (AES o algo por el estilo), usando una llave distinta para cada uno. Y luego los incrustas todos en un video o una grabación o una colección de imágenes, usando cualquiera de los trucos habituales para conseguir esto. Hay un excelente artículo en bulma.net/beowulf/stego/ que describe esto en detalle. Y ¡en cristiano! :)

Herel dijo...

Javier, ni lo uno ni lo otro, pero me gustan ambos campos.

César, pues no conocía el nombre, gracias por la info. Cuando escribía esto me estaba preguntando si esto estaría estudiado, si existiría el algoritmo, y si estaría determinada la longitud de la "basura" que sería necesaria añadir a un fichero encriptado -en función de su tamaño- para que el algoritmo dispusiera de datos suficientes para generar los infinitos descifrados legibles.
Espero leer tu artículo, que sin duda estará más documentado... ¡desde Diciembre! :)

on dijo...

Pero hay una trampa... estamos presuponiendo que el receptor legítimo del mensaje tiene una información adicional, que no se halla en el mensaje, y que un receptor no válido tampoco tiene: que es la forma de discriminar los mensajes falsos del verdadero.

Eso supone añadir un contexto, y tiene dos peligros. O bien el contexto es ampliamente conocido, en cuyo caso un receptor ilegítimo también puede conocerlo; o bien no es conocido. En ese último caso, el receptor legítimo podría desconocer el contexto, que en la práctica supondría una extensión de la clave.


A pesar de todo, aumenta mucho las posibilidades de ocultar efectivamente un mensaje.

Herel dijo...

Con el algoritmo correcto, el factor contexto sería despreciable. Me explico: suponte que como espías sabemos que el mensaje trata de una cita secreta en Burdeos el Lunes, nos falta saber la hora.
Si el algoritmo mágico existiera, se podrían descifrar a partir del código infinitos mensajes que contengan las palabras clave que buscamos como referencia: "Burdeos", "cita" y "lunes".
Cita en Burdeos el lunes a las 8.
Cita en Burdeos el lunes a las 9.
Cita en Burdeos el lunes a las 10.
Cita en Burdeos el lunes a las 11.
El lunes cita en Burdeos a las 12.
El lunes no hay cita en Burdeos.
...etc

Claro que, para generar todas esas opciones sin dejarse una sola posibilidad, haría falta una clave tan larga como el texto. Cuanto más lo pienso menos viabilidad tiene esto.

César dijo...

Efectivamente, eso es lo que dice la gente que se dedica a esto, hasta donde sé (que yo tampoco me dedico a esto). La única manera práctica conocida de generar un texto descifrable de varias maneras arbitrarias es usando un "one-time pad". Esto es, lo que dices: una llave tan larga como el mensaje mismo.

Esto es altamente impráctico, claro. Pero se ha usado en la práctica. Tiene dos ventajas importantes:

1. Puedes generar llaves que produzcan exáctamente cualquier mensaje que se te dé la gana.

2. Es el único sistema imposible de romper, demostrable matemáticamente, sujeto a algunas restricciones: la llave debe ser generada estrictamente al azar (al menos la del mensaje real); y la llave puede usarse sólo una vez, para cifrar un solo mensaje, después de lo cual no debe volver a usarse nunca.

Este sistema se usa cuando es posible establecer un arreglo de llaves ("pads") previamente, y cuando es de vital importancia que los mensajes sean imposibles de descifrar hoy y en cualquier punto en el futuro, con la tecnología que sea. En la práctica, por ejemplo, se puede crear un libro de códigos en el que cada página es un "one-time pad" desechable. Le das una copia al almirante y otra al capitán del submarino. Y listo: cualquiera de ellos puede cifrar mensajes imposibles de descifrar usando cualquiera de las páginas del libro. Naturalmente, después de usarse, cada página debe ser cuidadosamente destruída.

Y por cierto, oye, no creas que he estado trabajando un mes en un artículo... la idea se me ocurrió en diciembre y desde entonces he escrito algo de software en los ratos libres, que no son muchos. Ya al rato lo publico :)

on dijo...

Herel: y para que como espías supiésemos que el mensaje habla de la cita de Burdeos, y no es un haiku sobre las flores de cerezo (por ejemplo), tendríamos que poseer información previa. ¿Esa información nos llegó encriptada? etc...

Y si no existe de información previa, el enemigo quizá no distinga un mensaje de otro, pero ¿y nosotros?

Quizá no es viable aplicarlo tal cual, como en la teoría, pero algunas técnicas de esteganografía se basan en eso (como encriptar un fichero en otro de distinta extensión usando un programa como Truecrypt).


César: si es un sistema, se puede romper. Otro tema es el tiempo...

Herel dijo...

A ver, On, estamos hablando de un algoritmo que para una clave dada, ofrece un único resultado. Se supone que el contacto sabe esa clave, si no, apaga y vámonos.
De lo que se trataba más bien es que usando un programa de "fuerza bruta", un programa que pruebe todas las claves posibles, no haya una única solución válida, sino infinitas.
Pero como refuerza César, esto sólo es posible con una clave tan larga como el mensaje a cifrar, simple combinatoria.

Y lo de cambiar la extensión es un truco muy viejo, me acuerdo cuando empecé a trastear para programar un juego en C. Como no tenía mucha idea, y para cosas como los gráficos tenía que copiar códigos ya hechos. Pues nada, usaba gráficos PCX, pero para que nadie pudiera cargarlos y verlos directamente desde el disco duro, creo recordar que les cambiaba los 4 primeros caracteres de la cabecera o algo así y además les modificaba la extensión (esto último para despistar, pues es una medida muy fácil de deshacer). Con eso bastaba para se cargaran corruptos en un programa de dibujo estandar, pero no con mi código preparado para saltarse esos caracteres.

César, lo publicas, el Lunes... ¿según el calendario Maya?
Y cuando dices "al rato", supongo que no es lo mismo que "al ratito", como me dijeron que allí "ahora" no es lo mismo que "ahorita". :D

César dijo...

Ja-ja Herel :P

Prueba incrustar javascript en un post, y veremos si te sigues ríendo... y como sea, hoy aún es mi lunes personal, de acuerdo al calendario oficial mexicano :)

Pero ya está una parte. A ver si funciona para ti.

Y On, el "one-time pad" es imposible de descifrar. No importa si tienes el poder de cómputo de Google, o un ordenador cuántico, o lo que sea.

Claro, podría argumentarse si es realmente un "sistema"...

Zereth dijo...

Ohhhhhhhhh, creo que me he venido a enterar de más cosas que ignoraba.
Ok, la sugerencia de César del uso de LSD para entender su post creo que la descartaré, siempre si me conviene ser metiche-blog.


Saludos de nuevo

Anonymous dijo...

me llamo david y me mola ese codigo yo tengo algunos mensajes que yo he cifrado a ver si lo puedes desencrictar

si tuens mesenger te lo mando sino escribeme a esta direcion xatu-21-22@hotmail.com

codigo dijo...

hola solo vengo a difundir un texto codificado que hasta este momento el dicho dodigo es indesifrable:
20 2 23 15 14 19 9 5 7 26 1 10 5 12 18 3 15 22 12 24
11 17 21 20 12 5 3 20 27 13 14 20 11 26 9 19 11 26 13 19
4 25 12 4 22 4 10 11 8 2 22 23 23 2 24 10 1 13 7 15
23 16 26 1 26 21 5 4 6 7 13 14 21 17 3 15 12 2 27 20
1 18 2 14 13 22 11 23 8 17 7 26 12 25 19 5 13 7 8 4
21 24 17 22 2 2 23 1 3 27 27 7 26 16 10 20 17 17 6 1
14 19 25 13 7 27 21 21 10 25 8 25 2 18 15 11 8 27 9 14
12 15 16 7 17 16 12 14 5 8 6 6 17 24 5 4 18 25 3 22
22 20 18 27 27 9 26 12 11 16 9 24 25 19 20 23 3 8 10 13

talvez sean demaciados numeros pero espero que trabajen en el

cualquier comentario en :
http://elcodigoindesifrable.hi5.com

muchas gracias y hasta luego.