Recompensa por las seeds de las curvas elípticas NIST

 (words.filippo.io)
1 puntos por GN⁺ 2023-10-06 | 1 comentarios | Compartir por WhatsApp
  • Las 5 curvas elípticas NIST ampliamente usadas en la criptografía moderna derivan sus seeds de valores proporcionados por la NSA en los años 90, y hay una recompensa de $12,288 por encontrar el texto original
  • El objetivo son P-192, P-224, P-256, P-384 y P-521 de FIPS 186-2, y si la persona ganadora elige donar el pago a una organización benéfica estadounidense 501(c)(3), el monto se triplica a $36,864
  • Se cree que las seeds fueron creadas por Jerry Solinas en 1997, posiblemente hasheando una frase en inglés con SHA-1, pero la redacción exacta se perdió tras reemplazos o actualizaciones de equipo
  • El formato de la frase es incierto, incluyendo punto final, saltos de línea, posición y formato del contador, e incluso si incluía o no el nombre de la curva, así que una lista de unos 12k hashes se propone como primer objetivo de ataque
  • Quien envíe primero al menos un pre-seed recibe $6,144, y quien envíe primero los cinco completos recibe los $6,144 restantes; el orden de envío se decide por el encabezado Received del servidor de correo

Objetivo de la recompensa y monto del pago

  • El objetivo de la recompensa pública es encontrar el valor de entrada del hash (pre-seed) que generó las seeds de las 5 curvas elípticas NIST
  • La recompensa total es de $12,288, es decir, 12 Ki$
    • Si la persona ganadora elige una donación a una organización benéfica 501(c)(3) de EE. UU. en lugar de efectivo, el total aumenta a $36,864
  • Los hashes objetivo son estos 5
    • 3045AE6FC8422F64ED579528D38120EAE12196D5
    • BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
    • C49D360886E704936A6678E1139D26B7819F7E90
    • A335926AA319A27A1D00896A6773A4827ACDAC73
    • D09E8800291CB85396CC6717393284AAA0DA64BA

Por qué las seeds de las curvas NIST despertaron sospechas

  • Las curvas NIST P-192, P-224, P-256, P-384 y P-521 se publicaron en FIPS 186-2 en 2000 y, siguiendo el método ANSI X9.62, derivan parte de sus parámetros a partir de la salida de aplicar SHA-1 a una seed aleatoria
  • Muchos sistemas criptográficos usan curvas NIST, en especial P-256 y P-384
    • Ambas curvas están incluidas en la Commercial National Security Algorithm Suite
    • También se usan en certificados ECDSA X.509 que protegen gran parte de la web
  • Steve Weis en NIST curve seed origins resume lo que se sabe sobre las seeds aleatorias incluidas en la especificación FIPS 186
    • Parece que las seeds fueron proporcionadas por la NSA
    • Se cree que Jerry Solinas las generó en 1997
    • Es posible que se hayan creado hasheando una frase en inglés con SHA-1
  • Jerry Solinas llegó a mencionar como ejemplo una seed tipo SHA1("Jerry deserves a raise."), pero la frase real se perdió y frases parecidas no coincidieron con los hashes

Cómo encontrar el pre-seed podría reducir la desconfianza

  • En evaluaciones recientes, las curvas NIST han mostrado aspectos más favorables
    • Las complete addition formulas mitigan un footgun importante
    • Hoy se conocen mejores formas de diseñar interfaces más seguras
    • También está más claro el valor de las curvas de orden primo inmunes a ataques de cofactor
  • Entre algunas personas fuera de la práctica profesional persiste la preocupación de que la NSA pudiera haber elegido deliberadamente las seeds para seleccionar curvas débiles
  • A riddle wrapped in an enigma de Koblitz y Menezes sostiene que, incluso si la NSA hubiera controlado totalmente las seeds, ese tipo de ataque resulta poco convincente
    • Porque requeriría una clase de curvas débiles lo bastante amplia como para no haber sido detectada por la academia o la industria en 25 años
  • Aunque estas preocupaciones no parecen estar especialmente bien fundamentadas, encontrar el pre-seed podría ayudar a reducir el FUD alrededor de las curvas NIST
  • Encontrar la preimagen en inglés no garantiza por completo la rigidity, pero sí llenaría una pieza faltante en la historia de la criptografía

