Padding Policies for Extension Mechanisms for DNS (EDNS(0))
RFC 8467

INTERNET-DRAFT                                           Donald Eastlake
Intended Status: Proposed Standard                                Huawei
                                                            Mark Andrews
                                                                     ISC
Expires: May 29, 2015                                  November 30, 2014

                    Domain Name System (DNS) Cookies
                   <draft-ietf-dnsop-cookies-00.txt>

Abstract

   DNS cookies are a lightweight DNS transaction security mechanism that
   provides limited protection to DNS servers and clients against a
   variety of increasingly common denial-of-service and amplification /
   forgery or cache poisoning attacks by off-path attackers. DNS Cookies
   are tolerant of NAT, NAT-PT, and anycast and can be incrementally
   deployed.

Status of This Document

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

   Distribution of this document is unlimited. Comments should be sent
   to the author or the DNSEXT mailing list <dnsext@ietf.org>.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   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."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html. The list of Internet-Draft
   Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Donald Eastlake & Mark Andrews                                  [Page 1]
INTERNET-DRAFT                                               DNS Cookies

Table of Contents

      1. Introduction............................................3
      1.1 Contents of This Document..............................3
      1.2 Definitions............................................4

      2. Threats Considered......................................5
      2.1 Denial-of-Service Attacks..............................5
      2.1.1 DNS Amplification Attacks............................5
      2.1.2 DNS Server Denial-of-Service.........................5
      2.2 Cache Poisoning and Answer Forgery Attacks.............6

      3. Comments on Existing DNS Security.......................7
      3.1 Existing DNS Data Security.............................7
      3.2 DNS Message/Transaction Security.......................7
      3.3 Conclusions on Existing DNS Security...................7

      4. The COOKIE OPT Option...................................8
      4.1 Client Cookie..........................................9
      4.2 Server Cookie..........................................9
      4.3 Error Code............................................10

      5. DNS Cookies Protocol Description.......................11
      5.1 Originating Requests..................................11
      5.2 Responding to Requests................................11
      5.2.1 No OPT RR...........................................12
      5.2.2 No Valid Client Cookie..............................12
      5.2.3 Bad or Absent Server Cookie.........................13
      5.2.4 A Correct Server Cookie.............................13
      5.3 Processing Responses..................................14
      5.4 Client and Server Secret Rollover.....................14
      5.5 Implementation Requirement............................15

      6. NAT Considerations and AnyCast Server Considerations...16
      7. Deployment.............................................18
      8. IANA Considerations....................................19

      9. Security Considerations................................20
      9.1 Cookie Algorithm Considerations.......................20

      Acknowledgements..........................................21
      Normative References......................................22
      Informative References....................................22

      Appendix A: Example Client Cookie Algorithms..............24
      A.1 A Simple Algorithm....................................24
      A.2 A More Complex Algorithm..............................24

      Appendix B: Example Server Cookie Algorithms..............25
      B.1 A Simple Algorithm....................................25
      B.2 A More Complex Algorithm..............................25

Donald Eastlake & Mark Andrews                                  [Page 2]
INTERNET-DRAFT                                               DNS Cookies

1. Introduction

   As with many core Internet protocols, the Domain Name System (DNS)
   was originally designed at a time when the Internet had only a small
   pool of trusted users. As the Internet has grown exponentially to a
   global information utility, the DNS has increasingly been subject to
   abuse.

   This document describes DNS cookies, a lightweight DNS transaction
   security mechanism specified as an OPT [RFC6891] option.  This
   mechanism provides limited protection to DNS servers and clients
   against a variety of increasingly common abuses by off-path
   attackers. It is compatible with and can be used in conjunction with
   other DNS transaction forgery resistance measures such as those in
   [RFC5452].

   The protection provided by DNS cookies bears some resemblance to that
   provided by using TCP for DNS transactions. To bypass the weak
   protection provided by using TCP requires an off-path attacker
   guessing the 32-bit TCP sequence number in use. To bypass the weak
   protection provided by DNS Cookies requires such an attacker to guess
   a 64-bit pseudo-random quantity. Where DNS Cookies are not available
   but TCP is, a fall back to using TCP is a reasonable strategy.

   If only one party to a DNS transaction supports DNS cookies, the
   mechanism does not provide a benefit or significantly interfere; but,
   if both support it, the additional security provided is automatically
   available.

   The DNS cookies mechanism is designed to work in the presence of NAT
   and NAT-PT boxes and guidance is provided herein on supporting the
   DNS cookies mechanism in anycast servers.

