Хэш-алгоритмы

    Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.

    О себе


    Студент кафедры информационной безопасности.

    О хэшировании


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

    Хэш-функцией называется всякая функция h:X -> Y, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свертка) имеет фиксированную битовую длину. X — множество всех сообщений, Y — множество двоичных векторов фиксированной длины.

    Как правило хэш-функции строят на основе так называемых одношаговых сжимающих функций y = f(x1, x2) двух переменных, где x1, x2 и y — двоичные векторы длины m, n и n соответственно, причем n — длина свертки, а m — длина блока сообщения.
    Для получения значения h(M) сообщение сначала разбивается на блоки длины m (при этом, если длина сообщения не кратна m то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам M1, M2,.., MN применяют следующую последовательную процедуру вычисления свертки:

    Ho = v,
    Hi = f(Mi,Hi-1), i = 1,.., N,
    h(M) = HN


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

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

    О статистических свойствах и требованиях



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

    К ключевым функциям хэширования предъявляются следующие требования:
    — невозможность фабрикации,
    — невозможность модификации.

    Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.

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

    Под однонаправленностью понимают высокую сложность нахождения сообщения по заданному значению свертки. Следует заметить что на данный момент нет используемых хэш-функций с доказанной однонаправленностью.
    Под устойчивостью к коллизиям понимают сложность нахождения пары сообщений с одинаковыми значениями свертки. Обычно именно нахождение способа построения коллизий криптоаналитиками служит первым сигналом устаревания алгоритма и необходимости его скорой замены.
    Под устойчивостью к нахождению второго прообраза понимают сложность нахождения второго сообщения с тем же значением свертки для заданного сообщения с известным значением свертки.

    Это была теоретическая часть, которая пригодится нам в дальнейшем…

    О популярных хэш-алгоритмах



    Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).

    Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
    Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
    Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.

    Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.

    Российский стандарт — ГОСТ 34.11-94.

    В следующей статье



    Обзор алгоритмов MD (MD4, MD5, MD6).

    Литература



    А. П. Алферов, Основы криптографии.

    Брюс Шнайер, Прикладная криптография.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 11

      0
      Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.

      мне кажется или это по сути одно и тоже? :)
        0
        Нет, вы не правы. По сути в первом требовании имеется в виду невозможность подобрать правильный хэш для произвольного сообщения (эта невозможность кроется в незнании значения ключа). Злоумышленник не может за счет этого написать свое сообщение и отправить — хэш будет неверный. А второе требование заключается в том, что злоумышленник не может перехватить сообщение, заменить его на свое и отправить. В этой ситуации для него важна возможность составить сообщение с тем же хэшем, что и у «легального» сообщения. Задачи разделяются в силу того, что зачастую они имеют разную вычислительную потребность и решаются разными алгоритмами. Вторую задачу решить, теоретически, проще.
          0
          так вы же в тексте нигде не сказали про «незнание хэша» для первого случая. Из того что я процетировал можно лишь сделать вывод об идентичности утверждений.

          Да и кстати если вводите понятия «ключевые» и «безключевые» тоже можно было бы описать что это такое, а то из статьи непонятно. Как будто просто слова вставили.
        +2
        Конец статьи какой-то неожиданный. Но было интересно.
          0
          Конец неожиданный по причине того, что статья с непривычки писалась долго… С работы просто выгоняют поздно вечером, вот и пришлось спешно закругляться)
          0
          Забыли (или отложили упоминание?) про алгоритм Whirpool.
          Было бы очень интересно почитать мнение человека, который занимается информационной безопастностью про данный алгоритм.
            +2
            С этим алгоритмом просто не приходилось сталкиваться часто… Но, так как есть заинтересованные лица, по наличии свободного времени разберусь и опишу результаты.
              0
              Буду рад прочесть.
            0
            Наконец-то я узнал, как так можно свернуть строку произвольной длины в хэш и нельзя развернуть обратно %)
              0
              «длина» пишется с одной Н
                0
                Знаю. Туплю. Вроде все поправил. Спасибо.

              Only users with full accounts can post comments. Log in, please.