[ARCHIVE] Bitcoin challenge discusion

[almightyruler]

How much time should a search for a 50-bit key take? If I put a 50-bit key in a 50-bit range, this happens quickly, but a 32-bit key in a 50-bit range has not yet been found.

Here's a quick test when running with bits=xxx and the pubkey which cracks to a 32 bit privkey...

32 = 137954 jumps
33 = 359156 jumps (2.6X)
34 = 1826684 jumps (13.2X)
35 = 3512423 jumps (25.5X)

Looks like the work increases exponentially when the bits you specify are significantly different to the actual bits in the recovered key.

[Firebox]

How much time should a search for a 50-bit key take? If I put a 50-bit key in a 50-bit range, this happens quickly, but a 32-bit key in a 50-bit range has not yet been found.

[racminer]

Suppose I know that the private key for the public (32 bit) 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69 is in the range of 1-50 bits, can I run a script with an unknown bit size in the range of 1-50?

The Pollard-Kangaroo script from this message seems to find keys even when the specified bit size doesn't match the key mask, but it does take longer. I guess the bits parameter is a hint at where to start searching, rather than a maximum search space limit.

For example, both of these runs will find key #32 (b862a62e)

pollard_kangaroo.py 34 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69

pollard_kangaroo.py 30 0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69

True,
Kangaroos might indeed cross boundaries. I ran the script by specifying an initial interval [a b] and I noticed that I still get the correct answer even when the  solution does not belong to [a b].

I was able to retrieved case #62 private key 363D541EB611ABEE in  8122.18 sec.   (running 4 instances of the script  by splitting the interval in 4 pieces at 160000 h/s per core)

[Hurtson]

Congratulations to the winner who had found the #62  

I wonder which was the privkey  

Pubkey is 03231a67e424caf7d01a00d5cd49b0464942255b8e48766f96602bdfa4ea14fea8

I'm going to try cracking it with baby step giant step, but I think I'm right at the edge of memory that my compiler can allocate for the table. Trying it anyway.

Hopefully the person who claimed the prize is just waiting for several confirms before revealing the details. Or they're asleep

Great! Thanks for your help.

I'm trying with the Pollard Kangaroo script. Let's see how much it'll take  

can anyone share kangaroo script for CPU please?

[vimp666]

Congratulations to the winner who had found the #62  

I wonder which was the privkey  

Pubkey is 03231a67e424caf7d01a00d5cd49b0464942255b8e48766f96602bdfa4ea14fea8

I'm going to try cracking it with baby step giant step, but I think I'm right at the edge of memory that my compiler can allocate for the table. Trying it anyway.

Hopefully the person who claimed the prize is just waiting for several confirms before revealing the details. Or they're asleep

Great! Thanks for your help.

I'm trying with the Pollard Kangaroo script. Let's see how much it'll take  

can anyone share kangaroo script for CPU please?

you read this topic more closely and you will see 2 scripts
https://bitcointalk.org/index.php?topic=5166284.msg52379137#msg52379137
https://bitcointalk.org/index.php?topic=5166284.msg52318676#msg52318676
choose
and the original script http://fe57.org/forum/thread.php?board=4&thema=1

[PrivatePerson]

I was able to retrieved case #62 private key 363D541EB611ABEE in  8122.18 sec.   (running 4 instances of the script  by splitting the interval in 4 pieces at 160000 h/s per core)

It is a pity that this can be done only after an outgoing transaction
Can your script modification distinguish between compressed and uncompressed addresses?
If I understand correctly, the script does not stop at the specified range and if the key contains more bits, then the script starts to search for infinitely long?

[almightyruler]

I was able to retrieved case #62 private key 363D541EB611ABEE in  8122.18 sec.   (running 4 instances of the script  by splitting the interval in 4 pieces at 160000 h/s per core)

It is a pity that this can be done only after an outgoing transaction

So then it's good that Bitcoin clients typically send to a hash of the public key (P2PKH), rather than the public key itself (P2PK).

With some of the weaker keys, it would be possible for a selfish miner to:

1. Watch for transactions which redeem puzzle funds,
2. Extract the pubkey from the mempool transaction created by the puzzle solver,
3. Crack the privkey using Pollard or BSGS,
4. Use the privkey to create a new transaction which overrides the first, and include it in the next block they mine.

