La Gran Búsqueda de Números Primos de Mersenne en Internet para superar el mayor Número Primo conocido hasta la fecha

Si hace tres días me dice que os iba a estar hablado de esto no me lo hubiera creído, pero me escribieron a mi buzón de MyPublicInbox con una consulta sobre un trabajo de investigación, y una cosa me llevó a otra, y acabé por leer de todo esto un ratito, así que os he hecho este pequeño artículo que seguro que a más de uno os sucede como a mí, que acabáis descubriendo alguna curiosidad que, quién sabe, lo mismo os permite ganar un quesito algún día. 

Figura 1: La Gran Búsqueda de Números Primos de Mersenne en

Internet para superar el mayor Número Primo conocido hasta la fecha

Por supuesto, el trabajo de investigación no es nada de esto, pero sí que necesitaba entender previamente todo esto. Os lo cuento en un artículo cortito.

Todos sabéis de la importancia de los Números Primos para muchas cosas, por su característica de que son divisibles sólo por 1 y por sí mismos. Una de las áreas donde más impacto tienen es en el mundo de la Criptografía Moderna de hoy en día, donde el cifrado con claves RSA se basa en tener dos números primos p y q, que multiplicados dan n. Y la gracia es que calcular n a partir de p y q es trivial, porque es una operación directa, pero si tienes n, encontrar los dos números primos p y q es complicado y computacionalmente costoso.

Figura 2: Libro de Cifrado de las comunicaciones digitales:
de la cifra clásica a RSA 2ª Edición de 0xWord

Los Criptoanalistas buscan junto eso, crackear el código RSA en tiempo útil, buscando vulnerabilidades en las implementaciones de software, o nuevos avances tecnológicos en el cálculo de la descomposición factorial o nuevas aproximaciones matemáticas que reduzcan la complejidad algorítmica y hagan que se pueda romper una clave RSA en tiempo útil. Para seguir esto tenemos el RSA Challenge, que intenta saber qué longitudes de claves de RSA son las que ya no se consideran seguras.

Figura 3: RSA Factoring Challenge RSA2048

Por supuesto, la llegada de los Quantum Computers se supone que hará que todo ese proceso sea trivial, y por tanto llevamos años trabajando en nuevos sistemas de Criptografía Cuántica - basándonos en las propiedades del envío de información sensible con haces de luz - y la Criptografía Post-Cuántica (PQC), que se centra en utilizar sistemas de Criptografía no basados en factorización de números primos. En el mundo de la algorítmica tuvimos avances como el "Fast Factoring Integers by SVP Algorithms" con una propuesta de descomposición factorial más rápida, o el famoso "Algoritmo de Shor".

Figura 4: Algoritmo de Shor en Wikipedia en Español

En la parte de Criptografía Cuántica tenemos los Quantum Random Number Generators o los Sistemas de Quantum Key Distribution, que ya se están usando en producción, pero mientras llegan los ordenadores completos, estamos protegiendo los sistemas con algoritmos de criptografía que no basan su seguridad en la dificultad de la operación de factorizar los primos para n. Son los algoritmos de Post-Quantum Cryptography. Desplegarlos, es lo que se conoce como tener estrategias de Quantum Readiness o Quantum Safe. Todo por no ser complejo para un Quantum Computer calcular un número primo. De todo esta parte hablaremos en el Programa de Quantum y Post-Quantum Computing para Ciberseguridad: Formación Especializada, Libro & Foro Online que estamos llevando con la Universidad de Deusto.

Figura 5: Módulos de la formación de Quantum y Post-Quantum

Computing para Ciberseguridad

En toda esta amalgama de aproximaciones, disciplinas y áreas de investigación, seguir encontrando nuevos Números Primos o nuevas formas de probar si un número es o no es un Número Primo de forma acelearada sigue siendo importante y relevante. Si miramos al futuro mundo de Súper Computación y con que estamos creando en la carrera de por Súper Inteligencia Artificial puede ser que tengamos que extender la longitud de las claves a tamaños mucho mayor o aplicar, al mismo tiempo que puede hacer que sea más trivial romper una clave RSA. 

El Número Primo Más Grande

Aún no sabemos cuál puede ser la importancia real en la práctica en el futuro, pero si sabemos que avanzar en estas áreas de investigación es importante. Una de estas áreas de trabajo es seguir expandiendo los Números Primos y para tener un mayor conjunto de estos, y más grande que utilizar. Por eso, a día de hoy, continuamos buscando números primos de mayor tamaño.

De entre los Números Primos, hay un grupo especial de ellos que se llaman los Primos de Merssene, en honor al matemático francés Marín Mersenne que los comenzó a estudiar. Son números primos que son un número menos que una potencia de dos. Es decir, el número 3 es igual a 4 que es 2^2 menos 1. Lo mismo sucede con el número 31 que es 2 ^5 - 1.  Y no son tantos. A día de hoy se conocen 52 números Primos de Mersenne, y la distancia entre cada uno de ellos es cada vez mayor en el número de dígitos que tienen.

