Join Log in
Score:1
Brad avatar Crypto

RSADP/RSAEP with zero base/message value

ng flag
Brad

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!

53
0 + 0
rsa
Maarten Bodewes avatar
in flag
Maarten Bodewes
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.
0
Reply
Morrolan avatar
ng flag
Morrolan
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.
1
Reply
Score:3
Brad avatar Crypto
ng flag
Brad

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.

0 + 0
Maarten Bodewes avatar
in flag
Maarten Bodewes
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.
0
Reply
fgrieu avatar
ng flag
fgrieu
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_.
2
Reply
Brad avatar
ng flag
Brad
@MaartenBodewes - Sorry I don't see - where is the side channel if an implementation filters the raw c & m values before doing any exponentiation?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.