idnits 2.17.1 draft-kaiser-dnssd-bloomfilter-hints-00.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 16, 2018) is 1981 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. Kaiser 3 Internet-Draft University of Luxembourg 4 Intended status: Standards Track November 16, 2018 5 Expires: May 20, 2019 7 Efficient Hinting for Privacy Preserving DNS-SD using Bloomfilters 8 draft-kaiser-dnssd-bloomfilter-hints-00 10 Abstract 12 While DNS-SD over mDNS significantly improves the convenience of 13 network configuration, parts of the published information may 14 seriously breach the users' privacy. Currently discussed privacy 15 extensions either are not efficient in terms of multicast messages 16 sent, reduce privacy and complicate key revocation by introducing an 17 1:m pairing system, or use trial encryptions which are inefficient in 18 terms of necessary computational power. 20 The method proposed in this document leverages Bloomfilters to 21 significantly reduce the number of multicast (public) messages for a 22 DNS-SD privacy extension based on an 1:1 pairing mechanism. This 23 allows keeping the advantages of both an 1:1 pairing system and a 24 hinting system that does not require trial encryptions, while 25 mitigating the main disadvantage: multicast messages sent. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on May 20, 2019. 44 Copyright Notice 46 Copyright (c) 2018 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 62 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 2 63 2. Bloomfilter-based Discovery Protocol . . . . . . . . . . . . 3 64 2.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . 3 65 2.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 3 66 2.3. Direct Resolving . . . . . . . . . . . . . . . . . . . . 5 67 3. Bloomfilter Hints . . . . . . . . . . . . . . . . . . . . . . 5 68 3.1. Performance Analysis . . . . . . . . . . . . . . . . . . 5 69 3.2. Construction of Bloomfilter Hints . . . . . . . . . . . . 5 70 4. Security Considerations . . . . . . . . . . . . . . . . . . . 6 71 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 72 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 6 73 7. Informative References . . . . . . . . . . . . . . . . . . . 6 74 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 7 76 1. Introduction 78 DNS-SD [RFC6763] over mDNS [RFC6762] enables zero-configuration 79 service discovery in local networks. While it significantly improves 80 the convenience of network configuration, parts of the published 81 information may seriously breach the users' privacy. These privacy 82 issues and potential solutions are discussed in [KW14a], [KW14b], and 83 [K17]. 85 [[TODO]] 87 This document proposes leveraging Bloomfilters to significantly 88 reduce the number of multicast (public) messages for a DNS-SD privacy 89 extension like [I-D.ietf-dnssd-privacy], which is based on an 1:1 90 pairing mechanism (e.g. [I-D.ietf-dnssd-pairing]). 92 1.1. Requirements 94 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 95 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 96 document are to be interpreted as described in [RFC2119]. 98 2. Bloomfilter-based Discovery Protocol 100 2.1. Basic Idea 102 Instead of transmitting a lot of discovery messages containing 103 HASH(|), sending a single discovery message 104 containing a Bloomfilter over the respective hashes will 105 significantly reduce the number of necessary discovery messages. 107 False positives are not a problem. They will only cause an 108 additional pair of unicast messages. 110 2.2. Overview 112 This section provides an overview over Bloomfilter-based hinting, 113 illustrated by various scenarios where Alice searches for service 114 instances of type _type and Bob offers such an instance. This type 115 could be a _psds service instance for a two-stage discovery system, 116 or any other type for a one-stage discovery system. 118 In the following, [bf_1],...,[bf_n] are Bloomfilters whose 119 construction is described in Section 3.2. As we can store at least 120 25 hints in one Bloomfilter with a very low false positive rate (see 121 Section 3.1), n is expected to be very low. 123 If a pairing exists: 125 Alice Bob 127 _type PTR ? 128 ------------------------> 129 _type PTR [bf_1]._type 130 ... 131 _type PTR [bf_n]._type 132 <------------------------ 134 [bf_1]._type SRV,TXT ? 135 ------------------------> 136 ENCRYPT_k(SRV,TXT, A (of host as glue)) 137 <------------------------ 139 connect to service 140 ------------------------> 142 Only the first two messages are multicast (public). 144 The encrypted message SHOULD be padded in such a way that each answer 145 message has the same length, so that answers from the server are 146 indistinguishable from randomly selected bits for an unpaired device. 148 For checking a hint, Alice pre-calculates a list of 149 HASH(derive(secret)||nonce) for all her pairings per time interval, 150 and checks if any of these are in the Bloomfilter. This is even more 151 efficient than checking whether n received hashes are in a pre- 152 calculated hash table as described in [I-D.ietf-dnssd-privacy]. 154 If no pairing exists, and the hint is not false positive: 156 Alice Bob 158 _type PTR ? 159 ------------------------> 160 _type PTR [bf_1]._type 161 ... 162 _type PTR [bf_n]._type 163 <------------------------ 164 no match 166 In this case, a lot of messages are saved, as a severely compressed 167 version (1:25) of the hints was sufficient for Alice to realize that 168 this service instance was not meant for her. 170 If no pairing exists, and the hint is a false positive: 172 Alice Bob 174 _type PTR ? 175 ------------------------> 176 _type PTR [bf_1]._type 177 ... 178 _type PTR [bf_n]._type 179 <------------------------ 181 [bf_1]._type SRV,TXT ? 182 ------------------------> 183 ENCRYPT_k(SRV,TXT, A (of host as glue)) 184 <------------------------ 186 decryption failed 188 In the case of a false positive, only a pair of additional multicast 189 messages and the corresponding cryptographic operations are needed. 190 With a false positive rate of 1:16000 (see Section 3.1), this effect 191 is negligible. 193 This case also applies to an attacker trying to deceive Bob. 195 2.3. Direct Resolving 197 [[TODO: Show a diagram of the message flow for direct resolving.]] 199 3. Bloomfilter Hints 201 3.1. Performance Analysis 203 As specified in [RFC6763], the maximum length of a service instance 204 name is 63 bytes. As DNS labels are allowed to contain binary data, 205 this allows a 504 bit wide Bloomfilter. 207 Using classical Bloomfilters [[we could discuss more efficient 208 alternatives]] setting the maximum hints per Bloomfilter to 25 209 results in a desirable false positive rate of 1 in 16000. This 210 means, using the proposed Bloomfilter-based hinting method, the 211 necessary multicast (public) discovery messages can be reduced by 212 factor 25 at the cost of one additional set of messages for every 213 16000 discovery messages. Further, the server needs additional 214 computational power for constructing the bloomfilter. However, given 215 the efficiently of Bloomfilter construction, this is negligible. The 216 difference in needed computational power on the client is negligible 217 as well. 219 [[TODO: elaborate]] 221 3.2. Construction of Bloomfilter Hints 223 The Bloomfilters, [bf_1],...,[bf_n], in the protocol description 224 above, are constructed as follows: 226 o Initialize bf_1 as a 504 bit wide Bloomfilter. 228 o For each paired client p, put an identifier of the form 229 HASH(derive(secret_p)||nonce) into a Bloomfilter bf_1. The nonce 230 is constructed as described in Section 3.4 of 231 [I-D.ietf-dnssd-privacy]. 233 o If there are 25 elements in the Bloomfilter, start a new 234 Bloomfilter bf_{i+1} and repeat from step 2. 236 o Use the Bloomfilters bf_1,...,bf_n as service instance names of 237 service instances of type _type. 239 4. Security Considerations 241 [[TODO]] 243 5. IANA Considerations 245 This draft does not require any IANA action. 247 6. Acknowledgments 249 7. Informative References 251 [I-D.ietf-dnssd-pairing] 252 Huitema, C. and D. Kaiser, "Device Pairing Using Short 253 Authentication Strings", draft-ietf-dnssd-pairing-05 (work 254 in progress), October 2018. 256 [I-D.ietf-dnssd-privacy] 257 Huitema, C. and D. Kaiser, "Privacy Extensions for DNS- 258 SD", draft-ietf-dnssd-privacy-05 (work in progress), 259 October 2018. 261 [K17] Kaiser, D., "Efficient Privacy-Preserving 262 Configurationless Service Discovery Supporting Multi-Link 263 Networks", 2017, 264 . 266 [KW14a] Kaiser, D. and M. Waldvogel, "Adding Privacy to Multicast 267 DNS Service Discovery", DOI 10.1109/TrustCom.2014.107, 268 2014, . 271 [KW14b] Kaiser, D. and M. Waldvogel, "Efficient Privacy Preserving 272 Multicast DNS Service Discovery", 273 DOI 10.1109/HPCC.2014.141, 2014, 274 . 277 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 278 Requirement Levels", BCP 14, RFC 2119, 279 DOI 10.17487/RFC2119, March 1997, 280 . 282 [RFC6762] Cheshire, S. and M. Krochmal, "Multicast DNS", RFC 6762, 283 DOI 10.17487/RFC6762, February 2013, 284 . 286 [RFC6763] Cheshire, S. and M. Krochmal, "DNS-Based Service 287 Discovery", RFC 6763, DOI 10.17487/RFC6763, February 2013, 288 . 290 Author's Address 292 Daniel Kaiser 293 University of Luxembourg 294 6, avenue de la Fonte 295 Esch-sur-Alzette 4364 296 Luxembourg 298 Email: daniel.kaiser@uni.lu 299 URI: https://secan-lab.uni.lu/