idnits 2.17.1 draft-laurie-pki-sunlight-07.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 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 (January 29, 2013) is 4076 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 224 -- Looks like a reference, but probably isn't: '7' on line 351 -- Looks like a reference, but probably isn't: '32' on line 700 == Missing Reference: 'TBD' is mentioned on line 629, but not defined ** Obsolete normative reference: RFC 2560 (Obsoleted by RFC 6960) ** Obsolete normative reference: RFC 3447 (Obsoleted by RFC 8017) ** Obsolete normative reference: RFC 4627 (Obsoleted by RFC 7158, RFC 7159) ** Obsolete normative reference: RFC 5246 (Obsoleted by RFC 8446) Summary: 6 errors (**), 0 flaws (~~), 2 warnings (==), 4 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 Intended status: Experimental E. Kasper 5 Expires: August 2, 2013 January 29, 2013 7 Certificate Transparency 8 draft-laurie-pki-sunlight-07 10 Abstract 12 This document describes an experimental protocol for publicly logging 13 the existence of TLS certificates as they are issued or observed, in 14 a manner that allows anyone to audit certificate authority activity 15 and notice the issuance of suspect certificates, as well as to audit 16 the certificate logs themselves. The intent is that eventually 17 clients would refuse to honor certificates which do not appear in a 18 log, effectively forcing CAs to add all issued certificates to the 19 logs. 21 Logs are network services which implement the protocol operations for 22 submissions and queries that are defined in this document. 24 Status of this Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on August 2, 2013. 41 Copyright Notice 43 Copyright (c) 2013 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Informal introduction . . . . . . . . . . . . . . . . . . . . 4 59 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 5 60 1.2. Data structures . . . . . . . . . . . . . . . . . . . . . 5 61 2. Cryptographic components . . . . . . . . . . . . . . . . . . . 6 62 2.1. Merkle Hash Trees . . . . . . . . . . . . . . . . . . . . 6 63 2.1.1. Merkle audit paths . . . . . . . . . . . . . . . . . . 6 64 2.1.2. Merkle consistency proofs . . . . . . . . . . . . . . 7 65 2.1.3. Example . . . . . . . . . . . . . . . . . . . . . . . 8 66 2.1.4. Signatures . . . . . . . . . . . . . . . . . . . . . . 10 67 3. Log Format and Operation . . . . . . . . . . . . . . . . . . . 11 68 3.1. Log Entries . . . . . . . . . . . . . . . . . . . . . . . 11 69 3.2. Structure of the Signed Certificate Timestamp . . . . . . 14 70 3.3. Including the Signed Certificate Timestamp in the TLS 71 Handshake . . . . . . . . . . . . . . . . . . . . . . . . 15 72 3.3.1. TLS Extension . . . . . . . . . . . . . . . . . . . . 16 73 3.4. Merkle Tree . . . . . . . . . . . . . . . . . . . . . . . 17 74 3.5. Signed Tree Head . . . . . . . . . . . . . . . . . . . . . 18 75 4. Log Client Messages . . . . . . . . . . . . . . . . . . . . . 19 76 4.1. Add Chain to Log . . . . . . . . . . . . . . . . . . . . . 19 77 4.2. Add PreCertChain to Log . . . . . . . . . . . . . . . . . 20 78 4.3. Retrieve Latest Signed Tree Head . . . . . . . . . . . . . 20 79 4.4. Retrieve Merkle Consistency Proof between two Signed 80 Tree Heads . . . . . . . . . . . . . . . . . . . . . . . . 20 81 4.5. Retrieve Merkle Audit Proof from Log by Leaf Hash . . . . 21 82 4.6. Retrieve Entries from Log . . . . . . . . . . . . . . . . 21 83 4.7. Retrieve Accepted Root Certificates . . . . . . . . . . . 22 84 4.8. Retrieve Entry+Merkle Audit Proof from Log . . . . . . . . 22 85 5. Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 86 5.1. Submitters . . . . . . . . . . . . . . . . . . . . . . . . 24 87 5.2. TLS Client . . . . . . . . . . . . . . . . . . . . . . . . 24 88 5.3. Monitor . . . . . . . . . . . . . . . . . . . . . . . . . 24 89 5.4. Auditor . . . . . . . . . . . . . . . . . . . . . . . . . 25 90 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 91 7. Security Considerations . . . . . . . . . . . . . . . . . . . 27 92 7.1. Misissued Certificates . . . . . . . . . . . . . . . . . . 27 93 7.2. Detection of Misissue . . . . . . . . . . . . . . . . . . 27 94 7.3. Misbehaving logs . . . . . . . . . . . . . . . . . . . . . 27 95 8. Efficiency Considerations . . . . . . . . . . . . . . . . . . 28 96 9. Future Changes . . . . . . . . . . . . . . . . . . . . . . . . 29 97 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 98 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 100 1. Informal introduction 102 Certificate Transparency aims to mitigate the problem of misissued 103 certificates by providing publicly auditable, append-only, untrusted 104 logs of all issued certificates. The logs are publicly auditable so 105 that it is possible for anyone to verify the correctness of each log, 106 and to monitor when new certificates are added to it. The logs do 107 not themselves prevent misissue, but they ensure that interested 108 parties (particularly those named in certificates) can detect such 109 misissuance. Note that this is a general mechanism, but in this 110 document we only describe its use for public TLS server certificates 111 issued by public CAs. 113 Each log consists of certificate chains, which can be submitted by 114 anyone. It is expected that public CAs will contribute all their 115 newly-issued certificates to one or more logs; it is also expected 116 that certificate holders will contribute their own certificate 117 chains. In order to avoid logs being spammed into uselessness, it is 118 required that each chain is rooted in a known CA certificate. When a 119 chain is submitted to a log, a signed timestamp is returned, which 120 can later be used to provide evidence to clients that the chain has 121 been submitted. TLS clients can thus require that all certificates 122 they see have been logged. 124 Those who are concerned about misissue can monitor the logs, asking 125 them regularly for all new entries, and can thus check whether 126 domains they are responsible for have had certificates issued that 127 they did not expect. What they do with this information, 128 particularly when they find that a misissuance has happened, is 129 beyond the scope of this document, but broadly speaking they can 130 invoke existing business mechanisms for dealing with misissued 131 certificates. Of course, anyone who wants can monitor the logs, and 132 if they believe a certificate is incorrectly issued, take action as 133 they see fit. 135 Similarly, those who have seen signed timestamps from a particular 136 log can later demand a proof of inclusion from that log. If the log 137 is unable to provide this (or, indeed, if the corresponding 138 certificate is absent from monitors' copies of that log), that is 139 evidence of the incorrect operation of the log. The checking 140 operation is asynchronous to allow TLS connections to proceed without 141 delay, despite network connectivity issues and the vagaries of 142 firewalls. 144 The append-only property of each log is technically achieved using 145 Merkle Trees, which can be used to show that any particular version 146 of the log is a superset of any particular previous version. 147 Likewise, Merkle Trees avoid the need to blindly trust logs: if a log 148 attempts to show different things to different people, this can be 149 efficiently detected by comparing tree roots and consistency proofs. 150 Similarly, other misbehaviours of any log (e.g. issuing signed 151 timestamps for certificates they then don't log) can be efficiently 152 detected and proved to the world at large. 154 1.1. Requirements Language 156 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 157 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 158 document are to be interpreted as described in RFC 2119 [RFC2119]. 160 1.2. Data structures 162 Data structures are defined according to the conventions laid out in 163 section 4 of [RFC5246]. 165 2. Cryptographic components 167 2.1. Merkle Hash Trees 169 Logs use a binary Merkle hash tree for efficient auditing. The 170 hashing algorithm is SHA-256 [FIPS.180-2.2002] (note that this is 171 fixed for this experiment but it is anticipated that each log would 172 be able to specify a hash algorithm). The input to the Merkle Tree 173 Hash is a list of data entries; these entries will be hashed to form 174 the leaves of the Merkle hash tree. The output is a single 32-byte 175 Merkle Tree Hash. Given an ordered list of n inputs, D[n] = {d(0), 176 d(1), ..., d(n-1)}, the Merkle Tree Hash (MTH) is thus defined as 177 follows: 179 The hash of an empty list is the hash of an empty string: 181 MTH({}) = SHA-256(). 183 The hash of a list with one entry (also known as a leaf hash) is: 185 MTH({d(0)}) = SHA-256(0x00 || d(0)). 187 For n > 1, let k be the largest power of two smaller than n. The 188 Merkle Tree Hash of an n-element list D[n] is then defined 189 recursively as 191 MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])), 193 where || is concatenation and D[k1:k2] denotes the length (k2 - k1) 194 list {d(k1), d(k1+1),..., d(k2-1)}. (Note that the hash calculation 195 for leaves and nodes differ. This domain separation is required to 196 give second preimage resistance.) 198 Note that we do not require the length of the input list to be a 199 power of two. The resulting Merkle tree may thus not be balanced, 200 however, its shape is uniquely determined by the number of leaves. 201 [This Merkle tree is essentially the same as the history tree 202 [CrosbyWallach] proposal, except our definition handles non-full 203 trees differently.] 205 2.1.1. Merkle audit paths 207 A Merkle audit path for a leaf in a Merkle hash tree is the shortest 208 list of additional nodes in the Merkle tree required to compute the 209 Merkle Tree Hash for that tree. Each node in the tree is either a 210 leaf node, or is computed from the two nodes immediately below it 211 (i.e. towards the leaves). At each step up the tree (towards the 212 root), a node from the audit path is combined with the node computed 213 so far. In other words, the audit path consists of the list of 214 missing nodes required to compute the nodes leading from a leaf to 215 the root of the tree. If the root computed from the audit path 216 matches the true root, then the audit path is proof that the leaf 217 exists in the tree. 219 Given an ordered list of n inputs to the tree, D[n] = {d(0), ..., 220 d(n-1)}, the Merkle audit path PATH(m, D[n]) for the (m+1)th input 221 d(m), 0 <= m < n, is defined as follows: 223 The path for the single leaf in a tree with a one-element input list 224 D[1] = {d(0)} is empty: 226 PATH(0, {d(0)}) = {} 228 For n > 1, let k be the largest power of two smaller than n. The 229 path for the (m+1)th element d(m) in a list of n > m elements is then 230 defined recursively as 232 PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and 234 PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k, 236 where : is concatenation of lists and D[k1:k2] denotes the length (k2 237 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 239 2.1.2. Merkle consistency proofs 241 Merkle consistency proofs prove the append-only property of the tree. 242 A Merkle consistency proof for a Merkle Tree Hash MTH(D[n]) and a 243 previously advertised hash MTH(D[0:m]) of the first m leaves, m <= n, 244 is the list of nodes in the Merkle tree required to verify that the 245 first m inputs D[0:m] are equal in both trees. Thus, a consistency 246 proof must contain a set of intermediate nodes (i.e., commitments to 247 inputs) sufficient to verify MTH(D[n]), such that (a subset of) the 248 same nodes can be used to verify MTH(D[0:m]). We define an algorithm 249 that outputs the (unique) minimal consistency proof. 251 Given an ordered list of n inputs to the tree, D[n] = {d(0), ..., 252 d(n-1)}, the Merkle consistency proof PROOF(m, D[n]) for a previous 253 Merkle Tree Hash MTH(D[0:m]), 0 < m < n, is defined as: 255 PROOF(m, D[n]) = SUBPROOF(m, D[n], true) 257 The subproof for m = n is empty if m is the value for which PROOF was 258 originally requested (meaning that the subtree Merkle Tree Hash 259 MTH(D[0:m]) is known): 261 SUBPROOF(m, D[m], true) = {} 263 The subproof for m = n is the Merkle Tree Hash committing inputs 264 D[0:m] otherwise: 266 SUBPROOF(m, D[m], false) = {MTH(D[m])} 268 For m < n, let k be the largest power of two smaller than n. The 269 subproof is then defined recursively. 271 If m <= k, the right subtree entries D[k:n] only exist in the current 272 tree. We prove that the left subtree entries D[0:k] are consistent 273 and add a commitment to D[k:n]: 275 SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n]). 277 If m > k, the left subtree entries D[0:k] are identical in both 278 trees. We prove that the right subtree entries D[k:n] are consistent 279 and add a commitment to D[0:k]. 281 SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k]). 283 Here : is concatenation of lists and D[k1:k2] denotes the length (k2 284 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 286 The number of nodes in the resulting proof is bounded above by 287 ceil(log2(n)) + 1. 289 2.1.3. Example 291 The binary Merkle tree with 7 leaves: 293 hash 294 / \ 295 / \ 296 / \ 297 / \ 298 / \ 299 k l 300 / \ / \ 301 / \ / \ 302 / \ / \ 303 g h i j 304 / \ / \ / \ | 305 a b c d e f d6 306 | | | | | | 307 d0 d1 d2 d3 d4 d5 308 The audit path for d0 is [b, h, l]. 310 The audit path for d3 is [c, g, l]. 312 The audit path for d4 is [f, j, k]. 314 The audit path for d6 is [i, k]. 316 The same tree, built incrementally in four steps: 318 hash0 hash1=k 319 / \ / \ 320 / \ / \ 321 / \ / \ 322 g c g h 323 / \ | / \ / \ 324 a b d2 a b c d 325 | | | | | | 326 d0 d1 d0 d1 d2 d3 328 hash2 hash 329 / \ / \ 330 / \ / \ 331 / \ / \ 332 / \ / \ 333 / \ / \ 334 k i k l 335 / \ / \ / \ / \ 336 / \ e f / \ / \ 337 / \ | | / \ / \ 338 g h d4 d5 g h i j 339 / \ / \ / \ / \ / \ | 340 a b c d a b c d e f d6 341 | | | | | | | | | | 342 d0 d1 d2 d3 d0 d1 d2 d3 d4 d5 344 The consistency proof between hash0 and hash is PROOF(3, D[7]) = [c, 345 d, g, l]. c, g are used to verify hash0, and d, l are additionally 346 used to show hash is consistent with hash0. 348 The consistency proof between hash1 and hash is PROOF(4, D[7]) = [l]. 349 hash can be verified, using hash1=k and l. 351 The consistency proof between hash2 and hash is PROOF(6, D[7]) = [i, 352 j, k]. k, i are used to verify hash2, and j is additionally used to 353 show hash is consistent with hash2. 355 2.1.4. Signatures 357 Various data structures are signed. A log MUST use either elliptic 358 curve signatures using the NIST P-256 curve (section D.1.2.3 of DSS 359 [DSS]) or RSA signatures (RSASSA-PKCS1-V1_5 with SHA-256, section 8.2 360 of [RFC3447]) using a key of at least 2048 bits. 362 3. Log Format and Operation 364 Anyone can submit certificates to certificate logs for public 365 auditing, however, since certificates will not be accepted by TLS 366 clients unless logged, it is expected that certificate owners or 367 their CAs will usually submit them. A log is a single, ever-growing, 368 append-only Merkle Tree of such certificates. 370 When a valid certificate is submitted to a log, the log MUST 371 immediately return a Signed Certificate Timestamp (SCT). The SCT is 372 the log's promise to incorporate the certificate in the Merkle Tree 373 within a fixed amount of time known as the Maximum Merge Delay (MMD). 374 If the log has previously seen the certificate, it MAY return the 375 same SCT as it returned before. TLS servers MUST present an SCT from 376 one or more logs to the TLS client together with the certificate. 377 TLS clients MUST reject certificates that do not have a valid SCT for 378 the end-entity certificate. 380 Periodically, each log appends all its new entries to the Merkle 381 Tree, and signs the root of the tree. Auditors can thus verify that 382 each certificate for which an SCT has been issued indeed appears in 383 the log. The log MUST incorporate a certificate in its Merkle Tree 384 within the Maximum Merge Delay period after the issuance of the SCT. 386 Log operators MUST NOT impose any conditions on retrieving or sharing 387 data from the log. 389 3.1. Log Entries 391 Anyone can submit a certificate to any log. In order to enable 392 attribution of each logged certificate to its issuer, the log SHALL 393 publish a list of acceptable root certificates (this list might 394 usefully be the union of root certificates trusted by major browser 395 vendors). Each submitted certificate MUST be accompanied by all 396 additional certificates required to verify the certificate chain up 397 to an accepted root certificate. The root certificate itself MAY be 398 omitted from this list. 400 Alternatively, (root as well as intermediate) Certificate Authorities 401 may submit a certificate to logs prior to issuance. To do so, a 402 Certificate Authority constructs a Precertificate by adding a special 403 critical poison extension (OID 1.3.6.1.4.1.11129.2.4.3, whose 404 extnValue OCTET STRING contains ASN.1 NULL data (0x05 0x00)) to the 405 end entity TBSCertificate (this extension is to ensure that the 406 Precertificate cannot be validated by a standard X.509v3 client), and 407 signing the resulting TBSCertificate [RFC5280] with either 408 o a special-purpose (Extended Key Usage: Certificate Transparency, 409 OID 1.3.6.1.4.1.11129.2.4.4) Precertificate Signing Certificate. 410 The Precertificate Signing Certificate MUST be certified by the CA 411 certificate that will ultimately sign the end entity 412 TBSCertificate yielding the end entity certificate (note that the 413 log may relax standard validation rules to allow this, so long as 414 the issued certificate will be valid), 416 o or, the CA certificate that will sign the final certificate. 418 As above, the Precertificate submission MUST be accompanied by the 419 Precertificate Signing Certificate, if used, and all additional 420 certificates required to verify the chain up to an accepted root 421 certificate. The signature on the TBSCertificate indicates the 422 Certificate Authority's intent to issue a certificate. This intent 423 is considered binding (i.e., misissuance of the Precertificate is 424 considered equal to misissuance of the final certificate). Each log 425 verifies the Precertificate signature chain, and issues a Signed 426 Certificate Timestamp on the corresponding TBSCertificate. 428 Logs MUST verify that the submitted end entity certificate or 429 Precertificate has a valid signature chain leading back to a trusted 430 root CA certificate, using the chain of intermediate CA certificates 431 provided by the submitter. In case of Precertificates, each log MUST 432 also verify that the Precertificate Signing Certificate has the 433 correct Extended Key Usage extension. Logs MAY accept certificates 434 that have expired, are not yet valid, have been revoked or are 435 otherwise not fully valid according to X.509 verification rules in 436 order to accomodate quirks of CA certificate issuing software. 437 However, logs MUST refuse to publish certificates without a valid 438 chain to a known root CA. If a certificate is accepted and an SCT 439 issued, the accepting log MUST store the chain used for verification 440 including the certificate or Precertificate itself, and MUST present 441 this chain for auditing upon request. This chain is required to 442 prevent a CA avoiding blame by logging a partial or empty chain 443 [Note: this effectively excludes self-signed and DANE-based 444 certificates until some mechanism to control spam for those 445 certificates is found - the authors welcome suggestions]. 447 Each certificate entry in a log MUST include the following 448 components: 450 enum { x509_entry(0), precert_entry(1), (65535) } LogEntryType; 452 struct { 453 LogEntryType entry_type; 454 select (entry_type) { 455 case x509_entry: X509ChainEntry; 456 case precert_entry: PrecertChainEntry; 457 } entry; 458 } LogEntry; 460 opaque ASN.1Cert<1..2^24-1>; 462 struct { 463 ASN.1Cert leaf_certificate; 464 ASN.1Cert certificate_chain<0..2^24-1>; 465 } X509ChainEntry; 467 struct { 468 ASN.1Cert pre_certificate; 469 ASN.1Cert precertificate_chain<0..2^24-1>; 470 } PrecertChainEntry; 472 Logs MAY limit the length of chain they will accept. 474 "entry_type" is the type of this entry. Future revisions of this 475 protocol version may add new LogEntryType values. Section 4 explains 476 how clients should handle unknown entry types. 478 "leaf_certificate" is the end-entity certificate submitted for 479 auditing. 481 "certificate_chain" is a chain of additional certificates required to 482 verify the end entity certificate. The first certificate MUST 483 certify the end entity certificate. Each following certificate MUST 484 directly certify the one preceding it. The self-signed root 485 certificate MAY be omitted from the chain. 487 "pre_certificate" is the Precertificate submmited for auditing. 489 "precertificate_chain" is a chain of additional certificates required 490 to verify the Precertificate submission. The first certificate MAY 491 be a valid Precertificate Signing Certificate, and MUST certify the 492 first certificate. Each following certificate MUST directly certify 493 the one preceding it. The self-signed root certificate MAY be 494 omitted from the chain. 496 3.2. Structure of the Signed Certificate Timestamp 498 enum { certificate_timestamp(0), tree_hash(1), 255 } 499 SignatureType; 501 enum { v1(0), 255 } 502 Version; 504 struct { 505 opaque key_id[32]; 506 } LogID; 508 opaque TBSCertificate<1..2^16-1> 510 struct { 511 opaque issuer_key_hash[32]; 512 TBSCertificate tbs_certificate; 513 } PreCert; 515 opaque CtExtensions<0..2^16-1>; 517 "key_id" is the SHA-256 hash of the log's public key, calculated over 518 the DER encoding of the key represented as SubjectPublicKeyInfo. 520 "issuer_key_hash" is the SHA-256 hash of the certificate issuer's 521 public key, calculated over the DER encoding of the key represented 522 as SubjectPublicKeyInfo. This is needed to bind the issuer to the 523 final certificate. 525 "tbs_certificate" is the DER encoded TBSCertificate (see [RFC5280]) 526 component of the Precertificate - that is, without the signature and 527 the poison extension. If the Precertificate is not signed with the 528 CA certificate that will issue the final certificate, then the 529 TBSCertificate also has its issuer changed to that of the CA that 530 will issue the final certificate. Note that it is also possible to 531 reconstruct this TBSCertificate from the final certificate by 532 extracting the TBSCertificate from it and deleting the SCT extension. 533 Also note that since the TBSCertificate contains an 534 AlgorithmIdentifier that must match both the pre-certificate 535 signature algorithm and final certificate signature algorithm, they 536 must be signed with the same algorithm and parameters. 538 struct { 539 Version sct_version; 540 LogID id; 541 uint64 timestamp; 542 CtExtensions extensions; 543 digitally-signed struct { 544 Version sct_version; 545 SignatureType signature_type = certificate_timestamp; 546 uint64 timestamp; 547 LogEntryType entry_type; 548 select(entry_type) { 549 case x509_entry: ASN.1Cert; 550 case precert_entry: PreCert; 551 } signed_entry; 552 CtExtensions extensions; 553 }; 554 } SignedCertificateTimestamp; 556 The encoding of the digitally-signed element is defined in [RFC5246]. 558 "sct_version" is the version of the protocol the SCT conforms to. 559 This version is v1. 561 "timestamp" is the current NTP Time [RFC5905], measured since the 562 epoch (January 1, 1970, 00:00), ignoring leap seconds, in 563 milliseconds. 565 "entry_type" may be implicit from the context in which the SCT is 566 presented. 568 "signed_entry" is the "leaf_certificate" (in case of an 569 X509ChainEntry), or is the PreCert (in case of a PrecertChainEntry), 570 as described above. 572 "extensions" are future extensions to this protocol version (v1). 573 Currently, no extensions are specified. 575 3.3. Including the Signed Certificate Timestamp in the TLS Handshake 577 The SCT data corresponding to the end entity certificate from at 578 least one log must be included in the TLS handshake, either by using 579 an X509v3 certificate extension as described below, by using a TLS 580 Extension (section 7.4.1.4 of [RFC5246]) with type [TBD], or by using 581 OCSP Stapling (section 8 of [RFC6066]), where the response includes 582 an OCSP extension with OID 1.3.6.1.4.1.11129.2.4.5 (see [RFC2560]) 583 and body: 585 SignedCertificateTimestampList ::= OCTET STRING 587 At least one SCT MUST be included. Server operators MAY include more 588 than one SCT. 590 Similarly, a Certificate Authority MAY submit a precertificate to 591 more than one log, and all obtained SCTs can be directly embedded in 592 the final certificate, by encoding the SignedCertificateTimestampList 593 structure as an ASN.1 OCTET STRING and inserting the resulting data 594 in the TBSCertificate as an X.509v3 certificate extension (OID 595 1.3.6.1.4.1.11129.2.4.2). Upon receiving the certificate, clients 596 can reconstruct the original TBSCertificate to verify the SCT 597 signature. 599 The contents of the ASN.1 OCTET STRING embedded in an OCSP extension 600 or X509v3 certificate extension are as follows: 602 opaque SerializedSCT<1..2^16-1>; 604 struct { 605 SerializedSCT sct_list <1..2^16-1>; 606 } SignedCertificateTimestampList; 608 Here "SerializedSCT" is an opaque bytestring that contains the 609 serialized TLS structure. This encoding ensures that TLS clients can 610 decode each SCT individually (i.e., if there is a version upgrade, 611 out of date clients can still parse old SCTs while skipping over new 612 SCTs whose version they don't understand). 614 Likewise, SCTs can be embedded in a TLS Extension. See below for 615 details. 617 TLS clients MUST implement all three mechanisms. Servers MUST 618 implement at least one of the three mechanisms. Note that existing 619 TLS servers can generally use the certificate extension mechanism 620 without modification. 622 TLS servers should send SCTs from multiple logs in case one or more 623 logs is not acceptable to the client (for example, if a log has been 624 struck off for misbehaviour or has had a key compromise). 626 3.3.1. TLS Extension 628 The SCT can be sent during the TLS handshake using a TLS extension, 629 type [TBD]. 631 Clients that support the extension SHOULD send a ClientHello 632 extension with the appropriate type and empty "extension_data". 634 Servers MUST only send SCTs to clients who have indicated support for 635 the extension in the ClientHello, in which case the SCTs are sent by 636 setting the "extension_data" to a "SignedCertificateTimestampList". 638 Session resumption uses the original session information: clients 639 SHOULD include the extension type in the ClientHello but if the 640 session is resumed, the server is not expected to process it or 641 include the extension in the ServerHello. 643 3.4. Merkle Tree 645 The hashing algorithm for the Merkle Tree Hash is SHA-256. 647 Structure of the Merkle Tree input: 649 enum { timestamped_entry(0), 255 } 650 MerkleLeafType; 652 struct { 653 uint64 timestamp; 654 LogEntryType entry_type; 655 select(entry_type) { 656 case x509_entry: ASN.1Cert; 657 case precert_entry: TBSCertificate; 658 } signed_entry; 659 CtExtensions extensions; 660 } TimestampedEntry; 662 struct { 663 Version version; 664 MerkleLeafType leaf_type; 665 select (leaf_type) { 666 case timestamped_entry: TimestampedEntry; 667 } 668 } MerkleTreeLeaf; 670 Here "version" is the version of the protocol the MerkleTreeLeaf 671 corresponds to. This version is v1. 673 "leaf_type" is the type of the leaf input. Currently, only 674 "timestamped_entry" (corresponding to an SCT) is defined. Future 675 revisions of this protocol version may add new MerkleLeafType types. 676 Section 4 explains how clients should handle unknown leaf types. 678 "timestamp" is the timestamp of the corresponding SCT issued for this 679 certificate. 681 "signed_entry" is the "signed_entry" of the corresponding SCT. 683 "extensions" are "extensions" of the corresponding SCT. 685 The leaves of the Merkle Tree are the leaf hashes of the 686 corresponding "MerkleTreeLeaf" structures. 688 3.5. Signed Tree Head 690 Every time a log appends new entries to the tree, the log SHOULD sign 691 the corresponding tree hash and tree information (see the 692 corresponding Signed Tree Head client message in Section 4.3). The 693 signature for that data is structured as follows: 695 digitally-signed struct { 696 Version version; 697 SignatureType signature_type = tree_hash; 698 uint64 timestamp; 699 uint64 tree_size; 700 opaque sha256_root_hash[32]; 701 } TreeHeadSignature; 703 "version" is the version of the protocol the TreeHeadSignature 704 conforms to. This version is v1. 706 "timestamp" is the current time. The timestamp MUST be at least as 707 recent as the most recent SCT timestamp in the tree. Each subsequent 708 timestamp MUST be more recent than the timestamp of the previous 709 update. 711 "tree_size" equals the number of entries in the new tree. 713 "sha256_root_hash" is the root of the Merkle Hash Tree. 715 Each log MUST produce on demand a Signed Tree Head that is no older 716 than the Maximum Merge Delay. In the unlikely event that it receives 717 no new submissions during an MMD period, the log SHALL sign the same 718 Merkle Tree Hash with a fresh timestamp. 720 4. Log Client Messages 722 Messages are sent as HTTPS GET or POST requests. Parameters for 723 POSTs and all responses are encoded as JSON objects [RFC4627]. 724 Parameters for GETs are encoded as order independent key/value URL 725 parameters, using the "application/x-www-form-urlencoded" format 726 described in the "HTML 4.01 Specification" [HTML401]. Binary data is 727 base64 encoded [RFC4648] as specified in the individual messages. 729 The prefix can include a path as well as a server name 730 and a port. 732 In general, where needed, the "version" is v1 and the "id" is the log 733 id for the log server queried. 735 Any errors will be returned as HTTP 4xx or 5xx responses, with human 736 readable error messages. 738 4.1. Add Chain to Log 740 POST https:///ct/v1/add-chain 742 Inputs 744 chain An array of base64 encoded certificates. The first element is 745 the end entity certificate, the second chains to the first and so 746 on to the last, which is either the root certificate or a 747 certificate that chains to a known root certificate. 749 Outputs 751 sct_version The version of the SignedCertificateTimestamp structure, 752 in decimal. A compliant v1 implementation MUST NOT expect this to 753 be 0 (i.e. v1). 755 id The log ID, base64 encoded. Since log clients who request an SCT 756 for inclusion in TLS handshakes are not required to verify it, we 757 do not assume they know the ID of the log. 759 timestamp The SCT timestamp, in decimal. 761 extensions An opaque type for future expansion. It is likely that 762 not all participants will need to understand data in this field. 763 Logs should set this to the empty string. Clients should decode 764 the base64 encoded data and include it in the SCT. 766 signature The SCT signature, base64 encoded. 768 If the "sct_version" is not v1, then a v1 client may be unable to 769 verify the signature. It MUST NOT construe this as an error. [Note: 770 log clients don't need to be able to verify this structure, only TLS 771 clients do - if we were to serve the structure binary, then we could 772 completely change it without requiring an upgrade to v1 clients]. 774 4.2. Add PreCertChain to Log 776 POST https:///ct/v1/add-pre-chain 778 Inputs 780 chain An array of base64 encoded precertificates. The first element 781 is the end entity certificate, the second chains to the first and 782 so on to the last, which is either the root certificate or a 783 certificate that chains to a known root certificate. 785 Outputs are the same as Section 4.1. 787 4.3. Retrieve Latest Signed Tree Head 789 GET https:///ct/v1/get-sth 791 No inputs. 793 Outputs 795 tree_size The size of the tree, in entries, in decimal. 797 timestamp The timestamp, in decimal. 799 sha256_root_hash The Merkle Tree Hash of the tree, in base64. 801 tree_head_signature A TreeHeadSignature for the above data. 803 4.4. Retrieve Merkle Consistency Proof between two Signed Tree Heads 805 GET https:///ct/v1/get-sth-consistency 807 Inputs 809 first The tree_size of the first tree, in decimal. 811 second The tree_size of the second tree, in decimal. 813 Both tree sizes must be from existing v1 STHs (Signed Tree Heads). 815 Outputs 817 consistency An array of Merkle tree nodes, base64 encoded. 819 Note that no signature is required on this data, as it is used to 820 verify an STH, which is signed. 822 4.5. Retrieve Merkle Audit Proof from Log by Leaf Hash 824 GET https:///ct/v1/get-proof-by-hash 826 Inputs 828 hash A base64 encoded v1 leaf hash. 830 tree_size The tree_size of the tree to base the proof on, in 831 decimal. 833 The "hash" must be calculated as defined in Section 3.4. The 834 "tree_size" must designate an existing v1 STH. 836 Outputs 838 leaf_index The 0-based index of the end entity corresponding to the 839 "hash" parameter. 841 audit_path An array of base64 encoded Merkle tree nodes proving the 842 inclusion of the chosen certificate. 844 4.6. Retrieve Entries from Log 846 GET https:///ct/v1/get-entries 848 Inputs 850 start 0-based index of first entry to retrieve, in decimal. 852 end 0-based index of last entry to retrieve, in decimal. 854 Outputs 855 entries An array of objects, each consisting of 857 leaf_input The base64-encoded MerkleTreeLeaf structure. 859 extra_data The base64-encoded unsigned data pertaining to the log 860 entry. In the case of an X509ChainEntry, this is the 861 "certificate_chain". In the case of a PrecertChainEntry, this 862 is the "precertificate_chain". 864 Note that this message is not signed - the retrieved data can be 865 verified by constructing the Merkle Tree Hash corresponding to a 866 retrieved STH. All leaves MUST be v1. However, a compliant v1 867 client MUST NOT construe an unrecognized MerkleLeafType or 868 LogEntryType value as an error. This means it may be unable to parse 869 some entries, but note that each client can inspect the entries it 870 does recognize, as well as verify the integrity of the data by 871 treating unrecognized leaves as opaque input to the tree. 873 The "start" and "end" parameters SHOULD be within the range 0 <= x < 874 "tree_size" as returned by "get-sth" in Section 4.3. 876 Logs MAY honour requests where 0 <= "start" < "tree_size", and "end" 877 >= "tree_size" by returning a partial response convering only the 878 valid entries in the specified range. Note that the following 879 restriction may also apply: 881 Logs MAY restrict the number of entries which can be retrieved per 882 "get-entries" request. If a client requests more than the permitted 883 number of entries, the log SHALL return the maximum number of entries 884 permissible. These entries SHALL be sequential beginning with the 885 entry specified by "start". 887 4.7. Retrieve Accepted Root Certificates 889 Outputs 891 certificates An array of base64 encoded root certificates that are 892 acceptable to the log. 894 4.8. Retrieve Entry+Merkle Audit Proof from Log 896 GET https:///ct/v1/get-entry-and-proof 898 Inputs 899 leaf_index The index of the desired entry. 901 tree_size The tree_size of the tree for which the proof is desired. 903 The tree size must designate an existing STH. 905 Outputs 907 leaf_input The base64-encoded MerkleTreeLeaf structure. 909 extra_data The base64-encoded unsigned data, same as in Section 4.6. 911 audit_path An array of base64 encoded Merkle tree nodes proving the 912 inclusion of the chosen certificate. 914 This API is probably only useful for debugging. 916 5. Clients 918 There are various different functions clients of logs might perform. 919 We describe here some typical clients and how they could function. 920 Any inconsistency may be used as evidence that a log has not behaved 921 correctly, and the signatures on the data structures prevent the log 922 from denying that misbehaviour. 924 All clients should gossip with each other, exchanging STHs at least: 925 this is all that is required to ensure that they all have a 926 consistent view. The exact mechanism for gossip will be described in 927 an separate document, but it is expected there will be a variety. 929 5.1. Submitters 931 Submitters submit certificates or precertificates to the log as 932 described above. They may go on to use the returned SCT to construct 933 a certificate or use it directly in a TLS handshake. 935 5.2. TLS Client 937 TLS clients are not directly clients of the log, but they receive 938 SCTs alongside or in server certificates. In addition to normal 939 validation of the certificate and its chain, they should validate the 940 SCT by computing the signature input from the SCT data as well as the 941 certificate, and verifying the signature, using the corresponding 942 log's public key. Note that this document does not describe how 943 clients obtain the logs' public keys. 945 TLS clients MUST reject SCTs whose timestamp is in the future. 947 5.3. Monitor 949 Monitors watch logs and check that they behave correctly. They also 950 watch for certificates of interest. 952 A monitor needs to, at least, inspect every new entry in each log it 953 watches. It may also want to keep copies of entire logs. In order 954 to do this, it should follow these steps for each log: 956 1. Fetch the current STH using Section 4.3. 958 2. Verify the STH signature. 960 3. Fetch all the entries in the tree corresponding to the STH using 961 Section 4.6. 963 4. Confirm that the tree made from the fetched entries produces the 964 same hash as that in the STH. 966 5. Fetch the current STH using Section 4.3. Repeat until STH 967 changes. 969 6. Verify the STH signature. 971 7. Fetch all the new entries in the tree corresponding to the STH 972 using Section 4.6. If they remain unavailable for an extended 973 period, then this should be viewed as misbehaviour on the part of 974 the log. 976 8. Either: 978 1. Verify that the updated list of all entries generates a tree 979 with the same hash as the new STH. 981 Or, if it is not keeping all log entries: 983 2. Fetch a consistency proof for the new STH with the previous 984 STH using Section 4.4. 986 3. Verify the consistency proof. 988 4. Verify that the new entries generate the corresponding 989 elements in the consistency proof. 991 9. Go to Step 5. 993 5.4. Auditor 995 Auditors take partial information about a log as input and verify 996 that this information is consistent with other partial information 997 they have. An auditor might be an integral component of a TLS 998 client, it might be a standalone service or it might be a secondary 999 function of a monitor. 1001 Any pair of STHs from the same log can be verified by requesting a 1002 consistency proof using Section 4.4. 1004 A certificate accompanied by an SCT can be verified against any STH 1005 dated after the SCT timestamp + the Maximum Merge Delay by requesting 1006 a Merkle Audit Proof using Section 4.5. 1008 Auditors can fetch STHs from time to time of their own accord, of 1009 course, using Section 4.3. 1011 6. IANA Considerations 1013 IANA is requested to allocate an RFC 5246 ExtensionType Value for the 1014 CTS TLS extension. The Extension name is 1015 "signed_certificate_timestamp". 1017 7. Security Considerations 1019 7.1. Misissued Certificates 1021 Misissued certificates that have not been publicly logged, and thus 1022 do not have a valid SCT, will be rejected by TLS clients. Misissued 1023 certificates that do have an SCT from a log will appear in that 1024 public log within the Maximum Merge Delay, assuming the log is 1025 operating correctly. Thus, the maximum period of time during which a 1026 misissued certificate can be used without being available for audit 1027 is the MMD. 1029 7.2. Detection of Misissue 1031 The logs do not themselves detect misissued certificates, they rely 1032 instead on interested parties, such as domain owners, to monitor them 1033 and take corrective action when a misissue is detected. 1035 7.3. Misbehaving logs 1037 A log can misbehave in two ways: (1), by failing to incorporate a 1038 certificate with an SCT in the Merkle Tree within the MMD; and (2), 1039 by violating its append-only property by presenting two different, 1040 conflicting views of the Merkle Tree at different times and/or to 1041 different parties. Both forms of violation will be promptly and 1042 publicly detectable. 1044 Violation of the MMD contract is detected by log clients requesting a 1045 Merkle audit proof for each observed SCT. These checks can be 1046 asynchronous, and need only be done once per each certificate. In 1047 order to protect the clients' privacy, these checks need not reveal 1048 the exact certificate to the log. Clients can instead request the 1049 proof from a trusted auditor (since anyone can compute the audit 1050 proofs from the log), or request Merkle proofs for a batch of 1051 certificates around the SCT timestamp. 1053 Violation of the append-only property is detected by global 1054 gossiping, i.e., everyone auditing logs comparing their versions of 1055 the latest signed tree heads. As soon as two conflicting signed tree 1056 heads for the same log are detected, this is cryptographic proof of 1057 that log's misbehaviour. 1059 8. Efficiency Considerations 1061 The Merkle tree design serves the purpose of keeping communication 1062 overhead low. 1064 Auditing logs for integrity does not require third parties to 1065 maintain a copy of each entire log. The Signed Tree Heads can be 1066 updated as new entries become available, without recomputing entire 1067 trees. Third party auditors need only fetch the Merkle consistency 1068 proofs against a log's existing STH to efficiently verify the append- 1069 only property of updates to their Merkle Trees, without auditing the 1070 entire tree. 1072 9. Future Changes 1074 This section lists things we might address in a Standards Track 1075 version of this document. 1077 Rather than forcing a log operator to create a new log in order to 1078 change the log signing key, we may allow some key roll mechanism. 1080 We may add hash and signing algorithm agility. 1082 We may describe some gossip protocols. 1084 10. References 1086 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1087 Requirement Levels", BCP 14, RFC 2119, March 1997. 1089 [RFC2560] Myers, M., Ankney, R., Malpani, A., Galperin, S., and C. 1090 Adams, "X.509 Internet Public Key Infrastructure Online 1091 Certificate Status Protocol - OCSP", RFC 2560, June 1999. 1093 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 1094 Standards (PKCS) #1: RSA Cryptography Specifications 1095 Version 2.1", RFC 3447, February 2003. 1097 [RFC4627] Crockford, D., "The application/json Media Type for 1098 JavaScript Object Notation (JSON)", RFC 4627, July 2006. 1100 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 1101 Encodings", RFC 4648, October 2006. 1103 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 1104 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 1106 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 1107 Housley, R., and W. Polk, "Internet X.509 Public Key 1108 Infrastructure Certificate and Certificate Revocation List 1109 (CRL) Profile", RFC 5280, May 2008. 1111 [RFC5905] Mills, D., Martin, J., Burbank, J., and W. Kasch, "Network 1112 Time Protocol Version 4: Protocol and Algorithms 1113 Specification", RFC 5905, June 2010. 1115 [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: 1116 Extension Definitions", RFC 6066, January 2011. 1118 [DSS] National Institute of Standards and Technology, U.S. 1119 Department of Commerce, "Digital Signature Standard", 1120 FIPS 186-3, June 2009. 1122 [CrosbyWallach] 1123 Crosby, S. and D. Wallach, "Efficient data structures for 1124 tamper-evident logging", 2009. 1126 [HTML401] Hors, A., Raggett, D., and I. Jacobs, "HTML 4.01 1127 Specification", World Wide Web Consortium 1128 Recommendation REC-html401-19991224, December 1999, 1129 . 1131 [FIPS.180-2.2002] 1132 National Institute of Standards and Technology, "Secure 1133 Hash Standard", FIPS PUB 180-2, August 2002, . 1136 Authors' Addresses 1138 Ben Laurie 1140 Email: benl@google.com 1142 Adam Langley 1144 Email: agl@google.com 1146 Emilia Kasper 1148 Email: ekasper@google.com