4
$\begingroup$

Consider the following construction of a PRF $F: \{0,1\}^{128} \times \{0,1\}^{64} \to \{0,1\}^{64}$ on 64-bit messages and 128-bit keys. Define $f:\{0,1\}^3 \to \{0,1\}$ by

$$f(c,x,y) = \begin{cases} \neg(x \land y) &\text{if $c=0$}\\ \neg(x \lor y) &\text{if $c=1$.} \end{cases}$$

Define an (unkeyed) round function $R_i: \{0,1\}^{1024} \to \{0,1\}^{768}$ by

$R_i(S[0..1023])$:
For $j := 0,1,2,\dots,767$, do:
   $S'[j] := f(c_{i,j},S[r_{i,j}],S[r'_{i,j}])$
Return $S'[0..767]$.

Here the $c_{i,j},r_{i,j},r'_{i,j}$ are design-time constants chosen randomly at design time, from $c_{i,j} \in \{0,1\}$, $r_{i,j} \in \{0,1,\dots,1023\}$, $r'_{i,j} \in \{256,257,\dots,1023\}$. These design-time constants are public and known to everyone.

Finally, define the PRF by:

$F(K,M)$:
$S_0 := K||M||M||K||M||M||K||M||M||K||M||M$.
For $i := 0,1,2,\dots,47$, do:
  $S_{i+1} := K||M||M||R_i(S_i)$.
Return $S_{48}[256,257,\dots,319]$.

My question: What is the probability of the highest-probability differential characteristic in this PRF? Of course the answer will depend on the random choice of the design-time constants, but I'm looking for a typical answer or "average-case" answer. I am excluding related-key attacks, so I care about

$$\Pr[\Delta M \to \Delta Y] = \Pr_{K,M}[F_K(M) \oplus F_K(M \oplus \Delta M) = \Delta Y].$$

Is there a clean way to analyze this?

(Bonus question: are there any simple ways to decrease this probability significantly, without increasing the circuit depth of this construction?)

$\endgroup$
  • 1
    $\begingroup$ In some (more often than you'd think) cases you can do it algebraically. Given the large amount of rounds it may be hard (and mainly a lot of work). That approach usually allows to find lower and upper bounds, I'm not sure how to handle the "average" case. $\endgroup$ – Aleph Mar 15 '16 at 20:44
  • $\begingroup$ Unless I'm missing something dreadfully obvious, the function $f$ is biased towards the complement of the input $c_{i,j}$. As all the values $c_{i,j}$ are public, doesn't this mean that the output of the function $R_i$, and hence the function $F$ is distinguishable from random (being biased towards a known bit pattern)? I'm making this as a comment (because it doesn't answer the specific question you're asking), however it would appear to be a more severe weakness than a high-probability differential would be. $\endgroup$ – poncho Jul 8 '16 at 21:39
  • $\begingroup$ @poncho, Yes, you're absolutely right. Nice catch! What I'm actually trying to do is design a MAC with low circuit depth (there's a specific motivation, for protecting return addresses in hardware efficiently); this bias implies the MAC only provides $\sim 52$ bits of security. Not ideal. A possible solution might be to instead return $S_{45}[256,\dots,319] \oplus S_{45}[320,\dots,383]$ and use only 45 rounds of $R$ instead of 48 rounds. That would preserve the circuit depth and provide $\sim 61$ bits of entropy in the output, assuming there are no other cryptanalytic attacks. $\endgroup$ – D.W. Jul 9 '16 at 0:25
  • $\begingroup$ Want to write up your comment as an answer for me to upvote? It's a good observation. Alternatively, want me to edit the question to implement the fix or narrow it down to focus only on differential characteristics? I really appreciate the time you spent on this, and I hate to change a question after you've put thought into it. $\endgroup$ – D.W. Jul 9 '16 at 0:26
4
$\begingroup$

The function $f$ is biased towards the complement of the input $c_{i,j}$, assuming the other two inputs are approximately randomly distributed.

As all the values $c_{i,j}$ are public, this means that the output of the function $R_i$, and hence the function $F$ is strongly distinguishable from random (being biased towards a known bit pattern). This isn't an answer the specific question you've asked, however it would appear to be a more severe weakness than a high-probability differential would be.

$\endgroup$

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.