lardbucket: a flaw in shamir’s secret sharing method?

(This post is going to be much more mathy than my standard posts, mostly because I thought about this as I was filling out college applications and decided it would be interesting to follow up on the random thought.)

(I apologize in advance for the poor quality renderings, but they should at least be legible)

A bunch of math follows in the full post.

What?

I was thinking about Adi Shamir’s “How to Share a Secret” paper in Communications of the ACM a while back (1979), and I realized that given some information about the polynomial that was generated, it should be possible to get some information about the secret that was being encoded.

Okay, how is it supposed to work?

It’s probably best if you read the paper (it’s only two pages, and it’s a pretty easy read as math papers go), but I’ll give a brief overview: If you’re trying to keep a secret (say, the combination to a lock, an encryption key, or your bank PIN), you can turn it into an integer (also known as ). Then, you can make a polynomial (y’know, the curve with an equation like ) where is the secret you’re sharing, and the rest of the coefficients are random integers. If you make a polynomial of degree (where is the number of people you want to require to reconstruct the secret) (that is, the highest power of in the polynomial is ), you could pick as many points on that polynomial as you want (Shamir says you pick a total of points, so you need of the points to reconstruct the secret), and distribute them. Using some sort of algorithm, you can reconstruct the polynomial from points, and then recover the secret. Just a bit complicated.

What definitions are required?

These are from the paper mentioned above.

Our goal is to divide into pieces in such a way that: [...] (2) knowledge of any or fewer pieces leaves completely undetermined (in the sense that all its possible values are equally likely).
[...]
Given an integer valued data , we pick a prime which is bigger than both and .
[...]
The coefficients in are randomly chosen from a uniform distribution over the integers in
[...]

How can the polynomial be reconstructed?

One way to reconstruct the polynomial is using a Lagrange interpolation polynomial, which can also be used to get more information about than Shamir claims is possible with only pieces.

The Lagrange interpolation polynomial is the sum of the Lagrange basis polynomials multiplied by their respective y-values, constructed using the formula
. (from the Wikipedia)

How does that leak information?

We can use this with a simple example on the Wikipedia “Shamir’s Secret Sharing” page, copied below (I changed “S” to “D” to match Shamir’s paper):

---

Suppose that our secret is our ATM code: 1234 .We wish to divide the secret into 6 parts (n=6), where any subset of 3 parts (k=3) is sufficient to reconstruct the secret.At random we obtain 2 numbers: 166, 94.Our polynomial to produce secret shares (points) is therefore:

We construct 6 points from the polynomial:

---

Because the secret is the value of where , we can simplify each term of the Lagrange basis polynomial to just .Imagine we know the values of and (, or 2, pieces), and are trying to guess to determine what will be.The Lagrange polynomial formed would be:

Substituting in known values gives

Which reduces to

Because (=) is a positive integer, we know that , and that is a multiple of 2 (as the smallest denominator of ’s Lagrange basis polynomial is 2). Therefore, , where is a nonnegative integer.

So what does it mean?

This math seems to show that Shamir’s second claim (“knowledge of any or fewer pieces leaves completely undetermined (in the sense that all its possible values are equally likely)”) is false, as we have eliminated 4/5 of the possible values of . Repeating the above procedure for different unknown s reduces the possibilities even further (significantly so, in some cases). This is a significant reduction in possible values of , especially if is a key that takes a significant amount of time to check (like a bank PIN or safe combination), as it is an 80%+ reduction in the available keyspace.I’d be happy to get any comments on this, because I’m surprised that this hasn’t been pointed out before [if it's actually a flaw].

Andy Schmitz