Internet Engineering Task Force B. Bradley Internet-Draft Apple Inc. Intended status: Standards Track August 2, 2020 Expires: February 3, 2021 Private Discovery draft-bradley-dnssd-private-discovery-04 Abstract This document specifies a mechanism for advertising and discovering in a private manner. 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 February 3, 2021. Copyright Notice Copyright (c) 2020 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 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. Bradley Expires February 3, 2021 [Page 1] Internet-Draft August 2020 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Conventions and Terminology . . . . . . . . . . . . . . . . . 2 3. Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1. Probe . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2. Response . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3. Announcement . . . . . . . . . . . . . . . . . . . . . . 6 3.4. Query . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.5. Answer . . . . . . . . . . . . . . . . . . . . . . . . . 8 4. Timestamps . . . . . . . . . . . . . . . . . . . . . . . . . 9 5. Implicit Nonces . . . . . . . . . . . . . . . . . . . . . . . 9 6. Re-keying and Limits . . . . . . . . . . . . . . . . . . . . 9 7. Message Types . . . . . . . . . . . . . . . . . . . . . . . . 10 8. Message Fields . . . . . . . . . . . . . . . . . . . . . . . 10 9. Security Considerations . . . . . . . . . . . . . . . . . . . 11 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 11. To Do . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12. Normative References . . . . . . . . . . . . . . . . . . . . 12 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13 1. Introduction Advertising and discovering devices and services on the network can leak a lot of information about a device or person, such as their name, the types of services they provide or use, and persistent identifiers. This information can be used to identify and track a person's location and daily routine (e.g. buys coffee every morning at 8 AM at Starbucks on Main Street). It can also reveal intimate details about a person's behavior and medical conditions, such as discovery requests for a glucose monitor, possibly indicating diabetes. This document specifies a system for advertising and discovery of devices and services while preserving privacy and confidentiality. This document does not specify how keys are provisioned. Provisioning keys is complex enough to justify its own document(s). This document assumes each peer has a long-term asymmetric key pair (LTPK and LTSK) and communicating peers have each other's long-term asymmetric public key (LTPK). 2. Conventions and Terminology 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]. Bradley Expires February 3, 2021 [Page 2] Internet-Draft August 2020 "Friend" A peer you have a cryptographic relationship with. Specifically, that you have the peer's LTPK. "Probe" Unsolicited multicast message sent to find friends on the network. "Announcement" Unsolicited multicast message sent to inform friends on the network that you have become available or have updated data. "Response" Solicited unicast message sent in response to a probe or announcement. "Query" Unsolicited unicast message sent to get specific info from a peer. "Answer" Solicited unicast message sent in response to a query to provide info or indicate the lack of info. "Multicast" This term is used in the generic sense of sending a message that targets 0 or more peers. It's not strictly required to be a UDP packet with a multicast destination address. It could be sent via TCP or some other transport to a router that repeats the message via unicast to each peer. "Unicast" This term is used in the generic sense of sending a message that targets a single peer. It's not strictly required to be a UDP packet with a unicast destination address. Multi-byte values are encoded from the most significant byte to the least significant byte (big endian). When multiple items are concatenated together, the symbol "||" (without quotes) between each item is used to indicate this. For example, a combined item of A followed by B followed by C would be written as "A || B || C". 3. Protocol There are two techniques used to preserve privacy and provide confidentiality in this document. The first is announcing, probing, and responding with only enough info to allow a peer with your public key to detect that it's you while hiding your identity from peers Bradley Expires February 3, 2021 [Page 3] Internet-Draft August 2020 without your public key. This technique uses a fresh random signed with your private key using a signature algorithm that doesn't reveal your public key. The second technique is to query and answer in a way that only a specific friend can read the data. This uses ephemeral key exchange and symmetric encryption and authentication. The general flow of the protocol is a device sends multicast probes to discover friend devices on the network. If friend devices are found, it directly communicates with them via unicast queries and answers. Announcements are sent to report availability and when services are added or removed. Messages use a common header with a flags/type field. This indicates the format of the data after the header. Any data beyond the type- specific message body MUST be ignored. Future versions of this document may define additional data and this MUST NOT cause older message parsers to break. Updated formats that break compatibility with older parsers MUST use a new message type. This protocol avoids explicit version numbers. It's versioned using message types and flags. Flags are used for protocol extensions where a flag can indicate the presence of an optional field. A new message type is used when the old message type structure cannot reasonably be extended without breaking older parsers. For example, if the probe message in this document changed to use a different key type then older parsers would misinterpret the content of the message. A new type would be ignored by older, compliant parsers. Message format: 0 1 2 3 4 5 6 7 8 bits +-----+---------+~~~~~~~~~~~~~~~~~~~~ |Flags| Type | Type-specific data +-----+---------+~~~~~~~~~~~~~~~~~~~~ o Flags: Flags for future use. Set to 0 when sending. Ignore when receiving. o Type: Message type. See Section 7. 3.1. Probe A probe is sent via multicast to discover friends on the network. A probe contains a fresh, ephemeral public key (EPK1), a timestamp (TS1), and a signature (SIG1). This provides enough for a friend to identify the source, but doesn't allow non-friends to identify it. Probe Fields: Bradley Expires February 3, 2021 [Page 4] Internet-Draft August 2020 o EPK1 (Ephemeral Public Key 1). o TS1 (Timestamp 1). See Timestamps Section 4. o SIG1 (Signature of "Probe" || EPK1 || TS1 || "End"). When a peer receives a probe, it verifies TS1. If TS1 is outside the time window then it SHOULD be ignored. It then attempts to verify SIG1 with the public key of each of its friends. If verification fails for all public keys then it ignores the probe. If a verification succeeds for a public key then it knows which friend sent the probe. It SHOULD send a response to the friend. Message format: 0 1 2 3 4 5 6 7 8 bits +0 +-----+---------+ |Flg=0| Type=1 | 1 byte +1 +-----+---------+---------------+ | EPK1 (Ephemeral Public Key 1) | 32 bytes | | +33 +-------------------------------+ | TS1 (Timestamp 1) | 4 bytes +37 +-------------------------------+ | SIG1 (Signature 1) | 64 bytes | | | | +-------------------------------+ +101 Total bytes 3.2. Response A response contains a fresh, ephemeral public key (EPK2) and a symmetrically encrypted signature (ESIG2). The encryption key is derived by first generating a fresh ephemeral public key (EPK2) and its corresponding secret key (ESK2) and performing Diffie-Hellman (DH) using EPK1 and ESK2 to compute a shared secret. The shared secret is used to derive a symmetric session key (SSK2). A signature of the payload is generated (SIG2) using the responder's long-term secret key (LTSK2). The signature is encrypted with SSK2 (ESIG2). The nonce for ESIG2 is 1 and is not included in the response. The response is sent via unicast to the sender of the probe. When the friend that sent the probe receives the response, it performs DH, symmetrically verifies ESIG2 and, if successful, decrypts it to reveal SIG2. It then tries to verify SIG2 with the public keys of all of its friends. If a verification succeeds for a public key then it knows which friend sent the response. If any Bradley Expires February 3, 2021 [Page 5] Internet-Draft August 2020 steps fail, the response is ignored. If all steps succeed, it derives a session key (SSK1). Both session keys (SSK1 and SSK2) are remembered for subsequent communication with the friend. Response Fields: o EPK2 (Ephemeral Public Key 2). o ESIG2 (Encrypted Signature of "Response" || EPK2 || EPK1 || TS1 || "End"). Key Derivation values: o SSK1: HKDF-SHA-512 with Salt = "SSK1-Salt", Info = "SSK1-Info", Output size = 32 bytes. o SSK2: HKDF-SHA-512 with Salt = "SSK2-Salt", Info = "SSK2-Info", Output size = 32 bytes. Message format: 0 1 2 3 4 5 6 7 8 bits +0 +-----+---------+ |Flg=0| Type=2 | 1 byte +1 +-----+---------+---------------+ | EPK2 (Ephemeral Public Key 2) | 32 bytes | | +33 +-------------------------------+ | ESIG2 (Encrypted Signature 2) | 96 bytes | | | | +-------------------------------+ +129 Total bytes 3.3. Announcement An announcement indicates availability to friends on the network or if it has update(s). It is sent whenever a device joins a network (e.g. joins WiFi, plugged into Ethernet, etc.), its IP address changes, or when it has an update for one or more of its services. Announcements are sent via multicast. Announcement Fields: o EPK1 (Ephemeral Public Key 1). o TS1 (Timestamp 1). See Timestamps Section 4. Bradley Expires February 3, 2021 [Page 6] Internet-Draft August 2020 o SIG1 (Signature of "Announcement" || EPK1 || TS1 || "End"). When a peer receives an announcement, it verifies TS1. If TS1 is outside the time window then it SHOULD be ignored. It then attempts to verify SIG1 with the public key of each of its friends. If verification fails for all public keys then it ignores the probe. If a verification succeeds for a public key then it knows which friend sent the announcement. Message format: 0 1 2 3 4 5 6 7 8 bits +0 +-----+---------+ |Flg=0| Type=3 | 1 byte +1 +-----+---------+---------------+ | EPK1 (Ephemeral Public Key 1) | 32 bytes | | +33 +-------------------------------+ | TS1 (Timestamp 1) | 4 bytes +37 +-------------------------------+ | SIG1 (Signature 1) | 64 bytes | | | | +-------------------------------+ +101 Total bytes 3.4. Query A query is sent via unicast to request specific info from a friend. The query data (MSG1) is encrypted with the symmetric session key (SSK1 for the original prober or SSK2 for the original responder) for the target friend previously generated via the probe/response exchange. This encrypted field is EMSG1. The nonce for EMSG1 is 1 larger than the last nonce used with this symmetric key and is not included in the query. For example, if this is the first message sent to this friend after the probe/response then the nonce would be 2. The query is sent via unicast to the friend. When the friend receives a query, it symmetrically verifies EMSG1 against every active session's key and, if one is successful (which also identifies the friend), it decrypts the field. If verification fails, the query is ignored, If verification succeeds, the query is processed. Query Fields: o EMSG1 (Encrypted query data). Bradley Expires February 3, 2021 [Page 7] Internet-Draft August 2020 Message format: 0 1 2 3 4 5 6 7 8 bits +0 +-----+---------+ |Flg=0| Type=4 | 1 byte +1 +-----+---------+--------------+ | EMSG1 (Encrypted query data) | n + 16 bytes | | +------------------------------+ +17 + n Total bytes 3.5. Answer An answer is sent via unicast in response to a query from a friend. The answer data (MSG2) is encrypted with the symmetric session key of the destination friend (SSK1 it was the original prober or SSK2 if it was the original responder from the previous probe/response exchange). This encrypted field is EMSG2. The nonce for EMSG2 is 1 larger than the last nonce used with this symmetric key and is not included in the answer. For example, if this is the first message sent to this friend after the probe/response then the nonce would be 2. The answer is sent via unicast to the friend. When the friend receives an answer, it symmetrically verifies EMSG2 against every active session's key and, if one is successful (which also identifies the friend), it decrypts the field. If verification fails, the answer is ignored, If verification succeeds, the answer is processed. Answer Fields: o EMSG2 (Encrypted answer data). Message format: 0 1 2 3 4 5 6 7 8 bits +0 +-----+---------+ |Flg=0| Type=5 | 1 byte +1 +-----+---------+--------------+ | EMSG2 (Encrypted query data) | n + 16 bytes | | +------------------------------+ +17 + n Total bytes Bradley Expires February 3, 2021 [Page 8] Internet-Draft August 2020 4. Timestamps A timestamp in this document is the number of seconds since 1970-01-01 00:00:00 UTC (i.e. Unix Epoch Time). Timestamps sent in messages SHOULD be randomized by +/- 30 seconds to reduce the fingerprinting ability of observers. A timestamp of 0 means the sender doesn't know the current time (e.g. lacks a battery-backed RTC and access to an NTP server). Receivers MAY use a timestamp of 0 to decide whether to enforce time window restrictions. This can allow discovery in situations where one or more devices don't know the current time (e.g. location without Internet access). A timestamp is considered valid if it's within N seconds of the current time of the receiver. The RECOMMENDED value of N is 900 seconds (15 minutes) to allow peers to remain discoverable even after a large amount of clock drift. 5. Implicit Nonces The nonces in this document are integers that increment by 1 for each encryption. Nonces are never included in any message. Including nonces in messages would enable senders to be easily tracked by their predictable nonce sequence. This may seem futile if other layers of the system also leak trackable identifiers, such as IP addresses, but this document tries to avoid introducing any new privacy leaks in anticipation of leaks by other layers eventually being fixed. Random nonces could avoid tracking, but make replay protection difficult by requiring the receiver to remember previously received messages to detect a replay. One issue with implicit nonces and replay protection in general is handling lost messages. Message loss and reordering is expected and shouldn't cause complete failure. Accepting nonces within N of the expected nonce enables recovery from some loss and reordering. When a message is received, the expected nonce is checked first and then nonce + 1, nonce - 1, up to nonce +/- N. The RECOMMENDED value of N is 8 as a balance between privacy, robustness, and performance. 6. Re-keying and Limits Re-keying is a hedge against key compromise. The underlying algorithms have limits that far exceed reasonable usage (e.g. 96-bit nonces), but if a key was revealed then we want to reduce the damage by periodically re-keying. Probes are periodically re-sent with a new ephemeral public key in case the previous key pair was compromised. The RECOMMENDED maximum probe ephemeral public key lifetime is 20 hours. This is close to 1 Bradley Expires February 3, 2021 [Page 9] Internet-Draft August 2020 day since people often repeat actions on a daily basis, but with some leeway for natural variations. If a probe ephemeral public key is re-generated for other reasons, such as joining a WiFi network, the refresh timer is reset. Session keys are periodically re-key'd in case a symmetric key was compromised. The RECOMMENDED maximum session key lifetime is 20 hours or 1000 messages, whichever comes first. This uses the same close-to-a-day reasoning as probes, but adds a maximum number of messages to reduce the potential for exposure when many messages are being exchanged. Responses SHOULD be throttled if it appears that a peer is making an excessive number of requests since this may indicate the peer is probing for weaknesses (e.g. timing attacks, ChopChop-style attacks). 7. Message Types +--------------+-------+--------------------------------------------+ | Name | Type | Description | +--------------+-------+--------------------------------------------+ | Invalid | 0 | Invalid message type. Avoids | | | | misinterpreting zeroed memory. | | Probe | 1 | See Section 3.1. | | Response | 2 | See Section 3.2. | | Announcement | 3 | See Section 3.3. | | Query | 4 | See Section 3.4. | | Answer | 5 | See Section 3.5. | | Reserved | 6-255 | Reserved. Don't send. Ignore if received. | +--------------+-------+--------------------------------------------+ 8. Message Fields Bradley Expires February 3, 2021 [Page 10] Internet-Draft August 2020 +-------------+-----------------------------------------------------+ | Name | Description | +-------------+-----------------------------------------------------+ | EPK1/EPK2 | Ephemeral Public Key. 32-byte Curve25519 public | | | key. | | TS1 | Timestamp. 4-byte timestamp. See Timestamps | | | Section 4. | | SIG1/SIG2 | Signature. 64-byte Ed25519 signature. | | ESIG1/ESIG2 | Encrypted signature. Ed25519 signature encrypted | | | with ChaCha20-Poly1305. Formatted as the 64-byte | | | encrypted portion followed by a 16-byte MAC (96 | | | bytes total). | | EMSG1/EMSG2 | Encrypted message. Message encrypted with | | | ChaCha20-Poly1305. Formatted as the N-byte | | | encrypted portion followed by a 16-byte MAC (N + 16 | | | bytes total). | +-------------+-----------------------------------------------------+ 9. Security Considerations o Privacy considerations are specified in draft-cheshire-dnssd- privacy-considerations. o Ephemeral key exchange uses elliptic curve Diffie-Hellman (ECDH) with Curve25519 as specified in [RFC7748]. o Signing and verification uses Ed25519 as specified in [RFC8032]. o Symmetric encryption uses ChaCha20-Poly1305 as specified in [RFC7539]. o Key derivation uses HKDF as specified in [RFC5869] with SHA-512 as the hash function. o Randoms and randomization MUST use cryptographic random numbers. Information leaks may still be possible in some situations. For example, an attacker could capture probes from a peer they've identified and replay them elsewhere within the allowed timestamp window. This could be used to determine if their friend is present on that network. The network infrastructure may leak identifiers in the form of persistent IP addresses and MAC addresses. Mitigating this requires changes at lower levels of the network stack, such as periodically changing IP addresses and MAC addresses. Bradley Expires February 3, 2021 [Page 11] Internet-Draft August 2020 10. IANA Considerations o A multicast UDP port number would need to be allocated by IANA. o Message types defined by this document are intended to be managed by IANA. 11. To Do The following are some of the things that still need to be specified and decided: o Figure out how sleep proxies might work with this protocol. o Define probe and announcement random delays to reduce collisions. o Describe when to use the same EPK2 in a response to reduce churn on probe/response collisions. o Consider randomly answering probes for non-friends to mask real friends. o Design public service protocol to allow pairing. o Recommend random delays before sending responses to mask friend list sizes. 12. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand Key Derivation Function (HKDF)", RFC 5869, DOI 10.17487/RFC5869, May 2010, . [RFC7539] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF Protocols", RFC 7539, DOI 10.17487/RFC7539, May 2015, . [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . Bradley Expires February 3, 2021 [Page 12] Internet-Draft August 2020 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital Signature Algorithm (EdDSA)", RFC 8032, DOI 10.17487/RFC8032, January 2017, . Author's Address Bob Bradley Apple Inc. One Apple Park Way Cupertino CA 95014 USA Email: bradley@apple.com Bradley Expires February 3, 2021 [Page 13]