密码算法及协议2密钥交换协议

2023/1/141Chapter2.

KeyExchangeProtocols2023/1/142MathematicalPreliminariesGroupsThroughout,Gndenotesacyclicgroupoffiniteordern,writtenmultiplicatively.Usually,butnotnecessarily,thegroupordernisprime.Recallthatanygroupofprimeorderiscyclic,andthatanyfinitecyclicgroupisabelian.Also,Gn=<g>,wheregisanygenerator(i.e.,anelementofordern)ofGn;thus,theelementsofGnareenumeratedas1,g,g2,g3,...,gn-1.Often,wewriteGasashorthandforGn.ThediscretelogofanelementyGisdefinedastheleastnonnegativeintegerxsatisfyingy=gx.Wewritex=loggy.ForyG,weletord(y)denoteitsorder.Notethatord(y)|n.2023/1/1432023/1/144MathematicalPreliminariesProbabilityThroughout,wewillusebasicnotionsfromprobabilitytheory,suchassamplespace,events,probability

distributions,andrandomvariables.Wewillonlybeconcernedwithdiscreterandomvariables.Specifically,weusethefollowingnotionofstatisticaldistance.DefinitionNote2023/1/145MathematicalPreliminariesThestatisticaldistanceisametricinthefollowingsense:2023/1/146DiscreteLogandDie-HellmanAssumptionsThefollowingthreeassumptionsarecommonlyusedincryptographicschemesbasedonadiscretelogsetting.Assumption2.1TheDiscreteLogarithm

(DL)assumptionforgroupGstatesthatitishardtocomputexgivengeneratorgandrandomgroupelementgx.Assumption2.2The(Computational)Diffie-Hellman(DH)assumptionforgroupGstatesthatitishardtocomputegxygivengeneratorgandrandomgroupelementsgx,gy.Assumption2.3TheDecisionDiffie-Hellman(DDH)assumptionforgroupGstatesthatitishardtodecidewhetherzxymodngivengeneratorgandrandomgroupelementsgx,gy,gz.2023/1/147ProbabilisticPolynomialTime(p.p.t.)AlgorithmAn(deterministic)algorithmisawell-definedcomputationalprocedurethattakesavariableinputandhaltswithanoutput.Aprobabilisticalgorithmissuchacomputationalprocedurethatmayfailwithoutanoutput,theprobabilityoffailurecanbecontrolledtoadequatelysmall.Thesizeoftheinputisthetotalnumberofbitsneededtorepresenttheinputinordinarybinarynotationusinganappropriateencodingscheme.Apolynomial-timealgorithmisanalgorithmwhoseworst-caserunningtimefunctionisoftheformO(nk),wherenistheinputsizeandkisaconstant.Aprobabilisticpolynomial-timealgorithmissimilarlydefined.2023/1/148DiscreteLogandDiffie-HellmanAssumptionsEachassumptionstatesthatitishardtosolveaparticularproblem.Informally,‘hard’meansthatanyprobabilisticpolynomialtime(p.p.t.)algorithmonlysucceedswithnegligibleprobabilityincomputingthecorrectoutput.Evidently,theseassumptionssatisfy:DLDHDDH.ThereforeitisbetterifaprotocolcanbeprovedsecureunderjusttheDLassumption.Itturnsout,however,thatinmanycasesthesecuritycanonlybeprovedundertheDHassumption,orevenonlyundertheDDHassumption.2023/1/149RandomSelf-ReducibilityDefinition1.13Aproblemiscalledrandomself-reducibleifanyinstanceIoftheproblemcanbesolvedby:(i)transforminginstanceIintooneormore(uncorrelated)uniformly-randominstancesI’,(ii)solvinginstancesI’,(iii)extractingtheanswerforIfromtheanswersforI’.Steps(i)and(ii)arerequiredtoruninpolynomialtime.TheDL,DHandDDHproblemsarerandomself-reducible.ThisisimmediatefortheDLproblem:givenanyinstancey=gx,(i)transformytoy’=ygrwithrRZn,(ii)solvetherandominstancey’forx’=loggy’,and(iii)extractthesolutionasx=loggh=x’-rmodn.2023/1/1410RandomSelf-ReducibilityForcryptographicpurposes,itisagoodsignifapresumablyhardproblemisrandomself-reducible.Inthatcase,itisexcludedthateventhoughtheproblemishardintheworst-case,theproblemisactuallyeasyontheaverage.Toseewhy,considerarandomself-reducibleproblemandsupposethattheproblemiseasyontheaverage.Thentherecannotbeanyhardinstancesatall,sinceanysuchinstancecanbesolvedbysolvinganassociatedrandominstanceduetorandomself-reducibility.Proposition:

