Salt, Hash, and MGF1: What RSA-PSS Adds to the Verification Step

A textbook RSA signature on a message $m$ is an $e$-th root: the signer computes $\sigma = m^{d} \bmod N$ with the private exponent, and the verifier checks that $\sigma^{e} \bmod N$ equals the padded message representative. Two things are wrong with applying that directly to a message. The message is almost always shorter than the modulus, so the mapping to an integer is ambiguous. And raw RSA is multiplicatively homomorphic, so the signature on $m_1 m_2 \bmod N$ is the product of the signatures on $m_1$ and $m_2$, which lets an attacker construct a signature they never asked for from two signatures they did.

Padding fixes both. PKCS #1 v1.5 was the original answer and is still widespread; the Probabilistic Signature Scheme, from Bellare and Rogaway and standardised in RFC 8017, is the version with a proof.

The encoded message

PSS takes a message and produces a fixed-size integer, the encoded message, which is then raised to the private exponent as before. For an RSA modulus of $k$ bytes and a hash of output length $h$, the encoded message is $k$ bytes long, and the layout from most significant byte to least is:

• $k - h - 1$ bytes of masked data, written $\mathrm{maskedDB}$
• the $h$-byte hash $H$ of a string derived from the message and the salt
• one trailer byte 0xbc

There is no plaintext framing prefix. The leftmost bits of the encoded message are forced to zero so that the integer is less than the modulus: after masking, the encoder clears the top $8k - (\mathrm{modBits} - 1)$ bits of the first byte of $\mathrm{maskedDB}$, and the decoder checks that they are still zero after unmasking. The single trailer byte 0xbc is what distinguishes a PSS encoding from a v1.5 encoding, which begins 0x00 0x01 and is followed by 0xff bytes. The parser must verify each field’s constraints rather than merely locate the marker: finding the first 0x01 is not enough unless every byte before it is confirmed zero.

The masked data is where the structure lives. Before masking, the data block $DB$ of length $k - h - 1$ is

$$DB = \texttt{0x00}^{k - s - h - 2} ,|, \texttt{0x01} ,|, \mathrm{salt}$$

with $s$ the salt length. A run of zero bytes comes first, then a single 0x01 marking where the salt begins, then the salt itself. The zero run may be empty when the salt is at its maximum length, which is $k - h - 2$ bytes, so a decoder cannot assume at least one zero before the marker. This ordering is the reverse of the v1.5 block, which puts the 0x01 marker at the front and pads with 0xff after it.

The MGF and the masked database

The interesting part is what $H$ is. PSS does not set $H$ to the plain hash of the message. It computes

$$M’ = \texttt{0x00}^{8} ,|, mHash ,|, salt$$

where $mHash$ is the hash of the message and the eight zero bytes are there to make $M’$ a fixed length regardless of salt length. Then $H = \mathrm{Hash}(M’)$. The message hash is embedded in $H$ rather than placed in the encoded message directly, which is why the verifier cannot read it out; it must recover the salt, reconstruct $M’$, and rehash.

Recovering the salt requires a mask. The data block $DB$ of length $k - h - 1$ holds the zero run, the 0x01 marker, and the salt. It is masked by XOR with a string generated from $H$ using a mask generation function, MGF1, which is a counter-mode hash: $\mathrm{MGF1}(seed, len)$ computes $\mathrm{Hash}(seed ,|, \mathrm{counter})$ for counter values $0, 1, 2, \dots$ encoded as four-byte big-endian integers, concatenates the outputs, and truncates to $len$. The encoded message is $\mathrm{maskedDB} ,|, H ,|, \texttt{0xbc}$, with $\mathrm{maskedDB} = DB \oplus \mathrm{MGF1}(H, k-h-1)$.

def mgf1(seed: bytes, length: int, hash_name: str = "sha256") -> bytes:
    out = b""
    counter = 0
    while len(out) < length:
        out += hashlib.new(hash_name, seed + counter.to_bytes(4, "big")).digest()
        counter += 1
    return out[:length]

