3
$\begingroup$

I am currently trying to fully understand Dan Boneh's/ Victor Shoup's proof in their excellent crypto book draft, that the raw CBC construction is a secure pseudo random function family for prefix-free adversaries (see Section 6.4.1).

The methodology of the proof is to replace the PRF $E_K: \mathcal{X} \rightarrow \mathcal{X}$ with a function $f:\mathcal{X} \rightarrow \mathcal{X} $, that is chosen uniformly from random from set of all functions $f \stackrel{\$}{\leftarrow} \text{Funs}_{x,x}$:

enter image description here enter image description here

The crux is then to calculate an adversary's ability to distinguish this $\text{CBC-}f$ construction from a random choice out of $\text{Funs}_{mx,x}$ (the set of all functions $\mathcal{X}^{\leq m_\text{max}}\rightarrow \mathcal{X}$ with $1\leq m \leq m_\text{max} $). For this, a rooted tree is used, where each query represents a path in this tree. The goal is to find the probability, that two inputs for $f$ collide (CBC chain value $\oplus$ some $X_i$ collides with some other CBC chain value $\oplus$ some $X_j$). This is where the prefix-freeness comes into play, because it ensures, that the message blocks are statistically independent from the CBC chain values and hence two inputs for $f$ collide with probability $1/|\mathcal{X}|$.

Last but not least my question: Why do we have to consider internal collisions too? Why is it not sufficient to only consider collisions on the last $f$ invocation for every query? How can a prefix-free adversary know, if there was an internal collision, when he only sees $Y$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The answer is in the last sentence of the proof: "Once we have established that there are no collisions of these types, it will follow that all values associated with non-root nodes are random and independent, and this holds in particular for the values associated with the leaves, which represent the outputs of FCBC seen by the adversary."

To explain: we are only interested in the leaves which is the last invocation. However, the way to prove it is by proving it for all invocations. This seems quite natural because once there is an internal collision, the question of whether or not this leads to a final collision depends on the query contents, and this is unknown.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't get why I can't simply bound the collision probability for the last invocation of $f$. Obviously there must be a mistake if I argue like follows: Let $X_m$, $X'_m$ be two last message blocks and $y$, $y'$ the CBC chain values, they get XORed with before the final invocation of $f$. Then $\Pr{[X_m \oplus y = X'_m \oplus y']} = \Pr{[X_m \oplus X'_m = y \oplus y']}$. This holds with $1/|\mathcal{X}|$ since $y\oplus y'$ has uniform distribution due to $f$ and is independent from $X_m, X'_m$ due to the prefix-freeness (the adversary never sees $y, y'$). $\endgroup$
    – Patrick K
    Commented Aug 1, 2017 at 12:40
  • 1
    $\begingroup$ You assume that $y$ and $y'$ are independent. However, this is only true if they are different. However, if there was a collision somewhere in the middle, then it could be that $y=y'$. This is your mistake. $\endgroup$
    – Yehuda Lindell
    Commented Aug 1, 2017 at 15:19

Your Answer

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

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