RFC 8467

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

📅 published October 2018, from ietf

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

Okay bestie, this one is RFC 8467 💖 It's an IETF doc written by A. Mayrhofer at nic.at GmbH, it's in the Experimental category, and it's dated October 2018 (ISSN 2070-1721). It doesn't list anything it obsoletes or updates, so it's a clean, standalone vibe 🌸

Abstract ✨

RFC 7830 specifies the "Padding" option for Extension Mechanisms for DNS (EDNS(0)) but does not specify the actual padding length for specific applications. This memo lists the possible options ("padding policies"), discusses the implications of each option, and provides a recommended (experimental) option.

Status of This Memo 📜

This document is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation.

It defines an Experimental Protocol for the Internet community. It's a product of the Internet Engineering Task Force (IETF) and represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not every document the IESG approves is a candidate for any level of Internet Standard, so check out Section 2 of RFC 7841 for the full deets 🧐

You can find the current status of this document, any errata, and how to send feedback at https://www.rfc-editor.org/info/rfc8467.

Copyright (c) 2018 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 read these carefully, because they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they are provided without warranty as described in the Simplified BSD License.

Table of Contents 🗂️

   1. Introduction ....................................................2
   2. Terminology .....................................................2
   3. General Guidance ................................................3
   4. Padding Strategies ..............................................3
      4.1. Recommended Strategy: Block-Length Padding .................3
      4.2. Other Strategies ...........................................5
           4.2.1. Maximal-Length Padding ..............................5
           4.2.2. Random-Length Padding ...............................5
           4.2.3. Random-Block-Length Padding .........................6
   5. IANA Considerations .............................................6
   6. Security Considerations .........................................6
   7. References ......................................................7
      7.1. Normative References .......................................7
      7.2. Informative References .....................................7
   Appendix A.  Padding Policies That Are Not Sensible ................8
     A.1.  No Padding .................................................8
     A.2.  Fixed-Length Padding .......................................8
   Acknowledgements ...................................................9
   Author's Address ...................................................9

1. Introduction 🦋

Okay so [RFC7830] gives us the Extension Mechanisms for DNS (EDNS(0)) "Padding" option. It lets DNS clients and servers artificially increase the size of a DNS message by a variable number of bytes, which makes it way harder to correlate encrypted DNS messages by their size 🙈

BUT, and this is the tea ☕, RFC 7830 deliberately does not specify the actual length of padding to be used. So this memo is where we talk about the options for the actual size, list the pros and cons of each "padding strategy," and give you a recommended (experimental) strategy 🌈

Padding DNS messages is only useful when the transport is encrypted, using protocols like DNS over Transport Layer Security [RFC7858], DNS over Datagram Transport Layer Security [RFC8094], or other encrypted DNS transports specified in the future. No encryption, no slay 😭

2. Terminology 📚

Okay, the BCP 14 squad is up next 💅 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. Only the all-caps versions count, so the lowercase ones are just regular words 🫶

3. General Guidance 🍓

Here are the big-picture vibes for padding ✨

EDNS(0) options space: The maximum message length, as dictated by the protocol, limits the space for EDNS(0) options. Padding reduces the message space available to other EDNS(0) options, so the "Padding" option MUST be the last EDNS(0) option applied before a DNS message is sent 🎀

Resource Conservation: Especially when networking and processing resources are scarce (for example, battery-powered long-life devices, low bandwidth, or high-cost links), the trade-off between the increased size of padded DNS messages and the corresponding gain in confidentiality needs to be carefully considered ⚖️

Transport Protocol Independence: The message size used as input to the various padding strategies MUST be calculated excluding the potential extra 2-octet length field used in TCP transport. Otherwise, the padded (observable) size of the DNS packets could significantly change between different transport protocols and reveal an indication of the original (unpadded) length 👀

Here's an example to make it click. Say you've got a Block-Length Padding strategy with a block length of 32 octets and a DNS message that's 59 octets. Over UDP, the message gets padded to 64 octets. Now imagine that same message goes over TCP, and the padding strategy counts the extra 2 octets of the length field (61 octets total). Then the padded message would be 96 octets long, because the minimum length of the "Padding" option is 4 octets 😭💀

4. Padding Strategies 🧁

This section has a recommended strategy, plus a non-exhaustive list of other sensible strategies for choosing padding length. For completeness, Appendix A has two more strategies that are not sensible 🙃

Based on empirical research performed by Daniel K. Gillmor [NDSS-PADDING], padding SHOULD be performed following the Block-Length Padding strategy, as follows:

  1. Clients SHOULD pad queries to the closest multiple of 128 octets.
  2. If a server receives a query that includes the EDNS(0) "Padding" option, it MUST pad the corresponding response (see Section 4 of RFC 7830) and SHOULD pad the corresponding response to a multiple of 468 octets (see below).

Note that the recommendation above only applies if the DNS transport is encrypted (see Section 6 of RFC 7830). Bestie, read that twice 👑

In Block-Length Padding, a sender pads each message so that its padded length is a multiple of a chosen block length. This creates a greatly reduced variety of message lengths. An implementor needs to consider that even the zero-length "Padding" option increases the length of the packet by 4 octets. Even "nothing" adds 4 octets, lol 🙈

Options: Block length. For queries, values between 16 and 128 octets were discussed before empirical research was performed. Responses will require larger block sizes (see [NDSS-PADDING] and above for a discussion) 🌸

