分块对称密码的全微分和线性壳的极大值分布(IJCNIS-V6-N1-2)

I.J.ComputerNetworkandInformationSecurity,2014,1,11-18PublishedOnlineNovember2013inMECS()DOI:10.5815/ijcnis.2014.01.02Copyright©2014MECSI.J.ComputerNetworkandInformationSecurity,2014,1,11-18OnMaximaDistributionofFullDifferentialsandLinearHullsofBlockSymmetricCiphersLisitskiyK.E.NationalUniversityofRadioElectronics,Kharkiv,[e-mail]—Theproblemofdeterminationofmaximadis-tributionlawsoffulldifferentialsandlinearbiasofblocksymmetricciphersassubstitutiontransformationsiscon-sidered.Well-knowntheoreticalresults,publishedinlit-erature,aregiven,aswellasexperimentresultsonmak-ingthelawsofmaximadistributionoffulldifferentialtransitionsandmaximumbiasessoflinearhullsforre-ducedciphermodelfromBelorussianstandardandcipherKalina,whichpracticallyconfirmtheoreticalcalculations,arepresented.Theresultstestifythatmaximumvaluesofdifferentialandlinearprobabilitiesareconcentratedclosetotheiraveragevaluesandforevaluationofindexesofcipherprovablesecurityit’senoughtomakeatestofproximityofdifferentialandlinearcipherindexes,re-ceivedforonearbitrarilytakencipherkeycorrespondingtoindexesofrandomsubstitutions.IndexTerms—Provablesecurity,ofindexevaluationofprovablesecurityinblocksymmetricciphers,distributionofmaximums,miniversionsciphersI.INTRODUCTIONThispaperdealswithanewmethodologyofindexevaluationofprovablesecurityinblocksymmetricci-phers[1],accordingtowhichthepropertiesofblocksymmetriccipherscanbeevaluatedonthebasisofstudy-ingpropertiesoftheirreducedmodels.Herewewanttoremindoneofthecentralthesesofthismethodologywhichisformulatedasastatement:Allmodernblockciphers1afteracertainnumberofcyclesindependentlyofthoseusedinS-blocksciphers(herewedon’tmeantheirdegenerateddesigns)acquirethepropertiesofrandomsubstitutions,i.e.accordingtotheircombinatorialindexes(thenumberofinversions,increasesandcycles)aswellasaccordingtothelawsoftransitiontabledistributionofXORdifferences(fulldif-ferentials)andthedistributionlawsofbiaslinearapprox-imationtables(linearhulls)theyrepeatthecorrespondingindexesofrandomsubstitutions.AsaresultthemaximavaluesoffulldifferentialsandlinearhullsmeaningscanbedeterminedbycalculationsfromtheformulasforthedistributionlawsoftransitionprobabilitiesforXORta-HerethecipherDESisnotconsideredasamodernonebecausethetransitiontotherandomsubstitutionisperformedforseparatecipherkeysin16cyclesbecauseofthepresentsof0-typecharacteristics.blesandbiastablesoflinearapproximationsofappropri-aterandomsubstitutions.Herewith,thetestofrandomindexesoflargecipherscanbeperformedonthebasisofthedevelopmentandfurtheranalysisofrandomindexesofreducedmodels,permittingtomakecalculatingexperimentsinacceptable(real)term.Thisresultistestedonagreatnumberofreducedandlargemodelsofmanymodernciphers[2-10andothers].Theexperimentsmadehoweveraretiedtothelimitedsetofencryptionkeys.Nevertheless,onthebasisoftheseresultstheconclusionwasmadethatciphersecurityin-dexescanbedeterminednotbytheaveragingmethodoverthesetofkeysbutonthebasisofmaximadetermi-nationofdifferentialandlinearprobabilitiesforany(one)arbitrarilytakencipherkey.WealsorecallthatusingthisapproachtheevaluationofblocksymmetricciphersecurityindexesisproposedtodonotwiththehelpMADP(MaximumAverageDiffer-entialProbability)andMALHP(MaximumAverageLin-earHullProbability),asitisdoneinagreatnumberofpublications,butwiththehelpofAMDP(AverageMax-imumDifferentialProbability)andAMLHP(AverageMaximumLinearHullProbability)which,asshowninpaper[11]aremoresuitabletotheproblemsolved.Inthispaperwewanttosubstantiatethevalidityoftheconclusion,alreadypresentedinanumberofworks[2-10]thattheblocksymmetriccipherssecurityagainstdiffer-entialandlinearattacksreallycanbedeterminednotbytheaveragingmethodoverasetofkeysbutonthebasisofmaximumdeterminationofdifferentialandlinearprobabilitiesforany(one)arbitrarilytakencipherkeypermittingtooconvincethatmaximumvaluesoffulldif-ferentialsandcipherlinearhullscoincidewiththecorre-spondingindexesofrandomsubstitutions.Thegeneralapproachtosolvingthisproblemistostudythebehaviorofciphertransformationonthewholesetofcipherkeys.Experimentallythisapproachisbasedontheevaluationwiththehelpofcomputingexperimentsthemaximumvaluesoffulldifferentialsandlinearhullbiassforreducedciphermodelsforthewholesetofci-pherkeys(thereducedciphermodelspermittodoit)andthedeterminationofmaximumexperimentallyobtainedvaluesandtheirnumberforthewholesetofdifferentialandsubstitutionlineartableastheciphersthemselvesareconsidered.Mathematically,thisproblemcaststothemaximumdistributionstudyonagreatnumberofindependent12OnMaximaDistributionofFullDifferentialsandLinearHullsofBlockSymmetricCiphersCopyright©2014MECSI.J.ComputerNetworkandInformationSecurity,2014,1,11-18randomvalues.ThispaperposestheproblemofdeterminationofthegreatestpossiblevaluesoftransitionsamongagreatnumberoftableXORdifferencesandbiasesstablesoflinearapproximationsofsmallciphermodelsforthewholesetofencryptionkeys.Thefirstpartofthepapergivestheoreticalfoundations,whicharethebasisofdeterminationofthemaximadis-tributionlawsofagreatnumberofrand