probabilitiesubuntutweak

TheAuthenticatedCipherMORUS(v2)15Sep,2016Designers:HongjunWu,TaoHuangSubmitters:HongjunWu,TaoHuangContact:wuhongjun@gmail.
comDivisionofMathematicalSciencesNanyangTechnologicalUniversity,SingaporeTableofContents1Introduction.
32SpecicationofMORUS32.
1Preliminaries32.
1.
1Operations32.
1.
2NotationsandConstants42.
2Parameters42.
3Recommendedparametersets52.
4ThestateupdatefunctionofMOURS52.
5MORUS-64072.
5.
1TheinitializationofMORUS-64072.
5.
2Processingtheassociateddata72.
5.
3TheencryptionofMORUS-64092.
5.
4ThenalizationofMORUS-64092.
5.
5ThedecryptionandvericationofMORUS-64092.
6MORUS-1280.
102.
6.
1TheinitializationofMORUS-1280102.
6.
2Processingtheassociateddata112.
6.
3TheencryptionofMORUS-1280112.
6.
4ThenalizationofMORUS-1280113SecurityGoals124SecurityAnalysis124.
1Thesecurityoftheinitialization124.
1.
1Algebraicdegree124.
1.
2Dierentialcryptanalysis124.
2Thesecurityoftheencryptionprocess144.
3Thesecurityofmessageauthentication144.
3.
1Internalstatecollision144.
3.
2Attacksonthenalization165Features166Performance.
176.
1Softwareperformance176.
2Hardwareperformance177Designrationale187.
1Stateupdatefunction187.
2Encryptionandauthentication187.
3Selectionofrotationconstants198Changes198.
1ChangesfromMORUSv1.
1toMORUSv2198.
2ChangesfromMORUSv1toMORUSv1.
1209Intellectualproperty.
2010Consent2031IntroductionInthisdocument,wespecifytheMORUSfamilyofauthenticatedcipherswithtwodierentinternalstatesizes:640bitsand1280bits,andtwodierentkeysizes:128bitsand256bits.
ThreeMORUSalgorithms–MORUS-640-128,MORUS-1280-128,andMORUS-1280-256arerecommendedinthisspecica-tion.
MORUSisadedicatedauthenticatedcipher.
Ithasthreeparametersets,includingMORUS-640-128,MORUS-1280-128,MORUS-1280-256.
TheinternalstatesizeofMORUSiseither640bitsor1280bits.
Thekeysizecanbe128bitsor256bits.
MORUSusesa128-bitnoncewhichshouldnotbereusedwithoutchangingthekey.
A128-bittagisusedinMORUSforauthentication.
ThedesignofMORUSisbasedonthemethodofdesigningstreamciphers,whichhassmallnumberofoperationsinthestateupdatefunction.
Moreover,wecarefullychoosetheoperationswhichcanbeecientlyimplementedwiththeSIMDinstructions.
MORUSisecientinsoftware.
ThespeedofMORUS-1280canreach0.
69cpbusingIntelHaswellprocessor.
ThisisevenfasterthanAES-128-GCMwithAES-NI.
Tothebestofourknowledge,MOURSisthefastestauthenticatedcipherwithoutusingtheAES-NIinstruction.
MORUSisecientinhardware.
OnlylogicgateAND,XORandrotationsareusedinMORUS.
Theseoperationscanbeecientlyimplementedinhard-ware.
UsingtheCAESARhardwareAPI[5],MORUS-1280-128reaches96Gbit/sinXilinxVirtex-7FPGA.
InDIAC2015,MuehlberghuberandG¨urkaynakpre-sentedthatthespeedofASICimplementationofMORUSstateupdatefunctioncouldreachabove250Gbit/s[8].
Thisdocumentisorganizedasfollows.
TheMORUSspecicationisintro-ducedinSection2.
ThesecurityofMORUSisdiscussedinSection3andSection4.
ThefeaturesofMORUSarediscussedSection5.
TheperformanceofMORUSisgiveninSection6.
ThedesignrationaleisgiveninSection7.
2SpecicationofMORUS2.
1Preliminaries2.
1.
1OperationsThefollowingoperationsareusedinMORUS::bit-wiseexclusiveOR.
&:bit-wiseAND.
:concatenation.
>>:rotationtotheright.
x:ceilingoperation,xisthesmallestintegernotlessthanx.
Rotl12832(x,n):Dividea128-bitblockxinto432-bitwords,rotateeachwordleftbynbits.
Rotl25664(x,n):Dividea256-bitblockxinto464-bitwords,rotateeachwordleftbynbits.
42.
1.
2NotationsandConstantsThefollowingnotationsandconstantsareusedinMORUS:0n:nbitsof'0's.
1n:nbitsof'1's.
AD:associateddata(thisdatawillnotbeencryptedordecrypted).
AD128i:a16-byteassociateddatablock(thelastblockmaybeapartialblock).
AD256i:a32-byteassociateddatablock(thelastblockmaybeapartialblock).
adlen:bitlengthoftheassociateddatawith0≤adlen>>w(i1)mod5)mi)Noticethatmiistheplaintextblockusedineachstepandmi=0ifi=0mod5.
AndthedierenceinplaintextwillinjecttoRound2andbethesameinRound3-5.
Toeliminatethedierenceaftertwosteps,weneedthatCV6,CV10havenodierence.
Inourstudy,wewillfocusonfollowingtwoconditions:1:NodierenceatCV6.
ThisisbecauseCV6iscompletelydeterminedbythepreviousstateelementsandhasnothingtodowiththeplaintextblockinthesecondstep.
2:ForeachdierenceatbitiinCV3orCV4theremustbeadierenceatbitiinCV5.
Otherwise,isimpossibletoeliminatethedierenceusingthedierenceinthesecondplaintextblock.
Thenwesearchedtheinputdierencebitstondalowerboundforthenumberofbitswithdierence(activebits)intheinput.
Wefoundthatfortheinputdierencewithweightlessthanorequalto25,thereisnovalid10-rounddierentialcharacteristicsforMORUS.
Nowwemayevaluatetheboundforthedierentialprobabilities.
Wheninputdierenceisnbits,therearenbitsdierencesatCV2,CV3andCV5.
SinceeachbitdierencewillbeinvolvedintwoANDoperations,andeachANDoperationononebithasdierentialprobability21,thedierentialprobabilityisatmost25n(5ANDoperationsforCViandCVi+1,i=1,2,3,4,5).
Thedierentialprobabilityislessthan226*5=2130.
Next,weconsiderthecasethattheinputdierencegeteliminatedin3steps.
Ifthereare3activebitsintheinput,thedierentialprobabilityafter3stepsis2132byourapproximation.
Notethatthedierenceisnoteliminatedthroughtheapproximation.
Muchstrongerconditionsareneededtoeliminatethedif-ferences.
Hencetheprobabilitythattheinputdierencegeteliminatedafter3stepswillbemuchlowerthan2132whenthenumberofactivebitsis3.
Whenweincreasethenumberofactivebitsintheinput,thetrendistoincreasetheweightofactivebitsinthestates,whichwecanobserveinthepreviouscases.
Intuitively,thiscanbeexplainedaswhentheweightofactivebitsislow,thenumberofnewactivebitsexceedsthenumberofactivebitsgeteliminated.
Andwhentheweightishighenoughsuchthatthenumberofeliminatedactivebitsexceedsthenewactivebits,wecanexpecttheoverallweightwillbemuchhigherthanthesingledierencecaseintherst3steps.
Hence,althoughitisimpossi-bletoenumeratealltheinputdierences,webelievethatthereisnodierentialcharacteristicwithprobabilityhigherthan2128whichcaneliminatetheinputdierencein3steps.
Nowwedealwiththecasesthatthenumberofactivebitsintheinputislessthanthree.
16-Onlyoneactivebitintheinput.
Sincethepositionofactivehasnoimpactonthedierentials,weassumetheactivebitisatbit0.
Then,wepropagatethedierenceupto3steps(15rounds),assumingnoinputdierenceatnexttwosteps.
Now,weenumeratetheinputdierenceatstep2suchthatfollowingtwoconditionsaresatised:1.
ThereisnodierenceatRound11.
Again,itisbecausethedierencecannotbeeliminatedthroughthemessageinstep3.
2.
TheactivebitsatCV10coverstheactivesbitsatCV8andCV9.
Oursearchshowthatevenifweincreasethenumberofactivebitsto20intheinputofthesecondstep,itisimpossibletondadierentialcharacter-isticsatisedtheaboveconditions.
Withsimilarevaluationofprobability,andtakeconsiderationtothedierentialprobabilityintroducedbytheini-tialdierence,wecanconcludethattheprobabilitythattheinternalstatecollisionislessthan2128inthiscase.
-Twoactivebitsintheinput.
Byourapproximation,thedierentialproba-bilityisatleast2101foranytwoactivebitspropagateto3steps.
Wethinkitissafetoconsidertheprobabilityforinternalstatecollisiontobelessthan2128ifthenumberofactivebitsinthesecondstepislargerthan20,inspitethatsomedierenceintheinternalstatemaybecanceledeachother.
Inoursearch,wexonebitdierenceatbit0andtrytoimposeadierenceattheother127possiblepositions.
Andthesearchresultconrmsthatnovaliddierentialcharacteristicisfoundwhenthenumberofactivebitsislessthan21.
Now,considertherestcases:thedierencegeteliminatedafteratleast4steps.
Ifthereisonebitdierenceattheinput,thedierentialprobabilityisatleast2196usingourapproximation,whichismuchlowerthan2128.
Andifwewanttoeliminatethedierences,moreconditionsarerequired.
Hence,itisreasonabletoconsidertheprobabilitytoeliminatedtheinternaldierenceinthesecasestobelessthan2128.
Thisconcludeouranalysiswhentheinternalstatecollisionisconstructedthroughinjectionofplaintextdierences.
4.
3.
2AttacksonthenalizationInadditiontotheinternalstatecollision,whenthereisadierenceintheinternalstatebeforethenalization,thedierentialprobabilityislessthan2256after10rounds(accordingtotheanalysisgiveninSection4.
1.
2).
Hence,thedierenceatthetagisunpredictableinthiscase.
5FeaturesMORUShasthefollowingadvantages:171.
MORUSisecientinsoftware.
Accordingtotheprevioussection,thespeedofMORUS-1280is0.
69cpbonIntelHaswellprocessorsforlongmessages,whichisaround30%fasterthanAES-GCM[6].
2.
MORUSisfastinhardwareperformance.
InMORUS,thecriticalpathtogenerateakeystreamblockis3ANDgatesand8XORgates.
3.
MORUSisecientacrossplatforms.
Inconstructingauthenticatedencryp-tionschemes,AESisfrequentlyusedasabuildingblock.
Thereareau-thenticatedencryptionmodessothattheAEScanbeusedasunderlyingblockcipher,e.
g.
,EAX[1],CCM[10],GCM[6]andOCB2.
0[9].
Anum-berofdedicatedAEschemesuseAESroundfunction,e.
g.
,AEGIS[11]andALE[3].
TheseschemescanbenetfromtheAES-NIwhichperformsoneroundAESencryption/decryptioninasingleinstruction.
Ontheotherhand,althoughthewidelyuseofAES,thereareplatformswhichdonotsupporttheAES-NIinstructionset.
TheperformanceofAESbasedauthenticatedencryptionschemeswillbenotablyslowerontheseplatforms.
Incontrast,theMORUSfamilyoeramoresteadyperformanceacrossplatformssinceitsperformancedoesnotrelyontheuseofAES-NIinstructionset.
4.
Secure.
MORUSprovides128-bitauthenticationsecurity,strongerthanAES-GCM.
6Performance6.
1SoftwareperformanceWeimplementedMORUSinCcode.
WetestedthespeedontheIntelCorei7-4770processor(Haswell)running64-bitUbuntu13.
01.
Turboboostisturnedointheexperiment.
Thecompilerbeingusedisgcc4.
8.
1,andtheoptions"-O3-mavx2"areused.
Thetestisperformedbyencrypting/decryptingamessagerepeatedly,andprintingoutthenalmessage.
Toensurethatthetaggenerationisnotremovedduringthecompileroptimizationprocess,weusethetagastheIVforprocessingthenextmessage.
Toensurethatthetagvericationisnotremovedduringthecompileroptimizationprocess,wesumupthenumberoffailedvericationsandprintoutthenalresult.
Table5showsthespeedcomparisonoftheMORUS.
Forlongmessage,thespeedofMORUS-640andMOURS-1280isabout1.
19cpband0.
69cpb,respec-tively.
ThespeedofMOURS-1280isfasterthanthatofAES-128-GCMontheHaswell,whichis1.
03cpb[4].
6.
2HardwareperformanceMORUSisdesigntobeecientinhardwareimplementation.
WeimplementedMORUS-1280-128usingtheCAESARhardwareAPIproposedbyHomsirikamoletal.
fromGMU[5].
OnmodernFPGAVertix-7,thefrequencyofMORUSis367.
6MHz,using1179slices(4122LUTs)inarea.
ThethroughputofMORUS-1280forlongmessageis94,117Mbits/s.
18Table5:Thespeedcomparison(incyclesperbyte)fordierentmessagelengthonIntelHaswell.
EAmeansencryption-authentication;DVmeansdecryption-verication.
16B64B512B1024B4096B16384BMORUS-640(EA)40.
6410.
352.
301.
721.
301.
19MORUS-640(DV)38.
4710.
132.
301.
721.
291.
18MORUS-1280(EA)45.
3210.
381.
851.
240.
800.
69MORUS-1280(DV)45.
7410.
661.
911.
280.
810.
70InDIAC2015,MuehlberghuberandG¨urkaynakprovidedASICimplementa-tionresultsofMORUSandanumberofotherhardware-ecientauthenticatedciphers,includingAES-128-GCM,ICEPOLE,AEGIS,NORX,Tiaoxin-346[8].
ThethroughputoftheMORUSstateupdatefunctionisabove250Gbit/sforlongmessage.
Thethroughput/Arearatioismorethan8000kbps/GE.
Bothresultsarethehighestamongthoseauthenticatedciphers.
7DesignrationaleInourdesignofMORUS,wearetryingtodesignafastauthenticatedcipherwhichisnotbasedonAESsothatthisciphercanrunfastinplatformswithnoAES-NI.
Ourdesignisaimedatachievingthefollowinggoals:-Simple-Secure-Fastinhardware-Ecientinsoftware-AvoidusingAESroundfunction7.
1StateupdatefunctionTheconstructionofstateupdatefunctionofMORUSisbasedon5smallroundfunctionswithsimilaroperations.
Ineachroundfunction,onlyXOR,ANDandrotationsareused.
ThediusionofMORUSisfromtwotypesofrotations:therotationsonthewholeregisters(<<<)andtherotationsonfourpartialwordsinsidearegister(Rotlxxxyy).
ThelateroperationtakesadvantageoftheSSE2andAVXinstructionsinwhichtheshiftsonfourwordcanbedoneinonein-struction.
WechoosetheANDnon-linearfunctionsinceitcanbeeasilyandecientlyimplementedinbothsoftwareandhardware.
Twointernalstateele-mentsgetupdatedinaroundfunction.
Hence,everyinternalstateelementwillgetupdatedtwiceinastep.
ItisremarkablethatMORUSisconstructedusingsimplebit-wiseoperations,whichmakesitfastinhardwareimplementations.
7.
2EncryptionandauthenticationTheencryptionofMORUSadoptsthemethodusedinstreamciphers.
Thekeyandnoncearemixedintothestateduringinitializationandafterthat,thecipher19generateskeystreamsandXORsthekeystreamswiththeplaintexttoproduceciphertext.
InMORUS,messageblocksareinjectedintoitsstateupdatefunctionsoastoauthenticatethemessagesimultaneouslywiththeencryption.
IntheinitializationofMORUS,weuse16stepsofstateupdatefunction(80rounds).
Thisistoensurethestatecannotberecoveredandthedierentialprobabilityissmallaftertheinitialization.
Inthenalization,weintroduceanextraXORoperationtodistinguishthenalizationfromtheencryptionandweuseasimilarmethodasusedinAEGIS:mixingthelengthofassociateddataandplaintextisXORedtooneoftheinternalstateelementsandusedasamessageblocktoupdatethestatesfor8steps.
Inthisway,anychangeintheinternalstateorthelengthofmessagewillbeinvolvedincomputingthetag.
7.
3SelectionofrotationconstantsThediusioninMORUSreliesonthe10rotations.
Therefore,therotationcon-stantsneedtobecarefullychosen.
Weusefollowingrulesintheselectionofrotationsconstants:1.
Therotationconstantsshouldexcludethemultiplesof8.
2.
Norotationconstantshouldbeamultipleofanotherrotationconstant.
3.
Thesumofanytwoconstantsmodular32(or64forMORUS-1280)isnotequalto0oranotherconstant.
Weenumeratethepossiblechoicesofrotationconstantssatisfyingtheaboverequirementsandpropagatea1-bitdierenceonmessagetocounttheweightafterfourstepsforMORUS-640andvestepsforMORUS-1280.
Thenweselectasetoftherotationconstantswhichresultsinhighweight.
Thedesignershavenothiddenanyweaknessesinthiscipher.
8Changes8.
1ChangesfromMORUSv1.
1toMORUSv2MinormodicationsinthenalizationofMORUS.
ThestateSu+v3isre-movedinthecomputationofthemessageword.
Thetaggenerationischangedtothesamewayasthekeystreamgeneration.
ThesechangesareaimedtoimprovethehardwareeciencyofMORUS.
Thenumberofstepsusedinnalizationisincreasedfrom8to10,whichimprovesthesecuritymarginofMORUSnalization.
MoreexplanationsinthesecurityanalysisofMORUSinitializationand-nalizationareadded.
ThehardwareperformanceofMORUSisadded.
Someeditorialchanges.
208.
2ChangesfromMORUSv1toMORUSv1.
1ThereisnotweakofMORUSinthesecondroundofCAESARcompetition.
WecorrectedtheFig.
1ofthestateupdatefunctionandafewtyposinthisdocumentversion.
9IntellectualpropertyMOURSisnotpatentedanditisfreeofintellectualpropertyrestrictions.
Ifanyofthisinformationchanges,thesubmitter/submitterswillpromptly(andwithinatmostonemonth)announcethesechangesonthecrypto-competitionsmailinglist.
10ConsentThesubmitter/submittersherebyconsenttoalldecisionsoftheCAESARse-lectioncommitteeregardingtheselectionornon-selectionofthissubmissionasasecond-roundcandidate,athird-roundcandidate,analist,amemberofthenalportfolio,oranyotherdesignationprovidedbythecommittee.
Thesub-mitter/submittersunderstandthatthecommitteewillnotcommentontheal-gorithms,exceptthatforeachselectedalgorithmthecommitteewillsimplycitethepreviouslypublishedanalysesthatledtotheselectionofthealgorithm.
Thesubmitter/submittersunderstandthattheselectionofsomealgorithmsisnotanegativecommentregardingotheralgorithms,andthatanexcellentalgorithmmightfailtobeselectedsimplybecausenotenoughanalysiswasavailableatthetimeofthecommitteedecision.
Thesubmitter/submittersacknowledgethatthecommitteedecisionsreectthecollectiveexpertjudgmentsofthecommitteemembersandarenotsubjecttoappeal.
Thesubmitter/submittersunderstandthatiftheydisagreewithpublishedanalysesthentheyareexpectedtopromptlyandpubliclyrespondtothoseanalyses,nottowaitforsubsequentcommitteedecisions.
Thesubmitter/submittersunderstandthatthisstatementisrequiredasaconditionofconsiderationofthissubmissionbytheCAESARselectioncommittee.
References1.
M.
Bellare,P.
Rogaway,andD.
Wagner.
TheEAXmodeofoperation.
InFastSoftwareEncryption,pages389–407.
Springer,2004.
2.
E.
BihamandA.
Shamir.
DierentialCryptanalysisoftheDataEncryptionStan-dard.
Springer-Verlag,London,UK,UK,1993.
3.
A.
Bogdanov,F.
Mendel,F.
Regazzoni,V.
Rijmen,andE.
Tischhauser.
ALE:AES-BasedLightweightAuthenticatedEncryption.
InFastSoftwareEncryption,2013.
4.
S.
Gueron.
AES-GCMsoftwareperformanceonthecurrenthighendCPUsasaperformancebaselineforCAESAR.
DIAC2013:DirectionsinAuthenticatedCiphers,Augest2013.
215.
E.
Homsirikamol,W.
Diehl,A.
Ferozpuri,F.
Farahmand,P.
Yalla,J.
-P.
Kaps,andK.
Gaj.
CAESARHardwareAPI.
CryptologyePrintArchive,Report2016/626,2016.
http://eprint.
iacr.
org/2016/626.
6.
D.
McGrewandJ.
Viega.
TheGalois/CounterModeofOperation(GCM).
http://csrc.
nist.
gov/CryptoToolkit/modes/proposedmodes/gcm/gcm-spec.
pdf.
7.
A.
Mileva,V.
Dimitrova,andV.
Velichkov.
AnalysisoftheAuthenticatedCipherMORUS(v1),pages45–59.
SpringerInternationalPublishing,Cham,2016.
8.
M.
MuehlberghuberandF.
K.
G¨urkaynak.
TowardsEvaluatingHigh-SpeedASICImplementationsofCAESARCandidatesforDataatRestandDatainMotion.
WorkshoponDirectionsinAuthenticatedCiphers(DIAC)2015,2015.
9.
P.
Rogaway.
EcientInstantiationsofTweakableBlockciphersandRenementstoModesOCBandPMAC.
InAdvancesinCryptology–ASIACRYPT2004,pages16–31.
Springer,2004.
10.
D.
Whiting,R.
Housley,andN.
Ferguson.
CounterwithCBC-MAC(CCM).
Avail-ablefromhttp://csrc.
nist.
gov/groups/ST/toolkit/BCM/documents/proposedmo-des/ccm/ccm.
pdf,2003.
11.
H.
WuandB.
Preneel.
AEGIS:AFastAuthenticatedEncryptionAlgorithm.
SelectedAreasinCryptography–SAC2013,2013.