This repository has been archived by the owner on Nov 10, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 36
/
draft-ietf-trans-rfc6962-bis-36.txt
3528 lines (2311 loc) · 134 KB
/
draft-ietf-trans-rfc6962-bis-36.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
TRANS (Public Notary Transparency) B. Laurie
Internet-Draft A. Langley
Obsoletes: 6962 (if approved) E. Kasper
Intended status: Experimental E. Messeri
Expires: 14 November 2021 Google
R. Stradling
Sectigo
13 May 2021
Certificate Transparency Version 2.0
draft-ietf-trans-rfc6962-bis-36
Abstract
This document describes version 2.0 of the Certificate Transparency
(CT) protocol for publicly logging the existence of Transport Layer
Security (TLS) server certificates as they are issued or observed, in
a manner that allows anyone to audit certification authority (CA)
activity and notice the issuance of suspect certificates as well as
to audit the certificate logs themselves. The intent is that
eventually clients would refuse to honor certificates that do not
appear in a log, effectively forcing CAs to add all issued
certificates to the logs.
This document obsoletes RFC 6962. It also specifies a new TLS
extension that is used to send various CT log artifacts.
Logs are network services that implement the protocol operations for
submissions and queries that are defined in this document.
[RFC Editor: please update 'RFCXXXX' to refer to this document, once
its RFC number is known, through the document.]
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
Laurie, et al. Expires 14 November 2021 [Page 1]
Internet-Draft Certificate Transparency Version 2.0 May 2021
This Internet-Draft will expire on 14 November 2021.
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Simplified BSD License text
as described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Requirements Language . . . . . . . . . . . . . . . . . . 5
1.2. Data Structures . . . . . . . . . . . . . . . . . . . . . 5
1.3. Major Differences from CT 1.0 . . . . . . . . . . . . . . 5
2. Cryptographic Components . . . . . . . . . . . . . . . . . . 7
2.1. Merkle Hash Trees . . . . . . . . . . . . . . . . . . . . 7
2.1.1. Definition of the Merkle Tree . . . . . . . . . . . . 7
2.1.2. Verifying a Tree Head Given Entries . . . . . . . . . 8
2.1.3. Merkle Inclusion Proofs . . . . . . . . . . . . . . . 9
2.1.4. Merkle Consistency Proofs . . . . . . . . . . . . . . 10
2.1.5. Example . . . . . . . . . . . . . . . . . . . . . . . 13
2.2. Signatures . . . . . . . . . . . . . . . . . . . . . . . 14
3. Submitters . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1. Certificates . . . . . . . . . . . . . . . . . . . . . . 15
3.2. Precertificates . . . . . . . . . . . . . . . . . . . . . 15
3.2.1. Binding Intent to Issue . . . . . . . . . . . . . . . 17
4. Log Format and Operation . . . . . . . . . . . . . . . . . . 17
4.1. Log Parameters . . . . . . . . . . . . . . . . . . . . . 18
4.2. Evaluating Submissions . . . . . . . . . . . . . . . . . 19
4.2.1. Minimum Acceptance Criteria . . . . . . . . . . . . . 19
4.2.2. Discretionary Acceptance Criteria . . . . . . . . . . 20
4.3. Log Entries . . . . . . . . . . . . . . . . . . . . . . . 20
4.4. Log ID . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.5. TransItem Structure . . . . . . . . . . . . . . . . . . . 21
4.6. Log Artifact Extensions . . . . . . . . . . . . . . . . . 22
4.7. Merkle Tree Leaves . . . . . . . . . . . . . . . . . . . 23
4.8. Signed Certificate Timestamp (SCT) . . . . . . . . . . . 24
4.9. Merkle Tree Head . . . . . . . . . . . . . . . . . . . . 25
4.10. Signed Tree Head (STH) . . . . . . . . . . . . . . . . . 26
4.11. Merkle Consistency Proofs . . . . . . . . . . . . . . . . 26
Laurie, et al. Expires 14 November 2021 [Page 2]
Internet-Draft Certificate Transparency Version 2.0 May 2021
4.12. Merkle Inclusion Proofs . . . . . . . . . . . . . . . . . 27
4.13. Shutting down a log . . . . . . . . . . . . . . . . . . . 28
5. Log Client Messages . . . . . . . . . . . . . . . . . . . . . 28
5.1. Submit Entry to Log . . . . . . . . . . . . . . . . . . . 30
5.2. Retrieve Latest Signed Tree Head . . . . . . . . . . . . 32
5.3. Retrieve Merkle Consistency Proof between Two Signed Tree
Heads . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.4. Retrieve Merkle Inclusion Proof from Log by Leaf Hash . . 33
5.5. Retrieve Merkle Inclusion Proof, Signed Tree Head and
Consistency Proof by Leaf Hash . . . . . . . . . . . . . 34
5.6. Retrieve Entries and STH from Log . . . . . . . . . . . . 35
5.7. Retrieve Accepted Trust Anchors . . . . . . . . . . . . . 37
6. TLS Servers . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.1. TLS Client Authentication . . . . . . . . . . . . . . . . 38
6.2. Multiple SCTs . . . . . . . . . . . . . . . . . . . . . . 39
6.3. TransItemList Structure . . . . . . . . . . . . . . . . . 39
6.4. Presenting SCTs, inclusions proofs and STHs . . . . . . . 40
6.5. transparency_info TLS Extension . . . . . . . . . . . . . 40
7. Certification Authorities . . . . . . . . . . . . . . . . . . 41
7.1. Transparency Information X.509v3 Extension . . . . . . . 41
7.1.1. OCSP Response Extension . . . . . . . . . . . . . . . 41
7.1.2. Certificate Extension . . . . . . . . . . . . . . . . 41
7.2. TLS Feature X.509v3 Extension . . . . . . . . . . . . . . 41
8. Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
8.1. TLS Client . . . . . . . . . . . . . . . . . . . . . . . 42
8.1.1. Receiving SCTs and inclusion proofs . . . . . . . . . 42
8.1.2. Reconstructing the TBSCertificate . . . . . . . . . . 42
8.1.3. Validating SCTs . . . . . . . . . . . . . . . . . . . 42
8.1.4. Fetching inclusion proofs . . . . . . . . . . . . . . 43
8.1.5. Validating inclusion proofs . . . . . . . . . . . . . 43
8.1.6. Evaluating compliance . . . . . . . . . . . . . . . . 44
8.2. Monitor . . . . . . . . . . . . . . . . . . . . . . . . . 44
8.3. Auditing . . . . . . . . . . . . . . . . . . . . . . . . 45
9. Algorithm Agility . . . . . . . . . . . . . . . . . . . . . . 46
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 47
10.1. New Entry to the TLS ExtensionType Registry . . . . . . 47
10.2. Hash Algorithms . . . . . . . . . . . . . . . . . . . . 47
10.2.1. Specification Required guidance . . . . . . . . . . 47
10.3. Signature Algorithms . . . . . . . . . . . . . . . . . . 48
10.3.1. Expert Review guidelines . . . . . . . . . . . . . . 49
10.4. VersionedTransTypes . . . . . . . . . . . . . . . . . . 49
10.5. Log Artifact Extension Registry . . . . . . . . . . . . 50
10.5.1. Specification Required guidance . . . . . . . . . . 51
10.6. Object Identifiers . . . . . . . . . . . . . . . . . . . 51
10.6.1. Log ID Registry . . . . . . . . . . . . . . . . . . 51
10.7. URN Sub-namespace for TRANS errors
(urn:ietf:params:trans:error) . . . . . . . . . . . . . 52
10.7.1. TRANS Error Types . . . . . . . . . . . . . . . . . 53
Laurie, et al. Expires 14 November 2021 [Page 3]
Internet-Draft Certificate Transparency Version 2.0 May 2021
11. Security Considerations . . . . . . . . . . . . . . . . . . . 54
11.1. Misissued Certificates . . . . . . . . . . . . . . . . . 55
11.2. Detection of Misissue . . . . . . . . . . . . . . . . . 55
11.3. Misbehaving Logs . . . . . . . . . . . . . . . . . . . . 55
11.4. Multiple SCTs . . . . . . . . . . . . . . . . . . . . . 56
11.5. Leakage of DNS Information . . . . . . . . . . . . . . . 56
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 56
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 57
13.1. Normative References . . . . . . . . . . . . . . . . . . 57
13.2. Informative References . . . . . . . . . . . . . . . . . 59
Appendix A. Supporting v1 and v2 simultaneously (Informative) . 60
Appendix B. An ASN.1 Module (Informative) . . . . . . . . . . . 61
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 62
1. Introduction
Certificate Transparency aims to mitigate the problem of misissued
certificates by providing append-only logs of issued certificates.
The logs do not themselves prevent misissuance, but they ensure that
interested parties (particularly those named in certificates) can
detect such misissuance. Note that this is a general mechanism that
could be used for transparently logging any form of binary data,
subject to some kind of inclusion criteria. In this document, we
only describe its use for public TLS server certificates (i.e., where
the inclusion criteria is a valid certificate issued by a public
certification authority (CA)). A typical definition of "public" can
be found in [CABBR].
Each log contains certificate chains, which can be submitted by
anyone. It is expected that public CAs will contribute all their
newly issued certificates to one or more logs; however certificate
holders can also contribute their own certificate chains, as can
third parties. In order to avoid logs being rendered useless by the
submission of large numbers of spurious certificates, it is required
that each chain ends with a trust anchor that is accepted by the log.
A log may also limit the length of the chain it is willing to accept;
such chains must also end with an acceptable trust anchor. When a
chain is accepted by a log, a signed timestamp is returned, which can
later be used to provide evidence to TLS clients that the chain has
been submitted. TLS clients can thus require that all certificates
they accept as valid are accompanied by signed timestamps.
Those who are concerned about misissuance can monitor the logs,
asking them regularly for all new entries, and can thus check whether
domains for which they are responsible have had certificates issued
that they did not expect. What they do with this information,
particularly when they find that a misissuance has happened, is
beyond the scope of this document. However, broadly speaking, they
Laurie, et al. Expires 14 November 2021 [Page 4]
Internet-Draft Certificate Transparency Version 2.0 May 2021
can invoke existing business mechanisms for dealing with misissued
certificates, such as working with the CA to get the certificate
revoked, or with maintainers of trust anchor lists to get the CA
removed. Of course, anyone who wants can monitor the logs and, if
they believe a certificate is incorrectly issued, take action as they
see fit.
Similarly, those who have seen signed timestamps from a particular
log can later demand a proof of inclusion from that log. If the log
is unable to provide this (or, indeed, if the corresponding
certificate is absent from monitors' copies of that log), that is
evidence of the incorrect operation of the log. The checking
operation is asynchronous to allow clients to proceed without delay,
despite possible issues such as network connectivity and the vagaries
of firewalls.
The append-only property of each log is achieved using Merkle Trees,
which can be used to efficiently prove that any particular instance
of the log is a superset of any particular previous instance and to
efficiently detect various misbehaviors of the log (e.g., issuing a
signed timestamp for a certificate that is not subsequently logged).
It is necessary to treat each log as a trusted third party, because
the log auditing mechanisms described in this document can be
circumvented by a misbehaving log that shows different, inconsistent
views of itself to different clients. While mechanisms are being
developed to address these shortcomings and thereby avoid the need to
blindly trust logs, such mechanisms are outside the scope of this
document.
1.1. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
1.2. Data Structures
Data structures are defined and encoded according to the conventions
laid out in Section 3 of [RFC8446].
1.3. Major Differences from CT 1.0
This document revises and obsoletes the CT 1.0 [RFC6962] protocol,
drawing on insights gained from CT 1.0 deployments and on feedback
from the community. The major changes are:
Laurie, et al. Expires 14 November 2021 [Page 5]
Internet-Draft Certificate Transparency Version 2.0 May 2021
* Hash and signature algorithm agility: permitted algorithms are now
specified in IANA registries.
* Precertificate format: precertificates are now CMS objects rather
than X.509 certificates, which avoids violating the certificate
serial number uniqueness requirement in Section 4.1.2.2 of
[RFC5280].
* Removed precertificate signing certificates and the precertificate
poison extension: the change of precertificate format means that
these are no longer needed.
* Logs IDs: each log is now identified by an OID rather than by the
hash of its public key. OID allocations are managed by an IANA
registry.
* "TransItem" structure: this new data structure is used to
encapsulate most types of CT data. A "TransItemList", consisting
of one or more "TransItem" structures, can be used anywhere that
"SignedCertificateTimestampList" was used in [RFC6962].
* Merkle tree leaves: the "MerkleTreeLeaf" structure has been
replaced by the "TransItem" structure, which eases extensibility
and simplifies the leaf structure by removing one layer of
abstraction.
* Unified leaf format: the structure for both certificate and
precertificate entries now includes only the TBSCertificate
(whereas certificate entries in [RFC6962] included the entire
certificate).
* Log Artifact Extensions: these are now typed and managed by an
IANA registry, and they can now appear not only in SCTs but also
in STHs.
* API outputs: complete "TransItem" structures are returned, rather
than the constituent parts of each structure.
* get-all-by-hash: new client API for obtaining an inclusion proof
and the corresponding consistency proof at the same time.
* submit-entry: new client API, replacing add-chain and add-pre-
chain.
* Presenting SCTs with proofs: TLS servers may present SCTs together
with the corresponding inclusion proofs using any of the
mechanisms that [RFC6962] defined for presenting SCTs only.
(Presenting SCTs only is still supported).
Laurie, et al. Expires 14 November 2021 [Page 6]
Internet-Draft Certificate Transparency Version 2.0 May 2021
* CT TLS extension: the "signed_certificate_timestamp" TLS extension
has been replaced by the "transparency_info" TLS extension.
* Verification algorithms: added detailed algorithms for verifying
inclusion proofs, for verifying consistency between two STHs, and
for verifying a root hash given a complete list of the relevant
leaf input entries.
* Extensive clarifications and editorial work.
2. Cryptographic Components
2.1. Merkle Hash Trees
A full description of Merkle Hash Tree is beyond the scope of this
document. Briefly, it is a binary tree where each non-leaf node is a
hash of its children. For CT, the number of children is at most two.
Additional information can be found in the Introduction and Reference
section of [RFC8391].
2.1.1. Definition of the Merkle Tree
The log uses a binary Merkle Hash Tree for efficient auditing. The
hash algorithm used is one of the log's parameters (see Section 4.1).
This document establishes a registry of acceptable hash algorithms
(see Section 10.2). Throughout this document, the hash algorithm in
use is referred to as HASH and the size of its output in bytes as
HASH_SIZE. The input to the Merkle Tree Hash is a list of data
entries; these entries will be hashed to form the leaves of the
Merkle Hash Tree. The output is a single HASH_SIZE Merkle Tree Hash.
Given an ordered list of n inputs, D_n = {d[0], d[1], ..., d[n-1]},
the Merkle Tree Hash (MTH) is thus defined as follows:
The hash of an empty list is the hash of an empty string:
MTH({}) = HASH().
The hash of a list with one entry (also known as a leaf hash) is:
MTH({d[0]}) = HASH(0x00 || d[0]).
For n > 1, let k be the largest power of two smaller than n (i.e., k
< n <= 2k). The Merkle Tree Hash of an n-element list D_n is then
defined recursively as
MTH(D_n) = HASH(0x01 || MTH(D[0:k]) || MTH(D[k:n])),
where:
Laurie, et al. Expires 14 November 2021 [Page 7]
Internet-Draft Certificate Transparency Version 2.0 May 2021
* || denotes concatenation
* : denotes concatenation of lists
* D[k1:k2] = D'_(k2-k1) denotes the list {d'[0] = d[k1], d'[1] =
d[k1+1], ..., d'[k2-k1-1] = d[k2-1]} of length (k2 - k1).
Note that the hash calculations for leaves and nodes differ; this
domain separation is required to give second preimage resistance.
Note that we do not require the length of the input list to be a
power of two. The resulting Merkle Tree may thus not be balanced;
however, its shape is uniquely determined by the number of leaves.
(Note: This Merkle Tree is essentially the same as the history tree
[CrosbyWallach] proposal, except our definition handles non-full
trees differently).
2.1.2. Verifying a Tree Head Given Entries
When a client has a complete list of "entries" from "0" up to
"tree_size - 1" and wishes to verify this list against a tree head
"root_hash" returned by the log for the same "tree_size", the
following algorithm may be used:
1. Set "stack" to an empty stack.
2. For each "i" from "0" up to "tree_size - 1":
1. Push "HASH(0x00 || entries[i])" to "stack".
2. Set "merge_count" to the lowest value ("0" included) such
that "LSB(i >> merge_count)" is not set, where "LSB" means
the least significant bit. In other words, set "merge_count"
to the number of consecutive "1"s found starting at the least
significant bit of "i".
3. Repeat "merge_count" times:
1. Pop "right" from "stack".
2. Pop "left" from "stack".
3. Push "HASH(0x01 || left || right)" to "stack".
3. If there is more than one element in the "stack", repeat the same
merge procedure (the sub-items of Step 2.3 above) until only a
single element remains.
Laurie, et al. Expires 14 November 2021 [Page 8]
Internet-Draft Certificate Transparency Version 2.0 May 2021
4. The remaining element in "stack" is the Merkle Tree hash for the
given "tree_size" and should be compared by equality against the
supplied "root_hash".
2.1.3. Merkle Inclusion Proofs
A Merkle inclusion proof for a leaf in a Merkle Hash Tree is the
shortest list of additional nodes in the Merkle Tree required to
compute the Merkle Tree Hash for that tree. Each node in the tree is
either a leaf node or is computed from the two nodes immediately
below it (i.e., towards the leaves). At each step up the tree
(towards the root), a node from the inclusion proof is combined with
the node computed so far. In other words, the inclusion proof
consists of the list of missing nodes required to compute the nodes
leading from a leaf to the root of the tree. If the root computed
from the inclusion proof matches the true root, then the inclusion
proof proves that the leaf exists in the tree.
2.1.3.1. Generating an Inclusion Proof
Given an ordered list of n inputs to the tree, D_n = {d[0], d[1],
..., d[n-1]}, the Merkle inclusion proof PATH(m, D_n) for the (m+1)th
input d[m], 0 <= m < n, is defined as follows:
The proof for the single leaf in a tree with a one-element input list
D[1] = {d[0]} is empty:
PATH(0, {d[0]}) = {}
For n > 1, let k be the largest power of two smaller than n. The
proof for the (m+1)th element d[m] in a list of n > m elements is
then defined recursively as
PATH(m, D_n) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and
PATH(m, D_n) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k,
The : operator and D[k1:k2] are defined the same as in Section 2.1.1.
2.1.3.2. Verifying an Inclusion Proof
When a client has received an inclusion proof (e.g., in a "TransItem"
of type "inclusion_proof_v2") and wishes to verify inclusion of an
input "hash" for a given "tree_size" and "root_hash", the following
algorithm may be used to prove the "hash" was included in the
"root_hash":
Laurie, et al. Expires 14 November 2021 [Page 9]
Internet-Draft Certificate Transparency Version 2.0 May 2021
1. Compare "leaf_index" from the "inclusion_proof_v2" structure
against "tree_size". If "leaf_index" is greater than or equal to
"tree_size" then fail the proof verification.
2. Set "fn" to "leaf_index" and "sn" to "tree_size - 1".
3. Set "r" to "hash".
4. For each value "p" in the "inclusion_path" array:
If "sn" is 0, stop the iteration and fail the proof verification.
If "LSB(fn)" is set, or if "fn" is equal to "sn", then:
1. Set "r" to "HASH(0x01 || p || r)"
2. If "LSB(fn)" is not set, then right-shift both "fn" and "sn"
equally until either "LSB(fn)" is set or "fn" is "0".
Otherwise:
1. Set "r" to "HASH(0x01 || r || p)"
Finally, right-shift both "fn" and "sn" one time.
5. Compare "sn" to 0. Compare "r" against the "root_hash". If "sn"
is equal to 0, and "r" and the "root_hash" are equal, then the
log has proven the inclusion of "hash". Otherwise, fail the
proof verification.
2.1.4. Merkle Consistency Proofs
Merkle consistency proofs prove the append-only property of the tree.
A Merkle consistency proof for a Merkle Tree Hash MTH(D_n) and a
previously advertised hash MTH(D[0:m]) of the first m leaves, m <= n,
is the list of nodes in the Merkle Tree required to verify that the
first m inputs D[0:m] are equal in both trees. Thus, a consistency
proof must contain a set of intermediate nodes (i.e., commitments to
inputs) sufficient to verify MTH(D_n), such that (a subset of) the
same nodes can be used to verify MTH(D[0:m]). We define an algorithm
that outputs the (unique) minimal consistency proof.
2.1.4.1. Generating a Consistency Proof
Given an ordered list of n inputs to the tree, D_n = {d[0], d[1],
..., d[n-1]}, the Merkle consistency proof PROOF(m, D_n) for a
previous Merkle Tree Hash MTH(D[0:m]), 0 < m < n, is defined as:
Laurie, et al. Expires 14 November 2021 [Page 10]
Internet-Draft Certificate Transparency Version 2.0 May 2021
PROOF(m, D_n) = SUBPROOF(m, D_n, true)
In SUBPROOF, the boolean value represents whether the subtree created
from D[0:m] is a complete subtree of the Merkle Tree created from
D_n, and, consequently, whether the subtree Merkle Tree Hash
MTH(D[0:m]) is known. The initial call to SUBPROOF sets this to be
true, and SUBPROOF is then defined as follows:
The subproof for m = n is empty if m is the value for which PROOF was
originally requested (meaning that the subtree created from D[0:m] is
a complete subtree of the Merkle Tree created from the original D_n
for which PROOF was requested, and the subtree Merkle Tree Hash
MTH(D[0:m]) is known):
SUBPROOF(m, D_m, true) = {}
Otherwise, the subproof for m = n is the Merkle Tree Hash committing
inputs D[0:m]:
SUBPROOF(m, D_m, false) = {MTH(D_m)}
For m < n, let k be the largest power of two smaller than n. The
subproof is then defined recursively, using the appropriate step
below:
If m <= k, the right subtree entries D[k:n] only exist in the current
tree. We prove that the left subtree entries D[0:k] are consistent
and add a commitment to D[k:n]:
SUBPROOF(m, D_n, b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
If m > k, the left subtree entries D[0:k] are identical in both
trees. We prove that the right subtree entries D[k:n] are consistent
and add a commitment to D[0:k].
SUBPROOF(m, D_n, b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])
The number of nodes in the resulting proof is bounded above by
ceil(log2(n)) + 1.
The : operator and D[k1:k2] are defined the same as in Section 2.1.1.
Laurie, et al. Expires 14 November 2021 [Page 11]
Internet-Draft Certificate Transparency Version 2.0 May 2021
2.1.4.2. Verifying Consistency between Two Tree Heads
When a client has a tree head "first_hash" for tree size "first", a
tree head "second_hash" for tree size "second" where "0 < first <
second", and has received a consistency proof between the two (e.g.,
in a "TransItem" of type "consistency_proof_v2"), the following
algorithm may be used to verify the consistency proof:
1. If "consistency_path" is an empty array, stop and fail the proof
verification.
2. If "first" is an exact power of 2, then prepend "first_hash" to
the "consistency_path" array.
3. Set "fn" to "first - 1" and "sn" to "second - 1".
4. If "LSB(fn)" is set, then right-shift both "fn" and "sn" equally
until "LSB(fn)" is not set.
5. Set both "fr" and "sr" to the first value in the
"consistency_path" array.
6. For each subsequent value "c" in the "consistency_path" array:
If "sn" is 0, stop the iteration and fail the proof verification.
If "LSB(fn)" is set, or if "fn" is equal to "sn", then:
1. Set "fr" to "HASH(0x01 || c || fr)"
Set "sr" to "HASH(0x01 || c || sr)"
2. If "LSB(fn)" is not set, then right-shift both "fn" and "sn"
equally until either "LSB(fn)" is set or "fn" is "0".
Otherwise:
1. Set "sr" to "HASH(0x01 || sr || c)"
Finally, right-shift both "fn" and "sn" one time.
7. After completing iterating through the "consistency_path" array
as described above, verify that the "fr" calculated is equal to
the "first_hash" supplied, that the "sr" calculated is equal to
the "second_hash" supplied and that "sn" is 0.
Laurie, et al. Expires 14 November 2021 [Page 12]
Internet-Draft Certificate Transparency Version 2.0 May 2021
2.1.5. Example
The binary Merkle Tree with 7 leaves:
hash
/ \
/ \
/ \
/ \
/ \
k l
/ \ / \
/ \ / \
/ \ / \
g h i j
/ \ / \ / \ |
a b c d e f d6
| | | | | |
d0 d1 d2 d3 d4 d5
The inclusion proof for d0 is [b, h, l].
The inclusion proof for d3 is [c, g, l].
The inclusion proof for d4 is [f, j, k].
The inclusion proof for d6 is [i, k].
The same tree, built incrementally in four steps:
Laurie, et al. Expires 14 November 2021 [Page 13]
Internet-Draft Certificate Transparency Version 2.0 May 2021
hash0 hash1=k
/ \ / \
/ \ / \
/ \ / \
g c g h
/ \ | / \ / \
a b d2 a b c d
| | | | | |
d0 d1 d0 d1 d2 d3
hash2 hash
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
k i k l
/ \ / \ / \ / \
/ \ e f / \ / \
/ \ | | / \ / \
g h d4 d5 g h i j
/ \ / \ / \ / \ / \ |
a b c d a b c d e f d6
| | | | | | | | | |
d0 d1 d2 d3 d0 d1 d2 d3 d4 d5
The consistency proof between hash0 and hash is PROOF(3, D[7]) = [c,
d, g, l]. c, g are used to verify hash0, and d, l are additionally
used to show hash is consistent with hash0.
The consistency proof between hash1 and hash is PROOF(4, D[7]) = [l].
hash can be verified using hash1=k and l.
The consistency proof between hash2 and hash is PROOF(6, D[7]) = [i,
j, k]. k, i are used to verify hash2, and j is additionally used to
show hash is consistent with hash2.
2.2. Signatures
When signing data structures, a log MUST use one of the signature
algorithms from the IANA CT Signature Algorithms registry, described
in Section 10.3.
Laurie, et al. Expires 14 November 2021 [Page 14]
Internet-Draft Certificate Transparency Version 2.0 May 2021
3. Submitters
Submitters submit certificates or preannouncements of certificates
prior to issuance (precertificates) to logs for public auditing, as
described below. In order to enable attribution of each logged
certificate or precertificate to its issuer, each submission MUST be
accompanied by all additional certificates required to verify the
chain up to an accepted trust anchor (Section 5.7). The trust anchor
(a root or intermediate CA certificate) MAY be omitted from the
submission.
If a log accepts a submission, it will return a Signed Certificate
Timestamp (SCT) (see Section 4.8). The submitter SHOULD validate the
returned SCT as described in Section 8.1 if they understand its
format and they intend to use it directly in a TLS handshake or to
construct a certificate. If the submitter does not need the SCT (for
example, the certificate is being submitted simply to make it
available in the log), it MAY validate the SCT.
3.1. Certificates
Any entity can submit a certificate (Section 5.1) to a log. Since it
is anticipated that TLS clients will reject certificates that are not
logged, it is expected that certificate issuers and subjects will be
strongly motivated to submit them.
3.2. Precertificates
CAs may preannounce a certificate prior to issuance by submitting a
precertificate (Section 5.1) that the log can use to create an entry
that will be valid against the issued certificate. The CA MAY
incorporate the returned SCT in the issued certificate. One example
of where the returned SCT is not incorporated in the issued
certificate is when a CA sends the precertificate to multiple logs,
but only incorporates the SCTs that are returned first.
A precertificate is a CMS [RFC5652] "signed-data" object that
conforms to the following profile:
* It MUST be DER encoded as described in [X690].
* "SignedData.version" MUST be v3(3).
* "SignedData.digestAlgorithms" MUST be the same as the
"SignerInfo.digestAlgorithm" OID value (see below).
* "SignedData.encapContentInfo":
Laurie, et al. Expires 14 November 2021 [Page 15]
Internet-Draft Certificate Transparency Version 2.0 May 2021
- "eContentType" MUST be the OID 1.3.101.78.
- "eContent" MUST contain a TBSCertificate [RFC5280] that will be
identical to the TBSCertificate in the issued certificate,
except that the Transparency Information (Section 7.1)
extension MUST be omitted.
* "SignedData.certificates" MUST be omitted.
* "SignedData.crls" MUST be omitted.
* "SignedData.signerInfos" MUST contain one "SignerInfo":
- "version" MUST be v3(3).
- "sid" MUST use the "subjectKeyIdentifier" option.
- "digestAlgorithm" MUST be one of the hash algorithm OIDs listed
in the IANA CT Hash Algorithms Registry, described in
Section 10.2.
- "signedAttrs" MUST be present and MUST contain two attributes:
o A content-type attribute whose value is the same as
"SignedData.encapContentInfo.eContentType".
o A message-digest attribute whose value is the message digest
of "SignedData.encapContentInfo.eContent".
- "signatureAlgorithm" MUST be the same OID as
"TBSCertificate.signature".
- "signature" MUST be from the same (root or intermediate) CA
that intends to issue the corresponding certificate (see
Section 3.2.1).
- "unsignedAttrs" MUST be omitted.
"SignerInfo.signedAttrs" is included in the message digest
calculation process (see Section 5.4 of [RFC5652]), which ensures
that the "SignerInfo.signature" value will not be a valid X.509v3
signature that could be used in conjunction with the TBSCertificate
(from "SignedData.encapContentInfo.eContent") to construct a valid
certificate.
Laurie, et al. Expires 14 November 2021 [Page 16]
Internet-Draft Certificate Transparency Version 2.0 May 2021
3.2.1. Binding Intent to Issue
Under normal circumstances, there will be a short delay between
precertificate submission and issuance of the corresponding
certificate. Longer delays are to be expected occasionally (e.g.,
due to log server downtime), and in some cases the CA might not
actually issue the corresponding certificate. Nevertheless, a
precertificate's "signature" indicates the CA's binding intent to
issue the corresponding certificate, which means that:
* Misissuance of a precertificate is considered equivalent to
misissuance of the corresponding certificate. The CA should
expect to be held to account, even if the corresponding
certificate has not actually been issued.
* Upon observing a precertificate, a client can reasonably presume
that the corresponding certificate has been issued. A client may
wish to obtain status information (e.g., by using the Online
Certificate Status Protocol [RFC6960] or by checking a Certificate
Revocation List [RFC5280]) about a certificate that is presumed to
exist, especially if there is evidence or suspicion that the
corresponding precertificate was misissued.
* TLS clients may have policies that require CAs to be able to
revoke, and to provide certificate status services for, each
certificate that is presumed to exist based on the existence of a
corresponding precertificate.
4. Log Format and Operation
A log is a single, append-only Merkle Tree of submitted certificate
and precertificate entries.
When it receives and accepts a valid submission, the log MUST return
an SCT that corresponds to the submitted certificate or
precertificate. If the log has previously seen this valid
submission, it SHOULD return the same SCT as it returned before, as
discussed in Section 11.3. If different SCTs are produced for the
same submission, multiple log entries will have to be created, one
for each SCT (as the timestamp is a part of the leaf structure).
Note that if a certificate was previously logged as a precertificate,
then the precertificate's SCT of type "precert_sct_v2" would not be
appropriate; instead, a fresh SCT of type "x509_sct_v2" should be
generated.
Laurie, et al. Expires 14 November 2021 [Page 17]
Internet-Draft Certificate Transparency Version 2.0 May 2021
An SCT is the log's promise to append to its Merkle Tree an entry for
the accepted submission. Upon producing an SCT, the log MUST fulfil
this promise by performing the following actions within a fixed
amount of time known as the Maximum Merge Delay (MMD), which is one
of the log's parameters (see Section 4.1):
* Allocate a tree index to the entry representing the accepted
submission.
* Calculate the root of the tree.
* Sign the root of the tree (see Section 4.10).
The log may append multiple entries before signing the root of the
tree.
Log operators SHOULD NOT impose any conditions on retrieving or
sharing data from the log.
4.1. Log Parameters
A log is defined by a collection of immutable parameters, which are
used by clients to communicate with the log and to verify log
artifacts. Except for the Final Signed Tree Head (STH), each of
these parameters MUST be established before the log operator begins
to operate the log.
Base URL: The prefix used to construct URLs ([RFC3986]) for client
messages (see Section 5). The base URL MUST be an "https" URL,
MAY contain a port, MAY contain a path with any number of path
segments, but MUST NOT contain a query string, fragment, or
trailing "/". Example: https://ct.example.org/blue
Hash Algorithm: The hash algorithm used for the Merkle Tree (see
Section 10.2).
Signature Algorithm: The signature algorithm used (see Section 2.2).
Public Key: The public key used to verify signatures generated by
the log. A log MUST NOT use the same keypair as any other log.
Log ID: The OID that uniquely identifies the log.
Maximum Merge Delay: The MMD the log has committed to. This