My old Xeon server can crack a 51 bit key (using BSGS) in around 5 minutes, and 52 bits in around 12 minutes (edit: with a larger table it can crack much faster, eg 57 bits in 13 minutes), so the chances of a successful attack on a similarly weak key seem good. Such an attack would be of little use now, since the weaker keys were found (presumably by brute force?) long ago. I guess if the person claiming the puzzle prize didn't include a sufficient transaction fee, the time for the attacker to crack the key would be higher.

[pooya87]

I was able to retrieved case #62 private key 363D541EB611ABEE in  8122.18 sec.   (running 4 instances of the script  by splitting the interval in 4 pieces at 160000 h/s per core)

It is a pity that this can be done only after an outgoing transaction

So then it's good that Bitcoin clients typically send to a hash of the public key (P2PKH), rather than the public key itself (P2PK).

With some of the weaker keys, it would be possible for a selfish miner to:

1. Watch for transactions which redeem puzzle funds,
2. Extract the pubkey from the mempool transaction created by the puzzle solver,
3. Crack the privkey using Pollard or BSGS,
4. Use the privkey to create a new transaction which overrides the first, and include it in the next block they mine.

My old Xeon server can crack a 51 bit key (using BSGS) in around 5 minutes, and 52 bits in around 12 minutes, so the chances of a successful attack on a similarly weak key seem good. Such an attack would be of little use now, since the weaker keys were found (presumably by brute force?) long ago. I guess if the person claiming the puzzle prize didn't include a sufficient transaction fee, the time for the attacker to crack the key would be higher.

that's not why we are using hash of the public key. the hash is used because if in case some day there was a way to solve ECDLP faster the funds could remain safer. otherwise right now with what we have as algorithms and hardware to find the private key by just having the public key.
256 bit is HUGE. and "bitcoin clients" don't create weak keys. you have to go out of your way to create a key that has so much zeros like this:

Code:

000000000000000000000000000000000000000000000000000efae164cb9e3c

even with broken RNG it is still impossible to get something like that!

additionally there are lots and addresses that are reused, meaning they have revealed their public key already. if it were possible to break anything they would have been broken already.

[almightyruler]

My old Xeon server can crack a 51 bit key (using BSGS) in around 5 minutes, and 52 bits in around 12 minutes, so the chances of a successful attack on a similarly weak key seem good. Such an attack would be of little use now, since the weaker keys were found (presumably by brute force?) long ago. I guess if the person claiming the puzzle prize didn't include a sufficient transaction fee, the time for the attacker to crack the key would be higher.

that's not why we are using hash of the public key. the hash is used because if in case some day there was a way to solve ECDLP faster the funds could remain safer. otherwise right now with what we have as algorithms and hardware to find the private key by just having the public key.
256 bit is HUGE. and "bitcoin clients" don't create weak keys. you have to go out of your way to create a key that has so much zeros like this:

Code:

000000000000000000000000000000000000000000000000000efae164cb9e3c

even with broken RNG it is still impossible to get something like that!

additionally there are lots and addresses that are reused, meaning they have revealed their public key already. if it were possible to break anything they would have been broken already.

I wasn't suggesting that Bitcoin itself was vulnerable to pubkey->privkey attacks; this is the Bitcoin challenge thread, so of course we are talking about deliberately weak keys.

I think my suggestion still stands: if output #62 had been solved, but the fee was low, it's conceivable that someone else could have cracked the privkey before the transaction was incorporated into a block, then published their own transaction. It would be even easier for the lower range puzzle outputs.

I'm not a cryptographer, but the fact that you can crack a 62 bit key in a couple of hours IF you know the pubkey, versus "conceivably never" if you only know the RIPEMD160 hash of the pubkey, seems to suggest that the hashing does add a significant extra level of protection. Even accounting for 62 used bits being very weak when compared to 256.

Messed up privkeys are not impossible either. Creating a truly random private key is a fundamentally important part of Bitcoin, but I'm sure mistakes have been made, either by accident, or just through sloppy coding. Check out how mtgox lost 2609 BTC (not privkey related, but buggy coding related) : https://bitcointalk.org/index.php?topic=50206.0

Imagine silly code like this:

Code:

#define KEY_LEN 8                      /* 8 x 32 bits */
uint32_t key[KEY_LEN];                 /* 32 bytes */
create_random_key(&key);
memcpy(somewhere_else, key, KEY_LEN);  /* oops. only copies 8 bytes of key, instead of 32 */

And here's an example of where (I believe) a weak key was used in error: the key '7b7' (only 11 bits used) was sent 0.25 BTC a few months ago: https://www.blockchain.com/btc/address/1FJJTKza3HovjzguAnMY9VYPu5Kd6CRKa

I am guessing the sender was NOT intending to give away nearly $2k worth of BTC to a sweeper bot!

[PrivatePerson]

https://btcmanager.com/vulnerability-in-javascript-function-may-mean-long-term-bitcoin-hodlers-are-at-risk/?q=/vulnerability-in-javascript-function-may-mean-long-term-bitcoin-hodlers-are-at-risk/&
as I understand it, the entire range of 48 bits is already scanned?

[paniker]

anyony start in ubuntu 2+ gpu in bitcrack? how to do this?

[Hurtson]

Hello I see this today, I was trying to solve #105 puzzle, but  i see it solving time today, nearly 4700 years to solve,I think this is random search, how it can be  take too long time, no chances to find it early that mean?

-------|-----------|-----------------------------
 2^bits| (avg)jump | (avg)time
-------|-----------|-----------------------------
 2^010 |        74 |   0y  0m  0d 00:00:00s 000ms
 2^011 |       104 |   0y  0m  0d 00:00:00s 001ms
 2^012 |       148 |   0y  0m  0d 00:00:00s 001ms
 2^013 |       209 |   0y  0m  0d 00:00:00s 002ms
 2^014 |       296 |   0y  0m  0d 00:00:00s 002ms
 2^015 |       418 |   0y  0m  0d 00:00:00s 004ms
 2^016 |       592 |   0y  0m  0d 00:00:00s 005ms
 2^017 |       837 |   0y  0m  0d 00:00:00s 008ms
 2^018 |      1184 |   0y  0m  0d 00:00:00s 011ms
 2^019 |      1675 |   0y  0m  0d 00:00:00s 016ms
 2^020 |      2369 |   0y  0m  0d 00:00:00s 023ms
 2^021 |      3350 |   0y  0m  0d 00:00:00s 033ms
 2^022 |      4738 |   0y  0m  0d 00:00:00s 047ms
 2^023 |      6701 |   0y  0m  0d 00:00:00s 067ms
 2^024 |      9477 |   0y  0m  0d 00:00:00s 095ms
 2^025 |     13403 |   0y  0m  0d 00:00:00s 134ms
 2^026 |     18955 |   0y  0m  0d 00:00:00s 190ms
 2^027 |     26807 |   0y  0m  0d 00:00:00s 269ms
 2^028 |     37911 |   0y  0m  0d 00:00:00s 381ms
 2^029 |     53615 |   0y  0m  0d 00:00:00s 539ms
 2^030 |     75823 |   0y  0m  0d 00:00:00s 762ms
 2^031 |    107230 |   0y  0m  0d 00:00:01s 078ms
 2^032 |    151647 |   0y  0m  0d 00:00:01s 525ms
 2^033 |    214461 |   0y  0m  0d 00:00:02s 157ms
 2^034 |    303294 |   0y  0m  0d 00:00:03s 051ms
 2^035 |    428922 |   0y  0m  0d 00:00:04s 315ms
 2^036 |    606588 |   0y  0m  0d 00:00:06s 103ms
 2^037 |    857845 |   0y  0m  0d 00:00:08s 631ms
 2^038 |      1.2M |   0y  0m  0d 00:00:12s 206ms
 2^039 |      1.7M |   0y  0m  0d 00:00:17s 262ms
 2^040 |      2.4M |   0y  0m  0d 00:00:24s 412ms
 2^041 |      3.4M |   0y  0m  0d 00:00:34s 525ms
 2^042 |      4.9M |   0y  0m  0d 00:00:48s 825ms
 2^043 |      6.9M |   0y  0m  0d 00:01:09s 050ms
 2^044 |      9.7M |   0y  0m  0d 00:01:37s 651ms
 2^045 |     13.7M |   0y  0m  0d 00:02:18s 100ms
 2^046 |     19.4M |   0y  0m  0d 00:03:15s 303ms
 2^047 |     27.5M |   0y  0m  0d 00:04:36s 200ms
 2^048 |     38.8M |   0y  0m  0d 00:06:30s 607ms
 2^049 |     54.9M |   0y  0m  0d 00:09:12s 401ms
 2^050 |     77.6M |   0y  0m  0d 00:13:01s 214ms
 2^051 |    109.8M |   0y  0m  0d 00:18:24s 803ms
 2^052 |    155.3M |   0y  0m  0d 00:26:02s 428ms
