512比特的大整数的有效分解的利用Factoring as a Service

FactoringasaService13

Table2:HTTPSRSAcommonkeylengthsandexportRSAsupport.

Length5127681024153620482432307240968192RSAExportTotal

AllCertificatesDistinctKeysTrustedCertificates303,199(0.9%)26,582(0.1%)12,541,661(36.8%)

2,537(0.0%)

20,782,686(60.9%)

2,685(0.0%)65,765(0.2%)391,123(1.1%)2,172(0.0%)2,630,789(7.7%)34,121,474(100.0%)

14,680,782(43.0%)14,678,739(43.0%)

TrustedandValid

32,8700(0.0%)0(0.0%)14,5810(0.0%)0(0.0%)3,196,1694,016(0.0%)4,012(0.0%)

2,1080(0.0%)0(0.0%)6,891,67814,413,589(42.2%)14,411,618(42.2%)

1,191128(0.0%)128(0.0%)58,4321,787(0.0%)1,787(0.0%)218,334259,898(0.8%)259,830(0.8%)

971481(0.0%)481(0.0%)

theseserversarealsovulnerabletoanactiveman-in-the-middleattackfromanadversarywhosimplyreplacesthecertificate.

IftheclientandservernegotiateaDiffie-HellmanorellipticcurveDiffie-Hellmanciphersuite,theserverusesthepublickeyinitscertificatetosignitskeyexchangeparameterstoprovideauthentication.Anadversarywhoknowstheprivatekeycouldcarryoutaman-in-the-middleattackbyforgingacorrectsignatureontheirdesiredparameters.Sinceagainno512-bitcertificatesarecurrentlysignedortrusted,suchanactiveadversarycouldalsomerelyreplacetheservercertificateintheexchangealongwiththechosenDiffie-Hellmanparameters.Finally,connectionstoserverssupportingRSA_EXPORTciphersuitesmaybevulnerabletoanactivedowngradeattackiftheclientshavenotbeenpatchedagainsttheFREAKattack.[6]Successfullycarryingoutthisattackrequirestheattackertofactortheserver’sephemeralRSAkey,whichistypicallygeneratedwhentheserverapplicationlaunchesandisreusedaslongastheserverisup.“Ephemeral”RSAkeyscanpersistforhours,days,orweeksandarealmostalways512bitsinlength.

WeexaminedIPv4scanresultsforHTTPSonport443performedusingZmap[16]bytheUniversityofMichiganwhichweaccessedviaScans.ioandtheCensysscandatasearchinterfacedevelopedbyDurumeric,Adrian,Mirian,Bailey,andHalderman[13].Table2summarizesscansfromAugust23andSeptember1,2015.

Durumeric,Kasten,Bailey,andHalderman[15]examinedtheHTTPScer-tificateinfrastructurein2013usingfullIPv4surveysandfound2,631browser-trustedcertificateswithkeylengthsof512bitsorsmaller,ofwhich16werevalid.Heninger,Durumeric,Wustrow,andHalderman[19]performedafullIPv4scanofHTTPSinOctober2011withresponsesfrom12.8millionhosts,andfound123,038certificates(trustedandnon-trusted)containing512-bitRSAkeys.Similarto[19],weobservemanyrepeatedpublickeys.

14Valenta,Cohney,Liao,Fried,Bodduluri,Heninger

Table3:Mailprotocolkeylengths.

PortHandshake

SMTPIMAPSPOP3S

25993995

RSA_EXPORT512-bitCertificateKey

64(0%)102(0%)115(0%)

4,821,6151,483,955(30.8%)4,468,577561,201(12.6%)4,281,494558,012(13.0%)

5.3Mail

Table3summarizesseveralInternet-widescanstargetingSMTP,IMAPS,andPOP3S.ThescanswereperformedbytheUniversityofMichiganusingZmapbetweenAugust23,2015,andSeptember3,2015.

WeusedtheCensysscandatabaseinterfaceprovidedby[13]toanalyzethedata.WhileonlyafewhundredfewmailserversservedTLScertificatescontaining512-bitRSApublickeys,13%ofIMAPSandPOP3Sserversand30%ofSMTPserverssupportedRSA_EXPORTciphersuiteswith512-bitephemeralRSA,meaningthatunpatchedclientsarevulnerabletotheFREAKdowngradeattackbyanadversarywiththeabilitytoquicklyfactora512-bitRSAkey.

WealsoexaminedDKIMpublickeys.DomainKeysIdentifiedMail[2]isapublickeyinfrastructureintendedtopreventemailspoofing.PublickeysarepublishedbydomainsinaDNStextrecord,andmailprovidersattachdigitalsignaturestooutgoingmail,allowingrecipientstoverifyincomingmessages.

WegatheredDKIMpublickeysfromtheRapid7DNSdataset.However,thepublisheddatasethadlowercasedthebase64-encodedkeyentries,soinTable4:

ordertoexaminepublickeysweperformedDNSDKIMkeysizes.lookupsonthe11,600domainscontainingDKIMrecordsourselvesonSeptember4,2015.WemadeaLengthKeysbest-effortattempttoparsetherecords,but5%of40965(0.0%)

theresponsescontainedakeythatwasmalformedor204864(0.5%)

truncatedandcouldnotbeparsed.Oftheremainder,10281(0.0%)

124domainsused512-bitkeysorsmaller,including102410,726(92.2%)

onethatuseda128-bitRSApublickey.Wewere768126(1.1%)

abletofactorthiskeyinlessthanasecondona512103(0.9%)

laptopandverifythatitis,infact,averyshortRSA38420(0.2%)

