Algebraic Properties of the Block Cipher DESL

Abstract

The Data Encryption Standard Lightweight extension (DESL) is a lightweight block cipher which is very similar to DES, but unlike DES uses only a single S-box. This work demonstrates that this block cipher satisfies comparable algebraic properties to DES—namely, the round functions of DESL generate the alternating group and both ciphers resist multiple right-hand sides attacks.

1. Introduction

Lightweight cryptography provides solutions tailored for devices with energy or computational constraints, which are increasingly present with the rapid increase of sensors and IoT devices. These requirements should not be met at the cost of losing security properties. Therefore, lightweight ciphers should ensure they offer similar security guarantees to their counterparts.

One of the protocols designed following these principles is DESL, a lightweight cipher very similar to the Data Encryption Standard (DES) [1], proposed by Leander et al. [2]. The proposed cipher introduces one radical change: all substitution boxes in the DES are replaced with a single new S-box. As detailed by Leander et al., this DES Lightweight extension (DESL) has very attractive features in terms of implementability on low-cost platforms. The obvious cryptanalytic question is whether these features might have been paid for with a loss of security. In other words, is the security of DESL comparable to that of the original DES? Leander et al.’s original paper [2] shows that DESL offers resistance against several common attack techniques, including certain types of linear and differential cryptanalyses. Finding structural weaknesses in DESL’s design remains a challenge, so despite its short key length, DESL continues to attract interest and keeps getting cited [3,4,5]. Just a few days before submitting this manuscript, Ji et al. used DESL as a testing ground for proposed improvements of Matsui’s algorithm [6]. In this contribution, we compare two algebraic properties of DESL with those of DES.

First we show that the round functions of DESL generate the same permutation group as the round functions of DES, namely the alternating group on $2^{64}$ points. Our proof strategy is the same as taken by Wernsdorf for DES [7], the core part being to establish 3-transitivity for the group in question. It is not surprising that the replacement of DES’s S-boxes in DESL necessitates modifications of Wernsdorf’s proof, and one might be tempted to hope that facing only one S-box (instead of several as in DES) simplifies the analysis—this did not seem to be the case for the S-box in question.

In the second part of the paper, we compare the resistance of full and reduced round versions of DES and DESL against an algebraic attack technique known as multiple right-hand sides (MRHS) [8]. This type of attack seems particularly interesting for Feistel ciphers like DES and DESL MRHS equations allow a fairly compact encoding of non-linear equations for the secret key, obtained from a known plaintext–ciphertext pair. The operations for solving such equations are in principle suitable for being accelerated through hardware [9], but establishing run-time estimates for such an attack against genuine ciphers is (perhaps unsurprisingly) challenging. While being devised as a tool for cryptanalysis, Raddum and Zajac recently demonstrated that a cipher representation derived from MRHS equations may yield a faster encryption than a reference implementation of a cipher [10]. In [11], Zajac leveraged MRHS equations as a tool to study the connection between the cost of algebraic attacks and the multiplicative complexity of lightweight ciphers. Here we consider the original cryptanalytic application of MRHS equations. The experimental results we found indicate that DESL offers resistance to this type of algebraic attack that is comparable to DES. As an aside, our results falsify a conjecture by Schoonen [12] (Hypothesis 5.1).

To keep our presentation reasonably self-contained, the next section presents the relevant details on the block cipher in question as well as the main ideas underlying an MRHS-based algebraic attack.

2. Preliminaries

With the exception of two modifications, DESL is identical to the Data Encryption Standard; in particular, plaintexts and ciphertexts are elements of ${\{0,1\}}^{64}$ and the key can be taken for an element of ${\{0,1\}}^{56}$. The first difference between DES and DESL is not relevant for the group-theoretic property and the algebraic attack we explore: unlike for DES, there is no initial permutation and no final permutation of the data processed in the cipher. The implications of the second modification is less obvious: DESL replaces all eight S-boxes in DES with a single new S-box.

2.1. Description of DESL

Figure 1 illustrates the basic data flow in DESL, and we refer to the DES specification [1] and Leander et al.’s paper [2] for a detailed specification. For our purposes it is enough to be aware of the following:

• There are 16 rounds, each round i implementing a permutation ${\pi }_i\in S_{2^{64}}$ which depends on a round key $K_i\in {\{0,1\}}^{48}$. The latter is derived from the secret key $K\in {\{0,1\}}^{56}$ through a suitable key schedule.
• Each of the 16 rounds involves a round-key-dependent function $F_{K_i}^{\prime }\left(R_i\right)=P\circ ⨁\circ S\circ ⨁\circ E$ where

  –

  $E:{\{0,1\}}^{32}⟶{\{0,1\}}^{48}$ is an injective map specified in [1].

  –

  $⨁:{\{0,1\}}^{48}⟶{\{0,1\}}^{48},x⟼x\oplus K_i$ adds (xor) the round key $K_i$ to the input.

  –

  $S:{\{0,1\}}^{48}⟶{\{0,1\}}^{32}$ splits the input $(a_1,\cdots ,a_{48})\in {\{0,1\}}^{48}$ into 6-bit blocks and for each $j=1,\cdots ,8$ substitutes $(a_{6j-5},\cdots ,a_{6j})\in {\{0,1\}}^6$ with the corresponding 4-bit value obtained from

  Table 1. The substitution function $S:{\{0,1\}}^6⟶{\{0,1\}}^4$ of DESL is given by this S-box from [2]; $(a_1,\cdots ,a_6)\in {\{0,1\}}^6$ is mapped to the 4-bit binary representation of the table entry in row no. $a_1{a}_6$ and column no. $a_2{a}_3{a}_4{a}_5$ (both interpreted as binary representation of a number in $\{0,\cdots ,3\}$ resp. $\{0,\cdots ,15\}$).

  14	5	7	2	11	8	1	15	0	10	9	4	6	13	12	3
  5	0	8	15	14	3	2	12	11	7	6	9	13	4	1	10
  4	9	2	14	8	7	13	0	10	12	15	1	5	11	3	6
  9	6	15	5	3	8	4	11	7	1	12	2	0	14	10	13

  .

  –

  $P\in S_{2^{32}}$ is a permutation on 32-bit strings as specified in [1].

• In each round, the 64-bit input is split into a left half $L_i\in {\{0,1\}}^{32}$ and a right half $R_i\in {\{0,1\}}^{32}$. Then the value $L_i^{\prime }:=F_{K_i}^{\prime }\left(R_i\right)\oplus L_i$ is computed, where ⊕ is addition in ${\{0,1\}}^{48}$. The output of round i for $i\in \{1,\cdots ,15\}$ is $(R_i,L_i^{\prime })$. In the last round there is no swap, that is, the value $(L_{16}^{\prime },R_{16})$ is output.

For the group-theoretic part of our discussion of DESL, we make use of an observation about DES by Davio et al. [13] which has also been exploited in [7]. Namely, we rewrite DESL as shown in Figure 2, that is, by applying $P^{-1}$ respectively P before the first round and after the last round, we combine E and P into a single function $EP$ such that P no longer has to be applied after the application of the S-box. The composition of and E and P is given in

