Bitcoin Forum
September 15, 2019, 01:21:42 PM *
News: If you like a topic and you see an orange "bump" link, click it. More info.
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: about Brute-force missing private key in the end !  (Read 177 times)
omer-jamal
Full Member
***
Offline Offline

Activity: 476
Merit: 239


View Profile
January 31, 2019, 04:19:59 PM
 #1

hi i know displaying any parts of private key is dangerous ( Especially the first character ! )
is possible Brute-force attack ethereum private key missing a 20 character in the end ?!  - What time is expected

i think it's possible and Easy Especially ethereum the range ( 0-9 , A-F ) The odds are lower

What do you think about that?

do not send merit to this user He does not know where to spend it
1568553702
Hero Member
*
Offline Offline

Posts: 1568553702

View Profile Personal Message (Offline)

Ignore
1568553702
Reply with quote  #2

1568553702
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
qwk
Donator
Legendary
*
Offline Offline

Activity: 2240
Merit: 2146


Shitcoin Minimalist


View Profile
January 31, 2019, 04:28:13 PM
 #2

hi i know displaying any parts of private key is dangerous ( Especially the first character ! )
is possible Brute-force attack ethereum private key missing a 20 character ?!
Ethereum is off-topic, but this applies to Bitcoin as well, so why not answer it?
No, it's highly unlikely that a brute-force attack against 20 missing characters of a private key is to succeed.

For a very very rough estimate, you may consider the performance of the software of vanitygen, which basically is highly optimized brute-force-software for keys.
Anything longer than 10 to 12 characters seems to be bordering on impossible, given standard hardware.

All free men, wherever they may live, can use Bitcoin, and, therefore, as a free man, I take pride in the words "Ich bin ein Bitcoiner!"
Elliptic23
Newbie
*
Offline Offline

Activity: 17
Merit: 0


View Profile
January 31, 2019, 05:06:18 PM
 #3

hi i know displaying any parts of private key is dangerous ( Especially the first character ! )
is possible Brute-force attack ethereum private key missing a 20 character in the end ?!  - What time is expected

i think it's possible and Easy Especially ethereum the range ( 0-9 , A-F ) The odds are lower

What do you think about that?

You have all of the private key except 20 characters (80 bits)? Then it is possible and feasible to recover the entire key using baby-step-giant-step or pollard's tho algorithm.

It will require 2^40 work, which is a few hours on a GPU.
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
January 31, 2019, 05:18:11 PM
Last edit: January 31, 2019, 05:33:55 PM by arulbero
Merited by ETFbitcoin (1)
 #4

You have all of the private key except 20 characters (80 bits)? Then it is possible and feasible to recover the entire key using baby-step-giant-step or pollard's tho algorithm.

It will require 2^40 work, which is a few hours on a GPU.

1) Only if you know the public key too (not the address).

2) baby-step-giant-step in this case (80 bits) would require more than 2^40 work, because you don't have enough Ram to store 2^40 public keys.


To retrieve the last 60 bits (bitcoin case) my program takes about 5 minutes (it run on a single cpu). It uses baby-step-giant-step algorithm and 32 GB.
ETFbitcoin
Legendary
*
Offline Offline

Activity: 1764
Merit: 2022

Use SegWit and enjoy lower fees.


View Profile WWW
January 31, 2019, 06:43:08 PM
 #5

You have all of the private key except 20 characters (80 bits)? Then it is possible and feasible to recover the entire key using baby-step-giant-step or pollard's tho algorithm.

It will require 2^40 work, which is a few hours on a GPU.

1) Only if you know the public key too (not the address).

Additionally if you don't have the public key, you need to generate public key/address and check each of it on blockchain explorer or full node client RPC/API which is huge overhead.

KingZee
Sr. Member
****
Offline Offline

Activity: 602
Merit: 424


Check your coin privilege


View Profile
January 31, 2019, 09:18:57 PM
 #6

hi i know displaying any parts of private key is dangerous ( Especially the first character ! )
is possible Brute-force attack ethereum private key missing a 20 character in the end ?!  - What time is expected

