ImperialViolet

Adam Langley's Weblog

Books, 2022 (18 Dec 2022)

As Twitter is having a thing (agl@infosec.exchange, by the way) it's nice that RSS is still ticking along. To mark that fact as we reach the end of the year, I decided to write up a list of books that I've read in the past 12 months that feel worthy of recommendation to a general audience.

Flying Blind

Boeing was once a standard-bearer for American engineering and manufacturing abilities and now it's better known for the groundings of the 737 MAX 8 and 787. This is a history of how Boeing brought McDonnell Douglas and found that it contained lethal parasites.

Electrify

Burning things produces CO2 and air pollution. Both slowly hurt people so we should stop doing it where possible. This is a data-filled book on how to get a long way towards that goal, and is an optimistic respite from some of the other books on this list.

The Splendid & The Vile

Do we really need another book about WWII? Perhaps not, but I enjoyed this one which focuses on the members of the Churchill family in the first couple of years of the war.

Transformer

Ignorant as I am about microbiology, I love Nick Lane books because they make me feel otherwise and I cross my fingers that they're actually accurate. This book is avowedly presenting a wild theory—which is probably false—but is a wonderful tour of the landscape either way.

Stuff Matters

A pop-science book, but a good one that focuses on a number of materials in the modern world. If you know anything about the topic, this is probably too light-weight. But if, like me, you know little, it's a fun introduction.

Amusing Ourselves to Death

This is a book from 1985 about the horrors of television. Its arguments carry more force when transposed to the modern internet but are also placed into a larger context because they were made 40 years ago and TV hasn't destroyed civilisation (… probably).

The Story of VaccinateCA

I'm cheating: this isn't a book, although it is quite long. As we collectively fail to deal with several slow crises, here's a tale of what failed and what succeeded in a recent short, sharp crisis. It is very California focused, and less useful to those outside of America, but I feel that it's quite important.

Art of Computer Programming, Satisfiability

This isn't “general audience”, but if you read this far perhaps neither are you. SMT solvers are volatile magic and, while this is only about SAT, it's a great introduction to the area. I would love to say that I read it in the depth that it deserves, but even skimming the text and skipping the exercises is worth a lot.

The Economist also has its books of the year list. I've only read one of them, Slouching Towards Utopia, and it didn't make my list above!

Passkeys (22 Sep 2022)

This is an opinionated, “quick-start” guide to using passkeys as a web developer. It’s hopefully broadly applicable, but one size will never fit all authentication needs and this guide ignores everything that’s optional. So take it as a worked example, but not as gospel.

It doesn't use any WebAuthn libraries, it just assumes that you have access to functions for verifying signatures. That mightn't be optimal—maybe finding a good library is better idea—but passkeys aren't so complex that it's unreasonable for people to know what's going on.

This is probably a post that'll need updating over time, making it a bad fit for a blog, so maybe I'll move it in the future. But it's here for now.

Platforms for developing with passkeys include:

Database changes

Each user will need a passkey user ID. The user ID identifies an account, but should not contain any personally identifiable information (PII). You probably already have a user ID in your system, but you should make one specifically for passkeys to more easily keep it PII-free. Create a new column in your users table and populate it with large random values for this purpose. (The following is in SQLite syntax so you’ll need to adjust for other databases.)

/* SQLite can't set a non-constant DEFAULT when altering a table, only
 * when creating it, but this is what we would like to write. */
ALTER TABLE users ADD COLUMN passkey_id blob DEFAULT(randomblob(16));

/* The CASE expression causes the function to be non-constant. */
UPDATE USERS SET passkey_id=hex(randomblob(CASE rowid WHEN 0
                                                      THEN 16
                                                      ELSE 16 END));

A user can only have a single password but can have multiple passkeys. So create a table for them:

CREATE TABLE passkeys (
  id BLOB PRIMARY KEY,
  username STRING NOT NULL,
  public_key_spki BLOB,
  backed_up BOOLEAN,
  FOREIGN KEY(username) REFERENCES users(username));

Secure contexts

Nothing in WebAuthn works outside of a secure context, so if you’re not using HTTPS, go fix that first.

Enrolling existing users

When a user signs in with a password, you might want to prompt them to create a passkey on the local device for easier sign-in next time. First, check to see if their device has a local authenticator and that the browser is going to support passkeys:

