Design of S-boxes by concatenation of rotation-symmetric S-boxes

Abstract

S-kutuları olarak da isimlendirilen yerleştirme kutuları blok şifreli kriptosistemlerin birçoğunda doğrusal olmayan tek bileşenlerdir. Bu yüzden bu kriptosistemlerin dayanıklılığı ağırlıklı olarak S-kutularının kriptografik özelliklerine bağlıdır. Bu tezde, hem doğrusal olmama, farksal birbiçimlilik, mutlak gösterge ve cebirsel derece gibi geleneksel kriptografik özellikleri bakımından güçlü, hem de farksal güç analizi (DPA) gibi yan kanal saldırılarına karşı dayanıklı S-kutularının tasarımı amaçlanmaktadır. Bu amaç doğrultusunda, 6x6 bijektif S-kutularını üretmek için verimli bir tüketici arama algoritması tasarlanmıştır. Bu S-kutuları, x=(x0,x1,...,x5) iken tau(x)=(x0,x2,x3,x4,x5,x1) permütasyonu altındaki simetrik S-kutularının oluşturduğu sınıfta bulunmaktadır. Bu sınıftaki her bir S-kutusu S'nin, her x için taşıdığı simetri özelliği tau(S(x))=S(tau(x)) dolayısıyla S, 5x5 döngüsel simetrik S-kutularının (DSSK'ların) bağlaşımı yöntemiyle elde edilen bir yapı olarak düşünülebilir. Bu algoritmada DSSK'ların kombinasyonel özellikleri kullanılarak ve afin denkliğe sahip bağlaşımlar elenerek, 2^(61,28) olan arama uzayı 2^(48,47)'ye düşürülmüştür. Bu araştırmanın sonucunda, bu sınıfta 2^(37,56) tane doğrusal olmama koşutu 24 (6x6 bijektif S-kutuları için bilinen en yüksek değer) olan S-kutusunun var olduğu ve bunlar içinde farksal birbiçimliliği 4 olan S-kutusu sayısının 2^(33,99) olduğu bulunmuştur. Bu da bağlaşım yönteminin, doğrusal olmamakoşutunun yüksek olması ve farksal birbiçimliliğinin düşük olması açısından zengin bir sınıf sağladığını gösterir.

In most of the block cipher cryptosystems, the substitution boxes, or so-called S-boxes, are the only nonlinear components, and hence the strength of these cryptosystems depends heavily on the cryptographic properties of the S-boxes. In this thesis, it is aimed to design S-boxes which are on one hand strong in terms of traditional cryptographic properties such as nonlinearity, differential uniformity, absolute indicator and algebraic degree, and on the other hand resistant to side-channel attacks such as differential power analysis (DPA). In the direction of this aim, an efficient exhaustive search algorithm is proposed to generate 6x6 bijective S-boxes situated in a class of symmetric S-boxes under the permutation tau(x)=(x0,x2,x3,x4,x5,x1), where x=(x0,x1,...,x5). Due to the symmetry property of tau(S(x))=S(tau(x)) for all x, any S-box S in this class can be considered as a construction obtained by the concatenation of 5x5 rotation-symmetric S-boxes (RSSBs). In this algorithm, using the combinatorial properties of RSSBs and eliminating the affine equivalent concatenations, the search space of this class is reduced from 2^(61,28) to 2^(48,47). At the end of this search, it is found that in this class there exist 2^(37,56) S-boxes having the best known nonlinearity 24 and among them the number of differentially 4-uniform ones is 2^(33,99), which indicates that the concatenation method provides a rich class in terms of high nonlinearity and low differential uniformity.