Breaking up a private key into pieces

Ecurb123

full member

Activity: 182

Merit: 100

Quote from: DeathAndTaxes on November 10, 2013, 01:32:57 AM

If you cut a key with a key strength of 2^n in half then the key strength of either portion (assumed the attacker acquires the other portion) is reduced to ~~in half~~ to 2^(n/2). An attacker would be 2^(n/2) times easier.

For 256 bit EDSA the full key has 128 bit strength security a half key then only has 64 bit strength if the attacker has the other portion. While it may take some time and effort that is computationally feasible. 64 bit key strength should not be considered safe from brute force attack. You have made the attackers job 2^64 = 18,446,744,073,709,551,616 easier.

A much better option would be to XOR two 256 bit "partial keys" to create the final key. Each partial key retains the full key strength.

thanks to the OP for the question I was thinking about it too, and thanks to DeathAndTaxes for the explanation.

deepceleron

legendary

Activity: 1512

Merit: 1036

http://mywiki.wooledge.org/XyProblem

daviducsb

full member

Activity: 155

Merit: 100

thanks all for the very solid info. I will print this thread out to slowly reference

Abdussamad

legendary

Activity: 3682

Merit: 1580

Another option is to do it in the native bitcoin way and create a multi signature address:

https://people.xiph.org/~greg/escrowexample.txt

Then give each relative one private key.

Yet another option is to use Armory for this. Armory can create m of n backups but, I believe, only via the command line. Search the forum for that thread.

J35st3r

full member

Activity: 196

Merit: 100

Depending on what you want to do with this, you could consider Shamir's secret sharing. It does rely on third party software, but there is an open source thread at https://bitcointalksearch.org/topic/ann-passguardiancom-client-side-threshold-secret-sharing-142875 and also some discussion at https://bitcointalksearch.org/topic/paper-wallet-20-using-shamirs-secret-sharing-scheme-idea-148809

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: ozgur on November 10, 2013, 01:49:14 AM

Quote from: DeathAndTaxes on November 10, 2013, 01:32:57 AM

If you cut a key in half then the key strength of brute forcing the other half is reduced by half.

EDSA 256 bit keys has 128 bit strength security.

So if you cut it into two 128 bit "half keys" and the attacker has one it is only 64 bit key strength to resist an attack. While it may take some time and effort that is computationally feasible.

A much better option would be to construct the partial keys using XOR making each key have full strength.

I know what you mean, but to make it clear;

it is not halved, it is ~~2^128~~ 2^64 times easier

I updated the post, your right it is unclear. A clarification though, 256 bit ECDSA only has 128 bit key strength so half the key would be 64 bit key strength (too weak for me to sleep well at night).

So it is 2^64 (or a whole hell of a lot) easier to break then the full key.

Still you are dead on with the larger point. It SIGNIFICANTLY degrades the strength of the key and 64 bit is too close for comfort in my book. Keys with 64 bit key strength have been broken in a distributed computing project as a demonstration. It is almost certain that major nation states have the ability to break keys with 64 bit strength in a reasonable amount of time.

ozgur

newbie

Activity: 22

Merit: 0

Quote from: DeathAndTaxes on November 10, 2013, 01:32:57 AM

If you cut a key in half then the key strength of brute forcing the other half is reduced by half.

EDSA 256 bit keys has 128 bit strength security.

So if you cut it into two 128 bit "half keys" and the attacker has one it is only 64 bit key strength to resist an attack. While it may take some time and effort that is computationally feasible.

A much better option would be to construct the partial keys using XOR making each key have full strength.

I know what you mean, but to make it clear;

it is not halved, it is 2^128 times easier

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

If you cut a key with a key strength of 2^n in half then the key strength of either portion (assumed the attacker acquires the other portion) is reduced to ~~in half~~ to 2^(n/2). An attacker would be 2^(n/2) times easier.

For 256 bit EDSA the full key has 128 bit strength security a half key then only has 64 bit strength if the attacker has the other portion. While it may take some time and effort that is computationally feasible. 64 bit key strength should not be considered safe from brute force attack. You have made the attackers job 2^64 = 18,446,744,073,709,551,616 easier.

A much better option would be to XOR two 256 bit "partial keys" to create the final key. Each partial key retains the full key strength.

daviducsb

full member

Activity: 155

Merit: 100

I have a Q for some of the cryptography connoisseurs out there.

If I break my private key into two and give each half to a relative, could a hypothetical thief hack into the rest of my private key by finding one of the two halves?

How much of a private key would one have to have access to in order to hack?

What if I lobbed off the first five and last five digits? Could someone who found the bulk of the key hack it?

I should know this by now but never enquired. Any help appreciated. Thx

Topic: Breaking up a private key into pieces (Read 1401 times)