Secret sharing scheme WITHOUT Shamir Secrete Sharing

Question

I am planning to use the following XOR scheme to divide a secret into only 2 shares (I do not want to use Shamir Secret Sharing for different reasons that are beyond the scope of this post).

Here's an example of the XOR scheme I have in mind.

SECRET (128 bits) = 0 1 0 1 0 0 1 0 0 0 0 1 (…) 0 0 1 1 0

SHARE 1 = TRUNC128 (SHA512 (SECRET))

     =  0 0 0 0 1 1 1 0 0 0 1 1  (…)  1 1 0 0 1

SHARE 2 = SECRET ^ SHARE1

     =  0 1 0 1 0 0 1 0 0 0 0 1  (…)  0 0 1 1 0

     ^  0 0 0 0 1 1 1 0 0 0 1 1  (…)  1 1 0 0 1

    =  0 1 0 1 1 1 0 0 0 0 1 0  1 1 1 1 1

SECRET = SHARE1 ^ SHARE 2

   =  0 0 0 0 1 1 1 0 0 0 1 1  (…)  1 1 0 0 1

    ^  0 1 0 1 1 1 0 0 0 0 1 0  (…)  1 1 1 1 1

   =  0 1 0 1 0 0 1 0 0 0 0 1  (…)  0 0 1 1 0

I have a few questions about that XOR scheme as I am building a case for using it.

1) How resistant would such a scheme be to common attack vectors (brute force...)?

2) Are there any ways to evaluate what it (or how much it) would take to break that scheme?

3) Is that scheme already used in "notably safe applications"? If that is the case, which ones?

Answer 1

XOR secret sharing used directly is unconditionally secure, if the randomly generated first share $S_1$ is a uniformly distributed vector in $\{0,1\}^{128}$. Let the secret be $X \in \{0,1\}^{128}$ and the shares be $S_2=X+S_1,$ and $S_1,$ where $+$ denotes bitwise XOR.

For a third party to learn the secret, they need to brute force $O(2^{128})$ guesses in the worst case.

Now you've "hidden" the secret $X$ by your $S_1'=TRUNC_{128}(SHA_{512}(X)).$

As stated in the comments I was wrong, thebirthday paradox does not directly apply.

An attacker brute forcing the share $S_2’=X+X_1$ at the same complexity will not learn your secret but its hash, so you’ve gained something.

However in the absence of side information, the original XOR scheme is as secure, unless the guesses for the secret can be tested by using it, say, as a password to unlock some system. In that use case, your modification is an improvement since it prevents this way of testing if the guess is correct.

Answer 2

In fact, a XOR between two shares is Shamir's Secret Sharing. In full generality, Shamir's Secret Sharing works in a given finite field, with n shares and a threshold of t; in the specific case n = t = 2, using finite field $\text{GF}(2^{128})$ (for shares and values which are 128-bit strings), Shamir's Secret Sharing becomes just: secret value is the XOR of the two shares. Which is basically what you suggest.

Specifically, using Shamir's Secret Sharing reduced to n = t = 2 would be: generate share 1 as a random bit string, compute share 2 as the XOR of share 1 and the secret. Secret reconstruction is simply XORing the two shares together.

Now, you depart from Shamir's Secret Sharing in the following way: instead of making share 1 a purely random string, you generate it as a (truncated) hash of the secret itself. This makes the scheme weaker since now brute force attacks on the secret are feasible: given share 1 or share 2, one can try potential values for the secret, and see if each such value would yield the share. If share 1 had been generated randomly, such a brute force attack would not be feasible (it can be shown that the information content of a single share is zero, i.e. the secret cannot be reconstructed, even with an infinitely powerful computer). But, by using a deterministic method (the hash function) to make share 1, you inherently make the whole process simulatable (I am not sure "simulatable" is a word, but that means that one can, starting with the same secret value, obtain the exact same shares), which allows brute force attacks. An attacker with an infinitely powerful computer could try all possible secret values (there are "only" $2^{128}$ of them) in no time, and use one share value to find out which secret value is the right one.

In practical terms, i.e. in a world with real computers that have finite computing abilities, your scheme is crackable (by which I mean reconstructing the secret value given one of the shares) if the secret has low entropy. If the secret is itself a purely random string of 128 bits, then an attacker would need to try on average $2^{127}$ values before hitting the right one, and that's too much for current computers. But if the secret is some "real world data" with some structure (e.g. it is a "password", i.e. a string of characters that can be remembered and typed by a human being), then trying out all potential values could be substantially easier.

To sum up: if you replaced the truncated SHA-512 with simple plain random generation, then it would be "perfect" (in the same sense as Shamir's Secret Sharing, because it would be Shamir's Secret Sharing: immune to attackers with infinitely powerful computers). With the SHA-512, it becomes potentially vulnerable to brute force attacks, i.e. simply "trying out all potential values for the secret". The practical feasibility of such a brute force attack depends on how many potential values there are for the secret; if there are N equiprobable potential values, then the attack would need to try, on average, N/2 of them (if some values are more probable than others, then the attacker will start by trying these, and the analysis is slightly more complicated).