1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <stdbool.h>
4#include <string.h>
5#include <time.h>
6#include <zlib.h>
7
8#include <openssl/ssl.h>
9#ifndef WIN32
10#else
11#include <stdlib.h>
12#include <vc_compat.h>
13#endif
14
15#include "lsquic_int_types.h"
16#include "lsquic_crypto.h"
17#include "lsquic_crt_compress.h"
18#include "lsquic_util.h"
19
20#include "lsquic_str.h"
21
22#include "common_cert_set_2.c"
23#include "common_cert_set_3.c"
24
25/*
26 * common_cert_sub_strings contains ~1500 bytes of common certificate substrings
27 * as a dictionary of zlib from the Alexa Top 5000 set.
28 */
29static const unsigned char common_cert_sub_strings[] = {
30    0x04, 0x02, 0x30, 0x00, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x1d, 0x25, 0x04,
31    0x16, 0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03,
32    0x01, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03, 0x02, 0x30,
33    0x5f, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x86, 0xf8, 0x42, 0x04, 0x01,
34    0x06, 0x06, 0x0b, 0x60, 0x86, 0x48, 0x01, 0x86, 0xfd, 0x6d, 0x01, 0x07,
35    0x17, 0x01, 0x30, 0x33, 0x20, 0x45, 0x78, 0x74, 0x65, 0x6e, 0x64, 0x65,
36    0x64, 0x20, 0x56, 0x61, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x69, 0x6f, 0x6e,
37    0x20, 0x53, 0x20, 0x4c, 0x69, 0x6d, 0x69, 0x74, 0x65, 0x64, 0x31, 0x34,
38    0x20, 0x53, 0x53, 0x4c, 0x20, 0x43, 0x41, 0x30, 0x1e, 0x17, 0x0d, 0x31,
39    0x32, 0x20, 0x53, 0x65, 0x63, 0x75, 0x72, 0x65, 0x20, 0x53, 0x65, 0x72,
40    0x76, 0x65, 0x72, 0x20, 0x43, 0x41, 0x30, 0x2d, 0x61, 0x69, 0x61, 0x2e,
41    0x76, 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d,
42    0x2f, 0x45, 0x2d, 0x63, 0x72, 0x6c, 0x2e, 0x76, 0x65, 0x72, 0x69, 0x73,
43    0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x45, 0x2e, 0x63, 0x65,
44    0x72, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01,
45    0x01, 0x05, 0x05, 0x00, 0x03, 0x82, 0x01, 0x01, 0x00, 0x4a, 0x2e, 0x63,
46    0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x73, 0x6f, 0x75, 0x72, 0x63, 0x65, 0x73,
47    0x2f, 0x63, 0x70, 0x73, 0x20, 0x28, 0x63, 0x29, 0x30, 0x30, 0x09, 0x06,
48    0x03, 0x55, 0x1d, 0x13, 0x04, 0x02, 0x30, 0x00, 0x30, 0x1d, 0x30, 0x0d,
49    0x06, 0x09, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x05, 0x05,
50    0x00, 0x03, 0x82, 0x01, 0x01, 0x00, 0x7b, 0x30, 0x1d, 0x06, 0x03, 0x55,
51    0x1d, 0x0e, 0x30, 0x82, 0x01, 0x22, 0x30, 0x0d, 0x06, 0x09, 0x2a, 0x86,
52    0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x01, 0x05, 0x00, 0x03, 0x82, 0x01,
53    0x0f, 0x00, 0x30, 0x82, 0x01, 0x0a, 0x02, 0x82, 0x01, 0x01, 0x00, 0xd2,
54    0x6f, 0x64, 0x6f, 0x63, 0x61, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x43, 0x2e,
55    0x63, 0x72, 0x6c, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x1d, 0x0e, 0x04, 0x16,
56    0x04, 0x14, 0xb4, 0x2e, 0x67, 0x6c, 0x6f, 0x62, 0x61, 0x6c, 0x73, 0x69,
57    0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x30, 0x0b, 0x06, 0x03,
58    0x55, 0x1d, 0x0f, 0x04, 0x04, 0x03, 0x02, 0x01, 0x30, 0x0d, 0x06, 0x09,
59    0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x01, 0x01, 0x05, 0x05, 0x00, 0x30,
60    0x81, 0xca, 0x31, 0x0b, 0x30, 0x09, 0x06, 0x03, 0x55, 0x04, 0x06, 0x13,
61    0x02, 0x55, 0x53, 0x31, 0x10, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x04, 0x08,
62    0x13, 0x07, 0x41, 0x72, 0x69, 0x7a, 0x6f, 0x6e, 0x61, 0x31, 0x13, 0x30,
63    0x11, 0x06, 0x03, 0x55, 0x04, 0x07, 0x13, 0x0a, 0x53, 0x63, 0x6f, 0x74,
64    0x74, 0x73, 0x64, 0x61, 0x6c, 0x65, 0x31, 0x1a, 0x30, 0x18, 0x06, 0x03,
65    0x55, 0x04, 0x0a, 0x13, 0x11, 0x47, 0x6f, 0x44, 0x61, 0x64, 0x64, 0x79,
66    0x2e, 0x63, 0x6f, 0x6d, 0x2c, 0x20, 0x49, 0x6e, 0x63, 0x2e, 0x31, 0x33,
67    0x30, 0x31, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x2a, 0x68, 0x74, 0x74,
68    0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x65, 0x72, 0x74, 0x69, 0x66, 0x69, 0x63,
69    0x61, 0x74, 0x65, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79,
70    0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74,
71    0x6f, 0x72, 0x79, 0x31, 0x30, 0x30, 0x2e, 0x06, 0x03, 0x55, 0x04, 0x03,
72    0x13, 0x27, 0x47, 0x6f, 0x20, 0x44, 0x61, 0x64, 0x64, 0x79, 0x20, 0x53,
73    0x65, 0x63, 0x75, 0x72, 0x65, 0x20, 0x43, 0x65, 0x72, 0x74, 0x69, 0x66,
74    0x69, 0x63, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x20, 0x41, 0x75, 0x74, 0x68,
75    0x6f, 0x72, 0x69, 0x74, 0x79, 0x31, 0x11, 0x30, 0x0f, 0x06, 0x03, 0x55,
76    0x04, 0x05, 0x13, 0x08, 0x30, 0x37, 0x39, 0x36, 0x39, 0x32, 0x38, 0x37,
77    0x30, 0x1e, 0x17, 0x0d, 0x31, 0x31, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x1d,
78    0x0f, 0x01, 0x01, 0xff, 0x04, 0x04, 0x03, 0x02, 0x05, 0xa0, 0x30, 0x0c,
79    0x06, 0x03, 0x55, 0x1d, 0x13, 0x01, 0x01, 0xff, 0x04, 0x02, 0x30, 0x00,
80    0x30, 0x1d, 0x30, 0x0f, 0x06, 0x03, 0x55, 0x1d, 0x13, 0x01, 0x01, 0xff,
81    0x04, 0x05, 0x30, 0x03, 0x01, 0x01, 0x00, 0x30, 0x1d, 0x06, 0x03, 0x55,
82    0x1d, 0x25, 0x04, 0x16, 0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05,
83    0x05, 0x07, 0x03, 0x01, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07,
84    0x03, 0x02, 0x30, 0x0e, 0x06, 0x03, 0x55, 0x1d, 0x0f, 0x01, 0x01, 0xff,
85    0x04, 0x04, 0x03, 0x02, 0x05, 0xa0, 0x30, 0x33, 0x06, 0x03, 0x55, 0x1d,
86    0x1f, 0x04, 0x2c, 0x30, 0x2a, 0x30, 0x28, 0xa0, 0x26, 0xa0, 0x24, 0x86,
87    0x22, 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x72, 0x6c, 0x2e,
88    0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f,
89    0x67, 0x64, 0x73, 0x31, 0x2d, 0x32, 0x30, 0x2a, 0x30, 0x28, 0x06, 0x08,
90    0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x02, 0x01, 0x16, 0x1c, 0x68, 0x74,
91    0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x77, 0x77, 0x77, 0x2e, 0x76, 0x65,
92    0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x63,
93    0x70, 0x73, 0x30, 0x34, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x5a, 0x17,
94    0x0d, 0x31, 0x33, 0x30, 0x35, 0x30, 0x39, 0x06, 0x08, 0x2b, 0x06, 0x01,
95    0x05, 0x05, 0x07, 0x30, 0x02, 0x86, 0x2d, 0x68, 0x74, 0x74, 0x70, 0x3a,
96    0x2f, 0x2f, 0x73, 0x30, 0x39, 0x30, 0x37, 0x06, 0x08, 0x2b, 0x06, 0x01,
97    0x05, 0x05, 0x07, 0x02, 0x30, 0x44, 0x06, 0x03, 0x55, 0x1d, 0x20, 0x04,
98    0x3d, 0x30, 0x3b, 0x30, 0x39, 0x06, 0x0b, 0x60, 0x86, 0x48, 0x01, 0x86,
99    0xf8, 0x45, 0x01, 0x07, 0x17, 0x06, 0x31, 0x0b, 0x30, 0x09, 0x06, 0x03,
100    0x55, 0x04, 0x06, 0x13, 0x02, 0x47, 0x42, 0x31, 0x1b, 0x53, 0x31, 0x17,
101    0x30, 0x15, 0x06, 0x03, 0x55, 0x04, 0x0a, 0x13, 0x0e, 0x56, 0x65, 0x72,
102    0x69, 0x53, 0x69, 0x67, 0x6e, 0x2c, 0x20, 0x49, 0x6e, 0x63, 0x2e, 0x31,
103    0x1f, 0x30, 0x1d, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x16, 0x56, 0x65,
104    0x72, 0x69, 0x53, 0x69, 0x67, 0x6e, 0x20, 0x54, 0x72, 0x75, 0x73, 0x74,
105    0x20, 0x4e, 0x65, 0x74, 0x77, 0x6f, 0x72, 0x6b, 0x31, 0x3b, 0x30, 0x39,
106    0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x32, 0x54, 0x65, 0x72, 0x6d, 0x73,
107    0x20, 0x6f, 0x66, 0x20, 0x75, 0x73, 0x65, 0x20, 0x61, 0x74, 0x20, 0x68,
108    0x74, 0x74, 0x70, 0x73, 0x3a, 0x2f, 0x2f, 0x77, 0x77, 0x77, 0x2e, 0x76,
109    0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d, 0x2f,
110    0x72, 0x70, 0x61, 0x20, 0x28, 0x63, 0x29, 0x30, 0x31, 0x10, 0x30, 0x0e,
111    0x06, 0x03, 0x55, 0x04, 0x07, 0x13, 0x07, 0x53, 0x31, 0x13, 0x30, 0x11,
112    0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x0a, 0x47, 0x31, 0x13, 0x30, 0x11,
113    0x06, 0x0b, 0x2b, 0x06, 0x01, 0x04, 0x01, 0x82, 0x37, 0x3c, 0x02, 0x01,
114    0x03, 0x13, 0x02, 0x55, 0x31, 0x16, 0x30, 0x14, 0x06, 0x03, 0x55, 0x04,
115    0x03, 0x14, 0x31, 0x19, 0x30, 0x17, 0x06, 0x03, 0x55, 0x04, 0x03, 0x13,
116    0x31, 0x1d, 0x30, 0x1b, 0x06, 0x03, 0x55, 0x04, 0x0f, 0x13, 0x14, 0x50,
117    0x72, 0x69, 0x76, 0x61, 0x74, 0x65, 0x20, 0x4f, 0x72, 0x67, 0x61, 0x6e,
118    0x69, 0x7a, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x31, 0x12, 0x31, 0x21, 0x30,
119    0x1f, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x18, 0x44, 0x6f, 0x6d, 0x61,
120    0x69, 0x6e, 0x20, 0x43, 0x6f, 0x6e, 0x74, 0x72, 0x6f, 0x6c, 0x20, 0x56,
121    0x61, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x65, 0x64, 0x31, 0x14, 0x31, 0x31,
122    0x30, 0x2f, 0x06, 0x03, 0x55, 0x04, 0x0b, 0x13, 0x28, 0x53, 0x65, 0x65,
123    0x20, 0x77, 0x77, 0x77, 0x2e, 0x72, 0x3a, 0x2f, 0x2f, 0x73, 0x65, 0x63,
124    0x75, 0x72, 0x65, 0x2e, 0x67, 0x47, 0x6c, 0x6f, 0x62, 0x61, 0x6c, 0x53,
125    0x69, 0x67, 0x6e, 0x31, 0x53, 0x65, 0x72, 0x76, 0x65, 0x72, 0x43, 0x41,
126    0x2e, 0x63, 0x72, 0x6c, 0x56, 0x65, 0x72, 0x69, 0x53, 0x69, 0x67, 0x6e,
127    0x20, 0x43, 0x6c, 0x61, 0x73, 0x73, 0x20, 0x33, 0x20, 0x45, 0x63, 0x72,
128    0x6c, 0x2e, 0x67, 0x65, 0x6f, 0x74, 0x72, 0x75, 0x73, 0x74, 0x2e, 0x63,
129    0x6f, 0x6d, 0x2f, 0x63, 0x72, 0x6c, 0x73, 0x2f, 0x73, 0x64, 0x31, 0x1a,
130    0x30, 0x18, 0x06, 0x03, 0x55, 0x04, 0x0a, 0x68, 0x74, 0x74, 0x70, 0x3a,
131    0x2f, 0x2f, 0x45, 0x56, 0x49, 0x6e, 0x74, 0x6c, 0x2d, 0x63, 0x63, 0x72,
132    0x74, 0x2e, 0x67, 0x77, 0x77, 0x77, 0x2e, 0x67, 0x69, 0x63, 0x65, 0x72,
133    0x74, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x31, 0x6f, 0x63, 0x73, 0x70, 0x2e,
134    0x76, 0x65, 0x72, 0x69, 0x73, 0x69, 0x67, 0x6e, 0x2e, 0x63, 0x6f, 0x6d,
135    0x30, 0x39, 0x72, 0x61, 0x70, 0x69, 0x64, 0x73, 0x73, 0x6c, 0x2e, 0x63,
136    0x6f, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64, 0x64, 0x79, 0x2e, 0x63,
137    0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73, 0x69, 0x74, 0x6f, 0x72,
138    0x79, 0x2f, 0x30, 0x81, 0x80, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05,
139    0x07, 0x01, 0x01, 0x04, 0x74, 0x30, 0x72, 0x30, 0x24, 0x06, 0x08, 0x2b,
140    0x06, 0x01, 0x05, 0x05, 0x07, 0x30, 0x01, 0x86, 0x18, 0x68, 0x74, 0x74,
141    0x70, 0x3a, 0x2f, 0x2f, 0x6f, 0x63, 0x73, 0x70, 0x2e, 0x67, 0x6f, 0x64,
142    0x61, 0x64, 0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x30, 0x4a, 0x06,
143    0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x30, 0x02, 0x86, 0x3e, 0x68,
144    0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x65, 0x72, 0x74, 0x69, 0x66,
145    0x69, 0x63, 0x61, 0x74, 0x65, 0x73, 0x2e, 0x67, 0x6f, 0x64, 0x61, 0x64,
146    0x64, 0x79, 0x2e, 0x63, 0x6f, 0x6d, 0x2f, 0x72, 0x65, 0x70, 0x6f, 0x73,
147    0x69, 0x74, 0x6f, 0x72, 0x79, 0x2f, 0x67, 0x64, 0x5f, 0x69, 0x6e, 0x74,
148    0x65, 0x72, 0x6d, 0x65, 0x64, 0x69, 0x61, 0x74, 0x65, 0x2e, 0x63, 0x72,
149    0x74, 0x30, 0x1f, 0x06, 0x03, 0x55, 0x1d, 0x23, 0x04, 0x18, 0x30, 0x16,
150    0x80, 0x14, 0xfd, 0xac, 0x61, 0x32, 0x93, 0x6c, 0x45, 0xd6, 0xe2, 0xee,
151    0x85, 0x5f, 0x9a, 0xba, 0xe7, 0x76, 0x99, 0x68, 0xcc, 0xe7, 0x30, 0x27,
152    0x86, 0x29, 0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x63, 0x86, 0x30,
153    0x68, 0x74, 0x74, 0x70, 0x3a, 0x2f, 0x2f, 0x73,
154};
155
156#define common_certs_num 2
157const common_cert_t common_cert_set[common_certs_num] = {
158    {common_certs2_num, common_certs2, common_certs2_lens, common_certs2_hash},
159    {common_certs3_num, common_certs3, common_certs3_lens, common_certs3_hash},
160};
161
162
163static lsquic_str_t *s_ccsbuf;
164
165static int
166match_common_cert (lsquic_str_t * cert, lsquic_str_t * common_set_hashes,
167        uint64_t* out_hash, uint32_t* out_index);
168
169int
170lsquic_crt_init (void)
171{
172    unsigned i;
173
174    s_ccsbuf = lsquic_str_new(NULL, 0);
175    if (!s_ccsbuf)
176        return -1;
177    for (i=0 ;i<common_certs_num; ++i)
178    {
179        if (0 != lsquic_str_append(s_ccsbuf, (const char *)&common_cert_set[i].hash, 8))
180            return -1;
181    }
182    return 0;
183}
184
185
186lsquic_str_t *
187lsquic_get_common_certs_hash()
188{
189    return s_ccsbuf;
190}
191
192
193/* return 0 found, -1 not found */
194int
195lsquic_get_common_cert(uint64_t hash, uint32_t index, lsquic_str_t *buf)
196{
197    int i;
198    for (i = 0; i < common_certs_num; i++)
199    {
200        if (common_cert_set[i].hash == hash)
201        {
202            if (index < common_cert_set[i].num_certs)
203            {
204                lsquic_str_setto(buf, (const char *) common_cert_set[i].certs[index],
205                         common_cert_set[i].lens[index]);
206                return 0;
207            }
208            break;
209        }
210    }
211    return -1;
212}
213
214
215static int
216comp_ls_str (lsquic_str_t * a, const void * b, size_t b_len)
217{
218    size_t a_len;
219    int r;
220
221    a_len = lsquic_str_len(a);
222    r = memcmp(lsquic_str_buf(a), b, a_len < b_len ? a_len : b_len);
223    if (r)
224        return r;
225    else
226        return (a_len > b_len) - (b_len > a_len);
227}
228
229
230/* 0, matched -1, error */
231static int
232match_common_cert (lsquic_str_t * cert, lsquic_str_t * common_set_hashes,
233        uint64_t* out_hash, uint32_t* out_index)
234{
235    size_t i, j;
236    int n;
237    uint64_t hash;
238    size_t min, max, mid;
239
240    if (lsquic_str_len(common_set_hashes) % sizeof(uint64_t) != 0)
241        return -1;
242
243    for (i = 0; i < lsquic_str_len(common_set_hashes) / sizeof(uint64_t); i++)
244    {
245        memcpy(&hash, lsquic_str_buf(common_set_hashes) + i * sizeof(uint64_t),
246               sizeof(uint64_t));
247
248        for (j = 0; j < common_certs_num; j++)
249        {
250            if (common_cert_set[j].hash != hash)
251                continue;
252
253            if (common_cert_set[j].num_certs == 0)
254                continue;
255
256            min = 0;
257            max = common_cert_set[j].num_certs - 1;
258            while (max >= min)
259            {
260                mid = min + ((max - min) / 2);
261                n = comp_ls_str(cert, common_cert_set[j].certs[mid],
262                                 common_cert_set[j].lens[mid]);
263                if (n < 0)
264                {
265                    if (mid == 0)
266                        break;
267                    max = mid - 1;
268                }
269                else if (n > 0)
270                    min = mid + 1;
271                else
272                {
273                    *out_hash = hash;
274                    *out_index = mid;
275                    return 0;
276                }
277            }
278        }
279    }
280
281    return -1;
282}
283
284
285/* result is written to dict */
286static void
287make_zlib_dict_for_entries(cert_entry_t *entries,
288                                lsquic_str_t **certs, size_t certs_count,
289                                lsquic_str_t *dict)
290{
291    int i;
292    size_t zlib_dict_size = 0;
293    for (i = certs_count - 1; i >= 0; --i)
294    {
295        if (entries[i].type != ENTRY_COMPRESSED)
296        {
297            zlib_dict_size += lsquic_str_len(certs[i]);
298        }
299    }
300
301    // At the end of the dictionary is a block of common certificate substrings.
302    zlib_dict_size += sizeof(common_cert_sub_strings);
303
304    for (i = certs_count - 1; i >= 0; --i)
305    {
306        if (entries[i].type != ENTRY_COMPRESSED)
307        {
308            lsquic_str_append(dict, lsquic_str_buf(certs[i]), lsquic_str_len(certs[i]));
309        }
310    }
311
312    lsquic_str_append(dict, (const char *)common_cert_sub_strings, sizeof(common_cert_sub_strings));
313    assert((size_t)lsquic_str_len(dict) == zlib_dict_size);
314}
315
316
317static
318void get_certs_hash(lsquic_str_t *certs, size_t certs_count, uint64_t *hashs)
319{
320    size_t i;
321    for(i = 0; i < certs_count; ++i)
322    {
323        hashs[i] = lsquic_fnv1a_64((const uint8_t *)lsquic_str_buf(&certs[i]), lsquic_str_len(&certs[i]));
324    }
325}
326
327
328static void get_certs_entries(lsquic_str_t **certs, size_t certs_count,
329                              lsquic_str_t *client_common_set_hashes,
330                              lsquic_str_t *client_cached_cert_hashes,
331                              cert_entry_t *entries)
332{
333    size_t i;
334    int j;
335    cert_entry_t *entry;
336    uint64_t hash, cached_hash;
337    bool cached;
338
339    const bool cached_valid = (lsquic_str_len(client_cached_cert_hashes) % sizeof(uint64_t) == 0)
340                                && (lsquic_str_len(client_cached_cert_hashes) > 0);
341
342    assert(&entries[certs_count - 1]);
343
344    for (i = 0; i<certs_count; ++i)
345    {
346        entry = &entries[i];
347        if (cached_valid)
348        {
349            cached = false;
350            hash = lsquic_fnv1a_64((const uint8_t *)lsquic_str_buf(certs[i]), lsquic_str_len(certs[i]));
351
352            for (j = 0; j < (int)lsquic_str_len(client_cached_cert_hashes);
353                 j += sizeof(uint64_t))
354            {
355                memcpy(&cached_hash, lsquic_str_buf(client_cached_cert_hashes) + j,
356                       sizeof(uint64_t));
357                if (hash != cached_hash)
358                    continue;
359
360                entry->type = ENTRY_CACHED;
361                entry->hash = hash;
362                cached = true;
363                break;
364            }
365
366            if (cached)
367                continue;
368        }
369
370        if (0 == match_common_cert(certs[i], client_common_set_hashes,
371            &entry->set_hash, &entry->index))
372        {
373            entry->type = ENTRY_COMMON;
374            continue;
375        }
376
377        entry->type = ENTRY_COMPRESSED;
378   }
379}
380
381static size_t
382get_entries_size(cert_entry_t *entries, size_t entries_count)
383{
384    size_t i;
385    size_t entries_size = 0;
386    for(i=0; i<entries_count; ++i)
387    {
388        entries_size++;
389        switch (entries[i].type)
390        {
391        case ENTRY_COMPRESSED:
392            break;
393        case ENTRY_CACHED:
394            entries_size += sizeof(uint64_t);
395            break;
396        case ENTRY_COMMON:
397            entries_size += sizeof(uint64_t) + sizeof(uint32_t);
398            break;
399        default:
400            break;
401        }
402    }
403    entries_size++;  /* for end marker */
404    return entries_size;
405}
406
407static
408void serialize_cert_entries(uint8_t* out, int *out_len, cert_entry_t *entries,
409                            size_t entries_count)
410{
411    size_t i;
412    uint8_t *start = out;
413    for(i=0; i<entries_count; ++i)
414    {
415        *out++ = (uint8_t)(entries[i].type);
416        switch (entries[i].type)
417        {
418        case ENTRY_COMPRESSED:
419            break;
420        case ENTRY_CACHED:
421            memcpy(out, &entries[i].hash, sizeof(uint64_t));
422            out += sizeof(uint64_t);
423            break;
424        case ENTRY_COMMON:
425            memcpy(out, &entries[i].set_hash, sizeof(uint64_t));
426            out += sizeof(uint64_t);
427            memcpy(out, &entries[i].index, sizeof(uint32_t));
428            out += sizeof(uint32_t);
429            break;
430        default:
431            break;
432        }
433    }
434
435    *out++ = 0;  // end marker
436    *out_len = out - start;
437}
438
439
440int
441lsquic_get_certs_count (const struct compressed_cert *ccert)
442{
443    const unsigned char *in = ccert->buf;
444    const unsigned char *in_end = in + ccert->len;
445    size_t idx = 0;
446    uint8_t type_byte;
447
448    for (;;)
449    {
450        if (in >= in_end)
451            return -1;
452
453        type_byte = in[0];
454        ++in;
455        if (type_byte == 0)
456            break;
457
458        ++idx;
459        switch(type_byte)
460        {
461        case ENTRY_COMPRESSED:
462            break;
463        case ENTRY_CACHED:
464        {
465            if (in_end - in < (int)sizeof(uint64_t))
466                return -1;
467            in += sizeof(uint64_t);
468            break;
469        }
470        case ENTRY_COMMON:
471        {
472            if (in_end - in < (int)(sizeof(uint64_t) + sizeof(uint32_t)))
473                return -1;
474            in += sizeof(uint64_t) + sizeof(uint32_t);
475            break;
476        }
477        default:
478            return -1;
479        }
480    }
481    return idx;
482}
483
484
485/* return 0: OK, -1, error */
486static int parse_entries(const unsigned char **in_out, const unsigned char *const in_end,
487                         lsquic_str_t *cached_certs, size_t cached_certs_count,
488                         cert_entry_t *out_entries,
489                         lsquic_str_t **out_certs, size_t *out_certs_count)
490{
491    const unsigned char *in = *in_out;
492    size_t idx = 0;
493    uint64_t* cached_hashes;
494    cert_entry_t *entry;
495    lsquic_str_t *cert;
496    uint8_t type_byte;
497    int rv;
498    size_t i;
499
500    cached_hashes = NULL;
501
502    for (;;)
503    {
504        /* XXX potential invalid read */
505        type_byte = in[0];
506        ++in;
507
508        if (type_byte == 0)
509            break;
510
511        entry = &out_entries[idx];
512        cert = out_certs[idx];
513        /* XXX This seems dangerous -- there is no guard that `idx' does not
514         * exceed `out_certs_count'.
515         */
516        lsquic_str_d(cert);
517
518        ++idx;
519        entry->type = type_byte;
520        switch (entry->type)
521        {
522        case ENTRY_COMPRESSED:
523            break;
524        case ENTRY_CACHED:
525        {
526            memcpy(&entry->hash, in, sizeof(uint64_t));
527            in += sizeof(uint64_t);
528
529            if (!cached_hashes)
530            {
531                cached_hashes = malloc(cached_certs_count * sizeof(uint64_t));;
532                if (!cached_hashes)
533                    goto err;
534                get_certs_hash(cached_certs, cached_certs_count, cached_hashes);
535            }
536
537            for (i=0; i<cached_certs_count; ++i)
538            {
539                if (cached_hashes[i] == entry->hash)
540                {
541                    lsquic_str_append(cert, lsquic_str_buf(&cached_certs[i]),
542                                  lsquic_str_len(&cached_certs[i]));
543                    break;
544                }
545            }
546            /* XXX: return -1 if not found?  Logic removed in
547                                4fd7e76bc031ac637e76c7f0930aff53f5b71705 */
548            break;
549        }
550        case ENTRY_COMMON:
551        {
552            memcpy(&entry->set_hash, in, sizeof(uint64_t));
553            in += sizeof(uint64_t);
554            memcpy(&entry->index, in, sizeof(uint32_t));
555            in += sizeof(uint32_t);
556
557            if (0 == lsquic_get_common_cert(entry->set_hash, entry->index, cert))
558                break;
559            else
560                goto err;
561        }
562        default:
563            goto err;
564        }
565    }
566
567    rv = 0;
568    *in_out = in;
569    *out_certs_count = idx;
570
571  cleanup:
572    free(cached_hashes);
573    return rv;
574
575  err:
576    rv = -1;
577    goto cleanup;
578}
579
580
581struct compressed_cert *
582lsquic_compress_certs (lsquic_str_t **certs, size_t certs_count,
583                   lsquic_str_t *client_common_set_hashes,
584                   lsquic_str_t *client_cached_cert_hashes)
585{
586    size_t i;
587    size_t uncompressed_size = 0, compressed_size = 0 ;
588    z_stream z;
589    lsquic_str_t *dict;
590    size_t entries_size, result_length;
591    int out_len;
592    uint8_t* out;
593    uint32_t tmp_size_32;
594    cert_entry_t *entries;
595    struct compressed_cert *ccert;
596
597    ccert = NULL;
598    entries = malloc(sizeof(cert_entry_t) * certs_count);
599    if (!entries)
600        return NULL;
601
602    dict = lsquic_str_new(NULL, 0);
603    if (!dict)
604        goto err;
605
606    get_certs_entries(certs, certs_count, client_common_set_hashes,
607                              client_cached_cert_hashes, entries);
608
609    for (i = 0; i < certs_count; i++)
610    {
611        if (entries[i].type == ENTRY_COMPRESSED)
612        {
613             /*uint32_t length + cert content*/
614            uncompressed_size += 4 + lsquic_str_len(certs[i]);
615        }
616    }
617
618    if (uncompressed_size > 0)
619    {
620        memset(&z, 0, sizeof(z));
621        if (Z_OK != deflateInit(&z, Z_DEFAULT_COMPRESSION))
622            goto err;
623
624        make_zlib_dict_for_entries(entries, certs, certs_count, dict);
625        if(Z_OK != deflateSetDictionary(&z, (const unsigned char *)lsquic_str_buf(dict), lsquic_str_len(dict)))
626            goto err;
627        compressed_size = deflateBound(&z, uncompressed_size);
628    }
629
630    entries_size = get_entries_size(entries, certs_count);
631    result_length = entries_size + (uncompressed_size > 0 ? 4 : 0) +
632                    compressed_size;
633    ccert = malloc(sizeof(*ccert) + result_length);
634    if (!ccert)
635        goto err;
636    ccert->refcnt = 0;
637
638    out = ccert->buf;
639    serialize_cert_entries(out, &out_len, entries, certs_count);
640    out += entries_size;
641
642    if (uncompressed_size == 0)
643    {
644        ccert->len = entries_size;
645        goto cleanup;
646    }
647
648    tmp_size_32 = uncompressed_size;
649    memcpy(out, &tmp_size_32, sizeof(uint32_t));
650    out += sizeof(uint32_t);
651
652    z.next_out = out;
653    z.avail_out = compressed_size;
654
655    for (i = 0; i < certs_count; ++i)
656    {
657        if (entries[i].type != ENTRY_COMPRESSED)
658            continue;
659
660        tmp_size_32 = lsquic_str_len(certs[i]);
661        z.next_in = (uint8_t*)(&tmp_size_32);
662        z.avail_in = sizeof(tmp_size_32);
663        if (Z_OK != deflate(&z, Z_NO_FLUSH) || z.avail_in)
664            goto err;
665        z.next_in = (unsigned char *)lsquic_str_buf(certs[i]);
666        z.avail_in = lsquic_str_len(certs[i]);
667        if (Z_OK != deflate(&z, Z_NO_FLUSH) || z.avail_in)
668            goto err;
669    }
670
671    z.avail_in = 0;
672    if (Z_STREAM_END != deflate(&z, Z_FINISH))
673        goto err;
674
675    ccert->len = result_length - z.avail_out;
676
677  cleanup:
678    free(entries);
679    if (dict)
680        lsquic_str_delete(dict);
681    if (uncompressed_size)
682        deflateEnd(&z);
683    return ccert;
684
685  err:
686    if (ccert)
687        free(ccert);
688    ccert = NULL;
689    goto cleanup;
690}
691
692
693/* 0: ok */
694int
695lsquic_decompress_certs (const unsigned char *in, const unsigned char *in_end,
696                     lsquic_str_t *cached_certs, size_t cached_certs_count,
697                     lsquic_str_t **out_certs, size_t *out_certs_count)
698{
699    int ret;
700    size_t i;
701    uint8_t* uncompressed_data, *uncompressed_data_buf;
702    lsquic_str_t *dict;
703    uint32_t uncompressed_size;
704    size_t count = *out_certs_count;
705    cert_entry_t *entries;
706    z_stream z;
707
708    assert(*out_certs_count > 0 && *out_certs_count < 10000
709            && "Call lsquic_get_certs_count() to get right certificates count first and make enough room for out_certs_count");
710
711    if (count == 0 || count > 10000)
712        return -1;
713
714    dict = lsquic_str_new(NULL, 0);
715    if (!dict)
716        return -1;
717
718    uncompressed_data_buf = NULL;
719#ifdef WIN32
720    uncompressed_data = NULL;
721#endif
722    entries = malloc(count * sizeof(cert_entry_t));
723    if (!entries)
724        goto err;
725
726    ret = parse_entries(&in, in_end, cached_certs, cached_certs_count,
727                  entries, out_certs, out_certs_count);
728    if (ret)
729        goto err;
730
731    /* re-assign count with real valus */
732    count = *out_certs_count;
733
734    if (in < in_end)
735    {
736        if (in_end - in < (int)sizeof(uint32_t))
737            goto err;
738
739        memcpy(&uncompressed_size, in, sizeof(uncompressed_size));
740        in += sizeof(uint32_t);
741        /* XXX Is 128 KB an arbitrary limit or is there a reason behind it? */
742        if (uncompressed_size > 128 * 1024)
743            goto err;
744
745        uncompressed_data_buf = uncompressed_data = malloc(uncompressed_size);
746        if (!uncompressed_data)
747            goto err;
748
749        memset(&z, 0, sizeof(z));
750        z.next_out  = uncompressed_data;
751        z.avail_out = uncompressed_size;
752        z.next_in   = (unsigned char *) in;
753        z.avail_in  = in_end - in;
754
755        if (Z_OK != inflateInit(&z))
756            goto err;
757
758        ret = inflate(&z, Z_FINISH);
759        if (ret == Z_NEED_DICT)
760        {
761            lsquic_str_d(dict);
762            make_zlib_dict_for_entries(entries, out_certs, count, dict);
763            if (Z_OK != inflateSetDictionary(&z, (const unsigned char *)lsquic_str_buf(dict), lsquic_str_len(dict)))
764                goto err;
765            ret = inflate(&z, Z_FINISH);
766        }
767
768        if (Z_STREAM_END != ret || z.avail_out > 0 || z.avail_in > 0)
769            goto err;
770    }
771    else
772        uncompressed_size = 0;
773
774    for (i = 0; i < count; i++)
775    {
776        switch (entries[i].type)
777        {
778          case ENTRY_COMPRESSED:
779              if (uncompressed_size < sizeof(uint32_t))
780                  goto err;
781              lsquic_str_d(out_certs[i]);
782              uint32_t cert_len;
783              memcpy(&cert_len, uncompressed_data, sizeof(cert_len));
784              uncompressed_data += sizeof(uint32_t);
785              uncompressed_size -= sizeof(uint32_t);
786              if (uncompressed_size < cert_len)
787                  goto err;
788              lsquic_str_append(out_certs[i], (const char *)uncompressed_data, cert_len);
789              uncompressed_data += cert_len;
790              uncompressed_size -= cert_len;
791              break;
792          case ENTRY_CACHED:
793          case ENTRY_COMMON:
794          default:
795            break;
796        }
797    }
798
799  cleanup:
800    lsquic_str_delete(dict);
801    free(entries);
802    if (uncompressed_data_buf)
803        inflateEnd(&z);
804    free(uncompressed_data_buf);
805    if (0 == uncompressed_size)
806        return 0;
807    else
808        return -1;
809
810  err:
811    uncompressed_size = 1;  /* This triggers return -1 above */
812    goto cleanup;
813}
814
815
816void
817lsquic_crt_cleanup (void)
818{
819    if (s_ccsbuf)
820    {
821        lsquic_str_delete(s_ccsbuf);
822        s_ccsbuf = NULL;
823    }
824}
825