CVE-2015-2312: Uncontrolled Resource Consumption (CWE-400)
value: Sandstorm Cap'n Proto before 0.4.1.1 and 0.5.x before 0.5.1.1 allows remote peers to cause a denial of service (CPU and possibly general resource consumption) via a list with a large number of elements.
CWE description: The product does not properly control the allocation and maintenance of a limited resource, thereby enabling an actor to influence the amount of resources consumed, eventually leading to the exhaustion of available resources.
CVSS v3 base score: 7.5
Published: 2017-08-09T18:29Z
Repository: https://github.com/capnproto/capnproto
Language: Other
Files changed: CONTRIBUTORS, c++/src/capnp/arena.h, c++/src/capnp/encoding-test.c++, c++/src/capnp/layout.c++
Commit date: 2015-03-02 12:33:54 -0800
Commit message: SECURITY: CPU usage amplification attack.

Details: https://github.com/sandstorm-io/capnproto/tree/master/security-advisories/2014-03-02-0-all-cpu-amplification.md

Diff: diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index 82800200..47ac10ba 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -8,8 +8,9 @@ Remy Blank <rblank@google.com> (contributions copyright Google Inc.): KJ Timers
 Joshua Warner <joshuawarner32@gmail.com>: cmake build, AnyStruct/AnyList, other stuff
 Scott Purdy <scott@fer.io>: kj/std iostream interface
 Bryan Borham <bjboreham@gmail.com>: Initial MSVC support
 Philip Quinn <p@partylemon.com>: cmake build and other assorted bits
 Brian Taylor <el.wubo@gmail.com>: emacs syntax highlighting
+Ben Laurie <ben@links.org>: discovered and responsibly disclosed security bugs
 
 This file does not list people who maintain their own Cap'n Proto
 implementations as separate projects.  Those people are awesome too!  :)
diff --git a/c++/src/capnp/arena.h b/c++/src/capnp/arena.h
index 5b28e8de..2b14fa55 100644
--- a/c++/src/capnp/arena.h
+++ b/c++/src/capnp/arena.h
@@ -115,10 +115,17 @@ public:
   inline SegmentReader(Arena* arena, SegmentId id, kj::ArrayPtr<const word> ptr,
                        ReadLimiter* readLimiter);
 
   KJ_ALWAYS_INLINE(bool containsInterval(const void* from, const void* to));
 
+  KJ_ALWAYS_INLINE(bool amplifiedRead(WordCount virtualAmount));
+  // Indicates that the reader should pretend that `virtualAmount` additional data was read even
+  // though no actual pointer was traversed. This is used e.g. when reading a struct list pointer
+  // where the element sizes are zero -- the sender could set the list size arbitrarily high and
+  // cause the receiver to iterate over this list even though the message itself is small, so we
+  // need to defend agaisnt DoS attacks based on this.
+
   inline Arena* getArena();
   inline SegmentId getSegmentId();
 
   inline const word* getStartPtr();
   inline WordCount getOffsetTo(const word* ptr);
@@ -365,10 +372,14 @@ inline bool SegmentReader::containsInterval(const void* from, const void* to) {
           intervalLength(reinterpret_cast<const byte*>(from),
                          reinterpret_cast<const byte*>(to)) / BYTES_PER_WORD,
           arena);
 }
 
