Lose your device, but keep your keys

Ed keys everywhere

In iroh we are using Ed25519 keypairs a lot. Nodes are identified by ed keypairs, documents are identified by keypairs, also authors, namespaces etc. A gossip topic is an arbitrary 32 byte blob, which conveniently fits an ed public key.

With pkarr we have a great mechanism to publish information about keypairs. We are running a dns server, and we can also use the bittorrent mainline DHT for a fully peer to peer mechanism to publish and resolve pkarr packets.

Other recent protocols such as nostr are also using ed25519 keypairs.

Correction: Nostr does not use Ed25519 keypairs but Secp256k1. Fortunately there is a FROST implementation for secp256k1 as well. frost-secp256k1.

How to keep the keys safe

A problem that frequently comes up when using a keypair to control access to an identity or a resource is how to keep the private key safe.

Some keypairs are ephemeral and don't need to be safeguarded much.

Some will have significant security implications from the start (e.g. a keypair associated with access to a crypto wallet).

And some will initially be of low value, but might grow in value over time (e.g. a social media account).

In most cases, there is a constant conflict between the need to keep the keys safe and the need to constantly access the private key for signing messages.

Existing solutions

Local file system

The default way to store a private key is to just store it in a hidden directory in your local file system. While this is not extremely secure, it is still highly preferable to not using encryption at all. In many scenarios, e.g. device loss or theft, this is perfectly fine for low to medium value keypairs.

Secure key storage

Most modern hardware supports secure storage for private keys. However, access to such secure storage locations is highly platform dependent. It also only works for a limited set of cryptographic primitives, which might not include EdDSA. More fundamentally, while secure storage makes the key relatively inaccessible, it does not protect against key loss. It also does not provide a mechanism for revocation.

Delegation schemes

With the tools of public key cryptography you can come up with delegation schemes where a rarely used master key is used to delegate to a more frequently used keypair that can be revoked using the master key. This is a very complex topic that would require its own series of blog posts.

Threshold signatures

I was vaguely aware that something like threshold signatures exist. This is - very roughly speaking - a scheme where you split the private key into multiple parts called shares, and need a certain number of these shares to sign a message. Since the shares never have to be in one place, this provides safety in case a single share gets compromised or lost.

What I did not know however is that there exist threshold signature schemes such as FROST that work with Ed25519 such that generated signatures are fully compatible with normal Ed25519 signatures. So you can sign a message with a threshold signature scheme and then validate the signature as usual using the ed public key.

This means that such threshold signatures are compatible with existing infrastructure such as bep-0044 in the mainline DHT, pkarr, and nostr.

They are also compatible with all the other places in iroh where we are using ed keypairs.

Compared to Shamir Secret Sharing, the FROST scheme does not require the shares to be in one place to sign.

Creating key shares

The reason I got interested in threshold signatures is the backwards compatibility.

There are various ways to create key shares.

One I find interesting in particular is the ability to just take an existing ed private key and generate key shares from it. This way the scheme is not just compatible with Ed25519 signatures in general, but even with existing keypairs. So for example you can use this algorithm for an existing node id, document, or nostr account. Here you start with the keypair in one place and need to trust the security of that device, so you implicitly have a trusted dealer. You also need a secure way to transfer the shares to the target locations.

As a second option you can create the keypair and then immediately split it, again requiring a place that is considered secure at generation time and a way to securely transfer the shares.

And as the most advanced option a DKG (Distributed Key Generation) scheme that allows generating the key shares directly on the target devices without ever having them all in one place.

The advanced key share generation schemes are certainly interesting, but given that we are starting off with ed private keys in hidden directories, even the more simple approaches are fine for an initial exploration.

Exploring the frost_ed25519 crate

The FROST scheme is described in the paper FROST: Flexible Round-Optimized Schnorr Threshold Signatures. There is a crate implementing the scheme, from the ZCash foundation, that is pretty approachable.

My experiment can be found here.

Local operations - split, reconstruct, re-split

I implemented a little command line tool to split existing iroh keys into key shares.

❯ cargo run split --key ~/.iroh/keypair --target split
Splitting key 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa into 3 parts
Storing part 1 in directory split/1
Storing part 2 in directory split/2
Storing part 3 in directory split/3

❯ ls -l split/1
-rw-r--r--  1 rklaehn  staff  230 Oct  1 18:43 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa.pub
-rw-r--r--  1 rklaehn  staff  134 Oct  1 18:43 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa.secret

I also implemented a way to reconstruct a signing key from a sufficient number of key shares and to use that key to sign a message. Note that you can't reconstruct the ed private key, but just a key that can be used for signing.

> cargo run sign-local --key 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa --message hello split/1 split/2
Reconstructed a signing key from ["split/1/25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa.secret", "split/2/25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa.secret"]
Signature: 1a9c93300a5e9b293ca7845d52235324c6c327f60fea1790c4f22ac3cb1566508a9111f311aa2bca4d0dd19253b106e58c84c454bd966ba2715e30124bfdac02

And last but not least a way to reconstruct a signing key and then immediately create a new split without persisting the regenerated key.

