A tale of GQ signatures and adding GitLab support to OpenPubkey.
OpenPubkey is an open-source protocol that allows OpenID Providers (OPs) to bind user- or workload-identities to public keys. It’s a powerful tool that works with today’s OpenID Connect (OIDC). It allows OPs to essentially act like Certificate Authorities (CAs). It’s totally backwards compatible with existing OPs, requiring no changes whatsoever to today’s OIDC.
When we first released OpenPubkey, it was interoperable with many OPs (like Google and GitHub), but not with all of them. In fact, when we started this project, there was an actual technological limitation that prevented OpenPubkey from working with certain OPs, including GitLab’s OP. And support for GitLab’s OP was one of our most requested features.
Well, today I’m happy to announce that last week’s release of OpenPubkey v0.3.0 smashes through this limitation. OpenPubkey now interoperates with any OpenID Provider.
We did this using a very cool cryptographic primitive from the 1980s called a Guillou-Quisquater (GQ) signature. In this blog, I’ll explain what a GQ signature is, why it’s awesome, and how we used it to generalize OpenPubkey to any OpenID Provider. In fact, GQ signatures mean that in the future OpenPubkey might even be able to support non-OIDC protocols like SAML! In this post I’ll show how we used GQ signatures to add support for GitLab’s OP to the OpenPubkey open-source repository.
OpenID Connect (The Very Abridged Guide)
OpenID Providers (OP), such as Google, GitHub or GitLab attest to a user or workload’s identity by asking that user or workload to authenticate to the OP. If authentication is successful, the OP signs and issues an ID Token to that user or workload.
An ID Token consists of a payload, a protected-header and a signature. The payload is a set of JSON claims about the identity such as name, email address, etc. The signature allows anyone to check that the ID Token was actually issued by the OP.
Shown below is an example Google-issued ID Token:payload: {
"iss": "https://accounts.google.com",
"aud": "example-audience”
"email": "alice@gmail.com",
"nonce": 'a523ff…',
...
}
signatures: [
{"protected": {"typ": "JWT", "alg": "RS256", "kid": "1234...", "typ": "JWT"},
"signature": SIGN-RSA(google-signkey, (payload, signatures[0].protected))`
},
]
This ID Token is saying: I am Google and I’m telling you that whoever presents this ID Token is Alice@gmail.com.
Alice can then reveal this ID Token to a third party to prove that she is Alice@gmail.com. The ID Token functions like an authentication credential.
OpenPubkey (The Very Abridged Guide)
ID Tokens work extremely well and are used nearly everywhere to authenticate users, workloads and other machine identities. However they are missing a critical feature: public keys.
Imagine Alice wants to sign a message. How can everyone be sure that the message was actually signed by Alice?
What if a build system wants to use GitHub or GitLab to sign a build artifact that it generated?
Enter OpenPubkey, which binds identities to public keys using an object we call a PK Token. A PK Token is essentially an enhanced ID Token. The PK Token allows the OP to attest to a public key, and that key is used to sign the object.
Let’s first see how this works for Google’s OP. When a user requests an ID Token from Google’s OP, she has to include a nonce claim, which contains a random value. The nonce is then included in the ID Token provided by Google’s OP. So, to make OpenPubkey work with Google’s OP, the user chooses a public-private key pair, hashes the public key along with randomly-chosen noise, and puts the hash in the nonce she sends to the OP. The nonce is signed by the OP as part of the ID Token. Now we have a binding from the user’s identity to their public key. The PK Token consists of the ID Token, the user’s public key and the randomly-chosen noise. The user’s secret key is then used to sign objects, and the PK Token is included with the signature to attest to the key used to sign the object.
OpenPubkey works almost the same with GitHub’s OP, except that (1) GitHub’s OP attests to keys held by workloads, rather than users, and (2) we use the aud (audience) claim in the ID Token instead of the nonce claim.
But, neither of these approaches work for GitLab. GitLab’s ID Tokens do not contain a nonce claim and the aud (audience) claim can not be set by the workload.
GQ Signatures Prevent Replay Attacks
Before we explain how we used GQ signatures to add support for GitLab’s OP, let’s take a brief segue to explain why we started working with GQ signatures in the first place.
The original reason we started working with GQ signatures is to prevent replay attacks.
To see why we need to worry about replay attacks, let’s talk about how to use OpenPubkey in an application. Suppose you want to use PK Tokens to attest to public keys that are used to sign build artifacts in a repository. To do this, you need to post the PK Token along with the signed build artifact in the repository. But if you publish the PK Token in the repository, everyone can see it. This creates a risk that someone will just grab the ID Token in the PK Token in the repository and use it as an authentication credential. In other words, there is a risk that the ID Token will be used in a replay attack.
To ensure that someone can’t use the published ID Token as an authentication credential we transform it using GQ signatures.
A GQ signature is a proof of knowledge of an RSA signature. Essentially, if you replace the RSA signature on the ID Token with a GQ Signature, you can still prove that Google or GitHub signed your ID Token. But now, the ID Token can’t be used as an authentication credential to OIDC verifiers because it is no longer signed with a regular RSA signature. Instead, the ID Token just carries a proof that the ID Token was signed with an RSA signature. This proof is the GQ signature.
This was the original reason we added GQ signatures to OpenPubkey: To maintain the desired security properties of the ID Token while preventing it from being replayed as a credential.
(Note: OpenID Connect has a built-in mechanism to prevent exactly this sort of ID Token replay attack. You can scope the intended use of an ID Token so that any correctly configured OpenID Connect relying party will reject the ID Token as a credential. However, the security of this mechanism depends on verifiers being correctly configured to check the scoping, and that is always a dangerous assumption to make. We use GQ signatures to completely rule out such attacks even against misconfigured OpenID Connect relying parties.)
GQ Signatures Let You Sign Messages
GQ signatures have another useful property. They not only allow you to prove knowledge of an RSA signature but also allow you to use that knowledge of that RSA signature to sign a message. Essentially the RSA signature becomes a signing secret. We use the GQ signature to not only prove we know the RSA signature, but also to sign a commitment to the identity's public key. We used this approach to add support for GitLab’s OP to OpenPubkey.
The way this works is as follows:
- Alice requests an ID token from GitLab,
- Alice uses the RSA signature on the ID Token to generate a GQ signature that signs her public key and some other important values,
- Alice replaces the RSA signature on the ID Token with the GQ signature she just created.
Now Alice can prove to anyone that her ID Token was signed by GitLab and that someone who knew the RSA signature that Google generated signed her public key. The GQ Signature on Alice’s ID Token binds Alice’s public key to her ID Token.
Note that for this to work Alice needs to keep GitLab’s RSA signature a secret. This is important, because if anyone else were to learn GitLab’s RSA signature on Alice’s ID Token, then they could also generate a GQ signature and break the security of the scheme. That is why in the OpenPubkey client we delete the RSA signature immediately after generating the GQ Signature. To ensure that ID Tokens created for other purposes can’t be used as PK Tokens, we require that ID Token be specifically marked to be created for OpenPubkey. ID Tokens not marked in this way are rejected by all OpenPubkey verifiers.
You might be saying right now, wow that’s a really strange use of GQ signatures. Is that safe?
Well, turning RSA signatures into signing secrets was what GQ signatures were designed to do when they were first developed in the 1980s. And they haven’t been broken since.
GQ Signatures Unlocks a Universe of Protocols for OpenPubkey
GQ signatures enable OpenPubkey to bind any RSA signed message to a public key. As long as the protocol produces an RSA-signed message to the identity and this signed message includes an identifier such as a name or email address, we can use GQ signatures to bind that signed message to a public key.
This is great because OIDC requires every OP to produce RSA signatures!
…But wait there’s more!
I often get asked why we are limited to RSA signatures. The answer is yes but actually no.
Yes, the GQ signature approach is limited to RSA signatures but actually no. The no is because it’s better to use a different well-used practical approach that does the same thing for any signature algorithm (not just RSA). I’m thinking specifically of zkSNARKS, which allows you to sign messages under any secret knowledge (for more details see the Fiat-Shamir Heuristic). So as long as someone signs a message and that signature is secret, you can bind your public key to that message. The signature algorithm used by the OP doesn’t have to be RSA, it can be anything.
This isn’t some impractical theoretical idea either. Bonsai-pay is currently using zkSNARKs to bind public keys to ID tokens.
Get Involved with the OpenPubkey Community!
I hope you enjoyed this deep dive into GQ signatures and how they are useful for OpenPubkey. There are lots more exciting features in our latest release of OpenPubkey, so watch this space as I continue to blog about them.
We invite anyone who wants to contribute to OpenPubkey to visit and star our GitHub repo. We are building an open and friendly community and welcome pull requests from anyone — see the contribution guidelines to learn more. If you are interested in contributing to OpenPubkey, take a look at our list of Good First Issues or reach out to me.
