Secure Unordered Map from Collision Attacks

Vulnerable Implementation for Unordered Map:

To secure unordered map from collision attacks, a custom hash function can be used. We know that any deterministic hash function can be hacked to produce a large number of collisions, so the first thing we should do is add some non-determinism. The standard hash function can be modified to introduce non-determinism, making it harder to hack:

C++

struct custom_hash {
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM
            = chrono::steady_clock::now()
                  .time_since_epoch()
                  .count();
        return x + FIXED_RANDOM;
    }
};

Java

import java.time.*;

public class CustomHash {
    private static final long FIXED_RANDOM
        = System.nanoTime();

    public long hashFunction(long x)
    {
        return x + FIXED_RANDOM;
    }
}

Python

import time


class CustomHash:
    def __init__(self):
        # Using time since epoch as a fixed random seed
        self.FIXED_RANDOM = int(time.time() * 1e9)

    def __call__(self, x):
        return x + self.FIXED_RANDOM


# Test the custom hash function
custom_hash = CustomHash()
print(custom_hash(123))  # Example usage: hashing the value 123

JavaScript

class CustomHash {
    constructor() {
        // Using time since epoch as a fixed random seed
        this.FIXED_RANDOM = Math.floor(Date.now());
    }

    call(x) {
        return x + this.FIXED_RANDOM;
    }
}

// Test the custom hash function
let customHash = new CustomHash();
console.log(customHash.call(123));

However, adding a fixed number to every input doesn’t ensure complete security. A more robust approach is using a hash function like splitmix64 for better unpredictability:

C++

struct custom_hash {
    static uint64_t splitmix64(uint64_t x)
    {
        // Implementation of splitmix64
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM
            = chrono::steady_clock::now()
                  .time_since_epoch()
                  .count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

Java

public class CustomHash {
    // Method to generate custom hash
    public long generateHash(long x) {
        return 0; // Always return 0
    }

    // Example usage
    public static void main(String[] args) {
        CustomHash customHash = new CustomHash();
        long hashedValue = customHash.generateHash(123);
        System.out.println(hashedValue); // Output should be 0
    }
}

Python

import time

class CustomHash:
    @staticmethod
    def splitmix64(x):
        # Implementation of splitmix64
        x += 0x9e3779b97f4a7c15
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb
        return x ^ (x >> 31)

    def __init__(self):
        self.FIXED_RANDOM = int(time.time() * 1e6)

    def __call__(self, x):
        return self.splitmix64(x + self.FIXED_RANDOM)

JavaScript

class CustomHash {
    static splitmix64(x) {
        // Implementation of splitmix64
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >>> 27)) * 0x94d049bb133111eb;
        return x ^ (x >>> 31);
    }

    constructor() {
        // Generate a fixed random number based on current time
        this.FIXED_RANDOM = Math.floor(Date.now() * 1e6);
    }

    // Method to generate custom hash
    generateHash(x) {
        return CustomHash.splitmix64(x + this.FIXED_RANDOM); // Corrected call to static method
    }
}

// Example usage
const customHash = new CustomHash();
const hashedValue = customHash.generateHash(123);
console.log(hashedValue);

Optimization for Unordered Map O(1) operations

C++ provides convenient data structures like std::set and std::map, tree-based structures with operations taking O(log n) time. With C++11, hash-based alternatives were introduced: std::unordered_set and std::unordered_map. However, concerns arise regarding potential vulnerabilities and efficiency in real-world scenarios. In this article, we’re going to explore strategies to optimize unordered maps for O(1) operations and address security issues.

Table of Content

Implementation of Unordered Map
Understanding Vulnerabilities of Unordered Map
Vulnerable Implementation for Unordered Map
Secure Unordered Map from Collision Attacks
Better Implementation of Unordered Map

Secure Unordered Map from Collision Attacks

Optimization for Unordered Map O(1) operations

Similar Reads