Pistas conocidas sobre el valor de entrada del hash

  • Es muy probable que el valor de entrada sea una frase en inglés que mencione a Jerry Solinas; también podría incluir el nombre de otra persona y un contador
  • Es probable que haya hecho falta un contador porque, según el tamaño en bits de la curva, solo alrededor de 1 de cada 192 a 521 hashes sirve para generar una curva
    • Para la curva más grande, la probabilidad de que el contador sea menor que 2400 es del 99%
    • Para P-256, hay probabilidad de que el contador sea menor que 1175
  • Las seeds de P-192 y P-256 aparecían como ejemplos en una versión anterior del estándar ANSI X9.62, mientras que las demás aparecieron por primera vez en FIPS 186-2, así que la estructura de la frase podría variar
  • La recompensa solo cubre las 5 curvas NIST de orden primo, pero si el costo de prueba es bajo también se pueden intentar otros ejemplos de ANSI X9.62 y las seeds de curvas binarias de FIPS 186-2
    • ANSI prime192v2, prime192v3, prime239v1, prime239v2, prime239v3 no forman parte de la recompensa
    • NIST B-163, B-233, B-283, B-409, B-571 tampoco forman parte de la recompensa

Posibles formatos de cadena y lista de ataque

  • El formato exacto de la cadena sigue siendo un misterio
    • La frase podría terminar con punto o no
    • Podría tener o no saltos de línea
    • El contador podría estar en decimal, con leading zero, o en binario de 16 o 32 bits
    • El contador podría ir después del punto o unirse usando otro separador
    • Podrían haberse generado todas las seeds añadiendo distintos contadores a una misma frase, o haberse usado una frase diferente para cada seed
    • El nombre o tamaño de la curva podría haber estado incluido en la frase
  • Como la memoria humana falla mucho, existe la posibilidad de que algunos detalles del testimonio indirecto sean incorrectos
  • También es posible que, en lugar de un contador, se haya usado hashing repetido como SHA-1(s) o SHA-1(SHA-1(s))
  • Otro candidato es empezar con SHA-1(s) e ir incrementando el valor hash como en ANSI X9.62 Section A.3.3.1
  • Como lista de objetivos de ataque, se ofrece nist-and-ansi-prime-order-seeds-increments-99-percent.txt con unos 12k hashes
    • La lista cubre, para cada seed de curvas de orden primo de FIPS 186-2 y ANSI X9.62, el 99% del espacio de probabilidad
    • Si el costo de verificar muchos hashes es bajo, se recomienda atacar esa lista
    • Si es posible, comparar solo los primeros 16 bytes del hash también debería dar el mismo resultado
  • SHA-1 se presta a fuerza bruta muy rápida, así que es un problema adecuado para gente con experiencia en cracking de passphrases y fuerza bruta de brainwallets