Anyrandomself-reducibleproblemthatishardintheworst-caseisalsohardontheaverage.2023/1/1411RandomSelf-Reducibility2023/1/1412RandomSelf-Reducibility2023/1/1413RandomSelf-Reducibility2023/1/14142023/1/1415NegligibleFunctionForlateruse,wealsogiveamoreformalversionoftheDDHassumption,whichisstatedintermsofpolynomiallyindistinguishabledistributions.2023/1/1416PolynomiallyIndistinguishableDistributions2023/1/1417PolynomiallyIndistinguishableDistributions2023/1/1418PolynomiallyIndistinguishableDistributions2023/1/14192023/1/1420ExampleofPolynomiallyIndistinguishableSymmetricciphersAESciphertextsEk(m1),Ek(m2),…,Ek(mn)PRuniformelementsx1,x2,…,xn

{0,1}|E|

RFinitefieldsDiffie-Hellmantuple(g,gx,gy,gxy)PRuniformtuple(g,gx,gy,gz)RIntegersofthesamelengthtwo-primeoddcompositepq

PRuniformoddcompositen

RQuadraticresiduosityassumption(QRA):squarex2(modn)(nisarandomoddcomposite)PRuniformy<nofpositiveJacobisymbolmodn

R2023/1/1421HashFunctionDefinition:AfunctionH:{0,1}*

{0,1}k,mappingbitstringsofarbitrarylengthtobitstringsofafixedlengthk,k0,iscalledahashfunction.FunctionHiscalledacryptographichashfunction,ifitiseasytocomputeH(x)givenanystringx,andoneormoreofthefollowingrequirementsaresatisfied:preimageresistance(onewayness):givenak-bitstringyitiscomputationallyinfeasibletofindabitstringxsuchthatH(x)=y.2nd-preimageresistance(weakcollisionresistance):givenapairx,ywithy=H(x)itiscomputationallyinfeasibletofindabitstringx’xsuchthatH(x’)=y.collisionresistance(strongcollisionresistance):itiscomputationallyinfeasibletofindbitstringsx,x’withx’xsuchthatH(x)=H(x’).2023/1/1422HashFunctionIngeneral,collisionresistanceimplies2nd-preimageresistance,butcollisionresistanceneednotimplyonewayness.Inpractice,however,cryptographichashfunctionsusuallysatisfyallthreerequirements.PracticalexamplesofcryptographichashfunctionsareMD5,withoutputlengthsk=128SHA-1,withoutputlengthsk=160SHA-256,withoutputlengthsk=256Ifcollisionresistanceisnotrequired,onemaytruncatetheoutputsbydiscarding,e.g.,thelastk/2bits;theresultinghashfunctionisstillpreimageresistant.2023/1/1423RandomOracleModelManyprotocolsmakeuseofacryptographichashfunction.Inordertobeabletoproveanythingusefulonthesecurityofsuchprotocolsonecommonlyusestheso-calledrandomoraclemodel.Inthismodel,acryptographichashfunctionisviewedasarandomoracle,whichwhenqueriedwillbehaveasablackboxcontainingarandomfunctionh:{0,1}*{0,1}k,say.Iftheoracleisqueriedonaninputvaluex,itwillreturntheoutputvalueh(x).Asaconsequence,iftheoracleisqueriedmultipletimesonthesameinput,itwillreturnthesameoutputvalue,ashisafunction.Moreover,ifoneobservesthedistributionoftheoutputvaluefordifferentinputvalues,thedistributionwillbeuniform,ashisarandom.2023/1/1424RandomOracleModelNotethattheuseoftherandomoraclemodelisaheuristic!Ifweproveaprotocolsecureintherandomoraclemodel,itdoesnotfollowthatthesameprotocolusing,e.g.,SHA-1asitshashfunctionissecure,sinceSHA-1issimplynotarandomfunction.Thus,thepracticalupshotoftherandomoraclemodelisthataprotocolprovedsecureinitcanonlybebrokeniftheattackertakesintoaccountspecificpropertiesoftheconcretehashfunctionused.2023/1/1425RandomOracleModelProposition:LetHbeacryptographichashfunction,whichweviewasarandomoracle.LetAbeanadversarythatmakesatmostthashqueries.LetyR{0,1}kbegiven.TheprobabilitythatAfindsapreimagexsuchthatH(x)=yisatmostt/2k.LetxR{0,1}andy=H(x)begiven.TheprobabilitythatAfindsasecondpreimagex’,x’x,suchthatH(x’)=yisatmostt/2k.TheprobabilitythatAfindspreimagesx,x’,x’x,suchthatH(x)=H(x’)isatmostt2/2k.2023/1/14262023/1/1427Diffie-HellmanKeyExchangeSupposetwoparties,AandB,haveagreeduponagroupGn=<g>,wherewerequirentobeprime.TheDiffie-HellmankeyexchangeprotocolenablespartiesAandBtoarriveatasharedkeyKbyexchangingmessagesoverapublicchannel.KeyKremainsunknowntoanyeavesdropper.PartyApicksavaluexA

