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

10/30/2007

A Flaw in Shamir’s Secret Sharing method?

Filed under: Math — Andy @ 1:36 pm

(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 \LaTeX 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 D). Then, you can make a polynomial g(x) (y’know, the curve with an equation like g(x) = 1234 + 7245\cdot{x} + 3245\cdot{x^2}) where g(0) is the secret you’re sharing, and the rest of the coefficients are random integers. If you make a polynomial of degree k-1 (where k is the number of people you want to require to reconstruct the secret) (that is, the highest power of x in the polynomial is k-1), you could pick as many points on that polynomial as you want (Shamir says you pick a total of n points, so you need k of the n points to reconstruct the secret), and distribute them. Using some sort of algorithm, you can reconstruct the polynomial from k 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 D into n pieces D_1, . . ., D_n in such a way that: […] (2) knowledge of any k-1 or fewer D_i pieces leaves D completely undetermined (in the sense that all its possible values are equally likely).
[…]
Given an integer valued data D, we pick a prime p which is bigger than both D and n.
[…]
The coefficients a_1, . . ., a_{k-1} in q(x) are randomly chosen from a uniform distribution over the integers in [0, p)
[…]
D_1 = q(1), . . ., D_i = q(i), . . ., D_n = q(n)

How can the polynomial be reconstructed?

One way to reconstruct the polynomial q(x) is using a Lagrange interpolation polynomial, which can also be used to get more information about D than Shamir claims is possible with only k-1 D_i pieces.

