RFC 9474: RSA Blind Signatures
- F. Denis,
- F. Jacobs,
- C. A. Wood
Abstract
This document specifies an RSA-based blind signature protocol. RSA blind signatures were first introduced by Chaum for untraceable payments. A signature that is output from this protocol can be verified as an RSA-PSS signature.¶
This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF.¶
Status of This Memo
This document is not an Internet Standards Track specification; it is published for informational purposes.¶
This document is a product of the Internet Research Task Force
(IRTF). The IRTF publishes the results of Internet
Information about the current status of this document, any
errata, and how to provide feedback on it may be obtained at
https://
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved.¶
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://
1. Introduction
Originally introduced in the context of digital cash systems by Chaum
for untraceable payments [Chaum83], RSA blind signatures turned out to have
a wide range of applications ranging from privacy
Recently, interest in blind signatures has grown to address operational shortcomings from applications that use Verifiable Oblivious Pseudorandom Functions (VOPRFs) [VOPRF], such as Privacy Pass [PRIVACY-PASS]. Specifically, VOPRFs are not necessarily publicly verifiable, meaning that a verifier needs access to the VOPRF private key to verify that the output of a VOPRF protocol is valid for a given input. This limitation complicates deployments where it is not desirable to distribute private keys to entities performing verification. Additionally, if the private key is kept in a Hardware Security Module, the number of operations on the key is doubled compared to a scheme where only the public key is required for verification.¶
In contrast, digital signatures provide a primitive that is publicly verifiable and does not require access to the private key for verification. Moreover, [JKK14] shows that one can realize a VOPRF in the random oracle model by hashing a (message, signature) pair, where the signature is computed using a deterministic blind signature protocol.¶
This document specifies (1) a protocol for computing RSA blind signatures using RSA-PSS encoding and (2) a family of variants (Section 5) for this protocol, denoted RSABSSA (RSA Blind Signature with Appendix). In order to facilitate deployment, it is defined in such a way that the resulting (unblinded) signature can be verified with a standard RSA-PSS library.¶
This document represents the consensus of the Crypto Forum Research Group (CFRG). It is not an IETF product and is not a standard.¶
2. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
3. Notation
The following terms, which describe different protocol operations, are used throughout this document:¶
- bytes_to_int and int_to_bytes:
- Convert a byte string to and from a non-negative integer. bytes_to_int and int_to_bytes are implemented as OS2IP and I2OSP -- as described in [RFC8017] -- respectively. Note that these functions operate on byte strings in big-endian byte order.¶
- random
_integer _uniform (M, N): - Generate a random, uniformly distributed integer R between M inclusive and N exclusive, i.e., M <= R < N.¶
- bit_len(n):
- Compute the minimum number of bits needed to represent the positive integer n.¶
- inverse_mod(x, n):
- Compute the multiplicative inverse of x mod n or fail if x and n are not co-prime.¶
- is_coprime(x, n):
- Return true if x and n are co-prime, and false otherwise.¶
- len(s):
- The length of a byte string, in bytes.¶
- random(n):
- Generate n random bytes using a cryptographical
ly secure random number generator.¶ - concat(x0, ..., xN):
- Concatenation of byte strings. For example, concat(0x01, 0x0203, 0x040506) = 0x010203040506.¶
- slice(x, i, j):
- Return bytes in the byte string
xstarting from offsetiand ending at offsetj, inclusive. For example, slice(0x010203040506, 1, 5) = 0x0203040506.¶
4. Blind Signature Protocol
The RSA Blind Signature Protocol is a two-party protocol between a client and server
where they interact to compute sig = Sign(sk, input_msg), where input_msg = Prepare(msg)
is a prepared version of the private message msg provided by the client, and sk is the
private signing key provided by the server. See Section 6.2 for details on how sk is generated
and used in this protocol. Upon completion of this protocol, the server learns nothing,
whereas the client learns sig. In particular, this means the server learns nothing of msg
or input_msg and the client learns nothing of sk.¶
The protocol consists of four functions -- Prepare, Blind, BlindSign, and Finalize -- and requires
one round of interaction between client and server. Let msg be the client's private input
message, and let (sk, pk) be the server's private and public key pair.¶
The protocol begins by the client preparing the message to be signed by computing:¶
The client then initiates the blind signature protocol by computing:¶
The client then sends blinded_msg to the server, which then processes the message
by computing:¶
The server then sends blind_sig to the client, which then finalizes the protocol by computing:¶
The output of the protocol is input_msg and sig. Upon completion, correctness requires that
clients can verify signature sig over the prepared message input_msg using the server
public key pk by invoking the RSASSA
Shown graphically, the protocol runs as follows:¶
In the remainder of this section, we specify the Prepare, Blind, BlindSign, and Finalize functions that are used in this protocol.¶
4.1. Prepare
Message preparation, denoted by the Prepare function, is the process by which the message
to be signed and verified is prepared for input to the blind signing protocol.
There are two types of preparation functions: an identity preparation function
and a randomized preparation function. The identity preparation function returns
the input message without transformation, i.e., msg = Prepare.¶
The randomized preparation function augments the input message with fresh randomness.
We denote this process by the function Prepare, which takes as input a message
msg and produces a randomized message input_msg. Its implementation is shown below.¶
4.2. Blind
The Blind function encodes an input message and blinds it with the server's public key. It outputs the blinded message to be sent to the server, encoded as a byte string, and the corresponding inverse, an integer. RSAVP1 and EMSA-PSS-ENCODE are as defined in Sections 5.2.2 and 9.1.1 of [RFC8017], respectively.¶
If this function fails with a "blinding error" error, implementations SHOULD try the function again. The probability of one or more such errors in sequence is negligible. This function can also fail with an "invalid input" error, which indicates that one of the inputs (likely the public key) was invalid. Implementations SHOULD update the public key before calling this function again. See Section 6.1 for more information about dealing with such errors.¶
Note that this function invokes RSAVP1, which is defined to throw an optional error for invalid inputs. However, this error cannot occur based on how RSAVP1 is invoked, so this error is not included in the list of errors for Blind.¶
The blinding factor r MUST be randomly chosen from a uniform distribution. This is typically done via rejection sampling.¶
4.3. BlindSign
BlindSign performs the RSA private key operation on the client's blinded message input and returns the output encoded as a byte string. RSASP1 is as defined in Section 5.2.1 of [RFC8017].¶
4.4. Finalize
Finalize validates the server's response, unblinds the message to produce a signature, verifies it for correctness, and outputs the signature upon success. Note that this function will internally hash the input message as is done in Blind.¶
4.5. Verification
As described in Section 4, the output of the protocol is the prepared
message input_msg and the signature sig. The message that applications
consume is msg, from which input_msg is derived. Clients verify the
msg signature using the server's public key pk by invoking the
RSASSA(n, e) as pk, M as input_msg, and S as sig.¶
Verification and the message that applications consume therefore depend on
which preparation function is used. In particular, if the PrepareIdentity
function is used, then the application message is input_msg.
In contrast, if the Prepareslice(input_msg, 32, len(input_msg)), i.e., the prepared message
with the message randomizer prefix removed.¶
5. RSABSSA Variants
In this section, we define different named variants of RSABSSA. Each variant specifies EMSA-PSS options Hash, MGF, and sLen as defined in Section 9.1.1 of [RFC8017], as well as the type of message preparation function applied (as described in Section 4.1). Each variant uses the mask generation function 1 (MGF1) defined in Appendix B.2.1. of [RFC8017]. Future specifications can introduce other variants as desired. The named variants are as follows:¶
- RSABSSA
-SHA384 -PSS -Randomized : - This named variant uses SHA-384 as the EMSA-PSS Hash option,
MGF1 with SHA-384 as the EMSA-PSS MGF option, and 48 as the EMSA-PSS sLen option (48-byte salt length); it also uses
the randomized preparation function
(Prepare Randomize ). ¶ - RSABSSA
-SHA384 -PSSZERO -Randomized : - This named variant uses SHA-384 as the EMSA-PSS Hash option,
MGF1 with SHA-384 as the EMSA-PSS MGF option, and 0 as the EMSA-PSS sLen option (0-byte salt length); it also uses
the randomized preparation function
(Prepare Randomize ). ¶ - RSABSSA
-SHA384 -PSS -Deterministic : - This named variant uses SHA-384 as the EMSA-PSS Hash option,
MGF1 with SHA-384 as the EMSA-PSS MGF option, and 48 as the EMSA-PSS sLen option (48-byte salt length); it also uses
the identity preparation function
(Prepare Identity ). ¶ - RSABSSA
-SHA384 -PSSZERO -Deterministic : - This named variant uses SHA-384 as the EMSA-PSS Hash option,
MGF1 with SHA-384 as the EMSA-PSS MGF option, and 0 as the EMSA-PSS sLen option (0-byte salt length); it also uses
the identity preparation function
(Prepare Identity ). This is the only variant that produces deterministic signatures over the client's input message msg.¶
The RECOMMENDED variants are RSABSSA
Not all named variants can be used interchangeably
Applications that require deterministic signatures can use the RSABSSA
6. Implementation and Usage Considerations
This section documents considerations for interfaces to implementations of the protocol defined in this document. This includes error handling and API considerations.¶
6.1. Errors
The high-level functions specified in Section 4 are all fallible. The explicit errors generated throughout this specification, along with the conditions that lead to each error, are listed in the definitions for Blind, BlindSign, and Finalize. These errors are meant as a guide for implementors. They are not an exhaustive list of all the errors an implementation might emit. For example, implementations might run out of memory.¶
Moreover, implementations can handle errors as needed or desired. Where applicable, this document provides guidance for how to deal with explicit errors that are generated in the protocol. For example, a "blinding error" error is generated in Blind when the client produces a prime factor of the server's public key. Section 4.2 indicates that implementations SHOULD retry the Blind function when this error occurs, but an implementation could also handle this exceptional event differently, e.g., by informing the server that the key has been factored.¶
6.2. Signing Key Generation and Usage
The RECOMMENDED method for generating the server signing key pair is as specified in FIPS 186-5 [DSS].¶
A server signing key MUST NOT be reused for any other protocol beyond RSABSSA. Moreover, a server signing key MUST NOT be reused for different RSABSSA encoding options. That is, if a server supports two different encoding options, then it MUST have a distinct key pair for each option.¶
If the server public key is carried in an X.509 certificate, it MUST use the id-RSASSA-PSS OID [RFC5756]. It MUST NOT use the rsaEncryption OID [RFC5280].¶
7. Security Considerations
Lysyanskaya proved one
7.1. Timing Side Channels and Fault Attacks
BlindSign is functionally a remote procedure call for applying the RSA private
key operation. As such, side-channel resistance is paramount to protect the private key
from exposure [Remote
Moreover, we assume that the server does not initiate the protocol and therefore has no knowledge of when the Prepare and Blind operations take place. If this were not the case, additional side-channel mitigations might be required to prevent timing side channels through Prepare and Blind.¶
Beyond timing side channels, [FAULTS] describes the importance of implementation safeguards that protect against fault attacks that can also leak the private signing key. These safeguards require that implementations check that the result of the private key operation when signing is correct, i.e., given s = RSASP1(sk, m), verify that m = RSAVP1(pk, s), as is required by BlindSign. Applying this (or an equivalent) safeguard is necessary to mitigate fault attacks, even for implementations that are not based on the Chinese remainder theorem.¶
7.2. Message Robustness
An essential property of blind signature protocols is that the signer learns nothing of the message being signed. In some circumstances, this may raise concerns regarding arbitrary signing oracles. Applications using blind signature protocols should take precautions to ensure that such oracles do not cause cross-protocol attacks. Ensuring that the signing key used for RSABSSA is distinct from other protocols prevents such cross-protocol attacks.¶
An alternative solution to this problem of message blindness is to give signers proof that the message being signed is well structured. Depending on the application, zero-knowledge proofs could be useful for this purpose. Defining such proofs is out of scope for this document.¶
Verifiers should check that, in addition to signature validity, the signed message is well structured for the relevant application. For example, if an application of this protocol requires messages to be structures of a particular form, then verifiers should check that messages adhere to this form.¶
7.3. Message Entropy
As discussed in [Lys22], a malicious signer can construct an invalid public key and use it to learn information about low-entropy input messages. Note that some invalid public keys may not yield valid signatures when run with the protocol, e.g., because the signature fails to verify. However, if an attacker can coerce the client to use these invalid public keys with low-entropy inputs, they can learn information about the client inputs before the protocol completes.¶
A client that uses this protocol might be vulnerable to attack from a malicious signer unless it is able to ensure that one of the following conditions is satisfied:¶
- (1)
- The client has proof that the signer's public key is honestly generated. [GRSB19] presents
some
(non -interactive ) honest-verifier zero-knowledge proofs of various statements about the public key.¶ - (2)
- The input message has a value that the signer is unable to guess. That is, the client has added a high-entropy component that was not available to the signer prior to them choosing their signing key.¶
The named variants that use the Prepare
Note that these variants effectively mean that the resulting signature is always randomized. As such, this interface is not suitable for applications that require deterministic signatures.¶
7.4. Randomness Generation
All random values in the protocol, including the salt, message randomizer prefix (msg_prefix; see Appendix A), and random blind
value in Blind, MUST be generated from a cryptographical
Note that malicious implementations could also encode client information in the message being signed, but since clients can verify the resulting message signature using the public key, this can be detected.¶
7.5. Key Substitution Attacks
RSA is well known for permitting key substitution attacks, wherein an attacker generates a key pair (skA, pkA) that verifies some known (message, signature) pair produced under a different (sk, pk) key pair [WM99]. This means it may be possible for an attacker to use a (message, signature) pair from one context in another. Entities that verify signatures must take care to ensure that a (message, signature) pair verifies with a valid public key from the expected issuer.¶
7.6. Alternative RSA Encoding Functions
This document uses PSS encoding as specified in [RFC8017] for a number of
reasons. First, it is recommended in recent standards, including TLS 1.3 [RFC8446],
X.509 [RFC4055], and even PKCS #1 itself. According to [RFC8017],
"Although no attacks are known against RSASSA
Full Domain Hash (FDH) encoding [RSA-FDH] is also possible. This variant provides security equivalent to that of PSS [KK18]. However, FDH is less standard and is not used widely in related technologies. Moreover, FDH is deterministic, whereas PSS supports deterministic and probabilistic encodings.¶
7.7. Post-Quantum Readiness
The blind signature protocol specified in this document is not post-quantum ready, since it is based on RSA. Shor's polynomial-time factorization algorithm readily applies.¶
8. IANA Considerations
This document has no IANA actions.¶
9. References
9.1. Normative References
- [RFC2119]
-
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10
.17487 , , <https:///RFC2119 www >..rfc -editor .org /info /rfc2119 - [RFC5756]
-
Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, "Updates for RSAES-OAEP and RSASSA-PSS Algorithm Parameters", RFC 5756, DOI 10
.17487 , , <https:///RFC5756 www >..rfc -editor .org /info /rfc5756 - [RFC8017]
-
Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10
.17487 , , <https:///RFC8017 www >..rfc -editor .org /info /rfc8017 - [RFC8174]
-
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10
.17487 , , <https:///RFC8174 www >..rfc -editor .org /info /rfc8174
9.2. Informative References
- [Apple
Private Relay] -
"iCloud Private Relay Overview", , <https://
www >..apple .com /icloud /docs /i Cloud _Private _Relay _Overview _Dec2021 .pdf - [Chaum83]
-
Chaum, D., "Blind Signatures for Untraceable Payments", Springer-Verlag, , <https://
sceweb >..sce .uhcl .edu /yang /teaching /csci5234Web Security Fall2011 /Chaum -blind -signatures .PDF - [DSS]
-
"Digital Signature Standard (DSS)", National Institute of Standards and Technology report, DOI 10
.6028 , , <https:///nist .fips .186 -5 doi >..org /10 .6028 /NIST .FIPS .186 -5 - [FAULTS]
-
Boneh, D., DeMillo, R. A., and R. J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults", Advances in Cryptology - EUROCRYPT '97, pp. 37-51, DOI 10
.1007 , , <https:///3 -540 -69053 -0 _4 doi >..org /10 .1007 /3 -540 -69053 -0 _4 - [GoogleVPN]
-
"VPN by Google One, explained", <https://
one >..google .com /about /vpn /howitworks - [GRSB19]
-
Goldberg, S., Reyzin, L., Sagga, O., and F. Baldimtsi, "Efficient Noninteractive Certification of RSA Moduli and Beyond", , <https://
eprint >..iacr .org /2018 /057 .pdf - [JKK14]
-
Jarecki, S., Kiayias, A., and H. Krawczyk, "Round-Optimal Password
-Protected , , <https://Secret Sharing and T-PAKE in the Password-Only Model" eprint >..iacr .org /2014 /650 - [JKM18]
-
Jager, T., Kakvi, S. A., and A. May, "On the Security of the PKCS#1 v1.5 Signature Scheme", Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 1195-1208, DOI 10
.1145 , , <https:///3243734 .3243798 eprint >..iacr .org /2018 /855 - [KK18]
-
Kakvi, S. A. and E. Kiltz, "Optimal Security Proofs for Full Domain Hash, Revisited", Journal of Cryptology, vol. 31, no. 1, pp. 276-306, DOI 10
.1007 , , <https:///s00145 -017 -9257 -9 doi >..org /10 .1007 /s00145 -017 -9257 -9 - [Lys22]
-
Lysyanskaya, A., "Security Analysis of RSA-BSSA", , <https://
eprint >..iacr .org /2022 /895 - [Pretty
Good Phone Privacy] -
Schmitt, P. and B. Raghavan, "Pretty Good Phone Privacy", Proceedings of the 30th USENIX Security Symposium, , <https://
www >..usenix .org /conference /usenixsecurity2 1 /presentation /schmitt - [PRIVACY-PASS]
-
Celi, S., Davidson, A., Valdez, S., and C. A. Wood, "Privacy Pass Issuance Protocol", Work in Progress, Internet-Draft, draft
-ietf , , <https://-privacypass -protocol -16 datatracker >..ietf .org /doc /html /draft -ietf -privacypass -protocol -16 - [Remote
Timing Attacks] -
Brumley, D. and D. Boneh, "Remote Timing Attacks are Practical", Proceedings of the 12th USENIX Security Symposium, , <https://
www >..usenix .org /legacy /events /sec03 /tech /brumley /brumley .pdf - [RFC4055]
-
Schaad, J., Kaliski, B., and R. Housley, "Additional Algorithms and Identifiers for RSA Cryptography for use in the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 4055, DOI 10
.17487 , , <https:///RFC4055 www >..rfc -editor .org /info /rfc4055 - [RFC4086]
-
Eastlake 3rd, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, DOI 10
.17487 , , <https:///RFC4086 www >..rfc -editor .org /info /rfc4086 - [RFC5280]
-
Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., and W. Polk, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 5280, DOI 10
.17487 , , <https:///RFC5280 www >..rfc -editor .org /info /rfc5280 - [RFC8446]
-
Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10
.17487 , , <https:///RFC8446 www >..rfc -editor .org /info /rfc8446 - [RSA-FDH]
-
Bellare, M. and P. Rogaway, "Random oracles are practical: a paradigm for designing efficient protocols", CCS '93: Proceedings of the 1st ACM conference on Computer and communications security, pp. 62-73, DOI 10
.1145 , , <https:///168588 .168596 dl >..acm .org /doi /abs /10 .1145 /168588 .168596 - [TimingAttacks]
-
Kocher, P. C., "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems", Advances in Cryptology - CRYPTO '96, pp. 104-113, DOI 10
.1007 , , <https:///3 -540 -68697 -5 _9 doi >..org /10 .1007 /3 -540 -68697 -5 _9 - [VOPRF]
-
Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A. Wood, "Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups", Work in Progress, Internet-Draft, draft
-irtf , , <https://-cfrg -voprf -21 datatracker >..ietf .org /doc /html /draft -irtf -cfrg -voprf -21 - [WM99]
-
Blake-Wilson, S. and A. Menezes, "Unknown Key-Share Attacks on the Station
-to , International Workshop on Public Key Cryptography, PKC 1999, pp. 154-170, DOI 10-Station (STS) Protocol" .1007 , , <https:///3 -540 -49162 -7 _12 link >..springer .com /chapter /10 .1007 /3 -540 -49162 -7 _12
Appendix A. Test Vectors
This section includes test vectors for the blind signature protocol defined in Section 4. The following parameters are specified for each test vector:¶
- p, q, n, e, d:
- RSA private and public key (sk and pk) parameters, each encoded as a hexadecimal string.¶
- msg:
- Input message being signed, encoded as a hexadecimal string. The hash is computed using SHA-384.¶
- msg_prefix:
- Message randomizer prefix, encoded as a hexadecimal string. This is only present for variants that use the randomization preparation function.¶
- prepared_msg:
- The message actually signed. If the variant does not use the randomization preparation function, this is equal to msg.¶
- salt:
- Randomly generated salt used when computing the signature. The length is either 48 or 0 bytes.¶
- encoded_msg:
- EMSA-PSS encoded message. The mask generation function is MGF1 with SHA-384.¶
- inv:
- The message blinding inverse, encoded as a hexadecimal string.¶
- blinded_msg, blind_sig:
- The protocol values exchanged during the computation, encoded as hexadecimal strings.¶
- sig:
- The output message signature.¶
Acknowledgments
We would like to thank Bjoern Tackmann, who provided an editorial and security review of this document.¶