Что такое хеш-коллизия?

Хеш-коллизия (Hash Collision)

Хеш-коллизия — это ситуация, когда две или более различные входные данные, обработанные хеш-функцией, дают одинаковый выход (хеш). Хотя идеальная хеш-функция должна давать уникальные хеши для разных входов, на практике коллизии неизбежны из-за принципа Дирихле: если входных данных больше, чем возможных выходов, коллизии гарантированы.

Принцип Дирихле и парадокс дней рождения

import random
from math import sqrt, factorial

def birthday_paradox():
    """
    Парадокс дней рождения: в группе из 23 человек вероятность того,
    что двое родились в один день, > 50%
    
    Для хеш-функции: вероятность коллизии увеличивается с квадратным корнем
    количества хешей, а не линейно.
    """
    
    # Для 256-битного хеша (2^256 возможных значений)
    hash_bits = 256
    possible_hashes = 2 ** hash_bits
    
    # Вероятность коллизии достигает 50% после примерно sqrt(N) попыток
    collision_point = int(sqrt(possible_hashes))
    
    print(f"Размер пространства хешей: 2^{hash_bits}")
    print(f"Вероятность коллизии 50% после: ~2^{hash_bits // 2} попыток")
    print(f"Это примерно: {collision_point:.2e} попыток")

birthday_paradox()

Типы коллизий

1. Слабая коллизия (Weak Collision)

Найти два разных входа с одинаковым хешем:

import hashlib
from typing import Optional, Tuple

class HashCollisionFinder:
    @staticmethod
    def find_weak_collision_bruteforce(
        prefix: str = "",
        target_hash: str = None,
        max_attempts: int = 1000000
    ) -> Optional[Tuple[str, str, str]]:
        """
        Ищет слабую коллизию перебором
        (только для демонстрации на простых функциях!)
        """
        hash_dict = {}
        
        for i in range(max_attempts):
            data = f"{prefix}{i}".encode()
            # Используем простую функцию для демонстрации
            hash_val = hashlib.md5(data).hexdigest()[:8]  # Укороченный хеш
            
            if hash_val in hash_dict:
                return (hash_dict[hash_val], f"{prefix}{i}", hash_val)
            
            hash_dict[hash_val] = f"{prefix}{i}"
        
        return None

# Демонстрация с укороченным хешем
result = HashCollisionFinder.find_weak_collision_bruteforce(max_attempts=100000)
if result:
    input1, input2, collision_hash = result
    print(f"Найдена коллизия!")
    print(f"Input 1: {input1}")
    print(f"Input 2: {input2}")
    print(f"Хеш: {collision_hash}")

2. Сильная коллизия (Strong Collision)

Найти два входа с одинаковым хешем, где один известен заранее:

class StrongCollisionAttack:
    """
    Атака на известное значение:
    Дан: H(message1) = X
    Найти: message2, такой что H(message2) = X
    
    Это намного сложнее, чем поиск двух неизвестных сообщений
    """
    
    @staticmethod
    def preimage_attack_complexity():
        """
        Сложность атак на хеш-функции:
        
        Для n-битного хеша:
        - Слабая коллизия (найти любые два разных входа): O(2^(n/2))
        - Сильная коллизия (find preimage): O(2^n)
        
        Для SHA-256 (256 бит):
        - Слабая: ~2^128 попыток (управляемо)
        - Сильная: ~2^256 попыток (невозможно на практике)
        """
        pass

Примеры известных коллизий

1. MD5 коллизии

import hashlib

class MD5CollisionExample:
    """
    MD5 был взломан в 2004 году.
    Существуют известные пары, дающие одинаковый MD5 хеш.
    """
    
    @staticmethod
    def demonstrate_md5_collision():
        # Известная пара с коллизией MD5
        data1 = bytes([0xd1, 0x31, 0xdd, 0x02, 0xc5, 0xe6, 0xee, 0xc4])
        data2 = bytes([0xd1, 0x31, 0xdd, 0x02, 0xc5, 0xe6, 0xee, 0xcb])
        
        # (В реальности, коллизии MD5 намного сложнее)
        # Но они существуют и были найдены в 2004 году
        
        print("MD5 больше не считается криптографически стойким")
        print("Использование MD5 для безопасности запрещено")

MD5CollisionExample.demonstrate_md5_collision()

2. SHA-1 коллизия (2017 год)

class SHA1CollisionExample:
    """
    В 2017 году были найдены два PDF файла с одинаковым SHA-1 хешем.
    Это требовало огромных вычислительных ресурсов.
    """
    
    @staticmethod
    def demonstrate_sha1_weakness():
        print("SHA-1 коллизия была найдена в 2017 году")
        print("Требовалось: 110 лет машинного времени (parallelized)")
        print("SHA-1 больше не рекомендуется для новых приложений")

SHA1CollisionExample.demonstrate_sha1_weakness()

Обработка коллизий в хеш-таблицах

1. Цепочки (Chaining)