The Lagrange interpolation polynomial is the sum of the Lagrange basis polynomials multiplied by their respective y-values, constructed using the formula
\prod_{i=0,\, i\neq j}^{k} \frac{x-x_i}{x_j-x_i}. (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 (D=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.(a_1=166;a_2=94)\,\!Our polynomial to produce secret shares (points) is therefore: g\left(x\right)=1234+166x+94x^2\,\!

We construct 6 points from the polynomial: \left(1,1494\right);\left(2,1942\right);\left(3,2578\right);\left(4,3402\right);\left(5,4414\right);\left(6,5614\right)\,\!


Because the secret D is the value of g(x) where x = 0, we can simplify each term of the Lagrange basis polynomial to just \frac{-x_i}{x_j-x_i}.Imagine we know the values of D_2 and D_5 (k-1, or 2, pieces), and are trying to guess D_1 to determine what D will be.The Lagrange polynomial formed would be:
g(0) = D_1 \cdot{-2 \over 1-2}\cdot{-5 \over 1-5} + D_2 \cdot{-1 \over 2-1}\cdot{-5 \over 2-5} + D_5 \cdot{-1 \over 5-1}\cdot{-2 \over 5-2}

Substituting in known values gives
g(0) = D_1 \cdot{-2 \over 1-2}\cdot{-5 \over 1-5} + 1942 \cdot{-1 \over 2-1}\cdot{-5 \over 2-5} + 4414 \cdot{-1 \over 5-1}\cdot{-2 \over 5-2}

Which reduces to
g(0) = 2.5\cdot{D_1} - 2501

Because g(0) (=D) is a positive integer, we know that D_1 > 1000, and that D_1 is a multiple of 2 (as the smallest denominator of D_1‘s Lagrange basis polynomial is 2). Therefore, D = 5\cdot{x_1} + 4, where x_1 is a nonnegative integer.

So what does it mean?

This math seems to show that Shamir’s second claim (“knowledge of any k-1 or fewer D_i pieces leaves D 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 D. Repeating the above procedure for different unknown D_is reduces the possibilities even further (significantly so, in some cases). This is a significant reduction in possible values of D, especially if D 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

14 Comments »

  1. […] Schmitz (who is a high school senior) in LardBucket presents us with an analysis of A Flaw in Shamir’s Secret Sharing method? He invites readers to critique his […]

    Pingback by The Carnival of Mathematics 二十 (#20) - squareCircleZ ::oo — 11/2/2007 @ 11:18 pm

  2. […] also got a sneak preview even before the Carnival of a high school student’s discovery of a Flaw in Shamir’s Secret-Sharing algorithm. Check it […]

    Pingback by 20th Carnival of Mathematics « Ramblings of a Math Mom — 11/3/2007 @ 12:00 am

  3. Shamir’s secret sharing…

    Over at Lard Bucket, Andy Schmitz look at Adi Shamir’s secret sharing method. He identifies what he considers a possible flaw in the method, using an example from the Wikipedia entry, and invites readers to critique his reasoning. The executive……

    Trackback by The BWAIN — 11/3/2007 @ 10:06 am

  4. Unfortunately, trackbacks don’t seem to be working for me. Nevertheless, here’s your answer.

    Comment by Pseudonym — 11/3/2007 @ 10:09 am

  5. I tell a lie, they are working!

    Comment by Pseudonym — 11/3/2007 @ 10:10 am

  6. […] interesting? Entry #4 This is the first ever CoM post by a high school student: Andy found a flaw in a polynomial-based encoding system (he shows it is not as strong as it claims. In fact, it would be nice to show that it is not […]

    Pingback by Carnival of Math 二十 « JD2718 — 11/3/2007 @ 11:15 am

  7. Hey, Andy.

    The BWAIN suggests someone should update the Wikipedia article – maybe that honor should fall to you?

    Comment by Zac — 11/4/2007 @ 2:56 am

  8. You’d typically do all of this in a finite field instead of the integers (i.e. modulo a prime which in your example would be any prime larger than 10000). That way your “flaw” won’t work anymore.

    Comment by stefan — 3/16/2008 @ 4:14 pm

  9. If you work over only positive integers, then you are correct. On the other hand Shamir secret shares should be constructed over finite fields, where there is no flaw. Over finite fields there exists a value D1 for every solution of g(0).

    Comment by Tordr — 4/1/2008 @ 3:35 am

  10. Yeah, I was wondering about this problem too the first time I heard about Shamir’s secret sharing, then I asked someone who would know. It took about 30 secs for him to explain it and I banged my head into the table, thinking ‘oh, my God, I’m such an idiot’.
    I did not, luckily, decide to publish my idiocy to the entire freaking world on internet. What’s wrong with you?
    Shamir’s secret sharing is done over a finite field. End of problem.

    Comment by Thomas — 1/11/2011 @ 5:41 am

  11. i was JUST having this same discussion with someone. thanks for the cogent writeup.

    Comment by qarl — 6/24/2011 @ 9:13 pm

  12. Andy, you no doubt plan to update this page, but until that happens I’ll give readers a preview of your 11/18/2007 post, where you write,
    “Speaking of Adi Shamir, I’m pretty thoroughly convinced that tossing the modular arithmetic into Shamir’s secret sharing algorithm the way it was intended will give proper, non-leaking results. It looks like the flaw is really just an implementation flaw in the way I was looking at the problem (and the way it was replicated on the Wikipedia). So, while it’s something to look out for if you’re actually implementing the algorithm, it’s not a major problem if you’ve got a working, proper implementation. I’ll try to update my blog post (and the affected Wikipedia article, if it still needs fixing) soon.”

    Good for you for thinking something through and posting about it. Don’t be embarrassed that your objection turned out to be wrong. Theorums get disproved, and hypotheses get contradicted, and new ventures fail, all the time. That’s how science and academic knowledge and innovation advance. As Andy Grove of Intel is supposed to have said, “If you haven’t made at least one mistake today, you’re not trying hard enough”.

    Comment by Jim DeLaHunt — 4/22/2012 @ 6:08 pm

  13. […] demonstrate a method. The implementation provided is not a reliable/hardened solution (i.e. there are vulnerabilities because finite fields are not used) and should not be used anywhere near a production […]

    Pingback by Shamir's Secret Sharing & Passwords | Will Tracz — 1/10/2013 @ 3:28 pm

  14. […] various technical reasons the calculations should be carried out over a finite field. That doesn't really […]

    Pingback by Shamir’s Secret Sharing | Irreal — 9/10/2014 @ 6:05 am

RSS feed for comments on this post. TrackBack URI

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

My Stuff
Blog Stuff
Categories
Archives