Problemas con ECDSA determinista basado en RFC6979 en Bitcoin

La generación de números aleatorios ken una curva elíptica es crucial y en cualquier firma de transacciones en Bitcoin, kse requiere un número aleatorio para calcular un punto k*G. Si esto kno se elige al azar, instantáneamente filtra la clave privada.
Por lo tanto, se les ocurrió una idea de generación determinista de ECDSA que se describe en RFC6979 . Básicamente, concatenan la clave privada con el mensaje hash y usan una función HMAC y generan un pseudo aleatorio k.
Este método parece simple y fácil.

  • ¿Introduce alguna sobrecarga?
  • En caso afirmativo, ¿es esta sobrecarga insignificante?

¿O, en general, hay alguna ineficiencia o problema con este método y por qué todavía vemos una implementación no determinista de ECDSA?

Respuestas (1)

No hay problemas serios de eficiencia. La firma se realiza con poca frecuencia para un cliente en particular (generalmente, solo unas pocas firmas por transacción). Si bien es posible que la firma demore un poco más en generar el kvalor, no se notaría, especialmente considerando la poca frecuencia con la que lo usa un cliente en particular. La verificación de todas las firmas es el cuello de botella de la CPU para la verificación de bloques en bitcoin, porque todos los nodos completos tienen que verificar las firmas de todas las transacciones en la red, y esto lleva el mismo tiempo, independientemente de cómo kse haya elegido el parámetro.

Gregory Maxwell hizo un comentario sobre el uso de kvalores deterministas aquí :

Los principales argumentos en la mayoría de los espacios en contra de la eliminación aleatoria de DSA son la conformidad con FIPS (irrelevante para nosotros) y preocupaciones razonables sobre los riesgos de usar una construcción criptográfica (menos) revisada. Con un movimiento generalizado hacia DSA sin aleatorizar, esta última preocupación es un problema menor.

La nueva biblioteca libsecp256k1 de Pieter Wuille en realidad usa la generación determinista de k.

También tenga en cuenta que uno de los beneficios clave de usar esta construcción es que no necesita preocuparse por la explotación de una debilidad en su PRNG en el proceso de firma. Por ejemplo, firmar diferentes datos con el mismo kvalor filtra instantáneamente su clave privada . También se puede explotar un ataque similar si el PRNG es lo suficientemente débil como para determinar la relación entre los diferentes kvalores utilizados al firmar el mismo dato. Dado kque se genera de manera determinista a partir de los datos que está firmando (y la clave privada), estas preocupaciones sobre el PRNG ya no son tan relevantes, ya que siempre producirá la misma firma para la misma información. Esto también facilita la escritura de pruebas unitarias ECDSA.

Como mencionó, el proceso de verificación es el mismo y agregar un par de cálculos HMAC adicionales al lado del cliente realmente no afecta el proceso de firma.
Firmar los mismos datos dos veces con diferentes valores de 'k' es seguro.
@adaclin Solo si un atacante no puede determinar la relación entre los dos valores k utilizados. Si, por ejemplo, se sabe que una k es igual a la otra más uno, filtra instantáneamente su clave privada.
@PieterWuille Gracias, actualicé mi respuesta. Había confundido el ataque different-ks-same-data con el ataque different-data-same-ks mencionado aquí .
@abeikverdi En realidad, generar un nonce usando RFC6979 con SHA256 requiere 22 invocaciones de la función de compresión SHA256, que requiere del orden del 10 % del tiempo total de firma.
@PieterWuille ¿Puedes iluminarme? ¿No concatenamos simplemente la clave privada y el mensaje hash como el nonce HMAC?
@abeikverdi Lea RFC6979 e intente implementarlo, verá.
@PieterWuille Ya he leído RFC6979. Sin embargo, nunca intenté implementar eso. ¿Es este 10% de tiempo de sobrecarga al que se refiere, su experiencia personal? o es científico?
Lo comparé. No se puede ser más científico que eso.
@ StephenM347 ¿No generaría este RFC 6979 el mismo k dos veces? HMAC_DBGA(private key d || H(m)) genera la misma k para el mismo mensaje hash ya que la clave privada es constante. ¿no es así? ¿No es eso un problema?
@abeikverdi, no realmente, es exactamente por eso que es útil porque produce la misma firma para los mismos datos. Solo usa la misma k dos veces para el mismo mensaje. Solo cuando firma diferentes datos con el mismo valor de k, se filtra su clave privada. Usar la misma k para los mismos datos no da ninguna información nueva.
@ StephenM347 los datos a los que se refiere, que es el mensaje hash, ¿es el hash de la transacción?
@abeikverdi, esencialmente, sí, los datos que se firman son un hash de la transacción que se ha borrado de todas las entradas (no firma otras firmas). Hay un pequeño matiz más, que el scriptPubKey anterior de la salida que se gasta se inserta en el scriptSig antes del doble hash SHA256.
@StephenM347 ¡Muchas gracias! ¡Lo tengo totalmente ahora!
Problemas con ECDSA determinista basado en RFC6979 en Bitcoin
RespuestasAquíPolítica de privacidad1y, 0v