Вопрос: Можно ли за пару минут «на коленке» создать свою криптографическую хеш-функцию? Чтобы в результате было не подобрать входную строку? Ответ: Можно!
Привет, Хабр! На связи Игорь Батулин — руководитель группы разработки виртуального хостинга в Рунити. Когда-то с удовольствием прочитав книгу «Грокаем алгоритмы» Адитья Бхаргавы, с удивлением обнаружил, что автор не привел пример криптографической хеш-функции. Но стиль подачи материала очень напомнил мне то, как я рассказывал об этом студентам-экономистам во времена преподавания в вузе — просто и наглядно. В этой статье поделюсь одной из моих алгоритмических практик, упражнениями-загадками и взломом коллизии.
Навигация по тексту:
Как работает самописный хеш
Порядок работы хеша довольно прост. Алгоритм = таблица + простые правила. Каждой букве сопоставлено число:
Вычисляем хеш так:
Берем входную строку и делим на буквы.
Для каждой буквы выписываем числа из таблицы.
Складываем.
Берем три последних цифры.
Например:
хеш( ПРИВЕТ ) = 987(П) + 873(Р) + 345(И) + 957(В) + 198(Е) + 768(Т) = 4128 ---> хеш 128
Еще варианты:
хеш( ДА ) = 423 + 179 = 602 ---> хеш 602
хеш( НЕТ ) = 927 + 198 + 768 = 1893 ---> хеш 893
хеш( ДЛИННАЯ ДЛИННАЯ ПРЕДЛИННАЯ ФРАЗА ) ---> хеш 329
Упражнение-загадка
Попробуйте подобрать исходную фразу для хешей 377, 777 или 333. Подсказка: можете использовать калькулятор! Если не хочется считать вручную, я создал страничку-калькулятор, которая сделает это за вас.
Почему наш крипто-хэш — почти как настоящий
У нашего хэша есть свои особенности, но он схож с настоящей функцией. Вот некоторые его характеристики:
подобрать исходное значение по хешу очень сложно;
быстро работает;
функция детерминирована — один и тот же результат, если одно и то же на входе;
присутствует лавинный эффект — небольшое изменение одного символа кардинально меняет результат.
Отмечу, что здесь не учитываются перестановки. Потому найти коллизию (одинаковый результат для разных значений) для уже известной фразы — элементарно. Нужно переставить буквы. Как это работает:
хеш( ПРИВЕТ ) = хеш ( ПРВТИЕ ) = хеш ( РИВЕТП ) = хеш ( ТЕВИРП )
Для понимания механизма криптографического хеширования этого достаточно, потому что найти любую подходящую фразу по значению хеша не так просто.
История упрощенного алгоритма-примера
Однажды, параллельно с основной работой, я преподавал в вузе несколько IT-дисциплин. Один из предметов был о защите информации. На парах я сделал уклон больше на технические концепты — шифры, хеши, ЭЦП (электронные цифровые подписи), фаерволы, вирусы-антивирусы и эксплойты.
На занятии о криптографических хешах мы рассматривали теорию, примеры, коллизии, алгоритмы типа MD5 и SHA и их применение. Чувствовалось, что студентам было сложно. Обычные хеши они поняли — на простом примере на основе контрольных сумм. А вот как обеспечивается защита от подбора в криптографических, было никак не понять. Даже вычисление остатка от деления и его вариативность студентам казалось магией.
Традиционный пример, который я обычно приводил — с хешированием книгой, как в произведении «Код да Винчи» Дэна Брауна. Это когда из номера страницы, номера абзаца и номера слова получают слово из книги. И так несколько раз, а потом преобразовать обратно. По набору слов получить численные значения тяжелее, если в руках только бумажная версия. Получалось уже лучше, но всё же было не так наглядно.
По опыту знаю, что подобный материал лучше усваивается на практике. Потому я поделил студентов на группы и предложил им придумать свой вариант или адаптировать чужой алгоритм крипто-хеша, чтобы он выглядел простым и считался без калькулятора. После этого необходимо было подготовить секретное сообщение, захешировать его и передать остальным группам для подбора коллизии.
У команд получилось реализовать свои алгоритмы. Они писали хитрые запутанные формулы, добавляли «соль», делали симметричное шифрование, включали элементы случайности (чего нельзя) — в общем перебирали все варианты. Настало время передать друг другу хеш от секретного пароля и сам алгоритм.
Бурные обсуждения и споры начались, когда ребята поняли, что должны передать другим командам весь алгоритм хеширования, а в идеале формулу в Excel для расчета хеша. Это нужно, чтобы другие группы могли легко проверять и подбирать свои варианты коллизий. Часто команды передавали алгоритм с дополнительным ключом, делиться которым не были готовы. Они хотели всеми путями оставить «секрет» при себе. Это старый подход security through obscurity, когда алгоритм засекречен. Современные алгоритмы — открытые, доступные всем, они проанализированы экспертами, протестированы и доказаны как стойкие.
По итогу, почти все команды на этом и «провалились». Зная алгоритм и видя реализацию, найти подходящую коллизию не составляло труда. Конечно, были возмущения: «Вы же не угадали исходный пароль!». Видимо, от тех, кто пропустил лекцию и не читал теорию :)
Однако были и интересные решения. Одна студентка придумала достаточно эффективный, простой и понятный алгоритм, практически полностью описанный в начале статьи. Его пришлось немного «отшлифовать», но идея была ее. На следующем занятии мы уделили алгоритму особое внимание и детально его разобрали: подбирали коллизии, искали бэкдоры, думали над повышением стойкости и надежности.
Пробуем взломать коллизию
Вернемся к нашему примеру из начала статьи. Взлом хеша был темой следующего практического задания со студентами. Вначале я подробно еще раз объяснил, как работает алгоритм, написал таблицу на доске и выдал вспомогательные материалы. Напомнил, что мы ищем не обязательно исходное значение, а любое подходящее.
Спустя 20 минут и с трудом студенты всё же подобрали коллизию для одного примера:
хеш( ЕХЩ ) = 198 (Е) + 123 (Х) + 456 (Щ) = 777
Было интересно узнать, как «системно» обеспечить такой подбор коллизий без полного перебора вариантов каждый раз? Ребята не были математиками и не нашли подходящий вариант.
Пришлось им подсказать: в математике есть понятие базис, базисный вектор, единичный вектор. Его можно применить и тут, если найти комбинацию, которая дает в сумме последние три цифры 001. Тогда любую коллизию (например, 333) можно подобрать просто повторив комбинацию нужное количество раз — в данном случае 333 раза. Вот такой подобранный вариант:
хеш( ГПФ ) = 821 (Г) + 987 (П) + 193 (Ф) = 2001 => 001
Теперь, если мы повторим 333 раза буквы ГПФ (т.е. будет строка «ГПФГПФГ...ФГПФ» из 999 букв), мы получим нужное нам 333. Конечно, это слишком длинно и не все системы такое поддерживают.
Но можно пойти дальше! Я не зря упомянул «базисный вектор». Если сделать три базисных «вектора», для 001, для 010 и для 100, то всё гораздо легче:
333 = 003 + 030 + 300 = 3 * 001 + 3 * 010 + 3 * 100
В этом случае для поиска решения надо будет всего 3 первых, 3 вторых и 3 третьих строки. Я предварительно нашел такие строки:
001 = хеш( ГПФ )
010 = хеш( БЛР )
100 = хеш( БММ )
Тогда исходную строку для хеша 333 можно составить так:
3 ГПФ + 3 БЛР + 3 БММ =
= ГПФГПФГПФ + БЛРБЛРБЛР + БММБММБММ =
= ГПФГПФГПФБЛРБЛРБЛРБММБММБММ
В таком виде выглядит вполне приемлемо по длине. Аналогичным образом можно посчитать и другие подобные значения, которые упростят подбор. Тут стоит упомянуть «радужные таблицы» — огромные базы данных с подобными, предварительно рассчитанными сведениями. Конечно, их устройство сложнее, но принцип схожий.
Повышаем надежность и стойкость алгоритма
Самый простой вариант для повышения надежности — в таблице для букв сделать не 3 цифры, а, например, 5. Тогда подбор значений значительно усложнится. Если 3 цифры еще как-то можно подобрать вручную, то 5 требуют полного перебора и применение компьютера.
Как защититься от перестановки? Можно домножать число для буквы на свой множитель, связанный с номером позиции буквы в строке. Вручную считать будет не совсем удобно, зато это защитит от перестановок.
Бэкдоры в криптоалгоритмах
Представим, что в нашем алгоритме усложнили таблицу таким образом, что подобрать некий «базисный вектор» стало невозможно, кроме как перебором всех вариантов. Для которого потребуется, например, ундециллион лет. Предположим, что найти подходящую строку для значения 001 практически невозможно.
Что тогда сделали бы, чтобы заложить бэкдор? Можно взять любую букву, например, «Я», и вместо «890» поставить в таблице другое значение, которое в сумме с другой буквой (например, «Ж», 368) дает нужный нам хеш 001. Тогда новое «Я» должно быть 633, так как:
хеш( ЯЖ )= 633 (Я) + 368 (Ж) = 1001 => 001
Для усложненного алгоритма перебором найти эту комбинацию практически невозможно. Получается этот «ЯЖ» — секретный бэкдор, заложенный в алгоритм, известный только ограниченному кругу лиц (например, разработчикам шифра), который при возможном взломе может использовать эту заранее заложенную уязвимость. И таких лазеек может быть множество. Например, на заре своего появления подозрения вызывал алгоритм шифрования AES. Если посмотреть на него, то в таблице перестановок блоков, типа S-Box (Substitution box), можно найти «хитрые» значения.
Это пример с симметричным шифром (это не хеш), но кейс наглядный. На самом деле в сообществе большинство считает, что в AES закладок нет.
Выводы
Конечно, хеширование гораздо сложнее. В нашем случае приведен максимально упрощенный концепт для понимания принципов его работы.
Если после этой статьи вы чуть лучше поняли, зачем нужны MD5, SHA-256, или почему «добавим-ка случайную цифру» не повышает безопасность, значит цель уже достигнута. Настоящая криптография — это не про тайны, а про публично доказанную надежность.