NIP-41: Key Invalidation. first draft.

[fiatjaf]

This is a protocol for a backwards-compatible best-effort unambiguous key invalidation flow that aims to reduce the damage from compromised keys from catastrophic to just very bad.

Readable: https://github.com/nostr-protocol/nips/blob/nip41/41.md

[fiatjaf]

I think I must add the thought process on why this proposal is better than others that may have been considered.

Another idea -- to be added to the draft above -- is for a way to unambiguously mark the last key in the sequence as the final one, such that if it is revealed everybody can consider that entire chain of identities as dead forever. This is basically a "nuke" option for when the seed is compromised. There is no possible recover from that event, but at least the person who got their seed compromised can make it likely that the attacker won't steal their identity by publishing invalidation events for all the keys in the chain until the last one.

An (illustrative and probably broken) implementation of this scheme in JavaScript is provided here: https://github.com/nbd-wtf/nostr-tools/blob/nip41/nip41.ts, see also the (very brief) tests: https://github.com/nbd-wtf/nostr-tools/blob/nip41/nip41.test.js

[mikedilger]

Love this in principle.

I don't understand the mechanics of how the keys are generated. I tried a little bit but the math and the bitcoin derivation path things are all unfamiliar to me. I'd be happy to just install a tool on an offline computer that does this for me.

[mikedilger]

Since this happens in somewhat trusted hardware and still has a root secret there which if compromised blows the whole thing.... how is this better than simple key delegation/revocation of an online key from a secure key held in somewhat trusted hardware?

[fiatjaf]

There is in principle no way to do revocation, only delegation with an expiration time.

Delegation effectively creates new identities, that other clients have to painfully try to connect with the root identity, but they might choose not to -- and we have to survive in a world in which some clients will do that but others won't --, so a delegated key may show up as a completely new key to others, and that is desirable so the protocol can keep its simplicity. In the same way, reputation schemes and other things that require people to act on your public key directly may suffer from these inconsistencies.

Delegation doesn't play well with NIP-04 and anything else that might require ECDH.

I think NIP-26 delegation only really shines when one wants to allow a third-party to post things on their behalf.

---

But even if I am wrong, nothing prevents one from using this scheme + delegation. It hurts nothing to have one extra fallback if your super-safe delegator root key gets compromised by any means.

[optout21]

Some observations -- sorry if stating the obvious, but to verify my understanding

• This schemes solves the issue with key rotation whereby a compromised account can rotate to a new key which it controls, at the price of restricting rotation to a set of a priori created keys
• Generation/storage of the set must be done in a secure way, as if the whole set gets compromised, all is lost
• This scheme cannot be applied to keys already in use, as new keys have to be generated Please correct if needed

[optout21]

I was wondering if BIP-32 style key generation could not be used to achieve the same result?

The idea:

• Generate a master key
• Generate the following set of N key pairs, using special derivation paths:
  • K_1: m/44'/1237'/41'/1'
  • K_2: m/44'/1237'/41'/1'/1'
  • K_3: m/44'/1237'/41'/1'/1'/1'
  • ...
  • K_n: m/44'/1237'/41'/1'/1'/1'.../1'
• Start using the last key pair K_n
• In case it gets compromised, publish SK_n and PK_(n-1), similar as in the proposal above (SK=secret key, PK=public key) It is possible to verify that PK_n is derived from PK_(n-1) (using a single hardened child key derivation of BIP-32).

[optout21]

Here's an alternative idea that could be used with existing keys: create a backup keypair, publish the backup public key in a special message, and allow key rotation only to the previously published backup key.

• User uses keypair (S, P) to interact with the network
• User generates another 'backup' keypair (or several) (S', P')
• P' is published in a special message as backup key
• Once P is compromised, user can broadcast P' as new key.
• In this case the proof that the new key has been committed to beforehand is not a cryptographic proof, but the existence of an earlier message linking the two.

This could be applied to existing keys as well. The backup key pair or pairs can be arbitrary, or generated through some relation, e.g. NIP-06 with different indexes.

[fiatjaf]

