deterministiccjblaze

AnextendedabstractofthispaperappearsinNinthACMConferenceonComputerandCommu-nicationsSecurity,ACM,2002.
Thisisthefullversion.
AuthenticatedEncryptioninSSH:ProvablyFixingtheSSHBinaryPacketProtocolMihirBellareTadayoshiKohnoChanathipNamprempreSeptember2002AbstractTheSecureShell(SSH)protocolisoneofthemostpopularcryptographicprotocolsontheInternet.
Unfortunately,thecurrentSSHauthenticatedencryptionmechanismisinsecure.
InthispaperweproposeseveralxestotheSSHprotocoland,usingtechniquesfrommoderncryptography,weprovethatourmodiedversionsofSSHmeetstrongnewchosen-ciphertextprivacyandintegrityrequirements.
Furthermore,ourproposedxeswillrequirerelativelylittlemodicationtotheSSHprotocolortoSSHimplementations.
Webelievethatournewnotionsofprivacyandintegrityforencryptionschemeswithstatefuldecryptionalgorithmswillbeofindependentinterest.
Keywords:AuthenticatedEncryption,SecureShell,SSH,StatefulDecryption,SecurityProofs.
Dept.
ofComputerScience&Engineering,UniversityofCalifornia,SanDiego,9500GilmanDrive,LaJolla,California92093,USA.
E-Mail:mihir@cs.
ucsd.
edu.
URL:http://www-cse.
ucsd.
edu/users/mihir.
SupportedinpartbyNSFGrantCCR-0098123,NSFGrantANR-0129617andanIBMFacultyPartnershipDevelopmentAward.
.
Dept.
ofComputerScience&Engineering,UniversityofCalifornia,SanDiego,9500GilmanDrive,LaJolla,California92093,USA.
E-mail:tkohno@cs.
ucsd.
edu.
URL:http://www-cse.
ucsd.
edu/users/tkohno.
SupportedbyaNationalDefenseScienceandEngineeringGraduateFellowship.
Dept.
ofComputerScience&Engineering,UniversityofCalifornia,SanDiego,9500GilmanDrive,LaJolla,California92093,USA.
E-mail:meaw@cs.
ucsd.
edu.
URL:http://www-cse.
ucsd.
edu/users/cnamprem.
Supportedinpartbygrantsofrstauthor.
.
1Contents1Introduction32TheSSHBinaryPacketProtocol53AttackAgainsttheStandardImplementationofSSH64AttacksAgainstaNatural"Fix"65SecureFixestoSSH96ProvableSecurityResults106.
1Denitions116.
2SecurityNotions126.
3SSHSecurityResults147DiscussionandRecommendations17AFormalNotionsofSecurity21BGeneralSecurityResultsfortheEncode-then-E&MParadigm24B.
1Chosen-PlaintextPrivacy(ProofofLemma6.
4)24B.
2IntegrityofPlaintexts28B.
3ObtainingChosen-CiphertextPrivacy(ProofofProposition6.
2)29CSSHProofs29C.
1ProofofLemma6.
329C.
2ProofofTheorem6.
53021IntroductionConceivedasasecurealternativetotraditionalUnixtoolslikershandrcp[27],theIETFstan-dardizationbody'sSecureShell(SSH)protocol[17]1hasbecomeoneofthemostpopularandwidelyusedcryptographicprotocolsontheInternet.
Becauseofitspopularityandbecauseoftheinsecurityofprogramslikershandtelnet,anumberofinstitutionsonlyallowuserstoremotelyaccesstheirfacilitiesusingSSH.
ThecryptographicheartoftheSSHprotocolisitsBinaryPacketProtocol(BPP)[28];theBPPisresponsiblefortheunderlyingsymmetricencryptionandauthen-tication(ortheauthenticatedencryption)ofallmessagessentbetweentwopartiesinvolvedinanSSHconnection.
AlthoughothershavediscussedspecicpropertiesoftheSSHBPP(e.
g.
,problemswithnotusingaMAC[26]orproblemswithSSH'suseofCBCmode[10]),tothebestofourknowledgenoonehasperformedarigorous,provablesecurity-basedanalysisoftheentireSSHBPPauthenticatedencryptionmechanism.
OurgoalwasthustothoroughlyanalyzetheSSHBPPauthenticatedencryptionschemeand,intheeventthatwefoundanyproblems,topresentprovably-securexestotheprotocol.
InorderforourxestobeasusefulaspossibletotheInternetcommunity,whendevelopingourxesweconsideredboth(1)provablesecurityand(2)eciency.
Additionally,sinceretroac-tivelymodifyingexistingimplementationsisoftenveryexpensive,werequiredthatoursuggestedmodications(3)notsignicantlyalterthecurrentSSHspecication.
Forthelastpoint,wenotethatthecreatorsofSSHhadtheforesighttodesigntheSSHBPPinamodularway:inparticular,itisrelatively"easy"tochangetheSSHBPP'sunderlyingencryptionandmessageauthenticationmodules.
Analysisandprovablysecurerecommendations.
TheSSHBPPspecicationstatesthatSSHimplementationsshoulduseCBCmodeencryption[11]withchainedinitializationvectors(IVs);i.
e.
,theIVusedwhenencryptingamessageshouldbethelastblockofthepreviouscipher-text.
Unfortunately,CBCmodeencryptionwithchainedIVsisinsecure[23],andthisinsecurityextendstoSSH(thisextensionwasalsoreportedbyDai[10]).
SinceCBCmodeencryptionwithchainedIVsisinsecure,butCBCmodewithrandomIVsisprovablysecureagainstchosen-plaintextattacks[2],anaturalxtotheSSHprotocolmightbetoreplacetheuseofchained-IVCBCmodewithrandomizedCBCmode.
Unfortunately,weshowthatdoingsoisnotsucient.
Inparticular,sincetheSSHspecicationdoesnotrequirethepaddingtoberandom,theresultingSSHimplementationmaybevulnerabletoaratherseriousreaction-attack(aprivacyattackthatworksbymodifyingasender'sciphertextsandobservingthereceiver'sresponse).
WenextpresentseveralsecurexestotheSSHauthenticatedencryptionmechanism.
Forex-ample,wesuggestusingrandomizedCBCmodeencryption;thedierencebetweenthissuggestionandthesuggestionintheaboveparagraphisthatwerequireatleastonefullblockofrandompadding(thiscould,however,resultinhavingtoenciphermoreblocksthanthepreviousSSHal-ternative).
WealsosuggestanotherCBCvariantthatdoesnotrequireadditionalrandompadding:CBCmodewheretheIVisgeneratedbyencryptingacounterwithadierentkey.
Asanaddi-tionalalternative,wesuggestreplacingtheunderlyingencryptionschemewithavariantofcounter(CTR)mode[12,22]inwhichboththesenderandreceivermaintainacopyofthecounter.
Wealsopresentaframeworkwithinwhichtoanalyzeotherpossiblereplacements.
OneimportantadvantageofthesexesoverthecurrentSSHspecicationisprovablesecurity.
Makingreasonableassumptions(e.
g.
,thatSSH'sunderlyingblockcipherissecure),weareable1SSHversion1.
5[27]andSSHversion2.
0[17]areverydierent(e.
g.
,version1.
5uses32-bitCRCsforauthenticity).
WefocusouranalysisonSSHversion2.
0.
3toshowthatouralternativeswillpreserveprivacyagainstadaptivechosen-plaintextandadaptivechosen-ciphertextattacks.
Wealsoshowthatouralternativeswillresistforgery,replay,andout-of-orderdeliveryattacks.
Finally,wearguethatouralternatives,andespeciallythelattertwo,alsosatisfytheothertworequirementslistedabove(eciencyandeaseofmodication).
(WenotethatourCTRmodeconstructionaddressestheconcernswithCTRmoderaisedin[7].
)Theoreticalcontributions.
Thepreviousnotionsofprivacy[2]andintegrity[19,4]forauthen-ticatedencryptionschemesonlyaddressencryptionschemeswithstatelessdecryptionalgorithms.
TheSSHBPPdecryptionalgorithmis,however,stateful.
MotivatedbyadesiretoanalyzetheSSHBPPauthenticatedencryptionscheme,andbythedesiretocapturethepotential"power"ofstatefuldecryptionalgorithms,weextendthepreviousnotionsofprivacyandintegritytoen-cryptionschemeswithstatefuldecryptionalgorithms.
Theaforementioned"power"referstothefactthatifaschememeetsournewnotionsofsecurity,then,inadditiontosatisfyingtheexistingnotionsofprivacy[2]andintegrity[19,4],theschemewillbesecureagainstreplayattacksandout-of-orderdeliveryattacks—attacksnotcapturedunderthepreviousmodels.
OnealternativeapproachtoouranalysiswouldhavebeentomodeltheSSHBPPasa"securechannel"[9]sincethenotionofsecurechannelscanbeappliedtoencryptionschemeswithstatefuldecryptionalgorithms.
Wepointoutthatthecombinationofournotionsisstrongerthanthenotionofsecurechannels:combiningasecurekeyagreementprotocolwithanauthenticatedencryptionschemethatmeetsbothofournotionswillyieldasecurechannel.
Consequently,sinceourxestotheSSHBPPprovablymeetourstrongnotions,theresultingSSHBPPisalsoasecurechannel.
Weacknowledgethatonepotentialdisadvantageofournewnotionsofsecurityisthattheymaybe"toostrong"forsomeapplications:someapplicationsmaynotrequirethestrengthassociatedwithournotions(see[9,20]forreasons).
Forthoseapplications,thenotionofasecurechannelmightbemoreappropriate.
Ournotionsare,however,moreappropriateforapplications(likeSSH)thatdorequireahigherlevelofprotectionsuchasprotectionagainstout-of-orderdeliveryattacks.
Finally,wenotethatside-channelattacks(suchasthoseexploitinginformationleakedthroughthelengthofpacketsortheintervaloftimebetweenpackets[25])arenotcapturedbyoursecuritymodelsnoranyotherprovablesecuritymodelsthatweareawareof.
Overview.
AfterdescribingtheSSHBinaryPacketProtocolinSection2,wepresentasimpleattackagainstthecurrentSSHspecication(Section3).
InSection4weshowthat"xing"theSSHBPPinthenaturalwaymayresultinaninsecureprotocol.
MotivatedbythelessonswelearnedfromSections3and4,wethenpresentprovably-securexestotheSSHBinaryPacketProtocol(Section5).
InSection6wepresentourprovablesecurityresultsinmoredetail(deferringthedetailsoftheproofstotheappendices).
Finally,inSection7wediscussourresultsandmakerecommendationstotheSSHandappliedcryptographiccommunities.
Wediscussthesignicanceofourearlierattacksandtheadvantagesanddisadvantagesofswitchingtoourproposedmodications.
WealsodiscussthepossibilityofchangingtheSSHBPPfroman"Encrypt-and-MAC-based"constructiontoan"Encrypt-then-MAC-based"constructionandthepossibilityofmodifyingSSHtouseadedicatedauthenticatedencryptionschemesuchasXCBC[13]orOCB[24].
Backgroundandrelatedwork.
Anauthenticatedencryptionschemeisaschemedesignedtoprovidebothprivacyandintegrity.
FromanAPIperspective,asymmetricauthenticateden-cryptionschemeisequivalenttoanencryptionschemeexceptthatthedecryptionalgorithmcanreturnaspecialerrorcode.
Therearetwotypesofauthenticatedencryptionschemes:dedicatedconstructions(e.
g.
,RPC[19],XCBC[13],IACBC[18],andOCB[24])andgenericcompositioncon-structions,sonamedbecausetheyusestandardencryptionandmessageauthenticationschemesas"blackboxes.
"Analysisofthelatterclasswasinitiatedin[4,20].
TheschemesofSSH,SSLandIPSECfallinthisclass.
Theideaofmodelingdataformatsviaencodingschemesthatweuse4payloadpayloadlenpdlpaddingctrpayloadENCODEintermediateciphertextMACtagENCRYPTMACENCODEENCRYPTMACciphertextpacketFigure1:TheSSHauthenticatedencryptionscheme.
SeeSection2fordetails.
herewasintroducedin[5].
Anet.
al.
[1]considergenericcompositionintheasymmetricsettingandinparticularobtainresultsaboutthesecurityofthetransformwhichsplitsamessageintotwosub-messagesviaacommitmentscheme,signsoneofthesub-messagesandencryptstheother.
2TheSSHBinaryPacketProtocolTheSSHBinaryPacketProtocol[28]isresponsibleforencryptingandauthenticatingallmessagesbetweentwopartiesinvolvedinanSSHsession.
BeforebeginningtheauthenticatedencryptionportionofanSSHsession,aclientandaserverrstagreeuponasetofsharedsymmetrickeys(adierentsetforeachdirectionofaconnection).
Theclientandtheserveralsoagreeuponwhichencryptionandmessageauthenticationschemestheywishtouse.
Alloftheencryptionschemesrecommendedby[28]arebasedonCBCmodeencryption[11],andalloftherecommendedmessageauthenticationschemesarebasedonHMAC[21].
TheSSHauthenticatedencryptionschemeworksasshowninFigure1.
Givenapayloadmessage(inbytes),theSSHBPPencodesthatmessageintoanencodedpacketconsistingofthefollowingelds:afour-bytepacketlengtheldcontainingthelengthoftheremainingencodedpacket(inbytes),aone-bytepaddinglengtheld,thepayloadmessage,and(possiblyrandom)padding.
Thelengthofthetotalpacketmustbeamultipleoftheunderlyingblockcipher'sblocklength,andthepaddingmustbeatleastfourbyteslong.
AlthoughtheSSHspecicationallowsupto255bytesofpaddingperencodedpacket,bothimplementationsthatweevaluated(openssh-2.
9p2andSSHCommunications'ssh-3.
0.
1)usetheminimumpaddingnecessary.
TheresultingciphertextistheconcatenationoftheencryptionoftheaboveencodedpacketandtheMACoftheaboveencodedpacketprependedwitha32-bitcounter.
Inthefollowingdiscussionswetrytomakeclearwhetherwearereferringtotheintermediateciphertextoutputbytheunderlyingencryptionschemeortheciphertextpacket(theconcatenationoftheintermediateciphertextandtheMACtag)outputby5theSSHBPP.
Decryptionisdenedinanaturalway:thereceiverrstdecryptstheintermediateciphertextportionofaciphertexttogetanencodedpacket.
Thereceiverthenprependsa32-bitcounter(whichitalsomaintains)totheencodedpacketanddetermineswhetherthereceivedMACtagisvalid.
Ifso,thedecryptorremovesthepayloadfromtheencodedpacketanddeliversthepayloadtotheuser(orahigher-levelprotocol).
IftheMACvericationfails,theconnectionisterminated.
TheSSHspecicationrecommendstheuseofCBCmodewithinter-packetchaining.
Thismeansthat,whenencryptinganencodedpayload,thesenderusesastheinitializationvector(IV)eitherthelastblockoftheimmediatelyprecedingciphertextor,whenencryptingtherstmessage,anIVcomputedduringtheSSHkeyagreementprotocol.
WerefertothecurrentinstantiationoftheSSHprotocolasSSH-IPC,orSSHwithinter-packetchaining.
3AttackAgainsttheStandardImplementationofSSHThereisasimpleattackagainstSSH-IPC;thisattackwasalsorecentlyreportedbyDai[10].
TheproblemwithSSH-IPCisthatanattackerwillknowtheIVforthenextmessagetobeencryptedbeforethenextmessageisactuallyencrypted.
ThismeansthatifanattackercancontroltheentirerstblockoftheinputintoSSH-IPC'sunderlyingCBCencryptionscheme,itwillbeabletocontrolthecorrespondinginputtotheunderlyingblockcipher.
Sinceablockcipherisdeterministic,anattackercouldusethistogleaninformationaboutapreviouslyencryptedmessage(bylookingtoseeifsomevaluewasevertheinputtoapreviousblockcipherinvocation).
Wedescribetheattackinslightlymoredetail.
Weassumefornowthatanadversarycancontroltheentirerstblockofanencodedpacket.
SupposethatanadversaryhasaguessGoftherstencodedblockoftheithpacket,andletC1bethelastCBCblockofthei1stintermediateciphertext.
SinceweareconsideringSSH-IPC,theblockC1wasusedastheIVwhenencryptingtheithpacket.
LetC2betherstblockoftheithciphertext.
AndletC3bethelastCBCblockoftheunderlyingciphertexttheuserjustoutput(i.
e.
,theuserwilluseC3asitsnextIV).
IftheadversaryisabletoforcetheusertoencrypttheblockC1C3G,whereisthexoroperation,andiftheresultingblockisC2,theadversaryknowsitsguessofforGwascorrect;otherwisetheadversaryknowsitsguesswasincorrect.
AsmallcomplicationariseswhenmountingthisattackagainstSSH-IPCbecausetheattackercannotcontroltheentirerstblockofanencodedmessage(becausetherst40bitsofanencodedpacketcontainmetadata).
Thismeansthatanattackermaynotbeabletoforceauser'sunderlyingCBCschemetoencrypttheblockC1C3G.
Anattackerwill,however,beabletomountthisattackifC1andC3areidenticalinthebitsthattheattackercannotcontrol.
Letlbetheblocklength(inbits)oftheunderlyingblockcipher.
Sinceanattackercancontrolapproximatelylg(l/8)bitsofthepaddinglengtheldandapproximately15lg(l/8)bitsofthepacketlengtheldofanencodedmessage(SSHimplementationsareonlyrequiredtosupportpacketswithpayloadscontaininglessthan215bytesandallpacketsmustbepaddedtoamultipleoftheblocklength),anattackercouldmountavariantoftheaboveattackbywaitingforacollisiononapproximately25bits(buttheadversary'slastencryptionrequestmaybeupto215byteslong).
4AttacksAgainstaNatural"Fix"TheproblemwithSSH-IPCstemsfromthefactthatitsunderlyingencryptionschemeisitselfvulnerabletochosen-plaintextattacks.
AlogicalxmightthereforebetoreplacetheunderlyingencryptionschemewithrandomizedCBCmode(i.
e.
,CBCmodeinwhichanewrandomIVis6chosenforeachmessage;thisnewIVmustalsobesentwiththeciphertext).
RandomizedCBCmodewasproventoresistchosen-plaintextattacksin[2].
WerefertoanSSHimplementationthatusesrandomizedCBCmodeasSSH-NPC,orSSHwithnopacketchaining.
ItispossibletoprovethatSSH-NPCpreservesprivacyagainstchosen-plaintextattacksandintegrityunderanotioncalled"integrityofplaintexts"providedthatauserdoesnotuseSSH-NPCtoencryptmorethan232messageswithanygivenkey.
Thisproofholdsevenifthepaddingsusedinencodedpacketsarenotrandom(whichisallowedbytheSSHspecication).
Asthefollowingattackshows,however,eventhoughSSH-NPCwithnon-randompaddingpreservesprivacyagainstchosen-plaintextsattacks,itdoesnotpreserveprivacyagainstchosen-ciphertextattacks.
ReactionattackagainstSSH-NPC.
TheSSHspecicationencourages,althoughdoesnotrequire,implementationstouserandompadding.
Unfortunately,whenthepaddingvalueisxed(e.
g.
,allzeros),SSH-NPCissusceptibletoaneasily-mountablereactionattack.
Furthermore,thisattackcanbemadetoworkevenwhenthepaddingvaluesarenotxedbutshortandnothardtopredict:anattackercansimplywaituntilthepredictedpaddingvaluescollideandthenusethepredictedvaluetosuccessfullymountanattack.
TheattackwedescribehereissimilarinspirittoWagner'sattackin[6]andtotheattacksin[20,26](theterm"reactionattack"comesfrom[16]).
Theattackproceedsroughlyasfollows:anattackerintercepts(andpreventsthedeliveryof)twociphertextssentbyonepartyinvolvedinanSSHconnection.
Theadversarythenmakesaguessabouttherelationshipbetweenthetwoplaintextscorrespondingtothetwointerceptedciphertexts.
Theadversarythenusesthatguessandthosetwociphertextstocreateanew"ciphertext,"whichtheadversarythensendstotheotherpartyinvolvedintheSSHsession.
Byobservingthesec-ondparty'sreaction(recallthatifthesecondpartydoesnotacceptthedoctoredciphertext,theconnectionwillbeterminated),anadversarywilllearnwhetheritsguesswascorrect.
Intuitively,thisattackworksbecauseanattackercanmodifytheciphertextinsuchawaythatifitsguesswascorrect,theciphertextthatthesecondpartyreceiveswillverify.
Ifitsguesswasincorrect,withhighprobabilitytheciphertextwillnotverify.
Wenowdescribetheattackinmoredetail.
Asbefore,letdenotethexoroperation,letdenotetheconcatenationoftwostrings,andletldenotetheblocklength(inbits)oftheblockcipherthatSSH-NPCusesinCBCmode.
SupposeauserusesSSH-NPCtoencrypttwoequal-lengthmessagesM1andM2withlengthsatmostl40(orthatareidenticalaftertheirl40-thbit).
(Forsimplicityofexposition,assumethatthetwomessagesareexactlyl40bitslong.
)LetP11andP12betherstandthesecondblockoftheencodedpacketcorrespondingtothepayloadM1,respectively.
Similarly,letP21andP22betherstandthesecondblockoftheencodedpacketscorrespondingtoM2,respectively.
TheblocksP11andP21correspondtothepacketlength,thepaddinglength,andthepayloadeldsofthetwoencodedpackets,andtheblocksP12andP22correspondtothepaddingelds.
Sinceweareassumingxedpadding(suchaspaddingwithallzeros),thepaddingblocksP12andP22willbeequal.
WhenSSH-NPC'sunderlyingCBCmodeencryptionschemeencryptstherstencodedpacketP11P12,itwillgenerateaciphertextσ1=C10C11C12;SSH-NPC'sunderlyingMACwillalsogenerateatagτ1(theMACbeingcomputedovertheconcatenationofacounterandP11P12).
Similarly,SSH-NPCwillgeneratetheCBCciphertextC20C21C22andtheMACtagτ2fortheencodedpacketP21P22.
(ThetwoblocksC10andC20correspondtotheunderlyingCBCmode'srandominitializationvectors.
)NowassumethatthereceiverhasnotyetreceivedthetwociphertextscorrespondingtoM1andM2(i.
e.
,therecipient'scounterisidenticaltothecounterthatthesenderusedwhensheencryptedtherstmessage).
AssumethattheattackerknowseitherM1orM2andwantstoverifyaguessoftheother(orthattheattackerwantstoverifyaguessoftherelationshipbetweenM1andM2).
LetXbethevalueP11P21C20(recallthattheblocksP11andP12bothbeginwiththesame40bits7ofheaderinformationandthattheyrespectivelyendinM1andM2).
TheattackerthenasksthereceivertodecryptthemessageXC21C22τ1.
Iftheattacker'sguessiscorrect,thenXC21C22willdecrypt,viaSSH-NPC'sunderlyingCBCscheme,toP11P12,theMACtagτ1willverify,andthedecryptorwillacceptthemessage.
Iftheattacker'sguessisincorrect,however,XC21C22willnotdecrypttoP11P12,thetagτ1willnotverify(unlesstheattackeralsosucceedsinbreakingthesecurityoftheunderlyingMACscheme),andtheSSH-NPCconnectionwillterminate.
Theadversary,bywatchingtherecipientsreaction,thereforelearnsinformationabouttheplaintextsthesenderisencrypting.
Therearetwoaspectsofthisattackthatmakeiteasytomount.
First,thisattackonlyrequiresmodifyingencryptedpackets;nochosen-plaintextsarerequired.
Second,anattackercanlearnwhetheritsguessiscorrectsimplybywatchingtherecipient'sresponse.
Theseobservationsmeanthatallanattackerneedstoperformthisattackistheabilitytomonitor,preventthedeliveryof,andinjectmessagesintheencryptedcommunicationsbetweentwoparties.
SimilartoWagner'sattackin[6],thisattackcanbeusedto(amongotherthings)inferthecharactersthatausertypesoveraninteractiveSSH-NPCsession.
Ofcourse,oncetheattackermakesanincorrectguess,SSH-NPCterminatestheconnection.
Nonetheless,anattackermightstillbeabletorepeatitsattackaftertheuserbeginsanewsession.
Informationleakage,replay,andout-of-orderdeliveryattacks.
AlthoughtheSSHdraftsuggeststhatanSSHsessionrekeyaftereverygigabyteoftransmitteddata,doingsoisnotrequired.
WecautionthatifanSSH-NPC(orSSH-IPC)sessionisnotrekeyedfrequentlyenough,thenthesessionwillbevulnerabletoanumberofotherattacks.
RecallthattheSSHbinarypacketprotocolincludesa32-bitcounterineachmessagetobeMACed.
TheseattacksmakeuseofthefactthatiftheSSHconnectionisnotrekeyedfrequentlyenough,thenthecounterwillbegintorepeat.
Thesimpleobservationexploitedbytheinformationleakageattackisthefollowing.
RecallthatSSHgenerateseachMACusingtheencodedpayloadprependedwithacounterasaninputandthenappendstheMACtotheintermediateciphertexttogenerateaciphertextpacket.
Asaresult,iftheunderlyingMACalgorithmisstatelessanddeterministic(whichmanyMACsare),thenallowingthecountertorepeatwillleakinformationaboutauser'splaintexts(throughtheMAC).
Wepresenttheattacksinmoredetailsforcompleteness.
Supposethattheunderlyingmessageauthenticationschemeisstatelessanddeterministicandthatthepaddingissomexedvalue.
SupposethatanattackerAseesaciphertextwithaMACtagτandsuspectsthattheunderlyingpayloadisM.
Toverifyitsguess,Awaitsforthesendertoencrypt2321morepacketsandthenrequeststhesendertoencryptthepayloadM.
LetτbetheMACtagreturnedinresponsetotherequest.
IfA'sguessiscorrect,thenτwillequalτ.
Otherwiseτ=τwithveryhighprobability.
TheattackcanalsobeusedtobreaktheprivacyofSSH-NPCwhenSSH-NPCusesrandompadding.
Inparticular,iftherst232messagesthatausertagsresultinencodedpacketsthatusetheminimum4bytesofrandompadding,thenanattackercapableofforcingausertotaganadditional232chosen-plaintextswillbeabletolearninformationabouttheuser'sinitial232messages.
Thepropertyusedinthisattack(thattaggingwithadeterministicMACleaksinformationaboutplaintexts)wasalsoexploitedby[4]and[20].
Ifthecounterisallowedtorepeat,SSH-NPCalsobecomesvulnerabletoreplayattacksandout-of-orderdeliveryattacks.
Forreplayattacks,oncethereceiverhasdecrypted232messages,anattackerwillbeabletoconvincethereceivertore-acceptapreviouslyreceivedmessage.
Forout-of-orderdeliveryattacks,afterthesenderhasencryptedmorethat232messages,anattackerwillbeabletomodifytheorderinwhichthemessagesaredecrypted.
85SecureFixestoSSHWenowbrieydescribeournewSSHinstantiations.
WeshowinSection6thatthesenewal-ternativesprovablymeetourstrongestnotionsofsecurity.
Thatis,assumingthatthesexesarenotusedtoencryptmorethan232packetsbetweenrekeying,thesenewconstructionswillresistchosen-plaintextandchosen-ciphertextprivacyattacksaswellasforgery,replay,andout-of-orderdeliveryattacks.
Securityabove232isnotguaranteedbecause,after232packetsareencrypted,theSSHBPP's32-bitinternalcounterwillbegintowrap.
WewillcomparetheseinstantiationsofSSHtoothersanddiscussadditionalpossiblemodications,includingextendingthelengthofSSH'sinternalcounter,inSection7.
SSHviarandomizedCBCmodewithrandompadding:SSH-$NPC.
RecallthattheattackagainstSSH-NPCinvolvescreatinganewintermediateciphertextthatwoulddecrypttoanencodedpacketthattheuserpreviouslyencrypted(assumingtheattacker'sguesswascorrect).
Withthisinmind,weproposeaprovablysecureSSHinstantiation(SSH-$NPC)thatusesrandomizedCBCmodefortheunderlyingencryptionschemeandthatrequiresthatencodedpacketsuserandompadding.
Werequirethattherandompaddingbechosenanewforeachencryptionandthattherandompaddingoccupyatleastonefullblockoftheencodedpacket.
ThisconformstothecurrentSSHspecicationsincethelatterallowspaddingupto255bytes.
TheintuitionbehindthesecurityofthisalternativeandthereasonthatthisalternativeresiststheattackinSection4isthefollowing.
Sincetherandompaddingisnotsentintheclear,anattackerwillnotknowwhattherandompaddingisandwillnotbeabletoforgeaciphertextthatwilldecrypttothatpreviouslyencodedmessage(withthesamerandompadding).
Furthermore,anyotherattackagainstSSH-$NPCwouldtranslateintoanattackagainsttheunderlyingCBCmodeencryptionscheme,theunderlyingMAC,theencodingscheme,ortheunderlyingblockcipher.
SSHviaCBCmodewithCTRgeneratedIVs:SSH-CTRIV-CBC.
InsteadofusingCBCmodewitharandomIV,itisalsopossibletogeneratea"random-looking"IVbyencryptingacounterwithadierentkey;wecallthisalternativeSSH-CTRIV-CBC.
UnlikeSSH-$NPC,forSSH-CTRIV-CBCwedonotrequireafullblockofpaddingandwedonotrequirethepaddingtoberandom.
ThereasonwedonotrequirerandompaddingforthisalternativeisbecausethedecryptorisstatefulandthatanymodicationtoanunderlyingCBCciphertextwill,withprobability1,changetheencodedpacket.
ThisalternativeismoreattractivethanSSH-$NPCbecauseitdoesnotincreasethesizeofciphertextscomparedtoSSH-IPC(butitdoesrequireoneadditionalblockcipherapplicationcomparedtoSSH-IPC).
SSHviaCTRmodewithstatefuldecryption:SSH-CTR.
SSH-CTRusesstandardCTRmodeastheunderlyingencryptionschemewithonemodication:boththesenderandthereceivermaintainthecountersthemselves,ratherthantransmittingthemaspartoftheciphertexts.
WerefertothisvariantofCTRmodeasCTRmodewithstatefuldecryption.
WepointoutthatthisCTRmodevariantoersthesamelevelofchosen-plaintextprivacyasstandardCTRmode,thesecurityofwhichwasshownin[2].
AswithSSH-CTRIV-CBC,SSH-CTRdoesnotrequireadditionalpaddinganddoesnotrequirethepaddingtoberandom.
Furthermore,unlikeSSH-$NPCandSSH-CTRIV-CBC,SSH-CTRrequiresthesamenumberofblockcipherinvocationsasSSH-IPC.
Otherpossibilities.
TherearenumerousotherpossiblexestotheSSHBPP.
RatherthanenumerateallpossiblexestotheSSHBPP,inSection6wediscusshowonecanuseourgeneralprooftechniquestoprovethesecurityofotherxes(assuming,ofcourse,thattheotherxesareindeedsecure).
Forexample,anotherxofinterestmightbeSSH-EIV-CBC,orSSHwheretheunderlyingencryptionschemeisreplacedbyaCBCvariantinwhichtheIVistheencipherment9ofthelastblockofthepreviousciphertext.
6ProvableSecurityResultsPractice-orientedprovablesecurity.
ProvablesecuritywasrstintroducedbyGoldwasserandMicaliin[15].
Itencompassesboththedesignandtheanalysisofcryptographicconstructs.
Inthisapproach,onedesignsaconstructbasedoncomputationallyhardproblemssuchasfactoringlargecompositeintegers.
Thesehardproblemsaretreatedasatomicprimitiveswhosecompu-tationalhardnessthesecurityofthedesiredconstructisbasedupon.
Beforetheconstructcanbeanalyzed,however,onemustdeterminewhatitmeansforittobeconsidered"secure.
"Thisrequirespreciselydenedsecuritydenitionsandadversarymodels.
Theformershouldcapturethesecurityobjectivesthattheconstructistoachievewhilethelattershouldcapturethesettingsinwhichadversariesoperate.
Thegoalhereistocapturethesettingsinwhichtheconstructwillbedeployedinthereal-world.
Oncesecuritydenitionsandadversarymodelsaredetermined,one"proves"securityofthedesiredconstructviaareductionfromthehardnessoftheunderlyingprimitives,similartothewayonereducesSATtoaproblemtoprovethattheproblemisNP-complete.
Theterm"proves"isinquotesherebecause,ineect,onedoesnotprovethataconstructissecureinthisapproach.
Rather,oneprovidesareductionofthesecurityoftheconstructfromthatofitsunderlyingprimitives.
Thistechniqueallowsustoarriveatapowerfulconclusion:theonlywaytodefeatthedesiredconstructintheprescribedmodelsistobreaktheunderlyingprimitives.
Thus,aslongastheprimitivesareunbroken,weknowthattheconstructissecureundertheprescribedsecuritydenitionsandadversarymodels.
Ourapplicationofprovablesecurityinthispaperisalsopractice-orientedinthatweprovideconcreteboundsforourreductions.
Thisapproach,whichwasintroducedin[3],allowspractitionerstoquantitativelydeterminethesecurityoftheconstruct.
Forexample,theycanusethebest,currentlyknownattackagainsttheunderlyingprimitivessuchasAESandderivetheupperboundontheinsecurityoftheconstructinquestion.
Wenote,however,thatforsimplicitywedonotprovideexactboundsinthispaperbutsimplystateroughlyhowtheresourcesforbreakingtheconstructandthoseforbreakingtheunderlyingprimitivescompare.
Inmostcases,theyareequal.
Inothercases,theycanbeeasilydeterminedbylookingattheexpansionbetweenapayloadmessageanditsencodedpacket.
AnalyzingSSHviaanewparadigm.
AnSSHciphertextistheconcatenationoftheencryptionandtheMACof(someencodingsof)anunderlyingpayloadmessage.
Atrstglance,thisseemstofallintothe"Encrypt-and-MAC"methodofcomposinganencryptionschemewithaMACscheme:toencryptamessageM,applytheencryptionalgorithmtoMandthetaggenerationalgorithmtoM,thenconcatenatetheresultingstringstoproducethenalciphertexttobetransmitted.
Aspointedoutin[4,20],thisparticularcompositionmethodisnotgenericallysecure:securityunderstandardnotionsoftheencryptionandMACschemesusedasbuildingblocksunderthiscompositionmethodisnotenoughtoguaranteetheprivacyofthepayload.
Naturally,thisraisesaquestionregardingthesecurityofSSH.
Weshowherethat,withanappropriateencodingmethod,suchasthemethodusedinSSH,anEncode-then-E&Mschemecanactuallybemadesecure.
Infact,ouranalysismodelsSSHmoregenerallyasanauthenticatedencryptionschemeconstructedviaaparadigmwecallEncode-then-E&M:toencryptamessage,rstencodeit(asSSHdoes),thenencryptandMACtheencodedpackets.
OuranalysiswasdoneinageneralwayinordertoensurethatthatthedenitionsandtechniqueswedevelopedwillbeusefultotheevaluatorsofotherSSH-likeschemes.
10AsdescribedinSection2,anSSHBPPencodedmessage(forencryption)consistsofapacketlengtheld,apaddinglengtheld,payloaddata,andpadding.
Anencodedmessage(forMACing)isidenticaltoanencodedmessageforencryptionexceptthatitisprependedwitha32-bitcounter.
6.
1DenitionsNotation.
Ifxandyarestrings,then|x|denotesthelengthofxinbitsandxydenotestheirconcatenation.
Ifiisanon-negativeinteger,thenildenotestheunsignedl-bitbinaryrepresen-tationofi.
Theemptystringisdenotedε.
Whenwesayanalgorithmisstateful,wemeanthatitusesandupdatesitsstateandthattheentityexecutingitmaintainsthestatebetweeninvocations.
Letεdenotetheinitialstateofany(statefulorstateless)algorithm.
Iffisarandomized(resp.
,deterministic)algorithm,thenxR←f(y)(resp.
,x←f(y))denotestheprocessofrunningfoninputyandassigningtheresulttox.
IfAisaprogram,Axmeans"returnthevaluextoA.
"Encryptionschemeswithstatefuldecryption.
AsusualasymmetricencryptionschemeorauthenticatedencryptionschemeSE=(K,E,D)consistsofthreealgorithms.
TherandomizedkeygenerationalgorithmreturnsakeyK.
Theencryptionalgorithm,whichmaybebothrandomizedandstateful,takeskeyKandaplaintextandreturnsaciphertext.
MotivatedbySSH,thenovelfeaturehereisthatthedecryptionalgorithmmayalsobestateful(butnotrandomized);thedecryptionalgorithmtakeskeyKandaciphertextandreturnseitheraplaintextoraspecialsymbol⊥(indicatingfailure).
Considertheinteractionbetweenanencryptorandadecryptor.
If,atanypointintime,thesequenceofinputstothedecryptorisnotaprexofthesequenceofoutputsoftheencryptor,thenwesaythattheencryptionanddecryptionprocesseshavebecomeout-of-syncandrefertothedecryptioninputatthatpointintimeastherstout-of-syncinput.
Theusualcorrectnesscondition,whichsaidthatifCisproducedbyencryptingMunderKthendecryptingCunderKyieldsM,isreplacedwithalessstringentconditionrequiringonlythatdecryptionsucceedwhentheencryptionanddecryptionprocessesarein-sync.
Moreprecisely,thefollowingmustbetrueforanykeyKandplaintextsM1,M2,SupposethatbothEKandDKareintheirinitialstates.
Fori=1,2,letCi=EK(Mi)andletMi=DK(Ci).
ItmustbethatMi=Miforalli.
Messageauthenticationschemes.
AmessageauthenticationschemeorMACMA=(K,T,V)consistsofthreealgorithms.
TherandomizedkeygenerationalgorithmreturnsakeyK.
Thetag-gingalgorithm,whichmaybebothrandomizedandstateful,takeskeyKandaplaintextandreturnsatag.
ThedeterministicandstatelessvericationalgorithmtakeskeyK,aplaintext,andacandidatetagandreturnsabit.
ForanykeyKandmessageM,andforanyinternalstateofTK,werequirethatVK(M,TK(M))=1.
Encodingschemes.
An"encoding"isanunkeyedtransformation.
Weuseencodingstomodeltheprocessofloadingapayloadmessageintoapacketforencryptionandapacketformessageauthentication(recallthattheencodedpacketthattheSSHBPPencryptsisslightlydierentthantheencodedpacketthattheSSHBPPMACs).
Syntactically,anencodingschemeEC=(Enc,Dec)consistsofanencodingalgorithmandadecodingalgorithm.
TheencodingalgorithmEnc,whichmaybebothrandomizedandstateful,takesasinputamessageMandreturnsapairofmessages(Me,Mt).
ThedecodingalgorithmDec,whichmayalsobestatefulbutnotrandomized,takesasinputamessageMeandreturnsapairofmessages(M,Mt),or(⊥,⊥)onerror.
Thefollowingconsistencyrequirementmustbemet.
ConsideranytwomessagesM,Mwhere|M|=|M|.
Let(Me,Mt)R←Enc(M)forEncinsomestate,andlet(Me,Mt)R←Enc(M)forEncisinsome(possiblydierent)state.
Werequirethat|Me|=|Me|and|Mt|=|Mt|.
Furthermore,supposethatbothEncandDecareintheirinitialstates.
ForanysequenceofmessagesM1,M2,.
.
.
andfor11i=1,2,let(Mie,Mit)=Enc(Mi),andthenlet(mi,mit)=Dec(Mie).
WerequirethatMi=miandthatMit=mitforalli.
Encode-then-E&Mparadigm.
Nowconsideranencodingscheme,andlet(Me,Mt)betheencodingofsomemessageM.
TogenerateaciphertextforMusingtheEncode-then-E&Mcon-struction,themessageMeisencryptedwithanunderlyingencryptionscheme,themessageMtisMACedwithanunderlyingMACalgorithm,andtheresultingtwovalues(intermediateciphertextandMAC)areconcatenatedtoproducethenalciphertext.
Thecompositedecryptionprocedureissimilarexceptthewayerrors(e.
g.
,decodingproblemsortagvericationfailures)arehandled:inparticular,shouldthecompositedecryptionalgorithmenteranewstateorreturntoitspreviousstateWetaketheapproachusedinSSHwhereby,ifadecryptionfails,thecompositedecryptionalgorithmentersa"haltingstate.
"Thisapproachisperhapsthemostintuitivesince,upondetect-ingachosen-ciphertextattack,thedecryptionalgorithmpreventsallsubsequentciphertextsfrombeingdecrypted(ofcourse,thisalsomakesthedecryptorvulnerabletoadenial-of-service-typeattack).
Construction6.
1showstheEncode-then-E&Mcompositionmethodindetails.
Construction6.
1(Encode-then-E&M)LetEC=(Enc,Dec),SE=(Ke,E,D),andMA=(Kt,T,V)beencoding,encryption,andmessageauthenticationschemeswithcompatiblemessagespaces(theoutputsfromEncaresuitableinputstoEandT).
Letallstatesinitiallybeε.
WeassociatetotheseschemesacompositeEncode-then-E&MschemeSE=(K,E,D)asfollows:AlgorithmKKeR←Ke;KtR←KtReturnKe,KtAlgorithmEKe,Kt(M)(Me,Mt)R←Enc(M)σR←EKe(Me);τR←TKt(Mt)C←στReturnCAlgorithmDKe,Kt(C)Ifst=⊥thenreturn⊥IfcannotparseCthenst←⊥;return⊥ParseCasστ;Me←DKe(σ)IfMe=⊥thenst←⊥;return⊥(M,Mt)←Dec(Me)IfM=⊥thenst←⊥;return⊥v←VKt(Mt,τ)Ifv=0thenst←⊥;return⊥ReturnMAlthoughonlyDexplicitlymaintainsstateintheabovepseudocode,theunderlyingencoding,encryption,andMACschemesmayalsomaintainstate.
6.
2SecurityNotionsSincethegoalistomodelschemesbasedonblockciphersandcryptographichashfunctions,aconcretesecuritytreatmentisused.
Weassociatetoanyadversaryanumbercalledits"advantage"thatmeasuresitssuccessinbreakingagivenschemewithrespecttoagivensecuritynotion.
Thesmalleranadversary'sadvantageisagainstagivenscheme,thestrongerthatschemeiswithrespecttothatadversary.
Indiscussion,take"secure"tomeanthattheadvantageofanyadversarywith"practical"resourcesis"small.
"Webrieydescribethesecuritynotionshere.
AppendixApresentsthesenotionsinmoredetail.
Securitynotionsforencryptionschemeswithstatefuldecryption.
Asecureauthen-ticatedencryptionschemeSE=(K,E,D)isonethatpreservesbothprivacyandintegrity.
Thestandardnotionofindistinguishability(privacy)underchosen-plaintextattacks(ind-cpa)isasfol-lows[2]:weconsideragameinwhichanadversaryAisgivenaccesstoanleft-or-right-encryption(lr-encryption)oracleEK(LR(·,·,b)),forsomehiddenbitb,thatoninputtwoequallengthmessageM0,M1,returnsEK(Mb).
Afterperforminganumberoflr-encryptionqueries,theadversarymust12returnaguessforthebitb.
WedeneAdvind-cpaSE(A)astheprobabilitythatAreturns1whenb=1minustheprobabilitythatAreturns1whenb=0.
Forournotionofchosen-ciphertextprivacyforstatefuldecryption(ind-sfcca),weconsideragameinwhichanadversaryBisgivenaccesstoanlr-encryptionoracleEK(LR(·,·,b))andadecryptionoracleDK(·).
AslongasB'squeriestoDK(·)arein-syncwiththeresponsesfromEK(LR(·,·,b)),thedecryptionoracleperformsthedecryption(andupdatesitsinternalstate)butdoesnotreturnaresponsetoB.
OnceBmakesanout-of-syncquerytoDK(·),thedecryptionoraclereturnstheoutputofthedecryption.
WedeneAdvind-sfccaSE(B)astheprobabilitythatBreturns1whenb=1minustheprobabilitythatBreturns1whenb=0.
Thenewind-sfccanotionimpliesthepreviousnotionofindistinguishabilityunderchosen-ciphertextattacks(ind-cca[2]).
Notethat,withoutallowinganadversarytoquerythedecryptionoraclewithin-syncciphertexts(e.
g.
,inthestandardind-ccasetting),wewouldnotbeabletomodelattacksinwhichtheadversaryattacksastatefuldecryptorafterthelatterhaddecryptedanumberoflegitimateciphertexts(perhapsbecauseofsomeweaknessrelatedtothestateofthedecryptoratthattime).
Thestandardnotionforintegrityofplaintexts(int-ptxt)isasfollows[4]:weconsideragameinwhichanadversaryAisgivenaccesstoanencryptionoracleEK(·)andadecryption-vericationoracleDK(·).
OninputacandidateciphertextC,thedecryption-vericationoracleinvokesDK(C)andreturns1ifDK(C)=⊥and0otherwise.
WedeneAdvint-ptxtSE(A)astheprobabilitythatAcanndaciphertextCsuchthatDK(C)=1butthatthedecryptedvalueofC,i.
e.
DK(C),wasnotpreviouslyaquerytoEK(·).
Forournotionofintegrityofciphertextsforstatefuldecryption(int-sfctxt),weagainconsideragameinwhichanadversaryBisgivenaccesstothetwooraclesEK(·)andDK(·).
WedeneAdvint-sfctxtSE(B)astheprobabilitythatBcangenerateaciphertextCsuchthatDK(C)=1andCisanout-of-syncquery.
Thenewnotionofint-sfctxtimpliesthepreviousnotionofintegrityofciphertexts(int-ctxt[4])aswellassecurityagainstreplayandout-of-orderdeliveryattacks.
Thefollowingpropositionstatesthat,ifaschemeisindistinguishableunderchosen-plaintextsattacksandiftheschememeetsourstrongdenitionofintegrityofciphertexts,thentheschemewillmeetourstrongdenitionofindistinguishabilityunderchosen-ciphertextattacks.
TheproofappearsinAppendixB.
3.
Itissimilartotheresultsin[4]and[19]whichshowthatthestandardind-cpaandthestandardint-ctxtnotionimplythestandardind-ccanotion.
Proposition6.
2LetSE=(K,E,D)beasymmetricauthenticatedencryptionscheme.
Givenanyind-sfccaadversaryA,wecanconstructanint-sfctxtadversaryIandanind-cpaadversaryBsuchthatAdvind-sfccaSE(A)≤2·Advint-sfctxtSE(I)+Advind-cpaSE(B)andIandBusethesameresourcesasA.
UnforgeabilityofMACschemes.
WeconsiderasecureMACMA=(K,T,V)tobeonethatisstronglyunforgeableunderchosen-messageattacks[4].
WeconsideragameinwhichaforgerFisgivenaccesstoataggingoracleTK(·)andavericationoracleVK(·).
Theforgerisallowedarbitraryqueriestotheoraclesandwinsifitcanndapair(M,τ)suchthatVK(M,τ)=1butτwasneverreturnedbyTK(·)asatagforM.
WedenotetheadvantageofthisforgerasAdvuf-cmaMA(F).
Althoughthisnotionisingeneralstrongerthanthestandardnotionofunforgeability[3],wenotethatanypseudorandomfunctionisastronglyunforgeableMAC,andmostpracticalMACsseemtobestronglyunforgeable.
Pseudorandomfunctions.
Weformalizepseudorandomfunctionsandtheirsecurityfollowing[14,3].
SupposeFisafamilyoffunctionsfromsomemessagespaceMto{0,1}L,andletRandM→L13denotethefamilyofallfunctionsfromMto{0,1}L.
WedeneAdvprfF(D)astheadvantageofadistinguisherDindistinguishingarandominstanceofFfromarandominstanceofRandM→L.
Collisionresistanceofencodingschemes.
ThesecurityofacompositeEncode-then-E&Mconstructiondependsonpropertiesoftheunderlyingencoding,encryption,andMACschemes.
Inadditiontothestandardassumptionsofindistinguishabilityoftheencryptionschemeandunforge-abilityandpseudorandomnessoftheMACscheme,werequire"collisionresistance"oftheencodingscheme.
Wemotivatethisnotionasfollows.
ConsideranintegrityadversaryagainstacompositeEncode-then-E&Mscheme.
Iftheadversarycanndtwodierentmessagesthatencode(orde-code)tothesameinputfortheunderlyingMAC,thentheadversarymaybeabletocompromisetheintegrityofthecompositescheme.
Considernowanindistinguishabilityadversaryagainstthecompositescheme.
AslongastheadversarydoesnotgeneratetwoinputsfortheunderlyingMACthatcollide,theunderlyingMACshouldnotleakinformationabouttheplaintext.
Thefollowingdescribesthenotionsofcollisionresistanceforencodingschemes.
FormaldenitionsappearinAppendixA.
AnadversaryAmountinga"chosen-plaintextattack"againstanencodingschemeEC=(Enc,Dec)isgivenaccesstoanencodingoracleEnc(·).
IfAcanmaketheencodingoracleoutputtwopairsthatcollideontheirsecondcomponents(i.
e.
,theMt's),thenAwins.
WeallowAtorepeatedlyquerytheencodingoraclewiththesameinput.
Similarly,anadversaryBmountinga"chosen-ciphertextattack"againstECisgivenaccesstobothanencodingoracleandadecodingoracleDec(·).
IfBcancauseacollisioninthesecondcomponentsoftheoutputsofEnc(·),Dec(·),orboth,thenitwins.
Ofcourse,weexcludethecaseswhereBusesthetwooraclesinatrivialwaytoobtaincollisions(e.
g.
submittingaquerytoEnc(·)andthenimmediatelysubmittingtherstcomponentoftheresult,namelyMe,toDec(·)).
WerefertotheadvantagesoftheadversariesinthesetwosettingsasAdvcollcpaEC(A)andAdvcollccaEC(B),respectively.
Allencodingschemeswithdeterministicandstatelessencodingalgorithmsareinsecureunderchosen-plaintextcollisionattacks.
Furthermore,allencodingschemeswithstatelessdecodingalgorithmsareinsecureunderchosen-ciphertextcollisionattacks.
6.
3SSHSecurityResultsTheSSHencodingscheme,whenusedwithanl-bitblockcipher,isshowninFigure2(seealsoSection2).
Recallthat|x|denotesthelengthofstringxinbits,notbytes,andthatxkdenotestherepresentationofxasak-bitunsignedinteger.
Asmentioned,althoughFigure2showsthepaddingpasarandomstring(thesecondboxedequation),theSSHspecicationdoesnotrequirethatpberandom.
Additionally,althoughtheSSHspecicationallowsupto255bytesofpadding,thetwomajorimplementationsoftheSSHprotocol,openssh-2.
9p2andSSHCommunications'ssh-3.
0.
1,usetheminimum-recommendedpaddinglengthshowninFigure2.
TheproposedSSH-$NPCinstantiationofSSHreplacestherstboxedstatementwithbpl←bpl+lifbpl232.
Integrityandprivacyofourrecommendations.
OurproposedxesfromSection5aresecureunderourstrongnotionsofintegrity(int-sfctxt)andindistinguishability(ind-sfcca).
WesketchourproofofsecurityforSSH-CTR(seeAppendixC.
2fordetails).
TheprooftechniqueextendsnaturallytootherpossiblexestotheSSHBPP.
WerstpresentageneralresultthatholdsforallEncode-then-E&Mconstructions.
Thisresultstatesthat,foranyEncode-then-E&Mconstruction,iftheunderlyingencryptionschemeisind-cpa-secure,iftheunderlyingMACisasecurepseudorandomfunction,andiftheencodingschemeiscoll-cpacollisionresistant,thenthecompositeEncode-then-E&Mschemewillbeind-cpa-secure.
TheproofisinAppendixB.
1.
Lemma6.
4(PrivacyofEncode-then-E&MwithRespecttoChosen-PlaintextAttacks)LetSE,MA,andECrespectivelybeanencryption,amessageauthentication,andanencodingscheme.
LetSEbetheencryptionschemeassociatedtothemasperConstruction6.
1.
Then,givenanyind-cpaadversarySagainstSE,wecanconstructadversariesA,D,andCsuchthatAdvind-cpaSE(S)≤Advind-cpaSE(A)+2·AdvprfMA(D)+2·AdvcollcpaEC(C).
Furthermore,A,D,andCusethesameresourcesasSexceptthatA'sandD'sinputstotheirrespectiveoraclesmaybeofdierentlengthsthanthoseofS(duetotheencoding).
WenowstateourresultforSSH-CTR:15Theorem6.
5(SecurityofSSH-CTR)LetSEbeaCTR-modeencryptionschemewithstatefuldecryption,letMAbeamessageauthenticationscheme,andletECbetheencodingschemede-scribedabove.
LetSSH-CTRbetheencryptionschemeassociatedtothemasperConstruction6.
1.
Then,givenanyint-sfctxtadversaryIagainstSSH-CTR,wecanconstructadversariesFandCsuchthatEquation(1)holds.
Similarly,givenanyind-sfccaadversaryAagainstSSH-CTR,wecanconstructadversariesS,B,E,andGsuchthatEquation(2)holds.
Advint-sfctxtSSH-CTR(I)≤Advuf-cmaMA(F)+AdvcollccaEC(C)(1)Advind-sfccaSSH-CTR(A)≤2·Advint-sfctxtSSH-CTR(S)+Advind-cpaSE(B)+2·AdvprfMA(E)+2·AdvcollcpaEC(G)(2)Furthermore,FandCusethesameresourcesasIexceptthatF'smessagestoitsoraclesmaybeofdierentlengthsthanI'squeriestoitsoracles(duetoencoding)andC'smessagestoitsdecodingoraclemayhaveslightlydierentlengthsthanI'sdecryptionqueries.
Also,S,B,E,andGusethesameresourcesasAexceptthatB'sandE'sinputstotheirrespectiveoraclesmaybeofdierentlengthsthanthoseofA(duetotheencoding).
Theorem6.
5canbeinterpretedasfollows.
Equation(1)statesthatSSH-CTRprovidesstatefulchosen-ciphertextintegrityiftheMACisstronglyunforgeableandiftheencodingiscoll-ccacolli-sionresistant.
Equation(2)statesthatSSH-CTRprovidesstatefulchosen-ciphertextprivacyifitprovidesstatefulchosen-ciphertextintegrity,iftheunderlyingencryptionschemeisind-cpasecure,iftheMACisasecurepseudorandomfunction,andiftheencodingiscoll-cpasecure.
Asasexam-ple,makingreasonableassumptionsaboutthesecurityoftheHMACscheme,animplementationofSSH-CTRthatusesHMACandAESinstateful-decryptionCTRmodewillbesecureunderbothofthestrongnotionsprovidedthatatmost232messagesareencryptedbetweenrekeying.
NoticeherethatweusedierentsecuritypropertiesoftheMACtoobtaindierentsecurityaspectsofSSH-CTR,namelystrongunforgeabilityforintegrityandpseudorandomnessforprivacy.
ThisdistillsthepropertyoftheMACthatleadstoeachaspectofsecurity.
Wepointout,however,thatthenotionofstrongunforgeabilityisrelativelynew[4]andthatwedonotknowofanyprovably-securestronglyunforgeableMACsthatarenotalsopseudorandomfunctions.
ToproveTheorem6.
5(detailsinAppendixC.
2),werstuseLemma6.
3,Lemma6.
4,theind-cpaproofofsecurityforCTRmode[2],andtheassumedpseudorandomnessoftheunderlyingMACtoshowthatSSH-CTRisind-cpa-secure.
WethenproveEquation(1).
ApplyingProposition6.
2andourind-cpaandint-sfctxtresultsforSSH-CTRleadstoEquation(2).
WebrieydiscussourproofofEquation(1).
LetIbeanint-sfctxtadversaryandletMibeI'si-thchosen-plaintextquerytoitsencodingoracle,letMie,MitbetheencodingofMi,andletσiτibethereturnedciphertext.
LetσjτjbeI'sj-thdecryption-vericationoraclequery,letmjebethedecryptionofσjbytheunderlyingdecryptionalgorithm.
ToproveEquation(1),webasicallyshowthatgivenanint-sfctxtadversaryattackingSSH-CTR,thatadversarycanalsobeusedtoattacktheunforgeabilityoftheunderlyingMAC,toattackthecoll-ccacollisionresistanceoftheunderlyingencodingscheme,orthattherstout-of-orderciphertextsubmittedbytheadversary,σjτj,issuchthatσj=σjbutMje=mje.
BypropertiesofCTRmodewithstatefuldecryption,thelattereventcannotoccur.
ThesamepropertyholdsforSSH-CTRIV-CBCandSSH-EIV-CBC.
ForSSH-$NPCthelattereventcanoccur,buttheprobabilitythelattereventoccursissmallbecausethelast(random)blockoftheencodedpacketisnotgiventotheadversary.
ThestrategyweoutlinedinthisparagraphcanbeusedtoprovethesecurityofotherxestotheSSHBPPthatworkbyreplacingtheunderlyingencryptionscheme;namely,provethattheunderlyingencryptionschemeisind-cpasecureandthattheprobabilityoftheeventwedescribedissmall.
(Weonlyconsidertherstout-of-orderciphertextqueryanadversarymakesbecauseiftherstout-of-orderciphertextquerydoesnotdecrypt,thedecryptorentersahaltingstate.
)167DiscussionandRecommendationsHavingthuspresentedourmainresults,wearenowinapositiontomakespecicrecommendationstotheSSHcommunity.
WebeginbynotingthatafundamentalproblemwiththecurrentSSHspecicationisthatthecounter(thatisprependedtotheencodedpayloadbeforeMACing)isonly32bitslong.
AsshowninSection4,oncethe32bitcounterrepeats,anSSHsession'sMACtagsmaybegintoleakinformationaboutauser'splaintexts.
Ourprovablesecurityresultsreectthisconstraint:strongsecurityismaintainedonlyifthepartiesrekeyatleastonceevery232packets.
TwonaturalsolutionstothisproblemaretoeithermakethecounterlongerortorequireanSSHsessiontorekeyatleastonceevery232messages.
WerecommendthesecondoptionbecauseitdoesnotaectthepacketformatandthuswilllikelyrequireminimalchangestoexistingimplementationsofSSH.
Inthefollowingdiscussionweassumethatallimplementationswillrekeyfrequently.
WeconsiderthecurrentinstantiationoftheSSHBPPtransportprotocol,SSH-IPC,andourspecicrecommendations.
Wealsoconsidertwootherpossiblealternatives,namelyswitchingtoanEncrypt-then-MAC-basedconstructionortoadedicatedauthenticatedencryptionconstruction.
Theformerinvolvesre-engineeringtheSSHBPPsothatitrstencryptsamessagewithsomeun-derlyingencryptionschemeandthenMACstheresultingciphertext.
ThelatterinvolvesmodifyingSSHtouseadedicatedauthenticatedencryptionscheme(e.
g.
,XCBC[13],OCB[24]).
ContinuetouseSSH-IPCAsmentioned,SSH-IPCissusceptibletoanadaptivechosen-plaintextattackrequiringanSSHusertoencryptontheorderof213packets.
However,theattackmaynotbeconsideredpracticalsinceitrequirestheattackerto,afterseeingaciphertextcollision,controlthenextmessagethatauserencrypts.
Ifthesessionisencryptingalotofdataveryquickly(e.
g.
,whiletransferringale),thenanattackermaynothavetimetobothrecognizethatacollisionhasoccurredandtoforcetheusertoencryptaspecially-doctoredmessage.
Additionally,ifweconsiderhowtheSSHtransportprotocolisusedwithinSSH(andnotasanentitybyitself),thentheattackiscomplicatedbythefactthatanapplicationmaycompressandfurtherencodeuserdatabeforepassingtheresultingcompressedpayloadtotheSSH-IPCprotocol.
Nonetheless,wesuggestthattheuseofSSH-IPCbedeprecated.
Onesimplereasonisthat,eveniftheseattacksmaybediculttomountinpractice,inthemoderneraofstrongcryptographyitwouldseemcounterintuitivetovoluntarilyuseaprotocolwithlowsecuritywhenitispossibletoxthesecurityofSSHatlowcost.
SwitchtoSSH-NPCSinceSSH-NPCrequiressimilarchangestothespecicationandimple-mentationsasSSH-$NPCwhileachievinglesssecuritythanourotherxes,theredoesnotappeartobeanysubstantialreasonstoswitchtoSSH-NPC.
Therefore,wedonotconsideritfurther.
SwitchtoSSH-$NPCTheadvantagesoeredbySSH-$NPCareclear:itisprovablysecureandrequiresrelativelyminorandmostlylocalizedchangestotheSSHspecicationandtoimple-mentations.
Theaddedsecurity,however,comeswiththeadditionalcostofuptotwoextrablocksperpacket.
Ininteractivesessionswhereanindividualpacketmayonlycontainafewbytesofuserdata,theadditionalcostassociatedwiththoseextrablocksmaybesignicant(intermsofband-widthconsumption,thetimenecessarytoencryptandMACthosetwoextrablocks,andthetimerequiredtogeneratetheextrablockofrandomness).
AnotherpotentialproblemwithSSH-$NPCisthatitispronetoaccidentalimplementationmistakes.
RecallthatifthepaddingusedwithSSH-$NPCisnotrandomized,thenthesamereactionattackagainstSSH-NPCwillbeeectivehere.
SincetwoSSHimplementationswillinter-operateregardlessofwhethertheirpaddingisrandomorxed,anSSHdevelopermightaccidentallyusenon-randomorpredictablepadding.
Suchanaccidentalimplementationmistakecouldhaveserioussecurityconsequences.
SwitchtoSSH-CTRSSH-CTRIV-CBCorSSH-EIV-CBCTheSSH-CTRinstantiationis17apromisingcandidatesinceitisprovablysecure,doesnotincurpacketexpansion,anddoesnotrequirethepaddingtoberandom.
Furthermore,thereareseveralperformanceadvantageswithusingCTRmodeinsteadofCBCmode;forexample,asoftwareCTRmodeimplementationcanbeuptofourtimesfasterthanawell-optimizedCBCimplementation[22].
AlthoughperhapsnotasattractiveasSSH-CTR,SSH-CTRIV-CBCandSSH-EIV-CBCarealsopromisingcandidatesbecausetheyalsorequirenoadditionalpaddingandbecausetheyonlyuseonemoreblockcipherinvocationperpacketthanSSH-IPC.
RecallthattheunderlyingencryptionschemesforSSH-CTR,SSH-CTRIV-CBC,andSSH-EIV-CBCrequireboththesenderandthereceivertomaintainstate.
Priortothiswork,mostprov-ablesecurityanalysesfocusedonencryptionschemeswithstatelessdecryptionalgorithms(henceourneedtodenesecuritynotionsforencryptionschemeswithstatefuldecryptionalgorithms).
Consequently,oneinitialobjectiontothesethreeconstructionsmightbethattheyrequiretheunderlyingdecryptionalgorithmstomaintainstate.
However,sincethecompositeSSHBPPde-cryptionalgorithmisalreadystateful(becausethedecodingalgorithmisstateful),thefactthatthesethreexesuseunderlyingencryptionschemeswithstatefuldecryptionalgorithmsshouldbeoflittleconcern.
AnotherpotentialdisadvantagewithCTRmodeisthatitisoftenperceivedasbeingtoo"risky"[22].
As[22]pointsout,however,whenusedcorrectlyandwithproofsofsecurity,CTRmodehasmanyadvantagesoverotherencryptionmodes.
Furthermore,asBellovinandBlazepointoutin[7],onecanminimizetheriskincurredwithusingCTRmode(includingtheriskofbeingforcedtouserepeatingcounters)ifkeymanagementisdonedynamicallyandproperly,ifitisnotusedwithmultiplesenderswhosharekeys,andifitisusedinconjunctionwithstrongintegritychecks.
AlloftheseconditionsholdinthecaseofSSH-CTR.
SwitchtoEncrypt-then-MACInsteadofinsistingonusingthecurrentSSHEncode-then-E&Mconstruction,itwouldalsobepossibletoswitchtoanotherparadigmsuchasEncrypt-then-MAC(inwhichthemessageisrstencryptedwithanunderlyingencryptionschemeandthentheresultingciphertextisMACedwithanunderlyingmessageauthenticationscheme).
ThisalternativeisattractivebecauseanEncrypt-then-MACconstructionisprovablysecureassumingthatitsunderlyingencryptionandmessageauthenticationschemesarealsosecure[4,20].
Wenote,however,thatsinceourrecommendedxesprovablymeetourstrongestnotionsofsecurity,theremaybelittlemotivationtoswitchtoanEncrypt-then-MAC-basedconstruction.
Additionally,switchingtoanEncrypt-then-MACconstructionwilllikelyrequiremoreintrusivemodicationstothecurrentSSHspecicationandtoSSHimplementations.
Furthermore,unlesscareistaken,implementationsofthemodiedSSHspecicationmaynotbecompatiblewithimplementationsofthecurrentSSHspecication.
Conceptuallyspeaking,thechangesincurredbySSH-CTR,SSH-$NPC,SSH-CTRIV-CBC,andSSH-EIV-CBCinvolveonlychangingtheunderlyingencryptionmoduleand,inthecaseofSSH-$NPC,addingmorerandomnumbergenerationforthepadding.
Incontrast,thechangesincurredbyswitchingtotheEncrypt-then-MACconstructioninvolvechangingthewholeconstruction.
Ofcourse,thedierenceintheactualeortsthatdevelopersneedtoputinishighlyimplementationdependent.
SwitchtodedicatedauthenticatedencryptionschemesTherearesymmetrickey-basedauthenticatedencryptionschemesthataredesignedfromscratchand,thus,arepotentiallymoreecientthanschemesbasedonablack-boxcompositionofo-the-shelfencryptionandMACcom-ponents.
TheseincludeRPC[19],XCBC[13],IACBC[18],andOCB[24].
RecallthatcurrentlytheinputtotheSSHBPP'sunderlyingencryptionschemeisdierentfromtheinputtotheunderlyingMAC.
TherearetwopossiblewaystoincorporateadedicatedauthenticatedencryptionschemeintoSSH:(1)specicallyre-designtheSSHspecicationaroundasingleauthenticatedencryptioncomponentor(2)somehowplugadedicatedauthenticatedencryptionschemeintothecurrentSSH18design.
AswementionedwhenweconsideredtheEncrypt-the-MACparadigm,re-designingtheSSHspecicationisprobablynotanattractiveoption.
For(2),themostlogicalwaytoincorporateadedicatedschemeintoSSHwouldbetoreplacethecurrentencryptionscheme(CBCmodewithchainedIVs)withsomethinglikeXCBCorOCBandtousethe"none"messageauthenticationscheme.
AswearguedforSSH-CTR,SSH-$NPC,SSH-CTRIV-CBC,andSSH-EIV-CBC,thismodicationshouldbefairlyeasytodo,and,giventheeciencyofdedicatedauthenticatedencryptionschemes,couldresultinsignicantperformancegains.
ThepresentdrawbackwiththisapproachisthatthecurrentSSHspecicationdoesnotincludethe32-bitcounterintheinputtotheunderlyingencryptionscheme.
Since,underthisconstruction,thecounterwillnotbeboundtotheinputtothededicatedauthenticatedencryptionscheme,thisconstructioncannotprotectagainstreplayandout-of-orderdeliveryattacks(whileourproposedrecommendationscan).
Torectifythissituation,onewouldstillhavetomodifymorethanjustthe"black-box"encryptioncomponentoftheSSHBPP;doingsohasthesamedrawbacksaspossibility(1)above.
Closingremarks.
WeacknowledgethattherearemanypossiblewaystoxthecurrentproblemswiththeSSHprotocol.
Wearebiasedtowardsourrecommendedxes(e.
g.
,SSH-CTR)becausetheyare"lessintrusive"thantheotherpossiblemodicationsbutarestillecientandsecure.
"Lessintrusive"is,however,asubjectivemeasureandtheIETFSSHworkinggroupmaydecidethatitisfeasibletore-engineertheSSHprotocoltouseanEncrypt-then-MAC-basedconstructionoradedicatedauthenticatedencryptionscheme.
GiventheinertiaofthecurrentSSHprotocol,however,wefeelthattheworkinggroupmayhaveahardtimejustifyingsignicantmodicationstotheSSHspecication.
ThegoalofthisworkistoprovideenoughinformationtotheSSHcommunitysothattheSSHcommunitycanmakeaninformeddecisionwhendecidinghowtoxthecurrentproblemswithSSH.
AcknowledgmentsWethankAlexandraBoldyreva,GregoryNeven,AdrianaPalacio,BillSommerfeld,andDavidWagnerforcommentingonanearlierversionofthispaper.
ThesecondauthorthankstheUSENIXAssociationforaStudentGrantsupportinghisearlierworkwithSSH.
References[1]J.
H.
An,Y.
Dodis,andT.
Rabin.
Onthesecurityofjointsignatureandencryption.
InL.
Knudsen,editor,AdvancesinCryptology–EUROCRYPT2002,volume2332ofLectureNotesinComputerScience,pages83–107.
Springer-Verlag,BerlinGermany,Apr.
1995.
[2]M.
Bellare,A.
Desai,E.
Jokipii,andP.
Rogaway.
Aconcretesecuritytreatmentofsymmet-ricencryption.
InProceedingsofthe38thAnnualSymposiumonFoundationsofComputerScience,pages394–403.
IEEEComputerSocietyPress,1997.
[3]M.
Bellare,J.
Kilian,andP.
Rogaway.
Thesecurityofthecipherblockchainingmessageauthenticationcode.
InY.
Desmedt,editor,AdvancesinCryptology–CRYPTO'94,volume839ofLectureNotesinComputerScience,pages341–358.
Springer-Verlag,BerlinGermany,Aug.
1994.
[4]M.
BellareandC.
Namprempre.
Authenticatedencryption:Relationsamongnotionsandanalysisofthegenericcompositionparadigm.
InT.
Okamoto,editor,AdvancesinCryptology19–ASIACRYPT2000,volume1976ofLectureNotesinComputerScience,pages531–545.
Springer-Verlag,BerlinGermany,Dec.
2000.
[5]M.
BellareandP.
Rogaway.
Encode-then-encipherencryption:Howtoexploitnoncesorredun-dancyinplaintextsforecientcryptography.
InT.
Okamoto,editor,AdvancesinCryptology–ASIACRYPT2000,volume1976ofLectureNotesinComputerScience,pages317–330.
Springer-Verlag,BerlinGermany,Dec.
2000.
[6]S.
Bellovin.
ProblemareasfortheIPsecurityprotocols.
InProceedingsofthe6thUSENIXSecuritySymposium,SanJose,California,July1996.
[7]S.
BellovinandM.
Blaze.
Cryptographicmodesofoperationfortheinternet.
InSecondNISTWorkshoponModesofOperation,2001.
[8]J.
BlackandP.
Rogaway.
CBCMACsforarbitrary-lengthmessages:Thethree-keycon-struction.
InM.
Bellare,editor,AdvancesinCryptology–CRYPTO2000,LectureNotesinComputerScience.
Springer-Verlag,BerlinGermany,Aug.
2000.
[9]R.
CanettiandH.
Krawczyk.
Analysisofkey-exchangeprotocolsandtheiruseforbuildingsecurechannels.
InB.
Ptzmann,editor,AdvancesinCryptology–EUROCRYPT2001,volume2045ofLectureNotesinComputerScience,pages451–472.
Springer-Verlag,BerlinGermany,2001.
[10]W.
Dai.
AnattackagainstSSH2protocol,Feb.
2002.
Emailtotheietf-ssh@netbsd.
orgemaillist.
[11]DESmodesofoperation.
NationalInstituteofStandardsandTechnology,NISTFIPSPUB81,U.
S.
DepartmentofCommerce,Dec.
1980.
[12]W.
DieandM.
E.
Hellman.
Privacyandauthentication:Anintroductiontocryptography.
ProceedingsoftheIEEE,67(3):397–427,Mar.
1979.
[13]V.
GligorandP.
Donescu.
Fastencryptionandauthentication:XCBCencryptionandXECBauthenticationmodes.
InFastSoftwareEncryption2001,LectureNotesinComputerScience.
Springer-Verlag,BerlinGermany,2001.
[14]O.
Goldreich,S.
Goldwasser,andS.
Micali.
Onthecryptographicapplicationsofrandomfunctions.
InR.
Blakely,editor,AdvancesinCryptology–CRYPTO'84,volume196ofLectureNotesinComputerScience,pages276–288.
Springer-Verlag,BerlinGermany,1985.
[15]S.
GoldwasserandS.
Micali.
Probabilisticencryption.
JournalofComputerandSystemScience,28:270–299,1984.
[16]C.
Hall,I.
Goldberg,andB.
Schneier.
Reactionattacksagainstseveralpublic-keycryptosys-tems.
InProceedingsofInformationandCommunicationSecurity,ICICS'99,1999.
[17]InternetEngineeringTaskForce.
SecureShell(secsh)charter,2002.
http://www.
ietf.
org/html.
charters/secsh-charter.
html.
[18]C.
Jutla.
Encryptionmodeswithalmostfreemessageintegrity.
InB.
Ptzmann,editor,AdvancesinCryptology–EUROCRYPT2001,volume2045ofLectureNotesinComputerScience,pages529–544.
Springer-Verlag,BerlinGermany,May2001.
20[19]J.
KatzandM.
Yung.
Unforgeableencryptionandchosenciphertextsecuremodesofoperation.
InB.
Schneier,editor,FastSoftwareEncryption2000,volume1978ofLectureNotesinComputerScience,pages284–299.
Springer-Verlag,BerlinGermany,Apr.
2000.
[20]H.
Krawczyk.
Theorderofencryptionandauthenticationforprotectingcommunications(or:HowsecureisSSL).
InJ.
Kilian,editor,AdvancesinCryptology–CRYPTO2001,volume2139ofLectureNotesinComputerScience,pages310–331.
Springer-Verlag,BerlinGermany,Aug.
2001.
[21]H.
Krawczyk,M.
Bellare,andR.
Canetti.
HMAC:Keyed-hashingformessageauthenticationa.
IETFInternetRequestforComments2104,Feb.
1997.
[22]H.
Lipmaa,P.
Rogaway,andD.
Wagner.
CTR-modeencryption.
InFirstNISTWorkshoponModesofOperation,2000.
[23]P.
Rogaway.
ProblemswithproposedIPcryptography,1995.
Availableathttp://www.
cs.
ucdavis.
edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.
txt.
[24]P.
Rogaway,M.
Bellare,J.
Black,andT.
Krovetz.
OCB:Ablock-ciphermodeofoperationforecientauthenticatedencryption.
InProceedingsofthe8thConferenceonComputerandCommunicationsSecurity,pages196–205.
ACMPress,2001.
[25]D.
X.
Song,D.
Wagner,andX.
Tian.
TiminganalysisofkeystrokesandtimingattacksonSSH.
InTenthUSENIXSecuritySymposium,2001.
[26]S.
Vaudenay.
SecurityawsinducedbyCBCpadding–applicationstoSSL,IPSEC,WTLS.
.
.
.
InL.
Knudsen,editor,AdvancesinCryptology–EUROCRYPT2002,volume2332ofLectureNotesinComputerScience,pages534–545.
Springer-Verlag,BerlinGermany,2002.
[27]T.
Ylonen.
SSH—SecureloginconnectionsovertheInternet.
InSixthUSENIXSecuritySymposium,1996.
[28]T.
Ylonen,T.
Kivinen,M.
Saarinen,T.
Rinne,andS.
Lehtinen.
SSHtransportlayerprotocol,2002.
Draft12,availableat[17].
AFormalNotionsofSecurityDenitionA.
1(Collisionresistanceofencodingschemes)LetEC=(Enc,Dec)beaen-codingscheme.
LetAcpabeanadversarywithaccesstoanencodingoracleandletAccabeanadversarywithaccesstoanencodingoracleEnc(·)andadecodingoracleDec(·).
LetMidenoteanadversary'si-thencodingqueryandlet(Mie,Mit)denotetheresponseforthatquery.
LetmiedenoteAcca'si-thdecodingqueryandlet(mi,mit)denotetheresponseforthatquery.
Considerthefollowingexperiments:ExperimentExpcoll-cpaEC(Acpa)RunAEnc(·)cpa,andifAEnc(·)cpamakestwoqueriesMi,MjtoEnc(·)suchthati=jandMit=Mjtthenreturn1elsereturn0ExperimentExpcoll-ccaEC(Acca)RunAEnc(·),Dec(·)ccaand,ifoneofthefollowingoccurs:—AccamakestwoqueriesMi,MjtoEnc(·)suchthati=jandMit=Mjt21—Accamakestwoqueriesmie,mjetoDec(·)suchthati=j,mit=⊥,andmit=mjt—AccamakesaqueryMitoEnc(·)andaquerymjetoDec(·)suchthat(i=jorMi=mjorMie=mje)andMit=mjtthenreturn1elsereturn0WedenetheadvantagesoftheadversariesAcpaandAccainndingacollisionasAdvcollcpaEC(Acpa)=PrExpcoll-cpaEC(Acpa)=1AdvcollccaEC(Acca)=PrExpcoll-ccaEC(Acca)=1.
DenitionA.
2(Privacyforsymmetricencryptionschemes)LetSE=(K,E,D)beasym-metricencryptionscheme,andletb∈{0,1}.
LetAcpabeanadversarythathasaccesstoaleft-or-rightencryptionoracleEK(LR(·,·,b));letAccaandAsfccabeadversariesthathaveaccesstoaleft-or-rightencryptionoracleandadecryptionoracleDK(·).
Eachadversaryreturnsabit.
Considerthefollowingexperiments:ExperimentExpind-cpa-bSE(Acpa)KR←KRunAEK(LR(·,·,b))cpaReplytoEK(LR(M0,M1,b))queriesasfollows:CR←EK(Mb);AcpaCUntilAcpareturnsabitdReturndExperimentExpind-cca-bSE(Acca)KR←KRunAEK(LR(·,·,b)),DK(·)ccaReplytoEK(LR(M0,M1,b))queriesasfollows:CR←EK(Mb);AccaCReplytoDK(C)queriesasfollows:M←DK(C);AccaMUntilAccareturnsabitdReturndExperimentExpind-sfcca-bSE(Asfcca)KR←Ki←0;j←0;phase←0RunAEK(LR(·,·,b)),DK(·)sfccaReplytoEK(LR(M0,M1,b))queriesasfollows:i←i+1;CiR←EK(Mb)AsfccaCiReplytoDK(C)queriesasfollows:j←j+1;M←DK(C)Ifj>iorC=Cjthenphase←1Ifphase=1thenAsfccaMUntilAsfccareturnsabitdReturndWerequirethat,forallqueries(M0,M1)toEK(LR(·,·,b)),|M0|=|M1|.
ForExpind-cca-bSE(Acca),werequirethatAccanotqueryDK(·)onaciphertextpreviouslyreturnedbyEK(LR(·,·,b)).
Werespectivelydenethechosen-plaintext,chosen-ciphertext,andstatefulchosen-ciphertextprivacyadvantagesoftheadversariesasAdvind-cpaSE(Acpa)=PrExpind-cpa-1SE(Acpa)=1PrExpind-cpa-0SE(Acpa)=1Advind-ccaSE(Acca)=PrExpind-cca-1SE(Acca)=1PrExpind-cca-0SE(Acca)=1Advind-sfccaSE(Asfcca)=PrExpind-sfcca-1SE(Asfcca)=1PrExpind-sfcca-0SE(Asfcca)=1.
22DenitionA.
3(Integrityforsymmetricencryptionschemes)LetSE=(K,E,D)beasymmetricencryptionscheme.
LetAptxt,Actxt,andAsfctxtbeadversarieseachwithaccesstoanencryptionoracleEK(·)andadecryption-vericationoracleDK(·).
Thedecryption-vericationoracleinvokesDK(C)andreturns1ifDK(·)=⊥and0otherwise.
ConsidertheexperimentsExperimentExpint-ptxtSE(Aptxt)KR←K;S←RunAEK(·),DK(·)ptxtReplytoEK(M)queriesasfollows:CR←EK(M)S←S∪{M}AptxtCReplytoDK(C)queriesasfollows:M←DK(C)IfM=⊥andM∈Sthenreturn1IfM=⊥thenAptxt1ElseAptxt0UntilAptxthaltsReturn0ExperimentExpint-sfctxtSE(Asfctxt)KR←Ki←0;j←0;phase←0RunAEK(·),DK(·)ctxtReplytoEK(M)queriesasfollows:i←i+1;CiR←EK(Mb)AsfctxtCiReplytoDK(C)queriesasfollows:j←j+1;M←DK(C)Ifj>iorC=Cjthenphase←1IfM=⊥andphase=1thenreturn1IfM=⊥thenAsfctxt1ElseAsfctxt0UntilAsfctxthaltsReturn0andanexperimentExpint-ctxtSE(Actxt)thatisidenticaltoExpint-ptxtSE(Aptxt)exceptthattherstboxedequationisS←S∪{C}andthesecondboxedequationisC∈S.
Wedenetheadvantagesoftheadversariesinattackingtheplaintext,ciphertext,andstatefulciphertextintegrityoftheschemerespectivelyasAdvint-ptxtSE(Aptxt)=PrExpint-ptxtSE(Aptxt)=1Advint-ctxtSE(Actxt)=PrExpint-ctxtSE(Actxt)=1Advint-sfctxtSE(Actxt)=PrExpint-sfctxtSE(Asfctxt)=1.
DenitionA.
4(StrongUnforgeabilityofmessageauthenticationschemes)LetMA=(K,T,V)beamessageauthenticationscheme.
LetFbeaforgerwithaccesstoataggingoracleTK(·)andavericationoracleVK(·,·).
Considerthefollowingexperiment:ExperimentExpufcmaMA(F)KR←K;S←RunFTK(·),VK(·,·)ReplytoTK(M)queriesasfollows:τR←TK(M);S←S∪{(M,τ)};FτReplytoVK(M,τ)queriesasfollows:v←V(M,τ)Ifv=1and(M,τ)∈Sthenreturn1FvUntilFhaltsReturn023WedenetheadvantageofFinforgingamessageasAdvuf-cmaMA(F)=PrExpufcmaMA(F)=1.
DenitionA.
5(Pseudorandomfunctionsandsuper-pseudorandompermutations)LetF:{0,1}k*M→{0,1}LbeafamilyoffunctionsfromsomemessagespaceMto{0,1}L,andletRandM→LdenotethefamilyofallfunctionsfromMto{0,1}L.
LetP:{0,1}k*{0,1}l→{0,1}ldenoteafamilyofpermutationson{0,1}l,andletPermlbethefamilyofallpermutationson{0,1}l.
LetDprfbeaPRFdistinguisherforFandletDprpbeasuper-pseudorandomdistinguisherforP.
Considerthefollowingexperiments:ExperimentExpprf-bF(Dprf)Ifb=1thenKR←{0,1}k;g←FKElsegR←RandM→LRunDgprfReplytog(M)queriesasfollows:Dprfg(M)UntilDprfreturnsabitdReturndExperimentExpprp-cca-bF(Dprp)Ifb=1thenKR←{0,1}k;g←PKElsegR←PermlRunDg,g1prpReplytog(M)queriesasfollows:Dprpg(M)Replytog1(C)queriesasfollows:Dprpg1(C)UntilDprpreturnsabitdReturndWedenetheadvantagesoftheadversariesasAdvprfF(Dprf)=PrExpprf-1F(Dprf)=1PrExpprf-0F(Dprf)=1AdvprpccaP(Dprp)=PrExpprp-cca-1P(Dprp)=1PrExpprp-cca-0P(Dprp)=1.
BGeneralSecurityResultsfortheEncode-then-E&MParadigmWepresentheregeneralresultsfortheEncode-then-E&Mcompositionmethod.
Weusetheseresultswhenprovingthesecurityofourproposedxes.
TheseresultswillalsobeusefultotheevaluatorsofotherEncode-the-E&Mconstructions.
B.
1Chosen-PlaintextPrivacy(ProofofLemma6.
4)Lemma6.
4statesthat,toconstructacomposedschemethatprovideschosen-plaintextprivacyviathisparadigm,itisenoughtouseanind-cpasecureencryptionscheme,apseudorandomMAC,andacoll-cpasecureencodingschemeasbuildingblocks.
OnenotablefeatureoftheproofisthatitactuallyusesaweakerpropertythanpseudorandomnessfortheunderlyingMAC.
ButsincemostMACsinpracticearepseudorandom,thedistinctionisperhapsmainlyoftheoreticalinterest.
Distinctplaintextprivacyofmessageauthenticationschemes.
BeforeprovingLemma6.
4,werstpresentanewnotionofsecurityformessageauthenticationschemes:indistinguishabil-ityunderdistinctchosen-plaintextattacks,ind-dcpaforshort.
LetMA=(K,T,V)beamessageauthenticationscheme.
Thenotionofind-dcpaforMAisbasedonthenotionofind-cpaforen-cryptionschemes.
ForbitbandkeyKletTK(LR(·,·,b))denotethelr-tagoraclewhich,givenequal-lengthplaintextsM0,M1,returnsTK(Mb).
(Westressthatthelr-tagoraclereturnsonlythetagandnotthemessage-tagpairMbTK(Mb).
)Theind-dcpanotionisdenedasfollows.
24DenitionB.
1(IndistinguishabilityagainstDistinctChosen-PlaintextAttacks)LetMA=(K,T,V)beamessageauthenticationscheme.
Letb∈{0,1}.
LetAbeanadversarythathasaccesstoanoracleTK(LR(·,·,b)).
Considerthefollowingexperiment:ExperimentExpind-dcpa-bMA(Acpa)KR←KRunATK(LR(·,·,b))cpaReplytoTK(LR(M0,M1,b))queriesasfollows:CR←TK(Mb);AcpaCUntilAcpareturnsabitdReturndAboveitismandatedthatallleftmessagesofA'squeriesbeuniqueandthatallrightmessagesofA'squeriesbeunique.
WedenetheadvantageofAviaAdvind-dcpaMA(A)=PrExpind-dcpa-1MA(A)=1PrExpind-dcpa-0MA(A)=1.
TheoremB.
2(RelationbetweenIND-DCPAandPRF)LetMAbeaMACscheme.
Then,givenanyind-dcpaadversaryAagainstMA,wecanconstructadistinguisherDagainstMAsuchthatAdvind-dcpaMA(A)≤2·AdvprfMA(D)Furthermore,DusesthesameresourcesofA.
ThistheoremimpliesthatifMAissecureasaPRF(asisexpectedofmanyMACs;e.
g.
,[3,8]),thenitwillalsobeind-dcpasecure.
Thetheoremiseasytoverify.
Therefore,weomittheproof.
NowwestateandproveLemmaB.
3below.
Lemma6.
4followsdirectlyfromTheoremB.
2andLemmaB.
3.
Throughout,weletEnc(·,·)andDec(·,·)denotetheencodingalgorithmsEnc(·)andDec(·)exceptthattheyexplicitlytakeastateaspartoftheinputandreturnanewstateaspartoftheoutput.
LemmaB.
3LetSE=(Ke,E,D)beanencryptionscheme,letMA=(Kt,T,V)beamessageauthenticationscheme,andletEC=(Enc,Dec)beanencodingscheme.
LetSEbetheencryptionschemeassociatedtothemasperConstruction6.
1.
Then,givenanyind-cpaadversarySagainstSE,wecanconstructanind-cpaadversaryAagainstSE,anind-dcpaadversaryBagainstMA,andacollisionnderCsuchthatAdvind-cpaSE(S)≤Advind-cpaSE(A)+Advind-dcpaMA(B)+2·AdvcollcpaEC(C).
Furthermore,A,B,andCusethesameresourcesasSexceptthatA'sandB'sinputstotheirrespectiveoraclesmaybeslightlylargerthanthoseofS(duetotheencoding).
ProofofLemmaB.
3:LetSdenoteanind-cpaadversarythathasoracleaccesstoEK(LR(·,·,b)),b∈{0,1}.
Letx∈{1,2,3}.
WedenethreeexperimentsassociatedwithSasfollows.
ExperimentExpHxKeR←Ke;KtR←Kt;st0←ε;st1←εRunSreplyingtoitsoraclequery(M0,M1)asfollows:(Me,0,Mt,0,st0)R←Enc(M0,st0);(Me,1,Mt,1,st1)R←Enc(M1,st1)Switch(x):25Casex=1:σR←EKe(Me,1);τR←TKt(Mt,1)Casex=2:σR←EKe(Me,0);τR←TKt(Mt,1)Casex=3:σR←EKe(Me,0);τR←TKt(Mt,0)ReturnστtoSUntilShaltsandreturnsabitbReturnb.
LetPxdef=Pr[ExpHx=1]denotetheprobabilitythatexperimentExpHxreturns1,forx∈{1,2,3}.
BythedenitionofAdvind-cpaSE(S),wehaveAdvind-cpaSE(S)=P1P3=(P1P2)+(P2P3).
(3)GivenS,wecanconstructthreenewadversariesA,B,andCsuchthatthefollowinglemmasholdandthenewadversariesusetheresourcesspeciedinthestatementofLemmaB.
3.
LemmaB.
4P1P2≤Advind-cpaSE(A).
LemmaB.
5P2P3≤Advind-dcpaMA(B)+2·AdvcollcpaEC(C).
Equation(3)andtheabovelemmasimplyLemmaB.
3.
ProofofLemmaB.
4:WeconstructanadversaryAbreakingprivacyoftheunderlyingencryptionschemeSE=(Ke,E,D)usingtheadversarySbelow.
AdversaryAEK(LR(·,·,b))KtR←Kt;st0←ε;st1←εRunSreplyingtoitsoraclequery(M0,M1)asfollows:(Me,0,Mt,0,st0)R←Enc(M0,st0);(Me,1,Mt,1,st1)R←Enc(M1,st1)σR←EK(LR(Me,0,Me,1,b));τR←TKt(Mt,1)ReturnστtoSUntilShaltsandreturnsabitbReturnb.
Ifb=1,theadversaryAsimulatesSintheexactsameenvironmentasthatofExpH1.
Similarly,ifb=0,theadversaryAsimulatesSintheexactsameenvironmentasthatofExpH2.
Thus,P1P2=PrExpind-cpa-1SE(A)=1PrExpind-cpa-0SE(A)=1=Advind-cpaSE(A).
TheadversaryAusesthesameresourcesasSexceptthat,duetotheencoding,thequeriesthatAmakestoitsoraclemaybeslightlylargerthanthequeriesthatSmakestoitsoracle.
Also,AperformstwoencodingsforeachquerythatSmakesand,thus,itsrunningtimeis(polynomially)largerthanthatofS.
Recallthestandardconventionthatrunningtimeofanadversaryismeasuredwithrespecttotheentireexperimentinwhichitruns.
Hence,LemmaB.
4follows.
ProofofLemmaB.
5:GivenS,wecanconstructanadversaryBthatcanbreakthedistinctchosen-plaintextsprivacyoftheunderlyingMACschemeMA=(Kt,T,V)andanadversaryC26thatcanbreakthecollisionresistanceoftheunderlyingencodingschemeEC=(Enc,Dec).
Theseadversariesaredenedinbelow.
AdversaryBTK(LR(·,·,b))KeR←Ke;st0←ε;st1←εRunSreplyingtoitsithoraclequery(Mi0,Mi1)asfollows:(Mie,0,Mit,0,st0)R←Enc(Mi0,st0)(Mie,1,Mit,1,st1)R←Enc(Mi1,st1)IfMit,0∈{M1t,0,Mi1t,0}orMit,1∈{M1t,1,Mi1t,1}thenreturn0σR←EKe(Mie,0)τR←TK(LR(Mit,0,Mit,1,b))ReturnστtoSUntilShaltsandreturnsabitbReturnbAdversaryCEnc(·)KeR←Ke;KtR←Kt;stn←εdR←{0,1};c←dRunSreplyingtoitsoraclequery(M0,M1)asfollows:(Me,d,Mt,d)R←Enc(Md)(Me,c,Mt,c,stn)R←Enc(Mc,stn)σR←EKe(Me,0)τR←TKt(Mt,1)ReturnστtoSUntilShaltsandreturnsabitbLetPr2[·]andPr3[·]denotetheprobabilitiesassociatedwiththeexperimentExpH2andExpH3,respectively.
LetE2denoteaneventthatthereexistsatleastonecollisionamongtheMt,0'soramongtheMt,1'sinExpH2.
LetE3denoteaneventthatthereexistsatleastonecollisionamongtheMt,0'soramongtheMt,1'sinExpH3.
Wemakethefollowingclaims.
ClaimB.
6Pr2[E2]≤2·AdvcollcpaEC(C).
ClaimB.
7Pr2ExpH2=1∧E2Pr3ExpH3=1∧E3=Advind-dcpaSE(B).
WecannowboundthedierenceP2P3asfollows:P2P3=Pr2[ExpH2=1]Pr3[ExpH3=1]=Pr2ExpH2=1∧E2+Pr2[ExpH2=1∧E2]Pr3ExpH3=1∧E3Pr3[ExpH3=1∧E3]≤Advind-dcpaSE(B)+2·AdvcollcpaEC(C).
TojustifyClaimB.
6,letE0betheeventthatthereexistsatleastonecollisionamongtheMt,0'sinExpH2andletE1betheeventthatthereexistsatleastonecollisionamongtheMt,1'sinExpH2.
LetPr[·]beoverExpcoll-cpaEC(C).
Then,PrExpcoll-cpaEC(C)=1=Pr[E0∧d=0]+Pr[E1∧d=1]=12·Pr2[E0]+Pr2[E1]≥12·Pr2[E2]wherethesecondequalitycomesfromthefactthatthemessagesCreturnstoAareindependentofthebitd.
TojustifyClaimB.
7,wenotethatBreturns1onlyifalltheMt,0'sandMt,1'sareunique(i.
e.
,eventsE2orE3didnotoccur).
TheadversariesBandCusethesameresourcesasSexceptthatthequeriesthatBmakestoitsoraclemaybeslightlylargerthanthoseofSduetotheencoding.
Also,BandCeachperformtwoencodingsforeachquerythatSmakesand,thus,theirrunningtimesare(polynomially)largerthanthatofS.
Recallthestandardconventionthatrunningtimeofanadversaryismeasuredwithrespecttotheentireexperimentinwhichitruns.
Hence,LemmaB.
5follows.
27B.
2IntegrityofPlaintextsTheoremB.
8statesthatthecomposedschemeprovidesplaintextintegrityiftheunderlyingMACisunforgeable2andiftheunderlyingencodingschemeiscollision-resistantagainstchosen-ciphertextattacks.
Asonewouldexpect,weneedmorethanchosen-plaintextcollisionresistanceoftheunderlyingencodingschemeherebecauseanadversaryisallowedtosubmitciphertextquerieswhenmountinganintegrityattack.
TheoremB.
8(IntegrityofPlaintextsforEncode-then-E&M)LetSEbeanencryptionscheme,letMAbeamessageauthenticationscheme,andletECbeanencodingscheme.
LetSEbetheencryptionschemeassociatedtothemasperConstruction6.
1.
Then,givenanyint-ptxtadversaryAagainstSE,wecanconstructadversariesFandCsuchthatAdvint-ptxtSE(A)≤Advuf-cmaMA(F)+AdvcollccaEC(C).
Furthermore,FandCusethesameresourcesasAexceptthatF'smessagestoitstaggingandtagvericationoraclesmaybeslightlylargerthanA'sencryptionqueries(duetotheencoding)andthatC'smessagestoitsdecodingoraclemayhavedierentlengthsthanA'sdecryptionqueries.
WeproveTheoremB.
8asfollows.
LetSE=(K,E,D)bethecompositeencryptionschemecon-structedviaConstruction6.
1fromtheencryptionschemeSE=(Ke,E,D),theMACschemeMA=(Kt,T,V),andtheencodingschemeEC=(Enc,Dec).
AssumewehaveanadversaryAattackingtheintegrityofplaintextsofSE.
WeassociatetoAtwoadversaries:aforgerFbreakingtheunforgeabilityofMAandacollisionnderCbreakingthecollisionresistanceofECsuchthatAdvint-ptxtSE(A)≤Advuf-cmaMA(F)+AdvcollccaEC(C).
(4)TheforgerFandthecollisionnderCaresimple.
TheforgerFusesKetogenerateanencryptionkeyandusestheencryptionkeyanditstaggingoracletoanswerA'squeriesinastraight-forwardmanner.
Inparticular,itfollowsConstruction6.
1.
Similarly,thecollisionnderCusesthesameapproach.
ThisensuresthatAisexecutedinthesameenvironmentasthatinExpint-ptxtSE(A).
LetPr1[·],Pr2[·],andPr3[·]respectivelydenotetheprobabilitiesassociatedwiththeexper-imentsExpint-ptxtSE(A),ExpufcmaMA(F),andExpcoll-ccaEC(C).
LetEdenotetheeventthatAmakesaquerythatwouldcauseCtosucceedinndingacollision.
Then,bythedenitionofE,Pr1[E]=Pr3Expcoll-ccaEC(C)=1.
Furthermore,Pr1Expint-ptxtSE(A)=1∧E≤Pr2ExpufcmaMA(F)=1sinceEimpliesthatthevericationrequestthatcausedAtosucceedmusthaveproduced(throughthedecoding)apreviouslyunseentaggingmessageMt(therebyallowingFtosucceed).
Conse-quently,Pr1Expint-ptxtSE(A)=1=Pr1Expint-ptxtSE(A)=1∧E+Pr1Expint-ptxtSE(A)=1∧E≤Pr2ExpufcmaMA(F)=1+Pr3Expcoll-ccaEC(C)=1andEquation(4)follows.
AdversariesFandAuseequivalentresourcesexceptthatF'smessagestoitsoraclesmaybeslightlylargerduetotheencoding.
AdversariesCandAalsouseequiva-lentresourcesexceptthatC'smessagetoitsoraclemaynotbetheexactlythesamesizeasA'sdecryption-vericationqueries,althoughtheyarepolynomiallyrelated.
2Althoughthetheoremstatementreferstostrongunforgeability,weakunforgeabilityoftheunderlyingMACschemeisactuallysucientheresincethecoll-ccapropertyoftheunderlyingencodingschemeensuresthatinputstotheMACalgorithmwillnotcollide.
28B.
3ObtainingChosen-CiphertextPrivacy(ProofofProposition6.
2)Ourproofismodeledaftertheproofin[4].
LetSE=(K,E,D)beasymmetricencryptionscheme,andletAbeanyind-sfccaadversaryagainstSE.
WeassociatetoAanind-cpaadversaryBandanint-sfctxtadversaryI.
Theseadversariesaresimple.
TheadversaryBrunsAalmostexactlyasinExpind-sfcca-bSE(A)wherebisB'slr-encryptionoraclebit.
TheonlyexceptionisthatBreturn⊥toAifAsubmitsanout-of-syncdecryptionquery.
Then,BoutputswhatAoutputs.
Similarly,IrunsAalmostexactlyasinExpind-sfcca-ASE(b)wherebisabitthatIchoosesatrandom.
Theonlyexceptionisthat,whenAsuccessfullysubmitsanout-of-syncdecryptionquery,theadversaryIterminates.
LetPr1[·]denotetheprobabilityoverExpind-sfcca-bSE(A)andarandomchoiceforb∈{0,1},andletbdenotetheoutputofAintheseexperiments.
LetPr2[·]denotetheprobabilityinExpint-sfctxtSE(I).
LetPr3[·]denotetheprobabilityoverExpind-cpa-cSE(B)wherecisrandomlyselectedfrom{0,1}andletcbethebitBreturns.
LetEdenotetheeventthatAmakesatleastonequerytoaphase1decryptionoraclethatwouldsuccessfullydecrypt.
NotethatPr1b=b∧E≤Pr1[E]≤Advint-sfctxtSE(I)since,priortoEoccurring,Expint-sfctxtSE(I)runsAexactlyasinExpind-sfcca-bSE(A)forarandomband,onceEoccurs,Isucceedsinforgingaciphertext.
AlsonotethatPr1b=b∧E≤Pr3c=c=12·PrExpind-cpa-1SE(B)=1+12·1PrExpind-cpa-0SE(B)=1=12Advind-cpaSE(B)+12sincewheneverAdoesnotcauseeventEtooccur,A'sviewwhenrunbyBisequivalenttoitsviewwhenruninExpind-sfcca-bSE(A).
Consequently,12Advind-sfccaSE(A)+12=Pr1b=b=Pr1b=b∧E+Pr1b=b∧E≤Advint-sfctxtSE(I)+12Advind-cpaSE(B)+12.
TheadversariesBandIusethesameresourcesasAexceptthatBdoesnotperformanychosen-ciphertextqueriestoadecryptionoracle.
CSSHProofsC.
1ProofofLemma6.
3First,weprovetherstinequalityinthetheorem.
Recallthatthepaddingischosenindependentlyatrandomfrom{0,1}mbplwherembplistheminimumpaddinglength.
Foracoll-cpaadversaryAtowin,itmustmakeatleasttwoencodingqueriesMi,Mjsuchthati=jandMit=Mjt.
Fromtheconstruction,thismeansthatthevaluesofthecountersandthepaddingsmustcollide(i.
e.
stin=stjnandpi=pj).
Foreachcountervalue,theprobabilitythatthepaddingscollideis2mbpl.
Thereare232possiblevaluesforthecounter,andeachvalueoccursatmostqe/232timesover29thecourseoftheexperiment.
Therefore,theprobabilitythatanycoll-cpaadversaryAmakingatmostqeencodingqueriescanwinisatmostqe·2322·232·2mbplAftersomesimplication,therstinequalityinthetheoremfollows.
Now,weprovethesecondequalityinthetheorem.
RecallthattheconstructioninFigure2speciesthatMt←stn32MefortheencodingandthatMt←stu32Meforthedecoding.
Sincethestatesstn,stuarecountersthataremaintainedinternallybytheoracles,noadversaryBcanhavecontroloverthem.
Sincebothstatesstartat0,ifBislimitedtofewerthan232encodingqueriesand232decodingqueries,thenitiseasytoseethatBcannotpossiblymaketwoqueriessatisfyingeitherofthersttwoconditionsintheexperimentExpcoll-ccaEC(B).
WenowturnourattentiontothelastconditionintheexperimentandarguethatBcannotpossiblysatisfyiteither.
SupposetowardacontradictionthatBcansomehowmakeaqueryMitoEnc(·)andaquerymjetoDec(·)suchthat(i=jorMi=mjorMie=mje)andMit=mjtwherei,j≤232.
FromFigure2,Mit=mjtimpliesthatMie=mjeandconsequentlythatMi=mj.
Therefore,forthisconditiontobesatisedimustbedierentfromj.
However,i,j≤232.
Therefore,i=jimpliesthatstin=stju.
Therefore,Mit=mjt,andwehaveacontradiction.
Thus,AdvcollccaEC(B)=0.
C.
2ProofofTheorem6.
5Equation(2)followsdirectlyfromProposition6.
2andLemma6.
4.
Now,weproveEquation(1).
LetSE=(K,E,D)bethecompositeencryptionscheme(SSH-CTRinthiscase)constructedviaConstruction6.
1fromtheencryptionschemeSE=(Ke,E,D),theMACschemeMA=(Kt,T,V),andtheencodingschemeEC=(Enc,Dec).
Consideranyint-sfctxtadversaryIagainstSE.
WeassociatetoIauf-cmaforgerFagainstMAandacoll-ccacollisionnderCagainstECasfollows.
TheforgerFusesKetogenerateanencryptionkeyandusestheencryptionkeyanditstaggingoracletoanswerI'squeriesinastraight-forwardmanner.
Inparticular,itfollowsConstruction6.
1.
Similarly,thecollisionnderCusesthesameapproach.
ThisensuresthatIisexecutedinthesameenvironmentasthatinExpint-sfctxtSE(I)untilIsucceedsinmakinganout-of-syncquery.
Recallthattheint-sfctxtadversaryIcanmaketwotypesofqueries:encryptionqueriestoEKanddecryption-vericationqueriestoDK.
SupposeImakesqeencryptionqueriesandqddecryption-vericationqueries.
WedenoteI'si-thquerytoEKasMi,theencodingofMiasMie,Mit,andthereturnedciphertextasσiτi.
WedenoteI'si-thquerytoDKasσiτi(assumingthatI'si-thqueryisparsablesinceotherwiseDKwouldenterahaltingstate).
Wedenotethedecryption(viaD)ofσiasmieandthedecodingofmieas(mi,mit).
Byconvention,ifDk'sinternalstateis⊥,thenmie=⊥.
Also,ifmie=⊥,then(mi,mit)Now,letjbetheindexofI'srstout-of-syncdecryptionquery,andletkbethenumberofencryptionqueriespriortoI'sj-thdecryptionquery.
LetBadbeaneventinwhichallofthefollowingconditionshold:I'sj-thdecryptionquerycorrectlyveries,mjt∈{M1tMkt},k≥j,τj=τj,andmje=Mje.
(Recallthatiftherstout-of-syncdecryptionqueryfailstoverify,thedecryptionalgorithmwillreturn⊥forallsubsequentdecryptionqueries.
)Westatethefollowinglemmas.
LemmaC.
1Advint-sfctxtSE(I)≤Advuf-cmaMA(F)+AdvcollccaEC(C)+Pr[Bad]LemmaC.
2Pr[Bad]=0Then,Equation(1)inTheorem6.
5follows.
Now,weprovethelemmas.
30ProofofLemmaC.
1:LetPr[·]denotetheprobabilityfunctionunderlyingExpint-sfctxtSE(I).
LetσjτjbeI'srstout-of-syncquerytoDK(·).
Recallthat,priortoI'sj-thdecryption-vericationquery,ImadekqueriestoEK(·).
Wedenethefollowingevents.
EventE:I'srstout-of-syncquerytoitsoracleDK(·)correctlyveriesEventE1:Eoccursandmjt∈{M1tMkt}EventE2:Eoccursandmjt∈{M1tMkt}EventE2,1:E2occursandeitherkIfI'srstout-of-syncquerytoDK(·)doesnotcorrectlyverify,thenthedecryptionoracleentersitshaltingstate,andthus,nofurtherdecryptionquerieswillcorrectlyverifyandExpint-sfctxtSE(I)cannotreturn1.
Therefore,Advint-sfctxtSE(I)=Pr[E].
Also,noticethatPr[E]=Pr[E1∨E2,2,1]+Pr[E2,1∨E2,2,2]+Pr[E2,2,3].
Aspreviouspointedout,theadversariesFandCrunIexactlyasinExpint-sfctxtSE(I)untilIsucceedsinmakinganout-of-syncdecryption-vericationquery.
Therefore,itiseasytoseethat,ifeventsE1orE2,2,1occur,thenFsucceedsinndingauf-cmaforgeryagainstMA.
Similarly,ifeventsE2,1orE2,2,2occur,CsucceedsinndingacollisionagainstEC.
Consequently,Advint-sfctxtSE(I)=Pr[E1∨E2,2,1]+Pr[E2,1∨E2,2,2]+Pr[E2,2,3]≤Advuf-cmaMA(F)+AdvcollccaEC(C)+Pr[Bad]asdesired.
ProofofLemmaC.
2:Weareinterestedintheeventthatσj=σjbutmje=Mje(wherejistheindexoftherstout-of-orderdecryptionqueryandtheadversaryhasalreadyqueriedtheencryptionoracleatleastjtimes).
SinceSSH-CTRusesCTRmodewithstatefuldecryption,sincetheencryptionanddecryptionstatesarein-syncpriortothej-thdecryptionquery,andsince,foreachCTRmodestate,thereisabijectionbetweenplaintextsandciphertexts,ifσj=σj,thenmje=Mje.
ThismeansthatPr[Bad]=0.
31