Feeds:
Entradas
Comentarios

Posts Tagged ‘teoría de la información’

Un ordenador puede generar números aleatorios

En nuestro anterior mito, ya apuntamos hacia esta interesante -o eso creo- pregunta: ¿puede un ordenador generar números aleatorios?

Seguramente, un primer pensamiento intuitivo apunte a una respuesta afirmativa. Dado que los números aleatorios son muy utilizados en informática, y especialmente en criptografía; parece lógico. Además, todos hemos programado alguna vez usando las típicas funciones random. Bien, pues a pesar de ello, la respuesta es que NO.

Un ordenador es un sistema determinista. Esto quiere decir que tiene una relación directa de causa-efecto, por lo que, dada una misma entrada y un mismo proceso, siempre obtendremos una misma salida… aunque Windows a veces parezca contradecir este principio. Dado un algoritmo determinado, por tanto, si queremos ver cambios en la salida (efecto), tendremos que efectuar cambios en la entrada (causa).

Así, los algoritmos de generación de números “aleatorios” son en realidad, algoritmos de generación de números “pseudoaleatorios. Esto quiere decir que los números que obtenemos no son aleatorios, pero bajo determinadas circunstancias y condiciones, podemos utilizarlos como si lo fueran. Para generar estos números pseudoaleatorios, los algoritmos utilizan entropía externa al sistema, que actúa como semilla de generación para la entrada del proceso.

Esta entropía es captada en sistemas caóticos que, pese a ser deterministas, se ven influidos por un gran número de variables; y cuya modificación, aún siendo leve, puede variar en gran medida el estado del sistema. Los ejemplos más típicos de captación de entropía en ordenadores son la interacción con el usuario (movimiento del ratón, pulsación de teclas, etc.) o con las redes de comunicaciones (flujo de entrada/salida, estado de buffers, etc.). Así, y por poner un ejemplo, al generar una pareja de claves en GnuPG, el sistema instará al usuario a maximizar la interacción con el sistema, para así magnificar los cambios introducidos en la entropía del sistema caótico.

Pero, ¿y si cambiamos un poco la pregunta de nuestro mito?

Un ordenador puede obtener números aleatorios

Bueno, ya sabemos que un ordenador no permite generar números puramente aleatorios, pero que sí permite generar números pseudoaleatorios. Pero claro, ahora no estamos utilizando el verbo “generar”.

Ahora la respuesta es afirmativa. En este caso, la generación de números puramente aleatorios requiere de un dispositivo hardware que, en base a ciertos procesos físicos (desintegración de isótopos, ruido térmico, etc.), permite realizar mediciones aleatorias. Así, en el dispositivo tiene lugar algún tipo de proceso físico intrínsecamente aleatorio, que mediante los sensores apropiados será registrado por el ordenador. En última instancia, la medición efectuada será aleatoria, si bien el ordenador se limitará a realizar una lectura, no tomando parte en ningún proceso de generación.

Y hasta aquí este mito. Como siempre, espero que os haya resultado interesante.

Read Full Post »

El cifrado de Vernam no se puede usar en la práctica

En nuestro anterior mito, vimos que el secreto perfecto existe, y se denomina cifrado de Vernam. ¿Y se utiliza? Pues ciertamente sí, y de hecho ya se utilizaba en la era pre-digital, como libretas de un sólo uso.

En la Segunda Guerra Mundial fue ampliamente utilizado por varios de los contendientes; excepto los alemanes, que hicieron poco uso, al disponer del prodigio llamado Máquina Enigma… que también tiene lo suyo, por cierto. Se rumorea también que el famoso “teléfono rojo” que comunicaba la Casa Blanca con el Kremlin funcionaba mediante libretas de un solo uso. Sea como fuere, esta implementación del cifrado de Vernam requiere de un despliegue de medios logísticos impresionante, al tener que mover por todo el mundo libros de claves de una forma segura. Si cuentas en tu poder con una flota de barcos y aviones de guerra, no es tan complicado… pero eso no está al alcance de todos.

¿Y en la era digital? Bien, repasemos los principales obstáculos que presenta el cifrado de Vernam para su implementación.

