Recovering from Device Loss

[equalsJeffH]

[submitting on behalf of @leshi & @arnar and their collaborator Alex Takakuwa alextaka@uw.edu]

https://lists.w3.org/Archives/Public/public-webauthn/2018May/0464.html:
Subject: Recovering from Device Loss in WebAuthn
From: Alex Takakuwa alextaka@uw.edu
To: public-webauthn@w3.org

In April, we sent an email introducing some potential solutions to the
problem of “Recovering from Device Loss in WebAuthn”.

As you all know, in the current WebAuthn specifications, users face a
potentially onerous process when migrating to new devices either because of
device loss or just a device upgrade. We view this as a problem that can be
solved while retaining all the security guarantees of the existing WebAuthn
scheme and improving the usability of WebAuthn drastically all without
changing the API. We would like to encourage members of the WebAuthn
mailing lists to join us in developing proposals that can be accepted into
the WebAuthn specifications to solve the problem of recovery from device
loss and device upgrade.

Our preliminary proposals are listed here:
Recovering from lost devices in WebAuthn
https://docs.google.com/document/d/1tRLbXYLb9Z65QqhOX7v9D-aq_RUODyn5oALpCXj46K8/edit?usp=sharing

I look forward to hearing your feedback!

---

SEE ALSO:
[updated 27-Oct-2018]

See especially the recent comments below regarding the notes from the "Device loss summit" and a newly-proposed recovery approach, beginning here: #931 (comment)

Recovering from Device Loss in WebAuthn (Tue, 3 Apr 2018)
https://lists.w3.org/Archives/Public/public-webauthn/2018Apr/0009.html

The Transfer Access Protocol - Moving to New Authenticators in the FIDO Ecosystem
Technical Report UW-CSE-17-06-01
https://www.cs.washington.edu/tr/2017/06/UW-CSE-17-06-01.pdf

Secure authentication key sharing between mobile devices based on owner identity
https://ieeexplore.ieee.org/abstract/document/8311436/

Recovering from Device Loss in WebAuthn/FIDO2 [thread on fido-dev@]
https://groups.google.com/a/fidoalliance.org/forum/#!msg/fido-dev/Eh3cLPjuWlo/PlMGwP9mCAAJ;context-place=forum/fido-dev

