1 // Copyright (c) 2022 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/load_balancer/load_balancer_encoder.h"
6
7 #include <cstdint>
8 #include <cstring>
9 #include <optional>
10
11 #include "absl/cleanup/cleanup.h"
12 #include "absl/numeric/int128.h"
13 #include "absl/strings/string_view.h"
14 #include "absl/types/span.h"
15 #include "quiche/quic/core/crypto/quic_random.h"
16 #include "quiche/quic/core/quic_connection_id.h"
17 #include "quiche/quic/core/quic_data_writer.h"
18 #include "quiche/quic/core/quic_utils.h"
19 #include "quiche/quic/core/quic_versions.h"
20 #include "quiche/quic/load_balancer/load_balancer_config.h"
21 #include "quiche/quic/load_balancer/load_balancer_server_id.h"
22 #include "quiche/quic/platform/api/quic_bug_tracker.h"
23 #include "quiche/common/quiche_endian.h"
24
25 namespace quic {
26
27 namespace {
28
29 // Returns the number of nonces given a certain |nonce_len|.
NumberOfNonces(uint8_t nonce_len)30 absl::uint128 NumberOfNonces(uint8_t nonce_len) {
31 return (static_cast<absl::uint128>(1) << (nonce_len * 8));
32 }
33
34 // Writes the |size| least significant bytes from |in| to |out| in host byte
35 // order. Returns false if |out| does not have enough space.
WriteUint128(const absl::uint128 in,uint8_t size,QuicDataWriter & out)36 bool WriteUint128(const absl::uint128 in, uint8_t size, QuicDataWriter &out) {
37 if (out.remaining() < size) {
38 QUIC_BUG(quic_bug_435375038_05)
39 << "Call to WriteUint128() does not have enough space in |out|";
40 return false;
41 }
42 uint64_t num64 = absl::Uint128Low64(in);
43 if (size <= sizeof(num64)) {
44 out.WriteBytes(&num64, size);
45 } else {
46 out.WriteBytes(&num64, sizeof(num64));
47 num64 = absl::Uint128High64(in);
48 out.WriteBytes(&num64, size - sizeof(num64));
49 }
50 return true;
51 }
52
53 } // namespace
54
Create(QuicRandom & random,LoadBalancerEncoderVisitorInterface * const visitor,const bool len_self_encoded,const uint8_t unroutable_connection_id_len)55 std::optional<LoadBalancerEncoder> LoadBalancerEncoder::Create(
56 QuicRandom &random, LoadBalancerEncoderVisitorInterface *const visitor,
57 const bool len_self_encoded, const uint8_t unroutable_connection_id_len) {
58 if (unroutable_connection_id_len == 0 ||
59 unroutable_connection_id_len >
60 kQuicMaxConnectionIdWithLengthPrefixLength) {
61 QUIC_BUG(quic_bug_435375038_01)
62 << "Invalid unroutable_connection_id_len = "
63 << static_cast<int>(unroutable_connection_id_len);
64 return std::optional<LoadBalancerEncoder>();
65 }
66 return LoadBalancerEncoder(random, visitor, len_self_encoded,
67 unroutable_connection_id_len);
68 }
69
UpdateConfig(const LoadBalancerConfig & config,const LoadBalancerServerId server_id)70 bool LoadBalancerEncoder::UpdateConfig(const LoadBalancerConfig &config,
71 const LoadBalancerServerId server_id) {
72 if (config_.has_value() && config_->config_id() == config.config_id()) {
73 QUIC_BUG(quic_bug_435375038_02)
74 << "Attempting to change config with same ID";
75 return false;
76 }
77 if (server_id.length() != config.server_id_len()) {
78 QUIC_BUG(quic_bug_435375038_03)
79 << "Server ID length " << static_cast<int>(server_id.length())
80 << " does not match configured value of "
81 << static_cast<int>(config.server_id_len());
82 return false;
83 }
84 if (visitor_ != nullptr) {
85 if (config_.has_value()) {
86 visitor_->OnConfigChanged(config_->config_id(), config.config_id());
87 } else {
88 visitor_->OnConfigAdded(config.config_id());
89 }
90 }
91 config_ = config;
92 server_id_ = server_id;
93
94 seed_ = absl::MakeUint128(random_.RandUint64(), random_.RandUint64()) %
95 NumberOfNonces(config.nonce_len());
96 num_nonces_left_ = NumberOfNonces(config.nonce_len());
97 connection_id_lengths_[config.config_id()] = config.total_len();
98 return true;
99 }
100
DeleteConfig()101 void LoadBalancerEncoder::DeleteConfig() {
102 if (visitor_ != nullptr && config_.has_value()) {
103 visitor_->OnConfigDeleted(config_->config_id());
104 }
105 config_.reset();
106 server_id_.reset();
107 num_nonces_left_ = 0;
108 }
109
GenerateConnectionId()110 QuicConnectionId LoadBalancerEncoder::GenerateConnectionId() {
111 absl::Cleanup cleanup = [&] {
112 if (num_nonces_left_ == 0) {
113 DeleteConfig();
114 }
115 };
116 uint8_t config_id = config_.has_value() ? config_->config_id()
117 : kLoadBalancerUnroutableConfigId;
118 uint8_t shifted_config_id = config_id << kConnectionIdLengthBits;
119 uint8_t length = connection_id_lengths_[config_id];
120 if (config_.has_value() != server_id_.has_value()) {
121 QUIC_BUG(quic_bug_435375038_04)
122 << "Existence of config and server_id are out of sync";
123 return QuicConnectionId();
124 }
125 uint8_t first_byte;
126 // first byte
127 if (len_self_encoded_) {
128 first_byte = shifted_config_id | (length - 1);
129 } else {
130 random_.RandBytes(static_cast<void *>(&first_byte), 1);
131 first_byte = shifted_config_id | (first_byte & kLoadBalancerLengthMask);
132 }
133 if (!config_.has_value()) {
134 return MakeUnroutableConnectionId(first_byte);
135 }
136 uint8_t result[kQuicMaxConnectionIdWithLengthPrefixLength];
137 QuicDataWriter writer(length, reinterpret_cast<char *>(result),
138 quiche::HOST_BYTE_ORDER);
139 writer.WriteUInt8(first_byte);
140 absl::uint128 next_nonce =
141 (seed_ + num_nonces_left_--) % NumberOfNonces(config_->nonce_len());
142 writer.WriteBytes(server_id_->data().data(), server_id_->length());
143 if (!WriteUint128(next_nonce, config_->nonce_len(), writer)) {
144 return QuicConnectionId();
145 }
146 if (!config_->IsEncrypted()) {
147 // Fill the nonce field with a hash of the Connection ID to avoid the nonce
148 // visibly increasing by one. This would allow observers to correlate
149 // connection IDs as being sequential and likely from the same connection,
150 // not just the same server.
151 absl::uint128 nonce_hash = QuicUtils::FNV1a_128_Hash(absl::string_view(
152 reinterpret_cast<char *>(result), config_->total_len()));
153 const uint64_t lo = absl::Uint128Low64(nonce_hash);
154 if (config_->nonce_len() <= sizeof(uint64_t)) {
155 memcpy(&result[1 + config_->server_id_len()], &lo, config_->nonce_len());
156 return QuicConnectionId(reinterpret_cast<char *>(result),
157 config_->total_len());
158 }
159 memcpy(&result[1 + config_->server_id_len()], &lo, sizeof(uint64_t));
160 const uint64_t hi = absl::Uint128High64(nonce_hash);
161 memcpy(&result[1 + config_->server_id_len() + sizeof(uint64_t)], &hi,
162 config_->nonce_len() - sizeof(uint64_t));
163 return QuicConnectionId(reinterpret_cast<char *>(result),
164 config_->total_len());
165 }
166 if (config_->plaintext_len() == kLoadBalancerBlockSize) {
167 if (!config_->BlockEncrypt(&result[1], &result[1])) {
168 return QuicConnectionId();
169 }
170 return (QuicConnectionId(reinterpret_cast<char *>(result),
171 config_->total_len()));
172 }
173 return config_->FourPassEncrypt(
174 absl::Span<uint8_t>(result, config_->total_len()));
175 }
176
GenerateNextConnectionId(const QuicConnectionId & original)177 std::optional<QuicConnectionId> LoadBalancerEncoder::GenerateNextConnectionId(
178 [[maybe_unused]] const QuicConnectionId &original) {
179 // Do not allow new connection IDs if linkable.
180 return (IsEncoding() && !IsEncrypted()) ? std::optional<QuicConnectionId>()
181 : GenerateConnectionId();
182 }
183
MaybeReplaceConnectionId(const QuicConnectionId & original,const ParsedQuicVersion & version)184 std::optional<QuicConnectionId> LoadBalancerEncoder::MaybeReplaceConnectionId(
185 const QuicConnectionId &original, const ParsedQuicVersion &version) {
186 // Pre-IETF versions of QUIC can respond poorly to new connection IDs issued
187 // during the handshake.
188 uint8_t needed_length = config_.has_value()
189 ? config_->total_len()
190 : connection_id_lengths_[kNumLoadBalancerConfigs];
191 return (!version.HasIetfQuicFrames() && original.length() == needed_length)
192 ? std::optional<QuicConnectionId>()
193 : GenerateConnectionId();
194 }
195
ConnectionIdLength(uint8_t first_byte) const196 uint8_t LoadBalancerEncoder::ConnectionIdLength(uint8_t first_byte) const {
197 if (len_self_encoded()) {
198 return (first_byte &= kLoadBalancerLengthMask) + 1;
199 }
200 return connection_id_lengths_[first_byte >> kConnectionIdLengthBits];
201 }
202
MakeUnroutableConnectionId(uint8_t first_byte)203 QuicConnectionId LoadBalancerEncoder::MakeUnroutableConnectionId(
204 uint8_t first_byte) {
205 QuicConnectionId id;
206 uint8_t target_length =
207 connection_id_lengths_[kLoadBalancerUnroutableConfigId];
208 id.set_length(target_length);
209 id.mutable_data()[0] = first_byte;
210 random_.RandBytes(&id.mutable_data()[1], target_length - 1);
211 return id;
212 }
213
214 } // namespace quic
215