Table 2. The function $EP:{\{0,1\}}^{32}⟶{\{0,1\}}^{48}$, mapping $(a_1,\cdots ,a_{32})$ to $a_{EP\left(1\right)},\cdots ,a_{EP\left(32\right)}$ where $EP\left(j\right)$ is the j-th entry in the table, reading from left to right, top to bottom (e.g., $EP\left(7\right)=21$).

25	16	7	20	21	29
21	29	12	28	17	1
17	1	15	23	26	5
26	5	18	31	10	2
10	2	8	24	14	32
14	32	27	3	9	19
9	19	13	30	6	22
6	22	11	4	25	16

.

2.2. Multiple Right-Hand Sides (MRHS)

DESL, DES, and many other block ciphers can be modeled as series of polynomial equations over the binary field ${\mathbb{F}}_2$, therewith suggesting algebraic attacks as a possible attack vector. MRHS offers an alternative to algebraic attacks using SAT solvers or Gröbner bases. Instead of working with ordinary polynomials, equations are represented in a different way, which for several block ciphers, including DESL and DES, can be derived conveniently. For a detailed discussion of MRHS, we refer to Raddum and Semaev’s work [8]. Here we restrict ourselves to an informal review of those aspects needed for our application. In particular, we do not discuss specifics of the implementation of the algorithm and refer to [8] (Section 6) for more details (cf. also [12,14]).

2.2.1. Basic Terminology

For a column vector $x={(x_1{x}_2\cdots x_y)}^{\mathrm{T}}\in {\mathbb{F}}_2^y$, a $k\times y$ binary matrix A of rank k, and column vectors $b_1,b_2,\cdots ,b_s\in {\mathbb{F}}^k$ consider the following type of equation:

$$Ax=b_1,b_2,\cdots ,b_s.$$

(1)

We refer to such an equation as an MRHS system of linear equations with right hand sides $b_1,b_2,\cdots ,b_s$. By a solution to (1) we mean a vector in ${\mathbb{F}}_2^y$ satisfying at least one particular linear system of equations $Ax=b_i$. The set of all solutions to (1) is obtained by forming the union of the solutions to the individual systems $Ax=b_i$ ($1\le i\le s$). To work with MRHS systems of linear equations, we juxtapose the above column vectors $b_i$ to form a matrix L and rewrite Equation (1) as $Ax=\left[L\right]$. The pair $(A,L)$ is called a symbol, and when writing equations, the brackets around L emphasize that we are not working with an ordinary equation of matrices.

For example, the following is an MRHS system of linear equations:

$$\left(\begin{array}{ccccc}1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 0& 0& 1& 0\end{array}\right)\left(\begin{array}{c}x1\\ x2\\ x3\\ x4\\ x5\end{array}\right)=\left[\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 1\end{array}\right]$$

and algebraically, it corresponds to the nonlinear equation

$$x_1{x}_4+x_1{x}_2+x_2{x}_4+x_2+x_3+x_4+1=0.$$

Given a system of symbols

$$\begin{array}{cccc}\hfill S_1:& A_{1}x& =& \left[L_1\right]\\ \hfill & & ⋮\\ \hfill S_n:& A_{n}x& =& \left[L_n\right]\end{array},$$

(2)

a solution to such a system is defined in the obvious way: it is a vector $x\in {\mathbb{F}}_2^y$ satisfying all of the underlying n MRHS systems of linear equations, and the goal of the procedure discussed next is to identify all solutions of (2).

2.2.2. Solving a System of Symbols

There are three main components to MRHS: agreeing, gluing, and extracting equations. Since memory is finite in any actual implementation of the algorithm, it may also happen that we have to guess variables, and sometimes an equation symbol is made use of. Each of these parts is discussed below, and we start with a description of the main components.

Agreeing

The basic idea of an agreeing phase is to remove columns b in a right hand side $L_i$ if no solution of $A_{i}x=b$ can be a solution to the system (2). To achieve this, pairwise agreeing of symbols is employed. Namely, let $S_i:A_{i}x=\left[L_i\right]$ and $S_j:A_{j}x=\left[L_j\right]$ be two symbols; we say that $S_i$ and $S_j$ agree if for every $b\in L_i$, there exists a $b^{\prime }\in L_j$ such that the linear system

$$\left(\begin{array}{c}{A}_i\\ A_j\end{array}\right)x=\left(\begin{array}{c}b\\ b^{\prime }\end{array}\right)$$

(3)

is consistent, and, vice versa, for each $b^{\prime }\in L_j$ there exists a $b\in L_i$ such that (3) is consistent.

In a situation where $S_i$ and $S_j$ do not agree, we remove those columns b from $L_i$ for which the linear system $A_{i}x=b$ is inconsistent with $A_{j}x=\left[L_j\right]$. Dually, those columns $b^{\prime }$ from $L_j$ are removed, for which $A_{j}x=b^{\prime }$ is inconsistent with $A_{i}x=\left[L_i\right]$. Different strategies can be used to realize this basic idea, but for our purposes it is not necessary to go into further detail on this.

However, it is important to note that if two symbols $S_h$ and $S_i$ agree but $S_i$ and $S_j$ disagree, columns may be deleted in one or both of $L_i$ and $L_j$. After this happens, it may well happen that $S_h$ does not agree with either of the modified symbols, and it becomes necessary to re-agree$S_h$ with them. During the latter agreement, columns from $L_h$ may have to be deleted, and so on, possibly resulting in a chain reaction of column deletions. To ensure that a system of symbols reaches a pairwise-agreed state, we perform the Agreeing1 algorithm in Figure 3 (see [8] (Section 3.1)).

Gluing

When a system of symbols is in a pairwise-agreed state, we may choose to apply a different operation: The gluing of two symbols $S_i=(A_i,L_i)$ and $S_j=(A_j,L_j)$ results in a new symbol $Bx=\left[L\right]$ whose set of solutions is the set of common solutions to $A_{i}x=\left[L_i\right]$ and $A_{j}x=\left[L_j\right]$. After having formed this new symbol, it is inserted into the system at hand and the two symbols $S_i$ and $S_j$ which formed $(B,L)$ are no longer necessary and are removed from the system.

Gluing a matrix $L_i$ of width $s_i$ with a matrix $L_j$ of width $s_j$ may yield a matrix L with as many as $s_i·s_j$ columns. In an implementation, computing certain glues might therefore turn out to be infeasible, and one restricts to gluing only pairs of symbols where the number of columns in the resulting symbol does not exceed a certain threshold.

Once several glues have been performed, the symbols in the resulting system will usually no longer be pairwise-agreed, so the algorithm in Figure 3 can be run again, initiating another round of agreeing and gluing. The eventual goal of iterated agreeing and gluing steps is to obtain a system of symbols which consists of a single symbol.

Extracting Equations

From a given symbol $S:Ax=\left[L\right]$ we can try to extract unique right-hand side (URHS) equations, and if this is done, the resulting linear equations are placed in a dedicated symbol $S_0$ to which we refer as an equation symbol. The equation symbol is checked for consistency and size. The A-part of $S_0$ has the same number of columns as the A-parts of the other symbols, but its L-part has only one column. The equation symbol is not considered a proper part of the system (2) and does not take part in the Agreeing1 algorithm, nor is it removed after being glued to a symbol in the system. However, various implementations will involve $S_0$ in an agreement or gluing step. Furthermore, information from guessing variables may also be reflected by $S_0$.

