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.

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.

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.)