This paper presents a thorough analysis of the AEAD scheme NORX, focussing on differential and rotational properties. We first introduce mathematical models that describe differential propagation with respect to the non-linear operation of NORX. Afterwards, we adapt a framework previously proposed for ARX designs allowing us to automatise the search for differentials and characteristics. We give upper bounds on the differential probability for a small number of steps of the NORX core permutation. For example, in a scenario where an attacker can only modify the nonce during initialisation, we show that characteristics have probabilities of less than\(2^{-60}\) (\(32\)-bit) and\(2^{-53}\) (\(64\)-bit) after only one round. Furthermore, we describe how we found the best characteristics for four rounds, which have probabilities of\(2^{-584}\) (\(32\)-bit) and\(2^{-836}\) (\(64\)-bit), respectively. Finally, we discuss some rotational properties of the core permutation which yield some first, rough bounds and can be used as a basis for future studies.

1. 1.

   This is not an official term. We introduce it to easily distinguish between ARX- and purely logic-based primitives. Terminology-wise it is not entirely correct, though, as integer addition can be obviously modelled by bitwise logical operations as well.

2. 2.

   These are also respectively known as theouter andinner part of the state [9,10].

The authors would like to thank the anonymous reviewers for their comprehensive commentaries which helped to improve the quality of this paper.

Authors and Affiliations

1. Kudelski Security, Lausanne, Switzerland

   Jean-Philippe Aumasson

2. University of Passau, Passau, Germany

   Philipp Jovanovic

3. University of Coimbra, Coimbra, Portugal

   Samuel Neves

Corresponding author

Correspondence toPhilipp Jovanovic.

Editors and Affiliations

1. University of Campinas, Campinas, Brazil

   Diego F. Aranha

2. University of Waterloo, Waterloo, Ontario, Canada

   Alfred Menezes

A Addenda to Differential Cryptanalysis

Proof of Lemma 3.  On bit level Eq. 2 has the form

Obviously, the least significant bits (i.e.\(i = 0\)) are identical for Eqs. 1 and 2. For\(i > 0\) let\(t = (\alpha _i \oplus \beta _i \oplus \gamma _i) \oplus (\alpha _{i-1} \wedge \beta _{i-1})\). If\(t = 0\) then Eq. 1 has always the solution\(x_{i-1} = y_{i-1} = 0\). Otherwise, if\(t = 1\), Eq. 1 is only solvable if\(\alpha _{i-1} = 1\) or\(\beta _{i-1} = 1\), and these are exactly the cases captured in Eq. 2.

Proof of Lemma 5.  Without loss of generality we assume that\(\alpha \ne 0\) or\(\beta \ne 0\). Looking at Eq. 1, we see that the term\((\alpha \oplus \beta \oplus \gamma )\) has no effect on the probability of the differential\(\delta \), since it does not depend on either\(x\) or\(y\). It has therefore probability\(1\).

Analysing the bit level representation of Eq. 1, we observe that the term\((x_{i-1} \wedge \alpha _{i-1}) \oplus (y_{i-1} \wedge \beta _{i-1}) \oplus (\alpha _{i-1} \wedge \beta _{i-1})\) is balanced (i.e., is\(1\) with probability\(1/2\)) if\(\alpha _{i-1} = 1\) or\(\beta _{i-1} = 1\). Therefore, under the assumption of independence of\(\alpha _i\) and\(\beta _i\), the overall probability of\(\delta \) can be computed by counting the number of\(1\)s in the first\(n-1\) bits of\(\alpha \vee \beta \) or, equivalently, of\((\alpha \vee \beta ) \ll 1\), which proves the lemma.

Proof of Lemma 7. It is easy to see that the least significant bits (i.e.\(i = 0\)) of Eqs. 3 and 4 are the same. Therefore, we will consider them no longer. Looking at the bit level representation of Eq. 3 (for\(i > 0\)) we consider two cases:

• \(\alpha _i \oplus \beta _i \oplus \gamma _i = 0\): Here, Eq. 3 has always the solution\(x_{i-1} = y_{i-1} = 0\).

• \(\alpha _i \oplus \beta _i \oplus \gamma _i = 1\): In this case, the bit level representation of Eq. 3 is only solvable if either\(\alpha _{i-1} \ne \gamma _{i-1}\) or\(\beta _{i-1} \ne \gamma _{i-1}\). Furthermore, the bit level representation of Eq. 4 is given by

  $$\begin{aligned} (\alpha _i \oplus \beta _i \oplus \gamma _i) \wedge (\alpha _{i-1} \oplus \gamma _{i-1} \oplus 1) \wedge (\beta _{i-1} \oplus \gamma _{i-1} \oplus 1) = 0, \qquad i > 0 \end{aligned}$$

  It is evident that the latter equation only holds if\((\alpha _i \oplus \beta _i \oplus \gamma _i) = 0\),\(\alpha _{i-1} \ne \gamma _{i-1}\), or\(\beta _{i-1} \ne \gamma _{i-1}\). As seen above, these are the very same conditions that define a\(\mathsf {H}\)-differential.

