Adventures with RSA Blind Signing

Let’s try (and fail) to break RSA blind signatures today! Google One recently released a VPN service, with the goal of protecting users’ privacy as they browse the web (explainer, implementation). One interesting detail is that it uses RSA Blind Signing to decouple a user’s authentication (signing) from their internet browsing (redemption), so that users have a stronger guarantee that their online activity won’t be tied back to their identity. I was the cryptography reviewer for this project, so I took the opportunity to understand how RSA Blind Signatures work. In this writeup, I’ll first give a brief primer on blind signatures. Then the fun part: I’ll walk you through two RSA Blind Signature “non-attacks” — things I thought were vulnerabilities, but actually weren’t — so others can learn from my mistakes! I’ll wrap up with some advice for anyone who is looking to use blind signing protocols in the future.

Background on Blind Signing

Blind signing is exactly what it sounds like: a protocol where someone signs something without knowing (being blind to) what they are signing. This concept was first described by Chaum in 1982 in his paper, Blind Signatures for Untraceable Payments. Basically, blind signing allows you to decouple the signing step (since the signer is blind) from the redemption step, giving nice privacy guarantees. The concept might seem a bit contrived, but is actually useful in a few situations, including digital cash schemes and voting protocols. For a really good explanation of how this works using the voting analogy, see the Cloudflare blog post on Privacy Pass; if you like talks more, I explained the concept in my talk at 0x0G.

The VPN by Google One, Cloudflare, and Google Chrome are all interested in blind signing protocols as well. This is because they all have something in common: they want to make sure that users are actually valid users (as opposed to bots, scrapers, etc) before serving them content, but they also want to preserve the privacy of those users as they browse. Blind signing allows them to do both. The users prove that they are valid users by authenticating to a service, and giving the service a blinded value to sign (so the service doesn’t actually know what token it’s signing). Then, when the user wants to retrieve content, they unblind and redeem this signed value (token). The redeemed unblinded value that the redemption endpoint sees is unlinkable to the blinded value the authentication service saw and signed! Therefore with blind signing, a VPN by Google One user can have peace of mind that the VPN operator is not able to link their identity with their browsing activity using session IDs, which gives a stronger anonymity guarantee.

RSA blind signatures

The simplest blind signing scheme is based on RSA signing. I will not cover RSA signing here, other than to link to the RSA paper and to mention that it is extremely easy to implement insecurely, leading to a long and storied history of attacks on RSA and a general recommendation not to use RSA by cryptographers. I will discuss later why RSA based blind signatures were still the right choice for VPN by Google One.

RSA parameters, oversimplified (assume that these are chosen correctly):

e = public exponent
d = private exponent (known by signing server)
x^e^d == x (mod N) for all x in [0, N)

Protocol:

Notes: r must be relatively prime to N. The Client and Redemption Point must know the correct public key e.

“Non-attack” #1: token malleability

Suppose you are a malicious client, and want to run a bot farm. You'd like to legitimately get one signed token, and then use it to create many new illegitimate but valid signed tokens, for your bots to use, by taking advantage of token malleability.

First, you authenticate to the Signing Server and get a signed blinded token back: T = sig(BM). Next, you create a bunch of new tokens from this signed token without having to authenticate again, by multiplying your token by a constant. For example, you can make T’ = T/2:

T' = sig(BM) / 2
= (m*r^e)^d / 2
= m^d * r / 2

