6
$\begingroup$

I'm reading about OAEP / PKCS padding used for PGP to turn deterministic algorithms like RSA from deterministic encryption to probabilistic encryption (randomness in the resulting output). That way the same input encrypted with RSA should produce a different output each time.

However, the wikipedia page for probabilistic encryption addresses a seeming simple solution but doesn't give any details what is wrong with it:

An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm. Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding. However, early schemes which applied this naive approach were broken due to limitations in some deterministic encryption schemes. Techniques such as Optimal Asymmetric Encryption Padding (OAEP) integrate random padding in a manner that is secure using any trapdoor permutation.

Can someone explain (to a beginner) what is insecure about random padding being added?

In addition, for PGP encryption using RSA, my understanding is that a random nounce / AES key is generated and encrypted using RSA. Then that AES key is actually used to encrypt the source text.

So, if the whole AES key is random to begin with (and required to know anything about the encrypted text) - what exactly is OAEP adding?

Improve this question
$\endgroup$
4
  • $\begingroup$ Related question about not using padding with RSA. $\endgroup$
    – Xeoncross
    May 24, 2016 at 15:42
  • 3
    $\begingroup$ The problem are attacks where an attacker modifies the ciphertext. If the receiver isn't very careful they might either accept a modified message or act as padding oracle. $\endgroup$
    – CodesInChaos
    May 24, 2016 at 16:51
  • $\begingroup$ So would a hash included with the AES key (RSA(AES key + fixed length hash)) be as good as actual OAEP over the plaintext before AES? (AES(OAEP(plaintext))) $\endgroup$
    – Xeoncross
    May 24, 2016 at 20:41
  • $\begingroup$ Note that usually you would need a hybrid cryptosystem anyway as RSA is only suitable for relatively small messages. In that case you could use RSA-KEM. KEM simply encrypts a secret as large as the modulus and then performs key derivation over the unencrypted value. The resulting symmetric key can then be used to encrypt / decrypt. Basically it does padding but skips the message ;), and integrity can be validated using an AEAD cipher (of course any adversary can still encrypt, for authenticity you'd need a signature). $\endgroup$
    – Maarten Bodewes ♦
    Dec 6, 2022 at 19:11

2 Answers 2

Reset to default
3
$\begingroup$

The padding used for RSA is not the PKCS #5/#7 padding (as you seem to suggest in your own answer), but the Wikipedia entry seems to refer to PKCS #1 v1.5 (RFC2313)) which uses a padding

00 || BT || PS || 00 || D

where for RSA encryption we start with a 0x00-byte (to guarantee that the resulting number is below the modulus), then use BT (Block Type) equal to 0x02, the padding string (PS) is at least 8 long and consists of random non-zero bytes, the single 0x00 is added followed by the actual data being encrypted (D), and so that the total length equals the effective length in bytes of the modulus.

The padding can then be uniquely removed because the start of the RSA-decrypted block should follow this pattern that we can check, and we strip random bytes until we meet the first 00, after which we have the data.

The problem lies in implementations that check this padding and that somehow leak (e.g. by the different possible error responses, or time used for checking etc.) how exactly the padding removal failed (no start 00, no 02 byte, padding too short, data unexpected length..) and attacks were developed based on that (see Bleichenbacher oracle etc.). So the padding does work, but it is "ad hoc" (it has no proof of security) and it's too easy to do the checking in a wrong way. Hence OAEP, which has more of a theoretical basis.

Improve this answer
$\endgroup$
-1
$\begingroup$

I naively forgot that with a "random" amount of padding added the receiver would not know how many bytes to remove. That is why PKCS #5/#7 add the number of bytes as the padding value. For example, if we need to add 4 bytes then the last part of the message would look like: [... 04 04 04 04].

So the answer is PKCS #7 is the only possible way to add padding when the receiver doesn't know where the message stops and starts. Random padding isn't possible but correct padding is required for AES in block mode.

I'm still curious what wikipedia is talking about though...

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ PKCS#5/7 a deterministic padding is designed for block-ciphers and not for RSA. PKCS#5 padding only supports 64 bit blocks, PKCS#7 is limited to either 2040 or 2048 bits. PKCS#1 specifies padding for RSA, but the PKCS#1v1.5 variant is not secure against chosen ciphertext attacks, which is why it was replaced by OAEP in 2.0. $\endgroup$
    – CodesInChaos
    May 24, 2016 at 18:18
  • 2
    $\begingroup$ Also there are many ways to add removable variable-length padding, PKCS#7 is not the only one. For example if you want a deterministic padding you can simply add a single 1 bit followed by as many 0 bits as needed. (Note that this is even less secure in the context of RSA) There is also a padding that encodes the length of the padding and then uses random bytes for the rest. $\endgroup$
    – CodesInChaos
    May 24, 2016 at 18:22

Your Answer

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

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