idnits 2.17.1 draft-laurie-pki-sunlight-08.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 (March 14, 2013) is 4061 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 708 == Missing Reference: 'TBD' is mentioned on line 637, 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: September 15, 2013 March 14, 2013 7 Certificate Transparency 8 draft-laurie-pki-sunlight-08 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 September 15, 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. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 30 98 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 31 99 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33 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 certificate authorities (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 (i.e., k 189 < n <= 2k). The Merkle Tree Hash of an n-element list D[n] is then 190 defined 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 list {d(k1), 195 d(k1+1),..., d(k2-1)} of length (k2 - k1). (Note that the hash 196 calculation for leaves and nodes differ. This domain separation is 197 required to 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 the chain submitted to the log server. 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 (CA:true, Extended Key Usage: Certificate 410 Transparency, OID 1.3.6.1.4.1.11129.2.4.4) Precertificate Signing 411 Certificate. The Precertificate Signing Certificate MUST be 412 directly certified by the (root or intermediate) CA certificate 413 that will ultimately sign the end entity TBSCertificate yielding 414 the end entity certificate (note that the log may relax standard 415 validation rules to allow this, so long as the issued certificate 416 will be valid), 418 o or, the CA certificate that will sign the final certificate. 420 As above, the Precertificate submission MUST be accompanied by the 421 Precertificate Signing Certificate, if used, and all additional 422 certificates required to verify the chain up to an accepted root 423 certificate. The signature on the TBSCertificate indicates the 424 Certificate Authority's intent to issue a certificate. This intent 425 is considered binding (i.e., misissuance of the Precertificate is 426 considered equal to misissuance of the final certificate). Each log 427 verifies the Precertificate signature chain, and issues a Signed 428 Certificate Timestamp on the corresponding TBSCertificate. 430 Logs MUST verify that the submitted end entity certificate or 431 Precertificate has a valid signature chain leading back to a trusted 432 root CA certificate, using the chain of intermediate CA certificates 433 provided by the submitter. Logs MAY accept certificates that have 434 expired, are not yet valid, have been revoked or are otherwise not 435 fully valid according to X.509 verification rules in order to 436 accommodate quirks of CA certificate issuing software. However, logs 437 MUST refuse to publish certificates without a valid chain to a known 438 root CA. If a certificate is accepted and an SCT issued, the 439 accepting log MUST store the entire chain used for verification 440 including the certificate or Precertificate itself, and including the 441 root certificate used to verify the chain (even if it was omitted 442 from the submission) and MUST present this chain for auditing upon 443 request. This chain is required to prevent a CA avoiding blame by 444 logging a partial or empty chain [Note: this effectively excludes 445 self-signed and DANE-based certificates until some mechanism to 446 control spam for those certificates is found - the authors welcome 447 suggestions]. 449 Each certificate entry in a log MUST include the following 450 components: 452 enum { x509_entry(0), precert_entry(1), (65535) } LogEntryType; 454 struct { 455 LogEntryType entry_type; 456 select (entry_type) { 457 case x509_entry: X509ChainEntry; 458 case precert_entry: PrecertChainEntry; 459 } entry; 460 } LogEntry; 462 opaque ASN.1Cert<1..2^24-1>; 464 struct { 465 ASN.1Cert leaf_certificate; 466 ASN.1Cert certificate_chain<0..2^24-1>; 467 } X509ChainEntry; 469 struct { 470 ASN.1Cert pre_certificate; 471 ASN.1Cert precertificate_chain<0..2^24-1>; 472 } PrecertChainEntry; 474 Logs MAY limit the length of chain they will accept. 476 "entry_type" is the type of this entry. Future revisions of this 477 protocol version may add new LogEntryType values. Section 4 explains 478 how clients should handle unknown entry types. 480 "leaf_certificate" is the end-entity certificate submitted for 481 auditing. 483 "certificate_chain" is a chain of additional certificates required to 484 verify the end entity certificate. The first certificate MUST 485 certify the end entity certificate. Each following certificate MUST 486 directly certify the one preceding it. The final certificate MUST be 487 a root certificate accepted by the log. 489 "pre_certificate" is the Precertificate submited for auditing. 491 "precertificate_chain" is a chain of additional certificates required 492 to verify the Precertificate submission. The first certificate MAY 493 be a valid Precertificate Signing Certificate, and MUST certify the 494 first certificate. Each following certificate MUST directly certify 495 the one preceding it. The final certificate MUST be a root 496 certificate accepted by the log. 498 3.2. Structure of the Signed Certificate Timestamp 500 enum { certificate_timestamp(0), tree_hash(1), (255) } 501 SignatureType; 503 enum { v1(0), (255) } 504 Version; 506 struct { 507 opaque key_id[32]; 508 } LogID; 510 opaque TBSCertificate<1..2^16-1>; 512 struct { 513 opaque issuer_key_hash[32]; 514 TBSCertificate tbs_certificate; 515 } PreCert; 517 opaque CtExtensions<0..2^16-1>; 519 "key_id" is the SHA-256 hash of the log's public key, calculated over 520 the DER encoding of the key represented as SubjectPublicKeyInfo. 522 "issuer_key_hash" is the SHA-256 hash of the certificate issuer's 523 public key, calculated over the DER encoding of the key represented 524 as SubjectPublicKeyInfo. This is needed to bind the issuer to the 525 final certificate. 527 "tbs_certificate" is the DER encoded TBSCertificate (see [RFC5280]) 528 component of the Precertificate - that is, without the signature and 529 the poison extension. If the Precertificate is not signed with the 530 CA certificate that will issue the final certificate, then the 531 TBSCertificate also has its issuer changed to that of the CA that 532 will issue the final certificate. Note that it is also possible to 533 reconstruct this TBSCertificate from the final certificate by 534 extracting the TBSCertificate from it and deleting the SCT extension. 535 Also note that since the TBSCertificate contains an 536 AlgorithmIdentifier that must match both the pre-certificate 537 signature algorithm and final certificate signature algorithm, they 538 must be signed with the same algorithm and parameters. If the 539 Precertificate is issued using a Precertificate Signing Certificate, 540 and an Authority Key Identifier extension is present in the 541 TBSCertificate, the corresponding extension must also be present in 542 the Precertificate Signing Certificate - in this case, the 543 TBSCertificate also has its Authority Key Identifier changed to match 544 the final issuer. 546 struct { 547 Version sct_version; 548 LogID id; 549 uint64 timestamp; 550 CtExtensions extensions; 551 digitally-signed struct { 552 Version sct_version; 553 SignatureType signature_type = certificate_timestamp; 554 uint64 timestamp; 555 LogEntryType entry_type; 556 select(entry_type) { 557 case x509_entry: ASN.1Cert; 558 case precert_entry: PreCert; 559 } signed_entry; 560 CtExtensions extensions; 561 }; 562 } SignedCertificateTimestamp; 564 The encoding of the digitally-signed element is defined in [RFC5246]. 566 "sct_version" is the version of the protocol the SCT conforms to. 567 This version is v1. 569 "timestamp" is the current NTP Time [RFC5905], measured since the 570 epoch (January 1, 1970, 00:00), ignoring leap seconds, in 571 milliseconds. 573 "entry_type" may be implicit from the context in which the SCT is 574 presented. 576 "signed_entry" is the "leaf_certificate" (in case of an 577 X509ChainEntry), or is the PreCert (in case of a PrecertChainEntry), 578 as described above. 580 "extensions" are future extensions to this protocol version (v1). 581 Currently, no extensions are specified. 583 3.3. Including the Signed Certificate Timestamp in the TLS Handshake 585 The SCT data corresponding to the end entity certificate from at 586 least one log must be included in the TLS handshake, either by using 587 an X509v3 certificate extension as described below, by using a TLS 588 Extension (section 7.4.1.4 of [RFC5246]) with type [TBD], or by using 589 OCSP Stapling (section 8 of [RFC6066]), where the response includes 590 an OCSP extension with OID 1.3.6.1.4.1.11129.2.4.5 (see [RFC2560]) 591 and body: 593 SignedCertificateTimestampList ::= OCTET STRING 595 At least one SCT MUST be included. Server operators MAY include more 596 than one SCT. 598 Similarly, a Certificate Authority MAY submit a precertificate to 599 more than one log, and all obtained SCTs can be directly embedded in 600 the final certificate, by encoding the SignedCertificateTimestampList 601 structure as an ASN.1 OCTET STRING and inserting the resulting data 602 in the TBSCertificate as an X.509v3 certificate extension (OID 603 1.3.6.1.4.1.11129.2.4.2). Upon receiving the certificate, clients 604 can reconstruct the original TBSCertificate to verify the SCT 605 signature. 607 The contents of the ASN.1 OCTET STRING embedded in an OCSP extension 608 or X509v3 certificate extension are as follows: 610 opaque SerializedSCT<1..2^16-1>; 612 struct { 613 SerializedSCT sct_list <1..2^16-1>; 614 } SignedCertificateTimestampList; 616 Here "SerializedSCT" is an opaque bytestring that contains the 617 serialized TLS structure. This encoding ensures that TLS clients can 618 decode each SCT individually (i.e., if there is a version upgrade, 619 out of date clients can still parse old SCTs while skipping over new 620 SCTs whose version they don't understand). 622 Likewise, SCTs can be embedded in a TLS Extension. See below for 623 details. 625 TLS clients MUST implement all three mechanisms. Servers MUST 626 implement at least one of the three mechanisms. Note that existing 627 TLS servers can generally use the certificate extension mechanism 628 without modification. 630 TLS servers should send SCTs from multiple logs in case one or more 631 logs is not acceptable to the client (for example, if a log has been 632 struck off for misbehaviour or has had a key compromise). 634 3.3.1. TLS Extension 636 The SCT can be sent during the TLS handshake using a TLS extension, 637 type [TBD]. 639 Clients that support the extension SHOULD send a ClientHello 640 extension with the appropriate type and empty "extension_data". 642 Servers MUST only send SCTs to clients who have indicated support for 643 the extension in the ClientHello, in which case the SCTs are sent by 644 setting the "extension_data" to a "SignedCertificateTimestampList". 646 Session resumption uses the original session information: clients 647 SHOULD include the extension type in the ClientHello but if the 648 session is resumed, the server is not expected to process it or 649 include the extension in the ServerHello. 651 3.4. Merkle Tree 653 The hashing algorithm for the Merkle Tree Hash is SHA-256. 655 Structure of the Merkle Tree input: 657 enum { timestamped_entry(0), (255) } 658 MerkleLeafType; 660 struct { 661 uint64 timestamp; 662 LogEntryType entry_type; 663 select(entry_type) { 664 case x509_entry: ASN.1Cert; 665 case precert_entry: PreCert; 666 } signed_entry; 667 CtExtensions extensions; 668 } TimestampedEntry; 670 struct { 671 Version version; 672 MerkleLeafType leaf_type; 673 select (leaf_type) { 674 case timestamped_entry: TimestampedEntry; 675 } 676 } MerkleTreeLeaf; 678 Here "version" is the version of the protocol the MerkleTreeLeaf 679 corresponds to. This version is v1. 681 "leaf_type" is the type of the leaf input. Currently, only 682 "timestamped_entry" (corresponding to an SCT) is defined. Future 683 revisions of this protocol version may add new MerkleLeafType types. 684 Section 4 explains how clients should handle unknown leaf types. 686 "timestamp" is the timestamp of the corresponding SCT issued for this 687 certificate. 689 "signed_entry" is the "signed_entry" of the corresponding SCT. 691 "extensions" are "extensions" of the corresponding SCT. 693 The leaves of the Merkle Tree are the leaf hashes of the 694 corresponding "MerkleTreeLeaf" structures. 696 3.5. Signed Tree Head 698 Every time a log appends new entries to the tree, the log SHOULD sign 699 the corresponding tree hash and tree information (see the 700 corresponding Signed Tree Head client message in Section 4.3). The 701 signature for that data is structured as follows: 703 digitally-signed struct { 704 Version version; 705 SignatureType signature_type = tree_hash; 706 uint64 timestamp; 707 uint64 tree_size; 708 opaque sha256_root_hash[32]; 709 } TreeHeadSignature; 711 "version" is the version of the protocol the TreeHeadSignature 712 conforms to. This version is v1. 714 "timestamp" is the current time. The timestamp MUST be at least as 715 recent as the most recent SCT timestamp in the tree. Each subsequent 716 timestamp MUST be more recent than the timestamp of the previous 717 update. 719 "tree_size" equals the number of entries in the new tree. 721 "sha256_root_hash" is the root of the Merkle Hash Tree. 723 Each log MUST produce on demand a Signed Tree Head that is no older 724 than the Maximum Merge Delay. In the unlikely event that it receives 725 no new submissions during an MMD period, the log SHALL sign the same 726 Merkle Tree Hash with a fresh timestamp. 728 4. Log Client Messages 730 Messages are sent as HTTPS GET or POST requests. Parameters for 731 POSTs and all responses are encoded as JSON objects [RFC4627]. 732 Parameters for GETs are encoded as order independent key/value URL 733 parameters, using the "application/x-www-form-urlencoded" format 734 described in the "HTML 4.01 Specification" [HTML401]. Binary data is 735 base64 encoded [RFC4648] as specified in the individual messages. 737 The prefix can include a path as well as a server name 738 and a port. 740 In general, where needed, the "version" is v1 and the "id" is the log 741 id for the log server queried. 743 Any errors will be returned as HTTP 4xx or 5xx responses, with human 744 readable error messages. 746 4.1. Add Chain to Log 748 POST https:///ct/v1/add-chain 750 Inputs 752 chain An array of base64 encoded certificates. The first element is 753 the end entity certificate, the second chains to the first and so 754 on to the last, which is either the root certificate or a 755 certificate that chains to a known root certificate. 757 Outputs 759 sct_version The version of the SignedCertificateTimestamp structure, 760 in decimal. A compliant v1 implementation MUST NOT expect this to 761 be 0 (i.e., v1). 763 id The log ID, base64 encoded. Since log clients who request an SCT 764 for inclusion in TLS handshakes are not required to verify it, we 765 do not assume they know the ID of the log. 767 timestamp The SCT timestamp, in decimal. 769 extensions An opaque type for future expansion. It is likely that 770 not all participants will need to understand data in this field. 771 Logs should set this to the empty string. Clients should decode 772 the base64 encoded data and include it in the SCT. 774 signature The SCT signature, base64 encoded. 776 If the "sct_version" is not v1, then a v1 client may be unable to 777 verify the signature. It MUST NOT construe this as an error. [Note: 778 log clients don't need to be able to verify this structure, only TLS 779 clients do - if we were to serve the structure binary, then we could 780 completely change it without requiring an upgrade to v1 clients]. 782 4.2. Add PreCertChain to Log 784 POST https:///ct/v1/add-pre-chain 786 Inputs 788 chain An array of base64 encoded precertificates. The first element 789 is the end entity certificate, the second chains to the first and 790 so on to the last, which is either the root certificate or a 791 certificate that chains to a known root certificate. 793 Outputs are the same as Section 4.1. 795 4.3. Retrieve Latest Signed Tree Head 797 GET https:///ct/v1/get-sth 799 No inputs. 801 Outputs 803 tree_size The size of the tree, in entries, in decimal. 805 timestamp The timestamp, in decimal. 807 sha256_root_hash The Merkle Tree Hash of the tree, in base64. 809 tree_head_signature A TreeHeadSignature for the above data. 811 4.4. Retrieve Merkle Consistency Proof between two Signed Tree Heads 813 GET https:///ct/v1/get-sth-consistency 815 Inputs 817 first The tree_size of the first tree, in decimal. 819 second The tree_size of the second tree, in decimal. 821 Both tree sizes must be from existing v1 STHs (Signed Tree Heads). 823 Outputs 825 consistency An array of Merkle tree nodes, base64 encoded. 827 Note that no signature is required on this data, as it is used to 828 verify an STH, which is signed. 830 4.5. Retrieve Merkle Audit Proof from Log by Leaf Hash 832 GET https:///ct/v1/get-proof-by-hash 834 Inputs 836 hash A base64 encoded v1 leaf hash. 838 tree_size The tree_size of the tree to base the proof on, in 839 decimal. 841 The "hash" must be calculated as defined in Section 3.4. The 842 "tree_size" must designate an existing v1 STH. 844 Outputs 846 leaf_index The 0-based index of the end entity corresponding to the 847 "hash" parameter. 849 audit_path An array of base64 encoded Merkle tree nodes proving the 850 inclusion of the chosen certificate. 852 4.6. Retrieve Entries from Log 854 GET https:///ct/v1/get-entries 856 Inputs 858 start 0-based index of first entry to retrieve, in decimal. 860 end 0-based index of last entry to retrieve, in decimal. 862 Outputs 863 entries An array of objects, each consisting of 865 leaf_input The base64-encoded MerkleTreeLeaf structure. 867 extra_data The base64-encoded unsigned data pertaining to the log 868 entry. In the case of an X509ChainEntry, this is the 869 "certificate_chain". In the case of a PrecertChainEntry, this 870 is the "precertificate_chain". 872 Note that this message is not signed - the retrieved data can be 873 verified by constructing the Merkle Tree Hash corresponding to a 874 retrieved STH. All leaves MUST be v1. However, a compliant v1 875 client MUST NOT construe an unrecognized MerkleLeafType or 876 LogEntryType value as an error. This means it may be unable to parse 877 some entries, but note that each client can inspect the entries it 878 does recognize, as well as verify the integrity of the data by 879 treating unrecognized leaves as opaque input to the tree. 881 The "start" and "end" parameters SHOULD be within the range 0 <= x < 882 "tree_size" as returned by "get-sth" in Section 4.3. 884 Logs MAY honour requests where 0 <= "start" < "tree_size", and "end" 885 >= "tree_size" by returning a partial response covering only the 886 valid entries in the specified range. Note that the following 887 restriction may also apply: 889 Logs MAY restrict the number of entries which can be retrieved per 890 "get-entries" request. If a client requests more than the permitted 891 number of entries, the log SHALL return the maximum number of entries 892 permissible. These entries SHALL be sequential beginning with the 893 entry specified by "start". 895 4.7. Retrieve Accepted Root Certificates 897 Outputs 899 certificates An array of base64 encoded root certificates that are 900 acceptable to the log. 902 4.8. Retrieve Entry+Merkle Audit Proof from Log 904 GET https:///ct/v1/get-entry-and-proof 906 Inputs 907 leaf_index The index of the desired entry. 909 tree_size The tree_size of the tree for which the proof is desired. 911 The tree size must designate an existing STH. 913 Outputs 915 leaf_input The base64-encoded MerkleTreeLeaf structure. 917 extra_data The base64-encoded unsigned data, same as in Section 4.6. 919 audit_path An array of base64 encoded Merkle tree nodes proving the 920 inclusion of the chosen certificate. 922 This API is probably only useful for debugging. 924 5. Clients 926 There are various different functions clients of logs might perform. 927 We describe here some typical clients and how they could function. 928 Any inconsistency may be used as evidence that a log has not behaved 929 correctly, and the signatures on the data structures prevent the log 930 from denying that misbehaviour. 932 All clients should gossip with each other, exchanging STHs at least: 933 this is all that is required to ensure that they all have a 934 consistent view. The exact mechanism for gossip will be described in 935 an separate document, but it is expected there will be a variety. 937 5.1. Submitters 939 Submitters submit certificates or precertificates to the log as 940 described above. They may go on to use the returned SCT to construct 941 a certificate or use it directly in a TLS handshake. 943 5.2. TLS Client 945 TLS clients are not directly clients of the log, but they receive 946 SCTs alongside or in server certificates. In addition to normal 947 validation of the certificate and its chain, they should validate the 948 SCT by computing the signature input from the SCT data as well as the 949 certificate, and verifying the signature, using the corresponding 950 log's public key. Note that this document does not describe how 951 clients obtain the logs' public keys. 953 TLS clients MUST reject SCTs whose timestamp is in the future. 955 5.3. Monitor 957 Monitors watch logs and check that they behave correctly. They also 958 watch for certificates of interest. 960 A monitor needs to, at least, inspect every new entry in each log it 961 watches. It may also want to keep copies of entire logs. In order 962 to do this, it should follow these steps for each log: 964 1. Fetch the current STH using Section 4.3. 966 2. Verify the STH signature. 968 3. Fetch all the entries in the tree corresponding to the STH using 969 Section 4.6. 971 4. Confirm that the tree made from the fetched entries produces the 972 same hash as that in the STH. 974 5. Fetch the current STH using Section 4.3. Repeat until STH 975 changes. 977 6. Verify the STH signature. 979 7. Fetch all the new entries in the tree corresponding to the STH 980 using Section 4.6. If they remain unavailable for an extended 981 period, then this should be viewed as misbehaviour on the part of 982 the log. 984 8. Either: 986 1. Verify that the updated list of all entries generates a tree 987 with the same hash as the new STH. 989 Or, if it is not keeping all log entries: 991 2. Fetch a consistency proof for the new STH with the previous 992 STH using Section 4.4. 994 3. Verify the consistency proof. 996 4. Verify that the new entries generate the corresponding 997 elements in the consistency proof. 999 9. Go to Step 5. 1001 5.4. Auditor 1003 Auditors take partial information about a log as input and verify 1004 that this information is consistent with other partial information 1005 they have. An auditor might be an integral component of a TLS 1006 client, it might be a standalone service or it might be a secondary 1007 function of a monitor. 1009 Any pair of STHs from the same log can be verified by requesting a 1010 consistency proof using Section 4.4. 1012 A certificate accompanied by an SCT can be verified against any STH 1013 dated after the SCT timestamp + the Maximum Merge Delay by requesting 1014 a Merkle Audit Proof using Section 4.5. 1016 Auditors can fetch STHs from time to time of their own accord, of 1017 course, using Section 4.3. 1019 6. IANA Considerations 1021 IANA is requested to allocate an RFC 5246 ExtensionType Value for the 1022 CTS TLS extension. The Extension name is 1023 "signed_certificate_timestamp". 1025 7. Security Considerations 1027 7.1. Misissued Certificates 1029 Misissued certificates that have not been publicly logged, and thus 1030 do not have a valid SCT, will be rejected by TLS clients. Misissued 1031 certificates that do have an SCT from a log will appear in that 1032 public log within the Maximum Merge Delay, assuming the log is 1033 operating correctly. Thus, the maximum period of time during which a 1034 misissued certificate can be used without being available for audit 1035 is the MMD. 1037 7.2. Detection of Misissue 1039 The logs do not themselves detect misissued certificates, they rely 1040 instead on interested parties, such as domain owners, to monitor them 1041 and take corrective action when a misissue is detected. 1043 7.3. Misbehaving logs 1045 A log can misbehave in two ways: (1), by failing to incorporate a 1046 certificate with an SCT in the Merkle Tree within the MMD; and (2), 1047 by violating its append-only property by presenting two different, 1048 conflicting views of the Merkle Tree at different times and/or to 1049 different parties. Both forms of violation will be promptly and 1050 publicly detectable. 1052 Violation of the MMD contract is detected by log clients requesting a 1053 Merkle audit proof for each observed SCT. These checks can be 1054 asynchronous, and need only be done once per each certificate. In 1055 order to protect the clients' privacy, these checks need not reveal 1056 the exact certificate to the log. Clients can instead request the 1057 proof from a trusted auditor (since anyone can compute the audit 1058 proofs from the log), or request Merkle proofs for a batch of 1059 certificates around the SCT timestamp. 1061 Violation of the append-only property is detected by global 1062 gossiping, i.e., everyone auditing logs comparing their versions of 1063 the latest signed tree heads. As soon as two conflicting signed tree 1064 heads for the same log are detected, this is cryptographic proof of 1065 that log's misbehaviour. 1067 8. Efficiency Considerations 1069 The Merkle tree design serves the purpose of keeping communication 1070 overhead low. 1072 Auditing logs for integrity does not require third parties to 1073 maintain a copy of each entire log. The Signed Tree Heads can be 1074 updated as new entries become available, without recomputing entire 1075 trees. Third party auditors need only fetch the Merkle consistency 1076 proofs against a log's existing STH to efficiently verify the append- 1077 only property of updates to their Merkle Trees, without auditing the 1078 entire tree. 1080 9. Future Changes 1082 This section lists things we might address in a Standards Track 1083 version of this document. 1085 Rather than forcing a log operator to create a new log in order to 1086 change the log signing key, we may allow some key roll mechanism. 1088 We may add hash and signing algorithm agility. 1090 We may describe some gossip protocols. 1092 10. Acknowledgements 1094 The authors would like to thank Stephen Farrell, Brad Hill, ... for 1095 their valuable contributions. 1097 11. References 1099 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1100 Requirement Levels", BCP 14, RFC 2119, March 1997. 1102 [RFC2560] Myers, M., Ankney, R., Malpani, A., Galperin, S., and C. 1103 Adams, "X.509 Internet Public Key Infrastructure Online 1104 Certificate Status Protocol - OCSP", RFC 2560, June 1999. 1106 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 1107 Standards (PKCS) #1: RSA Cryptography Specifications 1108 Version 2.1", RFC 3447, February 2003. 1110 [RFC4627] Crockford, D., "The application/json Media Type for 1111 JavaScript Object Notation (JSON)", RFC 4627, July 2006. 1113 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 1114 Encodings", RFC 4648, October 2006. 1116 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 1117 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 1119 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 1120 Housley, R., and W. Polk, "Internet X.509 Public Key 1121 Infrastructure Certificate and Certificate Revocation List 1122 (CRL) Profile", RFC 5280, May 2008. 1124 [RFC5905] Mills, D., Martin, J., Burbank, J., and W. Kasch, "Network 1125 Time Protocol Version 4: Protocol and Algorithms 1126 Specification", RFC 5905, June 2010. 1128 [RFC6066] Eastlake, D., "Transport Layer Security (TLS) Extensions: 1129 Extension Definitions", RFC 6066, January 2011. 1131 [DSS] National Institute of Standards and Technology, U.S. 1132 Department of Commerce, "Digital Signature Standard", 1133 FIPS 186-3, June 2009. 1135 [CrosbyWallach] 1136 Crosby, S. and D. Wallach, "Efficient data structures for 1137 tamper-evident logging", 2009. 1139 [HTML401] Hors, A., Raggett, D., and I. Jacobs, "HTML 4.01 1140 Specification", World Wide Web Consortium 1141 Recommendation REC-html401-19991224, December 1999, 1142 . 1144 [FIPS.180-2.2002] 1145 National Institute of Standards and Technology, "Secure 1146 Hash Standard", FIPS PUB 180-2, August 2002, . 1149 Authors' Addresses 1151 Ben Laurie 1153 Email: benl@google.com 1155 Adam Langley 1157 Email: agl@google.com 1159 Emilia Kasper 1161 Email: ekasper@google.com