I'm trying to design an extension to Shamir's Secret Sharing that would allow the participant to specify a password instead of remembering/storing a large integer or binary data. So far, I have two ideas, both based on some PBKDF:

  • Run the password through a strong PBKDF to make $k_i$ then publish $(i, f(i)⊕ k_i)$ in a public, read-only location.
  • Similarly, run the password through a strong PBKDF and then publish $(i, \text{AES}(\text{key}=k_i, \text{message}=f(i))$ in a public, read-only location

I like the simplicity of the first method, and rationally I haven't found anything wrong with using nothing more than XOR, but to my intuition it smells a bit fishy.

Am I divulging any information that would weaken the algorithm by using just XOR? What about with AES?


Well, the first thing comes to mind is "what if your 'read-only location' isn't quite as read-only as you had hoped; if someone could modify your $f(i) \oplus k_i$ share, could they modify the reconstructed shared secret in a controlled way.

In your first example, I believe they could. Let us assume that we are doing Shamir's Secret Sharing over the field $GF(2^k)$; let us further assume that the attacker has $N-1$ shares (where $N$ is the number of shares we need to reconstruct the secret). Which his $N-1$ shares, he can reconstruct that, when you add in your share $f(i)$, the reconstructed secret will be $s = c \times f(i) + d$, for some values $c, d$ he can compute (and $\times$ and $+$ are over $GF(2^k)$.

Now, $c \neq 0$, and so this doesn't give him any information about what the secret is (given that he doesn't know your share). However, if he wants to modify the secret, say, add $t$ to is, what he can do is modify your encoded share on the read-only location, replacing $(i, f(i) \oplus k_i)$ with $(i, f(i) \oplus k_i \oplus (t \times c^{-1}))$.

Then, when you reconstruct the secret, using his N-1 shares, and your modified share, you will decode your share as $F(i) + (t \times c^{-1})$ (remember, in $GF(2^k)$, addition and exclusive-or are the same operation); then, when you combine this decrypted share with his, you're come up with $c(F(i) + tc^{-1})+d = cF(i)+d + t = s+t$, resulting in the modified shared secret that the attacker selected.

On the other hand, by using AES to encrypt the share, the attacker cannot do any such tricks. He can modify the share so that the shared secret becomes something else, however, he has no control over what that something else might be.

| improve this answer | |
  • $\begingroup$ "he has not control over what the something else might be" as long as the pbkdf is non-malleable. $\:$ Otherwise, one also needs to worry about someone modifying its parameters. $\:$ $\endgroup$ – user991 Sep 19 '13 at 5:21

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.