Guessing Variables

It may happen that all symbols in a system are pairwise-agreed, no new URHS equations can be extracted, and no pair of symbols can be glued without exceeding the threshold. Lacking a better alternative, in such a situation one can guess the (one-bit) value of a variable. Before performing a guess, the system of symbols—to which we will refer as the state—is stored. After the guess has been made, pairwise agreeing, gluing, and equation extraction are performed as normal. If after some steps the state, again, does not allow for any new URHS equation to be computed or pair of symbols to be glued, the state is saved again, and we guess the value of another variable.

Obviously a guess for a variable can be incorrect, and this discovery manifests as follows: during the agreement of two symbols, all right-hand sides of at least one of the symbols get removed, indicating that the system has no solution. When this happens, the state can be rolled back to a previously saved state, so that a different guess can be made.

3. The Group Generated by DESL’s Round Functions

In this section we show that the round functions of DESL generate the same group as the round functions of DES. The main part of the argument is to establish 3-transitivity of the group generated by DESL’s round functions. To present the (somewhat technical) proof it will be convenient to introduce some notation.

3.1. Notation

The inputs for the S-box of DESL are bitstrings of length 6, outputting bit strings of length 4, as detailed in Table 1. The bitstring inputs are obtained by dividing a 48 bit string into eight blocks of equal length. To refer to the latter, given $a\in {\{0,1\}}^{48}$, we set ${\left[a\right]}_j:={\left(a_i\right)}_{i=6j-5}^{6j}(j=1,\cdots ,8)$. Analogously, for $a\in {\{0,1\}}^{32}$, we write ${\left[a\right]}_j:={\left(a_i\right)}_{i=4j-3}^{4j}$$(j=1,\cdots ,8)$ for the selection of 4-bit blocks. It will be clear from the context when we are dealing with 48-bit, respectively 32-bit values. Finally, as manifested in the balanced Feistel structure, splitting a bitstring of even length into two halves is a common operation in DESL, and for $(a_1,\cdots ,a_{2m})\in {\{0,1\}}^{2m}$ we define $a_L:={\left(a_i\right)}_{i=1}^m\in {\{0,1\}}^m$ and $a_R:={\left(a_i\right)}_{i=m+1}^{2m}\in {\{0,1\}}^m$.

Furthermore, for ease of readability, we will often represent bitstrings by the decimal number they represent in binary (again, the length of the bitstring will always be clear from the context). Accordingly, we write $A_{2^{64}}$ and $S_{2^{64}}$ for the alternating and symmetric group respectively on ${\{0,1\}}^{64}$. Given a set of permutations $\Pi$, we denote by $\langle \Pi \rangle$ the group generated by them. Specifically we are interested in the group G generated by the round functions $F_K$ of DESL, where K ranges over all possible values in ${\{0,1\}}^{48}$. As in Wernsdorf’s analysis of DES in [7], we ignore any restrictions imposed by the key schedule and allow the round keys to be chosen freely.

Using the description and notation from Section 2.1, for a given round key $K\in {\{0,1\}}^{48}$ we can represent $F_K\in S_{2^{64}}$ as

$$\begin{array}{cccc}{F}_K:\hfill & {\{0,1\}}^{32}\times {\{0,1\}}^{32}& ⟶\hfill & {\{0,1\}}^{32}\times {\{0,1\}}^{32}\hfill \\ & (a,b)& ⟼\hfill & \left(b,{({\left[a\right]}_i\oplus S({\left[K\right]}_i\oplus {\left[EP\left(b\right)\right]}_i))}_{i=1}^8\right)\hfill \end{array}.$$

We can therefore state our result in terms of these functions, proving that

$$G=〈\{F_K\in S_{2^{64}}|K\in {\{0,1\}}^{48}\}〉=A_{2^{64}}.$$

3.2. Establishing 3-Transitivity of G

Before proving the main result, we will prove some previous lemmas.

Lemma 1.

The round functions of DESL generate a subgroup of $A_{2^{64}}$ that acts transitively on ${\{0,1\}}^{64}$.

Proof. 

Verifying the transitivity of G is straightforward, and the work of Even and Goldreich [15] ensures that G is contained in the alternating group.  ☐

As an intermediate step, we will show the transitivity of $G_0:=\{g\in G|g\left(0\right)=0\}$ on ${\{0,1\}}^{64}\backslash \left\{(0,\cdots ,0)\right\}$ and transitivity of $G_{0,d}:=\{g\in G|g\left(0\right)=0\mathrm{and}g\left(d\right)=d\}$ on ${\{0,1\}}^{64}\backslash \{(0,\cdots ,0),d\}$, where $d:={\left({\delta }_{31,i}\right)}_{i=1}^{64}$ has a single non-zero entry at the 31st position.

Before doing so, let us have a closer look at $G_0$ and $G_{0,d}$:

In view of the Feistel structure of DESL, it is perhaps not very surprising that we deal with pairs of round functions when exploring the transitivity of $G_0$ and $G_{0,d}$. We define four sets of key pairs, where the last two depend on the auxiliary value $d^{\prime }:=(0,0,0,1,0,0)\in {\{0,1\}}^6$:

$$\begin{array}{ccc}\hfill M& :=& \{(k,k^{\prime })\in {\{0,1\}}^6\times {\{0,1\}}^6|S\left(k\right)=S\left(k^{\prime }\right)\}\hfill \\ \hfill \mathbb{M}& :=& \{(K,K^{\prime })\in {\{0,1\}}^{48}\times {\{0,1\}}^{48}|\forall j\in \{1,\cdots ,8\}:({\left[K\right]}_j,{\left[K^{\prime }\right]}_j)\in M\}\hfill \\ \hfill M_{d^{\prime }}& :=& \{(k,k^{\prime })\in M|S(k\oplus d^{\prime })=S(k^{\prime }\oplus d^{\prime })\}\hfill \\ \hfill {\mathbb{M}}_{d^{\prime }}& :=& \{(K,K^{\prime })\in \mathbb{M}|({\left[K\right]}_4,{\left[K^{\prime }\right]}_4)\in M_{d^{\prime }}.\}\hfill \end{array}$$

The elements in G we are mainly interested in are of the form $F_{K,K^{\prime }}^L:=F_{K^{\prime }}^{-1}{F}_K$ or $F_{K,K^{\prime }}^R:=F_{K^{\prime }}{F}_K^{-1}$ with the key pair $(K,K^{\prime })$ being chosen from $\mathbb{M}$. For input pairs $(a,b)\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$ we have

$$\begin{array}{ccc}\hfill F_{K,K^{\prime }}^L(a,b)& =& ({\left[a\right]}_1\oplus S({\left[K\right]}_1\oplus {\left[EP\left(b\right)\right]}_1)\oplus S({\left[K^{\prime }\right]}_1\oplus {\left[EP\left(b\right)\right]}_1),\cdots ,\hfill \\ & & {\left[a\right]}_8\oplus S({\left[K\right]}_8\oplus {\left[EP\left(b\right)\right]}_8)\oplus S({\left[K^{\prime }\right]}_8\oplus {\left[EP\left(b\right)\right]}_8),b)\mathrm{and}\hfill \\ \hfill F_{K,K^{\prime }}^R(a,b)& =& (a,{\left[b\right]}_1\oplus S({\left[K\right]}_1\oplus {\left[EP\left(a\right)\right]}_1)\oplus S({\left[K^{\prime }\right]}_1\oplus {\left[EP\left(a\right)\right]}_1),\cdots ,\hfill \\ & & {\left[b\right]}_8\oplus S({\left[K\right]}_8\oplus {\left[EP\left(a\right)\right]}_8)\oplus S({\left[K^{\prime }\right]}_8\oplus {\left[EP\left(a\right)\right]}_8)).\hfill \end{array}$$