class HashTableWithChaining:
    def __init__(self, size: int = 100):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key: str) -> int:
        return sum(ord(c) for c in key) % self.size
    
    def insert(self, key: str, value):
        """Вставляет при коллизии в цепочку"""
        index = self._hash(key)
        
        # Проверяем, есть ли уже такой ключ
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        
        # Добавляем в цепочку
        self.table[index].append([key, value])
    
    def get(self, key: str):
        index = self._hash(key)
        
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        
        return None
    
    def get_collision_stats(self) -> dict:
        """Статистика коллизий"""
        collisions = sum(1 for bucket in self.table if len(bucket) > 1)
        avg_chain_length = sum(len(bucket) for bucket in self.table) / self.size
        max_chain_length = max(len(bucket) for bucket in self.table)
        
        return {
            "collisions": collisions,
            "avg_chain_length": avg_chain_length,
            "max_chain_length": max_chain_length
        }

# Демонстрация
ht = HashTableWithChaining(size=10)
ht.insert("apple", 1)
ht.insert("banana", 2)
ht.insert("cherry", 3)
ht.insert("date", 4)

stats = ht.get_collision_stats()
print(f"Коллизий: {stats['collisions']}")
print(f"Средняя длина цепочки: {stats['avg_chain_length']:.2f}")
print(f"Максимальная длина цепочки: {stats['max_chain_length']}")

2. Открытая адресация (Open Addressing)

class HashTableWithOpenAddressing:
    def __init__(self, size: int = 100):
        self.size = size
        self.table = [None] * size
        self.keys = [None] * size
    
    def _hash(self, key: str) -> int:
        return sum(ord(c) for c in key) % self.size
    
    def _probe(self, key: str, attempt: int) -> int:
        """Линейное зондирование"""
        index = self._hash(key)
        return (index + attempt) % self.size
    
    def insert(self, key: str, value):
        attempt = 0
        
        while attempt < self.size:
            index = self._probe(key, attempt)
            
            if self.table[index] is None:
                # Найдена свободная ячейка
                self.table[index] = value
                self.keys[index] = key
                return
            
            if self.keys[index] == key:
                # Обновляем существующий ключ
                self.table[index] = value
                return
            
            attempt += 1
        
        raise Exception("Хеш-таблица переполнена")
    
    def get(self, key: str):
        attempt = 0
        
        while attempt < self.size:
            index = self._probe(key, attempt)
            
            if self.keys[index] == key:
                return self.table[index]
            
            if self.table[index] is None:
                return None
            
            attempt += 1
        
        return None

# Демонстрация
ht = HashTableWithOpenAddressing(size=20)
ht.insert("apple", 1)
ht.insert("banana", 2)
print(ht.get("apple"))   # 1
print(ht.get("banana"))  # 2

Смягчение коллизий

1. Увеличение размера хеша

class HashCollisionMitigation:
    @staticmethod
    def compare_hash_sizes():
        """
        Вероятность коллизии зависит от размера хеша:
        
        8-битный хеш: коллизия после ~2^4 = 16 попыток
        16-битный хеш: коллизия после ~2^8 = 256 попыток
        32-битный хеш: коллизия после ~2^16 ≈ 65K попыток
        64-битный хеш: коллизия после ~2^32 ≈ 4 млрд попыток
        128-битный хеш: коллизия после ~2^64 попыток
        256-битный хеш: коллизия после ~2^128 попыток
        
        SHA-256 (256 бит) достаточен для практически всех целей
        """
        pass

2. Использование криптографически стойких функций

import hashlib

class SecureHashing:
    @staticmethod
    def use_sha256():
        """SHA-256 устойчив к коллизиям"""
        data = b"Important data"
        secure_hash = hashlib.sha256(data).hexdigest()
        return secure_hash
    
    @staticmethod
    def use_sha3():
        """SHA-3 даже более стоек (новый стандарт)"""
        data = b"Important data"
        secure_hash = hashlib.sha3_256(data).hexdigest()
        return secure_hash
    
    @staticmethod
    def never_use_md5():
        """MD5 НЕЛЬЗЯ использовать для безопасности"""
        # ПЛОХО: MD5 небезопасен
        # unsafe_hash = hashlib.md5(data).hexdigest()
        pass

Лучшие практики

1. Для криптографии: используйте SHA-256, SHA-3 или Blake2
2. Для паролей: используйте bcrypt, scrypt, Argon2 (они имеют встроенную защиту)
3. Для хеш-таблиц: убедитесь, что хеш-функция хорошо распределяет данные
4. Избегайте: MD5, SHA-1 для новых приложений
5. Мониторьте: размер коллизий в вашей хеш-таблице, используйте rehashing при необходимости

# Плохо
insecure = hashlib.md5(password.encode()).hexdigest()

# Хорошо
secure = hashlib.sha256(password.encode()).hexdigest()

# Отлично (для паролей)
hashed = bcrypt.hashpw(password.encode(), bcrypt.gensalt())

Хеш-коллизия — неизбежное явление, но правильный выбор хеш-функции и размера хеша минимизирует их влияние на производительность и безопасность системы.