Figura 6: Evolución en la búsqueda de Primos de Mersenne y sus dígitos

Por supuesto, no todos los números potencia de 2 menos 1 son números primos (sólo 52 hasta día de hoy lo son), pero se ha dado la circunstancia de que los últimos Números Primos más grandes descubiertos son todos Primos de Mersenne, así que ahí seguimos buscando los siguientes. Entre otras cosas - que el conocimiento per sé es más que suficiente - porque permite acotar además los números que hay que probar para localizar el siguiente Número Primo, mirando en únicamente si es un posible Primo de Mersenne.

Figura 7: GIMS (Great Internet Mersenne Number Prime Search)

El último Número Primo que es Primo de Mersenne descubierto es el 2^136.279.841 − 1 también llamado M136.279.841, y fue descubierto el 12 de octubre de 2024 por Luke Durant, tal y como se anunció en el proyecto GIMS (Great Internet Mersenne Number Prime Search), que desde el año 1996 busca eso, localizar con la ayuda de todos los investigadores de Internet el siguiente Primo de Mersenne

Si no conocías algo de esto, pues ya has aprendido algo hoy, pero si lo conocías, ya sabes que tenemos muchas áreas en las que investigar, y en las que trabajar, y puedes ponerte a ello. Me encantaría jugar a predecir cuándo - gracias a la evolución tecnológica - vamos a localizar el próximo número. ¿Te atreves a especular?

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)  

Ataque de Side-Channel a conversaciones con ChatGPT, CoPilot y otros LLMs

Hoy os vengo a hablar de un paper que fue publicado ayer mismo, y que me ha gustado mucho. Es una investigación que intenta descifrar la conversación que un usuario está teniendo con un LLM por medio de capturar la estructura de Tokens que se ha intercambiado, como side-channel.

Figura 1: Ataque de Side-Channel a conversaciones con ChatGPT, CoPilot y otros LLMs

Esto podría ser un problema clásico de criptografía y cripoanalisis, pero la gracia es que utilizan un LLM para que ayude a resolver el problema, os lo explico un poco para ver si queda más claro.

Figura 2: Libro de Cifrado de las comunicaciones digitales:
de la cifra clásica a RSA 2ª Edición de 0xWord

La idea es que tenemos un servicio que está utilizando un LLM, y éste servicio puede ser un chat, como ChatGPT o un CoPilot como el de Microsoft, donde el usuario está teniendo una conversación con el el motor LLM, que puede ser GPT3.5, GPT4, Llama2, o cualquier otro. 

Figura 3: Secuencias Tokenizadas por GPT3.5 y GPT4

Cuando el modelo LLM envía la información protegida contra inspección, el Tokenizador envía los datos en Stream, es decir, que hay una secuencia continua de Tokens que deben ser marcados periódicamente para saber cuándo comienza y termina un Token para poder ser descifrado y enseñado al usuario, tal y como se ve en estos dos ejemplos de la Figura 3 de cómo los Tokenizadores de GPT3.5 y GPT4 funcionan.

Figura 4: What Was Your Prompt? A Remote Keylogging Attack on AI Assistants

Supongamos que el atacante es capaz de acceder a la secuencia cifrada enviada por el Tokenizador, ¿Podrá saber de qué se está hablando o qué está diciendo? Esta es la pregunta que trata de resolver el paper de "What Was Your Prompt? A Remote Keylogging Attack on AI Assistants", y que como podéis imaginar, la respuesta es sí para muchos entornos.

Figura 5: Servicios vulnerables a este side-channel para descifrar de qué se está hablando.

Y la respuesta es la que véis en la imagen anterior, donde la mayoría de los servicios son vulnerables a esta técnica de ataque. Y para hacerlo sólo hay que utilizar la tecnología que tenemos a nuestro alcance. Al final, existen tres técnicas que pueden ayudar a inferir de que se está hablando, que se van a usar en el modelo descrito en el gráfico anterior, y que son las siguientes:

1.- Utilizar un LLM entrenado para analizar Tokens y saber de qué puede ir la conversación: Como os podéis imaginar, es un problema donde un con un modelo entrenado con datos de cadenas de Tokens y tipos de conversaciones que se están teniendo, la inteligencia artificial generativa puede ayudar. Así, los investigadores han entrenado un LLM con estas conversaciones Tokenizadas para poder evaluar de qué se está hablando y qué se está diciendo en concreto.

2.- Utilizar el contexto para incrementar el ratio de acierto: Al final, las conversaciones con un LLM son cadenas tokenizadas secuenciadas, lo que hace que si se averigua una conversación en un secuencia, se le puede decir al LLM que averigüe el tipo de conversación en la secuencia+1 sabiendo que en la secuencia anterior se hablaba de un determinado tema. Esto incrementa el índice de aciertos. Lo mismo hacia atrás una vez que se ha terminado el proceso.

