YAARX: Yet Another ARX Toolkit  0.1
 All Data Structures Files Functions Variables Macros Pages
Yet Another Toolkit for Analysis of ARX Cryptographic Algorithms

What is YAARX

YAARX is a set of programs for the differential analysis of ARX cryptographic algorithms. The latter represent a broad class of symmetric-key algorithms designed by combining a small set of simple operations such as modular addition, bit rotation, bit shift and XOR. More notable representatives of the ARX class of algorithms are the block ciphers FEAL, RC5, TEA and XTEA, the stream cipher Salsa20, the hash functions MD4, MD5, Skein and BLAKE as well as the recently proposed hash function for short messages SipHash.

How Does it Compare to Other ARX Tools

YAARX complements existing toolkits such as ARXtools and significantly extends others, such as The S-function Toolkit. More specifically, YAARX provides methods for the computation of the differential probabilities of various ARX operations (XOR, modular addition, multiplication, bit shift, bit rotation) as well as of several larger components built from them. YAARX also provides means to search for high-probability differential trails in ARX algorithms in a fully automatic way. The latter has been a notoriously difficult task for ciphers that do not have S-boxes, such as ARX.

What Can YAARX Do for You

YAARX can help the cryptanalyst in the process of analyzing ARX-based constructions in at least two ways.

Using the Tools Directly

One way is to use the tools directly to compute differential probabilities for a target cipher. To this end YAARX provides a set of programs for the computation of the differential probabilities (DP) of several operations with user provided inputs. Such are for example the programs for computing the DP of modular addition, XOR, bit shift, etc.: adp_xor, xdp_add, adp_xor3, adp_xor_fixed_input, adp_rsh, adp_lsh, max_adp_xor, max_xdp_add, max_adp_xor3, max_adp_xor_fixed_input, eadp_tea_f, max_eadp_tea_f .

A conceivable scenario in this category would be the case in which the cryptanalyst constructs a differential characteristic by hand and wants to estimate its probability by computing the probabilities with which differences propagate through the ARX operations. In this case YAARX can provide answer to questions such as:

  • Given input differences $da$ and $db$ to an operation $F$, and an output difference $dc$, what is the probability of the differential $(da,~ db \rightarrow dc)$?
  • Given input differences $da$ and $db$ to $F$, what is the output difference $dc$ that has maximum probability?
  • Given an input difference $da$ and an input value $b$ to $F$ and an output difference $dc$, what is the probability of the differential $(da,~ b \rightarrow dc)$?
  • Given input difference $da$ and a set of input differences $\{db_0,~db_1,\ldots\}$ to $F$, and an output difference $dc$, what is the probability of the differential $(da,~ \{db_0,~db_1,\ldots\} \rightarrow dc)$?
  • etc. ...

The differences $da$, $db$ and $dc$ can be XOR or additive (ADD) differences and the operation $F$ can either be one of the basic ARX operation, such as XOR, addition, etc. or a larger component e.g. a sequence of bit shift and XOR or of addition, rotation and XOR.

Modifying the Source Code

The second way in which YAARX can be useful would require a bit more effort and some programming literacy on the part of the cryptanalyst. The idea is, prior to using one of the YAARX tools, to first modify it according to ones' specific needs. This scenario is realistic in a case in which none of the YAARX tools is capable of directly addressing a problem for a given target cipher.

Scenarios in this category are likely to occur for example when one wants to automatically search for differential trails in a given cipher. While YAARX supports a general strategy for automatic search of trails, that is potentially applicable to many ARX algorithms, it is implemented for two specific ciphers, namely TEA and XTEA: tea_add_threshold_search, xtea_add_threshold_search, xtea_xor_threshold_search. Since the algorithmic technique underlying these implementations is general, the latter can be applied to other ARX algorithms after appropriate modifications. To facilitate this process, the source code is accompanied by extensive documentation.

Compilation

For successful compilation it is required to install the development version of the GNU Scientific Library (GSL) and the Multiprecision arithmetic library (GMP) developers tools . Under Ubuntu/Debian Linux the name of the packages are resp. libgsl0-dev and libgmp-dev .

After downloading the YAARX source code, it can be compiled by running the make command from within the top directory of the source tree. The pre-compiled programs are stored in the ./bin directoy .

The YAARX Tools

A list of the tools provided by YAARX, together with their computaional complexities is given in the table below. For more details on a specific algorithm refer to the documentation.

$\Delta$ Operator Algorithm Description, (DP = differential probability, ADD = modular addition)

Complexity, ( $n$ = word size, bits)

$+$ $\mathrm{adp}^{\ll}(da \rightarrow db)$ The ADD DP of left shift (LSH).

$O(1)$

$+$ $\mathrm{adp}^{\gg}(da \rightarrow db)$ The ADD DP of right shift (RSH).

$O(1)$

$\oplus$ $\mathrm{xdp}^{+}(da,db \rightarrow dc)$ The XOR DP (XDP) of ADD.

$O(n)$

$+$ $\mathrm{adp}^{\oplus}(da,db \rightarrow dc)$ The ADD DP (ADP) of XOR.

$O(n)$

$+$ $\mathrm{adp}^{\oplus}_{\mathrm{FI}}(a,db \rightarrow db)$ The ADD DP of XOR with one fixed input.

$O(n)$

$+$ $\mathrm{adp}^{3\oplus}(da,db,dc \rightarrow dd)$ The ADD DP of XOR with three inputs.

