Shamir's Secret Sharing Scheme (2005) | Hacker News Reader

Shamir's Secret Sharing Scheme (2005)

point-at-infinity.org

59 pointspandatigox33 comments

I've recently defined and implemented a new backup scheme for my personal stuff, and ssss plays a role in it:

Aside from my regular backups on Blu-ray (unencrypted), I've got two hard disks that hold the same data (and will be updated infrequently, once a year at most).

This is my disaster fallback: house burning down, me awakening from a coma without remembering any passwords or whatever.

Those hard disks are stored in the houses of two friends. And they are encrypted (BTW, that's not only for my peace of mind, but also for theirs: I wouldn't be comfortable holding personal information of my friends unencrypted).

The password to the encryption is split into n parts, such that very close family and friends get more parts and more remote friends get fewer parts. But noone can recover it without cooperation of at least one other.

Printed onto a sheet of paper, together with a clear description (including actual command line invocations) how those shares were generated and how they can be combined). Distributed to a lot of friends. That description is important and must be abundantly clear. Not necessarily to your grandma, but if she shows it to someone who knows at least a bit about computers, he must be able to make sense of it.

In your case, you don't want to protect your data from (illegal) seizure and searching (since you also keep unencrypted BR discs).

But seizing the key-holding devices from your inner circle can be used by law enforcement (or an unfavourable regime) to recover your data without your consent, and you have no way of stopping them.

I don't know a solution to the problem - in the case you lose knowledge of your pass-phrases, external memory is a requirement and such an attack would probably always be possible.

If someone knows a way to have both amnesia- and dictator-proof encrypted storage, I'd love to know about it!

At least they would need to seize from several people.

And apart from that they can just seize my unencrypted home backup.

Unencrypted, because I want to be able to restore the rest if a bit flips in some file. And my PAR3 tests were really unconvincing.

Unencrypted, because I want to be able to restore the rest if a bit flips in some file.

Is this a realistic concern? Is a bluray disc at risk of flipping its bits?

No, I meant having unreadable parts.

Sorry, I'm thinking too much about flipping bits and soft errors at work...

I've read that habits are stored in the memory in different ways than regular memories, and habits are more durable to incidents such as amnesia. (citation needed)

Perhaps by practicing typing the encryption key day after day, you could record it in muscle memory and it would be amnesia proof.

Or perhaps you could invent a unique hand-dance (think hand-jive) and practice it daily, and you could write a program that could decode the sequence into a key.

This is how the DNSSEC root key is divided.

https://www.schneier.com/blog/archives/2010/07/dnssec_root_k...

For a mathematical explanation, see http://jeremykun.com/2014/06/23/the-mathematics-of-secret-sh...

This was used in the 3301 / Cicada 'games' last year [1]. The only way I know about it. Cicada 'dead-dropped' difference peices of the SSSS code all over the world. We had to recover. One of the guys ended up 'bruting' the final line.

[1] http://uncovering-cicada.wikia.com/wiki/What_Happened_Part_1... (breif overview)

Haha, yeah, that's how I found about the scheme. The wikia's a very interesting read btw. Taught me stuff I never knew existed before. A real TIL

That challenge looks harder than most crackmes or ARGs, really cool.

One thing that popped into my head immediately was the usefulness of a system like this to implement various kinds of democratic "dead man switch" type constructs.

For example, let's say a dissident posts a dangerous leak to a bunch of sites in encrypted form. They then distribute the key to 60 of their friends with a threshold of, say, 25 (slightly more than 1/3) and say "combine your keys if anything happens to me."

First thought that came to me as well. Also, a good way to get people together if you use the scheme for your will or something ;)

From a functional perspective, if you were using this to protect data.. How is this different from splitting an AES key into multiple parts?

if you split an integer into multiple parts, then the person who has the higher order bits (maybe, all but one of them) can get together and share their information to get quite a lot of information about the key, possibly enough to guess it.

1. You get proven semantic security - that is nobody can learn anything other than the message length - for whatever you're splitting. If you divide up an AES key into chunks an attacker would get partial knowledge of the key from one of those chunks.

2. You get to pick how many parts are needed to reconstruct, e.g. three of seven parts required.

If you split into multiple parts, each part of the key is useful: it lets you reduce your search space by however many bits of the key you have. This is bad. Whereas with secret sharing, if you have less than the threshold needed, you have no cryptographic advantage to someone with no shares in terms of identifying the secret.

