Topic: Keys and such like - can they be rebuilt from partial? (Read 307 times)

Estimating the global average hashrate nowadays at around 8 EH/s (≈ 2⁶³ H/s), Bitcoin miners collectively do on the order of 2⁶⁴ work literally every two seconds.  That is, all miners in the world put together.  To do 2¹²⁸ work would still take them more than one trillion years (l(2^65)/(365.2425*86400))/l(10) ≈ 12.07).  To do 2²⁵⁶ work—forget about it.  What’s 2¹²⁸ × 1 trillion years?

Adding one bit doubles the amount of work needed to bruteforce.  Doubling the number of bits squares the amount of work needed to bruteforce.  To bruteforce 64 bits of key is within the reach of distributed computing, or powerful entities with supercomputers.  To bruteforce 128 bits is humanly impossible, and likely always will be.  Since it is theoretically possible, cryptographers prefer the term “computationally infeasible” to “impossible”.

---

Your report stats as of September 2017 provide one of the reasons why I know to heed your advice on this topic.

Quote from: DannyHamilton on January 04, 2018, 11:36:14 AM

Quote from: nullius on January 04, 2018, 11:08:00 AM

The babble of “bitfools”?  That’s a tough call.  Bizarre, essentially substance-free nonsense does not belong on a technical discussion forum.  But if it is here, then somebody does need to step up and point out the stupidity

I agree. The options as I see it are either the post gets removed, or it needs to be responded to.  Ignoring the troll won't work in that particular situation.  There is too much risk that a newbie won't realize it is nonsense, and then they'll repeat it elsewhere.  That's how bad information gets incorporated into "Common knowledge".

Too true.  The Earth is not flat, no compressor can reduce the length of all strings, and Segwit does not remove signatures.  But if somebody has resources to push an agenda, we can repeat ourselves all day and still be drowned out.  Moreover, there must be another line between spiking urban myths in embryonic form, and dutifully replying to nonsense which no reasonably intelligent person would find credible.  Perhaps patterns should be developed of providing brief pointers to concise sources of good information, à la the Usenet “read the FAQ section x.y.z” response.

Quote from: DannyHamilton on January 04, 2018, 11:36:14 AM

Quote from: nullius on January 04, 2018, 11:08:00 AM

without any attempt to soften and sugar-coat the response with undeserved niceness.

The niceness isn't for the sake of the fool.  The niceness is to increase the likelihood that everyone else that stumbles across the thread will be receptive to what I say. (I can get a bit snarky or passive-aggressive at times though).

Well, that is a matter of tact; and I suppose we have a difference of style, perhaps even a difference of opinion.  “In real life”, I am formally courteous to a fault; and I have patience, when I deem fit.  But also “in real life”, I am scathingly sarcastic and active-aggressive in giving short shrift to nonsense.  I am not simply a “keyboard warrior”.  I will call a spade a spade.  I hurt people’s feelings, if they deserve it—not people who make occasional dumb mistakes, as does everybody (including me), but those who are blatantly wrong, incorrigible, ineducable.  And I respect those who do similarly.

Some of the leading Core developers are oft criticized for some alleged lack of “niceness”, usually as perceived by people who are wrong.  To me, that shows only that they are strong, self-confident, and uncompromising.  I also don’t mind seeing djb more or less outright call his colleagues idiots in published papers; sometimes, they are idiots.  Though I am not a Linux fan, I do respect the Torvalds management style.  Yes, I am an unabashed elitist.

So as for authors—and so too as for readers.  Perhaps readers who need diplomatic saccharine are not worth convincing.  A reader who sincerely desires knowledge will care only if I be correct, not whether I have been “nice” in pointing out something wrong; whereas a reader who rejects knowledge due to lack of “niceness” to a third party in the discussion is not worthy of my time, anyway.  That is my opinion.

(Etymological side note:  The word “nice” once upon a time meant “foolish, stupid”.  I find that most fitting, a delicious historical irony.)

Quote from: DannyHamilton on January 04, 2018, 11:36:14 AM

Note: we seem to have wandered of thread topic here.  This conversation probably belongs in Meta.  I cetainly won't mind if a mod splits this thread and moves this part to Meta for us. (I don't think we can split our posts to a new thread ourselves, can we?)

Good call.  I’ll take this up further, if it gets split or moved; and otherwise, I’ll fully understand if you don’t.  I don’t know any means of splitting a topic.  This thread has already spawned an offshoot in Meta, q.v., to which it may be suitable to move posts from here; and I don’t mind editing and splitting out my above reply to TechPriest, if necessary.

The way I see it is this:

I draw my line where I want it.  I use that line to decide who I report, who I ignore, and who I respond to. Then I trust that the forum moderators have decided on their own line that they will use for actually removing posts.  If my line is too aggressive, they will ignore my report. If my line isn't aggressive enough, then they'll remove every post I report PLUS additional posts that I might have been okay with.  As long as I'm not wasting their time with a significant number of reports that they must ignore, I figure I'm helping them find the most problematic posts faster.

I guess my line must be okay, since I've reported over 4000 posts and I'm still at 99% accuracy.  If my accuracy ever drops below 90% I'll consider the possibility that I might have become overly sensitive to the nonsense.


Since this forum has an altcoin subforum, if it is a BCH thread, then I report it with "BCH: belongs in altcoin".

If it is a BCH post in an otherwise non-BCH thread, then I measure it against my own internal troll meter. Choosing between ignore them, respond to educate others, or report them to be deleted.


I agree. The options as I see it are either the post gets removed, or it needs to be responded to.  Ignoring the troll won't work in that particular situation.  There is too much risk that a newbie won't realize it is nonsense, and then they'll repeat it elsewhere.  That's how bad information gets incorporated into "Common knowledge".

If someone else already responded reasonably (as you did), then I'd just leave it at that. If nobody else responded yet and I had the time, I'd respond. If there is no response yet, and I don't have the time to respond, then I report it, and save a link so I can come back later when I have time and see what the status is.  If the moderator agreed with my report and removed it, then I'm done. If it's still there when I come back and nobody else has responded well yet, then I respond.


The niceness isn't for the sake of the fool.  The niceness is to increase the likelihood that everyone else that stumbles across the thread will be receptive to what I say. (I can get a bit snarky or passive-aggressive at times though).

Note: we seem to have wandered of thread topic here.  This conversation probably belongs in Meta.  I cetainly won't mind if a mod splits this thread and moves this part to Meta for us. (I don't think we can split our posts to a new thread ourselves, can we?)

We must admit that bruteforcing of 128 bit (second part of the key) it's impossible for now. Even bruteforcing 64 bits for ordinary hacker looks like impossible task. You need computer with calculating power like 100 000 GTX 970 (each GTX is about 40* 10⁶ numbers/second) to brute force 64 bit number in 2 years (1,46 years).  

Thanks for the advice.

My report stats currently say, “You have reported 144 posts with 100% accuracy”.  That is counting only since 1 December 2017, when I started to actively engage with the forum.  I am trying to help clean up the trash.

Yes, the mods do an heroic job.  In Meta, I have repeatedly likened their task to “emptying a landfill with a spoon—while the garbage trucks keep rolling in”.  I appreciate their efforts.


The question is, where should the line be drawn?  I generally applaud this forum’s policy of erring to the side of letting people express their opinions freely.  However, forums dissolve in noise when it is not required that opinions be at least moderately intelligent and plausibly well-expressed.

When considering horrible advice, linking to a trojan coin-stealer download is definitely over the line.  But what about when somebody advocates “brainwallets”?  I have seen you and gmaxwell respond to that with devastating efficacy!  Per what you say, the discussion must be had such that newbies can see the argument, and learn why brainwallets are an unequivocally bad idea.  Shilling for BCH?  That’s bad advice, insofar as it misleads newbies to a fraudulent fake Bitcoin; and it is simply offtopic on a Bitcoin forum.  In Meta, I have joined those (unsuccessfully) advocating that BCH shilling should be delete-on-sight.  (Lauda also had a good idea of negative-trusting BCH shills, which I would do if my trust rating carried any weight.)  The babble of “bitfools”?  That’s a tough call.  Bizarre, essentially substance-free nonsense does not belong on a technical discussion forum.  But if it is here, then somebody does need to step up and point out the stupidity—without any attempt to soften and sugar-coat the response with undeserved niceness.


Thanks.  I aim to raise the S/N ratio and not lower it, though sometimes I will flame away on a stupid thread which anyway refuses to die.  I do hope that the educational value of my post here exceeded the problems inherent in replying substantively to a troll, rather than ignoring it or brushing it off with a one-line “you’re an idiot—100% incorrect” reply.

When a newbie or sig-ad posts complete nonsense in either of the technical forums, I've taken to just hitting the "Report to moderator" link and typing "newbie nonsense in technical subforum" or "sig ad nonsense in technical subforum".

The moderators seem to do a pretty good job of cleaning all that crap out so that users can find useful help and intelligent conversation here.

Note, that I don't report someone that appears to be trying to understand and has just been mislead up until now.  It's those that are making ridiculous claims and giving horrible advice that don't belong here.

It's not enough to just ignore the trolls.  Those that are trying to learn are likely to be mislead by them.  We've got to actively work to get rid of their nonsense.

Also note, that I occasionally find it useful to engage with certain trolls, as it gives me an opportunity to point out to EVERYONE else that reads the thread exactly why their words are nonsense and their claims are false.  My hope is that as others search the internet looking for information on misleading things they've heard, they may stumble across the "conversation with a troll" and become enlightened to the truth.

Your response above looks like one of those opportunities.

The trick it to keep your cool, and calmly point out just how ridiculous and silly the troll's statements are.  You don't want people that are reading it to think you are just lashing out because you feel threatened. Instead, you want readers nodding their head in agreement with you as they think to themselves how silly and dumb the troll is.

Anger, threats, name calling, and other agressive behaviors tend to create a "us vs. them" situation where the reader feels defensive and emotionally may disregard what you say no matter how accurate or obvious it is.

Self-deprecating, light-hearted humor, clear examples, and passive behaviors tend to create an inclusive atmosphere where the reader is more interested in what you are saying, and less interested in why you are saying it.

Thanks for the tip.  Well, I suppose that IHBT.  I’ve been working to cultivate the habit of pausing when I see something inexplicably ridiculous, and glancing through post history before I hit the “reply” button.  I will try to do better with that in the future.

I've seen multiple threads in the past 24 hours where bitfools has shown up spouting nonsense as if he knows what he's talking about.

At first I thought he might just be misinformed and trying to be helpful.  I've come to realize that he's probably a troll that is knowingly intentionally trying to spread fear by using a bunch of familliar sounding words strung together in ways that don't make any sense to anyone that actually understands, but which sound scary to anyone that doesn't understand.

“bitfools”, username checks out.  You have no idea what you are talking about.

I don’t have a problem with newbies and non-experts who simply lack knowledge.  Nobody is omnicient.  But I have a big problem with fools who spout off stuff and nonsense self-evidently made up on the spot, and pass that off as “knowledge”.  If you don’t know, then say you don’t know—or shut up.  Each and every conclusion in your post was substantially incorrect.


No, it doesn’t.  Hex strings are only alternative representations of a binary value.  BIP 39 mnemonic phrases are also an encoding of a binary value (although that value is not used directly to create the binary seed).  In all these cases, they represent large integers.


In Bitcoin, private keys are 256 bits.  2²⁵⁶ ≈ 1.16×10⁷⁷; therefore, 256-bit numbers written in decimal require up to 78 digits.  Valid values for a Bitcoin private key include those from 0x1 (decimal 1; 1 digit) to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140.  If I did not make a dumb mistake, in decimal that latter equals 115792089237316195423570985008687907852837564279074904382606316063022768341312.  That number has 78 digits; count them.


How the hell is the block number relevant to this discussion?  No keys or address values are ever generated from the block number.  Moreover, half the digits of a value are half the digits; it makes no difference whether it is the first half or the last half.  To try all combinations of 502xxx requires 1000 guesses, 000–999; to check all combinations from xxx800 also requires 1000 guesses, 000–999.  (And if bruteforcing random values, on average you will only need to try 50% before you hit the right one.)

On the same principle, if you have half the bits of a 256-bit private key, it does not matter whether it be the first half, the last half, or some part in between (just as long as you know the offset).


Say what?  Hexadecimal (base16) values, and also the base58 values in WIF, only encode values which the computer decodes and handles in binary (base2, bits).


No, you cannot bruteforce 10–23 words of a BIP39 passphrase “super quick”.  It does not matter if you know the “algo”.  The “ALGO” is secure even if you know it.  If you know “just 1 or 2” words, then the work required to bruteforce the rest will range from 2¹¹⁰ to 2²⁵³.  There is nothing “super quick” about that!

Now, in the spirit of OP’s original question about knowing half the desired value:

Each word of a BIP 39 seed encodes 11 bits of randomness—except for the last word, which contains the lowest-orer bits of randomness plus a checksum value.  If you know the first 6 words of a 12-word seed, that means you know 66 bits of a 128-bit random value—slightly more than half.  Bruteforcing the rest will require 2⁶² work (128 - 66 = 62).  That can certainly be done by those with powerful compute clusters or through distributed computing; but it is not a task which could be considered “super quick”.

If you know the first 12 words of a 24-word seed, that means you know 12*11 = 132 bits of a 256-bit random value.  Bruteforcing the rest would require 2¹²⁴ work, which is infeasible even with a supercomputer.

I have thus far ignored the checksum bits.  In a 24-word phrase, all 24 words together represent a 264-bit value representing 256 bits of randomness, plus an 8-bit checksum; a 12-word seed represents 128 bits of randomness plus a 4-bit checksum.  By “exploiting” the checksum to discard values which do not match, you effectually remove the checksum; thus you can avoid running the results through 2048-iteration PBKDF2-SHA512, followed by the further hashing and EC maths required to generate addresses to check against.  I know I have not explained this well—I simply note it parenthetically, so as to not forget the checksum.  It’s not really relevant to this discussion.

By the way, this makes no sense whatsoever:  “Most of what ppl see in BTC is hex 'hashed' data, but when you talk key or seed then normally your talking the real deal, most dev's on BTC to prefer to hide this stuff from the user on theory he's too stupid to be trusted with his own data,”  Well, you are too stupid to be trusted with anything.

Well are you talking key like a BIT-INTEGER, or a seed 'in hex' or 'english'??

It really depends what you mean??

First step, take a step back and think about how this stuff works.

Seed is just that it feeds the box that generates a 'key', a key is just a BIG-NUMBER, it might have 70 base-10 digits, lets take a big number,

502800 which might be the current block number of bitcoin, the 502 will call the big-endian, the 800 the little endian, if your key is 502800, and you give me the first 502xxx then I only got to run from 1 to 800 through my 'crack box' that tests every address known for every  private-key in that range to match one of your addresses, super easy.

If you give me 800, it might take a super long time to 'guess' your address.

Now lets get real, your private key is normally seen as HEX or WIF, but in real when the work is done its a base ten number 1328921839L

...

WRT to your 'word' seed, a seed can be 12 random words that are hashed 2,000 times and a 64 char-random hex number is generated, the hashing isn't of any order so it doesn't help to know any part of your hash, on the other hand you give me the seed 'dog cat fish xxxx' where xxxx is what your forgot then I can run a dictionary on that  and hash all possible combo's until I generate a priv-key that hits your addresses.

...

Most of what ppl see in BTC is hex 'hashed' data, but when you talk key or seed then normally your talking the real deal, most dev's on BTC to prefer to hide this stuff from the user on theory he's too stupid to be trusted with his own data,

Your question about 1/2

say your seed is

'dog cat fish horse mule monkey fudge poop' [ who care 6,8,12,18, or 24 words ]

even if I have just 1 or 2 of these words, and I know your ALGO ( I know which wallet you used, then I can crack your private-key super quick )
 

“Nothing is especially safe”!?  You had better be worried about being killed by a flying fire hydrant than about bruteforce of Bitcoin’s cryptographic keys.  It has happened at least once somewhere that a man was killed by a flying fire hydrant.  Bruteforce of the type of crypto used in Bitcoin has never happened, and never will.

(More to the point, be worried about your computer’s security, theft, etc.  Bruteforcing of keys does not happen.  Stealing of keys happens oft.  But if you use hardware wallets and cold storage, you are already better protected than most people.)

hmm, ok - thanks for the replies so far. Makes sense. Nothing is especially safe in this game, I suppose! Although, I guess I am more worried about my Nano and its seeds than I used to be about cold storage keys, tbh.

Each bit is indeed independent of the others.  (Keys are made of bits, not characters.)  But that’s not the point:  If an attacker has half the key, then at worst from his perspective, he only needs to bruteforce half a key.

By analogy:  Imagine you have a combination lock which has a combination of 77 independent digits numbered 0–9.  (77 digits, because a 256-bit key has about 1.16×10⁷⁷ possible values.)  Now, an attacker has 39 of the digits of the combination.  The attacker can simply set those 39 digits, and work on the other 38.

The foregoing discussion considers only considers bruteforce attacks.

Well I doubt they would have any better then brute force way of figuring the other part of the key.
However you should understand that if someone has half of your key, they don't need to do half of the calculations that would be required for brute forcing the entire key. They would only need a square root of calculations, which for big numbers (as keys are) is a big difference.

For example if you have a 128 bit key, it is unlikely that anyone would be able of brute forcing your key. Not even the entire world, for perhaps thousand of years. But having a 64 bit key, well that is very insecure. Any developed government agency should be able to break that in reasonable time.
I can't give you exact calculations or even good guesses, but from experience I know that 128 bit keys are not rare at all, but I believe that even 80 bit keys are crackable by governments (I think cellphones use around 80 bit keys according to UK law or something).

My question relates to private keys, and also other "seeds" and similar strings that we want to keep private.

To what extent can they be rebuilt from a fragment? Don't worry, I haven't lost [part of] mine, but the question relates to how I can store them. For example, if someone had half of a key would they be able to derive the other half at a better-than-brute-force rate? Or is every character independent of every other, I guess I am asking.

And does this differ between coins, are there any notable difference?