>2^053 |    219.6M |   0y  0m  0d 00:36:49s 607ms
 2^054 |    310.6M |   0y  0m  0d 00:52:04s 856ms
 2^055 |    439.2M |   0y  0m  0d 01:13:39s 214ms
 2^056 |    621.1M |   0y  0m  0d 01:44:09s 712ms
 2^057 |    878.4M |   0y  0m  0d 02:27:18s 428ms
 2^058 |      1.2G |   0y  0m  0d 03:28:19s 424ms
 2^059 |      1.8G |   0y  0m  0d 04:54:36s 856ms
 2^060 |      2.5G |   0y  0m  0d 06:56:38s 849ms
 2^061 |      3.5G |   0y  0m  0d 09:49:13s 712ms
 2^062 |      5.0G |   0y  0m  0d 13:53:17s 698ms
 2^063 |      7.0G |   0y  0m  0d 19:38:27s 424ms
 2^064 |      9.9G |   0y  0m  1d 03:46:35s 397ms
 2^065 |     14.1G |   0y  0m  1d 15:16:54s 848ms
 2^066 |     19.9G |   0y  0m  2d 07:33:10s 795ms
 2^067 |     28.1G |   0y  0m  3d 06:33:49s 696ms
 2^068 |     39.8G |   0y  0m  4d 15:06:21s 591ms
 2^069 |     56.2G |   0y  0m  6d 13:07:39s 392ms
 2^070 |     79.5G |   0y  0m  9d 06:12:43s 183ms
 2^071 |    112.4G |   0y  0m 13d 02:15:18s 784ms
 2^072 |    159.0G |   0y  0m 18d 12:25:26s 367ms
 2^073 |    224.9G |   0y  0m 26d 04:30:37s 568ms
 2^074 |    318.0G |   0y  1m  7d 00:50:52s 735ms
 2^075 |    449.8G |   0y  1m 22d 09:01:15s 136ms
 2^076 |    636.1G |   0y  2m 14d 01:41:45s 471ms
 2^077 |    899.5G |   0y  3m 14d 18:02:30s 272ms
 2^078 |      1.3T |   0y  4m 28d 03:23:30s 942ms
 2^079 |      1.8T |   0y  6m 29d 12:05:00s 544ms
 2^080 |      2.5T |   0y  9m 26d 06:47:01s 884ms
 2^081 |      3.6T |   1y  1m 29d 00:10:01s 089ms
 2^082 |      5.1T |   1y  7m 22d 13:34:03s 769ms
 2^083 |      7.2T |   2y  3m 28d 00:20:02s 179ms
 2^084 |     10.2T |   3y  3m 15d 03:08:07s 538ms
 2^085 |     14.4T |   4y  7m 26d 00:40:04s 359ms
 2^086 |     20.4T |   6y  7m  0d 06:16:15s 076ms
 2^087 |     28.8T |   9y  3m 22d 01:20:08s 718ms
 2^088 |     40.7T |  13y  2m  0d 12:32:30s 152ms
 2^089 |     57.6T |  18y  7m 14d 02:40:17s 437ms
 2^090 |     81.4T |  26y  4m  1d 01:05:00s 304ms
 2^091 |    115.1T |  37y  2m 28d 05:20:34s 875ms
 2^092 |    162.8T |  52y  8m  2d 02:10:00s 608ms
 2^093 |    230.3T |  74y  5m 26d 10:41:09s 750ms
 2^094 |    325.7T |  105y  4m  4d 04:20:01s 216ms
 2^095 |    460.6T |  148y 11m 22d 21:22:19s 500ms
 2^096 |    651.3T |  210y  8m  8d 08:40:02s 433ms
 2^097 |    921.1T |  297y 11m 15d 18:44:39s 000ms
 2^098 |      1.3P |  421y  4m 16d 17:20:04s 867ms
 2^099 |      1.8P |  595y 11m  1d 13:29:18s 000ms
 2^100 |      2.6P |  842y  9m  3d 10:40:09s 735ms
 2^101 |      3.7P |  1191y 10m  3d 02:58:36s 000ms
 2^102 |      5.2P |  1685y  6m  6d 21:20:19s 471ms
 2^103 |      7.4P |  2383y  8m  6d 05:57:12s 000ms
 2^104 |     10.4P |  3371y  0m 13d 18:40:38s 942ms
 2^105 |     14.7P |  4767y  4m 12d 11:54:24s 000ms
 2^106 |     20.8P |  6742y  0m 27d 13:21:17s 885ms
 2^107 |     29.5P |  9534y  8m 24d 23:48:48s 000ms
 2^108 |     41.7P |  13484y  1m 25d 02:42:35s 771ms
 2^109 |     59.0P |  19069y  5m 19d 23:37:36s 000ms
 2^110 |     83.4P |  26968y  3m 20d 05:25:11s 542ms
 2^111 |    117.9P |  38138y 11m  9d 23:15:12s 000ms
 2^112 |    166.7P |  53936y  7m 10d 10:50:23s 085ms
 2^113 |    235.8P |  76277y 10m 19d 22:30:24s 000ms
 2^114 |    333.5P |  107873y  2m 20d 21:40:46s 171ms
 2^115 |    471.6P |  152555y  9m  9d 21:00:48s 000ms
 2^116 |    667.0P |  215746y  5m 11d 19:21:32s 342ms
 2^117 |    943.2P |  305111y  6m 19d 18:01:36s 000ms
 2^118 |      1.3E |  431492y 10m 23d 14:43:04s 685ms
 2^119 |      1.9E |  610223y  1m  9d 12:03:12s 000ms
 2^120 |      2.7E |  862985y  9m 17d 05:26:09s 371ms
[################################################]

[Darmont33]

anyony start in ubuntu 2+ gpu in bitcrack? how to do this?

I am also interested in this question, rent of several farms. But I think that the answer will be in several different bitcrack folders and several terminals

[racminer]

anyony start in ubuntu 2+ gpu in bitcrack? how to do this?

just run many instances of  bitcrack  changing the device number - d to 0 1 2 etc...

[bulleteyedk]

I just installed an older GTX 780 3GB card today, and did some dial-in on the settings, to max performance of MKeys/sec

I managed to get 168.7 MKeys/sec running cubitcrack, with these parameters: -b 48 -t 512 -p 980

[Raj Lassi]

found an old Radeon 5770 in my junk pile.  should have left it there.
hot-glued the fan back on.
bought a 6-pin power cable and everything.  2 day delivery.
thought i would run some openCL.
but legacy ATI + linux don't mix. 

[MeBender]

hey guys what is the key range for 64 bit address? I'm having trouble figuring out how to calculate key bit ranges and google doesn't turn anything up

[Hurtson]

hey guys what is the key range for 64 bit address? I'm having trouble figuring out how to calculate key bit ranges and google doesn't turn anything up

 ( In Decimal )
for #64

start = 2^ 63    =    9223372036854775808
end  = 2^ 64-1 =    18446744073709551615


use this site to convert decimal to hex https://www.rapidtables.com/convert/number/hex-to-decimal.html

[almightyruler]

use this site to convert decimal to hex https://www.rapidtables.com/convert/number/hex-to-decimal.html

Windows Calculator will also convert between hex and decimal when you're in Programmer mode (View -> Programmer, or Alt+3)

There's probably an equivalent for MacOS, Ubuntu etc.

[adaseb]

snip

That is actually pretty impressive and shows how much quicker Bitcrack is compared to the Vanitygen that I used in the past. When I first heard about this contest I had a few idle Radeon 7970/280X GPUs that couldn't mine ETH anymore and did nothing but collect dust. So I decided to try and find one of the #53 (or #54 ) private keys since this was a few years back.

Basically had to manually tweak the vanitygen software so it allowed sequential private keys and when I got it finally working I think my max speed was like 20 MKyes/second on a R9 280X. Also it was badly designed because if you added a second GPU it would run at like 15MKyes/second each and it wasn't efficent at all.

So you getting this speed is pretty impressive from that old GPU.