Bloom 필터를 사용하여 2MB RAM에서 800M 유출된 암호 확인

When users register or change their passwords, security guidelines (like NIST SP 800-63B) recommend checking their chosen password against a database of known breached passwords.

Data feeds like HaveIBeenPwned contain over 800 million leaked password hashes.

Storing 800 million SHA-1 hashes (20 bytes each) in a standard Hash Map or Redis set requires at least 16 GB of RAM. Performing a SQL database query on every password change adds unnecessary latency to your authentication pipeline.

In this post, we’ll explore how to use a probabilistic data structure—the Bloom Filter—to check hundreds of millions of leaked passwords in under 2 MB of RAM with constant O(k) lookup time.

The Problem: Why Hash Sets Don’t Scale in Memory

A standard Hash Set gives you O(1) lookups with zero error rate. However, memory usage grows linearly with the number of inserted items N:

• 800,000,000 raw hashes pprox 16 GB RAM (excluding object overhead).
• Adding metadata, pointers, and hash table buckets pushes actual memory consumption closer to 30+ GB.

For microservices, serverless functions, or API gateways, holding 30 GB of data in memory just for a password check is completely impractical.

The Algorithmic Fix: Bloom Filters

A Bloom Filter is a space-efficient probabilistic data structure. Instead of storing the actual keys, it uses a Bit Array of size m and k independent hash functions.

The Two Golden Rules of Bloom Filters

1. No False Negatives: If the filter returns false (“Not in Set”), the password is 100% guaranteed to be safe and uncompromised.
2. Controlled False Positives: If the filter returns true (“In Set”), the password is probably leaked. You can either reject it immediately or trigger a secondary check against a disk database.

Because we never store the actual string or hash—only single bit flips—we trade a tiny fraction of accuracy for orders-of-magnitude memory reduction.

The Math Behind Bloom Filters

The probability of a false positive p depends on three variables:

• n: Number of items inserted (e.g., 10,000,000 passwords)
• m: Size of the bit array (in bits)
• k: Number of hash functions

To achieve a false positive probability p, the optimal number of hash functions k is calculated as:

k=racmnln⁡(2) k = rac{m}{n} \ln(2)

And the required bit array size m for a desired false positive rate p is:

m=−racnln⁡(p)(ln⁡2)2 m = -rac{n \ln(p)}{(\ln 2)^2}

For 10 million passwords with a 1% false positive rate (p = 0.01), we only need roughly 95 million bits (~11.4 MB of memory).

Double Hashing: Efficient Hash Generation

Running k separate hash algorithms (like SHA256, MD5, FNV, etc.) per password would be CPU intensive. Instead, competitive programming and production systems use Kirsch-Mitzenmacher Double Hashing.

Using just two 32-bit hashes (h_1 and h_2), we can generate k distinct hash indices using the formula:

gi(x)=(h1(x)+i⋅h2(x))(modm) g_i(x) = (h_1(x) + i \cdot h_2(x)) \pmod m

Building a Password Guard in Node.js

Here is a complete Node.js implementation of a Bloom Filter using double hashing:

const crypto = require('crypto');

class PasswordBloomFilter {
  /**
   * @param {number} expectedItems (n) - Expected number of leaked passwords
   * @param {number} falsePositiveRate (p) - Desired error rate (e.g. 0.01 for 1%)
   */
  constructor(expectedItems = 10000000, falsePositiveRate = 0.01) {
    this.n = expectedItems;
    this.p = falsePositiveRate;

    // Calculate optimal m (bits) and optimal k (hashes)
    this.m = Math.ceil(-1 * (this.n * Math.log(this.p)) / (Math.log(2) ** 2));
    this.k = Math.round((this.m / this.n) * Math.log(2));

    // Allocate bit array (Buffer in Node.js)
    const byteSize = Math.ceil(this.m / 8);
    this.bitArray = Buffer.alloc(byteSize);
  }

  // Generate h1 and h2 using 64-bit split from SHA-256
  _getHashPair(item) {
    const hash = crypto.createHash('sha256').update(item).digest();
    const h1 = hash.readUInt32BE(0);
    const h2 = hash.readUInt32BE(4);
    return { h1, h2 };
  }

  // Set bit at index in buffer
  _setBit(index) {
    const byteIndex = Math.floor(index / 8);
    const bitOffset = index % 8;
    this.bitArray[byteIndex] |= (1 << bitOffset);
  }

  // Check bit at index in buffer
  _getBit(index) {
    const byteIndex = Math.floor(index / 8);
    const bitOffset = index % 8;
    return (this.bitArray[byteIndex] & (1 << bitOffset)) !== 0;
  }

  // Insert a known leaked password into the filter
  add(password) {
    const { h1, h2 } = this._getHashPair(password);
    for (let i = 0; i < this.k; i++) {
      const bitIndex = Math.abs((h1 + i * h2) % this.m);
      this._setBit(bitIndex);
    }
  }

  // Check if a user's chosen password might be leaked
  isLeaked(password) {
    const { h1, h2 } = this._getHashPair(password);
    for (let i = 0; i < this.k; i++) {
      const bitIndex = Math.abs((h1 + i * h2) % this.m);
      if (!this._getBit(bitIndex)) {
        return false; // Guaranteed NOT leaked!
      }
    }
    return true; // Probably leaked (triggers password change warning)
  }
}

// Example Express Middleware Usage
const filter = new PasswordBloomFilter(1000000, 0.01); // 1M passwords, 1% FP rate

// Pre-load breached hashes into memory on server startup
filter.add("Password123!");
filter.add("12345678");
filter.add("admin@2024");

function validatePasswordMiddleware(req, res, next) {
  const { password } = req.body;

  if (filter.isLeaked(password)) {
    return res.status(400).json({
      error: "Weak Password",
      message: "This password appears in known data breaches. Please choose a safer one."
    });
  }

  next();
}

Enter fullscreen mode Exit fullscreen mode

Key Engineering Takeaways

• Massive Memory Compression: Replaced tens of gigabytes of raw hash storage with a lightweight bit buffer.
• Instant O(k) Evaluation: Looking up a password requires computing k hash offsets in memory without hitches or network calls.
• Ideal First-Line Defense: Because there are zero false negatives, safe passwords bypass heavy database queries instantly.

Combining bitwise operations, probabilistic theory, and double hashing creates a high-performance guardrail for modern authentication systems.