9
$\begingroup$

I have written a code to encrypt a plaintext as below. Here I am using bouncycastle crypto provider and referring to the RSA+OAEP for that.

public static void main(String [] args) throws Exception {
    Security.insertProviderAt(new BouncyCastleProvider(), 1);
    String ciphertext = Base64.encode(encrypt(plaintext));
    String recoveredPlaintext = decrypt(Base64.decode(ciphertext));
}

private static byte [] encrypt(String plaintext) throws Exception {
    KeyStore keyStore = getKeyStore();
    Certificate[] certs = keyStore.getCertificateChain("oaep");
    Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPwithSHA1andMGF1Padding","BC");
    cipher.init(Cipher.ENCRYPT_MODE, certs[0].getPublicKey());
    return cipher.doFinal(plaintext.getBytes());
}

private static String decrypt(byte [] ciphertext) throws Exception {
    KeyStore keyStore = getKeyStore();
    PrivateKey privateKey = (PrivateKey) keyStore.getKey("oaep",
            "oaep".toCharArray());
    Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPwithSHA1andMGF1Padding","BC");
    cipher.init(Cipher.DECRYPT_MODE, privateKey);
    byte[] cipherbyte=cipher.doFinal(ciphertext);
    return new String(cipherbyte);
}

When I am googling I stumbled upon this blog post; which says that the RSA+OAEP is vulnerable to “Manger’s attack”.

  1. I wanted to know whether my code is effected with this vulnerability, if so how can I check that?

  2. There are several PKCS#1 versions. Which version's implementation has been used in the bouncycastle and how can I get to know the exact version (2.0,2.1,2.2) of PKCS# 1?

$\endgroup$
  • 2
    $\begingroup$ well you should at least explicitly specify the padding RSA/ECB/OAEPWithSHA-256AndMGF1Padding and then you will know what is really used (Java by default uses pkcs1.5 when not specified, I am not sure for BC) $\endgroup$ – gusto2 Jul 27 '18 at 7:42
  • $\begingroup$ Note that using new String or getBytes without explicitly mentioning the character set is a known source of encoding bugs as it uses the platform default. I'll not talk about the exception handling; I presume the code is for showing us the problem at hand. $\endgroup$ – Maarten Bodewes Jul 28 '18 at 15:16
7
$\begingroup$

Bouncy Castle Java releases 1.60 and FIPS 1.0.1 (and former) have precisely the issue exploited in Manger's attack: an exception occurs when a ciphertext $c$ is submitted such that $c^d\bmod N$, expressed as a bytetring as wide as $N$, does not start with a 0x00 byte; and then the rest of the decryption process does not occur, leading to markedly faster execution. If an adversary can iteratively submit a few thousands messages for decryption and detect the exception or the faster execution, s/he can decipher a ciphertext, or make a signature. The private key itself does not leak.

Pre-release version 1.61b03 (available here, also on GitHub) has a fix that removes the unwanted exception, and reduces timing variation by orders of magnitude. If it remains vulnerable, that could only be with precise and repeated timing by an attacker.


Manger's attack and countermeasures in later editions of PKCS#1v2

The attack is exposed in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001). It exploits an RSA decryption system that leaks a little information about $y=x^d\bmod N$ for $x$ repeatedly chosen by an attacker.

The applied part of the attack focuses on the leak of if $y<2^{8k-8}$ with $N$ of $8k-7$ to $8k$ bit; or equivalently: does $y$ start with a 0x00 byte when expressed as a big-endian bytestring of $k$ bytes, as it should in RSAES-OAEP padding:

OAEP

In PKCS#1 v2 7.1.2 (Decryption operation) step 4, that 0x00 is verified thru the use of "length $k-1$" in:

Convert the message representative $m$ to an encoded message $\text{EM}$ of length $k-1$ octets: $\text{EM}=\text{I2OSP}(m,k-1)$
If I2OSP outputs "integer too large," then output "decryption error" and stop.

PKCS#1v2 has a note stating that the above "decryption error" must be identical to one that can occur on failure of another redundancy check made after OAEP's masking is undone.

Manger observed that not all implementations do this properly; and those that do as instructed take less time when that test fails (due to the stop, the rest of the rest of the procedure is not performed, saving time), thus timing can reveal the desired bit of information.