if (!window.PublicKeyCredential ||
    !(PublicKeyCredential as any).isConditionalMediationAvailable) {
  return;
}

Promise.all([
    (PublicKeyCredential as any).isConditionalMediationAvailable(),
    PublicKeyCredential
      .isUserVerifyingPlatformAuthenticatorAvailable()])
  .then((values) => {
    if (values.every(x => x === true)) {
      promptUserToCreatePlatformCredential();
    }
  })

(The snippets here are in TypeScript. It should be easy to convert them to plain Javascript if that’s what you need. You might notice several places where TypeScript’s DOM types are getting overridden because lib.dom.d.ts hasn’t caught up. I hope these cases will disappear in time.)

If the user accepts, ask the browser to create a local credential:

var createOptions : CredentialCreationOptions = {
  publicKey: {
    rp: {
      // The RP ID. This needs some thought. See comments below.
      id: SEE_BELOW,
      // This field is required to be set to something, but you can
      // ignore it.
      name: "",
    },

    user: {
      // `userIdBase64` is the user's passkey ID, from the database,
      // base64-encoded.
      id: Uint8Array.from(atob(userIdBase64), c => c.charCodeAt(0)),
      // `username` is the user's username. Whatever they would type
      // when signing in with a password.
      name: username,
      // `displayName` can be a more human name for the user, or
      // just leave it blank.
      displayName: "",
    },

    // This lists the ids of the user's existing credentials. I.e.
    //   SELECT id FROM passkeys WHERE username = ?
    // and supply the resulting list of values, base64-encoded, as
    // existingCredentialIdsBase64 here.
    excludeCredentials: existingCredentialIdsBase64.map(id => {
      return {
        type: "public-key",
        id: Uint8Array.from(atob(id), c => c.charCodeAt(0)),
      };
    }),

    // Boilerplate that advertises support for P-256 ECDSA and RSA
    // PKCS#1v1.5. Supporting these key types results in universal
    // coverage so far.
    pubKeyCredParams: [{
      type: "public-key",
      alg: -7
    }, {
      type: "public-key",
      alg: -257
    }],

    // Unused during registrations, except in some enterprise
    // deployments. But don't do this during sign-in!
    challenge: new Uint8Array([0]),

    authenticatorSelection: {
      authenticatorAttachment: "platform",
      requireResidentKey: true,
    },

    // Three minutes.
    timeout: 180000,
  }
};

navigator.credentials.create(createOptions).then(
  handleCreation, handleCreationError);

RP IDs

There are two levels of controls that prevent passkeys from being used on the wrong website. You need to know about this upfront to prevent getting stuck later.

“RP” stands for “relying party”. You (the website) are a “relying party” in authentication-speak. An RP ID is a domain name and every passkey has one that’s fixed at creation time. Every passkey operation asserts an RP ID and, if a passkey’s RP ID doesn’t match, then it doesn’t exist for that operation.

This prevents one site from using another’s passkeys. A passkey with an RP ID of foo.com can’t be used on bar.com because bar.com can’t assert an RP ID of foo.com. A site may use any RP ID formed by discarding zero or more labels from the left of its domain name until it hits an eTLD. So say that you’re https://www.foo.co.uk: you can assert www.foo.co.uk (discarding zero labels), foo.co.uk (discarding one label), but not co.uk because that hits an eTLD. If you don’t set an RP ID in a request then the default is the site’s full domain.

Our www.foo.co.uk example might happily be creating passkeys with the default RP ID but later decide that it wants to move all sign-in activity to an isolated origin, https://accounts.foo.co.uk. But none of the passkeys could be used from that origin! If would have needed to create them with an RP ID of foo.co.uk in the first place to allow that.

But you might want to be careful about always setting the most general RP ID because then usercontent.foo.co.uk could access and overwrite them too. That brings us to the second control mechanism. As you’ll see later, when a passkey is used to sign in, the browser includes the origin that made the request in the signed data. So accounts.foo.co.uk would be able to see that a request was triggered by usercontent.foo.co.uk and reject it, even if the passkey’s RP ID allowed usercontent.foo.co.uk to use it. But that mechanism can’t do anything about usercontent.foo.co.uk being able to overwrite them.

So either pick an RP ID and put it in the “SEE BELOW” placeholder, above. Or else don’t include the rp.id field at all and use the default.

Recording a passkey

