Update four-pass algorithm to reduce copying and conform to draft-ietf-quic-load-balancers-19. Code is not in production. Performance (ns, Unencrypted / 3-pass / 1-pass) Tip-of-tree: 20.9/102/26.3 This CL: 21.2/96.7/26.4 PiperOrigin-RevId: 604412894
diff --git a/quiche/quic/load_balancer/load_balancer_config.cc b/quiche/quic/load_balancer/load_balancer_config.cc index 6dfb30c..70c2590 100644 --- a/quiche/quic/load_balancer/load_balancer_config.cc +++ b/quiche/quic/load_balancer/load_balancer_config.cc
@@ -89,6 +89,7 @@ : std::optional<LoadBalancerConfig>(); } +// Note that |ciphertext| does not include the first byte of the connection ID. bool LoadBalancerConfig::FourPassDecrypt( absl::Span<const uint8_t> ciphertext, LoadBalancerServerId& server_id) const { @@ -103,7 +104,7 @@ // Do 3 or 4 passes. Only 3 are necessary if the server_id is short enough // to fit in the first half of the connection ID (the decoder doesn't need // to extract the nonce). - uint8_t left[kLoadBalancerBlockSize]; + uint8_t* left = server_id.mutable_data(); uint8_t right[kLoadBalancerBlockSize]; uint8_t half_len; // half the length of the plaintext, rounded up bool is_length_odd = @@ -117,19 +118,18 @@ // Consolidate left and right into a server ID with minimum copying. if (server_id_len_ < half_len || (server_id_len_ == half_len && !is_length_odd)) { - // There is no half-byte to handle - memcpy(server_id.mutable_data(), &left[2], server_id_len_); + // There is no half-byte to handle. Server ID is already written in to + // server_id. return true; } if (is_length_odd) { - right[2] |= left[half_len-- + 1]; // Combine the halves of the odd byte. + right[0] |= *(left + --half_len); // Combine the halves of the odd byte. } - memcpy(server_id.mutable_data(), &left[2], half_len); - memcpy(server_id.mutable_data() + half_len, &right[2], - server_id_len_ - half_len); + memcpy(server_id.mutable_data() + half_len, right, server_id_len_ - half_len); return true; } +// Note that |plaintext| includes the first byte of the connection ID. QuicConnectionId LoadBalancerConfig::FourPassEncrypt( absl::Span<uint8_t> plaintext) const { if (plaintext.size() < total_len()) { @@ -151,14 +151,10 @@ // Consolidate left and right into a server ID with minimum copying. if (is_length_odd) { // Combine the halves of the odd byte. - left[half_len + 1] |= right[2]; + right[0] |= left[--half_len]; } - memcpy(plaintext.data() + 1, &left[2], half_len); - if (is_length_odd) { - memcpy(plaintext.data() + 1 + half_len, &right[3], half_len - 1); - } else { - memcpy(plaintext.data() + 1 + half_len, &right[2], half_len); - } + memcpy(plaintext.data() + 1, left, half_len); + memcpy(plaintext.data() + half_len + 1, right, plaintext_len() - half_len); return QuicConnectionId(reinterpret_cast<char*>(plaintext.data()), total_len()); } @@ -195,6 +191,7 @@ ? BuildKey(key, /* encrypt = */ false) : std::optional<AES_KEY>()) {} +// Note that |input| does not include the first byte of the connection ID. bool LoadBalancerConfig::InitializeFourPass(const uint8_t* input, uint8_t* left, uint8_t* right, uint8_t* half_len) const { @@ -210,17 +207,17 @@ memset(right, 0, kLoadBalancerBlockSize); // The first byte is the plaintext/ciphertext length, the second byte will be // the index of the pass. Half the plaintext or ciphertext follows. - left[0] = plaintext_len(); - right[0] = plaintext_len(); - // Leave left_[1], right_[1] as zero. It will be set for each pass. - memcpy(&left[2], input, *half_len); + left[kLoadBalancerBlockSize - 2] = plaintext_len(); + right[kLoadBalancerBlockSize - 2] = plaintext_len(); + // Leave left_[15]], right_[15] as zero. It will be set for each pass. + memcpy(left, input, *half_len); // If is_length_odd, then both left and right will have part of the middle // byte. Then that middle byte will be split in half via the bitmask in the // next step. - memcpy(&right[2], input + (plaintext_len() / 2), *half_len); + memcpy(right, input + (plaintext_len() / 2), *half_len); if (is_length_odd) { - left[*half_len + 1] &= 0xf0; - right[2] &= 0x0f; + left[*half_len - 1] &= 0xf0; + right[0] &= 0x0f; } return is_length_odd; } @@ -230,26 +227,26 @@ uint8_t* right) const { uint8_t ciphertext[kLoadBalancerBlockSize]; if (index % 2 == 0) { // Go right to left. - right[1] = index; + right[kLoadBalancerBlockSize - 1] = index; AES_encrypt(right, ciphertext, &*key_); for (int i = 0; i < half_len; ++i) { // Skip over the first two bytes, which have the plaintext_len and the // index. The CID bits are in [2, half_len - 1]. - left[2 + i] ^= ciphertext[i]; + left[i] ^= ciphertext[i]; } if (is_length_odd) { - left[half_len + 1] &= 0xf0; + left[half_len - 1] &= 0xf0; } return; } // Go left to right. - left[1] = index; + left[kLoadBalancerBlockSize - 1] = index; AES_encrypt(left, ciphertext, &*key_); for (int i = 0; i < half_len; ++i) { - right[2 + i] ^= ciphertext[i]; + right[i] ^= ciphertext[i]; } if (is_length_odd) { - right[2] &= 0x0f; + right[0] &= 0x0f; } }
diff --git a/quiche/quic/load_balancer/load_balancer_config_test.cc b/quiche/quic/load_balancer/load_balancer_config_test.cc index dd34fb1..20dcd55 100644 --- a/quiche/quic/load_balancer/load_balancer_config_test.cc +++ b/quiche/quic/load_balancer/load_balancer_config_test.cc
@@ -104,7 +104,7 @@ } // Compare EncryptionPass() results to the example in -// draft-ietf-quic-load-balancers-15, Section 4.3.2. +// draft-ietf-quic-load-balancers-19, Section 4.3.2. TEST_F(LoadBalancerConfigTest, TestEncryptionPassExample) { auto config = LoadBalancerConfig::Create(0, 3, 4, absl::string_view(raw_key, 16)); @@ -120,30 +120,30 @@ std::array<std::array<uint8_t, kLoadBalancerBlockSize>, kNumLoadBalancerCryptoPasses + 1> expected_left = {{ - {0x07, 0x00, 0x31, 0x44, 0x1a, 0x90, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x01, 0x31, 0x44, 0x1a, 0x90, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x01, 0x02, 0x8e, 0x1b, 0x50, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x03, 0x02, 0x8e, 0x1b, 0x50, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x03, 0x8e, 0x9a, 0x91, 0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, + {0x31, 0x44, 0x1a, 0x90, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x00}, + {0x31, 0x44, 0x1a, 0x90, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x01}, + {0xd4, 0xa0, 0x48, 0x50, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x01}, + {0xd4, 0xa0, 0x48, 0x50, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x03}, + {0x67, 0x94, 0x7d, 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x03}, }}; std::array<std::array<uint8_t, kLoadBalancerBlockSize>, kNumLoadBalancerCryptoPasses + 1> expected_right = {{ - {0x07, 0x00, 0x0c, 0x69, 0xc2, 0x75, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x00, 0x0f, 0x1a, 0x5b, 0x6b, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x02, 0x0f, 0x1a, 0x5b, 0x6b, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x02, 0x04, 0x94, 0x97, 0x62, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, - {0x07, 0x04, 0x04, 0x94, 0x97, 0x62, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00}, + {0x0c, 0x69, 0xc2, 0x75, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x00}, + {0x0e, 0x3c, 0x1f, 0xf9, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x00}, + {0x0e, 0x3c, 0x1f, 0xf9, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x02}, + {0x09, 0xbe, 0x05, 0x4a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x02}, + {0x09, 0xbe, 0x05, 0x4a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x07, 0x04}, }}; EXPECT_EQ(left, expected_left[0]); @@ -163,12 +163,12 @@ auto config = LoadBalancerConfig::Create(0, 3, 4, absl::string_view(raw_key, 16)); std::array<uint8_t, kLoadBalancerBlockSize> start_left = { - 0x07, 0x00, 0x31, 0x44, 0x1a, 0x90, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x31, 0x44, 0x1a, 0x90, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x00, }; std::array<uint8_t, kLoadBalancerBlockSize> start_right = { - 0x07, 0x00, 0x0c, 0x69, 0xc2, 0x75, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x0c, 0x69, 0xc2, 0x75, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07, 0x00, }; std::array<uint8_t, kLoadBalancerBlockSize> left = start_left, right = start_right; @@ -183,8 +183,8 @@ right.data()); // Since index is manually written into the second byte only on input, it is // not reversible. - left[1] = 0; - right[1] = 0; + left[15] = 0; + right[15] = 0; EXPECT_EQ(left, start_left); EXPECT_EQ(right, start_right); } @@ -216,7 +216,7 @@ } // Block decrypt test from the Test Vector in -// draft-ietf-quic-load-balancers-15, Appendix B. +// draft-ietf-quic-load-balancers-19, Appendix B. TEST_F(LoadBalancerConfigTest, BlockEncryptionExample) { const uint8_t ptext[] = {0xed, 0x79, 0x3a, 0x51, 0xd4, 0x9b, 0x8f, 0x5f, 0xee, 0x08, 0x0d, 0xbf, 0x48, 0xc0, 0xd1, 0xe5};
diff --git a/quiche/quic/load_balancer/load_balancer_decoder_test.cc b/quiche/quic/load_balancer/load_balancer_decoder_test.cc index 6e8a399..890557f 100644 --- a/quiche/quic/load_balancer/load_balancer_decoder_test.cc +++ b/quiche/quic/load_balancer/load_balancer_decoder_test.cc
@@ -63,7 +63,7 @@ } } -// Compare test vectors from Appendix B of draft-ietf-quic-load-balancers-15. +// Compare test vectors from Appendix B of draft-ietf-quic-load-balancers-19. TEST_F(LoadBalancerDecoderTest, DecoderTestVectors) { // Try (1) the "standard" CID length of 8 // (2) server_id_len > nonce_len, so there is a fourth decryption pass @@ -72,13 +72,13 @@ const struct LoadBalancerDecoderTestCase test_vectors[4] = { { *LoadBalancerConfig::Create(0, 3, 4, kKey), - QuicConnectionId({0x07, 0x41, 0x26, 0xee, 0x38, 0xbf, 0x54, 0x54}), + QuicConnectionId({0x07, 0x20, 0xb1, 0xd0, 0x7b, 0x35, 0x9d, 0x3c}), MakeServerId(kServerId, 3), }, { *LoadBalancerConfig::Create(1, 10, 5, kKey), - QuicConnectionId({0x2f, 0xcd, 0x3f, 0x57, 0x2d, 0x4e, 0xef, 0xb0, - 0x46, 0xfd, 0xb5, 0x1d, 0x16, 0x4e, 0xfc, 0xcc}), + QuicConnectionId({0x2f, 0xcc, 0x38, 0x1b, 0xc7, 0x4c, 0xb4, 0xfb, + 0xad, 0x28, 0x23, 0xa3, 0xd1, 0xf8, 0xfe, 0xd2}), MakeServerId(kServerId, 10), }, { @@ -89,10 +89,10 @@ MakeServerId(kServerId, 8), }, { - *LoadBalancerConfig::Create(3, 9, 9, kKey), - QuicConnectionId({0x72, 0x12, 0x4d, 0x1e, 0xb8, 0xfb, 0xb2, 0x1e, - 0x4a, 0x49, 0x0c, 0xa5, 0x3c, 0xfe, 0x21, 0xd0, - 0x4a, 0xe6, 0x3a}), + *LoadBalancerConfig::Create(0, 9, 9, kKey), + QuicConnectionId({0x12, 0x57, 0x79, 0xc9, 0xcc, 0x86, 0xbe, 0xb3, + 0xa3, 0xa4, 0xa3, 0xca, 0x96, 0xfc, 0xe4, 0xbf, + 0xe0, 0xcd, 0xbc}), MakeServerId(kServerId, 9), }, };
diff --git a/quiche/quic/load_balancer/load_balancer_encoder_test.cc b/quiche/quic/load_balancer/load_balancer_encoder_test.cc index c48de0d..f776eac 100644 --- a/quiche/quic/load_balancer/load_balancer_encoder_test.cc +++ b/quiche/quic/load_balancer/load_balancer_encoder_test.cc
@@ -194,7 +194,7 @@ } } -// Follow example in draft-ietf-quic-load-balancers-15. +// Follow example in draft-ietf-quic-load-balancers-19. TEST_F(LoadBalancerEncoderTest, FollowSpecExample) { const uint8_t config_id = 0, server_id_len = 3, nonce_len = 4; const uint8_t raw_server_id[] = { @@ -215,14 +215,14 @@ EXPECT_TRUE( encoder->UpdateConfig(*config, LoadBalancerServerId(raw_server_id))); EXPECT_TRUE(encoder->IsEncoding()); - const char raw_connection_id[] = {0x07, 0x8e, 0x9a, 0x91, - 0xf4, 0x94, 0x97, 0x62}; + const char raw_connection_id[] = {0x07, 0x67, 0x94, 0x7d, + 0x29, 0xbe, 0x05, 0x4a}; auto expected = QuicConnectionId(raw_connection_id, 1 + server_id_len + nonce_len); EXPECT_EQ(encoder->GenerateConnectionId(), expected); } -// Compare test vectors from Appendix B of draft-ietf-quic-load-balancers-15. +// Compare test vectors from Appendix B of draft-ietf-quic-load-balancers-19. TEST_F(LoadBalancerEncoderTest, EncoderTestVectors) { // Try (1) the "standard" ConnectionId length of 8 // (2) server_id_len > nonce_len, so there is a fourth decryption pass @@ -231,13 +231,13 @@ const LoadBalancerEncoderTestCase test_vectors[4] = { { *LoadBalancerConfig::Create(0, 3, 4, kKey), - QuicConnectionId({0x07, 0x41, 0x26, 0xee, 0x38, 0xbf, 0x54, 0x54}), + QuicConnectionId({0x07, 0x20, 0xb1, 0xd0, 0x7b, 0x35, 0x9d, 0x3c}), MakeServerId(kServerId, 3), }, { *LoadBalancerConfig::Create(1, 10, 5, kKey), - QuicConnectionId({0x2f, 0xcd, 0x3f, 0x57, 0x2d, 0x4e, 0xef, 0xb0, - 0x46, 0xfd, 0xb5, 0x1d, 0x16, 0x4e, 0xfc, 0xcc}), + QuicConnectionId({0x2f, 0xcc, 0x38, 0x1b, 0xc7, 0x4c, 0xb4, 0xfb, + 0xad, 0x28, 0x23, 0xa3, 0xd1, 0xf8, 0xfe, 0xd2}), MakeServerId(kServerId, 10), }, { @@ -249,9 +249,9 @@ }, { *LoadBalancerConfig::Create(0, 9, 9, kKey), - QuicConnectionId({0x12, 0x12, 0x4d, 0x1e, 0xb8, 0xfb, 0xb2, 0x1e, - 0x4a, 0x49, 0x0c, 0xa5, 0x3c, 0xfe, 0x21, 0xd0, - 0x4a, 0xe6, 0x3a}), + QuicConnectionId({0x12, 0x57, 0x79, 0xc9, 0xcc, 0x86, 0xbe, 0xb3, + 0xa3, 0xa4, 0xa3, 0xca, 0x96, 0xfc, 0xe4, 0xbf, + 0xe0, 0xcd, 0xbc}), MakeServerId(kServerId, 9), }, }; @@ -277,7 +277,7 @@ LoadBalancerEncoderPeer::SetNumNoncesLeft(*encoder, 2); EXPECT_EQ(encoder->num_nonces_left(), 2); EXPECT_EQ(encoder->GenerateConnectionId(), - QuicConnectionId({0x07, 0x1d, 0x4a, 0xb8, 0xc6, 0x1d, 0xd6, 0x5d})); + QuicConnectionId({0x07, 0x29, 0xd8, 0xc2, 0x17, 0xce, 0x2d, 0x92})); EXPECT_EQ(encoder->num_nonces_left(), 1); encoder->GenerateConnectionId(); EXPECT_EQ(encoder->IsEncoding(), false);