Today I was thinking about the idea that you could implement a software-based multi-factor encryption key for a wallet. What comes to mind is Shamir's Secret Sharing, but in reverse. I'll explain what that means after I explain basic SSS.
GoalModify wallet encryption, which normally requires the user to enter a password, and then key stretches it into a symmetric encryption key (such as AES256) and uses that to encrypt the wallet private keys. What I would like is: during wallet setup, you can have 3 passwords entered, and any 2 of them would be sufficient for the system to compute the AES256 encryption key. Of course, it would be nice to implement any M-of-N.
The idea is that 3 employees of an [wing of] an organization would be responsible for managing either a single-sig wallet, or a single key of a multi-sig wallet. In order to gain access to the offline key to sign transactions, the wallet will need to be decrypted, but the decryption key can't be calculated from any single employee's password.
BackgroundShamir's Secret Sharing is a mechanism by which a secret piece of data is interpretted as the highest order coefficeint of a polynomial, and then points of that polynomial are distributed and stored separately. For instance, you store the secret as the slope of a line, and then you write down three points of the line on separate pieces of paper. If you have any two pieces of paper, you have two points on the line and can compute the slope--which recovers the secret. This would be 2-of-3. You can do this with any M and N, using N points on an (M-1)th order polynomial.
While this concept is easy to visualize like we did in high school, you can't use floating point numbers because of precision issues. Instead, you do all operations on finite fields, which are really just modulo-arithmatic, cyclic groups. You simply define all operations to be on integers between 1 and some large prime N, define division to be a/b = a * b
N-1, and then you can implement all the algebra identically. I won't go into the details here, but this
is how SSS is implemented in crypto systems. However, usually the prime N is chosen ahead of time, and known by the device, so it knows which finite field to use to combine the points.
Rephrased goal: Shamir's Secret Sharing is a process for converting a secret into M-of-N shares to be distributed. What I want is a process for converting N shares (user passwords) into an M-of-N secret. It's the inverse of the problem being solved by SSS.
Half-way thereIf this was 2-of-2, 3-of-3, or M-of-M, stock SSS would work. Say for 3-of-3: the system collects all three passwords when the wallet is created, computes the highest-order coeffiicent of the parabola created by the hash of all three passwords (perhaps using the first four bytes of the hash as the X-value, and the remaining as the Y-value), then uses that as the encryption key for the wallet. When all passwords are entered, the system can compute this value, decrypt the wallet, then destroy it. This works, though there are simpler ways to combine mulitple passwords. But how do you do arbitrary M-of-N?
DiscussionBut this doesn't work for M-of-N where M is not equal to N. For 2-of-3: you would like to compute a slope that could be computed from any two of the three points, but the three points are not co-linear in a pre-defined finite field. One way would be to collect all the passwords first, and then figure out a set of finite field parameters for which all three points are colinear (for simple prime-based finite fields, try to find a prime N such that they are colinear). Store the FF parameters in the wallet, and the wallet will use that data when two passwords are entered. But this feels like a hack.
Unfortunately, my googling skills are failing me -- as I keep running into a bunch of unrelated things. I feel like this must be a solved problem, and I just need to find the right documentation of it.
AlternativesThe best alternative is to simply not let users create passwords, but create a secure encryption key, then use SSS and put the shares onto smartcards. In the institutional security world, this is at least how backups are made when using HSMs (and how Armory does fragmented backups of its wallets). In this case, we're simply trying to expand on the user-password concept to be executed on consumer PCs. At the moment, HSMs don't exist in the BTC world, and while they may, it would still be cool to have a solution for this problem here.
Another alternative, for small M and N is to simply store all N-choose-M multi-encrypted forms of the encryption key. For instance, for 2-of-3, the encryption key will be randomly generated by the system, and then it will be stored 3 times in the wallet, each one encrypted with a different 2 keys. Decrypting would simply be matter of trying to decrypt all three keys and picking the one that works (if any). But this is an even bigger hack, and it doesn't scale very well (though modern computers could handle most use-cases pretty easily if there was no additional key stretching).
CaveatsI recognize we're still talking about a single piece of consumer hardware that could be compromised by malware, or someone with DMA could swipe the key from RAM once all passwords are entered, etc. The goal is to provide a mechanism whereby multiple people are required to access the system, and together they monitor all interactions with the system and verify that no one is tampering/manipulating it. Is it failproof? No. But it still prevents one person who temporarily gains access from pulling the key off the disk, even if they have one password. If proper access control is exercised, this might provide another tool for implementing segregation of duties, in-place-of or in-addition-to multi-sig transactions.
In the future, this might be moot, since orgs will move to HSMs which are all tamper-proof, destroy the private keys if you try to open, implement similar M-of-N access control, etc. But for consumer hardware, I think this could be pretty strong.
