Protected Recovery Phrases: Plan and Progress

[nmattia]

Hi all!

There have been talks of making recovery phrases more secure. This is the plan to make it happen, and progress updates will follow here!

Relevant threads:

• Internet Identity Lack Of Security
• Immediate Action to Protect Internet Identity w/ Seed Phrases

TL;DR: @lastmjs and @Oleksii will contribute a cool feature

---

On May 12th, @lastmjs, @Oleksii, @Litzi, @dostro, @frederikrothenberger and myself discussed how to make this happen. For the record, Identity Labs (@dostro, @Litzi & @Oleksii) and @lastmjs offered to actually implement the changes, so big thanks to them! We’re updating the contributing guidelines and getting some internal (DFINITY) approval; once that’s done, this contribution will hopefully open the door to more people sending patches for Internet Identity!

Problem recap

You created an Internet Identity anchor and used it to log in to the NNS dapp, where you staked 10,000 ICPs in neurons for 8 years. A few months later, an attacker steals one of the devices you use to authenticate.

• Current situation: The attacker deletes all your recovery and authentication devices. You lost access to your anchor. You despair. You know that, in a little under 8 years from now, someone will be able to cash in on our dissolved neuron and convert all that ICP (10,000 + reward) to cycles for a ChatRoulette clone on the IC. You become a pessimist. You find solace in crypto market crashes and red ICP price plots.
• With proposed solution: The attacker cannot delete your recovery phrase because it is protected, meaning you have to enter it in order to delete it. You recover your anchor, delete all (compromised) authentication devices and you add new fresh devices. You have learned a valuable lesson about securing your devices and start a thriving IT security business. You have many beautiful children.

Solution

As hinted in the paragraph above, the proposed solution is the allow users to make their recovery phrases “protected”, meaning that in order to delete a recovery phrase, you need to first type it.

Ok, now comes the boring part where we describe the UX of “protected recovery phrases” (codename: “protected recovery phrases”) in excruciating detail. See below for even more boring implementation detail.

Functional Spec (or “how will it actually work”)

Let’s go:

• From now on, there will be an option to make a phrase “protected”. By making a recovery phrase protected, you will not be able to delete it without being able to type it in.
• This only applies to recovery phrases; other devices (regular authentication devices, recovery FIDO devices) are not affected.

  We focus on recovery phrases for 2 reasons: keep the change as simple as possible, and make sure we don’t limit ourselves for future enhancements to FIDO device security.

• This mechanism will be completely opt-in (optional and disabled by default).

  The “protected” feature is optional because some (3rd party) canisters rely on users being able to delete recovery phrases without having access to the recovery phrase.

• Existing recovery phrases will not be upgraded to “protected” automatically, but they can be upgraded to “protected” by the user. New recovery phrases will not be protected by default.

  We cannot automatically update existing phrases because current users may have forgotten their recovery phrases (can’t blame them, I surely did) and may wish to delete them and create new ones. We also cannot make new phrases “protected” by default because we want to avoid confusion (though we may do this in the future just to mess with them (joking, don’t quote me on this))

• To upgrade an existing phrase to “protected”, the user will need to input the recovery phrase.

  Because users like me (who have forgotten their recovery phrase) get excited about new features and click “YES I DO” and most likely would be stuck forever with an unwanted “recovery phrase”. Happened once, still have the ring. (just kidding) (we also do this to make sure users know exactly what they’re getting into)

The UI won’t change much, but notice the lock () icon near the recovery phrase:

When the lock is closed, the phrase is protected. When the lock is open, the phrase is not protected. Clicking an open lock will prompt for the recovery phrase, and (if correct) will then upgrade the recovery phrase to protected. Clicking a closed lock will prompt for the recovery phrase and (if correct) downgrade the phrase to not protected. (@lastmjs thinking of this now: should we allow downgrading? also, should we simply not show the “X” for deleting when the phrase is locked?)

Implementation

Ok, if anyone’s still reading, let’s talk implementation.

A new canister method will be added for “updating” a recovery phrase. This will perform an atomic update, be it either upgrade to or downgrade from protected. This method will either return “success” or an error; the error can be either “bad recovery phrase” (if the provided phrase did not match what the canister has) or “no more space” which may happen because making a phrase protected takes a little more space (see next point).

(is anyone really still reading?)

Special care has to be taken in the canister since adding a bit of information to a phrase (protected: true/false) will grow the anchor record. Since each anchor is serialized/deserialized as candid individually, and since candid supports optional fields, the first approach will be to add an optional field (“protected”) to recovery phrases. This means that deserializing existing, non-protected phrases will Just Work™. If this doesn’t work, a new variant (δ,ο,) may be added to KeyType; however we try to avoid this as this isn’t what KeyType is for, and it may be used in the future (if we enable attestation).

Plan

Alright! Who’s actually going to implement this?

• @lastmjs will implement the UI changes
• @Oleksii will implement the canister changes

