Authentication key rotation

[MartianSiddharth]

This issue thread will be used to better understand auth key rotation and how we can leverage it in the best way. This will also play a role in standardizing the handling of addresses and enable better interoperability among wallets. The initial conversation between @magnum6actual, @CapCap and @zekun000 is copied from discord.

Magnum6:

I'm tracking how the key rotation functions now - but I'm not tracking how to restore an account once the key has been rotated. For example, let's say I'm the owner of account 0xWHATEVER. When the account was created, the address was created by:

/** Returns the address associated with the given account */
  address(): string {
    return this.authKey().slice(-32);
  }

And authKey was created by the sha3 hash of my initial public key which resulted in address 0xWHATEVER. Being the security minded guy that I am, I rotate my key via Account::rotate_authentication_key which lets me sign with my current key and replace it with the new key I provide which in turn updates my authKey to the new sha3 hashed value. All good.

However, now there is no programatic relationship between my publicKey/authKey and the address of the account. If my computer crashes and I have to recreate my account/wallet from my seed phrase, how do I restore the address of the account? Does the user have to keep up with both their seed phrase mnemonic as well as the address? The address() getter (again):

/** Returns the address associated with the given account */
  address(): string {
    return this.authKey().slice(-32);
  }

would not return the original address if the key has been rotated.

I'm sure I'm missing something simple here. How do applications know the address of the account once the key has changed? Does the address change as well when the key is rotated? If I rotate the key in this example, is my address no longer 0xWHATEVER?

The only thing I see happening in Account::rotate_authentication_key is: account_resource.authentication_key = new_auth_key which suggests the address remains unchanged.

Max:

this is a great question! So this kind of uncertainty and almost "weird" relationship is a side effect of any system that allows for

1. public(or private) key to address derivation
2. key rotation Lets say you have two keys: Ka, and Kb and you also have the two derived addresses of those keys: Aa, and Ab

You have Ka, which you use to claim Aa, and mint some tokens to it from the faucet. All good so far 🙂

Now you want to rotate keys, as mentioned, so you rotate the key to Kb. Although you could use Kb to claim and mint tokens to Ab, all your stuff is already on Aa, and you just want to rotate the key for security.

After rotation, the state of the world is such:

1. The auth_key is changed for Aa from Ka to Kb. If you try to sign a transaction acting upon Aa with Ka, it will be rejected. If it's signed with Kb, it will work normally. No addresses have been changed: just which key is allowed to sign transactions for them
2. As you noticed though, key derivation is now broken for Ka: it doesn't control any addresses. Without going to the chain to ask "are you controlled by Ka or Kb?" there is no way to know. And of course because we take the SHA3 of the public key to get the auth key, there is no way to determine what the public key is given an auth key
3. With Kb in hand you could, if you were so inclined, still claim Ab as normal. If you were so inclined you could generate keys K[c...z] and then claim addresses A[c...z], and rotate the key for all of those to be Kb.

Does that make sense?

Magnum6:

Tracking on all of that. The question, though, if I only have knowledge of Kb, how do I even know what Aa was to begin with? Back to the scenario of the "new computer". I'm setting up my Aptos wallet, I enter the 12-word mnemonic for my most recent key which regenerates keypair and the hashed authkey. How does the application now know what Aa was before I rotated the key? How does Aa make it into the Account object because this.authKey().slice(-32); is just going to give me Ab? It seems that I have to either maintain a record of Aa or a record of Ka after I rotate the key just so I can know what Aa was.

Max:

yeah, that's unfortunately the tradeoff for allowing key rotation, and breaking the derivation assumption. I do imagine it could be a function of services and/or wallets to index said key rotations, and show you all addresses to which your key could go to 🙂

Magnum6:

Tracking. I'm going to ponder this one for a bit. This will be perceived as a significant issue for users. Not only do I have to keep my 12-word secret phrase. If I rotate my key and don't also accurately keep a record of a string of characters like "0xc8585f009c8a90f22c6b603f28b9ed8c", I have for all practical matter lost my assets. That's a pretty significant weak spot in the armor in my mind.

I think there may be a simple solution, though. Upon key rotation form Ka to Kb, register Ab with a single resource of something like:

struct OriginatingAddress {
   addr: address
}

