4
$\begingroup$

We just learned about this in school but i don't quite get the weakness of this method. If we let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit. If the enemy managed to find one half and he can use brute force on the other one. Will he manage to find it? Or does it depend on how times the enemy can try per second? What if he can try $10^6$ times per second? but does that mean that trying also counts as trying to combine the two halves? I mean that does he in every time he brute forces, also try at the same time to sum the two parts and unlock the key?

$\endgroup$
11
$\begingroup$

let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit

That right there is your misunderstanding. Shamir secret sharing does not split a secret into pieces that are smaller than the original secret. Instead, it splits the secret into pieces that are the same size as the original secret.

A simple graphical example typically does the best job describing Shamir's method. Assume that my secret is the number $42$ and that I want to split this into $3$ pieces to give to my friends such that any $2$ of them can get together and recreate my secret. So my threshold is $2$, so I pick a random polynomial of degree $1$ (one less than the threshold) and set the zero term to my secret. So let's say my polynomial is $f(x)=42+17x$. To generate my shares, I evaluate the polynomial at the points $1,2,3$ and get $(1,59),(2,76),(3,93)$.

I then give one share to each friend.

Now, to understand the security of this, you need to think back to the line that we used to generate these shares. If I give you 1 point on the line, what does that one point tell you about the line that was used to share the secret? How many lines can you draw through that one point? The answer is infinitely many. So, by having that one share, you have gained no useful information about the secret.

That is the beauty of Shamir's method. Having the less than the threshold number of shares gives you no useful information. It is only when you have that one share that you have any useful information at all.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This is great in in theory, with an infinite key-space. How does this hold up with 32 bit ints? Do I need to go to some sort of big int? $\endgroup$ – markgamache May 10 '19 at 19:28
  • 1
    $\begingroup$ @markgamache, 32-bit integers are fine. $\endgroup$ – mikeazo May 10 '19 at 21:55
  • $\begingroup$ As long as the space you're working in is at least as large as all possible secrets, then the number of possible "lines" in an incomplete solution, while not infinite, is the same (or worse) as just listing all possible secrets. In practice most implementations take large secrets and break them up into smaller pieces (e.g. bytes or words), and then run the SSS algorithm on each piece independently, so they can process secrets of any size while still using conveniently-sized numbers in the calculations. $\endgroup$ – Foogod Aug 31 '19 at 0:24
6
$\begingroup$

Shamir's secret sharing does not split a secret into smaller ones nor does it have weaknesses. It is information theoretically secure, and does not rely on limited computing strength of attacker. (Providing you have a good source of randomness).

It is perhaps best to start with a simpler secret sharing mechanism. Should I want to split a secret S into two parts, we choose a new uniformly random S1 and calculate the xor of them S2 = S ^ S1

S1 is uniformly random and obviously doesn't give any information about S. S2 is also uniformly random and doesn't give any information about S yet together they produce it perfectly.

Shamir's method allows more elaborate secret sharing where we need only k out of n shares to reconstruct the secret yet k-1 of n shares hold no information about the original secret. This is achieved by understanding that a polynomial of degree k is uniquely defined by and k points on it.(2 points define a line, 3 points a parabola, etc.). We can select k-1 points on a finite field and the secret as another point to construct a polynomial. We calculate more points to fill up the desired n shares. It can be shown that any k-1 points do not give information on the secret(Note this wouldn't have held if for instance we would be working over R).

For further reading: https://en.wikipedia.org/wiki/Finite_field https://en.wikipedia.org/wiki/Secret_sharing https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

| improve this answer | |
$\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.