Shamir's Secret Sharing is probably my favourite algorithm for showing the deep relationship between algebra and cryptography. The Fundamental Theorem of Algebra is a relatively straightforward result to show to a layperson, and Shamir's is basically as direct an application of it as you could want.
Then the part where using integers leaks information, and how to attack that, gets a bit hairier but is still a moderately accessible way to show cryptanalysis in practice. The fix using finite fields is then probably a step too far for most laypeople, and can be used as a lesson in how the fundamentals can be simple, but the devil is in the details.
I don't think you actually need FTA. I think you just need that an n'th degree polynomial has at most n roots. That might be better to show to a layperson, because if the layperson remembers their middle school algebra you can probably actually prove it to them.
For the part on leaking information, you can do the special case of two shares being required to recover the secret. You can then fairly straightforwardly show that if someone obtains just one share it does not help by showing that no matter what the secret, it is possible for that share to be a share for that secret. It's conceptually similar to how you show that xor with a true random key is unbreakable.
It's not the general case, but it can demonstrate how using modular arithmetic can fix an information leak.
Maybe somewhat. I think you can offer a simple explanation, but it depends a little on how you have already set up the problem.
Here's the problem setup: So we want to share a secret byte (178) among Alice, Bob, and Carol, so that we need all 3 of them to contribute to it. Three points defines a parabola so we choose two more random bytes: [38, 68], our polynomial is y = 178 + 38x + 68x². We then give Alice the point (1, 284), Bob the point (2, 526), and Carol the point (3, 904).
Now supposing that we have compromised both Bob and Carol's points we know that we have the two equations,
9a + 3b + c = 904
4a + 2b + c = 526
We can then eliminate b to get:
6a - c = 230
which we can rearrange as
c = 6a - 230.
Since `a` cannot be a fraction, we must be able to cut down the number of possibilities for c to just 42 possibilities, {4, 10, 16, 22, 28, ...}, since they must be separated by sixes. I'm not 100% sure but I think this factor grows like n!/(n-k)! for "I have compromised k of n secrets, by what factor have I reduced the search space?"
Here's how modular arithmetic solves this: It turns out that modulo a prime, all fractions are also whole numbers. That is, if I am working modulo the prime 13, I will find that I can divide 7/5 to find 4. Remember what division means, it inverts multiplication: I can find that 5 × 4 = 20 and then that 20 = 13 + 7, so they are at the same place "on the clock". In fact it suffices to just find 1/5 and multiply by 7, so you can find that 1/5 is 8 in the mod-13 ring, 8 × 5 = 40 = 39 + 1. You can also find that 1/6 is 11, so 6 × 11 = 66 = 65 + 1.
The proof that this must be the case is that if you take
[1, 2, ..., p-1].map(x => (x * n) % p)
this list cannot repeat itself: if it did, the resulting `x1 - x2` would divide `p`, by the distributive law of multiplication. It also is confined to only contain the numbers 1 through p-1, and so it must contain all of them exactly once: so if it doesn't repeat itself, it has to have a 1 in there somewhere.
That's kind of a brute force argument so you may want to also mention that there are two efficient ways to find these, one is called the "Extended Euclidean algorithm" (do a GCD computation to find that the GCD=1, but you can take the dividends that you discarded and cleverly assemble them to recover the constants from Bezout's identity, which in this case gives you the modular inverse) and the other is called "Fermat's little theorem" (since a^(p-1) % p == 1 for prime p, raise something to the p-2 power. Using exponentiation by squaring you only need ~log p multiplications that each take no more than ~log p time.
This is really fun, I love it. One could devise a whole game around that. Define functions that give you coordinates on a sphere (in this case, the earth), where X (e.g. the "treasure") is hidden. Then plot the functions, make k shares and make them (and mod p) discoverable through different other games (e.g. programming challenges). Then the first person to win all k-1 challenges and mod p is able to interpolate the exact location of the "treasure". A wonderful mix of maths, programming and real world adventure.
vault (https://vaultproject.io) uses Shamir to generate shares for operators to unseal the vault. In the latest release (1.0beta), vault seal keys can be wrapped with something like AWS KMS which allow for operator-less unsealing of the seal keys, but trade that off with potential operator access to the seal key itself.
Collusion between operators is a real problem of Shamir-based key systems. If you have a crypto system that depends on Shamir keys and a few of your operators leave the organization or become untrustworthy for some reason, then you need to revoke / resplit the origin key data material.
Additionally, the output of the ssss command itself is not secure, so you should consider having that data going through GPG to give each operator a GPG / keybase'd output which has never been seen in cleartext by anyone but themselves.
Long story short, key management continues to be really hard and needs to be thought through from begin to end with operational procedures in place to handle the real life situations that occur (employee collusion, employee join/depart, breach).
This math and the key analogy makes me think of the Reed–Solomon error correction algorithm which underlies the parchive sets used to transmit data on systems that are prone to errors in transmission or storage or that don't have any ECC built into the transfer protocols. That's effectively the same result. You are trying to reconstruct the full, original message/file and the checksum for certain pieces show damage so you use the additional data to reconstruct it. The math for the Reed–Solomon is similar in concept to oversampling the points on a line. You only need two points on a line to determine the actual path/slope, etc. so if you take three points, any two will allow you recreate the line.
It's old, but it's surprisingly not that old. From a cursory glance at Wikipedia, it looks like Shamir's paper was published in 1979, which is stunningly late for a technique that, in principle, could be done with pencil and paper.
When I first learned about SSSS, I asked my professor after class why it wasn't invented earlier. He replied that even thinking of trying something like SSSS first requires the insight that you can encode arbitrary data in numeric form, which only became obvious after the invention and proliferation of computers. Which, I suppose, is a good, concrete example of the notion that "a change in perspective is worth 80 IQ points" (Alan Kay).
While that's as good an explanation as any, I still suspect some clever 19th century mathematician could have come up with it as a way to protect e.g. the combination to a safe. Perhaps it was independently invented, but just never shared with the outside world. The whole notion that cryptography is a field of mathematics where results can and should be published to the world is, in itself, a bit recent, given the intense secrecy around the field as late as the Second World War.
"You can encode arbitrary data in numeric form" is Kurt Gödel in the first half of the 20th century.
His Incompleteness results show that you can essentially write "This statement is false" as a number and blow up the grand project of formalising all of mathematics as a single (edit: typos) infallible, provable monolith.
If that's the key insight you could do SSSS before any actual digital computers were built (those happen very slightly after Kurt Gödel does this work and Turing et al build on it)
> If that's the key insight you could do SSSS before any actual digital computers were built
The time window between Gödel's incompleteness theorems and the first digital computers seems to be roughly 1931 to 1946 (if you count ENIAC as the first). That very, very closely overlaps with the Second World War--and even the years before the war were treated by many governments as exactly that, years to prepare for war. I suspect that would put a damper on publishing any interesting results in cryptographic techniques, though to be fair, there is also no evidence that anyone secretly, independently invented SSSS during that period or during the 24 years afterward.
> "You can encode arbitrary data in numeric form" is Kurt Gödel in the first half of the 20th century.
Specifically, that's something like the first two thirds of his incompleteness proof spent establishing that as a fairly novel result, followed by rigorous mathematics to the effect of "Given a formula P(x,y) that asserts "We can't prove x(y,y).", can we prove P(P,P)?".
I’m not the one who posted it, but based on the number of folks who I’ve talked to unaware of SSSS, I wouldn’t be surprised if someone recently learned and decided to share the knowledge.
It's an XKCD1053 event - Somebody discovered something that was new and interesting to them, and probably decided to share it knowing there are other people who also aren't yet aware.
Dark Crystal[https://darkcrystal.pw] is perhaps my favorite implementation of this. It's built on top of Secure Scuttlebutt, and allows you to share private keys with trusted friends, so that you can later rebuild them when they are lost.
The only thing I remember about Secure Scuttlebutt is that it's anything but secure, but I can't for the life of me remember where I read it - can somebody jog my memory?
Might be because it's all written in somewhat hacky and not well-documented JS, making it harder to trust? There's an effort going right now to properly the (grown) protocol and provide reference implementations of the core components in Rust. Obviously, that doesn't make it secure per se, but it should make it much easier to reason about and audit.
Edit: apart from that, nanomonkey is right, if you post something publicly, it will be public. That's to be expected though. And assuming the use of libsodium is done correctly, there shouldn't be much of a problem with the primitives.
Now, the logic implemented on top of the protocol is a whole different story, sort of like most ethereum cautionary tales are not about ethereum being buggy, but people running buggy code on ethereum.
Well, public messages are...public. So anyone can follow you and view your posts. Once the data is out there, it can't be taken back. Private messages are encrypted, and only the sender's metadata can be viewed.
If you know of other insecurities, I'd be interested in hearing them.
This is fascinating but being neither a CS nor Maths graduate I'm having trouble following the maths from the moment modulo operations are introduced.
Would someone be able to suggest a self-learning resource (book, app, ...) that goes into cryptography and the required maths but doesn't demand too much pre-knowledge?
Whoever posted this may be interested in this (exploded) thread about decentralized surveillance, no spooks needed, which crucially relies on treshold crypto:
It's one of my least favourite things about vault as a product - it would have been technically feasible to not require unsealing for read-only operations, and thus not made a 2am restart a critical failure. I made a PoC once (I don't think it's still published anywhere) that does exactly this. Unfortunately they chose not to do this.
Admittedly simplicity is a feature in and of itself, and the read-only unsealing requires more complex asymmetric cryptography, but the excellent nacl[0] makes this a lot easier than it used to be.
I kid you not, the main reason we haven't implemented vault yet, is not because we're worried about security. It's because we're deathly afraid of locking ourselves out by making a mistake, taking the whole system down.
Meaning, this makes Vault more of a "let's really dedicate time to think of every possible scenario" type implementation rather than "let's just keep adding a couple of secrets a week".
It is possible to control both the number of key shares and the threshold required to unseal Vault (and now to do automatic unseal too), so I’m not certain this particular condition should be too much of a concern anymore. That said, considering as many scenarios as possible is definitely sensible!
I really do not understand your frustration. We are running 5 node cluster in production with the keepalived and nobody needs to wake up unsealing if one, or two instances fail. Perfectly good to do it in the morning by copy pasting curl oneliner from the keepass.
Then the part where using integers leaks information, and how to attack that, gets a bit hairier but is still a moderately accessible way to show cryptanalysis in practice. The fix using finite fields is then probably a step too far for most laypeople, and can be used as a lesson in how the fundamentals can be simple, but the devil is in the details.