3.- Texto plano conocido: No hace falta decir que es posible saber qué determinadas respuestas se están diciendo de forma repetida. Es decir, ChatGPT utiliza más o menos las mismas respuestas para terminar sus conversaciones de determinados temas, o para declinar contestar porque el Prompt solicitado está dentro de los marcados como Harmfull Mode. Sabiendo estos textos en conversaciones, es más fácil entrena al modelo a reconocerlos y detectar las secuencias de Tokens que tienen que ver con ellos.

Figura 6: Modelo de evaluación de cadenas tokenizadas con un LLM

Con estos datos, los investigadores diseñaron el proceso que podéis ver en la Figura 6 continuación donde capturan las cadenas de tokens de las secuencias, y se las entregan al LLM para que pueda decir de qué se está hablando en una determinada conversación.

Figura 7: Ratio de éxito por tipo de conversación

Los resultados son sorprendentes, porque de media, en el 55% de los casos - como se ve en la Figura 7 - el modelo infiere correctamente el tema de conversación que se está teniendo entre el usuario y el modelo LLM, y en el 29% de media - como se ve en la imagen siguiente - de los casos fue posible reconstruir la estructura de conversación entre el modelo y el usuario, lo que permite acceder a mucha información.

Figura 9: Evaluación de rendimiento en evaluación de la estructura de conversación

Este sí que es un ataque que podría añadirse a la lista de problemas de seguridad por las que un servicio o una app que usa un LLM que tú hayas construido se pueda ver afectado, que no está aún en el OWASP TOP 10 de LLM Apps & Services, pero que deberás tenerlo presente.

Figura 10: Hacker & Developer in the Age of GenAI LLM Apps & Services

Esta es una técnica novedosa, que seguro que se puede aplicar no a conversaciones de LLMs con usuarios, sino con muchos otros modelos de comunicación en stream como side-channel, donde un modelo LLM entrenado con estas cadenas tokenizadas podría llegar a ser capaz de inferir parcial o totalmente la información transferida. Una pasada.

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)  

Descifrando las cartas de María Stuart I de Escocia

La tecnología y sus avances no dejan de sorprendernos día a día. Y por una vez, no vamos a hablar exclusivamente de un avance conseguido utilizando Inteligencia Artificial sino que esta vez vamos a hablar de criptografía e Historia. En este caso concreto nos centraremos en la persona de María I de Escocia, ya que se han descubierto más de 50 cartas cifradas dirigidas al embajador francés de la época. 

Figura 1: Descifrando las cartas de María I de Escocia

Imagen: "Recreación de María I de Escocia con un ordenador" por Dall-e

Este ensayo, titulado "Deciphering Mary Stuart's lost letters from 1578-1584" nos muestra el gran impacto sobre nuestro conocimiento histórico y sus personajes que descubrimos cuando combinamos tecnología y conocimiento humano para comprender y descifrar algunos de los documentos dejados para la posteridad. 

Figura 2: Libro de Cifrado de las comunicaciones digitales:
de la cifra clásica a RSA 2ª Edición de 0xWord

Estas se encontraron en la Biblioteca Nacional de Francia y se han descifrado usando técnicas por ordenador y análisis contextual manual, y en este artículo vamos a intentar explicar el proceso seguido para realizar este interesantísimo trabajo y conocer más del sistema de cifrado que utilizaron. Si te gusta la criptografía, el libro de "Cifrado de las comunicaciones digitales: de la cifra clásica a RSA (2ª Edición)" de 0xWord es el que debes comprarte.

María I de Escocia

María I de Escocia, resumiendo “mucho”, accedió al trono muy joven, sólo a los seis días de nacer. Su vida no fue precisamente fácil ya que se vio involucrada en una serie de eventos bastante desafortunados como el asesinato de su esposo, ver a su hijo en la cárcel, abdicar en favor de él, etcétera. Pero quizás el evento que más le afectó, y con razón, fue su encarcelamiento durante 19 años en Inglaterra por conspirar contra la reina Isabel I (muchos católicos como María I de Escocia pensaban que Isabel I no era legítima heredera ya que su padre Enrique VIII había roto completamente con la Iglesia Católica).

Figura 3: Retrato de María I de Escocia

Durante este periodo de encarcelamiento, mantuvo contacto con diferentes personas en Francia e Inglaterra. El problema es que durante este periodo también fue objeto de varias conspiraciones que finalmente acabaron con su vida, en 1587. Esta complicada relación con la monarquía inglesa, los poderes católicos, sus contactos en Francia, etcétera, está reflejada en toda su correspondencia y estas cartas son muy importantes para comprender estas relaciones y los motivos reales detrás de su ejecución final. Por ello descifrar las cartas (María I de Escocia enviaba su correspondencia importante cifrada) son clave para entender toda la historia detrás de este gran personaje histórico.

Descifrando las cartas

Esta investigación se centra en descifrar precisamente la serie de cartas recientemente encontradas enviadas al Embajador de Francia, Michel de Castelnau. Estas cartas están totalmente cifradas, sin ningún elemento que ofrezca datos como la fecha, la persona que la escribe, el destinatario, etcétera. 

Figura 4: "Deciphering Mary Stuart's lost letters from 1578-1584"