Slightly more concretely: I can split a secret value s into two parts by randomly choosing a line that has X intercept s, then giving the value of the line at 1 and at 2. Neither of these alone gets me any closer to finding s, but if I know them both, then I can trivially get s.

Also, splitting the parts up directly means you can't do "any t of n is good enough" where t != n and t != 1.

> If you split into multiple parts, each part of the key is useful: it lets you reduce your search space by however many bits of the key you have.

That doesn't have to be true. Rather than splitting an AES key K into substrings, a better approach is to choose n parts such that:

    K_1 ^ K_2 ^ ... ^ K_n = K

None of the component K_i will reveal any information about K without knowledge of its peer components.

I wouldn't call that "splitting". This is how you do shamir's scheme over GF(2^n) when the number shares equals the threshold.

KEY:

ABCDEFGH

K1 K2 K3 K4 K1 K2 K3 K4

K1: AE K2: BF

and so on.. ?

That's fine if you are willing to require all n parts to be available to reconstruct the key.

In many applications, though, you want to allow a subset of the parts to reconstruct the key. You might want, say, 8 people to have key shares, but want any 3 of them to be able to reconstruct the key. Shamir's makes this kind of setup easy.

This is one of the technological/mathematical developments, along with multi-sig, that has great promise for improving the security and flexibility of Bitcoin. One of the worries for people with large bitcoin holdings is the being-hit-by-a-bus problem. With normal property the legal system provides the flexibility and rules by which valuable goods can be passed on to heirs. With Bitcoin, the loss of keys can mean huge amounts of value are irrecoverably lost. I hope that Shamir Secret Sharing is used as the basis for a bitcoin startup that allows bitcoin users to easily specify a set of trusted people who can come together to reconstruct keys on the event that the original holder of the keys is incapacitated or deceased.

The new century of inheriting goods is receiving pieces of paper, which put together, is worth a fortune

I've written a short, simple web implementation if you're interested in the math behind this:

http://karlgluck.github.io/ThresholdJS/

Here's a program I wrote that wraps the shares with passwords (at the expense of semantic security, though it has key stretching via pbkdf2 to somewhat mitigate lousy passwords) and bundles everything into a single file.

https://github.com/ryancdotorg/threshcrypt

Why only 128 ASCII Characters? Just so the secrets are manageable? I think that restriction should be removed... It would keep it's primary use case and make possible others.

A method to explode a bitcoin private key with SSS into multiple secret parts and use them to collaboratively sign transactions has unfortunately not yet been discovered.

What exists already, though, is something similar. Instead of fitting a polynomial through the points (=secret shares), where the intercept would be the full secret, there is a scheme where the full private key is just the simple multiplication of the secret shares.

From there, the co-signers use Pallier encryption to collaboratively compose the signature without revealing their secret parts to each other. It only works with two co-signers at the moment. Here is a demo:

http://www.jpaulgossip.com/demo/split-key.html

Why not just use the hybrid approach described in the linked page? Encrypt the bitcoin key with a block cipher, then encrypt that key with SSS.

It would be enough to attack the machine holding the decrypted bitcoin key in order to steal the money. So, you still have that dreaded single point of failure problem there.

The security solution consists in forcing the attacker to attack lots of machines and successfully control them in order to steal the money.

SSSS is worse than using OP_CHECKMULTISIG because one has to put all the secrets at once on a single machine to produce the final private key. If the machine is compromised, such key can be stolen right away. Using multisig script allows you to have several (possibly compromised) machines sign a transaction independently without ever producing any "master secret".

Here's my suggestion on how to use multisig with blinding so you can lock your bitcoins with N friends and have your financial privacy at the same time: http://oleganza.com/blind-ecdsa-draft-v2.pdf

Prototype for iOS (using my CoreBitcoin objc library): http://github.com/oleganza/blindsignaturedemo

Unfortunately, multisig forces you to use the blockchain. There are use cases where you don't want that. SSS, on the other hand, seems too complex to feed back through the ECDSA signing algorithm. In the link above they just use the factors of the private key to distribute as shared secrets. So, your private key cannot be a prime. But then again, ECDSA does not seem to require that from a private key. It's not that using a composite number would make it easier to work your way back to the discrete ECC logarithm ...

I was replying to your question on how to sign transactions. Multisig is the real and the best solution for this task. Maybe I don't understand the problem with "multisig forces you to use the blockchain". If you sign a bitcoin tx, then sure you need to get it on the blockchain. Or am I missing something?

Distributed signing is useful in other contexts too. It does not always have to be bitcoin-related ...

Reply on news.ycombinator.com