Posts etiquetados con ‘criptografía’

La seguridad de nuestras contraseñas

Esta es nuestra cuarta entrada dedicada a la criptografía, continuando las tres anteriores “¿Estamos seguros?” y “El hombre que se enfrentó a la NSA”  y “¿Cuánticamente seguros?”.

Nos hacemos la siguiente pregunta: ¿Qué cantidad n de números enteros aleatorios debemos tomar de un intervalo [1,N]  para que la probabilidad de que dos de ellos sean iguales, sea 1/2? La respuesta es que n debe ser aproximadamente 1.18 √ N. Recordemos que un número aleatorio es aquel obtenido al azar, y existen muchos métodos para generarlos (por ejemplo, echando monedas al aire o tirando dados).

Esta pregunta podría ser una de esas que se hacen los matemáticos y que podíamos pensar que no sirven para nada útil. Sin embargo, su respuesta tiene numerosas aplicaciones prácticas en la ciencia de la computación y también en la criptografía, tal y como mostraremos a continuación.

En esta entrada veremos un ejemplo de cómo los ordenadores pueden detectar claves criptográficas y almacenar mensajes de manera correcta. En particular, el método que se describe es el de identificación de una clave.

Un método común de identificación de claves es el método de las funciones hash. Una función hash produce cadenas arbitrarias de caracteres después de introducir un mensaje en una plataforma, por ejemplo, una clave alfanumérica, de manera que no se puede crear esa cadena a menos que se introduzcan los mismos datos. Al conjunto de entradas se le llama dominio U de la función hash. A un elemento de U se le llama preimagen o, dependiendo del contexto, clave o mensaje. El término hash proviene, aparentemente, de la analogía con el significado estándar en inglés de dicha palabra en el mundo real: picar y mezclar. Donald Knuth indica que aunque Hans Peter Luhn de IBM parece ser el primero que utilizó este concepto en 1953, el término sólo habría aparecido en la literatura a finales de los 60 del siglo XX.

Hans Peter Luhn

En este artículo “¿Qué son y para qué sirven los hash?: funciones de resumen y firmas digitales”, de Pedro Gutiérrez, puede encontrarse una valiosa información sobre el tema.

Las funciones hash se usan por ejemplo para proteger contraseñas, para garantizar la integridad de una descarga de datos, o para producir firmas digitales. No son propiamente métodos de encriptación, sino algoritmos.

Las funciones hash operan matemáticamente como una función f(x) que genera N resultados diferentes e igualmente probables. Si N es muy grande, sabemos que tras evaluar la función en 1.18 √ N elementos, tenemos una probabilidad de al menos ½ de que f(x1)=f(x2).

Se llama colisión cuando dos entradas distintas a la función producen la misma salida. El rango de la función es finito, debido a que el tamaño de sus cadenas de salida es fijo. Por tanto, la posibilidad de colisión no es nula. Una buena función de hash es aquella en que las colisiones son las mínimas. Se dice que la función de hash será perfecta si es inyectiva, quiere decir, que para cada dato de entrada se obtiene una cadena diferente. Para que esto ocurra, es necesario que la cardinalidad del conjunto dominio sea inferior o igual a la cardinalidad del conjunto imagen. Normalmente, sólo se dan funciones hash perfectas cuando las entradas están preestablecidas.

Las funciones hash, además de para identificar claves, pueden utilizarse para comparar ficheros. Por ejemplo, la función hash puede leer los primeros párrafos de un fichero y asociarles, similarmente, cadenas alfanuméricas. Si obtenemos la misma cadena, podemos estar casi seguros de que los ficheros son idénticos. ¿Por qué decimos casi idénticos? El físico Bartolo Luque, profesor de la Universidad Politécnica de Madrid, nos explica muy claramente la precisión de las funciones hash en su artículo “El problema del cumpleaños y la seguridad de nuestras contraseñas”, publicado en la revista “Investigación y ciencia” . A continuación resumiremos su explicación e invitamos a leer el artículo completo, mucho más detallado que esta breve entrada en seguridad y criptografía.

