QuicConnectionId::Hash adoption of SipHash
This CL rolls back cl/258561852 which was itself a rollback of cl/258413870. QuicConnectionIdTest.Hash was failing on 32bit platforms and has now been fixed.
Instead of simply XORing the connection ID bits, QuicConnectionId::Hash now uses SipHash with a random key generated once per process lifetime. This prevents attackers from crafting connection IDs to make them all land in the same data structure hash bucket.
gfe-relnote: QuicConnectionId uses SipHash, protected by gfe2_restart_flag_quic_connection_id_use_siphash
PiperOrigin-RevId: 258782229
Change-Id: I019c85ba2cde0447764306b87f12323d6867acb0
diff --git a/quic/core/quic_connection_id.cc b/quic/core/quic_connection_id.cc
index a74e3b1..f446ac8 100644
--- a/quic/core/quic_connection_id.cc
+++ b/quic/core/quic_connection_id.cc
@@ -4,11 +4,14 @@
#include "net/third_party/quiche/src/quic/core/quic_connection_id.h"
+#include <cstddef>
#include <cstdint>
#include <cstring>
#include <iomanip>
#include <string>
+#include "third_party/boringssl/src/include/openssl/siphash.h"
+#include "net/third_party/quiche/src/quic/core/crypto/quic_random.h"
#include "net/third_party/quiche/src/quic/core/quic_types.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_endian.h"
@@ -19,6 +22,34 @@
namespace quic {
+namespace {
+
+// QuicConnectionIdHasher can be used to generate a stable connection ID hash
+// function that will return the same value for two equal connection IDs for
+// the duration of process lifetime. It is meant to be used as input to data
+// structures that do not outlast process lifetime. A new key is generated once
+// per process to prevent attackers from crafting connection IDs in such a way
+// that they always land in the same hash bucket.
+class QuicConnectionIdHasher {
+ public:
+ explicit inline QuicConnectionIdHasher()
+ : QuicConnectionIdHasher(QuicRandom::GetInstance()) {}
+
+ explicit inline QuicConnectionIdHasher(QuicRandom* random) {
+ random->RandBytes(&sip_hash_key_, sizeof(sip_hash_key_));
+ }
+
+ inline size_t Hash(const char* input, size_t input_len) const {
+ return static_cast<size_t>(SIPHASH_24(
+ sip_hash_key_, reinterpret_cast<const uint8_t*>(input), input_len));
+ }
+
+ private:
+ uint64_t sip_hash_key_[2];
+};
+
+} // namespace
+
QuicConnectionId::QuicConnectionId() : QuicConnectionId(nullptr, 0) {}
QuicConnectionId::QuicConnectionId(const char* data, uint8_t length) {
@@ -127,14 +158,20 @@
}
size_t QuicConnectionId::Hash() const {
- uint64_t data_bytes[3] = {0, 0, 0};
- static_assert(sizeof(data_bytes) >= kQuicMaxConnectionIdLength,
- "kQuicMaxConnectionIdLength changed");
- memcpy(data_bytes, data(), length_);
- // This Hash function is designed to return the same value as the host byte
- // order representation when the connection ID length is 64 bits.
- return QuicEndian::NetToHost64(kQuicDefaultConnectionIdLength ^ length_ ^
- data_bytes[0] ^ data_bytes[1] ^ data_bytes[2]);
+ if (!GetQuicRestartFlag(quic_connection_id_use_siphash)) {
+ uint64_t data_bytes[3] = {0, 0, 0};
+ static_assert(sizeof(data_bytes) >= kQuicMaxConnectionIdLength,
+ "kQuicMaxConnectionIdLength changed");
+ memcpy(data_bytes, data(), length_);
+ // This Hash function is designed to return the same value as the host byte
+ // order representation when the connection ID length is 64 bits.
+ return QuicEndian::NetToHost64(kQuicDefaultConnectionIdLength ^ length_ ^
+ data_bytes[0] ^ data_bytes[1] ^
+ data_bytes[2]);
+ }
+ QUIC_RESTART_FLAG_COUNT(quic_connection_id_use_siphash);
+ static const QuicConnectionIdHasher hasher = QuicConnectionIdHasher();
+ return hasher.Hash(data(), length_);
}
std::string QuicConnectionId::ToString() const {
diff --git a/quic/core/quic_connection_id.h b/quic/core/quic_connection_id.h
index 4b76f31..6b1b0bc 100644
--- a/quic/core/quic_connection_id.h
+++ b/quic/core/quic_connection_id.h
@@ -72,6 +72,11 @@
bool IsEmpty() const;
// Hash() is required to use connection IDs as keys in hash tables.
+ // During the lifetime of a process, the output of Hash() is guaranteed to be
+ // the same for connection IDs that are equal to one another. Note however
+ // that this property is not guaranteed across process lifetimes. This makes
+ // Hash() suitable for data structures such as hash tables but not for sending
+ // a hash over the network.
size_t Hash() const;
// Generates an ASCII string that represents
@@ -112,6 +117,11 @@
QUIC_EXPORT_PRIVATE QuicConnectionId EmptyQuicConnectionId();
// QuicConnectionIdHash can be passed as hash argument to hash tables.
+// During the lifetime of a process, the output of QuicConnectionIdHash is
+// guaranteed to be the same for connection IDs that are equal to one another.
+// Note however that this property is not guaranteed across process lifetimes.
+// This makes QuicConnectionIdHash suitable for data structures such as hash
+// tables but not for sending a hash over the network.
class QuicConnectionIdHash {
public:
size_t operator()(QuicConnectionId const& connection_id) const noexcept {
diff --git a/quic/core/quic_connection_id_test.cc b/quic/core/quic_connection_id_test.cc
index 1d290fc..0d4b190 100644
--- a/quic/core/quic_connection_id_test.cc
+++ b/quic/core/quic_connection_id_test.cc
@@ -89,6 +89,23 @@
EXPECT_NE(connection_id64_1.Hash(), connection_id64_2.Hash());
EXPECT_NE(connection_id64_1.Hash(), connection_id64_3.Hash());
EXPECT_NE(connection_id64_2.Hash(), connection_id64_3.Hash());
+
+ // Verify that any two all-zero connection IDs of different lengths never
+ // have the same hash.
+ if (sizeof(connection_id64_1.Hash()) < sizeof(uint64_t) &&
+ !GetQuicRestartFlag(quic_connection_id_use_siphash)) {
+ // The old hashing algorithm returns 0 for all-zero connection IDs on
+ // 32bit platforms.
+ return;
+ }
+ const char connection_id_bytes[kQuicMaxConnectionIdLength] = {};
+ for (uint8_t i = 0; i < kQuicMaxConnectionIdLength - 1; ++i) {
+ QuicConnectionId connection_id_i(connection_id_bytes, i);
+ for (uint8_t j = i + 1; j < kQuicMaxConnectionIdLength; ++j) {
+ QuicConnectionId connection_id_j(connection_id_bytes, j);
+ EXPECT_NE(connection_id_i.Hash(), connection_id_j.Hash());
+ }
+ }
}
TEST_F(QuicConnectionIdTest, AssignAndCopy) {