Issue #1106 "Is there a community for webauthn implementation discussion?"
[short answer: yes, fido-dev@]
[NOTE: this issue #1106 also poses questions re "key loss" aka "device loss" aka "account recovery"]

Issue #334 "Add clearer definition of API use cases to the spec"
[touches upon guiding user such that recovery flows are available]

[alextaka]

Thanks for opening this Issue Jeff!

To help get everyone moving in the same direction and drive the conversation forward, UW is hosting a day/half-day summit on the topic of recovery from device loss on August 3 at the Paul Allen Center for Computer Science. All are welcome to attend!

https://doodle.com/poll/yb5rqiadhaksk5um

[equalsJeffH]

see also issue #931 wrt providing for RP signalling that it is OK for key material associated with platform authenticators to be "sync'd" across devices. For some definition of "sync'd", eg, see Recovering from lost devices in WebAuthn)

[suedadam]

I'm not familiar with the webauthn spec yet; however, in terms of sharing data, wouldn't you always risk the same issue with an accidental logging? (@ptoomey3 noted it as a possibility in issue #969 ).

In hope to start some sort of a discussion:

I think that the Key Copy method is my favorite as it doesn't relying on any non-trusted devices as you can share the key with other devices in your possession.

One thing I am confused about is the tradeoff talking about the RP losing hardware attestation, could you share some material about WebAuthn's hardware attestation capabilities?
I would think that any reliance on hardware specific identification would be a generally bad idea as that would complicate the process of moving devices where in a normal key management system, since it is completely software oriented, you can move keys around to different devices without any issues.

[jans23]

@suedadam By specification, each FIDO U2F devices contains an attestation key which proves its vendor. I believe that this correlates to vendors' promise that device private key can't be stolen. In addition devices contain a counter which would not be synchronized when copying keys initially.

[equalsJeffH]

Device Loss Summit 20-Aug-2018 Summary: https://lists.w3.org/Archives/Public/public-webauthn/2018Sep/att-0012/Summit_Summary.pdf

[emlun]

Here's the draft of our recovery extension idea presented at W3C TPAC today. I apologize for omitting the cryptograpy details until we've had them properly vetted.

Pseudo-spec draft: https://gist.github.com/emlun/74a4d8bf53fd760a5c5408b418875e2b
Slides from today's presentation: https://docs.google.com/presentation/d/1gjrgrh0dURyxj4o-yfzrXt6f220XbUghjSo9vDb6O60

[alextaka]

Cool stuff guys! Can't wait to see the final vetted math.

One issue I also see that wasn't explicitly noted is that the user will have to use device B will have to run a recovery procedure with every RP. We may want to study this, it could turn out to be completely acceptable to users.

[watahani]

@emlun
Thanks for your cool slide.

I'm not sure what is the “public key seed” in your slide. It seems that main key need to store or generate "recovery credential id" which equivalent to WebAuthn Credential ID.

extensions: {
  “recovery”: {
    “action”: “generate”
  }
}

extensionOutputs: { 
  “recovery”: {
    “action”: “generate”,
    “state”: 3,
    “creds”: [{
      “id”: “ABCD…”, //equivalent to WebAuthn credentialId
      “publicKey”: “AAAA…”
    }]
  }
}

How to be generated creds.id and creds.publicKey from "public key seed" in main authenticator? or just
be stored creds.id and creds.publicKey from recovery auhenticator?

[emlun]

@watahani We don't want to publish the crypto details just yet - I don't think we'll keep it secret, but we also don't want to risk people starting to use it before we've had it vetted by external cryptography experts.

You're right that the id in that response is similar to a WebAuthn credential ID. The public key would be derived from the "public key seed" and a random nonce, and the id would be derived from the public key in such a way that the recovery authenticator can reconstruct the private key from the id (again, we're not publishing the details just yet). The main authenticator doesn't need to store anything except for the "public key seed" - both the id and the publicKey would be stored by the Relying Party.

[equalsJeffH]

I'm thinking we ought to move this to a later milestone, eg L2-WD-02 or later...

[emlun]

Today at the face-to-face meeting in Fukuoka we presented our recovery extension in full, including all details of the key agreement scheme. The extension draft is published here: https://github.com/Yubico/webauthn-recovery-extension

This is NOT IMPLEMENTATION READY. Please keep in mind that the cryptographic details have not yet been extensively reviewed, so approach with caution until we have official approval from reputable cryptanalysts.

[emlun]

Today we also found some prior work proposing the same key agreement scheme: the ISAP protocol described in this article, which references this whitepaper. We haven't yet found any proof or analysis of its security, however. The white paper proposes proofs of the security of a larger protocol built on top, but I don't think one can automatically assume that they imply that the key agreement scheme in isolation must also be secure.

[galadran]

Hi @emlun,

I took a quick look over the extension draft and have some feedback on the crypto design which is below.

Best,
Dennis

Missing Requirements

It should be specified that S must be kept secret, otherwise collaborating RPs can forge an otherwise valid credential id and test whether a user holds the corresponding private key, which uniquely identifies the user. This is a weak guessing attack violating unlinkability.

Currently, Bob / the backup device is required to verify an alleged E is not invalid according to SEC 1, section 2.3.4. This procedure still allows for the E to be the point at infinity, which is invariant under scalar multiplication. This allows for a powerful attack on unlinkability:

A malicious RP can forge a credential id with E equal to the point at infinity. The resulting shared secret is also the point at infinity regardless of S and consequently the RP can forge the MAC value and derive the credential key. The RP then prompts the user to begin the recovery procedure. Bob / the Backup token will derive P and transmit P and a signature to the RP (P is sent as attested credential data). The RP can then subtract cred_key * G from P to learn S which uniquely identifies the user.

Consequently, devices must ensure E is not the point at infinity (or any low order point in a non-prime order group).

Minor Quibbles:

Why use each half of HKDF(e * S) as opposed to two distinct invocations of HKDF with different labels? Wouldn't the latter be cleaner?

Why add cred_key * G to S? What purpose does it serve over using cred_key * G directly?

[emlun]

S must be kept secret, otherwise collaborating RPs can forge an otherwise valid credential id and test whether a user holds the corresponding private key, which uniquely identifies the user. This is a weak guessing attack violating unlinkability.

Aha, there's the attack enabled by knowing S! We've known that anyone who knows S can create a valid credential ID that the backup authenticator would accept and use, but we hadn't found a way to leverage that into an attack. Thanks!

Might it make sense, then, to include an EDH key agreement in the import/export exchange, and encrypt S with the agreed ephemeral key? It wouldn't prevent a malicious client from active-MitMing the exchange and learning S (since we can't reasonably authenticate DH public keys across different authenticator vendors), but at least there would be forward secrecy and S wouldn't be in cleartext in client memory if the client is benign.