Thanks to them! In the meantime, DFINITY (ok, @nmattia) will work on the following:

• Make sure we can accept external contributions in time
• Provide a framework for downgrade tests (in case we need to rollback, esp. with the stable memory changes)
• Add haskell integration tests for the features (we’re not going to force anyone to learn haskell to contribute)

I’ll share more details on the timeline Soon™, but this should land by the end of May. Fingers crossed!

[paulyoung]

@nmattia

should we simply not show the “X” for deleting when the phrase is locked?

I suggest keeping the “X” but changing the appearance to communicate that it’s disabled.

[paulyoung]

@nmattia

should we allow downgrading?

As opposed to what? Only being able to remove the recovery phrase?

[paulyoung]

@nmattia

Special care has to be taken in the canister since adding a bit of information to a phrase (protected: true/false) will grow the anchor record.

I think I saw some (pseudo?)code which added this as a boolean value and I would like to suggest that an enum be used instead to protect against boolean blindness.

I would hate for there to be a bug because someone made a programming error where they provided true or false but meant the opposite.

I propose something like this instead:

enum {
  Protected,
  Unprotected,
}

I’m not sure if this has any impact on the size concerns.

[paulyoung]

I’d love it if people could share links to PRs in this thread.

[CatPirate]

@nmattia

. You have many beautiful children.

Maybe the owner can use their names as answers to security questions I personally prefer some passwords and a few more security layers added to it.

[sat]

You created an Internet Identity anchor and used it to log in to the NNS dapp, where you staked 10,000 ICPs in neurons for 8 years. A few months later, an attacker steals one of the devices you use to authenticate.

One very likely “device” to be stolen is IMHO a non-physical device, and that would in our case be the “recovery phrase”. Is there anything we can do to prevent this theft?

Maybe we can require entering multiple authentication and/or recovery devices in order to remove the “recovery phrase”? The actual required mix of the devices would be open for discussion, of course.

[mparikh]

@sat

One very likely “device” to be stolen is IMHO a non-physical device, and that would in our case be the “recovery phrase”. Is there anything we can do to prevent this theft?

Threshol sig the recovery phrase. The point is to divide the recover phrase into n tokens out of which any m tokens are required to recreate the recovery phrase. (m < n). See here ( GitHub - icdev2dev/bachao: Social Recovery of Internet Identity) for the concept & MVP.

[nmattia]

@paulyoung

I suggest keeping the “X” but changing the appearance to communicate that it’s disabled.

I like that, I guess we’ll let @lastmjs experiment a bit and he can share some thoughts with us

@paulyoung

As opposed to what? Only being able to remove the recovery phrase?

Yes, but I realize now it would be a bit confusing

@paulyoung

an enum be used instead to protect against boolean blindness.

Agreed; I’m sure @Oleksii will come up with a nice solution, if there’s anything unclear we can discuss it on the PR once it’s submitted!

[nmattia]

Agreed, there are many possible solutions we could implement; I suggest you contribute the idea in e.g. the original thread, and that we keep this thread for discussing the particular solution of “protected” recovery phrases!

[nmattia]

Alright, it’s been a week!

Quick update from our side:

• As mentioned here, II now officially accepts external contributions.
• We’ve gotten started on the “downgrade” test framework, which will be implemented in Rust (as opposed to the existing canister tests that are written in Haskell).

Note that we’ve also pushed some changes to the FAQ to clarify a few things regarding recovery phrases (as they are now), let me know if you have any feedback!

[Oleksii]

Hello guys. Sorry for delay. My vacation was a bit longer than planned. Guys I’m fan of generic solutions which can be used somehow in future. So I want to propose something like this:

@nmattia @lastmjs @paulyoung what do you think?

[nmattia]

@Oleksii

My vacation was a bit longer than planned.

Hope it was a good one

@Oleksii

I’m fan of generic solutions which can be used somehow in future.

I think we should also be careful not to make things more complicated than they need to be; I’ve often found that codebases rarely takes the direction you thought they’d take. In this case in particular I think we’re aiming for a small fix while we hash out the details for a “perfect” solution (lots of great ideas being floated in the original thread).

Did you try the two originally proposed solutions? Were there any issues?

[Oleksii]

@nmattia can you please point me to this solutions? I remember we discussed that we need to use optional field instead of SeedPhraseProtected proposal but without details. Maybe I missed something?

[nmattia]

@nmattia

Special care has to be taken in the canister since adding a bit of information to a phrase (protected: true/false) will grow the anchor record. Since each anchor is serialized/deserialized as candid individually, and since candid supports optional fields, the first approach will be to add an optional field (“protected”) to recovery phrases. This means that deserializing existing, non-protected phrases will Just Work™. If this doesn’t work, a new variant (δ,ο,) may be added to KeyType ; however we try to avoid this as this isn’t what KeyType is for, and it may be used in the future (if we enable attestation).

