Why random number used in RSA padding but not in AES?

Question

I noticed that people use a random number in the RSA-OAEP padding scheme to avoid deterministic encryption. But in pkcs#7 people just use the padding size rather than some random bits. Doesn't it make AES deterministic?

Answer 1

They are different concepts and have different approaches. AES like any block cipher is a primitive and the encryption is performed by using the block cipher mode of operation. Like ECB,CBC,CTR,GCM,EAX...

The pkcs#7 padding or any other padding that is used to fill the last block to the block size with ambiguous remove, not designed for randomization. Even one can design a randomized padding mechanism it can affect at most 2 blocks without wasting the other blocks. Therefore not a good randomization point. Indeed, the CTR and OFB don't use padding at all.

The randomization ( probabilistic encryption) is achieved by using IV/nonce.

Since the insecure ECB doesn't use an IV, it doesn't have Indistinguishability under chosen CPA attack (Ind-CPA). This is the minimum requirement for modern Cryptography, but not enough. The other modes have IND-CPA.

Like other Authenticated Encryption modes, AES-GCM can have IND-CCA2. And we prefer the Authenticated Encryption ( with Associated Data (AEAD)) to use. The common modes are AES-GCM, ChaCha20-Poly1305, EAX, and CCM. TLS 1.3 standard has the AES-GCM, AES-CCM, and ChaCha20-Poly1305 AEAD cipher modes.

And note that Authenticated Encryption is a stronger notion, AEAD > IND-CCA.

One should note that IV/nonce is necessary but not sufficient for security. For example, the CBC IV must be more than a nonce, it must be unpredictable. For the CTR mode, the (key,IV) pair must never be reused ( similar to GCM mode since it uses CTR mode inside). There is a mode against the nonce misuse: SIV (Synthetic Initialization Vector) mode, it called a nonce-misuse resistant authenticated-encryption.

Answer 2

But in PKCS#7 people just use the padding size rather than some random bits. Doesn't it make AES deterministic?

The padding used for block ciphers is just used to make sure that the plaintext can be split up into message blocks. A few block cipher modes such as ECB and CBC require this due to the way they work. Note that CipherText Stealing (CTS) can be used instead if the expansion of the ciphertext is detrimental to the scheme. Most other modes don't require that the message is split into full blocks, so padding does not need to be applied at all.

The padding specified within PKCS#7 (which itself is not a padding standard, it defines the Cryptographic Message Syntax) is indeed fully deterministic. It only depends on the size of the plaintext message after all. The contents of the message are entirely inconsequential. For this reason it requires a full extra block even if the message is already a multiple of the block size. Without it you'd need some way to distinguish the final part of the message from the padding (e.g. using a length indicator at the start).

I noticed that people use a random number in the RSA-OAEP padding scheme to avoid deterministic encryption.

As indicated the padding is indeed not used to randomize the plaintext message. The many padding schemes used for RSA are required to make RSA secure. However, the padding of block ciphers doesn't play any role with regards to security. If anything, PKCS#7 padding makes the block cipher mode less secure. Padding Oracle attacks are a well known way to attack CBC mode in transport mode, for instance. These can be avoided by careful implementation - e.g. in older SSL/TLS up to 1.2 - or by verifying a MAC/signature before decryption.

The way to avoid deterministic encryption for block cipher modes is to use an IV. The key and IV together provide the randomization required. All IND-CPA secure mode modes of operation require an IV, otherwise the ciphertext message is easily distinguished from random: just encrypt the same message twice and you get the same ciphertext. The type of IV required depends on the mode of operation.

For CBC mode the IV needs to be fully unpredictable (which is usually translated into "random", although "randomized" would be a better term). Other modes - such as the common counter mode (CTR) used in GCM and many other schemes - simply require a nonce, a unique value. This can be enough for many modes because - to the attacker - the key is already indistinguishable from random. You just need a unique value to make sure that the ciphertext of (partially) identical messages cannot be compared.

---

RSA is entirely different as the RSA security entirely relies to a large degree on the padding. With AES you can encrypt a single message block with a random key and get a secure ciphertext. If you'd do that with RSA you may be vulnerable to attack. This can be easily seen by just encrypting the value zero: the ciphertext would be zero too. However, there are many, many other attacks on "textbook" RSA.

That's why RSA requires a secure padding mode such as OAEP to encrypt messages. OAEP is provable secure and is easier to secure against padding oracles. To avoid those altogether hybrid encryption using RSA-KEM can be used, which is a secure RSA mode that doesn't require any padding (it encapsulates a random key with the same size as the modulus, which is provably secure).