1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/crypto/cert_compressor.h"
6
7 #include <cstdint>
8 #include <memory>
9 #include <string>
10 #include <utility>
11
12 #include "absl/strings/string_view.h"
13 #include "quiche/quic/core/quic_utils.h"
14 #include "quiche/quic/platform/api/quic_bug_tracker.h"
15 #include "quiche/quic/platform/api/quic_flag_utils.h"
16 #include "quiche/quic/platform/api/quic_flags.h"
17 #include "zlib.h"
18
19 namespace quic {
20
21 namespace {
22
23 // kCommonCertSubstrings contains ~1500 bytes of common certificate substrings
24 // in order to help zlib. This was generated via a fairly dumb algorithm from
25 // the Alexa Top 5000 set - we could probably do better.
26 static const unsigned char kCommonCertSubstrings[] = {
27 0x04, 0x02, 0x30, 0x00, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x1d, 0x25, 0x04,
28 0x16, 0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03,
29 0x01, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03, 0x02, 0x30,
30 0x5f, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x86, 0xf8, 0x42, 0x04, 0x01,
31 0x06, 0x06, 0x0b, 0x60, 0x86, 0x48, 0x01, 0x86, 0xfd, 0x6d, 0x01, 0x07,
32 0x17, 0x01, 0x30, 0x33, 0x20, 0x45, 0x78, 0x74, 0x65, 0x6e, 0x64, 0x65,
33 0x64, 0x20, 0x56, 0x61, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x69, 0x6f, 0x6e,
34 0x20, 0x53, 0x20, 0x4c, 0x69, 0x6d, 0x69, 0x74, 0x65, 0x64, 0x31, 0x34,
35 0x20, 0x53, 0x53, 0x4c, 0x20, 0x43, 0x41, 0x30, 0x1e, 0x17, 0x0d, 0x31,
36 0x32, 0x20, 0x53, 0x65, 0x63, 0x75, 0x72, 0x65, 0x20, 0x53, 0x65, 0x72,
37 0x76, 0x65, 0x72, 0x20, 0x43, 0x41, 0x30, 0x2d, 0x61, 0x69, 0x61, 0x2e,
38 0x76, 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d,
39 0x2f, 0x45, 0x2d, 0x63, 0x72, 0x6c, 0x2e, 0x76, 0x65, 0x72, 0x69, 0x73,
40 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x45, 0x2e, 0x63, 0x65,
41 0x72, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01,
42 0x01, 0x05, 0x05, 0x00, 0x03, 0x82, 0x01, 0x01, 0x00, 0x4a, 0x2e, 0x63,
43 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x73, 0x6f, 0x75, 0x72, 0x63, 0x65, 0x73,
44 0x2f, 0x63, 0x70, 0x73, 0x20, 0x28, 0x63, 0x29, 0x30, 0x30, 0x09, 0x06,
45 0x03, 0x55, 0x1d, 0x13, 0x04, 0x02, 0x30, 0x00, 0x30, 0x1d, 0x30, 0x0d,
46 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x05, 0x05,
47 0x00, 0x03, 0x82, 0x01, 0x01, 0x00, 0x7b, 0x30, 0x1d, 0x06, 0x03, 0x55,
48 0x1d, 0x0e, 0x30, 0x82, 0x01, 0x22, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86,
49 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x01, 0x05, 0x00, 0x03, 0x82, 0x01,
50 0x0f, 0x00, 0x30, 0x82, 0x01, 0x0a, 0x02, 0x82, 0x01, 0x01, 0x00, 0xd2,
51 0x6f, 0x64, 0x6f, 0x63, 0x61, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x43, 0x2e,
52 0x63, 0x72, 0x6c, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x1d, 0x0e, 0x04, 0x16,
53 0x04, 0x14, 0xb4, 0x2e, 0x67, 0x6c, 0x6f, 0x62, 0x61, 0x6c, 0x73, 0x69,
54 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x30, 0x0b, 0x06, 0x03,
55 0x55, 0x1d, 0x0f, 0x04, 0x04, 0x03, 0x02, 0x01, 0x30, 0x0d, 0x06, 0x09,
56 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x05, 0x05, 0x00, 0x30,
57 0x81, 0xca, 0x31, 0x0b, 0x30, 0x09, 0x06, 0x03, 0x55, 0x04, 0x06, 0x13,
58 0x02, 0x55, 0x53, 0x31, 0x10, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x04, 0x08,
59 0x13, 0x07, 0x41, 0x72, 0x69, 0x7a, 0x6f, 0x6e, 0x61, 0x31, 0x13, 0x30,
60 0x11, 0x06, 0x03, 0x55, 0x04, 0x07, 0x13, 0x0a, 0x53, 0x63, 0x6f, 0x74,
61 0x74, 0x73, 0x64, 0x61, 0x6c, 0x65, 0x31, 0x1a, 0x30, 0x18, 0x06, 0x03,
62 0x55, 0x04, 0x0a, 0x13, 0x11, 0x47, 0x6f, 0x44, 0x61, 0x64, 0x64, 0x79,
63 0x2e, 0x63, 0x6f, 0x6d, 0x2c, 0x20, 0x49, 0x6e, 0x63, 0x2e, 0x31, 0x33,
64 0x30, 0x31, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x2a, 0x68, 0x74, 0x74,
65 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x65, 0x72, 0x74, 0x69, 0x66, 0x69, 0x63,
66 0x61, 0x74, 0x65, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79,
67 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74,
68 0x6f, 0x72, 0x79, 0x31, 0x30, 0x30, 0x2e, 0x06, 0x03, 0x55, 0x04, 0x03,
69 0x13, 0x27, 0x47, 0x6f, 0x20, 0x44, 0x61, 0x64, 0x64, 0x79, 0x20, 0x53,
70 0x65, 0x63, 0x75, 0x72, 0x65, 0x20, 0x43, 0x65, 0x72, 0x74, 0x69, 0x66,
71 0x69, 0x63, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x20, 0x41, 0x75, 0x74, 0x68,
72 0x6f, 0x72, 0x69, 0x74, 0x79, 0x31, 0x11, 0x30, 0x0f, 0x06, 0x03, 0x55,
73 0x04, 0x05, 0x13, 0x08, 0x30, 0x37, 0x39, 0x36, 0x39, 0x32, 0x38, 0x37,
74 0x30, 0x1e, 0x17, 0x0d, 0x31, 0x31, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x1d,
75 0x0f, 0x01, 0x01, 0xff, 0x04, 0x04, 0x03, 0x02, 0x05, 0xa0, 0x30, 0x0c,
76 0x06, 0x03, 0x55, 0x1d, 0x13, 0x01, 0x01, 0xff, 0x04, 0x02, 0x30, 0x00,
77 0x30, 0x1d, 0x30, 0x0f, 0x06, 0x03, 0x55, 0x1d, 0x13, 0x01, 0x01, 0xff,
78 0x04, 0x05, 0x30, 0x03, 0x01, 0x01, 0x00, 0x30, 0x1d, 0x06, 0x03, 0x55,
79 0x1d, 0x25, 0x04, 0x16, 0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05,
80 0x05, 0x07, 0x03, 0x01, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07,
81 0x03, 0x02, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x1d, 0x0f, 0x01, 0x01, 0xff,
82 0x04, 0x04, 0x03, 0x02, 0x05, 0xa0, 0x30, 0x33, 0x06, 0x03, 0x55, 0x1d,
83 0x1f, 0x04, 0x2c, 0x30, 0x2a, 0x30, 0x28, 0xa0, 0x26, 0xa0, 0x24, 0x86,
84 0x22, 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x72, 0x6c, 0x2e,
85 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f,
86 0x67, 0x64, 0x73, 0x31, 0x2d, 0x32, 0x30, 0x2a, 0x30, 0x28, 0x06, 0x08,
87 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x02, 0x01, 0x16, 0x1c, 0x68, 0x74,
88 0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x77, 0x77, 0x77, 0x2e, 0x76, 0x65,
89 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x63,
90 0x70, 0x73, 0x30, 0x34, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x5a, 0x17,
91 0x0d, 0x31, 0x33, 0x30, 0x35, 0x30, 0x39, 0x06, 0x08, 0x2b, 0x06, 0x01,
92 0x05, 0x05, 0x07, 0x30, 0x02, 0x86, 0x2d, 0x68, 0x74, 0x74, 0x70, 0x3a,
93 0x2f, 0x2f, 0x73, 0x30, 0x39, 0x30, 0x37, 0x06, 0x08, 0x2b, 0x06, 0x01,
94 0x05, 0x05, 0x07, 0x02, 0x30, 0x44, 0x06, 0x03, 0x55, 0x1d, 0x20, 0x04,
95 0x3d, 0x30, 0x3b, 0x30, 0x39, 0x06, 0x0b, 0x60, 0x86, 0x48, 0x01, 0x86,
96 0xf8, 0x45, 0x01, 0x07, 0x17, 0x06, 0x31, 0x0b, 0x30, 0x09, 0x06, 0x03,
97 0x55, 0x04, 0x06, 0x13, 0x02, 0x47, 0x42, 0x31, 0x1b, 0x53, 0x31, 0x17,
98 0x30, 0x15, 0x06, 0x03, 0x55, 0x04, 0x0a, 0x13, 0x0e, 0x56, 0x65, 0x72,
99 0x69, 0x53, 0x69, 0x67, 0x6e, 0x2c, 0x20, 0x49, 0x6e, 0x63, 0x2e, 0x31,
100 0x1f, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x16, 0x56, 0x65,
101 0x72, 0x69, 0x53, 0x69, 0x67, 0x6e, 0x20, 0x54, 0x72, 0x75, 0x73, 0x74,
102 0x20, 0x4e, 0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b, 0x31, 0x3b, 0x30, 0x39,
103 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x32, 0x54, 0x65, 0x72, 0x6d, 0x73,
104 0x20, 0x6f, 0x66, 0x20, 0x75, 0x73, 0x65, 0x20, 0x61, 0x74, 0x20, 0x68,
105 0x74, 0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x77, 0x77, 0x77, 0x2e, 0x76,
106 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f,
107 0x72, 0x70, 0x61, 0x20, 0x28, 0x63, 0x29, 0x30, 0x31, 0x10, 0x30, 0x0e,
108 0x06, 0x03, 0x55, 0x04, 0x07, 0x13, 0x07, 0x53, 0x31, 0x13, 0x30, 0x11,
109 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x0a, 0x47, 0x31, 0x13, 0x30, 0x11,
110 0x06, 0x0b, 0x2b, 0x06, 0x01, 0x04, 0x01, 0x82, 0x37, 0x3c, 0x02, 0x01,
111 0x03, 0x13, 0x02, 0x55, 0x31, 0x16, 0x30, 0x14, 0x06, 0x03, 0x55, 0x04,
112 0x03, 0x14, 0x31, 0x19, 0x30, 0x17, 0x06, 0x03, 0x55, 0x04, 0x03, 0x13,
113 0x31, 0x1d, 0x30, 0x1b, 0x06, 0x03, 0x55, 0x04, 0x0f, 0x13, 0x14, 0x50,
114 0x72, 0x69, 0x76, 0x61, 0x74, 0x65, 0x20, 0x4f, 0x72, 0x67, 0x61, 0x6e,
115 0x69, 0x7a, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x31, 0x12, 0x31, 0x21, 0x30,
116 0x1f, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x18, 0x44, 0x6f, 0x6d, 0x61,
117 0x69, 0x6e, 0x20, 0x43, 0x6f, 0x6e, 0x74, 0x72, 0x6f, 0x6c, 0x20, 0x56,
118 0x61, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x65, 0x64, 0x31, 0x14, 0x31, 0x31,
119 0x30, 0x2f, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x28, 0x53, 0x65, 0x65,
120 0x20, 0x77, 0x77, 0x77, 0x2e, 0x72, 0x3a, 0x2f, 0x2f, 0x73, 0x65, 0x63,
121 0x75, 0x72, 0x65, 0x2e, 0x67, 0x47, 0x6c, 0x6f, 0x62, 0x61, 0x6c, 0x53,
122 0x69, 0x67, 0x6e, 0x31, 0x53, 0x65, 0x72, 0x76, 0x65, 0x72, 0x43, 0x41,
123 0x2e, 0x63, 0x72, 0x6c, 0x56, 0x65, 0x72, 0x69, 0x53, 0x69, 0x67, 0x6e,
124 0x20, 0x43, 0x6c, 0x61, 0x73, 0x73, 0x20, 0x33, 0x20, 0x45, 0x63, 0x72,
125 0x6c, 0x2e, 0x67, 0x65, 0x6f, 0x74, 0x72, 0x75, 0x73, 0x74, 0x2e, 0x63,
126 0x6f, 0x6d, 0x2f, 0x63, 0x72, 0x6c, 0x73, 0x2f, 0x73, 0x64, 0x31, 0x1a,
127 0x30, 0x18, 0x06, 0x03, 0x55, 0x04, 0x0a, 0x68, 0x74, 0x74, 0x70, 0x3a,
128 0x2f, 0x2f, 0x45, 0x56, 0x49, 0x6e, 0x74, 0x6c, 0x2d, 0x63, 0x63, 0x72,
129 0x74, 0x2e, 0x67, 0x77, 0x77, 0x77, 0x2e, 0x67, 0x69, 0x63, 0x65, 0x72,
130 0x74, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x31, 0x6f, 0x63, 0x73, 0x70, 0x2e,
131 0x76, 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d,
132 0x30, 0x39, 0x72, 0x61, 0x70, 0x69, 0x64, 0x73, 0x73, 0x6c, 0x2e, 0x63,
133 0x6f, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63,
134 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74, 0x6f, 0x72,
135 0x79, 0x2f, 0x30, 0x81, 0x80, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05,
136 0x07, 0x01, 0x01, 0x04, 0x74, 0x30, 0x72, 0x30, 0x24, 0x06, 0x08, 0x2b,
137 0x06, 0x01, 0x05, 0x05, 0x07, 0x30, 0x01, 0x86, 0x18, 0x68, 0x74, 0x74,
138 0x70, 0x3a, 0x2f, 0x2f, 0x6f, 0x63, 0x73, 0x70, 0x2e, 0x67, 0x6f, 0x64,
139 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x30, 0x4a, 0x06,
140 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x30, 0x02, 0x86, 0x3e, 0x68,
141 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x65, 0x72, 0x74, 0x69, 0x66,
142 0x69, 0x63, 0x61, 0x74, 0x65, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64,
143 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73,
144 0x69, 0x74, 0x6f, 0x72, 0x79, 0x2f, 0x67, 0x64, 0x5f, 0x69, 0x6e, 0x74,
145 0x65, 0x72, 0x6d, 0x65, 0x64, 0x69, 0x61, 0x74, 0x65, 0x2e, 0x63, 0x72,
146 0x74, 0x30, 0x1f, 0x06, 0x03, 0x55, 0x1d, 0x23, 0x04, 0x18, 0x30, 0x16,
147 0x80, 0x14, 0xfd, 0xac, 0x61, 0x32, 0x93, 0x6c, 0x45, 0xd6, 0xe2, 0xee,
148 0x85, 0x5f, 0x9a, 0xba, 0xe7, 0x76, 0x99, 0x68, 0xcc, 0xe7, 0x30, 0x27,
149 0x86, 0x29, 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x86, 0x30,
150 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x73,
151 };
152
153 // CertEntry represents a certificate in compressed form. Each entry is one of
154 // the three types enumerated in |Type|.
155 struct CertEntry {
156 public:
157 enum Type {
158 // Type 0 is reserved to mean "end of list" in the wire format.
159
160 // COMPRESSED means that the certificate is included in the trailing zlib
161 // data.
162 COMPRESSED = 1,
163 // CACHED means that the certificate is already known to the peer and will
164 // be replaced by its 64-bit hash (in |hash|).
165 CACHED = 2,
166 };
167
168 Type type;
169 uint64_t hash;
170 uint64_t set_hash;
171 uint32_t index;
172 };
173
174 // MatchCerts returns a vector of CertEntries describing how to most
175 // efficiently represent |certs| to a peer who has cached the certificates
176 // with the 64-bit, FNV-1a hashes in |client_cached_cert_hashes|.
MatchCerts(const std::vector<std::string> & certs,absl::string_view client_cached_cert_hashes)177 std::vector<CertEntry> MatchCerts(const std::vector<std::string>& certs,
178 absl::string_view client_cached_cert_hashes) {
179 std::vector<CertEntry> entries;
180 entries.reserve(certs.size());
181
182 const bool cached_valid =
183 client_cached_cert_hashes.size() % sizeof(uint64_t) == 0 &&
184 !client_cached_cert_hashes.empty();
185
186 for (auto i = certs.begin(); i != certs.end(); ++i) {
187 CertEntry entry;
188
189 if (cached_valid) {
190 bool cached = false;
191
192 uint64_t hash = QuicUtils::FNV1a_64_Hash(*i);
193 // This assumes that the machine is little-endian.
194 for (size_t j = 0; j < client_cached_cert_hashes.size();
195 j += sizeof(uint64_t)) {
196 uint64_t cached_hash;
197 memcpy(&cached_hash, client_cached_cert_hashes.data() + j,
198 sizeof(uint64_t));
199 if (hash != cached_hash) {
200 continue;
201 }
202
203 entry.type = CertEntry::CACHED;
204 entry.hash = hash;
205 entries.push_back(entry);
206 cached = true;
207 break;
208 }
209
210 if (cached) {
211 continue;
212 }
213 }
214
215 entry.type = CertEntry::COMPRESSED;
216 entries.push_back(entry);
217 }
218
219 return entries;
220 }
221
222 // CertEntriesSize returns the size, in bytes, of the serialised form of
223 // |entries|.
CertEntriesSize(const std::vector<CertEntry> & entries)224 size_t CertEntriesSize(const std::vector<CertEntry>& entries) {
225 size_t entries_size = 0;
226
227 for (auto i = entries.begin(); i != entries.end(); ++i) {
228 entries_size++;
229 switch (i->type) {
230 case CertEntry::COMPRESSED:
231 break;
232 case CertEntry::CACHED:
233 entries_size += sizeof(uint64_t);
234 break;
235 }
236 }
237
238 entries_size++; // for end marker
239
240 return entries_size;
241 }
242
243 // SerializeCertEntries serialises |entries| to |out|, which must have enough
244 // space to contain them.
SerializeCertEntries(uint8_t * out,const std::vector<CertEntry> & entries)245 void SerializeCertEntries(uint8_t* out, const std::vector<CertEntry>& entries) {
246 for (auto i = entries.begin(); i != entries.end(); ++i) {
247 *out++ = static_cast<uint8_t>(i->type);
248 switch (i->type) {
249 case CertEntry::COMPRESSED:
250 break;
251 case CertEntry::CACHED:
252 memcpy(out, &i->hash, sizeof(i->hash));
253 out += sizeof(uint64_t);
254 break;
255 }
256 }
257
258 *out++ = 0; // end marker
259 }
260
261 // ZlibDictForEntries returns a string that contains the zlib pre-shared
262 // dictionary to use in order to decompress a zlib block following |entries|.
263 // |certs| is one-to-one with |entries| and contains the certificates for those
264 // entries that are CACHED.
ZlibDictForEntries(const std::vector<CertEntry> & entries,const std::vector<std::string> & certs)265 std::string ZlibDictForEntries(const std::vector<CertEntry>& entries,
266 const std::vector<std::string>& certs) {
267 std::string zlib_dict;
268
269 // The dictionary starts with the cached certs in reverse order.
270 size_t zlib_dict_size = 0;
271 for (size_t i = certs.size() - 1; i < certs.size(); i--) {
272 if (entries[i].type != CertEntry::COMPRESSED) {
273 zlib_dict_size += certs[i].size();
274 }
275 }
276
277 // At the end of the dictionary is a block of common certificate substrings.
278 zlib_dict_size += sizeof(kCommonCertSubstrings);
279
280 zlib_dict.reserve(zlib_dict_size);
281
282 for (size_t i = certs.size() - 1; i < certs.size(); i--) {
283 if (entries[i].type != CertEntry::COMPRESSED) {
284 zlib_dict += certs[i];
285 }
286 }
287
288 zlib_dict += std::string(reinterpret_cast<const char*>(kCommonCertSubstrings),
289 sizeof(kCommonCertSubstrings));
290
291 QUICHE_DCHECK_EQ(zlib_dict.size(), zlib_dict_size);
292
293 return zlib_dict;
294 }
295
296 // HashCerts returns the FNV-1a hashes of |certs|.
HashCerts(const std::vector<std::string> & certs)297 std::vector<uint64_t> HashCerts(const std::vector<std::string>& certs) {
298 std::vector<uint64_t> ret;
299 ret.reserve(certs.size());
300
301 for (auto i = certs.begin(); i != certs.end(); ++i) {
302 ret.push_back(QuicUtils::FNV1a_64_Hash(*i));
303 }
304
305 return ret;
306 }
307
308 // ParseEntries parses the serialised form of a vector of CertEntries from
309 // |in_out| and writes them to |out_entries|. CACHED entries are resolved using
310 // |cached_certs| and written to |out_certs|. |in_out| is updated to contain
311 // the trailing data.
ParseEntries(absl::string_view * in_out,const std::vector<std::string> & cached_certs,std::vector<CertEntry> * out_entries,std::vector<std::string> * out_certs)312 bool ParseEntries(absl::string_view* in_out,
313 const std::vector<std::string>& cached_certs,
314 std::vector<CertEntry>* out_entries,
315 std::vector<std::string>* out_certs) {
316 absl::string_view in = *in_out;
317 std::vector<uint64_t> cached_hashes;
318
319 out_entries->clear();
320 out_certs->clear();
321
322 for (;;) {
323 if (in.empty()) {
324 return false;
325 }
326 CertEntry entry;
327 const uint8_t type_byte = in[0];
328 in.remove_prefix(1);
329
330 if (type_byte == 0) {
331 break;
332 }
333
334 entry.type = static_cast<CertEntry::Type>(type_byte);
335
336 switch (entry.type) {
337 case CertEntry::COMPRESSED:
338 out_certs->push_back(std::string());
339 break;
340 case CertEntry::CACHED: {
341 if (in.size() < sizeof(uint64_t)) {
342 return false;
343 }
344 memcpy(&entry.hash, in.data(), sizeof(uint64_t));
345 in.remove_prefix(sizeof(uint64_t));
346
347 if (cached_hashes.size() != cached_certs.size()) {
348 cached_hashes = HashCerts(cached_certs);
349 }
350 bool found = false;
351 for (size_t i = 0; i < cached_hashes.size(); i++) {
352 if (cached_hashes[i] == entry.hash) {
353 out_certs->push_back(cached_certs[i]);
354 found = true;
355 break;
356 }
357 }
358 if (!found) {
359 return false;
360 }
361 break;
362 }
363
364 default:
365 return false;
366 }
367 out_entries->push_back(entry);
368 }
369
370 *in_out = in;
371 return true;
372 }
373
374 // ScopedZLib deals with the automatic destruction of a zlib context.
375 class ScopedZLib {
376 public:
377 enum Type {
378 INFLATE,
379 DEFLATE,
380 };
381
ScopedZLib(Type type)382 explicit ScopedZLib(Type type) : z_(nullptr), type_(type) {}
383
reset(z_stream * z)384 void reset(z_stream* z) {
385 Clear();
386 z_ = z;
387 }
388
~ScopedZLib()389 ~ScopedZLib() { Clear(); }
390
391 private:
Clear()392 void Clear() {
393 if (!z_) {
394 return;
395 }
396
397 if (type_ == DEFLATE) {
398 deflateEnd(z_);
399 } else {
400 inflateEnd(z_);
401 }
402 z_ = nullptr;
403 }
404
405 z_stream* z_;
406 const Type type_;
407 };
408
409 } // anonymous namespace
410
411 // static
CompressChain(const std::vector<std::string> & certs,absl::string_view client_cached_cert_hashes)412 std::string CertCompressor::CompressChain(
413 const std::vector<std::string>& certs,
414 absl::string_view client_cached_cert_hashes) {
415 const std::vector<CertEntry> entries =
416 MatchCerts(certs, client_cached_cert_hashes);
417 QUICHE_DCHECK_EQ(entries.size(), certs.size());
418
419 size_t uncompressed_size = 0;
420 for (size_t i = 0; i < entries.size(); i++) {
421 if (entries[i].type == CertEntry::COMPRESSED) {
422 uncompressed_size += 4 /* uint32_t length */ + certs[i].size();
423 }
424 }
425
426 size_t compressed_size = 0;
427 z_stream z;
428 ScopedZLib scoped_z(ScopedZLib::DEFLATE);
429
430 if (uncompressed_size > 0) {
431 memset(&z, 0, sizeof(z));
432 int rv = deflateInit(&z, Z_DEFAULT_COMPRESSION);
433 QUICHE_DCHECK_EQ(Z_OK, rv);
434 if (rv != Z_OK) {
435 return "";
436 }
437 scoped_z.reset(&z);
438
439 std::string zlib_dict = ZlibDictForEntries(entries, certs);
440
441 rv = deflateSetDictionary(
442 &z, reinterpret_cast<const uint8_t*>(&zlib_dict[0]), zlib_dict.size());
443 QUICHE_DCHECK_EQ(Z_OK, rv);
444 if (rv != Z_OK) {
445 return "";
446 }
447
448 compressed_size = deflateBound(&z, uncompressed_size);
449 }
450
451 const size_t entries_size = CertEntriesSize(entries);
452
453 std::string result;
454 result.resize(entries_size + (uncompressed_size > 0 ? 4 : 0) +
455 compressed_size);
456
457 uint8_t* j = reinterpret_cast<uint8_t*>(&result[0]);
458 SerializeCertEntries(j, entries);
459 j += entries_size;
460
461 if (uncompressed_size == 0) {
462 return result;
463 }
464
465 uint32_t uncompressed_size_32 = uncompressed_size;
466 memcpy(j, &uncompressed_size_32, sizeof(uint32_t));
467 j += sizeof(uint32_t);
468
469 int rv;
470
471 z.next_out = j;
472 z.avail_out = compressed_size;
473
474 for (size_t i = 0; i < certs.size(); i++) {
475 if (entries[i].type != CertEntry::COMPRESSED) {
476 continue;
477 }
478
479 uint32_t length32 = certs[i].size();
480 z.next_in = reinterpret_cast<uint8_t*>(&length32);
481 z.avail_in = sizeof(length32);
482 rv = deflate(&z, Z_NO_FLUSH);
483 QUICHE_DCHECK_EQ(Z_OK, rv);
484 QUICHE_DCHECK_EQ(0u, z.avail_in);
485 if (rv != Z_OK || z.avail_in) {
486 return "";
487 }
488
489 z.next_in =
490 const_cast<uint8_t*>(reinterpret_cast<const uint8_t*>(certs[i].data()));
491 z.avail_in = certs[i].size();
492 rv = deflate(&z, Z_NO_FLUSH);
493 QUICHE_DCHECK_EQ(Z_OK, rv);
494 QUICHE_DCHECK_EQ(0u, z.avail_in);
495 if (rv != Z_OK || z.avail_in) {
496 return "";
497 }
498 }
499
500 z.avail_in = 0;
501 rv = deflate(&z, Z_FINISH);
502 QUICHE_DCHECK_EQ(Z_STREAM_END, rv);
503 if (rv != Z_STREAM_END) {
504 return "";
505 }
506
507 result.resize(result.size() - z.avail_out);
508 return result;
509 }
510
511 // static
DecompressChain(absl::string_view in,const std::vector<std::string> & cached_certs,std::vector<std::string> * out_certs)512 bool CertCompressor::DecompressChain(
513 absl::string_view in, const std::vector<std::string>& cached_certs,
514 std::vector<std::string>* out_certs) {
515 std::vector<CertEntry> entries;
516 if (!ParseEntries(&in, cached_certs, &entries, out_certs)) {
517 return false;
518 }
519 QUICHE_DCHECK_EQ(entries.size(), out_certs->size());
520
521 std::unique_ptr<uint8_t[]> uncompressed_data;
522 absl::string_view uncompressed;
523
524 if (!in.empty()) {
525 if (in.size() < sizeof(uint32_t)) {
526 return false;
527 }
528
529 uint32_t uncompressed_size;
530 memcpy(&uncompressed_size, in.data(), sizeof(uncompressed_size));
531 in.remove_prefix(sizeof(uint32_t));
532
533 if (uncompressed_size > 128 * 1024) {
534 return false;
535 }
536
537 uncompressed_data = std::make_unique<uint8_t[]>(uncompressed_size);
538 z_stream z;
539 ScopedZLib scoped_z(ScopedZLib::INFLATE);
540
541 memset(&z, 0, sizeof(z));
542 z.next_out = uncompressed_data.get();
543 z.avail_out = uncompressed_size;
544 z.next_in =
545 const_cast<uint8_t*>(reinterpret_cast<const uint8_t*>(in.data()));
546 z.avail_in = in.size();
547
548 if (Z_OK != inflateInit(&z)) {
549 return false;
550 }
551 scoped_z.reset(&z);
552
553 int rv = inflate(&z, Z_FINISH);
554 if (rv == Z_NEED_DICT) {
555 std::string zlib_dict = ZlibDictForEntries(entries, *out_certs);
556 const uint8_t* dict = reinterpret_cast<const uint8_t*>(zlib_dict.data());
557 if (Z_OK != inflateSetDictionary(&z, dict, zlib_dict.size())) {
558 return false;
559 }
560 rv = inflate(&z, Z_FINISH);
561 }
562
563 if (Z_STREAM_END != rv || z.avail_out > 0 || z.avail_in > 0) {
564 return false;
565 }
566
567 uncompressed = absl::string_view(
568 reinterpret_cast<char*>(uncompressed_data.get()), uncompressed_size);
569 }
570
571 for (size_t i = 0; i < entries.size(); i++) {
572 switch (entries[i].type) {
573 case CertEntry::COMPRESSED:
574 if (uncompressed.size() < sizeof(uint32_t)) {
575 return false;
576 }
577 uint32_t cert_len;
578 memcpy(&cert_len, uncompressed.data(), sizeof(cert_len));
579 uncompressed.remove_prefix(sizeof(uint32_t));
580 if (uncompressed.size() < cert_len) {
581 return false;
582 }
583 (*out_certs)[i] = std::string(uncompressed.substr(0, cert_len));
584 uncompressed.remove_prefix(cert_len);
585 break;
586 case CertEntry::CACHED:
587 break;
588 }
589 }
590
591 if (!uncompressed.empty()) {
592 return false;
593 }
594
595 return true;
596 }
597
598 } // namespace quic
599