# How does padding in RSA prevent existenial forgery attacks in RSA?

I am trying to understand how adding padding like the PKCS1.5 RSA signature scheme can prevent the existential forgery attack in RSA. Is it just by changing the structure of the message?

• "Just changing the structure of the message" seems too loose a definition. The padding makes sure that the RSA input is near as large as the modulus and that the verification fails with very high probability if the signature is maliciously mauled; this means that the amount of bits that are verified must be high and that the verification cannot succeed if any known mathematical operation is performed on the signature. Some more formal answer is warranted though. Nov 18, 2022 at 9:46
• Note that the hash is probably more important than the padding performed in RSA. That's maybe a bit unfair as RSA padding requires a hash as input. One of the ways to make RSA signing secure is to use a Full Domain Hash (FDH) which does not require additional padding. PSS is related to Full Domain Hashing, which is also considered to be secure (although PSS isn't usually deterministic due to the salt configuration parameter). Nov 18, 2022 at 9:54

If we consider "textbook" RSA signatures where messages a message $$m$$ is signed by $$s=m^d\mod N$$ where $$d$$ is the private signing key and verfied by computing $$s^e\mod N$$ and comparing it to $$m$$ where $$e$$ is the public verification key, and allow the message space to be any integer in the range $$[1,N-1]$$ then there is a universal forgery attack under the chosen message attack model (i.e. UUF-CMA fails) and an existential forgery attack under the known message attack (i.e. EUF-KMA fails).

The universal forgery is as follows: given a message $$m$$, the attacker asks for signatures for a random value $$r\mod N$$ and also for $$mr^{-1}\mod N$$ (the inverse is computed using the extended Euclidean algorithm). If the signature values are $$s_1$$ and $$s_2$$ then $$s_1s_2\mod N$$ is a legitimate signature for $$m$$ because $$(s_1s_2)^e= s_1^es_2^e\equiv rmr^{-1}\equiv m\pmod N$$.

The existential forgery is when provide with signatures $$s_1$$ and $$s_2$$ for the messages $$m_1$$ and $$m_2$$, the attacker can produce signatures for $$m_3=m_1^am_2^b\mod N$$ by submitting $$s_1^as_2^b\mod N$$. This is because $$(s_1^as_2^b)^e=(s_1^e)^a(s_2^b)^e\equiv m_1^am_2^b\equiv m_3\pmod N$$.

The existential attack can even be extended to where $$m$$ is the output of a, say, unpadded output of a 256-bit hash function. We collect signatures of hash values which factor into primes less than $$2^{29}$$ (i.e. hash values that are $$2^{29}$$-smooth). The chances that a hash value is smooth is about $$2^{-29}$$ so after collecting about $$2^{58}$$ signatures we should have $$2^{29}$$ smooth examples. Using index calculus we can use the smooth signatures find products/quotients of signatures that produce signatures for all small prime values. These in turn will allow us to forge all smooth hash values.

PKCS1.5 padding blocks this attack by making sure that the size of the $$m$$ that is exponentiated is roughly $$\log N$$ bits rather than 256. These numbers are much less likely to be smooth and render the attack as less feasible than factoring $$N$$.

• I presume that a FDH of a size of 512 bits and higher has a lot smaller chance of being smooth (basically $\log N$ as well)? Nov 18, 2022 at 11:17
• @MaartenBodewes For hash size 512-bits you should set a smoothness bound of about $2^{44}$ and collect about $2^{88}$ hashes, this will be harder than factoring a 1024-bit number. Nov 18, 2022 at 11:26