Webauthn: Consider requiring canonical CBOR throughout

[agl]

Canonical CBOR is a distinguished subset of CBOR encodings, and is specified in the original RFC. Most CBOR implementations will produce something close to canonical CBOR most of the time but, by requiring it, implementations can avoid decoder complexity. This might be especially valuable for authenticators, as they are constrained and need to parse CBOR if they are to handle extensions.

Without this, implementations are very likely to implement an ill-defined subset of CBOR anyway (e.g. by rejecting lengths with superfluous zeros and so on) and this will result in arguments whenever something produces valid (but non-canonical) CBOR that is rejected by some existing implementations. If this discovery happens late in the development of an implementation, it can be quite costly.

Conversely, if canonical CBOR is required, a single common implementation that is strict will ensure that the whole ecosystem remains healthy and interoperable on this point.

Lastly, the ordering requirements of canonical CBOR make it easy to reject maps with duplicate keys. Although that doesn't appear to be pertinent to the current webauthn spec, it's a classic way to cause confusion between two parsers (and thus security issues) and could arise in future extensions.

[jyasskin]

Do we ever expect situations where the number of items in a structure wouldn't be known when the client or authenticator starts generating that structure, or where an integer's value might depend on something later in the output? If so, then requiring a minimum-length encoding forces extra copies of the data. See BoringSSL's DER generator for an example. It also doesn't seem to simplify the parser. BoringSSL's DER parser has extra code to check that lengths are minimal, and I don't see places that save code because of the restriction.

The other two restrictions in Canonical CBOR, that structures don't use indeterminate lengths, and that map keys are sorted, do seem like worthwhile simplifications.

[agl]

Every bit of unneeded flexibility that you can eliminate in the encoding is good, so please ban indeterminate lengths and unsorted maps if that's all you feel that you can.

Minimal lengths in a variable-length encoding do require either knowing the value before writing it or else moving after-the-fact. For a host, shifting a few bytes in L1 cache at human-interaction rates is trivial. A small device might choose to calculate the lengths beforehand. That's just the cost for the smaller size of variable-length integers.

However, encoding strictness is not purely a sliding scale: a canonical encoding is qualitatively different because it gives a bijection between messages and encodings. This feature makes testing more effective. If there's only a single encoding for a given structure of message, and you've tested that encoding, then your implementation works. In contrast, consider a world with non-canonical length encodings:

One embedded implementation is running on a 16-bit processor and decides to use a uint16 to hold lengths because no message that it cares about will exceed 64KiB. Another implementation decides to simplify serialisation by writing all lengths as uint32's, padding with zeros as needed. Both will likely work with common host implementations that are "liberal in what they accept but conservative in what they send" but fail when talking to each other.

A canonical encoding avoids these expensive interop issues.

