What makes a sextillion-key wallet crackable?

[hmbdofficial]

So I stumbled upon this post on X and I was wondering, if a weak key space  make bitcoin brute-forceable? And If  the wallet was intentionally created with a much smaller key space, then was the sextillion key range chosen? And what make the challenge practical enough for someone with a GPU to search?

Also, how can we be sure the original private key wasn’t generated using proper 256 bit entropy? I thinking the weakness here seems to be the key generation method rather than the bitcoin’s cryptography itself would be glad to hear your inputs.
https://x.com/bitcoinnewscom/status/2089684716190421334?s=46

[philipma1957]

that number is a 1 followed bt 21 zeros


1,000,000,000,000,000,000,000

google how many bits in that number


and you get there are 70 bits needed


so it is a shit seed


a better puzzle would have been give a trezor seed out.

but put in a long ass passphrase

https://www.amazon.com/gp/product/B079Y9YBWB/ref=ox_sc_act_title_1?

1000 number tags 001 to 1000

pick 16 of them at random

first pick is 1/1000
second pick is 1/999 because you do not return the numbers so

1000x999x998x997=994,010,994,000  just under a trillion
 996x995x994x993= 978,178,362,840  just under a trillion
 992x990x989x988 =962,535,625,920 just under a trillion



then google how many bits in. 994,010,994,000 x 978,178,362,840 x 962,535,625,920 ai mode

the answer would be  120 bits

now trezor can do a 50 character passphrase

so picking the numbers above would likely be 36 characters long which can be fit into Trezor's passphrase set up

you could even make one with

1000x999x998x997=994,010,994,000  just under a trillion
 996x995x994x993= 978,178,362,840  just under a trillion
 992x990x989x988 =962,535,625,920 just under a trillion

and

987x986x985x984= 943,246,921,680 just under a trillion

this would be 40 more bits or 120+40=160

and it would be 16x3=48 characters long  even if you pick 1000 if you write that number as 000


if I where rich I would make a 1 coin and 5 coin puzzle

one would be with the 36 character puzzle 1 btc
one would be with the 48 character puzzle 5 btc

the descending number count is cause by not putting the picked numbers back in to the set of 1000 numbers.

you could put the numbers back

the math is

1000x1000x1000x1000=1×10¹²  1 trillion 40 bits
1000x1000x1000x1000=1×10¹²  1 trillion 80 bits
1000x1000x1000x1000=1×10¹²  1 trillion 120 bits should be good
1000x1000x1000x1000=1×10¹²  1 trillion 160 bits should be good.

[athanred]

if a weak key space  make bitcoin brute-forceable?

Of course. Here you can trace the progress of the puzzle: https://mempool.space/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

Also, how can we be sure the original private key wasn’t generated using proper 256 bit entropy?

We don't. We would need a DLEQ proof, or something similar, to be sure.

then was the sextillion key range chosen?

Each private key is in range between 1 and 115792089237316195423570985008687907852837564279074904382605163141518161494336. If you use some key in a smaller range, then it is more likely, that people will find it.

And what make the challenge practical enough for someone with a GPU to search?

The more you know about the private key, the easier it is to break. Here, the creator chose different ranges for different keys. The first key is equal to 1. The second is in range from 2 to 3. The third from range in 4 to 7. And so on, and so forth. People are now trying to break 71th hashed key, and 140th public key.

[philipma1957]

To me a puzzle with a 120 bit puzzle is of interest mostly to see if it gets cracked

I think the 160 bit puzzle using 16 picked numbers is not crackable

But I do wonder if the 120 could get cracked.

I also wonder if the 1000 tags picked from a box is random enough.

It likely is.

[Antidote47k]

Also, how can we be sure the original private key wasn’t generated using proper 256 bit entropy?

We don't. We would need a DLEQ proof, or something similar, to be sure.

Interestingly the problem doesn’t seem to be Bitcoins 256 bit private key itself but the amount of information we have about the key before the brute force even begins. Let’s say the attacker knows that the key was deliberately generated from such a small range, the security is no longer close to the full Bitcoin keyspace, the more information an attacker has about how the key was generated, the smaller the remaining search space becomes.

I’m also wondering if we only have the address and the public key/hash on chain, will it be possible to tell wether the private key behind it was generated with proper 256 bit entropy or from a weak process? If we can’t from blockchain alone, then the security of a wallet essentially depends on how the private key was generated in the first place, even though the resulting address looks exactly like any other bitcoin address

[BlackHatCoiner]

You're looking at Puzzle #71 from the famous 2015 Bitcoin Puzzle Transaction. Someone intentionally crippled the private key back in 2015 as a cryptographic bounty game, there is nothing wrong with Bitcoin's cryptography.

The creator funded 160 puzzles with increasing bit lengths. Puzzle #1 had a 1-bit key, Puzzle #2 had 2 bits, and Puzzle #71 has a 71-bit key (2^70 to 2^71 - 1). That range is roughly 1.18 sextillion keys. On my RTX 4080 it takes ~9,350 years to search 50% of that space. 

[Danish Ali]

I think that there must be misunderstanding in this thread between two things: "weak randomness" and a "deliberately small search range". It's a slightly different story.

In this kind of wallets (puzzles), the private key is not sampled from a wide range. It was sampled from a narrow spectrum of locations. This was stated by the creator from the beginning: that this is one of the possible keys between 2^{70} and 2^{71}-1 for puzzle number 71. No leakage and never any approximation. This range is limited, focused on purpose, and is explicitly discussed with everyone involved.

This means that you don't have to come up with a DLEQ proof or anything elegant here — there's no weak point to reveal. All of the ranges are public, as there's not really any point to the puzzle if they weren't.

Conversely, think about a "real" wallet: if you had a "real" random key of 256 bits, then the search space remains at the full 2^{256}. It does not become crackable simply because someone wishes to search it, given that no errors are committed in the creation process, such as using a bad random number generator.

Thus directly answering OP's question: No, it is not because of the cryptography in Bitcoin, nor for any "improper randomness". It is a wallet intentionally designed with a limited and transparent set of options to be used as a game. This is not the case with a normal wallet as long as its RNG is not bad.

[athanred]

you don't have to come up with a DLEQ proof or anything elegant here

Then, it is all about trusting the creator, that all private keys are in proper ranges. But solvers have no way to verify that claim. What if the code was buggy, and some keys were out of range? For example:

Code:

00000000000000000000000000000000000000000000000000000000badc0ded   03BA7E94B974384B9B3D2975C52FDFE901837C47EB78F0C0BA2C382523E6158B5A
10000000000000000000000000000000000000000000000000000000badc0ded   0255AA07B46EC64663FB3DD3B825A092459E85270456EB5C3A1AF96D2DF81B2572

Let's assume, that you know only 0255AA07B46EC64663FB3DD3B825A092459E85270456EB5C3A1AF96D2DF81B2572. How do you know, that this public key contains a private key in range between 2^31 and 2^32? You don't. You simply trust the creator.

there's no weak point to reveal

Of course. But there is also no proof, that all private keys are in proper ranges.

All of the ranges are public, as there's not really any point to the puzzle if they weren't.

But nobody, except the creator, knows, if all private keys are generated correctly. There always could be some bugs. Also, for all hash-based puzzles you don't know, if someone really solved the next puzzle, or if the creator just moved it, and the community found the private key later, when the public key was revealed.