1 Internet Engineering Task Force (IETF) A. Mayrhofer
2 Request for Comments: 8467 nic.at GmbH
3 Category: Experimental October 2018
4 ISSN: 2070-1721
5
6
7 Padding Policies for Extension Mechanisms for DNS (EDNS(0))
8
9 Abstract
10
11 RFC 7830 specifies the "Padding" option for Extension Mechanisms for
12 DNS (EDNS(0)) but does not specify the actual padding length for
13 specific applications. This memo lists the possible options
14 ("padding policies"), discusses the implications of each option, and
15 provides a recommended (experimental) option.
16
17 Status of This Memo
18
19 This document is not an Internet Standards Track specification; it is
20 published for examination, experimental implementation, and
21 evaluation.
22
23 This document defines an Experimental Protocol for the Internet
24 community. This document is a product of the Internet Engineering
25 Task Force (IETF). It represents the consensus of the IETF
26 community. It has received public review and has been approved for
27 publication by the Internet Engineering Steering Group (IESG). Not
28 all documents approved by the IESG are candidates for any level of
29 Internet Standard; see Section 2 of RFC 7841.
30
31 Information about the current status of this document, any errata,
32 and how to provide feedback on it may be obtained at
33 https://www.rfc-editor.org/info/rfc8467.
34
35 Copyright Notice
36
37 Copyright (c) 2018 IETF Trust and the persons identified as the
38 document authors. All rights reserved.
39
40 This document is subject to BCP 78 and the IETF Trust's Legal
41 Provisions Relating to IETF Documents
42 (https://trustee.ietf.org/license-info) in effect on the date of
43 publication of this document. Please review these documents
44 carefully, as they describe your rights and restrictions with respect
45 to this document. Code Components extracted from this document must
46 include Simplified BSD License text as described in Section 4.e of
47 the Trust Legal Provisions and are provided without warranty as
48 described in the Simplified BSD License.
49
50
51
52 Mayrhofer Experimental [Page 1]
53 RFC 8467 Padding Policies for EDNS(0) October 2018
54
55
56 Table of Contents
57
58 1. Introduction ....................................................2
59 2. Terminology .....................................................2
60 3. General Guidance ................................................3
61 4. Padding Strategies ..............................................3
62 4.1. Recommended Strategy: Block-Length Padding .................3
63 4.2. Other Strategies ...........................................5
64 4.2.1. Maximal-Length Padding ..............................5
65 4.2.2. Random-Length Padding ...............................5
66 4.2.3. Random-Block-Length Padding .........................6
67 5. IANA Considerations .............................................6
68 6. Security Considerations .........................................6
69 7. References ......................................................7
70 7.1. Normative References .......................................7
71 7.2. Informative References .....................................7
72 Appendix A. Padding Policies That Are Not Sensible ................8
73 A.1. No Padding .................................................8
74 A.2. Fixed-Length Padding .......................................8
75 Acknowledgements ...................................................9
76 Author's Address ...................................................9
77
78 1. Introduction
79
80 [RFC7830] specifies the Extension Mechanisms for DNS (EDNS(0))
81 "Padding" option, which allows DNS clients and servers to
82 artificially increase the size of a DNS message by a variable number
83 of bytes, hampering size-based correlation of encrypted DNS messages.
84
85 However, RFC 7830 deliberately does not specify the actual length of
86 padding to be used. This memo discusses options regarding the actual
87 size of padding, lists advantages and disadvantages of each of these
88 "padding strategies", and provides a recommended (experimental)
89 strategy.
90
91 Padding DNS messages is useful only when transport is encrypted using
92 protocols such as DNS over Transport Layer Security [RFC7858], DNS
93 over Datagram Transport Layer Security [RFC8094], or other encrypted
94 DNS transports specified in the future.
95
96 2. Terminology
97
98 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
99 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
100 "OPTIONAL" in this document are to be interpreted as described in
101 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
102 capitals, as shown here.
103
104
105
106
107 Mayrhofer Experimental [Page 2]
108 RFC 8467 Padding Policies for EDNS(0) October 2018
109
110
111 3. General Guidance
112
113 EDNS(0) options space: The maximum message length, as dictated by the
114 protocol, limits the space for EDNS(0) options. Since padding will
115 reduce the message space available to other EDNS(0) options, the
116 "Padding" option MUST be the last EDNS(0) option applied before a DNS
117 message is sent.
118
119 Resource Conservation: Especially in situations where networking and
120 processing resources are scarce (e.g., battery-powered long-life
121 devices, low bandwidth, or high-cost links), the trade-off between
122 increased size of padded DNS messages and the corresponding gain in
123 confidentiality must be carefully considered.
124
125 Transport Protocol Independence: The message size used as input to
126 the various padding strategies MUST be calculated excluding the
127 potential extra 2-octet length field used in TCP transport.
128 Otherwise, the padded (observable) size of the DNS packets could
129 significantly change between different transport protocols and reveal
130 an indication of the original (unpadded) length. For example, given
131 a Block-Length Padding strategy with a block length of 32 octets and
132 a DNS message with a size of 59 octets, the message would be padded
133 to 64 octets when transported over UDP. If that same message were
134 transported over TCP and the padding strategy considered the extra 2
135 octets of the length field (61 octets in total), the padded message
136 would be 96 octets long (as the minimum length of the "Padding"
137 option is 4 octets).
138
139 4. Padding Strategies
140
141 This section contains a recommended strategy, as well as a
142 non-exhaustive list of other sensible strategies, for choosing
143 padding length. Note that, for completeness, Appendix A contains two
144 more strategies that are not sensible.
145
146 4.1. Recommended Strategy: Block-Length Padding
147
148 Based on empirical research performed by Daniel K. Gillmor
149 [NDSS-PADDING], padding SHOULD be performed following the Block-
150 Length Padding strategy as follows:
151
152 (1) Clients SHOULD pad queries to the closest multiple of 128
153 octets.
154
155 (2) If a server receives a query that includes the EDNS(0) "Padding"
156 option, it MUST pad the corresponding response (see Section 4 of
157 RFC 7830) and SHOULD pad the corresponding response to a
158 multiple of 468 octets (see below).
159
160
161
162 Mayrhofer Experimental [Page 3]
163 RFC 8467 Padding Policies for EDNS(0) October 2018
164
165
166 Note that the recommendation above only applies if the DNS transport
167 is encrypted (see Section 6 of RFC 7830).
168
169 In Block-Length Padding, a sender pads each message so that its
170 padded length is a multiple of a chosen block length. This creates a
171 greatly reduced variety of message lengths. An implementor needs to
172 consider that even the zero-length "Padding" option increases the
173 length of the packet by 4 octets.
174
175 Options: Block length. For queries, values between 16 and 128 octets
176 were discussed before empiric research was performed. Responses will
177 require larger block sizes (see [NDSS-PADDING] and above for a
178 discussion).
179
180 Very large block lengths will have confidentiality properties similar
181 to the Maximal-Length Padding strategy (Section 4.2.1), since almost
182 all messages will fit into a single block. Such "very large block
183 length" values are:
184
185 o 288 bytes for the query (the maximum size of a one-question query
186 over TCP, without any EDNS(0) options) and
187
188 o the EDNS(0) buffer size of the server for the responses.
189
190 Advantages: This policy is reasonably easy to implement, reduces the
191 variety of message ("fingerprint") sizes significantly, and does not
192 require a source of (pseudo) random numbers, since the padding length
193 required can be derived from the actual (unpadded) message.
194
195 Disadvantage: Given an unpadded message and the block size of the
196 padding (which is assumed to be public knowledge once a server is
197 reachable), the size range of a padded message can be predicted.
198 Therefore, the minimum length of the unpadded message can be
199 inferred.
200
201 The empirical research cited above performed a simulation of padding,
202 based on real-world DNS traffic captured on busy recursive resolvers
203 of a research network. The evaluation of the performance of
204 individual padding policies was based on a "cost to attacker" and
205 "cost to defender" function, where the "cost to attacker" was defined
206 as the percentage of query/response pairs falling into the same size
207 bucket and "cost to defender" was defined as the size factor between
208 padded and unpadded messages. Padding with a block size of 128 bytes
209 on the query side and 468 bytes on the response side was considered
210 the optimum trade-off between defender and attacker cost. The
211 response block size of 468 was chosen so that 3 blocks of 468 octets
212 would still comfortably fit into typical Maximum Transmission Unit
213 (MTU) size values.
214
215
216
217 Mayrhofer Experimental [Page 4]
218 RFC 8467 Padding Policies for EDNS(0) October 2018
219
220
221 The block size will interact with the MTU size. Especially for
222 length values that are a large fraction of the MTU, unless the block
223 length is chosen so that a multiple just fits into the MTU, Block-
224 Length Padding may cause unnecessary fragmentation for UDP-based
225 delivery. Of course, choosing a block length larger than the MTU
226 always forces fragmentation.
227
228 Note: Once DNSSEC-validating clients become more prevalent, observed
229 size patterns are expected to change significantly. In that case,
230 the recommended strategy might need to be revisited.
231
232 4.2. Other Strategies
233
234 4.2.1. Maximal-Length Padding
235
236 In Maximal-Length Padding, the sender pads every message to the
237 maximum size allowed by protocol negotiations.
238
239 Advantages: Maximal-Length Padding, when combined with encrypted
240 transport, provides the highest possible level of message-size
241 confidentiality.
242
243 Disadvantages: Maximal-Length Padding is wasteful and requires
244 resources on the client, all intervening networks and equipment, and
245 the server. Depending on the negotiated size, this strategy will
246 commonly exceed the MTU and result in a consistent number of
247 fragments, reducing delivery probability when datagram-based
248 transport (such as UDP) is used.
249
250 Due to resource consumption, Maximal-Length Padding is NOT
251 RECOMMENDED.
252
253 4.2.2. Random-Length Padding
254
255 When using Random-Length Padding, a sender pads each message with a
256 random amount of padding. Due to the size of the "Padding" option
257 itself, each message size is increased by at least 4 octets. The
258 upper limit for padding is the maximum message size. However, a
259 client or server may choose to impose a lower maximum padding length.
260
261 Options: Maximum and minimum padding length.
262
263 Advantages: Theoretically, this policy should create a natural
264 distribution of message sizes.
265
266 Disadvantage: Random-Length Padding allows an attacker who can
267 observe a large number of requests to infer the length of the
268 original value by observing the distribution of total lengths.
269
270
271
272 Mayrhofer Experimental [Page 5]
273 RFC 8467 Padding Policies for EDNS(0) October 2018
274
275
276 According to the limited empirical data available, Random-Length
277 Padding exposes slightly more entropy to an attacker than Block-
278 Length Padding. Because of that, and the risk outlined above,
279 Random-Length Padding is NOT RECOMMENDED.
280
281 4.2.3. Random-Block-Length Padding
282
283 This policy combines Block-Length Padding with a random component.
284 Specifically, a sender randomly chooses between a few block length
285 values and then applies Block-Length Padding based on the chosen
286 block length. The random selection of block length might even be
287 reasonably based on a "weak" source of randomness, such as the
288 transaction ID of the message.
289
290 Options: Number of and the values for the set of block lengths;
291 source of randomness
292
293 Advantages: Compared to Block-Length Padding, this creates more
294 variety in the resulting message sizes for a certain individual
295 original message length.
296
297 Disadvantage: Requires more implementation effort compared to simple
298 Block-Length Padding.
299
300 Random-Block-Length Padding requires further empirical study, as do
301 other combinations of padding strategies.
302
303 5. IANA Considerations
304
305 This document has no IANA actions.
306
The IETF is responsible for the creation and maintenance of the DNS RFCs. The ICANN DNS RFC annotation project provides a forum for collecting community annotations on these RFCs as an aid to understanding for implementers and any interested parties. The annotations displayed here are not the result of the IETF consensus process.
This RFC is included in the DNS RFCs annotation project whose home page is here.
307 6. Security Considerations
308
309 The choice of the right padding policy (and the right parameters for
310 the chosen policy) has a significant impact on the resilience of
311 encrypted DNS against size-based correlation attacks. Therefore, any
312 implementor of the "Padding" option must carefully consider which
313 policies to implement, the default policy chosen, which parameters to
314 make configurable, and the default parameter values.
315
316 No matter how carefully a client selects their padding policy, this
317 effort can be jeopardized if the server chooses to apply an
318 ineffective padding policy to the corresponding response packets.
319 Therefore, a client applying the "Padding" option may want to choose
320 a DNS server that applies a padding policy on responses that is at
321 least equally effective.
322
323
324
325
326
327 Mayrhofer Experimental [Page 6]
328 RFC 8467 Padding Policies for EDNS(0) October 2018
329
330
331 Note that even with encryption and padding, it might be trivial to
332 identify that the observed traffic is DNS. Also, padding does not
333 prevent information leaks via other side channels (particularly
334 timing information and number of query/response pairs).
335 Countermeasures against such side channels could include injecting
336 artificial "cover traffic" into the stream of DNS messages or
337 delaying DNS responses by a certain amount of jitter. Such
338 strategies are out of the scope of this document. Additionally,
339 there is not enough theoretic analysis or experimental data available
340 to recommend any such countermeasures.
341
342 7. References
343
344 7.1. Normative References
345
346 [NDSS-PADDING]
347 Gillmor, D., "Empirical DNS Padding Policy", March 2017,
348 <https://dns.cmrg.net/
349 ndss2017-dprive-empirical-DNS-traffic-size.pdf>.
350
351 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
352 Requirement Levels", BCP 14, RFC 2119,
353 DOI 10.17487/RFC2119, March 1997,
354 <https://www.rfc-editor.org/info/rfc2119>.
355
356 [RFC7830] Mayrhofer, A., "The EDNS(0) Padding Option", RFC 7830,
357 DOI 10.17487/RFC7830, May 2016,
358 <https://www.rfc-editor.org/info/rfc7830>.
359
360 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
361 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
362 May 2017, <https://www.rfc-editor.org/info/rfc8174>.
363
364 7.2. Informative References
365
366 [RFC7858] Hu, Z., Zhu, L., Heidemann, J., Mankin, A., Wessels, D.,
367 and P. Hoffman, "Specification for DNS over Transport
368 Layer Security (TLS)", RFC 7858, DOI 10.17487/RFC7858, May
369 2016, <https://www.rfc-editor.org/info/rfc7858>.
370
371 [RFC8094] Reddy, T., Wing, D., and P. Patil, "DNS over Datagram
372 Transport Layer Security (DTLS)", RFC 8094,
373 DOI 10.17487/RFC8094, February 2017,
374 <https://www.rfc-editor.org/info/rfc8094>.
375
376
377
378
379
380
381
382 Mayrhofer Experimental [Page 7]
383 RFC 8467 Padding Policies for EDNS(0) October 2018
384
385
386 Appendix A. Padding Policies That Are Not Sensible
387
388 A.1. No Padding
389
390 In the No Padding policy, the "Padding" option is not used, and the
391 size of the final (actually, "non-padded") message obviously exactly
392 matches the size of the unpadded message. Even though this
393 "non-policy" seems redundant in this list, its properties must be
394 considered for cases in which just one of the parties (client or
395 server) applies padding.
396
397 Also, this policy is required when the remaining message size of the
398 unpadded message does not allow for the "Padding" option to be
399 included -- i.e., there are fewer than 4 octets left.
400
401 Advantages: This policy requires no additional resources on the
402 client, server, and network side.
403
404 Disadvantages: The original size of the message remains unchanged;
405 hence, this approach provides no additional confidentiality.
406
407 The No Padding policy MUST NOT be used unless message size disallows
408 the use of the "Padding" option.
409
410 A.2. Fixed-Length Padding
411
412 In Fixed-Length Padding, a sender chooses to pad each message with a
413 padding of constant length.
414
415 Options: Actual length of padding
416
417 Advantages: Since the padding is constant in length, this policy is
418 very easy to implement and at least ensures that the message length
419 diverges from the length of the original packet (even if only by a
420 fixed value).
421
422 Disadvantage: Obviously, the amount of padding is easily discoverable
423 from a single unencrypted message or by observing message patterns.
424 When a public DNS server applies this policy, the length of the
425 padding hence must be assumed to be public knowledge. Therefore,
426 this policy is (almost) as useless as the No Padding policy described
427 above.
428
429 The Fixed-Length Padding policy MUST NOT be used except for test
430 applications.
431
432
433
434
435
436
437 Mayrhofer Experimental [Page 8]
438 RFC 8467 Padding Policies for EDNS(0) October 2018
439
440
441 Acknowledgements
442
443 Daniel K. Gillmor performed empirical research out of which the
444 "Recommended Strategy" was copied. Stephane Bortzmeyer and Hugo
445 Connery provided text. Shane Kerr, Sara Dickinson, Paul Hoffman,
446 Magnus Westerlund, Charlie Kaufman, Joe Clarke, and Meral Shirazipour
447 performed reviews or provided substantial comments.
448
449 Author's Address
450
451 Alexander Mayrhofer
452 nic.at GmbH
453 Karlsplatz 1/2/9
454 Vienna 1010
455 Austria
456
457 Email: alex.mayrhofer.ietf@gmail.com
458 URI: http://edns0-padding.org/
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492 Mayrhofer Experimental [Page 9]
493
Note that even with encryption and padding, it might be trivial to identify that the observed traffic is DNS.
Note that even with encryption and padding, it might be easy to identify that the observed traffic is DNS.
easy to understand what that means. --VERIFIER NOTES-- While the suggested text*might* be easier to read (and as a non-English speaker easy/trivial are easy to read even if they do not convey the same semantic), it is not worth a verified errata IMHO.