3
$\begingroup$

As I understand, the security of key-sharing depends on the cleartext actually being random.

If I split a secret which contains things like ASCII or even fixed strings (think -----BEGIN PGP PRIVATE KEY-----) what kind of preprocessing is recommended?

My current thinking is either one time Pad:

$ \text{Shamir}_{(N,M)} \left(\left( \text{secret} \otimes \text{random} \right),\text{random} \right) \rightarrow M \text{ shares} , N \text{ required}$

or multiple rounds of AES:

$ \text{Shamir}_{(N,M)} \left(\text{AES}_{key}\left(\text{secret} \right)^{rounds},\text{key} ,\text{rounds}\right)\rightarrow M \text{ shares} , N \text{ required}$

$\endgroup$
  • 1
    $\begingroup$ Actually, Shamir Secret Sharing is information-theoretically secure so you cannot infere anything about the plaintext that you didn't alredy knew beforehand. $\endgroup$ – SEJPM Mar 6 '17 at 11:43
  • $\begingroup$ I thought you could decrease the guessing space if you have $I<N $ shares? $\endgroup$ – hansm Mar 6 '17 at 11:47
  • 3
    $\begingroup$ If you have a fixed prefix like that PGP header, then that's not a secet. But information theoretic security means, for any $k<n$, the attacker gets nothing. He can guess, but he can't check if his guess was right. $\endgroup$ – tylo Mar 6 '17 at 11:53
4
$\begingroup$

As I understand, the security of key-sharing depends on the cleartext actually being random.

Actually not, the premise of the Shamir Secret Sharing (SSS) scheme is that it is information-theoretically secure.

That means if you require $N$ shares for reconstruction and an attacker has $<N$ shares, the following equation holds: $$\Pr[M=m\mid C=c]=\Pr[M=m]$$

Which basically says that given the ciphertext you know as much about the plaintext as you know without having the ciphertext.

Or, put differently, as tylo said in the comments:

He can guess, but he can't check if his guess was right.


As for why this holds (as you may ask yourself now): Notice that SSS basically encodes your secret as the point $(0,s)$ and that the shares are points $(x,f(x)), x\neq 0$ of a (nearly-random) polynomial of degree $N-1$ over some field (usually $\mathbb F_p^*$). Now imagine as an example you're given 2 points of a degree-2 polynomial (which would be N-1 shares). For every possible $s$, you can now find a third point such that $(0,s)$ is on the polynomial. Put otherwise: There's no additional constraining condition that would help you narrow specific plaintexts down as more likely.

$\endgroup$
  • $\begingroup$ The polynomial explanation was, what did the trick. $\endgroup$ – hansm Mar 6 '17 at 20:23
2
$\begingroup$

As I understand, the security of key-sharing depends on the cleartext actually being random.

Your understanding is incorrect. The security of key sharing does assume that the random coins used in making the shares are indistinguishable from random, however it makes no assumption about the cleartext. The attacker could know that the cleartext is one of two possible values; if he has $I < N$ shares, he still gets no information about which one it might be.

Now, one reason you might want to share an AES key (rather than the actual secret) is for length; each secret shared key needs to be at least as long as the secret; if you have a 1 Megabyte secret that needs sharing, it'd make sense to encrypt it with a random key, and secret share the key. However, that's for practical reasons, not security ones.

$\endgroup$

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.