Ability to recover from a future compromise of Nano's signature scheme

[PlasmaPower]

Like other coins, Nano's signature scheme could be compromised in a number of ways

• blake2b is found to be weaker than thought and collisions are created (typical over time with hash functions)
• the discrete logarithm is found to be weak over the curve25519 group (unlikely)
• quantum computing advances to the point where it can break ed25519 (likely but should take a long time)
• additional signature methods are used, such as MuSig, and end up leaking the extended private key
• a popular third party library or application computes nonces for signatures insecurely (either by accident or maliciously), leaking the extended private key

Most of these are in the far future, but in the event that one happens, or one becomes imminent, recovering ownership in a decentralized manner would be near impossible without having a safety net in place. This proposal is for a safety net, what I'm calling recovery keys.

Recovery key requirements

• can be used to prove ownership without also allowing the verifier to claim ownership, even if the extended private key is compromised
• immune to the listed possibilities for Nano's signature scheme being compromised, and other foreseeable future cryptographic attacks
• small enough to not increase ledger size too much
• computable reasonably quickly (doesn't need to be extremely fast as it only needs to be computed once per account, but still should be computable without a long delay on mobile devices)

Assumptions

• modern hashes cannot be reversed given their input has enough entropy. This is a subset of preimage attacks, where exactly the original plaintext is recovered. Even "normal" preimage attacks are extremely hard to pull off (usually hash functions are deemed insecure when collisions are created, an even lesser attack).
• the private key itself is not compromised, as it's first hashed before being used. This is reliant on the previous assumption.
• the recovery key is sufficiently rolled out by the time a Nano signature scheme compromise occurs, and there are enough copies of all accounts' recovery keys to ensure community consensus on recovery keys (including those not in use by a node, for instance ledger backups or copies made by block explorers)
• consensus should not be able to overwrite recovery keys, because consensus is reliant on the signature scheme working

My proposal

My proposal uses Lamport one-time hash-based signatures, double hashing for private key -> public key conversion, key derivation by hashing with an index, and a hashed public key.

For hash functions my proposal uses H0(x) as SHA3-512, H1(x) as Whirlpool, and H2(x) as blake2b with 64 byte output for key derivation.

Denoting x || y as x concatenated with y, and pk being the private key, my proposed 64 byte recovery key would be calculated as follows:

H0(H1( H0(H1(H2("recovery key" || 0 || 0 || pk))) || H0(H1(H2("recovery key" || 0 || 1 || pk))) || H0(H1(H2("recovery key" || 1 || 0 || pk))) || H0(H1(H2("recovery key" || 1 || 1 || pk))) || H0(H1(H2("recovery key" || 2 || 0 || pk))) || H0(H1(H2("recovery key" || 2 || 1 || pk))) || ... ))

I'll be denoting these hashes by their depth from the outside, so the recovery key is at depth 0, and the private key is part of each depth 4. The repeated hashes at depth 1 would be continued until the first index is 255, inclusive. The first index is the bit position (0 through 255), and the second is the bit value (0 or 1). This gives the recovery key the one-time ability to sign a 256 bit message, presumably a public key for a new signature scheme.

A signature with the recovery key would consist of firstly revealing the expanded public key (the concatenated hashes at depth 1), and secondly the hashes at depth 3 for the chosen bit values at each bit position. If Nano's signature scheme is compromised, or compromise is imminent (e.g. a quantum computer has been shown to be capable of an attack), once the dust settles, this would be used to prove ownership and transition to a new signature scheme.

My proposed recovery key for an all 0 32-bit private key is 0b2d29b511f8e97792074d91fbebb5760da9a2d07f09678a35eb57ee0e098d44ad3681a7f3ecd567ca5dba3bdb9cf09015a9c007880518bf16973f53409bf68f. This took my desktop 0.002 seconds to compute (using only one thread) using the following Rust implementation compiled on release mode, so this scheme is definitely fast enough.

use blake2::Blake2b;
use digest::Digest;
use hex;
use sha3::Sha3_512;
use whirlpool::Whirlpool;

fn main() {
    let key = [0u8; 32];
    let mut depth0 = Sha3_512::default();
    let mut depth1 = Whirlpool::default();
    for i in 0..=255 {
        for v in 0..=1 {
            let mut depth2 = Sha3_512::default();
            let mut depth3 = Whirlpool::default();
            let mut depth4 = Blake2b::default();
            depth4.input(b"recovery key");
            depth4.input(&[i]);
            depth4.input(&[v]);
            depth4.input(&key);
            depth3.input(depth4.result());
            depth2.input(depth3.result());
            depth1.input(depth2.result());
        }
    }
    depth0.input(depth1.result());
    println!("{}", hex::encode(depth0.result().as_slice()));
}

Additional assumptions for this scheme

• A preimage attack is not possible on SHA3-512(Whirlpool(x)) by the time the recovery keys need to be used. This is probably a safe assumption, given that computing a preimage for most old hash functions now deemed insecure is still not possible. While quantum computers do lower the pre-image attack cost, existing theoretical quantum attacks alone do not come close to creating a preimage attack for this scheme and cannot solve the problem in polynomial time.

How to distribute these keys

In any scenario, these would be signed by the account. The point is that they're signed for and recorded well before an attack is known, so that when the attack happens the community will have already recorded the recovery keys and doesn't need to trust new signatures from the account, just one made and recorded well before the attack. After the attack, establishing community consensus on the recovery keys for each account would probably be a manual process.

• On-chain distribution: this is the most obvious. Recovery keys could either be distributed as part of existing block fields, as part of a new block field, or as part of a new block type. This has the clear advantage of being part of the ledger, but also means that it'll add to ledger size. For this to not be compromisable by faulty consensus, block cementing would be necessary.
• Off-chain but on-network distribution: the recovery keys could be distributed as part of the real-time network, but not stored as part of the chain. Consensus for faulty accounts is not necessary for recovery keys. If in a couple cases, there isn't agreement on what the recovery key of an account that behaved badly is, that is likely acceptable.

[clemahieu]

consensus should not be able to overwrite recovery keys, because consensus is reliant on the signature scheme working

The point is that they're signed for and recorded well before an attack is known

Can these points be guaranteed?

An attacker constructing a fork which sends the entire balance of a victim account to two different accounts with two different recovery keys would favor consensus over recovery key and thus break the first assumption.

Sending the entire balance of a victim account to a new account, and thus a new recovery key would seem to erase the "well before" nature of the recovery key.

[PlasmaPower]

Here's how I think it would go down:

• An attack is unveiled, either as an imminent attack like a new quantum attack, an attack possible right now like a MuSig bug, or wide spread user reports of funds being stolen
• Nano shuts down the network and exchanges to the best of their ability
• The ledger and user reports are examined for attack. Either:
  • There's no credible signs of an attack (no one's exploited it yet)
  • There's a large scale attack on a third party, like Ethereum's The DAO. From here, Nano can decide to roll back transactions to the best of their ability, or leave the network as-is as it's not a vulnerability in Nano itself.
  • There's evidence of an attack on the network itself. Nano rolls back the attack to the best of its ability while trying to be fair with exchanges and such. There will probably be some loss of funds, but it's a lot better than no one really knowing who owns most funds.
