Consider generating new shared Qubes Master Signing Key

[rootkovska]

I think it's a nobrainer to state that it would be beneficial for everybody, i.e. the project, its users, and even myself, if we could get a new Qubes Master Signing Key (QMSK), such that could be shared between N parties, of which M would be required to meet in order to use the key to sign other keys (i.e. the specific Release Signing Keys).

For this effort to make sense, there are a few additional requirements though:

1. There should be just one key, usable the same way as standard GPG keys are used to sign/verify software. The solution that N people have just N keys and all of them sign the other keys, is simply not acceptable from the user point of view.

2. None of the N holders should be able to walk away with the full QMSK after any of the signing ceremony.

3. The owner of the laptop on which the creation and/or any of the further ceremonies take place, should also not be able to steal the QMSK.

The recent discussion on qubes-devel [1] has encouraged me to think again about this problem and I've come up with the following idea which I'd like that we further discuss:

1. Assuming we have a laptop that approximates the idea of a stateless laptop [2] reasonably well (of course, I'm realistic enough to know we won't have any True Stateless Laptop anytime soon). Let's call this laptop: Laptop. Also, we shall defer the discussion about how well should this approximation be, until some later time. Meanwhile I'm more interested in discussing other aspects of this proposal.

2. The Laptop runs Tails and uses encrypted persistent partition (likely LUKS-based, like the standard Persistence mode in Tails does), which is called Persistent Partition. The Persistent Partition is unlockable with a keyfile, which we shall call: the Keyfile.

3. During the Initial Ceremony, we generate: 1) the new QMSK, and 2) the Keyfile which will be used for the Persistent Partition encryption. The Keyfile is then used to mount the Persistent Partition and the new QMSK is moved onto this partition.

4. Still at the Initial Ceremony, the keyfile is split among N parties, creating N Shared Keys. This likely could be achieved using the ssss program (don't remember if it's part of the standard Tails distro, if not, we should use something that is, or convince Tails people to include it :)

