Курсовая работа по автоматизации на тему Анализ стойкости и уязвимостей алгоритмов хеширования (на примере MD5, SHA-1, SHA-256).

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

H:{0,1}∗→{0,1}nH:{0,1}∗→{0,1}n (1)

, где входное множество может быть любым битовым строкам произвольной длины, а выходом является битовая строка длины n.
Криптографическая хеш-функция должна удовлетворять следующим свойствам:
1. Детерминированность. Для одного и того же входного значения функция всегда возвращает одинаковый результат.
2. Быстрая вычислимость. Хеш-функция должна быстро преобразовывать входные данные в выходное значение независимо от размера входа.
3. Эффект лавины. Небольшое изменение входных данных (даже одного бита) должно привести к полностью отличному хеш-значению.
4. Однонаправленность (необратимость). Практически невозможно восстановить исходные данные по известному хеш-значению. Это свойство критично для защиты конфиденциальной информации, например паролей.
5. Устойчивость к коллизиям. Должно быть практически невозможно найти два различных входных значения, которые дают одинаковое хеш-значение.
6. Устойчивость к поиску прообраза. Для заданного хеш-значения h должно быть практически невозможно найти сообщение m такое, что H(m) = h.
7. Устойчивость ко второму прообразу. Для заданного сообщения m1 должно быть практически невозможно найти другое сообщение m2 ≠ m1, такое что H(m1) = H(m2).
История криптографического хеширования уходит корнями в середину XX века. В 1953 году Ганс Петер Луи из компании IBM первым предложил концепцию "хеш-кодирования". Однако до 1968 года эта идея оставалась неизвестной широкому научному сообществу.
Переломной точкой стала работа Роберта Морриса, опубликованная в журнале "Communications of the ACM" в 1968 году. Его обзор криптографического хеширования считается ключевой публикацией, закрепившей в научном обороте понятие "хеш".
В 1976 году Уитфилд Диффи и Мартин Хеллман впервые предложили использование хеш-функций в криптографических целях [7]. Впоследствии появились первые практические алгоритмы:
• MD1-MD4 (1990-1992) – алгоритмы, разработанные Роном Ривестом, которые стали основой для более поздних разработок.
• MD5 (1991) – широко распространённый алгоритм с 128-битным выходом.
• SHA-0 (1993) – первая версия стандарта, разработанная NSA совместно с NIST.
• SHA-1 (1995) – исправленная версия, которая заменила SHA-0.
• SHA-2 (2002) – семейство алгоритмов, включающее SHA-256, SHA-512 и другие [4].
• SHA-3 (2015) – новый стандарт, разработанный в результате международного конкурса.
Все известные атаки на криптографические хеш-функции можно классифицировать на несколько категорий:
1. Коллизионные атаки: направлены на поиск двух различных входных значений, дающих одинаковый хеш:
• Коллизионная атака "в лоб" – поиск двух произвольных сообщений с одинаковым хешем.
• Коллизионная атака с заданным префиксом – построение двух сообщений с заданными префиксами, дающих одинаковый хеш.
• Атака "дней рождения" - основана на парадоксе дней рождения; требует примерно 2^(n/2) операций для поиска коллизии в n-битной функции.
2. Атаки на поиск прообраза:
• Атака нахождения прообраза - по известному хешу найти сообщение, которое его генерирует.
• Атака нахождения второго прообраза - для известного сообщения найти другое с тем же хешем.
3. Дифференциальные атаки: анализ различий между входными и выходными данными для выявления закономерностей.
4. Атаки расширения длины: возможность использовать хеш известного сообщения для вычисления хеша расширенного сообщения без знания исходных данных.
5. Брутфорс-атаки: полный перебор всех возможных входных значений. В эпоху развития GPU-вычислений такие атаки становятся практически осуществимыми даже для достаточно больших размеров хешей.