Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Хеш-функции можно считать основной рабочей силой современной криптографии. Изначально созданные для повышения эффективности цифровых подписей, сейчас они используются практически в любой части инфраструктуре, где хранят информацию и обмениваются ей. Их можно найти в криптографических протоколах, в процессе работы с ключами шифрования, защищенных веб-соединения и даже сканировании на вредоносное программное обеспечение. Без хеш-функций большая часть вещей вокруг нас просто не работала бы.
Самыми распространенными являются такие хеш-функции, как 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-значение.
Сам же 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 — константа, зависящая от размера ключа
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 представляет из себя следующую конструкцию.
Если же 264 бита выходного сигнала не хватит, то можно параллельно последнему блоку запустить выходное преобразование нужное количество раз, как показано на рисунке.
Применение
В конце хотелось бы упомянуть области применения хеш-функции Skein. Используя систему дополнительных аргументов, есть возможность настроить алгоритм для вычисления кодов аутентификации сообщения MAC или HMAC (hash-based MAC). Также Skein может служить, как генератор случайных чисел или в качестве механизма вычисления электронно цифровой подписи.