> cargo run re-split --key 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa --target newsplit split/1 split/3
Reconstructing key from ["split/1", "split/3"]
Re-splitting key into 3 parts
Storing part 1 in directory newsplit/1
Storing part 2 in directory newsplit/2
Storing part 3 in directory newsplit/3

> ls -l newsplit/1
-rw-r--r--  1 rklaehn  staff  230 Oct  1 18:51 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa.pub
-rw-r--r--  1 rklaehn  staff  134 Oct  1 18:51 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa.secret

This is all easy enough, but if the key shares are all on the same file system the scheme just adds complexity but no additional security.

So we need a way to use the key shares from multiple machines that can be physically separated.

Iroh is a library that can get you a fast and encrypted connection between any two devices anywhere in the world. So this should be easy, right? Let's see.

Remote operations - sign and cosign

For using the key shares, there are two possible roles. The signer actively wants to sign a message, e.g. to publish it somewhere, but does not have the entire private key. Depending on the exact parameters for the key shares, it needs one or more co-signers.

The co-signer is a little daemon that has one or more key share for which it can co-sign. For this exploration it will just wait for incoming co-sign requests and sign them.

The protocol

The protocol looks like this

• The signer sends a request to all configured co-signers to sign a message for a 32 byte public key.
• Each co-signer that has a key share for the requested public key answers with a commitment and remembers a corresponding nonce.
• The signer waits until it gets the required number of commitments. It then creates a signing package from all the commitments and the message and sends that to all co-signers that answered in the first round.
• all co-signers sign the signing package and return a signature share.
• as soon as the signer has enough signing shares, it can create a signature.
• optionally we can validate that the signature is correct using the known ed public key.

Co-Signer

The co-signer in this scheme acts as a server, so it needs to locally store its iroh keypair to have a stable node id. It also needs to publish discovery information. It does not, however, have to look up discovery information since it does not call other nodes.

So this is how the endpoint setup looks like:

let discovery = PkarrPublisher::n0_dns(secret_key.clone());
let endpoint = iroh_net::endpoint::Endpoint::builder()
    .alpns(vec![COSIGN_ALPN.to_vec()])
    .secret_key(secret_key)
    .discovery(Box::new(discovery))
    .bind()
    .await?;

Once the endpoint is created, the co-signer needs to run a normal accept loop where it just handles incoming co-sign requests

while let Some(incoming) = endpoint.accept().await {
    let data_path = data_path.clone();
    tokio::spawn(async {
        if let Err(cause) = handle_cosign_request(incoming, data_path).await {
            tracing::error!("Error handling cosign request: {:?}", cause);
        }
    });
}

Handling a request is described below.

The code contains a lot of boilerplate for serialization and deserialization, but other than that is pretty straightforward. The fact that the frost_ed25519 crate has nice package structs for the different steps including serialization helped a lot.

One thing to be aware of is that the request handler has to wait for the other side to close the connection, otherwise the last packet sent from our side might get lost. For a detailed explanation, look at our blog post Closing a QUIC Connection.

let connection = incoming.await?;
let remote_node_id = iroh_net::endpoint::get_remote_node_id(&connection)?;
info!("Incoming connection from {}", remote_node_id,);
let (mut send, mut recv) = connection.accept_bi().await?;
let key_bytes = read_exact_bytes(&mut recv).await?;
let key = PublicKey::from_bytes(&key_bytes)?;
info!("Received request to co-sign for key {}", key);
let secret_share_path = data_path.join(format!("{}.secret", key));
let secret_share = SecretShare::deserialize(&std::fs::read(&secret_share_path)?)?;
let key_package = KeyPackage::try_from(secret_share)?;
info!("Got fragment, creating commitment");
let (nonces, commitments) =
    frost::round1::commit(key_package.signing_share(), &mut thread_rng());
info!("Sending identifier");
send.write_all(&key_package.identifier().serialize()).await?;
info!("Sending commitment");
write_lp(&mut send, &commitments.serialize()?).await?;
info!("Waiting for signing package");
let signing_package = SigningPackage::deserialize(&read_lp(&mut recv).await?)?;
info!("Received signing package, creating signature share");
let signature_share = frost::round2::sign(&signing_package, &nonces, &key_package)?;
info!("Sending signature share");
send.write_all(&signature_share.serialize()).await?;
info!("Finished handling cosign request");
// wait for the connection to close.
// if we don't do this, we might lose the last message in transit
connection.closed().await;

To run the co-sign daemon, you just need a directory containing one or more key shares you want it to co-sign, in the format generated by the split or re-split commands.

> cargo run cosign --data-path split/2
Can cosign for following keys
- 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa (min 2 signers)

Listening on 4bqd4r3fivo5722twrvmlwcs7wjlnv6xf567lyweb7yyb34x37ba

Signer

In a real use case this would be embedded in an application, but for this exploration we will do it as a cli utility as well.

The signer in this scheme acts as client. It does not need a stable node id, but it needs the ability to look up the addresses of other nodes. So the endpoint setup looks like this:

let endpoint = iroh_net::endpoint::Endpoint::builder()
    .secret_key(secret_key)
    .discovery(Box::new(DnsDiscovery::n0_dns()))
    .bind()
    .await?;

