Score:2

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

bm flag

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?

Maarten Bodewes avatar
in flag
"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.
Maarten Bodewes avatar
in flag
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).
Score:3
ru flag

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

Maarten Bodewes avatar
in flag
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)?
Daniel S avatar
ru flag
@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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.