Znuniformlyatrandom,andsendsyA=gxAtopartyB.Similarly,partyBpicksavaluexB

Znuniformlyatrandom,andsendsyB=gxBtopartyA.UponreceiptofyB,partyAcomputeskeyKAB

yBxA.Similarly,partyBcomputeskeyKBA

yAxB.Clearly,K=KAB=KBAisasharedkeyforAandB2023/1/1428Diffie-HellmanKeyExchangeDiscussionNoentityauthentication.Secureagainstpassiveadversaries(eavesdroppers).Man-in-the-middleattackexists.2023/1/1429Diffie-HellmanKeyExchange2023/1/1430PassiveAttacksApassiveattacker(oreavesdropper)learnsthevaluesyA=gxAandyB=gxB.UndertheDLassumptionitisinfeasibletodeterminexAandxBfromyAandyB.However,thisdoesnotguaranteethatthevalueofK=yAxBcannotbedeterminedgivenjustyAandyB.ToexcludethispossibilityweneedtheDHassumption.AstrongerassumptionisneededtoensurethataneavesdropperdoesnotlearnanyinformationwhatsoeveronK.Ingeneral,aneavesdroppermaylearnsomepartialinformationonK,whilefullrecoveryofKisinfeasible.2023/1/1431PassiveAttacksForexample,aneavesdroppermightbeabletodeterminetheparityofK,viewingKasaninteger,whichwouldmeanthattheeavesdropperlearnsonebitofinformation.ToexcludesuchpossibilitiesweneedtheDDHassumption.Wewillnowmakethismoreprecise.Firstwearguewhyweneedtorequirethatnisprime.Supposenisnotprime,sayn=2p’,wherep’isprime.ForanyelementyG,wehaveord(y){1,2,p’,2p’}andord(y)iseasilycomputed.Wehavethefollowingtable,whereeachcaseoccursapproximatelywithprobability1/4:2023/1/1432PassiveAttacksHence,theorderofthekeyKisbiased,asPr[ord(K)=p’]3/4andPr[ord(K)=2p’]1/4.IfKwouldbegenerateduniformlyatrandominG,thenwewouldhavePr[ord(K)=p’]Pr[ord(K)=2p’]1/2.SuchaslightdeviationinthedistributionofKseemsinnocent.However,supposekeyKisusedtoencrypta1-bitmessage,saymR{1,g},usingc=mKasciphertext(liketheone-timepadconstruction).Inthatcase,aneavesdropperwouldcomputeord(c).Iford(c)=pthenmostlikelym=1,andiford(c)=2pthenmostlikelym=g.2023/1/1433PassiveAttacksExercise:ArguethattheDDHassumptionisfalsewhenncontainsasmallprimefactor.2023/1/1434PassiveAttacksSo,assumethatnisprime.BTW,ifaneavesdropperwouldbeabletodetermineanypartialinformationonkeyK,thenwewouldgetacontradictionwiththeDDHassumption.2023/1/1435APracticalVariantWenowconsidertheDiffie-Hellmanprotocolasabove,exceptthatthekeyKisdefinedasfollows:

K=H(gxAxB),whereHisacryptographichashfunction.Clearly,bothpartiesarestillabletocomputeKbyfirstcomputinggxyandthenapplyingH.ApracticalchoiceforHisthestandardizedSHA-1hashfunction.2023/1/1436APracticalVariantThereasonforusingahashfunctionHisthateventhoughgxAxBwillhaveasufficientamountofentropy,itcannotbesimplyusedasanAESkey,forexample.ThevalueofgxAxBwillbeuniformlydistributedamongthegroupelementsinG\{1},butusuallyaredundantrepresentationisusedforthegroupelements.Forexample,ifGisasubgroupofZp,thenelementsofGareusuallyrepresentedasbitstringsoflength[log2p],whiletheorderofGcanbemuchsmallerthanp.Theuseofacryptographichashfunctionisapracticalwaytoremovethisredundancy.Theresultwillbeafullyrandombitstringaslongastheorderofthegroupnexceeds2k,wherekdenotestheoutputlengthofH,i.e.,H:{0,1}*

{0,1}k.2023/1/1437APracticalVariantWenowconcludethattheresultingprotocolissecureagainstpassiveattacks,assumingtheDHassumptionandtheRandomOraclemodel.2023/1/1438Aside:ElGamalEncryptionRecallthattheElGamalcryptosystemisdefinedasfollows,givenasecurityparameterk.Notethatkeygenerationandencryptionarerandomized,whiledecryptionisdeterministic.Inpractice,thegroup<g>maybesharedbetweenmanyusers.2023/1/1439AuthenticatedKeyExchangeUndertheDDHassumption,theDiffie-Hellmanprotocolissecureagainstpassiveattackers.Againstactiveattackers,however,theprotocoliscompletelyinsecure.WhileapassiveattackerisrestrictedtoeavesdroppingonthecommunicationbetweenAandB,anactiveattackerisallowedtomanipulatethemessagesexchangedbetweenAandBatitsownliking.Thatis,anattackermaydelete,inject,andmodifymessages.Inthecontextofkeyexchangeprotocols,themostprominenttypeofactiveattackisaso-calledman-in-the-middleattack.Here,theideaisthatwhenAandBengage,say,inanexecutionoftheDiffie-Hellmanprotocol,theattackerwillreplacethevaluesyAandyBbyvaluesy’Aandy’Bofitsownchoice,respectively.Below,weconsiderafewexamples.2023/1/1440Man-in-the-MiddleAttacks2023/1/1441Man-in-the-MiddleAttacks2023/1/1442AProtocolUsingDigitalSignaturesTheDiffie-Hellmanprotocolonlywithstandspassiveattacks.Afirst,butgeneral,ideatoobtainakeyexchangeprotocolwithstandingactiveattacksistoauthenticatethecommunicationbetweenAandB.Forinstance,wemayassumethatAandBknoweachother’spublickeysinadigitalsignaturescheme.2023/1/1443AProtocolUsingDigitalSignaturesThereismanysolutionstothisproblem,butonlyafewhavebeenprovedcorrect.Wewillnotgiveaformalsecurityanalysisatthispoint.Theprotocolisasfollows.PartyApicksxA

Znuniformlyatrandom,andsendsyA=gxAalongwithasignatureon(yA,B)topartyB.Similarly,partyBpicksxB

Znuniformlyatrandom,andreplieswithyB=gxBalongwithasignatureon(yA,yB,A)topartyA.Asbefore,theagreeduponkeyisK=gxAxB.AprotocolofthistypeissecureundertheDDHassumption,alsoassumingthatthedigitalsignatureschemeissecure.2023/1/1444I