Now you can unblind your new, evilly procured token T':
sig(m') = T' / r
= m^d / 2

Send your evil unblinded token to the Redemption Point, which does the validity check without suspecting a thing:
given signed token: sig(m') = m^d / 2
given message: m' = m / 2^e
check: m' == sig(m')^e
which gives: m / 2^e == (m^d / 2)^e
expanded: m / 2^e == m / 2^e

So the Redemption Point sees this check as passing, meaning they have unwittingly accepted the evil token! Using this approach, you could produce near-infinite evil tokens using just one honest token: just multiply the honest token by different constants, and tweak m' accordingly.

Now why doesn’t this work? Moti pointed out to me graciously: it actually would work fine if you were only operating over plain messages m… the attack works because of the ability to tweak m freely, since the receiver doesn’t actually know ahead of time what the message should be. In fact, this is the way that RSA blind signatures are initially written up on the Wikipedia page (though hashing is mentioned at the end of that section). However, the correct way to implement RSA blind signatures is to operate on the hash of the message, instead of the message itself. If you replace all instances above of m and m' with h(m)and h(m'), you will see that in order to successfully create a malicious h(m') to fool the Redemption Point, you would have to find a preimage to the hash function. We assume that this is a computationally infeasible task, if the hash function is well chosen.

This is yet another example of low-level asymmetric crypto pitfalls… and also why it’s important to reference the correct writeup when analyzing cryptographic protocols! Of course, Google One’s VPN implements this correctly, and I was just chasing a false lead.

“Non-attack” #2: nonce reconstruction

Here’s a more subtle non-attack. RSA blind signing is constructed so that even if the Signing Server and Redemption Point collude, they should not be able to link a token signing from redemption. Let’s poke around to see what they could learn by colluding. Say the Signing Server saw a blinded token BM, and the Redemption Point saw a redeemed token with message m. They think that these two are linked, meaning that BM was a blinded token made from m. Working together, they will try to reconstruct r from these pieces.

Signer knows: BM, d (privkey)
Redemption point knows: m, sig(h(m)), h(m)
Everyone knows: e (pubkey)
Solve for r: BM = h(m) * r^e mod N
Divide by shared h(m): BM / h(m) = r^e mod N
Raise by privkey d: (BM / h(m))^d = r^e^d mod N = r'

So, the evil Signing Server and Redemption Point have reconstructed the secret nonce r (their guess is denoted as r'). They can now check if this r' actually corresponds to the original BM and m that were received:

BM == h(m) * r' ^ e mod N
== h(m) * ((BM / h(m))^d)^e mod N
== h(m) * BM / h(m) mod N
== BM mod N

So, the original BM and m received do correspond with r', meaning that the Signing Server and Redemption Point have successfully linked a token signing with a token redemption! This breaks the anonymity and privacy guarantees of RSA Blind Signing, and means that a malicious browser / CDN / VPN can track your behavior across the internet…

Or does it? Before reading on, maybe try to figure out why this attack actually doesn’t work? It’s a fun exercise! Credit to Thai for pointing this out first.

Okay, here’s why this doesn’t work… because any reconstructed r', from any BM and m values even if they are not correlated, will pass this check! Let’s work through it with example BM_1 that corresponds to m_1, and sig(h(m_2)), m_2 where m_1 != m_2:

Signer knows: BM_1, d (privkey)
Redemption point knows: m_2, sig(h(m_2))
Everyone knows: e (pubkey)
Solve for r: BM_1 = h(m_1) * r_1^e mod N
Divide by h(m_2): BM_1 / h(m_2) = h(m_1) * r_1^e / h(m_2) mod N
Raise by privkey d: (BM_1 / h(m_2))^d = (h(m_1)/h(m_2))^d * r_1 mod N = r'

Notice how in the original attack, when we divided by h(m) it cancelled out on the right, since we assumed that the signer and redemption point were looking at the same message. In this example, it doesn’t cancel out nicely because we are assuming that m_1 != m_2. Since the Signing Server and Redemption Point don’t know whether the messages are correlated, they set their guess r' to this messy value (BM_1 / h(m_2))^d. Let’s see how the equivalence check plays out:

BM_1 == h(m_2) * r' ^ e mod N
== h(m_2) * (h(m_1)/h(m_2))^d * r_1)^e mod N
== h(m_2) * h(m_1)/h(m_2) * r_1^e mod N
== h(m_1) * r_1^e mod N

And this check actually still succeeds, as we end up with the original definition of BM_1 = h(m_1) * r_1^e! So what this means is that whether you are reconstructing r' from two related or unrelated values doesn’t matter, as no matter what, your reconstructed r' will pass the faulty check of relatedness. So you don’t actually learn any information, either way.

Alternatives

There are many other protocols to blindly create tokens, which can be broadly grouped under blind signatures and anonymous tokens. Blind signatures include RSA, Schnorr/DSA, BLS, and Abe; this post is a great introduction to the field. Some well-known examples of anonymous token protocols are Privacy Pass, used by Cloudflare, and Trust Tokens, used by Google Chrome. (I was also lucky enough to review Trust Tokens before it launched; I gave a talk at 0x0G about my findings).

The drawback for anonymous token schemes such as VOPRF-based Privacy Pass and Trust Tokens is that they are not publicly verifiable — that is, any redemption point would have to know the secret key d in order to check that a signature is valid. RSA, Schnorr, Abe, and other blind signatures are publicly verifiable: you only need the pubkey e to perform a signature validity check. In the case of VPN by Google One, it was highly desirable for the signatures to be publicly verifiable so that the private key wouldn’t have to be distributed to all exit nodes. Therefore, it made sense to choose a publicly verifiable signature scheme in this setting. Schnorr blind signatures are shown to be broken, BLS blind signatures are computationally expensive, and Abe blind signatures have large signatures; given design requirements, RSA blind signatures were the best fit for VPN by Google One.

For both anonymous tokens and blind signature schemes, one critical component is for all clients to see the same public key (or in the case of Trust Tokens, the same set of public keys) — this is the only way the unlinkability property can hold. If different users see different public keys, then the signer and redemption endpoints will be able to differentiate between groups of users based on which public key they are working with — therefore grouping the users into different anonymity sets.

Conclusion

My main takeaway from all this is that RSA is weird! As a result, RSA blind signing has strange properties, and its security relies on subtle things such as hashing and correct RSA parameter selection. But the core protocol is not broken; in fact, this paper proves it to be secure under the random oracle model. So our attempts to break RSA blind signatures were doomed to fail all along, but hopefully it was a fun adventure! If you want to learn more or be involved in discussions on this topic, here is a recent draft for the Crypto Forum Research Group (CFRG) on RSA blind signatures.

Thanks

With contributions from Thai Duong, Moti Yung, Tancrède Lepoint, and Scott Hendrickson — thanks for working with me on this review! Thanks also to Andres Erbsen, Jeremy Rubin, and Geoff Bradway for giving feedback on this blog post and making it more readable.