In other words, when evaluating $F_{(K,K^{\prime })}^L(a,b)$, the right half of the input does not vary and its left half is XORed with the value ${(S({\left[K\right]}_i\oplus {\left[EP\left(b\right)\right]}_i)\oplus S({\left[K^{\prime }\right]}_i\oplus {\left[EP\left(b\right)\right]}_i))}_{i=1}^8$ to the left half of the input.

For $F_{(K,K^{\prime })}^R$ the situation is similar, with the left half of the input being stabilized.

The following proposition helps in understanding the effect of repeatedly applying a map of the form $F_{K,K^{\prime }}^R$, respectively $F_{K,K^{\prime }}^L$.

Proposition 1.

The functions $F_{K,K^{\prime }}^L$ and $F_{K,K^{\prime }}^R$ defined above satisfy the following:

(a) 

$\forall (K,K^{\prime })\in \mathbb{M}:F_{K,K^{\prime }}^L\in G_{0,d}$ and $F_{K,K^{\prime }}^R\in G_0$.  

(b) 

$\forall (K,K^{\prime })\in {\mathbb{M}}_{d^{\prime }}:F_{K,K^{\prime }}^L\in G_{0,d}$ and $F_{K,K^{\prime }}^R\in G_{0,d}$.  

(c) 

Let $n\in \mathbb{N}$. Then, for all $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in \mathbb{M}$ and for all $(a,b)\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$, the following hold:

$F_{K_1,K_1^{\prime }}^R\circ \cdots \circ F_{K_n,K_n^{\prime }}^R(a,b)=$

$$\begin{array}{ccc}\hfill (a,& {\left[b\right]}_1\oplus & \underset{i=1}{\overset{n}{⨁}}(S({\left[K_i\right]}_1\oplus {\left[EP\left(a\right)\right]}_1)\oplus S({\left[K_i^{\prime }\right]}_1\oplus {\left[EP\left(a\right)\right]}_1)),\cdots ,\hfill \\ & {\left[b\right]}_8\oplus & \underset{i=1}{\overset{n}{⨁}}(S({\left[K_i\right]}_8\oplus {\left[EP\left(a\right)\right]}_8)\oplus S({\left[K_i^{\prime }\right]}_8\oplus {\left[EP\left(a\right)\right]}_8)))\hfill \end{array}$$

and, analogously,

$F_{K_1,K_1^{\prime }}^L\circ \cdots \circ F_{K_n,K_n^{\prime }}^L(a,b)=$

$$\begin{array}{ccc}\hfill ({\left[a\right]}_1& \oplus & \underset{i=1}{\overset{n}{⨁}}(S({\left[K_i\right]}_1\oplus {\left[EP\left(b\right)\right]}_1)\oplus S({\left[K_i^{\prime }\right]}_1\oplus {\left[EP\left(b\right)\right]}_1)),\cdots ,\hfill \\ \hfill {\left[a\right]}_8& \oplus & \underset{i=1}{\overset{n}{⨁}}(S({\left[K_i\right]}_8\oplus {\left[EP\left(b\right)\right]}_8)\oplus S({\left[K_i^{\prime }\right]}_8\oplus {\left[EP\left(b\right)\right]}_8)),b).\hfill \end{array}$$

Proof. 

The proof is immediate from the definition of $F_{K,K^{\prime }}^L$ and $F_{K,K^{\prime }}^R$.  ☐

To understand better which values can be obtained in the left and right 32-bit halves of the output through repeated application of a map of the form $F_{K,K^{\prime }}^R$ (respectively $F_{K,K^{\prime }}^L$), given some 64-bit input, it is helpful to take a look at some ${\mathbb{F}}_2$-vector subspaces of ${\mathbb{F}}_2^4$:

Lemma 2.

For $y\in {\{0,1\}}^6\backslash \left\{(0,0,0,0,0,0)\right\}$ let

$$U\left(y\right):=\langle S\left(k\oplus y\right)\oplus S\left(k^{\prime }\oplus y\right)|(k,k^{\prime })\in M\rangle \subseteq {\mathbb{F}}_2^4$$

be the ${\mathbb{F}}_2$-vector space spanned by $\{S\left(k\oplus y\right)\oplus S\left(k^{\prime }\oplus y\right)|(k,k^{\prime })\in M\}$.

Similarly, denote by $U_{d^{\prime }}\left(y\right)$ the ${\mathbb{F}}_2$-vector space

$$U_{d^{\prime }}\left(y\right):=\langle S\left(k\oplus y\right)\oplus S\left(k^{\prime }\oplus y\right)|(k,k^{\prime })\in M_{d^{\prime }}\rangle .$$

Then, the following statements hold:

(a) 

$\forall y\in {\{0,1\}}^6\backslash \{(0,0,0,0,0,0),(0,0,0,0,0,1)\}:U\left(y\right)={\{0,1\}}^4$.  

(b) 

$U(0,0,0,0,0,1)=\{0,2,4,6,8,10,12,14\}$.  

(c) 

$\forall y\in \{2,6,17,18,21,22,41,45,49,53,58,62\}:U_{d^{\prime }}\left(y\right)={\{0,1\}}^4$.  

(d) 

$\forall y\in {\{0,1\}}^6\backslash \left\{(0,0,0,1,0,0)\right\}:U_{d^{\prime }}\left(y\right)\ne \left\{0\right\}$.

Proof. 

The proof is by direct computation, e.g., using a programming language like Python [16]. ☐

Remark 1.

Bringing the notation in Lemma 2 to use, from Proposition 1 we obtain the following statements which for the case $U\left({\left[EP\left(a\right)\right]}_i\right)={\{0,1\}}^4$ (respectively $U\left({\left[EP\left(b\right)\right]}_k\right)={\{0,1\}}^4$) may be regarded as “hinting at transitivity”:

• For $i=1,\cdots ,8$ let $u_i\in U\left({\left[EP\left(a\right)\right]}_i\right)$ be a bitstring. Then, there exist $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in \mathbb{M}$ such that $F_{K_1,K_1^{\prime }}^R\circ \cdots \circ F_{K_n,K_n^{\prime }}^R(a,b)=(a,{\left[b\right]}_1\oplus u_1,\cdots ,{\left[b\right]}_8\oplus u_8)$ for all $(a,b)\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$.  
• For $i=1,\cdots ,8$ let $u_i\in U\left({\left[EP\left(b\right)\right]}_i\right)$ be a bitstring. Then, there exist $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in \mathbb{M}$ such that $F_{K_1,K_1^{\prime }}^L\circ \cdots \circ F_{K_n,K_n^{\prime }}^L(a,b)=({\left[a\right]}_1\oplus u_1,\cdots ,{\left[a\right]}_8\oplus u_8,b)$ for all $(a,b)\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$.  
• For $i\in \{1,\cdots ,8\}\backslash \left\{4\right\}$ let $u_i\in U\left({\left[EP\left(a\right)\right]}_i\right)$ be a bitstring and let $u_4\in U_{d^{\prime }}\left({\left[EP\left(a\right)\right]}_4\right)$. Then, there exist $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in {\mathbb{M}}_{d^{\prime }}$ such that $F_{K_1,K_1^{\prime }}^R\circ \cdots \circ F_{K_n,K_n^{\prime }}^R(a,b)=(a,b_1\oplus u_1,\cdots ,b_8\oplus u_8)$ for all $(a,b)\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$.  
• For $i\in \{1,\cdots ,8\}\backslash \left\{4\right\}$ let $u_i\in U\left({\left[EP\left(b\right)\right]}_i\right)$ be a bitstring and let $u_4\in U_{d^{\prime }}\left({\left[EP\left(b\right)\right]}_4\right)$. Then there exist $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in {\mathbb{M}}_{d^{\prime }}$ such that $F_{K_1,K_1^{\prime }}^L\circ \cdots \circ F_{K_n,K_n^{\prime }}^L(a,b)=(a_1\oplus u_1,\cdots ,a_8\oplus u_8,b)$ for all $(a,b)\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$.

Therefore, if we know that the equality $U\left({\left[EP\left(a\right)\right]}_k\right)={\{0,1\}}^4$ holds for some $1\le k\le 8$, then for each bitstring $c\in {\{0,1\}}^4$ we can find a sequence of key pairs $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in \mathbb{M}$ with

$${\left[{\left[F_{K_1,K_1^{\prime }}^R\circ \cdots \circ F_{K_n,K_n^{\prime }}^R(a,b)\right]}_R\right]}_k=c.$$

For instance, we can choose pairs $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })$ with $({\left[K_j\right]}_k,{\left[K_j^{\prime }\right]}_k)\in M$ corresponding to the linear combination of $c\oplus {\left[b\right]}_k$, and the rest of the positions being 0. This ensures that all $(K_j,K_j^{\prime })$ are contained in $\mathbb{M}$, and if $U_{d^{\prime }}\left({\left[EP\left(a\right)\right]}_k\right)={\{0,1\}}^4$ or $k\ne 4$, we can also ensure $(K_1,K_1^{\prime }),\cdots ,(K_n,K_n^{\prime })\in {\mathbb{M}}_{d^{\prime }}$.

Similarly, in case $U\left({\left[EP\left(b\right)\right]}_k\right)$ contains all bitstrings of length 4, we can obtain a sequence of key pairs with

$${\left[{\left[F_{K_1,K_1^{\prime }}^L\circ \cdots \circ F_{K_n,K_n^{\prime }}^L(a,b)\right]}_L\right]}_k=c.$$

The subsequent lemmata enable us to argue that $G_{0,d}$ acts transitively on ${\{0,1\}}^{64}\backslash \{0,d\}$. In other words, we prove that for all $x,y\in {\{0,1\}}^{64}\backslash \{0,d\}$ the equivalence $x\sim y$ holds, where $x\sim y\iff \exists g\in G_{0,d}:g\left(x\right)=y$. The proofs exploit in particular the transitivity of ∼.

Lemma 3.

Let $e:=(1,0,1,\cdots ,1)\in {\{0,1\}}^{32}$ be the 32-bit vector which has a single 0-entry at the second position and 1-entries everywhere else, and let $(z,z^{\prime })\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$ be arbitrary. Then $(e,z)\sim (e,z^{\prime })$.

Proof. 

Let $(z,z^{\prime })\in {\{0,1\}}^{32}\times {\{0,1\}}^{32}$ be arbitrary, but fixed. From Table 2 we see that

$${\left[EP\left(e\right)\right]}_i=\left\{\begin{array}{cc}(1,1,1,1,1,1)\hfill & ,\mathrm{if}i\in \{1,2,3,6,7,8\}\hfill \\ (1,1,1,1,1,0)\hfill & ,\mathrm{if}i=4\hfill \\ (0,1,1,1,1,1)\hfill & ,\mathrm{if}i=5\hfill \end{array}\right.$$

Hence, by properties (a) and (c) of Lemma 2 we obtain $U\left({\left(EP\left(e\right)\right)}_i\right)={\{0,1\}}^4$ for all $i=1,\cdots ,8$ as well as $U_{d^{\prime }}\left({\left(EP\left(e\right)\right)}_4\right)={\{0,1\}}^4$.

Therefore, because of Remark 1 for $c=(z_1^{\prime },z_2^{\prime },z_3^{\prime },z_4^{\prime })$ we get:

$(e,z)\sim (e,(z_1^{\prime },z_2^{\prime },z_3^{\prime },z_4^{\prime },z_5,\cdots ,z_{32}))$, since $(e,(z_1^{\prime },z_2^{\prime },z_3^{\prime },z_4^{\prime },z_5,\cdots ,z_{32}))=F_{K^1,K^{1^{\prime }}}^R\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R(e,z)$, for the corresponding $(K^i,K^{i^{\prime }})$, $i\in \{1,\cdots ,n\}$.

Analogously, since $U\left({\left(EPe\right)}_2\right)={\{0,1\}}^4$, we can obtain:

$(e,(z_1^{\prime },z_2^{\prime },z_3^{\prime },z_4^{\prime },z_5,\cdots ,z_{32}))\sim (e,(z_1^{\prime },\cdots ,z_8^{\prime },z_9,\cdots ,z_{32})).$

If we continue carrying out the same procedure, since all the subspaces considered are ${\{0,1\}}^4$, we can finally see that $(e,z)\sim (e,z^{\prime })$. ☐

Lemma 4.

$\forall a\in {\{0,1\}}^{64}\backslash \{0,d\},\exists a^{\prime }\in {\{0,1\}}^{64}\backslash \{0,d\}:a^{\prime }\sim aand\exists i\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}:a_i^{\prime }=1$.

Proof. 

If $\exists i\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}:a_i=1$, then we obtain the lemma with $a^{\prime }:=a$.

Otherwise, we distinguish two cases:

• If $\exists i\in \{33,\cdots ,64\}:a_i=1$:
  Then $\exists l\in \{1,\cdots ,8\}$ such that ${\left[EP{\left(a\right)}_{i=33}^{64}\right]}_l\ne 0$:

  –

  If ${\left[EP{\left(a\right)}_{i=33}^{64}\right]}_l\ne 1$, then $U{\left(\left[EP{\left(a\right)}_{i=33}^{64}\right)\right]}_l{)=\{0,1\}}^4$. Therefore, because of Remark 1, we can show $a^{\prime }=F_{K^1,K^{1^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a\right)$ such that ${\left({\left[a^{\prime }\right]}_L\right)}_j=1$ for $j\in \{4l-3,\cdots ,4l\}$. Thus, $\exists i\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}:a_i^{\prime }=1$.  

  –

  If ${\left[EP{\left(a\right)}_{i=33}^{64}\right]}_l=1$, then $U\left({\left[EP{\left(a\right)}_{i=33}^{64}\right]}_l\right)=\{0,2,4,6,8,10,12,14\}$. With an argument similar to the previous one, we can get an element $a^{\prime }=F_{K^1,K^{1^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a\right)$, such that ${\left(a_L^{\prime }\right)}_i=1$ for $i\in \{4l-3,\cdots ,4l-1\}$. Therefore, $\exists i\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}:a_i^{\prime }=1$.