There you go! AFAIR we discussed having either an optional yes/no (see also @paulyoung 's good point here) or an extra variant for KeyType if the first solution doesn’t work.

[Oleksii]

Got it. Thanks @nmattia .

[Oleksii]

Team,

Let’s start with an alignment:

• The problem is that an attacker can add or remove any and all devices from a compromised anchor
• @dostro, @Litzi, and myself from the Internet Identity Labs team and @lastmjs from the Demergent Labs team collaborated on solutions and decided to propose we start with a fix for the most phishable attack vector, the recovery phrase
• The reason we chose to start specifically with the recovery phrase is because we believe this is the most harmful attack surface, given that it’s the most phishable, and that incremental iteration will generally help make faster and more informed decisions for future improvements

The worst case scenario for a compromised anchor is that the final recovery method, typically the recovery phrase, is removed by an attacker, leaving no opportunity for the anchor owner to recover.

Therefore we propose 3 branches for your review, each implementing a different approach to support a method of protecting the recovery phrase from removal by anyone that doesn’t know it:

1. GitHub PR to Add new KeyType
2. GitHub PR for an Optional ProtectionType in DeviceData type
3. (Our recommendation) GitHub PR for Optional list of Tags in DeviceData type

The flow for each is generally the same:

• In the remove method, read information about the device being removed
• If the device is a protected recovery phrase, make sure the recovery phrase the user submitted matches
• Trap if no match and return without removing the recovery phrase

One important note: Fixing this attack vector still leaves one open that an attacker could add a protected recovery phrase from a different compromised device, even if the anchor already has a protected recovery phrase. We could restrict only 1 protected recovery phrase per anchor in this fix if you all think we should.

1. Add new KeyType

The KeyType enum currently has the following 4 options:

1. Unknown
2. Platform
3. CrossPlatform
4. SeedPhrase

We propose in this option to add a 5th option for SeedPhraseProtected to differentiate between protected and unprotected recovery phrases.

Strengths

• A clean implementation with minimal complexity
• Minimal memory management overhead

Weaknesses

• This does add another KeyType that needs management down the line, should KeyType undergo a migration (though we’re not aware of any such plans)

Opportunities

• None besides the immediate feature implementation

Threats

• None that we’ve identified

2. Optional ProtectionType in DeviceData type

@paulyoung suggested adding a new enum that we implemented as an optional variable to the DeviceData type that could store information about this key being a protected recovery phrase.

Strengths

• Simple rollback

Weaknesses

• The DeviceData type will include an additional optional field, which increases state by more than necessary given that only a fraction of devices will need it

Opportunities

• Possibility to add additional ProtectionTypes in the future

Threats

• None that we’ve identified

3. (Our recommendation) Optional list of Tags in DeviceData type

Iterating on the 2nd option, the field we add to DeviceData could be a list of Tags as metadata for the device. Not only could it be used to protect the recovery phrase, but it could be used to protect any device, set different administrative permissions per device, and generally add substantial flexibility

Strengths

• Simple rollback
• Generalized, reusable solution to make devices more flexible

Weaknesses

• Such a generalized solution might influence future feature implementations to leverage this rather than a potentially more appropriate, scaleable, harder-to-implement solution

Opportunities

• As @frederikrothenberger reminded us about @timo’s previous suggestion, this is one way to set different administrative permissions per device so that only devices with the Admin Tag, for example, are able to add/remove devices, Superadmin to add/remove recovery phrases, TxApprover for devices capable of approving transactions, etc, etc

Threats

• Currently, we’re scoping the reading of the Protected Tag only on removal of a seed phrase because attackers might be able to add their own protected devices, and until there’s a UI for administrative control, we should be more cautious with this feature.

The threat for option 3 requires a more thoughtful approach to the UI in the medium term so that users can configure which devices can add other high-permission devices, but unless Dfinity has medium-term plans to extend device functionality in these ways we believe this enables a highly flexible design space for future feature implementations at low cost.

[anonymous]

I’m a big fan of option 3.

@Oleksii

As @frederikrothenberger reminded us about @timo’s previous suggestion, this is one way to set different administrative permissions per device so that only devices with the Admin Tag, for example, are able to add/remove devices, Superadmin to add/remove recovery phrases, TxApprover for devices capable of approving transactions, etc, etc

I was recently thinking of how cool it would be to share my II with someone, but I wouldn’t want them to be able to approve transactions. This functionality would be amazing

[paulyoung]

@Oleksii

We could restrict only 1 protected recovery phrase per anchor in this fix if you all think we should.

This seems important to do, otherwise an attacker can add a protected recovery phrase that can never be removed by the owner.

That could still happen to people whose devices are compromised who have not yet created a recovery phrase, but if there’s a limit of 1 then at least everyone could proactively prevent this by creating one before a potential attacker does.

[dostro]

I would also vote for introducing this patch