June 15, 2015
Java's JCA (Java Cryptography Architecture) specifies an API for cryptographic algorithms, which can be implemented by what is referred to as "cryptographic providers", i.e. libraries implementing the API functions. This allows Java applications to use an abstract common interface without having to commit to a specific cryptographic implementation. Java is shipped with a set of default providers and a variety of open source and commercial providers exist. The latter often come into play when cryptographic hardware support should be made available to an application.
So far, so good. In general, one would assume that when checking cryptographic Java application for flaws, these have to be searched foremost in the application or the cryptographic providers themselves. However, here, we will address a feature of the JCA API which must already be considered a flaw. Specifically, this is the fact that there, RSA is treated as block cipher. For instance, an RSA cipher object can be instantiated as follows:
Here, "ECB" is a block cipher mode of operation, which simply means that if the encrypted data is longer than what can be input to a single RSA encryption operation, repeated RSA operations are executed and the output is concatenated. "OAEPWithSHA1AndMGF1Padding" indicates that before each RSA encryption, the plaintext is subject to the OAEP encoding method, the purpose of which is explained further down.
Before we identify the problem about this fact, let us first understand what lead the creators of the JCA API to take this design decision. As a matter of fact, raw RSA indeed comes close to a block cipher, as it is, like a block cipher, what is referred to in mathematics as a permutation. However, it clearly does not fulfil all requirements for a block cipher. For multiple reasons, the use of raw RSA is insecure, and it is not part of our cryptographic toolbox at all.
Consequently, RSA always has to be used with a suitable encoding method (a.k.a "padding"). One such example is the OAEP encoding, a.k.a PKCS#1 v2.1 encoding. This is a modern encoding method for RSA, avoiding all known vulnerabilities of older encoding methods, such as PKCS#1 v1.5. Specifically, an RSA ciphertext encrypted using the OAEP encoding method, with appropriate parameters, cannot be altered without the recipient detecting this during decryption. This feature is generally referred to as the "integrity" of the plaintext.
This brings us to the question, which problems result if RSA would be used in ECB mode. First of all, it is interesting to note, that the commonly known flaw of the ECB mode, i.e. the production of identical ciphertext blocks for identical plaintext blocks and thus the visibility of patterns in the ciphertext does not apply. This is due to the following: Any secure RSA encoding method must ensure that the same plaintext encrypted twice does not produce the same ciphertext. If this were not the case, then this encoding would already be flawed when used for the encryption of a single RSA plaintext block. Specifically, we must take into account, that messages to be encrypted may very well be of low entropy, for instance short strings like "yes" and "no". In this case, a deterministic encryption in the above sense would be broken by the attacker simply iterating through all the guessed messages, encrypting them, and comparing the encryption result to the ciphertext in question. In symmetric cryptography, i.e. when using block ciphers, this does not apply since in general, the encryption operation is not accessible to the attacker. All secure encoding schemes for RSA prevent this vulnerability by adding random data to the message data.
The actual problem that results when using RSA in ECB mode is related to the integrity protection of scheme used for the encryption of the individual blocks: An attacker could alter a message consisting of multiple RSA-OAEP blocks by removing, reordering or inserting blocks. For the latter, he could freely insert blocks decrypting to plaintexts of his choice. This would subvert the security features of the OAEP encoding to a large extend. The same applies to encoding methods with less stringent integrity protection features, such as PKCS#1 v1.5, where the attacker's possibilities for manipulations of the plaintext are also extended.
The correct way of dealing with data of a length which cannot be encrypted in a single RSA block certainly is hybrid encryption, where the public-key scheme is used for the encryption of a symmetric key, which then is used for the encryption and authentication (integrity protection) of the payload data.
To see that the problem discussed here has actually to be considered a flaw in the JCA API, first of all note, that in the Java JCA specification, it is even explicitly required that the insecure Java cipher combination "RSA/ECB/OAEPWithSHA1AndMGF1Padding" is supported by any provider. However, obviously, at least some cryptographic providers do not allow the encryption of multiple blocks. But this does not necessarily hold for any provider, and an implementer of a Java cryptographic provider adhering to the JCA specification may easily realize this functionality as indicated. Then the responsibility for the avoidance of the insecure combinations completely falls to the implementers of the application, who, however, will be easily mislead by the Java specification which propagates these insecure schemes. Furthermore, they might even be tempted to implement those insecure schemes documented in JCA specification within their applications with code of their own, even if the cryptographic providers they use, do not offer them.
To get an idea of the confusion that this design choice in the JCA caused among implementers, it is sufficient to glance over the following discussions (in none which the actual threats are indicated correctly, however):