Hacker News Reader

Comment by Mandatum | Hacker News Reader

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

View on HN

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.

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 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.

Reply on news.ycombinator.com