Adventures with RSA Blind Signing

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.

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.

“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.

“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.

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).

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Cathie Yun

Cathie Yun

Cryptographer, climber, explorer. Previously working on ZK proofs at Chain/Interstellar, now on Google’s cryptography security team.