Brief description
Upon receiving each incoming request header data, Envoy will iterate over existing request headers to verify that the total size of the headers stays below a maximum limit. The implementation in versions 1.10.0 and after for HTTP/1.x traffic and all versions of Envoy for HTTP/2 traffic had O(n^2) performance characteristics. A remote attacker may craft a request that stays below the maximum request header size but consists of many thousands of small headers to consume CPU and result in a denial-of-service attack.
CVSS
CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H (7.5, High)
Affected version(s)
Envoy 1.10.0 and after are affected for HTTP/1.x traffic. All Envoy versions for HTTP/2 traffic. Fix will be in 1.11.2.
Affected component(s)
HTTP/1.x codec, HTTP/2 codec, HeaderMap implementation
Attack vector(s)
A request that consists of thousands of very small headers. For example, an HTTP/1.1 POST request containing thousands of very small headers.
Discover(s)/Credits
Asra Ali, Google
Harvey Tuch, Google
Example exploit or proof-of-concept
X sends an HTTP/1.1 POST request with 10,000 tiny headers “x-0: ”, …, “x-10000: ” each second.
Upon receiving each incoming header value, Envoy verifies that the total request header size is below the maximum limit using a for loop over the existing header map in the implementation for byteSize().
Details
Both the HTTP/1.1 and HTTP/2 codec limit the maximum size of all request headers. To verify this limit, the byteSize() method of the HeaderMap is called. This method returns the estimated size of the HeaderMap by calculating the sum of each HeaderEntry key-value pair in the HeaderMap. Each time Envoy adds a header, it calls byteSize() to verify that the resulting HeaderMap will remain below the limit. This results in an O(n^2) operation in the number of headers.
The issue was first noticed via a timeout in Envoy’s wire-level HTTP/1.1 fuzzer: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=16325
Mitigations
In some situations, the maximum request header size can likely be smaller than the default limit of 60 KiB. This is configurable in the HTTP Connection Manager configuration. Lowering this limit can reduce the number of request headers, and possibly mitigate excessive CPU consumption.
Detection
Envoy’s exposes the loop duration and poll delay to monitor performance of the event loops on worker threads, so it is possible to examine these statistics to detect suspicious CPU resource consumption. Elevated worker thread dispatcher.loop_duration_us statistics will provide circumstantial evidence of an ongoing attack. These statistics can be enabled by setting enable_dispatcher_stats to true.
References
CVE-2019-15226
Brief description
Upon receiving each incoming request header data, Envoy will iterate over existing request headers to verify that the total size of the headers stays below a maximum limit. The implementation in versions 1.10.0 and after for HTTP/1.x traffic and all versions of Envoy for HTTP/2 traffic had O(n^2) performance characteristics. A remote attacker may craft a request that stays below the maximum request header size but consists of many thousands of small headers to consume CPU and result in a denial-of-service attack.
CVSS
CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H (7.5, High)
Affected version(s)
Envoy 1.10.0 and after are affected for HTTP/1.x traffic. All Envoy versions for HTTP/2 traffic. Fix will be in 1.11.2.
Affected component(s)
HTTP/1.x codec, HTTP/2 codec, HeaderMap implementation
Attack vector(s)
A request that consists of thousands of very small headers. For example, an HTTP/1.1 POST request containing thousands of very small headers.
Discover(s)/Credits
Asra Ali, Google
Harvey Tuch, Google
Example exploit or proof-of-concept
X sends an HTTP/1.1 POST request with 10,000 tiny headers “x-0: ”, …, “x-10000: ” each second.
Upon receiving each incoming header value, Envoy verifies that the total request header size is below the maximum limit using a for loop over the existing header map in the implementation for byteSize().
Details
Both the HTTP/1.1 and HTTP/2 codec limit the maximum size of all request headers. To verify this limit, the
byteSize()method of the HeaderMap is called. This method returns the estimated size of the HeaderMap by calculating the sum of each HeaderEntry key-value pair in the HeaderMap. Each time Envoy adds a header, it callsbyteSize()to verify that the resulting HeaderMap will remain below the limit. This results in an O(n^2) operation in the number of headers.The issue was first noticed via a timeout in Envoy’s wire-level HTTP/1.1 fuzzer: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=16325
Mitigations
In some situations, the maximum request header size can likely be smaller than the default limit of 60 KiB. This is configurable in the HTTP Connection Manager configuration. Lowering this limit can reduce the number of request headers, and possibly mitigate excessive CPU consumption.
Detection
Envoy’s exposes the loop duration and poll delay to monitor performance of the event loops on worker threads, so it is possible to examine these statistics to detect suspicious CPU resource consumption. Elevated worker thread dispatcher.loop_duration_us statistics will provide circumstantial evidence of an ongoing attack. These statistics can be enabled by setting enable_dispatcher_stats to true.
References