Very large block lengths have confidentiality properties similar to the Maximal-Length Padding strategy (Section 4.2.1), since almost all messages will fit into a single block. Such "very large block length" values are:

  • 288 bytes for the query (the maximum size of a one-question query over TCP, without any EDNS(0) options), and
  • the EDNS(0) buffer size of the server for the responses.

Advantages: This policy is reasonably easy to implement, reduces the variety of message ("fingerprint") sizes significantly, and does not require a source of (pseudo) random numbers, since the padding length required can be derived from the actual (unpadded) message. No randomness needed, iconic 🧚

Disadvantage: Given an unpadded message and the block size of the padding (which is assumed to be public knowledge once a server is reachable), the size range of a padded message can be predicted. Therefore, the minimum length of the unpadded message can be inferred. So the block size is kind of a spoiler 😬

The empirical research cited above ran a simulation of padding, based on real-world DNS traffic captured on busy recursive resolvers of a research network. The performance of individual padding policies was evaluated using a "cost to attacker" and a "cost to defender" function. The "cost to attacker" was defined as the percentage of query/response pairs falling into the same size bucket, and the "cost to defender" was defined as the size factor between padded and unpadded messages. Padding with a block size of 128 bytes on the query side and 468 bytes on the response side was considered the optimum trade-off between defender and attacker cost. The response block size of 468 was chosen so that 3 blocks of 468 octets would still comfortably fit into typical Maximum Transmission Unit (MTU) size values 📊✨

The block size interacts 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. Plot twist incoming 🦋

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. Maximum privacy energy 🔒

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. That's a lot of extra baggage 🧳💀

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. In theory, it's giving natural vibes 🌸

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. Not the move 😤

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. Okay, that's the tea for this section ☕💅

4.2.3. Random-Block-Length Padding 🎲✨

okay so this one is a combo move 💅 It mixes Block-Length Padding with a bit of randomness. The sender randomly picks from a few block length values, then does Block-Length Padding using whichever one it landed on 🎀 The random pick could even come from a "weak" source of randomness, like the transaction ID of the message 🧚

Options: the number of block lengths and their values, plus the source of randomness 🌸

Advantages: compared to plain Block-Length Padding, you get more variety in the final message sizes for one original message length 🦋

Disadvantage: it's more work to implement than simple Block-Length Padding 😭

Random-Block-Length Padding still needs more empirical study, same as other combos of padding strategies 🔬💜

5. IANA Considerations 🗂️

This document has no IANA actions. Nothing to register here, bestie 🫶

6. Security Considerations 🔐

okay this section is THE important one, so read it like it's your group chat's most serious plan 😭🔥

The choice of padding policy (and the parameters for that policy) has a huge impact on how well encrypted DNS holds up against size-based correlation attacks 💀 So any implementor of the "Padding" option has to think hard about which policies to implement, which default policy to pick, which parameters to make configurable, and what the default parameter values should be 👑

Here's the plot twist 🙈 No matter how carefully a client picks its padding policy, that effort can get wrecked if the server applies a weak padding policy to its response packets. So a client using the "Padding" option may want to choose a DNS server that pads responses at least as effectively 🫶

Also, even with encryption and padding, it might be super easy to tell that the traffic is DNS 👀 And padding doesn't stop information leaks through other side channels, especially timing and the number of query/response pairs ⏱️ Countermeasures for those side channels could include injecting artificial "cover traffic" into the DNS message stream, or delaying DNS responses by some amount of jitter 🌈 But those strategies are out of scope for this document, and there isn't enough theoretical analysis or experimental data out there to recommend any of them yet 🧐

Not me getting side-eyed by a timing attack. Padding alone is not the whole story, bestie 💀

7. References 📚

7.1. Normative References 💖

7.2. Informative References 🌷

Appendix A. Padding Policies That Are Not Sensible 🙅‍♀️

A.1. No Padding 🫥

in the No Padding policy, the "Padding" option isn't used at all, so the final (aka "non-padded") message size exactly matches the unpadded message size 📏 I know, it seems redundant to list a "non-policy" like this, but it still matters when only one side (client or server) is padding 🤔

This policy is also required when the unpadded message doesn't have room for the "Padding" option, meaning there are fewer than 4 octets left 🥲

Advantages: no extra resources needed on the client, server, or network side ✨

Disadvantages: the original message size stays the same, so this gives you zero extra confidentiality 💀

The No Padding policy MUST NOT be used unless the message size doesn't allow the "Padding" option 🛑

A.2. Fixed-Length Padding 🧱

in Fixed-Length Padding, the sender pads each message with a constant amount of padding 💅

Options: the actual length of the padding 🔢

Advantages: it's super easy to implement, and it at least makes sure the message length differs from the original packet length (even if only by a fixed value) 🌈

Disadvantage: the amount of padding is easy to spot from a single unencrypted message or by watching message patterns 👀 When a public DNS server uses this policy, the padding length has to be assumed to be public knowledge 📣 So this policy is (almost) as useless as the No Padding policy above 😭

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

Acknowledgements 🫶

Daniel K. Gillmor did the empirical research that the "Recommended Strategy" was copied from 🙌 Stephane Bortzmeyer and Hugo Connery provided text ✍️ Shane Kerr, Sara Dickinson, Paul Hoffman, Magnus Westerlund, Charlie Kaufman, Joe Clarke, and Meral Shirazipour did reviews or left 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/
📦 where this page comes from