1.1 Contents of This Document

   In Section 2, we discuss the threats against which the DNS cookie
   mechanism provides some protection.

   Section 3 describes existing DNS security mechanisms and why they are
   not adequate substitutes for DNS cookies.

   Section 4 describes the COOKIE OPT option.

   Section 5 provides a protocol description.

   Section 6 discusses some NAT and anycast related DNS Cookies design
   considerations.

Donald Eastlake & Mark Andrews                                  [Page 3]
INTERNET-DRAFT                                               DNS Cookies

   Section 7 discusses incremental deployment considerations.

   Sections 8 and 9 describe IANA and Security Considerations.

1.2 Definitions

   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].

   An "off-path attacker", for a particular DNS client and server, is
   defined as an attacker who cannot observe the DNS request and
   response messages between that client and server.

   "Soft state" indicates information learned or derived by a host which
   may be discarded when indicated by the policies of that host but can
   be later re-instantiated if needed.  For example, it could be
   discarded after a period of time or when storage for caching such
   data becomes full. If operations requiring that soft state continue
   after it has been discarded, it will be automatically re-generated,
   albeit at some cost.

   "Silently discarded" indicates that there are no DNS protocol message
   consequences; however, it is RECOMMENDED that appropriate network
   management facilities be included in implementations, such as a
   counter of the occurrences of each such event type.

   "IP address" is used herein as a length independent term and includes
   both IPv4 and IPv6 addresses.

Donald Eastlake & Mark Andrews                                  [Page 4]
INTERNET-DRAFT                                               DNS Cookies

Mayrhofer                     Experimental                      [Page 4]
RFC 8467              Padding Policies for EDNS(0)          October 2018

   The block size will interact with the MTU size.  Especially for
   length values that are a large fraction of the MTU, unless the block
   length is chosen so that a multiple just fits into the MTU, Block-
   Length Padding may cause unnecessary fragmentation for UDP-based
   delivery.  Of course, choosing a block length larger than the MTU
   always forces fragmentation.

   Note: Once DNSSEC-validating clients become more prevalent, observed
   size patterns are expected to change significantly.  In that case,
   the recommended strategy might need to be revisited.

4.2.  Other Strategies

4.2.1.  Maximal-Length Padding

   In Maximal-Length Padding, the sender pads every message to the
   maximum size allowed by protocol negotiations.

   Advantages: Maximal-Length Padding, when combined with encrypted
   transport, provides the highest possible level of message-size
   confidentiality.

   Disadvantages: Maximal-Length Padding is wasteful and requires
   resources on the client, all intervening networks and equipment, and
   the server.  Depending on the negotiated size, this strategy will
   commonly exceed the MTU and result in a consistent number of
   fragments, reducing delivery probability when datagram-based
   transport (such as UDP) is used.

   Due to resource consumption, Maximal-Length Padding is NOT
   RECOMMENDED.

4.2.2.  Random-Length Padding

   When using Random-Length Padding, a sender pads each message with a
   random amount of padding.  Due to the size of the "Padding" option
   itself, each message size is increased by at least 4 octets.  The
   upper limit for padding is the maximum message size.  However, a
   client or server may choose to impose a lower maximum padding length.

   Options: Maximum and minimum padding length.

   Advantages: Theoretically, this policy should create a natural
   distribution of message sizes.

   Disadvantage: Random-Length Padding allows an attacker who can
   observe a large number of requests to infer the length of the
   original value by observing the distribution of total lengths.

Mayrhofer                     Experimental                      [Page 5]
RFC 8467              Padding Policies for EDNS(0)          October 2018

   According to the limited empirical data available, Random-Length
   Padding exposes slightly more entropy to an attacker than Block-
   Length Padding.  Because of that, and the risk outlined above,
   Random-Length Padding is NOT RECOMMENDED.

4.2.3.  Random-Block-Length Padding

   This policy combines Block-Length Padding with a random component.
   Specifically, a sender randomly chooses between a few block length
   values and then applies Block-Length Padding based on the chosen
   block length.  The random selection of block length might even be
   reasonably based on a "weak" source of randomness, such as the
   transaction ID of the message.

   Options: Number of and the values for the set of block lengths;
   source of randomness

   Advantages: Compared to Block-Length Padding, this creates more
   variety in the resulting message sizes for a certain individual
   original message length.

   Disadvantage: Requires more implementation effort compared to simple
   Block-Length Padding.

   Random-Block-Length Padding requires further empirical study, as do
   other combinations of padding strategies.

5.  IANA Considerations

   This document has no IANA actions.