Currently, Bob / the backup device is required to verify an alleged E is not invalid according to SEC 1, section 2.3.4. This procedure still allows for the E to be the point at infinity, which is invariant under scalar multiplication. This allows for a powerful attack on unlinkability:

[...] The RP can then subtract cred_key * G from P to learn S which uniquely identifies the user.

Consequently, devices must ensure E is not the point at infinity (or any low order point in a non-prime order group).

Good catch, we'll add that. This also has me thinking it might make sense to include the rpIdHash in the HKDF info parameter (in which case we could probably drop rpIdHash from the MAC)?

Why use each half of HKDF(e * S) as opposed to two distinct invocations of HKDF with different labels? Wouldn't the latter be cleaner?

Yeah, that might be cleaner. It also shouldn't make a difference in terms of performance cost as you'd need to run one HKDF-Extract and two HMAC-Hash in either case.

Why add cred_key * G to S? What purpose does it serve over using cred_key * G directly?

If you don't, then p = credKey and the main authenticator therefore knows the backup credential private key. With P = cred_key * G + S, you need to know s to compute p = cred_key + s, so only the backup authenticator is able to exercise its backup credentials.

@dainnilsson @ve7jtb thoughts on this?

[galadran]

Might it make sense, then, to include an EDH key agreement in the import/export exchange, and encrypt S with the agreed ephemeral key? It wouldn't prevent a malicious client from active-MitMing the exchange and learning S (since we can't reasonably authenticate DH public keys across different authenticator vendors), but at least there would be forward secrecy and S wouldn't be in cleartext in client memory if the client is benign.

I am not sure how much benefit there is to protecting S in transit. Either the client is not malicious in which case S will not be recorded, or the client is malicious and can intercept (or even replace) the S value. However, it might provide some protection against faulty client implementations.

This also has me thinking it might make sense to include the rpIdHash in the HKDF info parameter (in which case we could probably drop rpIdHash from the MAC)?

I don't see much difference here, but more key separation is always nice.

Why add cred_key * G to S? What purpose does it serve over using cred_key * G directly?

If you don't, then p = credKey and the main authenticator therefore knows the backup credential private key. With P = cred_key * G + S, you need to know s to compute p = cred_key + s, so only the backup authenticator is able to exercise its backup credentials.

There's two cases to be distinguished here - at the point of backup credential registration - is the main authenticator malicious or not? If the main authenticator is malicious, the RP cannot detect it and consequently the main authenticator can provide a backup key of its own construction (to which it knows the private key). If the main authenticator is not malicious, it will destroy its private key e, which means if it is compromised later, it cannot compute cred_key. So in the first case, adding S cannot be enforced and in the latter case, adding S has no impact.

[dainnilsson]

We should clarify the consequence of a bad actor getting access to S. It's clear that anyone with access to S can forge a valid recovery credential, which potentially could be used to break the unlinkability aspect. One mitigating factor here would be if the client (browsers) UX is clear about distinguishing a call to create() with action: "recover" from the standard flow, which I think would be good practice purely for usability reasons as well.

On ensuring E != point at infinity I fully agree, the requirement on enforcing this should be added.

Regarding the use of HKDF, I'm not sure I see how invoking it twice to derive 2 keys is more clean than just doing so once. It's my understanding that deriving multiple keys is one of the stated purposes of HKDF (from RFC5869):

HKDF follows the "extract-then-expand" paradigm, where the KDF
logically consists of two modules.  The first stage takes the input
keying material and "extracts" from it a fixed-length pseudorandom
key K.  The second stage "expands" the key K into several additional
pseudorandom keys (the output of the KDF).

Am I missing some reason for why separate invocations of HKDF would be beneficial?

On the addition of S, I would consider an alternative take on the non-malicious main authenticator:
What if a flaw in either the destruction or the generation of e is found in the main authenticator (through compromise or other means)?
I'd argue that if there is no need for the main authenticator to ever possess the private key, it would be desirable for it not to ever be exposed to it.

[galadran]

Am I missing some reason for why separate invocations of HKDF would be beneficial?

My thinking here was implementation rather than any cryptographic properties.

cred_key = HKDF(...)
mac_key = HKDF(...)

vs

key_mat = HKDF(...)
cred_key = key_mat[..]
mac_key = key_mat[..]

But as I said, its a very minor quibble!

On the addition of S, I would consider an alternative take on the non-malicious main authenticator: What if a flaw in either the destruction or the generation of e is found in the main authenticator (through compromise or other means)? I'd argue that if there is no need for the main authenticator to ever possess the private key, it would be desirable for it not to ever be exposed to it.

