Optimal asymmetric encryption padding: Difference between revisions

Revision as of 16:16, 4 June 2022

Latest revision as of 17:46, 12 July 2025

(17 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Scheme often used with RSA encryption}}

{{redirect|OAEP|the division of the Thailand Ministry of Science Technology and Environment previously known as the Office of Atomic Energy for Peace|Office of Atoms for Peace}}

In [[cryptography]], '''Optimal Asymmetric Encryption Padding''' ('''OAEP''') is a [[padding (cryptography)|padding scheme]] often used together with [[RSA (algorithmcryptosystem)|RSA encryption]]. OAEP was introduced by [[Mihir Bellare|Bellare]] and [[Phillip Rogaway|Rogaway]],<ref>[[Mihir Bellare|M. Bellare]], [[Phillip Rogaway|P. Rogaway]]. ''Optimal Asymmetric Encryption -- How to encrypt with RSA''. Extended abstract in Advances in Cryptology -– [[Eurocrypt]] '94 Proceedings, [[Lecture Notes in Computer Science]] Vol. 950, A. De Santis ed, [[Springer-Verlag]], 1995. [http://www-cse.ucsd.edu/users/mihir/papers/oaeoaep.pdf full version (pdf)]</ref> and subsequently standardized in [[PKCS1|PKCS#1 v2]] and RFC 2437.

The OAEP algorithm is a form of [[Feistel network]] which uses a pair of [[random oracle]]s G and H to process the plaintext prior to [[asymmetric encryption]]. When combined with any secure [[trapdoor one-way function|trapdoor one-way permutation]] <math>f</math>, this processing is proved in the [[random oracle model]] to result in a combined scheme which is [[semantic security|semantically secure]] under [[chosen plaintext attack]] [[ciphertext indistinguishability|(IND-CPA)]]. When implemented with certain trapdoor permutations (e.g., RSA), OAEP is also provedproven to be secure against [[chosen ciphertext attack]]. OAEP can be used to build an [[all-or-nothing transform]].

OAEP satisfies the following two goals:

Line 11 ⟶ 12:

The original version of OAEP (Bellare/Rogaway, 1994) showed a form of "[[plaintext-aware encryption|plaintext awareness]]" (which they claimed implies security against [[chosen ciphertext attack]]) in the random oracle model when OAEP is used with any trapdoor permutation. Subsequent results contradicted this claim, showing that OAEP was only [[ciphertext indistinguishability|IND-CCA1]] secure. However, the original scheme was proved in the [[random oracle model]] to be [[ciphertext indistinguishability|IND-CCA2]] secure when OAEP is used with the RSA permutation using standard encryption exponents, as in the case of RSA-OAEP.<ref>

Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and [[Jacques Stern (cryptographer)|Jacques Stern]]. ''RSA-- OAEP is secure under the RSA assumption''. In J. Kilian, ed., Advances in Cryptology --– [[CRYPTO]] 2001, vol. 2139 of Lecture Notes in Computer Science, SpringerVerlag, 2001. [http://eprint.iacr.org/2000/061.pdf full version (pdf)]</ref>

An improved scheme (called OAEP+) that works with any trapdoor one-way permutation was offered by [[Victor Shoup]] to solve this problem.<ref>

Victor Shoup. ''OAEP Reconsidered''. IBM Zurich Research Lab, Saumerstr. 4, 8803 Ruschlikon, Switzerland. September 18, 2001. [http://www.shoup.net/papers/oaep.pdf full version (pdf)]</ref>

More recent work has shown that in the [[Standard Modelmodel (cryptography)|standard model]] (that is, when hash functions are not modeled as random oracles) it is impossible to prove the IND-CCA2 security of RSA-OAEP under the assumed hardness of the [[RSA problem]].<ref>

P. Paillier and J. Villar, ''Trading One-Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption'', Advances in Cryptology --– [[Asiacrypt]] 2006.</ref><ref>

D. Brown, [http://eprint.iacr.org/2006/223 ''What Hashes Make RSA-OAEP Secure?''], IACR ePrint 2006/233.</ref>

==Algorithm==

[[File:OAEP paddingencoding schema.pngsvg|410x410px|thumb|410x410pxright|OAEP encoding schema according to RFC 8017]]

In the diagram,

* ''MGF'' is the [[Mask generation function|mask generating function]], usually MGF1,

* ''Hash'' is the chosen [[Cryptographic hash function|hash function]],

* ''hLen'' is the length of the output of the hash function in bytes,

* ''k'' is the length of the [[RSA (cryptosystem)|RSA]] modulus ''n'' in bytes,

* ''kM'' is to the lengthmessage ofto thebe [[RSApadded, (cryptosystem)|RSA]]with moduluslength ''nmLen'' in(at most <math>\mathrm{mLen}= k - 2 \cdot \mathrm{hLen} - 2</math> bytes),

* ''M'' is the message to be padded (at most <math>k - 2 \cdot \mathrm{hLen} - 2</math> bytes),

* ''L'' is an optional label to be associated with the message (the label is the empty string by default and can be used to authenticate data without requiring encryption),

* ''PS'' is a byte string of <math>k - \mathrm{mLen} - 2 \cdot \mathrm{hLen} - 2</math> null-bytes.

Line 49:

# Hash the label ''L'' using the chosen hash function: <math>\mathrm{lHash} = \mathrm{Hash}(L)</math>

# To reverse step 9, split the encoded message ''EM'' into the byte 0x00, the ''maskedSeed'' (with length ''hLen'') and the ''maskedDB'': <math>\mathrm{EM} = \mathrm{0x00} || \mathrm{maskedSeed} || \mathrm{maskedDB}</math>

# Generate the ''seedMask'' which was used to mask the ''seed'': <math>\mathrm{seedMask} = \mathrm{MGF}(\mathrm{maskedDB}, \mathrm{hLen})</math>

# To reverse step 8, recover the ''seed'' with the ''seedMask'': <math>\mathrm{seed} = \mathrm{maskedSeed} \oplus \mathrm{seedMask}</math>

Line 55:

# To reverse step 6, recover the data block ''DB:'' <math>\mathrm{DB} = \mathrm{maskedDB} \oplus \mathrm{dbMask}</math>

# To reverse step 3, split the data block into its parts: <math>\mathrm{DB} = \mathrm{lHash'} || \mathrm{PS} || \mathrm{0x01} || \mathrm{M}</math>.

## VerifiyVerify that:

##* ''lHash''' is equal to the computed ''lHash''

##* ''PS'' only consists of bytes 0x00

##* ''PS'' and ''M'' are seperatedseparated by the 0x01 byte and

##* the first byte of ''EM'' is the byte 0x00.

## If any of these conditions aren't met, then the padding is invalid.