6.  Security Considerations

   The choice of the right padding policy (and the right parameters for
   the chosen policy) has a significant impact on the resilience of
   encrypted DNS against size-based correlation attacks.  Therefore, any
   implementor of the "Padding" option must carefully consider which
   policies to implement, the default policy chosen, which parameters to
   make configurable, and the default parameter values.

   No matter how carefully a client selects their padding policy, this
   effort can be jeopardized if the server chooses to apply an
   ineffective padding policy to the corresponding response packets.
   Therefore, a client applying the "Padding" option may want to choose
   a DNS server that applies a padding policy on responses that is at
   least equally effective.

Mayrhofer                     Experimental                      [Page 6]
RFC 8467              Padding Policies for EDNS(0)          October 2018

   Note that even with encryption and padding, it might be trivial to
   identify that the observed traffic is DNS.  Also, padding does not
   prevent information leaks via other side channels (particularly
   timing information and number of query/response pairs).
   Countermeasures against such side channels could include injecting
   artificial "cover traffic" into the stream of DNS messages or
   delaying DNS responses by a certain amount of jitter.  Such
   strategies are out of the scope of this document.  Additionally,
   there is not enough theoretic analysis or experimental data available
   to recommend any such countermeasures.

7.  References

7.1.  Normative References

   [NDSS-PADDING]
              Gillmor, D., "Empirical DNS Padding Policy", March 2017,
              <https://dns.cmrg.net/
              ndss2017-dprive-empirical-DNS-traffic-size.pdf>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC7830]  Mayrhofer, A., "The EDNS(0) Padding Option", RFC 7830,
              DOI 10.17487/RFC7830, May 2016,
              <https://www.rfc-editor.org/info/rfc7830>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

7.2.  Informative References

   [RFC7858]  Hu, Z., Zhu, L., Heidemann, J., Mankin, A., Wessels, D.,
              and P. Hoffman, "Specification for DNS over Transport
              Layer Security (TLS)", RFC 7858, DOI 10.17487/RFC7858, May
              2016, <https://www.rfc-editor.org/info/rfc7858>.

   [RFC8094]  Reddy, T., Wing, D., and P. Patil, "DNS over Datagram
              Transport Layer Security (DTLS)", RFC 8094,
              DOI 10.17487/RFC8094, February 2017,
              <https://www.rfc-editor.org/info/rfc8094>.

Mayrhofer                     Experimental                      [Page 7]
RFC 8467              Padding Policies for EDNS(0)          October 2018

Appendix A.  Padding Policies That Are Not Sensible

A.1.  No Padding

   In the No Padding policy, the "Padding" option is not used, and the
   size of the final (actually, "non-padded") message obviously exactly
   matches the size of the unpadded message.  Even though this
   "non-policy" seems redundant in this list, its properties must be
   considered for cases in which just one of the parties (client or
   server) applies padding.

   Also, this policy is required when the remaining message size of the
   unpadded message does not allow for the "Padding" option to be
   included -- i.e., there are fewer than 4 octets left.

   Advantages: This policy requires no additional resources on the
   client, server, and network side.

   Disadvantages: The original size of the message remains unchanged;
   hence, this approach provides no additional confidentiality.

   The No Padding policy MUST NOT be used unless message size disallows
   the use of the "Padding" option.

A.2.  Fixed-Length Padding

   In Fixed-Length Padding, a sender chooses to pad each message with a
   padding of constant length.

   Options: Actual length of padding

   Advantages: Since the padding is constant in length, this policy is
   very easy to implement and at least ensures that the message length
   diverges from the length of the original packet (even if only by a
   fixed value).

   Disadvantage: Obviously, the amount of padding is easily discoverable
   from a single unencrypted message or by observing message patterns.
   When a public DNS server applies this policy, the length of the
   padding hence must be assumed to be public knowledge.  Therefore,
   this policy is (almost) as useless as the No Padding policy described
   above.

   The Fixed-Length Padding policy MUST NOT be used except for test
   applications.

Mayrhofer                     Experimental                      [Page 8]
RFC 8467              Padding Policies for EDNS(0)          October 2018

Acknowledgements

   Daniel K. Gillmor performed empirical research out of which the
   "Recommended Strategy" was copied.  Stephane Bortzmeyer and Hugo
   Connery provided text.  Shane Kerr, Sara Dickinson, Paul Hoffman,
   Magnus Westerlund, Charlie Kaufman, Joe Clarke, and Meral Shirazipour
   performed reviews or provided substantial comments.

Author's Address

   Alexander Mayrhofer
   nic.at GmbH
   Karlsplatz 1/2/9
   Vienna  1010
   Austria

   Email: alex.mayrhofer.ietf@gmail.com
   URI:   http://edns0-padding.org/

Mayrhofer                     Experimental                      [Page 9]