Home  Blog  About Us  Work we do  Content  Contact Us 
Just about everything we touch online these days requires a password (and certainly all sensitive information is protected by one).
Passwords work because they are a secret. At its most basic, a password is a key, theoretically, only known by the person(s) who are supposed to know it. Knowledge of a password gives access to the person who is aware of the secret. Most password systems only use one password and only require one person present to unlock. Its analogous to a door with a lock. 
What if you wanted to add additional levels of security such that it required more than one person�s permission to access some service? (More than one lock on the door). Here are a few examples:
However, with a little imagination we can conceive some more advanced scenarios: 
With your business partners, you agree that any two of the four people, together, have sufficient privilege to access the bank account. It can be any combination of two, and at any time it might be a different pair.
To launch the nuclear missile, you define a hierarchy of passwords with different strengths. The password of The President, for instance, could count as three votes. That of The Secretary of Defense counts as two, and all others count as one. So, The President and The Secretary of Defense, together, have the authority to launch the missiles, as does The President and the votes of three ordinary grunts, or five grunts together … etc.
Maybe some of the family members who have passwords to read the will are old, and might die themselves before the will is to be opened. You don�t want to encrypt the will and find out that, if some of the other members of the family pass on, that the information in the will is lost forever. You would also like the ability to grant passwords to newly discovered “next of kin” family members without requiring those already holding passwords to have to change theirs.
Or how about a totally weird scenario (which is really just a canononical form of the examples above)?:
Someone is hopeless at remembering passwords, so elects to write their password down. However, they do not want their password to be written where anyone can simply read it, so they break it up into a set of twelve subpasswords. These subpasswords are then hidden. They put one in their wallet, another in their desk at work, one on a bulletin board in the kitchen, one in the bedside table, one on their laptop, one at their brother�s house … Any subset combination of four of these is required to gain access, and any less than this is totally useless. When access is required, the nearest four subpasswords are retreived and correctly used.
These are interesting challenges. Before I show a solution, it�s worthwhile enumerating, explicitly, the desired characteristics of a good multipassword solution:
If a password is broken down into a collection of subpasswords, exposure of one of the subpasswords should not give an attacker any further hints of the solution. (For example if there are four passwords in a set and, for whatever reason, I know password P_{1}, if I also learn the values of P_{2} and/or P_{3} or P_{4}, it should give me no more knowledge about how to unlock the cypher than I have by knowing just P_{1}). All subpasswords should be required to obtain a solution, and knowledge of even allbutone of them, should give the attacker no more advantage then knowing none at all.
Ideally, the subpasswords in the set should by the same order of magnitude in length as the master password they combine to create. (We don�t want to turn a 12 character master password into 6 subpasswords that are hundreds of characters long each).
It would be desirable, if one of the subpasswords happened to be exposed, to allow a new master password to be generated without having to reissue new subpasswords to the nonexposed ones (So you can give a password to your brother before he leaves on a 10 year offthegrid expedition and be able to allow him keep the same password, even if things change). Bonus marks if he can keep the same password if the number of sub passwords changes through the years (additions or subtractions).
It would be nice to have the ability to generate new viable subpasswords without having to reissue all new passwords. (For instance, if one of the subpasswords was written on piece of paper which got burned before anyone could read it).
There is a system for generating and decoding passwords that enables all of this functionality. It�s called Shamir�s Algorithm. We�ll look at how it works in short while, but first let�s look at some other solutions that partially work, and examine their limitations …
This is as simple as it sounds; we simply take the master password and carve it up into the number of subpasswords we desire. For instance if the master password is �PRINCESS�, we could distribute this to four people like this:
We don�t have to do this at a character level, we could perform it at bit level if necessary, carving up a string, and/or we could stripe the slices rather than taking it in chunks, but however we do it, its not ideal.
It doesn�t take too long to see issues with a carveup strategy. The first issue, is that it gives away part of the final solution in the clear. Each password contains part of the master solution, greatly reducing the space that a bruteforce attack would need. Secondly, if you happened to “stumbleupon” other subpasswords, you could append these to yours and further reduce the address space. Each subpassword you encounter gives you more information about the solution.
It�s not a very elegant solution. Fundamentally, though, the biggest drawback is the need to have all components present to unlock. If you break a password into n subpasswords, then you need all of these present to recreate the original! This does not fulfill our desire to be able to grant access to a smaller subset of people. It's like smashing a plate into lots of pieces. You need to have all the pieces if you need put it back together again. 
A slightly more elegant solution, which solves the problem of exposure of multiple passwords giving you more information, relies on the concept of random offsets. Whilst this solution is superior to the carveup method, it still suffers from the restriction that all subsecrets need to be present to be recombined to generate the original password. It's still a broken plate reconstruction problem!
Let�s imagine that the secret we are trying to scramble (our password) is a number. We call this secret number S. (If our secret is not a number, it�s very easy to encode a text string into a number).
If we want to generate n subpasswords, all we do is generate n1 random numbers (positive or negative).
Let�s call these random numbers: R_{1}, R_{2}, R_{3} … R_{n1}
For the last subpassword, we give it the value: (S  R_{1}  R_{2}  R_{3} … R_{n1})
To the left is an example of breaking the password into six subpasswords. The first five subpasswords are randomly generated, and the last is calculated such that adding all the subpasswords generates the required sum. Now, to recreate the secret, everyone simply needs to add their subpasswords. Individually, nobody has any information about what is the secret and what is random, and even if n1 people got together and colluded, they are still unable to determine from the missing piece what is random and what is real. 
Another variant of this uses the bitwise exclusive or operation XOR. (One or the other, but not both).
The XOR function has a useful property that when applied twice with the same value it returns the input to its original state (A XOR B) XOR B = A As before, the first n1 subpasswords are created as random numbers. To generate the last we calculate it using the formula S XOR R_{1} XOR R_{2} XOR R_{3} XOR … XOR R_{n1} 
To reveal the secret S we get everyone to XOR their subpasswords. The double application of XOR on each random number toggles each bit to its original state.
As before, this system will only work if all subpasswords are present, which is both a blessing and a curse. Without all subpasswords being available, collusion or exposure of any combination of passwords will reveal nothing about the solution.
OK, it�s now time to reveal an algorithm that meets all our requirements. The algorithm I'm going to discusss is called Shamir�s Algorithm. It involves a little math, but not too much, and I�ll try to introduce the concepts slowly. Key to the utility of this algorithm is that it does not force the restriction that the number of subpasswords to decrypt has to be the same as the number of subpasswords generated. We can tweak the parameters such that any number of subpasswords (less than or equal to the total number generated), can be used to unlock. All the King's Horses and all the King's men, would be proud! It is possible to put Humpty Dumpty back together again … and we don't need all his pieces to do it! 
Imagine a sheet of graph paper. On this piece of graph paper we�re going to plot a point. For this example, we'll use the coordinates (25,20) This is your password! (bear with me, all will be revealed later). If I asked you to draw a line that passed through this point, how would you draw it? 
Below are some example lines. In fact, there are an infinite number of ways to draw a line through one point. To correctly desribe a straight line using points, you need at least two.
This is where we introduce our secret S, by setting this as the intercept with the yaxis. There is only one line that passes through this intercept and also through our coordinate (see below).
The equation of a straight line can be described with the equation: Y = mX + C Where m is the gradient (slope) of the line, and C is the intercept (where the line crosses the vertical axis). We can see that the secret S is the intercept (C) of a unique straight line that passes through our point. Only this line passes through these two points. 
Any two points along this line are all that is needed to describe the line, and using these two points allows the intercept to be determined.
And here, in its simplest form, is our algorithm. In this implementation, because it is a straight line, two points are needed.
We can create any number of points on this line that we desire. We can distribute hundreds of coordinates and give them out. Individually, each coordinate is totally useless. There are an infinite number of potential lines that pass through any single point. However, if two people get together and pool their knowledge, they can recreate the line and thus determine the intercept, and find the secret. As you can see from the geometery, it can be any two people. Awesome! 
OK, let's move on from linear to quadratic. Straight lines are what mathematicians call order1 polynomials. To describe a straight line, in addition to the constant C, you need just one parameter, which describes how to apply the independent variable. This is why you need two points to fully describe a line; you need to two simmultaneous equations to determine the parameters.
Quadratic equations are order2 polynomials. To describe a quadratic, in addition to the constant C, you need two parameters.
A quadratic equation can be described by the function y = Ax^{2} + Bx + C
With only two points, there are an infinite number of quadratic curves that can be fitted through them. Here are a few examples:
I think you can probably see where we are going with this one. As before, we'll encode our secret S as the intercept of our polynomial with the yaxis. Now, all we need to do is describe the curve.
Here is an example quadratic curve. Using three points we can completely describe a quadratic curve. As with the linear example, we can create as many point as we desrire along the curve and give these subsecrets to whoever we wish. With a quadratic, however, three of these people need to get together to decode the secret. It can be any three people, but three people are needed. 
And so, on and so on. Here are some order3 polynomials (commonly called a cubics). Four points are needed to fully describe a cubic function. If we encoded our secret with a cubic function and distributed coordinate subpasswords it would require any combination of four points to determine the intercept and the secret.
We can keep increasing the degree (order) of the polynomial as needed to break the problem down into the required number of slices. An ordern polynomial curve requires n+1 points to accurately describe it.
Let's review the list of ideal characteristics discussed above and see how this solution handles them:
We can see how this algorithm is not a brokenplate type problem. We don't need all the subpasswords to recreate the secret. All we need is sufficient to mathematically solve the order of the equation we are using. 

Knowledge of any noncomplete combination of subpasswords gives an attacker no additional information on how to solve the problem. Even if you have knowledge of n1 passwords, there are still an infinite number of curves that fit through these points, and thus an infinite number of possible intercepts. 

As we can clearly see, it's very easy to generate new subpasswords as needed. If we need to generate and distribute a new subpassword, we simply pull off another coordinate from the curve and give that out! None of the existing passwords need to change. 

If some of the subpasswords are compromised (and you know which ones) and you want to regenerate new ones, but keep the uncompromised ones the same, you can generate a new curve that passes through the points you wish to keep. 

To weight passwords (such as giving The President a nuclear launch password with three times the power of a regular password), we simply give out multiple coordinates to that person. Thus, for the nuclear launch example requiring requiring five votes, we generate an order4 polynomial, give The President three coordinates from the curve, The Secretary of Defence two coordinates off the curve, and the rest of the troops one coordinate each. 
Check out other interesting blog^{}articles. You might like this one about PIN passwords.