Never reconstruct 1.3 record numbers above 2^48-1
In DTLS 1.2, it was syntactically impossible to make a record number
over 2^48-1 or an epoch number over 2^16-1. This was nice because it
meant record numbers could be packed into an 8-byte structure.
DTLS 1.3 attempted to lift these constraints, but ineffectively. The
epoch count cannot go past 2^16-1 due to how the message number works.
The outgoing record count has no reason to exceed 2^48-1 because we
would have to send 5 petabytes to count that high even with empty
records, and indeed we check this right now.
The incoming record count is complicated. Record number reconstruction
*could* count that high if we receive 2^33 records (the max we can jump
is 2^15 at a time). This is within the realm of possibility for an
attacker, but too high to practically count via unit tests, and useless
for a well-behaved sender because the sender has no reason to skip
sequence numbers.
The result is that we need to use more memory and worry about a case
that we cannot practically test, which is only useful for attackers.
This is not useful. Instead, change the record number reconstruction
logic to never give back record numbers past 2^48. If the peer manages
to send 5 petabytes and count that high without rekeying, we'll jam the
record number and start dropping those packets. An error would be
preferable, but that would be a codepath we cannot effectively test, so
I opted to just bodge the reconstruction logic.
With this done, we can pack the record numbers again. The next CL will
introduce a DTLSRecordNumber type to abstract the various bit
manipulations we've been doing.
Bug: 42290594
Change-Id: I8bb0584a792578cf1d2a9df0b0c035d794c85beb
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/72270
Auto-Submit: David Benjamin <davidben@google.com>
Reviewed-by: Nick Harper <nharper@chromium.org>
Commit-Queue: Nick Harper <nharper@chromium.org>
diff --git a/ssl/dtls_record.cc b/ssl/dtls_record.cc
index 911dcc6..f769696 100644
--- a/ssl/dtls_record.cc
+++ b/ssl/dtls_record.cc
@@ -123,6 +123,8 @@
BSSL_NAMESPACE_BEGIN
+static constexpr uint64_t kMaxSequenceNumber = (uint64_t{1} << 48) - 1;
+
bool DTLSReplayBitmap::ShouldDiscard(uint64_t seq_num) const {
const size_t kWindowSize = map_.size();
@@ -179,25 +181,31 @@
uint64_t reconstruct_seqnum(uint16_t wire_seq, uint64_t seq_mask,
uint64_t max_valid_seqnum) {
+ // Although DTLS 1.3 can support sequence numbers up to 2^64-1, we continue to
+ // enforce the DTLS 1.2 2^48-1 limit. With a minimal DTLS 1.3 record header (2
+ // bytes), no payload, and 16 byte AEAD overhead, sending 2^48 records would
+ // require 5 petabytes. This allows us to continue to pack a DTLS record
+ // number into an 8-byte structure.
+ assert(max_valid_seqnum <= kMaxSequenceNumber);
+ assert(seq_mask == 0xff || seq_mask == 0xffff);
+
uint64_t max_seqnum_plus_one = max_valid_seqnum + 1;
uint64_t diff = (wire_seq - max_seqnum_plus_one) & seq_mask;
uint64_t step = seq_mask + 1;
+ // This addition cannot overflow. It is at most 2^48 + seq_mask. It, however,
+ // may exceed 2^48-1.
uint64_t seqnum = max_seqnum_plus_one + diff;
- // seqnum is computed as the addition of 3 non-negative values
- // (max_valid_seqnum, 1, and diff). The values 1 and diff are small (relative
- // to the size of a uint64_t), while max_valid_seqnum can span the range of
- // all uint64_t values. If seqnum is less than max_valid_seqnum, then the
- // addition overflowed.
- bool overflowed = seqnum < max_valid_seqnum;
+ bool too_large = seqnum > kMaxSequenceNumber;
// If the diff is larger than half the step size, then the closest seqnum
// to max_seqnum_plus_one (in Z_{2^64}) is seqnum minus step instead of
// seqnum.
bool closer_is_less = diff > step / 2;
// Subtracting step from seqnum will cause underflow if seqnum is too small.
bool would_underflow = seqnum < step;
- if (overflowed || (closer_is_less && !would_underflow)) {
+ if (too_large || (closer_is_less && !would_underflow)) {
seqnum -= step;
}
+ assert(seqnum <= kMaxSequenceNumber);
return seqnum;
}
@@ -491,7 +499,6 @@
const size_t record_header_len = dtls_record_header_write_len(ssl, epoch);
// Ensure the sequence number update does not overflow.
- const uint64_t kMaxSequenceNumber = (uint64_t{1} << 48) - 1;
if (write_epoch->next_seq + 1 > kMaxSequenceNumber) {
OPENSSL_PUT_ERROR(SSL, ERR_R_OVERFLOW);
return false;
diff --git a/ssl/internal.h b/ssl/internal.h
index 29a674c..0f3bd82 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -1222,6 +1222,9 @@
// successfully deprotected in this epoch. This function returns the sequence
// number that is numerically closest to one plus |max_valid_seqnum| that when
// bitwise and-ed with |seq_mask| equals |wire_seq|.
+//
+// |max_valid_seqnum| must be most 2^48-1, in which case the output will also be
+// at most 2^48-1.
OPENSSL_EXPORT uint64_t reconstruct_seqnum(uint16_t wire_seq, uint64_t seq_mask,
uint64_t max_valid_seqnum);
diff --git a/ssl/ssl_internal_test.cc b/ssl/ssl_internal_test.cc
index 2cca65a..b6abafd 100644
--- a/ssl/ssl_internal_test.cc
+++ b/ssl/ssl_internal_test.cc
@@ -399,16 +399,13 @@
EXPECT_EQ(reconstruct_seqnum(0xffff, 0xffff, 0x2f000), 0x2ffffu);
EXPECT_EQ(reconstruct_seqnum(0xfffe, 0xffff, 0x2f000), 0x2fffeu);
- // Test that reconstruct_seqnum can return
- // std::numeric_limits<uint64_t>::max().
- EXPECT_EQ(reconstruct_seqnum(0xff, 0xff, 0xffffffffffffffff),
- std::numeric_limits<uint64_t>::max());
- EXPECT_EQ(reconstruct_seqnum(0xff, 0xff, 0xfffffffffffffffe),
- std::numeric_limits<uint64_t>::max());
- EXPECT_EQ(reconstruct_seqnum(0xffff, 0xffff, 0xffffffffffffffff),
- std::numeric_limits<uint64_t>::max());
- EXPECT_EQ(reconstruct_seqnum(0xffff, 0xffff, 0xfffffffffffffffe),
- std::numeric_limits<uint64_t>::max());
+ // Test that reconstruct_seqnum can return the maximum sequence number,
+ // 2^48-1.
+ constexpr uint64_t kMaxSequence = (uint64_t{1} << 48) - 1;
+ EXPECT_EQ(reconstruct_seqnum(0xff, 0xff, kMaxSequence), kMaxSequence);
+ EXPECT_EQ(reconstruct_seqnum(0xff, 0xff, kMaxSequence - 1), kMaxSequence);
+ EXPECT_EQ(reconstruct_seqnum(0xffff, 0xffff, kMaxSequence), kMaxSequence);
+ EXPECT_EQ(reconstruct_seqnum(0xffff, 0xffff, kMaxSequence - 1), kMaxSequence);
}
TEST(ReconstructSeqnumTest, Decrement) {
@@ -431,35 +428,35 @@
EXPECT_EQ(reconstruct_seqnum(0xffff, 0xffff, 0x20000), 0x1ffffu);
EXPECT_EQ(reconstruct_seqnum(0xfffe, 0xffff, 0x20000), 0x1fffeu);
- // Test when the max seen sequence number is close to the uint64_t max value.
- // In some cases, the closest numerical value in the integers will overflow
- // a uint64_t. Instead of returning the closest value in Z_{2^64},
- // reconstruct_seqnum should return the closest integer less than 2^64, even
- // if there is a closer value greater than 2^64.
- EXPECT_EQ(reconstruct_seqnum(0, 0xff, 0xffffffffffffffff),
- 0xffffffffffffff00u);
- EXPECT_EQ(reconstruct_seqnum(0, 0xff, 0xfffffffffffffffe),
- 0xffffffffffffff00u);
- EXPECT_EQ(reconstruct_seqnum(1, 0xff, 0xffffffffffffffff),
- 0xffffffffffffff01u);
- EXPECT_EQ(reconstruct_seqnum(1, 0xff, 0xfffffffffffffffe),
- 0xffffffffffffff01u);
- EXPECT_EQ(reconstruct_seqnum(0xfe, 0xff, 0xffffffffffffffff),
- 0xfffffffffffffffeu);
- EXPECT_EQ(reconstruct_seqnum(0xfd, 0xff, 0xfffffffffffffffe),
- 0xfffffffffffffffdu);
- EXPECT_EQ(reconstruct_seqnum(0, 0xffff, 0xffffffffffffffff),
- 0xffffffffffff0000u);
- EXPECT_EQ(reconstruct_seqnum(0, 0xffff, 0xfffffffffffffffe),
- 0xffffffffffff0000u);
- EXPECT_EQ(reconstruct_seqnum(1, 0xffff, 0xffffffffffffffff),
- 0xffffffffffff0001u);
- EXPECT_EQ(reconstruct_seqnum(1, 0xffff, 0xfffffffffffffffe),
- 0xffffffffffff0001u);
- EXPECT_EQ(reconstruct_seqnum(0xfffe, 0xffff, 0xffffffffffffffff),
- 0xfffffffffffffffeu);
- EXPECT_EQ(reconstruct_seqnum(0xfffd, 0xffff, 0xfffffffffffffffe),
- 0xfffffffffffffffdu);
+ constexpr uint64_t kMaxSequence = (uint64_t{1} << 48) - 1;
+ // kMaxSequence00 is kMaxSequence with the last byte replaced with 0x00.
+ constexpr uint64_t kMaxSequence00 = kMaxSequence - 0xff;
+ // kMaxSequence0000 is kMaxSequence with the last byte replaced with 0x0000.
+ constexpr uint64_t kMaxSequence0000 = kMaxSequence - 0xffff;
+
+ // Test when the max seen sequence number is close to the 2^48-1 max value.
+ // In some cases, the closest numerical value in the integers will exceed the
+ // limit. In this case, reconstruct_seqnum should return the closest integer
+ // within range.
+ EXPECT_EQ(reconstruct_seqnum(0, 0xff, kMaxSequence), kMaxSequence00);
+ EXPECT_EQ(reconstruct_seqnum(0, 0xff, kMaxSequence - 1), kMaxSequence00);
+ EXPECT_EQ(reconstruct_seqnum(1, 0xff, kMaxSequence), kMaxSequence00 + 0x01);
+ EXPECT_EQ(reconstruct_seqnum(1, 0xff, kMaxSequence - 1),
+ kMaxSequence00 + 0x01);
+ EXPECT_EQ(reconstruct_seqnum(0xfe, 0xff, kMaxSequence),
+ kMaxSequence00 + 0xfe);
+ EXPECT_EQ(reconstruct_seqnum(0xfd, 0xff, kMaxSequence - 1),
+ kMaxSequence00 + 0xfd);
+ EXPECT_EQ(reconstruct_seqnum(0, 0xffff, kMaxSequence), kMaxSequence0000);
+ EXPECT_EQ(reconstruct_seqnum(0, 0xffff, kMaxSequence - 1), kMaxSequence0000);
+ EXPECT_EQ(reconstruct_seqnum(1, 0xffff, kMaxSequence),
+ kMaxSequence0000 + 0x0001);
+ EXPECT_EQ(reconstruct_seqnum(1, 0xffff, kMaxSequence - 1),
+ kMaxSequence0000 + 0x0001);
+ EXPECT_EQ(reconstruct_seqnum(0xfffe, 0xffff, kMaxSequence),
+ kMaxSequence0000 + 0xfffe);
+ EXPECT_EQ(reconstruct_seqnum(0xfffd, 0xffff, kMaxSequence - 1),
+ kMaxSequence0000 + 0xfffd);
}
TEST(ReconstructSeqnumTest, Halfway) {