where addr gets set to Aa on each rotation - along with some code that resolves either this.authKey().slice(-32); for a new account or pulls that resource for a rotated account. As you rotate through K[c..z], you always have A[c..z] with the original address. Maybe encrypt addr's value with K[c..z] to fully protect the rotation.

Max:

I think it's likely that the distributed recovery will be a thing, and that many wallets will use said services to allow a mnemonic to be sufficient for users to reclaim their addresses. I agree that it's a rough edge though

The reason for the auth_key is to maintain a common interface (the hash) for different cryptographic methods - i.e for multi ed25519 you'd have a vec of public keys instead of just one

Zekun:

thanks for the proposal, it's interesting and doable for people to create a new account at Ab and store the original address as resource there. I'm not sure it should be provided as mandatory service by default since it incurs cost, it'd be a fun hackathon project. Developers could also have name service to register string -> address too

Magnum6:

I'll move this conversation to repo issue now, but this is a problem you should not think about in terms of engineering cost. It's a UX cost - and I promise you it's wildly more expensive as a UX problem than an engineering problem. Don't position one of the best features of Aptos, key rotation, as a trade-off. That language should not even be in the marketing lexicon.

Zekun:

I didn't mean engineering cost, i mean the gas cost for creating new account and resource at Ab.

Magnum6:

Either way. Either Aptos does it or it has to be built external, but someone has to pay for it and those costs accrue to the user regardless of where they originate from. What's the projected frequency of key rotation and the real dollar/fiat terms in account lifetime gas fees for implementing? I suspect it's negligible.

Zekun:

my thought is to provide options for people who don't want to pay the extra cost to opt out, or rather who want it to opt in. the core lib should be minimized

[magnum6actual]

@MartianSiddharth - thanks for posting this.

A few thoughts/notes:

1. The above code was prior to the 32 byte address - so the slice is gone. That's immaterial to this issue, but thought I'd point it out.

2. While persisting the address could be handled by wallet implementors - I don't think that's a great path. It needs to be handled on chain. Without that, we're introducing an unnecessary vector for losing access to accounts that isn't a problem for other chains and inviting wallet interoperability problems. With so much great going for Aptos, no reason to introduce failure points that don't exist on other chains, especially when those can be mitigated.

3. When calling AptosFramework::AptosAccount::rotate_authentication_key, I think we should create an OriginatingAddress resource as descried above and store the original address there at the address pointed to by the new authKey. In other words, using Max's notation, with rotating key Kb for Ka at address Aa, store that resource with Aa at address Ab. This gives us a link back to the original address. And this would happen for every future key rotation as well so that Kn/An always has a pointer to Aa.

4. Standard practice for Aptos wallets would then be to persist the private key plus the address in local storage. This is different from wallets on other chains that just store the private key. Initially, that address is just the authkey, but will be different once keys are rotated. When the wallet is pulled from local storage, the private key and address would be used in account constructor constructor(privateKeyBytes?: Uint8Array | undefined, address?: MaybeHexString) (from the SDK).

5. The only time a wallet provider would need to access the OriginatingAddress resource is when reconstituting a wallet from a mnemonic phrase. The phrase allows restoration of the keypair/private key. One could then access the original address by reading the OriginatingAddress resource stored at the derived address for the just restored authkey (e.g. the Kb/Ab->Aa from point 3 above).

6. This would require an addition to AptosFramework::AptosAccount with some function to access the OriginatingAddress resource and ideally a matching call in the sdk.

I think this approach ensures all wallet implementations handle persisting the address in the same way, eliminates a new vector of losing account access, and doesn't require much in terms of additional compute or storage resources as new calls/storage only happens when 1) rotating a key, or 2) reconstituting a wallet from a mnemonic phrase.

Of course - all is open for discussion. We're happy to take a whack at a PR but will be a week or two before we can get to it. Anyone else can certainly take the lead if so desired. Although, that being said, I'd certainly like to hear other thoughts on this.

[MartianSiddharth]

I agree with your approach. Without the original address, a user will just lose their account and their assets. So, storing the original address of the user on the blockchain makes complete sense.