In case it gets compromised, publish SK_n and PK_(n-1), similar as in the proposal above (SK=secret key, PK=public key)

I think this is not worth it, I think, because you don't want to reveal your private key if just some people know, or if you are not really sure it has leaked or not.

[fiatjaf]

publish the backup public key in a special message, and allow key rotation only to the previously published backup key.

How can anyone know what is the "correct" backup key? An attacker can just publish backdated backup keys. And doesn't matter what you put in there to guard against that, the key owner themselves can always create a series of prepared backup keys and rotate to multiple at the same time.

[optout21]

In case it gets compromised, publish SK_n and PK_(n-1), similar as in the proposal above (SK=secret key, PK=public key)

I think this is not worth it, I think, because you don't want to reveal your private key if just some people know, or if you are not really sure it has leaked or not.

I meant to follow the exact logic as in this PR;and that message contains the compromised secret key. But public key is sufficient. I may have misunderstood, I thought that A' below is the compromised secret key:

{
  "kind": 13,
  "tags": [
    ["p", "A"],
    ["hidden-key", "A'"]
  ],
  "content": "optional explanation",
  "pubkey": "B"
  "created_at": ...
}

[optout21]

How can anyone know what is the "correct" backup key?

The event posted by the user as a response to the compromise contains the new pubkey, which has to have a previous 'backup announce' event.

An attacker can just publish backdated backup keys.

Yes, backdating is an issue to be mitigated, e.g. by timestamps or including its hash in some subsequent message.

The bigger issue in my view is if the 'backup announce' event is not found, having in mind the non-guaranteed event notification nature of Nostr. Because in that case there is no way to verify that the new key has been indeed preannounced.

And doesn't matter what you put in there to guard against that, the key owner themselves can always create a series of prepared backup keys and rotate to multiple at the same time.

I don't understand, what is the concern here?

[fiatjaf]

that message contains the compromised secret key

It does not. That's the entire point.

[fiatjaf]

public_key(secret_key + DIFF) == public_key(secret_key) + DIFF

But this is exactly the case, actually with one difference:

public_key(secret_key + DIFF) == public_key(secret_key) + public_key(DIFF)

[optout21]

I retract/correct the above. Indeed it is:

public_key(secret_key + DIFF) == public_key(secret_key) + DIFF

with the clarification that the addition on the right side is plain numerical (scalar) addition, while on the right side (public key) it is point addition (see wikipedia).

Unit test: https://github.com/catenocrypt/nip41-proto0/blob/main/src/keys.rs#L355

[optout21]

Prototype implementation available:

https://github.com/catenocrypt/nip41-proto0

[fiatjaf]

This is amazing.

[pocomane]

Sorry, probably I am to saying something very naive: I am not a crypto-guy.

But why you can not use an "Out-of-chain" key in the revocation message, given that the rest of information to validate the request can be put in the tags?

For example, referring to the current draft, consider a chain of just two keys A and B. On the key compromisation the user generate a new key C (or another chain to take into account future issues) and posts:

{
  "kind": 13,
  "tags": [
    ["p", "A"],
    ["hidden-key", "A'"],
    ["revoke-secret", "B"],
    ["sign", "serilization-signed-with-b"]
  ],
  "content": "optional explanation",
  "pubkey": "C"
  "created_at": ...
}

And then use C from that time on?

With serilization-signed-with-b I just mean the same signature as if the event was published with the key B (obviously the signature of the event is based on C instead).

In this way you can have an infinite series of keys. And such revocation can be used also for regular key updates ("regular" as in "Change my key every 4 month").

Probably this scheme can be simplified, I kept a close relation to the original nip because it seems to me that any attack to the "Out-of-chain" method can be direct also to the original one.

But as I sayid I have very minimal experience (almost none) in the crypto field...

[optout21]

While working on the prototype implementation, the idea came to me that this could be achieved by using only BIP32 derivations. I think that's better as the cryptography employed is standard.

So I have created a new PR with this version: https://github.com/nostr-protocol/nips/pull/450

