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. illustration of the attack

¹ 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.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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