TLS Client Puzzles Extension

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 7 May 2025.¶

Copyright Notice

Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Overview and rationale

Adversaries can exploit the design of the TLS protocol to craft powerful asymmetric DDOS attacks. Once an attacker has opened a TCP connection, the attacker can transmit effectively static content that causes the server to perform expensive cryptographic operations. Rate limiting offers one possible defense against this type of attack; however, pure rate limiting systems represent an incomplete solution:¶

1. Rate limiting systems work best when a small number of bots are attacking a single server. Rate limiting is much more difficult when a large number of bots are directing small amounts of traffic to each member of a large distributed pool of servers.¶

2. Rate limiting systems encounter problems where a mixture of “good” and “bad” clients are hidden behind a single NAT or Proxy IP address and thus are all stuck being treated on equal footing.¶

3. Rate limiting schemes often penalize well-behaved good clients (which try to complete handshakes and may limit their number of retries) much more heavily than they penalize attacking bad clients (which may try to disguise themselves as good clients, but which otherwise are not constrained to behave in any particular way).¶

Client puzzles are complementary to rate-limiting and give servers another option than just rejecting some fraction of requests. A server can provide a puzzle (of varying and server-selected complexity) to a client as part of a HelloRetryRequest extension. The client must choose to either abandon the connection or solve the puzzle and resend its ClientHello with a solution to the puzzle. Puzzles are designed to have asymmetric complexity such that it is much cheaper for the server to generate and validate puzzles than it is for clients to solve them.¶

Client puzzle systems may be inherently “unfair” to clients that run with limited resources (such as mobile devices with batteries and slow CPUs). However, client puzzle schemes will typically only be evoked when a server is under attack and would otherwise be rejecting some fraction of requests. The overwhelming majority of transactions will never involve a client puzzle. Indeed, if client puzzles are successful in forcing adversaries to use a new attack vector, the presence of client puzzles will be completely transparent to end users.¶

It is likely that not all clients will choose to support this extension. During attack scenarios, servers will still have the option to apply traditional rate limiting schemes (perhaps with different parameters) to clients not supporting this extension or using a version of TLS prior to 1.3.¶

2. Notational Conventions

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in [RFC2119].¶

Messages are formatted with the notation as described within [RFC8446].¶

3. Handshake Changes

Client puzzles are implemented as a new ClientPuzzleExtension to TLS 1.3 [RFC8446]. A client supporting the ClientPuzzleExtension MUST indicate support by sending a ClientPuzzleExtension along with their ClientHello containing a list of puzzle types supported, but with no puzzle response. When a server wishes to force the client to solve a puzzle, it MAY send a HelloRetryRequest with a ClientPuzzleExtension containing a puzzle of a supported puzzle type and with associated parameters. To continue with the handshake, a client MUST resend their ClientHello with a ClientPuzzleExtension containing a response to the puzzle. The ClientHello must otherwise be identical to the initial ClientHello, other than for attributes that are defined by specification to not be identical.¶

If a puzzle would consume too many resources, a client MAY choose to abort the handshake with the new fatal alert “puzzle_too_hard” and terminate the connection.¶

A typical handshake when a puzzle is issued will look like:¶

   Client                                               Server

   ClientHello
     + ClientPuzzleExtension
     + ClientKeyShare        -------->
                             <--------       HelloRetryRequest
                                       + ClientPuzzleExtension
   ClientHello
     + ClientPuzzleExtension
     + ClientKeyShare        -------->
                                                   ServerHello
                                                ServerKeyShare
                                        {EncryptedExtensions*}
                                        {ServerConfiguration*}
                                                {Certificate*}
                                         {CertificateRequest*}
                                          {CertificateVerify*}
                             <--------              {Finished}
   {Certificate*}
   {CertificateVerify*}
   {Finished}                -------->
   [Application Data]        <------->     [Application Data]

Figure 1. Message flow for a handshake with a client puzzle¶

* Indicates optional or situation-dependent messages that are not always sent.¶

{} Indicates messages protected using keys derived from the ephemeral secret.¶

[] Indicates messages protected using keys derived from the master secret.¶

Note in particular that the major cryptographic operations (starting to use the ephemeral secret and generating the CertificateVerify) are performed after the server has received and validated the ClientPuzzleExtension response from the client.¶

      struct {
          ClientPuzzleType type<2..254>;
          opaque client_puzzle_challenge_response<0..2^16-1>;
      } ClientPuzzleExtension;

      enum {
         echo (0),
         sha256_cpu (1),
         sha512_cpu (2),
         birthday_puzzle (3),
         (0xFFFF)
      } ClientPuzzleType;

4. Usage by Servers

