Dealing with DoS when using a HashMap

matklad · May 22, 2023, 12:09pm

I’ve noticed that, by default, Zig hash map doesn’t depend on random number generation, and instantiates a particular hash function with a fixed seed. It seems to me that this is potentially vulnurable to a DoS attack, when the attacker can craft hash map entries which force collisions.

In particular, it seems that recently added http server has this problem when dealing with headers:

github.com

ziglang/zig/blob/a1bb9e94d402eb678635fc92fe7f990a69fd144c/lib/std/http/Headers.zig#L11


      
          const std = @import("../std.zig");
          
          
const Allocator = std.mem.Allocator;
          
          
const testing = std.testing;
          const ascii = std.ascii;
          const assert = std.debug.assert;
          
          
pub const HeaderList = std.ArrayListUnmanaged(Field);
          pub const HeaderIndexList = std.ArrayListUnmanaged(usize);
          pub const HeaderIndex = std.HashMapUnmanaged([]const u8, HeaderIndexList, CaseInsensitiveStringContext, std.hash_map.default_max_load_percentage);
          
          
pub const CaseInsensitiveStringContext = struct {
              pub fn hash(self: @This(), s: []const u8) u64 {
                  _ = self;
                  var buf: [64]u8 = undefined;
                  var i: u8 = 0;
          
          
        var h = std.hash.Wyhash.init(0);
                  while (i < s.len) : (i += 64) {
                      const left = @min(64, s.len - i);

Am I correct that the code as is is vulnerable to DoS? That is, that a malicious client can send a sequence of headers which would require O(N^2) CPU time to process?

What would be the correct and idiomatic way to fix that?