NORX replaces all the additions of the Chacha20 quarter-round function with the non-linear $x \oplus y \oplus ((x \land y) \ll 1)$ operation. Gimli supposedly improves on it with $x \oplus y \oplus ((z \land y) \ll 1)$, adding a third input $z$ because as they claim it removes the need for the additional xor that NORX has. In addition the Gimli paper says "Gimli varies the 1-bit shift distance, improving diffusion compared to NORX and possibly even compared to ARX". So we end up with $$ a \gets z \oplus y \oplus ((x \land y) \ll 3) \\ b \gets y \oplus x \oplus ((x \lor z) \ll 1) \\ c \gets x \oplus (z \ll 1) \oplus ((y \land z) \ll 2) $$

My issue with this is that nowhere in the Gimli specification (as far as I could tell anyway) it explains why they did $z \ll 1$ or why they used bitwise or in $x \lor z$ nor does it explain the exact parameter choices for the non-linear operation (why $a \gets z \oplus y \oplus ((x \land y) \ll 3)$ rather than $a \gets z \oplus x \oplus ((z \land y) \ll 3)$ for example).

Is there any justification for these changes that I might have missed?

  • $\begingroup$ I don't see a $c<<1$ in the equations. You do realize that the alternative expression you suggest is algebraically equivalent to what they have (one of the AND'ed variables appears as a term in the outside sum, as well as a third variable which is not AND'ed) $\endgroup$ – kodlu Mar 31 at 23:31
  • $\begingroup$ @kodlu Apologies, fixed it. As for the rest of your comment I am not sure what you mean. $\endgroup$ – Bob Semple Mar 31 at 23:37
  • $\begingroup$ Take $a\leftarrow x_1\oplus x_2 \oplus ((x_1 \land x_3)<<3).$ Due to commutativity both of the expressions above are equivalent to this. $\endgroup$ – kodlu Mar 31 at 23:59
  • $\begingroup$ Yes, I am aware of that. $\endgroup$ – Bob Semple Apr 1 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.