Daniel Bleichenbacher’s RSA signature forgery is a well-known exploit of RSA vulnerabilities. The original post explains the idea concisely, yet during my OH as a TA of CIS 551, it seems that it still confused many people. This post is an attempt to further crystallize the idea.

Starting point: assumptions of the victims

RSA in practice enforces padding mechanism such as PKCS1v1.5, since vanilla RSA is deterministic and insecure. Unfortunately, as observed by Daniel Bleichenbacher, real world implementation often fails to fully validate the RSA signature padding format after decryption and accepts malformed signatures where the hash is not right-justified at the least significant bits. In other words, while a valid message after decryption has the format 00 01 FF FF FF ... FF 00 ASN.1 HASH as specified in PKCS1v1.5, 00 01 FF FF ... FF 00 ASN.1 HASH GARBAGE will also be accepted by a naive verifier.

Goal: reverse engineer a signature \(c\) for the target \(m_{padded}\) to be accepted by a buggy implementation

As we know, \(c = m_{padded}^{d} \mod n\) and \(m_{padded} = c^{e} \mod n\). We don’t know \(d\), yet with known \(e\) and if the public exponent e is small at the same time (so that \(c^{e} < n\), i.e., \(m_{padded} = c^{e}\)), specifically, when \(e=3\) (often used for the efficiency of the computation), one could easily forge a signature. The goals here are two folds:

  • For a target HASH (original message \(m\)), craft \(m_{padded}\) where we have the freedom to control the length of FF padding and GARBAGE contents s.t. \(m_{padded}\) is a perfect cube.
  • Calculate the signature \(c=m_{padded}^{\frac{1}{3}}\).

Math problem: crafting a cube \(m_{padded}\) and finding its cubic root \(c\)

The goal above corresponds to crafting the target (padded) message \(m_{padded}\) (which is nothing but a big integer) as a cube and finding its cubic root \(c\). The original post shows an instance of “pens and pencils” style derivation.

Recall that \((A-B)^{3}=A^3-3(A^2)B + 3A(B^2) - B^3\), if we think of \(c=A-B\), we need to craft \(m_{padded}\) such that it can be numerically represented as the RHS polynomial of the equation. This is not that hard given the fixed message format 00 01 FF FF ... FF 00 ASN.1 HASH GARBAGE. For example, we could easily figure out the degree of a polynomial as \(3057 = 3072-14-1\), i.e., \(A=2^{3057}\) (hint: \((1FF00)_{2}=2^{18-1}-2^{9-1}\)).

We also have the freedom to control the number of FF paddings and the contents of GARBAGE. Bleichenbacher reserves 2072 bits for GARBAGE and denotes the numeric value of the byte string 00 ASN.1 HASH as \(D\) (with SHA-1, it is 36 bytes or 288 bits long). Therefore \(m_{padded}\) can be numerically represented as \(m_{padded}=2^{3057}-2^{2360}+D*2^{2072}+garbage=2^{3057}-N*2^{2072}+garbage\) where \(N=2^{288}-D\) and \(N\) as a cube — this is reasonable since we could easily tweak the message before hash. Again we have the full freedom to craft the variable garbage and therefore we could arrive at \(m_{padded}=2^{3057}-N*2^{2072}+(N^2\times 2^{1087}/3)-(N^3 * 2^{102}/27)\) which fits the identity. Therefore, \(c = 2^{1019}-(N*2^{34}/3))^{3}\) which is exactly our forged signature.

In fact, one doesn’t need to faithfully do the painful derivation above. Probably an easier approach is to repeatedly craft \(m_{padded}\) and check if it is a perfect cube using a cubic root calculation function from a numerical computing package. Most oftenly, such engineering style trial and error loop can be skipped as well. \(m_{padded}\) doesn’t even need to be a perfect cube and we can just take, e.g., \(c=\lceil m_{padded}^{\frac{1}{3}} \rceil\). The underlying reason is that the deltas \(c^{3}-m_{padded}\) will fall into changes of GARBAGE section which we don’t actually care.