Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Assume that we have a message $m$ of size $n$, and it is padded with two 01 bytes in front. Then the signature $s$ is computed using a private key $ks$. Can we still use the Known Message Attack to create a signature for message $m^2$ or $pad||m||pad||m$ by multiplying the signature with itself? Or will the padding stop this despite being weak?

share|improve this question
add comment

2 Answers

up vote 5 down vote accepted

If we note $|m|$ the number of bits in the bytestring coding the message $m$, the first padding considered is $m\mapsto \tilde m=257\cdot2^{|m|}+m$, and the signature is $m\mapsto\tilde S(m)=S(\tilde m)=\tilde m^d\bmod N$, where $S$ is the textbook/naked RSA signing $m\mapsto m^d\bmod N$. Notice that for any $m$ small enough that $m^2$ can be signed, we can derive $S(m^2)$ as $\big(S(m)\big)^2\bmod N$; and if $n^2$ is too big, we may still have $S(m^2\bmod N)=\big(S(m)\big)^2\bmod N$.

NO, we can not derive $\tilde S(m^2)$ as $\big(\tilde S(m)\big)^2\bmod N$. That equality holds if and only if $\tilde m^2\equiv\widetilde{m^2}\pmod N$. At least, when $m$ is small enough that $\widetilde{m^2}<N$ or some similar huge bound (not explicit in the statement), that simplifies to $\tilde m^2=\widetilde{m^2}$, and there is no $m$ matching that: notice that the square of an integer which two leftmost bytes after removing leading zeroes are 0101 has its two leftmost bytes after removing leading zeroes among {0102, 0103, 0104}. I conjecture, without proof, that above said bound, we can not efficiently come up with any solution without knowing the factorization of $N$.

But NO, the scheme is not secure. Even with the (unstated) constraint of messages of the same width, it is easy to come up with distinct messages $m_0, m_1, m_2, m_3$ such that $\widetilde{m_0}\cdot\widetilde{m_1}=\widetilde{m_2}\cdot\widetilde{m_3}$; and then we can derive $\tilde S(m_3)$ as $\Big(\tilde S(m_0)\cdot\tilde S(m_1)\cdot\big(\tilde S(m_2)\big)^{-1}\Big)\bmod N$, where the inverse is computed $\pmod N$.


More generally, linear padding schemes (such as the second one proposed) are weak in RSA, and subject to attacks. See Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem, section 4.1.

Even non-linear padding schemes may be quite weak; for example (INCITS/)ISO/IEC 9796:1991 (informally known as ISO/IEC 9796-1, and mostly described in section 11.35 of the HAC) was trounced in 1999, then withdrawn.

Using a padding scheme with a hash helps, but is not an insurance of security against such forgeries, even in combination with a linear padding scheme; for example ISO/IEC 9796-2:1997 was shown to have a vulnerability (not practically exploitable in any setup that I know of), even in its strengthened variant of 2002, now officialy designated as ISO/IEC 9796-2 scheme 1 and in wide use, that prescribes a hash of at least 160 bits. However I do not know of any attack (even theoretical) on the padding of RSASSA-PKCS1-v1_5 of PKCS#1.


Conclusion: when at all possible, and in any setup where an adversary could obtain the signature of chosen messages, use RSA signature schemes with provably secure padding based on Full Domain Hash, like RSASSA-PSS of PKCS#1, or when message recovery is needed ISO/IEC 9796-2 schemes 2 or 3 (although I have never seen a complete formal proof of the later ISO/IEC 9796-2 schemes, I trust them enough).

share|improve this answer
add comment

Considering the padding as an addition, padded message passed to sign is $m\cdot 2^{16}+0101$, $0101$ in hexadecimal, assuming padding is done on the lower bytes (for higher bytes the logic is just the same). Being $e$ the private exponent, and $m^2$ computed in the size of $m$,

$(m\cdot 2^{16}+0101)^e \pmod m$ is very different from $(m^2\cdot 2^{16}+0101)^e\pmod m$, and clearly $(m\cdot 2^{16}+0101)^{2e}\neq(m^2\cdot 2^{16}+0101)^e$.

share|improve this answer
    
When signing, the private exponent d is used, not the public exponent e. Also, the definition of the padding is now clarified, and is not as in this answer (please excuse my first comment, which was wrong). –  fgrieu Dec 19 '13 at 10:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.