Security effects of the seed's length in OAEP

Question

In the OAEP scheme for asymetric encryption padding a random seed is used, whose length can be chosen. The paper which introduced OAEP in 1994 just states, that the seed's length $k_0$ should be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.

I am wondering, what the securiy effects would be, of choosing a very small or very large $k_0$.

NOTE: I am asking about the generic OAEP, not RSA-OAEP, which fixes $k_0$ to the length of the hash function used.

Answer 1

Let's start with the preliminaries. The basic scheme has encryption defined as follows:

$$\mathcal{E}^{G, H}(x) = f(x \oplus G(r) || r \oplus H(x \oplus G(r)))$$

Some definitions:

• $f: \{0,1\}^k \rightarrow\{0, 1\}^k$ is a trapdoor permutation where $k$ is the security parameter
• $x$ is the message to encrypt
• $n = |x|$ is the bit length of the message
• $k_0 = k - n$ (the value of interest in out case)
• $G: \{0,1\}^{k_0} \rightarrow\{0, 1\}^n$ is a "generator" from $k_0$ bits to $n$ bits
• $H: \{0,1\}^n \rightarrow\{0, 1\}^{k_0}$ is a "hash function" from $n$ bits to $k_0$ bits
• $r \gets \{0, 1\}^{k_0}$ is a randomly selected $k_0$ bit string

---

The general idea behind setting $2^{k_0}$ to be much larger than the adversaries run time is to prevent the adversary from having a non-negligible chance of brute forcing the value of $r$. Recall that $r$ is a random $k_0$ bit string so there are $2^{k_0}$ possible values of $r$.

Suppose that $k_0$ was selected to be only a couple bits, in this case $\mathcal{E}^{G, H}$ is not secure under a chosen plaintext attack (IND-CPA). For an intuition of how to prove IND-CPA see this graphic. Briefly, if an adversary submits messages $m_0, m_1$ to be encrypted by $\mathcal{E}^{G,H}$ and gets back $c$ it needs to determine if $c$ is the encryption of $m_0$ or $m_1$. Here's how it does that:

$G$, $H$, and $f$ are all public , so the only unknown in the equation is $r$, which was randomly sampled. If $r$ is small enough (i.e. if $k_0$ is small) then an adversary can compute $\mathcal{E}^{G, H}(m_0)$ and $\mathcal{E}^{G, H}(m_1)$ for all possible values of $r$. Once it computes a value that matches $c$ the adversary knows that $c$ is the encryption of whichever message was input into $\mathcal{E}^{G, H}$, which means it has a non-negligible advantage in the IND-CPA game (i.e. the scheme is not IND-CPA).

So naturally we want to pick a $k_0$ that is large enough such that an adversary is unable to brute force the value of $r$. This implies the definition that $k_0$ be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.

---

So to conclude, for values $k_0$ that are very small the results are catastrophic as you lose semantic security. For values $k_0$ that are very large there's no security drawback, but your permutation $f$ needs to be bigger which generally translates to a slower scheme (think RSA2048 vs RSA4096 for example).