We can make it optional to store the address persistently after each rotation by using a flag in the functions - here the user will be responsible for storing their addresses (along with their mnemonic). This is a risky operation as a computer crash could possibly lose their address information, to avoid it, we can make the default value of the flag to indicate storing persistently on the blockchain (using OriginatingAddress as mentioned)

[Kabie]

@magnum6actual

Some edge cases:

1. Kb could be the auth key of Aa, Ab and Ac at the same time.
2. It is possible that Ab's auth key could already be replaced with Kc.

[magnum6actual]

Yeah - and I don't even think I'd call those edge cases as we've already hit #1 in early user testing for our app. Both cases are possible, even likely, and will have to be accounted for by wallet providers. In as much as the community can handle these in a unified manner - it will go a long way towards supporting cross wallet mobility.

Which furthers my belief that there needs to be an on-chain scheme to handle the cross referencing or the key rotation capability is going to become the new way crypto users lose access to their resources - a loss vector that only Aptos users are at risk of.

[MartianSiddharth]

I agree with the above comment. Just wanted to add here that these edge cases can only be produced by a single user using the same key pair (Kb) for multiple accounts (Aa, Ab, Ac). It is highly improbable for another user to land on the same key pair Kb

[MartianSiddharth]

Another way of storing an address (Aa) is through the original mnemonic phrase (Ma) that was used to create the account (address = auth key). Aa = f(Ma) The new mnemonic and the old mnemonic can be concatenated. So, instead of storing a 12/24 word mnemonic, users will be storing a 24/48 word mnemonic. This way the user doesn't have to store two separate types of data (mnemonic + address) but rather a longer mnemonic (which they were probably anyway not memorizing). Mb . Ma On further rotations, the last half of the mnemonic phrase carries over and is concatenated to the end of a new mnemonic phrase Mc . Ma

What do you think of this solution?

[magnum6actual]

That can work for basic key rotation - but it can't account for the edge cases (or likely common cases) that @Kabie suggests. Then you've got the "why are aptos mnemonics 12 then 24 or 48 words?" user confusion/friction.

All of these scenarios can be handled on chain by Account::rotate_authentication_key. Sometime in the next couple of weeks I'm just going to write a PR with a suggested method (likely a vector

of all addresses Kn is the auth key for).

[JoshLind]

@magnum6actual, forgive me if I'm missing something! 😄 Just trying to catch up on this thread.

TL;DR, why can't we use a blockchain explorer to identify all the accounts with authentication keys that match our new one? If we find an account, the address should be held under the account resource as self_address? Or are we worried that searching all accounts is expensive? I suspect I'm missing something 😆

Don't we technically have all the information we need for account address recovery already on-chain? For example, when we create a new account, we:

1. Use a mnemonic phrase to generate an Ed25519 private/public key pair (priv_a, pub_a).
2. When the account is created on-chain, we first create an AuthenticationKeyPreimage (which is just pub_a concatenated with a scheme identifier: pub_a | scheme_id) and then create the AuthenticationKey using sha256 of the preimage, i.e., auth_key = sha_256(pub_a | scheme_id).
3. The derived address from the auth_key is simply some prefix of bytes from the auth_key, e.g., the entire auth_key at Aptos or the first X bytes in other implementations. So now we have account_address = some_prefix(auth_key).

Now, we want to rotate the authentication key for the account_address. We do:

1. Use a new mnemonic phrase to generate a new Ed25519 private/public key pair (priv_b, pub_b).
2. Follow step (2) above to get auth_key = sha_256(pub_b | scheme_id).
3. Call Account::rotate_authentication_key(new_auth_key) which internally just updates the authentication_key internally for the account, i.e., account_resource.authentication_key = new_auth_key.
4. Forget the old mnemonic phrase from (1) in the previous paragraph.

Now, how we do identify account_address with the new mnemonic phrase only? We generate (priv_b, pub_b) again, construct the auth_key from pub_b again, auth_key = sha_256(pub_b | scheme_id), and then just use a blockchain explorer/indexer to look up any accounts that have an auth_key that matches ours? This should tell us all the accounts we "own". Does this make sense?

[magnum6actual]

Tracking. I like the idea - but auth key isn't searchable (that I'm aware of) in the Aptos devnet explorer. Although - that could be easy enough to add. It would be great to see it as part of the api - like /authkey/{authkey}/addresses and return all addresses linked to that authkey.

