4
$\begingroup$

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.

$\endgroup$
3
+100
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – mat Apr 7 '17 at 6:53
  • 1
    $\begingroup$ One little trifle: $x$ should actually be the message to encrypt padded with zeroes, shouldn't it? $\endgroup$ – mat Apr 7 '17 at 6:53
  • $\begingroup$ 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$. $\endgroup$ – puzzlepalace Apr 7 '17 at 7:20
  • 1
    $\begingroup$ Normally I'd wait longer before awarding a bounty but this one has been done and dusted. $\endgroup$ – Maarten - reinstate Monica Apr 7 '17 at 23:13
  • 1
    $\begingroup$ 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. $\endgroup$ – puzzlepalace Apr 10 '17 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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