idnits 2.17.1 draft-laurie-pki-sunlight-05.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 : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. ** The document seems to lack a Security Considerations section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 20, 2012) is 4117 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: '7' is mentioned on line 353, but not defined == Missing Reference: '32' is mentioned on line 656, but not defined ** Obsolete normative reference: RFC 2560 (Obsoleted by RFC 6960) ** Obsolete normative reference: RFC 5246 (Obsoleted by RFC 8446) Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). 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 Intended status: Experimental E. Kasper 5 Expires: June 23, 2013 December 20, 2012 7 Certificate Transparency 8 draft-laurie-pki-sunlight-05 10 Abstract 12 The aim of Certificate Transparency is to have every public end- 13 entity (for example, web servers) and intermediate TLS certificate 14 issued by a known Certificate Authority recorded in one or more 15 certificate logs. In order to detect misissuance of certificates, 16 all logs are publicly auditable. In particular, domain owners or 17 their agents will be able to monitor logs for certificates issued on 18 their own domain. 20 To protect clients from unlogged misissued certificates, each log 21 signs all certificates it records, and clients can choose not to 22 trust certificates that are not accompanied by an appropriate log 23 signature. For privacy and performance reasons log signatures are 24 embedded in the TLS handshake via the TLS authorization extension, in 25 a stapled OCSP extension, or in the certificate itself via an X.509v3 26 certificate extension. 28 To ensure a globally consistent view of any particular log, each log 29 also provides a global signature over the entire log. Any 30 inconsistency of logs can be detected through cross-checks on the 31 global signature. Consistency between any pair of global signatures, 32 corresponding to snapshots of a particular log at different times, 33 can be efficiently shown. 35 Logs are only expected to certify that they have seen a certificate, 36 and thus we do not specify any revocation mechanism for log 37 signatures in this document. Logs are append-only, and log 38 signatures do not expire. 40 Requirements Language 42 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 43 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 44 document are to be interpreted as described in RFC 2119 [RFC2119]. 46 Status of this Memo 48 This Internet-Draft is submitted in full conformance with the 49 provisions of BCP 78 and BCP 79. 51 Internet-Drafts are working documents of the Internet Engineering 52 Task Force (IETF). Note that other groups may also distribute 53 working documents as Internet-Drafts. The list of current Internet- 54 Drafts is at http://datatracker.ietf.org/drafts/current/. 56 Internet-Drafts are draft documents valid for a maximum of six months 57 and may be updated, replaced, or obsoleted by other documents at any 58 time. It is inappropriate to use Internet-Drafts as reference 59 material or to cite them other than as "work in progress." 61 This Internet-Draft will expire on June 23, 2013. 63 Copyright Notice 65 Copyright (c) 2012 IETF Trust and the persons identified as the 66 document authors. All rights reserved. 68 This document is subject to BCP 78 and the IETF Trust's Legal 69 Provisions Relating to IETF Documents 70 (http://trustee.ietf.org/license-info) in effect on the date of 71 publication of this document. Please review these documents 72 carefully, as they describe your rights and restrictions with respect 73 to this document. Code Components extracted from this document must 74 include Simplified BSD License text as described in Section 4.e of 75 the Trust Legal Provisions and are provided without warranty as 76 described in the Simplified BSD License. 78 Table of Contents 80 1. Informal introduction . . . . . . . . . . . . . . . . . . . . 4 81 2. Cryptographic components . . . . . . . . . . . . . . . . . . . 6 82 2.1. Merkle Hash Trees . . . . . . . . . . . . . . . . . . . . 6 83 2.1.1. Merkle audit paths . . . . . . . . . . . . . . . . . . 6 84 2.1.2. Merkle consistency proofs . . . . . . . . . . . . . . 7 85 2.1.3. Example . . . . . . . . . . . . . . . . . . . . . . . 8 86 2.1.4. Signatures . . . . . . . . . . . . . . . . . . . . . . 9 87 3. Log Format . . . . . . . . . . . . . . . . . . . . . . . . . . 10 88 3.1. Log Entries . . . . . . . . . . . . . . . . . . . . . . . 10 89 3.2. Including the Signed Certificate Timestamp in the TLS 90 Handshake . . . . . . . . . . . . . . . . . . . . . . . . 14 91 3.3. Merkle Tree . . . . . . . . . . . . . . . . . . . . . . . 15 92 3.4. Tree Head Signature . . . . . . . . . . . . . . . . . . . 16 93 4. Client Messages . . . . . . . . . . . . . . . . . . . . . . . 17 94 4.1. Add Chain to Log . . . . . . . . . . . . . . . . . . . . . 17 95 4.2. Add PreCertChain to Log . . . . . . . . . . . . . . . . . 18 96 4.3. Retrieve Latest Signed Tree Head . . . . . . . . . . . . . 18 97 4.4. Retrieve Merkle Consistency Proof between two Signed 98 Tree Heads . . . . . . . . . . . . . . . . . . . . . . . . 18 99 4.5. Retrieve Merkle Audit Proof from Log by Leaf Hash . . . . 19 100 4.6. Retrieve Entries from Log . . . . . . . . . . . . . . . . 19 101 4.7. Retrieve Entry+Merkle Audit Proof from Log . . . . . . . . 20 102 5. Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 103 5.1. Monitor . . . . . . . . . . . . . . . . . . . . . . . . . 21 104 5.2. Auditor . . . . . . . . . . . . . . . . . . . . . . . . . 22 105 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 106 7. Security and Privacy Considerations . . . . . . . . . . . . . 24 107 7.1. Misissued Certificates . . . . . . . . . . . . . . . . . . 24 108 7.2. Detection of Misissue . . . . . . . . . . . . . . . . . . 24 109 7.3. Misbehaving logs . . . . . . . . . . . . . . . . . . . . . 24 110 8. Efficiency Considerations . . . . . . . . . . . . . . . . . . 25 111 9. Future Changes . . . . . . . . . . . . . . . . . . . . . . . . 26 112 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 27 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 115 1. Informal introduction 117 Certificate Transparency aims to mitigate the problem of misissued 118 certificates by providing publicly auditable, append-only, untrusted 119 logs of all issued certificates. The logs are publicly auditable so 120 that it is possible for anyone to verify the correct operation of 121 each log, and to monitor when new certificates are added to it. The 122 logs do not themselves prevent misissue, but they ensure that 123 interested parties (particularly those named in certificates) can 124 detect such misissuance. Note that this is a general mechanism, but 125 in this document we only describe its use for public TLS server 126 certificates issued by public CAs. 128 Each log consists of certificate chains, which can be submitted by 129 anyone. It is expected that public CAs will contribute all their 130 newly-issued certificates to one or more logs; it is also expected 131 that certificate holders will contribute their own certificate 132 chains. In order to avoid logs being spammed into uselessness, it is 133 required that each chain is rooted in a known CA certificate. When a 134 chain is submitted to a log, a signed timestamp is returned, which 135 can later be used to provide evidence to clients that the chain has 136 been submitted. Clients can thus require that all certificates they 137 see have been logged. 139 Those who are concerned about misissue can monitor the logs, asking 140 them regularly for all new entries, and can thus check whether 141 domains they are responsible for have had certificates issued that 142 they did not expect. What they do with this information, 143 particularly when they find that a misissuance has happened, is 144 beyond the scope of this document, but broadly speaking they can 145 invoke existing business mechanisms for dealing with misissued 146 certificates. Of course, anyone who wants can monitor the logs, and 147 if they believe a certificate is incorrectly issued, take action as 148 they see fit. 150 Similarly, those who have seen signed timestamps from a particular 151 log can later demand a proof of inclusion from that log. If the log 152 is unable to provide this (or, indeed, if the corresponding 153 certificate is absent from monitors' copies of that log), that is 154 evidence of the incorrect operation of the log. The checking 155 operation is asynchronous to allow TLS connections to proceed without 156 delay, despite network connectivity issues and the vagaries of 157 firewalls. 159 The append-only property of each log is technically achieved using 160 Merkle Trees, which can be used to show that any particular version 161 of the log is a superset of any particular previous version. 162 Likewise, Merkle Trees avoid the need to blindly trust logs: if a log 163 attempts to show different things to different people, this can be 164 efficiently detected by comparing tree roots and consistency proofs. 165 Similarly, other misbehaviours of any log (e.g. issuing signed 166 timestamps for certificates they then don't log) can be efficiently 167 detected and proved to the world at large. 169 2. Cryptographic components 171 2.1. Merkle Hash Trees 173 Logs use a binary Merkle hash tree for efficient auditing. The 174 hashing algorithm is SHA-256 (note that this is fixed for this 175 experiment but it is anticipated that each log would be able to 176 specify a hash algorithm). The input to the Merkle tree hash is a 177 list of data entries; these entries will be hashed to form the leaves 178 of the Merkle hash tree. The output is a single 32-byte root hash. 179 Given an ordered list of n inputs, D[n] = {d(0), d(1), ..., d(n-1)}, 180 the Merkle Tree Hash (MTH) is thus defined as follows: 182 The hash of an empty list is the hash of an empty string: 184 MTH({}) = SHA-256(). 186 The hash of a list with one entry is: 188 MTH({d(0)}) = SHA-256(0x00 || d(0)). 190 For n > 1, let k be the largest power of two smaller than n. The 191 Merkle Tree Hash of an n-element list D[n] is then defined 192 recursively as 194 MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])), 196 where || is concatenation and D[k1:k2] denotes the length (k2 - k1) 197 list {d(k1), d(k1+1),..., d(k2-1)}. (Note that the hash calculation 198 for leaves and nodes differ. This domain separation is required to 199 give second preimage resistance.) 201 Note that we do not require the length of the input list to be a 202 power of two. The resulting Merkle tree may thus not be balanced, 203 however, its shape is uniquely determined by the number of leaves. 204 [This Merkle tree is essentially the same as the history tree [1] 205 proposal, except our definition omits dummy leaves.] 207 2.1.1. Merkle audit paths 209 A Merkle audit path for a leaf in a Merkle hash tree is the shortest 210 list of additional nodes in the Merkle tree required to compute the 211 Merkle Tree Hash for that tree. Each node in the tree is either a 212 leaf node, or is computed from the two nodes immediately below it 213 (i.e. towards the leaves). At each step up the tree (towards the 214 root), a node from the audit path is combined with the node computed 215 so far. In other words, the audit path consists of the list of 216 missing nodes required to compute the nodes leading from a leaf to 217 the root of the tree. If the root computed from the audit path 218 matches the true root, then the audit path is proof that the leaf 219 exists in the tree. 221 Given an ordered list of n inputs to the tree, D[n] = {d(0), ..., 222 d(n-1)}, the Merkle audit path PATH(m, D[n]) for the (m+1)th input 223 d(m), 0 <= m < n, is defined as follows: 225 The path for the single leaf in a tree with a one-element input list 226 D[1] = {d(0)} is empty: 228 PATH(0, {d(0)}) = {} 230 For n > 1, let k be the largest power of two smaller than n. The 231 path for the (m+1)th element d(m) in a list of n > m elements is then 232 defined recursively as 234 PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and 236 PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k, 238 where : is concatenation of lists and D[k1:k2] denotes the length (k2 239 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 241 2.1.2. Merkle consistency proofs 243 Merkle consistency proofs prove the append-only property of the tree. 244 A Merkle consistency proof for a Merkle Tree Hash MTH(D[n]) and a 245 previously advertised hash MTH(D[0:m]) of the first m leaves, m <= n, 246 is the list of nodes in the Merkle tree required to verify that the 247 first m inputs D[0:m] are equal in both trees. Thus, a consistency 248 proof must contain a set of intermediate nodes (i.e., commitments to 249 inputs) sufficient to verify MTH(D[n]), such that (a subset of) the 250 same nodes can be used to verify MTH(D[0:m]). We define an algorithm 251 that outputs the (unique) minimal consistency proof. 253 Given an ordered list of n inputs to the tree, D[n] = {d(0), ..., 254 d(n-1)}, the Merkle consistency proof PROOF(m, D[n]) for a previous 255 root hash MTH(D[0:m]), 0 < m < n, is defined as PROOF(m, D[n]) = 256 SUBPROOF(m, D[n], true): 258 The subproof for m = n is empty if m is the value for which PROOF was 259 originally requested (meaning that the subtree root hash MTH(D[0:m]) 260 is known): 262 SUBPROOF(m, D[m], true) = {} 264 The subproof for m = n is the root hash committing inputs D[0:m] 265 otherwise: 267 SUBPROOF(m, D[m], false) = {MTH(D[m])} 269 For m < n, let k be the largest power of two smaller than n. The 270 subproof is then defined recursively. 272 If m <= k, the right subtree entries D[k:n] only exist in the current 273 tree. We prove that the left subtree entries D[0:k] are consistent 274 and add a commitment to D[k:n]: 276 SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n]). 278 If m > k, the left subtree entries D[0:k] are identical in both 279 trees. We prove that the right subtree entries D[k:n] are consistent 280 and add a commitment to D[0:k]. 282 SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k]). 284 Here : is concatenation of lists and D[k1:k2] denotes the length (k2 285 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 287 The number of nodes in the resulting proof is bounded above by 288 ceil(log2(n)) + 1. 290 2.1.3. Example 292 The binary Merkle tree with 7 leaves: 294 hash 295 / \ 296 / \ 297 / \ 298 / \ 299 / \ 300 k l 301 / \ / \ 302 / \ / \ 303 / \ / \ 304 g h i j 305 / \ / \ / \ | 306 a b c d e f d6 307 | | | | | | 308 d0 d1 d2 d3 d4 d5 310 The audit path for d0 is [b, h, l]. 312 The audit path for d3 is [c, g, l]. 314 The audit path for d4 is [f, j, k]. 316 The audit path for d6 is [i, k]. 318 The same tree, built incrementally in four steps: 320 hash0 hash1=k 321 / \ / \ 322 / \ / \ 323 / \ / \ 324 g c g h 325 / \ | / \ / \ 326 a b d2 a b c d 327 | | | | | | 328 d0 d1 d0 d1 d2 d3 330 hash2 hash 331 / \ / \ 332 / \ / \ 333 / \ / \ 334 / \ / \ 335 / \ / \ 336 k i k l 337 / \ / \ / \ / \ 338 / \ e f / \ / \ 339 / \ | | / \ / \ 340 g h d4 d5 g h i j 341 / \ / \ / \ / \ / \ | 342 a b c d a b c d e f d6 343 | | | | | | | | | | 344 d0 d1 d2 d3 d0 d1 d2 d3 d4 d5 346 The consistency proof between hash0 and hash is PROOF(3, D[7]) = [c, 347 d, g, l]. c, g are used to verify hash0, and d, l are additionally 348 used to show hash is consistent with hash0. 350 The consistency proof between hash1 and hash is PROOF(4, D[7]) = [l]. 351 hash can be verified, using hash1=k and l. 353 The consistency proof between hash2 and hash is PROOF(6, D[7]) = [i, 354 j, k]. k, i are used to verify hash2, and j is additionally used to 355 show hash is consistent with hash2. 357 2.1.4. Signatures 359 Various data structures are signed. A log can use either elliptic 360 curve signatures using the NIST P-256 curve (section D.1.2.3 of DSS 361 [DSS]) or RSA signatures using a key of at least 2048 bits. 363 3. Log Format 365 Anyone can submit certificates to certificate logs for public 366 auditing, however, since certificates will not be accepted by clients 367 unless logged, it is expected that certificate owners or their CAs 368 will usually submit them. A log is a single, ever-growing, append- 369 only Merkle Tree of such certificates. 371 When a valid certificate is submitted to a log, the log MUST 372 immediately return a Signed Certificate Timestamp (SCT). The SCT is 373 the log's promise to incorporate the certificate in the Merkle Tree 374 within a fixed amount of time known as the Maximum Merge Delay (MMD). 375 If the log has previously seen the certificate, it MAY return the 376 same SCT as it returned before. TLS servers MUST present an SCT from 377 one or more logs to the client together with the certificate. TLS 378 clients MUST reject certificates that do not have a valid SCT for the 379 end-entity certificate. 381 Periodically, each log appends all its new entries to the Merkle 382 Tree, and signs the root of the tree. Clients and auditors can thus 383 verify that each certificate for which an SCT has been issued indeed 384 appears in the log. The log MUST incorporate a certificate in its 385 Merkle Tree within the Maximum Merge Delay period after the issuance 386 of the SCT. 388 Logs MUST NOT impose any conditions on copying data retrieved from 389 the log. 391 3.1. Log Entries 393 Anyone can submit a certificate to any log. In order to enable 394 attribution of each logged certificate to its issuer, the log SHALL 395 publish a list of acceptable root certificates (this list might 396 usefully be the union of root certificates trusted by major browser 397 vendors). Each submitted certificate MUST be accompanied by all 398 additional certificates required to verify the certificate chain up 399 to an accepted root certificate. The root certificate itself MAY be 400 omitted from this list. 402 Alternatively, (root as well as intermediate) Certificate Authorities 403 may submit a certificate to logs prior to issuance. To do so, a 404 Certificate Authority constructs a Precertificate by adding a special 405 critical poison extension (OID 1.3.6.1.4.1.11129.2.4.3, whose 406 extnValue OCTET STRING contains ASN.1 NULL data (0x05 0x00)) to the 407 leaf TBSCertificate (this extension is to ensure that the 408 Precertificate cannot be validated by a standard X.509v3 client), and 409 signing the resulting TBSCertificate [RFC5280] with either 410 o a special-purpose (Extended Key Usage: Certificate Transparency, 411 OID 1.3.6.1.4.1.11129.2.4.4) Precertificate Signing Certificate. 412 The Precertificate Signing Certificate MUST be certified by the CA 413 certificate that will ultimately sign the leaf TBSCertificate 414 (note that the log may relax standard validation rules to allow 415 this, so long as the final signed certificate will be valid), 417 o or, the CA certificate that will sign the final certificate. 419 As above, the Precertificate submission MUST be accompanied by the 420 Precertificate Signing Certificate, if used, and all additional 421 certificates required to verify the chain up to an accepted root 422 certificate. The signature on the TBSCertificate indicates the 423 Certificate Authority's intent to issue a certificate. This intent 424 is considered binding (i.e., misissuance of the Precertificate is 425 considered equal to misissuance of the final certificate). Each log 426 verifies the Precertificate signature chain, and issues a Signed 427 Certificate Timestamp on the corresponding TBSCertificate. 429 Logs MUST verify that the submitted leaf certificate or 430 Precertificate has a valid signature chain leading back to a trusted 431 root CA certificate, using the chain of intermediate CA certificates 432 provided by the submitter. In case of Precertificates, each log MUST 433 also verify that the Precertificate Signing Certificate has the 434 correct Extended Key Usage extension. Logs MAY accept certificates 435 that have expired, are not yet valid, have been revoked or are 436 otherwise not fully valid according to X.509 verification rules in 437 order to accomodate quirks of CA certificate issuing software. 438 However, logs MUST refuse to publish certificates without a valid 439 chain to a known root CA. If a certificate is accepted and an SCT 440 issued, the accepting log MUST store the chain used for verification 441 including the certificate or Precertificate itself, and MUST present 442 this chain for auditing upon request. This chain is required to 443 prevent a CA avoiding blame by logging a partial or empty chain 444 [Note: this effectively excludes self-signed and DANE-based 445 certificates until some mechanism to control spam for those 446 certificates is found - the authors welcome suggestions]. 448 Each certificate entry in a log MUST include the following 449 components: 451 enum { x509_entry(0), precert_entry(1), (65535) } LogEntryType; 453 struct { 454 LogEntryType entry_type; 455 select (entry_type) { 456 case x509_entry: X509ChainEntry; 457 case precert_entry: PrecertChainEntry; 458 } entry; 459 } LogEntry; 461 opaque ASN.1Cert<1..2^24-1>; 463 struct { 464 ASN.1Cert leaf_certificate; 465 ASN.1Cert certificate_chain<0..2^24-1>; 466 } X509ChainEntry; 468 struct { 469 ASN.1Cert tbs_certificate; 470 ASN.1Cert precertificate_chain<1..2^24-1>; 471 } PrecertChainEntry; 473 Logs MAY limit the length of chain they will accept. 475 "entry_type" is the type of this entry. Future revisions of this 476 protocol version may add new LogEntryType values. Section 4 explains 477 how clients should handle unknown entry types. 479 "leaf_certificate" is the end-entity certificate submitted for 480 auditing. 482 "certificate_chain" is a chain of additional certificates required to 483 verify the leaf certificate. The first certificate MUST certify the 484 leaf certificate. Each following certificate MUST directly certify 485 the one preceding it. The self-signed root certificate MAY be 486 omitted from the chain. 488 "tbs_certificate" is the TBSCertificate component of the 489 Precertificate (i.e., the original TBSCertificate, without the 490 Precertificate signature and the SCT extension). 492 "precertificate_chain" is a chain of certificates required to verify 493 the Precertificate submission. The first certificate MUST be the 494 original Precertificate, with its unsigned part matching the 495 "tbs_certificate". The second certificate MUST be a valid 496 Precertificate Signing Certificate, and MUST certify the first 497 certificate. Each following certificate MUST directly certify the 498 one preceding it. The self-signed root certificate MAY be omitted 499 from the chain. 501 Structure of the Signed Certificate Timestamp: 503 enum { certificate_timestamp(0), tree_hash(1), 255 } 504 SignatureType; 506 enum { v1(0), 255 } 507 Version; 509 struct { 510 opaque key_id[32]; 511 } LogID; 513 opaque CtExtensions<0..2^16-1>; 515 "key_id" is the SHA-256 hash of the log's public key, calculated over 516 the DER encoding of the key represented as SubjectPublicKeyInfo. 518 struct { 519 Version sct_version; 520 LogID id; 521 uint64 timestamp; 522 CtExtensions extensions; 523 digitally-signed struct { 524 Version sct_version; 525 SignatureType signature_type = certificate_timestamp; 526 uint64 timestamp; 527 LogEntryType entry_type; 528 select(entry_type) { 529 case x509_entry: ASN.1Cert; 530 case precert_entry: ASN.1Cert; 531 } signed_entry; 532 CtExtensions extensions; 533 }; 534 } SignedCertificateTimestamp; 536 The encoding of the digitally-signed element is defined in [RFC5246]. 538 "sct_version" is the version of the protocol the SCT conforms to. 539 This version is v1. 541 "timestamp" is the current UTC time since epoch (January 1, 1970, 542 00:00), in milliseconds. 544 "entry_type" may be implicit from the context in which the SCT is 545 presented. 547 "signed_entry" is the "leaf_certificate" (in case of an 548 X509ChainEntry), or "tbs_certificate" (in case of a 549 PrecertChainEntry). 551 "extensions" are future extensions to this protocol version (v1). 552 Currently, no extensions are specified. 554 3.2. Including the Signed Certificate Timestamp in the TLS Handshake 556 The SCT data from at least one log must be included in the TLS 557 handshake, either by using an Authorization Extension [RFC5878] with 558 type 182, or by using OCSP Stapling (section 8 of [RFC6066]), where 559 the response includes an OCSP extension with OID 560 1.3.6.1.4.1.11129.2.4.5 (see [RFC2560]) and body: 562 SignedCertificateTimestampList ::= OCTET STRING 564 At least one SCT MUST be included. Server operators MAY include more 565 than one SCT. 567 Similarly, a Certificate Authority MAY submit the precertificate to 568 more than one log, and all obtained SCTs can be directly embedded in 569 the final certificate, by encoding the SignedCertificateTimestampList 570 structure as an ASN.1 OCTET STRING and inserting the resulting data 571 in the TBSCertificate as an X.509v3 certificate extension (OID 572 1.3.6.1.4.1.11129.2.4.2). Upon receiving the certificate, clients 573 can reconstruct the original TBSCertificate to verify the SCT 574 signature. 576 The contents of the ASN.1 OCTET STRING embedded in an OCSP extension 577 or X509v3 certificate extension are as follows: 579 opaque SerializedSCT<1..2^16-1>; 581 struct { 582 SerializedSCT sct_list <1..2^16-1>; 583 } SignedCertificateTimestampList; 585 Here "SerializedSCT" is an opaque bytestring that contains the 586 serialized TLS structure. This encoding ensures that clients can 587 decode each SCT individually (i.e., if there is a version upgrade, 588 out of date clients can still parse old SCTs while skipping over new 589 SCTs whose version they don't understand). 591 SCTs embedded in the TLS Authorization Extension are each encoded as 592 an individual AuthorizationDataEntry [RFC5878]. 594 3.3. Merkle Tree 596 Each certificate log MUST periodically append all its new log entries 597 to the log Merkle Tree. The log MUST sign these entries by 598 constructing a binary Merkle Tree with log entries as consecutive 599 inputs to the tree, signing the corresponding Merkle Tree Hash, and 600 publishing each update to the tree in a Signed Merkle Tree Update. 601 The hashing algorithm for the Merkle Tree Hash is SHA-256. 603 Structure of the Merkle Tree input: 605 enum { timestamped_entry(0), 255 } 606 MerkleLeafType; 608 struct { 609 uint64 timestamp; 610 LogEntryType entry_type; 611 select(entry_type) { 612 case x509_entry: ASN.1Cert; 613 case precert_entry: ASN.1Cert; 614 } signed_entry; 615 CtExtensions extensions; 616 } TimestampedEntry; 618 struct { 619 Version version; 620 MerkleLeafType leaf_type; 621 select (leaf_type) { 622 case timestamped_entry: TimestampedEntry; 623 } 624 } MerkleTreeLeaf; 626 Here "version" is the version of the protocol the MerkleTreeLeaf 627 corresponds to. This version is v1. 629 "leaf_type" is the type of the leaf input. Currently, only 630 "timestamped_entry" (corresponding to an SCT) is defined. Future 631 revisions of this protocol version may add new MerkleLeafType types. 632 Section 4 explains how clients should handle unknown leaf types. 634 "timestamp" is the timestamp of the corresponding SCT issued for this 635 certificate. 637 "signed_entry" is the "signed_entry" of the corresponding SCT. 639 "extensions" are "extensions" of the corresponding SCT. 641 The leaves of the Merkle Tree are the hashes of the corresponding 642 "MerkleTreeLeaf" structures. 644 3.4. Tree Head Signature 646 Every time a log appends new entries to the tree, the log MUST sign 647 the corresponding tree hash and tree information (see also the 648 corresponding Signed Tree Head client message in Section 4.3). The 649 signature input is structured as follows: 651 digitally-signed struct { 652 Version version; 653 SignatureType signature_type = tree_hash; 654 uint64 timestamp; 655 uint64 tree_size; 656 opaque sha256_root_hash[32]; 657 } TreeHeadSignature; 659 "version" is the version of the protocol the TreeHeadSignature 660 conforms to. This version is v1. 662 "timestamp" is the current time. The timestamp MUST be at least as 663 recent as the most recent SCT timestamp in the tree. Each subsequent 664 timestamp MUST be more recent than the timestamp of the previous 665 update. 667 "tree_size" equals the number of entries in the new tree. 669 "sha256_root_hash" is the root of the Merkle Hash Tree. 671 Each log MUST produce a Tree Head Signature at least as often as the 672 Maximum Merge Delay. In the unlikely event that it receives no new 673 submissions during an MMD period, the log SHALL sign the same Merkle 674 Tree Hash with a fresh timestamp. 676 4. Client Messages 678 Messages are sent as HTTPS GET or POST requests. Parameters for 679 POSTs and all responses are encoded as JSON objects. Parameters for 680 GETs are encoded as URL parameters. Binary data is base64 encoded as 681 specified in the individual messages. 683 The prefix can include a path as well as a server name 684 and a port. It must map one-to-one to a known public key (how this 685 mapping is distributed is out of scope for this document). 687 In general, where needed, the "version" is v1 and the "id" is the log 688 id for the log server queried. 690 4.1. Add Chain to Log 692 POST https:///ct/v1/add-chain 694 Inputs 696 chain An array of base64 encoded certificates. The first element is 697 the leaf certificate, the second chains to the first and so on to 698 the last, which is either the root certificate or a certificate 699 that chains to a known root certificate. 701 Outputs 703 sct_version The version of the SignedCertificateTimestamp structure, 704 in decimal. A compliant v1 implementation MUST NOT expect this to 705 be 0 (i.e. v1). 707 id The log ID, base64 encoded. Since clients who request an SCT for 708 inclusion in the TLS handshake are not required to verify it, we 709 do not assume they know the ID of the log. 711 timestamp The SCT timestamp, in decimal. 713 extensions An opaque type for future expansion. It is likely that 714 not all participants will need to understand data in this field. 715 Logs should set this to the empty string. Clients should decode 716 the base64 encoded data and include it in the SCT. 718 signature The SCT signature, base64 encoded. 720 If the "sct_version" is not v1, then a v1 client may be unable to 721 verify the signature. It MUST NOT construe this as an error. [Note: 722 log clients don't need to be able to verify this structure, only TLS 723 clients do - if we were to serve the structure binary, then we could 724 completely change it without requiring an upgrade to v1 clients]. 726 4.2. Add PreCertChain to Log 728 POST https:///ct/v1/add-pre-chain 730 Inputs 732 chain An array of base64 encoded precertificates. The first element 733 is the leaf certificate, the second chains to the first and so on 734 to the last, which is either the root certificate or a certificate 735 that chains to a known root certificate. 737 Outputs are the same as Section 4.1. 739 4.3. Retrieve Latest Signed Tree Head 741 GET https:///ct/v1/get-sth 743 No inputs. 745 Outputs 747 tree_size The size of the tree, in entries, in decimal. 749 timestamp The timestamp, in decimal. 751 sha256_root_hash The root hash of the tree, in base64. 753 tree_head_signature A TreeHeadSignature for the above data. 755 4.4. Retrieve Merkle Consistency Proof between two Signed Tree Heads 757 GET https:///ct/v1/get-sth-consistency 759 Inputs 761 first The tree_size of the first tree, in decimal. 763 second The tree_size of the second tree, in decimal. 765 Both tree sizes must be from published v1 STHs (Signed Tree Heads). 767 Outputs 768 consistency An array of Merkle tree nodes, base64 encoded. 770 Note that no signature is required on this data, as it is used to 771 verify an STH, which is signed. 773 4.5. Retrieve Merkle Audit Proof from Log by Leaf Hash 775 GET https:///ct/v1/get-proof-by-hash 777 Inputs 779 hash A base64 encoded v1 leaf hash. 781 tree_size The tree_size of the tree to base the proof on, in 782 decimal. 784 The "hash" must be calculated as defined in Section 3.3. The 785 "tree_size" must designate a published v1 STH. 787 Outputs 789 timestamp The tree's timestamp, in decimal. 791 leaf_index The index of the leaf corresponding to the "hash" 792 parameter. 794 audit_path An array of base64 encoded Merkle tree nodes proving the 795 inclusion of the chosen certificate. 797 4.6. Retrieve Entries from Log 799 GET https:///ct/v1/get-entries 801 Inputs 803 start Index of first entry to retrieve, in decimal. 805 end Index of last entry to retrieve, in decimal. 807 Outputs 809 entries An array of objects, each consisting of 811 leaf_input The base64-encoded MerkleTreeLeaf structure. 813 extra_data The base64-encoded unsigned data pertaining to the log 814 entry. In the case of an X509ChainEntry, this is the 815 "certificate_chain". In the case of a PrecertChainEntry, this 816 is the "precertificate_chain". 818 Note that this message is not signed - the retrieved data can be 819 verified by constructing the root hash corresponding to a retrieved 820 STH. All leaves MUST be v1. However, a compliant v1 client MUST NOT 821 construe an unrecognized MerkleLeafType or LogEntryType value as an 822 error. This means it may be unable to parse some entries, but note 823 that each client can inspect the entries it does recognize, as well 824 as verify the integrity of the data by treating unrecognized leaves 825 as opaque input to the tree. 827 4.7. Retrieve Entry+Merkle Audit Proof from Log 829 GET https:///ct/v1/get-entry-and-proof 831 Inputs 833 leaf_index The index of the desired entry. 835 tree_size The tree_size of the tree for which the proof is desired. 837 The tree size must designate a published STH. 839 Outputs 841 entries An array of objects, each consisting of 843 leaf_input The base64-encoded MerkleTreeLeaf structure. 845 auxiliary_data The base64-encoded unsigned data, same as in 846 Section 4.6. 848 timestamp The tree's timestamp, in decimal. 850 audit_path An array of base64 encoded Merkle tree nodes proving the 851 inclusion of the chosen certificate. 853 This API is probably only useful for debugging. 855 5. Clients 857 There are various different functions clients of logs might perform. 858 We describe here some typical clients and how they could function. 859 Any inconsistency may be used as evidence that a log has not behaved 860 correctly, and the signatures on the data structures prevent the log 861 from denying that misbehaviour. 863 All clients should gossip with each other, exchanging STHs at least: 864 this is all that is required to ensure that they all have a 865 consistent view. The exact mechanism for gossip will be described in 866 an separate document, but it is expected there will be a variety. 868 5.1. Monitor 870 Monitors watch logs and check that they behave correctly. They also 871 watch for certificates of interest. 873 A monitor needs to, at least, inspect every new entry in each log it 874 watches. It may also want to keep copies of entire logs. In order 875 to do this, it should follow these steps for each log: 877 1. Fetch the current STH using Section 4.3. 879 2. Verify the STH signature. 881 3. Fetch all the entries in the tree corresponding to the STH using 882 Section 4.6. 884 4. Confirm that the tree made from the fetched entries produces the 885 same hash as that in the STH. 887 5. Fetch the current STH using Section 4.3. Repeat until STH 888 changes. 890 6. Verify the STH signature. 892 7. Fetch all the new entries in the tree corresponding to the STH 893 using Section 4.6. If they remain unavailable for an extended 894 period, then this should be viewed as misbehaviour on the part of 895 the log. 897 8. Either: 899 1. Verify that the updated list of all entries generates a tree 900 with the same hash as the new STH. 902 Or, if it is not keeping all log entries: 904 2. Fetch a consistency proof for the new STH with the previous 905 STH using Section 4.4. 907 3. Verify the consistency proof. 909 4. Verify that the new entries generate the corresponding 910 elements in the consistency proof. 912 9. Go to Step 5. 914 5.2. Auditor 916 Auditors take partial information about a log as input and verify 917 that this information is consistent with other partial information 918 they have. An auditor might be an integral component of a TLS 919 client, it might be a standalone service or it might be a secondary 920 function of a monitor. 922 Any pair of STHs from the same log can be verified by requesting a 923 consistency proof using Section 4.4. 925 A certificate accompanied by an SCT can be verified against any STH 926 dated after the SCT timestamp + the Maximum Merge Delay by requesting 927 a Merkle Audit Proof using Section 4.5. 929 Auditors can fetch STHs from time to time of their own accord, of 930 course, using Section 4.3. 932 6. IANA Considerations 934 IANA is requested to allocate an RFC 5878 AuthorizationData Type for 935 the CST included in an Authorization Extension. The value 182 is 936 preferred. 938 7. Security and Privacy Considerations 940 7.1. Misissued Certificates 942 Misissued certificates that have not been publicly logged, and thus 943 do not have a valid SCT, will be rejected by clients. Misissued 944 certificates that do have an SCT from a log will appear in that 945 public log within the Maximum Merge Delay, assuming the log is 946 operating correctly. Thus, the maximum period of time during which a 947 misissued certificate can be used without being available for audit 948 is the MMD. 950 7.2. Detection of Misissue 952 The logs do not themselves detect misissued certificates, they rely 953 instead on interested parties, such as domain owners, to monitor them 954 and take corrective action when a misissue is detected. 956 7.3. Misbehaving logs 958 A log can misbehave in two ways: (1), by failing to incorporate a 959 certificate with an SCT in the Merkle Tree within the MMD; and (2), 960 by violating its append-only property by presenting two different, 961 conflicting views of the Merkle Tree at different times and/or to 962 different parties. Both forms of violation will be promptly and 963 publicly detectable. 965 Violation of the MMD contract is detected by clients requesting a 966 Merkle audit proof for each observed SCT. These checks can be 967 asynchronous, and need only be done once per each certificate. In 968 order to protect the clients' privacy, these checks need not reveal 969 the exact certificate to the log. Clients can instead request the 970 proof from a trusted auditor (since anyone can compute the audit 971 proofs from the log), or request Merkle proofs for a batch of 972 certificates around the SCT timestamp. 974 Violation of the append-only property is detected by global 975 gossiping, i.e., everyone auditing logs comparing their versions of 976 the latest signed tree heads. As soon as two conflicting signed tree 977 heads for the same log are detected, this is cryptographic proof of 978 the that log's misbehaviour. 980 8. Efficiency Considerations 982 The Merkle tree design serves the purpose of keeping communication 983 overhead low. 985 Auditing logs for integrity does not require third parties to 986 maintain a copy of each entire log. The Signed Tree Heads can be 987 updated as new entries become available, without recomputing entire 988 trees. Third party auditors need only fetch the Merkle consistency 989 proofs against a log's existing STH to efficiently verify the append- 990 only property of updates to their Merkle Trees, without auditing the 991 entire tree. 993 9. Future Changes 995 This section lists things we might address in a Standards Track 996 version of this document. 998 Rather than forcing a log operator to create a new log in order to 999 change the log signing key, we may allow some key roll mechanism. 1001 We may add hash and signing algorithm agility. 1003 We may describe some gossip protocols. 1005 10. References 1007 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1008 Requirement Levels", BCP 14, RFC 2119, March 1997. 1010 [RFC2560] Myers, M., Ankney, R., Malpani, A., Galperin, S., and C. 1011 Adams, "X.509 Internet Public Key Infrastructure Online 1012 Certificate Status Protocol - OCSP", RFC 2560, June 1999. 1014 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 1015 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 1017 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 1018 Housley, R., and W. Polk, "Internet X.509 Public Key 1019 Infrastructure Certificate and Certificate Revocation List 1020 (CRL) Profile", RFC 5280, May 2008. 1022 [RFC5878] Brown, M. and R. Housley, "The Transport Layer Security 1023 (TLS) Authorization Extensions", RFC 5878, May 2010. 1025 [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: 1026 Extension Definitions", RFC 6066, January 2011. 1028 [DSS] National Institute of Standards and Technology, U.S. 1029 Department of Commerce, "Digital Signature Standard", 1030 FIPS 186-3, June 2009. 1032 [1] 1034 Authors' Addresses 1036 Ben Laurie 1038 Email: benl@google.com 1040 Adam Langley 1042 Email: agl@google.com 1044 Emilia Kasper 1046 Email: ekasper@google.com