[JoshLind]

but auth key isn't searchable (that I'm aware of) in the Aptos devnet explorer. Although - that could be easy enough to add. It would be great to see it as part of the api - like /authkey/{authkey}/addresses and return all addresses linked to that authkey.

Yeah. There is a workstream planned to tackle exactly this: offering more support for searching through on-chain data. From a user experience perspective we'll want this functionality anyway, to help with things like tracking tokens, NFTs, ownership, etc., Auth key will be another one of these 😄 Glad to hear there is a way to solve this today, though!

[magnum6actual]

Spent some time contemplating this today and now think the auth key search is not the right path. A fundamental principle of Move is not allowing random assets to be sent to an account. Wallet auth key search allows me to bypass this restriction. I can create an account, load it up with resources, call Account::rotate_authentication_key and drop in my target's auth key, and now I've spammed them with a resource they didn't want - if wallets are searching for auth keys.

I'm back to my original premise that this needs to be an on chain record. I also need to quit running my mouth and just write the code/pr to demonstrate.

[JoshLind]

@magnum6actual. Apologies for the radio silence. There's been a lot going on. To respond to your comment above: I agree that it's not ideal and there's obviously a few things to consider here 🤔

A fundamental principle of Move is not allowing random assets to be sent to an account.

I guess what this comes down to is how you semantically define account ownership 😄 Sure, a random account (with random assets) now shares the same authentication key with you, but the spammer still hasn't assigned "random assets" to your account, i.e., you could always choose not to "claim" that account or do anything with it. 😄 However, I agree that this kind of spam attack isn't great. Especially if we want to live in a world where we define account ownership as simply holding the private portion of the authentication key.

However, one simple way of solving this problem is to augment the Account::rotate_authentication_key method to also require the caller to prove they have the corresponding private portion of the authentication key (e.g., the caller must also sign a nonce using the private key before the rotation is considered valid). This solves two issues: (i) it prevents users from accidentally rotating the authentication key to something they don't own; and (ii) it prevents the spam attack you outlined above. I still think this is cleaner than needing to build some form of address chaining. Actually, the more I think about it, the more I believe it makes sense. I'd be interested to see what others think here too 😃

[magnum6actual]

@JoshLind I like where you’re headed with this. I think there are really 3 constituent points that make up the broader issue:

1. Should we allow key rotation without verifying ownership of the destination auth key?

2. Should “authkey to address” be a one-to-one or one-to-many relationship?

3. How to best persist the address for a given auth key?

To me, #1 is a no-brainer. You should not be able to rotate key to an auth key you don’t own. That’s easy enough.

The second point isn’t as clear, but my opinion is that a one-to-one constraint makes the most sense. I think it can get confusing for users to have multiple addresses/accounts for one singing pair. And when you get into key rotation - if there are multiple addresses using the same auth key, when you do try to rotate, you have to rotate all of the addresses introducing the possibility that some get rotated, some don’t (if transactions fail), and now you’ve got multiple addresses and multiple auth keys. A one-to-one address to authkey constraint eliminates all of that.

So the, the final question, how to best persist the address for a given auth key. This becomes easier with the above two constraints. To enforce the one-to-one relationship constraint, we need to set a state showing that an auth key has been assigned. We can do that by writing the corresponding address to a struct on the auth key.

Here’s a rough example (disclaimer, I haven’t tried to compile this):

struct KeyPointer has key, store {
        target_address: address,
    }

public fun rotate_authentication_key_internal(
        account: &signer,
        auth_key: &signer,
    ) acquires Account {
        let addr = Signer::address_of(account);
        assert!(exists_at(addr), Errors::not_published(EACCOUNT));
	let new_auth_key = Signer::address_of(auth_key);
	//verify nothing exists at the address of the new auth key
        assert!(!exists_at(new_auth_key), Errors::invalid_argument(EAUTHENTICATION_KEY_IN_USE));
        let account_resource = borrow_global_mut<Account>(addr);
        account_resource.authentication_key = new_auth_key;
	//create an account at the address of the new authkey, establishing the "used" state along with persisting address relationship
	Account::create_account(new_auth_key);
	move_to<KeyPointer>(auth_key, KeyPointer {target_address: addr})
    }

