Is it ever OK to to sign RSA messages with padding random bytes?

Question

If a message is padded with cryptographically secure random bytes, is there any reason why this would be less secure than the standard signature padding schemes (PKCS1 v1.5 and PSS)? To give context to the meaning of the word "secure," I would note that my only intention is to prevent others from being able to forge the message signature.

Answer 1

Let's begin with digital signatures;

Digital Signature

A digital signature scheme is simple the triple $Gen, Sign, Verify$ of polynomial-time algorithms. We want the $Gen$ and $Sign$ probabilistic and $Verify$ deterministic. The $Gen$ outputs public key $K_{pub}$ and private key $K_{prv}$

To sign a message $m$ compute $$\sigma = Sign^R(K_{prv}, m)$$ and output $(m,\sigma)$. To verify a signature compute $$\{0,1\} = Verify(K_{pub},m, \sigma)$$ and output $1$ or $0$ as signature is valid or invalid, respectively.

Since the first true signature scheme (Rabin Signature Scheme) we hash the message before the sign and this is required for the security also enables signing long messages. The hash function needs to be a collision-resistant one. Then we have;

$$\sigma = Sign^R(K_{prv}, H, m)$$ and

$$\{0,1\} = Verify(K_{pub},H, m, \sigma)$$

There are various security levels of digital signatures, here we look at the weakest adversarial goal on the signature forgeries;

Existential Forgery:

An adversary $\mathcal{A}$ creates any message/signature pair $(m,\sigma)$, where $m$ is not signed before the legitimate user. The $m$ need not have any meaning, the $\mathcal{A}$ doesn't need to control over the message $m$.

This is the weakest goal of the adversary then this implies that the strongest scheme is those which are secure against existential forgery.

As an example consider the standard text-book RSA signature. Consider two signature an attacker intercepts; $\sigma_1 = m_1^e \bmod N$ and $\sigma_2 = m_2^e \bmod n$ then $\sigma = \sigma_1 \cdot \sigma_2$ will be a valid signature for the message $m_1 \cdot m_2$. This attack uses the multiplicative property of the RSA function.

RSA-Full-Domain-Hash (bonus)

RSA-FDH is introduced by Mihir Bellare and Phillip Rogaway in 1993

• Random Oracles are Practical: A Paradigm for Designing Efficient Protocols

This requires a hash function $H_{FDH}:\{0,1\}^* \to \mathbb{Z}_N^*$ ( first $*$ is the Klein star and the second one is the multiplicative group $\mathbb{Z}_N -\{0\}$.) It was not easy to produce a hash function during 1996, however, today we have XoF's like SHAKE128 that can produce arbitrary size.

The signature is

\begin{array}{ll} \operatorname{SignFDH}_{N,d}(M) & & & &&&&&\\ \quad\quad y \leftarrow H_{FDH}(M)\\ \quad\quad \textbf{return } \sigma = y^d \bmod n\\ \end{array}

The signature verification is

\begin{array}{l} \operatorname{VerifyFDH}_{N,e}(M,\sigma) &\\ \quad\quad y \leftarrow \sigma^e \bmod N&\\ \quad\quad y \leftarrow H_{FDH}(M)&\\ \quad\quad \textbf{if } y = y' \textbf{ then return } 1 \textbf{ else return } 0\\ \end{array}

As we can see the attacker needs to produce the message, not the hash of the message to produce a forgery. The verification is performed on the Message, not on the hash of the message!

Now it proven to be is existentially unforgeable under adaptive chosen-message attacks) in the random oracle model.

• The Exact Security of Digital Signatures: How to Sign with RSA and Rabin, Mihir Bellare and Phillip Rogaway in 1996
• On the exact security of Full Domain Hash, Coron in 2000

PKCS1-v1_5 Signature Scheme (Related)

Also known as RSASSA-PKCS1-v1_5 and its security is finally is given

• On the Security of the PKCS#1 v1.5 Signature Scheme, Joger et. al, 2018.

It has an $EM$ structure as this

EM = 0x00 || 0x01 || PS || 0x00 || T.

so what are they;

• PS is FFs block and at least 8 octets (octet is 8-bit)

• T is the H(M) and the hash algorithm identifier;

  T = AlgorithmIdentifier|digest

• the first 0x00 guarantees that EM is less than the modulus.

• The rest details like the real size of FF block etc. can be found in rfc 8017 section 9.2

Turn back to OPs question

Is it ever OK to sign RSA messages with padding random bytes? If a message is padded with cryptographically secure random bytes, is there any reason why this would be less secure than the standard signature padding schemes (PKCS1 v1.5 and PSS)?

The message is hashed with a secure hash function ( say SHA-512), since it is not full domain hashing you fill the rest with random bytes. In this case, it is very similar to PKCS1-v1_5 Signature Scheme. Except you did not put the boundary blocks 00 and 01 and replaced them all with random bytes and the missing hash function id.

• Can a random text that has taken the $e$-th power be a signature forgery?

  No, The forger needs to provide the message $m'$ too. During verification, the hash of the message $\operatorname{SHA-512}(m')$ will be taken and compared with the one in the signature.

So what is the advantage of the $EM$ structure? It has additional verification of the format and the used hash function is encoded.

Conclusion: stick to formats, they have a long time evaluations due to security concerns.

Answer 2

The correctness of the padding should be verifiable from the hash of the message - that is, given the hash of the message, the same padding should be reproducible. Otherwise, "existential forgery" would be possible.

So what is "existential forgery"?

Basically, you just produce a random string of bytes as your signature. When it's interpreted as an integer and raised to e'th power mod n, the lower 256/384/512 bits will be as valid a hash value as any other, so even though we don't know what message produces such hash value, we've found one that exists, hence "existential forgery".

To actually make the attack work requires some extra effort, including but not limited to:

• mounting collision attack on the hash function against the verification exponent with many random messages.

• for small modulus, GNFS may yield results with part of lower-order bits matching the candidate message digests.

As noted by @fgrieu in the comment, the question asks a hypothetical situation that cannot be universally applied, thereby making it a false proposition.