BoringSSL is strict when parsing (although it's DER, not CBOR) in order to improve the ecosystem. We have caught a lot of those sorts of issues early, while they are still cheap to fix. That's what I meant when I said “a single common implementation that is strict will ensure that the whole ecosystem remains healthy and interoperable”. (Our GREASE efforts have a similar motivation.)

Strictness in the parser can also save lots or complexity and issues elsewhere. For example, a failure to be strict about DER lengths in NSS resulted in a complete break of signature validation, and thus a complete break of TLS, and lived in the code for many years. Strictness in the DER parser has also allowed us to remove workarounds elsewhere for cases where bugs had crept into the ecosystem. The payoff from a few checks at the bottom has been significant.

[jovasco]

I would very much like non-cannonical CBOR be supported from authenticator to client.

In specific:

• always use shortest encoding: for example, when generating the authenticator data, it is much easier to reserve 2 bytes for the length and go back and correct them than precalculating the length, especially when your device supports extensions.
• indefinite encoding: again, it is much easier to generate an indefinite encoding tag for arrays and maps and terminate it accordingly. There are also some very interesting uses for indefinite encoding for byte strings.

I agree it would be nice if this was required towards the authenticator.

[jyasskin]

@jovasco Is there a situation where the authenticator would not know how many extensions it's going to send before starting to encode the list of them? Recall that CBOR's length prefix counts the number of items, unlike DER's which needs the number of bytes.

[jovasco]

@jyasskin Probably not. At this point, I see no need to use indefinite maps and arrays but this might easily change in future specs. I consider indefinite length strings essential (from authenticator to client).

As for sorted maps... this type of optimization is only going to matter for really small or slow processors. Requiring this from the client is one thing, requiring the authenticator to enforce this would actually add complexity to more a generic parser (who suddenly would need to care about order).

As for 16 bit processors, I have no problem just banning additional types 26 and 27 (4 and 8 byte length fields) for all major types in all directions.

[jyasskin]

If you know the number of elements in a list ahead of time, it's really easy to produce a min-length encoding of the length.

What's the use case for unknown-length byte- and utf8-strings sent from the authenticator?

I don't think we'd specify that authenticators MUST or even SHOULD check that the map is sorted, but rather that they MAY.

[agl]

For small chips, I would imagine that the encoding would be generated directly by code and, as such, maps would be sorted by virtue of the code blocks that emit each element being ordered.

I agree that checking different requirements of the canonical form should be a MAY for implementations as a few large implementations doing the checks is sufficient to keep the ecosystem on track.

I don't believe that these messages will be so large that an implementation will not be able to calculate the size of strings beforehand.

[jovasco]

All of this is, for me, about generating messages in-place. I do not want to have to generate the extension data a buffer and later copy it to the authenticator data buffer and then copy that into the reply buffer. Resources are not abundant in an embedded implementation.

Going through all the extension and buffer generation logic to calculate the size to then go back and do it all again when generating this data just to avoid a possible single extra 0 byte in the length just seems too expensive.

That map fields will always be in the same order for a single implementation is very likely, yes. However, that does not mean an alphabetical order is obvious.

Indefinite length strings are a convenient way to reserve space in the reply when you do yet know the length of that field. A good example is the signature field which is somewhere between 70-73 bytes, depending on the signature value.

Why you think this canonical CBOR from authenticator to platform is so important?

[agl]

ASN.1 ECDSA signatures are a common case of having to serialise something in a format with minimum-sized lengths. (There is BER, with indefinite lengths, but DER, without them, utterly dominates.)

ECDSA hardware often returns signatures in a simple format where r and s are just 32-byte (for P-256), big-endian numbers. Thus an embedded system writing out an ASN.1 signature needs to find the number of leading zeros of these numbers, see whether the resulting MSB is set, calculate the lengths, write them out, maybe write a padding zero byte, write out a subslice of the r value, do another length and padding for s, and then write out a subslice of the s value.

It would save a little code in the short-term if the values didn't have to be minimal, sure.

However, complexity in formats is very costly to an ecosystem over time. Requiring canonical CBOR (and having a few, large implementations enforce it, in order to keep the ecosystem honest) means that there's only one serialisation of a given message. Thus interop testing and unit-tests are dramatically more effective. And that sort of testing is realistically all that we're going to get in an ecosystem as large and diverse as we hope security keys will be.

Otherwise, in time, we'll see interop issues where implementation A is emitting non-standard, but valid, CBOR that implementation B just doesn't handle correctly. These issues might not be found until devices are out in the world, at which point they are very expensive to fix.

In TLS, which has a comparatively simple serialization (all fixed-size length prefixes), several extension mechanisms have been abandoned because enough implementations screwed them up that they're non-functional in practice. Implementations have been found to be sensitive to the order of supposedly unordered maps, or to have exploitable bugs in the face of duplicate entries. (A canonical order from the start would have been great. It also makes detecting and rejecting duplicate entries easy.)

At this point, TLS implementations are injecting random extensions in real-world usage to try and ensure that the major extension point remains useful for the future.

I believe the costs over time of extra complexity in a serialisation format will completely dwarf the costs of having to write a little more code to implement. (Unless your ecosystem is a monoculture, in which case webauthn will have failed anyway.)

[jovasco]

I believe the complexity of the protocol is because of _what_ we serialize, not _how_ we serialize it.

That said, I am going to withdraw my objection to canonical cbor. I will solve in-place generation in a different way. Indefinite encoding of strings would allow things like fragmenting map keys and that is just plain expensive and unhelpful. Adding our own set of restrictions will just create confusion, as will different requirements in different directions.

However, if we are adding this, I believe we must require every implementation to enforce it. If we don't, compatibility between two implementations might become inconsistent.

As an aside, I believe the WebAuthn ecosystem will be more of an oligarchy. There will be only a handful platform implementations and their implementations will become the defacto standard, bugs included. Their quality and adherence to the spec will be a main factor in the success of this protocol.

[selfissued]

As has been discussed in the corresponding FIDO 2.0 CTAP issue https://github.com/fido-alliance/fido-2-specs/issues/200, the recipient can't assume that the content is canonical CBOR even if it's specified that it must be. That imposes additional validation steps that the authenticator must perform that otherwise would not be necessary. This seems like a "false savings" to me, as many of the canonicalization features add no value for this use case.

[jovasco]

@selfissued Validating canonical CBOR and handling non-canonical CBOR are of a different order altogether.

For example, when comparing map keys in canonical CBOR, I can rely on them being a single, fixed length string (ie, use strncmp straight form the input buffer). Validating that the tag is fixed length is essentially free because I have to parse the tag and check the length anyway. If I have to handle normal CBOR, I would have to extract the string into a separate buffer because they are allowed to be indefinite length strings with multiple parts. (key "alg" can be 63616C67, 7F62616C6167FF, 7F6161616C6167FF,... ).

Although it would be 15 minutes of fun to write a strncmp routine that can handle indefinite length CBOR strings straight from the input buffer, the complexity is not desirable.

As for testing, if you want to test for normal cbor, you would need to test every field in both fixed and indefinite length versions, preferably with a few different segmentations.

[selfissued]

Thinking about the discussion of Canonical CBOR that happened on the FIDO 2 call today, there seems to be enough support for it that I'm willing to drop my objection. As a programmer, I understand the argument that you can then validate maps using a constant-space data structure, rather than space that's of the order of the size of the map. It also makes it easier to detect and reject duplicate keys.

In the end, I think there are costs either way we go on this. But I am sympathetic to Adam Langley's arguments that we want to do what we can to facilitate interoperation as the ecosystem develops.

[jovasco]

@selfissued Glad to hear it, Mike.

It even allows you to detect and reject duplicate keys you do not expect, understand or care about with the same order check. Although some believe you don't have to care about what you do not understand, a duplicate map key is a programming error that should be caught as early as possible for a clean ecosystem.

[agl]

I did some more testing with existing FIDO U2F tokens over the weekend and found two (with completely separate firmware) that got into such a bad state after processing an invalid key handle that they needed a power cycle to get back to normal operation.

No amount of care in a specification can address issues like that, but it does suggest that we can expect a very low level of testing on these devices, which will then be out in the world and very hard to fix.

Thus I expect that a "required" subset of CBOR will appear even if not intended: it'll be roughly whatever major implementations emit, because going outside of that will hit various bugs. As an example, TCP options have a very simple tag/value format but, if you don't send some of them in the same order as Windows, then your packets will get dropped by a small (but painful) fraction of networking hardware.

[nadalin]

@selfissued Need to point to the CTAP for Canonical CBOR definition

[emlun]

@selfissued CTAP spec: https://fidoalliance.org/specs/fido-v2.0-rd-20170927/fido-client-to-authenticator-protocol-v2.0-rd-20170927.html

[equalsJeffH]

note @ttaubert's https://github.com/w3c/webauthn/issues/543#issuecomment-349944903 wrt CTAP2's CBOR map key sorting order -- it is not the same as canonical CBOR. it's clearly stated in the CTAP2 spec so if we can address this issue by simply citing CTAP2 message encoding, then we do not have to do anything special wrt the map key sorting order it would seem.