+inline bool SegmentReader::amplifiedRead(WordCount virtualAmount) {
+  return readLimiter->canRead(virtualAmount, arena);
+}
+
 inline Arena* SegmentReader::getArena() { return arena; }
 inline SegmentId SegmentReader::getSegmentId() { return id; }
 inline const word* SegmentReader::getStartPtr() { return ptr.begin(); }
 inline WordCount SegmentReader::getOffsetTo(const word* ptr) {
   return intervalLength(this->ptr.begin(), ptr);
diff --git a/c++/src/capnp/encoding-test.c++ b/c++/src/capnp/encoding-test.c++
index e93b09b0..6bf07adf 100644
--- a/c++/src/capnp/encoding-test.c++
+++ b/c++/src/capnp/encoding-test.c++
@@ -1408,10 +1408,40 @@ TEST(Encoding, Has) {
   EXPECT_TRUE(root.asReader().hasDataField());
   EXPECT_TRUE(root.asReader().hasStructField());
   EXPECT_TRUE(root.asReader().hasInt32List());
 }
 
+TEST(Encoding, VoidListAmplification) {
+  MallocMessageBuilder builder;
+  builder.initRoot<test::TestAnyPointer>().getAnyPointerField().initAs<List<Void>>(1u << 28);
+
+  auto segments = builder.getSegmentsForOutput();
+  EXPECT_EQ(1, segments.size());
+  EXPECT_LT(segments[0].size(), 16);  // quite small for such a big list!
+
+  SegmentArrayMessageReader reader(builder.getSegmentsForOutput());
+  auto root = reader.getRoot<test::TestAnyPointer>().getAnyPointerField();
+  EXPECT_NONFATAL_FAILURE(root.getAs<List<TestAllTypes>>());
+
+  MallocMessageBuilder copy;
+  EXPECT_NONFATAL_FAILURE(copy.setRoot(reader.getRoot<AnyPointer>()));
+}
+
+TEST(Encoding, EmptyStructListAmplification) {
+  MallocMessageBuilder builder;
+  builder.initRoot<test::TestAnyPointer>().getAnyPointerField()
+      .initAs<List<test::TestEmptyStruct>>(1u << 28);
+
+  auto segments = builder.getSegmentsForOutput();
+  EXPECT_EQ(1, segments.size());
+  EXPECT_LT(segments[0].size(), 16);  // quite small for such a big list!
+
+  SegmentArrayMessageReader reader(builder.getSegmentsForOutput());
+  auto root = reader.getRoot<test::TestAnyPointer>().getAnyPointerField();
+  EXPECT_NONFATAL_FAILURE(root.getAs<List<TestAllTypes>>());
+}
+
 TEST(Encoding, Constants) {
   EXPECT_EQ(VOID, test::TestConstants::VOID_CONST);
   EXPECT_EQ(true, test::TestConstants::BOOL_CONST);
   EXPECT_EQ(-123, test::TestConstants::INT8_CONST);
   EXPECT_EQ(-12345, test::TestConstants::INT16_CONST);
diff --git a/c++/src/capnp/layout.c++ b/c++/src/capnp/layout.c++
index 5956bb99..aa90fbfc 100644
--- a/c++/src/capnp/layout.c++
+++ b/c++/src/capnp/layout.c++
@@ -306,10 +306,15 @@ struct WireHelpers {
       SegmentReader* segment, const word* start, const word* end)) {
     // If segment is null, this is an unchecked message, so we don't do bounds checks.
     return segment == nullptr || segment->containsInterval(start, end);
   }
 
+  static KJ_ALWAYS_INLINE(bool amplifiedRead(SegmentReader* segment, WordCount virtualAmount)) {
+    // If segment is null, this is an unchecked message, so we don't do read limiter checks.
+    return segment == nullptr || segment->amplifiedRead(virtualAmount);
+  }
+
   static KJ_ALWAYS_INLINE(word* allocate(
       WirePointer*& ref, SegmentBuilder*& segment, WordCount amount,
       WirePointer::Kind kind, BuilderArena* orphanArena)) {
     // Allocate space in the message for a new object, creating far pointers if necessary.
     //
@@ -1673,10 +1678,19 @@ struct WireHelpers {
           KJ_REQUIRE(wordsPerElement * ElementCount64(elementCount) <= wordCount,
                      "INLINE_COMPOSITE list's elements overrun its word count.") {
             goto useDefault;
           }
 
+          if (wordsPerElement * (1 * ELEMENTS) == 0 * WORDS) {
+            // Watch out for lists of zero-sized structs, which can claim to be arbitrarily large
+            // without having sent actual data.
+            KJ_REQUIRE(amplifiedRead(srcSegment, elementCount * (1 * WORDS / ELEMENTS)),
+                       "Message contains amplified list pointer.") {
+              goto useDefault;
+            }
+          }
+
           return setListPointer(dstSegment, dst,
               ListReader(srcSegment, ptr, elementCount, wordsPerElement * BITS_PER_WORD,
                          tag->structRef.dataSize.get() * BITS_PER_WORD,
                          tag->structRef.ptrCount.get(), ElementSize::INLINE_COMPOSITE,
                          nestingLimit - 1),
@@ -1691,10 +1705,19 @@ struct WireHelpers {
           KJ_REQUIRE(boundsCheck(srcSegment, ptr, ptr + wordCount),
                      "Message contains out-of-bounds list pointer.") {
             goto useDefault;
           }
 
+          if (elementSize == ElementSize::VOID) {
+            // Watch out for lists of void, which can claim to be arbitrarily large without having
+            // sent actual data.
+            KJ_REQUIRE(amplifiedRead(srcSegment, elementCount * (1 * WORDS / ELEMENTS)),
+                       "Message contains amplified list pointer.") {
+              goto useDefault;
+            }
+          }
+
           return setListPointer(dstSegment, dst,
               ListReader(srcSegment, ptr, elementCount, step, dataSize, pointerCount, elementSize,
                          nestingLimit - 1),
               orphanArena);
         }
@@ -1929,10 +1952,19 @@ struct WireHelpers {
       KJ_REQUIRE(ElementCount64(size) * wordsPerElement <= wordCount,
                  "INLINE_COMPOSITE list's elements overrun its word count.") {
         goto useDefault;
       }
 
+      if (wordsPerElement * (1 * ELEMENTS) == 0 * WORDS) {
+        // Watch out for lists of zero-sized structs, which can claim to be arbitrarily large
+        // without having sent actual data.
+        KJ_REQUIRE(amplifiedRead(segment, size * (1 * WORDS / ELEMENTS)),
+                   "Message contains amplified list pointer.") {
+          goto useDefault;
+        }
+      }
+
       if (checkElementSize) {
         // If a struct list was not expected, then presumably a non-struct list was upgraded to a
         // struct list.  We need to manipulate the pointer to point at the first field of the
         // struct.  Together with the "stepBits", this will allow the struct list to be accessed as
         // if it were a primitive list without branching.
@@ -1986,18 +2018,28 @@ struct WireHelpers {
       // This is a primitive or pointer list, but all such lists can also be interpreted as struct
       // lists.  We need to compute the data size and pointer count for such structs.
       BitCount dataSize = dataBitsPerElement(ref->listRef.elementSize()) * ELEMENTS;
       WirePointerCount pointerCount =
           pointersPerElement(ref->listRef.elementSize()) * ELEMENTS;
+      ElementCount elementCount = ref->listRef.elementCount();
       auto step = (dataSize + pointerCount * BITS_PER_POINTER) / ELEMENTS;
 
-      KJ_REQUIRE(boundsCheck(segment, ptr, ptr +
-                     roundBitsUpToWords(ElementCount64(ref->listRef.elementCount()) * step)),
+      WordCount wordCount = roundBitsUpToWords(ElementCount64(elementCount) * step);
+      KJ_REQUIRE(boundsCheck(segment, ptr, ptr + wordCount),
                  "Message contains out-of-bounds list pointer.") {
         goto useDefault;
       }
 
+      if (elementSize == ElementSize::VOID) {
+        // Watch out for lists of void, which can claim to be arbitrarily large without having sent
+        // actual data.
+        KJ_REQUIRE(amplifiedRead(segment, elementCount * (1 * WORDS / ELEMENTS)),
+                   "Message contains amplified list pointer.") {
+          goto useDefault;
+        }
+      }
+
       if (checkElementSize) {
         if (elementSize == ElementSize::BIT && expectedElementSize != ElementSize::BIT) {
           KJ_FAIL_REQUIRE(
               "Found bit list where struct list was expected; upgrading boolean lists to structs "
               "is no longer supported.") {
@@ -2023,11 +2065,11 @@ struct WireHelpers {
                    "Message contained list with incompatible element type.") {
           goto useDefault;
         }
       }
 
-      return ListReader(segment, ptr, ref->listRef.elementCount(), step,
+      return ListReader(segment, ptr, elementCount, step,
                         dataSize, pointerCount, elementSize, nestingLimit - 1);
     }
   }
 
   static KJ_ALWAYS_INLINE(Text::Reader readTextPointer(

Vulnerable code:       KJ_REQUIRE(boundsCheck(segment, ptr, ptr +
                     roundBitsUpToWords(ElementCount64(ref->listRef.elementCount()) * step)),
      return ListReader(segment, ptr, ref->listRef.elementCount(), step,
Fixed code: Ben Laurie <ben@links.org>: discovered and responsibly disclosed security bugs
  KJ_ALWAYS_INLINE(bool amplifiedRead(WordCount virtualAmount));
  // Indicates that the reader should pretend that `virtualAmount` additional data was read even
  // though no actual pointer was traversed. This is used e.g. when reading a struct list pointer
  // where the element sizes are zero -- the sender could set the list size arbitrarily high and
  // cause the receiver to iterate over this list even though the message itself is small, so we
  // need to defend agaisnt DoS attacks based on this.

inline bool SegmentReader::amplifiedRead(WordCount virtualAmount) {
  return readLimiter->canRead(virtualAmount, arena);
}

TEST(Encoding, VoidListAmplification) {
  MallocMessageBuilder builder;
  builder.initRoot<test::TestAnyPointer>().getAnyPointerField().initAs<List<Void>>(1u << 28);

  auto segments = builder.getSegmentsForOutput();
  EXPECT_EQ(1, segments.size());
  EXPECT_LT(segments[0].size(), 16);  // quite small for such a big list!

  SegmentArrayMessageReader reader(builder.getSegmentsForOutput());
  auto root = reader.getRoot<test::TestAnyPointer>().getAnyPointerField();
  EXPECT_NONFATAL_FAILURE(root.getAs<List<TestAllTypes>>());

  MallocMessageBuilder copy;
  EXPECT_NONFATAL_FAILURE(copy.setRoot(reader.getRoot<AnyPointer>()));
}

TEST(Encoding, EmptyStructListAmplification) {
  MallocMessageBuilder builder;
  builder.initRoot<test::TestAnyPointer>().getAnyPointerField()
      .initAs<List<test::TestEmptyStruct>>(1u << 28);

  auto segments = builder.getSegmentsForOutput();
  EXPECT_EQ(1, segments.size());
  EXPECT_LT(segments[0].size(), 16);  // quite small for such a big list!

  SegmentArrayMessageReader reader(builder.getSegmentsForOutput());
  auto root = reader.getRoot<test::TestAnyPointer>().getAnyPointerField();
  EXPECT_NONFATAL_FAILURE(root.getAs<List<TestAllTypes>>());
}

  static KJ_ALWAYS_INLINE(bool amplifiedRead(SegmentReader* segment, WordCount virtualAmount)) {
    // If segment is null, this is an unchecked message, so we don't do read limiter checks.
    return segment == nullptr || segment->amplifiedRead(virtualAmount);
  }

          if (wordsPerElement * (1 * ELEMENTS) == 0 * WORDS) {
            // Watch out for lists of zero-sized structs, which can claim to be arbitrarily large
            // without having sent actual data.
            KJ_REQUIRE(amplifiedRead(srcSegment, elementCount * (1 * WORDS / ELEMENTS)),
                       "Message contains amplified list pointer.") {
              goto useDefault;
            }
          }

          if (elementSize == ElementSize::VOID) {
            // Watch out for lists of void, which can claim to be arbitrarily large without having
            // sent actual data.
            KJ_REQUIRE(amplifiedRead(srcSegment, elementCount * (1 * WORDS / ELEMENTS)),
                       "Message contains amplified list pointer.") {
              goto useDefault;
            }
          }

      if (wordsPerElement * (1 * ELEMENTS) == 0 * WORDS) {
        // Watch out for lists of zero-sized structs, which can claim to be arbitrarily large
        // without having sent actual data.
        KJ_REQUIRE(amplifiedRead(segment, size * (1 * WORDS / ELEMENTS)),
                   "Message contains amplified list pointer.") {
          goto useDefault;
        }
      }

      ElementCount elementCount = ref->listRef.elementCount();
      WordCount wordCount = roundBitsUpToWords(ElementCount64(elementCount) * step);
      KJ_REQUIRE(boundsCheck(segment, ptr, ptr + wordCount),
      if (elementSize == ElementSize::VOID) {
        // Watch out for lists of void, which can claim to be arbitrarily large without having sent
        // actual data.
        KJ_REQUIRE(amplifiedRead(segment, elementCount * (1 * WORDS / ELEMENTS)),
                   "Message contains amplified list pointer.") {
          goto useDefault;
        }
      }

      return ListReader(segment, ptr, elementCount, step,