magister

Funciones hash

In criptografía, matemáticas on junio 16, 2008 at 3:54 am

Corre

: Drini: Vamos a jugar un juego, mi estimado Luis. Yo pienso un color (como blanco, rojo, azul, etc. para simplificar, nada de “azul prusiano” o “rojo bermellón”). Tienes una oportunidad de adivinar. Si atinas, te doy 20 euros, si pierdes, me das 10. ¿Vale?
: Luis: Ok.

(Drini piensa VERDE)

: Luis: Pues… estás pensando en VERDE.
: Drini: No, fallaste, estaba pensando en CAFE
: Luis: Bueno, psshh… toma los 10 euros, pero me parece que has hecho trampa
: Drini: ¿trampa yo? ¿cómo te atreves a sugerir eso?

Lola

: Drini: Vamos a jugar un juego, Luis. Yo pienso un color (como blanco, rojo, azul, etc. para simplificar, nada de “azul prusiano” o “rojo bermellón”). Tienes una oportunidad de adivinar. Si atinas, te doy 10 euros, si pierdes, me das 5. ¿Vale?
: Luis: Hmm… ¿y quién me garantiza que no mentirás sobre tu elección?
: Drini: Bueno, aquí anda Netito, le digo a Netito el color que pienso, tú adivinas y él corrobora mi elección.
: Luis: Ok, me parece.
: Drini: Ya pensé el color, acércate, Netito, para que te diga mi elección.

(Netito se acerca)

: Drini: (en secreto) Mira Netito, tú limítate a asentir a lo que yo diga y te ganas 5 euros, ¿ok?
: Netito: Ok.

: Drini: Estamos listos, Luis, ya pensé un color. Adivina.
: Luis: Estás pensando AZUL.
: Drini: No, pensé en ROJO. ¿verdad Netito?
: Netito: Sí, pensó ROJO.
: Luis: Pshh.. otra vez perdí, toma los 10 euros. Nos vemos luego.
: Drini: Bye, Luis.

(Drini le da 5 euros a Netito)

Matrix

Los ejemplos son bastante metafóricos, y en realidad está hablando de Internet, para aquellos a los que no les ha caído el veinte.

En un entorno digital, donde las interacciones no son persona a persona, hay un elemento de incertidumbre siempre presente sobre la fiabilidad de la información. ¿Cómo garantizar que la persona con la que hablamos sea quien afirma ser? Podría ser alguien más tomando su lugar (usando su mismo nombre de usuario, robando sus contraseñas, etc.) Por ejemplo, si alguien muestra un correo electrónico o un “log” de una conversación como prueba de algo, ¿cómo saber que no han sido alterados o inventados?

Además, toda la información que transita por Internet, cada mensaje, cada correo, pasa (sin que se note) por docenas de servidores intermediarios (netitos), cada uno de ellos puede alterar la información. Y es que en el ejemplo había muy poco en juego. Pero ¿y si fuera esencial certificar la veracidad de alguna afirmación? Por ejemplo, si estuviera en juego la contraseña a una cuenta bancaria, o si hubiera información confidencial que no deba ser manipulada…

Un listo podría notar que en los ejemplos bastaba con que yo escribiera en un papel el color pensado, y lo mostrara después de su elección, pero en línea, donde las personas no interactúan cara a cara, eso no es posible. El equivalente digital sería almacenar la información en un sitio (por ejemplo en una pagina web) y luego indicar al jugador que acceda a la página, pero nuevamente los mismos fallos se presentan: yo podría alterar la información antes de que el otro jugador la vea, podría una tercera persona intervenir (a favor mío o del otro jugador). Piensa que podrían no ser 5 euros en juego, sino 500mil. Incluso si yo pusiera la información en una página protegida con contraseña, podría yo cambiarla antes de que el oponente acceda a ella (yo hago trampa), pero también podría la otra persona “adivinar” la clave y leer la respuesta sin que yo me entere (siendo ahora yo la víctima).