El primer paso descifrarlas ha sido transcribir los documentos que sólo contienen gráficos a un formato legible para programas de ordenador. No era tarea fácil ya que hablamos de 150.000 símbolos en total y, además, no se podía usar OCR. Por lo tanto, desarrollaron una aplicación específica para el proyecto llamada CrypTool2.

Figura 5: Software CryptTool2 creado específicamente para sustuir

los símbolos gráficos por otros legibles para el ordenador.

Una vez digitalizados estos símbolos y convertidos a caracteres legible por una máquina, se aplicó un análisis y descifrado por ordenador utilizando esa herramienta. Este primer paso permitió descubrir o identificar el idioma original de los textos (en este caso francés pero podría haber sido inglés o italiano) y recuperar diferentes fragmentos de éste.

Se identificaron elementos homófonos, símbolos utilizados para nombres, lugares o los meses del año. También se encontraron patrones recurrentes (algo importante en el proceso de cualquier descifrado) e incluso errores en estos patrones por fallos humanos durante la utilización de las tablas de cifrado y descifrado.

Figura 6: Ejemplo de descifrado después de identificar a los homófonos

Durante siglos, el principio básico de los cifrados permaneció igual: cada letra del alfabeto se sustituía por un símbolo, es decir, un cifrado por sustitución. Pero desde el siglo X, los árabes desarrollaron métodos efectivos para romper códigos basados en el análisis de frecuencia. Más adelante, para evitar la ruptura de códigos basada en el análisis de frecuencia, se introdujeron cifrados homofónicos, en los que, para las letras más comunes, se ofrecía una elección de varios símbolos (también conocidos como homófonos como se ha mencionado anteriormente) para cifrar esa letra. 

Los homófonos hacían que el cifrado fuera más difícil de romper y se incluía una nomenclatura que consistía en una lista de símbolos para palabras, nombres o sílabas frecuentemente usados. Los investigadores de este ensayo tenían claro que el cifrado era homofónico pero el problema principal estaba en que no conocían el idioma del texto original y además encontraron algunas características que hacían que el cifrado en estas nuevas cartas fuera un tanto especial.

El cifrado María-Castelnau

Los Archivos Nacionales Británicos tienen muchas claves de cifrados utilizados por María I de Escocia y sus colegas. Estas claves fueron capturadas o reconstruidas a partir de mensajes interceptados. De hecho, el famoso cifrado de Babington (la conspiración que llevó a la muerte por ejecución de María I de Escocia) era del tipo monoalfabético con una pequeña nomenclatura propia.

Pero, por otro lado, la mayoría de los otros cifrados encontrados en esos archivos eran homofónicos con una nomenclatura centrada en nombres, lugares y palabras comunes del francés o el inglés. Además, se usaban símbolos gráficos y marcas que se colocan debajo o arriba de la letra para modificar su sonido o incluso darle una pronunciación específica (esto se denominan símbolos diacríticos).

Figura 7: Parte del cifrado María-Castelnau

Pero lo curioso es que el cifrado reconstruido con estas nuevas cartas no aparece en ninguna de las otras cartas mencionadas anteriormente (aunque si comparten características fundamentales como la homofonía). De hecho, en este nuevo cifrado empleado en estas cartas aparecen símbolos como caracteres que representan el valor nulo o “especiales” que sirven para indicar una repetición o incluso la eliminación de un símbolo concreto (el último, por ejemplo). 

Esto es especialmente interesante porque estamos hablando de símbolos que modifican el texto escrito, es decir son caracteres especiales que realizan una función específica sobre el texto (al más puro estilo de la Máquina de Turing con comandos que hacen avanzar o retroceder en la cinta). No está claro si este método alternativo de cifrado fue inventado por María I de Escocia o por algunos de sus colegas.

¿De qué se hablaba en estas nuevas cartas?

Uno de los temas principales que encontramos en estas nuevas cartas cifradas es el esfuerzo continuo de María Stuart I de Escocia en crear canales seguros con Castelnau, para poder contactar con sus aliados en Francia. Las cartas también mencionan la posible boda entre el Duque de Anjou y la Reina Isabel, mientras que María I de Escocia defiende el matrimonio, también le advierte a Castelnau sobre sus dudas de la sinceridad por parte inglesa y sus planes para debilitar a Francia. 

Figura 8: Ejemplo de una de las cartas originales con el texto cifrado.

Además, María I de Escocia muestra una gran animadversión hacia el Conde de Leicester y otros miembros de la facción puritana, a quienes acusa de fomentar conspiraciones en su contra. Por otro lado, las cartas también hablan de las negociaciones para la liberación de María I de Escocia y su restablecimiento en el trono escocés (y sus quejas sobre sus condiciones de cautiverio). En el documento original de esta investigación se encuentra un resumen completo de todas y cada una de las cartas descifradas.

¿Y cómo eran esos canales de comunicación confidenciales o seguros?

