RSA Signature Attack without Valid Message and Signature Pairs

CryptoGuru

12/15/23, 10:03 PM

I know about the existential forgery attack on RSA where a forgery is possible given two valid message and signature pairs but I am wondering how can a forgery be done on RSA with just the knowledge of the public key (e and n) without the knowledge of another message/signature pair given that the signatures are not padded?

0 + 5

forgery

fgrieu

12/15/23, 10:22 PM

Hint: what exactly is an existential forgery? With that written, how do you make these? Note: We don't even need $n$ or $e$ to make one, or even two existential forgeries. With $n$ alone. we can make a third (and we don't even need pencil and paper). If we could factor $n$ into the product of two distinct primes, we could make nine existential forgeries (but in RSA, adversaries can't factor $n$). With $(n,e)$, we can make as many existential forgeries as $n$ and our patience allows.

CryptoGuru

12/15/23, 10:48 PM

Would it be just an attack where we sign the message with a random number r and then divide the signature/r (the blinding attack)?

fgrieu

12/16/23, 5:41 AM

Developing: An Existential Forgery is any (message,signature) pair $(m,s)$ that pass the test made by the verifier against the public key $(e,n)$. In one definition of textbook RSA signature, that test is: $0\le m<n$ and $0\le s<n$ and $s^e\bmod n=m$. Again, one can make two EFs without even knowing $n$, an additional EF knowing $n$ (and that $e$ is odd in RSA), and six additional EFs if knowing a factorization of $n$ as $n=pq$ with $\gcd(p,q)=1$. With knowledge of $(e,n)$, we can make as many EFs as $n$ allows.

CryptoGuru

12/16/23, 6:57 PM

So could an attacker create a random signature $s$ and based on that generate a message such that message = Encryption($s$) = $s^e\bmod n$?

fgrieu

12/16/23, 8:18 PM

Yes! Alternatively, without $n$, $(m,s)=(0,0)$ and $=(1,1)$ are valid EFs. So is $(n-1,n-1)$. And more generally the nine $(m,m)$ with $m\bmod p\in\{0,1,p-1\}$ and $m\bmod q\in\{0,1,q-1\}$, assuming $n=p\,q$ with $\gcd(p,q)=1$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: RSA Signature Attack without Valid Message and Signature Pairs

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.