Algorithmic Complexity Attacks (HashDoS) & SipHash Defense

Anatomy of a HashDoS Attack: Equivalent Substrings & Meet-in-the-Middle

How does an attacker generate $2^{16} = 65{,}536$ colliding strings in milliseconds?

• Equivalent Two-Char Blocks (Java hashCode / DJB2): In Java's polynomial hash $h(s) = \sum s[i] \cdot 31^{L-1-i} \bmod 2^{32}$, any two-character block $c_1 c_2$ contributes $31 c_1 + c_2$. Since 'A' * 31 + 'a' = 65 * 31 + 97 = 2112 and 'B' * 31 + 'B' = 66 * 31 + 66 = 2112, the substrings "Aa" and "BB" have the exact same hash value! Concatenating $k = 16$ choices of {"Aa", "BB"} produces $2^{16} = 65{,}536$ distinct 32-byte strings with identical hash codes in $O(1)$ effort—and because every character comparison checks the full string prefix before failing, total comparison work reaches $\Theta(N^2 \cdot L)$!
• Seed-Independent Differential Multicollisions (MurmurHash / CityHash): Non-cryptographic hashes like MurmurHash3 and CityHash64 were designed for statistical uniformity (passing SMHasher avalanche tests), not adversarial preimage resistance. Using internal state differentials, attackers construct pairs of blocks $(\Delta_1, \Delta_2)$ that cancel each other inside the mixing rounds regardless of the 32-bit/64-bit startup seed.

Visualizing the SipRound Add-Rotate-XOR (ARX) Butterfly

Production C++20 Implementation: RFC-Compliant SipHash-2-4

// C++20: Reference SipHash-2-4 (Aumasson & Bernstein) for HashDoS-Resistant Tables
#include <cstdint>
#include <cstddef>
#include <bit>
#include <cstring>

class SipHash24 {
    uint64_t k0_, k1_;

    static constexpr void sipRound(uint64_t& v0, uint64_t& v1, uint64_t& v2, uint64_t& v3) noexcept {
        v0 += v1; v1 = std::rotl(v1, 13) ^ v0; v0 = std::rotl(v0, 32);
        v2 += v3; v3 = std::rotl(v3, 16) ^ v2;
        v0 += v3; v3 = std::rotl(v3, 21) ^ v0;
        v2 += v1; v1 = std::rotl(v1, 17) ^ v2; v2 = std::rotl(v2, 32);
    }

public:
    constexpr SipHash24(uint64_t k0, uint64_t k1) noexcept : k0_(k0), k1_(k1) {}

    uint64_t operator()(const uint8_t* data, size_t len) const noexcept {
        uint64_t v0 = k0_ ^ 0x736f6d6570736575ULL;
        uint64_t v1 = k1_ ^ 0x646f72616e646f6dULL;
        uint64_t v2 = k0_ ^ 0x6c7967656e657261ULL;
        uint64_t v3 = k1_ ^ 0x7465646279746573ULL;

        const size_t blocks = len / 8;
        for (size_t i = 0; i < blocks; ++i) {
            uint64_t m = 0;
            std::memcpy(&m, data + i * 8, sizeof(uint64_t));
            v3 ^= m;
            sipRound(v0, v1, v2, v3);
            sipRound(v0, v1, v2, v3); // c = 2 compression rounds
            v0 ^= m;
        }

        // Pack remaining 0..7 bytes in little-endian + (len mod 256) in top byte [56..63]
        uint64_t last = static_cast<uint64_t>(len & 0xff) << 56;
        const uint8_t* tail = data + blocks * 8;
        for (size_t r = 0; r < (len & 7); ++r) {
            last |= static_cast<uint64_t>(tail[r]) << (r * 8);
        }

        v3 ^= last;
        sipRound(v0, v1, v2, v3);
        sipRound(v0, v1, v2, v3);
        v0 ^= last;

        v2 ^= 0xffULL;
        for (int d = 0; d < 4; ++d) sipRound(v0, v1, v2, v3); // d = 4 finalization rounds
        return v0 ^ v1 ^ v2 ^ v3;
    }
};