Además de estos canales seguros, otro punto importante era también la distracción, ya que en paralelo a estos canales cifrados había una comunicación normal bajo la supervisión de Sir Francis Walsingham (el “maestro de espías” y némesis de María I de Escocia). Uno de los mensajeros más destacados era por ejemplo Claude de Courcelles, pero este no fue el único y además había continuos intentos de reclutar a nuevos mensajeros.  En las cartas también se menciona la posible infiltración de mensajeros pagados por Walsingham para poder interceptar las cartas y revelar a los componentes de la cadena de comunicación.

Figura 9: Sir Francis Walsingham

Un punto importante que se menciona en las cartas y que afecta al funcionamiento de estos canales de comunicación es el cambio de embajador francés por Châteauneuf (en vez de Castelnau). Esto llevo a que María I de Escocia ya no se comunicara más por canales oficiales, sino que solamente utilizaría los confidenciales aumentando las sospechas de la existencia de estos y que finalmente fueron descubiertos e interceptados.

Conclusiones

Esta investigación de las cartas descubiertas ha permitido obtener un mejor conocimiento sobre la vida de María I de Escocia sobre su periodo de cautiverio. Pero además estas revelaciones también influyen sobre la historia en general que ocurrió alrededor de su imagen y el efecto en otros acontecimientos posteriores. Y esto es sólo una primera aproximación, la gran cantidad de información revelada es enorme y requerirá de más tiempo de análisis y comparación con el resto de otra correspondencia para encontrar nuevas evidencias o datos que aporten más información a este personaje histórico y todo lo que le rodeaba.

Figura 10: Libro de "Microhistorias: anécdotas y curiosiades de la historia
de la informática (y los hackers)" de Fran Ramírez y Rafel Troncoso 0xWord.

Este ensayo es un ejemplo más de la importancia de la tecnología hoy en día pero también destacar la gran contribución del análisis humano detrás de esta investigación, hoy que prácticamente todo se hace ya con Inteligencia Artificial. Y si te gustan estas historias del impacto tecnológico y su evolución histórica (además de historias de hackers) recuerda que tenemos este libro que escribimos con mucho cariño mi colega Rafael Troncoso y yo llamado “Microshistorias: anécdotas y curiosidades de la Informática”, de 0xWord. 

Happy Hacking Hackers!!! 

Autor: Fran Ramírez, es investigador de seguridad y miembro del equipo de Ideas Locas en CDO en Telefónica, co-autor del libro "Microhistorias: Anécdotas y Curiosidades de la historia de la informática (y los hackers)", del libro "Docker: SecDevOps", también de "Machine Learning aplicado a la Ciberseguridad” además del blog CyberHades. Puedes contactar con Fran Ramirez en MyPublicInbox.

 Contactar con Fran Ramírez en MyPublicInbox

Factorización de RSA con un Optimizador de Quantum Computing (y Classic Computing)

Desde hace años llevamos hablando del riesgo para los algoritmos de cifrado de la aparición de los ordenadores cuánticos. Sabemos que cuando lleguen los ordenadores cuánticos profesionales, la factorización de números enteros que es soporte fundamental de RSA, será trivial. Y esto nos dejará sin uno de los soportes fundamentales de la criptografía moderna, ya que en él se sustenta el cifrado de las comunicaciones modernas.

Figura 1: Factorización de RSA con un Optimizador

de Quantum Computing (y Classic Computing)

Imagen: Dall-e 2 (happy hacker in futurist art style)

Pero hace años que se está estudiando e investigando cómo sería posible romper RSA, por supuesto. Es uno de los grandes objetivos de los investigadores en criptografía, y cualquier avance que abra nuevas puertas, nuevos caminos, nuevas formas de atacar la robustez de RSA, son siempre exploradas y analizadas en detalle. Si no estás familiarizado con RSA, te recomiendo que te compres, leas y subrayes este libro.

Figura 2: Libro de Cifrado de las comunicaciones digitales:
de la cifra clásica a RSA 2ª Edición de 0xWord

Desde el año 2001 existe el RSA Factoring Challenge, donde se premia a los que consiguen hitos relevantes en su ruptura, pero al mismo tiempo, donde los investigadores buscan dejar su nombre escrito, pues es un reconocimiento mundial. Si vemos la tabla en Wikipedia, podemos ver que el reto comienza en RSA100, que ya fue roto en el año 1991.

Figura 3: RSA Factoring Challenge (RSA100 a RSA220)

Si vamos a la segunda parte de la tabla, ya vemos que el último hito lo tenemos en romper RSA250, conseguido en el año 2020. Algo que, a pesar de ser un avance en la investigación y en la técnica, deja todavía muy lejos a RSA2048 que es el más utilizado hoy en día.

Figura 4: RSA Factoring Challenge RSA2048

Lo que sí es cierto es que ya se conocen algoritmos para romper RSA cuando existan los equipos cuánticos del tamaño necesario para ejecutarlos, como es el caso del propuesto por Peter Shor, que permite factorizar los números enteros en tiempo asintótico de O((logN)^3) y espacial de O(logN). Este algoritmo no es nuevo y, como explica la Wikipedia, en el año 2001 se puedo aplicar en un ordenador cuántico de 7 Qbits para descomponer 15 en 3 y 5.

