Score:2

How important is constant-time verification of lHash label in RSA-OAEP?

vu flag

In my hobbyist project implementation of RSA-OAEP, I omitted support for labels at the beginning. I set the label to empty string on encryption and ignored the label on decryption.

Now I'm adding a special function to set and test the label, but it's not constant-time yet. The security note in PKCS#1v2.2 says that the verification of the label along with other ciphertext verifications should be done as a atomic constant-time step.

Q1: So I want to ask: how dangerous it is to verify the label not in constant time?

I can think of pre-shared secret label being guessed by an outsider with the encryption public key as one scenario, Q2: are there others?

fgrieu avatar
ng flag
The question uses RSA-OAEP where clearly it means [RSAES-OAEP](https://pkcs1.grieu.fr/page=#%5B%7B%22num%22%3A44%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C118%2C640%2Cnull%5D). That license is fine and common. It should however be noted that RSAES-OAEP is the reduction to practice of [RSA-OAEP](https://cseweb.ucsd.edu//~mihir/papers/oaep.pdf), and has a few differences, including the introduction of labels.
Score:2
ng flag

how dangerous it is to verify the label not in constant time?

As far as I can tell not much, as long as the label is public, and this verification is performed and not conditioned by the verification of the 0x00 byte on the left of the result of the raw/textbook RSA decryption $c^d\bmod n$. That applies regardless of if the decryption operation has support for labels.


The security note in PKCS#1v2.2 mentioned in the question reads:

Note. Care must be taken to ensure that an opponent cannot distinguish the different error conditions in Step 3.f, whether by error message or timing, or, more generally, learn partial information about the encoded message EM. Otherwise an opponent may be able to obtain useful information about the decryption of the ciphertext C, leading to a chosen-ciphertext attack such as the one observed by Manger [35].

That note actually refers to the test (bolded below) at the end of Step 3.g of the decryption operation:

Separate DB into an octet string lHash’ of length hLen, a (possibly empty) padding string PS consisting of octets with hexadecimal value 0x00, and a message M as
            DB = lHash’ || PS || 0x01 || M .
If there is no octet with hexadecimal value 0x01 to separate PS from M, if lHash does not equal lHash’, or if Y is nonzero, output “decryption error” and stop.

The “verify the label” in the question refers to the comparison of lHash (the hash of the label or of the empty string is there is no label) and lHash’. The byte Y is the one on the left of the bytestring representing $c^d\bmod n$ in big-endian notation over just as many bytes as required to represent the public modulus $n$, and $c$ essentially is the ciphertext presented to the decryption engine.

If we perform the comparison of lHash’ and lHash only conditionally if the comparison of Y to 0x00 succeeds (for example, if we compare Y || lHash’ to 0x00 || lHash with memcmp of the C standard library), then we are precisely in the conditions required by Manger's attack, which allows to decipher a message by iteratively submitting incorrect cryptograms to a decryption device and observing it's reaction.

If we perform the comparison of lHash’ to lHash in non-constant time but regardless of if Y matches 0x00 (and perform that test of Y and it's aggregation with the test of lHash’ in constant time, or perform that test of Y conditionally if the comparison of lHash’ to lHash succeeds), the situation is not nearly as bad, because our timing variation leaks no clue about if Y matches 0x00, which is what the adversary most wants to know. Even though the adversary still gains partial information about EM, I don't see that an attack can be made to work, even with much more queries to the decryption engine, because every byte of lHash’ at time of comparison depends on each bit of EM beside those in Y.

Not checking lHash’ is not a correct implementation of RSAES-OAEP with no support of tag (in that case the comparison must be performed against the hash of the empty string), and is likely to enable Manger's attack.


I can think of pre-shared secret label being guessed by an outsider with the encryption public key as one scenario.

My mental picture for the label is that it is a public constant intended to allow a single public/private key pair to be used in different independent contexts. That's useful to avoid attacks that relay an externaly authenticated ciphertext (e.g. signed by the originator) to a context not intended to receive it. I had never realized that the label (or it's hash) can be a pre-shared secret, and used to authenticate the cryptograms submitted to an RSAES-OAEP decryption device. If there is a security proof of RSAES-OAEP under that usage, I missed it. And indeed it's then ultra-critical that the comparison between lHash’ and lHash is constant-time.

Are there others?

Beside Manger's attack considered above, I don't see any.

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.