• Community consensus on recovery keys is established. There may be isolated cases where people disagree on the recovery key of an account, but again this is a lot better than no one knowing who owns most funds.
• A beta network upgrade is released to use a new signature scheme if ed25519 is compromised in general, and import a snapshot of balances per recovery key to transition to the new signature scheme via a one time recovery key signature
• The change is rolled out to the live net, combining community consensus on recovery keys and ledger state / balances (with core dictating a lot of this, like how far rollbacks should go)

Basically, no Nano couldn't establish perfect consensus on which transactions were part of the attack, what the exact state of the ledger without the attack would be, or completely nullify the damage of an attack to services accepting deposits like exchanges. But at least Nano would have a clear definition of who owns the vast majority of funds, instead of attackers having as much of a claim to the funds as the real owner (since the attacker can sign as the owner).

[PlasmaPower]

So to answer your question:

Can these points be guaranteed?

Not for the movement of funds post-attack, but that's an intrinsic problem and this solution does a lot better than what Nano could do without such a safety net.

[funkspock]

@clemahieu While I find the concept of recovery keys interesting, at minimum I believe that Nano should have the capability to switch its Public-key cryptography. As you might know NIST is working on the standardization of Post-Quantum Crypto: https://www.nist.gov/news-events/news/2019/01/nist-reveals-26-algorithms-advancing-post-quantum-crypto-semifinals So far, 26 algorithms have made it to the semi finals, and the expectation is that 3 algorithms (based on three different families of crypto) will prevail. At some point eventually a switch needs to take place, and this capability for (almost) seamless transition needs to be thought about and worked out: e.g. code-readiness, testing, playbook, communication plan, etc. Also, as @PlasmaPower mentioned, the current or any future crypto might become compromised which again shows that this capability is highly needed. This leads to the question, how well is Nano currently prepared and what would its desired state be.

[PlasmaPower]

What do you mean by "the capability to switch its Public-key cryptography" other than recovery keys?

[funkspock]

@PlasmaPower We might need to switch to a Lattice-, or Code-based, or Multivariate crypto system. This means that the Nano code needs to be (1) made ready to easily switch the crypto system. This is not trivial, as you probably need to make sure that this part of the code can easily be replaced -which of course requires testing. There is no reason to wait on testing as now there is no time pressure to realize a solution. (2) Consequently, this also means that the code needs to enable transitioning: e.g. via hardfork/snapshots, dual-stack, or some form of translation/tunneling (similar to IPv4 to IPv6 transition). Recovery keys is one of the options that can be considered. With capability I was referring to item (1) which I see as a pre-requisite for (2).

[PlasmaPower]

I don't think investing near that much effort right now is warranted. We'll have plenty of heads up for quantum computers. As long as we have recovery keys, we can implement the rest later without causing any additional problems.

[PlasmaPower]

Even if I was given the option of switching all accounts to quantum secure signatures right now, seamlessly, I would decline, because there are tradeoffs with quantum secure crypto such as performance, size, and that it hasn't been studied as much.