# Best differential characteristic for this PRF

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

• 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. – Aleph Mar 15 '16 at 20:44
• 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. – poncho Jul 8 '16 at 21:39
• @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. – D.W. Jul 9 '16 at 0:25
• 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. – D.W. Jul 9 '16 at 0:26

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.