• I have created a new PR, as opposed to commenting/editing the existing one, mostly due to the fact that the key generation cryptography is different, and this is at the heart of the scheme. But I fully acknowledge that the idea and solution was laid out in the original PR, and if the original authors prefer, I'm fine with incorporating these changes to the original PR. I view this mainly a technical aspect (github).

• The similarities and differences of this scheme to the original PR:

  • Solves the same original issue
  • Basic ideas of a chain of pre-generated set of keys, using the last, rotating to the previous, etc. are the same
  • The way to generate one key from the previous is different, here using 'standard' BIP32 derivation, though the basic layout is the same (key part, extra part, taking a hash of the concatenation).
  • The original scheme uses a (32-byte) 'hidden' public key. Here that is perfectly analogue to the 32-byte chain code of the extended key. One detail is that the chain code (analogue to the hidden key) can be represented as a hex string (though npub notation could also be used for it).
  • One difference is that in the original scheme, when invalidating key N and rotating to N-1, the hidden part of N is revealed. In this scheme it is the chain code of N-1. However, this is not a big difference, if one was to shift the hidden keys by one index, then the end result would be the same.
  • The generation of the 0th key is also different (using a derivation path as opposed to just taking the seed)

[fiatjaf]

I see. I've read this and read again, but I don't understand what is happening on BIP-32. Is it basically the same thing but using a bunch of other components?

[optout21]

I see. I've read this and read again, but I don't understand what is happening on BIP-32. Is it basically the same thing but using a bunch of other components?

I think most people who first read this PR are put off to some degree by the details of key generation. It uses some BIP32 derivation (for the hidden keys), but also direct key hashing and tweaking. My new proposal achieves the same results using only BIP32-style derivation. I think this way it is a bit easier to understand and digest the scheme, and also implementation is a bit easier (as it is using logic widely used in bitcoin code, no custom stuff).

[optout21]

But why you can not use an "Out-of-chain" key in the revocation message, given that the rest of information to validate the request can be put in the tags?

I'm not sure I got your concerns correctly, but I try to answer it. I think you don't understand the 'hijacking' issue.

Let's say there is a mechanism to rotate to a new, arbitrary key, and there is no scheme with any key pre-generation. If a user discovers that his current key got compromised (by e.g. someone else posting offending content under the identity), she can create a new message, and send out a message to everyone: "please stop using pubkey A, instead use B". Fine. But what would a real bad-intention identity thief do? First thing, before posting anything under the stolen identity, it could create a new key X and message everyone: "please stop using pubkey A, instead use X". After that it can post some bad-intention posts. Now the real user noticies, and what can she do? Not much, as it has been already broadcasted that the new identity is X, which she does not control. So the rotation mechanism is not much of a use, as clever attackers can use it to their advantage.

One solution to this is restrict rotation to a 'new' key which can be verified that belongs to the user. If the 'previous' key A can be deterministically derived from the 'new' key B, that means B has been created before the first usage of A. The user can do this by pre-generating the keys, but the attacker cannot. He cannot come up with a key which would generate A. (I use 'new' in quotes because at generation it is actually generated last).

So no, no arbitrary C key can be used as new key, because clients should verify the rotation messages, and the relationship would not hold. It holds only for one key.

How this helped; if not please give the PR text some more reads :)

[pocomane]

First, thanks for the replay, I understand that I placed my question in the wrong place. I did not note that was a PR, I thought it was an issue. If you think it may be clearer, I can continue in a new issue.

But what would a real bad-intention identity thief do? First thing, before posting anything under the stolen identity, it could create a new key X and message everyone: "please stop using pubkey A, instead use X". After that it can post some bad-intention posts. Now the real user noticies, and what can she do?

She can make a new request asking to change to C, providing the "Revoke secret" B, making clear to all the clients that the previous request to change to X was unauthorized (well, actually the change to X should be ignored in the first place since the attacker can not provide B). My "Proposal" is a sort of mix between nip-41 and a "Change key" request signed with the previous key alone.

EDIT. Please ignore the rest. The described attack is not possible because the private part of B is not compromised.

