Incremental private key cracking mode - no resume/continue

[johnlockejrr]

"incremental private key cracking mode" has no resume/continue, if you run it one day from a key and the system crashes/is rebooted/whatever how can one resume the work/test? Maybe some log file or resume info like "John The Ripper" has? Thanks!

[ryancdotorg]

You can use the -v flag to get progress output on stderr, then redirect that to a file or read it in a wrapper script. I might implement something to make it stop after a given number of keys.

[johnlockejrr]

Yes, I use the -v flag but it only shows me the progress like 0/9288383, I would like to know the last key tried, still reading your code, wanted to write from time to time to a log file the last hex key checked so for one day run, in case of a crash or whatever, I won't loose all the work, because your program is daaaamn fast ;)

[ryancdotorg]

the second number is how many keys have been tried (and should auto-scale reporting interval to update several time per minute), you can compute the last key tried by taking the increment, multiplying by keys tried, and adding the starting key.

Part of why brainflayer is fast is that it is single-threaded. Writing a status file would require either a potentially blocking disk write, forking (and calling waitpid until the child finishes), or creating a thread. All of these introduce additional complexity and potential slowdowns.

If you can limit the number of keys tried, it's pretty simple to wrap brainflayer in a shell script that does, say, 1,000,000,000 keys at a time and logs progress.

[johnlockejrr]

you're right. writing to disk every key is not an option, that's why I thought about writing last key once per hour. anyway, computing last key incrementing from the given key is an option. by the way, the key is a HEX string, say I start from 0000000000000000000000000000000000000000000000000000000000000001 and arrive to 0/9288383 can I just add 9288383 to 0000000000000000000000000000000000000000000000000000000000000001 and get the last key?

[ryancdotorg]

yes, so long as you haven't specified the -n option

[johnlockejrr]

Any idea how can I do that in C? Doesn't seem to work for me:

#include <stdio.h>

int main() {
  int x;
  x = 0xb04c426e30f75098e207fb537b5c975f77ad7f8d + 1;
  printf("%x\n", x);
}

Output: 77ad7f8e

[ryancdotorg]

I'm somewhat surprised that didn't throw a compiler error. C doesn't have a convenient way to handle numbers that large (you could use a bignum library or OpenSSL...). Python will handle large numbers like that just fine, though.

[johnlockejrr]

Yeah, my bad, tried also unsigned long long int and %llx format, same almost same thing, it gets truncated to 7b5c975f77ad7f8e

[johnlockejrr]

Good tip with python:

#!/usr/bin/env python2.7

x = 0xb04c426e30f75098e207fb537b5c975f77ad7f8d + 1;

print("%0.2x" % x)

Output: b04c426e30f75098e207fb537b5c975f77ad7f8e

[ryancdotorg]

Intended solution for this: add an option to stop after processing a given number of keys.

[jamesyoungdigital]

From the Bitcoin Wiki:

Specifically, any 256-bit number from 0x1 to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140 is a valid private key.

I would think 0xFFFF ... are the least significant bits, but not entirely sure. Does brainflayer in increment mode automatically stop at the largest valid key, if you start searching from a large key and hit the largest valid key?

I was thinking about a start increment and stop here option, so brainflayer is guaranteed to stop searching with increment mode in a specific key space. I'm not sure if that's already an option, but the idea is to run brainflayer -I start_key -E end_key and have it running on say 64 Xeon CPUs, so it checks the desired key space 64-times faster (?)

For instance the second brainflayer would start with -I = (previous -E endpoint+1), and end with -E for a specific number of keys searched, say, a trillion or more each brainflayer run x 64 CPUs.

My thinking goes along a DES brute-force key search I worked on, which was obvious but worked like a charm. If I had code which looked like this:

// iterations is where to stop looking
bool found_key(uint64_t start, uint64_t iterations, uint64_t step, uint64_t des_key)
{
    for (uint64_t i = start; i <= iterations; i += step) {
         if (i == des_key) return true;
    }
}

... and I had the program running on 4 CPUs, then:

start = 0, iterations = big number, e.g. DES_KEY_SISE, step = 4
start = 1, iterations = as above, step = 4
start = 2, iterations = as above, step = 4
start = 3, iterations = as above, step = 4

This as a naive way of doing it, but the speed up was amazing on 16 Xeon CPUs with the method above extended for 16 processes. I'd take the found key which was a "properly generated" one to test against, and one of the des cracker programs would stop with the found key. Admittedly the other proceses would keep running and I would kill them off manually, but it was a fun experiment.

