I wonder what is the security of RSAES-PKCS1-v1_5 under chosen-plaintext attack, in the context of signature verification.
Notations. Let $(N,d)$ be an RSA signing key, and $(N,e)$ the corresponding verification key, with no assumption on $e$ (in particular, I don't assume $e=3$ and consider the general case $e=2^{16}+1$). Let $n$ be the bit-size of $N$.
More specifically, assume that one produces a signature $s$ for a short message $m$ using RSAES-PKCS1-v1_5 padding (bad practice): $$ s = pad(m)^d \bmod{N}, $$ where
pad(m) = 00 || 02 || R || 00 || m
and R
contains 8 or more nonzero bytes to make $pad(m)$ as long as the byte-length of $N$. (Note: unlike RSASSA-PKCS1-v1_5, the bytes in R
are not fixed to FF
.) Also here, the message is not hashed.
I wonder whether universal forgery is possible with only oracle access to the verification oracle $O(s)$, which returns $m$ if $s^e \bmod{N}$ corresponds to a valid padded message, and returns an error otherwise.
In an answer, Thomas Pornin writes that this "type 2" padding yields a weak signature scheme due to malleability of modular exponentiation. I understand that "type 1" (RSASSA-PKCS1-v1_5) is for digital signatures and "type 2" (RSAES-PKCS1-v1_5) for encryption, yet I don't see how malleability can be applied here to break the security.
Side question. In another answer poncho wrote that if $x^3 = h \bmod{2^{k}}$, then $y^3 = h \bmod{2^{k+1}}$ for $y=x$ or $y=x+2^k$. Hence here, given a target message $m$, is it easy to construct $s'$ such that $s'^e = m \bmod{2^{n+1}}$ for $n$-bit $N$. Which means that there exists $t$ such that $s'^e = m + t\cdot 2^{n+1}$. The integers $s'$ and $t$ are easily, but can they be leveraged to deduce $s$ such that $s^e = m \bmod{N}$?