El problema de certificar información digital es bastante complejo. Concentrándonos en la situación del juego, lo esencial del problema es:

  1. Se tiene que fijar un dato (el color)
  2. Se tiene que mantener secreto un tiempo y revelarse luego de algún evento.
  3. Se tiene que certificar que la información no se haya manipulado en el tiempo intermedio.

Una forma de solucionarlo es cifrando el color y entregándolo al inicio del juego. Así nos aseguramos que el recipiente no conozca la información antes de tiempo (por estar cifrada), así como que yo no la pueda cambiar (porque desde el inicio del juego el otro participante ya tiene la respuesta en su poder).

Corre

: Drini: Vamos a jugar un juego, Luis. Yo pienso un color (como blanco, rojo, azul, etc. para simplificar, nada de “azul prusiano” o “rojo bermellón”). Tienes una oportunidad de adivinar. Si atinas, te doy 10 euros, si pierdes, me das 5. ¿Vale?
: Luis: Hmm… ¿y quién me garantiza que no mentirás sobre tu elección?
: Drini: Bueno, aquí anda Netito, le digo a Netito el color que pienso, tú adivinas y él corrobora mi elección.
: Luis: No, yo sé que ustedes son amiguetes y lo más probable es que se pongan de acuerdo para estafarme. A otro perro con ese hueso.
: Drini: Tengo otra idea. Yo escojo el color, lo cifro mediante un código y lo escribo en esta pizarra, así te aseguras de que ya no puedo cambiar mi elección. Después de que adivines, te digo cómo descifrar el código y verificas si la respuesta que das coincide o no.
: Luis: Bueno, así me parece bien, porque ya no puedes cambiar tu respuesta (está en la pizarra) y yo podré comprobar si acierto o no cuando me reveles el código. ¡Juguemos!
: Drini: Perfecto, entonces escribo en la pizarra… TIRH.
: Luis: Me parece que pensaste en GRIS
: Drini: No, fallaste de nuevo, el color que pensé es AZUL. Paga tus 10 euros.
: Luis: ¡Momento! Revélame el código para que yo pueda asegurarme de realmente perdí.
: Drini: Claro, el código de cifrado es:

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
T N O S U J Y B X E V H G A P D M C L F R Q W K Z I

Cada letra de la fila superior se cambia por la letra de la fila inferior.
: Luis: Psshh… pues sí, perdí 😦 toma tus 10 euros.
: Drini: Je, je, je…

Matrix recargado

Nuevamente, me he pasado de listo. Antes de continuar, considera el siguiente cifrado:

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
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Mucho más natural, ¿no? Y bajo ese esquema.. TIRH = ….

Ha quedado clara la falla del sistema en el último escenario. No basta con hacer público el mensaje cifrado. También hay que hacer público el método de cifrado antes de la toma de decisiones porque de lo contrario no se está garantizando el tercer punto del problema (el mensaje no debe ser alterado).  La trampa se hace ya no alterando el mensaje, sino la forma de descifrar el mensaje (para obtener la respuesta que se quiera).

Ahora, si al inicio del juego le diera la tabla de código a Luis podría él revertir el cifrado al leer TIRH en la pizarra y darme la respuesta correcta sin necesidad de adivinar, por lo que revelar el método al inicio del juego asegura que se cumple la condición 3 pero ya no la condición 2 (que el mensaje debe ser secreto hasta que yo decida revelarlo). Ser o no ser…

De nueva cuenta, la historia es metafórica, la situación bien podría corresponder a dos empresas haciendo una transacción de varios millones, pero que la trasferencia electrónica se deba hacer sólo después de haber firmado el contrato, siendo imprescindible que un documento permanezca secreto durante las negociaciones pero al mismo tiempo no sea posible modificarlo. E incluso, aunque no se diera el método de cifrado al inicio del proceso (permitiendo a la empresa Drini Co. hacer trampa al final), sería posible que la Luis contratara un hacker que descubriera la forma de descifrar el documento (permitiendo a Luis Inc. hacer trampa al inicio).

El Señor de los Anillos

Malo si haces (revelar el código al inicio), malo si no haces (revelar el código al final). Aparentemente.