i think it's possible and Easy Especially ethereum the range ( 0-9 , A-F ) The odds are lower

What do you think about that?

I'm not familiar with ethereum very well, but what format is this private key? In bitcoin for example bruteforcing a key written in WIF would be harder than the original hex used to generate it.

Also like arulbero mentioned, you need to know the address you're looking for, because if for example, you only know if you have the right key once the balance of your target is not zero, your search becomes a LOT slower.

khaled0111
Hero Member
*****
Offline Offline

Activity: 826
Merit: 544



View Profile
January 31, 2019, 09:58:48 PM
Last edit: February 01, 2019, 01:13:49 AM by khaled0111
Merited by Jating (1), omer-jamal (1)
 #7

Ethereum private keys format is 64 HEX.
Without the public address, brute forcing is pointless/time and resource consuming since all addresses in that range with funds is a possible target.

In your case, I think there are 20^16=1208925819614629174706176 possiblities. If you don't allready know the public address, then for each private key you have to derive the public address and check it whether it has funds or not.

          ███████
      ██   ▀███▀   ██
  ▄█▄  ▄▄█████████▄▄  ▄█▄
 ▄███▄██▀▀       ▀▀██▄███▄
 ██▀███    ▄▄█▄█    ███▀██
    ██      █▀▀██    ██
██  ██     █████▀    ██  ██
    ██   ▄▄█▄▄▄██    ██
 ██▄███    █▀█▀▀    ███▄██
 ▀███▀██▄▄       ▄▄██▀███▀
  ▀██  ▀▀█████████▀▀  ██▀
      ██   ▄███▄   ██
          ███████
bspin   ███████████████████████
███████████████████████████
███████████████████████████
███████▀█▀    ▀▀▀██▀███████
███████            ▄███████
███████ ▄██▄▄▄▄▄▀ ▄████████
███ ▀  ▀  ██▀▀   ▄▀  ▀  ███
███▄▄█▀  █▀     █▄▄█▀  ████
█████   █▀       ██   █████
████▄▄▄▄█▄▄▄▄▄▄▄▄█▄▄▄▄█████
███████████████████████████
███████████████████████████
  ███████████████████████
       ▄▄█████████▄▄
    ▄█████████████████▄
  ▄█████████████████████▄
 ▄█████████  █  █████████▄
▄████████        █████████▄
███████████  ██  ██████████
███████████       █████████
███████████  ███  █████████
▀████████        ▄████████▀
 ▀█████████  █  █████████▀
  ▀█████████████████████▀
    ▀█████████████████▀
       ▀▀█████████▀▀
..PLAY NOW..
omer-jamal
Full Member
***
Offline Offline

Activity: 476
Merit: 239


View Profile
February 01, 2019, 07:56:50 AM
Last edit: February 02, 2019, 06:03:37 AM by omer-jamal
 #8

Thanks all,
Most your posts : with public key Brute-force  more easy ?
how knowing public key speed up the Brute-force private key  ? Is there a lesson explains this point?

relationship between Public and private key As you know one-way function how public key Speed up the process ?

Edit / Oh this really dangerous!  Even can found offline
some thing like :

Code:
loop
{
    [ Brute-force private key ]
    
    get : public address

    if { public address == target address  } // found !

    return private key
}

do not send merit to this user He does not know where to spend it
arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
February 01, 2019, 01:45:56 PM
Last edit: February 01, 2019, 01:59:58 PM by arulbero
Merited by Coding Enthusiast (3)
 #9


1) Only if you know the public key too (not the address).

2) baby-step-giant-step in this case (80 bits) would require more than 2^40 work, because you don't have enough Ram to store 2^40 public keys.


How it works

imagine you have:

a) a partial private key d:
f461d7473a944648de9630a2062fc29f676fab0c6e9c344a472f70bef31dca17 (you lost the last digit, 7)

