RSA OEAP tests with small ciphertext should fail

[2024Dan]

There are three vectors (376, 385, 392) in rsa_oaep_misc_test.json that have ciphertext == 0 or ciphertext == 1.

Currently these vectors are expected to pass, which matches what is defined in section 5.1.2 of RFC 8017: 5.1.2. RSADP c ciphertext representative, an integer between 0 and n - 1

Perhaps these vectors should fail, to match what is defined in section 7.1.2 of NIST SP 800-56Br2: _7.1.2 RSADP

2. c: the ciphertext; an integer such that 1 < c < (n – 1)_

[bleichenbacher-daniel]

Nice. I wasn't even aware that there are discrepancies between RFC 8017 and the NIST standard. Theoretically, the encryption in NIST SP 800-56 would have to say that if 1 < c < n-1 is not satisfied then the sender should change the seed and try again. However, getting c=1 is so unlikely it will never happen and I had to do some work to even construct such cases.

I think that neither accepting or rejecting these test vectors should therefore count an issue. The main reason why I added these test vectors is simply to have some edge cases to look for problems in the integer arithmetic. Maybe the test vectors can be replaced with test cases that are acceptable by all standards. Unfortunately, I don't have access to the generation code and can't update the test vectors on this site.

[bleichenbacher-daniel]

Maybe a first question to ask here is accepting c=1 ciphertexts as valid leads to any problems with OAEP. I don't see any, but I'm just doing a handwaving analysis which could not be careful enough.

The construction doesn't require the knowledge of the private key. That seems not a problem, since OAEP is not authenticated. The construction requires to select a specific seed, label and compute the corresponding plaintext. Thus plaintext awareness is not violated either. Also https://www.cl.cam.ac.uk/~rja14/Papers/robustness.pdf shows that RSA is not key committing, hence the property that one can find multiple keys for which c=1 is a valid ciphertext is not violating any expectations either.

NIST often includes practical considerations. E.g. one could argue that seeing an edge case ciphertext is most likely not a random fluke but almost certainly some implementation error, hardware malfunction or attack.

[bleichenbacher-daniel]

I'm removing the test vectors with edge case values for c as long as their treatment is ambiguous. They can be replaced by other ones where the decryption encounters edge case behavior modulo one of the primes only. This assumes of course that the decryption uses CRT. However it has significant advantages. The construction is more flexible. It is now possible to generate test vectors with edge case behavior for standard key sizes such as 2048 bits (as long as the two hashes are the same and their digests are smaller than a quarter of the modulus)

Some new test vectors are temporarily here: https://github.com/bleichenbacher-daniel/Rooterberg/tree/main/test_vectors/rsa_encryption The format of the test vectors is not yet clear an may change in the future.