When the promise from navigator.credentials.create resolves successfully, you have a newly created passkey! Now you have to ensure that it gets recorded by the server.

The promise will result in a PublicKeyCredential object, the response field of which is an AuthenticatorAttestationResponse. First, sanity check some data from the browser. Since this data isn’t signed over in the configuration that we’re using, it’s fine to do this check client-side.

const cdj = JSON.parse(
    new TextDecoder().decode(cred.response.clientDataJSON));
if (cdj.type != 'webauthn.create' ||
    (('crossOrigin' in cdj) && cdj.crossOrigin) ||
    cdj.origin != 'https://YOURSITEHERE') {
  // handle error
}

Call getAuthenticatorData() and getPublicKey() on response and send those ArrayBuffers to the server.

At the server, we want to insert a row into the passkeys table for this user. The authenticator data is a fairly simple, binary format. Offset 32 contains the flags byte. Sanity check that bit 7 is set and then extract:

  1. Bit 4 as the value of backed_up. (I.e. (authData[32] >> 4) & 1.)
  2. The big-endian, uint16 at offset 53 as the length of the credential ID.
  3. That many bytes from offset 55 as the value of id.

The ArrayBuffer that came from getPublicKey() is the value for public_key_spki. That should be all the values needed to insert the row.

Handling a registration exception

The promise from create() might also result in an exception. InvalidStateError is special and means that a passkey already exists for the local device. This is not an error, and no error will have been shown to the user. They’ll have seen a UI just like they were registering a passkey but the server doesn’t need to update anything.

NotAllowedError means that the user canceled the operation. Other exceptions mean that something more unexpected happened.

To test whether an exception is one of these values do something like:

function handleCreationError(e: Error) {
  if (e instanceof DOMException) {
    switch (e.name) {
      case 'InvalidStateError':
        console.log('InvalidStateError');
        return;

      case 'NotAllowedError':
        console.log('NotAllowedError');
        return;
    }
  }

  console.log(e);
}

(But obviously don’t just log them to the console in real code.)

Signing in with autocomplete

Somewhere on your site you have username & password inputs. On the username input element, add webauthn to the autocomplete attribute. So if you have:

<input type="text" name="username" autocomplete="username">

… then change that to …

<input type="text" name="username" autocomplete="username webauthn">

Autocomplete for passkeys works differently than for passwords. For the latter, when the user selects a username & password from the pop-up, the input fields are filled for them. Then they can click a button to submit the form and sign in. With passkeys, no fields are filled, but rather a pending promise is resolved. It’s then the site’s responsibility to navigate/update the page so that the user is signed in.

That pending promise must be set up by the site before the user focuses the username field and triggers autocomplete. (Just adding the webauthn tag doesn’t do anything if there’s not a pending promise for the browser to resolve.) To create it, run a function at page load that:

  1. Does feature detection and, if supported,
  2. Starts a “conditional” WebAuthn request to produce the promise that will be resolved if the user selects a credential.

Here’s how to do the feature detection:

if (!window.PublicKeyCredential ||
    !(PublicKeyCredential as any).isConditionalMediationAvailable) {
  return;
}

(PublicKeyCredential as any).isConditionalMediationAvailable()
  .then((result: boolean) => {
    if (!result) {
      return;
    }

    startConditionalRequest();
  });

Then, to start the conditional request:

var getOptions : CredentialRequestOptions = {
  // This is the critical option that tells the browser not to show
  // modal UI.
  mediation: "conditional" as CredentialMediationRequirement,

  publicKey: {
    challenge: Uint8Array.from(atob(CHALLENGE_SEE_BELOW), c =>
                                 c.charCodeAt(0)),

    rpId: SAME_AS_YOU_USED_FOR_REGISTRATION,
  }
};

navigator.credentials.get(getOptions).then(
  handleSignIn, handleSignInError);

Challenges

Challenges are random values, generated by the server, that are signed over when using a passkey. Because they are large random values, the server knows that the signature must have been generated after it generated the challenge. This stops “replay” attacks where a signature is captured and used multiple times.

Challenges are a little like a CSRF token: they should be large (16- or 32-byte), cryptographically-random values and stored in the session object. They should only be used once: when a sign-in attempt is received, the challenge should be invalidated. Future sign-in attempts will have to use a fresh challenge.

