1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually, the birthday paradox does not apply in this case; it'll take an expected $2^{127}$ guesses on $U_i$ before you happen to hit on the correct secret. In addition, in the XOR scheme itself, each share individually gives no information about the shared secret; hence it doesn't make sense to talk about 'bits of security', which is really how much computation an adversary needs to perform to break the system, and in this case, a computationally unbounded attacker cannot. Yes, he could take a guess of the secret, however a single share does not tell him whether the guess was correct. $\endgroup$ – poncho May 12 at 11:23
  • $\begingroup$ @poncho 1) Would you mind elaborating a bit on your explanations? 2) Is the scheme I described already used in "notably safe applications"? If that is the case, which ones? $\endgroup$ – connief May 15 at 4:19
  • 2
    $\begingroup$ @connief: it's not clear what needs to be elaborated; as described, an adversary with a share and a guess of the shared secret could verify his guess; if instead you selected $share1$ randomly (rather than a deterministic function of the secret), he could not. As for whether a 'notably safe application' uses a deterministic selecting of shares, well, I would certainly hope not... $\endgroup$ – poncho May 15 at 12:00
  • $\begingroup$ @poncho. Thanks a lot. What would be your views of my scheme if the secret were the private key of a bitcoin address (or another kind of "computationally hard to guess" secret)? $\endgroup$ – connief May 18 at 3:26
0
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Minor nit: In fact, a XOR between two shares is not Shamir's Secret Sharing; there is no finite field $GF(p^k)$ and public identifiers $a$, $b$ such that the recombination step of the two shares $ar+s$ and $br+s$ (random $r$, secret $s$) is a simple xor of the two shares. XOR is a valid Secret Sharing method; just not Shamir's... $\endgroup$ – poncho May 13 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.