• If $\forall i\in \{33,\cdots ,64\}:a_i=0$.
  Since $a\ne 0$, then $\exists i\in \{1,\cdots ,32\}:a_i=1$. Therefore, $\exists l\in \{1,\cdots ,8\}$ such that ${\left[EP{\left(a\right)}_{i=1}^{32}\right]}_l\ne 0$ and, like before (but using “right-functions”) we prove that we can get an element $a^{\prime }=F_{K^1,K^{1^{\prime }}}^R\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R\left(a\right)$, where $(K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$, such that $\exists i\in \{33,\cdots ,64\}:a_i^{\prime }=1$. Notice that in this case the pairs $(K^i,K^{i^{\prime }})$ must be not only in $\mathbb{M}$, but in ${\mathbb{M}}_{d^{\prime }}$, so that $a\sim a^{\prime }$ (Proposition 1(b)).

  –

  If $l\ne 4$

  ∗

  If ${\left(EP{\left(a\right)}_{i=1}^{32}\right)}_l\ne 1$, then $U{\left(\left[EP{\left(a\right)}_{i=1}^{32}\right)\right]}_l{)=\{0,1\}}^4$.

  Therefore, because of Remark 1, we can have $a^{\prime }=F_{K^1,K^{1^{\prime }}}^R\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R\left(a\right)$, where $(K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$, with $a_i^{\prime }=1$ for some $i\in \{33,\cdots ,64\}$.  

  ∗

  If ${\left[EP{\left(a\right)}_{i=1}^{32}\right]}_l=1$, then $U{\left(\left[EP{\left(a\right)}_{i=1}^{32}\right)\right]}_l)=\{0,2,4,6,8,10,12,14\}$. With the same argument as before, we can get an element $a^{\prime }=F_{K^1,K^{1^{\prime }}}^R\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R\left(a\right)$, such that $a_i^{\prime }=1$ for $i=32+j$, where $j\in \{4l-3,\cdots ,4l-1\}$.

  –

  If $l=4$: Since $a\ne d$, according to Table 2, ${\left(EPa\right)}_4\ne (0,0,0,1,0,0)$. Therefore, we have $U_{d^{\prime }}\left({\left(EPa\right)}_4\right)\ne 0$ (Lemma 2(d)) and we can obtain, as in the previous cases, an element $a^{\prime }:=F_{K^1,K^{1^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R\left(a\right)\sim a$, with $a_i^{\prime }=1$ for some $i\in \{33,\cdots ,64\}$.

Hence, this case is traced back to the case $\exists i\in \{33,\cdots ,64\}:a_i=1$ and the proof is complete. ☐

Lemma 5.

$\forall a^{\prime }\in {\{0,1\}}^{64}\backslash \{0,d\}:a^{\prime }\sim aand\exists i\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}:a_i^{\prime }=1,\exists a^{″}\in {\{0,1\}}^{64}\backslash \{0,d\}:a^{″}\sim a^{\prime }and\forall i\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\}:a_i^{″}=e_i$.

Proof. 

If $\forall i\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\}:a_i^{″}=e_i$, then we immediately obtain the Lemma with $a^{″}:=a^{\prime }$.

Otherwise, we choose an index $j\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}:a_j^{\prime }=1$ and we will prove that

$\exists a^0\in {\{0,1\}}^{64}\backslash \{0,d\}:a^0\sim a^{\prime },{\left[a^0\right]}_L={\left[a^{\prime }\right]}_{L}and\forall i\in I\left(j\right):{\left(a^0\right)}_{32+i}=1$, where the sets $I\left(j\right)$ are defined in Figure 4.