The snippet above has a value CHALLENGE_SEE_BELOW which is assumed to be the base64-encoded challenge for the sign-in. The sign-in page might XHR to get the challenge, or the challenge might be injected into the page’s template. Either way, it must be generated at the server!

Handling sign-in

If the user selects a passkey then handle­Sign­In will be called with a Public­Key­Credential object, the response field of which is a Authenticator­Assertion­Response. Send the Array­Buffers raw­Id, response.­client­Data­JSON, response.­authenticator­Data, and response.­signature to the server.

At the server, first look up the passkey: SELECT (username, public_key_spki, backed_up) FROM passkey WHERE id = ? and give the value of rawId for matching. The id column is a primary key, so there can either be zero or one matching rows. If there are zero rows then the user is signing in with a passkey that the server doesn’t know about—perhaps they deleted it. This is an error, reject the sign-in.

Otherwise, the server now knows the claimed username and public key. To validate the signature you’ll need to construct the signed data and parse the public key. The public_key_spki values from the database are stored in SubjectPublicKeyInfo format and most languages will have some way to ingest them. Here are some examples:

Your languages’s crypto library should provide a function that takes a signature and some signed data and tells you whether that signature is valid for a given public key. For the signature, pass in the value of the signature ArrayBuffer that the client sent. For the signed data, calculate the SHA-256 hash of clientDataJSON and append it to the contents of authenticatorData. If the signature isn’t valid, reject the sign-in.

But there are still a bunch of things that you need to check!

