Stateless key rotation using a series of hidden commitments

[fiatjaf]

So the idea here is that Nostr apps could generate a series of keys for each user, all based on an initial seed. And they would show the seed and the first key to the user. The seed must be kept safe at maximum security, while the user can be a little more relaxed with that first key.

Then if for any reason the first key was compromised the user could use the seed, maybe in a very safe fully-offline device in a vault inside a nuclear bunker, and use it to get the second key, then use that second key to sign an event telling all interested parties that the first key was compromised.

The event from the second key alone would be sufficient for all supporting clients to verify that that second key was indeed owned by the same person who owned the first key, and that the first key was irrevocably compromised. Upon seeing this event all clients could easily automatically stop following the first key and start following the second, and (if this is applicable) even move their internal state (chats, metadata and so on) from the first key profile to the second key profile.

Once upon a time I asked @RubenSomsen to come up with a way to do this and he invented the following scheme:

So what if the secondary key is simply committed inside the primary key similar to a tapscript. Opening the commitment proves the relationship.

It's basically:

A' = A + hash(A||B')G B' = B + hash(B||C')G C' = C + hash(C||D')*G

etc.

A' can be overruled by B' by revealing A and B', which allows the commitment to B' inside of A' to be verified. A, B, and C have completely independent entropy

A more naïve scheme would be to just make A = hash(B), B = hash(C) and so on (or something like that), but this would require revealing the compromise private key, which we don't want to do since that could increase the damage. Other, safer methods would involve doing zero-knowledge proofs, but the scheme above seems to be much better since it is simple and clients can probably implement it easily.

Even for clients that do not implement it, a third-party "compromised keys directory" web app could be created so users could manually go there and use that to verify if someone was compromised or not.

[fiatjaf]

I believe the series of keys A, B, C and so on could be generated using something like NIP-06 (i.e. BIP-32) and from the first, say, 1000 keys (or less, I don't know what is the ideal number here), the sequence A', B', C' and so on could be generated.

[kevinsmith]

It's better than what we have now, certainly. And more reliable than the social endorsements I described in #101. But it requires a complete set of possible keys to be generated before use, which means there's a chance of running out at some point. (Though I guess you could generate a million keys and it'd be extremely unlikely that you'd ever use those all up.)

A user would need to store all possible keys along with their seed in that super-secure offline vault, right?

It would be great to be able to generate an indefinite number of private keys that could all somehow show proof that they're derived from the same master, but there are people far more adept at cryptography than me who haven't come up with it, so I'm assuming it's not possible.

[fiatjaf]

No, I believe you would only have to store one seed and from that you can derive all the keys. You would have to pregenerate all before using the first though, but I don't think that is a big problem.

By the way, this is not supposed to solve all the issues with key management in the entire world. You still have to take care of your keys, you can't just rotate every hour to a new key, that will not scale well.

[kevinsmith]

Since the real problem here is the sensitivity of a single, precious private key in an ecosystem where one is basically required to give it out to publish to the protocol, maybe NIP-26 is the solution?

By the way, just wanted to thank you for everything you've done to make nostr possible, @fiatjaf. Digging into it this year has been exciting. It's taken me back decades and made it feel like it did when I was discovering the young Internet, full of possibilities and fun problems to solve.

[ottman]

@markharding any thoughts here?

[fiatjaf]

I think the use case for NIP-26 is different and these two solutions can live together. My impression from NIP-26 is that you're not meant to use one different pubkey for each micro Nostr app you decide to try, but mostly for when you have to handle a private key to someone else or for a use case like Minds in which they control the key already and you're just adopting it. But maybe this wasn't very clear and other people have other ideas.

[kevinsmith]

When discussing the problem of private keys being compromised on a podcast recently, @jb55 pointed to NIP-26 as a likely solution. Maybe he can provide his angle on it here.

[kevinsmith]

After sleeping on it, I think @fiatjaf's comment about several solutions working together is spot on for secure key management. This feels like a good set:

• Community norms to only use a NIP-07 extension for web clients and never, ever enter your private key into a web app because it's impossible for a web app to guarantee protection from XSS. (If the app can see your private key, an attacker can too.)
• NIP-26
• This proposal + a new NIP for announcing key rotation

I'd personally be comfortable with this proposal as long as I could generate an absurd number of keys beforehand such that I could never realistically use them all up.

[vitorpamplona]

IMHO, this feels like an overly complex cryptographic scheme (requires cryptographic review to make sure it's doing the right thing in each new language) which when combined with NIP-26 (two seeds delegating derived keys from one another to constantly verify) and NIP-05 (verification using trusted protocols DNS+HTTP) makes account management of Nostr quite complicated.

As more and more NIPs are created to solve the details of key management/verification/recovery, I see more and more reasons to kill them all in favor of a simpler DID process, reusing tools that already exist for other applications.

[kevinsmith]

Was just about to suggest you take a stab at creating a nostr DID method that could live in an event, but you beat me to it! https://github.com/nostr-protocol/nostr/issues/45#issuecomment-1362102659

[csuwildcat]

[rot13maxi]

If I’m reading the notation correctly, this scheme:

A' = A + hash(A||B')*G
B' = B + hash(B||C')*G
C' = C + hash(C||D')*G