La verdadera causa del problema es que los cifrados usados en el ejemplo son reversibles. Es decir, si se conoce el método se puede pasar de un mensaje “en claro” a un mensaje “cifrado” y viceversa.
Una vez fija la tabla, es posible ir y venir entre las dos formas sin ningún esfuerzo, quien posea la tabla poseerá todas las piezas del rompecabezas.

Incluso podríamos imaginar un sistema en donde los métodos de cifrado y descifrado sean distintos, revelaríamos el método de cifrado al inicio y revelamos el de descifrado al final. Aunque en apariencia más robusto que el esquema anterior, en realidad padece de los mismos problemas. Por ejemplo: el oponente podría descubrir por sí mismo el método de descifrado tomando ventaja durante el proceso.

La solución está en (redoble de tambores…) usar un sistema de cifrado que “no se pueda descifrar”. Siendo más precisos, una proceso para cifrar un mensaje que no se pueda revertir, por lo que no sea posible obtener el mensaje original a partir del mensaje en clave (aunque se conozca el proceso de cifrado).

De esta forma, al inicio del proceso los participantes se ponen de acuerdo en el proceso de cifrado, se da el mensaje en clave garantizando la inviolabilidad del mismo, y al no ser posible revertir el proceso se garantiza también el secreto.

En teoría se oye bien, pero ¿cómo obtener tal método? La respuesta es: mediante funciones de hash. Pero antes…

Las dos torres

Antes de explicar cómo obtener un método que no se pueda revertir, primero vamos a ver cómo obtener un método que sea ”difícil” de revertir.

Ya en el rollo digital, lo primero que haremos será trabajar con números. Convertimos cada letra a un número como sigue:

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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Así, por ejemplo, la palabra “WIKI” corresponde a (23 9 11 9).

El método de cifrado es:

  • El número correspondiente a cada letra, se eleva a la quinta potencia, se divide entre 29 y se toma el resto para obtener el valor cifrado

Por ejemplo, la letra V (que corresponde al número 22) se transforma en la M porque:

225 = 5153632  dividiendo entre 29 se obtiene 177711 y el resto de la división es 13, correspondiendo a la letra M.

Bajo este esquema, PEDRO se convierte, por ejemplo, en SVIOJ. El sistema es relativamente simple (con una calculadora se puede cifrar  un texto manualmente en unos par de minutos) pero es muy invertir el proceso.

Como reto, descifrar el mensaje ALBE (es decir, qué palabra de 4 letras se convierte, mediante el proceso descrito, en ALBE). La siguiente sección proporciona una forma de solución.

El regreso del rey

Supongamos que queremos descifrar la letra K (es decir, 11). Tenemos que hallar un número x tal que al elevarlo a la 5, dividir entre 29 y tomar el resto, el resultado sea 11. En otras palabras, resolver la ecuación de congruencia x^5 = 11 (mod 29), el cual ya no es un problema elemental de teoría de números y se conoce como el problema del logaritmo discreto.

Pero realmente no es necesario estudiar aritmética avanzada para descifrar el mensaje. El esquema sigue padeciendo de la misma debilidad: los mensajes con completamente reversibles. En otras palabras, no hay dos letras que se transformen o cifren en una misma. Así, como ya sabemos que la P se convierte en S, cada vez que aparezca una S en el mensaje cifrado sabremos que el original es P.

Como consecuencia, para descifrar el mensaje basta /construir/ la tabla nuevamente y se obtiene un diccionario para realizar la traducción en cualqueir sentido. Disponiendo de métodos electrónicos es cuestión de minutos reconstruir la tabla de cifrado

A B C D E F G ...
A C K I V D P ...

así, si recibiéramos el mensaje cifrado KADV, sabríamos que el original es CAFE, sin necesidad de hacer más cálculos.

Hay que aclarar un punto sutil. No estamos “descifrando” en el sentido de invertir el proceso de codificación (porque no calculamos el logaritmo discreto) lo cual es difícil, sino que hicimos trampa reconstruyendo todas las posibilidades de cifrado para obtener un diccionario. Pero.. ¿y si eso no fuera posible? Por cierto, la solución del reto en la sección anterior es AQUI (AQUI se cifra como ALBE).

