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