idnits 2.17.1 draft-laurie-pki-sunlight-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 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The document seems to lack a Security Considerations section. ** 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.) ** The abstract seems to contain references ([RFC5280], [RFC5878]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 253: '...e submission, the log MUST immediately...' RFC 2119 keyword, line 257: '... MUST present an SCT from one or mor...' RFC 2119 keyword, line 258: '...ficate. Clients MUST reject certifica...' RFC 2119 keyword, line 264: '...he log. The log MUST incorporate a ce...' RFC 2119 keyword, line 274: '... certificate MUST be accompanied by ...' (28 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (September 12, 2012) is 4244 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) -- Missing reference section? 'RFC5878' on line 556 looks like a reference -- Missing reference section? 'RFC5280' on line 559 looks like a reference -- Missing reference section? '1' on line 564 looks like a reference -- Missing reference section? 'RFC5246' on line 553 looks like a reference -- Missing reference section? '32' on line 459 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Laurie 3 Internet-Draft A. Langley 4 Expires: March 16, 2013 E. Kasper 5 September 12, 2012 7 Certificate Transparency 8 draft-laurie-pki-sunlight-00 10 Abstract 12 The aim of Certificate Transparency is to have every public end- 13 entity TLS certificate issued by a known Certificate Authority 14 recorded in one or more certificate logs. In order to detect mis- 15 issuance of certificates, all logs are publicly auditable. In 16 particular, domain owners will be able to monitor logs for 17 certificates issued on their own domain. 19 In order to protect clients from unlogged mis-issued certificates, 20 logs sign all recorded certificates, and clients can choose not to 21 trust certificates that are not accompanied by an appropriate log 22 signature. For privacy and performance reasons log signatures are 23 embedded in the TLS handshake via the TLS authorization extension 24 [RFC5878], or in the certificate itself via an X.509v3 certificate 25 extension [RFC5280]. 27 In order to ensure a globally consistent view of the log, logs also 28 provide a global signature over the entire log. Any inconsistency of 29 logs can be detected through cross-checks on the global signature. 31 Logs are only expected to certify that they have seen a certificate 32 and thus, we do not specify any revocation mechanism for log 33 signatures in this document. Logs will be append-only, and log 34 signatures will be valid indefinitely. 36 Status of this Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at http://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on March 16, 2013. 53 Copyright Notice 55 Copyright (c) 2012 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (http://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the Simplified BSD License. 68 1. Cryptographic components 70 1.1. Merkle Hash Trees 72 Logs use a binary Merkle hash tree for efficient auditing. The 73 hashing algorithm is SHA-256. The input to the Merkle tree hash is a 74 list of data entries; these entries will be hashed to form the leaves 75 of the Merkle hash tree. The output is a single 32-byte root hash. 76 Given an ordered list of n inputs, D[0:n] = {d(0), d(1), ..., 77 d(n-1)}, the Merkle Tree Hash (MTH) is thus defined as follows: 79 The hash of an empty list is the hash of an empty string: 81 MTH({}) = SHA-256(). 83 The hash of a list with one entry is: 85 MTH({d(0)}) = SHA-256(0 || d(0)). 87 For n > 1, let k be the largest power of two smaller than n. The 88 Merkle Tree Hash of an n-element list D[0:n] is then defined 89 recursively as 91 MTH(D[0:n]) = SHA-256(1 || MTH(D[0:k]) || MTH(D[k:n])), 93 where || is concatenation and D[k1:k2] denotes the length (k2 - k1) 94 list {d(k1), d(k1+1),..., d(k2-1)}. 96 Note that we do not require the length of the input list to be a 97 power of two. The resulting Merkle tree may thus not be balanced, 98 however, its shape is uniquely determined by the number of leaves. 99 _This Merkle tree is essentially the same as the_ history tree [1] 100 _proposal except our current definition omits dummy leaves._ 102 1.1.1. Merkle audit paths 104 A Merkle audit path for a leaf in a Merkle hash tree is the list of 105 all additional nodes in the Merkle tree required to compute the 106 Merkle Tree Hash for that tree. If the root computed from the audit 107 path matches the true root, then the audit path is proof that the 108 leaf exists in the tree. 110 Given an ordered list of n inputs to the tree, D[0:n] = {d(0), ..., 111 d(n-1)}, the Merkle audit path PATH(m, D[0:n]) for the (m+1)th input 112 d(m), 0 <= m < n, is defined as follows: 114 The path for the single leaf in a tree with a one-element input list 115 D[0:1] = {d(0)} is empty: 117 PATH(0, {d(0)}) = {} 119 For n > 1, let k be the largest power of two smaller than n. The 120 path for the (m+1)th element d(m) in a list of n > m elements is 121 then defined recursively as 123 PATH(m, D[0:n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and 125 PATH(m, D[0:n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for k <= m < n, 127 where : is concatenation of lists and D[k1:k2] denotes the length (k2 128 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 130 1.1.2. Merkle consistency proofs 132 Merkle consistency proofs prove the append-only property of the tree. 133 A Merkle consistency proof for a Merkle Tree Hash MTH(D[0:n]) and a 134 previously advertised hash MTH(D[0:m]) of the first m leaves, m <= n, 135 is the list of nodes in the Merkle tree required to verify that the 136 first m inputs D[0:m] are equal in both trees. Thus, a consistency 137 proof must contain a set of intermediate nodes (i.e., commitments to 138 inputs) sufficient to verify MTH(D[0:n]), such that (a subset of) the 139 same nodes can be used to verify MTH(D[0:m]). We define an algorithm 140 that outputs the (unique) minimal consistency proof. 142 Given an ordered list of n inputs to the tree, D[0:n] = {d(0), ..., 143 d(n-1)}, the Merkle consistency proof PROOF(m, D[0:n]) for a previous 144 root hash MTH(D[0:m]), 0 < m < n, is defined as PROOF(m, D[0:n]) = 145 SUBPROOF(m, D[0:n], true): 147 The subproof for m = n is empty if m is the value for which PROOF was 148 originally requested (meaning that the subtree root hash MTH(D[0:m]) 149 is known): 151 SUBPROOF(m, D[0:m], true) = {} 153 The subproof for m = n is the root hash committing inputs D[0:m] 154 otherwise: 156 SUBPROOF(m, D[0:m], false) = {MTH(D[0:m])} 158 For m < n, let k be the largest power of two smaller than n. The 159 subproof is then defined recursively. 161 If m <= k, the right subtree entries D[k:n] only exist in the current 162 tree. We prove that the left subtree entries D[0:k] are consistent 163 and add a commitment to D[k:n]: 165 SUBPROOF(m, D[0:n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n]). 167 If m > k, the left subtree entries D[0:k] are identical in both 168 trees. We prove that the right subtree entries D[k:n] are consistent 169 and add a commitment to D[0:k]. 171 SUBPROOF(m, D[0:n], b) = SUBPROOF(m - k, D[k:n], false) : 172 MTH(D[0:k]). 174 Here : is concatenation of lists and D[k1:k2] denotes the length (k2 175 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 177 The number of nodes in the resulting proof is bounded above by 178 ceil(log2(n)) + 1. 180 1.1.3. Example 182 The binary Merkle tree with 7 leaves: 184 hash 185 / \ 186 / \ 187 / \ 188 / \ 189 / \ 190 k l 191 / \ / \ 192 / \ / \ 193 / \ / \ 194 g h i j 195 / \ / \ / \ | 196 a b c d e f d6 197 | | | | | | 198 d0 d1 d2 d3 d4 d5 200 The audit path for d0 is [b, h, l]. 202 The audit path for d3 is [c, g, l]. 204 The audit path for d4 is [f, j, k]. 206 The audit path for d6 is [i, k]. 208 The same tree, built incrementally in four steps: 210 hash0 hash1=k 211 / \ / \ 212 / \ / \ 213 / \ / \ 214 g c g h 215 / \ | / \ / \ 216 a b d2 a b c d 217 | | | | | | 218 d0 d1 d0 d1 d2 d3 220 hash2 hash 221 / \ / \ 222 / \ / \ 223 / \ / \ 224 / \ / \ 225 / \ / \ 226 k i k l 227 / \ / \ / \ / \ 228 / \ e f / \ / \ 229 / \ | | / \ / \ 230 g h d4 d5 g h i j 231 / \ / \ / \ / \ / \ | 232 a b c d a b c d e f d6 233 | | | | | | | | | | 234 d0 d1 d2 d3 d0 d1 d2 d3 d4 d5 236 The consistency proof between hash0 and hash is PROOF(3, D[0:7]) = 237 [c, d, g, l]. c, g are used to verify hash0, and d, l are 238 additionally used to verify hash. 240 The consistency proof between hash1 and hash is PROOF(4, D[0:7]) = 241 [l]. hash can be verified, using hash1=k and l. 243 The consistency proof between hash2 and hash is PROOF(6, D[0:7]) = 244 [i, j, k]. k, i are used to verify hash1, and j is additionally used 245 to verify hash. 247 2. Log Format 249 Certificate owners will be expected to submit certificates to 250 certificate logs for public auditing. A log is a single, ever- 251 growing, append-only Merkle Tree of such certificates. 253 After accepting a certificate submission, the log MUST immediately 254 return a Signed Certificate Timestamp (SCT). The SCT is the log's 255 promise to incorporate the certificate in the Merkle Tree within a 256 fixed amount of time known as the Maximum Merge Delay (MMD). Servers 257 MUST present an SCT from one or more logs to the client together with 258 the certificate. Clients MUST reject certificates that do not have a 259 valid Signed Certificate Timestamp. 261 Periodically, the log appends all new entries to the Merkle Tree, and 262 signs the root of the tree. Clients and auditors can thus verify 263 that each certificate for which an SCT has been issued indeed appears 264 in the log. The log MUST incorporate a certificate in its Merkle 265 Tree within the Maximum Merge Delay period after the issuance of the 266 SCT. 268 2.1. Log Entries 270 Anyone can submit a certificate to the log. In order to attribute 271 each logged certificate to its issuer, the log shall publish a list 272 of acceptable root certificates (this list should be the union of 273 root certificates trusted by major browser vendors). Each submitted 274 certificate MUST be accompanied by all additional certificates 275 required to verify the certificate chain up to an accepted root 276 certificate. The self-signed root certificate itself MAY be omitted 277 from this list. 279 Alternatively, (root as well as intermediate) Certificate Authorities 280 may submit a certificate to the log prior to issuance. To do so, a 281 Certificate Authority constructs a Precertificate by signing the leaf 282 TBSCertificate [RFC5280] with a special-purpose (Extended Key Usage: 283 Certificate Transparency) Precertificate Signing Certificate. The 284 Precertificate Signing Certificate MUST be certified by the CA 285 certificate. As above, the Precertificate submission MUST be 286 accompanied by the Precertificate Signing Certificate and all 287 additional certificates required to verify the chain up to an 288 accepted root certificate. The signature on the TBSCertificate 289 indicates the Certificate Authority's intent to issue a certificate. 290 This intent is considered binding (i.e., misissuance of the 291 Precertificate is considered equal to misissuance of the final 292 certificate). The log verifies the Precertificate signature chain, 293 and issues a Signed Certificate Timestamp on the corresponding 294 TBSCertificate. The SCT can then be directly embedded in the final 295 certificate, by appending it to the TBSCertificate as an X.509v3 296 certificate extension. Upon receiving the certificate, clients can 297 reconstruct the original TBSCertificate to verify the SCT signature. 299 The log MUST verify that the submitted leaf certificate or 300 Precertificate has a valid signature chain leading back to a trusted 301 root CA certificate, using the chain of intermediate CA certificates 302 provided by the submitter. In case of Precertificates, the log MUST 303 also verify that the Precertificate Signing Certificate has the 304 correct Extended Key Usage extension. The log MAY accept 305 certificates that have expired, are not yet valid, have been revoked 306 or are otherwise not fully valid according to X509 verification 307 rules. However, the log MUST refuse to publish certificates without 308 a valid chain to a known root CA. If a certificate is accepted and 309 an SCT issued, the log MUST store the chain used for verification (or 310 in case of Precertificates, the entire Precertificate chain, 311 including the signed Precertificate), and MUST present this chain for 312 auditing upon request. 314 Each certificate entry in the log MUST include the following 315 components: 317 enum { x509_entry(0), precert_entry(1), (65535) } LogEntryType; 319 struct { 320 LogEntryType entry_type; 321 select (entry_type) { 322 case x509_entry: X509ChainEntry; 323 case precert_entry: PrecertChainEntry; 324 } entry; 325 } LogEntry; 327 opaque ASN.1Cert<1..2^24-1>; 329 struct { 330 ASN.1Cert leaf_certificate; 331 ASN.1Cert certificate_chain<0..2^24-1>; 332 } X509ChainEntry; 334 struct { 335 ASN.1Cert tbs_certificate; 336 ASN.1Cert precertificate_chain<1..2^24-1>; 337 } PrecertChainEntry; 339 [benl: Should we consider a small number for the certificate_chain? 340 Or perhaps note that a log can impose a limit?] 342 "leaf_certificate" is the end-entity certificate submitted for 343 auditing. 345 "certificate_chain" is a chain of additional certificates required to 346 verify the leaf certificate. The first certificate MUST certify the 347 leaf certificate. Each following certificate MUST directly certify 348 the one preceding it. The self-signed root certificate MAY be 349 omitted from the chain. 351 "tbs_certificate" is the TBSCertificate component of the 352 Precertificate (i.e., the original TBSCertificate, without the 353 Precertificate signature and the SCT extension). 355 "precertificate_chain" is a chain of certificates required to verify 356 the Precertificate submission. The first certificate MUST be the 357 original Precertificate, with its unsigned part matching the 358 "tbs_certificate". The second certificate MUST be a valid 359 Precertificate Signing Certificate, and MUST certify the first 360 certificate. Each following certificate MUST directly certify the 361 one preceding it. The self-signed root certificate MAY be omitted 362 from the chain. 364 Structure of the Signed Certificate Timestamp: 366 enum { certificate_timestamp(0), tree_hash(1), 255 } 367 SignatureType; 369 struct { 370 uint64 timestamp; 371 digitally-signed struct { 372 SignatureType signature_type = certificate_timestamp; 373 uint64 timestamp; 374 LogEntryType entry_type; 375 ASN.1Cert certificate; 376 }; 377 } SignedCertificateTimestamp; 379 The encoding of the digitally-signed element is defined in [RFC5246]. 381 "timestamp" is the current UTC time since epoch (January 1, 1970, 382 00:00), in milliseconds. 384 "signed_certificate" is the "leaf_certificate" (in case of an 385 X509ChainEntry), or "tbs_certificate" (in case of a 386 PrecertChainEntry). 388 2.2. Merkle Tree 390 A certificate log MUST periodically append all new log entries to the 391 log Merkle Tree. The log MUST sign these entries by constructing a 392 binary Merkle Tree with log entries as consecutive inputs to the 393 tree, signing the corresponding Merkle Tree Hash, and publishing each 394 update to the tree in a Signed Merkle Tree Update. The hashing 395 algorithm for the Merkle Tree Hash is SHA-256. 397 Structure of the Merkle Tree input: 399 struct { 400 uint64 timestamp; 401 LogEntryType entry_type; 402 ASN.1Cert certificate; 403 } MerkleTreeLeaf; 405 Here "timestamp" is the timestamp of the corresponding SCT issued for 406 this certificate. 408 Structure of the Signed Merkle Tree Update: 410 struct { 411 uint64 old_tree_size; 412 uint64 timestamp; 413 MerkleTreeLeaf new_leaves<0..2^64-1>; 414 digitally-signed struct { 415 SignatureType signature_type = tree_hash; 416 uint64 timestamp; 417 uint64 tree_size; 418 opaque sha256_root_hash[32]; 419 } TreeHeadSignature; 420 } SignedMerkleTreeUpdate; 422 "old_tree_size" is the size of the tree prior to this update. 424 "timestamp" is the current time. The timestamp MUST be at least as 425 recent as the most recent SCT timestamp in the tree. Each subsequent 426 timestamp MUST be more recent than the timestamp of the previous 427 update. 429 "tree_size" equals the number of entries in the new tree. 431 "new_leaves" is the list of leaves added to the tree in this update, 432 ordered by leaf index. This order can be fixed arbitrarily amongst 433 new entries. 435 "sha256_root_hash" is the root of the Merkle Hash Tree. 437 The log MUST produce a Signed Merkle Tree Update at least as often as 438 the Maximum Merge Delay. In the unlikely event that it receives no 439 new submissions during an MMD period, the log SHALL sign the same 440 Merkle Tree Hash with a fresh timestamp. 442 2.3. Audit Proofs 444 It is possible to audit the entire log by computing the current 445 "sha256_root_hash" value from consecutive Signed Merkle Tree Updates, 446 and verifying the Tree Head Signature. We rely on cross-checks of 447 the Signed Tree Head between auditors to verify that their views of 448 the log are consistent. 450 Additionally, logs provide Merkle audit proofs for efficient partial 451 checks. (In fact, anyone can compute audit proofs from the full 452 log.) Merkle audit proofs allow auditors to efficiently verify that 453 a certificate for which an SCT has been issued indeed appears in the 454 log, without inspecting the entire log. 456 Structure of the Merkle audit proof: 458 struct { 459 opaque sha256_hash[32]; 460 } MerkleNode; 462 struct { 463 uint64 tree_size; 464 uint64 timestamp; 465 uint64 leaf_index; 466 MerkleNode audit_path<0..2^16-1>; 467 TreeHeadSignature tree_head_signature; 468 } MerkleAuditProof; 470 "tree_size" is the generation of the tree that this proof is for. 472 "timestamp" is the corresponding timestamp. 474 "leaf_index" is the index of the audited node in the Merkle tree, 475 from 0 to "tree_size - 1". 477 "audit_path" is a list of additional nodes in the Merkle tree 478 required for reconstructing the root hash corresponding to the 479 "tree_size". Nodes must be listed from leaf to root level, i.e., in 480 the order they are used in the Merkle Tree Hash computation, as 481 defined in Section 1.1.1. _Notice that the left-right ordering is 482 determined by the position of the leaf._ The leaf node under audit as 483 well as the root node shall be omitted from the path. 485 "tree_head_signature" is the TreeHeadSignature for generation 486 "tree_size". 488 A valid audit proof for a Merkle Tree Leaf MUST satisfy the 489 following: 491 o The "tree_size" MUST be at least 1; 493 o The "leaf_index" MUST NOT exceed "tree_size - 1"; 495 o The "tree_signature" MUST be a valid signature on the 496 corresponding "timestamp", "tree_size", and the root hash 497 reconstructed from the Merkle Tree Leaf, "leaf_index" and 498 "audit_path". 500 3. Security and Privacy Considerations 502 3.1. Misissued Certificates 504 Misissued certificates that have not been publicly logged, and thus 505 do not have a valid SCT, will be rejected by clients. Misissued 506 certificates that do have an SCT from a log will appear in the public 507 log update within the Maximum Merge Delay, assuming the log is 508 operating correctly. Thus, the maximum period of time during which a 509 misissued certificate can be used without notice is the MMD. 511 3.2. Misbehaving logs 513 A log can misbehave in two ways: (1), by failing to incorporate a 514 certificate with an SCT in the Merkle Tree within the MMD; and (2), 515 by violating its append-only property by presenting two different, 516 conflicting views of the Merkle Tree at different times and/or to 517 different parties. Both forms of violation will be promptly and 518 publicly detectable. 520 Violation of the MMD contract is detected by clients requesting a 521 Merkle audit proof for each observed SCT. These checks can be 522 asynchronous, and need only be done once per each certificate. In 523 order to protect the clients' privacy, these checks need not reveal 524 the exact certificate to the log. Clients can instead request the 525 proof from a trusted auditor (since anyone can compute the audit 526 proofs from the log), or request Merkle proofs for a batch of 527 certificates around the SCT timestamp. 529 Violation of the append-only property is detected by global 530 gossiping, i.e., everyone auditing the log comparing their versions 531 of the latest signed tree head. As soon as two conflicting signed 532 tree heads are detected, this is cryptographic proof of the log's 533 misbehaviour. 535 4. Efficiency Considerations 537 The Merkle tree design serves the purpose of keeping communication 538 overhead low. 540 Auditing the log for integrity does not require third parties to 541 maintain a copy of the entire log. The Signed Tree Head root hash 542 can be updated incrementally as new entries become available, without 543 recomputing the entire tree. Third party auditors need only store a 544 logarithmic number of intermediate nodes in the Merkle Tree. 546 Additionally, the Merkle consistency proofs defined in Section 1.1.2 547 can be used to efficiently prove the append-only property of an 548 incremental update to the Merkle Tree, without auditing the entire 549 tree. 551 5. References 553 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 554 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 556 [RFC5878] Brown, M. and R. Housley, "The Transport Layer Security 557 (TLS) Authorization Extensions", RFC 5280, May 2010. 559 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 560 Housley, R., and W. Polk, "Internet X.509 Public Key 561 Infrastructure Certificate and Certificate Revocation List 562 (CRL) Profile", RFC 5280, May 2008. 564 [1] 566 Authors' Addresses 568 Ben Laurie 570 Email: benl@google.com 572 Adam Langley 574 Email: agl@google.com 576 Emilia Kasper 578 Email: ekasper@google.com