$O(n)$

$+$ $\mathrm{adp}^{\gg\oplus}(da,db \rightarrow dc)$ The ADD DP of RSH followed by XOR.

$O(n)$

$+$ $\mathrm{eadp}^{F}(da \rightarrow dd)$. The expected additive DP (EADP) of the F-function of TEA, averaged over all round keys and constants: $F(k_0,k_1,\delta |~ x) = ((x \ll 4) + k_0) \oplus (x + \delta) \oplus ((x \gg 5) + k_1)$.

$O(n)$

$+$ $\mathrm{adp}^{F'}(k_0, k_1, \delta |~ da \rightarrow db)$ The additive DP (ADP) of a modified version of the F-function of TEA with the shift operations removed: $F'(k_0, k_1, \delta |~ x) = (x + k_0) \oplus (x + \delta) \oplus (x + k_1)$.

$O(n)$

$+$ $\mathrm{adp}^{\mathrm{ARX}}(r,da,db,dd \rightarrow de)$ The ADD DP of the sequence of operations ADD, ROT by $r$ positions, XOR.

$O(4n)$

$\oplus$ $\max_{dc}~\mathrm{xdp}^{+}(da, db \rightarrow dc)$ The maximum XOR DP of ADD.

$O(n) \le c \ll O(2^n)$

$+$ $\max_{dc}~\mathrm{adp}^{\oplus}(da, db \rightarrow dc)$ The maximum ADD DP of XOR.

$O(n) \le c \ll O(2^n)$

$+$ $\max_{dc}~\mathrm{adp}^{\oplus}_{\mathrm{FI}}(a, db \rightarrow dc)$. The maximum ADD DP of XOR with one fixed input:

$O(n) \le c \ll O(2^n)$

$+$ $\max_{dd}~\mathrm{adp}^{3\oplus}(da, db, dc \rightarrow dd)$ The maximum ADD DP of XOR with three inputs:

$O(n) \le c \ll O(2^n)$

$+$ $\max_{dd}~\mathrm{adp}^{\oplus}_{\mathrm{SET}}(da, db, \{{dc}_0, {dc}_1, \ldots\} \rightarrow dd)$ The maximum ADD DP of XOR with three inputs, where one of the inputs satisfies a set of ADD differences.

$O(n) \le c \ll O(2^n)$

$\oplus$ $\max_{de}~\mathrm{adp}^{\mathrm{ARX}}(r, da, db, dd \rightarrow de)$ The maximum ADD DP of ARX.

$O(n) \le c \ll O(2^n)$

$+$ $\max_{dd} \mathrm{eadp}^{F}(da \rightarrow dd)$ The maximum expected additive DP (EADP) of the F-function of TEA, averaged over all round keys and constants: $ F(x) = ((x \ll 4) + k_0) \oplus (x + \delta) \oplus ((x \gg 5) + k_1)$.

$ O(n) \le c \ll O(2^n)$

$+$ $\mathrm{adp}^{F}(k_0, k_1, \delta |~ da \rightarrow dd)$ The ADD DP of the F-function of TEA for a fixed key and round constants: $F(k_0, k_1, \delta |~ x) = ((x \ll 4) + k_0) \oplus (x + \delta) \oplus ((x \gg 5) + k_1)$.

$ O(n) \ll c \le O(2^n)$

$\oplus$ $\mathrm{xdp}^{F}(k_0, k_1, \delta |~ da \rightarrow dd)$. The XOR DP of the F-function of TEA for a fixed key and round constants: $F(k_0, k_1, \delta |~ x) = ((x \ll 4) + k_0) \oplus (x + \delta) \oplus ((x \gg 5) + k_1)$.

$ O(n) \ll c \le O(2^n)$

$+$ $\mathrm{adp}^{F}(k, \delta |~ da \rightarrow dd)$. The ADD DP of the F-function of XTEA for a fixed key and round constants: $F(k, \delta |~ x) = ((((x \ll 4) \oplus (x \gg 5)) + x) \oplus (k + \delta)$.

$ O(n) \ll c \le O(2^n) $.

$\oplus$ $\mathrm{xdp}^{F}(k, \delta |~ da \rightarrow dd)$. The XOR DP of the F-function of XTEA for a fixed key and round constants: $F(k, \delta |~ x) = ((((x \ll 4) \oplus (x \gg 5)) + x) \oplus (k + \delta)$.

$ O(n) \ll c \le O(2^n)$

$+$ $\mathrm{pDDT}~\mathrm{adp}^{\oplus}$ Partial difference distribution table (pDDT) for $\mathrm{adp}^{\oplus}$ for a fixed probability threshold $p_\mathrm{thres}$

$c = f(p_\mathrm{thres})$

$\oplus$ $\mathrm{pDDT}~\mathrm{xdp}^{+}$ Partial difference distribution table (pDDT) for $\mathrm{xdp}^{+}$ for a fixed probability threshold $p_\mathrm{thres}$

$c = f(p_\mathrm{thres})$

$+$ tea_add_threshold_search Automatic search for ADD differential trails in block cipher TEA.

$+$ xtea_add_threshold_search Automatic search for ADD differential trails in block cipher XTEA.
$\oplus$ xtea_xor_threshold_search Automatic search for XOR differential trails in block cipher XTEA.

Copyright

YAARX is developed in the Laboratory of Algorithmics, Cryptology and Security (LACS) of Luxembourg University and is licensed under GPL (c) 2012-2013.