Luque menciona “casi” porque existe la posibilidad de que se produzca una colisión. Un tipo particular de función hash produce ristras de 160 caracteres de longitud. Estas secuencias pueden representarse en el sistema hexadecimal, con base 16.  Así, nuestra información es capaz de proporcionar 2160=1048 salidas. Además, pueden usarse mensajes con un tamaño máximo de 264 bits, de modo que el número total de argumentos posibles es 103x 10^18, un número inmenso. El número de entradas es inmensamente mayor que el número de salidas, lo que sugiere que muchas entradas generarán el mismo resultado.

Un pequeño cálculo, volviendo al problema del párrafo inicial, nos da que para obtener una colisión con probabilidad ½, aplicando la aproximación de [1,N=1048], obtendremos n=1.18 x 1024 números aleatorios generables en el intervalo.

Como vemos, la función hash goza de una inyectividad lo suficientemente fiable como para que numerosas páginas web cifren con ellas sus bases de datos. Para un pirata informático sería una tarea ardua el descifrar nuestras contraseñas, pues les exigiría encontrar todas las entradas que produjeran un mismo hash o mensaje.

______

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, ICSU) y Cristina Sardón (ICMAT-CSIC).

Etiquetas: , , ,
Categorias: General

El hombre que se enfrentó a la NSA

En la entrada anterior contábamos el nacimiento hace unos cuarenta años de los protocolos criptográficos llamados de clave pública. Estos avances científicos supusieron el comienzo de una batalla entre la comunidad científica y la Agencia Nacional de Seguridad de los Estados Unidos (NSA) que continúa a día de hoy.

Sede de la NSA en Fort Meade, Maryland

Nos vamos atrás en la historia al año 1977. Hasta entonces, la criptografía era cosa de seguridad nacional, pero los avances que estaban experimentado los computadores anunciaban esta necesidad también para el sector privado.

El campo de batalla fue el International Symposium on Information Theory, que se celebró en la Universidad de Cornell el 10 de octubre de 1977; y el detonante, la presentación de un grupo de investigadores de la Universidad de Stanford, Martin Hellman, profesor asociado de ingeniería eléctrica y sus dos estudiantes de doctorado, Steve Pohlig y Ralph Merkle. Ya un año antes, Hellman había publicado con otro de sus estudiantes, Whitfield Diffie, un artículo titulado “New Directions in Cryptography”, en el que introducía lo que se llama protocolo Diffie-Hellman.

Martin E. Hellman

El artículo se había publicado en las revistas del IEEE (Institute of Electrical and Electronics Engineers) una sociedad científica centrada en las ingenierías, un auténtico monstruo que hoy cuenta con 420.000 miembros. Y la NSA lo leyó y enviaron una carta no oficial amenazando a Hellman con represalias, ya que consideraban que la criptografía sólo podía estar en manos de la seguridad nacional. Incluso se argumentaba que la criptografía era un arma y su publicaión contravenía la ley de exportación de armas. Temiendo represalias, Hellman defendió su causa con la ayuda de su universidad. Esta concluyó que todo era legal.

Sin embargo, ya que Pohlig y Merkle eran estudiantes, las presentaciones corrieron a cargo del propio Hellman. Todo transcurrió sin incidentes. Y realmente, el uso que se dió a este protocolo fue sobre todo en seguridad por el gobierno (y por los traficantes de drogas).

Bobby Inman

 

El nuevo director de la NSA, Bobby Ray Inman, contactó con los investigadores, descubriendo que su interés había sido el de buscar protección para los ordenadores, lo que entonces era un problema incipiente y que había pasado inadvertido a la NSA.

