rekor: Checkpoint spec compliance: Incorrect key ID for non-ECDSA keys

Background

https://github.com/C2SP/C2SP/blob/main/signed-note.md defines the specification for a signed note, which is the format of a checkpoint. Note that this specification was only recently created. When checkpoints were added to Rekor, we followed the code for Go’s checksum db note format, which is the signed note format - docs, code

The signature is the following format:

— <key name> base64(32-bit key ID || signature)

where key ID is the following format, roughly the truncated hash of the key name, signature scheme, and public key:

key ID = SHA-256(key name || 0x0A || signature type || public key)[:4]

Go’s checksum db note code only defines a verifier for ed25519 keys (code), again aligning with the spec, where signature type = 0x01. It does not support ecdsa keys.

For historical reasons (citation needed) and as noted in the spec, ecdsa key IDs are the truncated hash of the DER encoded public key in SPKI format (code, with the truncation happening here).

Issue

When Rekor generates a signed note, it generates the key ID as a truncated DER encoded public key hash regardless of signature type. ecdsa is spec compliant, but ed25519 and RSA is not. The impact of this is if we were to switch to ed25519 or RSA signing keys, Rekor checkpoints would not be verifiable by omniwitness, armored witness or any other upcoming witness implementations.

The other issue is that the c2sp spec doesn’t define support for RSA. There is an issue tracking this request, but general consensus is a lack of interest in supporting RSA due to additional signature support for witnesses, RSA vulnerability concerns and key/signature size. For public instances that could join a witness network, we should strongly recommend using ecdsa or ed25519 keys. For private instances, RSA can still be supported using the 0xff identifier type as per the spec.

Fixes

Given the last time I made a change to the checkpoint format, dropping the timestamp, it impacted clients, I want to make sure we thoughtfully roll this out.

Clients will need to add support for parsing signed notes following the spec, particularly computing the key ID differently for ed25519 and RSA keys. If you want to avoid any chance of breakage for private deployments that are currently using these key types, you could fallback to the DER encoded public key ID.

However, I don’t know if clients were using the key ID to verify checkpoints. If the client was simply dropping the 32-bit key ID from base64(32-bit key ID || signature) before verifying the signature, this change seems quite safe to do. For example, for sigstore-go (which uses the Rekor library), we’re doing just that - Base64 is the signature without the key ID (Hash). Technically this isn’t following the spec, as the key ID should be compared against a known key. That doesn’t seem like a requirement for Sigstore though, more for witnesses, since we have a way of distributing trusted keys. (Edit: this is not true for other clients, so we will need client changes)

For server side changes, given the public instance has only used ecdsa, we could fix the format for ed25519 and RSA signing keys without any impact to clients. If we want to do this in a non-breaking way, we would need to introduce the new checkpoint format in another response field for the /log API, though I don’t like that approach as much as it’ll complicate client logic for fetching a checkpoint and prolong this fix.

About this issue

  • Original URL
  • State: open
  • Created 3 years ago
  • Comments: 17 (14 by maintainers)

Commits related to this issue

Most upvoted comments

I vote no rsa support unless it’s defined in spec, we’d just be setting ourselves up for future incompatibility

@loosebazooka and I were chatting today about this, and came up with a good compromise that avoids clients needing to know this computation - let’s include the checkpoint key ID (the truncated hash) as an optional field in the trust root TransparencyLogInstance. Clients can then treat the checkpoint key ID as an arbitrary string rather than a constructed identity.

I would vote that we make it optional to avoid making this a breaking change to the trust root. If the checkpoint key ID is not set, then the client should assume checkpoint key ID == log ID (which is the case for ecdsa and RSA). For new ed25519 logs, the checkpoint key ID must be set.

What do you think @bdehamer @woodruffw?

Stop assuming that everything is ECDSA

Correct, particularly adding support for ed25519.

Propagate the key type from its representation in TrustedRoot.tlogs[].public_key Use the key type to determine the key ID algorithm to apply

Correct. Note that at some point, we’ll also want to handle 0x04 co-signed checkpoints, signed with ed25519 as per the spec. So the key ID gives you both the signature algorithm and the structure that you’re verifying, a checkpoint vs witnessed checkpoint. But that’s forward looking

Please direct me to another issue if this is the wrong place, but: is there a demonstrated (public or private) desire for RSA-based tlogs? Given that RSA sigs are much larger and that RSA signing is generally slower, I was under the impression that it wasn’t commonly used for tlogs (despite RFC 6962 allowing it).

Actually the opposite, RSA is not preferred. I brought this up in https://github.com/C2SP/C2SP/issues/63, and the consensus was a) concerns about RSA vulns particularly for PKCS#1v1.5, b) key/sig size, c) another alg to support. I did point out RFC 6962 allows for it, but since RFC 6962 doesn’t have support for checkpoints and C2SP is focused on improving Certificate Transparency, they’re fine going off-spec.

So if we want to say no RSA for Rekor, I’m OK with that. Rekor does support it currently so we might get some pushback from private instances, so I’d want to ask around. But if we’re already in the state where most clients are just supporting ecdsa, then it’s not really a breaking change.

Wasn’t there also something about using a different style of logid for rekor? I can’t seem to remember details, but there was no guarantee it was going to continue to be a hash of the public key like CT.

Yea, the CT v2 RFC defined log IDs as OIDs rather than a hash of a public key. The idea being that you might want to reuse a public key across logs but have each log have its own identity. I don’t think we’ll move away from the log ID being the hash though as most tools expect this, so instead we’ll rotate the key the next time we create a new log.

For non-ECDSA keys, the key ID is defined as SHA-256(key name || 0x0A || signature type || public key)[:4], where public key is DER(SPKI(raw public key)) For ECDSA keys, the key ID is not defined, but Rekor chooses to use SHA-256(public key)[:4]

Unfortunately, reading more, the public key encoding is a bit messy.

  • ed25519 public keys use the 32-byte public key byte array for the public key part of the key ID, which would be for 0x01 ed25519 checkpoint signatures and 0x04 witness cosignatures (which mandate ed25519).
  • For 0x02 ECDSA checkpoint signatures and 0x05 RFC6962 checkpoints, it is SHA256(DER(SPKI(raw public key))). (Note that there is an open issue to restrict the new RFC6962 checkpoints to only ecdsa, to not deal with RSA)
  • For RSA, for 0xff we are on our own. I would recommend SHA256(DER(SPKI(raw public key))) for public key, and use 0xff for the signature type.

For ECDSA, it is defined in the spec. It wasn’t Rekor that decided the different format for ecdsa, I believe it was either RFC 6962 or some of the original witness work, and the spec didn’t want to break existing logs using ecdsa. Rekor’s key ID is currently SHA256(DER(SPKI(raw pubkey))) - code

sigstore-python currently only expects ECDSA-based tlogs, and so does (2) unconditionally

If you aren’t handling RSA or ed25519, then this is even better, as it wouldn’t be a breaking client change.

Sorry about that rollout, we had assumed the other content in the signed note was considered optional.

The good news with this change is that there would be no changes to metadata produced from the public instance, since it uses ecdsa and there would be no changes there. I am unaware of any other public logs.

To make sure we don’t break anyone, let’s do the client changes (I can file bugs in each repo to track the change), and after a few months, we can roll out the change here. We’ll also document in Rekor that an ecdsa key should be preferred and must be chosen if you will host a public log. How does that sound?