Now - the above is just an idea. There are other things to factor (do you delete the KeyPointer account when rotating again, a support function to allow rotating an account authkey to 0x0, testing etc). But this gets the idea across. It’s cheap as the only time you’ll run this code is on key rotation. This also gives you a quick REST API way to pull the struct with the address associated with the auth key without the overhead of an indexer search. And wallets can locally persist the address after the first lookup (although there could be a scenario where the key is rotated outside of the wallet - but that can be checked upon signature failure).

[CapCap]

Just a thought; it could signal security to rotate to 0x to guarantee the original module author can’t touch the account contents

[magnum6actual]

Just a thought; it could signal security to rotate to 0x to guarantee the original module author can’t touch the account contents

Yeah - that was the thought. Would need an explicit function in AptosFramework::Account to rotate to 0x if something like the above was implemented. I'd be a proponent of a function to do so titled Account::burn_the_ships

[Kabie]

I think it would be more flexible if we make a safe version that require the rotated key to claim the auth, and keep the one we have now.

[davidiw]

There's a lot of text here, so let me summarize something we can do:

1. Account creation -> wallet generates key and mnemonic
2. Key rotation -> new private key, rotates new auth key on-chain, on-chain creates account associated with the new auth keys address and installs a redirect resources
3. Key recovery -> produces a private / public key -- wallet looks on-chain to see if there's a redirect resource and uses the redirect address. It then validates that the current public key maps to the auth key on the destination / source / originating account.

If this is generally agreeable, I can throw together an extension to the rotation function that does this and maybe we can close out this issue?

[magnum6actual]

This is good, @davidiw

[movekevin]

The redirect resource makes sense but there are several concerns in the thread that have not been adequately addressed:

1. the new Kb key can own public addresses Aa, Ab, Ac. This means the redirect resources would need to support multiple public addresses.
2. Rotating the key now costs extra gas. If the redirect resource has a long list of public addresses, this will become more and more expensive over time a more addresses are added.
3. Junk public addresses in redirect resource. This happens if Aa is rotated to use Kc for example instead of Kb. The redirect resource at Ab will still think Kb can unlock Aa but that's no longer the case. This leaves some "junk" resources around that's just a waste of space. This might be addressable with a "cleanup" function that Kb can call but I suspect no one would want to call it as it's just extra gas they have to pay that doesn't benefit them. The junk resources would just unnecessarily add to network storage => Tragedy of the common

[magnum6actual]

My preference would be to enforce a 1-to-1 relationship between addresses and authkeys. That would make @movekevin these issues simpler to resolve.

On key rotation, confirm the address corresponding to incoming authkey doesn't already have resources (e.g. if it has an Account resource, then it is already the authkey for an account that hasn't been rotated, if it has a redirect resource, then it is the auth key for an account that's had at least 1 rotation). If the incoming authkey is already affiliated with either of these, the rotation should fail.

Second, when rotating the key, delete any existing redirect resources of the currentauth key.

I think that handles everything.

[jjleng]

In my opinion, creating a redirect resource for address lookup is less ideal. The reasons are already discussed in this thread. The resource is a side-effect state that requires extra maintenance (such as cleaning up properly) and costs extra gas.

I actually like @JoshLind's idea. The information can be looked up through explorer/indexer. We need to provide a canonical way for people to look up this easily.

As far as @magnum6actual's comments:

1. Should we allow key rotation without verifying ownership of the destination auth key?

2. Should “authkey to address” be a one-to-one or one-to-many relationship?

1 is a no-brainer indeed. We should perform the ownership check. As Josh suggested, we can "augment the Account::rotate_authentication_key method". I think we have an agreement on this. We need to ask users to prove that they own the private key of the target auth key.

I don't think 2 is necessary. Mapping one set of key pair to multiple addresses is actually convenient. A wallet can easily allow users to switch accounts with a dropdown. In terms of the rotation failure case as @magnum6actual mentioned ("some get rotated, some don’t"), it is honestly the user's responsibility. They need to retry if they want. The bottom line is the assets are still safe even if rotation failed provided that the private key was not leaked.

[magnum6actual]