El problema se complicó cuando en agosto de 1977, Ron Rivest, Adi Shamir y Leonard Adleman, del Massachusetts Institute of Technology (MIT), dieron a conocer su sistema RSA. El tema era ya incontrolable, aunque el gobierno ha contado siempre con un poderoso instrumento, la financiación a través de la National Science Foundation (NSF) y de la propia NSA. Y ha creado el National Bureau of Standards (NIST), que homologa los productos criptográficos.

Es digno de reconocimiento el valor de Martin Hellman, nacido en octubre de 1945, y entonces un joven de 32 años. Hellman fue el principal protagonista en esta primera “crypto war” con la administración gubernamental.  Son muchos los premios y honores que Hellman ha conseguido desde entonces, y quizás el más relevante es el Premio Turing en 2015, que se suele considerar como el Nobel de la Computación. Hellman está usando el millón de dólares del premio para impulsar sus proyectos para el diálogo y la paz en el mundo. También ha sido reconocido su trabajo para disminuir las tensiones étnicas. Las personas interesadas pueden seguirle en su página web y en su blog.

No cabe duda de que en un mundo cada vez mas interconectado, esta disputa continuará, pero no será fácil ponerle puertas al campo de la investigación.

____

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, ICSU) y Cristina Sardón (ICMAT-CSIC).

Etiquetas: , , ,
Categorias: General

¿Estamos seguros?

Vivimos en un mundo de claves secretas para proteger nuestros datos: correo electrónico, transacciones bancarias, tarjetas de crédito, comunicaciones por móvil, … ¿Nos preguntamos cómo funciona el sistema? Todo está basado en la criptografía, y por lo tanto, en las matemáticas.

Hasta hace poco, la herramienta principal eran los números primos combinados mediante algoritmos de diferente índole, que dotarán de mayor o menor seguridad a nuestra clave. El cifrado de seguridad mediante el uso de números primos surgió en 1975 con W. Diffie y M. Hellman, de la Universidad de Stanford en California, quienes idearon el denominado cifrado asimétrico o clave pública (el llamado protocolo Diffie-Hellman). Diffie era estudiante ce Hellman, y debemos añadir un tercer personaje a la historia, R.C. Merkle. Ellos iniciaron una batalla en los setenta y ochenta del siglo XX con la agencia de seguridad del gobierno norteamericano que merece una entrada aparte.

Diffie, Hellman y Merkle

La clave pública usa las denominadas funciones matemáticas trampa, que hacen posible el cifrado, pero virtualmente imposible el descifrado. Son funciones unidireccionales. Esto quiere decir, que es muy fácil “ir” pero prácticamente imposible “volver”. Vamos a explicarlo con un ejemplo: si tomamos dos números primos al azar, como el 7 y el 13, y los multiplicamos, obtenemos el número 91. El proceso indirecto se trata de deshacer la operación y saber qué números dan 91, mediante diferentes operaciones. Porque la multiplicación, no es ni mucho menos, la única operación de cifrado. El sentido común sugiere, que para cifras pequeñas, podríamos hacer un listado de primos y combinarlos de todas las formas posibles para recuperar el 91. Sin embargo, los cifrados de nuestras redes sociales o cuentas bancarias manejan dígitos de gran envergadura. Por ejemplo, consideremos el número 1.409.305.684.859. Este número es el resultado de multiplicar dos números primos: 705.967 y 1.996.277. Encontrar este par de números,no es una tarea inmediata si usamos la lista de primos como en el caso del 91. Este cálculo necesita la implementación de un software, porque desde Euclides ya sabemos que hay infinitos números primos. Además, los ordenadores sólo trabajan con un sistema binario, lo que supone una gran limitación, pues se introducen aproximaciones en los números para poder expresarlos en base dos.

Uno de los sistemas de encriptación más famosos es el denominado RSA, siglas correspondientes con los apellidos de los criptógrafos matemáticos  Rivest, Shamir y Adlerman, que desarrollaron una de las versiones de criptografía de clave pública en 1977. La seguridad del algoritmo procede de la factorización de números enteros. Los mensajes se representan mediante números y el mecanismo se basa en la operación producto de dos números primos muy grandes, elegidos al azar y mantenidos en secreto. El orden de estos números es menor de 10200 hasta el momento; sin embargo, la capacidad creciente de cálculo de los ordenadores prevé un crecimiento del orden de precisión en las encriptaciones con números primos aún más gigantescos.

Ron Rivest, Adi Shamir y Leonard Adleman

Un dato curioso es que en 1994, se lanzó un reto a la comunidad matemática para derribar el sistema de encriptación RSA. Un grupo de 600 matemáticos con la ayuda de 1600 voluntarios consiguieron factorizar según el método RSA, un número de 129 cifras. Para desencriptar claves con cifras superiores a 1024, se necesitarían todos los ordenadores del universo desencriptando en paralelo y aún así, su tiempo de computación se calcula semejante a la edad del universo: decenas de miles de millones de años.

Uno de los paradigmas de este siglo es la computación cuántica. Y esa futura encriptación cuántica es aún un proceso emergente. La ventaja fundamental de la encriptación cuántica frente a la clásica, es una propiedad fundamental extraída de las leyes de la mecánica cuántica. Si un tercer intruso en la lectura del mensaje (el remitente, que encripta la clave, y el receptor, que la desencripta, son los dos principales roles en la emisión del mensaje) intenta hacer “eavesdropping”, término acuñado para la escucha secreta tradicionalmente relegado al ámbito de seguridad, el proceso de creación de la clave se altera, advirtiéndose el intruso antes de que se transmita la información privada. La explicación radica en el principio de incertidumbre de Heisenberg, que dicta que si realizamos una medida sobre un sistema cuántico, dicho sistema se altera después de la medida y permanece en un estado fijo, no entrelazado.

Las claves de la mecánica cuántica han de ser descifradas a nivel subatómico, pues la mecánica cuántica es la teoría del “pequeño mundo”, donde nos movemos en longitudes menores a 10-15 fermi, que es el tamaño de un núcleo atómico. Por tanto, las lecturas se harán con láser, capaz de alterar partículas cuánticas como los electrones, mediante la incidencia de fotones.

Como podemos ver, la teoría de la criptografía clásica, sólo utiliza matemáticas que podríamos llamar tradicionales, como es la teoría de números y, en particular, los números primos. Sin embargo, las teorías más contemporáneas, a partir de 1984, utilizan la mecánica cuántica, tal y como contaremos en una próxima entrada de este blog.

Para terminar, haremos unos pequeños comentarios curiosos a la teoría de la encriptación clásica. Por ejemplo, que los Estados Unidos y Canadá sólo permiten el uso de ciertas claves criptográficas en su territorio, que no tienen autorizada la venta ni la exportación. Las claves se hallan en una especie de pastillas que en contacto con el oxígeno exterior, se solidifican en una masa informe y cuya lectura con rayos X destruye la información, convirtiéndose en ceros (recordemos aquellos mensajes a James Bond) .

Sobre los números primos, existe el proyecto GIMPS (Great Internet Mersenne Prime Search), en el que cualquiera puede colaborar con su ordenador. Se trata de que el ordenador trabaje en paralelo con los ordenadores de otros muchos colaboradores voluntarios en este proyecto común: el descubrimiento de un tipo particular de números primos, los denominados primos de Mersenne, con un mínimo de diez millones de cifras. El pasado enero, todos los colaboradores de GIMPS, proclamaron el descubrimiento de un número primo de Mersenne con más de 22 millones de cifras, cuyo valor es 274207281-1. La computación sólo se llevará a cabo en tiempos muertos de su ordenador, mientras el salvapantallas esté encendido, por lo que no impedirá su trabajo habitual.

____

Manuel de León (CSIC, Fundador del ICMAT, Real Academia de Ciencias, Real Academia Canaria de Ciencias, ICSU) y Cristina Sardón (ICMAT-CSIC).

Etiquetas: , , ,
Categorias: General