This is addressed in PKCS#1 v2.1 (and PKCS#1 v2.2, identical in this regard) by using $\text{I2OSP}(m,k)$ without the $-1$, which outputs an extra additional byte $Y$ and never triggers an error. $Y$ is tested in the end, together with other redundancy criteria applying to the message after OAEP unmasking.

If there is no octet with hexadecimal value 0x01 to separate $\text{PS}$ from $M$, if $\text{lHash}$ does not equal $\text{lHash’}$, or if $Y$ is nonzero, output "decryption error" and stop.
Note. Care must be taken to ensure that an opponent cannot distinguish the different error conditions in (the above), 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, leading to a chosen-ciphertext attack such as the one observed by Manger.

All versions of RSAES-OAEP in PKCS#1v2.0, 2.1 and 2.2 are interoperable, and the procedures described lead to identical results, except that their timing variation is less likely to leak information in 2.1 and later.


Bouncy Castle's code

In Bouncy Castle's version 1.60 (current when the question was asked and this answer first drafted) the code specific to RSAES-OAPEP decryption is decodeBlock in OAEPEncoding.java. That contains

    byte[]  data = engine.processBlock(in, inOff, inLen);
    byte[]  block = new byte[engine.getOutputBlockSize()];
    // as we may have zeros in our leading bytes for the block we produced
    // on encryption, we need to make sure our decrypted block comes back
    // the same size.
    System.arraycopy(data, 0, block, block.length - data.length, data.length);

The definition of engine is such that processBlock returns data with leading zero bytes suppressed, and getOutputBlockSize returns $k-1$ when $N$ is $k$-byte. It follows that block.length - data.length is $-1$ when $(c^d\bmod N)\ge2^{8k-8}$, and then System.arraycopy makes an ArrayIndexOutOfBoundsException not locally caught nor listed in those that the caller is invited to expect, and that the rest of the function is not executed.

$\endgroup$
  • 1
    $\begingroup$ Heh, the code in the question doesn't use any padding at all. I just gave it one zero byte, and I got back an empty octet string after decryption; it decrypts back to plaintext when I give it "RSA/ECB/NoPadding" which ignores padding and doesn't strip it :P $\endgroup$ – Maarten Bodewes Jul 27 '18 at 23:40
  • $\begingroup$ I have mistakenly added the "RSA";which means NoPadding in the above code snippet. But it should be "RSA/ECB/OAEPwithSHA1andMGF1Padding". $\endgroup$ – NShani Jul 28 '18 at 8:36
2
$\begingroup$

The RSAES-OAEP scheme in PKCS1 v2.0, v2.1 and v2.2 (rfc2437, rfc3447, rfc8017 respectively) is the same scheme, although the notation changed between 2.0 and 2.1; see why did oaep change from pkcs1 v2.0 and v2.1? and https://stackoverflow.com/questions/42709020/is-there-a-default-label-for-the-built-in-rsa-oaep-encryption-in-java . This scheme is slightly different from (not interoperable with) the one originally proposed by Bellare & Rogaway.

The JCA API does not allow for returning any indication of the RSA-decrypted but still-padded value being < $2^{(nsize-detectable)}$ so there can't be an explicit oracle. The BC implementation of unpadding in org.bouncycastle.crypto.encodings.OAEPEncoding obviously tries to be constant-time and I don't see anything they missed. However, the underlying RSA 'core' (which is org.bouncycastle.crypto.engines.RSABlindedEngine to defend against timing or sidechannel there) does indirectly put the result in a BigInteger temporarily, which might give some timing signal, although I think only very rarely for the (round-binary) keysizes commonly used, because the value must have top 32 bits zero not just 8. You could try testing it if you want to be sure.

Of course this only matters if the attacker can receive the signal; if they're local (on the same machine) there are usually several possibilities, but if they're remote it can only work if you (always) give a prompt visible response to every purported ciphertext (good or bad).

Also, as Maarten commented, using the JVM default charset for encoding and decoding is a good way to get your data corrupted, at least intermittently, though not a security issue.

$\endgroup$
  • $\begingroup$ At the time we first reviewed it, the BC implementation of unpadding in org.bouncycastle.crypto.encodings.OAEPEncoding had a shortcoming that we both missed (see my updated answer). I initially focused on other, comparatively minor timing dependencies. It is only after I understood the exact interface of the RSACoreEngine that I found Manger's attack indeed applied, in its simplest form. $\endgroup$ – fgrieu Aug 18 '18 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.