idnits 2.17.1 draft-laurie-pki-sunlight-06.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 4105 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 225 -- Looks like a reference, but probably isn't: '7' on line 352 -- Looks like a reference, but probably isn't: '32' on line 701 == Missing Reference: 'TBD' is mentioned on line 919, but not defined ** Obsolete normative reference: RFC 1305 (Obsoleted by RFC 5905) ** 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: 7 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-06 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 4.9. Examples . . . . . . . . . . . . . . . . . . . . . . . . . 23 86 5. Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 87 5.1. Submitters . . . . . . . . . . . . . . . . . . . . . . . . 24 88 5.2. TLS Client . . . . . . . . . . . . . . . . . . . . . . . . 24 89 5.3. Monitor . . . . . . . . . . . . . . . . . . . . . . . . . 24 90 5.4. Auditor . . . . . . . . . . . . . . . . . . . . . . . . . 25 91 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 92 7. Security Considerations . . . . . . . . . . . . . . . . . . . 27 93 7.1. Misissued Certificates . . . . . . . . . . . . . . . . . . 27 94 7.2. Detection of Misissue . . . . . . . . . . . . . . . . . . 27 95 7.3. Misbehaving logs . . . . . . . . . . . . . . . . . . . . . 27 96 8. Efficiency Considerations . . . . . . . . . . . . . . . . . . 28 97 9. Future Changes . . . . . . . . . . . . . . . . . . . . . . . . 29 98 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 99 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 101 1. Informal introduction 103 Certificate Transparency aims to mitigate the problem of misissued 104 certificates by providing publicly auditable, append-only, untrusted 105 logs of all issued certificates. The logs are publicly auditable so 106 that it is possible for anyone to verify the correctness of each log, 107 and to monitor when new certificates are added to it. The logs do 108 not themselves prevent misissue, but they ensure that interested 109 parties (particularly those named in certificates) can detect such 110 misissuance. Note that this is a general mechanism, but in this 111 document we only describe its use for public TLS server certificates 112 issued by public CAs. 114 Each log consists of certificate chains, which can be submitted by 115 anyone. It is expected that public CAs will contribute all their 116 newly-issued certificates to one or more logs; it is also expected 117 that certificate holders will contribute their own certificate 118 chains. In order to avoid logs being spammed into uselessness, it is 119 required that each chain is rooted in a known CA certificate. When a 120 chain is submitted to a log, a signed timestamp is returned, which 121 can later be used to provide evidence to clients that the chain has 122 been submitted. TLS clients can thus require that all certificates 123 they see have been logged. 125 Those who are concerned about misissue can monitor the logs, asking 126 them regularly for all new entries, and can thus check whether 127 domains they are responsible for have had certificates issued that 128 they did not expect. What they do with this information, 129 particularly when they find that a misissuance has happened, is 130 beyond the scope of this document, but broadly speaking they can 131 invoke existing business mechanisms for dealing with misissued 132 certificates. Of course, anyone who wants can monitor the logs, and 133 if they believe a certificate is incorrectly issued, take action as 134 they see fit. 136 Similarly, those who have seen signed timestamps from a particular 137 log can later demand a proof of inclusion from that log. If the log 138 is unable to provide this (or, indeed, if the corresponding 139 certificate is absent from monitors' copies of that log), that is 140 evidence of the incorrect operation of the log. The checking 141 operation is asynchronous to allow TLS connections to proceed without 142 delay, despite network connectivity issues and the vagaries of 143 firewalls. 145 The append-only property of each log is technically achieved using 146 Merkle Trees, which can be used to show that any particular version 147 of the log is a superset of any particular previous version. 148 Likewise, Merkle Trees avoid the need to blindly trust logs: if a log 149 attempts to show different things to different people, this can be 150 efficiently detected by comparing tree roots and consistency proofs. 151 Similarly, other misbehaviours of any log (e.g. issuing signed 152 timestamps for certificates they then don't log) can be efficiently 153 detected and proved to the world at large. 155 1.1. Requirements Language 157 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 158 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 159 document are to be interpreted as described in RFC 2119 [RFC2119]. 161 1.2. Data structures 163 Data structures are defined according to the conventions laid out in 164 section 4 of [RFC5246]. 166 2. Cryptographic components 168 2.1. Merkle Hash Trees 170 Logs use a binary Merkle hash tree for efficient auditing. The 171 hashing algorithm is SHA-256 [FIPS.180-2.2002] (note that this is 172 fixed for this experiment but it is anticipated that each log would 173 be able to specify a hash algorithm). The input to the Merkle Tree 174 Hash is a list of data entries; these entries will be hashed to form 175 the leaves of the Merkle hash tree. The output is a single 32-byte 176 Merkle Tree Hash. Given an ordered list of n inputs, D[n] = {d(0), 177 d(1), ..., d(n-1)}, the Merkle Tree Hash (MTH) is thus defined as 178 follows: 180 The hash of an empty list is the hash of an empty string: 182 MTH({}) = SHA-256(). 184 The hash of a list with one entry (also known as a leaf hash) is: 186 MTH({d(0)}) = SHA-256(0x00 || d(0)). 188 For n > 1, let k be the largest power of two smaller than n. The 189 Merkle Tree Hash of an n-element list D[n] is then defined 190 recursively as 192 MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])), 194 where || is concatenation and D[k1:k2] denotes the length (k2 - k1) 195 list {d(k1), d(k1+1),..., d(k2-1)}. (Note that the hash calculation 196 for leaves and nodes differ. This domain separation is required to 197 give second preimage resistance.) 199 Note that we do not require the length of the input list to be a 200 power of two. The resulting Merkle tree may thus not be balanced, 201 however, its shape is uniquely determined by the number of leaves. 202 [This Merkle tree is essentially the same as the history tree 203 [CrosbyWallach] proposal, except our definition handles non-full 204 trees differently.] 206 2.1.1. Merkle audit paths 208 A Merkle audit path for a leaf in a Merkle hash tree is the shortest 209 list of additional nodes in the Merkle tree required to compute the 210 Merkle Tree Hash for that tree. Each node in the tree is either a 211 leaf node, or is computed from the two nodes immediately below it 212 (i.e. towards the leaves). At each step up the tree (towards the 213 root), a node from the audit path is combined with the node computed 214 so far. In other words, the audit path consists of the list of 215 missing nodes required to compute the nodes leading from a leaf to 216 the root of the tree. If the root computed from the audit path 217 matches the true root, then the audit path is proof that the leaf 218 exists in the tree. 220 Given an ordered list of n inputs to the tree, D[n] = {d(0), ..., 221 d(n-1)}, the Merkle audit path PATH(m, D[n]) for the (m+1)th input 222 d(m), 0 <= m < n, is defined as follows: 224 The path for the single leaf in a tree with a one-element input list 225 D[1] = {d(0)} is empty: 227 PATH(0, {d(0)}) = {} 229 For n > 1, let k be the largest power of two smaller than n. The 230 path for the (m+1)th element d(m) in a list of n > m elements is then 231 defined recursively as 233 PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and 235 PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k, 237 where : is concatenation of lists and D[k1:k2] denotes the length (k2 238 - k1) list {d(k1), d(k1+1),..., d(k2-1)} as before. 240 2.1.2. Merkle consistency proofs 242 Merkle consistency proofs prove the append-only property of the tree. 243 A Merkle consistency proof for a Merkle Tree Hash MTH(D[n]) and a 244 previously advertised hash MTH(D[0:m]) of the first m leaves, m <= n, 245 is the list of nodes in the Merkle tree required to verify that the 246 first m inputs D[0:m] are equal in both trees. Thus, a consistency 247 proof must contain a set of intermediate nodes (i.e., commitments to 248 inputs) sufficient to verify MTH(D[n]), such that (a subset of) the 249 same nodes can be used to verify MTH(D[0:m]). We define an algorithm 250 that outputs the (unique) minimal consistency proof. 252 Given an ordered list of n inputs to the tree, D[n] = {d(0), ..., 253 d(n-1)}, the Merkle consistency proof PROOF(m, D[n]) for a previous 254 Merkle Tree Hash MTH(D[0:m]), 0 < m < n, is defined as: 256 PROOF(m, D[n]) = 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 Merkle Tree Hash 260 MTH(D[0:m]) is known): 262 SUBPROOF(m, D[m], true) = {} 264 The subproof for m = n is the Merkle Tree Hash committing inputs 265 D[0:m] 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 309 The audit path for d0 is [b, h, l]. 311 The audit path for d3 is [c, g, l]. 313 The audit path for d4 is [f, j, k]. 315 The audit path for d6 is [i, k]. 317 The same tree, built incrementally in four steps: 319 hash0 hash1=k 320 / \ / \ 321 / \ / \ 322 / \ / \ 323 g c g h 324 / \ | / \ / \ 325 a b d2 a b c d 326 | | | | | | 327 d0 d1 d0 d1 d2 d3 329 hash2 hash 330 / \ / \ 331 / \ / \ 332 / \ / \ 333 / \ / \ 334 / \ / \ 335 k i k l 336 / \ / \ / \ / \ 337 / \ e f / \ / \ 338 / \ | | / \ / \ 339 g h d4 d5 g h i j 340 / \ / \ / \ / \ / \ | 341 a b c d a b c d e f d6 342 | | | | | | | | | | 343 d0 d1 d2 d3 d0 d1 d2 d3 d4 d5 345 The consistency proof between hash0 and hash is PROOF(3, D[7]) = [c, 346 d, g, l]. c, g are used to verify hash0, and d, l are additionally 347 used to show hash is consistent with hash0. 349 The consistency proof between hash1 and hash is PROOF(4, D[7]) = [l]. 350 hash can be verified, using hash1=k and l. 352 The consistency proof between hash2 and hash is PROOF(6, D[7]) = [i, 353 j, k]. k, i are used to verify hash2, and j is additionally used to 354 show hash is consistent with hash2. 356 2.1.4. Signatures 358 Various data structures are signed. A log MUST use either elliptic 359 curve signatures using the NIST P-256 curve (section D.1.2.3 of DSS 360 [DSS]) or RSA signatures (RSASSA-PKCS1-V1_5 with SHA-256, section 8.2 361 of [RFC3447]) using a key of at least 2048 bits. 363 3. Log Format and Operation 365 Anyone can submit certificates to certificate logs for public 366 auditing, however, since certificates will not be accepted by TLS 367 clients unless logged, it is expected that certificate owners or 368 their CAs will usually submit them. A log is a single, ever-growing, 369 append-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 TLS client together with the certificate. 378 TLS clients MUST reject certificates that do not have a valid SCT for 379 the end-entity certificate. 381 Periodically, each log appends all its new entries to the Merkle 382 Tree, and signs the root of the tree. Auditors can thus verify that 383 each certificate for which an SCT has been issued indeed appears in 384 the log. The log MUST incorporate a certificate in its Merkle Tree 385 within the Maximum Merge Delay period after the issuance of the SCT. 387 Log operators MUST NOT impose any conditions on retrieving or sharing 388 data from the log. 390 3.1. Log Entries 392 Anyone can submit a certificate to any log. In order to enable 393 attribution of each logged certificate to its issuer, the log SHALL 394 publish a list of acceptable root certificates (this list might 395 usefully be the union of root certificates trusted by major browser 396 vendors). Each submitted certificate MUST be accompanied by all 397 additional certificates required to verify the certificate chain up 398 to an accepted root certificate. The root certificate itself MAY be 399 omitted from this list. 401 Alternatively, (root as well as intermediate) Certificate Authorities 402 may submit a certificate to logs prior to issuance. To do so, a 403 Certificate Authority constructs a Precertificate by adding a special 404 critical poison extension (OID 1.3.6.1.4.1.11129.2.4.3, whose 405 extnValue OCTET STRING contains ASN.1 NULL data (0x05 0x00)) to the 406 end entity TBSCertificate (this extension is to ensure that the 407 Precertificate cannot be validated by a standard X.509v3 client), and 408 signing the resulting TBSCertificate [RFC5280] with either 409 o a special-purpose (Extended Key Usage: Certificate Transparency, 410 OID 1.3.6.1.4.1.11129.2.4.4) Precertificate Signing Certificate. 411 The Precertificate Signing Certificate MUST be certified by the CA 412 certificate that will ultimately sign the end entity 413 TBSCertificate yielding the end entity certificate (note that the 414 log may relax standard validation rules to allow this, so long as 415 the issued 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 end entity 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 pre_certificate; 470 ASN.1Cert precertificate_chain<0..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 end entity certificate. The first certificate MUST 484 certify the end entity certificate. Each following certificate MUST 485 directly certify the one preceding it. The self-signed root 486 certificate MAY be omitted from the chain. 488 "pre_certificate" is the Precertificate submmited for auditing. 490 "precertificate_chain" is a chain of additional certificates required 491 to verify the Precertificate submission. The first certificate MAY 492 be a valid Precertificate Signing Certificate, and MUST certify the 493 first certificate. Each following certificate MUST directly certify 494 the one preceding it. The self-signed root certificate MAY be 495 omitted from the chain. 497 3.2. Structure of the Signed Certificate Timestamp 499 enum { certificate_timestamp(0), tree_hash(1), 255 } 500 SignatureType; 502 enum { v1(0), 255 } 503 Version; 505 struct { 506 opaque key_id[32]; 507 } LogID; 509 opaque TBSCertificate<1..2^16-1> 511 struct { 512 opaque issuer_key_hash[32]; 513 TBSCertificate tbs_certificate; 514 } PreCert; 516 opaque CtExtensions<0..2^16-1>; 518 "key_id" is the SHA-256 hash of the log's public key, calculated over 519 the DER encoding of the key represented as SubjectPublicKeyInfo. 521 "issuer_key_hash" is the SHA-256 hash of the certificate issuer's 522 public key, calculated over the DER encoding of the key represented 523 as SubjectPublicKeyInfo. This is needed to bind the issuer to the 524 final certificate. 526 "tbs_certificate" is the DER encoded TBSCertificate (see [RFC5280]) 527 component of the Precertificate - that is, without the signature and 528 the poison extension. If the Precertificate is not signed with the 529 CA certificate that will issue the final certificate, then the 530 TBSCertificate also has its issuer changed to that of the CA that 531 will issue the final certificate. Note that it is also possible to 532 reconstruct this TBSCertificate from the final certificate by 533 extracting the TBSCertificate from it and deleting the SCT extension. 534 Also note that since the TBSCertificate contains an 535 AlgorithmIdentifier that must match both the pre-certificate 536 signature algorithm and final certificate signature algorithm, they 537 must be signed with the same algorithm and parameters. 539 struct { 540 Version sct_version; 541 LogID id; 542 uint64 timestamp; 543 CtExtensions extensions; 544 digitally-signed struct { 545 Version sct_version; 546 SignatureType signature_type = certificate_timestamp; 547 uint64 timestamp; 548 LogEntryType entry_type; 549 select(entry_type) { 550 case x509_entry: ASN.1Cert; 551 case precert_entry: PreCert; 552 } signed_entry; 553 CtExtensions extensions; 554 }; 555 } SignedCertificateTimestamp; 557 The encoding of the digitally-signed element is defined in [RFC5246]. 559 "sct_version" is the version of the protocol the SCT conforms to. 560 This version is v1. 562 "timestamp" is the current NTP Time [RFC1305], measured since the 563 epoch (January 1, 1970, 00:00), ignoring leap seconds, in 564 milliseconds. 566 "entry_type" may be implicit from the context in which the SCT is 567 presented. 569 "signed_entry" is the "leaf_certificate" (in case of an 570 X509ChainEntry), or is the PreCert (in case of a PrecertChainEntry), 571 as described above. 573 "extensions" are future extensions to this protocol version (v1). 574 Currently, no extensions are specified. 576 3.3. Including the Signed Certificate Timestamp in the TLS Handshake 578 The SCT data corresponding to the end entity certificate from at 579 least one log must be included in the TLS handshake, either by using 580 an X509v3 certificate extension as described below, by using a TLS 581 Extension (section 7.4.1.4 of [RFC5246]) with type [TBD], or by using 582 OCSP Stapling (section 8 of [RFC6066]), where the response includes 583 an OCSP extension with OID 1.3.6.1.4.1.11129.2.4.5 (see [RFC2560]) 584 and body: 586 SignedCertificateTimestampList ::= OCTET STRING 588 At least one SCT MUST be included. Server operators MAY include more 589 than one SCT. 591 Similarly, a Certificate Authority MAY submit a precertificate to 592 more than one log, and all obtained SCTs can be directly embedded in 593 the final certificate, by encoding the SignedCertificateTimestampList 594 structure as an ASN.1 OCTET STRING and inserting the resulting data 595 in the TBSCertificate as an X.509v3 certificate extension (OID 596 1.3.6.1.4.1.11129.2.4.2). Upon receiving the certificate, clients 597 can reconstruct the original TBSCertificate to verify the SCT 598 signature [TBD: how?]. 600 The contents of the ASN.1 OCTET STRING embedded in an OCSP extension 601 or X509v3 certificate extension are as follows: 603 opaque SerializedSCT<1..2^16-1>; 605 struct { 606 SerializedSCT sct_list <1..2^16-1>; 607 } SignedCertificateTimestampList; 609 Here "SerializedSCT" is an opaque bytestring that contains the 610 serialized TLS structure. This encoding ensures that TLS clients can 611 decode each SCT individually (i.e., if there is a version upgrade, 612 out of date clients can still parse old SCTs while skipping over new 613 SCTs whose version they don't understand). 615 Likewise, SCTs can be embedded in a TLS Extension. See below for 616 details. 618 TLS clients MUST implement all three mechanisms. Servers MUST 619 implement at least one of the three mechanisms. Note that existing 620 TLS servers can generally use the certificate extension mechanism 621 without modification. 623 TLS servers should send SCTs from multiple logs in case one or more 624 logs is not acceptable to the client (for example, if a log has been 625 struck off for misbehaviour or has had a key compromise). 627 3.3.1. TLS Extension 629 The SCT can be sent during the TLS handshake using a TLS extension, 630 type [TBD]. 632 Clients that support the extension SHOULD send a ClientHello 633 extension with the appropriate type and empty "extension_data". 635 Servers MUST only send SCTs to clients who have indicated support for 636 the extension in the ClientHello, in which case the SCTs are sent by 637 setting the "extension_data" to a "SignedCertificateTimestampList". 639 Session resumption uses the original session information: clients 640 SHOULD include the extension type in the ClientHello but if the 641 session is resumed, the server is not expected to process it or 642 include the extension in the ServerHello. 644 3.4. Merkle Tree 646 The hashing algorithm for the Merkle Tree Hash is SHA-256. 648 Structure of the Merkle Tree input: 650 enum { timestamped_entry(0), 255 } 651 MerkleLeafType; 653 struct { 654 uint64 timestamp; 655 LogEntryType entry_type; 656 select(entry_type) { 657 case x509_entry: ASN.1Cert; 658 case precert_entry: TBSCertificate; 659 } signed_entry; 660 CtExtensions extensions; 661 } TimestampedEntry; 663 struct { 664 Version version; 665 MerkleLeafType leaf_type; 666 select (leaf_type) { 667 case timestamped_entry: TimestampedEntry; 668 } 669 } MerkleTreeLeaf; 671 Here "version" is the version of the protocol the MerkleTreeLeaf 672 corresponds to. This version is v1. 674 "leaf_type" is the type of the leaf input. Currently, only 675 "timestamped_entry" (corresponding to an SCT) is defined. Future 676 revisions of this protocol version may add new MerkleLeafType types. 677 Section 4 explains how clients should handle unknown leaf types. 679 "timestamp" is the timestamp of the corresponding SCT issued for this 680 certificate. 682 "signed_entry" is the "signed_entry" of the corresponding SCT. 684 "extensions" are "extensions" of the corresponding SCT. 686 The leaves of the Merkle Tree are the leaf hashes of the 687 corresponding "MerkleTreeLeaf" structures. 689 3.5. Signed Tree Head 691 Every time a log appends new entries to the tree, the log SHOULD sign 692 the corresponding tree hash and tree information (see the 693 corresponding Signed Tree Head client message in Section 4.3). The 694 signature for that data is structured as follows: 696 digitally-signed struct { 697 Version version; 698 SignatureType signature_type = tree_hash; 699 uint64 timestamp; 700 uint64 tree_size; 701 opaque sha256_root_hash[32]; 702 } TreeHeadSignature; 704 "version" is the version of the protocol the TreeHeadSignature 705 conforms to. This version is v1. 707 "timestamp" is the current time. The timestamp MUST be at least as 708 recent as the most recent SCT timestamp in the tree. Each subsequent 709 timestamp MUST be more recent than the timestamp of the previous 710 update. 712 "tree_size" equals the number of entries in the new tree. 714 "sha256_root_hash" is the root of the Merkle Hash Tree. 716 Each log MUST produce on demand a Signed Tree Head that is no older 717 than the Maximum Merge Delay. In the unlikely event that it receives 718 no new submissions during an MMD period, the log SHALL sign the same 719 Merkle Tree Hash with a fresh timestamp. 721 4. Log Client Messages 723 Messages are sent as HTTPS GET or POST requests. Parameters for 724 POSTs and all responses are encoded as JSON objects [RFC4627]. 725 Parameters for GETs are encoded as order independent key/value URL 726 parameters, using the "application/x-www-form-urlencoded" format 727 described in the "HTML 4.01 Specification" [HTML401]. Binary data is 728 base64 encoded [RFC4648] as specified in the individual messages. 730 The prefix can include a path as well as a server name 731 and a port. 733 In general, where needed, the "version" is v1 and the "id" is the log 734 id for the log server queried. 736 Any errors will be returned as HTTP 4xx or 5xx responses, with human 737 readable error messages. 739 4.1. Add Chain to Log 741 POST https:///ct/v1/add-chain 743 Inputs 745 chain An array of base64 encoded certificates. The first element is 746 the end entity certificate, the second chains to the first and so 747 on to the last, which is either the root certificate or a 748 certificate that chains to a known root certificate. 750 Outputs 752 sct_version The version of the SignedCertificateTimestamp structure, 753 in decimal. A compliant v1 implementation MUST NOT expect this to 754 be 0 (i.e. v1). 756 id The log ID, base64 encoded. Since log clients who request an SCT 757 for inclusion in TLS handshakes are not required to verify it, we 758 do not assume they know the ID of the log. 760 timestamp The SCT timestamp, in decimal. 762 extensions An opaque type for future expansion. It is likely that 763 not all participants will need to understand data in this field. 764 Logs should set this to the empty string. Clients should decode 765 the base64 encoded data and include it in the SCT. 767 signature The SCT signature, base64 encoded. 769 If the "sct_version" is not v1, then a v1 client may be unable to 770 verify the signature. It MUST NOT construe this as an error. [Note: 771 log clients don't need to be able to verify this structure, only TLS 772 clients do - if we were to serve the structure binary, then we could 773 completely change it without requiring an upgrade to v1 clients]. 775 4.2. Add PreCertChain to Log 777 POST https:///ct/v1/add-pre-chain 779 Inputs 781 chain An array of base64 encoded precertificates. The first element 782 is the end entity certificate, the second chains to the first and 783 so on to the last, which is either the root certificate or a 784 certificate that chains to a known root certificate. 786 Outputs are the same as Section 4.1. 788 4.3. Retrieve Latest Signed Tree Head 790 GET https:///ct/v1/get-sth 792 No inputs. 794 Outputs 796 tree_size The size of the tree, in entries, in decimal. 798 timestamp The timestamp, in decimal. 800 sha256_root_hash The Merkle Tree Hash of the tree, in base64. 802 tree_head_signature A TreeHeadSignature for the above data. 804 4.4. Retrieve Merkle Consistency Proof between two Signed Tree Heads 806 GET https:///ct/v1/get-sth-consistency 808 Inputs 810 first The tree_size of the first tree, in decimal. 812 second The tree_size of the second tree, in decimal. 814 Both tree sizes must be from existing v1 STHs (Signed Tree Heads). 816 Outputs 818 consistency An array of Merkle tree nodes, base64 encoded. 820 Note that no signature is required on this data, as it is used to 821 verify an STH, which is signed. 823 4.5. Retrieve Merkle Audit Proof from Log by Leaf Hash 825 GET https:///ct/v1/get-proof-by-hash 827 Inputs 829 hash A base64 encoded v1 leaf hash. 831 tree_size The tree_size of the tree to base the proof on, in 832 decimal. 834 The "hash" must be calculated as defined in Section 3.4. The 835 "tree_size" must designate an existing v1 STH. 837 Outputs 839 leaf_index The 0-based index of the end entity corresponding to the 840 "hash" parameter. 842 audit_path An array of base64 encoded Merkle tree nodes proving the 843 inclusion of the chosen certificate. 845 4.6. Retrieve Entries from Log 847 GET https:///ct/v1/get-entries 849 Inputs 851 start 0-based index of first entry to retrieve, in decimal. 853 end 0-based index of last entry to retrieve, in decimal. 855 Outputs 856 entries An array of objects, each consisting of 858 leaf_input The base64-encoded MerkleTreeLeaf structure. 860 extra_data The base64-encoded unsigned data pertaining to the log 861 entry. In the case of an X509ChainEntry, this is the 862 "certificate_chain". In the case of a PrecertChainEntry, this 863 is the "precertificate_chain". 865 Note that this message is not signed - the retrieved data can be 866 verified by constructing the Merkle Tree Hash corresponding to a 867 retrieved STH. All leaves MUST be v1. However, a compliant v1 868 client MUST NOT construe an unrecognized MerkleLeafType or 869 LogEntryType value as an error. This means it may be unable to parse 870 some entries, but note that each client can inspect the entries it 871 does recognize, as well as verify the integrity of the data by 872 treating unrecognized leaves as opaque input to the tree. 874 The "start" and "end" parameters SHOULD be within the range 0 <= x < 875 "tree_size" as returned by "get-sth" in Section 4.3. 877 Logs MAY honour requests where 0 <= "start" < "tree_size", and "end" 878 >= "tree_size" by returning a partial response convering only the 879 valid entries in the specified range. Note that the following 880 restriction may also apply: 882 Logs MAY restrict the number of entries which can be retrieved per 883 "get-entries" request. If a client requests more than the permitted 884 number of entries, the log SHALL return the maximum number of entries 885 permissible. These entries SHALL be sequential beginning with the 886 entry specified by "start". 888 4.7. Retrieve Accepted Root Certificates 890 Outputs 892 certificates An array of base64 encoded root certificates that are 893 acceptable to the log. 895 4.8. Retrieve Entry+Merkle Audit Proof from Log 897 GET https:///ct/v1/get-entry-and-proof 899 Inputs 900 leaf_index The index of the desired entry. 902 tree_size The tree_size of the tree for which the proof is desired. 904 The tree size must designate an existing STH. 906 Outputs 908 leaf_input The base64-encoded MerkleTreeLeaf structure. 910 extra_data The base64-encoded unsigned data, same as in Section 4.6. 912 audit_path An array of base64 encoded Merkle tree nodes proving the 913 inclusion of the chosen certificate. 915 This API is probably only useful for debugging. 917 4.9. Examples 919 [TBD] 921 5. Clients 923 There are various different functions clients of logs might perform. 924 We describe here some typical clients and how they could function. 925 Any inconsistency may be used as evidence that a log has not behaved 926 correctly, and the signatures on the data structures prevent the log 927 from denying that misbehaviour. 929 All clients should gossip with each other, exchanging STHs at least: 930 this is all that is required to ensure that they all have a 931 consistent view. The exact mechanism for gossip will be described in 932 an separate document, but it is expected there will be a variety. 934 5.1. Submitters 936 Submitters submit certificates or precertificates to the log as 937 described above. They may go on to use the returned SCT to construct 938 a certificate or use it directly in a TLS handshake. 940 5.2. TLS Client 942 TLS clients are not directly clients of the log, but they receive 943 SCTs alongside or in server certificates. In addition to normal 944 validation of the certificate and its chain, they should validate the 945 SCT by computing the signature input from the SCT data as well as the 946 certificate, and verifying the signature, using the corresponding 947 log's public key. Note that this document does not describe how 948 clients obtain the logs' public keys. 950 TLS clients MUST reject SCTs whose timestamp is in the future. 952 5.3. Monitor 954 Monitors watch logs and check that they behave correctly. They also 955 watch for certificates of interest. 957 A monitor needs to, at least, inspect every new entry in each log it 958 watches. It may also want to keep copies of entire logs. In order 959 to do this, it should follow these steps for each log: 961 1. Fetch the current STH using Section 4.3. 963 2. Verify the STH signature. 965 3. Fetch all the entries in the tree corresponding to the STH using 966 Section 4.6. 968 4. Confirm that the tree made from the fetched entries produces the 969 same hash as that in the STH. 971 5. Fetch the current STH using Section 4.3. Repeat until STH 972 changes. 974 6. Verify the STH signature. 976 7. Fetch all the new entries in the tree corresponding to the STH 977 using Section 4.6. If they remain unavailable for an extended 978 period, then this should be viewed as misbehaviour on the part of 979 the log. 981 8. Either: 983 1. Verify that the updated list of all entries generates a tree 984 with the same hash as the new STH. 986 Or, if it is not keeping all log entries: 988 2. Fetch a consistency proof for the new STH with the previous 989 STH using Section 4.4. 991 3. Verify the consistency proof. 993 4. Verify that the new entries generate the corresponding 994 elements in the consistency proof. 996 9. Go to Step 5. 998 5.4. Auditor 1000 Auditors take partial information about a log as input and verify 1001 that this information is consistent with other partial information 1002 they have. An auditor might be an integral component of a TLS 1003 client, it might be a standalone service or it might be a secondary 1004 function of a monitor. 1006 Any pair of STHs from the same log can be verified by requesting a 1007 consistency proof using Section 4.4. 1009 A certificate accompanied by an SCT can be verified against any STH 1010 dated after the SCT timestamp + the Maximum Merge Delay by requesting 1011 a Merkle Audit Proof using Section 4.5. 1013 Auditors can fetch STHs from time to time of their own accord, of 1014 course, using Section 4.3. 1016 6. IANA Considerations 1018 IANA is requested to allocate an RFC 5246 ExtensionType Value for the 1019 CTS TLS extension. The Extension name is 1020 "signed_certificate_timestamp". 1022 7. Security Considerations 1024 7.1. Misissued Certificates 1026 Misissued certificates that have not been publicly logged, and thus 1027 do not have a valid SCT, will be rejected by TLS clients. Misissued 1028 certificates that do have an SCT from a log will appear in that 1029 public log within the Maximum Merge Delay, assuming the log is 1030 operating correctly. Thus, the maximum period of time during which a 1031 misissued certificate can be used without being available for audit 1032 is the MMD. 1034 7.2. Detection of Misissue 1036 The logs do not themselves detect misissued certificates, they rely 1037 instead on interested parties, such as domain owners, to monitor them 1038 and take corrective action when a misissue is detected. 1040 7.3. Misbehaving logs 1042 A log can misbehave in two ways: (1), by failing to incorporate a 1043 certificate with an SCT in the Merkle Tree within the MMD; and (2), 1044 by violating its append-only property by presenting two different, 1045 conflicting views of the Merkle Tree at different times and/or to 1046 different parties. Both forms of violation will be promptly and 1047 publicly detectable. 1049 Violation of the MMD contract is detected by log clients requesting a 1050 Merkle audit proof for each observed SCT. These checks can be 1051 asynchronous, and need only be done once per each certificate. In 1052 order to protect the clients' privacy, these checks need not reveal 1053 the exact certificate to the log. Clients can instead request the 1054 proof from a trusted auditor (since anyone can compute the audit 1055 proofs from the log), or request Merkle proofs for a batch of 1056 certificates around the SCT timestamp. 1058 Violation of the append-only property is detected by global 1059 gossiping, i.e., everyone auditing logs comparing their versions of 1060 the latest signed tree heads. As soon as two conflicting signed tree 1061 heads for the same log are detected, this is cryptographic proof of 1062 that log's misbehaviour. 1064 8. Efficiency Considerations 1066 The Merkle tree design serves the purpose of keeping communication 1067 overhead low. 1069 Auditing logs for integrity does not require third parties to 1070 maintain a copy of each entire log. The Signed Tree Heads can be 1071 updated as new entries become available, without recomputing entire 1072 trees. Third party auditors need only fetch the Merkle consistency 1073 proofs against a log's existing STH to efficiently verify the append- 1074 only property of updates to their Merkle Trees, without auditing the 1075 entire tree. 1077 9. Future Changes 1079 This section lists things we might address in a Standards Track 1080 version of this document. 1082 Rather than forcing a log operator to create a new log in order to 1083 change the log signing key, we may allow some key roll mechanism. 1085 We may add hash and signing algorithm agility. 1087 We may describe some gossip protocols. 1089 10. References 1091 [RFC1305] Mills, D., "Network Time Protocol (Version 3) 1092 Specification, Implementation", RFC 1305, March 1992. 1094 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1095 Requirement Levels", BCP 14, RFC 2119, March 1997. 1097 [RFC2560] Myers, M., Ankney, R., Malpani, A., Galperin, S., and C. 1098 Adams, "X.509 Internet Public Key Infrastructure Online 1099 Certificate Status Protocol - OCSP", RFC 2560, June 1999. 1101 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 1102 Standards (PKCS) #1: RSA Cryptography Specifications 1103 Version 2.1", RFC 3447, February 2003. 1105 [RFC4627] Crockford, D., "The application/json Media Type for 1106 JavaScript Object Notation (JSON)", RFC 4627, July 2006. 1108 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 1109 Encodings", RFC 4648, October 2006. 1111 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 1112 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 1114 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 1115 Housley, R., and W. Polk, "Internet X.509 Public Key 1116 Infrastructure Certificate and Certificate Revocation List 1117 (CRL) Profile", RFC 5280, May 2008. 1119 [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: 1120 Extension Definitions", RFC 6066, January 2011. 1122 [DSS] National Institute of Standards and Technology, U.S. 1123 Department of Commerce, "Digital Signature Standard", 1124 FIPS 186-3, June 2009. 1126 [CrosbyWallach] 1127 Crosby, S. and D. Wallach, "Efficient data structures for 1128 tamper-evident logging", 2009. 1130 [HTML401] Hors, A., Raggett, D., and I. Jacobs, "HTML 4.01 1131 Specification", World Wide Web Consortium 1132 Recommendation REC-html401-19991224, December 1999, 1133 . 1135 [FIPS.180-2.2002] 1136 National Institute of Standards and Technology, "Secure 1137 Hash Standard", FIPS PUB 180-2, August 2002, . 1140 Authors' Addresses 1142 Ben Laurie 1144 Email: benl@google.com 1146 Adam Langley 1148 Email: agl@google.com 1150 Emilia Kasper 1152 Email: ekasper@google.com