Webauthn: Recovering from Device Loss

[equalsJeffH]

[submitting on behalf of @leshi & @arnar and their collaborator Alex Takakuwa [e-mail]]

https://lists.w3.org/Archives/Public/public-webauthn/2018May/0464.html:
Subject: Recovering from Device Loss in WebAuthn
From: Alex Takakuwa [e-mail]
To: [email protected]

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: https://github.com/w3c/webauthn/issues/931#issuecomment-431781149

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@](https://groups.google.com/a/fidoalliance.org/forum/#!forum/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 https://github.com/w3c/webauthn/issues/931#issuecomment-579934579

[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.