Proof of Lemma 9. The claim can be proven analogously to Lemma 5. It follows from the fact that in the bit level representation of Eq. 3 the expression

is balanced if\(\alpha _{i-1} \oplus \gamma _{i-1} = 1\) or\(\beta _{i-1} \oplus \gamma _{i-1} = 1\).

B CVC Code

Below we show exemplarily forNORX\(64\) how to translate the differential search operations to the CVC language. Variables have the datatypeBITVECTOR(W), where\(W = 64\) is the wordsize.

Computation of\(\mathsf {hw} (w)\) using helper variables\(h_0,\dots ,h_5\), where\(\mathsf {hw} (w) = h_5\):

C Selected Differentials

1.1C.1 Experimental Verification ofNODE

The first table shows the results from our verification ofNODE, see Sect. 3.3. Notation is used as follows.\(w_{e}\): expected weight, #\(S\): number of samples,\(v_{e}\): expected value of input/output pairs adhering the differential,\(v_{m}\): measured value of input/output pairs adhering the differential,\(w_{m}\): measured weight. After that we list the differentials in\(32\)- and\(64\)-bit\(\mathsf {F} ^{1.5}\) that we used to perform the verification.

1.2C.2 Probability-1 Differentials in\(\mathsf {G}\)

UsingNODE we could show that there are exactly\(3\) probability-1 differentials in both versions (\(32\)- and\(64\)-bit) of\(\mathsf {G}\).

1.3C.3 Best Differential Characteristics for\(\mathsf {F} ^{4}\)

The following two tables show the best differential characteristics in\(\mathsf {F} ^{4}\) that we were capable to find withNODE. The values\(\delta _0\) and\(\delta _4\) are in- and output difference, respectively, and\(\delta _1\),\(\delta _2\), and\(\delta _3\) are internal differences. The differences are listed after a single application of\(\mathsf {F}\), respectively, and the values\(w_i\), with\(i \in \{0,\dots ,3\}\), are the corresponding differential weights.

1.4C.4 Best Iterative Differentials for\(\mathsf {F} \)

1.5C.5 Best Differentials Having Equal Columns of Weight\(44\) in\(\mathsf {F} \)

D Addenda to Rotational Cryptanalysis

Proof of Lemma 11. After evaluating and simplifying the equation\(\mathsf {H} (x,y) \ggg r = \mathsf {H} (x \ggg r, y \ggg r)\) we get\(( (x \wedge y) \ll 1 ) \ggg r = ( (x \ggg r) \wedge (y \ggg r) ) \ll 1\). Translating this equation to bit vectors results in

The probability that those two vectors match is\((3/4)^2 = 9/16\), as\(a \wedge b = 0\) with probability\(3/4\) for bits\(a\) and\(b\) chosen uniformly at random.

Proof of Lemma 13. The first important observation is that the statement of this lemma is independent of the function\(f\), as it only makes a claim on the image of\(f\). Thus it is sufficient to prove the lemma for\(z \ggg r = z\), where\(z = f(x,y)\) and\(x\) or\(y\) was fixed.

We identify the indices of an\(n\)-bit string by the elements in\(G := \mathbb {Z}/n\mathbb {Z}\). Let\(\tau : G \longrightarrow G, ~ i \mathrm{{mod }}n \mapsto (i + 1) \mathrm{{mod }}n\). Then\(\tau \) obviously generates the cyclic group\(G\), i.e.\(\mathrm {ord} (\tau ) = n\). Moreover, for an arbitrary\(r \in \mathbb {Z}\) we have\(\mathrm {ord} (\tau ^r) = n / \gcd (r,n)\), see [26, §§6.2]. In other words, the subgroup\(H:=\langle \tau ^r \rangle \) of\(G\) has order\(n/\gcd (r,n)\). By Lagrange’s theorem we have\(\mathrm {ord} ( G ) = [ G : H ] \cdot \mathrm {ord} ( H )\) and it follows for the group index\([ G : H ] = \gcd (r,n)\), which corresponds to the number of (left) cosets of\(H\) in\(G\). These cosets contain the indices of a bit string which are mapped onto each other by a rotation\(\ggg r\). This means that there are\(2^{\gcd (r,n)}\)\(n\)-bit strings\(z\) which satisfy\(z \ggg r = z\). Thus the probability, that an\(n\)-bit string\(z\), chosen uniformly at random among all\(n\)-bit strings, satisfies\(z \ggg r = z\) is\(2^{- (n - \gcd (r,n))}\). This proves the lemma.

Reprints and permissions

© 2015 Springer International Publishing Switzerland

Policies and ethics