En primer lugar, tenemos el problema de la longitud de la clave, que debe ser la misma que la del mensaje. Esto supondría un problema para cifrar cantidades de datos ingentes. Pero, pensándolo con perspectiva, para ciertos datos sensibles podemos asumir la utilización de claves de 1, 2 o incluso 100 Mb; pues hoy en día el ancho de banda permite manejar tales cantidades sin demasiado esfuerzo.

En segundo lugar, tenemos el problema de generación aleatoria de la clave. Tenemos pendiente otro mito sobre el tema, así que simplemente diré que es perfectamente posible generar números puramente aleatorios usando un ordenador y cierta ayuda externa.

En tercer lugar, tenemos el problema del secreto precompartido. Si dos extremos de la comunicación quieren comunicarse usando cifrado de Vernam, deberán tener en su poder una misma clave. Pero, ¿cómo hacemos para que ambos tengan la misma clave, sin que exista un contacto físico? Enviarla a través de un canal de comunicaciones implica un claro riesgo de intercepción. Cuando comento esto en clase, siempre hay algún alumno que sugiere mandar la clave cifrada; pero eso nos dejaría justo en el punto de partida… otra vez. Y esto es lo que se conoce como problema del secreto precompartido.

Para el común de los mortales, el problema del secreto precompartido se ha solucionado mediante el uso de criptografía de clave pública; en un esquema híbrido que usa la infraestructura de clave pública para intercambiar una clave y, una vez se cumplen las premisas que solventan el problema del secreto precompartido, pasa a utilizar algoritmos de cifrado simétrico. Pero claro, si queremos aplicar el cifrado de Vernam y conservar su cualidad de secreto perfecto, no podemos acudir a la infraestructura de clave pública; pues aún cuando sus algoritmos tienen un nivel de seguridad muy bueno, no son virtualmente indescifrables, ni mucho menos.

Así pues, la pregunta sobre si existe una implementación práctica del cifrado de Vernam se transforma en otra:

¿Existe un método completamente seguro de intercambiar una clave?

Pues sí, existe, y es lo que conocemos como intercambio cuántico de claves o, más coloquialmente, criptografía cuántica. Allá por julio de 2007 (sí, ha llovido…), en el número 118 de la revista @rroba publiqué un artículo sobre criptografía cuántica, donde explicaba sus bases, su funcionamiento, y algún ejemplo práctico (tanto en versión “de juguete” como en versión “hardcore“).

Lo primero que hay que tener presente es que, al menos de forma directa, la criptografía cuántica no guarda ninguna relación con la computación cuántica (sobre la que también escribí en @rroba a principios del 2007, en el número 114). Lo segundo a tener en cuenta es que este sistema no es ni muchísimo menos algo nuevo: el primer algoritmo de intercambio cuántico de claves es el BB84, propuesto en 1984 por Charles H. Bennett y Gilles Brassard.

Poner en esta entrada una explicación comprensible de BB84 sería una locura. Para que os hagáis una idea, el artículo de @rroba son 6 páginas de texto en Times a 10 puntos, y en clase me lleva aproximadamente 30 minutos dar la explicación “de juguete” y que todo el mundo (o eso creo) se entere. Así que seguiré el principio básico universal de Internet, y pondré un enlace: en esta página podréis encontrar la famosa “explicación de juguete“, que permite comprender el funcionamiento de BB84 sin meterse en matemáticas farragosas.

¿Y por qué es completamente seguro el intercambio cuántico de claves? Porque, según las propias leyes de la física, la intercepción del intercambio tiene dos consecuencias: en primer lugar, hace que la clave resultante no sea válida para ninguno de los actores de la comunicación (emisor, receptor y atacante), al utilizar un tipo de lectura destructiva; y en segundo lugar, emisor y receptor detectarían que la comunicación ha sido interceptada. Para una explicación más profunda, os remito al apartado de ataques del artículo en la Wikipedia.

