17
$\begingroup$

As I understand, ECB should not be used as encryption mode unless you are encrypting single blocks of data which are always unique and only are encrypted once.

I have a collection of ids represented by integers that I encrypt and transmit (individually) with the same public key using RSA/ECB/PKCS1PADDING. Sometimes the same ids are encrypted and transmitted multiple times but as far as I can tell the ciphertext is never the same.

Can anyone tell me how this is possible? As far as I understand, this would not be an acceptable scenario to use ECB, but why are the encrypted messages never the same even though the key and plaintext messages are?

$\endgroup$
2

2 Answers 2

23
$\begingroup$

The Java algorithm string "RSA/ECB/PKCS1Padding", as you already found out, does not implement ECB; it only encrypts/decrypts a single block. The Bouncy Castle cryptographic security provider has a better named algorithm string, "RSA/None/PKCS1Padding", which better indicates that no mode of operation is used. It is likely that "/ECB" was just included to mimic the cipher string for block ciphers. So you would have to call the cipher "RSA/ECB/PKCS1Padding" multiple times to implement ECB.

"PKCS1Padding" indicates RSA with PKCS#1 v1.5 padding for encryption. This padding is indeterministic - i.e. it uses a random number generator. This explains why each ciphertext block will be different.


To make RSA secure it is required to use a secure padding scheme. If PKCS#1 v1.5 padding is used then there is a significant (11 byte) overhead for each block of plaintext. The padding consists of at least eight bytes of positive random values which explains why the ciphertext is always different even if the same plaintext block is encrypted. If you would use RSA in ECB mode then you would end up losing the padding overhead for each block. That means that the ciphertext would be significantly larger than the plaintext.

Furthermore, RSA operations require a lot of CPU resources. The RSA encryption/decryption operations are based on modular exponentiation with extremely large numbers. Using RSA operations on many blocks will therefore use a lot of CPU time. This is especially true for decryption; encryption has the advantage that the public exponent is generally relatively small. But even RSA encryption will be a lot more CPU-expensive than any symmetric cipher.

To encrypt larger messages you should be using a hybrid cryptosystem where asymmetric (RSA) encryption is paired with a fast, efficient symmetric cipher such as AES. In your case where you encrypt a large amount of numbers it is better to aggregate them in a structure, encrypt the structure using AES and then encrypt the AES key using your RSA public key.


Notes:

  • OAEP is more secure than PKCS#1 padding. If you choose OAEP then the padding overhead is even larger, making ECB even less efficient;
  • It is also possible to use RSA-KEM or any other technique to establish the symmetric key - those techniques are however not present in the Java JCA library as of now;
  • For block ciphers ECB performs the block cipher operation for each block in the plaintext. This is not secure in most situations, independent of the padding used. It is however useful as a lower level operation such as key wrapping of a symmetric key;
  • Instead of designing your own protocol you could be using container formats such as the Cryptographic Message Syntax (CMS) or Pretty Good Privacy (PGP); both formats already implement a hybrid cryptosystem;
  • Increasing the key size only to support larger messages is generally not recommended: it would require a huge increase of CPU time during encryption and decryption, only dwarfed by the time it takes to generate the larger RSA key pair;
  • You may want to sign the message before encryption for additional security (sometimes it makes more sense to sign afterwards, it depends on the use case);
  • Using all possible bytes for PKCS#1 v1.5 padding comes with a downside: the random padding is only ~64 bits so there is a possibility of a collision with an earlier padding due to the birthday bound - it is better to use an overhead of 19 bytes instead of 11 bytes and have ~128 bits of padding.
$\endgroup$
3
  • $\begingroup$ Love this answer. I had to figure this out the hard way. Stupid Java causing RSA ECB confusion for us. Wish I'd found this answer 3 hours ago. :-) $\endgroup$ Apr 30, 2017 at 5:02
  • 1
    $\begingroup$ Addition: PKCS#1v1 encryption padding, aka RSAES-PKCS1-v1_5, is to be considered obsolete and harmful, because (A) it's very difficult to make a practical decryption system that can't be turned into a decryption oracle, see Bleichenbacher's attack and it's many declinations. (B) The 11-byte overhead includes only 64-bit random, and enumerating these [thus being able to verify a message guess] should no longer be considered out of reach. $\endgroup$ May 11, 2021 at 7:19
  • $\begingroup$ OAEP is already mentioned, I changed the answer explicitly to indicate the ~64 bit random issue (in the last note). I added the ~ because the bytes are random in the range [1-255], which is 63.954827494870863500624995073980888309087304664495058885096944917 bits - although it literally doesn't matter a bit :P $\endgroup$ May 11, 2021 at 13:41
0
$\begingroup$

Without knowing the exact implementation you are using, from the algorithm name, I think you are generating a random key for the symmetric cipher and encrypting that with the RSA key. This way your ciphertexts will be unique.

I would recommend using a cipher mode that provides integrity protection, such as AES-GCM or Poly1305-AES. ECB could be dangerous if later in the development your messages become longer than a single block or you start re-using symmetric keys.

You should also defend against replay attacks. What are the consequences if someone intercepts and re-transmits a valid ID?

Have you considered using an existing protocol, e.g. tunnelling over SSH or TLS? You can use key pinning and select a single good cipher suite if necessary.

$\endgroup$
2
  • $\begingroup$ See my edit. I will probably use SSL as extra security, but the data needs to stay encrypted at the server side at all times. I will look into defending against replay attacks, thanks! $\endgroup$ May 25, 2015 at 0:16
  • $\begingroup$ @user3685322 : $\:$ It would be much better to use TLS, rather than SSL. $\;\;\;\;$ $\endgroup$
    – user991
    May 25, 2015 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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