idnits 2.17.1 draft-ietf-tcpm-fastopen-08.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 : ---------------------------------------------------------------------------- ** There is 1 instance of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 11, 2014) is 3696 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 793 (Obsoleted by RFC 9293) -- Obsolete informational reference (is this intentional?): RFC 1323 (Obsoleted by RFC 7323) -- Obsolete informational reference (is this intentional?): RFC 1644 (Obsoleted by RFC 6247) -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) -- Obsolete informational reference (is this intentional?): RFC 6013 (Obsoleted by RFC 7805) == Outdated reference: A later version (-10) exists of draft-ietf-tcpm-fastopen-01 Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft Y. Cheng 3 draft-ietf-tcpm-fastopen-08.txt J. Chu 4 Intended status: Experimental S. Radhakrishnan 5 Expiration date: August, 2014 A. Jain 6 Google, Inc. 7 March 11, 2014 9 TCP Fast Open 11 Abstract 13 This document describes an experimental TCP mechanism TCP Fast Open 14 (TFO). TFO allows data to be carried in the SYN and SYN-ACK packets 15 and consumed by the receiving end during the initial connection 16 handshake, thus saving up to one full round trip time (RTT) compared 17 to the standard TCP, which requires a three-way handshake (3WHS) to 18 complete before data can be exchanged. However TFO deviates from the 19 standard TCP semantics since the data in the SYN could be replayed to 20 an application in some rare circumstances. Applications should not 21 use TFO unless they can tolerate this issue detailed in the 22 Applicability section. 24 Status of this Memo 26 Distribution of this memo is unlimited. 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF), its areas, and its working groups. Note that other 33 groups may also distribute working documents as Internet-Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/1id-abstracts.html 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html 46 Copyright Notice 48 Copyright (c) 2014 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Data In SYN . . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 2.1 Relaxing TCP Semantics on Duplicated SYNs . . . . . . . . . 4 67 2.2. SYNs with Spoofed IP Addresses . . . . . . . . . . . . . . 4 68 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 5 69 4. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7 70 4.1. Fast Open Cookie . . . . . . . . . . . . . . . . . . . . . 7 71 4.1.1. TCP Options . . . . . . . . . . . . . . . . . . . . . . 7 72 4.1.2. Server Cookie Handling . . . . . . . . . . . . . . . . 8 73 4.1.3. Client Cookie Handling . . . . . . . . . . . . . . . . 9 74 4.1.3.1 Client Caching Negative Responses . . . . . . . . . 9 75 4.2. Fast Open Protocol . . . . . . . . . . . . . . . . . . . . 10 76 4.2.1. Fast Open Cookie Request . . . . . . . . . . . . . . . 10 77 4.2.2. TCP Fast Open . . . . . . . . . . . . . . . . . . . . . 11 78 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 13 79 5.1. Resource Exhaustion Attack by SYN Flood with Valid 80 Cookies . . . . . . . . . . . . . . . . . . . . . . . . . . 13 81 5.1.1 Attacks from behind Shared Public IPs (NATs) . . . . . . 14 82 5.2. Amplified Reflection Attack to Random Host . . . . . . . . 15 83 6. TFO's Applicability . . . . . . . . . . . . . . . . . . . . . . 16 84 6.1 Duplicate Data in SYNs . . . . . . . . . . . . . . . . . . . 16 85 6.2 Potential Performance Improvement . . . . . . . . . . . . . 16 86 6.3. Example: Web Clients and Servers . . . . . . . . . . . . . 17 87 6.3.1. HTTP Request Replay . . . . . . . . . . . . . . . . . . 17 88 6.3.2. Speculative Connections by the Applications . . . . . . 17 89 6.3.3. HTTP over TLS (HTTPS) . . . . . . . . . . . . . . . . . 17 90 6.3.4. Comparison with HTTP Persistent Connections . . . . . . 17 91 7. Open Areas for Experimentation . . . . . . . . . . . . . . . . 18 92 7.1. Performance impact due to middle-boxes and NAT . . . . . . 18 93 7.2. Cookie-less Fast Open . . . . . . . . . . . . . . . . . . . 19 94 7.3 Impact on congestion control . . . . . . . . . . . . . . . . 19 95 8. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 20 96 8.1. T/TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 97 8.2. Common Defenses Against SYN Flood Attacks . . . . . . . . . 20 98 8.3. TCP Cookie Transaction (TCPCT) . . . . . . . . . . . . . . 20 100 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 20 101 10. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . 21 102 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 103 11.1. Normative References . . . . . . . . . . . . . . . . . . . 21 104 11.2. Informative References . . . . . . . . . . . . . . . . . . 21 105 Appendix A. Example Socket API Changes to support TFO . . . . . . 23 106 A.1 Active Open . . . . . . . . . . . . . . . . . . . . . . . . 23 107 A.2 Passive Open . . . . . . . . . . . . . . . . . . . . . . . . 23 108 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 110 1. Introduction 112 TCP Fast Open (TFO) is an experimental update to TCP that enables 113 data to be exchanged safely during TCP's connection handshake. This 114 document describes a design that enables applications to save a round 115 trip while avoiding severe security ramifications. At the core of TFO 116 is a security cookie used by the server side to authenticate a client 117 initiating a TFO connection. This document covers the details of 118 exchanging data during TCP's initial handshake, the protocol for TFO 119 cookies, potential new security vulnerabilities and their mitigation, 120 and the new socket API. 122 TFO is motivated by the performance needs of today's Web 123 applications. Current TCP only permits data exchange after the 3-way 124 handshake (3WHS)[RFC793], which adds one RTT to network latency. For 125 short Web transfers this additional RTT is a significant portion of 126 overall network latency, even when HTTP persistent connection is 127 widely used. For example, the Chrome browser keeps TCP connections 128 idle for up to 5 minutes but 35% of Chrome HTTP requests are made on 129 new TCP connections [RCCJR11]. For such Web and Web-like applications 130 placing data in the SYN can yield significant latency improvements. 131 Next we describe how we resolve the challenges that arise upon doing 132 so. 134 1.1 Terminology 136 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 137 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 138 document are to be interpreted as described in RFC 2119 [RFC2119]. 139 TFO refers to TCP Fast Open. Client refers to the TCP's active open 140 side and server refers to the TCP's passive open side. 142 2. Data In SYN 144 Standard TCP already allows data to be carried in SYN packets 145 ([RFC793], section 3.4) but forbids the receiver from delivering it 146 to the application until 3WHS is completed. This is because TCP's 147 initial handshake serves to capture old or duplicate SYNs. 149 To enable applications exchange data in TCP handshake, TFO removes 150 the constraint and allows data in SYN packets to be delivered to the 151 application. This change of TCP semantic raises two issues discussed 152 in the following subsections, making TFO unsuitable for certain 153 applications. 155 Therefore TCP implementations MUST NOT use TFO by default, but only 156 use TFO if requested explicitly by the application on a per service 157 port basis. Applications need to evaluate TFO applicability described 158 in Section 6 before using TFO. 160 2.1 Relaxing TCP Semantics on Duplicated SYNs 162 TFO allows data to be delivered to the application before the 3WHS 163 is completed, thus opening itself to a data integrity issue in either 164 of the two cases below: 166 a) the receiver host receives data in a duplicate SYN after it has 167 forgotten it received the original SYN (e.g. due to a reboot); 169 b) the duplicate is received after the connection created by the 170 original SYN has been closed and the close was initiated by the 171 sender (so the receiver will not be protected by the 2MSL TIMEWAIT 172 state). 174 The now obsoleted T/TCP [RFC1644] attempted to address these issues. 175 It was not successful and not deployed due to various vulnerabilities 176 as described in the Related Work section. Rather than trying to 177 capture all dubious SYN packets to make TFO 100% compatible with TCP 178 semantics, we made a design decision early on to accept old SYN 179 packets with data, i.e., to restrict TFO use to a class of 180 applications (Section 6) that are tolerant of duplicate SYN packets 181 with data. We believe this is the right design trade-off balancing 182 complexity with usefulness. 184 2.2. SYNs with Spoofed IP Addresses 186 Standard TCP suffers from the SYN flood attack [RFC4987] because SYN 187 packets with spoofed source IP addresses can easily fill up a 188 listener's small queue, causing a service port to be blocked 189 completely until timeouts. 191 TFO goes one step further to allow server-side TCP to send up data to 192 the application layer before 3WHS is completed. This opens up serious 193 new vulnerabilities. Applications serving ports that have TFO enabled 194 may waste lots of CPU and memory resources processing the requests 195 and producing the responses. If the response is much larger than the 196 request, the attacker can further mount an amplified reflection 197 attack against victims of choice beyond the TFO server itself. 199 Numerous mitigation techniques against regular SYN flood attacks 200 exist and have been well documented [RFC4987]. Unfortunately none are 201 applicable to TFO. We propose a server-supplied cookie to mitigate 202 these new vulnerabilities in Section 3 and evaluate the effectiveness 203 of the defense in Section 7. 205 3. Protocol Overview 207 The key component of TFO is the Fast Open Cookie (cookie), a message 208 authentication code (MAC) tag generated by the server. The client 209 requests a cookie in one regular TCP connection, then uses it for 210 future TCP connections to exchange data during 3WHS: 212 Requesting a Fast Open Cookie: 214 1. The client sends a SYN with a Fast Open Cookie Request option. 216 2. The server generates a cookie and sends it through the Fast Open 217 Cookie option of a SYN-ACK packet. 219 3. The client caches the cookie for future TCP Fast Open connections 220 (see below). 222 Performing TCP Fast Open: 224 1. The client sends a SYN with Fast Open Cookie option and data. 226 2. The server validates the cookie: 227 a. If the cookie is valid, the server sends a SYN-ACK 228 acknowledging both the SYN and the data. The server then 229 delivers the data to the application. 231 b. Otherwise, the server drops the data and sends a SYN-ACK 232 acknowledging only the SYN sequence number. 234 3. If the server accepts the data in the SYN packet, it may send the 235 response data before the handshake finishes. The maximum amount is 236 governed by the TCP's congestion control [RFC5681]. 238 4. The client sends an ACK acknowledging the SYN and the server data. 240 If the client's data is not acknowledged, the client retransmits 241 the data in the ACK packet. 243 5. The rest of the connection proceeds like a normal TCP connection. 244 The client can repeat many Fast Open operations once it acquires a 245 cookie (until the cookie is expired by the server). Thus TFO is 246 useful for applications that have temporal locality on client and 247 server connections. 249 Requesting Fast Open Cookie in connection 1: 251 TCP A (Client) TCP B(Server) 252 ______________ _____________ 253 CLOSED LISTEN 255 #1 SYN-SENT ----- ----------> SYN-RCVD 257 #2 ESTABLISHED <---- ---------- SYN-RCVD 258 (caches cookie C) 260 Performing TCP Fast Open in connection 2: 262 TCP A (Client) TCP B(Server) 263 ______________ _____________ 264 CLOSED LISTEN 266 #1 SYN-SENT ----- ----> SYN-RCVD 268 #2 ESTABLISHED <---- ---- SYN-RCVD 270 #3 ESTABLISHED <---- ---- SYN-RCVD 272 #4 ESTABLISHED ----- --------------------> ESTABLISHED 274 #5 ESTABLISHED --- ----------> ESTABLISHED 276 4. Protocol Details 278 4.1. Fast Open Cookie 280 The Fast Open Cookie is designed to mitigate new security 281 vulnerabilities in order to enable data exchange during handshake. 282 The cookie is a message authentication code tag generated by the 283 server and is opaque to the client; the client simply caches the 284 cookie and passes it back on subsequent SYN packets to open new 285 connections. The server can expire the cookie at any time to enhance 286 security. 288 4.1.1. TCP Options 290 Fast Open Cookie Option 292 The server uses this option to grant a cookie to the client in the 293 SYN-ACK packet; the client uses it to pass the cookie back to the 294 server in subsequent SYN packets. 296 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 297 | Kind | Length | 298 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 299 | | 300 ~ Cookie ~ 301 | | 302 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 304 Kind 1 byte: constant TBD (assigned by IANA) 305 Length 1 byte: range 6 to 18 (bytes); limited by 306 remaining space in the options field. 307 The number MUST be even. 308 Cookie 4 to 16 bytes (Length - 2) 309 Options with invalid Length values or without SYN flag set MUST be 310 ignored. The minimum Cookie size is 4 bytes. Although the diagram 311 shows a cookie aligned on 32-bit boundaries, alignment is not 312 required. 314 Fast Open Cookie Request Option 316 The client uses this option in the SYN packet to request a cookie 317 from a TFO-enabled server 318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 319 | Kind | Length | 320 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 322 Kind 1 byte: same as the Fast Open Cookie option 323 Length 1 byte: constant 2. This distinguishes the option 324 from the Fast Open cookie option. 325 Options with invalid Length values, without SYN flag set, or with ACK 326 flag set MUST be ignored. 328 4.1.2. Server Cookie Handling 330 The server is in charge of cookie generation and authentication. The 331 cookie SHOULD be a message authentication code tag with the following 332 properties: 333 1. The cookie authenticates the client's (source) IP address of the 334 SYN packet. The IP address may be an IPv4 or IPv6 address. 336 2. The cookie can only be generated by the server and can not be 337 fabricated by any other parties including the client. 339 3. The generation and verification are fast relative to the rest of 340 SYN and SYN-ACK processing. 342 4. A server may encode other information in the cookie, and accept 343 more than one valid cookie per client at any given time. But this 344 is server implementation dependent and transparent to the 345 client. 347 5. The cookie expires after a certain amount of time. The reason for 348 cookie expiration is detailed in the "Security Consideration" 349 section. This can be done by either periodically changing the 350 server key used to generate cookies or including a timestamp when 351 generating the cookie. 353 To gradually invalidate cookies over time, the server can 354 implement key rotation to generate and verify cookies using 355 multiple keys. This approach is useful for large-scale servers to 356 retain Fast Open rolling key updates. We do not specify a 357 particular mechanism because the implementation is server 358 specific. 360 The server supports the cookie generation and verification 361 operations: 363 - GetCookie(IP_Address): returns a (new) cookie 365 - IsCookieValid(IP_Address, Cookie): checks if the cookie is valid, 366 i.e., it has not expired and it authenticates the client IP address. 368 Example Implementation: a simple implementation is to use AES_128 to 369 encrypt the IPv4 (with padding) or IPv6 address and truncate to 64 370 bits. The server can periodically update the key to expire the 371 cookies. AES encryption on recent processors is fast and takes only a 372 few hundred nanoseconds [RCCJR11]. 374 If only one valid cookie is allowed per-IP and the server can 375 regenerate the cookie independently, the best validation process is 376 to simply regenerate a valid cookie and compare it against the 377 incoming cookie. In that case if the incoming cookie fails the check, 378 a valid cookie is readily available to be sent to the client. 380 4.1.3. Client Cookie Handling 382 The client MUST cache cookies from servers for later Fast Open 383 connections. For a multi-homed client, the cookies are both client 384 and server IP dependent. Beside the cookie we RECOMMEND that the 385 client caches the MSS to the server to enhance performance. 387 The MSS advertised by the server is stored in the cache to determine 388 the maximum amount of data that can be supported in the SYN packet. 389 This information is needed because data is sent before the server 390 announces its MSS in the SYN-ACK packet. Without this information, 391 the data size in the SYN packet is limited to the default MSS of 536 392 bytes for IPv4 [RFC1122] and 1240 bytes for IPv6 [RFC2460]. In 393 particular it's known an IPv4 receiver advertised MSS less than 536 394 bytes would result in transmission of an unexpected large segment. If 395 the cache MSS is larger than the typical 1460 bytes, the extra large 396 data in SYN segment may have issues that offsets the performance 397 benefit of Fast Open. For examples, the super-size SYN may trigger IP 398 fragmentation and may confuse firewall or middle-boxes, causing SYN 399 retransmission and other side-effects. Therefore the client MAY limit 400 the cached MSS to 1460 bytes. 402 4.1.3.1 Client Caching Negative Responses 404 The client MUST cache negative responses from the server in order to 405 avoid potential connection failures. Negative responses include 406 server not acknowledging the data in SYN, ICMP error messages, and 407 most importantly no response (SYN/ACK) from the server at all, i.e., 408 connection timeout. The last case is likely due to incompatible 409 middle-boxes or firewall blocking the connection completely after it 410 sees data in SYN. If the client does not react to these negative 411 responses and continue to retry Fast Open, the client may never be 412 able to connect to the specific server. 414 For any negative responses, the client SHOULD disable Fast Open on 415 the specific path (the source and destination IP addresses and ports) 416 at least temporarily. Since TFO is enabled on a per-service port 417 basis but cookies are independent of service ports, the client's 418 cache should include remote port numbers too. 420 4.2. Fast Open Protocol 422 One predominant requirement of TFO is to be fully compatible with 423 existing TCP implementations, both on the client and the server 424 sides. 426 The server keeps two variables per listening port: 428 FastOpenEnabled: default is off. It MUST be turned on explicitly by 429 the application. When this flag is off, the server does not perform 430 any TFO related operations and MUST ignore all cookie options. 432 PendingFastOpenRequests: tracks number of TFO connections in SYN-RCVD 433 state. If this variable goes over a preset system limit, the server 434 MUST disable TFO for all new connection requests until 435 PendingFastOpenRequests drops below the system limit. This variable 436 is used for defending some vulnerabilities discussed in the "Security 437 Considerations" section. 439 The server keeps a FastOpened flag per connection to mark if a 440 connection has successfully performed a TFO. 442 4.2.1. Fast Open Cookie Request 444 Any client attempting TFO MUST first request a cookie from the server 445 with the following steps: 447 1. The client sends a SYN packet with a Fast Open Cookie Request 448 option. 450 2. The server SHOULD respond with a SYN-ACK based on the procedures 451 in the "Server Cookie Handling" section. This SYN-ACK SHOULD 452 contain a Fast Open Cookie option if the server currently supports 453 TFO for this listener port. 455 3. If the SYN-ACK contains a Fast Open Cookie option, the client 456 replaces the cookie and other information as described in the 457 "Client Cookie Handling" section. Otherwise, if the SYN-ACK is 458 first seen, i.e., not a (spurious) retransmission, the client MAY 459 remove the server information from the cookie cache. If the SYN- 460 ACK is a spurious retransmission without valid Fast Open Cookie 461 Option, the client does nothing to the cookie cache for the 462 reasons below. 464 The network or servers may drop the SYN or SYN-ACK packets with the 465 new cookie options, which will cause SYN or SYN-ACK timeouts. We 466 RECOMMEND both the client and the server to retransmit SYN and SYN- 467 ACK without the cookie options on timeouts. This ensures the 468 connections of cookie requests will go through and lowers the latency 469 penalty (of dropped SYN/SYN-ACK packets). The obvious downside for 470 maximum compatibility is that any regular SYN drop will fail the 471 cookie (although one can argue the delay in the data transmission 472 till after 3WHS is justified if the SYN drop is due to network 473 congestion). Next section describes a heuristic to detect such drops 474 when the client receives the SYN-ACK. 476 We also RECOMMEND the client to record the set of servers that failed 477 to respond to cookie requests and only attempt another cookie request 478 after certain period. 480 An alternate proposal is to request a TFO cookie in the FIN instead, 481 since FIN-drop by incompatible middle-boxes does not affect latency. 482 However paths that block SYN cookies may be more likely to drop a 483 later SYN packet with data, and many applications close a connection 484 with RST instead anyway. 486 Although cookie-in-FIN may not improve robustness, it would give 487 clients using a single connection a latency advantage over clients 488 opening multiple parallel connections. If experiments with TFO find 489 that it leads to increased connection-sharding, cookie-in-FIN may 490 prove to be a useful alternative. 492 4.2.2. TCP Fast Open 494 Once the client obtains the cookie from the target server, it can 495 perform subsequent TFO connections until the cookie is expired by the 496 server. 498 Client: Sending SYN 500 To open a TFO connection, the client MUST have obtained a cookie from 501 the server: 503 1. Send a SYN packet. 505 a. If the SYN packet does not have enough option space for the 506 Fast Open Cookie option, abort TFO and fall back to regular 3WHS. 508 b. Otherwise, include the Fast Open Cookie option with the cookie 509 of the server. Include any data up to the cached server MSS or 510 default 536 bytes. 512 2. Advance to SYN-SENT state and update SND.NXT to include the data 513 accordingly. 515 To deal with network or servers dropping SYN packets with payload or 516 unknown options, when the SYN timer fires, the client SHOULD 517 retransmit a SYN packet without data and Fast Open Cookie options. 519 Server: Receiving SYN and responding with SYN-ACK 521 Upon receiving the SYN packet with Fast Open Cookie option: 523 1. Initialize and reset a local FastOpened flag. If FastOpenEnabled 524 is false, go to step 5. 526 2. If PendingFastOpenRequests is over the system limit, go to step 5. 528 3. If IsCookieValid() in section 4.1.2 returns false, go to step 5. 530 4. Buffer the data and notify the application. Set FastOpened flag 531 and increment PendingFastOpenRequests. 533 5. Send the SYN-ACK packet. The packet MAY include a Fast Open 534 Option. If FastOpened flag is set, the packet acknowledges the SYN 535 and data sequence. Otherwise it acknowledges only the SYN 536 sequence. The server MAY include data in the SYN-ACK packet if the 537 response data is readily available. Some application may favor 538 delaying the SYN-ACK, allowing the application to process the 539 request in order to produce a response, but this is left up to the 540 implementation. 542 6. Advance to the SYN-RCVD state. If the FastOpened flag is set, the 543 server MUST follow [RFC5681] (based on [RFC3390]) to set the 544 initial congestion window for sending more data packets. 546 If the SYN-ACK timer fires, the server SHOULD retransmit a SYN-ACK 547 segment with neither data nor Fast Open Cookie options for 548 compatibility reasons. 550 A special case is simultaneous open where the SYN receiver is a 551 client in SYN-SENT state. The protocol remains the same because 552 [RFC793] already supports both data in SYN and simultaneous open. But 553 the client's socket may have data available to read before it's 554 connected. This document does not cover the corresponding API change. 556 Client: Receiving SYN-ACK 558 The client SHOULD perform the following steps upon receiving the SYN- 559 ACK: 561 1. Update the cookie cache if the SYN-ACK has a Fast Open Cookie 562 Option or MSS option or both. 564 2. Send an ACK packet. Set acknowledgment number to RCV.NXT and 565 include the data after SND.UNA if data is available. 567 3. Advance to the ESTABLISHED state. 569 Note there is no latency penalty if the server does not acknowledge 570 the data in the original SYN packet. The client SHOULD retransmit any 571 unacknowledged data in the first ACK packet in step 2. The data 572 exchange will start after the handshake like a regular TCP 573 connection. 575 If the client has timed out and retransmitted only regular SYN 576 packets, it can heuristically detect paths that intentionally drop 577 SYN with Fast Open option or data. If the SYN-ACK acknowledges only 578 the initial sequence and does not carry a Fast Open cookie option, 579 presumably it is triggered by a retransmitted (regular) SYN and the 580 original SYN or the corresponding SYN-ACK was lost. 582 Server: Receiving ACK 584 Upon receiving an ACK acknowledging the SYN sequence, the server 585 decrements PendingFastOpenRequests and advances to the ESTABLISHED 586 state. No special handling is required further. 588 5. Security Considerations 590 The Fast Open cookie stops an attacker from trivially flooding 591 spoofed SYN packets with data to burn server resources or to mount an 592 amplified reflection attack on random hosts. The server can defend 593 against spoofed SYN floods with invalid cookies using existing 594 techniques [RFC4987]. We note that although generating bogus cookies 595 is cost-free, the cost of validating the cookies, inherent to any 596 authentication scheme, may be substantial compared to processing a 597 regular SYN packet. We describe these new vulnerabilities of TFO and 598 the countermeasures in detail below. 600 5.1. Resource Exhaustion Attack by SYN Flood with Valid Cookies 602 An attacker may still obtain cookies from some compromised hosts, 603 then flood spoofed SYN with data and "valid" cookies (from these 604 hosts or other vantage points). Like regular TCP handshakes, TFO is 605 vulnerable to such an attack. But the potential damage can be much 606 more severe. Besides causing temporary disruption to service ports 607 under attack, it may exhaust server CPU and memory resources. Such an 608 attack will show up on application server logs as a application level 609 DoS from Bot-nets, triggering other defenses and alerts. 611 To protect the server it is important to limit the maximum number of 612 total pending TFO connection requests, i.e., PendingFastOpenRequests 613 (Section 4.2). When the limit is exceeded, the server temporarily 614 disables TFO entirely as described in "Server Cookie Handling". Then 615 subsequent TFO requests will be downgraded to regular connection 616 requests, i.e., with the data dropped and only SYN acknowledged. This 617 allows regular SYN flood defense techniques [RFC4987] like SYN- 618 cookies to kick in and prevent further service disruption. 620 The main impact of SYN floods against the standard TCP stack is not 621 directly from the floods themselves costing TCP processing overhead 622 or host memory, but rather from the spoofed SYN packets filling up 623 the often small listener's queue. 625 On the other hand, TFO SYN floods can cause damage directly if 626 admitted without limit into the stack. The RST packets from the 627 spoofed host will fuel rather than defeat the SYN floods as compared 628 to the non-TFO case, because the attacker can flood more SYNs with 629 data to cost more data processing resources. For this reason, a TFO 630 server needs to monitor the connections in SYN-RCVD being reset in 631 addition to imposing a reasonable max queue length. Implementations 632 may combine the two, e.g., by continuing to account for those 633 connection requests that have just been reset against the listener's 634 PendingFastOpenRequests until a timeout period has passed. 636 Limiting the maximum number of pending TFO connection requests does 637 make it easy for an attacker to overflow the queue, causing TFO to be 638 disabled. We argue that causing TFO to be disabled is unlikely to be 639 of interest to attackers because the service will remain intact 640 without TFO hence there is hardly any real damage. 642 5.1.1 Attacks from behind Shared Public IPs (NATs) 644 An attacker behind a NAT can easily obtain valid cookies to launch 645 the above attack to hurt other clients that share the path. 646 [BRISCOE12] suggested that the server can extend cookie generation to 647 include the TCP timestamp---GetCookie(IP_Address, Timestamp)---and 648 implement it by encrypting the concatenation of the two values to 649 generate the cookie. The client stores both the cookie and its 650 corresponding timestamp, and echoes both in the SYN. The server then 651 implements IsCookieValid(IP_Address, Timestamp, Cookie) by encrypting 652 the IP and timestamp data and comparing it with the cookie value. 654 This enables the server to issue different cookies to clients that 655 share the same IP address, hence can selectively discard those 656 misused cookies from the attacker. However the attacker can simply 657 repeat the attack with new cookies. The server would eventually need 658 to throttle all requests from the IP address just like the current 659 approach. Moreover this approach requires modifying [RFC1323] to send 660 non-zero Timestamp Echo Reply in SYN, potentially cause firewall 661 issues. Therefore we believe the benefit does not outweigh the 662 drawbacks. 664 5.2. Amplified Reflection Attack to Random Host 666 Limiting PendingFastOpenRequests with a system limit can be done 667 without Fast Open Cookies and would protect the server from resource 668 exhaustion. It would also limit how much damage an attacker can cause 669 through an amplified reflection attack from that server. However, it 670 would still be vulnerable to an amplified reflection attack from a 671 large number of servers. An attacker can easily cause damage by 672 tricking many servers to respond with data packets at once to any 673 spoofed victim IP address of choice. 675 With the use of Fast Open Cookies, the attacker would first have to 676 steal a valid cookie from its target victim. This likely requires the 677 attacker to compromise the victim host or network first. But in some 678 case it may be relatively easy. 680 The attacker here has little interest in mounting an attack on the 681 victim host that has already been compromised. But it may be 682 motivated to disrupt the victim's network. Since a stolen cookie is 683 only valid for a single server, it has to steal valid cookies from a 684 large number of servers and use them before they expire to cause 685 sufficient damage without triggering the defense. 687 One can argue that if the attacker has compromised the target network 688 or hosts, it could perform a similar but simpler attack by injecting 689 bits directly. The degree of damage will be identical, but TFO- 690 specific attack allows the attacker to remain anonymous and disguises 691 the attack as from other servers. 693 For example with DHCP an attacker can obtain cookies when he (or the 694 host he has compromised) owns a particular IP address by performing 695 regular Fast Open to servers supporting TFO and collect valid 696 cookies. The attacker then actively or passively releases his IP 697 address. When the IP address is re-assigned to a victim, the attacker 698 now owning a different IP address, floods spoofed Fast Open requests 699 to perform an amplified reflection attack on the victim. 701 The best defense is for the server not to respond with data until 702 handshake finishes. In this case the risk of amplification reflection 703 attack is completely eliminated. But the potential latency saving 704 from TFO may diminish if the server application produces responses 705 earlier before the handshake completes. 707 6. TFO's Applicability 709 This section is to help applications considering TFO to evaluate 710 TFO's benefits and drawbacks using the Web client and server 711 applications as an example throughout. Applications here refer 712 specifically to the process that writes data into the socket, i.e., a 713 JavaScript process that sends data to the server. A proposed socket 714 API change is in the Appendix. 716 6.1 Duplicate Data in SYNs 718 It is possible that using TFO results in the first data written to a 719 socket to be delivered more than once to the application on the 720 remote host (Section 2.1). This replay potential only applies to data 721 in the SYN but not subsequent data exchanges. 723 Empirically [JIDKT07] showed the packet duplication on a Tier-1 724 network is rare. Since the replay only happens specifically when the 725 SYN data packet is duplicated and also the duplicate arrives after 726 the receiver has cleared the original SYN's connection state, the 727 replay is thought to be uncommon in practice. Neverthless a client 728 that cannot handle receiving the same SYN data more than once MUST 729 NOT enable TFO to send data in a SYN. Similarly a server that cannot 730 accept receiving the same SYN data more than once MUST NOT enable TFO 731 to receive data in a SYN. 733 6.2 Potential Performance Improvement 735 TFO is designed for latency-conscious applications that are sensitive 736 to TCP's initial connection setup delay. To benefit from TFO, the 737 first application data unit (e.g., an HTTP request) needs to be no 738 more than TCP's maximum segment size (minus options used in SYN). 739 Otherwise the remote server can only process the client's application 740 data unit once the rest of it is delivered after the initial 741 handshake, diminishing TFO's benefit. 743 To the extent possible, applications SHOULD reuse the connection to 744 take advantage of TCP's built-in congestion control and reduce 745 connection setup overhead. An application that employs too many 746 short-lived connections will negatively impact network stability, as 747 these connections often exit before TCP's congestion control 748 algorithm takes effect. 750 6.3. Example: Web Clients and Servers 752 6.3.1. HTTP Request Replay 754 While TFO is motivated by Web applications, the browser should not 755 use TFO to send requests in SYNs if those requests cannot tolerate 756 replays. One example is POST requests without application-layer 757 transaction protection (e.g., a unique identifier in the request 758 header). 760 On the other hand, TFO is particularly useful for GET requests. 761 Although not all GET requests are idem-potent, GETs are frequently 762 replayed today across striped TCP connections: after a server 763 receives an HTTP request but before the ACKs of the requests reach 764 the browser, the browser may timeout and retry the same request on 765 another (possibly new) TCP connection. This differs from a TFO replay 766 only in that the replay is initiated by the browser, not by the TCP 767 stack. 769 6.3.2. Speculative Connections by the Applications 771 Some Web browsers maintain a history of the domains for frequently 772 visited web pages. The browsers then speculatively pre-open TCP 773 connections to these domains before the user initiates any requests 774 for them [BELSHE11]. While this technique also saves the handshake 775 latency, it wastes server and network resources by initiating and 776 maintaining idle connections. 778 6.3.3. HTTP over TLS (HTTPS) 780 For TLS over TCP, it is safe and useful to include TLS CLIENT_HELLO 781 in the SYN packet to save one RTT in TLS handshake. There is no 782 concern about violating idem-potency. In particular it can be used 783 alone with the speculative connection above. 785 6.3.4. Comparison with HTTP Persistent Connections 787 Is TFO useful given the wide deployment of HTTP persistent 788 connections? The short answer is yes. Studies [RCCJR11][AERG11] show 789 that the average number of transactions per connection is between 2 790 and 4, based on large-scale measurements from both servers and 791 clients. In these studies, the servers and clients both kept idle 792 connections up to several minutes, well into "human think" time. 794 Keeping connections open and idle even longer risks a greater 795 performance penalty. [HNESSK10][MQXMZ11] show that the majority of 796 home routers and ISPs fail to meet the the 124-minute idle timeout 797 mandated in [RFC5382]. In [MQXMZ11], 35% of mobile ISPs silently 798 timeout idle connections within 30 minutes. End hosts, unaware of 799 silent middle-box timeouts, suffer multi-minute TCP timeouts upon 800 using those long-idle connections. 802 To circumvent this problem, some applications send frequent TCP keep- 803 alive probes. However, this technique drains power on mobile devices 804 [MQXMZ11]. In fact, power has become such a prominent issue in modern 805 LTE devices that mobile browsers close HTTP connections within 806 seconds or even immediately [SOUDERS11]. 808 [RCCJR11] studied Chrome browser performance based on 28 days of 809 global statistics. The Chrome browser keeps idle HTTP persistent 810 connections for 5 to 10 minutes. However the average number of the 811 transactions per connection is only 3.3 and TCP 3WHS accounts for up 812 to 25% of the HTTP transaction network latency. The authors estimated 813 that TFO improves page load time by 10% to 40% on selected popular 814 Web sites. 816 7. Open Areas for Experimentation 818 We now outline some areas that need experimentation in the Internet 819 and under different network scenarios. These experiments should help 820 the community evaluate Fast Open benefits and risks towards further 821 standardization and implementation of Fast Open and its related 822 protocols. 824 7.1. Performance impact due to middle-boxes and NAT 826 [MAF04] found that some middle-boxes and end-hosts may drop packets 827 with unknown TCP options. Studies [LANGLEY06, HNRGHT11] both found 828 that 6% of the probed paths on the Internet drop SYN packets with 829 data or with unknown TCP options. The TFO protocol deals with this 830 problem by falling back to regular TCP handshake and re-transmitting 831 SYN without data or cookie options after the initial SYN timeout. 832 Moreover the implementation is recommended to negatively cache such 833 incidents to avoid recurring timeouts. Further study is required to 834 evaluate the performance impact of these malicious drop behaviors. 836 Another interesting study is the (loss of) TFO performance benefit 837 behind certain carrier-grade NAT. Typically hosts behind a NAT 838 sharing the same IP address will get the same cookie for the same 839 server. This will not prevent TFO from working. But on some carrier- 840 grade NAT configurations where every new TCP connection from the same 841 physical host uses a different public IP address, TFO does not 842 provide latency benefits. However, there is no performance penalty 843 either, as described in Section "Client: Receiving SYN-ACK". 845 7.2. Cookie-less Fast Open 847 The cookie mechanism mitigates resource exhaustion and amplification 848 attacks. However cookies are not necessary if the server has 849 application-level protection or is immune to these attacks. For 850 example a Web server that only replies with a simple HTTP redirect 851 response that fits in the SYN-ACK packet may not care about resource 852 exhaustion. For such an application, the server could decide to 853 disable TFO cookie checks. 855 Disabling cookies (i.e., no Fast Open TCP options in SYN and SYN/ACK) 856 simplifies both the client and the server, as the client no longer 857 needs to request a cookie and the server no longer needs to check or 858 generate cookies. Disabling cookies also potentially simplifies 859 configuration, as the server no longer needs a key. It may be 860 preferable to enable SYN cookies and disable TFO [RFC4987] when a 861 server is overloaded by a large-scale Bot-net attack. 863 Careful experimentation is necessary to evaluate if cookie-less TFO 864 is practical. The implementation can provide an experimental feature 865 to allow zero length, or null, cookies as opposed to the minimum 4 866 bytes cookies. Thus the server may return a null cookie and the 867 client will send data in SYN with it subsequently. If the server 868 believes it's under a DoS attack through other defense mechanisms, it 869 can switch to regular Fast Open for listener sockets. 871 7.3 Impact on congestion control 873 Although TFO does not directly change the congestion control, there 874 are subtle cases that it may. When SYN-ACK times out, regular TCP 875 reduces the initial congestion window before sending any data 876 [RFC5681]. However in TFO the server may have already sent up to an 877 initial window of data. 879 If the server serves mostly short connections then the losses of SYN- 880 ACKs are not as effective as regular TCP on reducing the congestion 881 window. This could result in an unstable network condition. The 882 connections that experience losses may attempt again and add more 883 load under congestion. A potential solution is to temporarily disable 884 Fast Open if the server observes many SYN-ACK or data losses during 885 the handshake across connections. Further experimentation regarding 886 the congestion control impact will be useful. 888 8. Related Work 890 8.1. T/TCP 892 TCP Extensions for Transactions [RFC1644] attempted to bypass the 893 three-way handshake, among other things, hence shared the same goal 894 but also the same set of issues as TFO. It focused most of its effort 895 battling old or duplicate SYNs, but paid no attention to security 896 vulnerabilities it introduced when bypassing 3WHS [PHRACK98]. 898 As stated earlier, we take a practical approach to focus TFO on the 899 security aspect, while allowing old, duplicate SYN packets with data 900 after recognizing that 100% TCP semantics is likely infeasible. We 901 believe this approach strikes the right tradeoff, and makes TFO much 902 simpler and more appealing to TCP implementers and users. 904 8.2. Common Defenses Against SYN Flood Attacks 906 [RFC4987] studies on mitigating attacks from regular SYN flood, i.e., 907 SYN without data. But from the stateless SYN-cookies to the stateful 908 SYN Cache, none can preserve data sent with SYN safely while still 909 providing an effective defense. 911 The best defense may be to simply disable TFO when a host is 912 suspected to be under a SYN flood attack, e.g., the SYN backlog is 913 filled. Once TFO is disabled, normal SYN flood defenses can be 914 applied. The "Security Consideration" section contains a thorough 915 discussion on this topic. 917 8.3. TCP Cookie Transaction (TCPCT) 919 TCPCT [RFC6013] eliminates server state during initial handshake and 920 defends spoofing DoS attacks. Like TFO, TCPCT allows SYN and SYN-ACK 921 packets to carry data. But the server can only send up to MSS bytes 922 of data during the handshake instead of the initial congestion window 923 unlike TFO. Therefore the latency of applications such as Web may be 924 worse than with TFO. 926 9. IANA Considerations 928 The Fast Open Cookie Option and Fast Open Cookie Request Option 929 define no new namespace. The options require IANA to allocate one 930 value from the TCP option Kind namespace. Early implementation before 931 the IANA allocation SHOULD follow [RFC6994] and use experimental 932 option 254 and magic number 0xF989 (16 bits), then migrate to the new 933 option after the allocation accordingly. 935 10. Acknowledgement 937 We thank Bob Briscoe, Michael Scharf, Gorry Fairhurst, Rick Jones, 938 Roberto Peon, William Chan, Adam Langley, Neal Cardwell, Eric 939 Dumazet, and Matt Mathis for their feedbacks. We especially thank 940 Barath Raghavan for his contribution on the security design of Fast 941 Open and proofreading this draft numerous times. 943 11. References 945 11.1. Normative References 947 [RFC793] Postel, J. "Transmission Control Protocol", RFC 793, 948 September 1981. 950 [RFC1122] Braden, R., Ed., "Requirements for Internet Hosts - 951 Communication Layers", STD 3, RFC 1122, October 1989. 953 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 954 Requirement Levels", BCP 14, RFC 2119, March 1997. 956 [RFC5382] S. Guha, Ed., Biswas, K., Ford B., Sivakumar S., Srisuresh, 957 P., "NAT Behavioral Requirements for TCP", RFC 5382 959 [RFC5681] Allman, M., Paxson, V. and E. Blanton, "TCP Congestion 960 Control", RFC 5681, September 2009 962 [RFC6994] Touch, Joe, "Shared Use of Experimental TCP Options", 963 RFC6994, August 2013. 965 [RFC3390] Allman, M., Floyd, S., and C. Partridge, "Increasing TCP's 966 Initial Window", RFC 3390, October 2002. 968 11.2. Informative References 970 [AERG11] Al-Fares, M., Elmeleegy, K., Reed, B., Gashinsky, I., 971 "Overclocking the Yahoo! CDN for Faster Web Page Loads". 972 In Proceedings of Internet Measurement Conference, 973 November 2011. 975 [HNESSK10] Haetoenen, S., Nyrhinen, A., Eggert, L., Strowes, S., 976 Sarolahti, P., Kojo., M., "An Experimental Study of Home 977 Gateway Characteristics". In Proceedings of Internet 978 Measurement Conference. October 2010 980 [HNRGHT11] Honda, M., Nishida, Y., Raiciu, C., Greenhalgh, A., 981 Handley, M., Tokuda, H., "Is it Still Possible to 982 Extend TCP?". In Proceedings of Internet Measurement 983 Conference. November 2011. 985 [LANGLEY06] Langley, A, "Probing the viability of TCP extensions", 986 URL http://www.imperialviolet.org/binary/ecntest.pdf 988 [MAF04] Medina, A., Allman, M., and S. Floyd, "Measuring 989 Interactions Between Transport Protocols and 990 Middleboxes". In Proceedings of Internet Measurement 991 Conference, October 2004. 993 [MQXMZ11] Wang, Z., Qian, Z., Xu, Q., Mao, Z., Zhang, M., 994 "An Untold Story of Middleboxes in Cellular Networks". 995 In Proceedings of SIGCOMM. August 2011. 997 [PHRACK98] "T/TCP vulnerabilities", Phrack Magazine, Volume 8, Issue 998 53 artical 6. July 8, 1998. URL 999 http://www.phrack.com/issues.html?issue=53&id=6 1001 [RCCJR11] Radhakrishnan, S., Cheng, Y., Chu, J., Jain, A., 1002 Raghavan, B., "TCP Fast Open". In Proceedings of 7th 1003 ACM CoNEXT Conference, December 2011. 1005 [RFC1323] Jacobson, V., Braden, R., Borman, D., "TCP Extensions for 1006 High Performance", RFC 1323, May 1992. 1008 [RFC1644] Braden, R., "T/TCP -- TCP Extensions for Transactions 1009 Functional Specification", RFC 1644, July 1994. 1011 [RFC2460] Deering, S., Hinden, R., "Internet Protocol, Version 6 1012 (IPv6) Specification", RFC 2460, December 1998. 1014 [RFC4987] Eddy, W., "TCP SYN Flooding Attacks and Common 1015 Mitigations", RFC 4987, August 2007. 1017 [RFC6013] Simpson, W., "TCP Cookie Transactions (TCPCT)", RFC6013, 1018 January 2011. 1020 [SOUDERS11] Souders, S., "Making A Mobile Connection". 1021 http://www.stevesouders.com/blog/2011/09/21/making-a- 1022 mobile-connection/ 1024 [BRISCOE12] Briscoe, B., "Some ideas building on draft-ietf-tcpm- 1025 fastopen-01", tcpm list, 1026 http://www.ietf.org/mail-archive/web/tcpm/ 1027 current/msg07192.html 1029 [BELSHE11] Belshe, M., "The era of browser preconnect.", 1030 http://www.belshe.com/2011/02/10/ 1031 the-era-of-browser-preconnect/ 1033 [JIDKT07] Jaiswal, S., Iannaccone, G., Diot, C., Kurose, J., 1034 Towsley, D., "Measurement and classification of 1035 out-of-sequence packets in a tier-1 IP backbone.". 1036 IEEE/ACM Transactions on Networking (TON), 15(1), 54-66. 1038 Appendix A. Example Socket API Changes to support TFO 1040 A.1 Active Open 1042 The active open side involves changing or replacing the connect() 1043 call, which does not take a user data buffer argument. We recommend 1044 replacing connect() call to minimize API changes and hence 1045 applications to reduce the deployment hurdle. 1047 One solution implemented in Linux 3.7 is introducing a new flag 1048 MSG_FASTOPEN for sendto() or sendmsg(). MSG_FASTOPEN marks the 1049 attempt to send data in SYN like a combination of connect() and 1050 sendto(), by performing an implicit connect() operation. It blocks 1051 until the handshake has completed and the data is buffered. 1053 For non-blocking socket it returns the number of bytes buffered and 1054 sent in the SYN packet. If the cookie is not available locally, it 1055 returns -1 with errno EINPROGRESS, and sends a SYN with TFO cookie 1056 request automatically. The caller needs to write the data again when 1057 the socket is connected. On errors, it returns the same errno as 1058 connect() if the handshake fails. 1060 An implementation may prefer not to change the sendmsg() because TFO 1061 is a TCP specific feature. A solution is to add a new socket option 1062 TCP_FASTOPEN for TCP sockets. When the option is enabled before a 1063 connect operation, sendmsg() or sendto() will perform Fast Open 1064 operation similar to the MSG_FASTOPEN flag described above. This 1065 approach however requires an extra setsockopt() system call. 1067 A.2 Passive Open 1069 The passive open side change is simpler compared to active open side. 1070 The application only needs to enable the reception of Fast Open 1071 requests via a new TCP_FASTOPEN setsockopt() socket option before 1072 listen(). 1074 The option enables Fast Open on the listener socket. The option value 1075 specifies the PendingFastOpenRequests threshold, i.e., the maximum 1076 length of pending SYNs with data payload. Once enabled, the TCP 1077 implementation will respond with TFO cookies per request. 1079 Traditionally accept() returns only after a socket is connected. But 1080 for a Fast Open connection, accept() returns upon receiving a SYN 1081 with a valid Fast Open cookie and data, and the data is available to 1082 be read through, e.g., recvmsg(), read(). 1084 Authors' Addresses 1086 Yuchung Cheng 1087 Google, Inc. 1088 1600 Amphitheatre Parkway 1089 Mountain View, CA 94043, USA 1090 EMail: ycheng@google.com 1092 Jerry Chu 1093 Google, Inc. 1094 1600 Amphitheatre Parkway 1095 Mountain View, CA 94043, USA 1096 EMail: hkchu@google.com 1098 Sivasankar Radhakrishnan 1099 Department of Computer Science and Engineering 1100 University of California, San Diego 1101 9500 Gilman Dr 1102 La Jolla, CA 92093-0404 1103 EMail: sivasankar@cs.ucsd.edu 1105 Arvind Jain 1106 Google, Inc. 1107 1600 Amphitheatre Parkway 1108 Mountain View, CA 94043, USA 1109 EMail: arvind@google.com