Matrix revoluciones

Una función de hash es una función que es “fácil” de calcular, pero imposible de revertir por no ser “uno a uno”.

Supongamos que ahora el método de cifrado consiste en elevar al cubo, dividir entre 19 y tomar el resto.

Cuando hagamos la trampa de reconstruir el diccionario obtendremos:

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
A H H G K G A R G L A R L H L K K R S A H H G K G A

Y nuestro truco habrá sido derrotado, porque si recibimos el mensaje HARL ya no sabremos si corresponde a la palabra BALO o CARO

La novedad es que este nuevo sistema ya no es “uno a uno” (correspondencia exacta entre un código y otro) sino que hay colisiones en el método. Por tanto, es realmente imposible saber a ciencia cierta el mensaje original

Dado que es imposible “descifrar” el mensaje ¿qué utilidad puede tener tal tipo de función? La respuesta es: certificación digital.

Si en el juego de adivinar colores, yo pensara AZUL acordando publicar el hash (cifrado) con el método de elevar al cubo y dividir entre 19, pondría en la pizarra: AAHR

Dado que hay muchas palabras que dan el mismo hash, específicamente, hay 625 diferentes palabras de 4 letras con el hash AAHR, Luis tendría que calcular todas las 625 combinaciones para poder adivinar mi color.

Quizás aquí convenga cambiar un poco el juego para hacer énfasis en los puntos finos de la situación. Si el juego consistiera en adivinar una palabra de 4 letras (no necesariamente un color), y digamos, yo pienso CABO, el hash que haré público será HAHL. Luis tiene que adivinar qué palabra de cuatro letras pensé, habiendo 625 diferentes posibilidades. Para él, saber el hash le es inútil (porque no puede usarlo para recuperar la palabra original dado que hay colisiones). De esta forma, el hash asegura la segunda condición del problema (mantiene el secreto), pero ¿qué hay de la tercera, que yo no pueda falsificar la respuesta?

Imaginemos que Luis por suerte propone CABO, la misma palabra que yo había pensado. Para hacer trampa, tendría yo que encontrar una palabra de 4 letras que tenga el mismo hash y en realidad no es difícil hacerlo: por ejemplo NABO, NANO, CANO, VANO, etc.

Sin embargo, lo que sucede es que la función que di como ejemplo NO es una buena función de hash, es una función muy simple para propósitos ilustrativos. Sin embargo hay funciones de hash que sí satisfacen el tercer criterio (la inviolabilidad del mensaje).

¿Porqué es una mala función de hash? La principal debilidad es que hay demasiadas colisiones, lo que proporciona bastante espacio de maniobra para generar nuevas combinaciones con el mismo hash. Es decir, hay mucha probabilidad de colisión. El enfoque de crear un diccionario para romper el hash no es de mucha utilidad ya que en aplicaciones el diccionario no contendría 26 letras sino que constaría de miles de millones de entradas.

Las funciones de hash usadas en aplicaciones reales son algoritmos muchísimo más complejos que los del ejemplo, imposibles de revertir y prácticamente imposible generar un mensaje falso que tenga el mismo hash que un mensaje dado. Dependiendo del algoritmo y de los parámetros que se usen, se obtienen diferentes grados de seguridad.

Por ejemplo, el hash MD5 se usa comúnmente para verificar que la descarga de un archivo sea correcta (si el hash del archivo descargado no coincide con el hash publicado en el sitio web, es que la descarga se realizó incorrectamente) funciona porque la probabilidad de que el archivo corrupto tenga el mismo hash que el archivo original es casi nula. Pero aunque es seguro para certificar la información en una descarga cualquiera en Internet, no sería apropiado para certificar una transferencia de millones de euros, en cuyo caso se usaría un hash mucho más fuerte (de mayor complejidad y que haga uso de mayor cantidad de recursos computacionales).

La vida de Brian

Una aplicación de certificación con hashes es la comprobación digital de identidad.

