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

Improve this question
$\endgroup$
4
  • 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, 2016 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, 2016 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, 2016 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, 2016 at 0:26

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.