Una transacción débil en ECDSA en la cadena de bloques de Bitcoin y con la ayuda de Lattice Attack recibimos una clave privada para monedas BTC

 

¿Qué sabemos sobre el ataque a la red?

Para empezar, el  algoritmo de firma digital de curva elíptica (ECDSA)  es un esquema de firma digital común que vemos en muchas de nuestras revisiones de código. Tiene algunas propiedades deseables, pero también puede ser muy frágil recuperar la clave privada con un ataque de canal lateral que revela menos de un bit del nonce secreto.

ECDSA es una forma especial del algoritmo de firma digital  (DSA). DSA es un esquema de firma digital bastante común, que se define mediante tres algoritmos: generación de claves, firma y verificación. El algoritmo de generación de claves genera claves privadas y públicas;  la clave privada es responsable de crear firmas;  y la clave pública se encarga de verificar las firmas.  El algoritmo de firma toma un mensaje y una clave privada como entrada y genera una firma. El algoritmo de verificación toma un mensaje, una firma y una clave pública como entrada y devuelve un valor de  true o  false, que indica si la firma es válida.

DSA está definido para cualquier grupo matemático, y este esquema es seguro siempre que el problema del logaritmo discreto sea difícil para ese grupo. Un grupo de uso común es el de los números enteros módulo a número primo p.

Junto con este grupo tendremos un generador de grupos g y alguna   función  hashH criptográficamente segura . Podemos asumir eso  p , g y  H será de conocimiento común.

La generación de claves funciona seleccionando primero aleatoriamente un valor  x de enteros de módulo  p . Luego se calcula el valor y = g^x mod p

La clave privada de la firma es  x , y la clave pública es  y . La clave de firma debe mantenerse en secreto, ya que es la que permite realizar las firmas.

El algoritmo de firma crea una firma a partir del mensaje  m y la clave secreta x. Primero, se genera un elemento de grupo aleatorio  k . Esto se conoce como un nonce, que es importante cuando se trata de ataques.

Luego se calculan los valores  r = g^k mod p y s = ( k^-1 ( H ( m ) + xr )) mod p

Aquí  k^- 1 , es el grupo inverso, y  H ( m ) es el resultado de calcular el hash m e interpretar el resultado como un módulo entero p .

La firma se define como un par de  ( r , s ). (Nota: si uno de los  valores r o  ses igual a  0, el algoritmo se reinicia con el nuevo valor de  k ).

El algoritmo de verificación recibe una firma  ( r , s ), un mensaje  m y una clave pública como entrada. Sea  ŝ = s^-1 , entonces el algoritmo devuelve verdadero si y solo si  r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .

Esta verificación de validación funciona porque  g^H( m ) y^r = g^H(m)+ xr = g^ks, y por lo tanto (g^H(m)y^r)^ŝ = g^k = r

Un esquema de firma digital se considera seguro si no se puede falsificar.

La inmutabilidad tiene un significado criptográfico formal, pero en un nivel alto significa que no puede crear firmas sin conocer la clave secreta (a menos que haya copiado una firma ya existente creada a partir de la clave secreta). Probado como  DSAimposible de falsificar bajo el supuesto  de un registro discreto  .

DSA se define sobre un grupo matemático. Cuando  DSA se usa con el grupo de curvas elípticas como este grupo matemático, lo llamamos  ECDSA. El grupo  de curvas elípticas consta de puntos de curvas elípticas, que son pares de  ( x , y ), que satisfacen la ecuación  y^2 = x^3 + ax + b para algunos  a , b . Para esta publicación de blog, todo lo que necesita saber es que al usar curvas elípticas puede definir un grupo finito, lo que significa que obtiene el generador de grupos  g (punto de curva elíptica) y las  operaciones de suma  y  multiplicación de puntos  exactamente como estas. puede con números enteros. Como forman un grupo finito, generador,g , tendrá un orden finito,  p. Esta publicación de blog no explicará ni requerirá que sepa cómo funcionan estas  operaciones de curva elíptica .

ECDSA работает так же, как DSA, но с другой группой. Секретный ключ x по-прежнему будет случайным значением из целых чисел по модулю p . Теперь публичный ключ y по- прежнему вычисляется как y = g^x , за исключением того, что теперь g является точкой эллиптической кривой. Это означает, что y также будет точкой эллиптической кривой (раньше y был целым числом по модулю p ). Еще одно отличие заключается в том, как мы вычисляем значение r . Мы по-прежнему генерируем случайный одноразовый номер k как целое число по модулю p , как и раньше. Мы вычислим g^k , но опять же,g — точка эллиптической кривой, и, следовательно, g^k — тоже. Следовательно, мы можем вычислить ( x^k , y^k ) = g^k и установить r = x^k . Теперь значение s можно вычислить, как и раньше, и мы получим нашу сигнатуру ( r , s ), которая по-прежнему будет целым числом по модулю p , как и раньше. Чтобы проверить, нам нужно сделать поправку на тот факт, что мы вычислили r немного по-другому.