El problema es éste: yo tengo una cuenta en un sistema (digamos Wikipedia). Si por alguna razón alguien robara mi contraseña, podría suplantar mi “identidad” en el sistema y actuar en mi nombre. Incluso podría cambiar la pregunta que se usa para recuperar la información, cambiar la dirección de correo electrónica asociada a la cuenta. En otras palabras, yo perdería por completo la posibilidad de recuperarla.

Bueno, podría yo acudir a los administradores del sistema quienes podrían reasignarme una nueva contraseña para recuperar la cuenta. Pero el problema surge de nuevo: ¿cómo garantizar que efectivamente soy yo quien está pidiendo la ayuda?

Es decir, otra persona podría intentar hacerse pasar por mi, pidiendo ayuda para que se le reasigne una clave y entonces los administradores del sistema le entregarían las llaves del reino, pensando que me las entregan a mi. No pueden enviar tampoco una contraseña a la dirección de correo, porque podría haber sido alterada.

Siendo un problema de certificación, de nueva cuenta podemos resolverlo usando hashes públicos. Como bien se dice, la prevención es la mejor solución.

En este momento, selecciono una frase cualquiera, por ejemplo:

Mira siempre el lado bueno de la vida

y calculo su hash bajo un esquema criptográfico de alta seguridad conocido, por ejemplo, SHA-512. Entonces hago público hoy el hash (por ejemplo, incluyéndolo en mi página de usuario):

82748725d9aabf69f9aded742f7e7faee94f6b9228b
767434eb4030fd4b8a9869503e90ee09700df8ddde0
929253cc07236d48f956a2de6eb30ab19085d47959

indicando que es una certificación digital de mi identidad

Transcurre el tiempo y sucede el temido evento de que mi cuenta es robada, mis datos alterados, mi correo electrónico cambiado, etc. Acudo con los administradores del sistema pidiendo ayuda:

: Drini: Buenos días, necesito ayuda para recuperar mi cuenta que ha sido robada. ¿podrían asignarme una nueva contraseña?
: Devs: No, porque podrías ser un impostor ¿quién nos garantiza que tú eres el dueño original de la cuenta?
: Drini: Ah, porque tengo una certificación digital de mi identidad. El día 17 de julio de 2008 puse en mi página de usuario el hash SHA-512. El impostor no conoce la frase original pero yo sí, la cual es:
“Mira siempre el lado bueno de la vida”
: Devs: Ok, espera un par de minutos mientras calculamos el hash de esa frase.
(…..)
: Devs: ¡Coinciden! Eso nos prueba que eres el dueño de la cuenta, ¿a dónde quieres que enviemos la nueva contraseña?

Asunto resuelto. ¿porqué funciona el esquema? Porque aunque otra persona tenga posesión de mi cuenta, no podrá crear una frase que tenga el mismo hash que publiqué, debido a que estoy usando un hash de alta seguridad.

En realidad, el problema de los colores es una metáfora de esta situación. Poner el hash en mi página de usuario, equivale a seleccionar un color y mantenerlo secreto, hasta que llega un momento (el final del juego/la certificación de la identidad) en que revelo la frase original, garantizando que la respuesta es la misma que la seleccionada originalmente.

Para más información: [[en:Commitment_scheme]] pero ojo, que cualquiera puede editar la wikipedia de modo que no se puede confiar en su información.

Existen herramientas en línea para calcular y verificar hashes: [1] y [2]

Anuncios
  1. Ejele :

    *Drini: […]Si atinas, te doy 10 euros, si pierdes, me das 5 ¿cinco? =P[…]
    *Drini: (en secreto) Mira Netito, tú limítate a asentir a lo que yo diga y te ganas 5 euros, ¿ok? […]
    *Luis: Pshh.. otra vez perdí, toma los 10 euros. Nos vemos luego.
    *Drini: Bye, Luis.

    (Drini le da 5 euros a Netito)

    ¡Que generoso nos salió Luis, dando 10 cuando el pacto fue de 5 XD!

  2. Me gustó tu post, mucha informacion y con peritas y manzanas, genial !

    Saludos !

  3. Felicitaciones, bien claro

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

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: