La privacidad no existe

Cifrado

Cifrado con clave pública y clave privada

A finales del año pasado apareció en el blog de Chema Alonso un interesante artículo acerca de como la NSA podría haber “troyanizado” los números primos para descifrar las comunicaciones. La conclusión de dicho artículo es que la privacidad en Internet no existe. Nada queda oculto a quien dispone de los recursos suficientes. Aunque de criptografía sé muy poco, voy a intentar explicar lo que he entendido del artículo, añadiendo una introducción previa. Si me equivoco en algo agradecería que me lo hagáis saber en la zona de comentarios.

En primer lugar, cuando se habla de algoritmos de 1024 bits, estamos hablando de números que oscilan entre 1 (2^0) y 2^1024 (una cifra descomunal) En criptografía es fundamental poder escoger de la forma más aleatoria posible entre un conjunto de números primos cuanto más amplio mejor. Sabiendo los números primos que se hicieron servir, revertir el cifrado sería inmediato. Si se supiera que los números aleatorios entre los que el algoritmo escoge no son muchos, para descifrar el mensaje se debería aplicar fuerza bruta probando los posibles números. Si son pocos sería cuestión de minutos, o incluso segundos, si son muchos serían años con los mejores ordenadores actuales, incluso siglos, milenios… todo depende de la cantidad de números posibles. Entonces, ¿un algoritmo de 1024 bits de cuantos números posibles dispone para escoger aleatoriamente?

Según la función de Gauss para los números primos, la cantidad aproximada de números primos en un intervalo de 1 a m sería:

m / (ln(m))

Entonces en nuestro caso sería 2^1024 / ( ln(2^1024) ) y ese valor es enorme. Hay millones de números primos que se pueden representar con 1024 bits. Con tanta variedad, ningún ordenador actual, ni conjunto de ellos, podría romper el cifrado.

El algoritmo Diffie-Hellman, usado para el intercambio de claves en un canal no seguro, es de 1024 bits. Muchísimos servicios en Internet lo usan. Herramientas como por ejemplo SSH (y por lo tanto también SCP y SFTP) o los protocolos VPN, acrónimo para las redes privadas que funcionan a través de redes públicas.

El revuelo lo ha causado un estudio que concluye que las implementaciones del algoritmo son defectuosas y dejan sólo 68.000 números primos posibles. Según el mismo estudio, al reducirse de tal modo la cantidad posible de semillas, está dentro de la capacidad computacional de una organización como la NSA romper el cifrado casi en tiempo real, dice textualmente:

Our calculations suggest that it is plausibly within NSA’s resources to have performed number field sieve precomputa-tions for at least a small number of 1024-bit Diffie-Hellman groups. This would allow them to break any key exchanges made with those groups in close to real time.

 

Esto no acaba aquí. En criptografía, el algoritmo Dual Elliptic Curve Deterministic Random Bit Generator se considera óptimo para la generación aleatoria de números. Todo era perfecto hasta que salió un estudio de las universidades de Pennsylvania y Loraine (Francia) donde se afirma que una de las implementaciones más usadas de dicho algoritmo tiene saboteada la generación de números aleatorios:

 

The newspaper articles describe documents making specific reference to a backdoor in the Dual EC random number generator, which had been standardized by both NIST and ANSI. NIST responded by withdrawing its recommendation for the Dual EC DRBG, writing “This algorithm includes default elliptic curve points for three elliptic curves,the provenance of which were not described. Security researchers have highlighted the importance of generating these elliptic curve points in a trustworthyway. This issue was identified during the development process, and the concern was initially addressed by including specifications for generating different points than the default values that were provided. However, recent community commentary has called into question the trustworthiness of these default elliptic curve points” [38]. There is evidence that the ability to backdoor the Dual EC
algorithm has been exploited in the wild: Juniper Networks had implemented
Dual EC in NetScreen VPN routers, but had used it with custom-generated
parameters. In December 2015 Juniper published a security advisory [25] an-
nouncing that an attacker had made unauthorized modifications to the source
code for these products to substitute a different curve point in the Dual EC
implementation.

 

Con este sabotaje y hardware especializado es posible revertir el cifrado en algo menos que milenios como cabría esperar. 80 minutos son suficientes:

 

Both the Initialization and the Descent steps can be heavily parallelized.
The expected CPU-time for computing an individual logarithm is a few days
on a typical core, distributed more or less equally between the two steps. Using
parallelization, we managed to get a result in 80 minutes of wall-clock time:
the initialization took around 20 minutes parallelized across 500 cores, and the descent took 60 minutes parallelized across 352 cores. (We used 44 cores for each large special q to be descended.)

 

Las dudas razonables sobre la capacidad de la NSA pare descifrar comunicaciones  llevaron a los especialistas a preguntarse el cómo. En cierta manera, no poder explicar si es técnicamente posible era una muy buena defensa para la NSA. Ahora, y a pesar de mi gran desconocimiento sobre estos temas, me parece razonable afirmar que en Internet la privacidad no existe.  Muy recomendable leer el artículo de Chema Alonso. Espero que el mio sirva también como introducción a lo que ahí escribe pues da bastantes cosas por sabidas.

Nota:

Con el objetivo de hacer la lectura más amena he hablado de números aleatorios cuando realmente son pseudo-aleatorios. La Wikipedia contiene un artículo donde explica cómo funcionan las funciones de generación de números aleatorios de los lenguajes programación. Para entender mejor el artículo de la Wikipedia que explica su generación, hay que tener en cuenta que en matemáticas, se dice que dos números a y b son congruentes respecto al módulo m cuando al dividirlos ambos por este módulo producen el mismo resto. Me resulta curioso que algoritmos mucho más complejos para la generación aleatoria de números, usados en “grandes ligas” como la criptografía, sigan siendo pseudo-aleatorios. Por supuesto, implementados sin trampa, la aleatoriedad que consiguen es más que suficiente para lograr el objetivo de cifrar de forma segura.

 

Un pensamiento en “La privacidad no existe

  1. Pingback: Un algoritmo de generación de números pseudoaleatorios | Víctor Iglesias

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.