Хеш-функции можно считать основной рабочей силой современной криптографии. Изначально созданные для повышения эффективности цифровых подписей, сейчас они используются практически в любой части инфраструктуре, где хранят информацию и обмениваются ей. Их можно найти в криптографических протоколах, в процессе работы с ключами шифрования, защищенных веб-соединения и даже сканировании на вредоносное программное обеспечение. Без хеш-функций большая часть вещей вокруг нас просто не работала бы.
Самыми распространенными являются такие хеш-функции, как SHA-0, SHA-1 и SHA-2, включающая в себя SHA-256 и SHA-512. Но уже к концу первого десятилетия двадцать первого века для каждой из них были представлены методы конструирования коллизий, что показало наличие уязвимостей в алгоритмах и ставило под сомнение безопасность электронной цифровой подписи на основе данных хеш-функций. В связи с этим Национальный институт стандартов и технологий США (NIST) в 2007 году объявил конкурс на новый криптографический стандарт SHA-3.
Введение
Вооружившись списком требований, в ряду которых были устойчивость к известным атакам, минимизация используемой памяти и оптимизация под 64-разрядные процессоры, команда ученых под предводительством Брюса Шнайера, автором блочных шифров Twofish и Blowfish, в 2008 году представила на конкурс свое семейство хеш-функций переменной разрядности Skein, что дословно означает «моток пряжи». К сожалению авторов, в 2012 году алгоритм Skein уступил в финале SHA-3 более быстрому и менее уязвимому Keccak.
В Skein входят три составляющие:
конфигурируемый симметричный блочный шифр Threefish
уникальный блок итераций (UBI)
дополнительная система аргументов
Пойдем по порядку.
Threefish
Threefish — это конфигурируемый блочный алгоритм симметричного шифрования, разработанный Шнайером для использования в Skein. Первое, что сделал автор, это отказался от использования сети Фейстеля, с использованием которой были построены его прошлые шифры Blowfish и Twofish. В основе Threefish лежит подстановочно-перестановочная сеть (sp-сеть), а ее главная рабочая единица, нелинейная функция MIX, состоит из операций сложения, циклического сдвига и XOR и принимает на вход 2 слова размером по 64 бит каждое. После окончания раунда слова меняются местами, при этом через каждые 4 таких раунда используется раундовый ключ для нелинейности. За заявленную ранее возможность конфигурации алгоритма отвечает так называемое tweak-значение.
![](https://habrastorage.org/getpro/habr/upload_files/baf/6fa/823/baf6fa82335d9e04072931d5608b0393.png)
Сам же Threefish можно представить как функцию TF(K, T, P), где
K — ключ шифрования
T — tweak-значение
P - открытый текст
Теперь немного о цифрах. Threefish может работать с блоками данных размером 256, 512 и 1024 бита. Размер ключа выбирается такой же, как и размер блока. Количество раундов для алгоритма выбирается так: 72 и 80 раундов для 256/512-битных и 1024-битных блоков соответственно. Tweak-значение всегда 128 бит.
Функция MIX получает на вход пару значений (k1, k2) и возвращает также пару значений (g1, g2) , полученную по правилу:
g1 = (k1 + k2) mod 264
g2 = (k2 ≪ R) ⊕ g1 , R — константа, зависящая от размера ключа
![](https://habrastorage.org/getpro/habr/upload_files/66b/8f3/977/66b8f3977ab7f027718318713e37acf0.png)
UBI
В Skein Threefish работает в режиме Unique Block Iteration. UBI работает следующим образом. На вход каждого блока поступает выходное сообщение предыдущего блока и последовательность, длина которой произвольна, а в результате получается значение фиксированного размера. Каждый из этих блоков представляется в виде функции F(S, A, T):
S — начальное значение длиной Nb байт
A — сообщение
T — начальное значение твика
Сначала дополним сообщение A, как показано на схеме, и разобьем на n блоков по Nb байт
F(S, A, T)вычисляется так:
H0=S
Hi+1 = TF(Hi ; T + min(NA; (i+1) Nb) + ai 2126 + bi (B2119+ 2127) ; Ai)Ai
где a0=bk-1= 1, а остальные ai=bi=0, также при A кратном 8 B=0, иначе B=1
Дополнительная система аргументов
Теперь поговорим, как можно настроить работу алгоритма под разные ситуации. С этой целью в Skein добавлены дополнительные аргументы, добавляющие вариативности хеш-функции.
В этой системе есть два типа аргументов: постоянные, которые обязательны при любом режиме работы, и ситуативные, настраивающие алгоритм под разные задачи. К первым относятся:
Configuration — определяет размер значения на выходе и некоторые параметры для поддержки дерева хеширования
Output — определяет выходное преобразование
Необязательных же параметров намного больше:
Public Key - открытый ключ хешируется для подписи, это гарантирует, что при использовании разных открытых ключей для одного сообщения получаются различные хеши
Message - сообщение
Nonce - отвечает за работу в режиме потокового шифрования и случайного хеширования
Key - превращает Skein в MAC(message authentication code) или KDF(key derivation function)
Personalization - используется, если требуется создание различных функций для различных пользователей
Skein
Мы уже разобрали основные составляющие алгоритма, осталось только собрать его из известных деталей. Рассмотрим структуру Skein, как обычной хеш-функции, без модификаций и персонализации. Его работа построена на множественных вызовах UBI-блоков. В нашем случае их 3, по одному для каждого типа вызова UBI: конфигурационный блок, блок сообщения, блок выходного преобразования. Возьмем начальное значение S = 0. Алгоритм Skein представляет из себя следующую конструкцию.
![](https://habrastorage.org/getpro/habr/upload_files/567/cfa/1a9/567cfa1a9b61c5e6b6612c4d0529b751.png)
Если же 264 бита выходного сигнала не хватит, то можно параллельно последнему блоку запустить выходное преобразование нужное количество раз, как показано на рисунке.
![](https://habrastorage.org/getpro/habr/upload_files/b67/5c3/7a6/b675c37a6ecb2e8f22d814b6b4877a89.png)
Применение
В конце хотелось бы упомянуть области применения хеш-функции Skein. Используя систему дополнительных аргументов, есть возможность настроить алгоритм для вычисления кодов аутентификации сообщения MAC или HMAC (hash-based MAC). Также Skein может служить, как генератор случайных чисел или в качестве механизма вычисления электронно цифровой подписи.