Okay, I see the benefit here, but it only applies if you have a main authenticator with a bad RNG, the adversary learns S and the RP has already rejected the main authenticator. Then adding S does prevent the attacker's use of the honestly registered recovery credential.

Perhaps its worth adding in some security guidance for RPs in event they believe an authenticator (or an entire class of them) have been compromised. They must obviously reject main or recovery credentials if they have reason to believe the authenticator owning them is compromised. Additionally, if they reject a main authenticator, they should also consider rejecting any recent update of the recovery credentials, as these could have been forged by the attacker / main authenticator as a backdoor in the event the main authenticator is revoked.

[emlun]

Hi everyone, I'm pleased to report there's been some more progress on this.

Yubico and Mozilla have been collaborating with researchers from Surrey Centre for Cyber Security, at the University of Surrey, who have now formally modeled and proved security of this key generation scheme - meaning that the backup private keys (p = cred_key + s) can indeed be derived only if one knows the backup seed private key (s); and that the backup public keys (P = cred_key * G + S) remain unlinkable to ensure privacy. The next phase will be to investigate whether signatures produced by these backup private keys remain unforgeable. The researchers intend to publish their work after that is done.

[equalsJeffH]

on 2020-01-29 call: @emlun reported on @emlun's #931 (comment)

[jlgarnier]

Good news and good job! Looking forward to reading the final proceedings!

[emlun]

The research paper has now been accepted to the ACM CCS conference! The eprint is published here for public review: https://eprint.iacr.org/2020/1004

[didcx]

My comments is going to be strictly focused on platform authenticators(esp. fingerprint scanners) not the unknowns(meaning the rest).
That's what my current project will heavily depend on.
I think there are many ways to solve the registration and authentication problems via the net or web. And one of the approach being used currently is one of the uncalled solutions on my part. I think to solve this problem one needs to at least group access to platform authenticators(esp.fingerprint scanners) into three parts.

1. System Access.
2. Local Access(i.e local Apps without internet integration) and
3. Web Access(Apps with internet access(mostly heavily dependant on the Internet)).
   I think and known that if things a viewed this way, then it will surely be less complicated to solve than the current state of confusions in the current WebAuth.

[eldanb]

