idnits 2.17.00 (12 Aug 2021) /tmp/idnits43577/draft-wood-key-consistency-02.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: ---------------------------------------------------------------------------- == There are 2 instances of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (4 March 2022) is 71 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 6962 (Obsoleted by RFC 9162) == Outdated reference: draft-irtf-cfrg-argon2 has been published as RFC 9106 == Outdated reference: A later version (-04) exists of draft-ietf-privacypass-protocol-02 == Outdated reference: A later version (-03) exists of draft-ietf-privacypass-architecture-02 Summary: 2 errors (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Davidson 3 Internet-Draft Brave Software 4 Intended status: Informational M. Finkel 5 Expires: 5 September 2022 The Tor Project 6 M. Thomson 7 Mozilla 8 C. A. Wood 9 Cloudflare 10 4 March 2022 12 Key Consistency and Discovery 13 draft-wood-key-consistency-02 15 Abstract 17 This document describes the key consistency and correctness 18 requirements of protocols such as Privacy Pass, Oblivious DoH, and 19 Oblivious HTTP for user privacy. It discusses several mechanisms and 20 proposals for enabling user privacy in varying threat models. In 21 concludes with discussion of open problems in this area. 23 Discussion Venues 25 This note is to be removed before publishing as an RFC. 27 Discussion of this document takes place on the mailing list (), which 28 is archived at . 30 Source for this draft and an issue tracker can be found at 31 https://github.com/chris-wood/key-consitency. 33 Status of This Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at https://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on 5 September 2022. 50 Copyright Notice 52 Copyright (c) 2022 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 57 license-info) in effect on the date of publication of this document. 58 Please review these documents carefully, as they describe your rights 59 and restrictions with respect to this document. Code Components 60 extracted from this document must include Revised BSD License text as 61 described in Section 4.e of the Trust Legal Provisions and are 62 provided without warranty as described in the Revised BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 67 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 68 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 69 3. Core Requirements . . . . . . . . . . . . . . . . . . . . . . 3 70 4. Consistency and Correctness at Key Acquisition . . . . . . . 4 71 4.1. Direct Discovery . . . . . . . . . . . . . . . . . . . . 4 72 4.2. Single Proxy Discovery . . . . . . . . . . . . . . . . . 5 73 4.3. Multi-Proxy Discovery . . . . . . . . . . . . . . . . . . 6 74 4.4. Database Discovery . . . . . . . . . . . . . . . . . . . 7 75 5. Minimum Validity Periods . . . . . . . . . . . . . . . . . . 9 76 6. Separate Consistency Verification . . . . . . . . . . . . . . 9 77 6.1. Independent Verification . . . . . . . . . . . . . . . . 9 78 6.2. Key-Based Encryption . . . . . . . . . . . . . . . . . . 10 79 7. Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 10 80 8. Security Considerations . . . . . . . . . . . . . . . . . . . 10 81 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 82 9.1. Normative References . . . . . . . . . . . . . . . . . . 10 83 9.2. Informative References . . . . . . . . . . . . . . . . . 11 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 86 1. Introduction 88 Several proposed privacy-enhancing protocols such as Privacy Pass 89 [PRIVACY-PASS], Oblivious DoH [ODOH], and Oblivious HTTP [OHTTP] 90 require clients to obtain and use a public key for execution. For 91 example, Privacy Pass public keys are used by clients for validating 92 privately issued tokens for anonymous session resumption. Oblivious 93 DoH and HTTP both use public keys to encrypt messages to a particular 94 server. 96 User privacy in these systems depends on users receiving a key that 97 many, if not all, other users receive. If a user were to receive a 98 public key that was specific to them, or restricted to a small set of 99 users, then use of that public key could be used to learn targeted 100 information about the user. Users also need to receive the correct 101 public key. 103 In this document, we elaborate on these core requirements, and survey 104 various system designs that might be used to satisfy them. The 105 purpose of this document is to highlight challenges in building and 106 deploying solutions to this problem. 108 1.1. Requirements 110 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 111 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 112 "OPTIONAL" in this document are to be interpreted as described in 113 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 114 capitals, as shown here. 116 2. Terminology 118 This document defines the following terms: 120 Key Consistency and Correctness System (KCCS): A mechanism for 121 providing clients with a consistent view of cryptographic key 122 material within a period of time. 124 Reliant System: A system that embeds one or more key consistency and 125 correctness systems. 127 The KCCS's consistency model is dependent on the implementation and 128 reliant system's threat model. 130 3. Core Requirements 132 Privacy-focused protocols which rely on widely shared public keys 133 typically require keys be consistent and correct. Informally, key 134 consistency is the requirement that all users who communicate with an 135 entity share the same view of the key associated with that entity; 136 key correctness is that the key's secret information is controlled by 137 the intended entity and is not known to be available to an external 138 attacker. 140 Some protocols depend on large sets of users with consistent keys for 141 privacy reasons. Specifically, all users with a consistent key 142 represent an anonymity set wherein each user of the key in that set 143 is indistinguishable from the rest. An attacker that can actively 144 cause inconsistent views of keys can therefore compromise user 145 privacy. 147 An attacker that can cause a user to use an incorrect key will likely 148 compromise the entire protocol, not just privacy. 150 Reliant systems must also consider agility when trying to satisfy 151 these requirements. A naive solution to ensuring consistent and 152 correct keys is to only use a single, fixed key pair for the entirety 153 of the system. Users can then embed this key into software or 154 elsewhere as needed, without any additional mechanics or controls to 155 ensure that other users have a different key. However, this solution 156 clearly is not viable in practice. If the corresponding key is 157 compromised, the system fails. Rotation must therefore be supported, 158 and in doing so, users need some mechanism to ensure that newly 159 rotated keys are consistent and correct. 161 Operationally, servers rotating keys may likely need to accommodate 162 distributed system state-synchronization issues without sacrificing 163 availability. Some systems and protocols may choose to prioritize 164 strong consistency over availability, but this document assumes that 165 availability is preferred to total consistency. 167 4. Consistency and Correctness at Key Acquisition 169 There are a variety of ways in which reliant systems may build key 170 consistency and correct systems (KCCS), ranging in operational 171 complexity to ease-of-implementation. In this section, we survey a 172 number of possible solutions. The viability of each varies depending 173 on the applicable threat model, external dependencies, and overall 174 reliant system's requirements. 176 We do not include the fixed public key model from Section 3, as this 177 is likely not a viable solution for systems and protocols in 178 practice. In all scenarios, the server corresponding to the desired 179 key is considered malicious. 181 4.1. Direct Discovery 183 In this model, users would directly query servers for their 184 corresponding public key, as shown below. 186 +----------+ +----------+ 187 | | | | 188 | Client +--------------> Server | 189 | | | | 190 +----------+ +----------+ 192 Figure 1: Direct Discovery Example 194 The properties of this solution depend on external mechanisms in 195 place to ensure consistency or correctness. Absent any such 196 mechanisms, servers can produce unique keys for users without 197 detection. External mechanisms to ensure consistency here might 198 include, though are not limited to: 200 * Presenting a signed assertion from a trusted entity that the key 201 is correct. 203 * Presenting proof that the key is present in some tamper-proof log, 204 similar to Certificate Transparency ([RFC6962]) logs. 206 * User communication or gossip ensuring that all users have a shared 207 view of the key. 209 The precise external mechanism used here depends largely on the 210 threat model. If there is a trusted external log for keys, this may 211 be a viable solution. 213 4.2. Single Proxy Discovery 215 In this model, there exists a proxy that fetches keys from servers on 216 behalf of multiple users, as shown below. 218 +----------+ 219 | | 220 | Client +----------+ 221 | | | 222 +----------+ | 223 | 224 +----------+ +\/--------+ +----------+ 225 | | | | | | 226 | Client +---------> Proxy +------> Server | 227 | | | | | | 228 +----------+ +^---------+ +----------+ 229 x | 230 x | 231 +----------+ | 232 | | | 233 | Client +----------+ 234 | | 235 +----------+ 237 Figure 2: Single Proxy Discovery Example 239 If this proxy is trusted, then all users which request a key from 240 this server are assured they have a consistent view of the server 241 key. However, if this proxy is not trusted, operational risks may 242 arise: 244 * The proxy can collude with the server to give per-user keys to 245 clients. 247 * The proxy can give all users a key owned by the proxy, and either 248 collude with the server to use this key or retroactively use this 249 key to compromise user privacy when users later make use of the 250 key. 252 Mitigating these risks may require tamper-proof logs as in 253 Section 4.1, or via user gossip protocols. 255 4.3. Multi-Proxy Discovery 257 In this model, users leverage multiple, non-colluding proxies to 258 fetch keys from servers, as shown below. 260 +----------+ 261 | | 262 +---------------> Proxy +-----------+ 263 | | | | 264 | +----------+ | 265 | | 266 +----------+ +----------+ +----\/----+ 267 | │ | | | | 268 | Client +---------> Proxy +------> Server | 269 | │ | | | | 270 +----------+ +----------+ +----^-----+ 271 | x | 272 | x | 273 | +----------+ | 274 | | | | 275 +--------------> Proxy +-----------+ 276 | | 277 +----------+ 279 Figure 3: Multi-Proxy Discovery Example 281 These proxies are ideally spread across multiple vantage points. 282 Examples of proxies include anonymous systems such as Tor. Tor 283 proxies are general purpose and operate at a lower layer, on 284 arbitrary communication flows, and therefore they are oblivious to 285 clients fetching keys. A large set of untrusted proxies that are 286 aware of key fetch requests (Section 4.2) may be used in a similar 287 way. Depending on how clients fetch such keys from servers, it may 288 become more difficult for servers to uniquely target individual users 289 with unique keys without detection. This is especially true as the 290 number of users of these anonymity networks increases. However, 291 beyond Tor, there does not exist a special-purpose anonymity network 292 for this purpose. 294 4.4. Database Discovery 296 In this model, servers publish keys in an external database and 297 clients fetch keys from the database, as shown below. 299 +----------+ 300 | | 301 | Client +-----------+ 302 | | | 303 +----------+ | 304 | 305 +----------+ +----------+ +----------+ 306 | | | | | | 307 | Client +---------> Database <------+ Server | 308 | | | | | | 309 +----------+ +----------+ +----------+ 310 x | 311 x | 312 +----------+ | 313 | | | 314 | Client +-----------+ 315 | | 316 +----------+ 318 Figure 4: Database Discovery Example 320 The database is expected to have a table that asserts mappings 321 between server names and keys. Examples of such databases are as 322 follows: 324 * An append-only, audited table similar to that of Certificate 325 Transparency [RFC6962]. The log is operated and audited in such a 326 way that the contents of the log are consistent for all users. 327 Any reliant system which depends on this type of KCCS requires the 328 log be audited or users have some other mechanism for checking 329 their view of the log state (gossiping). However, this type of 330 system does not ensure proactive security against malicious 331 servers unless log participants actively check log proofs. This 332 requirement may impede deployment in practice. Experience with 333 Certificate Transparency shows that most implementations have 334 chosen not to check SignedCertificateTimestamps before using (that 335 is, accepting as valid) a corresponding TLS certificate. 337 * A consensus-based table whose assertions are created by a 338 coalition of entities that periodically agree on the correct 339 binding of server names and key material. In this model the 340 agreement is achieved via a consensus protocol, but the specific 341 consensus protocol is dependent on the implementation. 343 For privacy, users should either download the entire database and 344 query it locally, or remotely query the database using privacy- 345 preserving queries (e.g., a private information retrieval (PIR) 346 protocol). In the case where the database is downloaded locally, it 347 should be considered stale and re-fetched periodically. The 348 frequency of such updates can likely be infrequent in practice, as 349 frequent key updates or rotations may affect privacy; see Section 5 350 for details. Downloading the entire database works best if there are 351 a small number of entries, as it does not otherwise impose bandwidth 352 costs on each client that may be impractical. 354 5. Minimum Validity Periods 356 In addition to ensuring that there is one key at any time, or a 357 limited number keys, any system needs to ensure that a server cannot 358 rotate its keys too often in order to divide clients into smaller 359 groups based on when keys are acquired. Such considerations are 360 already highlighted within the Privacy Pass ecosystem, more 361 discussion can be found at [PRIVACY-PASS-ARCH]. Setting a minimum 362 validity period limits the ability of a server to rotate keys, but 363 also limits the rate of key rotation. 365 6. Separate Consistency Verification 367 The other schemes described here all attempt to directly limit the 368 number of keys that a client might accept. However, by changing how 369 keys are used, clients can impose costs on servers that might 370 discourage key diversity. 372 Protocols that have distinctly separate processes for acquiring and 373 using keys might benefit from moving consistency checks to the usage 374 part of the protocol. Correctness might be guaranteed through a 375 relatively simple process, such obtaining keys directly from a 376 server. A separate correctness check is then applied before keys are 377 used. 379 6.1. Independent Verification 381 Anonymous queries to verify key consistency can be used prior to use 382 of keys. A request for the current key (or limited set of keys) will 383 reveal if the key that was acquired is different than the original. 384 If the key that was originally obtained is not included, the client 385 can abort any use of the key. 387 It is important that any validation process not carry any information 388 that might tie it to the original key discovery process or that the 389 system providing verification be trusted. A proxy (see Section 4.2) 390 might be sufficient for providing anonymity, though more robust 391 anonymity protections (see Section 4.3) could provide stronger 392 guarantees. Querying a database (see Section 4.4) might provide 393 independent verification if that database can be trusted not to 394 provide answers that change based on client identity. 396 6.2. Key-Based Encryption 398 Key-based encryption has a client encrypt the information that it 399 sends to a server, such as a token or signed object generated with 400 the server keys. This encryption uses a key derived from the key 401 configuration, specifically not including any form of key identifier 402 along with the encrypted information. If key derivation for the 403 encryption uses a pre-image resistant function (like HKDF), the 404 server can only decrypt the information if it knows the key 405 configuration. As there is no information the server can use to 406 identify which key was used, it is forced to perform trial decryption 407 if it wants to use multiple keys. 409 These costs are only linear in terms of the number of active keys. 410 This doesn't prevent the use of multiple keys, it only makes their 411 use incrementally more expensive. Trial decryption costs can be 412 increased by choosing a time- or memory-hard function such as 413 [ARGON2] to generate keys. 415 Encrypting this way could provide better latency properties than a 416 separate check. 418 7. Future Work 420 The model in Section 4.3 seems to be the most lightweight and easy- 421 to-deploy mechanism for ensuring key consistency and correctness. 422 However, it remains unclear if there exists such an anonymity network 423 that can scale to the widespread adoption of and requirements of 424 protocols like Privacy Pass, Oblivious DoH, or Oblivious HTTP. 425 Existing infrastructure based on technologies like Certificate 426 Transparency or Key Transparency may work, but there is currently no 427 general purpose system for transparency of opaque keys (or other 428 application data). 430 8. Security Considerations 432 This document discusses several models that systems might use to 433 implement public key discovery while ensuring key consistency and 434 correctness. It does not make any recommendations for such models as 435 the best model depends on differing operational requirements and 436 threat models. 438 9. References 440 9.1. Normative References 442 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 443 Requirement Levels", BCP 14, RFC 2119, 444 DOI 10.17487/RFC2119, March 1997, 445 . 447 [RFC6962] Laurie, B., Langley, A., and E. Kasper, "Certificate 448 Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013, 449 . 451 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 452 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 453 May 2017, . 455 9.2. Informative References 457 [ARGON2] Biryukov, A., Dinu, D., Khovratovich, D., and S. 458 Josefsson, "Argon2 Memory-Hard Function for Password 459 Hashing and Proof-of-Work Applications", Work in Progress, 460 Internet-Draft, draft-irtf-cfrg-argon2-13, 11 March 2021, 461 . 464 [ODOH] Kinnear, E., McManus, P., Pauly, T., Verma, T., and C. A. 465 Wood, "Oblivious DNS Over HTTPS", Work in Progress, 466 Internet-Draft, draft-pauly-dprive-oblivious-doh-11, 17 467 February 2022, . 470 [OHTTP] Thomson, M. and C. A. Wood, "Oblivious HTTP", Work in 471 Progress, Internet-Draft, draft-ietf-ohai-ohttp-01, 15 472 February 2022, . 475 [PRIVACY-PASS] 476 Celi, S., Davidson, A., Faz-Hernandez, A., Valdez, S., and 477 C. A. Wood, "Privacy Pass Issuance Protocol", Work in 478 Progress, Internet-Draft, draft-ietf-privacypass-protocol- 479 02, 31 January 2022, 480 . 483 [PRIVACY-PASS-ARCH] 484 Davidson, A., Iyengar, J., and C. A. Wood, "Privacy Pass 485 Architectural Framework", Work in Progress, Internet- 486 Draft, draft-ietf-privacypass-architecture-02, 31 January 487 2022, . 490 Authors' Addresses 492 Alex Davidson 493 Brave Software 494 Email: alex.davidson92@gmail.com 496 Matthew Finkel 497 The Tor Project 498 Email: sysrqb@torproject.org 500 Martin Thomson 501 Mozilla 502 Email: mt@lowentropy.net 504 Christopher A. Wood 505 Cloudflare 506 101 Townsend St 507 San Francisco, 508 United States of America 509 Email: caw@heapingbits.net