Requires that you reveal the compromised key. As mentioned earlier, it also requires that you generate keys upfront because each key contains a commitment to the next key (iow, you need to generate C before you generate B, so you need a finite set generated upfront).

an alternative approach would be to have some reference to a “revocation key” (maybe in a NIP-5 identifier, maybe in some other construction). That revocation key can sign a message that says “this key shouldn’t be used anymore, use this one instead”. One nice thing about a scheme like that is that the future key could have its revocation key based on the same seed, or different entropy all together.

Users still have to manage keys, but if you wanted to, you could generate both signing keys and revocation seed from the same seed with different derivations, or you could keep them separate.

[fiatjaf]

It doesn't require you to publish the compromised key. For example, If the keypair (a', A') is compromised you can revoke it by publishing A and B' (and then everybody assumes B' is your next key). The compromised private key is a' = a + hash(A||B') and that is never revealed because you never reveal a.

It does require you to generate keys upfront, but that isn't a big issue since you can generate a thousand keys from a single seed and store just that seed.

Having a separate revocation key is worse because Nostr doesn't have this key infrastructure that ties one key to the other and so on, everything is stateless, each event is supposed to be valid by itself. In this scheme the revocation event would be just an event published by B' with the contents of it being A, and from that alone everything would be settled. Very easy to handle by clients.

[vitorpamplona]

everything is stateless, each event is supposed to be valid by itself

That sounds false since you will have to keep up with revocations. That is a stateful service. Events using a revoked key (which come later) will not be valid anymore. Clients and relays will have to manage a stateful active key service.

[fiatjaf]

Not at all. If A is following B1 and gets a revocation event from B2 then A stops following B1 and starts following B2. Now A won't be getting new events from B1 at all. If A sees an event from B1 on the open network somewhere (e.g. as a reply to someone) they will treat that as a normal unknown key.

The only stateful thing is the list of people you're following, but that already exists, so no changes here.

[vitorpamplona]

Oh so you are saying that relays still accept B1 as a valid key as normal, even though the relay got confirmation from the owner the key has been rotated.

Meaning if the key was stolen, relays will continue to work with the attacker.

Should stored NIP04 PMs just disappear as well? Or how would clients know messages aren't being inserted in the past?

[kevinsmith]

DMs are a problem none of the schemes I've seen readily address, including the DIDs discussed elsewhere.

[fiatjaf]

First let's assume keys won't be revoked and rotated all the time. This suggestion here is just for catastrophic events. I am not trying to say everything will be awesome when a private key is compromised.

Yes, relays can still accept the B1 keys even if they are now controlled by the attacker. Relays may want to keep track of revoked keys and block those, but that will be their choice and the protocol shouldn't specify that.

If clients are storing old DMs somewhere in a local database or whatnot they can still keep those and assign them to the new user so the DM history looks the same. If they are relying on public relays to store the DMs or on a private backup relay they can do other tricks to prevent the attacker from inserting new DMs in the history, but again this is client's implementation choice.

The simplest behavior of automatically nuking or hiding DMs once you get a revocation key is good enough to me too. It will save lives.

[vitorpamplona]

The way DIDs address DM is by blocking access to the key. Messages clients have stored remain visible (with a cached key if the client software must reverify the past). But since the key is not in the DID Document anymore, the key cannot be used to receive or send new signed messages by anyone (even if you have a cached key somewhere). The protocol fails the cryptographic verification because it simply cannot find the key. There is no way for the attacker to insert past messages because clients (and relays) use the receiving date time, not the date time inside the payload.

[fiatjaf]

So basically the same UX, except DIDs have a central registry clients can query to fetch all this data, so the implementation is arguably simpler.

[vitorpamplona]

Not necessarily a central registry. The key difference is the control over access to the keys. In Nostr, the key is itself in the payload. If it leaks, there is no way to control it. In a DID scheme, everyone agrees the author has control and can nuke the key from existence.

The proposed scheme here would be similar to DIDs if relays nuked old keys (and blocked the new use of old keys) as soon as they see a rotation. Clients can freeze PMs after they receive a rotation and they have to block the new use of old keys as well.

[vitorpamplona]

First let's assume keys won't be revoked and rotated all the time.

I don't think this is realistic. Passwords should be changed from time to time in any app. Corporate policies always have some periodic rotation (90 days for health care). If you use a T2 chip with the key being generated by the phone in such a way that it never leaves the chip, the private key will need to change every 1-2 years on average when the user changes the phone.

[fiatjaf]

That means Nostr keys shouldn't be treated like passwords or subject to corporate policies, they should be safely stored like Bitcoin keys.

In any case if this scheme would be implemented and people would rotate keys every month it would still require the user to keep a seed in a safe place, so the point you just raised would apply regardless.

[vitorpamplona]

People might be required by law to rotate private keys. For instance, if I use nostr professionally ... say to talk to my customers (I sell medical devices)..., I must have a periodic key rotation policy in place by law.

So, what's the best security scheme here? Right now, I have the same private key in 15 nostr apps at the moment, between my laptop, my desktop, and my phone. It feels wrong reusing the private key. It probably already leaked even though I am trying to be careful. I only expect the number of apps to grow as micro apps are becoming more common.

Maybe the best is to have the seed, get the current key, and then delegate new keys to 15 devices via NIP-26? If the current key leaks, get a new key and invalidate all 15 delegations. If one of the 15 devices leak, rotate that key. Keep the seed completely offline, in a hardware device. The generated private key though will need to be transferred to a laptop for use, or we need to find a hardware device that is able to sign nostr transactions directly on device.

In a DID world, I would have an account with a DID provider (cold or hot) and insert/delete new public keys into that record. So, the "seed" that needs protection is the key to access the DID provider and change the DID Document (probably in a hardware device). In this case, since private keys are never visible or transferred anywhere, it's harder to have a leak.

[fiatjaf]

I understand that you are trying to achieve the perfect UX and security, but really that is not possible. It can't be done on Nostr. NIP-26 delegation is not a silver bullet, it can't be used indiscriminately. This suggestion here is also just a best-effort mitigation strategy that fits well with the rest of the protocol. Unless there is a hidden breakthrough somewhere I don't think we will be able to get the perfect key management UX here.

DIDs do not solve that either.

Also I don't see think Nostr should care about the law. Imagine if Bitcoin had cared about the law? It would have been a protocol for money to printed by the central banks and fully controlled by these.

[vitorpamplona]

I am not searching for the perfect UX. We are not even close to discussing the perfect UX. This is just the very, VERY basics of key management. What people need to do to use Nostr in a safe way in practical reality.

DIDs don't solve everything, but they do solve the issue at hand (key rotation) extremely well.

[Semisol]

why can't you do this?

A' = A + hash(A||B)G B' = B + hash(B||C)G

this allows for generation of keys without having to compute an entire chain with a finite amount of keys.
to overrule A', you publish from B' the value of A, B and hash(B||C). you can verify A' = A + hash(B||C)*G and B' = B + x*G

other method

to overrule `A`, you publish from `B` the value of `A` and `hash(B||C)`. you can verify `A' = A + hash(B||C)*G` and the next key becomes `B' = B + x*G`

[fiatjaf]

why can't you do this?

Because it requires publishing the private key a' when you want to revoke it.

[vitorpamplona]

Crazy idea: what if users don't follow keys, but the NIP05 identifier? Everything else stays the same.

In that way, users can change their keys at any time and UIs would automatically change to the new one. Chats would be migrated since they follow the NIP05, not the pubkey. Followers are marked by NIP05, not by keys.

An extremely simple solution that uses existing tools many apps already support.

Since the hidden commitments proposal will not be implemented by relays (to block misuse of rotated keys), and will have to be implemented by clients, why require more complexity on their side if they already have a working solution?

[eskema]

first, the protocol has no way to follow nip05, and even if it did, the provider could maliciously change the pubkey with another one and send you spam. the authority is the pubkey, not the verifier.

[vitorpamplona]

The protocol doesn't need to follow NIP05. That's the key part.

The client would not follow a public key. The attacker can change the NIP record to whatever it wants, it won't matter. The app will follow whatever key is listed in NIP05 identifiers chosen by the user. It will follow all keys listed there. So if a user has a key per device, all keys are being followed from a single follow(NIP05) in the app.

[eskema]

my head is twisting right now.. if I understand correctly what you're saying is you're fetching all names from the user kind-0 nip05 field domain json? but that only works if the provider is the same user, otherwise you will get random keys. what am I missing?

[vitorpamplona]

Point taken. We could change NIP 05 to be an array of keys per user. But maybe it makes sense to add all keys if the client's user only types the main domain name. It would work for those of us that are using our own domain to place our keys.

[kevinsmith]

This still doesn’t get past the problem of requiring users to trust a third party to authorize using their identity. Even if you hold the domain, you’re still trusting your registrar and ICANN not to rug you.

[vitorpamplona]

Sure, but only because right now NIP05 requires DNS/HTTP (which is a major flaw). It doesn't need to. The same JSON can be downloaded directly from IP, placed behind Tor, and maybe even from a lightning node. It can be a nostr event from another Nostr pubkey, where the latest payload's contents are the exact JSON as defined in NIP-05. Or, It can even be a converted DID:ION address if people want it to be. It's all the same. No DNS/HTTP is required.

The strongest point of this idea is that it separates the cryptographic verification of a message (which continues to be the same and allows the simplicity of the protocol to shine) from the need to identify if a given public key is currently trusted by the client's user. Those are two very different goals.

Either way, the fact a client or a relay can verify a package doesn't mean much. Neither in this new idea nor in the original hidden-commitments proposal. Additional work to identify if the used public key is trusted by the user must be made. And since everybody is already using NIP05 for that, maybe that is the best place for it.

[fix]

Interesting read! Can I sum up the requirements here so it is clear to me, and getting everything right

• having a single nostr private key and copying it/using it in many contexts put it at risk long term. This is a long hanging fruit since the beginning of PGP btw
• the "naive" way (used by PGP web of trust, or keybase for instance) is to publish the key and rotate it via a "known channel": email, twitter, social networks etc... However this is reducing the security to a channel: your email or twitter account is hacked and the hacker can publish a new key, creating confusion. Reducing asymmetric cryptography security to password protected accounts is somewhat ironic....
• Idea here is to be able to rotate in a "predictable way" the key so you don't use for too long your nostr key and feel safe about using nostr long term, without the need of creating a new key and reidentify yourself with your contacts every now and then.

Interestingly there have been recently a keyring protocol addressing a similar issue: one time use of bitcoin wallet: BIP32/BIP43/BIP44 implemented in hardware (ledger, coldwallet, trezor...) as well in many cryptocurrencies tooling. However reusing this as such is not enough: most of the time this keyring is just for allowing yourself followup your wallets and nobody else. Here we need everybody able to "guess" which key is the next one.

Note the BIP32 is not an easy beast for security. If you want to open for public guessing of the next pubkey, you need a non hardened derivation, leading to catastrophic failure if only one of the private key being compromised

Now to the proposed protocol, here is the attack model:

• User generate 1000 keys (npriv, npub) each one using the commitment of the next one (then they are generated backward starting from the last one which is a random seed)
• Since each key is randomly generated, user need to store all of them
• Hacker compromise the first key but cannot propose a new key without compromising the other keys before. This part needs to be formally proven.
• User use the next key and publish the element of the first keys so every one can verify that the second key is committed inside the first key.
• Publishing means somehow making it public (blockchain, directory) etc...
• Contacts are listening for these sources and update keys accordingly.

One interface for the hacker is to delay the propagation of the revocation. Worse, with time revocation database are getting huge, so this would make hard to query and open up to other attack scheme via simple DoS so it make hard to keep 'old' keys so an attacker could reuse the one that are dropped. In this case publishing could become a nightmare to manage. I would advocate for some revocation time to prevent this, ie keys are always distributed with (npub, expiration).

Ok now we are just reinventing the wheel (except the rotation algorithm), because this is exactly what PGP has done with revocation, already signed revocation (if you lose your private key), web of trusts WKS (you know things like https://intevation.de/.well-known/openpgpkey/hu/it5sewh54rxz33fwmr8u6dy4bbz8itz4) etc... and it did not work because this is hard for the user to manage.

My point here is we need to be better if we don't want to have the same issues. So in a nutshell my minimum requirement for a good keyring would be:

• rotating the keys without revealing compromised keys
• get rid of revocation lists by having the web of trust decentralised and stored for very long time 'somehow'...
• minimize the data being stored/queried by the users.

If we see this in a different point of view:

• everybody is a CA (Certificate Authority) and manage their own (D)PKI
• the CA management is able to create keys 'on-demand' (application wise for a period of time)

looks like a pretty hard challenge huh.

[vitorpamplona]

Nice @fix! I agree with everything you said.

On your everybody is a CA idea, I just made this new proposal draft to bring some of the DID structure directly into Nostr: https://github.com/nostr-protocol/nips/issues/123

Feel free to destroy it :) I don't know if it fully works, but we are here to find a solution.

[Semisol]

why can't you do this?

Because it requires publishing the private key a' when you want to revoke it.

No you don't.

assuming we use this

A' = A + hash(A||B)*G
B' = B + hash(B||C)*G

how does proving A' is pointing to B and B' is derived from this require private keys?
you publish:

• A
• hash(A||B)
• B
• hash(B||C)

[fiatjaf]

@Semisol Sorry, I read your proposal backwards. So in your scheme you start with A' and then you move to B', but B' depends on C? So you must have pregenerated C and B when you create A', right?

Actually no, you can generate B at runtime in your scheme. I see.

So when you're moving to B' you need to pick C, which is just a random number. So that works. Interesting.

[fiatjaf]

@fix I am not sure I follow the revocation list stuff. Why do we need revocation lists? We don't. The relays themselves are the revocation lists. Or there could third-party services hosting these revocation events, but these services don't have to be trusted, so they're in the same category as the relays.

Also this is not intended to be a standard routine key rotation procedure, it is just to minimize damage for when keys are compromised -- and make it so the next key is deterministic and negate the possibility of an attacker announcing its own key as the next one from the compromised key.

Also two corrections:

• the proposed scheme doesn't require you to store all the pregenerated keys, you can store just a seed and derive again whenever you need to move to the next key.
• the proposed scheme doesn't require you to reveal the private key that is being revoked, that would be very bad.

[fix]

On revocation list:

• assuming one private key is compromised, you need to have somewhere the information to everybody on earth 'not use this key anymore'. If somehow this information is not available to some people or removed after a period of time, the hacker can use this key to sign events on your behalf using the already compromised key.
• the situation is very similar on what happened for PGP/email i think
• managing revocation services is a hard thing imho

on the two corrections:

• ack, you need to keep only the next key that is commited, no need to pregenerate keys.
• ack, no reveal of private keys (i was not intending that, my text was not clear i reckon)

[fiatjaf]

@Semisol I think it your scheme is broken because if to revoke A' you must publish

• A
• hash(A||B)
• B
• hash(B||C)

Then anyone can immediately publish

• B
• hash(B||C)
• Y
• hash(Y||X)

And say that the next key is Y' = Y + hash(Y || X). There is no way for anyone to differentiate X from C and hash(Y || X) from hash(C || D) as these are just opaque unknown values. So basically anyone can revoke anyone else's key and assume their place.

[fix]

lol, was about to post this way of hijacking the key stream

[makinTheStuff]

I'm new and I have a lot of catching up to do so I hope it's ok if I join in on the discussion. What if instead of trying to revoke or cycle keys bitcoin is used as a clock. Using your seed you can generate a key and sign a message with the public key and block height at the time of signing which you use as your ID. If you would like to broadcast a new key include your old pub key, new pub key and signature of the new pub key and current block height. That way if your key is compromised it has a global "date" so clients can easily distinguish which events are valid. One last thing with respect to that is if a key was compromised at block 769082 and the victim finds out at 769092, the clients interacting with the attacker now has now been communicating for the span of time it took to complete 10 blocks. If the victim knows the last time they shared a valid message sent from them then they can figure out what the blockheight would have been and use that block height to generate the new signature which would invalidate all the prior messages keeping dm's and the like in tact. The extreme of this could be using a private key with the ability to spend a btc utxo's. In that case you can do the same thing but include proof of ownership which would allow you to revoke a whole set of keys when spending btc to another wallet if that was something clients wanted to incorporate.

Thank you all for sparking this flame. It's exciting to be here and I hope I can help

[fix]

hi @makinTheStuff Your solution is based on registering id on bitcoin which has 2 aspects

• expensive, so most user won't be doing it, on their own so delegating on third part this aspect
• will be public, might not be always a wanted feature.

On the security side, all users SHOULD check bitcoin every time they verify a signature, so in the end, everybody SHOULD have a bitcoin node too.

If all these aspects are respected, yes this is likely the most secure way of dealing with your keys. There are interesting projects going on leveraging this technique, the main one being ION backed by microsoft which is a protocol doing exactly that (you can check one of my impervious key there) and for general user you can check Impervious browser built around it.

[cameri]

I'm new and I have a lot of catching up to do so I hope it's ok if I join in on the discussion. What if instead of trying to revoke or cycle keys bitcoin is used as a clock. Using your seed you can generate a key and sign a message with the public key and block height at the time of signing which you use as your ID. If you would like to broadcast a new key include your old pub key, new pub key and signature of the new pub key and current block height. That way if your key is compromised it has a global "date" so clients can easily distinguish which events are valid. One last thing with respect to that is if a key was compromised at block 769082 and the victim finds out at 769092, the clients interacting with the attacker now has now been communicating for the span of time it took to complete 10 blocks. If the victim knows the last time they shared a valid message sent from them then they can figure out what the blockheight would have been and use that block height to generate the new signature which would invalidate all the prior messages keeping dm's and the like in tact. The extreme of this could be using a private key with the ability to spend a btc utxo's. In that case you can do the same thing but include proof of ownership which would allow you to revoke a whole set of keys when spending btc to another wallet if that was something clients wanted to incorporate.

Thank you all for sparking this flame. It's exciting to be here and I hope I can help

This creates a dependency on Bitcoin which is undesirable.

[ghost]

This creates a dependency on Bitcoin which is undesirable.

Agree.

[ursuscamp]

I'm torn on the issue of Bitcoin dependence.

I understand wanting to avoid the image of nostr being just a hangout place just for Bitcoin enthusiasts, but the Bitcoin blockchain is a unique resource in the history of the internet, if you're looking for an objective source of truth. And this problem is just screaming for an objective source of truth somewhere in the solution.

[kdmukai]

The generated private key though will need to be transferred to a laptop for use, or we need to find a hardware device that is able to sign nostr transactions directly on device.

Wherever things land, I'm ready to build air-gapped Nostr key generation/delegation/rotation/signing into SeedSigner. Currently just playing with key generation and export, but helping to build out python-nostr so I'll have the necessary tools ready to just plug in and go.

[test7813]

hi there, I have a proposal:

I agree that until we are dependent on DNS we're kinda stuck even with DIDs... also we always forget about things like the nonce used for signing messages etc.... we have no control over the client's source code and whether they are doxing or not

Let's have 2 npubs per profile. The master Npub is generated (preferably on airgapped seedsigner) and is the only one that is allowed to modify the master npub associated with the profile. The child npub is the one used for everyday signing and so on

If/when the child npub is compromised simply publish a profile update with new master and child npub. optionnally stamp blockheight+UTC after which the user wants to signal compromission

ideally the Nostr note publishing the new profile update should be QR coded from airgapped device

I know it's not perfect but it makes it already that much harder to break