I'd push back in this. Pulling an address from a resource is less computational intensive than an indexer search. Writing & deleting the redirect resources is likely fractions of a penny in gas.

On the issue of a 1-to-n relationship between auth keys and addresses, we really need to think about this from a UX perspective. Choosing the key pair I'm going to use then turns into a multi-step process of what address affiliated with that key pair am I going to use. And the user has to keep track of what mnemonic goes with what key pair goes with what addresses??

I would not leave this issue to "it is honestly the user's responsibility". Why would that be the case? UX should lean towards the users' benefit and ease, not the developers'.

[jjleng]

I would argue that computational heaviness is not a big concern in this case. Given that indexer is used in other heavy use cases anyway, like NFT token look up. Writing and deleting one resource might not be costly. But they could add up. e.g. for custodial wallet providers/apps who manage 100k+ wallets, why should they pay thousands of dollars each month for key rotation (assume they do key rotation each month).

1-to-n vs 1-to-1 is the key discussing point between these two paths. This is indeed a UX discussion. Without this 1-to-1 assumption, the redirect resource solution could be complicated. 1-to-1 doesn't solve "And the user has to keep track of what mnemonic goes with what key pair goes with what addresses??". If a user owns multiple addresses, she has to keep track of n mnemonic to get each address for the 1-to-1 situation. With 1-to-n she needs to keep track of a few mnemonics. The ideal case is a user only has to keep track of one latest mnemonic. In the failure case, she might need to remember 2 or more. But this is still less than the 1-to-1 case. I personally prefer to enter the mnemonic once and recover all my addresses rather than do it five times.

[davidiw]

There are a lot of tradeoffs in the space.

Key considerations:

• Wallet dependency costs
• Security
• Costs
• Simplicity

Events and indexers)

• Requires a dependency on an external service that may or may not be available
• Events are pruned so a dependency on an indexer is a must
• Indexers are not necessarily direct representations of the blockchain
• Cost is limited to that of emitting an event (should still be in the realm of creating a new resource)
• Easily allows the same private key / public key to be used by multiple accounts (though this is arguably insecure)
• Security concerns: which indexer, where is it hosted, how is it verified

Account + Resource)

• No external dependencies, can easily be retrieved by querying any fullnode, these are canonical, consistent
• Resources are not pruned
• There is some resource propagation but that can be mitigated by cleanup on rotation
• Requires a vector of addresses if we want to support multiple addresses and in turn the complexity of the contract
• Cost may be a bit more, but if the cost of creating an account is so high, then Aptos is at a disadvantage -- in other words, this should be negligible
• Security concern: account rotation can result in a resource being created at another account. Mallory may notice Alice is about to create an account. Mallory "rotates" her key to Alice's despite not knowing the private key. Alice may be able to claim her account, but it has a RedirectionResource that may confuse Alice's wallet. There are a few options around this:
  • Make the protocol that processes RedirectionResources ignore these
  • Require a two phase rotation (create account for redirection resource and then submit a multiagent transaction that creates the resource)
  • Have proof of private key ownership in the rotation method -- if there's a desire to create a RedirectionResource. cc @alinush

My gut feeling initially was the event approach, but the lack of canonical and verifiable indexes and events is concerning.

[alinush]

What a great discussion!

Regarding the proof of ownership during account creation (i.e., a proof of knowledge of the secret key associated with the public key hashed in the auth_key), I tend to agree that we should have it. Not just for spamming, but also to err on the side of safety.

Regarding recovering a wallet via indexers versus via storing a pointer to the old address, I'd say the centralized answer is indexers while the decentralized answer is to have a pointer to the old address. Depending on the frequency of wallets being recovered, we might be okay with the centralized answer since, after all, someone will run an indexer.

Regarding having the same public key (auth_key) for multiple accounts (addresses), my instinct is to go with simplicity here and enforce a unique public key per account. I'd say multiple mnemonics for multiple accounts can be avoided by doing some careful key-derivation.

But, AFAICT, to enforce a unique public key per account we'd need the pointer solution of @magnum6actual, which means we could avoid indexers "for free."

[alinush]

Closing this issue since it seems to have been addressed by implementing the OriginatingAddress table in https://github.com/aptos-labs/aptos-core/pull/2972. Re-open otherwise.