Research On Provable Security Of Substitution-Permutation Network Type Block Cipher Structures

The security analysis of symmetric cryptography is widely used in data encryption,message authentication code,hash function.stream cipher and pseudorandom number generator,and key management.Therefore,its security analysis has always been one of the core issues in the field of cryptography.Its provable security conclusion about the structure can exclude all attacks satisfying the hypothesis on the basis of reasonable assumptions to some extent.(Generalized)Feistel structure and substitution-permutation network structure(SPN structure)are the two basic structures most commonly used in existing block cipher schemes.The study of their provable security conclusions is of great significance to guide the design of cryptographic algorithms such as block cipher and hash function.This paper has made some conclusions on improving the existing encryption schemes based on substitution-permutation networks,which serve as the basis for the follow-up research.Substitution-permutation networks start with a set of public permutations on the set of n-bit strings which are called S-boxes.These public permutations are then extended to a keyed permutation on wn-bit inputs for some integer w by iterating the following steps:Substitution step-break down the wn-bit state into w disjoint chunks of n bits,and evaluate an S-box on each chunk;Permutation step-apply a keyed permutation to the whole wn-bit state(which is also applied to the plaintext before the first round).The traditional security notion for block ciphers is(strong)pseudorandomness:for any adversary with reasonable resources,the block cipher with a random and secret key should be indistinguishable from a truly random permutation.To prove security for substitution-permutation networks,the "S boxes" may be idealized as secret random functions or permutations,leaving the permutation layers as efficient "noncryptographic" functions.In this case,the S-boxes act as the only source of cryptographic hardness,while the permutation layers only supply auxiliary combinatorial properties.This limits the provable security to the domain-size of the S boxes,which is unfortunately as small as 8 bits in,e.g.,the AES.Consequently,provable results on substitution-permutation networks do not relate to any concrete block ciphers based on substitution-permutation network.Instead,they should be viewed as theoretical support for the substitution-permutation network approach to constructing block ciphers.There are few papers in this direction on the security proof of substitution-permutation network structure.Most of the previous work has analyzed key-independent,secret S-boxes.Based on this research,we discover that with more than two rounds,non-linear substitution-permutation network structure could ensure beyond-birthday-bound security.Though,practitioners prefer linear substitution-permutation network structure,the security of which is only proved up to birthday-bound at three rounds.Observing this gap,this paper focuses on linear substitution-permutation network structures with independent S-boxes and independent round keys,and on the case where w≥2.For such linear substitution-permutation network structure this paper proves the first beyondbirthday-bound security result on four rounds,which break the birthday bound barrier.At the same time,this paper considers linear tweakable substitution-permutation network structure(w≥2)with independent S-boxes and independent round keys,and proves that the linear tweakable substitution-permutation network structure is beyondbirthday-bound security on six rounds.In 2013,Gerard et al.proposed the partial substitution-permutation network construction(P-SPN construction),in which the S-box layer is applied to only a part of the state in each round(in exchange for somewhat increasing the number of rounds).AtEurocrypt 2020,Grassi et al.proposed the HADES design strategy that combines the classical substitution-permutation network construction with the partial substitutionpermutation network construction.A middle layer of partial substitution-permutation network rounds is surrounded by two layers of substitution-permutation network rounds in a HADES design.Among that,the efficiency provided by the partial substitutionpermutation network construction,along with the clean security arguments applicable for the substitution-permutation network construction.Besides,the HADES design strategy that combines the classical substitution-permutation network construction with the partial substitution-permutation network construction.There are almost no results about provable security of HADES,and the research on HADES focuses on its designs(the MDS matrix)and attacks(differential attacks and linear attacks).Beyond-Birthday-Bound Security for 4-round Linear SPN Structure.This paper demonstrates that,under specific assumptions,a four-round linear substitutionpermutation network can achieve beyond the birthday bound security.Compared to the birthday bound security achievable with only three rounds,this result showcases the optimal security achieved by the four-round linear SPN structure.This breakthrough signifies important progress in the security of SPN structures.Additionally,this paper proves the notion of point-wise proximity,thus establishing 2n/3-bit multi-user security for four round linear substitution-permutation networks as well.Firstly,this paper defines a "second order zero-free" linear matrix,characterizing conditions on the linear layers that are sufficient for 2n/3-bit security.For a linear transformation T to meet this,it has to be"zero-free".In addition,in both T and T-1,the sum of every two entries from the same row shall be non-zero.Thus,the conditions are slightly stronger than that for birthday-bound,and may be viewed as a second order extension of the aforementioned "zero-free" condition.In addition,a newer proof framework for the linear substitution-permutation network structure is proposed,namely "peeling off the outer rounds".With this,this paper shows that a four round linear substitution-permutation network is beyond-birthday-bound secure,if:(1)four independent public random Sboxes are used in the four rounds respectively,(2)such a "second order zero-free"linear permutation layer is used in every round,(3)the round keys are uniform and independent.Birthday-Bound Security of Four Round HADES Structure.This paper proves that,under specific assumptions,a four-round HADES structure can achieve birthday bound security.In comparison to previous research on the design and attacks of HADES structures,this result provides the unique conclusion regarding the provable security of HADES structures.This breakthrough signifies significant progress in the research of provable security for the HADES structure.Firstly,a good linear permutation layer is defined,which describes the conditions of a linear permutation layer that are sufficient to satisfy n/2-bit security.For a linear MDS matrix to satisfy this requirement,it must satisfy the "zero-free" property,and at the same time,in T and T-1,the sum of each term from the same column should be nonzero.Then,combining the proof of the partial substitution-permutation network structure and the proof framework of "peeling off the outer rounds",the first proof result of the HADES structure is proposed.Based on the above,this paper tries to prove that the four-round HADES structure is safe,with the middle two rounds that consists of partial S-boxes surrounded by the outer two rounds of substitution-permutation network.With this,this paper shows that a four round HADES structure is birthday-bound secure,if:.(1)four independent public random S-boxes are used in the four rounds respectively,(2)such a linear permutation layer(MDS matrix)is used in every round,(3)the round keys are uniform and independent.At the same time,this paper gives a three-round HADES structure attack process.Beyond-Birthday-Bound Security of Six Round Tweakable Linear SPN Structure.This paper presents a general model for a tweakable linear substitution-permutation network structure and proves that a six-round tweakable linear SPN structure is a strong tweakable pseudorandom permutation capable of achieving beyond the birthday bound security.This result indicates that the six-round tweakable linear SPN structure achieves the best security among current tweakable linear SPN structures.This breakthrough represents significant progress in the research of security for tweakable linear SPN structures.We further extend this line of work,by investigating how to add a tweak t into the linear substitution-permutation network model to have a strong tweakable pseudorandom permutation.Firstly,a good linear matrix is defined,which describes the conditions of a linear permutation layer sufficient to satisfy 2n/3-bit security.Then,using the proof framework of "peeling off the outer rounds",twice,the security results of the breakthrough birthday bound security of the linear tweakbale substitutionpermutation network structure are proposed.In this paper,a sub-tweak γi(t)is derived using a linear tweak derivation function γi and is straightforwardly xored into the i-th round-key.With this,this paper shows that a six round linear tweakable substitutionpermutation network is beyond-birthday-bound secure,if:(1)six independent public random S-boxes are used in the six rounds respectively,(2)a good linear permutation layer is used in every round,(3)the round keys are uniform and independent.