Servers MAY send puzzles to clients when under duress, and the percentage of clients receiving puzzles and the complexity of the puzzles both MAY be selected as a function of the degree of duress.¶

Servers MAY use additional factors, such as client IP reputation information, to determine when to send a puzzle as well as the complexity.¶

5. GREASE

To exercise both the solvers in clients, as well as the mechanisms for adding new puzzle types, we add a greasing mechanism similar to that proposed in [RFC8701].¶

The following puzzle types are reserved as GREASE values for the puzzle type field:¶

• 0x0A0A¶

• 0x1A1A¶

• 0x2A2A¶

• 0x3A3A¶

• 0x4A4A¶

• 0x5A5A¶

• 0x6A6A¶

• 0x7A7A¶

• 0x8A8A¶

• 0x9A9A¶

• 0xAAAA¶

• 0xBABA¶

• 0xCACA¶

• 0xDADA¶

• 0xEAEA¶

• 0xFAFA¶

6. Proposed Client Puzzles

Having multiple client puzzle types allows good clients a choice to implement puzzles that match with their hardware capabilities (although this also applies to bad clients). It also allows “broken” puzzles to be phased out and retired, such as when cryptographic weaknesses are identified.¶

      struct {
          uint16 difficulty;
          uint8 salt<0..2^16-1>;
      } SHA256CPUPuzzleChallenge;

      struct {
          uint64 challenge_solution;
      } SHA256CPUPuzzleResponse;

      struct {
         uint16 n;
         uint16 k;
         uint16 difficulty;
         uint8 salt<0..2^16-1>;
     } BirthdayPuzzleChallenge;

     struct {
         uint8 V<20>;
         uint8 solution<0..2^16-1>;
     } BirthdayPuzzleResponse;

7. IANA Considerations

The IANA will need to assign an extension codepoint value for ClientPuzzleExtension.¶

The IANA will need to assign an AlertDescription codepoint value for puzzle_too_hard.¶

The IANA will also need to maintain a registry of client puzzle types.¶

8. Security Considerations

A hostile server could cause a client to consume unbounded resources. Clients MUST bound the amount of resources (cpu/time and memory) they will spend on a puzzle.¶

A puzzle type with economic utility could be abused by servers, resulting in unnecessary resource usage by clients. In the worst case, this could open up a new class of attacks where clients might be directed to malicious servers to get delegated work. As such, any new puzzle types SHOULD NOT be ones with utility for other purposes (such as mining cryptocurrency or cracking password hashes). Including fixed labels in new puzzle definitions may help mitigate this risk.¶

Depeding on the structure of the puzzles, it is possible that an attacker could send innocent clients to a hostile server and then use those clients to solve puzzles presented by another target server that the attacker wishes to attack. There may be ways to defend against this by including IP information in the puzzles (not currently proposed in this draft), although that introduces additional issues.¶

All extensions add complexity, which could expose additional attack surfaces on the client or the server. Using cryptographic primitives and patterns already in-use in TLS can help reduce (but certainly not eliminate) this complexity.¶

An attacker that can force a server into client puzzle mode could result in a denial of service to clients not supporting puzzles or not having the resources to complete the puzzles. This is not necessarily worse than if the server was overloaded and forced to deny service to all clients or to a random selection of clients. By using client puzzles, clients willing to rate-limit themselves to the rate at which they can solve puzzles should still be able to obtain service while the server is able to stay available for these clients.¶

It is inevitable that attackers will build hardware optimized to solve particular puzzles. Using common cryptographic primitives (such as SHA-256) also means that commonly deployed clients may have hardware assistance, although this also benefits legitimate clients.¶

9. Privacy Considerations

Measuring the response time of clients to puzzles gives an indication of the relative capabilities of clients. This could be used as an input for client fingerprinting.¶

Client’s support for this extension, as well as which puzzles they support, could also be used as an input for client fingerprinting.¶

10. Acknowledgments

The story of client puzzles dates back to Dwork and Naor [DN92] and Juels and Brainard [JB99]. This draft was in large part based on the 2016 draft by Nygren et. al. [I-D.nygren-tls-client-puzzles], which in turn was partially inspired by work done by Kyle Rose in 2001, as well as a 2001 paper by Drew Dean (Xerox PARC) and Adam Stubblefield (Rice) [SEC2001.DEAN], as well as being shaped by discussions with Eric Rescorla, Yoav Nir, Richard Willey, Rich Salz, Kyle Rose, Brian Sniffen, and others on the TLS working group. An alternate approach was proposed in [I-D.nir-tls-puzzles]. Some similar mechanisms for protecting IKE are discused in [RFC8019].¶

Authors' Addresses