b) the public key P:
x : 4461130191898d8b22c00c474a5903a679afcf7988c2db3636223ab4ce7883e2
y:  50abf843d037afdb1a40ae565c8c72b7b29740282bd335a63d369e6eeced21a2

You lost the last hex digit, 7,  16 is then the search space size.
How can you retrieve the correct value?

Option:
 
1) brute force, there are max 16 tries to do:  from f461....dca10 to f461....dca1e, for each private key you compute the public key and compare the result with P.


2) baby-step-giant-step (--> http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/):

you create two lists, the first one (giant steps list) in a hash table stored in Ram and the second one (baby steps list) dynamic:

a) (giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(16) = 4, namely the distance between 2 elements is 4*G .  

Then we create the list:
k*G, (k+4)*G, (k+8)*G, (k+12)*G   where k is the first possible key to check (k = f461....dca10)

b) now we generate the baby-steps list (the distance beween 2 consecutive elements is 1*G) on fly, starting from

P  

and we check if it is equal to an element in the giant-steps list, if not try with

P - 1*G, P - 2*G and so on (P-3*G is the last element).

In our case, P - 3*G =  (k+4)*G

--> P = (k+7)*G  --> private key k+7


If you don't know the last 2 hex digits, the search space is 256 elements, then you need to create a list of 16 elements (baby-steps: k*G, (k+16)*G, (k+2*16)*G, ...,(k+15*16)*G) and the baby-steps list (P, P - 1*G, P - 2*G, ...., P - 15*G).

16 elements * 16 elements = 256 comparisons



A software (not mine) that works in this way: https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 666
Merit: 1027


Novice C♯ Coder


View Profile WWW
February 01, 2019, 03:31:54 PM
 #10

@arulbero thanks for the explanation but it seems like you made a small mistake here:
k*G, (k+4)*G, (k+8)*G, (k+12)*G   where k is the first possible key to check (k = f461....dca10)
In giant steps you pre-compute 0G, 1G, 2G, ..., (m-1)G. So in this case it seems you should be calculating kG, (k+1)G, (k+2)G, (k+3)G

Then for the baby step you calculate
s= m * -G
loop: r=r+s

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

arulbero
Legendary
*
Offline Offline

Activity: 1282
Merit: 1305


View Profile
February 01, 2019, 03:42:40 PM
Last edit: February 01, 2019, 04:17:59 PM by arulbero
Merited by ETFbitcoin (1), Coding Enthusiast (1)
 #11

@arulbero thanks for the explanation but it seems like you made a small mistake here:
k*G, (k+4)*G, (k+8)*G, (k+12)*G   where k is the first possible key to check (k = f461....dca10)
In giant steps you pre-compute 0G, 1G, 2G, ..., (m-1)G. So in this case it seems you should be calculating kG, (k+1)G, (k+2)G, (k+3)G

Then for the baby step you calculate
s= m * -G
loop: r=r+s


Giant means giant, baby baby.

You have 2 possibilities:

1)
Baby-steps:  0, 1*G, 2*G, ..., (m-1)*G  //  Giant-steps:  P, P - m*G, P - 2*m*G, ...., P - (m-1)*(m)*G

or

2)
Baby-steps:  P, P - 1*G, P - 2*G, ...., P - (m-1)*G //  Giant-steps:  0, m*G,  2*m*G, ...., (m-1)*m*G


In either cases  you can find a key between 1 (P = 1G) and m^2 - 1 (P - (m-1)*G = (m-1)*m*G  -->  P = (m^2 - 1)*G)
You have two lists of m elements.

If you need a search space from k to k + m^2 - 1 (size of search = n = m^2),

in the case 1)  add k*G in the baby-steps list:  k*G, (k+1)*G, (k+2)*G,...., (k+m-1)*G or sub k*G from P in the giant-steps list
in the case 2)  add k*G in the giant-steps list:  k*G, (k+m)*G, (k+2*m)*G,...., (k+(m-1)*m)*G or sub k*G from P in the baby-steps list

baby: step of 1G
giant: step of mG (where m is sqrt(n))

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!