Optimal asymmetric encryption padding

Optimal Asymmetric Encryption Padding , in German about optimal asymmetric encryption padding , often also abbreviated as OAEP , is a cryptographic padding method . It is a special form of a Feistel network with which, in the random oracle model, an encryption method that is semantically secure against selected plaintext attacks can be built from any trapdoor permutation . If OAEP is used with the trapdoor permutation RSA, the method now called RSA-OAEP is even secure against dialed cipher attacks ( IND-CCA ). The method was published in 1994 by Mihir Bellare and Phillip Rogaway .

Procedure (basic variant)

Sequence of the OAEP schemes in the CCA variant (see section Variants ). In the basic version of the method, k ₁ = 0 , i.e. H. no zeros are appended.
The output X, Y serves as the input value for the trap door permutation f .

It is a security parameter, and so large that an attacker can only perform significantly fewer arithmetic steps. ${\displaystyle n}$ ${\displaystyle k_{0}}$ ${\displaystyle 2^{k_{0}}}$

Next there is a family of trap door permutations on messages with bits , and the length of the messages which are to be transmitted. ${\displaystyle F}$ ${\displaystyle f:\{0,1\}^{n}\mapsto \{0,1\}^{n}}$ ${\displaystyle n}$ ${\displaystyle k=n-k_{0}}$

Finally, let and be cryptographic hash functions . The encryption method -OAEP is now defined as follows. The key generation consists in the choice of . ${\displaystyle G:\{0,1\}^{k_{0}}\mapsto \{0,1\}^{k}}$ ${\displaystyle H:\{0,1\}^{k}\mapsto \{0,1\}^{k_{0}}}$ ${\displaystyle F}$ ${\displaystyle f,f^{-1}}$

Encryption

To encrypt a -Bit message , proceed as follows: ${\displaystyle k}$ ${\displaystyle m}$

• One chooses as a random sequence of bits. ${\displaystyle r\in \{0,1\}^{k_{0}}}$ ${\displaystyle k_{0}}$
• Then you calculate

${\displaystyle X=m\oplus G(r)}$and . ${\displaystyle Y=r\oplus H(m\oplus G(r))}$

• The key text is then given as: ${\displaystyle c}$

${\displaystyle c=f(X||Y)}$,

where stands for concatenation . ${\displaystyle ||}$

Decryption

To reconstruct the message , perform the following steps: ${\displaystyle m}$

• First you use the trap door to

${\displaystyle Z=(X||Y)=f^{-1}(c)}$

to calculate.

• The random value is now reconstructed as ${\displaystyle r}$

${\displaystyle r=Y\oplus H(X)}$.

• Finally you get the message again as ${\displaystyle m}$

${\displaystyle m=X\oplus G(r)}$.

variants

A simple modification of the above protocol can also achieve IND-CCA1 security, i.e. security against selected ciphertext attacks . To do this, the length of the message is reduced to bits and concatenated with zeros. When decoding, you check whether the reconstructed value has the correct form, and otherwise abort. ${\displaystyle m}$ ${\displaystyle k-k_{1}}$ ${\displaystyle k_{1}}$

Victor Shoup presented an extension of the procedure with which IND-CCA2 security can be achieved for any trap door permutation.

RSA-OAEP

The reason for developing OAEP was to find a way to encrypt with RSA securely (in the sense of IND-CCA2 security). If RSA is used as trap door permutation in OAEP, the procedure is referred to as RSA-OAEP. Although OAEP does not achieve IND-CCA2 security in the general case, this is the case for RSA-OAEP in the random oracle model and under the RSA assumption.

Since the result of the OAEP encoding is a number between 0 and , but the -bit RSA modulus is less than , it can happen that the result of the OAEP encoding has a larger numerical value than the RSA modulus. However, this must not happen because in this case the decryption is no longer unique. Therefore, in such a case, the OAEP encoding must be repeated with a new random . ${\displaystyle 2^{n}}$ ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle 2^{n}}$ ${\displaystyle r}$

RSA-OAEP was standardized in PKCS # 1 and RFC 3447 , whereby the hash function used is a parameter of the procedure, i.e. it was not specified. Under these circumstances, i.e. without a random oracle, RSA-OAEP is secure under the phi-hiding assumption IND-CPA if the hash function used is t-wise independent . In the standardization, however, a change was made, through which the procedure is no longer verifiably secure: To avoid the repetition of the OAEP encoding mentioned above, it was specified that the result of OAEP must be 8 bits shorter than the RSA modulus; the first 8 bits are filled with 0. When decrypting, the recipient must check whether the first 8 bits have the value 0 and cancel if not. If an attacker can distinguish whether a decryption was aborted for this or for another reason, an attack occurs that regains the entire plaintext without the secret key. To do this, he only needs approx. 1000 queries to an error oracle, which only outputs whether and for what reason an attempt at decryption failed. Such oracles can occur, for example, with TLS / SSL connections, where the attack was also carried out in practice.

credentials

1. ↑ Mihir Bellare and Phillip Rogaway : Optimal Asymmetric Encryption - How to encrypt with RSA . In: EUROCRYPT 94 (=  Lecture Notes in Computer Science ). vol. 950. Springer, 1994, pp. 92-111 ( ucsd.edu [PDF]).
2. ^ Victor Shoup: OAEP Reconsidered . In: CRYPTO 2001 (=  Lecture Notes in Computer Science ). vol. 2139. Springer, 2001, pp. 239-259 ( shoup.net [PDF]).
3. ↑ Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, Jacques Stern: RSA-OAEP is secure under the RSA Assumption . In: Journal of Cryptology . tape 17 , no. 2 . Springer, 2004, p. 81-104 ( ens.fr [PDF]).
4. ↑ Eike Kiltz, Adam O'Neill, Adam Smith: Instantiability of RSA-OAEP under Chosen-Plaintext Attack . In: CRYPTO 2010 (=  Lecture Notes in Computer Science ). vol. 6223. Springer, 2010, p. 295-313 ( iacr.org [PDF]).
5. ↑ James Manger: A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS # 1 v2.0 . In: CRYPTO 2001 (=  Lecture Notes in Computer Science ). vol. 2139. Springer, 2001, pp. 260-274 ( ethz.ch [PDF]).