# Security effects of the seed's length in OAEP

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.

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).

• Awesome, thanks a lot. When I tried to find the answer, I only considered the use of $k_0$ against a padding oracle and didn't think about other properties.
– mat
Commented Apr 7, 2017 at 6:53
• One little trifle: $x$ should actually be the message to encrypt padded with zeroes, shouldn't it?
– mat
Commented Apr 7, 2017 at 6:53
• Yes, if we fix the size of $n$ based on our choices of $k$ and $k_0$ then we need to zero pad all values of $x$ for $|x| < n$. Commented Apr 7, 2017 at 7:20
• Normally I'd wait longer before awarding a bounty but this one has been done and dusted. Commented Apr 7, 2017 at 23:13
• Well if I know that you encrypted either e.g. "yes" or "no" (the analogues of $m_0$ and $m_1$) then a short seed allows me to figure out what you sent without me having the private key. Commented Apr 10, 2017 at 23:24