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

Question

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?

Answer 1

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$.