Credential ID uniqueness expectations are inconsistent/vague

[emlun]

As pointed out in #558, the requirements on the uniqueness of the credential ID are not completely clear.

§4.1. PublicKeyCredential Interface reads:

[[identifier]]
[...] This identifier is used to look up credentials for use, and is therefore expected to be globally unique with high probability across all credentials of the same type, across all authenticators. This API does not constrain the format or length of this identifier, except that it must be sufficient for the platform to uniquely select a key. [...]

§4.2.1 Information about Public Key Credential (interface AuthenticatorAttestationResponse), point attestationObject reads:

[...] [the authenticator data] contains the AAGUID, a unique credential ID, and the credential public key. [...]

§5. WebAuthn Authenticator model reads:

[...] Each public key credential has an identifier which is unique (or extremely unlikely to be duplicated) among all public key credentials. [...]

§5.2.1. The authenticatorMakeCredential operation reads:

When this operation is invoked, the authenticator must perform the following procedure:
[...]
Generate an identifier for this credential, such that this identifier is globally unique with high probability across all credentials with the same type across all authenticators.

(All emphasis added)

In summary, the uniqueness of the credential ID is specified as

• "expected to be" probably globally unique for all public key credentials
• informally required to be unique with undefined scope
• informally required to be probably globally unique
• formally required to be probably globally unique
• formally required only to be unique among the public key credentials available at a given time when one is needed

I suggest that

1. the requirements on credential ID uniqueness be specified only once - for example in §4.1 where it is defined or in §5.2.1 which defines how it should be generated.
2. a concrete requirement is given instead of "with a high probability" - for example "with a probability greater than 1 - 2^150" (this value (edit: 150 bits of entropy) would mean a collision chance < 1E-9 at 1E18 credential IDs generated).

[emlun]

An alternative to (2) is, as @akshayku points out in #558, to explicitly allow RPs to reject registration of an already registered credential ID.

[akshayku]

For the RP's who have implemented or are going to implement ONLY credentialID based lookup, uniqueness of the credentialID is very important. I would suggest it to be minimum of 16 bytes.

At the same time, we probably should refrain away from how its generated which allows flexibility and inventiveness for the authenticators.

[jovasco]

Actually, that's a lot more requirements than I found with a quick search, I only found the reference in 4.2.1.

@akshayu It's not possible to guarantee this as the authenticator does not have the required context and vendors do not know how other vendors generate Credential IDs. Collisions are always possible.

@emlun There is little point to that probability requirement in that form as it cannot be verified or guaranteed. I am not an expert in encryption theory so I can be wrong but since each authenticator uses a unique wrapping key, the uniqueness can be designed for the value being wrapped but this does not guarantee the resulting key handle has the same uniqueness across different authenticators. If this is correct, a vendor cannot even guarantee it for his own authenticators let alone globally. I only see one sane way to implement this: generate 150 random bits and add them to the wrapped value. It will work but is a huge waste of space.

How about a 32 byte minimum length of a value generated by a cryptographic operation?

[emlun]

I was using the 2017-08-11 WD, perhaps we had different versions?

Anyway, those are all good points; I retract suggestion (2), and then (1) isn't really necessary anymore.

However I think it's a good idea to instead explicitly allow RPs to refuse registering a duplicate credential ID. Authenticators are already required to generate a new credential ID for every call to new create(), so registration can simply be retried if the RP refuses it. It could make for a confusing user experience, but it should be extremely rare. Currently §6.1.13 technically requires the RP to accept any registration request with a good and trustworthy signature.

Allowing RPs to refuse duplicate credential IDs would also eliminate the risk of DoS attacks that register the same credential ID a billion times to break an RP that looks the user up in a table keyed with the credential ID.

[jovasco]

I agree on the explicitly allowing to refuse a duplicate.

I would still add a minimum length requirements and the requirement to use a cryptographic operation. The first one will create lots of bits, I think the second one will guarantee at least as much entropy as the encryption key (again, not a cryptography expert).

[ve7jtb]

I agree the RP SHOULD refuse a duplicate credential id. I would make that a MUST but some may only be indexing credential id by user id for starred credentials so might not be able to easily tell if it is duplicate. Collisions in UUID https://en.wikipedia.org/wiki/Universally_unique_identifier are relatively well understood. A 16 byte value is probably sufficient. If the problem is a weak random number generator more bits probably won't help. Encrypting a random value won't add to the entropy, encrypting a non random value would add entropy from the encryption key assuming that the key changes.

How best to generate it probably depends on the RNG and the quality of its sources of entropy. Being overly specific may force people to make suboptimal choices for their platform. Some may have a source of cosmic background radiation and others not so much.

The point is as random as possible and RP reject duplicates if they detect collisions.

[akshayku]

Totally agree with @ve7jtb suggestion.

[jovasco]

So 16 bytes length, fine by me. What about the entropy?

[emlun]

If RPs are recommended that they SHOULD refuse duplicate credential IDs I think it's not necessary to specify any minimum length or entropy for the credential ID. The worst that would happen is a bad user experience with badly designed authenticators, and that's on the authenticator designer if that's worth ignoring the SHOULD clause.

[Kieun]

In cases of UAF, the credential Id (called keyId) is unique in the scope of aaguid (called AAID). We cannot guarantee that the credential Ids are unique across all authenticators. For usability, the server may check duplication of credential Ids in the scope aaguid instead of looking up all records.

[emlun]

@Kieun Does UAF generate a new credential ID if registration is retried?

[Kieun]

@emlun Yes. Credential Ids are generated randomly by authenticators during registration.
Comparing to U2F and WebAuthn, in UAF the probability of credential Id duplication is low. And with tuple of AAID (aaguid), keyID (credential Id), the server can locate credential public key and user id. So, if we have AAGUID for the first factor authenticators, we can avoid credential duplication problems.
For the second factor cases such as U2F, the server already know the user id by nature before sending challenge so that the server doesn't have to look up user record with credential Id.

[christiaanbrand]

Why would it not be up to the RP to decide if they want to accept duplicate credential IDs? Just key off the user id too now. We've added it especially for you :)

[jovasco]

@christiaanbrand As long as it is explicitly allowed that's fine, the current wording does not allow it.

[emlun]

Of course the RP can already choose no accept it or not, but if you really lawyer it up on §6.1 it technically doesn't allow the RP to refuse duplicate credential IDs. :)

I see two main reasons for recommending against accepting duplicates:

• It reduces the importance of credential IDs being very unique
• It reduces the risk of RPs implementing lookups in a way vulnerable to DoS attack similar to the attack on many HTTP servers that made a splash a few years ago: A table with credential ID as key and a linked list of usernames/public keys/etc as value. An attacker could take such an implementation down by registering the same credential ID an unlimited N times and then causing the server to look it up M times at O(N) time complexity - so the attacker's O(N + M) operations would be amplified to O(N² + NM) operations on the server.

[emlun]

Actually... apparently someone already thought of this. The last paragraph of 6.1. Registering a new credential reads:

To avoid ambiguity during authentication, the Relying Party SHOULD check that each credential is registered to no more than one user. If registration is requested for a redential that is already registered to a different user, the Relying Party SHOULD fail this ceremony, or it MAY decide to accept the registration, e.g. while deleting the older registration.

How embarassing to have missed that... It might however be worthwile to make this one of the formal algorithm steps.

[AngeloKai]

This is an editorial fix. Making the step a formal part of the algorithm step can help clarify things. Assigning the issue to PR milestone.

@equalsJeffH @nadalin @YubicoDemo for tracking.

[equalsJeffH]

moving to CR milestone given @emlun's #579 (comment) and PR #709 being open.