New member of the LS-design, Mysterion, has arrived recently. Compared to the predecessors, Robin and Fantomas, it is designed to be more secure and it is possible to implement it efficiently.
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!