We define $a^0:=F_{K^1,K^{1^{\prime }}}^R\circ F_{K^2,K^{2^{\prime }}}^R\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R\left(a^{\prime }\right)$, with $(K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$. Therefore, ${\left[a^0\right]}_L={\left[a^{\prime }\right]}_L$, and we will see that if $(K^i,K^{i^{\prime }}),i\in \{1,\cdots ,n\}$ have been chosen appropriately, we can have ${\left(a^0\right)}_{32+i}=1,\forall i\in I\left(j\right)$.

For $j=1$:

According to Table 2, ${\left[EP{\left(a^{\prime }\right)}_L\right]}_2\ne 0$ and ${\left[EP{\left(a^{\prime }\right)}_L\right]}_3\notin \{0,1\}$, since the corresponding positions for $a_1^{\prime }$ are 12 and 14, which are in blocks 2 and 3. Therefore, we have:

• If ${\left[EP{\left(a^{\prime }\right)}_L\right]}_2\ne 1$, then $U\left({\left[EP{\left(a^{\prime }\right)}_L\right]}_2\right)={\{0,1\}}^4$. Hence, because of Remark 1, $\exists (K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$ such that ${\left[{\left[a^0\right]}_R\right]}_2={[F_{K^1,K^{1^{\prime }}}^L\circ F_{K^2,K^{2^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^{\prime }\right)]}_2=(1,1,1,1)$. Therefore, ${\left(a^0\right)}_{32+i}=1$ for all $i\in \{5,\cdots ,8\}$.
• If ${\left[EP{\left(a^{\prime }\right)}_L\right]}_2=1$, then $U\left({\left[EP{\left(a^{\prime }\right)}_L\right]}_2\right)=\{0,2,4,6,8,10,12,14\}$. With a similar argument, $\exists (K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$ such that ${\left[{\left[a^0\right]}_R\right]}_2={[F_{K^1,K^{1^{\prime }}}^L\circ F_{K^2,K^{2^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^{\prime }\right)]}_2=(1,1,1,0)$. Therefore, ${\left(a^0\right)}_{32+i}=1$ for all $i\in \{5,\cdots ,7\}$.

Since ${\left[EP{\left(a^{\prime }\right)}_L\right]}_3\notin \{0,1\}$, then $U\left({\left[EP{\left(a^{\prime }\right)}_L\right]}_3\right)={\{0,1\}}^4$ and therefore $\exists (K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$ such that ${\left[{\left[a^0\right]}_R\right]}_3={[F_{K^1,K^{1^{\prime }}}^L\circ F_{K^2,K^{2^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^{\prime }\right)]}_3=(1,1,1,1)$. Therefore, ${\left(a^0\right)}_{32+i}=1$ for all $i\in \{9,\cdots ,12\}$.

Thus, considering the composition of the functions involved, we obtain $a^0$ such that ${\left(a^0\right)}_{32+i}=1,\forall i\in \{5,\cdots ,12\}\backslash \left\{8\right\}$.

A similar argument applies to the other values of $j\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\}$.

Now, we will see that $\exists a^1\in {\{0,1\}}^{64}\backslash \{0,d\}:a^1\sim a^0,{\left[a^1\right]}_R={\left[a^0\right]}_{R}and\forall i\in J\left(j\right):{\left(a^1\right)}_i=e_i$, where the sets $J\left(j\right)$ are defined in Figure 5.

We define $a^1:=F_{K^1,K^{1^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^{\prime }\right)$, with $(K^i,K^{i^{\prime }})\in \mathbb{M}$. Therefore, ${\left[a^0\right]}_R={\left[a^{\prime }\right]}_R$, and we will see that choosing adequate elements $(K^i,K^{i^{\prime }})$, we can have ${\left(a^1\right)}_i=e_i,\forall i\in J\left(j\right)$.

For $j=1$, $I\left(1\right)=\{5,\cdots ,12\}\backslash \left\{8\right\}$:

According to Table 2, let us see which positions $EP\left({\left({\left[a^0\right]}_R\right)}_i\right)$ are in for the different values of $i\in I\left(1\right)$. We can see $EP\left({\left({\left[a^0\right]}_R\right)}_5\right)$ is in position 18 (block 3) and 20 (block 4), $EP\left({\left({\left[a^0\right]}_R\right)}_6\right)$ is in position 41 (block 7) and 43 (block 8), $EP\left({\left({\left[a^0\right]}_R\right)}_7\right)$ is in position 3 (block 1), $EP\left({\left({\left[a^0\right]}_R\right)}_9\right)$ is in position 35 and 37 (blocks 6 and 7), $EP\left({\left({\left[a^0\right]}_R\right)}_{10}\right)$ is in position 23 and 25 (block 4 and 5), $EP\left({\left({\left[a^0\right]}_R\right)}_{11}\right)$ is in position 45 (block 8), and $EP\left({\left({\left[a^0\right]}_R\right)}_{12}\right)$ is in position 9 (block 2).

In all blocks j, for $j\in \{1,\cdots ,8\}\backslash \left\{3\right\}$, we have ${\left[EP{\left[a^0\right]}_R\right]}_j\notin \{0,1\}$ and then $U\left({\left[EP{\left[a^0\right]}_R\right]}_j\right)={\{0,1\}}^4$. Therefore, as discussed in the previous proofs, $\exists (K^i,K^{i^{\prime }})\in \mathbb{M}$ such that ${\left[{\left[a^1\right]}_L\right]}_j:={[F_{K^1,K^{1^{\prime }}}^L\circ F_{K^2,K^{2^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^{\prime }\right)]}_j={\left[e\right]}_j\forall j\in \{1,\cdots ,8\}\backslash \left\{3\right\}$. For block 3, we have ${\left[EP{\left[a^0\right]}_R\right]}_3=1$, therefore $\exists (K^i,K^{i^{\prime }})\in \mathbb{M}$ such that ${\left(a^1\right)}_i:={(F_{K^1,K^{1^{\prime }}}^L\circ F_{K^2,K^{2^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^{\prime }\right))}_i=e_i\forall i\in \{9,\cdots ,11\}$.

Therefore, the only position we cannot assure is equal to e is $i=12$, therefore $J{\left(1\right)}^c=\left\{12\right\}$.

For the rest of the indices j, we use similar arguments to compute sets $J\left(j\right)$.

• If $j\in \{1,6,9,14,16,17,21,22,25,29,32\}$, the set $\left(\right\{1,\cdots ,32\}\backslash \{13,\cdots ,16\left\}\right)\backslash J\left(j\right)$ has only one element. Therefore, as ${\left({\left(a^1\right)}_L\right)}_i=e_i\forall i\in$ J(j),${\left[EP\left(a_L^1\right)\right]}_i\notin \{0,1\}\forall i\in \{1,\cdots ,8\}\backslash \left\{4\right\}$, so $U\left({\left[EP\left(a_L^1\right)\right]}_i\right)={\{0,1\}}^4$. Therefore, choosing appropriate $(K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$ we get $a^2:=F_{K^1,K^{1^{\prime }}}^R\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^R\left(a^1\right)$, such that ${\left({\left[a^2\right]}_R\right)}_i=e_i\forall i\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\}$ (Remark 1).
  Therefore, we have ${\left[EP\left(a_R^2\right)\right]}_i\notin \{0,1\}\forall i\in \{1,\cdots ,8\}\backslash \left\{4\right\}$, so $U\left({\left[EP\left(a_L^2\right)\right]}_i\right)={\{0,1\}}^4$. Now, choosing adequate $(K^i,K^{i^{\prime }})\in {\mathbb{M}}_{d^{\prime }}$, we can have $a^3:=F_{K^1,K^{1^{\prime }}}^L\circ \cdots \circ F_{K^n,K^{n^{\prime }}}^L\left(a^2\right)$, such that ${\left(a^3\right)}_i=e_i\forall i\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\}$. Therefore, for $a^{″}:=a^3$ we have the desired result.
  Hence, we have seen that the lemma holds if $a_j^{\prime }=1$ for $j\in \{1,6,9,14,16,17,21,22,25,29,32\}$.
• For indices $j\in \{1,\cdots ,32\}\backslash \{2,5,10,18,26,31\}$, we have $J\left(j\right)\cap \{1,6,9,14,16,17,21,22,25,29,32\}\ne \varnothing$. Therefore, we are in the case where $\exists j\in \{1,6,9,14,16,17,21,22,25,29,32\}$ such that ${\left(a^1\right)}_i=1$, and carrying out the same procedure as the one to get $a^3$ from $a^{\prime }$, we get $a^{″}$ satisfying ${\left(a^{″}\right)}_i=e_i\forall i\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\}$.

 ☐

Lemma 6.

$\forall a^{″}\in {\{0,1\}}^{64}\backslash \{0,d\}:a_i^{″}=e_i\forall i\in \{1,\cdots ,32\}\backslash \{13,\cdots ,16\},\exists z\in {\{0,1\}}^{32}:a^{″}\sim (e,z)$.

Proof. 

According to Table 2, ${\left[\left(EP{\left(a\right)}_L\right)\right]}_4$ corresponds to positions 26, 5, 18, 31, and 2. Since $\{2,5,10,18,26,31\}\cap \{13,\cdots ,16\}=\varnothing$, we know ${\left(a_L^{″}\right)}_i=e_i,\forall i\in \{2,5,10,18,26,31\}$. Therefore, ${\left[\left(EP{\left(a\right)}_L\right)\right]}_4=(1,1,1,1,1,0)=62$ and because of Lemma 2 (c), $U\left({\left[EP\left({\left(a^{″}\right)}_L\right)\right]}_j\right)={\{0,1\}}^4$. Thus, considering appropriate $(K^i,K^{i^{\prime }})$, we get $(e,z)=F_{K^1,K^{1^{\prime }}}^L\circ \cdots F_{K^n,K^{n^{\prime }}}^L\left(a^{″}\right)$, for some $z\in {\{0,1\}}^{32}$. ☐

Corollary 1.

$\forall a\in {\{0,1\}}^{64}\backslash \{0,d\}\exists z\in {\{0,1\}}^{32}:a\sim (e,z)$.

Proof. 

Considering the chain $a\sim a^{\prime }\sim a^{″}\sim (e,z)$, where these elements are as described in the previous lemmata, the result follows. ☐

Corollary 2.

$G_{0,d}$ is transitive on ${\{0,1\}}^{64}\backslash \{0,d\}$.

Proof. 

Let $a,a^{\prime }\in {\{0,1\}}^{64}\backslash \{0,d\}$, by Lemma 6 and Corollary 1, $\exists z,z^{\prime }\in {\{0,1\}}^{32}:a\sim (e,z)\sim (e,z^{\prime })\sim a^{\prime }.$ ☐

Corollary 3.

$G_0$ is transitive on ${\{0,1\}}^{64}\backslash \left\{0\right\}$.

Proof. 

Because of Corollary 1, it is enough to show that $\exists g\in G_0$ such that $g\left(d\right)\ne d$.

Note that since $g\in G_0$, then $g\left(d\right)\ne 0$.

Let $(K,K^{\prime })\in \mathbb{M}\backslash {\mathbb{M}}_{d^{\prime }}$, then $S\left(K\right)=S\left(K^{\prime }\right)$ and $S(K\oplus d^{\prime })\ne S(K^{\prime }\oplus d^{\prime })$. Therefore, $F_{K,K^{\prime }}^R\left(d\right)=(d_L,d_R\oplus )S(K\oplus d^{\prime })\oplus S(K^{\prime }\oplus d^{\prime })\ne d$, and $F_{K,K^{\prime }}^R\in G_0$. ☐

Lemma 7.

If $G_0$ is transitive on ${\{0,1\}}^{64}\backslash \left\{(0,\cdots ,0)\right\}$ and $G_{0,d}$ is transitive on ${\{0,1\}}^{64}\backslash \{(0,\cdots ,0),d\}$, then G is 3-transitive on ${\{0,1\}}^{64}$.

Proof. 

It follows immediately from [17] (Theorem 9.1). ☐

Once we have shown that G is a 3-transitive subgroup of $A_{2^{64}}$, it is not particularly difficult to verify that G is actually equal to the alternating group on $2^{64}$ points.

Theorem 1.

The round functions of DESL generate the alternating group, i.e., $G=A_{2^{64}}$.

Proof. 

We refer to the proof of Theorem 1 in [7], since the same proof applies here. ☐

4. Applying MRHS to DESL and DES

The previous section focuses on a structural group-theoretic property which does not take the actual number of DESL rounds into account. Subsequently, we studied an algebraic attack against reduced and full round versions of DESL and compared the behavior of the attack with the situation for DES. The underlying question is, to what extent does the modified S-box change the complexity of an algebraic attack?

4.1. Symbol Creation for DESL

Since the structure of DES and DESL is the same, the process for creating the A-parts of MRHS symbols for DESL is the same as that for DES, which is described nicely in [12] (pp. 50–53). The only difference is that the L-part of each symbol will not correspond to a DES S-box, but instead to the DESL S-box. This L-part is given as

$$\left[\begin{array}{cccccccccccccccc}0& 0& 0& 0& 0& 0& 0& 0& F& F& F& F& F& F& F& F\\ 0& 0& 0& 0& F& F& F& F& 0& 0& 0& 0& F& F& F& F\\ 0& 0& F& F& 0& 0& F& F& 0& 0& F& F& 0& 0& F& F\\ 0& F& 0& F& 0& F& 0& F& 0& F& 0& F& 0& F& 0& F\\ 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3& 3\\ 5& 5& 5& 5& 5& 5& 5& 5& 5& 5& 5& 5& 5& 5& 5& 5\\ 8& 5& E& 3& 6& 9& 6& 9& 6& 6& 9& 9& A& C& 3& 5\\ E& 9& 4& 3& 1& 6& F& 8& 9& 7& 2& C& 6& C& 9& 3\\ 8& B& D& 6& 7& 4& 8& 3& 1& E& 6& 1& C& 9& 3& E\\ 6& 9& 9& A& 5& 9& 6& 6& 6& 5& 6& 9& 5& A& A& 9\end{array}\right],$$

where each entry is written as standard hex notation to save space. Note that the top six rows correspond to each of the possible inputs to an S-box, and the bottom four rows correspond to the output of the S-box. For example, if the input to the S-box is 000000, then the output is 1110, both being readable from the first column of this matrix. If the input is 000001, then the output is 0101, both being readable from the second column. Further, if the input is 000010, the output is 0101, and if the input is 000011, the output is 0000.

4.2. Results

For serious ciphers, very often the first MRHS action cycle of agreeing, gluing, and equation extracting (that is, until a guess is called for) will not be sufficient to discover the key, so guesses of the key variables must be committed. Naturally, the fewer guesses required, the better an attack is deemed to be. We give the name $\delta$ to the number of key bits we must guess before we discover the whole key through an MRHS attack.

For our attacks, we use a machine called Blue with the following specifications: two quad-core Xeon E5520 2.26 GHz processors (though only one core was used), 24 GB of RAM, using Windows 7 Server (Standard Edition). The ciphertext was 0123456789ABCDEF, and the key was the first 56 bits of the SHA-1 hash of “Katalina” (without quotes).

Under these conditions, DESL was attacked on Blue, varying both the number of rounds of the cipher and the threshold of MRHS. The results are summarized in

Table 3. DESL $\delta$ on Blue, for varying rounds and thresholds.

	Rounds of DESL
Threshold	4	6	8	10	12	14	16
20	0	34	36	36	40	38	40
21	0	34	39	37	39	39	42
22	0	33	39	37	38	43	38
23	0	33	38	45	46	48	46

, with the note that the threshold listed is actually the base 2 logarithm of the actual threshold, so we always choose a power of 2 for the number of columns each L-part is allowed to grow to.

We can see from this data that four rounds of DESL could be handled in the initial turn of an MRHS attack, but things became more complicated with more rounds. For more than six rounds it was not at all guaranteed that an increased threshold would actually help with the computation. Only for twelve rounds did we see an improvement with increased threshold, but once we moved to a threshold of 23, $\delta$ increased dramatically.

By way of contrast, DES was attacked on Blue varying the number of rounds and threshold. The results are summarized in

Table 4. DES $\delta$ on Blue, varying rounds and thresholds.

	Rounds of DES
Threshold	4	6	8	10	12	14	16
20	1 (+1)	35 (+1)	36 (+0)	36 (+0)	41 (+1)	41 (+3)	40 (+0)
21	0 (+0)	35 (+1)	39 (+0)	37 (+0)	39 (+0)	40 (+1)	39 (−3)
22	0 (+0)	32 (−1)	39 (+0)	37 (+0)	38 (+0)	40 (−3)	38 (+0)
23	0 (+0)	33 (+0)	39 (+1)	43 (−2)	46 (+0)	48 (+0)	46 (+0)

.

Overall, DESL was about as secure as DES from an MRHS perspective, though there were two occasions where DESL required three more bits to guess before recovering the entire key.

We remark in passing that it was conjectured by Schoonen in [12] (Hypothesis 5.1) that for 7–16 rounds of DES, $\delta$ would always be 56 minus the (base 2 logarithm of the) threshold, but Table 4 makes it plain that this was not the case.

5. Conclusions

Unlike DES, the DES Lightweight extension (DESL) uses a single S-box. The security of DESL against a number of common types of attacks has already been argued in the literature. In this work we establish that the round functions of DESL generate the same permutation group as the round functions of DES, namely, the alternating group on $2^{64}$ points. Moreover, based on our work, DESL appeared to offer comparable resistance to MRHS-based algebraic attacks as DES. Therefore, from these algebraic points of view, DESL has no disadvantage compared to DES, and the structural properties of DESL remain an interesting cryptanalytic topic of study.