Вопрос: Можно ли за пару минут «на коленке» создать свою криптографическую хеш-функцию? Чтобы в результате было не подобрать входную строку? Ответ: Можно!

Привет, Хабр! На связи Игорь Батулин — руководитель группы разработки виртуального хостинга в Рунити. Когда-то с удовольствием прочитав книгу «Грокаем алгоритмы» Адитья Бхаргавы, с удивлением обнаружил, что автор не привел пример криптографической хеш-функции. Но стиль подачи материала очень напомнил мне то, как я рассказывал об этом студентам-экономистам во времена преподавания в вузе — просто и наглядно. В этой статье поделюсь одной из моих алгоритмических практик, упражнениями-загадками и взломом коллизии.

Навигация по тексту:

Как работает самописный хеш

Порядок работы хеша довольно прост. Алгоритм = таблица + простые правила. Каждой букве сопоставлено число:

Таблица соответствия букв сообщения и значений для хеша
Таблица соответствия букв сообщения и значений для хеша

Вычисляем хеш так:

  1. Берем входную строку и делим на буквы.

  2. Для каждой буквы выписываем числа из таблицы.

  3. Складываем.

  4. Берем три последних цифры.

Например:

хеш( ПРИВЕТ ) = 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 S-box
AES S-box

Это пример с симметричным шифром (это не хеш), но кейс наглядный. На самом деле в сообществе большинство считает, что в AES закладок нет. 

Выводы

Конечно, хеширование гораздо сложнее. В нашем случае приведен максимально упрощенный концепт для понимания принципов его работы.

Если после этой статьи вы чуть лучше поняли, зачем нужны MD5, SHA-256, или  почему «добавим-ка случайную цифру» не повышает безопасность, значит цель уже достигнута. Настоящая криптография — это не про тайны, а про публично доказанную надежность.

Комментарии (8)


  1. vilgeforce
    05.06.2025 10:33

    "Почему наш крипто-хэш — почти как настоящий" - нипочему. Он не имеет отношения к криптографии, скорее что-то типа CRC и он не имеет отношения к хэшам


    1. binom248 Автор
      05.06.2025 10:33

      Так попробуйте подобрать "на бумажке" решение (фразу) для 333.
      А если серьезно - то понятно что тут примитивнейший алгоритм, но который использует серьезные криптографические примитивы, в данном случае, задачу "рюкзака". Пусть и сильно упрощенно для понимания.


  1. vened
    05.06.2025 10:33

    Попробуйте подобрать исходную фразу для хешей 377, 777 или 333.

    Для 333. Можно в уме.

    Нам нужно 333 (mod 1000). Будем целить в 1333 - выглядит так, что можно столько набрать на трёх слагаемых. Запись искомого числа оканчивается на 3, значит оно равно 3 (mod 10). 3 (mod 10) можно получить несколькими способами. Действуя наобум и немного прикинув частотность имеющихся чисел, выбираем 8 + 8 + 7 == 23 == 3 (mod 10). То есть, нам подходят только числа, оканчивающиеся на 8 и 7, но их тут, похоже, достаточно. Выписываем такие числа: 927, 567, 797, 957, 987, 287, 198, 758, 678, 368. Вспоминаем, что нам нужно 8 + 8 + 7, но при этом должно быть 33 (mod 100). Это означает, что достаточно рассмотреть по две последних цифры записи. И у нас уже есть повторы. Удобно, что почти все двузначные числа, соответствующие выбранным, достаточно большие, то есть, при десятках - пять и более единиц. Поэтому 133 выглядит слишком малым целевым числом (уже 3 * 44 == 32), его недостаточно, чтобы обеспечить вариативность по трём слагаемым. Прицеливаемся на 233. Смотрим примерные числа и проверяем (должна быть сигнатура 8, 8, 7): 78 + 68 + 87 == 233. Сразу подходит, угадали. Проверяем результат для трёх цифр: 678 + 368 + 287 == 1333 == 333 (mod 1000). Готово. Нашли один из ответов: ЭЖУ.

    (Подсказка: можно ещё проще.)


    1. binom248 Автор
      05.06.2025 10:33

      Отличное решение! Спасибо) Вообще, я старался придумать пример, чтобы выглядел очень простым, но в тоже время чтобы вот так, "в уме" было очень сложно подобрать коллизию. Но вы опровергли мою гипотезу) Значит надо выбрать число сложнее, например, 827. Или ещё лучше - усложнить алгоритм, сопоставив каждой букве число из 4-х цифр (а не из 3-х).


      1. xi-tauw
        05.06.2025 10:33

        Вы опасно некомпетентны в криптографии. Берем расширенный алгоритм Евклида и считаем его для 1000 и буквы А (179)

        Получаем: 1000*(-75) + 179 * 419 = 1

        Тащим 1000 к 1 и домножаем все на 827.

        827*1000*75 + 827 = 827*179*419

        То есть, строка из 346513 букв А даст нужный "хэш". И я надеюсь, что вам очевидно, что дальше за О(1) я выберу для любого вашего "хэша" прообраз.


        1. binom248 Автор
          05.06.2025 10:33

          Так про это же есть в статье. Только там используется хеш( ГПФ ) = 001, а так та же самая логика, что вы озвучили.

          Но если ограничить наш условный "пароль" допустим, 32 символами - то подобрать коллизию будет уже не так просто! Ну и самое главное - это же просто максимально упрощенный пример, подготовленный для понимания принципа. Понятно, что он обладает множеством недостатков.


          1. xi-tauw
            05.06.2025 10:33

            Ну да. Куда уж универсальному алгоритму, который показывает нахождение прообразов для любой конфигурации вашего "хеша" до примера из статьи. Я уж молчу про нахождение парного прообраза.


            1. binom248 Автор
              05.06.2025 10:33

              Что касается расширенного алгоритма Евклида - вы абсолютно правы, что это эффективный системный метод поиска прообраза для подобных случаев. И прошу прощения за терминологию - мы проверяли стойкость к коллизиям первого рода. А лучший способ обучения - не рассказывать уже готовое решение, а дать его выработать самостоятельно.