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

quic/core/quic_connection_id.cc

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 {

quic/core/quic_connection_id.h

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 {

quic/core/quic_connection_id_test.cc

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) {