Parse the clientDataJSON as UTF-8 JSON and check that:

  1. The type member is “webauthn.get”.
  2. The challenge member is equal to the base64url encoding of the challenge that the server gave for this sign-in.
  3. The origin member is equal to your site’s sign-in origin (e.g. a string like “https://www.example.com”).
  4. The crossOrigin member, if present, is false.

There’s more! Take the authenticatorData and check that:

  1. The first 32 bytes are equal to the SHA-256 hash of the RP ID that you’re using.
  2. That bit zero of the byte at offset 32 is one. I.e. (authData[32] & 1) == 1. This is the user presence bit that indicates that a user approved the signature.

If all those checks work out then sign in the user whose passkey it was. I.e. set a cookie and respond to the running Javascript so that it can update the page.

If the stored value of backed_up is not equal to (authData[32] >> 4) & 1 then update that in the database.

Removing passwords

Once a user is using passkeys to sign in, great! But if they were upgraded from a password then that password is hanging around on the account, doing nothing useful yet creating risk. It would be good to ask the user about removing the password.

Doing this is reasonable if the account has a backed-up passkey. I.e. if SELECT 1 FROM passkeys WHERE username = ? AND backed_up = TRUE has results. A site might consider prompting the user to remove the password on an account when they sign in with a passkey and have a backed-up one registered.

Registering new, passkey-only users

For sign ups of new users, consider making them passkey-only if the feature detection (from the section on enrolling users) is happy.

When enrolling users where a passkey will be their only sign-in method you really want the passkey to end up “in their pocket”, i.e. on their phone. Otherwise they could have a passkey on the computer that they signed-up with but, if it’s not syncing to their phone, that’s not very convenient. There is not, currently, a great answer for this I’m afraid! Hopefully, in a few months, calling navigator­.credentials.­create() with authenticator­Selection.­authenticator­Attachment set to cross-plat­form will do the right thing. But with iOS 16 it’ll exclude the platform authenticator.

So, for now, do that on all platforms except for iOS/iPadOS, where authenticator­Attachment should continue to be plat­form.

(I’ll try and update this section when the answer is simplier!)

Settings

If you’ve used security keys with any sites then you’ll have noticed that they tend to list registered security keys in their account settings, have users name each one, show the last-used time, and let them be individually removed. You can do that with passkeys too if you like, but it’s quite a lot of complexity. Instead, I think you can have just two buttons:

First, a button to add a passkey that uses the createOptions object from above, but with authenticatorAttachment deleted in order to allow other devices to be registered.

Second, a “reset passkeys” button (like a “reset password” button). It would prompt for a new passkey registration, delete all other passkeys, and invalidate all other active sessions for the user.

Test vectors

Connecting up to your language’s crypto libraries is one of the trickier parts of this. To help, here are some test vectors to give you a ground truth to check against, in the format of Python 3 code that checks an assertion signature.

import codecs

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.serialization import (
  load_der_public_key)

# This is the public key in SPKI format, as obtained from the
# `getPublicKey` call at registration time.
public_key_spki_hex = '''
3059301306072a8648ce3d020106082a8648ce3d03010703420004dfacc605c6
e1192f4ab89671edff7dff80c8d5e2d4d44fa284b8d1453fe34ccc5742e48286
d39ec681f46e3f38fe127ce27c30941252430bd373b0a12b3e94c8
'''

# This is the contents of the `clientDataJSON` field at assertion
# time. This is UTF-8 JSON that you also need to validate in several
# ways; see the main body of the text.
client_data_json_hex = '''
7b2274797065223a22776562617574686e2e676574222c226368616c6c656e67
65223a22594934476c4170525f6653654b4d455a444e36326d74624a73345878
47316e6f757642445a483664436141222c226f726967696e223a226874747073
3a2f2f73656375726974796b6579732e696e666f222c2263726f73734f726967
696e223a66616c73657d
'''

# This is the `authenticatorData` field at assertion time. You also
# need to validate this in several ways; see the main body of the
# text.
authenticator_data_hex = '''
26bd7278be463761f1faa1b10ab4c4f82670269c410c726a1fd6e05855e19b46
0100000cc7
'''

# This is the signature at assertion time.
signature_hex = '''
3046022100af548d9095e22e104197f2810ee9563135316609bc810877d1685b
cff62dcd5b022100b31a97961a94b4983088386fd2b7edb09117f4546cf8a5c1
732420b2370384fd
'''

def from_hex(h):
    return codecs.decode(h.replace('\n', ''), 'hex')

def sha256(m):
    digest = hashes.Hash(hashes.SHA256())
    digest.update(m)
    return digest.finalize()

# The signed message is calculated from the authenticator data and
# clientDataJSON, but the latter is hashed first.
signed_message = (from_hex(authenticator_data_hex) +
                  sha256(from_hex(client_data_json_hex)))

public_key = load_der_public_key(from_hex(public_key_spki_hex))
public_key.verify(from_hex(signature_hex),
                  signed_message,
                  ec.ECDSA(hashes.SHA256()))
# `verify` throws an exception if the signature isn't valid.
print('ok')

Where to ask questions

StackOverflow is a reasonable place, with the passkey tag.

Passkeys (04 Jul 2022)

The presentations are out now (Google I/O, WWDC): we're making a push to take WebAuthn to the masses.

WebAuthn has been working reasonably well for enterprises and technically adept users. But we were not going to see broad adoption while the model was that you had to purchase a pair of security keys, be sure to register the backup on every site, yet also keep it in a fire safe. So the model for consumers replaces security keys with phones, and swaps out having a backup authenticator with backing up the private keys themselves. This could have been a different API, but it would have been a lot to have a second web API for public-key authentication, so WebAuthn it is. Basing things on WebAuthn also means that you can still use your security key if you like*, and hopefully with a expanded ranges of sites.

(* albeit not with Android this year, because it doesn't support a recent enough version of CTAP yet. Sorry.)

The WebAuthn spec is not a gentle introduction, but you can find several guides on how to make the API calls. Probably there'll be more coming. What I wanted to cover in this post is the groundwork semantics around passkeys. These are not new if you're fully versed in WebAuthn, but they are new if you've only used WebAuthn in a 2nd-factor context.

I'll probably build on this in some future posts and maybe amalgamate some past writings into a single document. The next paragraph just drops you into things without a lot of context. Perhaps it'll be useful for someone, but best to understand it as fragments of a better document that I'm accumulating.

Ok:

An authenticator is a map from (RP ID, user ID) pairs, to public key credentials. I'll expand on each of those terms:

An authenticator, traditionally, is the physical thing that holds keys and signs stuff. Security keys are authenticators. Laptops can be too; Windows Hello has been an authenticator for a while now. In the world of passkeys, phones are important authenticators. Now that keys may sync, you might consider the sync account itself to be a distributed authenticator. So, rather than thinking of authenticators as physical things, think of it as whatever maintains this map that contains the user's credentials.

An RP ID identifies a website. It's a string that contains a domain name. (In non-web cases, like SSH, it can be a URL, but I'm not covering them here.) A website can use an RP ID if that RP ID is equal to, or a suffix of, the site's domain, and the RP ID is at least an eTLD + 1. So https://foo.bar.example.com can use RP IDs foo.bar.example.com, bar.example.com, and example.com, but not com (because that's less than an eTLD + 1), nor example.org (because that's an unrelated domain). Because the credential map is keyed by RP ID, one website can't use another's credentials. However, be conscious of subdomains: usercontent.example.com can use an RP ID of example.com, although the client data will let the server know which origin made any given request.

Next, a user ID is an opaque byte string that identifies an account on a website. The spec says that it mustn't contain identifiable information (i.e. don't just make it the user's email address) because security keys don't protect the user ID to the same degree that they protect other information. The recommendation is to add a column to your users table, generate a large random value on demand, and store it there for each user. (The spec says 64 bytes but if you just generated 16 from a secure random source, I think you would be fine.) You could also HMAC an internal user ID, although that concentrates risk in that HMAC key.

Recall that an authenticator maps (RP ID, user ID) pairs to credentials? The important consequence is that if a site creates a credential it'll overwrite any existing credential with the same user ID. So an authenticator only contains a single credential for a given account. (For those who know WebAuthn already: I'm assuming discoverable credentials throughout.)

