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

Question

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.

Answer 1

It does appear to be a variation, or possibly an extension, on the BB'06 attack.

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.