1
$\begingroup$

I have a question about how RSADP/RSAEP are defined (in RFC2437 https://datatracker.ietf.org/doc/html/rfc2437#section-5.1.2):

RSADP (and RSAEP) are described with the same limits for the message (m) and ciphertext (c), namely 0 <= m < n. In this case the modular exponentiation primitive assumes padding has already occurred, so leaving that out of the picture.

5.1.2 RSADP

   RSADP (K, c)

   Input:

   K         RSA private key, where K has one of the following forms
                 -a pair (n, d)
                 -a quintuple (p, q, dP, dQ, qInv)
   c         ciphertext representative, an integer between 0 and n-1

   Output:
   m         message representative, an integer between 0 and n-1; or
             "ciphertext representative out of range"

I have the following question: do/should implementations actually accept 0 & 1 as valid c & m values? Wouldn't zero and one both remain constant under exponentiation, so that the cipher text and plain text would not change? Isn't that bad? Is it correct for an implementation to reject these values - even though the spec seems to allow them?

UPDATE: I'm not asking about padding per-se, since the exponentiation occurs after padding (in the encryption case), but rather why the spec seems to allow these insecure values at all. Why doesn't the spec disallow 0 & 1 explicitly? Admittedly it is statistically rare if the result of padding were such a value, but my question is shouldn't the RSADP/EP functions disallow these values and the overall OAEP scheme built on top of these functions be specified to choose a different padding input in that case?

Maybe there's something I'm missing here, so appreciate any info.

Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ Obviously not, no, but remember that encrypting a static message with the same key also directly leaks information. So basically I think that this is not so much a security requirement; it is about loss of information. But probably others will be better at giving a more mathematical explanation. There are many other reasons why a secure padding is required. $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 6, 2022 at 5:02
  • 1
    $\begingroup$ Due to how RSAES-PKCS1-v1_5 defines its padding - specifically the fixed byte it utilizes - I believe it is impossible for the padded message to represent either a 0 or a 1 when turned into an integer by the OS2IP primitive. For RSAES-OAEP the padded message could end up representing a 0 or a 1, but the probability of this happening is on the order of an adversary guessing a prime factor of your modulus first try. $\endgroup$
    – Morrolan
    Commented Feb 6, 2022 at 20:44

1 Answer 1

Reset to default
3
$\begingroup$

Turns out NIST's definition of RSAEP/RSADP differs from the RFC 2437 version.

NIST's definition can be found in SP800-56Br2: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf

In section 7.1 Encryption and Decryption Primitives, the NIST specification requires implementations to reject values of 0, 1 & n-1 as follows:

7.1.1 RSAEP
...
1. If m does not satisfy 1 < m < (n – 1), output an indication that m is out of range, and exit without further processing

Similar limitations are required for both encryption & decryption.

Therefore, an implementation should filter and explicitly block these inputs.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The problem is if you want to perform the comparison if the input is randomized anyway. It's an additional, unnecessary and potential dangerous step because of possible side channel attacks. $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 6, 2022 at 23:59
  • 2
    $\begingroup$ The NIST requirement of removing fixed points $0$, $1$ and $n-1$ likely is to block attacks against decryption where the adversary submits these ciphertexts $c$ for decryption, in a side channel attack like Simple Power Analysis. With $c=0$ and $c=1$, the adversary knows $c^f\bmod n$, or $c^f\bmod p$ and $c^f\bmod q$ all along the calculation, even if they do not know $f$; and even more worrying, with $c=n-1$, they can get the parity of $f$ if they manage to distinguish one value from the other. This removal does not look like a solid defense to me, but can't harm in decryption. $\endgroup$
    – fgrieu ♦
    Commented Feb 7, 2022 at 7:20
  • $\begingroup$ @MaartenBodewes - Sorry I don't see - where is the side channel if an implementation filters the raw c & m values before doing any exponentiation? $\endgroup$
    – Brad
    Commented Feb 7, 2022 at 23:50

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.