# RSA small public exponent signature forgery - use part of the public key as ciphertext

I would like to ask you about what I think is a variation of BB'06 signature forgery¹.

Unlike BB'06 where the forged signature is valid for any pkey with e=3 the one I have is valid only for one pkey. Interesting in it is that out of the 128 bytes long signature the first 85 bytes is actually part of the pkey that I used to decrypt the message, the rest 43 is the forged part.

When decoded it gives garbage + correct ASN.1. On system with proper ASN.1 padding check the signature is invalid, on BB'06 vulnerable system the signature is valid.

Do anyone have idea which variation/method is used to produce it?

Here is example.

¹ Moderator note: BB'06 refers the Daniel Bleichenbacher's attack on incorrect verification of PKCS#1 V1.5 type 01 signature, which abound; see Daniel Bleichenbacher's RSA signature forgery based on implementation error (archived account by Hal Finney of Crypto 2006 rump session; alternate link); Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and yet other reports.

As you know, with the BB'06 attack, we find a signature $$s$$ such that $$s^3 \equiv m \pmod{2^\lambda}$$, where $$m$$ is the ASN.1-padded hash, and $$\lambda$$ is the length of the padded hash; as long as $$s^3 < n$$, then this signature looks valid (as long as the verifier doesn't look at the garbage in front of the padded hash).
Now, this works only is $$m$$ has a cube root modulo $$2^\lambda$$; this will be true iff the number of 0's at the end of $$m$$ is a multiple of 3, that is, is 0, 3, 6, etc; for a random $$m$$, this is true with probability $$\frac{4}{7}$$.
Now, for the actual $$m$$ in question, that's not true; it has exactly one 0 at the end, and hence the straight-forward BB'06 attack doesn't work.
What this variation does is take advantage of the identity within RSA $$(-s)^3 \equiv -(s^3)$$. That is, they search for an $$s'$$ s.t. $${s'}^3 \equiv n-m \pmod{2^\lambda}$$; $$n-m$$ is odd, that is, has no 0's at the end, and so such an $$s'$$ will exist (and is easy to find). Then, it sets $$s = n-s'$$, and that satisfies $$s^3 \bmod n \equiv m \pmod{2^\lambda}$$.
Now, it turns out that $$s'$$ is significantly smaller than $$n$$ (it must be below $$\sqrt[3]{n}$$), and so the higher order bits of $$s$$ come directly from $$n$$, which is what you see.