Here’s an interesting brainteaser for any developer out there: How do you create a password that’s shared between a group of people, with each individual knowing a small part of it, and only when they act in unison is the password reassembled and usable?
This isn’t just a hypothetical; it could help in situations where multiple people need to act as one. Just to make things extra-interesting, we want to build in a redundancy, so the full password can still be recovered even if one or two people are absent. (If the password is split between five people, for example, the individual components from three or more people should be enough to recover the password.)
Now let’s make things extra-super-interesting, by insisting that the plaintext of the password is never stored anywhere after the initial generation, only in the text of the individual “pieces.” When those pieces come together, each part is hashed, and multiple hashes are used to produce the full password. (A hash means a one-way function that takes a string and produces a number; there should be no reverse function possible.)
Let’s get to work.
How to Have Multiple Parts
It’s an easy conundrum to navigate if we ignore the hashes initially.
Say the password is 15 characters long (say, abc-def-ghi-jkl-mno; I’ve added the dashes to make it easier to read).
We want to set things up so any three parts will yield the password; as a result, each part has to be at least five characters long. In fact, every character in the password has to occur three times so that any combination of three passwords from five includes everything necessary; otherwise, it would be possible to have a combination that would lack one letter.
Let’s assume that passwords can be entered in any order, but they contain information that supplies a unique third of the password. For 3 out of 5 there are 5!/((5-3)! x 3!) = 10 different combinations:
- 5! = 5 x 4 x 3 x 2 x 1 = 120,
- while 3! = 3 x 2 x 1 = 6 = 20
- and 2! = 2
- so it’s 120/(2 x 6) = 10.
If we number the individual “password parts” 1-5, then the following combinations are produced; this list shows which all unique combinations available to the people who enter the password parts:
For 123, if Participant 1 has ‘abc,’ Participant 2 has ‘def,’ and so on, not only do they enter abc, def, ghi, etc., they also need to provide jkl and mno. As a result, no matter which three people enter their passwords, the combination provides the full password.
The password might include duplicates of letters—but what’s important here isn’t just the letters themselves, but also their position vis-à-vis the password. Only if the correct 15 letters are in the correct 15 places is the password valid.
The simplest way (albeit not very secure) would be to assign positions of letters to each of the five people, then generate a code for each person. Later they reenter the code, which is transformed to reveal letters and positions. For further security, each code is checksummed, and no attempt made to validate individual codes on entry, except when three separate codes are entered.
A better solution is randomly assigning letters and positions to the five people. But is that really secure? It seems to depend heavily on the five not leaving individual passwords to anyone, and software accepting any three codes as well-written.
Given that each plaintext password has 9 characters (and positions), it might be convenient to output the password as five groups of 4 characters. Something like R5T6-Z4RU-MN9J-TT2Q-FGT7, which is a bit like license unlock codes for software.
The Pros and the Cons
I said at the start that a hash function was needed, but clearly this method uses a reversible function. The original password of 9 characters and positions has to be transformed into the 20-character code; then it has to be transformed back. This isn’t quite as strong as a hash. The algorithm used should be published.
The original 15-character password need not (and should not) be stored in plaintext, just the hash of it using SHA-256 or SHA-512. This hash is also compared to the reconstructed password after three codes have been entered and converted back to characters, and the characters moved into their original positions; if the hashes are the same, the password is valid.
Implementing this system requires a two-way conversion function. It also requires the use of a random-number function to create the initial 15-character password, and then to create the five sets of characters and positions. Using a very long run PRNG such as a Mersenne Twister can prevent attempts at brute forcing.
Note that I’ve used the letters a-o in this example, but that the initial password can be made up from any set of characters, digits, and so on. The principles explained here can also work for longer passwords and differing numbers of participants.
If you want a proof of concept for splitting the password, check out this console program I wrote on GitHub. This is just used to generate the original password; it uses two files (SFMT.cs and RandomBase.cs) uncahgned from a fast C# Mersenne Twitter implementation (SFMT).
From this password, five unique and random nine character long passwords are generated using these chars. The position of each of the chars in the original password is also held:
The numbers are the positions of the characters in the 9-letter password that correspond to placement within the 15-letter master password. So Q in JQYODCAXB is position 5 in JOGUDQXREBYCKPA.
These 9 letter passwords and positions are combined and converted into the following strings:
Any three of these can be entered and combined to produce the original password.