By Henri Bourdeau, published 2023-10-15
Hey there! This is a work-in-progress version of the article. You will stumble on text like this:
TODO remove the WIP introduction.
They are placeholder for missing part of the article, usually the illustrations. So don’t worry about skipping them.
Where is the best place to keep record of all your passwords?
👉 A password manager such as KeePassX.
How to generate a secure password manager master key?
👉 Using diceware or the original dice version.
How do you synchronize the password manager across devices?
👉 Using Syncthing.
But how do you backup the password manager master key?
And how do you transfer it to your loved ones if something happens to you?
The main use case to me is to let my loved ones access my password manager if something happens to me. When the time comes, I will not be there to walk them through it.
With Secret Splitter, you do not need to be a rocket scientist to make it work. The decoding logic is especially straightforward.
This page explains how Secret Splitter works:
You do not need to read and understand that last part to use or code Secret Splitter yourself.
If you want to skip directly to using it, here are links to:
Similar tools / other implementations that I know of:
Shamir’s Secret Sharing, Secret Splitter is based on it
If you know Shamir’s Secret Sharing algorithm, the main difference is that Secret Splitter works on fixed-size blocks of the secret. So Secret Splitter can skip the search for a prime number bigger than the secret, making splitting secrets much faster.
Hey there, I’m optional content! Click me to hear what I have to say.
Tu fully understand how Secret-Splitter works, you will need basic knowledge about some mathematical tools.
Boxes like me will appear from time to time to explain those tools to you. Feel free to skip us if you already know them, or are just looking for a high-level overview of Secret-Splitter.Before we start: what’s a polynomial?
This section will teach you what you need to know about polynomials to fully understand how secret splitter works.
A Polynomial is a curve that can be more or less curvy. Every polynomial has a degree, D, that tells you how curvy it is.
TODO canvas with default image, polynomials of degree 0, 1, 3 + legend. with JS, a button to increase/decrease the degree, starting at 0, + dynamic redraw of the polynomial
See how the shape of the polynomial changes when you increase or decrease its order.
As you can see, a polynomial of degree 0 is just a flat line. Increasing the degree to 1 adds a slope. Increasing it to 2 adds a turn. Every further increase will add a new turn.
Another way to look at it is that the degree tells you how many times a given polynomial can cross a flat line.
TODO smame canvas + flat horizontal line that can be dragged up and down to see them cross. If possible, highlight intersections.
Move the horizontal line up and down and see how many times you can get it to cross the polynomial.
TODO special sentense for 0?
What makes polynomials useful for secret splitter is that:
👉There is only one polynomial of degree D going through a given list of D+1 points.
TODO canvas where reader chooses number of points + can move the points around, and we draw the polynomial
Pick a number of points and move them up and down to see how the corresponding polynomial changes. Can you always make it look like a straight line?
👉 You can always make a polynomial of a higher degree look like one of a smaller degree.
TODO canvas where you choose a degree + “target” degree that is lower. It draws a polynomial of degree target, and the user can move the chosen+1 points and see the reulting polynomial.
Move the points of your polynomial up and down. Can you make it match the target polynomial?
So to share a polynomial of degree D with someone else, you just need to give them examples of points on that polynomial.
TODO user can choose the degree of a polynomial that is automatically generated & drawn. By clicking on the polynomial, they can select points on it. The canvas then draws the polynomial that goes through those selected points.
Click on the blue polynomial above to select the points to send. The yellow line is the polynomial rebuilt using those points.
How many points to you need to give them so they can retrieve the polynomial? What happens if you give them more? What happens if you give them less points?
And that’s it, you now know everything you need about polynomials!
I will use shapes and colors to differentiate points. Points with the same shape belong to the same polynomial.
Points are initially grouped by shape: each byte has its own polynomial.
Each piece has one point of each byte: one piece has all the points of a given color.
Notice that some colors are missing: you don’t necessarily need all the pieces.
Points are grouped by shape again: for each byte of the mask, you have some of the points of its polynomial.
This works because you need exactly D points to uniquely identify a polynomial of degree D-1.
If N is at least as big as D, you have D points or more for each byte of the mask. This is enough to identify the original polynomials and retrieve their value at 0: the original mask.
But if N is smaller than D, you don’t have enough information to retrieve the mask and decode the secret.
If this feels like magic, have a look at the previous section Before we start: what’s a polynomial to see it all in action.
As a bonus, if you have more than D pieces you can check if someone tried to cheat by corrupting their piece:
If the result of step 2 is different from the one of 1 then yes, the piece is corrupt.
But the result of step 2 is still the correct secret! The corruption attempt was useless, and you have exposed the fraud.
This section explicits the format used to store puzzle pieces generated with Secret Splitter.
A puzzle piece is a yaml serialisation of the following mapping:
# name of the algorithm used for splittingalgorithm: block-wise SSS# base64 representation of the result of the mask XOR the byte representation of the secretencoded secret: YXo=# string, tells if the secret encoded is a string encoded as UTF-8 ("utf-8") or a raw stream of bytes ("none")encoding: utf-8# one puzzle piece, exact format depending on the algorithm# this implementation, block-wise SSS, stores a sequence of [point, value] items, one per block of the secret# Flow-sequence format preferred to keep it on one linepuzzle piece:[[1,258],[1,3]]# different algorithms might add additional fields required for recovering the secretNote that for the puzzle piece to be valid, there should be one puzzle sub-piece per byte of the encoded secret.
An attacker wants to know your secret. They know that you have used Secret Splitter to make pieces out of it.
The question is: does it make their job easier? What if they got hold of some of the pieces?
I will measure how much this knowledge makes brute-force attacks easier. This is agnostic of the kind of secrets, and quantifies the usability of that knowledge. The same reasoning applies to more sophisticated, use-case specific attacks.
The short answer is:
👉 Naive use of Secret Splitter reveals the length of your secret and whether it is some text or a file.
As we will see, you can easily avoid that by adding context to the secret you store (jump to section).
If you trust that person to store their piece as securely as you would, then it’s actually harder to steal the D pieces than it is to steal the secret directly from you: an attacker would have to steal that piece number D, plus some extra work to get the previous D-1 pieces.
For each one, they try it out and see if it is the correct one.
For a password manager master key for example, this means trying to unlock the database.
If not, they move on to the next possible value.
An attacker will need to try on average half of all the possible values before finding your secret. Intuitively there is a 50% chance to have already seen your secret once they have been through half of them.
The benefits of that kind of attacks are:
The drawbacks are:
So attackers cannot actually test all possible values. They have to make assumptions reduce the number of possible values:
And here I only consider 8 bytes secrets. Doubling the size of your secret squares the number of possibilities. There are 160 million billion ways to take 4 words out of the 20,000 common English words.
This is why longer secrets are usually better than short but complex ones. My master key is 7 words generated with the original diceware method. That’s one of about 2 billion billion billion possibilities. Yet, easy to remember.
The main drawback is that any wrong assumption dooms the attacker. Your secret is just not among the possibilities they are considering. But they will only find that out after doing all the work.
A Secret Splitter piece contains the following information:
encoded secret the result of random mask XOR secret bytes.encoding Is the secret a string or binary data?puzzle piece For each byte of the mask, one point of a D-1 degree polynomial that equals the value of that byte when evaluated at 0.Both encoded secret and puzzle piece reveal the length of the secret. Without it, attackers have to first go through all values of size 1, then all of size 2, etc… By starting at the right size, they skip a lot of work.
On raw binary data, this saves about 66% of the effective average work: Without the size information, attackers have to first waste the possibilities of sizes lower than n. They would then on average go through half of the possibilities of size n. With it, it’s just on average half of the possibilities of size n.
It diminishes very quickly for non-binary data however. For a password in lower-case Latin characters, an attacker would only save about 7.4% of the work. Add upper-case and its down to around 3.8%.
Where do those numbers come from?
For a secret of length with possible values for each character, an attacker needs on average attempts to brute-force the secret knowing its lenght, and attempts without knowing it.
The amount of work saved is .
Using , we get:
So in practice, knowing the length of your secret is not very valuable.
If it still troubles you, there is a very easy way to make that knowledge completely useless:
The idea is to add useful information for whoever will need to use your secret in what you split using Secret Splitter.
For example if you are splitting the password
MySuperPassword, use Secret Splitter on:
Here is the master key to my keepass database: "MySuperPassword"
You will make the size of encoded secret larger than the actual secret. So attackers deciding to use that information are doomed: they believe the secret to be larger than it is!
As a bonus, by including instructions with the secret, you are making sure that they will never be lost.
You can apply the same trick to binary data by encoding them in base64 first:
Here is the base64 encoded gzip archive storing my secret: H4sIAAAAAAAAAw3K0Q2AIAwFwFXeEMYZdIwKL9BEC2kJRqfX77uNTmhAMOkPTvFCBJNzYFQZ2FFlEqld3RnBjFtHRXm1Qyz/iQZaavknNRwSXJcPmrlj8lcAAAA=
encoding: utf-8 indicates that the secret consists of readable characters.
But remember that to try and guess your secret, attackers need a way to test if their guesses are correct. So they would already get that information from the context.
If an attacker holds D or more pieces of the puzzle, they can decode the puzzle.
That is a feature.
If they hold less than D pieces, they can’t. However the pieces they hold might leak some information about what your secret could be.
This depends on how the random polynomials were generated in step 5 of Encoding / creating the puzzle
Even if an attacker gets holds of D-1 pieces of your secret, they won’t learn anything about your secret from them.
See section How secure is Secret Splitter? - the math for the proof.
Secret Splitter is about finding points on polynomial curves:
For that, Secret Splitter relies on Lagrange Interpolation. I will start by showing you how it works when decoding a puzzle, as it is simpler. We will then look at creating the Secret Splitter puzzle.
This section explains step 3 and 4 from Decoding / solving the puzzle above.
After step 2, you have a list of at least N points, for each byte of the mask. You know that those points are values taken by polynomials of degree D-1.
You need to find the value taken by those polynomials at 0.
Using Lagrange Interpolation, the value at 0 is the sum of each value multiplied by a corresponding interpolation factor :
With:
And that’s it!
Repeat for each byte of the mask and XOR the result with the encoded secret provided in each puzzle piece. If N is bigger or equal to D, you have decoded the secret. If not, you have random data.
The in controls which point you are getting. By changing it to any other value , the formula above gives you , the value taken by the polynomial at that point.
This section explains step 5 from Encoding / creating the puzzle above.
To create a puzzle requiring D pieces to solve, you need to generate random polynomials of degree D-1. They should each take at 0 the value of a byte of the mask given by step 4.
You then sample T points on each of those polynomials using Lagrange Interpolation, exactly as when decoding a puzzle. You just change in the formula above by the -coordinates of the points you want.
So to create a puzzle from your secret, Secret Splitter will, for each byte of the mask:
This gives you a total of T pieces for each byte of the sub-puzzle. You can then proceed with step 6.
By design:
The tricky part is to generate the random polynomials correctly.
Do it right and attackers won’t learn anything about your secret until they hold at least D pieces of the puzzle. But do it wrong and just a couple of pieces can give enough information to make brute-force attacks on the secret trivial.
My implementation does it right. But to show you how, and prove you why, we need two more tools: modular arythmetics and uniform probability distributions.
Arythmetics is the part of Maths about adding, substracting, multiplying and dividing numbers together.
If we put all numbers on a rod, adding and substracting means going right or left.
Adding 3 is moving 3 ticks to the right. Substracting 3 moving 3 ticks to the left.
TODO image with the line of real numbers, some points and example of moving them by additions/substractions
Multiplying and dividing is inflating or deflating the rod.
Multiplying by 3 is inflating the rod until every tick fills the space previously held by 3 ticks. Dividing by 3 deflating the rod until it takes 3 ticks to fill the space previously held by one tick.
TODO image with the line of real numbers, some points and example of scaling them by multiplications/divisions
First, you put a teleportation portal on 0. Then you pick the modulus number, say 4, and put a teleportation portal on it.
Now everything that goes into one of the portals continues its way, but getting out from the other portal.
If you were to stand on that number rod, you would see something like this:
image from the portal game
Which translates to this when looked at from the side:
infinite rod with repeating portals, tick numbers that reset every time
For additions, substractions and multiplications you can keep on doing it just like regular arythmetics:
TODO image with 2+3%4
It’s just that to read the result, you start counting the number of ticks since the last portal.
A more analytical way to do modular arythmetics is to ignore the modulus to start with and do your computations as usual. Once you get your result, you check if it’s bigger than your modulus. If yes, you substract the modulus over and over until your result is smaller than it. If your result is negative, you do the opposite and add your modulus over and over until the result gets positive.
For example , which is bigger than 4. So
TODO two pictures of the numer rod, one without portals on which we do 3x3, and a second one were we add the portals and read the result
Dividing is a bit trickier.
In regular arythmetics, for any number you can find one number such that . This number is called the inverse. Dividing by is the same as multiplying by its inverse.
But in modular arythmetics, there can be several different numbers that qualify as the inverse.
If we look for inverses of 3 modulus 4, the following numbers work.
So say you want to divide 2 by 3. You will get different results depending on which number you pick as the inverse of 3. This is not very practical, we need a way to decide which one is the real inverse of 3 modulus 4.
The inverse of an integer in modular arythmetics is, when it exists, the integer that gives 1 when multiplied by your number. If it exists, the good news is it’s unique. But the bad news is it doesn’t always exist.
So the inverse of 3 modulus 4 is 3. But 2 does not have an inverse modulus 4: you cannot divide by 2 modulus 4.
A last thing about modular division:
There are some integers that stand out in arythmetics because they only have two integer divisors, one and themselves. Those numbers are called prime numbers.
👉 If your modulus is a prime number, then every integer except 0 has a modular inverse. This will be very useful for Secret Splitter.