Figura 5: Algoritmo de Shor en Wikipedia en Español

Hoy en día, los investigadores están buscando encontrar nuevas formas de atacar el problema de romper RSA desde varios puntos diferentes, que ayuden a reducir la complejidad desde diferentes puntos de vista.  El primero de ellos, intentando encontrar algoritmos que factoricen números enteros grandes de forma más eficiente. Exprimiendo para ello la matemática. Como explican en Segu-Info, en el año 2021, el matemático alemán Claus-Peter Schnorr publicó el artículo académico de "Fast Factoring Integers by SVN Algorithms", que propone un método más eficiente para intentar que las computadoras clásicas pudieran romper RSA, pero no escala tanto como para ser una amenaza real para RSA2048. 

Figura 6: Artículo de Fast Factoring Integers by SVN Algorithms

Por otro lado, es cierto que las Computadoras Cuánticas - no orientadas a este problema, sino generalistas - avanzan cada vez más deprisa y, en cuanto estas lleguen, podrán implementar el algoritmo de citado anteriormente de Peter Shor, lo que obliga a trabajar y pensar en los algoritmos de Post-Quantum Encryption y a tener una estrategia de reemplazo en todos los rincones. Como ya vimos, el gobierno de Estados Unidos ya ha comenzado con su camino en esta dirección, bajo la publicación de la Quantum Computing Cybersecurity Preparedness Act. 

Figura 7: Quantum Computing Cybersecurity Preparedness Act

Y es que, cada día vemos equipos cuánticos de más potencia y calidad. A finales del año 2022, la empresa IBM anunció que su ordenador cuántico OSPrey de 433 Qbits, pero sobre todo que planea tener en el año 2025 a Kookaburra, con un objetivo de más de 4158 Qbits, lo que cambiará, seguro, las reglas del juego con los algoritmos que se van a poder ejecutar.

Figura 8: IBM lanza OSPrey con 433 Qbits y planea tener

Kookaburra con más de 4158 Qbits en 2025

Por supuesto, habrá que ver en lo que están trabajando Google y Microsoft en estas áreas de investigación, donde también tienen puestos muchos recursos en la competición cuántica que estamos viendo desde hace unos años.

Factorización de RSA con Quantum Computing y Classic Computing

A todos estos avances, el pasado 23 de Diciembre de 2022 se presentó un artículo académico en China, titulado "Factoring integers with sublinear resources on a superconducting quantum processor", donde un equipo de investigación amplio explicaba cómo habían utilizado una aproximación mixta para resolver el problema de escala que tenía el algoritmo de "Fast Factoring Integers by SVN Algorithms", utilizando para las partes que no escalaban un ordenador cuántico. 

Figura 9: Optimizaciones de Shor basadas en optimizador cuántico

Para su prueba de concepto, utilizaron la factorización de enteros en RSA48 utilizando un ordenador de 10 Qbits. En este caso utilizan, computación clásica para la mayor parte del algoritmo, pero añade un optimizador cuántico "QAOA" que sirve para resolver las partes no escalables del algoritmo de Schnorr  para optimizar el algoritmo de Shor, que no garantizaban un rendimiento asintótico sublinear, y elevaba la complejidad al tiempo que reducía la potencia de la solución.

Figura 10: Se utiliza computación clásica para implementar Shor y se optimiza con un optimizador cuántico. Esta aproximación aumenta la eficacia de Shor con los equipos cuánticos actuales reduciendo el número de Qbits necesarios.

Con esta aproximación, el equipo de investigación ha hecho también un estudio de cuál sería el tamaño del equipo cuántico que se necesitaría para llegar a romper RSA2048 con esta aproximación mixta, lo que ha generado mucha controversia en la comunidad investigadora, a la par que mucho miedo geopolítico entre los encargados de los sistemas de cifrado de las grandes empresas y estados.

Figura 11: IBM ya podría romper RSA-2048 con su OSPrey

Claro, si sumas las últimas noticias, pues parece que IBM ya podría romper RSA-2048 con su equipo OSPrey, y parece que los equipos de más de 372 Qbits, están más cerca de lo que parece. Pero aún hay que ver cómo evoluciona esto. Lo cierto es que, viendo la velocidad a la que van las noticias, hay que ir pensando en poner estrategias de Post-Quantum Encryption en los estados y gobiernos cuanto antes, porque puede ser que no en mucho tiempo, esto ya sea posible de una manera más o menos común.

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)  

Quantum Computing Cybersecurity Preparedness Act: Comienza la era de Ciberseguridad Post-Quantum en Estados Unidos

El gobierno de Estados Unidos ha decidido aprobar en el congreso la llamada "Quantum Computing Cybersecurity Preparedness Act", que abre el camino de la era de ciberseguridad post-cuántica en la seguridad de la administración de EEUU. Ha sido firmada por el presidente Biden, y en ella se establecen los primeros pasos a tomar para preparar los sistemas criptográficos para la llegada en algún momento en el tiempo, de los ordenadores cuánticos.

