Attacks on code misusing RSA_public_decrypt

Question

I've encountered some code that I'm reviewing that is misusing RSA_public_decrypt to "authenticate" a variable-length response without using any hash. The code assumes that a successful decryption means that the given data buffer was generated by the server and processes it without any additional checks.

I believe that this is unsafe, even though the code is using the RSA_PKCS1_PADDING mode. Is there a reference to a set of attacks on misuse of RSA in this way?

For additional context, this code is using a 2048-bit key with e=3.

Answer 1

In OpenSSL 1.0.2 (and former) at least, based on its documentation and code of an implementation, the big picture is that RSA_public_decrypt with RSA_PKCS1_PADDING applies the RSA public-key transformation $S\mapsto S^e\bmod N$ where $S$ is the alleged signature, then checks that the outcome (considered as a big-endian bytestring of the same size as $N$) is of the following form $$\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\underbrace{\mathtt{FF}\ldots\mathtt{FF}}_{\ge8\text{ bytes}}\mathbin\|\mathtt{00}\mathbin\|D$$ and in the affirmative returns the bytestring $D$, and its length.

However, implementation is configuration dependent. Sticking to openssl-1.0.2t, RSA_public_decrypt of rsa_crpt.c can vector to a number of things, including RSA_eay_public_decrypt of rsa_eay.c with padding checks in RSA_padding_check_PKCS1_type_1 of rsa_pk1.c, but also to various other engines for HSM, Smart Card, OS-dependent service (like CryptoAPI on Windows). Thus exactly what it does is quite configuration-dependent. In particular:

• Implementations should check that $S<N$, and the aforementioned version of RSA_eay_public_decrypt does, but some implementations do not. The main cryptographic significance is that, if this check is not performed, it is possible to transform a rightful signature $S$ into into another accepted one $S'=S+jN$ (depending on if there is a length check for $S$, that could be for all or a fraction of rightful $S$). In the context of the question where the easiest forgeries $S$ are much smaller than $N$, $S+N$ would typically have the right size, and would look less regular (thus suspicious) to the naked eye.
• Implementations often accept that the leading $\mathtt{00}$ is absent, and the aforementioned RSA_padding_check_PKCS1_type_1 does. There might be some even more lenient checks in other implementations. Either would give more freedom in the following attack.

---

code (..) is misusing RSA_public_decrypt to "authenticate" a variable-length response without using any hash. The code assumes that a successful decryption means that the given data buffer was generated by the server and processes it without any additional checks.
(..) 2048-bit key with $e=3$.

With these parameters, it's indeed possible to forge the signature for a number of $D$. In particular, it is enough that $\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\mathtt{FF}\ldots\mathtt{FF}\mathbin\|\mathtt{00}\mathbin\|D$ is a $e^\text{th}$ power. If the key is $k$-bit, and $\tilde k=8\lceil k/8\rceil$, it is enough that $D$ is the low-order $\tilde k/8-11$ bytes of $S^e$ with $S$ the signature in the integer range $$\Biggl[\;\biggl\lceil\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}}\;\biggr\rceil\;,\ \biggl\lfloor\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}+2^{\tilde k-88}-1}\biggr\rfloor\;\Biggr]$$

For small enough $e$, this interval in non-empty, and it is possible to obtain $D$ with some of its left bits at a chosen value, by putting the others at zero and computing $S$ as $\biggl\lceil\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}+D}\;\biggr\rceil$. More (smaller, possibly empty) intervals are possible for shorter $D$.

Here $k=\tilde k=2048$, $e=3$, that interval contains over $>2^{603}$ signatures $S$, and there are as many 245-byte $D$. One such signature $S$ is

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000032cbfd4a7adc7905583fd1456434c26cdf83a920b31e26cc57a313376f4148ebf9544218c1bdc0793bf961895224ef87d397320d586eb7c6ce051ad3fe93b96e22c7f1ec329b88780a17483947fbb7bf3707b0f445

with $S^3$ equal to

0001ffffffffffffffff0077652063616e20666f7267652061207369676e6174757265206f7574206f66206e6f776865726500000000000000000000000000000000000000000000000000000000000000000000000018e546e7c17e2565ec99cfa7249fd76b89b819c73a68a5e19d0302472cdd57230fb23fba23f25e9e76d6345156620f5ecabd14f65fd2fd230a38a769eb521b6e61ac9d9a995e857d03525128e8c1689814fec44d88abded8e3ee67e87b227536f1c42b9a8a1c08d918de54653f8cb1cd54699edfd00763fb0644e304c9644b87b75731bd6fabe7920bb47ba3151f614256814655db5ced95b7c480c5daf51d96145dc26d831fea327f3d

thus this $S$ is acceptable (regardless of the value of the public key) by most RSA_public_decrypt, and produces a 245-byte $D$ of

77652063616e20666f7267652061207369676e6174757265206f7574206f66206e6f776865726500000000000000000000000000000000000000000000000000000000000000000000000018e546e7c17e2565ec99cfa7249fd76b89b819c73a68a5e19d0302472cdd57230fb23fba23f25e9e76d6345156620f5ecabd14f65fd2fd230a38a769eb521b6e61ac9d9a995e857d03525128e8c1689814fec44d88abded8e3ee67e87b227536f1c42b9a8a1c08d918de54653f8cb1cd54699edfd00763fb0644e304c9644b87b75731bd6fabe7920bb47ba3151f614256814655db5ced95b7c480c5daf51d96145dc26d831fea327f3d

which, when interpreted as a C string in ASCII or UTF-8, is the string

we can forge a signature out of nowhere

The LLL algorithm may allow further forgeries, I'm not a specialist of that.