Фильтр Блума для проверки паролей: 2 МБ вместо 30 ГБ

Зачем проверять пароли на утечки?

Когда пользователь регистрируется или меняет пароль, рекомендации по безопасности (например, NIST SP 800-63B) советуют сверять его с базой известных утечек. Такие сервисы, как HaveIBeenPwned, содержат более 800 миллионов хэшей паролей. Хранение 800 миллионов SHA-1 хэшей (по 20 байт каждый) в обычном хэш-множестве или Redis требует минимум 16 ГБ оперативной памяти, а с учётом накладных расходов — более 30 ГБ. Для микросервисов и serverless-функций это непозволительная роскошь. В этой статье мы разберём, как фильтр Блума позволяет проверять пароли по базе утечек, используя менее 2 МБ памяти и обеспечивая константное время проверки O(k).

Почему хэш-множества не масштабируются по памяти

Обычное хэш-множество даёт точные ответы и O(1) по времени, но память растёт линейно с числом элементов N. Для 800 миллионов хэшей потребуется минимум 16 ГБ (только сами хэши), а с учётом указателей и служебных структур — 30+ ГБ. Это неприемлемо для реальных систем. Решение — вероятностная структура данных: фильтр Блума.

Фильтр Блума: алгоритмическое решение

Фильтр Блума — это компактная вероятностная структура. Вместо хранения ключей он использует битовый массив размером m и k независимых хэш-функций. Его ключевые свойства:

• Нет ложных отрицаний: если фильтр говорит «пароль не в базе», это гарантированно так.
• Есть ложные срабатывания: если фильтр говорит «в базе», пароль может быть утёкшим. В этом случае можно запустить дополнительную проверку по диску или отклонить пароль.

Такой подход позволяет радикально сократить память, жертвуя небольшой точностью.

Математика фильтра Блума

Вероятность ложного срабатывания p зависит от трёх параметров: n (число элементов), m (размер битового массива) и k (число хэш-функций). Оптимальные значения вычисляются по формулам:

k = (m/n) * ln(2)

m = - (n * ln(p)) / (ln(2))^2

Например, для 10 миллионов паролей и вероятности ложного срабатывания 1% (p=0.01) потребуется примерно 95 миллионов бит, то есть около 11.4 МБ. Это в тысячи раз меньше исходных данных.

Двойное хэширование: эффективная генерация индексов

Вычислять k отдельных хэш-функций (SHA-256, MD5 и т.д.) для каждого пароля — дорого. Вместо этого используется двойное хэширование Кирша–Митценмахера: имея два 32-битных хэша h1 и h2, можно получить k индексов по формуле:

g_i(x) = (h1(x) + i * h2(x)) mod m

Это даёт хорошее распределение при минимальных вычислительных затратах.

Реализация фильтра Блума на Python

Ниже приведена полная реализация фильтра Блума на Python с двойным хэшированием. Мы используем встроенные модули hashlib и math.

import hashlib
import math
import os

class PasswordBloomFilter:
    """
    Фильтр Блума для проверки паролей на утечки.
    Параметры:
        expected_items (int): ожидаемое количество паролей в базе
        false_positive_rate (float): желаемая вероятность ложного срабатывания (например, 0.01)
    """
    def __init__(self, expected_items=10000000, false_positive_rate=0.01):
        self.n = expected_items
        self.p = false_positive_rate
        # Оптимальные размеры
        self.m = math.ceil(- (self.n * math.log(self.p)) / (math.log(2) ** 2))
        self.k = round((self.m / self.n) * math.log(2))
        # Битовая массив на основе bytearray
        self.bit_array = bytearray(math.ceil(self.m / 8))

    def _get_hash_pair(self, item):
        """Вычисляет h1 и h2 из SHA-256 (первые 8 байт)."""
        digest = hashlib.sha256(item.encode('utf-8')).digest()
        h1 = int.from_bytes(digest[:4], 'big')
        h2 = int.from_bytes(digest[4:8], 'big')
        return h1, h2

    def _set_bit(self, index):
        """Устанавливает бит в 1."""
        byte_index = index // 8
        bit_offset = index % 8
        self.bit_array[byte_index] |= (1 << bit_offset)

    def _get_bit(self, index):
        """Возвращает значение бита (0 или 1)."""
        byte_index = index // 8
        bit_offset = index % 8
        return (self.bit_array[byte_index] >> bit_offset) & 1

    def add(self, password):
        """Добавляет пароль в фильтр."""
        h1, h2 = self._get_hash_pair(password)
        for i in range(self.k):
            idx = (h1 + i * h2) % self.m
            self._set_bit(idx)

    def is_leaked(self, password):
        """Проверяет, возможно ли пароль был в утечках."""
        h1, h2 = self._get_hash_pair(password)
        for i in range(self.k):
            idx = (h1 + i * h2) % self.m
            if not self._get_bit(idx):
                return False  # Гарантированно не в базе
        return True  # Вероятно, в базе

# Пример использования:
filter = PasswordBloomFilter(expected_items=1000000, false_positive_rate=0.01)
# Загружаем известные утечки (здесь для демонстрации)
filter.add('Password123!')
filter.add('12345678')
filter.add('admin@2024')

# Проверка пароля пользователя
def validate_password(password):
    if filter.is_leaked(password):
        return 'Пароль найден в утечках, выберите другой.'
    else:
        return 'Пароль безопасен.'

print(validate_password('Password123!'))  # Вероятно, утёк
print(validate_password('mySecurePass!')) # Безопасен

Этот код можно легко интегрировать в любой веб-фреймворк, например, в FastAPI или Django. Для продакшена стоит загружать базу утечек в фильтр при старте приложения.

Практические выводы

Фильтр Блума — это мощный инструмент для систем аутентификации. Он позволяет:

• Сократить потребление памяти с десятков гигабайт до нескольких мегабайт.
• Выполнять проверку за O(k) — константное время, независимо от размера базы.
• Гарантировать отсутствие ложных отрицаний: безопасные пароли никогда не будут отклонены.

Что делать прямо сейчас: скопируйте код фильтра Блума, адаптируйте его под ваш стек (например, на Node.js или Go) и подключите к процессу регистрации. Начните с небольшой базы утечек (например, 10 тысяч паролей) и постепенно увеличивайте её. Это улучшит безопасность вашего сервиса без значительных затрат ресурсов.