Por supuesto, desde 1984 han ocurrido unas cuántas cosas, y se ha hablado de avances en el sistema (nuevos algoritmos E91 y S09), así como de avances en ataques (por ejemplo, teleclonación cuántica). Sin embargo, los principios físicos actuales (quién sabe si cambiarán) nos dicen que el sistema es seguro. Por ejemplo, por mucho que se avance en las probabilidades de clonación cuántica, el teorema de no clonación nos dice que nunca se podrá realizar una clonación cuántica perfecta.

Por poner un ejemplo práctico: realizar una clonación cuántica con una probabilidad de 50% (la esperada sin aplicar ningún ataque especial) sobre fotones entrelazados que representan bits, es completamente equivalente a inventarse directamente los bits de la clave. La probabilidad de acertar cada bit es del 50% (es 0 ó 1), idéntica a la de leer correctamente en fotón. Acumulando la probabilidad sobre un conjunto de información suficientemente largo, vemos que no parece un método que ofrezca buenos resultados. En resumen: la probabilidad esperada de interceptar correctamente un intercambio cuántico de claves, es la misma que de inventarse la clave y acertar.

Así, existen implementaciones prácticas del intercambio cuántico de claves, que se sirven de BB84 (o algún algoritmo equivalente) para intercambiar claves aleatorias, y después poder aplicar, por fin, el cifrado de Vernam. Como curiosidad histórica, la banca es uno de los principales mercados donde se utiliza la criptografía cuántica de forma práctica, y de hecho en 2004 se produjo en Viena la primera transferencia de dinero usando criptografía cuántica.

Y hasta aquí este segundo mito, espero que os haya gustado. Siento que me dejo innumerables cosas en el tintero, pero es que la criptografía cuántica es un tema tan complejo, que podríamos dedicar un blog completo sólo a ella.

Read Full Post »

Como ya hiciera en su día con las extensiones de Firefox, inauguro con esta entrada una nueva serie que lleva por título “Cazadores de mitos de seguridad“. ¿Y a qué estará dedicada? Bueno, creo que el título es bastante aclarativo: vamos a intentar desterrar ciertos mitos y creencias relacionadas con la seguridad de la información que, en menor o mayor medida, parecen estar arraigadas en el subconsciente colectivo.

Cabe reseñar un detalle más: hablaremos de mitos o creencias que, aunque pudieran ser incorrectos de forma parcial o total, no son completamente absurdos. Vamos, que son de los que una persona con todas sus neuronas operativas podría creerse. Es decir, nada de “cierran hotmail“, “quién te tiene bloqueado en el messenger“, “soy el representante de chupa-chups” y demás chorradas de cadenas de correos. Que vamos a cazar mitos, no gilipolleces. :P

Sin más, vamos a cazar nuestro primer mito…

No existe el cifrado perfecto

Cuando comienzo el tema de criptografía, todos los años hago a mis alumnos una de mis preguntas trampa favoritas: ¿existe el cifrado perfecto? Respondiendo de una forma puramente intuitiva, todo el mundo parece predispuesto a pensar que la respuesta es no. Además, la dinámica de la seguridad de la información, donde rige esa máxima de “hecha la ley, hecha la trampa“, parece ayudar a impulsar esta creencia.

Y sin embargo sí existe el secreto perfecto, un sistema de cifrado irrompible. Una vez que se conoce esta información, lo siguiente que se pregunta la gente es: ¿cómo de nueva es esta técnica? ¿sólo está al alcance de gobiernos? ¿cómo es de compleja?

Y aquí es donde llega la segunda sorpresa. El cifrado de Vernam -así es como se llama el secreto perfecto, en honor a su descubridor, Gilbert Vernam– data de 1917, es tan simple como el álgebra de Boole, y podría llevarlo a cabo un niño pequeño con papel y lápiz. ¿Y en qué consiste exactamente? Formalmente, se trata de la combinación de un texto en claro con una clave completamente aleatoria de un solo uso, y de la misma longitud que el mensaje. Pero veamos un ejemplo algo más práctico…

Imaginemos que tenemos un mensaje codificado, con una longitud total de 10 bits. Generamos una clave aleatoria de 10 bits, y realizamos la combinación mediante la operación XOR:

texto en claro: 0 1 0 0 1 1 0 1 0 0
         clave: 1 0 1 1 1 0 0 1 0 1
 texto cifrado: 1 1 1 1 0 1 0 0 0 1

