Why does decryption fail after modification of the ciphertext for RSA with OAEP padding

Question

I have ciphertext which was encrypted using RSA with "OAEPWithMD5AndMGF1Padding" - i.e. OAEP using MD5 for the Mask Generation Function.

I understand the general idea of how the randomized padding works, but I'm not completely sure why the decryption process completely fails if I change one byte of the ciphertext. How does the algorithm spot that there were changes and why does it not return some random plain text?

---

For demonstration purposes, here is my code in Java:

        int              ilgis = 0;
        BigInteger       ct = new BigInteger("2D9487AA09DBE708084A97CC466A7CB2CAE2E00100D11FF8C79CF0568858F91E2A5CFC8FD3007F530FC12695870F", 16);
        byte[]           inputBytes = ct.toByteArray();
        SecureRandom     random = new SecureRandom();
        Cipher           cipher = Cipher.getInstance("RSA/None/OAEPWithMD5AndMGF1Padding", "BC");
        KeyFactory       keyFactory = KeyFactory.getInstance("RSA", "BC");

        RSAPublicKeySpec pubKeySpec = new RSAPublicKeySpec(
                new BigInteger("00A17DE2DBF5C2C68AF8EA044547670D3C8E2F4F9693804B7EC6FBCA5F09D0ABF85A73DB4DFC8FFF0EADF9B040375D", 16),
                new BigInteger("03", 16));
        RSAPrivateKeySpec privKeySpec = new RSAPrivateKeySpec(
                new BigInteger("00A17DE2DBF5C2C68AF8EA044547670D3C8E2F4F9693804B7EC6FBCA5F09D0ABF85A73DB4DFC8FFF0EADF9B040375D", 16),
                new BigInteger("6BA941E7F92C845CA5F1582E2F9A08D30974DFB9B7AADBEF595662C4E29DD76FDEDF48F5CBBD4ED2E961355F2013", 16));

        RSAPublicKey pubKey = (RSAPublicKey)keyFactory.generatePublic(pubKeySpec);
        RSAPrivateKey privKey = (RSAPrivateKey)keyFactory.generatePrivate(privKeySpec);

        System.out.println("Ciphertext: " + toHex(inputBytes, inputBytes.length));
        cipher.init(Cipher.DECRYPT_MODE, privKey, random);
        byte[] plainText = new byte[cipher.getOutputSize(inputBytes.length)];

        ilgis += cipher.doFinal(inputBytes, 0, inputBytes.length, plainText, 0);
        System.out.println("Plain text : " + toHex(plainText, ilgis) + " length: " + ilgis);
```

Answer 1

Let's look at the decryption part of RFC 8017 for OAEP. Let's only look at step 3, as step 1 is called length checking, and step 2 is the step to perform modular exponentiation and integer to octet string conversion (or, rather interpretation). Step 1 can fail but is out of scope for this as it acts on the ciphertext itself, step 2 cannot fail, even though the result may not make sense.

So here is step 3. Note that EM is the message after modular exponentiation with the private exponent, i.e. the input that should be generated after step 3 in the encryption phase.

3.  EME-OAEP decoding:

    a.  If the label L is not provided, let L be the empty string.
        Let lHash = Hash(L), an octet string of length hLen (see
        the note in Section 7.1.1).

Label L is a configuration option and therefore doesn't have to do with error checking. So we can know lHash regardless of any calculations performed during decryption.

    b.  Separate the encoded message EM into a single octet Y, an
        octet string maskedSeed of length hLen, and an octet
        string maskedDB of length k - hLen - 1 as

           EM = Y || maskedSeed || maskedDB.

This just splits the message EM without regard of the value of the octets.

    c.  Let seedMask = MGF(maskedDB, hLen).

Some function to calculate the seedMask, will finish without regard of the input...

    d.  Let seed = maskedSeed \xor seedMask.

Some function to calculate the seed, will finish without regard of the input...

    e.  Let dbMask = MGF(seed, k - hLen - 1).

Some function to calculate the dbMask, will finish without regard of the input...

    f.  Let DB = maskedDB \xor dbMask.

Some function to calculate the DB, will finish without regard of the input...

Now this is interesting, since we now have seed, dbMask but more importantly DB, which all have been defined in the encryption function as well. In other words, this whole process so far reversed the calculations in the padding process. If the input is garbage, then DB won't match the DB during encryption, but the above calculations will conclude in some result.

    g.  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.

Splitting DB of course is still performed without evaluating the values in the octets.

        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.  (See
        the note below.)

Finally, after all these calculations, we do some validation, before actually outputting M, which is the encrypted plaintext message. This is deliberately placed as final check, because we could have checked Y back at step 3b where it was the direct result of the modular exponentiation. To know why, see the section below.

So first we have to check the initial octet is 00 (although we may want to postpone that, see the section below).

Then most importantly we check if lHash' matches the hash over the label l, which is a configuration option so known beforehand. Generally, this label l cannot even be configured in implementations of RSA-OAEP so we can usually assume that lHash is simply the hash over an empty (zero octet) message, i.e. a constant specific to the configured hash function.

This is the most important step because it will check a full hash output size (in your case 16 octets for MD5) for correctness. And these 16 octets depend on all the other octets due to the masking process. Well, all other octets apart from Y that was already validated anyway. So there is negligible chance that the bits of this constant value are correct if any bits of EM have been altered.

Then we go over PS, expecting only 00 octets until the next octet which should have value 01 (if you look at it like that you don't have to check the 00 octets, just check if the first non-zero octet is 01). Finally we have M which can be anything so there is no possibility to check.

The chance that octet Y is correct and / or that the PS padding (which may be 0 bytes) and 01 byte is correct if incorrect ciphertext or key is used is around 1 in 192 * 256, depending somewhat on the modulus value. Although that chance is not very high, it is far from being negligibly small. So comparing the lHash and lHash' values is the comparison that matters.

---

Now for completeness, the note:

Note: Care must be taken to ensure that an opponent cannot
distinguish the different error conditions in Step 3.g, whether by
error message or timing, and, more generally, that an opponent
cannot 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 [MANGER].

OK, so that's just about avoiding side channel attacks on the final validation.

It can probably be implemented very easily by validating lHash in a time-constant manner first. If that step hash negligible chance of completing if EM has an incorrect value, then obviously the Y must have value 00 and the separator be present and correct if it does complete.

---

If you want to know even more about OAEP padding validation and why it is secure then you probably have to consult the security proofs that have been presented for RSA-OAEP.