Community hub
0 subscribers7 pages, 0 posts
Recent from talks
All channels
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Probabilistic signature scheme.
Nothing was collected or created yet.
Probabilistic signature scheme
View on Wikipediafrom Wikipedia
Probabilistic Signature Scheme (PSS) is a cryptographic signature scheme designed by Mihir Bellare and Phillip Rogaway.[1]
RSA-PSS is an adaptation of their work and is standardized as part of PKCS#1 v2.1. In general, RSA-PSS should be used as a replacement for RSA-PKCS#1 v1.5.
Design
[edit]PSS was specifically developed to allow modern methods of security analysis to prove that its security directly relates to that of the RSA problem. There is no such proof for the traditional PKCS#1 v1.5 scheme.
Implementations
[edit]References
[edit]- ^ Bellare, Mihir; Rogaway, Phillip. "PSS: Provably Secure Encoding Method for Digital Signatures" (PDF). Archived from the original (PDF) on 2017-08-10.
- ^ "RSA-PSS". OpenSSL Documentation. Retrieved April 7, 2025.
- ^ "wolfSSL Changelog | wolfSSL Embedded SSL/TLS Library Documentation". wolfSSL. Retrieved 2018-10-05.
External links
[edit]Probabilistic signature scheme
View on Grokipediafrom Grokipedia
Overview
Definition and Motivation
A probabilistic signature scheme is a type of digital signature algorithm that incorporates randomness into the signing process, typically via random salts or nonces, to generate distinct signatures for identical messages, thereby bolstering resistance to specific cryptographic attacks.[6] Unlike deterministic schemes, this probabilistic element ensures that the output varies with each signing operation, even for the same input, while maintaining verifiability.[6] At its core, such a scheme comprises three algorithms: key generation to produce public and private key pairs, a probabilistic signing algorithm that uses randomness to compute the signature, and a deterministic verification algorithm to check signature validity.[6] The primary motivation for probabilistic signature schemes arose from the limitations of earlier deterministic RSA-based signatures, such as those in PKCS#1 v1.5, which employ fixed padding and lack tight provable security guarantees under standard assumptions like the hardness of the RSA problem.[7] These deterministic methods have been analyzed for potential vulnerabilities in adaptive chosen-message scenarios, though practical forgery remains infeasible under standard assumptions.[8] By introducing randomness, probabilistic schemes render signatures non-malleable, thwarting such attacks and providing security reductions that are asymptotically tight to the underlying trapdoor function, often RSA.[6] In contrast to deterministic schemes, where signing the same message invariably yields the identical signature—potentially exposing risks like replay attacks or easier forgery in multi-user environments—probabilistic approaches mitigate these issues by ensuring signature uniqueness per signing instance.[7] This design not only enhances overall robustness but also aligns with modern standards recommending probabilistic methods for critical applications.[9]Historical Development
The probabilistic signature scheme (PSS) was introduced by Mihir Bellare and Phillip Rogaway in their 1996 EUROCRYPT paper, "The Exact Security of Digital Signatures: How to Sign with RSA and Rabin," as a response to vulnerabilities in earlier RSA-based signature schemes and to provide provable security in the random oracle model.[6] This work built on their prior development of optimal asymmetric encryption padding (OAEP) from 1994, adapting similar probabilistic padding techniques to signatures to achieve tight security bounds against existential forgery under chosen-message attacks. PSS was formalized as RSASSA-PSS in PKCS #1 version 2.0, released by RSA Laboratories in 1998, which integrated it into standardized RSA cryptography specifications alongside OAEP for encryption.[10] By the early 2000s, IETF efforts advanced its adoption, with PKCS #1 version 2.1 published as RFC 3447 in 2003, refining parameters and aligning with emerging standards.[2] Further evolution included its specification for use in the Cryptographic Message Syntax (CMS) via RFC 4056 in 2005, enabling broader deployment in secure email and document signing protocols.[11] PKCS #1 version 2.2, issued in 2016, incorporated errata and updated supported hash functions (e.g., adding SHA-2 variants) to address implementation inconsistencies and enhance compatibility with FIPS standards.[12] Key milestones include the 1996 proposal establishing provable security foundations, early 2000s IETF standardization solidifying its role in protocols, and the 2020s shift toward post-quantum cryptography—yet PSS remains the dominant scheme for RSA-based signatures in legacy and hybrid systems.Technical Description
Core Components
Probabilistic signature schemes, such as the Probabilistic Signature Scheme (PSS), fundamentally rely on a trapdoor permutation as their core cryptographic primitive, most commonly the RSA function, which is based on modular exponentiation using a public exponent and a large composite modulus where and are large primes.[6] This trapdoor structure allows efficient computation in one direction (encryption or signing with the public key) while assuming the computational hardness of inverting the function without the private key, providing the foundational security assumption for the scheme.[6] Additionally, the scheme incorporates cryptographic hash functions, such as SHA-256, to digest input messages and generate masks, ensuring collision resistance and one-way properties essential for secure encoding.[12] Key parameters in a probabilistic signature scheme include the RSA key pair: a public key consisting of the modulus and exponent , and a private key such that , where is Euler's totient function.[12] The scheme also specifies a salt of length , a parameter typically equal to the hash output length (e.g., 20 bytes for SHA-1, 32 bytes for SHA-256) to achieve optimal security as recommended in the standard, which introduces randomness during signing.[12] Furthermore, it employs hash function families for general hashing (e.g., producing message digests) and for mask generation, often implemented as the Mask Generation Function 1 (MGF1) derived from , allowing flexibility while maintaining provable security properties.[6] In message encoding, the input message is first hashed using to produce a fixed-length digest, which is then probabilistically padded by incorporating the salt and additional randomness before applying the trapdoor permutation, ensuring that signatures for the same message vary to thwart certain forgery attacks.[6] The scheme's security hinges on the presumed difficulty of inverting the RSA trapdoor function under chosen-ciphertext attacks, a hardness assumption formalized in the original PSS design.[6] In the standardized RSASSA-PSS variant, the scheme operates as a "signature with appendix," requiring the verifier to process both the signature and the full original message during validation, rather than recovering the message from the signature alone.[12]Signing and Verification Algorithms
In probabilistic signature schemes such as RSASSA-PSS, key generation follows the standard RSA procedure. Two large distinct primes and are selected such that , where is the modulus. A public exponent is chosen such that and , with . The private exponent is then computed as . The public key consists of , while the private key is or an equivalent representation such as for efficiency, where , , and .[13] The signing algorithm, RSASSA-PSS-SIGN, takes as input a message (an octet string), the private key , a hash function with output length octets, a mask generation function , and a salt length . First, the message is hashed to produce . A random salt of length octets is generated. An auxiliary string is formed, where denotes eight zero octets, and then is computed. The padding string is constructed as a string of zero octets followed by the octet and then the salt, where and is the bit length of minus 1. A mask is generated, and the masked data block is . The leftmost bits of are set to zero. The encoded message is then . This is converted to an integer , and the signature is computed as , where RSASP1 performs the RSA computation using the private key (typically or using the Chinese Remainder Theorem for efficiency). Finally, the signature is output, where is the octet length of . If the message is too long or encoding fails, an error is returned.[14][15] For pseudocode representation, the core signing process can be outlined as follows:RSASSA-PSS-SIGN(K, M, Hash, MGF, sLen):
mHash = Hash(M)
if bit length of M > emBits - 8hLen - 8sLen - 9:
return "message too long"
salt = random octet string of length sLen
M' = 0^8 || mHash || salt
H = Hash(M')
DB = 0^(emLen - sLen - hLen - 2) || 0x01 || salt
dbMask = MGF(H, emLen - hLen - 1)
maskedDB = DB XOR dbMask
set leftmost 8emLen - emBits bits of maskedDB to 0
EM = maskedDB || H || 0xBC
m = OS2IP(EM)
s = RSASP1(K, m)
S = I2OSP(s, k)
return S
RSASSA-PSS-SIGN(K, M, Hash, MGF, sLen):
mHash = Hash(M)
if bit length of M > emBits - 8hLen - 8sLen - 9:
return "message too long"
salt = random octet string of length sLen
M' = 0^8 || mHash || salt
H = Hash(M')
DB = 0^(emLen - sLen - hLen - 2) || 0x01 || salt
dbMask = MGF(H, emLen - hLen - 1)
maskedDB = DB XOR dbMask
set leftmost 8emLen - emBits bits of maskedDB to 0
EM = maskedDB || H || 0xBC
m = OS2IP(EM)
s = RSASP1(K, m)
S = I2OSP(s, k)
return S
RSASSA-PSS-VERIFY((n, e), M, S, Hash, MGF, sLen):
if length of S ≠ k:
return "invalid signature"
s = OS2IP(S)
m = RSAVP1((n, e), s)
EM = I2OSP(m, emLen)
mHash = Hash(M)
if emLen < hLen + sLen + 2 or EM[emLen] ≠ 0xBC:
return "invalid signature"
maskedDB = EM[1..emLen - hLen - 1]
H = EM[emLen - hLen .. emLen - 1]
if leftmost 8emLen - emBits bits of maskedDB ≠ 0:
return "invalid signature"
dbMask = MGF(H, emLen - hLen - 1)
DB = maskedDB XOR dbMask
set leftmost 8emLen - emBits bits of DB to 0
if DB[1 .. emLen - sLen - hLen - 2] ≠ all zeros or DB[emLen - sLen - hLen - 1] ≠ 0x01:
return "invalid signature"
salt = DB[emLen - sLen - hLen .. emLen - hLen - 1]
M' = 0^8 || mHash || salt
H' = Hash(M')
if H' = H:
return "valid signature"
else:
return "invalid signature"
RSASSA-PSS-VERIFY((n, e), M, S, Hash, MGF, sLen):
if length of S ≠ k:
return "invalid signature"
s = OS2IP(S)
m = RSAVP1((n, e), s)
EM = I2OSP(m, emLen)
mHash = Hash(M)
if emLen < hLen + sLen + 2 or EM[emLen] ≠ 0xBC:
return "invalid signature"
maskedDB = EM[1..emLen - hLen - 1]
H = EM[emLen - hLen .. emLen - 1]
if leftmost 8emLen - emBits bits of maskedDB ≠ 0:
return "invalid signature"
dbMask = MGF(H, emLen - hLen - 1)
DB = maskedDB XOR dbMask
set leftmost 8emLen - emBits bits of DB to 0
if DB[1 .. emLen - sLen - hLen - 2] ≠ all zeros or DB[emLen - sLen - hLen - 1] ≠ 0x01:
return "invalid signature"
salt = DB[emLen - sLen - hLen .. emLen - hLen - 1]
M' = 0^8 || mHash || salt
H' = Hash(M')
if H' = H:
return "valid signature"
else:
return "invalid signature"
Padding Mechanism
The padding mechanism in the Probabilistic Signature Scheme (PSS) employs a randomized encoding process, known as EMSA-PSS, to prepare the message for RSA signing while incorporating entropy to thwart existential forgery attacks under chosen-message scenarios. This mechanism produces an encoded message EM of fixed length emLen octets, where emLen equals the octet length of the RSA modulus n (typically emLen = \lceil k / 8 \rceil, with k denoting the bit length of n). The structure ensures the padded output is indistinguishable from random, leveraging a hash function and a mask generation function (MGF) for security.[2] The construction begins with computing mHash = Hash(m), where Hash is a cryptographic hash function producing hLen octets of output. A random salt, an octet string of length sLen, is generated; sLen ranges typically from 0 to hLen, but hLen is recommended to achieve the tightest security bounds in the proof. The value M' is formed as the concatenation of eight zero octets || mHash || salt, and H = Hash(M') is computed. The data block DB follows as PS || 0x01 || salt, where PS consists of emLen - sLen - hLen - 2 zero octets. A mask dbMask = MGF(H, emLen - hLen - 1) is then derived using the MGF (e.g., MGF1, an iterated hash-based function), and maskedDB = DB \oplus dbMask is calculated, with the leftmost bits of maskedDB padded to zero if emLen does not divide evenly by the bit length requirement. Finally, the encoded message is where 0xbc serves as a fixed trailer octet (the DER encoding of the value 188, signaling the end of the structure). This yields EM of exactly emLen octets.[2] The salt introduces essential randomness, ensuring distinct signatures for identical messages and randomizing the input to the final hash H, which enhances resistance to adaptive attacks. The MGF generates a pseudorandom mask via iterative hashing (e.g., applying Hash repeatedly with counter suffixes), XORing it across the DB to obscure the positions of the fixed 0x01, salt, and PS, thereby distributing randomness throughout most of EM while preserving verifiability via the unmasked H and trailer. This design, formalized in PKCS#1 standards, originates from the provably secure PSS encoding by Bellare and Rogaway, adapted for practical deployment with explicit padding parameters.[2][6]Security Properties
Provable Security Model
The security of the probabilistic signature scheme (PSS) is formally analyzed within the random oracle model (ROM), where hash functions such as and the mask generation function (MGF) are idealized as random oracles mapping inputs to uniformly random outputs. This model facilitates provable security guarantees by simulating ideal hash behavior, avoiding reliance on specific hash function properties. The core security goal for PSS is existential unforgeability under chosen-message attack (EUF-CMA), which requires that no efficient adversary, given access to a signing oracle for adaptively chosen messages, can produce a valid signature on a fresh message.[6] The foundational security proof for PSS employs a reduction from the EUF-CMA security of the scheme to the hardness of the RSA inversion problem, as established by Bellare and Rogaway. Specifically, any adversary that forges a PSS signature with non-negligible probability can be transformed into an algorithm that inverts an RSA challenge (i.e., given -th power residue , computes ) with probability , up to negligible terms. This reduction is tight, incurring only constant overhead in success probability and polynomial loss in running time, unlike looser reductions in prior schemes like full-domain hash (FDH). The forgery probability is further bounded as , where and are the numbers of signing and hash queries, and , are output lengths related to the salt and hash; with salt length for security parameter , the term ensures the additional probability is negligible.[6] A key theorem states that if RSA is secure against efficient inversion (no polynomial-time algorithm succeeds with non-negligible probability), then PSS is EUF-CMA-secure in the ROM, with the reduction preserving tightness via constant factors in the security loss. The original 1996 proof by Bellare and Rogaway relies on random oracles for (mapping to fixed-length outputs) and MGF (derived from another oracle ). Later refinements, such as those by Coron in 2002, optimize the proof to achieve equivalent security with a shorter salt of length , maintaining the tight reduction in the ROM; efforts to extend proofs to the standard model, including early analyses around 2000, yield only loose bounds with exponential security loss, reinforcing PSS's practical reliance on the ROM.[6][18]Advantages Over Deterministic Schemes
Probabilistic signature schemes, such as RSA-PSS, incorporate randomness through mechanisms like salts and masks, which provide significant advantages over deterministic schemes like RSA-PKCS#1 v1.5 by mitigating vulnerabilities that exploit predictable padding and outputs.[6] In particular, the randomness thwarts multi-collision attacks that rely on the fixed structure of deterministic paddings; for instance, Bleichenbacher's 1998 adaptive chosen-ciphertext attack on PKCS#1 v1.5 padding exploited oracle responses to recover plaintexts by iteratively refining invalid ciphertexts, a risk analogous to signature forgeries in deterministic settings where partial information leaks. Deterministic signatures are susceptible to chosen-message forgeries when partial signature information is compromised, as attackers can exploit the invariance to craft valid signatures for related messages; PSS counters this by using a random salt to generate unique, varying outputs for the same message, ensuring that even with leaked partial data, forgeries remain computationally infeasible under the EUF-CMA model.[6] Compared to RSA-PKCS#1 v1.5, which lacks provable security and admits known forgeries—such as those on low-exponent RSA with related messages demonstrated by Coppersmith et al.—PSS offers tight provable security in the random oracle model, albeit with slightly longer signatures due to the additional random bits (typically 8-32 bytes for the salt).[9] In practice, PSS reduces signature malleability, where an attacker might modify a valid deterministic signature to produce another valid one without the private key, making it particularly suitable for applications like blind signing that require non-revealing message processing without compromising security.[6]Implementations and Applications
Standardization and Protocols
Probabilistic signature schemes, exemplified by RSASSA-PSS, were first formally defined in PKCS#1 version 2.1 by RSA Laboratories in 2002, with subsequent revisions incorporating refinements to the scheme's structure and parameters.[2] This standard established RSASSA-PSS as a randomized alternative to deterministic padding methods, emphasizing its role in enhancing security through probabilistic encoding.[2] The Internet Engineering Task Force (IETF) further standardized RSASSA-PSS for integration into broader cryptographic frameworks, notably in RFC 4056 published in 2005, which specifies its use within the Cryptographic Message Syntax (CMS) and Public-Key Infrastructure X.509 (PKIX) environments.[11] Building on this, RFC 8017 in 2016 updated PKCS#1 to version 2.2, providing clearer definitions for PSS parameters such as the mask generation function and salt length to ensure consistent implementation across systems.[12] In protocol integrations, RSASSA-PSS plays a key role in secure communications. The Transport Layer Security (TLS) Protocol version 1.3, as defined in RFC 8446, mandates RSASSA-PSS for RSA-based server authentication in the CertificateVerify message, requiring schemes like rsa_pss_rsae_sha256 for verifying handshake integrity.[19] Similarly, the XML Signature Syntax and Processing (XMLDSig) specification supports RSASSA-PSS as an optional RSA signature algorithm, identified by the URI http://www.w3.org/2007/05/xmldsig-more#rsa-pss, for signing XML documents in web services and data interchange.[20] For email security, S/MIME version 4.0 incorporates RSASSA-PSS via CMS in RFC 8551, recommending its use with SHA-256 for signing messages to provide authenticity and non-repudiation.[21] Additionally, FIPS 186-4 from NIST in 2013 approves RSASSA-PSS as a required mode for RSA digital signatures in federal systems, ensuring compliance with approved cryptographic primitives; this was updated in FIPS 186-5 (2023) to integrate PSS with post-quantum signature schemes like Dilithium.[22][23] Parameter recommendations in these standards emphasize robustness: the hash function H must be from a secure family such as SHA-2 (e.g., SHA-256), the salt length should match the hash output length (typically 32 octets for SHA-256), and the encoded message length emLen must equal the RSA modulus size in octets.[12] Both RSASSA-PSS and RSASSA-PKCS1-v1.5 are approved for cryptographic module validations under FIPS 140-3. RSASSA-PSS thus serves as the primary instantiation of probabilistic signature schemes across these formal standards.Practical Implementations
Probabilistic signature schemes, particularly RSASSA-PSS, are implemented in several widely used cryptographic libraries to facilitate secure digital signing and verification. OpenSSL provides support for RSASSA-PSS through its EVP interface, including functions such asEVP_PKEY_sign and EVP_PKEY_verify with PSS padding, introduced in version 1.0.1. Bouncy Castle, a Java cryptography library, offers the PSSSigner class for generating and verifying RSASSA-PSS signatures, integrating mask generation functions like MGF1.[24] In Python, PyCryptodome implements RSASSA-PSS via the PKCS1_PSS module, which supports customizable hash algorithms and defaults to MGF1 for the mask generation step.[25]
Deploying RSASSA-PSS requires careful attention to key management and randomness to maintain security. Current recommendations from NIST specify RSA key sizes of at least 2048 bits for signatures, providing adequate protection against classical attacks until at least 2030. Salt values, which introduce randomness into the padding, must be generated using a cryptographically secure pseudorandom number generator (CSPRNG) to ensure the scheme's probabilistic properties and resistance to forgery. A notable implementation pitfall involves improper handling of the mask generation function (MGF) chaining, which can expose padding oracles.
Practical tools in various languages simplify RSASSA-PSS usage. Go's crypto/rsa package includes the SignPSS function for signing hashed messages with PSS padding, paired with VerifyPSS for validation, making it suitable for server-side applications.[26] In blockchain contexts, RSASSA-PSS serves as a fallback for RSA-based signatures in protocols that occasionally require legacy compatibility.
As of 2025, RSASSA-PSS is mandated for RSA signatures in TLS 1.3 handshake messages such as CertificateVerify, while certificate chain signatures may still use PKCS#1 v1.5 under CA/Browser Forum baselines, though PSS is increasingly preferred. Meanwhile, migrations to quantum-resistant alternatives like Dilithium are underway in response to NIST's post-quantum cryptography standards, with organizations planning hybrid schemes by 2030 while PSS remains dominant for legacy RSA systems.