Internet DRAFT - draft-kaiser-dnssd-bloomfilter-hints
draft-kaiser-dnssd-bloomfilter-hints
Network Working Group D. Kaiser
Internet-Draft University of Luxembourg
Intended status: Standards Track November 16, 2018
Expires: May 20, 2019
Efficient Hinting for Privacy Preserving DNS-SD using Bloomfilters
draft-kaiser-dnssd-bloomfilter-hints-00
Abstract
While DNS-SD over mDNS significantly improves the convenience of
network configuration, parts of the published information may
seriously breach the users' privacy. Currently discussed privacy
extensions either are not efficient in terms of multicast messages
sent, reduce privacy and complicate key revocation by introducing an
1:m pairing system, or use trial encryptions which are inefficient in
terms of necessary computational power.
The method proposed in this document leverages Bloomfilters to
significantly reduce the number of multicast (public) messages for a
DNS-SD privacy extension based on an 1:1 pairing mechanism. This
allows keeping the advantages of both an 1:1 pairing system and a
hinting system that does not require trial encryptions, while
mitigating the main disadvantage: multicast messages sent.
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 May 20, 2019.
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
Kaiser Expires May 20, 2019 [Page 1]
Internet-Draft DNS-SD Bloomfilter Hints November 2018
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 Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 2
2. Bloomfilter-based Discovery Protocol . . . . . . . . . . . . 3
2.1. Basic Idea . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3. Direct Resolving . . . . . . . . . . . . . . . . . . . . 5
3. Bloomfilter Hints . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Performance Analysis . . . . . . . . . . . . . . . . . . 5
3.2. Construction of Bloomfilter Hints . . . . . . . . . . . . 5
4. Security Considerations . . . . . . . . . . . . . . . . . . . 6
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6
6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 6
7. Informative References . . . . . . . . . . . . . . . . . . . 6
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 7
1. Introduction
DNS-SD [RFC6763] over mDNS [RFC6762] enables zero-configuration
service discovery in local networks. While it significantly improves
the convenience of network configuration, parts of the published
information may seriously breach the users' privacy. These privacy
issues and potential solutions are discussed in [KW14a], [KW14b], and
[K17].
[[TODO]]
This document proposes leveraging Bloomfilters to significantly
reduce the number of multicast (public) messages for a DNS-SD privacy
extension like [I-D.ietf-dnssd-privacy], which is based on an 1:1
pairing mechanism (e.g. [I-D.ietf-dnssd-pairing]).
1.1. Requirements
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].
Kaiser Expires May 20, 2019 [Page 2]
Internet-Draft DNS-SD Bloomfilter Hints November 2018
2. Bloomfilter-based Discovery Protocol
2.1. Basic Idea
Instead of transmitting a lot of discovery messages containing
HASH(<nonce>|<pairing key>), sending a single discovery message
containing a Bloomfilter over the respective hashes will
significantly reduce the number of necessary discovery messages.
False positives are not a problem. They will only cause an
additional pair of unicast messages.
2.2. Overview
This section provides an overview over Bloomfilter-based hinting,
illustrated by various scenarios where Alice searches for service
instances of type _type and Bob offers such an instance. This type
could be a _psds service instance for a two-stage discovery system,
or any other type for a one-stage discovery system.
In the following, [bf_1],...,[bf_n] are Bloomfilters whose
construction is described in Section 3.2. As we can store at least
25 hints in one Bloomfilter with a very low false positive rate (see
Section 3.1), n is expected to be very low.
If a pairing exists:
Alice Bob
_type PTR ?
------------------------>
_type PTR [bf_1]._type
...
_type PTR [bf_n]._type
<------------------------
[bf_1]._type SRV,TXT ?
------------------------>
ENCRYPT_k(SRV,TXT, A (of host as glue))
<------------------------
connect to service
------------------------>
Only the first two messages are multicast (public).
Kaiser Expires May 20, 2019 [Page 3]
Internet-Draft DNS-SD Bloomfilter Hints November 2018
The encrypted message SHOULD be padded in such a way that each answer
message has the same length, so that answers from the server are
indistinguishable from randomly selected bits for an unpaired device.
For checking a hint, Alice pre-calculates a list of
HASH(derive(secret)||nonce) for all her pairings per time interval,
and checks if any of these are in the Bloomfilter. This is even more
efficient than checking whether n received hashes are in a pre-
calculated hash table as described in [I-D.ietf-dnssd-privacy].
If no pairing exists, and the hint is not false positive:
Alice Bob
_type PTR ?
------------------------>
_type PTR [bf_1]._type
...
_type PTR [bf_n]._type
<------------------------
no match
In this case, a lot of messages are saved, as a severely compressed
version (1:25) of the hints was sufficient for Alice to realize that
this service instance was not meant for her.
If no pairing exists, and the hint is a false positive:
Alice Bob
_type PTR ?
------------------------>
_type PTR [bf_1]._type
...
_type PTR [bf_n]._type
<------------------------
[bf_1]._type SRV,TXT ?
------------------------>
ENCRYPT_k(SRV,TXT, A (of host as glue))
<------------------------
decryption failed
In the case of a false positive, only a pair of additional multicast
messages and the corresponding cryptographic operations are needed.
With a false positive rate of 1:16000 (see Section 3.1), this effect
is negligible.
Kaiser Expires May 20, 2019 [Page 4]
Internet-Draft DNS-SD Bloomfilter Hints November 2018
This case also applies to an attacker trying to deceive Bob.
2.3. Direct Resolving
[[TODO: Show a diagram of the message flow for direct resolving.]]
3. Bloomfilter Hints
3.1. Performance Analysis
As specified in [RFC6763], the maximum length of a service instance
name is 63 bytes. As DNS labels are allowed to contain binary data,
this allows a 504 bit wide Bloomfilter.
Using classical Bloomfilters [[we could discuss more efficient
alternatives]] setting the maximum hints per Bloomfilter to 25
results in a desirable false positive rate of 1 in 16000. This
means, using the proposed Bloomfilter-based hinting method, the
necessary multicast (public) discovery messages can be reduced by
factor 25 at the cost of one additional set of messages for every
16000 discovery messages. Further, the server needs additional
computational power for constructing the bloomfilter. However, given
the efficiently of Bloomfilter construction, this is negligible. The
difference in needed computational power on the client is negligible
as well.
[[TODO: elaborate]]
3.2. Construction of Bloomfilter Hints
The Bloomfilters, [bf_1],...,[bf_n], in the protocol description
above, are constructed as follows:
o Initialize bf_1 as a 504 bit wide Bloomfilter.
o For each paired client p, put an identifier of the form
HASH(derive(secret_p)||nonce) into a Bloomfilter bf_1. The nonce
is constructed as described in Section 3.4 of
[I-D.ietf-dnssd-privacy].
o If there are 25 elements in the Bloomfilter, start a new
Bloomfilter bf_{i+1} and repeat from step 2.
o Use the Bloomfilters bf_1,...,bf_n as service instance names of
service instances of type _type.
Kaiser Expires May 20, 2019 [Page 5]
Internet-Draft DNS-SD Bloomfilter Hints November 2018
4. Security Considerations
[[TODO]]
5. IANA Considerations
This draft does not require any IANA action.
6. Acknowledgments
7. Informative References
[I-D.ietf-dnssd-pairing]
Huitema, C. and D. Kaiser, "Device Pairing Using Short
Authentication Strings", draft-ietf-dnssd-pairing-05 (work
in progress), October 2018.
[I-D.ietf-dnssd-privacy]
Huitema, C. and D. Kaiser, "Privacy Extensions for DNS-
SD", draft-ietf-dnssd-privacy-05 (work in progress),
October 2018.
[K17] Kaiser, D., "Efficient Privacy-Preserving
Configurationless Service Discovery Supporting Multi-Link
Networks", 2017,
<http://nbn-resolving.de/urn:nbn:de:bsz:352-0-422757>.
[KW14a] Kaiser, D. and M. Waldvogel, "Adding Privacy to Multicast
DNS Service Discovery", DOI 10.1109/TrustCom.2014.107,
2014, <http://ieeexplore.ieee.org/xpl/
articleDetails.jsp?arnumber=7011331>.
[KW14b] Kaiser, D. and M. Waldvogel, "Efficient Privacy Preserving
Multicast DNS Service Discovery",
DOI 10.1109/HPCC.2014.141, 2014,
<http://ieeexplore.ieee.org/xpl/
articleDetails.jsp?arnumber=7056899>.
[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>.
[RFC6762] Cheshire, S. and M. Krochmal, "Multicast DNS", RFC 6762,
DOI 10.17487/RFC6762, February 2013,
<https://www.rfc-editor.org/info/rfc6762>.
Kaiser Expires May 20, 2019 [Page 6]
Internet-Draft DNS-SD Bloomfilter Hints November 2018
[RFC6763] Cheshire, S. and M. Krochmal, "DNS-Based Service
Discovery", RFC 6763, DOI 10.17487/RFC6763, February 2013,
<https://www.rfc-editor.org/info/rfc6763>.
Author's Address
Daniel Kaiser
University of Luxembourg
6, avenue de la Fonte
Esch-sur-Alzette 4364
Luxembourg
Email: daniel.kaiser@uni.lu
URI: https://secan-lab.uni.lu/
Kaiser Expires May 20, 2019 [Page 7]