A credential is a collection of various fields. Most obviously a private key, but also metadata: the RP ID, for one, and user information. There's three pieces of user information: the user name, display name, and ID. We've covered the user ID already. The other two are free-form strings that get displayed in UI to help a user select a credential. The user name is generally how a user identifies themselves to the site, e.g. an email address. The display name is how the user would want to be addressed, which could be their legal name. Of the two, the user name will likely be more prominent in UIs.

Lastly a passkey is a WebAuthn credential that is safe and available when the user needs it, i.e. backed up. Not all implementations will be backing up credentials right away and passkeys on those platforms can be called “single-device passkeys”, which is a little awkward, but so's the lack of backup.

Another important aspect of the structure of things is that, while an account only has a single password, it can have multiple passkeys. That's because passkeys can't be copy–pasted around like passwords can. Instead users will register a passkeys as needed to cover their set of devices.

The authenticatorAttachment field in the assertion structure hints to the website about when an additional passkey might be needed. If the value of that field is cross-platform then the user had to use another device to sign-in and it might be worth asking them if they want to register the local device.

When there are multiple passkeys registered on a site, users will need to manage them. The way that sites have often ended up managing 2nd-factor WebAuthn credentials is via an explicit list in the user's account settings. Usually the user will be prompted to name a credential at registration time to distinguish them. That's still a reasonable way to manage passkeys if you like. (We pondered whether browsers could send a passkey “name” at registration time to avoid prompting the user for one but, in a world of syncing, there doesn't seem to be a good value that isn't either superfluously generic, e.g. “Google devices”, or a privacy problem, e.g. the sync account identifier).

If prompting for names and having an explicit list seems too complex then I think it would also be fine to simply have a reset button that a) registers a new passkey, b) deletes every other passkey on the account, and c) signs out all other sessions. I.e. a button that mirrors a password reset flow. For a great many sites, that would work well.

We don't want passwords to hang around on an account forever as a neglected weak-link. In order to guide sites in determining when that might be worth prompting the user to remove their password, there's a new backup state bit in the authenticator data that the server gets with each authentication. If it's set then the passkey will survive the loss of the device. (Unless the device is destroyed after creating the passkey but before managing to sync. But that's the same as generating a random password in a password manager.)

There are not firm rules around using that bit, but once the user has a backed up passkey on a portable authenticator then it's probably time to ask about dropping the password. Sites can know this when they see a creation or assertion operation with the backup state bit set and either the attachment is cross-platform, or it's platform but that platform is a mobile device. That's a conservative set of rules because, for example, a credential created on a MacBook might get synced to the user's iPhone. But maybe that user doesn't have an iPhone.

As you can see, one of the challenges with passkeys is the complexity! Several teams are Google are still working on fleshing out the things demoed at I/O but we know that good guidance will be important. In the mean time, I'm happy to answer questions over Twitter and am pondering if public office hours would be helpful too.

The several canons of CBOR (17 Apr 2022)

There are many encoding formats. CBOR is one of them. Like several others, a subset of it basically fine—I'm not starting that fight today.

Whatever encoding you use, it's nice to reduce flexibility. If there are multiple ways of encoding the same thing then, for anything with a non-negligible diversity of implementations, you'll find that there is a canonical encoding, it's just not documented. As soon as one implementation tries using a valid, but less common encoding, it'll find that it doesn't work and something will change to sort it all out. But that process of eventual coordination is expensive—better to do it explicitly and up-front.

