idnits 2.17.1 draft-nygren-tls-client-puzzles-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([I-D.ietf-tls-tls13]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 302 has weird spacing: '...ficulty filte...' == Line 367 has weird spacing: '...ficulty secon...' == Line 371 has weird spacing: '...olution list ...' -- The document date (June 28, 2016) is 2831 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'I-D.josefsson-scrypt-kdf' is defined on line 516, but no explicit reference was found in the text == Outdated reference: A later version (-28) exists of draft-ietf-tls-tls13-13 == Outdated reference: A later version (-10) exists of draft-ietf-ipsecme-ddos-protection-06 Summary: 1 error (**), 0 flaws (~~), 7 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group E. Nygren 3 Internet-Draft S. Erb 4 Intended status: Standards Track Akamai Technologies 5 Expires: December 30, 2016 A. Biryukov 6 D. Khovratovich 7 University of Luxembourg 8 June 28, 2016 10 TLS Client Puzzles Extension 11 draft-nygren-tls-client-puzzles-01 13 Abstract 15 Client puzzles allow a TLS server to defend itself against asymmetric 16 DDoS attacks. In particular, it allows a server to request clients 17 perform a selected amount of computation prior to the server 18 performing expensive cryptographic operations. This allows servers 19 to employ a layered defense that represents an improvement over pure 20 rate-limiting strategies. 22 Client puzzles are implemented as an extension to TLS 1.3 23 [I-D.ietf-tls-tls13] wherein a server can issue a HelloRetryRequest 24 containing the puzzle as an extension. The client must then resend 25 its ClientHello with the puzzle results in the extension. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at http://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on December 30, 2016. 44 Copyright Notice 46 Copyright (c) 2016 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (http://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Overview and rationale . . . . . . . . . . . . . . . . . . . 2 62 2. Notational Conventions . . . . . . . . . . . . . . . . . . . 3 63 3. Handshake Changes . . . . . . . . . . . . . . . . . . . . . . 4 64 3.1. The ClientPuzzleExtension Message . . . . . . . . . . . . 5 65 4. Usage by Servers . . . . . . . . . . . . . . . . . . . . . . 6 66 5. Proposed Client Puzzles . . . . . . . . . . . . . . . . . . . 6 67 5.1. Cookie Client Puzzle Type . . . . . . . . . . . . . . . . 7 68 5.2. SHA-256 CPU Puzzle Type . . . . . . . . . . . . . . . . . 7 69 5.3. SHA-512 CPU Puzzle Type . . . . . . . . . . . . . . . . . 8 70 5.4. Equihash: Memory-hard Generalized Birthday Problem Puzzle 71 Type . . . . . . . . . . . . . . . . . . . . . . . . . . 8 72 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 73 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 74 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 11 75 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 11 76 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 77 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 78 10.2. Informative References . . . . . . . . . . . . . . . . . 12 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 81 1. Overview and rationale 83 Adversaries can exploit the design of the TLS protocol to craft 84 powerful asymmetric DDOS attacks. Once an attacker has opened a TCP 85 connection, the attacker can transmit effectively static content that 86 causes the server to perform expensive cryptographic operations. 87 Rate limiting offers one possible defense against this type of 88 attack; however, pure rate limiting systems represent an incomplete 89 solution: 91 1. Rate limiting systems work best when a small number of bots are 92 attacking a single server. Rate limiting is much more difficult 93 when a large number of bots are directing small amounts of 94 traffic to each member of a large distributed pool of servers. 96 2. Rate limiting systems encounter problems where a mixture of 97 "good" and "bad" clients are hidden behind a single NAT or Proxy 98 IP address and thus are all stuck being treated on equal footing. 100 3. Rate limiting schemes often penalize well-behaved good clients 101 (which try to complete handshakes and may limit their number of 102 retries) much more heavily than they penalize attacking bad 103 clients (which may try to disguise themselves as good clients, 104 but which otherwise are not constrained to behave in any 105 particular way). 107 Client puzzles are complementary to rate-limiting and give servers 108 another option than just rejecting some fraction of requests. A 109 server can provide a puzzle (of varying and server-selected 110 complexity) to a client as part of a HelloRetryRequest extension. 111 The client must choose to either abandon the connection or solve the 112 puzzle and resend its ClientHello with a solution to the puzzle. 113 Puzzles are designed to have asymmetric complexity such that it is 114 much cheaper for the server to generate and validate puzzles than it 115 is for clients to solve them. 117 Client puzzle systems may be inherently "unfair" to clients that run 118 with limited resources (such as mobile devices with batteries and 119 slow CPUs). However, client puzzle schemes will typically only be 120 evoked when a server is under attack and would otherwise be rejecting 121 some fraction of requests. The overwhelming majority of transactions 122 will never involve a client puzzle. Indeed, if client puzzles are 123 successful in forcing adversaries to use a new attack vector, the 124 presence of client puzzles will be completely transparent to end 125 users. 127 It is likely that not all clients will choose to support this 128 extension. During attack scenarios, servers will still have the 129 option to apply traditional rate limiting schemes (perhaps with 130 different parameters) to clients not supporting this extension or 131 using a version of TLS prior to 1.3. 133 2. Notational Conventions 135 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 136 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 137 document are to be interpreted as described in [RFC2119]. 139 Messages are formatted with the notation as described within 140 [I-D.ietf-tls-tls13]. 142 3. Handshake Changes 144 Client puzzles are implemented as a new ClientPuzzleExtension to TLS 145 1.3 [I-D.ietf-tls-tls13]. A client supporting the 146 ClientPuzzleExtension MUST indicate support by sending a 147 ClientPuzzleExtension along with their ClientHello containing a list 148 of puzzle types supported, but with no puzzle response. When a 149 server wishes to force the client to solve a puzzle, it MAY send a 150 HelloRetryRequest with a ClientPuzzleExtension containing a puzzle of 151 a supported puzzle type and with associated parameters. To continue 152 with the handshake, a client MUST resend their ClientHello with a 153 ClientPuzzleExtension containing a response to the puzzle. The 154 ClientHello must otherwise be identical to the initial ClientHello, 155 other than for attributes that are defined by specification to not be 156 identical. 158 Puzzles issued by the server contain a token that the client must 159 include in their response. This allows a server to issue puzzles 160 without retaining state, which is particularly useful when used in 161 conjunction with DTLS. 163 If a puzzle would consume too many resources, a client MAY choose to 164 abort the handshake with the new fatal alert "puzzle_too_hard" and 165 terminate the connection. 167 A typical handshake when a puzzle is issued will look like: 169 Client Server 171 ClientHello 172 + ClientPuzzleExtension 173 + ClientKeyShare --------> 174 <-------- HelloRetryRequest 175 + ClientPuzzleExtension 176 ClientHello 177 + ClientPuzzleExtension 178 + ClientKeyShare --------> 179 ServerHello 180 ServerKeyShare 181 {EncryptedExtensions*} 182 {ServerConfiguration*} 183 {Certificate*} 184 {CertificateRequest*} 185 {CertificateVerify*} 186 <-------- {Finished} 187 {Certificate*} 188 {CertificateVerify*} 189 {Finished} --------> 190 [Application Data] <-------> [Application Data] 192 Figure 1. Message flow for a handshake with a client puzzle 194 * Indicates optional or situation-dependent messages that are not 195 always sent. 197 {} Indicates messages protected using keys derived from the ephemeral 198 secret. 200 [] Indicates messages protected using keys derived from the master 201 secret. 203 Note in particular that the major cryptographic operations (starting 204 to use the ephemeral secret and generating the CertificateVerify) are 205 performed _after_ the server has received and validated the 206 ClientPuzzleExtension response from the client. 208 3.1. The ClientPuzzleExtension Message 210 The ClientPuzzleExtension message contains an indication of supported 211 puzzle types during the initial ClientHello, a selected puzzle type 212 and puzzle challenge during HelloRetryRequest, and the puzzle type 213 and puzzle response in the retried ClientHello: 215 struct { 216 ClientPuzzleType type<1..255>; 217 opaque client_puzzle_challenge_response<0..2^16-1>; 218 } ClientPuzzleExtension; 220 enum { 221 cookie (0), 222 sha256_cpu (1), 223 sha512_cpu (2), 224 birthday_puzzle (3), 225 (0xFFFF) 226 } ClientPuzzleType; 228 type During initial ClientHello, a vector of supported client puzzle 229 types. During the HelloRetryRequest, a vector of exactly one 230 element containing the proposed puzzle. During the retried 231 ClientHello, a vector containing exactly one element with the type 232 of the puzzle being responded to. 234 client_puzzle_challenge_response Data specific to the puzzle type, 235 as defined in Section (#puzzles). In the initial ClientHello, 236 this MUST be empty (zero-length). During HelloRetryRequest, this 237 contains the challenge. During the retried ClientHello, this 238 contains a response to the challenge. Puzzles containing a token 239 may have it within this field. 241 4. Usage by Servers 243 Servers MAY send puzzles to clients when under duress, and the 244 percentage of clients receiving puzzles and the complexity of the 245 puzzles both MAY be selected as a function of the degree of duress. 247 Servers MAY also occasionally send puzzles to clients under normal 248 operating circumstances to ensure that the extension works properly. 250 Servers MAY use additional factors, such as client IP reputation 251 information, to determine when to send a puzzle as well as the 252 complexity. 254 5. Proposed Client Puzzles 256 Having multiple client puzzle types allows good clients a choice to 257 implement puzzles that match with their hardware capabilities 258 (although this also applies to bad clients). It also allows "broken" 259 puzzles to be phased out and retired, such as when cryptographic 260 weaknesses are identified. 262 5.1. Cookie Client Puzzle Type 264 The "cookie" ClientPuzzleType is intended to be trivial. The 265 client_puzzle_challenge_response data field is defined to be a token 266 that the client must echo back. 268 During an initial ClientHello, this MUST be empty (zero-length). 269 During HelloRetryRequest, the server MAY send a cookie challenge of 270 zero or more bytes as client_puzzle_challenge_response . During the 271 retried ClientHello, the client MUST respond by resending the 272 identical cookie sent in the HelloRetryRequest. 274 5.2. SHA-256 CPU Puzzle Type 276 This puzzle forces the client to calculate a SHA-256 [RFC5754] 277 multiple times. In particular, the server selects a difficulty and a 278 random salt. The client solves the puzzle by finding any nonce where 279 a SHA-256 hash across the nonce, the salt and a label contains 280 difficulty leading zero bits. 282 struct { 283 opaque token<0..2^16-1>; 284 uint16 difficulty; 285 uint8 salt<0..2^16-1>; 286 } SHA256CPUPuzzleChallenge; 288 struct { 289 opaque token<0..2^16-1>; 290 uint64 challenge_solution; 291 } SHA256CPUPuzzleResponse; 293 token The token allows the server to encapsulate and drop state, and 294 also acts as a cookie for DTLS. During an initial ClientHello, 295 this MUST be empty (zero-length). During HelloRetryRequest, the 296 server MAY send a token challenge of zero or more bytes. During 297 the retried ClientHello, the client MUST respond by resending the 298 identical token sent in the HelloRetryRequest. Servers MAY 299 included an authenticated version of difficulty and salt in this 300 token if they wish to be stateless. 302 difficulty filter affecting the time to find solution. 304 salt A server selected variable-length bytestring. 306 challenge_solution The solution response to the puzzle, as solved by 307 the client. 309 To find the response, the client must find a numeric value of 310 challenge_solution where: 312 SHA-256(challenge_solution || salt || label) contains difficulty 313 leading zeros. 315 where "||" denotes concatenation and where label is the NUL- 316 terminated value "TLS SHA256CPUPuzzle" (including the NUL 317 terminator). 319 Clients offering to support this puzzle type SHOULD support a 320 difficulty value of at least 18. [[TODO: is this a good value? 321 https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison has a 322 comparison of SHA256 on various hardware.]] 324 5.3. SHA-512 CPU Puzzle Type 326 The SHA-512 CPU Puzzle Type is identical to the "SHA256 CPU Puzzle 327 Type" except that the SHA-512 [RFC5754] hash function is used instead 328 of SHA-256. The label used is the value "TLS SHA512CPUPuzzle". 330 Clients offering to support this puzzle type SHOULD support 331 difficulty values of at least 17. [[TODO: is this a good value?]] 333 5.4. Equihash: Memory-hard Generalized Birthday Problem Puzzle Type 335 Using Equihash, the asymmetric memory-hard generalized birthday 336 problem PoW [NDSS2016], this puzzle will force a client to use a 337 significant amount of memory to solve. The solution to this puzzle 338 can be trivially verified. 340 struct { 341 opaque token<0..2^16-1>; 342 uint16 n; 343 uint16 k; 344 uint16 difficulty; 345 uint8 salt<0..2^16-1>; 346 } BirthdayPuzzleChallenge; 348 struct { 349 opaque token<0..2^16-1>; 350 uint8 V<20>; 351 uint8 solution<0..2^16-1>; 352 } BirthdayPuzzleResponse; 354 token The token allows the server to encapsulate and drop state, and 355 also acts as a cookie for DTLS. During an initial ClientHello, 356 this MUST be empty (zero-length). During HelloRetryRequest, the 357 server MAY send a token challenge of zero or more bytes. During 358 the retried ClientHello, the client MUST respond by resending the 359 identical token sent in the HelloRetryRequest. Servers MAY 360 included an authenticated version of n, k, difficulty and salt in 361 this token if they wish to be stateless. 363 salt A server selected variable-length bytestring. 365 n, k parameters affecting the complexity of Wagner's algorithm. 367 difficulty secondary filter affecting the time to find solution. 369 V 20 byte nonce used in solution. 371 solution list of 2^k (n/(k+1)+1)-bit nonces used in solution, 372 referred to as xi below. 374 In the further text, the output of blake2b is treated as a 512-bit 375 register with most significant bits coming from the last bytes of 376 blake2b output (i.e. little-endian conversion). 378 To compute the response, the client must find a V and 2^k solutions 379 such that: 381 blake2b(salt||V||x1) XOR blake2b(salt||V||x2) XOR ... XOR 382 blake2b(I||V||x(2^k)) = 0 383 blake2b(label||salt||V||x1||x2||...||x(2^k)) has difficulty leading 384 zero bits. 386 where "||" denotes concatenation and where label is the NUL- 387 terminated value "TLS BirthdayPuzzle" (including the NUL terminator). 388 Incomplete bytes in nonces xi are padded with zero bits, which occupy 389 the most significant bits. 391 The client MUST provide the solution list in an order that allows a 392 server to verify the solution was created using Wagner's algorithm: 394 blake2b(salt||V||x(w_2^l+1)) XOR blake2b(salt||V||x(w_2^l+2)) XOR ... 395 XOR blake2b(I||V||x(w*2^l+2^l)) has nl/(k+1) leading zero bits for 396 all w,l. 398 and two 2^(l-1)(n/(k+1)+1)-bit numbers Z1 and Z2 must satisfy Z1. 504 [RFC5754] Turner, S., "Using SHA2 Algorithms with Cryptographic 505 Message Syntax", RFC 5754, DOI 10.17487/RFC5754, January 506 2010, . 508 10.2. Informative References 510 [I-D.ietf-ipsecme-ddos-protection] 511 Nir, Y. and V. Smyslov, "Protecting Internet Key Exchange 512 Protocol version 2 (IKEv2) Implementations from 513 Distributed Denial of Service Attacks", draft-ietf- 514 ipsecme-ddos-protection-06 (work in progress), April 2016. 516 [I-D.josefsson-scrypt-kdf] 517 Percival, C. and S. Josefsson, "The scrypt Password-Based 518 Key Derivation Function", draft-josefsson-scrypt-kdf-05 519 (work in progress), May 2016. 521 [I-D.nir-tls-puzzles] 522 Nir, Y., "Using Client Puzzles to Protect TLS Servers From 523 Denial of Service Attacks", draft-nir-tls-puzzles-00 (work 524 in progress), April 2014. 526 [NDSS2016] 527 Biryukov, A. and D. Khovratovich, "Equihash: Asymmetric 528 proof-of-work based on the Generalized Birthday problem", 529 February 2016, 530 . 534 [SEC2001.DEAN] 535 Dean, D. and A. Stubblefield, "Using Client Puzzles to 536 Protect TLS", Proceedings of the 10th USENIX Security 537 Symposium , August 2001, 538 . 541 Authors' Addresses 542 Erik Nygren 543 Akamai Technologies 545 EMail: erik+ietf@nygren.org 546 URI: http://erik.nygren.org/ 548 Samuel Erb 549 Akamai Technologies 551 EMail: serb@akamai.com 553 Alex Biryukov 554 University of Luxembourg 556 EMail: alex.biryukov@uni.lu 558 Dmitry Khovratovich 559 University of Luxembourg 561 EMail: khovratovich@gmail.com