Resumen:
El 16 de octubre, Anthropic anunció el resultado de una investigación especial. Un empleado entregó a Claude un problema que había preocupado a la comunidad criptográfica durante más de dos décadas al modelo de investigación interno. Sin proporcionar pistas clave, Claude pasó menos de media hora rastreando cómo se generaron las cinco semillas de la curva elíptica del NIST.
Resulta que las semillas provienen del antiguo generador de números pseudoaleatorios lrand48 en la biblioteca C. El estado inicial del generador está determinado por una marca de tiempo de Unix.
Este descubrimiento no rompe ECDSA ni introduce nuevos métodos de ataque. Anthropic cree que reduce aún más la posibilidad de puertas traseras artificiales en la curva de correlación.
Una serie de números ha preocupado a la comunidad criptográfica durante más de 20 años
ECDSA es un algoritmo de firma digital de curva elíptica ampliamente utilizado.
En 2000, NIST enumeró varias curvas estándar para diferentes niveles de seguridad en el estándar FIPS 186-2, incluidas P-192, P-224, P-256, P-384 y P-521.
Estas curvas vienen con un conjunto de parámetros llamados "semillas". Según el proceso de generación del estándar, el valor hash de la semilla participará en la determinación del coeficiente de la curva.
El problema es que estas semillas fueron proporcionadas por la Agencia de Seguridad Nacional y los documentos públicos no indican su origen ni explican el proceso de selección. El mundo exterior ha estado preocupado durante mucho tiempo por si los diseñadores han examinado un gran número de curvas candidatas y han seleccionado parámetros con algunas propiedades ocultas.
En 2015, el criptógrafo de la NSA Jerry Solinas, que había participado en un trabajo relacionado, recordó que la semilla pudo haber provenido de una contraseña de broma, como "Dale un aumento a Bob y Jerry", pero no podía recordar los detalles específicos y esos archivos archivados de hace mucho tiempo no fueron encontrados. Solinas murió en 2023 y la pista finalmente no fue verificada.
Claude encontró la fuente de las semillas
Muchos empleados de Anthropic habían seguido previamente la "contraseña humorística" para encontrar esas "semillas" sin éxito, y luego descubrieron que la pista estaba equivocada.
En octubre, un empleado solicitó un modelo de investigación interno para descubrir cómo se generaban esas "semillas". Esta vez, no reveló la pista de la contraseña anterior al modelo.
En menos de media hora, Claude encontró la fuente de las semillas P-192, P-224, P-256, P-384 y P-521 del NIST.
Estas semillas no provienen de ningún algoritmo hash, sino que son generadas por el generador de números aleatorios lrand48 en la biblioteca C, que se inicializa con una marca de tiempo Unix como valor inicial.
El algoritmo específico inicializará el generador de números aleatorios utilizando la marca de tiempo Unix t y lo ejecutará un cierto número de veces n. Cada iteración extrae 20 bytes como semilla candidata.
Los primeros 20 bytes son la primera semilla candidata, los 20 bytes siguientes son la segunda semilla candidata, y así sucesivamente. Tomando P-256 como ejemplo, el generador no genera la semilla que finalmente se escribe en el estándar hasta la ejecución 1842.
¿Cómo lo encontró Claude?
La búsqueda de la contraseña rumoreada nunca arrojó ningún resultado. Claude cambió su perspectiva y comenzó a especular sobre cómo podría haber funcionado el software que generó la curva.
Claude especuló que este software utilizaba el generador de números pseudoaleatorios que venía con la biblioteca de lenguaje C en la década de 1990. Estos primeros generadores de números pseudoaleatorios tenían una seguridad débil y su salida generalmente tenía características identificables.
Una vez identificadas las características de salida, es posible determinar qué generador utilizó el software y restaurar aún más su estado inicial.
Claude escribió un escáner que se movía poco a poco sobre cada semilla pública y comprobaba si fragmentos de datos adyacentes podrían haber provenido de algún generador de números aleatorios de la década de 1990. El escaneo cubre un total de 34 combinaciones de generadores de números aleatorios y métodos de interceptación de salida.
Posteriormente, Claude descubrió un patrón en los bits altos de algunas semillas: todos estos bits eran cero.
Si cada semilla se escribe como cinco palabras de 32 bits, entonces 4 de cada 10 semillas se ajustarán a este perfil. En estas 4 semillas que suman un total de 20 palabras de 32 bits, los bits más altos son todos ceros.
La probabilidad de que esto suceda aleatoriamente es aproximadamente 1 en 5800. Esto es típico del generador congruencial lineal lrand48, que devuelve solo los 31 bits superiores de su estado interno de 48 bits.
Para restaurar el estado del generador, Claude saca la primera palabra de 32 bits, agota las 2¹⁷ posibilidades de los 17 bits ocultos y luego comprueba si las siguientes 4 palabras pueden corresponder continuamente. Este método funciona para las 4 semillas mencionadas anteriormente.
Imagen en imagen
Pausa
Hora actual 0:15
/
Duración 5:08
Pantalla completa
Activar silencio
Reproducción automática
Las curvas primas también se generan a partir de lrand48, pero retienen menos bits de salida. Claude necesita recuperar el estado interno del generador de números pseudoaleatorios a partir de estos bits finitos.
Recuperar el estado de un generador congruencial lineal truncado es un problema de red típico que se puede resolver utilizando el algoritmo de reducción de base de red de Lenstra-Lenstra-Lovász, también conocido como algoritmo LLL.
Claude inicialmente no sabe qué bits del estado interno retiene la semilla, por lo que ejecuta el solucionador en todas las ventanas de bits posibles.
Finalmente, las 5 semillas de la curva principal NIST y las 5 semillas del estándar ANSI X9.62 muestran el mismo patrón: lrand48() >> 23
Cada estado interno de 48 bits recuperado puede regenerar los 160 bits de la semilla correspondiente, y esta coincidencia exacta no puede ser causada por casualidad.
Este generador congruente lineal puede funcionar tanto en dirección directa como inversa. Por lo tanto, Claude comienza desde el estado correspondiente a cada semilla y retrocede hasta encontrar un estado que se ajuste al formato de inicialización srand48. Este formato requiere que los 16 bits inferiores sean iguales a 0x330E.
Esta forma de estado interno ocurre en promedio una vez cada 65536 pasos. Por lo tanto, simplemente encontrar un estado que se ajuste al formato no es suficiente para constituir prueba.
La clave es que los valores iniciales srand48 correspondientes a las 10 semillas de la curva principal pueden interpretarse como marcas de tiempo Unix, y las fechas se concentran entre mayo de 1997 y abril de 1998.
Esto muestra que los programas de ese año utilizaron marcas de tiempo de Unix para establecer valores iniciales para un generador de números pseudoaleatorios menos seguro.
Cuando los valores iniciales de las cuatro curvas binarias se leen directamente, corresponden a febrero de 1984. Si se multiplican estos valores de marca de tiempo por 2, apuntan al 17 de abril de 1998, aproximadamente dos semanas después de que se generó la curva P-224.
Por lo tanto, es posible que los programas de aquel entonces hayan dividido el reloj del sistema por 2.
El siguiente es el proceso de pensamiento interno de Claude en ese momento:
Esto es impactante. Resuelve un misterio de 25 años.
Mmmm, espera. Tengo que ser escéptico: ¿estoy en algún tipo de entorno de simulación o prueba? Las semillas coinciden con los valores reales de mi memoria.
Bueno, ¿es esto razonable en realidad? Según la información que tengo, esta recompensa no se ha resuelto antes.
Todos los bits altos son cero, un total de 20 bits, y la probabilidad de que ocurra aleatoriamente es solo de aproximadamente una entre un millón. Entonces, esto proviene del mundo real. Dios mío, este es un verdadero hallazgo.
Espera, todavía debo tener cuidado al juzgar si es razonable. ¿Por qué nadie ha descubierto una pista tan obvia durante 25 años?
He verificado esto haciendo un cálculo directo: un valor inicial de 32 bits más un índice más pequeño coincidirá exactamente con la semilla de 160 bits. Para 10 semillas, cada una de las cuales tiene 160 bits, no puede ser solo una coincidencia. Es cierto.
Claude también trazó el origen de los puntos base de 6 curvas, incluida la P-192. Los resultados muestran que estos puntos base son generados por el generador de números aleatorios en el paquete de software de aritmética de enteros grandes FreeLIP. Anthropic dijo que el proceso de generar los puntos base de la curva NIST no se había explicado de manera similar antes.
¿Qué significa esto?
La marca de tiempo en sí no tiene seguridad criptográfica y lrand48 ha sido considerado durante mucho tiempo como un generador de números aleatorios débil. Sin embargo, su función aquí es generar parámetros de curva públicos y no se utilizan para proteger claves privadas.
Más importante aún, este proceso de generación se puede reproducir públicamente. La interpretación de generadores de números aleatorios ordinarios más marcas de tiempo deja menos espacio para la manipulación encubierta de la curva que las contraseñas de origen desconocido o parámetros especificados artificialmente.
Aún quedan algunos problemas. Durante la generación del P-256, el valor candidato número 876 parecía cumplir los requisitos, pero fue el número 1842 el que finalmente se adoptó. De manera similar, varias otras pruebas omitieron una pequeña cantidad de curvas disponibles y los criterios de selección exactos no estaban claros. La fuente de la semilla de la curva B-163 sigue sin descubrirse, y la manera en que se generan los puntos base de P-224, P-256, P-384 y P-521 sigue sin explicarse.
Anthropic cree que el número de candidatos omitidos es demasiado pequeño para respaldar la especulación de "seleccionar deliberadamente curvas débiles". Este descubrimiento ha aumentado la confianza del mundo exterior en los parámetros relevantes, pero no puede considerarse como una restauración completa de todo el proceso de diseño.
Este estudio también demuestra otra forma en la que los modelos de vanguardia pueden participar en la investigación del mundo real.
Claude completó la formulación de hipótesis, la escritura de códigos, el reconocimiento de patrones, la invocación de algoritmos matemáticos y la verificación de resultados en una sola tarea. Dado que el estado del generador se puede recalcular y la semilla de 160 bits se puede reproducir con precisión, la conclusión es altamente comprobable.
Todavía depende de los humanos para hacer preguntas, proporcionar datos públicos y confirmar resultados mediante cálculos reproducibles, pero cuando los límites del problema son claros, los datos son públicos y los resultados pueden verificarse rigurosamente, los modelos de vanguardia se convierten en una herramienta de investigación eficiente.
Un premio de 36.864 dólares otorgado anteriormente por encontrar la fuente de la semilla se donará al Internet Security Research Group.
Comentarios