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?

jedisct1 · June 12, 2023, 9:01am

The way to defend against this class of attack is to use a cryptographic hash function (for example std.crypto.auth.siphash.SipHash128(1,2) with a secret key (not 0).

Jorropo · June 14, 2023, 12:16pm

Cryptographic hash functions are secure when you use enough bits if your hashmap is not EiBs big you will only use very little bits, it is easy to find collisions on the few bits your hashmap will use, you will run out of memory way before a cryptographic hash function is secure.

andrewrk · June 18, 2023, 11:20pm

Would you initialize the secret key at runtime with random bytes? Or hard-code the secret key into the source for determinism?

huntrss · June 19, 2023, 5:48am

This needs to be done at runtime. Using a key in source would mean the adversary can just use this information and forge an attack based on this key.

AndrewCodeDev · June 19, 2023, 5:54am

This needs to be done at runtime. Using a key in source would mean the adversary can just use this information and forge an attack based on this key.

+1 - especially when insider attacks are 20% of data breaches these days.