7
$\begingroup$

I'm self-studying Katz' book (2nd ed), and I have a small question about Theorem 3.32, which says:

If $F$ is a pseudorandom permutation, then $CTR$ mode is $CPA-$secure.

They present a proof there, but I think that another proof is viable, which is basically a corollary of a theorem they presented earlier.

My proof is the following. Consider Theorem 3.31, which says

If $F$ is a pseudorandom function, then $m\mapsto \langle r, F_k(r)\oplus m \rangle$ ($k$ is the key, $r$ is uniformly chosen) is a $CPA-$secure encryption scheme.

So, why don't we simply prove that $G_k(\cdot)$ defined as $$G_k({\tt ctr}) = \langle F_k({\tt ctr}+1), F_k({\tt ctr}+2),\ldots,F_k({\tt ctr}+\ell)\rangle $$ is pseudorandom? we would have by the cited theorem that $CTR$ mode (which is the encryption scheme described in the theorem using $G_k$) would be $CPA-$secure. Of course, showing that $G_k$ is pseudorandom if $F_k$ is does not impose a problem, since any distinguisher to $G_k$ can be turned into a distinguisher to $F_k$.

Everything makes sense, I don't see why this proof would not work and why did they bother writing a 2 pages long proof for what could be a corollary! (the only thing I think could fail is that the theorem used was proven for length-preserving $F_k$, but -I think- the proof also applies to the general case).

Anyone can point me to a mistake in my argument? btw, this could also prove that $OFB$ mode is $CPA-$secure.

Thanks in advance

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ $G_k$ is obviously not pseudorandom (for example $G_k(0)$ and $G_k(1)$ are very similar). $\endgroup$
    – fkraiem
    Jan 2, 2017 at 15:41
  • 1
    $\begingroup$ @fkraiem I see, I didn't notice that! I was thinking that we can define an oracle for a given distinguisher $D$ to $G_k$ from an oracle to $g(\cdot)$ (which is either $F_k$ or a random $f(\cdot)$), then if $D$ distinguishes succesfully between a random $h(\cdot):\{0,1\}^n\to \{0,1\}^{n\ell}$, we could distinguish between $f(\cdot)$ and $F_k$. The problem is, of course, that our oracle for $D$ is not between $G_k$ and a random $h(\cdot):\{0,1\}^n\to \{0,1\}^{n\ell}$, but between $G_k$ and $h$ with the same shape as $G_k$. $\endgroup$
    – Daniel
    Jan 2, 2017 at 15:55
  • 1
    $\begingroup$ @fkraiem However, that makes me think... this shows that $G_k$ is indistinguishable from a function with that shape (duh), maybe what can be done is to modify Theorem 3.31 so that it does not use a pseudorandom function but a function of $G_k$ shape, I think the proof can be modified... but anyway, I'm almost sure this "modification" is precisely the proof of Theorem 3.32 itself. In any case, I think that asking this gave some insights on the intuition of the proof, which is good. By the way, I'm pretty sure this still works in the OFB case, do you agree? Thanks fkraiem. $\endgroup$
    – Daniel
    Jan 2, 2017 at 15:58
  • 1
    $\begingroup$ @fkraiem I was wondering, Theorem 3.31 is true even if $F$ is a weak pseudorandom function (indistinguishable from a random function with oracle access to $F$ on random -not chosen- inputs). Unfortunately $G_k$ as defined here is not a weak pseudorandom function, right? since their outputs are simply shifts of $G_k(0)$, so $G_k(r)$ and $G_k(r')$ are easily related (for any $r, r'$) $\endgroup$
    – Daniel
    Jan 2, 2017 at 17:01
  • 1
    $\begingroup$ @fkraiem Even though $G_k(0)$ and $G_k(1)$ have a lot of "overlap," it doesn't follow that $G_k$ is not pseudorandom -- though we need to be more precise. Formally, for any value of ctr it is the case that $G_k(ctr)$ is a pseudorandom string, when $k$ is uniformly random and kept secret. However, it's true that $G_k$ is not a pseudorandom function, for the reason you give. $\endgroup$
    – Chris Peikert
    Jan 2, 2017 at 20:42

1 Answer 1

Reset to default
7
$\begingroup$

One gap in your proposed argument is that $ctr$ is known to the adversary (it is included in the ciphertext), whereas saying "$G_k(ctr)$ is pseudorandom" implicitly assumes that both $k$ and $ctr$ are kept secret. This is a minor point, because $G_k(ctr)$ is pseudorandom even if the adversary is also given $ctr$.

A more serious gap is that to prove CPA security, you must deal with the fact that the adversary can obtain multiple ciphertexts for messages of its choice. If, for example, $ctr$ was always the all-zeros string (which would preserve the pseudorandomness of $G_k(ctr)$), the scheme would definitely not be CPA secure, because it would be breakable by a "two-time pad" attack. So a correct proof must deal with the possibility that $ctr$ might be repeated from one message to the next, or more generally, that $ctr+i=ctr'+j$ for some two initial counter values $ctr, ctr'$ and offsets $i,j$ for two ciphertexts. This issue is what most of the Katz-Lindell proof is dedicated to addressing, and is the source of the "birthday term" $q^2/2^n$ in the analysis.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you Chris. So, for the first part, I agree with fkraiem when he/she says that $G_k$ is not pseudorandom, since for pseudorandomness "test" we assume that $k$ is secret but ${\tt ctr}$ on the other hand is not (since the adversary is given oracle access), am I missing something here? $\endgroup$
    – Daniel
    Jan 2, 2017 at 19:50
  • $\begingroup$ About your second point, I do agree, and I understand why is the $q^2/2^n$ there. However, that proof is very similar to the proof of the theorem I mentioned, so I thought that maybe this was being a bit redundant. I can see this is not the case since Katz' proof deals with intermediate possible repetitions, while the former only deals with repetition of ${\tt ctr}$. I accept your answer though, thanks a lot for taking the time! $\endgroup$
    – Daniel
    Jan 2, 2017 at 19:50
  • $\begingroup$ @SolidSnake No, $G_k$ is pseudorandom even if ctr is known (but $k$ must be kept secret). This is because a PRF produces pseudorandom outputs even when given known (distinct) inputs. $\endgroup$
    – Chris Peikert
    Jan 2, 2017 at 20:36
  • $\begingroup$ Ok, so $G_k$ has pseudorandom outputs, which I agree. I'm not sure though if this condition by itself leads to CPA-security (that is, if we can modify Theorem 3.31 so that the conclusion remains the same, only assuming that $F_k$ has pseudorandom outputs -something like a pseudorandom generator-, not that it is a pseudorandom function). I don't think so, because in this case we could avoid the birthday term in Thm 3.32. $\endgroup$
    – Daniel
    Jan 2, 2017 at 20:52
  • $\begingroup$ As we've seen, CPA security of CTR mode is not a direct corollary of Theorem 3.31, because $G_k$ is not a PRF. You can of course tweak Theorem 3.31 in various ways to cover CTR mode, but ultimately the proof will look very much like the proof of Theorem 3.32; in particular, it will need to deal with the possibility of "overlap" between $ctr+i$ and $ctr'+j$. $\endgroup$
    – Chris Peikert
    Jan 2, 2017 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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