However I think to have found the issue with such mechanism: after the user asked for a change to C, an attacker can get the B that she provided and make a new request to change to X, but with an antecedent timestamp.

But... is this an issue also for nip-41 ? Yes, the user can still use the next key in the chain; but iterating this attack, the evil-guy can force user to consume al the keys in the chain.

[fiatjaf]

I think most people who first read this PR are put off to some degree by the details of key generation. It uses some BIP32 derivation (for the hidden keys), but also direct key hashing and tweaking. My new proposal achieves the same results using only BIP32-style derivation. I think this way it is a bit easier to understand and digest the scheme, and also implementation is a bit easier (as it is using logic widely used in bitcoin code, no custom stuff).

Well, I hope you are right about this and people start to get more interested on the idea. So far, though, I think it has done more harm than good, because before we had two people that understood NIP-41 (me and you), now it's just one (you).

[mikedilger]

In order to understand this PR sufficiently enough to think clearly about it and offer good feedback, one first needs to understand BIP32 (which while about "derivation paths" does not use the word "path" in it anywhere). To understand that, one needs to understand extended keys (extended by randomness), child key derivation functions, hardened child keys vs not hardened child keys (which I don't get), and of course all the elliptic curve stuff it is based on, plus the notation such as the meaning of the apostrophe (which I still don't understand). Maybe bitcoin programmers find all this stuff obvious and well-known, but I'm struggling. I think I understand extending a key with randomness... I don't know why, or how that brings about the claimed properties, or even what the claimed properties are. I think I understand the slash notation (repeated application of a child key derivation function). I spent 40 minutes or so trying to understand BIP32 today and then had to get back to work. I aspire to be able to review this PR.

[fiatjaf]

Yes, I have the same trouble understanding BIP-32 myself. I also think the advantages of "reusing a thing that is widely used in Bitcoin" are not as straightforward, because BIP-32 was clearly not intended to serve this purpose, so my head just starts spinning.

[optout21]

I'm not sure if the previous two comments refer to #450 or this PR (@mikedilger), but I have the feeling that #450 is meant and I feel addressed. I do think that #450 is a simpler, cleaner, more consistent version of #158, that's why I invested the time to write it up. I may be wrong or may not be able to get my point across.

While trying to understand the details of this PR #158, the steps of the derivation reminded my of something familiar. I realized that it is very similar to the derivation function of BIP32, and then it clicked, that it could be done entirely using BIP32 derivation. I mention the following specific details, I think they are not straightforward to understand/implement, but they are gone with #450:

• The real purpose of the 'hidden keys' is hard to grasp, they are not used as keys (for signing, etc). They are just 32 bytes of secret data. They are very analogue to the extension part of BIP32 extended keys ('chain code'; they are not called key there)
• The adding of hash numbers to keys requires an understanding of the details of elliptic curve public key cryptography. BIP32 hides those complexities: using a derivation with a child index one can get a new derived key, but the details are hidden inside BIP32.

I reproduce here the the key derivation -- the only operation called upon is BIP32 derivation (with derivation path), no 'low-level' hashing or key arithmetic operation is needed.

Another way to define the extended private keys is that they are derived from the seed using the following derivation paths:

m/44'/1237'/41'
m/44'/1237'/41'/41
m/44'/1237'/41'/41/41
m/44'/1237'/41'/41/41/41
...

Besides, BIP32 derivation is also used in this original version, so concerns about complexity of BIP32 applies to both version.

[fiatjaf]

I don't think this should be a NIP on itself, it is too restrictive and won't be used in practice by most people. I'll close this and reintroduce it, maybe, at a later stage, as a part of another NIP that will include multiple ways of doing key soft-invalidations.

[arthurfranca]

Readable: https://github.com/nostr-protocol/nips/blob/nip41/41.md

I think this is pointing to another newer branch with the same name

[AsaiToshiya]

It is here: https://github.com/nostr-protocol/nips/blob/3b823c8f22bac877cc4ee461e1eef2c925ffc64e/41.md

[fiatjaf]

Fixed above.