Figura 1: Quantum Computing Cybersecurity Preparedness Act

Comienza la era de Ciberseguridad Post-Quantum en Estados Unidos

Mucho se ha hablado de los problemas de ciberseguridad que existirán cuando los ordenadores cuánticos sean una realidad práctica en nuestras vidas, ya que las "complejas" operaciones matemáticas que hoy en día garantizan la confidencialidad de los datos que hoy se cifran con nuestros algoritmos criptográficos, ya no servirán con la existencia de equipos informáticos cuánticos, lo que dejará al descubierto todos los datos que hoy protegemos. Grandes investigadores, como son el Dr. Ignacio Cirac o el Dr. Luciano Bello, que dedican su trabajo al campo de la computación cuántica, llevan años en sus ponencias hablando del impacto que en el mundo de la ciberseguridad.

Figura 2: Quantum Computing Cybersecurity Preparedness Act

En el libro de "El cifrado de las comunicaciones digitales: De la cifra clásica a RSA (2ª Edición)", tienes la base de toda la criptografía clásica y moderna de nuestros sistemas, y con la llegada en el futuro, que sea en la década del 2030, todas esas protecciones caerán, y podríamos tener muchas consecuencias no deseadas. Datos cifrados capturados en transmisiones, copias de archivos con claves olvidadas, volúmenes de almacenamiento con datos confidenciales protegidos, etcétera, se abrirán para todos.

Figura 3: Libro de Cifrado de las comunicaciones digitales:
de la cifra clásica a RSA 2ª Edición de 0xWord

Hace ya años, en el artículo de Quantum Cryptography, os contaba cómo en Telefónica habíamos utilizado tecnología cuántica para hacer el cifrado de datos, que es otra aproximación válida, ya que se basa en proteger las claves de cifrado compartiéndolas con tecnología cuántica. Una aproximación válida hoy en día, pero que no funcionaría en el futuro si el algoritmo de cifrado no fuera PQE, ya que permitiría al atacante acceder a la información incluso sin clave.

Figura 4: PoC de cifrado cuántico de Telefónica, la UPM y Huawei

Con el objetivo de preparase, se lleva años trabajando en los algoritmos PQE (Post-Quantum Encryption), que utilizan diferentes aproximaciones para evitar el uso de las funciones matemáticas que hoy son útiles, pero con la llegada de los ordenadores cuánticos dejarán de serlo. Y es por ello que se lleva trabajando en la elección de algoritmos criptográficos PQE desde el hace años para que, con tiempo, preparamos la seguridad de la información de nuestros datos, y fueron anunciados en Julio de este año.

Algoritmos de cifrado post-cuántico elegidos por el NIST

Para ello el NIST ha estado trabajando en el programa de Post-Quantum Cryptography Standarization en la elección de cuáles deberían de ser esos algoritmos PQE, que al final fueron cuatro los elegidos. Para el cifrado general, se eligió a Crystals-Kyber como el algoritmo a utilizar para cifrado público.

Figura 5: Algoritmos PQE elegidos por NIST: Cifrado público

Para firma digital, los algoritmos elegidos han sido tres, que son Crystals-Delithium, Falcon y Sphincs+, que están totalmente documentados, y disponibles para que todo el mundo los pueda implementar.

Figura 6: Algoritmos PQE elegidos por NIST: Firma Digital

Ahora, ya que existe una recomendación clara de cuáles son los algoritmos de criptografía post-quantum, lo que ha aprobado el gobierno de EEUU en su Quantum Computing Cybersecurity PreparednessAct es comenzar el proyecto de transformación de todos los algoritmos criptográficos a un modelo PQE, por lo que con el nuevo acto se insta a dos cosas:

Figura 7: Quantum Computing Cybersecurity Preparedness Act

• Establecer cuáles son las guías de transición para migrar a algoritmos PQE para toda la administración.

• En un plazo máximo de 15 meses, se presente la estrategia nacional de ciberseguridad para la era post-quantum. 

Lo que llevará a trabajar en criptografía mirando, y dando por hecho, en breve habremos entrado en una nueva era. No está mal para terminar el año.

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)  

Cómo romper la arquitectura de cifrado de mensajes extremo a extremo de Rocket.Chat [2 de 2]

Tras la primera parte de este artículo de "Cómo romper la arquitectura de cifrado de mensajes extremo a extremo de Rocket.Chat", hoy toca centrarnos en el ataque sobre la arquitectura del ataque al cifrado E2E. El objetivo del ataque sobre la arquitectura E2E de Rocket.Chat, será la de obtener y descifrar los mensajes almacenados en persistencia del lado del servidor.

Figura 12: Cómo romper la arquitectura de cifrado de

mensajes extremo a extremo de Rocket.Chat [2 de 2]

Para lograrlo, si habéis podido revisar la arquitectura que os presenté en la primera parte de este artículo, una captura de red que contenga las cabeceras X-user-id y X-auth-token, propias de un usuario autenticado para cualquier llamada a la API Rest del servidor, serán requisito necesario y suficiente para replicar el ataque. 

