Threshold ECDSA Signatures

Hi everybody! There have been some concerns about the 1/3rd (f+1 out of 3f+1) threshold for the ECDSA keys on the internet computer, and whether this gives sufficient security. We have taken this feedback seriously and took a step back to revisit different approaches to increase the security of threshold ECDSA.

First, some background info. It is very difficult to make threshold ECDSA signatures, much more difficult than eg threshold BLS signatures. We cannot simply set a 2/3rd (i.e., 2f+1 out of 3f+1) threshold for ECDSA signatures like we do for BLS. The best fault tolerance such that we both have liveness and safety from known practical protocols is 1/3rd (i.e., f+1 out of 3f+1). Note that this fault tolerance is actually the same as the consensus protocol ICC uses: even though we use 2/3rd threshold BLS keys, the protocol can only be proven safe and live with up to 1/3rd corruptions, which is also the theoretical optimal threshold for asynchronous consensus. Despite this, you could argue that practical attacks on tECDSA are perhaps easier to perform than attacks on ICC: for tECDSA, you’d have to steal the key material of 1/3rd of the nodes and obtain the full signing key, while for ICC you’d either need an coordinated active attack controlling 1/3rd of the nodes and some control over the network connection between nodes, or you need to steal the key material of 2/3rd of the nodes which would let you sign anything.

So how can we make things even more secure? There are many different approaches:

  1. More nodes & larger subnets. This is conceptually the simplest approach. Work is in progress on this front, and you can follow the status in this forum thread.
  2. Shuffle nodes between subnets. This has been suggested by the community and is an appealing idea: it could mean that an attacker cannot target a specific subnet as the membership constantly changes, and the only way to corrupt a subnet is to compromise a sufficiently large fraction of the overall IC nodes, meaning each subnet becomes more secure as the IC gets bigger. However, I believe that we first need more independent nodes before shuffling actually adds security.
  3. Enable AMD SEV. Enabling some form of SEV could make it much harder to break into a node. Currently, the current IC nodes are of the “Gen-1” hardware specifiation which only support SEV-ES (and is no longer available) while new nodes will have Gen-2 hardware which support SEV-SNP. Gen-2 hardware (specification) is currently available. The relevant point here is that Gen-1 hardware with SEV-ES do not provide the security guarantees we want as they do not protect memory integrity and are thus vulnerable to attack by privileged users while Gen-2 with SEV-SNP does provide memory integrity and the ability for external parties to more easily validate the integrity of the system.
  4. Increase tECDSA security threshold.While we know that we cannot increase the fault tolerance for both safety and liveness, we could sacrifice some liveness fault tolerance to increase the safety fault tolerance. A concrete example: a 34 node subnet can currently tolerate 11 corrupted nodes, meaning we can still sign, and the secret key is not compromised. We could change the thresholds to tolerate 15 corrupted nodes, making it harder for the attacker to steal the secret key. However, this means we can only tolerate 3 nodes that are unavailable. If a 4th node is offline, the subnet cannot create ECDSA signatures anymore.
    Since being unable to sign with a key is almost as bad as an attacker compromising a key, we think that this approach is not the best solution to apply on all subnets. It could be a promising solution to let smaller subnets also maintain the ECDSA key using a higher threshold (such that we can scale out the signing capabilities), while larger subnets still maintain the ECDSA key with a 1/3rd threshold. In this way, if a smaller subnet can no longer create ECDSA signatures due to too many failures, the larger subnets still hold the ECDSA key and can reshare it to other subnets.
  5. Regularly reshare the ECDSA secret key. The idea is that nodes can regularly update their encryption key used to decrypt their secret key shares in the distributed key generation protocol that maintains the ECDSA key. The ECDSA secret key shares will be reshared every time membership changes or any of the members updated their encryption key.
    The result of this approach is that if an attacker steals an ECDSA secret key share or a DKG decryption key from a node, it will only be usable for a limited amount of time, because the keys refresh regularly. This means that an attacker would have to steal the key material of 1/3rd of the subnet nodes within a small time window, which seems much more complicated to pull off.
    One caveat is that the node signing key could also be stolen, and an attacker could try to slowly steal node signing keys, and then quickly register malicious encryption keys on behalf of those nodes, such that it can still steal the ECDSA signing key. To avoid this attack, we can limit how frequently node encryption keys can be updated for nodes in one subnet. An attacker can then only slowly try to register malicious keys for nodes. However, this is a very visible attack, and nodes can complain upon seeing a malicious key registered in their name, upon which they can be removed from the subnet.

The first three options all require a bit more time, as it involves new hardware and onboarding new node providers. So while we are actively working on 1 and 3, I do not expect they will help strengthen the ECDSA security this calendar year. Option 4 is mainly helpful to allow smaller subnets to also sign, when we have larger subnets that back up the key with the standard threshold. Initially we plan to only use large subnets, where this idea does not help. Option 5 however meaningfully improves the security of ECDSA and can be implemented more quickly.

Planned next steps.

Our proposal is to implement option 5 now, and then release a “production ready” ECDSA key, which will be maintained on large (e.g., 34 node) subnets. We can further improve the security of this key when more nodes are added and increase the subnet size. However, when a new feature is added that significantly improves the security (eg, SEV enabled replicas), we can also consider creating a new ECDSA key that has always been at this level of security, and applications can then choose whether they want to migrate to this key.

Please let us know what you think!

28 Likes