15
$\begingroup$

I am looking at a RSA signature verification that is quite obviously flawed and am wondering if there's a way to exploit that flaw in practice.

Signature is generated using RSA with PKCS 1.5 padding, i.e. $S = M^d \mod N$, where $M$ is a padded message: $M = 00 \| 01 \| FFF ... F\|00\|m$ and $m$ is the raw message being signed, which is always a 64-char pseudo-random ASCII hex string (it's a hash value).

When verifying signature, however, there is no check for padding. Verification is done by computing $M = S^e \mod N$, converting M to a byte array and then simply looking for a substring $m$ in $M$.

Modulus $N$ is 2048 bits and public exponent $e = 65537$.

Attacker can obtain a limited number of valid signatures (of a padded message) but there's no direct control over what $m$ will get signed (it's a time-base hash value).

Do you see any way to forge signature of attacker-chosen $m$ so that it'd be accepted by this flawed verification procedure?

Thanks!

Improve this question
$\endgroup$
3
  • $\begingroup$ What endianness did you write $M$ in? $\;$ $\endgroup$ – user991 Aug 8 '15 at 10:28
  • 2
    $\begingroup$ @RickyDemer: he said it was the standard PKCS 1.5 padding, and so that'd be bigendian $\endgroup$ – poncho Aug 8 '15 at 13:40
  • $\begingroup$ @RickyDemer Bigendian, as correctly noted by poncho. $\endgroup$ – Andrey Aug 8 '15 at 16:42
6
$\begingroup$

If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android).

In any case, the attack does not work for $e=65536$. However, if your question is whether or not it's OK to use this, then it certainly is not. The existence of the $e=3$ attack should be enough to convince you of that. On the other hand, if your question is constructive to find an attack, then I don't know - but it's a great research question.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. I know that this can be broken in practice for $e = 3$ and that's why I specified the actual value of $e$. I also know that it's not OK to use this in real-world system; my question os more on the research side. $\endgroup$ – Andrey Aug 9 '15 at 19:57
  • $\begingroup$ Good question then! $\endgroup$ – Yehuda Lindell Aug 9 '15 at 20:49
  • $\begingroup$ In the answer, $e=65537$ is meant where there is $e=65536$. With this $e$ and 2048-bit $N$, I concur that we know no attack (and doubt that there is one). For very large $N$ (of $e\cdot64\cdot8\approx 2^{25}$ bits), there's a trivial attack, and I wonder how much this can be lowered. $\endgroup$ – fgrieu♦ Aug 10 '15 at 13:57
3
$\begingroup$

There exist polynomial time attacks against RSA signatures with constant padding. So, this actually does not exploit the missing check for the padding. It uses index calculus

The latest paper that I am aware of in this series is http://www.dtc.umn.edu/~odlyzko/doc/index.calculation.rsa.pdf

but you might also be interested in this paper: https://www.iacr.org/archive/crypto2001/21390431.pdf, as it exactly looks at the issue of fixed padding.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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