Forma de envío y condiciones de pago

  • La recompensa se paga a la primera persona que envíe por correo a seeds@filippo.io los pre-seeds de las 5 curvas NIST de orden primo
  • La estructura de pago tiene dos etapas
    • Quien envíe primero al menos 1 pre-seed recibe la mitad: $6,144
    • Quien envíe primero los 5 pre-seeds completos recibe los $6,144 restantes
    • Una misma persona puede recibir ambos pagos, así que no hace falta esperar a encontrar los cinco
  • Se puede elegir entre cobrar en efectivo o donar a una organización benéfica 501(c)(3) de EE. UU.
    • Si se elige donar, el monto se triplica
    • Puede rechazarse una organización benéfica cuya orientación choque de forma drástica con los valores del organizador
    • Si la persona es estadounidense o de nacionalidad italiana y no puede recibir legalmente la transferencia, debe elegir la opción de donación
    • Los impuestos sobre la recompensa en efectivo son responsabilidad de quien la reciba
  • El asunto del correo debe incluir ANTISPAM para pasar las reglas de allowlisting
  • El orden de llegada se decidirá finalmente según el encabezado Received del servidor de correo
  • La recompensa vence si las seeds pasan a ser conocimiento público; de lo contrario, sigue vigente hasta que se anuncie lo contrario en esta página
    • Si la recompensa se cancela o reduce, se avisará con 6 meses de anticipación
  • No hay restricciones sobre el método para encontrar las seeds
    • Se permite fuerza bruta, conjeturas ingeniosas, investigación, recuperación de respaldos antiguos de NIST, o cualquier otro método
    • También se promete no preguntar por el método si la persona no quiere revelarlo

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-10-06
Opiniones en Hacker News

  • El trasfondo aquí es bastante gracioso: últimamente circula la historia de que las semillas “aleatorias” de las P-curves de NIST, creadas por Jerry Solinas de la NSA en los años 90, en realidad eran el hash SHA1 de una cadena variante de "Give Jerry a raise"
    En ese momento, pasar una cadena por SHA1 se consideraba un mecanismo de confianza: la estructura de la semilla desaparecía y la NSA no podría elegir deliberadamente una semilla débil
    Pero en los años 2000, NIST/NSA dañaron su propia reputación, así que esa explicación por sí sola ya no alcanzó para acallar las teorías conspirativas; más tarde, cuando NIST quiso mostrar que las semillas eran benignas, Jerry Solinas intentó reconstruirlas, pero al parecer olvidó la cadena que había usado
    Un conspiracionista de verdad asumiría que nadie encontrará la cadena que genera esta semilla, pero si alguien la encuentra, podría ser un golpe bastante fuerte contra la teoría de que las P-curves de NIST se generaron con mala intención, así que es una recompensa interesante

    • Aunque alguien encuentre que el hash de una cadena como "Give Jerry a raise of $100000 dollars now!!!" coincide con la semilla, no creo que eso pruebe que no hubo mala intención
      Si se conocían las propiedades particulares que debía tener una curva débil, se podrían haber hasheado muchísimas variantes de cadenas parecidas y elegir una hasta que apareciera una constante con las propiedades deseadas
    • A finales de los años 90 también estaba de moda usar MD5 y SHA1 juntos para lograr “robustez adicional” en construcciones arbitrarias
      SSLv2 y SSLv3 son buenos ejemplos, y aunque el tamaño de salida coincide con SHA1, no sería tan sorprendente que hubiera sido una canalización como echo "$string" | md5sum | sha1sum
    • Para una historia más larga, conviene ver el artículo de Koblitz y Menezes mencionado en el texto, “A Riddle Wrapped in an Enigma”. Ese artículo también trata por qué en 2015 la NSA dijo que había que ir hacia un mundo poscuántico
      https://eprint.iacr.org/2015/1018
      https://eprint.iacr.org/2015/1018.pdf
      Las mismas sospechas de puertas traseras también existían sobre (EC)DSA, y los partidarios de RSA afirmaban que la NSA lo promovía porque había puesto una puerta trasera en DSA, pero no había pruebas, y se dice que en 20 años tampoco se ha descubierto una forma de poner una puerta trasera en DSA o ECDSA
      También hay una anécdota de una reunión de estandarización en la que un representante de la NSA volvió después de hacer una llamada telefónica y dijo que la NSA creía que ECC era suficiente para las comunicaciones seguras de todas las agencias del gobierno de EE. UU., incluida la Federal Reserve, lo que sorprendió a todos
      Así como luego se supo que los ajustes a DES eran una defensa contra el criptoanálisis diferencial, y las debilidades de SHA-0, el SHA original, no estaban en el SHA-1 final, otras acciones de la NSA también se recibían con sospecha
    • Quemé CPU de más intentando encontrar la entrada que generó el valor “aleatorio” de unos 166 bits usado para construir G en secp256k1 y secp224k1, pero fracasé
      En ambas curvas, la elección de G es el doble de un punto con una coordenada x de tamaño sospechosamente adecuado, y esa característica es igual en las dos curvas
      En estas curvas, la elección de G es la única entrada con mucha entropía, pero en la práctica se puede probar que es casi irrelevante, y como mucho quien la eligió conoce un logaritmo discreto arbitrario en particular
      En protocolos forzados podría convertirse en una puerta trasera, pero sería muy artificial; aun así, como era el único parámetro desconocido, me pareció que valía la pena buscarlo
      Si se encuentra la semilla de las P-curves, quizá sea parecida a las semillas usadas para los puntos generadores de otras curvas, y también podría resolverse ese pequeño misterio
    • Para este tipo de fines, lo estándar suele ser usar constantes trascendentales como π o e, porque no se pueden elegir
      En teoría, una frase podría escogerse para que produzca el hash deseado

  • El GCHQ del Reino Unido emplea a más matemáticos que cualquier laboratorio o universidad del país. Supongo que su contraparte estadounidense será parecida.
    El intercambio de claves Diffie-Hellman también era conocido por el GCHQ y la NSA antes de que Diffie y Hellman lo redescubrieran.
    Es difícil hacer afirmaciones categóricas sobre las capacidades de base de las agencias de inteligencia, y no digo que realmente conozcan esta familia de curvas débiles, pero tampoco parece imposible. Esta área es su trabajo principal.

    • Creo que corresponde sospechar. Sobre todo porque el argumento de que es imposible se presenta como si fuera matemático, pero en realidad se parece más a un argumento social.
      Normalmente se dice que la academia es tan buena que, si la NSA hubiera hecho algo, ya lo habría descubierto; y si no estás de acuerdo, te tratan como alguien que no entiende y está difundiendo FUD. Este texto también repite esa línea, pero es bueno que el problema se tome más en serio mediante una recompensa organizada.
      Trabajé en criptografía en el pasado y durante varios años revisé regularmente papers de criptografía por trabajo; también asistí a conferencias, conversé con investigadores e implementé varias variantes “peculiares” de criptografía de curva elíptica. Desde una posición que no es completamente interna, pero tampoco completamente externa, esta creencia aceptada me parece peligrosa.
      Los argumentos centrales son dos: que si hubiera sido posible un ataque de cleptografía en la estandarización de las curvas NIST, la academia o la industria ya lo habrían encontrado; y que, como Dual_EC_DRBG fue sospechoso de inmediato, la comunidad criptográfica abierta es buena detectando puertas traseras.
      El primero es poco convincente. En la academia existe el problema del cajón de archivos y el incentivo de “publicar o desaparecer”; y es obvio qué le conviene más a un investigador joven: crear un nuevo algoritmo de pruebas de conocimiento cero y publicar un paper que reciba citas, o atacar un algoritmo que todos creen sólido y quizás no obtener nada.
      La base es un consenso de expertos del tipo “muchas personas inteligentes lo estudiaron a fondo y no encontraron nada”, pero en la academia es difícil publicar resultados negativos, así que no hay forma de saber cuánto esfuerzo se invirtió realmente.
      La cleptografía, es decir, la forma de introducir puertas traseras en estándares, casi no sirve para nadie que no sea la NSA, así que no es una buena trayectoria profesional y tampoco ayuda a pasar a la industria ni a recibir citas.
      En cambio, la NSA puede pagar más que la academia, contratar a más investigadores que toda la academia para dedicarlos a investigaciones con alta probabilidad de fracaso o útiles solo para puertas traseras en estándares, y durante décadas pudo hacer investigación multidisciplinaria que la investigación criptográfica académica no puede hacer por presupuesto de hardware.
      Si tuviera que apostar sobre quién entiende mejor ECC, la NSA o la academia, la potencia de fuego está del lado del gobierno y no hay comparación. Se puede estimar aproximadamente cuántos doctores en matemáticas emplea el gobierno, pero no sabemos cuánta potencia de fuego dedicó realmente la academia a este espacio de problemas.
      El segundo argumento tampoco es ideal. La gente planteó preocupaciones de inmediato no solo sobre Dual_EC_DRBG, sino también sobre las curvas NIST. La única diferencia es que, en el primer caso, había un algoritmo conocido para llevar a cabo el ataque necesario, y en el segundo no.
      Desde hace décadas se conoce una forma de evitar que este tipo de debate sea necesario, y esa es la razón por la que las curvas NIST se generaron a partir de salidas de SHA1. El mejor momento para retirar gradualmente las curvas NIST fue hace décadas; el segundo mejor momento es ahora.
    • La NSA también emplea a profesores de matemáticas especializados en teoría de números de Estados Unidos.

  • La razón por la que contribuyo a esta recompensa es que, si de verdad se trata de una frase que se puede crackear como contraseña, descubrirla tendría una gran importancia histórica.

  • Es bastante inquietante que las curvas elípticas NIST se hayan creado hasheando semillas proporcionadas por la NSA.
    Suena como: “No se preocupen, las hicimos hasheando una frase sin importancia. Ahora la olvidamos, pero solo era Jerry haciendo una broma sobre un aumento de sueldo”.
    Cuesta creer que no hayan pasado antes por una verificación fuerte, y que no se haya hecho una selección de semillas más razonable, como mezclar semillas aleatorias de varias partes con intereses distintos y generadores de números aleatorios por hardware.

    • Se siente así porque vivimos en 2023 y vemos las cosas sabiendo lo que ocurrió desde los años 90 hasta hoy.
      Ese método habría sido bueno, pero en ese momento probablemente no mucha gente vio la necesidad.
    • Si hoy la mayor parte del tráfico de Internet está cifrada, uno se pregunta para qué hacen falta centros de datos gigantes como Bluffdale.
      https://en.wikipedia.org/wiki/Utah_Data_Center

  • Hay un video donde el profesor Dan Boneh explica el contexto: https://youtu.be/8WDOpzxpnTE?t=892

  • Si entendí bien, ¿eso significa que la comunidad aceptó cadenas sospechosas de origen desconocido, y que habría sido muy fácil reemplazarlas por cadenas de origen claro usando otra entrada conocida en el hash?

    • Lo entendiste bien, y por eso es bastante desastroso. Me vienen a la mente “estuvimos tan cerca” y “solo tenías una cosa que hacer”.
      Lamentablemente, hasta donde sé, esta es la única vez que se menciona incompetencia en relación con la NSA y los estándares criptográficos; normalmente las historias apuntan en la dirección contraria.
      Lo más problemático es que NIST ya tenía antecedentes de haber introducido una puerta trasera en un estándar relacionado con curvas elípticas, y también se señaló de inmediato que este mecanismo no generaba confianza, pero ni NIST ni la NSA hicieron nada. Igual que con Dual_EC_DRBG.
      Aún más problemático es que en 2015 la NSA dijo explícitamente que no se debía actualizar desde las curvas NIST a otras curvas posteriores. La razón era que las computadoras cuánticas pronto serían lo bastante buenas como para romper todo ECC, así que todos debían migrar a criptografía poscuántica.
      Si ECC funcionara bien, las computadoras cuánticas estuvieran lejos y quisieras mantener a la gente atada a las curvas NIST el mayor tiempo posible, eso es exactamente lo que habrías dicho.
      Es difícil decir que la comunidad criptográfica salga con honor de esta situación. Pasaron casi 25 años, y existen curvas más nuevas que no tienen este problema; entonces, ¿por qué las curvas NIST todavía se usan? ¿Dónde está el esfuerzo para retirarlas gradualmente como se hizo con SHA1? Este texto, más bien, parece promocionar esas curvas.

  • Si te sientes con suerte, puedes intentar adivinar el hash SHA1 aquí: https://wending.dev/hash_guessing/

    • ¿Eso no solo genera el SHA1 de la cadena de entrada? Como dice el artículo, debería incluir algún tipo de contador.
      Si el generador de semillas de la NSA sabía aunque fuera un poco de criptografía y de computadoras, no habría estado metiendo a mano 500 frases distintas hasta que saliera una buena curva.
      Incluso si lo hubiera hecho, las variaciones posibles son infinitas: agregar un punto al final, cambiar mayúsculas y minúsculas, ponerlo en formato de título, etc.
      La lista de variaciones plausibles que habría que probar difícilmente puede llegar a ser completa, pero si esta página solo genera hashes SHA1, aunque adivines la cadena con la puntuación y las mayúsculas correctas, en la práctica es imposible encontrar el hash real.
      Como mínimo, para verificar si el hash resultante es un valor incrementado, debería poder comprobarse si coinciden unos 10 bytes al principio o al final. Aun así, en su mayoría solo hará que la gente pierda el tiempo, y el autor seguramente sabe que no llevará a ninguna parte.
      La página debería decir que es solo un juguete de demostración y que, aunque adivines correctamente, no te permitirá encontrar la semilla real.

  • Lo que aprendí de observar durante mucho tiempo las discusiones encendidas entre criptógrafos fue: “no apuestes contra Bernstein y no confíes en NIST”.
    Ahora creo que debería corregirlo a: “no apuestes contra Bernstein ni contra Filippo, y no confíes en NIST. Si estas dos reglas entran en conflicto, de todos modos no confíes en NIST”.

  • Es cierto que SHA-1 está roto, pero pensaba que el problema era principalmente de colisiones mediante ataques de extensión de longitud o ataques de texto plano conocido.
    Encontrar en la práctica la frase secreta cuando solo se tiene el hash seguía pareciéndome difícil.

    • Correcto. Todavía se considera que SHA-1 tiene resistencia a preimagen.
      Pero si la hipótesis sobre la estructura de la semilla es correcta, aquí la resistencia a preimagen no es tan importante. SHA-1 es muy rápido y fácil de paralelizar, así que alguien que busque con insistencia en el espacio de variaciones de "Jerry needs a raise" tiene bastante probabilidad de descubrir la entrada original.
    • Esto es un simple ataque de diccionario, y es la forma en que se rompen la mayoría de los hashes de contraseñas.
      No tiene mucho que ver con SHA1 en sí.