publickey.Table4summarizesthedistribution.

1281(0.0%)

Durumeric,Adrian,Mirian,Kasten,Bursztein,591(5.1%)Lidzborski,Thomas,Eranti,Bailey,andHalder-Parseerror

man[14]surveyedcryptographicfailuresinemailTotal11,637protocolsusingInternet-widescansanddatafromGoogle.TheyexamineDKIMusefromtheperspec-tiveofGmail’sserversinApril2015anddiscoveredthat83%ofmailreceivedbyGmailcontainedaDKIMsignature,butofthese,6úiledtovalidate.Ofthesefailures,15%wereduetoakeysizeoflessthan1024bits,and63%wereduetoothererrors.

FactoringasaService15

5.4IPsec

WeconductedtwoZmapscansofthefullIPv4spacetosurveykeysizesinusebyIPsecVPNimplementa-tionsthatuseRSAsignaturesforidentityvalidationTable5:IPsecVPNcer-duringserver-clienthandshakes.Anadversarywhotificatekeyscompromisedtheprivatekeysforoneofthesecer-tificatescouldmountanactiveman-in-the-middleLengthKeysattack.

409637(0.8%)

OurZmapscanstargetedIKEv1aggressive30721(0.0%)

mode[18],whichminimizesthenumberofmessages20482,257(51.3%)

sentbetweentheserverandclientandallowsthe10241,804(41.0%)

servertosendacertificateafteraonlyasinglemes-7681(0.0%)

sageisreceived.Themessageswesentcontained51269(1.6%)

proposalsforDES,3DES,AES-128,andAES-256eachwithbothSHA1andMD5.Ourfirstscanof-Parseerror234(5.3%)feredakeyexchangeusingOakleygroup2(a1024-Total4,403(100%)bitDiffie-Hellmangroup)andelicitedcertificatesfrom4%oftheserversthatacceptedourmessage.OursecondscanofferedOakleygroup1(a768-bitDiffie-Hellmangroup)andreceivedresponsesfrom0.2%ofhosts.Ofthenon-responsesfrombothscans,71%oftheserversrespondedindicatingthattheydidnotsupportourcombinationofaggressivemodewithourchosenparameters,16%rejectedourconnectionforbeingunauthorized(notonawhitelist),andtheremaining11%returnedothererrors.5.5

SSH

SSHhostsauthenticatethemselvestotheclientbysigningtheprotocolhandshakewiththeirpublichostkey.Clientsmatchthehostkeytoastoredtrustedfingerprint.AnadversarywhoisabletocompromisetheprivatekeyforanSSHhostkeycanperformanactiveman-in-the-middleattack.

Table6summarizeshostkeysizescollectedbyaZmapscanofSSHhostsonport22mimickingOpenSSH6.6.1p1.ThedatawascollectedinApril2015byAdrianetal.[1],whoprovidedittous.Averylargenum-berofhostsused1040-bitkeys;thesehostshadbannersidentifyingthemasusingDropbear,alightweightSSHimplementationaimedatembeddedTable6:SSHhostkeylengths.

RSASize5127687841020102410401536204820644096RSATotalDSAECDSA

Hosts

Distinct

508(0.0%)3162,972(0.0%)2,4193,119(0.0%)223774(0.0%)572296,229(4.4%)91,7882,786,574(41.3%)1,407,922

639(0.0%)536

3,632,865(53.9%)1,752,406

1,612(0.0%)95715,235(0.2%)1,269

6,741,3523,258,742692,0112,192

421,9442,192

16Valenta,Cohney,Liao,Fried,Bodduluri,Heninger

devices.Heninger,Durumeric,Wustrow,andHalderman[19]performedafullIPv4scanofSSHpublickeysinFebruary2012offeringonlyDiffie-HellmanGroup1keyexchange.Of10millionresponses,theyreportedthat8,459used512-bitRSAhostkeysandobservedmanyrepeatedhostkeys.

Clientscanalsousepublickeystoauthenticatethemselvestoaserver.AnadversarywhoisabletocompromisetheprivatekeyforaclientSSHauthentica-tionkeycanaccesstheserverbylogginginastheclient.BenCox[10]collected1,376,262SSHpublickeysthathadbeenuploadedtoGitHubbyuserstoau-thenticatethemselvestotheservicebetweenDecember2014andJanuary2015byusingGitHub’spublicAPI.Hecollected1,205,330RSApublickeys,27,683DSApublickeys,and1,060ECDSApublickeys.OftheRSApublickeys,2had256-bitlength,3had512-bitlength,and28had768-bitlength.

5.6PGP

1000001000010001001011199Keyscreated512768102420483072409651990200200520102015Figure5:PGPRSApublickeylengthsbyreportedcreationdate.

PGPimplementsencryptionanddigitalsignaturesonemailorfiles.RSApublickeyscanbeusedforbothencryptionandsignatures.PGPisdesignedtouseapublic“weboftrust”model:userscandistributetheirpublickeysalongwithsignaturesattestingtrustrelationshipsviaapublicnetworkofkeyservers.AnadversarywhocompromisesaPGPpublickeycoulduseittoimpersonateauserwithadigitalsignatureordecryptcontentencryptedtothatuser.WedownloadedaPGPkeyserverbootstrapdatasetfromkeyserver.borgnet.usonOctober4,2015.Itcontained4.9millionpublickeysfrom3millionusers.Ofthese,1.6millionwereRSA,1.7millionwereDSA,1.7millionwereElGamal,398wereECDH,158wereEdDSA,and513wereECDSA.Figure5showstheshifttolongerRSAkeylengthsovertime.