3
$\begingroup$

I used to think that adding random padding to an rsa plaintext was to prevent attack when you can ask/have access to different ciphered output, and decipher it without access to the private key (under certain conditions).

I've came across a signature verification scheme that seems to use random padding (at start and end of the hash) to make the signature, but does not enforce any padding scheme.

From what I understand, using proper padding (pkcs#xxx), and ensuring the padding scheme is respected is a must-do when it comes to signing messages.

But I was wondering at which point using this one is flawed ?

$\endgroup$
5
  • $\begingroup$ "came across a signature verification scheme", well, any answer will have to depend on that specific scheme. Then, if it's something archetypal, we can expand a little bit on that. $\endgroup$
    – DannyNiu
    Sep 26, 2023 at 8:38
  • $\begingroup$ Welcome to Cryptography.se. Do you mean RSA-OAEP or RSA-FDH or something else? Is there a specific reason that you are not providing where did you see it? $\endgroup$
    – kelalaka
    Sep 26, 2023 at 8:38
  • 1
    $\begingroup$ The verification scheme is just checking that bytes 43 to 106 equals the hash of the signed message the other 448 bytes are random / not checked. So it's not RSA-FDH, neither textbook rsa per-se. No specific reason, I just did not thought it was relevant. It's in a bootloader secureboot verification process. $\endgroup$
    – Xilokar
    Sep 26, 2023 at 9:01
  • $\begingroup$ crypto.meta.stackexchange.com/q/100/23623 $\endgroup$
    – kelalaka
    Sep 26, 2023 at 9:28
  • 1
    $\begingroup$ @Xilokar There seems to be an answer which could be accepted, and I don't see any answer popping up that would be even more clear (other than to break the scheme entirely), maybe a good idea to accept the existing answer? $\endgroup$
    – Maarten Bodewes
    Feb 24 at 19:17

1 Answer 1

2
$\begingroup$

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448+106+1-43 = 512 bytes (consistent with $n$ of 4096-bit), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e\in\{3,5,7\}$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 512-1-106 = 405 bytes or $b=3240$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le7$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.


That signature scheme is not an academically recognized one. It's definitely not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e=F_4=65537$, then I wish I knew what they had in mind.

$\endgroup$
3
  • $\begingroup$ I would not have answered this question if I thought it was for an actually deployed system. Answering here was easier than text messages thru a colleague. $\endgroup$
    – fgrieu
    Sep 27, 2023 at 13:47
  • 1
    $\begingroup$ Thanks for your answer. I wasn't aware of the policy on cryptostackexchange regarding deployed system, and apologize... I was adviced to ask here when I prompted my findings on a social network. n is 4096-bit and e is 65537, so I guess security is achieved by increasing e only $\endgroup$
    – Xilokar
    Sep 27, 2023 at 15:38
  • 1
    $\begingroup$ @Xilokar: I fixed some details (I had previously misread "other 448 bytes"). I don't know how to attack with e=65537, but would not bet that it is secure facing better attack à la Coppersmith. My statement is that this signature scheme is unacademical, and should not be trusted. $\endgroup$
    – fgrieu
    Sep 27, 2023 at 16:10

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.