If anyone is working on this feature request, or not, if I could bother you every now and then for parts of the code I can't figure out, I'd like to start out on work with brainflayer. One idea for later is to find candidate areas that are critical and run frequently but don't branch, e.g. an "oclBrainflayer" running on a number of GPUs.

[ryancdotorg]

The scalar private keys are most significant bit first. For multiple cores/CPUs, you can use e.g. -n 1/4 for the first, -n 2/4 for the second, -n 3/4 for the third, and -n 4/4 for the fourth if you had for cores.

FWIW, running incremental private key searches is mostly a waste of electricity - lottery tickets and casinos have better expected value.

[jamesyoungdigital]

Thanks Ryan!

I did think a full key space search was impractical, but I appreciate the odds as you explained.

What I wanted to do was create a known key within a range and find it with brainflayer to see what the output looks like.

Then work on some python tools to complement brainflayer. I've revitalized the bitcoin library that the original maintainer doesn't have time for. I'll have to write better docs and add options for local blockchain rpc calls. This is the bitcoin library used in Hacking Bitcoin with Math demo code.

Thanks again Ryan!

On Tue, 6 Nov. 2018, 5:04 pm Ryan Castellucci <[email protected] wrote:

The scalar private keys are most significant bit first. For multiple cores/CPUs, you can use e.g. -n 1/4 for the first, -n 2/4 for the second, -n 3/4 for the third, and -n 4/4 for the fourth if you had for cores.

FWIW, running incremental private key searches is mostly a waste of electricity - lottery tickets and casinos have better expected value.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ryancdotorg/brainflayer/issues/56#issuecomment-436141025, or mute the thread https://github.com/notifications/unsubscribe-auth/Ao5ZJ5AXjCTkfP4UsBjBmLm46xlMMhg0ks5usSaDgaJpZM4RwIE3 .

[jamesyoungdigital]

Hi Ryan,

Thank you for your responses. If I could just bother you (please) to make sure I am understanding a few things correctly?

When you say a scalar private key starts at most significant bits first, does than mean:

./brainflayer -v -I 0000000 ..... 0000001 -b addrs.blf

The 000001 part and increment from there means checking the most significant bits first? Or am I confused and and it literally starts from private key 0x01 and increments from there? Just want to check. Would it be reasonably easy to change the code somewhere to have -I and the input is hex which is then converted into a starting point scalar key? I will have to do a bit of research to check that out, even though I will only use it for small tests with defcoin addresses.

Also, with the passphrase input method, does brainflayer check every passphrase as a brainwallet generated key for each address supplied in the bloom filter of addresses? And the same for incremental key search, will it try each batch of keys it generates for every address given?

My brainflayer does 1.656 billion checks/hour (~ 500000 p/s), so does that mean it's actually checking every password/passphrase supplied for each address supplied at that rate? Or does it mean it's checking 500,000 p/s on my machine, so assuming I have 500,000 passphrases, it's checking every passphrase for one address per second?

Thank you again!

Edit: actually, it seems it checked 0/trillion within 37 minutes. So this means it checked a trillion keys for every address supplied in 37 minutes? Wow.

[ryancdotorg]

./brainflayer -v -I 0000000 ..... 0000001 -b addrs.blf

This starts with private key 0x1 and increments from there. The word "scalar" is a technical term. More simply, private keys are just large integers.

Would it be reasonably easy to change the code somewhere to have -I and the input is hex which is then converted into a starting point scalar key?

I don't understand the question.

Also, with the passphrase input method, does brainflayer check every passphrase as a brainwallet generated key for each address supplied in the bloom filter of addresses? And the same for incremental key search, will it try each batch of keys it generates for every address given?

Please read up on how bloom filters work. Checking a bloom filter gives a result of "probably in the list" or "definitely not in the list" in a single operation.

does that mean it's actually checking every password/passphrase supplied for each address supplied at that rate?

That is the rate of password/passphrase checking, yes.

[jamesyoungdigital]

Thank you again.

The question you didn't get: I think the key specified is already in hex format (d'oh) so I could start with e.g. -I 000000 ... cafebabe as the starting point. I was a bit tired and realised it probably wasn't a binary string input!

Thanks for the tip on bloom filters. I'll check that out.

Thanks for the 11th HOPE talk with the math expert too, I really enjoyed that!

On Thu, 8 Nov. 2018, 1:19 pm Ryan Castellucci <[email protected] wrote:

./brainflayer -v -I 0000000 ..... 0000001 -b addrs.blf

This starts with private key 0x1 and increments from there. The word "scalar" is a technical term. More simply, private keys are just large integers.

Would it be reasonably easy to change the code somewhere to have -I and the input is hex which is then converted into a starting point scalar key?

I don't understand the question.

Also, with the passphrase input method, does brainflayer check every passphrase as a brainwallet generated key for each address supplied in the bloom filter of addresses? And the same for incremental key search, will it try each batch of keys it generates for every address given?

Please read up on how bloom filters work. Checking a bloom filter gives a result of "probably in the list" or "definitely not in the list" in a single operation.

does that mean it's actually checking every password/passphrase supplied for each address supplied at that rate?

That is the rate of password/passphrase checking, yes.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ryancdotorg/brainflayer/issues/56#issuecomment-436849551, or mute the thread https://github.com/notifications/unsubscribe-auth/Ao5ZJyYFqz2vGh7M8XN4V-2IIgBIc80sks5us5SngaJpZM4RwIE3 .

[jamesyoungdigital]

Hi Ryan,

If I could trouble you with another question. I forked an early version of Bitcoin and have a private blockchain, so I know some private keys. It's working, because I gave it really tiny ones I can check in a few seconds.

I'm using -n for 1/8 ... 8/8. I started with -I 0000000000000000000000000000000000000000000000000000000000000001 (one, that's still one whether it's represented as big or little endian is that right?)

and I knew I would eventually hit the private key

0000000000000000000000000000000000000000000000000000000000556e52

at some point. Is that also in big endian notation? So it starts at 1, and increments up to 556e52? So the 1 goes from right to left, in a sense, 1, 2, 3, 4, ... up to 556e52?

So, my question is, if I wanted to have another 8 cores start looking at a different keyspace, some arbitrary space from N bits in size, knowing that it would eventually hit a key, say

3d94cd64

What would be a good way to start the attack on that keyspace, eventually hitting that key?

Would I just specify -I as

(removing leading zeros) 3d94cd63? (Notice I just subtracted one from the right side). So it would check that key, then move onto the target key of 3d94cd64 and find it?

My thinking is that it will increment up, starting at (say) 3d94cd00, then go:

3d94cd00 3d94cd01 3d94cd02 3d94cd03 3d94cd04 and so on to eventually hit 3d94cd64

Is my thinking correct? Does the question make sense so far?

Suppose I wanted to leave it running a time, and give the -I 3d940000 start point, then it would take 3d94cd64 (target) - 3d940000 (start for -I ) = CD64 key checks until it hit my target?

Or do the numbers go out "left" (until it finds one), so if I start with -I

0000000000000000000000000000000000000000000000000000000000010000

and I want to hit target

0000000000000000000000000000000000000000000000000000000000556e52

will it cycle through 10000, 10001, 10002, 10003, ... 11000, ... 1e000 ... df000 ... (next digit "left") 1ef600 ... 200000 ... 300000 ... 550000 ... up to target 556e52 ?

In terms of absolute difference, it would start from 10000 hex and cycle through "left", to check 546E52 (hex) keys until it hits the target of 556e52 ?

I hope this makes sense, because I want a start point for a 24-bit keyspace and time it to eventually hit my target with the output of

0abcd00000....:c:(hex)priv:0000000000000000000000000000000000000000000000000000000000556e52

I hope I explained that reasonably well, did it make any sense? I want to start searching that larger keyspace with -n 1/8, 2/8 ... 8/8 and find an -I to start with that's smaller than my expected target, so I can discover how long it might take 8 brainflayer instances to reach my known target.

Another question: does it make any sense to do this?

./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000000001 -b addrs.blf -n 1/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000000300 -b addrs.blf -n 2/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000000600 -b addrs.blf -n 3/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000000900 -b addrs.blf -n 4/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000000c00 -b addrs.blf -n 5/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000000f00 -b addrs.blf -n 6/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000001200 -b addrs.blf -n 7/8 ./brainflayer -v -I 000000000000000000000000000000000000000000000000000000000001500 -b addrs.blf -n 8/8

Or of course with much larger number differences for each start point of brainflayer, so they don't all start at the same point to reach a target?

Or would I start with the same start point for all 8 instances, and a much larger start point for another 8 instances, keeping the start point the same for each x/8?

Thank you! Now I think I am starting to understand how it works and to tune it for experiments a little better.