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
- Add checkpoint key ID to trust root This adds a string to represent the checkpoint key ID for a log, which will differ for ed25519 logs. To simplify client implementation, we will provide this string... — committed to haydentherapper/protobuf-specs by haydentherapper 3 years ago
- Add checkpoint key ID to trust root This adds a string to represent the checkpoint key ID for a log, which will differ for ed25519 logs. To simplify client implementation, we will provide this string... — committed to haydentherapper/protobuf-specs by haydentherapper 3 years ago
- Add checkpoint key ID to trust root This adds a string to represent the checkpoint key ID for a log, which will differ for ed25519 logs. To simplify client implementation, we will provide this string... — committed to haydentherapper/protobuf-specs by haydentherapper 3 years ago
- Add checkpoint key ID to trust root (#284) * Add checkpoint key ID to trust root This adds a string to represent the checkpoint key ID for a log, which will differ for ed25519 logs. To simplify c... — committed to sigstore/protobuf-specs by haydentherapper 3 years ago
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?
Correct, particularly adding support for ed25519.
Correct. Note that at some point, we’ll also want to handle
0x04co-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 lookingActually 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.
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.
Unfortunately, reading more, the
public keyencoding is a bit messy.public keypart of the key ID, which would be for0x01ed25519 checkpoint signatures and0x04witness cosignatures (which mandate ed25519).0x02ECDSA checkpoint signatures and0x05RFC6962 checkpoints, it isSHA256(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)0xffwe are on our own. I would recommendSHA256(DER(SPKI(raw public key)))forpublic key, and use0xfffor 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)))- codeIf 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?