Figura 13: Libro de Bug Bounty: De profesión "Cazarrecompensas"

en 0xWord, escrito por Pablo García

No obstante, cualquier administrador de la aplicación con acceso a la base de datos no relacional tiene la capacidad de replicarlo obteniendo los mismos resultados, lo que demuestra que la arquitectura de cifrado no garantiza para nada el cifrado E2E. Espero que os guste y os animéis a probarlo, porque es un buen ejemplo para los amantes de los CTFs, de los Bug Bounties o de los ejercicios de Red Team.

El Bug en la arquitectura E2E de Rocket.Chat

La vulnerabilidad reside en la unión de una llamada al servicio de la API e2e.updateGroupKey con bajo nivel de privilegios en autorización de uso, junto con una funcionalidad desarrollada para continuidad de negocio en la que cualquier usuario, puede solicitar el reseteo de credenciales E2E. Siendo el primer usuario con status “online” que pertenezca al grupo, al que el servidor notificó con una llamada en broadcast el encargado de generar la nueva clave E2EKey para el usuario que la solicitó.

Figura 14: Llamada a la API Rest que se utilizará para la explotación

Dentro de un grupo seguro el objetivo mediante el uso indebido de la llamada a la API, será el de manipular las claves E2EKey de la colección suscripciones del servidor, como se explica en el gráfico siguiente.

Figura 15: Manipular las claves de E2EKey

La funcionalidad de negocio que se utilizará para la explotación, será la de reseteo de credenciales que se representa en el siguiente diagrama.

Figura 16: Esquema del proceso de reseteo de claves.

El vector de ataque será el de replicar las claves E2EKey del grupo seguro objetivo, en un nuevo grupo espejo, mediante el uso de de la función e2e.updateGroupKey por el atacante, el diagrama del ataque será el siguiente.

Figura 17: Esquema del ataque para conseguir la duplicación

El proceso de la explotación completa, se puede ver en el siguiente vídeo, donde se utiliza un conjunto de código para hacer el exploit. La explicación de los códigos es la siguiente:

• dump_data.py: Desarrollado en Python3. Objetivo: extracción de los datos del servidor para el usuario del que se obtuvo la captura de red.

• attack_mode.py: Desarrollado en Python3. Objetivo: actualización de las claves E2EKey por el usuario atacante al usuario objetivo.

• msg_parser.ts: Desarrollado en javascript, ejecutado en node. Objetivo: convertir el formato de los mensajes y obtener tanto el vector de linealización IV como el cipherText de cada mensaje.

• Microservicio criptográfico: Desarrollado en java. Objetivo: Realizar las operaciones criptográficas de cifrado y hashing.
• automation_process.py: Desarrollado en python3. Objetivo: automatización del proceso de descifrado de mensajes, utilizará llamadas a:
• Servidor central de rocketchat
• msg_parser.ts
• Microservicio criptográfico

Figura 18: PoC  del ataque a Rocket.Chat

Si sigues el vídeo, verás que primero se crea un grupo de chat seguro, donde se manda un mensaje. Esta será la "bandera" a conseguir con la PoC. Será la evidencia para demostrar que se ha conseguido ver un mensaje que supuestamente debería estar protegido E2E.

Figura 19: Canal seguro con mensaje a obtener como objetivo de la PoC.

Para ello, como se ha explicado anteriormente, se crea primero un grupo espejo que se utilizará como parte el esquema de ataque.

Figura 20: Generación del grupo espejo en el que replicar las claves.

Ahora, se extraen los datos del usuario objetivo con los scripts en Python explicados anteriormente, para lograr hacer la actualización de las claves E2EDKey.

Figura 21: Extracción de los datos del usuario objetivo

y actualización de claves E2EKey.

Una vez extraídos los datos, ya se puede hacer el reseteo de las credenciales del usuario, para dar acceso al atacante al sistema.

Figura 22: Reseteo de credenciales, para el atacante.

Y con las nuevas credenciales, se pueden ver los datos descifrados que teníamos como objetivo original en el proceso, tal y como se puede ver en el script y en la herramienta de Rocket.Chat.

Figura 23: Validación final de los datos descifrados.

Conclusión final

Este artículo recoge la PoC de una demostración que haré en la próxima LIBRECON en Bilbao, los días 15 y 16 de Noviembre, donde estaré dando una charla. Puedes conseguir tu entrada en MyPublicInbox con Tempos en la sección de Convierte tus Tempos. Además, se ha solicitado un CVE para este bug con el CVE ID Request 1348331 y la investigación se ha reportado vía Hacker1 y tienes en la siguiente URL la información:

• https://hackerone.com/bugs?report_id=1757663

Esperemos que pronto se añadan medidas de seguridad para evitar estos esquemas de ataque y dar más protección a la plataforma Rocket.Chat. Espero que os haya gustado la explicación y que os anime a hacer más investigaciones propias.

Saludo,

Autor: Ildefonso González Sánchez, pentester.

Contactar con Ildefonso González Sánchez