Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice David Adrian¶ Karthikeyan Bhargavan∗ Zakir Durumeric¶ Pierrick Gaudry† Matthew Green§ J. Alex Halderman¶ Nadia Heninger‡ Drew Springall¶ Emmanuel Thomé† Luke Valenta‡ Benjamin VanderSloot¶ Eric Wustrow¶ Santiago Zanella-Béguelink Paul Zimmermann† ∗INRIAParis-Rocquencourt †INRIANancy-GrandEst,CNRS,andUniversitédeLorraine kMicrosoftResearch ‡UniversityofPennsylvania §JohnsHopkins ¶UniversityofMichigan Foradditionalmaterialsandcontactinformation,visitWeakDH.org. ABSTRACT coded, or widely shared Diffie-Hellman parameters has the effectofdramaticallyreducingthecostoflarge-scaleattacks, WeinvestigatethesecurityofDiffie-Hellmankeyexchangeas bringing some within range of feasibility today. usedinpopularInternetprotocolsandfindittobelesssecure The current best technique for attacking Diffie-Hellman than widely believed. First, we present Logjam, a novel flaw relies on compromising one of the private exponents (a, b) inTLSthatletsaman-in-the-middledowngradeconnections by computing the discrete log of the corresponding public to “export-grade” Diffie-Hellman. To carry out this attack, value (ga modp, gb modp). With state-of-the-art number we implement the number field sieve discrete log algorithm. fieldsievealgorithms,computingasinglediscretelogismore After a week-long precomputation for a specified 512-bit difficult than factoring an RSA modulus of the same size. group, we can compute arbitrary discrete logs in that group However,anadversarywhoperformsalargeprecomputation inaboutaminute. Wefindthat82%ofvulnerableserversuse foraprimepcanthenquicklycalculatearbitrarydiscretelogs asingle512-bitgroup,allowingustocompromiseconnections inthatgroup,amortizingthecostoveralltargetsthatshare to7%ofAlexaTopMillionHTTPSsites. Inresponse,major this parameter. Although this fact is well known among browsers are being changed to reject short groups. mathematical cryptographers, it seems to have been lost WegoontoconsiderDiffie-Hellmanwith768-and1024-bit among practitioners deploying cryptosystems. We exploit it groups. Weestimatethateveninthe1024-bitcase,thecom- to obtain the following results: putationsareplausiblegivennation-stateresources. Asmall number of fixed or standardized groups are used by millions Active attacks on export ciphers in TLS. We introduce of servers; performing precomputation for a single 1024-bit Logjam,anewattackonTLSbywhichaman-in-the-middle group would allow passive eavesdropping on 18% of popular attacker can downgrade a connection to export-grade cryp- HTTPS sites, and a second group would allow decryption tography. ThisattackisreminiscentoftheFREAKattack[7] of traffic to 66% of IPsec VPNs and 26% of SSH servers. A butappliestotheephemeralDiffie-Hellmanciphersuitesand closereadingofpublishedNSAleaksshowsthattheagency’s isaTLSprotocolflawratherthananimplementationvulner- attacks on VPNs are consistent with having achieved such ability. Wepresentmeasurementsthatshowthatthisattack a break. We conclude that moving to stronger key exchange applies to 8.4% of Alexa Top Million HTTPS sites and 3.4% methods should be a priority for the Internet community. of all HTTPS servers that have browser-trusted certificates. To exploit this attack, we implemented the number field 1. INTRODUCTION sieve discrete log algorithm and carried out precomputation for two 512-bit Diffie-Hellman groups used by more than Diffie-Hellman key exchange is widely used to establish 92% of the vulnerable servers. This allows us to compute sessionkeysinInternetprotocols. Itisthemainkeyexchange individualdiscretelogsinaboutaminute. Usingourdiscrete mechanism in SSH and IPsec and a popular option in TLS. logoracle,wecancompromiseconnectionstoover7%ofTop We examine how Diffie-Hellman is commonly implemented Million HTTPS sites. Discrete logs over larger groups have and deployed with these protocols and find that, in practice, been computed before [8], but, as far as we are aware, this it frequently offers less security than widely believed. is the first time they have been exploited to expose concrete There are two reasons for this. First, a surprising number vulnerabilities in real-world systems. of servers use weak Diffie-Hellman parameters or maintain We were also able to compromise Diffie-Hellman for many support for obsolete 1990s-era export-grade crypto. More otherserversbecauseofdesignandimplementationflawsand critically, the common practice of using standardized, hard- configurationmistakes. Theseincludeuseofcomposite-order subgroups in combination with short exponents, which is vulnerabletoaknownattackofvanOorschotandWiener[51], Permissiontomakedigitalorhardcopiesofpartorallofthisworkforpersonalor andtheinabilityofclientstoproperlyvalidateDiffie-Hellman classroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributed parameterswithoutknowingthesubgrouporder,whichTLS forprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcita- has no provision to communicate. We implement these tiononthefirstpage. Copyrightsforthird-partycomponentsofthisworkmustbe attacks too and discover several vulnerable implementations. honored. Forallotheruses,contacttheOwner/Author(s). Copyrightisheldbythe owner/author(s). Risks from common 1024-bit groups. We explore the im- CCS’15,October12–16,2015,Denver,Colorado,USA. plications of precomputation attacks for 768- and 1024-bit ACM978-1-4503-3832-5/15/10. groups,whicharewidelyusedinpracticeandstillconsidered DOI:http://dx.doi.org/10.1145/2810103.2813707. polynomial sieving linear descent selection algebra y,g p log db x precomputation individual log Figure 1: The number field sieve algorithm for discrete log consists of a precomputation stage that depends only on the prime p and a descent stage that computes individual logs. With sufficient precomputation, an attacker can quickly break any Diffie-Hellman instances that use a particular p. secure. We provide new estimates for the computational re- sievealgorithmforfactoring[12,31],andinfactmanypartsof sourcesnecessarytocomputediscretelogsingroupsofthese theimplementationscanbeshared. Thegeneraltechniqueis sizes,concludingthat768-bitgroupsarewithinrangeofaca- calledindexcalculusandhasfourstageswithdifferentcompu- demic teams, and 1024-bit groups may plausibly be within tational properties. The first three steps are only dependent range of state-level attackers. In both cases, individual logs on the prime p and comprise most of the computation. can be quickly computed after the initial precomputation. First is polynomial selection, in which one finds a polyno- We then examine evidence from published Snowden docu- mialf(z)defininganumberfieldQ(z)/f(z)forthecomputa- mentsthatsuggestsNSAmayalreadybeexploiting1024-bit tion. (For our cases, f(z) typically has degree 5 or 6.) This Diffie-HellmantodecryptVPNtraffic. Weperformmeasure- parallelizes well and is only a small portion of the runtime. ments to understand the implications of such an attack for In the second stage, sieving, one factors ranges of integers popularprotocols,findingthatanattackerwhocouldperform andnumberfieldelementsinbatchestofindmanyrelationsof precomputations for ten 1024-bit groups could passively de- elements,allofwhoseprimefactorsarelessthansomebound crypttraffictoabout66%ofIKEVPNs,26%ofSSHservers, B (calledB-smooth). Modernimplementationsusespecial-q 16% of SMTP servers, and 24% of popular HTTPS sites. lattice sieving, which for each special q explores a sieving Mitigations and lessons. As a short-term countermeasure region of 22I candidates, where I is a parameter. Sieving parallelizeswellsinceeachspecialqishandledindependently in response to the Logjam attack, all mainstream browsers of the others, but is computationally expensive, because we are implementing a more restrictive policy on the size of must search through and attempt to factor many elements. Diffie-Hellman groups they accept. We further recommend The time for this step depends on heuristic estimates of that TLS servers disable export-grade cryptography and the probability of encountering B-smooth numbers in this carefully vet the Diffie-Hellman groups they use. In the search; it also depends on I and on the number of special q longer term, we advocate that protocols migrate to stronger to consider before having enough relations. Diffie-Hellmangroups,suchasthosebasedonellipticcurves. In the third stage, linear algebra, we construct a large, sparse matrix consisting of the coefficient vectors of prime 2. DIFFIE-HELLMANCRYPTANALYSIS factorizations we have found. A nonzero kernel vector of the Diffie-Hellmankeyexchangewasthefirstpublishedpublic- matrix modulo the order q of the group will give us logs of key algorithm [14]. In the simple case of prime groups, many small elements. This database of logs serves as input Alice and Bob agree on a prime p and a generator g of a tothefinalstage. Thedifficultydependsonqandthematrix multiplicative subgroup modulo p. Alice sends ga modp, size and can be parallelized in a limited fashion. Bob sends gb modp, and each computes a shared secret The final stage, descent, actually deduces the discrete log gab modp. While there is also a Diffie-Hellman exchange ofthetargety. Were-sieveuntilwecanfindasetofrelations over elliptic curve groups, we address only the “mod p” case. thatallowustowritethelogofy intermsofthelogsinthe The security of Diffie-Hellman is not known to be equiva- precomputed database. This step is accomplished in three lenttothediscretelogproblem(exceptincertaingroups[13, phases: aninitializationphase,whichtriestowritethetarget 33,34]),butcomputingdiscretelogsremainsthebestknown in terms of medium-sized primes, a middle phase, in which cryptanalytic attack. An attacker who can find the discrete these medium-sized primes are further sieved until they can log x from y=gx modp can easily find the shared secret. be represented by elements in the database of known logs, Textbook descriptions of discrete log can be misleading and a final phase that actually reconstructs the target using aboutthecomputationaltradeoffs,forexamplebybalancing the log database. Crucially, descent is the only NFS stage parameters to minimize overall time to compute a single that involves y (or g), so polynomial selection, sieving, and discrete log. In fact, as illustrated in Figure 1, a single large linear algebra can be done once for a prime p and reused to precomputation on p can be used to efficiently break all compute the discrete logs of many targets. Diffie-Hellman exchanges made with that prime. Thetypicalcase Diffie-Hellmanistypicallyimplemented 1Recent spectacular advances in discrete log algorithms with prime fields and large group orders. In this case, the have resulted in a quasi-polynomial algorithm for small- mostefficientdiscretelogalgorithmisthenumberfieldsieve characteristic fields [3], but these advances are not known to (NFS) [21,24,43].1 There is a closely related number field apply to the prime fields used in practice. 2 TherunningtimeofthisalgorithmisLp(1/3,(64/9)1/3)= Source Popularity Prime | (cid:0) (1.923+o(1))(logp)1/3(loglogp)2/3 | | | | | (cid:1) | | | | | | | | | | | | ----------------------------------------- | --- | --- | --- | --- | ------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | exp . This is obtained Apache 82% 9fdb8b8a004544f0045f1737d0ba2e0b by tuning many parameters, including the degree of f, the 274cdf1a9f588218fb435316a16e3741 sieving region parameter I, and, most importantly, the 71fd19d8d8f37c39bf863fd60e3e3006 80a3030c6e4c3757d08f70e6aa871033 | smoothness | bound | B. | Early | articles | (e.g. | [21]) encountered | | | | | | | | | | | ---------- | ----- | --- | ----- | -------- | ----- | ----------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | technicaldifficultieswithdescentandreportedthatthecom- mod_ssl 10% d4bcd52406f69b35994b88de5db89682 plexity of this step would equal that of the precomputation; c8157f62d8f33633ee5772f11f05ab22 d6b5145b9f241e5acc31ff090a4bc711 thismayhavecontributedtomisconceptionsabouttheperfor- 48976f76795094e71e7903529f5a824b | manceoftheNFSfordiscretelogs. | | | | Morerecentanalyseshave | | | | | | | | | | | | | ----------------------------- | ---------------- | ---------- | --------- | ---------------------- | ------------- | ------- | ----- | --------------------------------- | ------ | ------- | ------------------- | ----------- | ------- | ----------- | ----- | | | | | | | Lp(1/3,1.442) | | | (others) | 8% | | (463distinctprimes) | | | | | | improved | the | complexity | of | descent | to | | [10], | | | | | | | | | | and later | to Lp(1/3,1.232) | | [2], | which | is much | cheaper | than | | | | | | | | | | | | | | | | | | Table1: Top512-bitDHprimesforTLS. | | | | | | 8.4%ofAlexa | | | the precomputation | | in | practice. | | | | | | | | | | | | | | | | | | | | | | Top 1M HTTPS | | domains | allow | DHE_EXPORT, | | of | which | | The numerous | | parameters | | of the | algorithm | allow | some | | | | | | | | | | | | | | | | | | 92.3% use | one of | the two | most | popular | primes, | shown | here. | flexibilitytoreducetimeonsomecomputationalstepsatthe | expense | of others. | For | example, | sieving | more | will | result in | | | | | | | | | | ------------ | ---------- | ------------------ | ----------------- | -------------- | ----------- | --------- | --------- | ---------------- | ------- | ---------------- | --------- | --------------- | ------------ | ------- | -------- | | a smaller | matrix, | making | linear | algebra | cheaper, | | and doing | | | | | | | | | | | | | | | | | | for both normal | | and export-grade | | Diffie-Hellman, | | | the vast | | more work | in | the precomputation | | | makes | the final | descent | | | | | | | | | | | | | | | | | | majority of | servers | use | a handful | of common | | groups. | | | step easier. | In | §3.3, we | show | how exploiting | | these | tradeoffs | | | | | | | | | | | | | | | | | | In this section, | | we exploit | these | facts | to construct | | a novel | | allows us | to quickly | compute | | 512-bit | discrete | logs | in order | | | | | | | | | | | | | | | | | | attack against | TLS, | which | we | call the | Logjam | attack. | First, | | to perform | an | effective | man-in-the-middle | | | attack | on TLS. | | | | | | | | | | | | | | | | | | we perform | NFS | precomputations | | for | the two | most | popular | | Improperly | | generated | groups | | A different | | family of | | | | | | | | | | | | | | | | | | 512-bit primes | on | the web, | so | that we | can quickly | compute | | algorithmsrunsintimeexponentialingrouporder,andthey | | | | | | | | | the discrete | log for | any | key-exchange | message | | that uses | one | | ------------- | ---- | --- | ------------ | --- | ---- | --------- | -------- | -------------- | ------- | ---- | ------------ | ------------------ | --- | --------- | ------ | | are practical | even | for | large primes | | when | the group | order is | | | | | | | | | | | | | | | | | | of them. Next, | we | show | how a | man-in-the-middle, | | so | armed, | small or has many small prime factors. To avoid this, most can attack connections between popular browsers and any implementations use “safe” primes, which have the property server that allows export-grade Diffie-Hellman, by using a that p−1=2q for some prime q, so that the only possible TLS protocol flaw to downgrade the connection to export- subgroups have order 2, q, or 2q. However, as we show in strength and then recovering the session key. We find that §3.5, improperly generated groups are sometimes used in thisattackwithourprecomputationscancompromiseabout practice and susceptible to attack. 7.8% of HTTPS servers among Alexa Top Million domains. | The baby-step | | giant-step | | [45] and | Pollard | rho | [42] algo- | | | | | | | | | | ------------- | ---- | ---------- | ----- | -------- | ---------- | ---- | ---------- | ------------------------ | --- | --- | --- | --- | --- | --- | --- | | | | √ | | | | | | 3.1 TLSandDiffie-Hellman | | | | | | | | | rithms both | take | q time | to | compute | a discrete | | log in any | | | | | | | | | | (sub)group | of | √order q, | while | Pollard | lambda | [42] | can find | | | | | | | | | TheTLShandshakebeginswithanegotiationtodetermine | x < t in | time | t. These | parallelize | | well | [50], and | precom- | | | | | | | | | | -------- | --------- | -------- | ----------- | --- | ----------------- | --------- | ------- | ------------------------------------- | --- | --- | --- | --- | --------------- | --- | --- | | | | | | | | | | thecryptoalgorithmsusedforthesession. | | | | | Theclientsendsa | | | | putation | can speed | up | individual | | log calculations. | | If the | | | | | | | | | listofsupportedciphersuites(andarandomnoncecr)within q factorization of the subgroup order is known, one can theClientHellomessage,whereeachciphersuitespecifiesakey use any of the above algorithms to compute the discrete exchange algorithm and other primitives. The server selects ei log in each subgroup of order q dividing q, and then re- aciphersuitefromtheclient’slist andsignalsitsselectionin i cover x using the Chinese remainder theore m. T his is the a ServerHello message (containing a random nonce sr). | | | | | | | P | √ | | | | | | | | | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | Pohlig-Hellman algorithm [41], which costs ei qi using TLS specifies ciphersuites supporting multiple varieties of i baby-step giant-step or Pollard rho. Diffie-Hellman. Textbook Diffie-Hellman with unrestricted | | | | | | | | | strength is | called | “ephemeral” | | Diffie-Hellman, | | or DHE, | and | | -------------- | --- | --- | ---------------------------------- | --- | --- | --- | --- | ------------- | --------------- | ----------- | ---- | --------------- | ---------------- | ------- | --- | | Standardprimes | | | Generatingprimeswithspecialproper- | | | | | | | | | | | | | | | | | | | | | | is identified | by ciphersuites | | that | begin | with TLS_DHE_*.2 | | In | tiescanbecomputationallyburdensome,somanyimplemen- tations use fixed or standardized Diffie-Hellman parameters. DHE,theserverisresponsibleforselectingtheDiffie-Hellman Itchoosesagroup(p,g),computesgb,andsends | A prominent | example | | is the | Oakley | groups | [40], | which give | parameters. | | | | | | | | | ----------- | ------- | --- | ------ | ------ | ------ | ----- | ---------- | ----------- | --- | --- | --- | --- | --- | --- | --- | “safe” primes of length 768 (Oakley Group 1), 1024 (Oakley aServerKeyExchangemessagecontainingasignatureoverthe (cr,sr,p,g,gb) Group 2), and 1536 (Oakley Group 5). These groups were tuple using the long-term signing key from published in 1998 and have been used for many applications its certificate. The client verifies the signature and responds since, including IKE, SSH, Tor, and OTR. with a ClientKeyExchange message containing ga. | | | | | | | | | To ensure | agreement | | on the | negotiation | messages, | | and to | | ---------------------------- | -------------- | ------------ | ------------ | ----------------------- | ---------------- | ----------- | ----------- | ---------------------- | --------- | ----------- | -------------------------- | ------------ | --------- | --------------- | ------ | | When | primes | are of | sufficient | strength, | | there seems | to be | | | | | | | | | | | | | | | | | | prevent downgrade | | attacks | [52], | each | party | computes | the | | nodisadvantagetoreusingthem. | | | | However,widespreadreuse | | | | | | | | | | | | | | | | | | | | | TLSmastersecretfromgab | | | andcalculatesaMACofitsview | | | | | | of Diffie-Hellman | | groups | can | convert | attacks | that | are at the | | | | | | | | | | | | | | | | | | of the handshake | | transcript. | | These MACs | | are exchanged | | | limits of | an adversary’s | | capabilities | | into devastating | | breaks, | | | | | | | | | | | | | | | | | | in a pair of | Finished | messages | | and verified | by | the recipients. | | | since it | allows | the attacker | to | amortize | the | cost | of discrete | | | | | | | | | logprecomputationamongvastnumbersofpotentialtargets. Thereafter, client and server start exchanging application | | | | | | | | | data, protected | by | an authenticated | | encryption | | scheme | with | | --- | --- | --- | --- | --- | --- | --- | --- | --------------- | --- | ---------------- | --- | ---------- | --- | ------ | ---- | gab. | | | | | | | | | keys also derived | | from | | | | | | | --- | --- | --- | --- | --- | --- | --- | --- | ----------------- | --- | ---- | --- | --- | --- | --- | --- | 3. ATTACKINGTLS Tocomplywith1990s-eraU.S.exportrestrictionsoncryp- TLS supports Diffie-Hellman as one of several possible tography, SSL 3.0 and TLS 1.0 supported reduced-strength | key exchange | | methods, | and | about | two-thirds | | of popular | | | | | | | | | | ------------ | --- | -------- | --- | ----- | ---------- | --- | ---------- | --------- | -------- | --- | ------ | ------------- | -------------- | --- | --- | | | | | | | | | | 2TLS also | supports | a | rarely | used “static” | Diffie-Hellman | | | HTTPSsitesallowit,mostcommonlyusing1024-bitprimes. | | | | | | | | | format, where | the | server’s | key | exchange | value | is fixed | and | | -------- | --------- | ------ | --- | ---------- | ---- | ------- | ------ | -------------------------- | --- | -------- | ------------------------------ | -------- | ----- | -------- | --- | | However, | a smaller | number | | of servers | also | support | legacy | | | | | | | | | | | | | | | | | | containedinitscertificate. | | | Newciphersuitesthatuseelliptic | | | | | “export-grade” Diffie-Hellman using 512-bit primes that are curve Diffie-Hellman (ECDHE) are gaining in popularity, but well within reach of NFS-based cryptanalysis. Furthermore, we focus exclusively on the traditional prime field variety. 3 | | | | | | | | negotiate | export-grade | | ciphersuites. | To | circumvent | | this, we | | --- | --- | --- | --- | --- | --- | --- | --------------- | ------------ | ------------- | ------------- | ----------- | ----------- | ---------- | -------- | | | | | | | | | show how | an | attacker | who can | compute | 512-bit | | discrete | | | | | | | | | in real | time | | | | | | | | | | | | | | | logs | | can downgrade | | a regular | DHE | connection | | | | | | | | | | to use a | DHE_EXPORT | | group, | and thereby | | break | both the | | | | | | | | | confidentiality | | and integrity | of | application | data. | | | | | | | | | | | The attack, | | which we | call Logjam, | | is depicted | in | Figure 2 | | | | | | | | | and relies | on | a flaw in | the way | TLS | composes | | DHE and | | | | | | | | | DHE_EXPORT. | | When a | server | selects | DHE_EXPORT | | for a | handshake,itproceedsbyissuingasignedServerKeyExchange | | | | | | | | message | containing | a 512-bit | p512, | but | the structure | | of this | | --- | --- | --- | --- | --- | --- | --- | ------- | ---------- | --------- | ----- | --- | ------------- | --- | ------- | messageisidenticaltothemessagesentduringstandardDHE | | | | | | | | ciphersuites. | | Critically, | the signed | portion | | of the | server’s | | --- | --- | --- | --- | --- | --- | --- | ---------------------------- | -------- | ----------- | -------------- | ------------------------- | ------ | -------- | -------- | | | | | | | | | message | fails to | include | any indication | | of the | specific | cipher- | | | | | | | | | suitethattheserverhaschosen. | | | | Providedthataclientoffers | | | | DHE,anactiveattackercanrewritetheclient’sClientHelloto | Figure 2: | The Logjam | attack. | A | man-in-the-middle | | can | | | | | | | | | | --------- | -------------- | --------------- | --- | ----------------- | ---- | ---------- | --------------------- | --- | ---------- | --- | ----------- | --- | -------- | --- | | | | | | | | | offer a corresponding | | DHE_EXPORT | | ciphersuite | | accepted | by | | force TLS | clients to use | export-strength | | DH | with | any server | | | | | | | | | theserverandremoveotherciphersuitesthatcouldbechosen | that allows | DHE_EXPORT. | Then, | by | finding | the 512-bit | dis- | | | | | | | | | | ----------- | ----------- | ----- | --- | ------- | ----------- | ---- | -------- | ------------ | --- | -------- | --------------- | --- | -------- | --- | | | | | | | | | instead. | The attacker | | rewrites | the ServerHello | | response | to | cretelog,theattackercanlearnthesessionkeyandarbitrarily | | | | Datafs | | | | replacethechosenDHE_EXPORTciphersuitewithamatching | | | | | | | | | ------------------------ | --- | --- | ------ | ---------------------- | --- | --- | -------------------------------------------------- | ----------- | --- | ------------ | --- | ----------------- | --- | --- | | readormodifythecontents. | | | | referstoFalseStart[30] | | | | | | | | | | | | | | | | | | | non-export | ciphersuite | | and forwards | the | ServerKeyExchange | | | applicationdatathatsomeTLSclientssendbeforereceiving | | | | | | | | message | to the | client | as is. The | client | will | interpret | the | | ------------ | ----------------- | --- | --- | --- | --- | --- | ------------ | ---------- | ----------- | ---------- | -------- | -------------- | ---------- | ---- | | the server’s | Finished message. | | | | | | | | | | | | | | | | | | | | | | export-grade | tuple | (p512,g,gb) | | as valid | DHE | parameters | cho- | | | | | | | | | sen by | the server | and | proceed | with | the handshake. | | The | DHE_EXPORT ciphersuites that were restricted to primes no clientandserverhavedifferenthandshaketranscriptsatthis | | | | | | | | stage, but | an | attacker | who can | compute | b | in close | to real | | ---------------- | ------------------ | ---------- | --------- | -------------- | ---------- | ---------- | ---------------- | ------- | ----------- | ---------- | ---------- | --------------- | ---------- | -------- | | longer than | 512 bits. | In all | other | respects, | DHE_EXPORT | | | | | | | | | | | | | | | | | | time can | then | derive the | master | secret | and | connection | keys | | protocol | messages are | identical | to DHE. | The | relevant | export | | | | | | | | | | | | | | | | | to complete | the | handshake | with | the | client, | and then | freely | | restrictions | are no longer | in | effect, | but many | libraries | and | | | | | | | | | | | | | | | | | read and | write | application | data | pretending | | to be the | server. | | servers maintain | support | for | backwards | compatibility. | | Many | | | | | | | | | | | | | | | | | There | are two | remaining | challenges | | in implementing | | this | | TLS servers | are still | configured | with | two | groups: | a strong | | | | | | | | | | | | | | | | | active downgrade | | attack. | The | first is | to compute | individual | | | 1024-bit | group for regular | DHE | key | exchanges | and | a 512-bit | | | | | | | | | | | | | | | | | discrete | logs in | close to | real time, | and | the second | is | to delay | | group for | legacy DHE_EXPORT. | | This | has | been | considered | | | | | | | | | handshakecompletionuntilthediscretelogcomputationhas safebecausemostmodernTLSclientsdonotofferoraccept | | | | | | | | hadtimetofinish. | | Weaddresstheseinthenextsubsections. | | | | | | | ------------- | ------------- | -------- | ------- | --------- | ---- | ----------- | ---------------- | --- | ----------------------------------- | --- | ------- | ------ | --- | -------- | | DHE_EXPORT | ciphersuites. | | | | | | | | | | | | | | | To understand | how | HTTPS | servers | in the | wild | use Diffie- | | | | | | | | | | | | | | | | | Comparison | | with previous | | attacks | Logjam | | is remi- | | Hellman, | we modified | the ZMap | [15] | toolchain | to | offer DHE | | | | | | | | | niscentoftherecentFREAK[7]attack,inwhichanattacker and DHE_EXPORT ciphersuites and scanned TCP/443 on downgrades a regular RSA key exchange to one that uses both the full public IPv4 address space and the Alexa export-grade 512-bit ephemeral RSA keys, relying on a bug Top 1M domains. The scans took place in March 2015. Of in several TLS client implementations. The attacker then 539,000HTTPSsitesamongTop1Mdomains,wefoundthat factors the ephemeral key to hijack future connections that 68.3% supported DHE and 8.4% supported DHE_EXPORT. use the same key. The cryptanalysis takes several hours on Of 14.3 million IPv4 HTTPS servers with browser-trusted commodityhardwareandisusableuntiltheservergenerates certificates, 23.9% supported DHE and 4.9% DHE_EXPORT. a fresh ephemeral RSA key (typically when it restarts). WhiletheTLSprotocolallowsserverstogeneratetheirown In contrast, Logjam is due to a protocol flaw in TLS, not Diffie-Hellman parameters, the overwhelming majority use an implementation bug. From a client perspective, the only | oneofahandfulofprimes. | | AsshowninTable1,justtwo512- | | | | | | | | | | | | | | ---------------------- | --- | --------------------------- | --- | --- | --- | --- | ------- | ------------ | ----- | ------ | ------ | ----------- | --- | ------ | | | | | | | | | defense | is to reject | small | primes | in DHE | handshakes. | | (Prior | bit primes account for 92.3% of Alexa Top 1M domains that tothiswork,mostpopularbrowsersacceptedpofsize≥512 supportDHE_EXPORT,and92.5%ofallserverswithbrowser- bits.) Logjam affects fewer servers than FREAK, but, as we trusted certificates that support DHE_EXPORT. (Non-export shall see, the cost per compromised connection is far lower, DHE follows a similar distribution with longer primes.) The sincetheprecomputationforeach512-bitgroupcanbeused most popular 512-bit prime was hard-coded into many ver- indefinitelyagainstallserversthatusethatgroup,andsince sions of Apache. Introduced in 2005 with Apache 2.1.5, it each individual discrete log only takes about a minute. was used until 2.4.7, which disabled export ciphersuites. We LogjamandFREAKbothfollowthesamepatternasother founditinusebyabout564,000serverswithbrowser-trusted cross-protocolattacksdiscoveredinTLS. AsearlyasSSL3.0, certificates. The second most popular 512-bit prime is the Schneier and Wagner noted a related vulnerability that they default used for DHE_EXPORT when using mod_ssl. It was called key exchange rollback [52]. Mavrogiannopoulos et al. | introduced | in version | 2.3.0 | in 1999. | We | found it | in use by | | | | | | | | | | ---------- | ---------- | ----- | -------- | --- | -------- | --------- | --- | --- | --- | --- | --- | --- | --- | --- | showedhowexplicit-curveECDHEhandshakescouldbecon- about 89,000 servers with browser-trusted certificates. fused with DHE handshakes [35]. All these attacks could | | | | | | | | be prevented | by | additionally | signing | | the ciphersuite | | in the | | --- | --- | --- | --- | --- | --- | --- | ------------ | --- | ------------ | ------- | --- | --------------- | --- | ------ | 3.2 ActiveDowngradetoExport-GradeDHE | | | | | | | | ServerKeyExchangemessage. | | | WeexpectthatTLS1.3willfix | | | | | | --- | --- | --- | --- | --- | --- | --- | ------------------------- | --- | --- | ------------------------- | --- | --- | --- | --- | Giventhewidespreaduseoftheseprimes,anattackerwith this protocol flaw. More generally, Logjam can also be inter- the ability to compute discrete logs in 512-bit groups could preted as a backwards compatibility attack [23] where one efficiently break DHE_EXPORT handshakes for about 8% of party uses only strong cryptography but the other supports Alexa Top 1M HTTPS sites, but modern browsers never both strong and weak ciphersuites. 4 | 3.3 512-bitDiscreteLogComputations | | | | | | | | 1 | | | | | | | | ---------------------------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | syek WemodifiedCADO-NFS[1]toimplementthenumberfield | sieve discrete | | log algorithm | | from §2 | and applied | it | to three | | | | | | | | | -------------- | --- | ------------- | --- | ------- | ----------- | --- | -------- | --- | --- | --- | --- | --- | --- | --- | fo 0.5 | 512-bit | primes, | including | the | top two | DHE_EXPORT | | primes | | | | | | | | | ------- | ------- | --------- | --- | ------- | ---------- | --- | ------ | --- | --- | --- | --- | --- | --- | --- | FDC | showninTable1. | | Precomputationtook7daysforeachprime, | | | | | | | | | | | | | | ---------------------------------------------------- | --- | ------------------------------------ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | afterwhichcomputingindividuallogstookamedianof70sec- | | | | | | | | 0 | | | | | | | onds. We list the runtime for each stage of the computation 30 60 90 120 150 | below. The | times | were | about | the same | for | each prime. | | | | | | | | | | ---------- | ----- | ---- | ----- | -------- | --- | ----------- | --- | --- | --- | --- | --- | --- | --- | --- | Seconds | Precomputation | | | As illustrated | in | Figure | 1, the | precom- | | | | | | | | | -------------- | --- | --- | -------------- | --- | ------ | ------ | ------- | --- | --- | --- | --- | --- | --- | --- | putationphaseincludesthepolynomialselection,sieving,and Figure3: Individual discrete log time for 512-bit DH. linearalgebrasteps. Forthisprecomputation,wedeliberately After a week-long precomputation for each of the two top sieved more than strictly necessary. This enabled two opti- export-grade primes (see Table 1), we can quickly break mizations: first, with more relations obtained from sieving, any key exchange that uses them. Here we show times for we eventually obtain a larger database of known logs, which computing 3,500 individual logs; the median is 70 seconds. | makesthedescentfaster. | | | Second,moresievingrelationsalso | | | | | | | | | | | | | ---------------------- | --- | --- | ------------------------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | yieldasmallerlinearalgebrastep,whichisdesirablebecause 3.4 ActiveAttackImplementation | sieving | is much | easier | to parallelize | than | linear | algebra. | | | | | | | | | | --------- | ------------ | ------ | -------------- | ---------- | --------- | --------- | ------- | ----------------- | --- | ------------------- | ---- | -------- | ------- | ---------- | | For the | polynomial | | selection | and | sieving | steps, | we used | | | | | | | | | | | | | | | | | We implemented | | a man-in-the-middle | | | network | attacker | | idle time | on 2000–3000 | | CPU | cores in | parallel, | of which | most | | | | | | | | | | | | | | | | | that sits between | a | TLS client | (web | browser) | and | any server | | CPUs were | Intel | Sandy | Bridge. | Polynomial | | selection | ran | | | | | | | | thatsupportsDHE_EXPORTandusesthemostcommon512- | for about | 3 hours, | which | in | total corresponds | | to 7,600 | core- | | | | | | | | | ---------------- | -------- | ----------- | --------- | ----------------- | ---------- | --------- | --------- | ----------- | --------- | ------------------ | ---------- | ------------- | ---------- | ----------- | | | | | | | | | | bit Apache | group. | Our implementation | | follows | | the message | | hours. | Sieving | ran for | 15 hours, | corresponding | | | to 21,400 | | | | | | | | | | | | | | | | | sequence in | Figure | 2: it downgrades | | the | connection | towards | | core-hours. | This | sufficed | to | collect | 40,003,519 | relations | of | | | | | | | | | | | | | | | | | the server, | computes | the | session | keys, | and takes | over the | | which 28,372,442 | | were | unique, | involving | 15,207,865 | | primes | | | | | | | | | | | | | | | | | connection | towards | the client | by | impersonating | | the server. | | of at most | 27 | bits (hence | bound | B from | §2 | is 227). | | | | | | | | | | | | | | | | | | The main | challenge | is | to compute | the | shared | secret gab | From this data set, we obtained a square matrix with before the handshake completes in order to forge a Finished 2,157,378rowsandcolumns,with113nonzerocoefficientsper message from the server. With our descent implementation, | rowonaverage. | | Wesolvedthecorrespondinglinearsystemon | | | | | | | | | | | | | | ----------------------------------- | ------- | -------------------------------------- | ---------- | ----- | -------------- | ------- | ---- | --------------- | -------- | -------- | ------- | ----------- | -------- | --------- | | | | | | | | | | the computation | takes | an | average | of 70 | seconds, | but there | | a 36-node | cluster | with | two 8-core | Intel | Xeon | E5-2650 | CPUs | | | | | | | | | | | | | | | | | are several | ways an | attacker | can | work around | this | delay: | | pernode,connectedwithInfinibandFDR. | | | | | Weusedtheblock | | | | | | | | | | | | | | | | | | | Non-browser | clients. | | | | | | Wiedemann algorithm [11,49] with parameters m=18 and Different TLS clients impose different n=6. Using the unoptimized implementation from CADO- time limits for the handshake, after which they kill the NFS [1] for linear algebra over GF(p), the computation connection. Command-line clients such as curl and git finished in 120 hours, corresponding to 60,000 core-hours. oftenrununattended, sotheyhavelongornotimeouts, and We expect that optimizations could bring this cost down by we can hijack their connections without difficulty. at least a factor of three. TLS warning alerts. Web browsers tend to have shorter In total, the wall-clock time for each precomputation was timeouts,butwecankeeptheirconnectionsalivebysending slightly over one week. Each resulting database of known TLS warning alerts, which are ignored by the browser but logs for the descent occupies about 2.5 GB in ASCII format. resetthehandshaketimer. Forexample,thisallowsustokeep | | | | | | | | | Firefox’sTLSconnectionsaliveindefinitely. | | | | | (Otherbrowsers | | | ------- | ------- | ------------- | -------------- | ------- | ------------- | ---------- | ------- | ----------------------------------------- | ---------- | ---------- | ----- | ---------- | -------------- | ----------- | | Descent | Once | this | precomputation | | was finished, | | we were | | | | | | | | | | | | | | | | | we tested close | the | connection | after | a minute.) | | Although | | able to | run the | final descent | | step to | compute | individual | dis- | | | | | | | | | | | | | | | | | the victim | connection | still | takes | much | longer | than usual, | cretelogsinaboutaminutefortargetsineachofthesegroups. In order to save time on individual computations, we imple- the attacker might choose to compromise a request for a | | | | | | | | | background | resource | that | does not | delay | rendering | the page. | | ------ | --------------- | --- | ------------ | ----- | --- | ------ | ---- | ---------- | ------------ | ---- | -------- | ----- | --------- | --------- | | mented | a client-server | | architecture | using | the | ZeroMQ | mes- | | | | | | | | | | | | | | | | | Ephemeral | key caching. | | | | | | saging library. The server maintains the precomputed data Many TLS servers do not use a gb in RAM and returns logs for values passed to it by clients. fresh value b for each connection, but instead compute WeimplementedthedescentcalculationinamixofPython onceandreuseitformultiplenegotiations. Withoutenabling gb and C. The first and second stages are parallelized and run the SSL_OP_SINGLE_DH_USE option, OpenSSL will reuse sieving in C, and the final discrete log is deduced in Python. for the lifetime of a TLS context. While both Apache and We ran the server on a machine with two 18-core Intel Xeon Nginx internally apply this option, certain load balancers, E5-2699CPUsand128GBofRAM. Onaverage,computing such as stud [48], do not. The F5 BIG-IP load balancers individual logs took about 70 seconds, but the time varied and hardware TLS frontends will reuse gb unless the “Single from 34 to 206 seconds (see Fig. 3). This is divided between DH”optionischecked[53]. MicrosoftSchannelcachesgb for about20secondsfordescentinitializationandtheremainder two hours—this setting is hard-coded. For these servers, an gb on the middle phase. Further optimizations—such as more attacker can compute the discrete log of from one connec- effective parallelization on the middle phase or additional tionanduseittoattacklaterhandshakes,avoidingtheneed sieving—should bring the median time well below a minute. to do the computation online. By randomly sampling IPv4 For purposes of comparison, a single 512-bit RSA factor- hosts serving browser-trusted certificates that support DHE, gb ization using the CADO-NFS implementation takes about we found that 17% reused at least once over the course eight days of wall-clock time on the computer used for the of 20 handshakes, and that 15% only used one value. How- descent,andaboutthreehoursparallelizedacross1,800cores ever, for DHE_EXPORT, only 0.1% reused gb, likely because of Amazon EC2 c4.8xlarge instances. Microsoft IIS does not support 512-bit export ciphersuites. 5 TLS False Start. Even when clients enforce shorter time- To see if TLS servers in the wild were vulnerable to this outs and servers do not reuse values for b, the attacker can attack, we tested various non-safe primes found in our scans. still break the confidentiality of user requests if the client For each non-safe prime p, we opportunistically factored supports the TLS False Start extension [30]. This extension p−1 using Bernstein’s batch method [5]. We then ran the reduces connection latency by having the client send early GMP-ECM implementations of the Pollard p−1 algorithm applicationdata(suchasanHTTPrequest)withoutwaiting and the ECM factoring methods [54] for 5 days parallelized for the server’s Finished message to arrive. Recent versions across 28 cores and discovered 36,447 prime factors. of Chrome, Internet Explorer, and Firefox implement False Wethenexaminedthegeneratorsgusedwitheachprimep. Start, but their policies on when to enable it vary between We classified a tuple (p,g,y) sent by a server as interesting versions. Firefox35,Chrome41,andInternetExplorer(Win- iftheprimefactorizationofp−1hadrevealedprimefactors dows 10) send False Start data with DHE. In these cases, a of the order of g, and ordered them by the estimated work man-in-the-middlecanrecordthehandshakeanddecryptthe requiredusingPohlig-HellmanandPollardlambdatorecover False Start payload at leisure. We note that this initial data atargetprivateexponentxoflengthrangingfrom64to256 sentbyabrowseroftencontainssensitiveuserauthentication bits. There were 753 (p,g) pairs where we knew factors of information, such as passwords and cookies. thesubgroupgeneratedbyg;thesehadbeenusedfor40,903 connections across all of our scans. 3.5 OtherWeakandMisconfiguredGroups WeimplementedthevanOorschotandWieneralgorithmin Sage[47]usingaparallelPollardrhoimplementationthatwe In our scans, we found several other exploitable security wroteinCusingtheGMPlibrary. Weusedthedistinguished issues in the DHE configurations used by TLS servers. points method for collision detection; for a prime known in 512-bit primes in non-export DHE We found 2,631 advance, this implementation can be arbitrarily sped up by servers with browser-trusted certificates (and 118 in the precomputing a table of distinguished points. Top 1M domains) that used 512-bit or weaker primes for We computed partial information about the server secret non-export DHE. In these instances, active attacks may exponent used in 460 exchanges and were able to recover be unnecessary. If a browser negotiates a DHE ciphersuite the whole exponent used by 159 different hosts, 53 of which with one of these servers, a passive eavesdropper can later authenticated with valid browser-trusted certificates. In all compute the discrete log and obtain the TLS session keys cases, the vulnerable hosts used 512-bit prime moduli; three for the connection. An active attack may still be necessary of them used 160-bit exponents and the rest used 128 bits. when the client’s ordering of ciphersuites would result in the The order of the largest-order subgroup ranged from 46 bits servernotselectingDHE.Inthiscase,asintheDHE_EXPORT (which finishes in seconds) to 81 bits (which took between downgrade attack, an active attacker can force the server to 50 and 176 hours) implementation. The Pollard lambda choose a vulnerable DHE ciphersuite. calculations used interval width varying from 40 to 70 bits. As a proof-of-concept, we implemented a passive eaves- Our computations would have allowed us to hijack con- dropper for regular DHE connections and used it to decrypt nections to a variety of vulnerable TLS servers, including testconnectionstowww.fbi.gov. UntilApril2015,thisserver web interfaces for VPN devices (48 hosts), communications used the default 512-bit DH group from OpenSSL, which software(21hosts),webconferencingservers(27hosts),and was the third group for which we performed the NFS pre- FTP servers (6 hosts). As a proof-of-concept, we modified computation. The website no longer supports DHE. our man-in-the-middle attacker of §3.3 to impersonate a Attacks on composite-order subgroups Failure to vulnerable server and capture user credentials. Compared generate Diffie-Hellman primes according to best practices to an attack using NFS, we could compute the discrete log can result in devastating attacks. Not every TLS server with a delay hardly noticeable for browser users. uses “safe” primes. Out of approximately 70,000 distinct Misconfiguredgroups TheDigitalSignatureAlgorithm primes seen across both export and non-export TLS scans, (DSA) [38] uses primes p such that p−1 has a large prime 4,800 were not safe, meaning that (p−1)/2 was composite. factor q and g generates only a subgroup of order q. When (Incidentally, we also found 9 composite p.) These groups using properly generated DSA parameters, these groups are arenotnecessarilyvulnerable,aslongasg generatesagroup secureforuseinDiffie-Hellmankeyexchanges. Notably,DSA withatleastonesufficientlylargesubgroupordertoruleout groups are hard-coded in Java’s sun.security.provider the Pohlig-Hellman algorithm as an attack. package and are used by default in many Java-based TLS In some real-life configurations, however, choosing such servers. However,someserversinourscansusedJava’sDSA primes can lead to an attack. For efficiency reasons, some primesaspbutmistakenlyusedtheDSAgrouporderqinthe implementationsuseephemeralkeysgxwithashortexponent placeofthegeneratorg. Wefound5,741hostsmisconfigured x; commonlysuggestedsizesforxareassmallas160or224 this way. bits, intended to match the estimated strength of a 1024- or Thissubstitutionofqforgislikelyduetoausabilityprob- 2048-bit group. For safe p, such exponent lengths are not lem: the canonical ASN.1 representation of Diffie-Hellman known to decrease security, as the most efficient attack will key exchange parameters (coming from PKCS#3) is a se- be the Pollard lambda algorithm. But if the order of the quence (p,g), while that of DSA parameters (coming from subgroup generated by g has small factors, they can be used PKIX) is (p,q,g); we conjecture that the confusion between to recover information about exponents. From a subset of these formats led to a simple programming error. factors {q 1 e1...q k ek} with P Q i q i e √ i = z, Pohlig-Hellman can In a DSA group, the subgroup generated by q is likely recover x mod z in time i ei qi. If x≤z, this suffices to to have many small prime factors in its order, since for p recover x. If not, Pollard lambda can use this information generated according to [38], (p−1)/q is a random integer. p to recover x in time x/z. This attack was first described ForJava’ssun.security.provider512-bitprime,usingqas as hypothetical by van Oorschot and Wiener [51]. ageneratorleaks290bitsofinformationaboutexponentsat 6 a cost of roughly 240 operations. Luckily, since the provider confidence,particularlyforthe1024-bitcase. Wesummarize | | | | max(n/2,384) | | n-bit | p, | | | | | | | | | --- | --- | --- | ------------ | --- | ----- | --- | --- | --- | --- | --- | --- | --- | --- | generates exponents of length for all the costs, measured or estimated, in Table 2. this does not suffice to recover a full exponent. Still, this DH-768: Feasible with academic power Forthe768- | misconfiguration | bug | results | in a significant | | loss of security | | | | | | | | | | ---------------- | --------------- | ------- | ---------------- | ------------ | ---------------- | --- | -------------------- | ------------ | ---------------------------------- | ----------- | ------------- | -------- | --------- | | | | | | | | | bit case, | we base our | estimates | on | the recent | discrete | log | | and serves | as a cautionary | | tale for | programmers. | | | | | | | | | | | | | | | | | | record at | 596 bits [8] | and | the integer | factorization | | record of | | | | | | | | | 768bitsfrom2009[29]. | | Whilethealgorithmsforfactorization | | | | | 4. STATE-LEVELTHREATSTODH | | | | | | | | and discrete | log are | similar, | the discrete | log | linear | algebra | | --- | --- | --- | --- | --- | --- | --- | ------------ | ------- | -------- | ------------ | --- | ------ | ------- | The previous sections demonstrate the existence of practi- stage is many times more difficult, as the matrix entries are cal attacks against Diffie-Hellman key exchange as currently no longer Boolean. We can reduce overall time by sieving used by TLS. However, these attacks rely on the ability to more, thus generating a smaller input matrix to the linear downgrade connections to export-grade crypto or on the use algebra step. Since sieving parallelizes better than linear | | | | | | | | algebra, | this tradeoff | is desirable | for | large | inputs. | | | ------------------- | ---------- | ---------------------------------- | --- | ---------- | --------- | --- | ----------- | ------------- | ------------ | ----------- | ----- | ----------- | ------- | | ofunsafeparameters. | | Inthissectionweaddressthefollowing | | | | | | | | | | | | | | | | | | | | A 596-bit | factorization | | takes about | 5 | core-years, | most | | question: | how secure | is Diffie-Hellman | | in broader | practice, | | | | | | | | | | | | | | | | | of it spent | on sieving. | In | comparison, | the | record | 596-bit | asusedinotherprotocolsthatdonotsufferfromdowngrade, and when applied with stronger groups? discrete log effort tuned parameters such that they spent To answer this question we must first examine how the 50 core-years on sieving. This reduced their linear algebra numberfieldsievefordiscretelogscalesto768-and1024-bit calculation to 80 core-years. We used this same strategy in groups. Aswearguebelow,768-bitgroups,whicharestillin our 512-bit experiments in §3.3. relativelywidespreaduse,arenowwithinreachforacademic Similarly, the 768-bit RSA factoring record spent more computational resources, and performing precomputations time on sieving in order to save time on the linear algebra for a small number of 1024-bit groups is plausibly within step. The cost of sieving was around 1500 core-years, and the resources of state-level attackers. The precomputation the matrix that was produced had 200M rows and columns. | | | | | | | | As a result, | the linear | algebra | took | 150 core-years, | | but tak- | | --- | --- | --- | --- | --- | --- | --- | ------------ | ---------- | ------- | ---- | --------------- | --- | -------- | wouldlikelyrequirespecial-purposehardware,butwouldnot | | | | | | | | ing algorithmic | improvements | | since | 2009 | into account | and | | ----------------------------- | ----------------- | --- | --------------------- | --- | ----------- | --- | --------------------------- | ------------ | --- | ------------------------- | ---- | ------------ | --- | | require any | major algorithmic | | improvements | | beyond what | is | | | | | | | | | | | | | | | | optimizingforthetotaltime,3 | | | weestimatethatfactoringan | | | | | knownintheacademicliterature. | | | Wefurthershowthateven | | | | | | | | | | | in the 1024-bit case, the descent time—necessary to solve RSA-768 integer would take 900 core-years in total. any specific discrete log instance within a common group— Fora768-bitdiscretelog, wecanexpectthattentimesas would be fast enough to break individual key exchanges in much sieving as the RSA case would reduce the matrix to close to real time. around 150M rows. We extrapolate from experiments with Inlightoftheseresults,weexamineseveralstandardInter- existing software that this linear algebra would take 28,500 net security protocols—IKE, SSH, and TLS—to determine core-years, for a total of 36,500 core-years. This is within thevulnerabilityoftheirkeyexchangestoattacksbyresource- reach by computing power available to academics. ful attackers. Although the cost of the precomputation for a The descent step takes relatively little time. We experi- | | | | | | | | mented | with both | CADO-NFS | and | a new | implementation | | | -------- | ---------------- | ----- | ------ | ---- | ---------- | --- | ------ | --------- | -------- | --- | ----- | -------------- | --- | | 1024-bit | group is several | times | higher | than | for an RSA | key | | | | | | | | withGMP-ECMbasedontheearly-abortstrategydescribed ofequalsize,weobservethataone-timeinvestmentcouldbe | | | | | | | | in [6]. Using | these | techniques, | the initial | descent | phase | took | | ------- | --------------- | --------- | --- | ------------- | ----- | --- | ------------- | ----- | ----------- | ----------- | ------- | ----- | ---- | | used to | attack millions | of hosts, | due | to widespread | reuse | of | | | | | | | | themostcommonDiffie-Hellmanparameters. Unfortunately, an average of around 1 core-day. The remaining phase uses our measurements also indicate that it may be very difficult sieving much as in the precomputation; extrapolating from tosunsettheuseoffixed1024-bitDiffie-Hellmangroupsthat experiments, the rest of the descent should take at most havelongbeenembeddedinstandardsandimplementations. 1 core-day. In total, after precomputation, the cost of a Finally, we apply this new understanding to a set of re- single768-bitdiscretelogcomputationisaround2core-days cently published documents leaked by Edward Snowden [46] and is easily parallelizable. toevaluatethehypothesisthattheNationalSecurityAgency | | | | | | | | DH-1024: | Plausible | with | state-level | | resources | Ex- | | ----------- | ----------- | ---- | ------------- | --- | ------- | ---- | -------- | --------- | ---- | ----------- | --- | --------- | --- | | has already | implemented | such | a capability. | | We show | that | | | | | | | | perimentallyextrapolatingsievingparameterstothe1024-bit this hypothesis is consistent with the published details of case is difficult due to the tradeoffs between the steps of the the intelligence community’s cryptanalytic capabilities, and, algorithm and their relative parallelism. The prior work indeed, matches the known capabilities more closely than proposing parameters for factoring a 1024-bit RSA key is other proposed explanations, such as novel breaks on RC4 thin: [28] proposes smoothness bounds of 42 bits, but the or AES. We believe that this analysis may help shed light proposed value of the sieving region parameter I is clearly | on unanswered | questions | | about how | NSA may | be gaining | | | | | | | | | | ------------- | --------- | ------- | --------- | ------- | ---------- | --- | ----------- | ----------- | --------- | -------- | ------- | ----------- | ---- | | | | | | | | | too small, | giving too | few | smooth | results | per sieving | sub- | | access to | VPN, SSH, | and TLS | traffic. | | | | | | | | | | | | | | | | | | | task. Since | no publicly | available | software | can | currently | deal | 4.1 ScalingNFSto768-and1024-bitDH with values of I larger than those proposed, we could not experimentallyupdatetheestimatesofthispaperwithmore Estimatingthecostfordiscretelogcryptanalysisatlonger | | | | | | | | relevant | parameter | choices. | | | | | | --------- | ----------- | ---------------- | --- | --- | ------- | ------ | -------- | --------- | -------- | --- | --- | --- | --- | | key sizes | is far from | straightforward, | | due | in part | to the | | | | | | | | Withoutbetterparameterchoices,weresorttoextrapolat- complexityofparametertuningandtotradeoffsbetweenthe ing from asymptotic complexity. For the number field sieve, | | | | | | | | | | (cid:0) | | | | (cid:1) | | --- | --- | --- | --- | --- | --- | --- | --- | --- | ------- | --- | --- | --- | ------- | sieving and linear algebra steps, which have very different the complexity is exp (k+o(1))(logN)1/3(loglogN)2/3 , computational characteristics. (Much more attention has where N is the integer to factor or the prime modulus for gonetounderstanding1024-bitfactorization,but,eventhere, discrete log, and k is an algorithm-specific constant. This many published estimates are crude extrapolations of the formula is inherently imprecise, since the o(1) in the expo- | asymptotic | complexity.) | We | attempt | estimates | for 768- | and | | | | | | | | | ---------- | ------------ | --- | ------- | --------- | -------- | --- | --- | --- | --- | --- | --- | --- | --- | 1024-bit discrete log based on the existing literature and 3We would lower the smoothness bounds compared to the our own experiments, but further work is needed for greater parameters in [29]. 7 Sieving LinearAlgebra Descent I log B core-years rows core-years core-time 2 RSA-512 14 29 0.5 4.3M 0.33 TimingswithdefaultCADO-NFSparameters. DH-512 15 27 2.5 2.1M 7.7 10mins Forthecomputationsinthispaper;maybesuboptimal. RSA-768 16 37 800 250M 100 Est.basedon[29]withlesssieving. DH-768 17 35 8,000 150M 28,500 2days Est.basedon[8,29]andourownexperiments. RSA-1024 18 42 1,000,000 8.7B 120,000 Est.basedoncomplexityformula. DH-1024 19 40 10,000,000 5.2B 35,000,000 30days Est.basedoncomplexityformulaandourexperiments. Table2: Estimating costs for factoring and discrete log. Forsieving,wegivetwoimportantparameters: thenumberof bits of the smoothness bound B and the sieving region parameter I. For linear algebra, all costs for DH are for safe primes; for DSA primes with q of 160 bits, this should be divided by 6.4 for 1024 bits, 4.8 for 768 bits, and 3.2 for 512 bits. nent can hide polynomial factors. This complexity formula, a more modern size reduces costs, as transistors are cheaper with k=1.923, describes the overall time for both discrete atnewertechnologies. Withstandardtransistorcostsanduti- log and factorization, which are both dominated by sieving lization,thiswouldcostabout$2perchiptomanufacture,af- and linear algebra in the precomputation. The space com- terfixeddesignandtape-outcostsofroughly$2M[32]. This plexity(thesizeofthematrixinmemory)isthesquareroot suggests that an $8M investment would buy enough ASICs of this function, i.e., the same function, taking k=0.9615. tocompletetheDH-1024sievingprecomputationinoneyear. Discrete log descent has a complexity of the same form as Sinceastepofdescentusessieving,thesamehardwarecould well; [2, Chapter 4] gives k = 1.232, using an early-abort likely be reused to speed calculations of individual logs. strategy similar to the one in [6] mentioned above. Estimatingthefinancialcostforthelinearalgebraismore Evaluating the formula for 768- and 1024-bit N gives us difficult, since there has been little work on designing chips estimatedmultiplicativefactorsbywhichtimeandspacewill that are suitable for the larger fields involved in discrete log. increase from the 768- to the 1024-bit case. For precompu- Toderivearoughestimate,wecanbeginwithgeneralpurpose tation, the total time complexity will increase by a factor hardware and the core-year estimate from Table 2. The of 1220, while space complexity will increase by a factor of Titan supercomputer [39]—at 300,000 CPU cores, currently 35. These are valid for both factorization and discrete log, the most powerful supercomputer in the U.S.—would take since they have the same asymptotic behavior. Hence, for 117yearstocompletethe1024-bitlinearalgebrastage. Titan DH-1024,wegetatotalcostfortheprecomputationofabout was constructed in 2012 for $94M, suggesting a cost of $11B 45M core-years. The time complexity for each individual insupercomputerstofinishthisstepinayear. Inthecontext log after the precomputation should be multiplied by 95. of factorization, moving linear algebra from general purpose This last number does not correspond to what we observed CPUs to ASICs has been estimated to reduce costs by a in practice; we attribute that to the fact that the descent factor of 80 [17]. If we optimistically assume that a similar step has been far less studied both in theory and in practice reductioncanbeachievedfordiscretelog,thehardwarecost compared to the other steps. to perform the linear algebra for DH-1024 in one year is For 1024-bit descent, we experimented with our early- plausibly on the order of hundreds of millions of dollars. abort implementation to inform our estimates for descent To put this dollar figure in context, the FY2012 bud- initialization, which should dominate the individual discrete get for the U.S. Consolidated Cryptologic Program (which log computation. For a random target in Oakley Group 2, includes the NSA) was $10.5 billion4 [57]. The agency’s initialization took 22 core-days, yielding a few primes of at classified 2013 budget request, which prioritized investment most 130 bits to be descended further. In twice this time, in “groundbreaking cryptanalytic capabilities to defeat ad- we reached primes of about 110 bits. At this point, we were versarial cryptography and exploit internet traffic,” included certaintohavebootstrappedthedescent,andcouldcontinue notable$100Mincreasesintwoprograms[57]: “cryptanalytic down to the smoothness bound in a few more core-days if ITservices”(to$247M),andacrypticallynamed“cryptanal- proper sieving software were available. Thus we estimate ysisandexploitationservicesprogramC”(to$360M).NSA’s that a 1024-bit descent would take about 30 core-days, once leaked strategic plan for the period called for it to “continue again easily parallelizable. to invest in the industrial base and drive the state of the artforhighperformancecomputingtomaintainpre-eminent Costs in hardware Although 45M core-years is a huge cryptanalytic capability for the nation” [63]. computational effort, it is not necessarily out of reach for a nation state. Moreover, at this scale, significant cost savings 4.2 IsNSABreaking1024-bitDH? couldberealizedbydevelopingapplication-specifichardware. Our calculations suggest that it is plausibly within NSA’s Sieving is a natural target for hardware implementation. resources to have performed number field sieve precomputa- To our knowledge, the best prior description of an ASIC tions for at least a small number of 1024-bit Diffie-Hellman implementationof1024-bitsievingisthe2007workofGeisel- groups. This would allow them to break any key exchanges mannandSteinwandt[18]. Inthefollowing,weupdatetheir made with those groups in close to real time. If true, this estimates for modern techniques and adjust parameters for wouldansweroneofthemajorcryptographicquestionsraised discretelog. Weincreasetheirchipcountbyafactoroftento by the Edward Snowden leaks: How is NSA defeating the sievemoreandsaveonlinearalgebraasabove,givinganesti- encryption for widely used VPN protocols? mate of 3M chips to complete sieving in one year. Shrinking thediesfromthe130nmtechnologynodeusedinthepaperto 4The National Science Foundation’s budget was $7 billion. 8 | Classified | documents | | published | by | Der Spiegel | [46] | indi- | | | | | | | | | ----------- | --------- | ------------- | ---------- | ------ | ----------- | ----------- | ------ | --- | --- | --- | --- | --- | --- | --- | | cate that | NSA is | passively | decrypting | | IPsec | connections | at | | | | | | | | | significant | scale. | The documents | | do not | describe | the | crypt- | | | | | | | | analytictechniquesused,buttheydoprovideanoverviewof | the attack | system | architecture. | | After | reviewing | how | IPsec | | | | | | | | | ----------------- | ----------- | --------------- | ------------ | ---------- | -------------- | ------------- | ------- | ---------- | --------------------------------- | --------- | -------- | ------ | ------- | ---------- | | key establishment | | works, | we will | use | the published | informa- | | | | | | | | | | tion to evaluate | | the hypothesis | | that | the NSA | is leveraging | | | | | | | | | | precomputation | | to calculate | discrete | | logs at | scale. | | | | | | | | | | IKE | Internet | Key Exchange | | (IKE) | is the | main | key es- | | | | | | | | | tablishment | protocol | used | for | IPsec | VPNs. | There are | two | | | | | | | | | versions, | IKEv1 | [22] and | IKEv2 | [25], | which | differ in | mes- | | | | | | | | | sage structure | but | are | conceptually | similar. | | For the | sake of | | | | | | | | | brevity, | we will use | IKEv1 | terminology. | | | | | | | | | | | | | | | | | | | | | Figure4: | NSA’sVPNdecryptioninfrastructure. | | | | | This | | Each | IKE session | begins | with | a Phase | 1 | handshake, | in | | | | | | | | | | | | | | | | | classified | illustration | published | | by Der | Spiegel | [67] shows | | which the | client | and server | | select a | Diffie-Hellman | | group | | | | | | | | | | | | | | | | | captured | IKE handshake | | messages | being | passed | to a high- | | from a small | set | of standardized | | parameters | | and perform | a | | | | | | | | performancecomputingsystem,whichreturnsthesymmetric | key exchange | to | establish | a shared | secret. | The | shared | secret | | | | | | | | | ------------ | --- | --------- | -------- | ------- | --- | ------ | ------ | ------------ | ------- | -------- | --- | ------- | ------- | ---------- | | | | | | | | | | keys for ESP | session | traffic. | The | details | of this | attack are | is combined with other cleartext values transmitted by each consistentwithanefficientbreakfor1024-bitDiffie-Hellman. | side, such | as nonces | and | cookies, | to | derive | a value | called | | | | | | | | | ---------- | ------------ | --- | -------- | -------------- | ------ | ----------- | ------ | --- | --- | --- | --- | --- | --- | --- | | SKEYID. | IKE provides | | several | authentication | | mechanisms, | | | | | | | | | including symmetric pre-shared keys (PSK); when IKEv1 is Evidence for a discrete log attack While the ability authenticated with a PSK, this value is incorporated into to decrypt VPN traffic does not by itself indicate a defeat | the derivation | of | SKEYID. | | | | | | | | | | | | | | -------------- | ------------ | ------- | ------- | ------------------- | --- | -------------- | --- | ------------------ | -------- | ------------ | ----------- | ----------- | ----------- | ----------- | | | | | | | | | | of Diffie-Hellman, | | there are | several | features | of | IKE and the | | The resulting | SKEYID | | is used | to encrypt | and | authenticate | | | | | | | | | | | | | | | | | | VAO’s operation | | that support | this | hypothesis. | | | | a Phase | 2 handshake. | | Phase | 2 establishes | | the parameters | | | | | | | | | | | | | | | | | | The IKE | protocol | has | been | extensively | analyzed | [9,36], | | and key | material, | KEYMAT, | | for a cryptographic | | transport | | | | | | | | | | | | | | | | | | and is not | believed | to be | exploitable | | in standard | configu- | protocolusedtoprotectsubsequenttraffic,suchasEncapsu- | | | | | | | | | rations under | passive | eavesdropping | | attacks. | | In order to | | --------------- | ------- | --- | ----- | ------- | ------------- | --- | ------ | ------------- | ------- | ------------- | ------- | -------- | --- | -------------- | | lating Security | Payload | | (ESP) | [27] or | Authenticated | | Header | | | | | | | | | | | | | | | | | recover the | session | keys | for the | ESP or | AH | protocols, the | (AH) [26]. In some circumstances, this phase includes an attacker must at minimum recover the SKEYID generated additional round of Diffie-Hellman. Ultimately, KEYMAT is by the Phase 1 exchange. Absent a vulnerability in the key derived from SKEYID, additional nonces, and the result of derivation function or transport encryption, this requires the optional Phase 2 Diffie-Hellman exchange. the attacker to recover a Diffie-Hellman shared secret after NSA’sVPNexploitationprocess Thedocumentspub- passively observing an IKE handshake. lished by Der Spiegel describe a system named TURMOIL WhileIKEisdesignedtosupportarangeofDiffie-Hellman thatisusedtocollectanddecryptVPNtraffic. Theevidence groups, our Internet-wide scans (§4.3) show that the vast indicates that this decryption is performed using passive majority of IKE systems select one particular 1024-bit DH eavesdropping and does not require message injection or group, Oakley Group 2, even when offered stronger groups. man-in-the-middle attacks on IPsec or IKE. Figure 4, an Given an efficient oracle for solving the discrete logarithm excerpt from one of the documents [67], illustrates the flow problem, attacks on IKE are possible provided that the of information through the TURMOIL system attacker can obtain the following: (1) a complete two-sided TheinitialphasesoftheattackinvolvecollectingIKEand IKE transcript, including the Diffie-Hellman ephemeral keys ESP payloads and determining whether the traffic matches ga and gb as well as the nonces and cookies transmitted by any tasked selector [65]. If so, TURMOIL transmits the bothsidesoftheconnection,and(2)inIKEv1only,thePSK complete IKE handshake and may transmit a small amount used in deriving SKEYID. of ESP ciphertext to NSA’s Cryptanalysis and Exploitation Both of the above requirements are also present in the Services (CES) [56,65] via a secure tunnel. Within CES, a NSA’s VPN attack system. As Figure 4 illustrates, a hard specializedVPNAttackOrchestrator(VAO)systemmanages requirement of the VAO is the need to obtain the complete a collection of high-performance grid computing resources two-sided IKE transcript [60]. The published documents located at NSA Headquarters and in a data center at Oak indicate that this requirement substantially increases the Ridge National Laboratory, which perform the computation complexity of the attack execution, since IKE transcripts required to generate the ESP session key [61,62,67]. VAO must be reassembled (“paired”) whenever the interaction also maintains a database, CORALREEF, that stores cryp- traverses multiple network paths [55,56,58,66]. tographic values, including a set of known PSKs and the The attack system also seems to require knowledge of the resulting “recovered” ESP session keys [60,61,67]. PSK. Several documents describe techniques for analysts The ESP traffic itself is buffered for up to 15 minutes [64], to locate a PSK, including using a database of router con- until CES can respond with the recovered ESP keys if they figurations [70,71], the CORALREEF database of known were generated correctly. Once keys have been returned, the PSKs [60], previously decrypted SSH traffic [60], or system ESP traffic is decrypted via hardware accelerators [59] or administrator “chatter” [70]. Additionally, NSA is willing to in software [68,69]. From this point, decrypted VPN traffic “[r]un attacks to recover PSK” [60]. is reinjected into TURMOIL processing infrastructure and Of course, this explanation is not dispositive. The possi- passed to other systems for storage and analysis [69]. The bility remains that NSA could defeat IPsec using alternative documentsindicatethatNSAisrecoveringESPkeysatlarge means. Certain published NSA documents refer to soft- scale, with a target of 100,000 per hour [64]. ware “implants” on VPN devices, indicating that the use of 9 Vulnerable servers, if the attacker can precompute for ... all512-bitgroups all768-bitgroups one1024-bitgroup ten1024-bitgroups HTTPSTop1Mw/activedowngrade 45,100(8.4%) 45,100(8.4%) 205,000(37.1%) 309,000(56.1%) HTTPSTop1M 118(0.0%) 407(0.1%) 98,500(17.9%) 132,000(24.0%) HTTPSTrustedw/activedowngrade 489,000(3.4%) 556,000(3.9%) 1,840,000(12.8%) 3,410,000(23.8%) HTTPSTrusted 1,000(0.0%) 46,700(0.3%) 939,000(6.56%) 1,430,000(10.0%) IKEv1IPv4 – 64,700(2.6%) 1,690,000(66.1%) 1,690,000(66.1%) IKEv2IPv4 – 66,000(5.8%) 726,000(63.9%) 726,000(63.9%) SSHIPv4 – – 3,600,000(25.7%) 3,600,000(25.7%) Table 3: Estimated impact of Diffie-Hellman attacks. We use Internet-wide scanning to estimate the number of real- world servers for which typical connections could be compromised by attackers with various levels of computational resources. For HTTPS, we provide figures with and without downgrade attacks on the chosen ciphersuite. All others are passive attacks. targeted malware is a piece of the collection strategy [60]; of profiled servers chose Oakley Group 1, and 63.9% chose however, the same documents also note that decryption of Oakley Group 2. This coincides with our anecdotal findings the resulting traffic does not require IKE handshakes, and thatmostVPNclientsonlyofferOakleyGroup2bydefault. thus appears to be an alternative mechanism to the VAO SSH All SSH handshakes complete either a finite field attack described above. The most compelling argument for Diffie-Hellman or elliptic curve Diffie-Hellman exchange as a pure cryptographic attack is the generality of the VAO part of the SSH key exchange. The SSH protocol explicitly approach, which appears to succeed across a broad swath of defines support for Oakley Group 2 (1024-bit) and Oakley non-compromised devices. Group 14 (2048-bit) but also allows a server-defined group, whichcanbenegotiatedthroughanauxiliaryDiffie-Hellman 4.3 Effectsofa1024-bitBreak Group Exchange (DH-GEX) handshake [16]. In this section, we use Internet-wide scanning to assess In order to measure how SSH uses DH in practice, we the impact of a hypothetical DH-1024 break on three popu- implemented the SSH protocol in the ZMap toolchain and lar protocols: IKE, SSH, and HTTPS. Our measurements scanned1%randomsamplesofthepublicIPv4addressspace indicate that these protocols, as they are commonly used, in April 2015. We find that 98.9% of SSH servers support would be subject to widespread compromise by a state-level the 1024-bit Oakley Group 2, 77.6% support the 2048-bit attacker who had the resources to invest in precomputation Oakley Group 14, and 68.7% support DH-GEX. for a small number of common 1024-bit groups. DuringtheSSHhandshake,theclientandserverselectthe client’s highest priority mutually supported key exchange IKE WemeasuredhowIPsecVPNsuseDiffie-Hellmanin algorithm. Therefore,wecannotdirectlymeasurewhatalgo- practicebyscanninga1%randomsampleofthepublicIPv4 rithmserverswillpreferinpractice. Inordertoestimatethis, address space for IKEv1 and IKEv2 (the protocols used to we performed a scan in which we mimicked the algorithms initiate an IPsec VPN connection) in May 2015. We used offered by OpenSSH 6.6.1p1, the latest version of OpenSSH. theZMapUDPprobemoduletomeasuresupportforOakley In this scan, 21.8% of servers preferred the 1024-bit Oakley Groups 1 and 2 (two popular 768- and 1024-bit, built-in Group2,and37.4%preferredaserver-definedgroup. 10%of groups) and which group servers prefer. To test support the server-defined groups were 1024-bit, but, of those, near for individual groups, we offered only the single group in all provided Oakley Group 2 rather than a custom group. question. To detect default behavior, we offered servers a Combining these equivalent choices, we find that a state- variety of DH groups, with the lowest priority groups being level attacker who performed NFS precomputations for the Oakley Groups 1 and 2. When measuring server preference, 1024-bit Oakley Group 2 (which has been in standards for we scanned with the 3DES symmetric cipher—the most almosttwodecades)couldpassivelyeavesdroponconnections commonly supported symmetric cipher in our single group to 3.6M (25.7%) publicly accessible SSH servers. scans. Becauseofthis,thepercentageswepresentforIKEv1 and IKEv2 are a lower bound for the number of servers that HTTPS DHEiscommonlydeployedonwebservers. 68.3% prefer Oakley Groups 1 and 2. of Alexa Top 1M sites support DHE, as do 23.9% of sites Of the 80K hosts that responded with a valid IKE packet, with browser-trusted certificates. Of the Top 1M sites that 44.2%werewillingtoacceptanofferedproposalfromatleast supportDHE,84%usea1024-bitorsmallergroup,with94% one scan. The majority of the remaining hosts responded of these using one of five groups. with a NO-PROPOSAL-CHOSEN message regardless of our pro- Despite widespread support for DHE, a passive eavesdrop- posal. Many of these may be site-to-site VPNs that reject per can only decrypt connections that organically agree to oursourceaddress. Weconsiderthesehosts“unprofiled”and use Diffie-Hellman. We can estimate the number of sites for omit them from the results here. whichthiswilloccurbyofferingthesamesetsofciphersuites Wefoundthat31.8%ofIKEv1and19.7%ofIKEv2servers as Chrome, Firefox, and Safari. While the offered ciphers support Oakley Group 1 (768-bit) while 86.1% and 91.0% differ slightly between browsers, this turns out to result in respectively supported Oakley Group 2 (1024-bit). In our negligible differences in whether DHE is chosen. sample of IKEv1 servers, 2.6% of profiled servers preferred Approximately24.0%ofbrowserconnectionswithHTTPS- the 768-bit Oakley Group 1—which is within cryptanalytic enabled Top 1M sites (and 10% with browser-trusted sites) reach today for moderately resourced attackers—and 66.1% willnegotiateDHEwithoneofthetenmostpopular1024-bit preferred the 1024-bit Oakley Group 2. For IKEv2, 5.8% primes; 17.9% of connections with Top 1M sites could be 10 passivelyeavesdroppedgiventheprecomputationforasingle Our analysis suggests that 1024-bit discrete log may be 1024-bit prime. The most popular site that negotiates a within reach for state-level actors. As such, 1024-bit DHE DHE ciphersuite using one of the two most common 1024-bit (and 1024-bit RSA) must be phased out in the near term. primes is sohu.com (ranked 31st globally). NIST has recommended such a transition since 2010 [4]. We Mail TLS is also used to secure email transport. SMTP, recommendthatclientsraisetheminimumDHEgroupsizeto | | | | | | | | | 2048bitsassoonasserverconfigurationsallow. | | | | | | Serveropera- | | | ------------ | ---- | --- | ----- | -------- | ------- | ------------- | --- | ------------------------------------------ | --- | --- | --- | --- | --- | ------------ | --- | | the protocol | used | to | relay | messages | between | mail servers, | | | | | | | | | | torsshouldmoveto2048-bitorlargergroupstofacilitatethis | allows a | connection | to | be upgraded | | to TLS by | issuing | the | | | | | | | | | | ---------------- | ---------- | ---------------------------- | ----------- | ---------- | ---------- | ------- | ---- | ----------- | -------------- | --------- | ------ | -------------- | -------------- | --- | ------ | | | | | | | | | | transition. | Precomputation | | | for a 2048-bit | non-trapdoored | | | | STARTTLScommand. | | POP3SandIMAPS,usedbyendusers | | | | | | | | | | | | | | | | | | | | | | | group is | around | 109 times | harder | than | for a 1024-bit | | group, | | to fetch | received | mail, | wrap | the entire | connection | in | TLS. | | | | | | | | | so2048-bitDiffie-Hellmanwillremainsecurebarringamajor | We studied | | 1% samples | of | the public | IPv4 | address | space | | | | | | | | | | ---------- | ------ | ---------- | -------------- | ---------- | ---- | ------- | ----- | ----------- | ------------ | --- | --- | --- | --- | --- | --- | | | | | | | | | | algorithmic | improvement. | | | | | | | | for IMAPS, | POP3S, | and | SMTP+StartTLS. | | We | found | that | | | | | | | | | 50.7% of SMTP servers supported STARTTLS, 41.4% sup- Avoid fixed-prime 1024-bit groups. For implementa- ported DHE, and 14.8% supported DHE_EXPORT ciphers. tions that must continue to use or support 1024-bit groups 15.5% of SMTP servers used one of the ten most common for compatibility reasons, generating fresh groups may help 1024-bit groups. mitigate some of the damage caused by NFS-style precom- For IMAPS, 8.4% of servers supported DHE_EXPORT and putation for very common fixed groups. However, we note 75%supportedDHE.However,thetenmostcommon1024-bit that it is possible to create trapdoored primes [20,44] that primes account for only 5.4% of servers. POP3S deployment are computationally difficult to detect. At minimum, clients is similar, with 8.9% of servers supporting DHE_EXPORT should check that servers’ parameters use safe primes or a and 74.9% supporting DHE, but with the ten most common verifiable generation process, such as that proposed in FIPS 1024-bit primes accounting for only 4.8% of servers. 186 [38]. Ideally, the process for generating and validating Ifeachofthetopten1024-bitprimesusedbyeachprotocol parameters in TLS should be standardized so as to thwart were compromised, this would affect approximately 1.7M the risk of trapdoors. | SMTP, 276K | IMAPS, | | and 245K | POP3S | servers. | Using | our | | | | | | | | | | ---------- | ------ | --- | -------- | ----- | -------- | ----- | --- | ------------------ | --- | ------ | --- | ------- | --- | --------- | --- | | | | | | | | | | Don’t deliberately | | weaken | | crypto. | Our | downgrade | | downgradeattackof§3.3,anattackerwithmodestresources attackonexport-grade512-bitDiffie-HellmangroupsinTLS | can hijack | connections | | to approximately | | 1.6M | SMTP, | 429K | | | | | | | | | | ---------- | ----------- | --- | ---------------- | --- | ---- | ----- | ---- | ----------- | --- | --------- | ---------------- | --- | ------ | ------- | --- | | | | | | | | | | illustrates | the | fragility | of cryptographic | | “front | doors”. | Al- | IMAPS, and 454K POP3S servers. though the key sizes originally used in DHE_EXPORT were | | | | | | | | | intended | to be | tractable | only | to NSA, | two decades | | of algo- | | --- | --- | --- | --- | --- | --- | --- | --- | -------- | ----- | --------- | ---- | ------- | ----------- | --- | -------- | 5. RECOMMENDATIONS rithmic and computational improvements have significantly | | | | | | | | | lowered | the bar | to attacks | on | such | key sizes. | Despite | the | | ---------------------- | -------- | -------- | ---- | --------- | ------------- | ------------ | ---- | -------------- | ---------- | ---------- | ------- | ------ | --------------- | ------- | ------ | | Our findings | | indicate | that | one of | the key | recommenda- | | | | | | | | | | | | | | | | | | | eventual | relaxation | of | crypto | export | restrictions | and | subse- | | tions from | security | experts | in | response | to the threat | of | mass | | | | | | | | | | | | | | | | | | quent attempts | | to remove | support | | for DHE_EXPORT, | | the | | surveillance—promotion | | | of | DHE-based | TLS | ciphersuites | | | | | | | | | | offering “perfect forward secrecy” over RSA-based cipher- technical debt induced by the additional complexity has left suites—may have actually reduced security for many hosts. implementations vulnerable for decades. Like FREAK [7], In this section, we present concrete recommendations to re- our attacks warn of the long-term debilitating effects of | | | | | | | | | deliberately | weakening | | cryptography. | | | | | | ---------- | -------- | ---------- | ------- | -------------- | ------------- | ---------- | ------ | ------------------------ | --------- | --- | ------------- | --- | --- | --- | --- | | cover the | expected | security | of | Diffie-Hellman | as | it is used | in | | | | | | | | | | mainstream | Internet | protocols. | | | | | | | | | | | | | | | | | | | | | | | 6. DISCLOSUREANDRESPONSE | | | | | | | | | Transition | to | elliptic | curves. | | Transitioning | to | ellip- | | | | | | | | | tic curve Diffie-Hellman (ECDH) key exchange with appro- We notified major client and server developers about | | | | | | | | | the vulnerabilities | | discussed | | in this | paper before | we | made | | ----------------- | ------- | ------------ | ----- | -------- | --------------- | ------------- | ---- | ------------------- | -------- | --------- | ------ | ------------ | ------------ | --------- | ------- | | priate parameters | | avoids | all | known | feasible | cryptanalytic | | | | | | | | | | | | | | | | | | | our findings | public. | Prior | to | our work, | Internet | Explorer, | | | attacks. | Current | elliptic | curve | discrete | log algorithms | | for | | | | | | | | | | | | | | | | | | Chrome, | Firefox, | and | Opera | all accepted | 512-bit | | primes, | | strong curves | | do not | gain | as much | of an advantage | | from | | | | | | | | | | | | | | | | | | whereas | Safari | allowed | groups | as small | as 16 | bits. | As a | | precomputation. | | In addition, | | ECDH | keys are | shorter | than | | | | | | | | | in “mod p” Diffie-Hellman, and shared-secret computations result of our disclosures, Internet Explorer [37], Firefox, and are faster. Unfortunately, the most widely supported ECDH ChromearetransitioningtheminimumsizeoftheDHEgroups parameters, those specified by NIST, are now viewed with they accept to 1024 bits, and OpenSSL and Safari are ex- suspicion due to NSA influence on their design, despite no pectedtofollowsuit. Ontheserverside,wenotifiedApache, known or suspected weaknesses. These curves are under- Oracle, IBM, Cisco, and various hosting providers. Aka- going scrutiny, and new curves, such as Curve25519, are mai has removed all support for export ciphersuites. Many being standardized by the IRTF for use in Internet proto- TLS developers plan to support a new extension that allows | | | | | | | | | clients and | servers | to negotiate | | a few | well-known | groups | of | | -------- | --------- | --- | ------------- | --- | -------- | ------ | ----- | ----------- | ------- | ------------ | --- | ----- | ---------- | ------ | --- | | cols. We | recommend | | transitioning | to | elliptic | curves | where | | | | | | | | | 2048-bitsandhigherandtogracefullyrejectweakones[19]. | possible; | this is | the most | effective | long-term | solution | | to the | | | | | | | | | | --------------- | ------- | --------- | -------------- | --------- | -------- | --------- | ------ | ------------- | --- | --- | --- | --- | --- | --- | --- | | vulnerabilities | | described | in this | paper. | | | | | | | | | | | | | | | | | | | | | 7. CONCLUSION | | | | | | | | | Increase | minimum | | key strengths. | | Server | operators | | | | | | | | | | shoulddisableDHE_EXPORTandconfigureDHEciphersuites Diffie-Hellman key exchange is a cornerstone of applied to use primes of 2048 bits or larger. Browsers and clients cryptography,butwefindthat,asusedinpractice,itisoften should raise the minimum accepted size for Diffie-Hellman less secure than widely believed. The problems stem from groups to at least 1024 bits in order to avoid downgrade at- thefactthatthenumberfieldsievefordiscretelogallowsan tackswhencommunicatingwithserversthatstillusesmaller attacker to perform a single precomputation that depends groups. Primes of less than 1024 bits should not be con- only on the group, after which computing individual logs in sidered secure, even against an attacker with moderate re- that group has a far lower cost. Although this fact is well sources. known to cryptographers, it apparently has not been widely 11 understood by system builders. Likewise, many cryptogra- [11] D.Coppersmith.SolvinglinearequationsoverGF(2)via | | | | | | | blockWiedemannalgorithm.Math. | | Comp.,62(205),1994. | | ----------- | -------------- | ------- | ------------ | -------------- | -------- | ---------------------------------------- | --- | ------------------- | | phers did | not appreciate | that | the security | of a large | fraction | | | | | | | | | | | [12] R.CrandallandC.B.Pomerance.Prime | | Numbers: A | | of Internet | communication | depends | on | Diffie-Hellman | key | | | | | | | | | | | Computational Perspective.Springer,2001. | | | | exchanges | that use a few | small, | widely | shared groups. | | | | | [13] B.denBoer.Diffie-Hellmanisasstrongasdiscretelogfor | A key | lesson from this | state | of affairs | is that | cryptogra- | | | | | ----- | ---------------- | ----- | ---------- | ------- | ---------- | --- | --- | --- | certainprimes.InCrypto,1988. phersandcreatorsofpracticalsystemsneedtoworktogether [14] W.DiffieandM.E.Hellman.Newdirectionsin | more effectively. | System | builders | should | take responsibility | | | | | | ----------------- | ------------------- | -------- | ------------- | ------------------- | ----- | ----------------- | -------------- | --------------------- | | | | | | | | cryptography.IEEE | Trans. Inform. | Theory,22(6):644–654, | | for being | aware of applicable | | cryptanalytic | attacks. | Cryp- | | | | 1976. | tographers, | for their part, | should | involve | themselves | in how | | | | | ----------- | --------------- | ------ | ------- | ---------- | ------ | --- | --- | --- | [15] Z.Durumeric,E.Wustrow,andJ.A.Halderman.ZMap: cryptoisactuallybeingapplied,suchasthroughengagement FastInternet-widescanninganditssecurityapplications.In withstandardseffortsandsoftwarereview. Bridgingtheper- Usenix Security,2013. ilous gap that separates these communities will be essential [16] M.Friedl,N.Provos,andW.Simpson.Diffie-Hellmangroup exchangeforthesecureshell(SSH)transportlayerprotocol. | for keeping | future systems | secure. | | | | | | | | ----------- | -------------- | ------- | --- | --- | --- | --- | --- | --- | RFC4419,Mar.2006. [17] W.Geiselmann,H.Kopfer,R.Steinwandt,andE.Tromer. Acknowledgments Improvedrouting-basedlinearalgebraforthenumberfield | | | | | | | sieve.InInformation | Technology: | Coding and Computing, | | ----------- | ------------- | ------- | ------- | ------ | ---------- | ------------------- | ----------- | --------------------- | | The authors | wish to thank | Michael | Bailey, | Daniel | Bernstein, | 2005. | | | RonDreslinski,TanjaLange,AdamLangley,KennyPaterson, [18] W.GeiselmannandR.Steinwandt.Non-wafer-scalesieving Andrei Popov, Ivan Ristic, Edward Snowden, Brian Smith, hardwarefortheNFS:Anotherattempttocopewith Martin Thomson, and Eric Rescorla. This material is based 1024-bit.InEurocrypt,2007. in part upon work supported by the U.S. National Science [19] D.Gillmor.NegotiatedfinitefieldDiffie-Hellmanephemeral Foundation under contracts CNS-1345254, CNS-1409505, parametersforTLS.IETFInternetDraft,May2015. CNS-1518741, and EFRI-1441209, by the Office of Naval [20] D.M.Gordon.Designinganddetectingtrapdoorsfor Research under contract N00014-11-1-0470, by the ERC discretelogcryptosystems.InCrypto,1992. Starting Grant 259639 (CRYSP), by the French ANR re- [21] D.M.Gordon.DiscretelogarithmsinGF(p)usingthe search grant ANR-12-BS02-001-01, by the NSF Graduate numberfieldsieve.SIAM J. Discrete Math.,6(1),1993. Research Fellowship Program under grant DGE-1256260, [22] D.HarkinsandD.Carrel.TheInternetkeyexchange(IKE). RFC2409,Nov.1998. by the Mozilla Foundation, by a gift from Supermicro, by [23] T.Jager,K.G.Paterson,andJ.Somorovsky.Onebad the Google Ph.D. Fellowship in Computer Security, by the apple: Backwardscompatibilityattacksonstate-of-the-art Morris Wellman Faculty Development Assistant Professor- cryptography.InNDSS,2013. ship,andbyanAlfredP.SloanFoundationResearchFellow- [24] A.JouxandR.Lercier.Improvementstothegeneral ship. Some experiments were conducted using the Grid’5000 numberfieldsievefordiscretelogarithmsinprimefields.A testbed, which is supported by INRIA, CNRS, RENATER, comparisonwiththeGaussianintegermethod.Math. Comp.,72(242):953–967,2003. | and several | other universities | | and organizations; | | additional | | | | | ----------- | ------------------ | --- | ------------------ | --- | ---------- | --- | --- | --- | experiments used UCS hardware donated by Cisco. [25] C.Kaufman,P.Hoffman,Y.Nir,P.Eronen,andT.Kivinen. Internetkeyexchangeprotocolversion2(IKEv2). RFC7296,Oct.2014. 8. REFERENCES [26] S.Kent.IPauthenticationheader.RFC4302,Dec.2005. [27] S.Kent.IPencapsulatingsecuritypayload(ESP). [1] S.Bai,C.Bouvier,A.Filbois,P.Gaudry,L.Imbert, RFC4303,Dec.2005. A.Kruppa,F.Morain,E.Thomé,andP.Zimmermann. [28] T.Kleinjung.Cofactorisationstrategiesforthenumberfield cado-nfs,animplementationofthenumberfieldsieve sieveandanestimateforthesievingstepforfactoring1024 algorithm,2014.Release2.1.1. bitintegers,2006.http://www.hyperelliptic.org/tanja/ [2] R.Barbulescu.Algorithmes de logarithmes discrets dans les SHARCS/talks06/thorsten.pdf. corps finis.PhDthesis,UniversitédeLorraine,France,2013. [3] R.Barbulescu,P.Gaudry,A.Joux,andE.Thomé.A [29] T.Kleinjung,K.Aoki,J.Franke,A.K.Lenstra,E.Thomé, J.W.Bos,P.Gaudry,A.Kruppa,P.L.Montgomery,D.A. heuristicquasi-polynomialalgorithmfordiscretelogarithm Osvik,H.teRiele,A.Timofeev,andP.Zimmermann. infinitefieldsofsmallcharacteristic.InEurocrypt,2014. Factorizationofa768-bitRSAmodulus.InCrypto,2010. [4] E.Barker,W.Barker,W.Burr,W.Polk,andM.Smid. [30] A.Langley,N.Modadugu,andB.Moeller.Transportlayer | NIST | Special Publication | 800-57: | Recommendation | | for Key | | | | | ---- | ------------------- | ------- | -------------- | --- | ------- | --- | --- | --- | Management,2007. security(TLS)falsestart.IETFInternetDraft,2010. [5] D.J.Bernstein.Howtofindsmoothpartsofintegers,2004. [31] A.K.LenstraandH.W.Lenstra,Jr.,editors.The http://cr.yp.to/factorization/smoothparts-20040510.pdf. Development of the Number Field Sieve.Springer,1993. [6] D.J.BernsteinandT.Lange.BatchNFS.InSelected Areas [32] M.Lipacis.Semiconductors: Moorestress=structural industryshift.Technicalreport,Jefferies,2012. in Cryptography,2014. [7] B.Beurdouche,K.Bhargavan,A.Delignat-Lavaud, [33] U.M.Maurer.Towardstheequivalenceofbreakingthe Diffie-Hellmanprotocolandcomputingdiscretelogarithms. C.Fournet,M.Kohlweiss,A.Pironti,P.-Y.Strub,andJ.K. InCrypto,1994. | Zinzindohoue.Amessystateoftheunion: | | | | Tamingthe | | | | | | ----------------------------------- | --- | --- | --- | --------- | --- | --- | --- | --- | compositestatemachinesofTLS.InIEEE Symposium on [34] U.M.MaurerandS.Wolf.Diffie-Hellmanoracles.InCrypto, | Security | and Privacy,2015. | | | | | 1996. | | | | -------- | ----------------- | --- | --- | --- | --- | ----- | --- | --- | [8] C.Bouvier,P.Gaudry,L.Imbert,H.Jeljeli,andE.Thomé. [35] N.Mavrogiannopoulos,F.Vercauteren,V.Velichkov,and Newrecordfordiscretelogarithminaprimefinitefieldof B.Preneel.Across-protocolattackontheTLSprotocol.In 180decimaldigits,2014.http://caramel.loria.fr/p180.txt. ACM CCS,pages62–72,2012. [9] R.CanettiandH.Krawczyk.SecurityanalysisofIKE’s [36] C.Meadows.AnalysisoftheInternetkeyexchangeprotocol | | | | | | | usingtheNRLprotocolanalyzer.InIEEE | | Symposium on | | --- | --- | --- | --- | --- | --- | ---------------------------------- | --- | ------------ | signature-basedkey-exchangeprotocol.InCrypto,2002. | | | | | | | Security and Privacy,1999. | | | | --- | --- | --- | --- | --- | --- | -------------------------- | --- | --- | [10] A.CommeineandI.Semaev.Analgorithmtosolvethe discretelogarithmproblemwiththenumberfieldsieve.In [37] MicrosoftSecurityBulletinMS15-055.Vulnerabilityin | PKC,2006. | | | | | | Schannelcouldallowinformationdisclosure,May2015. | | | | --------- | --- | --- | --- | --- | --- | ------------------------------------------------ | --- | --- | 12 [38] NIST.FIPSPUB186-4: Digitalsignaturestandard,2013. [54] P.Zimmermannetal.GMP-ECM,2012. [39] OakRidgeNationalLaboratory.IntroducingTitan,2012. https://gforge.inria.fr/projects/ecm. https://www.olcf.ornl.gov/titan. [55] APEXactive/passiveexfiltration.Medialeak,Aug.2009. [40] H.Orman.TheOakleykeydeterminationprotocol. http://www.spiegel.de/media/media-35671.pdf. RFC2412,Nov.1998. [56] Fieldedcapability: End-to-endVPNSPIN9designreview. [41] S.C.PohligandM.E.Hellman.Animprovedalgorithmfor Medialeak.http://www.spiegel.de/media/media-35529.pdf. computinglogarithmsoverGF(p)anditscryptographic [57] FY2013congressionalbudgetjustification.Medialeak. significance(corresp.).Trans. Inform. Theory,24(1),1978. http://cryptome.org/2013/08/spy-budget-fy13.pdf. [42] J.M.Pollard.AMonteCarlomethodforfactorization.BIT [58] GALLANTWAVE@scale.Medialeak. Numerical Mathematics,15(3):331–334,1975. http://www.spiegel.de/media/media-35514.pdf. [43] O.Schirokauer.Virtuallogarithms.J. Algorithms, [59] Innov8experimentprofile.Medialeak. 57(2):140–147,2005. http://www.spiegel.de/media/media-35509.pdf. [44] I.A.Semaev.Specialprimenumbersanddiscretelogsin [60] IntrototheVPNexploitationprocess.Medialeak,Sept. finiteprimefields.Math. Comp.,71(237):363–377,2002. 2010.http://www.spiegel.de/media/media-35515.pdf. [45] D.Shanks.Classnumber,atheoryoffactorization,and [61] LONGHAUL–WikiInfo.Medialeak. genera.InProc. Sympos. Pure Math.,volume20.1971. http://www.spiegel.de/media/media-35533.pdf. [46] SpiegelStaff.Pryingeyes: InsidetheNSA’swaronInternet [62] POISONNUT–WikiInfo.Medialeak. security.DerSpiegel,Dec2014. http://www.spiegel.de/media/media-35519.pdf. http://www.spiegel.de/international/germany/ [63] SIGINTstrategy.Medialeak. inside-the-nsa-s-war-on-internet-security-a-1010361.html. http://www.nytimes.com/interactive/2013/11/23/us/ [47] W.Steinetal.Sage Mathematics Software (Version 6.5). politics/23nsa-sigint-strategy-document.html. TheSageDevelopmentTeam,2015. [64] SPIN15VPNstory.Medialeak. http://www.sagemath.org. http://www.spiegel.de/media/media-35522.pdf. [48] stud: ThescalableTLSunwrappingdaemon,2012. [65] TURMOIL/APEX/APEXhighleveldescriptiondocument. https://github.com/bumptech/stud/blob/ Medialeak.http://www.spiegel.de/media/media-35513.pdf. 19a7f19686bcdbd689c6fbea31f68a276e62d886/stud.c#L593. [66] TURMOILIPsecVPNsessionization.Medialeak,Aug.2009. [49] E.Thomé.Subquadraticcomputationofvectorgenerating http://www.spiegel.de/media/media-35528.pdf. polynomialsandimprovementoftheblockWiedemann algorithm.J. Symbolic Comput.,33(5):757–775,2002. [67] TURMOILVPNprocessing.Medialeak,Oct.2009. [50] P.C.VanOorschotandM.J.Wiener.Parallelcollision http://www.spiegel.de/media/media-35526.pdf. searchwithapplicationtohashfunctionsanddiscrete [68] VALIANTSURF(VS):Capabilitylevels.Medialeak. logarithms.InACM CCS,1994. http://www.spiegel.de/media/media-35517.pdf. [51] P.C.VanOorschotandM.J.Wiener.OnDiffie-Hellman [69] VALIANTSURF–WikiInfo.Medialeak. keyagreementwithshortexponents.InEurocrypt,1996. http://www.spiegel.de/media/media-35527.pdf. [52] D.WagnerandB.Schneier.AnalysisoftheSSL3.0protocol. [70] VPNSigDevbasics.Medialeak. In2nd Usenix Workshop on Electronic Commerce,1996. http://www.spiegel.de/media/media-35520.pdf. [53] J.Wagnon.SSLprofilespart5: SSLoptions,2013.https:// [71] WhatyourmothernevertoldyouaboutSIGDEVanalysis. devcentral.f5.com/articles/ssl-profiles-part-5-ssl-options. Medialeak.http://www.spiegel.de/media/media-35551.pdf. 13