For signing, it first calls out to all configured co-signers and sends them a co-sign request for the key to be signed for. Then it waits until it has a sufficient number of valid responses.

let cosigners = futures::stream::iter(args.cosigners.iter())
    .map(|cosigner| send_cosign_request_round1(&endpoint, &cosigner, &args.key))
    .buffer_unordered(10)
    .filter_map(|res| async {
        res.inspect_err(|e| warn!("Error sending cosign request: {:?}", e))
            .ok()
    })
    .take(min_cosigners)
    .collect::<Vec<_>>()
    .await;

Once it has a sufficient number of co-signers, it creates a commitments map from the received commitments and adds a commitment from the local key share.

let mut commitments_map = BTreeMap::new();
for (_, _, identifier, commitments) in cosigners.iter() {
    commitments_map.insert(*identifier, commitments.clone());
}
let local_identifier = *key_package.identifier();
commitments_map.insert(local_identifier, commitments);

From this point on it is assumed that the co-signers will be reachable. If a co-signer would drop out after this point, you would have to repeat the entire signing process.

In the next step, the signer creates a signing package, sends it to all the co-signers that answered in the first round, and then collects the signature shares. It also generates a local signature share from the local key share.

We keep the connections to the co-signers open between the first and second round by just keeping the SendStream and RecvStream around. Keeping the SendStream or RecvStream around keeps the connection alive despite the actual Connection object being dropped.

let signing_package = frost::SigningPackage::new(commitments_map, args.message.as_bytes());
let signing_package_bytes = signing_package.serialize()?;
let signing_package_bytes_len = signing_package_bytes.len() as u32;
let mut signature_shares = BTreeMap::new();
info!("Creating local signature share");
let local_signature_share = frost::round2::sign(&signing_package, &nonce, &key_package)?;
signature_shares.insert(local_identifier, local_signature_share);
for (mut send, mut recv, identifier, _) in cosigners {
    write_lp(&mut send, &signing_package_bytes).await?;
    let signature_share_bytes = read_exact_bytes(&mut recv).await?;
    let signature_share = frost::round2::SignatureShare::deserialize(signature_share_bytes)?;
    signature_shares.insert(identifier, signature_share);
}

As soon as all requested signature shares arrive, it can finally create the signature by aggregating the signing shares. For this step we also need the PublicKeyPackage which is identical for all shares and contains no secret information.

info!("got {} signature shares", signature_shares.len());
let signature = frost::aggregate(&signing_package, &signature_shares, &public_key_package)?;

Once we finally have the signature, we can quickly check if it is actually a correct signature for the private key. In a real application we would now take the signed data and send it somewhere, e.g. to pkarr. But for this exploration we just print it.

let bytes = signature.serialize();
let iroh_signature = iroh_net::key::Signature::from(bytes);
if let Err(cause) = key.verify(args.message.as_bytes(), &iroh_signature) {
    error!("Verification failed: {:?}", cause);
}
println!("Signature: {}", hex::encode(&bytes));

Usage:

> cargo run sign --message test --key 25mzjgjlrcrma7wkm4l3fjv2afcs53cvmmyw3v2uwwt2dczsinaa --data-path split/1 4bqd4r3fivo5722twrvmlwcs7wjlnv6xf567lyweb7yyb34x37ba
Signature: a42d8ada7fc84a99f95e588eed99f89cc3ffdf3806862d6f5efd6511dd7b97912d04655e2c5f8f42e85c231ba8e084ae07d3e88c1bc17bc31156a9765b71200b

Possible usage

So now we have a way to split an ed keypair into multiple key shares, store these shares on multiple devices, and sign a message using a co-signer.

How would we use this to have good usabilty when publishing to e.g. pkarr or nostr while still keeping the key safe?

Here is one of many possible schemes:

One key share a will be on the device that is actively publishing. One key share b would be on a remote server, either on a computer owned by the user or on a server operated by a service provider. And the third share c would be safely stored by the user, e.g. on a USB stick.

The user device would first do a co-sign request, which would be answered by the co-sign server. Then it would publish the signed message.

The co-sign server has a key share b for the key, but that alone is not sufficient to sign messages for the key. The device itself has a key share a for the key, but this is also insufficient to sign for the key. So device loss or even device compromise is insufficient to gain access to publishing to the key.

Recovery on key loss

If the user device is lost or compromised, the user can simply disable publishing to the key by stopping the co-sign server. Then regenerate the signing key on a secure device, create a new set of three key shares a2, b2, c2, destroy the old two key shares b and c, and start from scratch with a similar setup as before.

The key share a on the lost device is completely useless without either b or c.

If a higher level of security is required, you could change the minimum required number of shares to 3 and run multiple co-sign servers on separate devices.

Note that if you want to publish from multiple devices, you would still use the same key share a on all those devices instead of creating an additional key share. That way you avoid the key becoming compromised when multiple devices get lost or stolen, e.g. when your laptop and phone get stolen at the same time.

Automation

This entire process would be automated to provide a smooth user experience, for both publishing and decomissioning a device. A user could go through many devices without ever having to change a public key.