Итак, как и прежде, мы вычисляем значение ( g^H(m)y^r)^ŝ , но теперь это значение является точкой эллиптической кривой, поэтому мы берем x-координату этой точки и сравниваем ее с нашим значением r .

Восстановление секретных ключей из повторно используемых одноразовых номеров NONCES

Теперь, когда мы понимаем, что такое ECDSA и как он работает, давайте продемонстрируем его хрупкость. Опять же, поскольку это схема цифровой подписи, крайне важно, чтобы секретный ключ никогда не раскрывался никому, кроме лица, подписывающего сообщение.

Однако, если подписывающее лицо когда-либо выпускает подпись, а также выпускает использованный одноразовый номер, злоумышленник может немедленно восстановить секретный ключ.

Скажем, я освобождаю подпись ( r , s ) для сообщения m и случайно обнаруживаю, что использовал одноразовый номер k .

Поскольку s = ( k^-1 ( H ( m ) + xr )), мы можем легко вычислить секретный ключ:

s = (k^-1(H(m) + xr))

ks = H(m) + xr

ks – H(m) = xr

x = r^-1(ks – H(m))

Следовательно, подписывающая сторона должна не только хранить в секрете свой секретный ключ, но и все свои одноразовые номера, которые они когда-либо генерировали, в секрете.

Даже если подписывающий держит в секрете каждый одноразовый номер NONCES, если он случайно повторит один одноразовый номер NONCES (даже для разных сообщений), секретный ключ также может быть немедленно восстановлен.

Пусть ( r , s 1 ) и ( r , s 2 ) будут двумя подписями, созданными на сообщениях m 1 и m 2 (соответственно) из одного и того же одноразового номера, k - поскольку они имеют один и тот же одноразовый номер, значения r будут одинаковыми, так что это очень легко обнаруживается злоумышленником:

s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)

s1 – s2 = k^-1(H(m1) – H(m2))

k(s1 – s2) = H(m1) – H(m2)

k = (s1 – s2)^-1(H(m1) – H(m2))

Una vez que hemos recuperado el nonce  k usando la fórmula anterior, podemos recuperar la clave privada realizando el ataque descrito anteriormente.

Vamos a digerir esto por un momento.

Si   alguna vez se divulga  el nonce  de firma, la clave secreta se puede  recuperar de inmediato , lo que  rompe todo nuestro esquema de firma .NONCES

Además, si alguna vez se repiten dos nonces, sin importar cuáles sean los mensajes,  un atacante  puede detectar esto fácilmente e inmediatamente  recuperar la clave secreta , rompiendo nuevamente todo nuestro esquema.

¡Es bastante frágil y solo son  ataques ligeros !

Pero hay un  nuevo  Lattice Attack  que ha sido descrito con gran detalle  (Joachim Breitner y Nadia Heninger)Йоахим Брайтнер и Надя Хенингер 

Documento  [PDF] :  Sentido nonce sesgado: Ataques de celosía contra firmas ECDSA débiles en criptomonedas

En la cadena de bloques de Bitcoin, encontramos cierta transacción:

transacción:  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

para direcciones Bitcoin:  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

y logramos multiplicar las firmas falsas y aplicar la grilla

donde usando el  script de Python  algoritmo LLL.py  con la instalación de paquetes en  GOOGLE COLAB

INSTALAR >> SAGE + ECDSA + BITCOIN + algoritmo LLL

Logramos llegar  Private Key a  Bitcoin Wallet partir de una transacción débil en  ECDSA.

Instalación

Ejecute el script Bash: lattice.sh

Resultado en formato HEX ¡Clave privada encontrada!

Archivo: ONESIGN.txt (Valor R, S, Z de la firma ECDSA)

Propagamos firmas falsas para el algoritmo de script PythonLLL.py

Archivo: CLAVE PRIVADA.txt

Archivo: DIRECCION.txt

Comprobación de la clave privada en el sitio web de bitaddress

¡Se encontró la clave privada!

https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

0.001 BTC

ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF:  5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX:  31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 

Este video fue creado para el  portal CRYPTO DEEP TECH  para garantizar la seguridad financiera de los datos y la criptografía de curva elíptica secp256k1 contra firmas ECDSA débiles en la criptomoneda BITCOIN

Vídeo:  https://youtu.be/YP4Xj6gUcf4

Telegrama :  https://t.me/cryptodeeptech

Fuente:  https://cryptodeep.ru/lattice-attack