RSA Encryption and Signature - Weak Padding Assume that I have an plaintext $m$ and it is padded with $randompad||00||m$ and then it is encrypted with RSA and a public encryption key so we get the encrypted $Sm$. 

Then to assure its integrity we use our signature key and we publish the verification key. The input to the signature is this (so again we have padding) $01||Sm$. Then the signature $Sign$ is calculated and we send both $Sign$ and $Sm$ to the receiver. 

Is there anyway somebody could change our message assuming that he knows the public encryption key and the verification key as well?

In order to verify it or decrypt it all the padding bytes on the left are discarded.
I've been reading the RSA-survey but I can't find any attacks that would work, only if somebody made us sign another message like a blind attack. Do you have any suggestions? Would a key-only attack work in this case?
Yes, there is an attack that has a fair chance of success, like $2^{-8}$ per $Sign$ (and perhaps $Sm$) submitted; or even more depending on exactly how the encryption padding is removed/verified. The attack does not require submitting a message for signature to a party knowing the signature private key. I consider the attacker successful whenever she manages to submit something that the receiver accepts, deciphering and recovering the message $m$, even when the attacker gets no clues about $m$.

More hints: The attacker needs no other input than the signature verification public key, and perhaps the size of the encryption modulus. The attacker's expected cost for a success may be $2^{15}$ modexp (more or less depending on exactly how the signature padding is removed/verified, and for some interpretations of that how much the bit size of the signature modulus exceeds the bit size of the encryption modulus, rounded-up to the next multiple of 8).



The big picture: the attacker repeatedly chooses $Sign$ arbitrarily, and weeds out some appropriate subset of them for submission, by making just what the receiver would do, as far as the attacker can; because there is (explicitly at least) little more than one byte (the $01$) of verifiable signature padding, a sizable fraction of $Sign$ are an acceptable signature for some $Sm$, and (critically) the adversary can find that $Sm$. The adversary submits those $Sign$ (and the associated $Sm$ if that's part of the protocol) that pass that (very weak) signature verification test; and because there is (explicitly at least) little more than one byte (the $00$) of verifiable message padding, a sizable fraction will also decipher to some $m$.

Like most simple attacks exploiting a lack of enough padding (here: in a signature scheme allowing message recovery), the cost of the attack (expressed in number of modular operations) is mostly independent of the size of the signature modulus.



To better grab how the system and attack works, we need to further define what the parameters are. Let the signature modulus be $N$ of $n$ bits, and the encryption modulus be $N'$ of $n'$ bits. The result of the encryption step is a number up to $N'-1$, thus $Sm$ is a bytestring of $\lceil n'/8\rceil$ bytes when it is used in the signature padding $01||Sm$, which has one more byte. Thus $01||Sm$ is a bytestring representing an integer of exactly $\lceil n'/8\rceil\cdot8+1$ bits, and the cryptosystem can sign the result of any encryption when $N\ge(2^{\lceil n'/8\rceil\cdot8}+N')$, including but not limited to if $n\ge(\lceil n'/8\rceil\cdot8+2)$ bits. Perhaps the system is intended for $n=(\lceil n'/8\rceil\cdot8+8)$. If $n$ was much more, the signature padding would be shown as $00..01||Sm$.

We must also reconstruct or assume what exactly the receiver does:


receive $Sign$;
perhaps (that's untold) reject the submission if $Sign\ge N$;
compute $Sign^e\bmod N$, making that a bytestring of $\lceil n/8\rceil$ bytes;
reject the submission if the leftmost byte of that is not $01$;
consider the remaining bytes of the bytestring of (3.) to be $Sm$ (or if $Sm$ is explicit in the receiver's input, fail if the remaining bytes do not match $Sm$);
perhaps (that's untold) reject the submission if $Sm\ge N'$;
compute $Sm^{d'}\bmod N'$ and convert that to a bytestring of $\lceil n'/8\rceil$ bytes;
perhaps (that's untold) reject the submission if the leftmost byte of that bytestring is not $00$ (that corresponds to checking the few zero bits that customarily are on the left of $randompad||00||m$ in order to make the corresponding integer less than $N'$);
assuming that $m$ has fixed width $w$ bytes, reject the submission if the $(w+1)$th byte from the right of the bytestring of (7.) is not $00$ (or, assuming that $m$ is a bytestring of variable width not containing $00$ such as a C or UTF-8 string, recover $w$ and $m$ by scanning that bytestring from the right until a $00$ is found, rejecting the submission if the bytestring contains no such byte);
Having found no rejection reason, accept the message $m$ extracted from the bytestring of (7.).


The attack should be obvious by now: the attacker repeatedly selects $Sign$ e.g. randomly in $\{0\dots N-1\}$, and performs (3.), until the bytestring obtained has a $01$ on the left so that it pass (4.), and the remaining $Sn$ pass (6.) if applicable [note: I have not included (6.) in my estimate of the attack's cost, but the increase would be by a factor of $2^{\lceil n'/8\rceil\cdot8}/N'$, which is less than $2^8$]. The attacker submits those surviving $Sign$ (and perhaps the matching $Sn$ if that's required). In the first option of (9.), the odds of success of the attacker are $2^{-8}$ per attempts (and more in the other option), assuming no step (8.).

A speedup (and a practical attack even when $n\gg n'$) is possible when $e$ is very small, like $3$, $5$, $17$; that is left as an exercise to the reader. The conclusion should be: use strong padding (not: do not use very small public exponents).