Block ciphers are one of the key components in cryptography. Recently, lightweight cryptography became popular and it carried the design approach of a block cipher into different points. Depending on the requirements of the platform: low energy consumption, restriction on area, low multiplicative complexity, resistance against side-channel attacks etc., many new design approaches were proposed over the years.

In 1945, Shannon defined two properties of a block cipher: diffusion and confusion. Restrictions on lightweight cryptography pushes the search of a perfectly secure diffusion and confusion components to find suboptimal secure but efficient components. S-boxes are one of the main primitive in symmetric-key cryptography. They are the smallest component in an algorithm which provides confusion. The size of an S-box can change from three-bit to n-bit but mostly four and eight-bit length is preferred.

We focus on S-box constructions and consider the uniformity property of an S-box which plays an important role in Threshold Implementations (TI). Most papers so far have studied TI sharings for given S-boxes. We proceed in the opposite way: starting from n-bit S-boxes with known sharings we construct new (n + 1)-bit S-boxes from them with the desired sharings. We studied general n-bit S-boxes but we did our experiments for small sizes i.e. three to five bits.

It follows that the truth table of the constructed (n + 1) × (n + 1) S-box S has the form shown in Table 1.

Applying the approach over 3 × 3 S-boxes to obtain 4 × 4 S-boxes showed that (1) enriches the number of classes we can construct and the uniform sharings we can obtain as shown in Table 2.

Similarly, applying the approach over 4 × 4 S-boxes to obtain 5 × 5 but restricted only to the affine and quadratic S-boxes gives the results shown in Table 3. We obtain 23 out of the 75 quadratic classes given in [1]. In addition, it is clear from this construction why for the classes and no uniform sharing with 3 shares was found in [1]. Namely, they are extensions of class which has no uniform sharing itself.

To sum up, we have shown that Shannon’s expansion can be used to construct uniform sharing for certain affine equivalent classes of S-boxes. We have also shown the limitations of this expansion, namely that not all 4-bit S-box classes can be obtained from the 3-bit S-box classes in this way.

Thanks to Kerem Varici for writing this blog post!

New member of the LS-design, Mysterion(1), has arrived recently. Compared to the predecessors, Robin(2) and Fantomas(3), it is designed to be more secure and it is possible to implement it efficiently.

(1) (2) (3)

In 2014, addressing to the question “How simple can block ciphers be?”, a new block cipher family called LS-design was proposed in FSE’14. The aim of the design is basically efficient bit slice implementation of the cipher by combining linear diffusion L-boxes with non-linear bitslice S-boxes. The total number of AND gates is minimized for masked implementations against side channel attacks and two instances, involutive cipher Robin and non-involutive cipher Fantomas, are proposed.

A year after, Leander et al., pointed out a flaw in which leads to a weak key set of density . The problem can be solved by either adding dense constant values to the cipher or tweaking the cipher. The second solution approach brings us to the new member of the LS-design family: Mysterion.

Mysterion is the extension of the LS-design (i.e. XLS-design). Although the design rational shares the same ideas with former family members, Mysterion uses two different linear diffusion layers instead of one to increase the security level. Comparison of the two designs can be seen in the Figure 1.

Figure 1: Comparison of the designs

Mysterion supports 128-bit and 256-bit block sizes. Mysterion-128 has 4×32-bit blocks and Mysterion-256 has 8×32-bit blocks. Details of the cipher can be given as:

The S-box: Mysterion uses the Class13 s-box [1], that has a bitslice implementation with four AND and four XOR gates, algebraic degree three with a differential probability of 2^(-2), and linear probability of 2^(-1).

The L-box: Mysterion uses recursive MDS matrices as diffusion layer which are derived by using the recent paper [2]. Branch number of MDS matrix is 9.

ShiftColumns: For Mysterion-128, ShiftColumns acts on columns two by two and for Mysterion-256, ShiftColumns acts on columns one by one.

This work extends the block cipher design space from LS-designs to XLS-designs. This is an interesting step forward, since it is in line with the general question of “how simple can block ciphers be?”, in a context — i.e. considering the risk of side-channel analysis — where simplicity is usually correlated with security. XLS-designs can be implemented efficiently (and lead to better security bounds against linear and differential cryptanalysis), their best implementation requires informed decisions (e.g. on whether the use of bit manipulations can be critical). These questions lead to many open problems regarding the best cipher instances for different block/key sizes.

References

[1] Ullrich M., De Cannière C., Indesteege S., Küçük Ö., Mouha N., Preneel B.: Finding optimal bitsliced implementations of 4×4-bit s-boxes. In: SKEW 2011 Symmetric Key Encryption Workshop, Copenhagen, pp. 16–17 (2011)
[2] Augot D., Finiasz M.: Direct construction of recursive MDS diffusion layers using shortened BCH codes. In: Cid C., Rechberger C. (eds.): Fast Software Encryption-21st International Workshop, FSE 2014, 3– 5 London, 2014, Revised Selected Papers, pp. 3–17. Lecture Notes in Computer Science, vol. 8540, Springer, Berlin (2015).

Thanks to Kerem Varici for writing this blog post!