5. The original Keyfile is then destroyed (here's where one of the benefits of using Tails for this exercise become clear, another benefit: we can use nearly arbitrary old machine as the Laptop)

6. Subsequently, whenever there is a need to use the QMSK, e.g. to sign the new Qubes Release Key, at least M out of N parties needs to meet, boot the Laptop using Tails, plug at least M USB sticks, combine the M Shared Keys, recreate the Keyfile, then mount the Persistent Partition.

7. Once the Persistent Partition gets mounted, we can create new keys (e.g. Release Signing Key), and sign them with the Master Key. Also, in case we needed to sign some other keys (e.g. other people's key), we the the trick suggested by @petertodd might be used: a one-time-use Binding Keys could be created, and signed by the QMSK. Note: I'm not really convinced about the idea of bi-directional signing (i.e. to have the binding key also sign the QMSK) -- this seems like some superficial trick, not really needed by us.

8. Once the keys are ready for export, we can copy them to some ephemeral fs, unmount the Persistent Partition (plus some make sure the memory with secrets also got wiped...), and subsequently export the keys, even using something like a USB stick...

Open issues:

1. What's the best way to import the Shared Keys? Plugging USB sticks obviously endangers the laptop to some attacks... Using HSMs does not change much hear, as these are... also USB devices. One option is to keep them on some read-only mediums (DVD), of course encrypted with some user-only-known passphrase.

2. It seems to me that the Persistent Partition could be also burnt to such a DVD, for even if we are going to be generating new keys there, these would be exported and no problem if we discard them from the Persistent Partition.

3. The choice of M and N. Right now I'm thinking M = 2, N = 3 (me, Marek, plus somebody only we know who). Other options might be possible though.

4. Will we ever have a need to sign any keys non-generated on the Laptop? Likely not: only Release Keys, and these should then sign individual developer's keys. Does this make most of the discussion in [1] futile, or am I missing something?

/cc @marmarek @andrewdavidwong @woju @petertodd

[1] https://groups.google.com/d/msg/qubes-devel/XreFo6RM47Q/U_jmqK5SBgAJ [2] https://blog.invisiblethings.org/papers/2015/state_harmful.pdf

[andrewdavidwong]

@rootkovska: This is a duplicate of #2535. Would you mind copy/pasting your comment there, since #2535 has existing cross-references?

[rootkovska]

Hm... that doesn't look quite like a duplicate? ISTM the two tickets have two different purposes: the #2535 is about eliminating the single Master Key, while this ticket is about how to make it significantly more secure, while still preserving the single QMSK. Also what I suggest here is orthogonal to the work on reproducible builds.

[Ekleog]

The scheme raised here assumes the stateless laptop has not been physically compromised by the one person who keeps it in store in-between meetings.

I hit the same issue recently and found [1], which would allow to split the key across multiple laptops without requiring that the key ever be reconstructed in the memory of a single computer (which would become a single point of compromise). Each owner of a part of the QMSK could have his own offline laptop for this use, and ensure its physical security by whatever means deemed relevant.

However, this would mean the data to be signed would have to transit between multiple such offline computers, which adds one layer of communication. Still, if data only moves from/to such offline laptops, the security should be still at least the same as with a single trusted hardware.

The issue I see with this scheme is the need to generate the key on a single computer, which would allow this computer to steal the entire key. A solution to counter this could be to physically go to the store all three, agree on a low-cost computer, generate a key on it in a completely isolated environment and, once the key is split in parts and given to the ones who should have it, physically destroy the computer.

I don't know if you want to go to such lengths to protect the QMSK, but this would mitigate the threat of "the developer storing the stateless laptop can physically tamper with it to recover the full QMSK," and require that such a developer also has to figure out a flaw in the scheme used to transfer data to other secure laptops to compromise them and recover the full QMSK. In a partial version without the destroying-a-computer part, it would defend against future compromise of the developer holding the stateless laptop.

[1] https://link.springer.com/chapter/10.1007/11596981_28 , unfortunately it seems to be behind a paywall. Basically, it splits a RSA key in parts, then each part is enough to compute a partial signature, and once N out of M partial signatures are collected an actual signature can be computed.

[rtiangha]

Stupid question, but it's probably worth asking just to be clear, but would this scheme account for people leaving the team for unexpected reasons (such as sudden death due to health or whatnot) to the point where N = M-1? How to handle key revocation, especially in corner cases where team members disappear or choose to leave the project and who become hard to reach afterwards, is something to think about.

[rootkovska]

@Ekleog: it would, of course, be ideal to use a scheme where the key does not need to be reconstructed at any point in memory. But the Q is: do standard tools exists that could do that trick? See the req #1 above.

@rtiangha: Luckily in case the present (or any future) QMSK becomes unlockable, there would be a simple work-around: just agree on some new scheme ans generate a new key! Surely in case of a death of one of the M people, this might be justified.

[Ekleog]

@rtiangha I fear no scheme can reasonably account for people leaving the team and becoming malicious: once they have access to a cryptographic secret, there is no revoking their access but revoking the entire cryptographic secret (ie. in this case, the QMSK). For example, if A, B and C all partial access to a 2-in-3 shared secret, and A and B leave the team, they can use their secret parts to reconstruct the secret, and there is no way (that I know of) to force them to forget it.

However, in case of sudden death, their secret portion can reasonably be deemed lost forever (well, not if it's too sudden, but...), and the question is about adding a new member to the team. I think both SSS and the paper I linked above allow adding a new member. Mathematically speaking, SSS is based on the fact that given N points of a polynomial of degree N, it's possible to reconstruct the entire polynomial, but having N-1 points give absolutely no information on the polynomial at any point other than these N-1 points (that's Lagrange polynomials). The scheme then works by picking a random polynomial of degree N where P(0) is the secret, and gives P(1)..P(M) to each member. Then, any N people together can reconstruct the entire polynomial and compute it at P(0), thus retrieving the secret. Adding a member in the pool can be performed by just giving him P(M+1), which is possible so long as N people still have access to their secret portions (and can thus reconstruct the complete secret). For the scheme I linked, I didn't read the paper in detail yet, but as far as I understood it was also using SSS to share parts of the secret key, which would mean it's possible to use the same idea. Please don't trust me on that point, though.

@rootkovska I think standard tools cannot do the trick for the key generation, key splitting and signature part. However, that complexity would be completely hidden from the user, by generating a public key corresponding to the shared secret key in PGP format before destroying the secret key.

As I don't think I'm clear, here is an example of timeline:

Key generation and splitting:

1. A, B and C use a commonly-deemed-secure laptop to generate an RSA keypair using GPG (standard tools)
2. They split the secret key among themselves (non-standard-tools)
3. The secret key shards are transferred to each of A, B and C's secure laptops (standard tools)
4. The public key is put on keyservers by any mean (standard tools)
5. The commonly-deemed-secure laptop is made to completely forget the private key (eg. by physical destruction or any other mean, preferably assuming the laptop was not actually secure but not targeted against RSA keypair generation as nothing could be done in this case) ("standard tools" if fire and ashes are standard tools)

New binding keypair:

1. A generates a new keypair (standard tools)
2. A transfers the keypair's public key to B and C's secure laptops (here A could try to attack B and C's laptops by this data transfer, but it's coming from A's secure laptop so it's still at least as good as without this separation) (standard tools)
3. A, B and C all use their secret key shards to compute a partial signature of the public key (non-standard tools)
4. A, B and C transfer their partial signatures to an untrusted computer (standard tools)
5. The untrusted computer computes the overall signature based on the partial signatures (non-standard tools)
6. The untrusted computer puts online the new public key and its signature (standard tools)
7. A can now sign things with this new keypair (standard tools)

Verification of a new binding key (only user interaction):

1. User U downloads the QMSK public key from the keyservers and triple-checks it from many sources (standard tools)
2. U fetches the binding key's public key and signature from the keyservers (standard tools)
3. U can now use the binding key's public key for any usage (standard tools)

So non-standard tools would have to be used by A, B and C, but U would just see this as a standard PGP key, not having to know the secret key is split between multiple laptops and multiple users.

Just to say, I didn't find an implementation of the scheme described in the paper I linked, so this would require developing one that is able to parse PGP key format, which could be a long-term effort if none is developed by the time you get to it.

PS: I regard myself as only a hobbyist cryptographer, please don't trust me on anything I've said.

[andrewdavidwong]

Hm... that doesn't look quite like a duplicate? ISTM the two tickets have two different purposes: the #2535 is about eliminating the single Master Key, while this ticket is about how to make it significantly more secure, while still preserving the single QMSK.

No. If you read the description on that issue, the QMSK is/can still be present in that scheme.

Also what I suggest here is orthogonal to the work on reproducible builds.

Sure, but so is having a multi-signature scheme. It's just a historical artifact that you initially proposed it at the same time in #816.

Anyway, I don't mind keeping both issues open or closing #2535 if you've changed your mind about the latter.

[HeikoStamer]

Now I can present a piece of free software to you, that can do the 'trick': https://savannah.nongnu.org/projects/dkgpg/ You can meet me at 34C3, if you have any questions on that topic.

[marmarek]

Due to the interactiveness of the protocols a lot of messages between participating parties have to be exchanged in a secure way. We employ GNUnet, and in particular its mesh routed CADET service, to establish private and broadcast channels for this message exchange.

This part is worrying. It means that an application having access to secret key material need also access to the network, including parsing something retrieved from the outside.

[HeikoStamer]

The decryption protocol can be made non-interactive, unfortunately, the signing protocol not. For threshold RSA the situation is better, however it is not implemented yet.

[HeikoStamer]

Just one further note: there is also a TCP/IP replacement for GNUnet. Thus a private network between the parties (e.g. torified) will work.

[marmarek]

Interesting article about another possibility for multi-signature: https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust/blob/master/topics-and-advance-readings/Schnorr-Signatures--An-Overview.md

There looks to be some support for ECC in GnuPG 2.1, but I don't see anything about multisig. Even if generating and splitting the key and also signing things would require use of custom tool, that would be an improvement, as long as such signatures could be verified using standard tools.

[DemiMarie]

What about instead requiring N of M signatures?

[HeikoStamer]

@DemiMarie IMHO one signature is much easier to handle using standard tools.

DKGPG has been improved in the last years, e.g. to exchange required messages over Tor network, see https://www.nongnu.org/dkgpg/35c3_slides.pdf

[Rspigler]

What about instead requiring N of M signatures?

Bitcoin Core is switching to this.

https://github.com/bitcoin/bitcoin/pull/23020