Topic: about Brute-force missing private key in the end ! (Read 343 times)

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))

@arulbero thanks for the explanation but it seems like you made a small mistake here:
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

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

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 :

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.

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.

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.

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.

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.

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?