net/quic/crypto/cert_compressor.cc

   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