A minor comment (added in the original repo but copying here too as that doesn't seem as active):

Hi,

I believe that in "Step 3", stage 3,

"
Let cred_key = KDF1(ECDH(e, S)) and mac_key = KDF2(ECDH(e, S)).
"

Should actually be

"
Let cred_key = KDF1(ECDH(s, E)) and mac_key = KDF2(ECDH(s, E)).
"

Correct?

[emlun]

Thanks, that's fixed now. Looks like PR #1425 does not have the same typo.

[MeydanOzeri]

It seems that all recovery options depend on having access to an authenticator, weather it's a roaming one or a platform one.
What is the approach for dealing with a user that lost access to all of it's authenticators ?
He will be locked out forever ?

I have some idea that I'm playing with in my head to try and solve this scenario, basically it relies upon asymmetric encryption signatures.

Upon registration the clients browser creates a public private key pair, it shows the user the private key in the form of a seed phrase (same as crypto wallets) and tells the user to store it safely, after the user is confirming that he stored it, the public key is saved by the RP for a future recovery scenario, and the private key is deleted.

When the user triggers the recovery flow, the RP will send a randomly generated message to the client, the client will be prompted to provide his seed phrase (private key) and the clients browser will use it to sign the message provided by the RP, then it will send the signed message to the RP where it will be verified by the public key associated with the account, if the signature is valid we can be certain that the correct and only private key was used.

After that the user will get the ability to perform a new attestation and create a new credential, when he is done all the old credentials will be deleted, and he will be shown a new recovery seed phrase for future recovery scenarios. (making it a one time use recovery phrase)

I find that this approach is a safe option since it is resistant to RP database breaches as acquiring the public key will not help the attacker, the private key is generated on the client side and doesn't leave it, so it is resistant to man in the middle attacks.
Brute forcing/guessing attacks are irrelevant since there are to many different possibilities for a private key when using a secure asymmetric algorithm.

The only security issues I can come up with this approach is that it is not resistant to phishing attacks/social engineering attacks + the user will need to store it safely otherwise it is open to theft attacks.

I'm still trying to find a way to invalidate phishing/social engineering attacks with this approach. so far I didn't find a way.

Looking forward for your feedbacks on this idea.

[dagnelies]

Just to add my grain of salt. I think there are plenty of ways to recover accounts upon device loss.

• associate the account to an email/phone and simply send a link to register a new device on demand
• provide a link or QR code to register a new device that the user can store somewhere safe
• use recovery passwords / phrase
• register multiple devices
• video identification / confirmation

I even wrote a small article about it https://dev.to/dagnelies/webauthn-what-if-i-loose-my-device-1lbh

I don't think there is a need to embed some "backup" functionality as part of the protocol itself. I would even be worried if the private key would be shared in any way, even if it's called a backup. It would be like sharing an unencrypted password. One strong security aspect of webauthn is the certainity that this private key is a secret tied to the authenticator device and that there is no way to "extract it". I hope it stays that way. 😉

[Blobonat]

@dagnelies

One strong security aspect of webauthn is the certainity that this private key is a secret tied to the authenticator device and that there is no way to "extract it".

The proposal by @emlun does not violate that principle. There is no need for the authenticators to export or share secrets.

[Firstyear]

This sounds like a problem for the RP to think about and implement their own work flows, not for the devices to have to share secrets which weakens the whole system.

The same way we have password-reset emails, you need to think about the same for when someone loses a webauthn device.

[lucasgcbkhomp]

This sounds like a problem for the RP to think about and implement their own work flows, not for the devices to have to share secrets which weakens the whole system.

The same way we have password-reset emails, you need to think about the same for when someone loses a webauthn device.

Indeed. This has always been an issue with 2FA in general which is why you have users who do not wish to use it. How your system deals with ways to circumvent 2FA implosion is not 2FA standard, it's business logic.

Therefore, from what I gather, Webauthn having inbuilt recovery is... beyond its scope?

If you'd like to register a new public key for the Webauthn pair (your new device), then that's business logic of your service. You can have both webauthn and SSO to access the service and perform modifications to your settings. Or you can just have webauthn and watch as users eventually brick themselves out of your system.

[boppreh]

@dagnelies

Unfortunately all the methods you listed either sacrifice privacy, or require accessing the backup location/device during sign up, which is both dangerous and adds friction. At minimum, I think a good recovery method (1) should reveal no private information; (2) can be stored somewhere secure like in a safe deposit box or with trusted friend; and (3) still allows me to create new accounts without opening the safe or asking the friend every time.

This can be done, but has to be supported by the protocol. I'd rather disable the recovery method for my extra-sensitive accounts, than have no good recovery method on any account.

[dagnelies]

@boppreh I find your statements kind of confusing...

Unfortunately all the methods you listed either sacrifice privacy

You mean by providing an email/phone number to recover the account? Well, yeah, it's the convenient way to send you a recovery link. But all other alternative recovery options do not require any information.

or require accessing the backup location/device during sign up

Well, not necessarily. You could add a second/third device to your account anytime, or print a QR code on a sheet of paper to put in your safe anytime. It's not necessarily upon registration.

which is both dangerous

What is dangerous exactly?

At minimum, I think a good recovery method (1) should reveal no private information; (2) can be stored somewhere secure like in a safe deposit box or with trusted friend;

Then you're the perfect candidate to print a QR code on a sheet of paper, put it in your friend's safe 🤣

(3) still allows me to create new accounts without opening the safe or asking the friend every time.

Well, you can always do that. Why would you need anything to "create a new account" ?!?

This can be done, but has to be supported by the protocol. I'd rather disable the recovery method for my extra-sensitive accounts, than have no good recovery method on any account.

Well, you are in luck (🙄 ?), google, microsoft and apple do not only sync passwords in the cloud now, but also the private keys created with webauthn, that they dubbed "passkeys" ...there you go with your built-in recovery method, the big 3 simply have a copy of your keys. Whether you find this great or worrysome is up to you.

Viele Grüße

[boppreh]

@dagnelies Sorry for the confusion, let me try to reword it. I think recoverable accounts should be the default, from the moment the account is created, and that default features should not reveal any private information like email or phone number.

I also think that some of the most secure storage methods are naturally hard to access, like house safes, bank deposit boxes, and secret shares. By forcing users to access that storage to create each account (like printing a new QR code and putting in a safe), users will either:

a. opt out of recoverable accounts;
b. delay backing up their keys;
c. or prefer riskier recovery mechanisms, like carrying the backup device with them.

All of those options increase the chance of account loss. That's the dangerous part.

And I agree with your sarcastic assessment that cloud sync is less desirable, which is why I like the original proposal here.

[dagnelies]

Well, I still think registering your smartphone and your laptop (for example) to your account sounds quite ok.

It is private, is convenient since you can login directly on each device and if you lose one you can still use the other.

I personally think the ideal way is to leave the choice to the user depending on its preference.

[MasterKale]

Closing as addressed by PR #1695.