For example, TCP options are chunks of tag–length–value and the spec doesn't define any restriction on their ordering. That didn't stop me blowing up a Ubuntu release because a change of mine happened to alter the order that Linux sent them, and some DSL modems dropped packets when options came in that order. That's an expensive discovery of an implicit canonicalisation rule.

If you're using CBOR then RFC 7049 has a section titled “Canonical CBOR”. One of the things it defines is how to order map elements. Great! No more TCP options messes. You can read that section for yourself, but one interpretation of the words there is what I'll call the three-step ordering for map keys:

  1. Lowest valued types come first then, within each type,
  2. Shortest encoded key comes first then, within consecutive keys with equal lengths,
  3. Sort lexicographically.

However, there is another interpretation of the same section which I'll call the two-step ordering. It drops the first step, i.e. doesn't sort by types. When I first read that section, I certainly came away with only one interpretation, but I can somewhat see how the other arises.

CTAP, the protocol for talking to security keys, uses CBOR a lot and explicitly picks the three-step ordering. An errata was eventually raised against the RFC to “clarify” that the three-step order was correct, but it was rejected as a semantic change. So perhaps that's an official ruling that two-step was the correct understanding?

It only matters if you mix different types of keys in the same map, and sometimes you don't, so maybe it's moot for you. (But keep in mind that negative and non-negative numbers are different types in CBOR.) Anyway, the IETF revised the CBOR RFC to firmly clarify the issue add a third option:

RFC 7049 is obsoleted by 8949. The old “Canonical CBOR” section is replaced by “Core Deterministic Encoding Requirements” and that specifies what I'll have to call the one-step ordering:

  1. Sort lexicographically on the encoded key.

It has some advantages! Like, why was it ever more complicated than that in the first place? But it was, and now there's two (or three) orderings. The two-step ordering even has a subsection of its own in the new RFC and a note saying that it “could be called Old Canonical CBOR”. If only shipped implementations were as changeable as the X-Men universe.

So that's why there's two and half “canonical” CBORs and now I have something that I can reference when people ask me about this.

Update: Someone on Twitter (Thomas Duboucher, perhaps? Sorry, I lost the tweet!) pointed out that the 1- and 3-step ordering give the same results in many cases. Having thought about it, that's correct! As long as you don't use maps, arrays, or tagged values as map keys, I believe they coincide. For something like CTAP2, where map keys are always ints or strings, they work out the same. So perhaps things aren't so bad. (Or perhaps a really subtle difference is worse! Time will tell.)

Picking parameters (15 Mar 2022)

When taking something from cryptographic theory into practice, it's very important to pick parameters. I don't mean picking the right parameters — although that certainly helps. I mean picking parameters at all.

That might seem obvious, but there are pressures pushing towards abdication: what if you get it wrong? Why not hedge bets and add another option? What about the two groups who already shipped something? We could just add options so that everyone's happy.

There are always exceptions, but the costs of being flexible are considerable. ANSI X9.62, from 1998, specified how elliptic curves were encoded in ASN.1 and included not just 27 possible curves, but allowed the parameters to be inherited from the issuing CA and allowed completely arbitrary elliptic curves to be defined inside a public key. That specifies almost nothing and avoids really standardising on anything. Thankfully I've not seen parameter inheritance implemented for ECC (it would be a security mess) but support for custom elliptic curves does, sadly, exist.

A couple of years ago, Microsoft had a signature bypass because of support for arbitrary curves [details]. Today, OpenSSL had an infinite loop in certificate parsing because of the same. On the flip side, I'm not aware that anyone has ever used the ability to specify arbitrary curves for anything useful.

It's not fair to just blame X9.62: don't get me started about RSA PSS. The cost of having too many options is frequently underestimated. Why does AES-192 exist, for example, other than to inflate test matrices?

As an aside, it's interesting to wonder how many CPU decades have been spent fuzzing OpenSSL's certificate parsing and yet today's issue wasn't reported before. This isn't a 2-128 fraction of state space that fuzzers couldn't be expected to find, and I'm not sure that Tavis found it from fuzzing at all.


There's an index of all posts and one, long page with them all too. Email: agl AT imperialviolet DOT org.