def pss_verify_em(em: bytes, msg_hash: bytes, h_len: int) -> bool:
    # em is the k-byte encoded message recovered as sig^e mod N
    if em[-1] != 0xBC:
        return False
    masked_db = em[: len(em) - h_len - 1]
    h = em[len(em) - h_len - 1 : -1]
    db = bytes(a ^ b for a, b in zip(masked_db, mgf1(h, len(masked_db))))
    sep = db.find(0x01)          # first non-zero byte marks the salt
    if sep < 0 or any(db[:sep]): # everything before it must be zero
        return False
    salt = db[sep + 1 :]
    return hashlib.sha256(b"\x00" * 8 + msg_hash + salt).digest() == h

The comparison on the last line must be constant-time in a real implementation, for the reason given in the MAC and signature split. The code above also omits the unused-bit check: RFC 8017 clears the leftmost $8k - (\mathrm{modBits} - 1)$ bits of $\mathrm{maskedDB}$ during encoding, and the decoder must verify that they are still zero after unmasking, because a modulus whose bit length is not a multiple of eight leaves spare bits at the top of the first byte.

Why the salt is what makes it provable

The salt is random bytes, $s$ of them, generated fresh for each signature. Two signatures on the same message under the same key therefore differ, and both verify. That non-determinism is the point.

Without a salt, the encoding is a deterministic function of the message hash. An attacker who can find any two messages whose encodings collide gets a signature on one for free from the other, and the security proof for the scheme reduces to collision resistance of the hash, which is not enough for a tight bound. With the salt, the encoded message has $8s$ bits of entropy, and the proof can reduce forgery to inverting RSA on a random value: the simulator picks the salt, chooses $H$ at random, and constructs a challenge that matches the encoding only if the adversary happens to choose a message whose hash lands in the right place. A forgery that satisfies the verification equation is, with probability about $2^{-8s}$ per attempt, a signature on the simulated challenge, which is an RSA inversion.

The practical reading of the proof is that salt length trades signature size and verifier work against the tightness of the reduction. A 32-byte salt gives a factor of $2^{-256}$, which is beyond any realistic attack. The older recommendation of salt length equal to the hash length is common and satisfies this; RFC 8017 also permits a salt length equal to the maximum that fits, which fills the available space in the encoded message and removes the need to choose.

Verification asymmetry

Signing under PSS is expensive because it involves one private-key operation, which for a 2048-bit modulus is a modular exponentiation with a full-length exponent using the Chinese remainder theorem. Verification is cheap: the exponent 65537 has two set bits, so raising to it needs sixteen squarings and one multiplication modulo $N$, independent of the message, and the dominant remaining cost is the hash of the message and the MGF1 expansion, a handful of hash calls.

That asymmetry is unusual in this cluster. ECDSA and Ed25519 verification are the expensive side because they require scalar multiplication, and signing needs one too, so the ratio between the two operations is close to one. RSA-PSS pushes the cost to the signer, which suits protocols where one signer serves many verifiers, such as certificate issuance or signed software releases.

The cost of PSS over v1.5 is one extra hash call and the MGF1 expansion in verification, which is a few more hash compressions for a 256-byte modulus. The signer pays the same small amount above the modexp. Nothing about PSS is meaningfully slower than v1.5 in either direction, which is why the main reason to keep v1.5 is compatibility with existing verifiers rather than performance.

Malleability and encoding checks

RSA signatures are malleable in one trivial way: if $\sigma$ is a valid signature, so is $N - \sigma$, because $(-\sigma)^e \equiv \sigma^e$ when $e$ is odd, which it always is. A verifier that compares signature bytes for equality, or that indexes signatures in a database, sees two distinct valid values for the same message. PSS does not remove this; the encoded-message check removes it in effect for well-formed encodings, because the recovered integer must begin with 0x00 0x01, and only one of the two candidates can satisfy that. The other candidate produces an encoded message whose high bits are wrong and is rejected.

The encoding checks are therefore not optional. An implementation that verifies the hash but skips the 0x01 separator or the zero-byte framing accepts encodings that a signer under a different scheme would produce, which is a cross-scheme confusion attack: a v1.5 signature reinterpreted as PSS, or the reverse, depending on which checks are loose. The rule that both PKCS #1 and the various implementation guides repeat is that the verifier must reconstruct the encoding exactly as the signer would and compare the whole result, not search for the components inside it.

The same discipline applies to Ed25519, where the encoding of the point and of the scalar must be canonical, and to ECDSA, where a signature is a pair of integers that can be encoded with different lengths. The pattern is general: the mathematical verification equation is only as strong as the parsing in front of it, and the parser is where the implemented system diverges from the proven one.