El proceso de descifrado sería el inverso, aplicando la operación XOR al texto cifrado y la clave:

   texto cifrado: 1 1 1 1 0 1 0 0 0 1
           clave: 1 0 1 1 1 0 0 1 0 1
texto descifrado: 0 1 0 0 1 1 0 1 0 0

¿Y por qué es irrompible este cifrado?

Siendo formales, porque así lo demostró el padre de la teoría de la información, el mismísimo Claude E. Shannon (Shannon, Claude (1949). “Communication Theory of Secrecy Systems“. Bell System Technical Journal 28 (4): 656–715). Pero claro, a ver quién tiene narices de comprender perfectamente ese paper

De una forma intuitiva, vamos a tratar de dar una explicación “de andar por casa“: dado un mensaje cifrado con longitud de n bits, podríamos generar y utilizar todas las 2^n posibles claves, que nos permitirían descifrar todos los 2^n posibles mensajes en claro; y que, en la práctica, se corresponden con todos los posibles mensajes que se pueden codificar con n bits. Resumiendo: podríamos hacer que, dada la clave apropiada, el mensaje original fuera virtualmente cualquiera que pudiera haberse representado con tal cantidad de información.

En resumen, hay tres características imprescindibles que debe cumplir la clave en el cifrado de Vernam:

  1. La clave debe tener la misma longitud que el mensaje.
  2. La clave debe ser completamente aleatoria.
  3. Cada clave debe utilizarse una única vez.

Estas características, y en especial la última, hacen que una de las implementaciones más conocidas del cifrado de Vernam sea la de la libreta de un solo uso (one-time pad), que tanto se ha utilizado a lo largo de la historia.

¿Y si no se cumplen estas características?

  1. Si la clave tiene una longitud menor que el mensaje, no será posible aplicar la operación de forma completa.
  2. Si la clave no es aleatoria, se podrán utilizar los patrones de la misma para llevar a cabo algún tipo de criptoanálisis, eliminando la seguridad del sistema.
  3. Si la clave se utiliza con distintos mensajes en claro, es trivial obtener la clave secreta (¡que se lo digan a Sony! xD).

¿Y por qué no se utiliza este sistema de forma exclusiva?

Lo de generar claves aleatorias hoy en día no es un problema, pues aún cuando los ordenadores sólo pueden generar información pseudoaleatoria (habrá otro mito sobre esto), existen dispositivos que permiten generar números aleatorios reales. El problema, obviamente, es lo de usar claves del mismo tamaño que el mensaje. En primer lugar, por el volumen de información, que se duplicaría (cifrar un fichero de 4 Gb requeriría una clave de 4 Gb); y en segundo lugar, por el problema del “secreto precompartido” de los algoritmos de cifrado simétrico, que nos exige una gestión y transmisión segura de claves.

Es por esto que, tradicionalmente, los sistemas de cifrado basados en libretas de un solo uso han sido utilizados únicamente por entidades poderosas (gobiernos, ejércitos, agencias de inteligencia, etc.), con los medios y la capacidad operativa suficientes como para distribuir físicamente por todo el mundo las claves de cifrado de un sólo uso.

¿Significa esto que no existen implementaciones prácticas del cifrado Vernam?

Bueno, además de las clásicas de usar libros físicos de claves, tan típicas en la Segunda Guerra Mundial y la Guerra Fría… pues sí. Pero esto va para otro mito, que si no me alargo demasiado. :P

Además, el cifrado de Vernam ha servido de inspiración para los sistemas de cifrado simétrico de flujo, que usan el mismo concepto, pero mediante algoritmos de generación de flujos de clave. Obviamente, no disfrutan de la cualidad de “secreto perfecto” del cifrado de Vernam, al no cumplir las características de longitud completa de clave y aleatoriedad de la misma.

Y hasta aquí el primer mito. Espero que os haya gustado, y que la explicación haya quedado suficientemente comprensible. Y si he metido la pata en algo, invoco a mi buen amigo Eloi, que como experto en el tema, sabrá corregirme. :)

Read Full Post »

A %d blogueros les gusta esto: