Lost Half of Private Key - Are Bitcoins Safe?

[Bitcoin++]

Say that someone knows half a private key and the corresponding public address.
Can he find out the other half of the private key somehow?

... apart from brute forcing for a billion years 

[1714976817]

1714976817

[1714976817]

1714976817

[cp1]

It makes it 340282366920938463463374607431768211456 times easier to brute force.

So if you could guess 10^9 per second it'd only take you 10^24 years instead of 10^63 years.

[Baitty]

It makes it 340282366920938463463374607431768211456 times easier to brute force.

So if you could guess 10^9 per second it'd only take you 10^24 years instead of 10^63 years.

Nice math! But OP short answer. YES they are safe.

[S4VV4S]

Say that someone knows half a private key and the corresponding public address.
Can he find out the other half of the private key somehow?

... apart from brute forcing for a billion years 

Yes, you could give it to them 

[DeathAndTaxes]

It makes it 340282366920938463463374607431768211456 times easier to brute force.

So if you could guess 10^9 per second it'd only take you 10^24 years instead of 10^63 years.

256 bit ECDSA keys only have 128 bit security.  Half of an ECDSA key would be 64 bit security.  While a naive attack would be to increment all possible private keys there are more sophisticated attacks ( https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms ) which are of complexity O( n^(1/2) ) steps where n is the key length.

64 bit security would be breakable but it is very likely the cost to break they key would be greater than the reward.  Although if this isn't a hypothetical I would recommend transferring the coins now.

[cp1]

Yes, you could give it to them 

Yeah, it's far more likely they will find out the second half by the same method they found out the first half.
Also there's some possibility that there's some EC vulnerability if you know half of a key, but that's beyond my knowledge.

[ShakyhandsBTCer]

Say that someone knows half a private key and the corresponding public address.
Can he find out the other half of the private key somehow?

... apart from brute forcing for a billion years 

You would likely be safe.

There are certain sophisticated attacks that could be done to further narrow down the possibility of what the possibility the rest of your private key is.

To keep it simple, you will likely not have your coins stolen within seconds of someone finding your private key, but it would be advisable to cease using the subject BTC address right away and to move your coins at your earliest connivence.

Note: the corresponding public address does not matter, the attacker knowing this does not make a difference (besides the fact that an attacker may know that the address they are trying to "hack" contains x amount of bitcoin

[Meuh6879]

don't use storage wallet as "active wallet" ... the first principe of bitcoin 
you can't retrieve a thing if nobody (hacking machine) is connected to ...

[Bitcoin++]

It makes it 340282366920938463463374607431768211456 times easier to brute force.

So if you could guess 10^9 per second it'd only take you 10^24 years instead of 10^63 years.

256 bit ECDSA keys only have 128 bit security.  Half of an ECDSA key would be 64 bit security.  While a naive attack would be to increment all possible private keys there are more sophisticated attacks ( https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms ) which are of complexity O( n^(1/2) ) steps where n is the key length.

64 bit security would be breakable but it is very likely the cost to break they key would be greater than the reward.  Although if this isn't a hypothetical I would recommend transferring the coins now.

Thanks for answers.

Reason I asked is that I prefer to give half a key to Alice and Bob and the other half to Charlie and Dennis. I consider this a backup strategy in case something happens to me (so my family can inherit) or I lose my notes (e.g. house burns down). To add safety I could use multisig, but the risks to worry about should be elsewhere; may these conspire and steal my coins, did a screen capture see the private key, did I write them down without any typos?

[Parham6]

it'd only take you 10^24 years...

Sounds pretty unsecure to me, if you do that maybe someone's grand grand super grandest gran children could crack it in time?

[shorena]

-snip-
may these conspire and steal my coins, did a screen capture see the private key, did I write them down without any typos?

You could mitigate these risk.
Take the private key and split it in X parts.
Sign each part with the complete private key to make sure noone can temper with the parts.
Safe each pair (signature, part of the key and public key to verify the signature) in a textfile and encrypt each file symmetric with strong passwords.
Talk to a notar to set up your will and release the passwords through that.
Destroy all passwords afterwards (probably best to use some sort of hash as password, so cant "accidently" remember them yourself).
This way the notar cant steal your coins unless he/she works with A, B, C and D, which is unlikely.
Unless you brag that you have this fool proof system to protect your 150,000 Bitcoins

This would however make it pretty impossible to get your coins while you are still alive. Not sure if thats the sort of solution you are looking for. Maybe exchange the part with the will with something less drastic. E.g. Safe, sealed envelopes, lock box etc.


Edit:

-snip-
256 bit ECDSA keys only have 128 bit security.  Half of an ECDSA key would be 64 bit security.  While a naive attack would be to increment all possible private keys there are more sophisticated attacks ( https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms ) which are of complexity O( n^(1/2) ) steps where n is the key length.

64 bit security would be breakable but it is very likely the cost to break they key would be greater than the reward.  Although if this isn't a hypothetical I would recommend transferring the coins now.

I hope you can help me out here. I have a problem calculating the time needed to crack it under the following assumptions.

2⁶⁴ ~ 1,8 * 10¹⁹. If an attack could be done with a 1TH/s (~1*10¹²) miner, that would take roughly 1,7 * 10¹³ seconds or roughly 2 10⁸ days (556K years).
1 PH/s (~1,1*10¹⁵) miner would need 4,5 hours.

Is it possible to use a ASIC miner for that attack? The way I understand the code[1] sha256 isnt used, which would not allow an attacker to use ASICs, correct? So the best possible machine to attack would be something like sabre? [2]

According to djb sabre can do "... 3000000000000000000000 multiplications per year ..." so 3*10²¹/year or 9,5*10¹³/s

So that beast would plow through 2⁶⁴ multiplications/operations (?) in ~53 hours.

(?) but thats not what it has to do to crack the code, right?

To sum it up, I guess my questions are:
- How do I get from X bit code to Y bit security? (I assume the way to go is: find the best available algorithm for the problem and use the big O approximation) Not sure if this applies for this example since the way I understand OP we dont have the public key.
- How do I get from Y bit security to Z calculations. IIRC big O does this as well, but ...
I dont really know what my but is here, besides that I am a little afraid because I just realized how powerfull the sabre cluster actually is.



-------------

it'd only take you 10^24 years...

Sounds pretty unsecure to me, if you do that maybe someone's grand grand super grandest gran children could crack it in time?

9¹⁰ is very slow, thats a single core CPU running @ ~ 953 MHz, Not sure about the exact numbers but that sounds like trying to crack the code with your smartphone.



[1] https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms#Example
[2] http://blog.cr.yp.to/20140602-saber.html

[PangPang]

it'd only take you 10^24 years...

Sounds pretty unsecure to me, if you do that maybe someone's grand grand super grandest gran children could crack it in time?

10^ 24 = 1,000,000,000,000,000,000,000,000
And the Sun has a remaining life of about 5 billion years (5* 10^9). http://helios.gsfc.nasa.gov/qa_sun.html#sunlife

[DeathAndTaxes]

Reason I asked is that I prefer to give half a key to Alice and Bob and the other half to Charlie and Dennis. I consider this a backup strategy in case something happens to me (so my family can inherit) or I lose my notes (e.g. house burns down). To add safety I could use multisig, but the risks to worry about should be elsewhere; may these conspire and steal my coins, did a screen capture see the private key, did I write them down without any typos?

Well I wouldn't write down any secrets by hand and your additional risks always apply not matter how you share access.  The best solution would be to store the funds in a P2SH address which requires m of n (i.e. 2 of 4) private keys.  If you wanted to ensure certain subsets are require (i.e. (Alice or Bob) AND (Charlies or Dennis) ) then you could just make it 2 of 2 and give each "or" pair the same key. 

Instead of P2SH another option would be to SSS (Shamir's Secret Sharing) to break a single key into n pieces where m of them are needed to recreate the original secret (the private key).  Honestly I don't see much use in this but it could be done.  One last option which is simplistic but still provides better security than cutting the key in half is XOR two keys to produce the final key.   With one of the two subkeys the security of the key isn't reduced.   The two subkeys should each be 256 bit but here is an example with smaller keys.

01010110 Produce random subkey1
11000001 Produce random subkey2
---------------------------------------
10010111 XOR the two subkeys to produce the Bitcoin privatekey

Giving one person 01010110 and the other one 11000001 and telling them to XOR their keys to produce the full key is better than giving one person 1001 and the other one 0001 and telling them to concatenate the pieces.


No matter how you split the "secret" you could enhance security by delaying the funding of the address by making the funding transaction have a nTimeLock set years in the future and providing all participants with that tx. Even if your friends conspire the address is empty until the nTimeLock is reached (and they can broadcast the funding tx).  You obviously don't know when your death will be but this can be extended as many times as needed by spending the original coins to a new address (redning the nTimeLock tx invalid) and creating a new timelocked funding tx.

[DeathAndTaxes]

Is it possible to use a ASIC miner for that attack?

An ECDSA breaking ASIC? Sure.  A Bitcoin mining ASIC? No.  ASICs do one thing and one thing only.

How do I get from X bit code to Y bit security? (I assume the way to go is: find the best available algorithm for the problem and use the big O approximation) Not sure if this applies for this example since the way I understand OP we dont have the public key.

That is my mistake.  My numbers assumed the PubKey was known.  I misread the OP.  If the PubKey is unknown then the best attack is 2^160 (searching for a preimage of the PubKeyHash).

How do I get from Y bit security to Z calculations. IIRC big O does this as well, but ...

You use Big O or for ECDSA you just remember that bit strength is 1/2 key length.  Also remember Big O just gets us to the magnitude.  There is no computer which can perform Pollard rho in a single operation.  It might require 10 operations or 10,000 but these are linearly constraints.  For cryptography we want to ensure the magnitude alone puts an attack beyond what is feasible.

I dont really know what my but is here, besides that I am a little afraid because I just realized how powerful the sabre cluster actually is.

Against 64 bit security?  Nobody should be using anything with only 64 bit security.  Note this is supported by emperical evidence as well.  A 112 bit ECC key (56 bit security) is the largest known ECC key to be brute forced.  It was completed in 3.5 months of runtime using 200 Playstation 3s. http://lacal.epfl.ch/112bit_prime

[shorena]

Is it possible to use a ASIC miner for that attack?

An ECDSA breaking ASIC? Sure.  A Bitcoin mining ASIC? No.  ASICs do one thing and one thing only.

Yes the question was hinting at Bitcoin mining ASICs, which ofc makes no sense. Thanks for the reminder what ASICs actually are

-snip-
You use Big O or for ECDSA you just remember that bit strength is 1/2 key length.  Also remember Big O just gets us to the magnitude.  There is no computer which can perform Pollard rho in a single operation.  It might require 10 operations or 10,000 but these are linearly constraints.  For cryptography we want to ensure the magnitude alone puts an attack beyond what is feasible.

I understand, so we just ignore everything else (constants, etc.) and just take the fastest growing part. E.g. if we had two loops from 0 to n within eachother we have O(n²) no matter how many commands are used in each loop. This would ofc just give us a rough picture, but (see below)

Against 64 bit security?  Nobody should be using anything with only 64 bit security.  Note this is supported by emperical evidence as well.  A 112 bit ECC key (56 bit security) is the largest known ECC key to be brute forced.  It was completed in 3.5 months of runtime using 200 Playstation 3s. http://lacal.epfl.ch/112bit_prime

but... as I read in the artical we are happy with a rough estimate anyway, because of the birthday paradoxon. There is a very slim chance that the last calculation would give us the result. It is more likely that we get our answer sooner. Thus the time needed for a calculation can only be estimated (e.g. 50% chance of success after X days) and is not fixed. So my calculation above is way off anyway.

And yes I just remembered that we are talking about 64 bit, thus we are in the exponent. So in comparison 128 bit security is not only "twice as secure" but "2⁶⁴ times as secure"

[boumalo]

You are ruling multisignature addresses but it could be your solution

You can also protect your back-up by storing it more securely, maybe not at home

[ShakyhandsBTCer]

It makes it 340282366920938463463374607431768211456 times easier to brute force.

So if you could guess 10^9 per second it'd only take you 10^24 years instead of 10^63 years.

256 bit ECDSA keys only have 128 bit security.  Half of an ECDSA key would be 64 bit security.  While a naive attack would be to increment all possible private keys there are more sophisticated attacks ( https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms ) which are of complexity O( n^(1/2) ) steps where n is the key length.

64 bit security would be breakable but it is very likely the cost to break they key would be greater than the reward.  Although if this isn't a hypothetical I would recommend transferring the coins now.

Thanks for answers.

Reason I asked is that I prefer to give half a key to Alice and Bob and the other half to Charlie and Dennis. I consider this a backup strategy in case something happens to me (so my family can inherit) or I lose my notes (e.g. house burns down). To add safety I could use multisig, but the risks to worry about should be elsewhere; may these conspire and steal my coins, did a screen capture see the private key, did I write them down without any typos?

Why don't you copy/paste 1/2 of your private key separately and put each half in a safe deposit box. You could set up each box so that while you are alive, only you have access to both boxes, but upon receipt of notification that you have died, Bob would have access to one box and Allice would have access to the other.

This issue with multi sig is that both parties could potentially work together to gain access to your funds, as well as the fact that multi sig is relatively new to the Bitcoin network.

Writing down your key is not a good idea as even one "typo" would cause your entire "key" (it wouldn't actually be a key anymore) worthless

[cech4204a]

To make it simple answer, yes your BTC are safe, but you still need to transfer them to another wallet to make sure you remain safe, since half is something, they will first try to crack yours and than other that they have no idea about .

[Bitcoin++]

Writing down your key is not a good idea as even one "typo" would cause your entire "key" (it wouldn't actually be a key anymore) worthless

+1

Absolutely. I used brainwallet and wrote down the private key. I knew the risk of typos, so immediately aftewards I used the option to type a private key in to get an address out. Well, mistakes did happen, like is this an "s" or "S" or "5". It took quite some trial and error to get it right.

[single-mom]

Safe but you cannot access the either