12 декабря 2011

Обзор алгоритмов хэширования – финалистов конкурса SHA-3

Проект SHA-3 – это открытый конкурс по выбору нового стандарта хэширования США SHA-3, который проводится в настоящее время Институтом Стандартов и Технологий США (NIST – National Institute of Standards and Technologies). Аналогично проведенному ранее конкурсу по выбору стандарта симметричного шифрования AES, данный проект подразумевает выбор наилучшего по критериям криптостойкости и быстродействия (и не только) из присланных на конкурс алгоритмов хэширования.

Сергей Панасенко

Требования к участникам проекта были опубликованы в ноябре 2007 г. В течение последующего года на конкурс было прислано более 50 алгоритмов, разработанных известными криптологами из многих стран мира.

В 2009 г. из алгоритмов-участников конкурса было выбрано 14 алгоритмов, которые участвовали во втором этапе проекта SHA-3. Затем эксперты сузили количество кандидатов до пяти, которые стали финалистами конкурса SHA-3 и активно анализируются в настоящее время. Данная статья посвящена именно этим алгоритмам хэширования, один из которых должен стать новым стандартом хэширования США.

BLAKE

Авторы алгоритма BLAKE – Жан-Филипп Омассон (Jean-Philippe Aumasson), Лука Хензен (Luca Henzen), Уилли Мейер (Willi Meier) и Рафаэль Фан (Raphael Phan).

BLAKE построен по усиленной схеме Меркля-Дамгаарда (см. [1]). Его основой являются преобразования двух более ранних алгоритмов хэширования – LAKE и ChaCha.

Допустимые размеры выходных значений: 224, 256, 384 и 512 бит. Алгоритм разбивает данные на блоки по 512 бит (для 224- и 256-битных хэш-значений) или по 1024 бит (для 384- и 512-битных хэш-значений). Дополнение последнего блока хэшируемых данных производится следующим образом [2]:

добавляется единичный бит;
добавляется необходимое количество нулевых бит;
добавляется еще один единичный бит;
добавляется 64-битное значение, равное размеру исходного сообщения.

Помимо основных требований к алгоритму хэширования (включая криптостойкость и быстродействие), при разработке BLAKE авторы ставили целью обеспечить следующие свойства алгоритма:

прозрачное использование дополнительного параметра (salt) при необходимости;
возможность распараллеливания вычислений;
возможность различных оптимизаций при реализации алгоритма;
возможность реализации на платформах с минимальными ресурсами.

Функция сжатия алгоритма инициализируется выходным значением предыдущей функции сжатия (или вектором инициализации – Initialization Vector, IV) с участием дополнительного параметра (при его использовании) и количества уже обработанных бит сообщения (счетчик). Затем выполняется 10 или 14 раундов преобразований (в зависимости от размера выходного значения) с участием собственно блока хэшируемых данных. Внутреннее состояние функции сжатия является достаточно большим и представляет собой двумерный массив 4 X 4, каждая ячейка которого представляет собой слово данных – 32 или 64 бита в зависимости от размера выходного значения. Выходное значение функции сжатия формируется в рамках финализирующего преобразования функции сжатия, в котором также участвует salt и предыдущее выходное значение – для обеспечения прямой связи. Размер выходного значения – 8 слов.

Каждый раунд состоит из 8 вызовов функции G(), которая обрабатывает 4 из 16 слов состояния: сначала поочередно или параллельно обрабатываются столбцы массива состояния, затем – диагонали. Функция G() обрабатывает входные слова (обозначенные как a, b, c, d) следующим образом (см. рис. 1):

a = a + b + (m_x c_y);

d = (d a) >>> 16;

c = c + d;

b = (b c) >>> 12;

a = a + b + (m_y c_x);

d = (d a) >>> 8;

c = c + d;

b = (b c) >>> 7,

где:

m_i – используемое слово блока сообщения, i зависит от номера раунда и номера вызова функции G();

c_i – используемая константа.

Рис. 1 Основное преобразование алгоритма BLAKE

Операции сложения выполняются по модулю 2^w, где w – размер слова в битах.

Выше (и на рисунке) указаны преобразования функции G() для 224- или 256-битного выходного значения. Функция G(), используемая при вычислении хэш-значений остальных размеров, отличается лишь количеством бит, на которые выполняются операции вращения слов.

Как видно, алгоритм имеет четкую и ясную структуру и легко реализуем, как программно, так и аппаратно. Основное преобразование алгоритма – функция G() – унаследована в незначительно модифицированном виде от алгоритма ChaCha, анализ которого не выявил каких-либо проблем с криптостойкостью.

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

несколько атак на BLAKE с 2,5 раунда; пример атаки – нахождение прообраза для 512-битного хэш-значения с трудоемкостью 2⁴⁸¹ операций [3];
метод поиска near-коллизии для функции сжатия 256-битного варианта алгоритма с 4 раундами с трудоемкостью 2⁴² операций [4].

Таким образом, можно утверждать, что алгоритм BLAKE имеет весьма высокий запас криптостойкости.

Grostl

Алгоритм Grostl разработан большим коллективом специалистов из Технического университета Дании и Технологического университета г. Грац, Австрия.

При разработке данного алгоритма его авторы преследовали следующие цели [5]:

простота анализа алгоритма;
доказанная криптостойкость алгоритма;
хорошее быстродействие на различных платформах;
«встроенная» защита от атак, использующих утечки данных по побочным каналам;
возможность распараллеливания вычислений.

Алгоритм построен по схеме Меркля-Дамгаарда с финальным преобразованием. Возможные размеры хэш-значений – от 8 до 512 бит, кратные 8 битам. При размерах, меньших или равных 256, входные данные разбиваются на блоки по 512 бит, в остальных случаях – по 1024 бита. Размер внутреннего состояния алгоритма равен размеру блока хэшируемых данных.

Дополнение последнего блока выполняется следующим образом:

добавляется единичный бит;
добавляется необходимое количество нулевых бит (при необходимости);
добавляется 64-битное количество блоков входных данных после дополнения.

Функция сжатия является крайне простой (см. рис. 2). Она построена на двух преобразованиях – P() и Q(), которые определенным образом обрабатывают блок сообщения и внутреннее состояние (с предварительно наложенным на него операцией XOR блоком сообщения), после чего результаты работы данных функций объединяются операцией XOR. Такая структура обеспечивает быстрое и эффективное наложение блока сообщения на внутреннее состояние, а также связь вперед, усиливающую криптостойкость против некоторых видов атак.

Рис. 2 Функция сжатия алгоритма Grostl

Преобразования P() и Q() целиком основаны на незначительно модифицированных преобразованиях алгоритма шифрования AES, каждое из них выполняет несколько раундов (10 или 14 в зависимости от размера состояния) следующих операций над состоянием, которое представляется в виде двумерного байтового массива:

наложение раундовой константы (преобразования P() и Q() отличаются друг от друга только различными значениями раундовых констант);
байтовая замена (используется таблица замен алгоритма AES);
вращение строк массива;
умножение столбцов массива на матрицу.

Финальное преобразование выполняет обработку состояния (полученного после обработки последнего блока сообщения) функцией P(); результат данной обработки накладывается на состояние операцией XOR, после чего выполняется усечение состояния до требуемого размера хэш-значения.

Алгоритм производит впечатление весьма простого в реализации и обладает прозрачной и легкой для анализа структурой.

Известны несколько работ, посвященных криптоанализу алгоритма Grostl (например, [6-8]), однако, какие-либо уязвимости данного алгоритма в этих работах не обнаружены.

JH

Автор алгоритма JH – Хонгджун Ву (Hongjun Wu) из Института исследований в области телекоммуникаций, Сингапур.

Алгоритм построен по схеме Меркля-Дамгаарда. Входное сообщение разбивается на блоки по 512 бит. Возможные размеры хэш-значений – 224, 256, 384 и 512 бит. Независимо от размера выходного значения алгоритма в нем используется одна и та же функция сжатия, формирующая после обработки последнего блока сообщения 1024-битное значение, которое усекается до требуемого размера [9].

Функция сжатия в качестве входных параметров использует 512-битный блок сообщения и 1024-битное выходное значение функции сжатия после обработки предыдущего блока H_i-1 (или значение IV). Она выполняет следующие действия (см. рис. 3):

блок сообщения M_i накладывается на левую 512-битную половину значения H_i-1 операцией XOR;
результат предыдущей операции обрабатывается функцией E(), которая подробно описана далее;
M_i накладывается на правую половину 1024-битного выходного значения функции E() операцией XOR, в результате получается значение H_i.

Рис. 3 Функция сжатия алгоритма JH

1024-битное состояние представляется функцией сжатия в виде 8-мерного массива, каждое измерение которого содержит 2 слова по 4 бита. Данная функция представляет собой блочный шифр в виде подстановочно-перестановочной сети и выполняет 35 раундов преобразований (а также дополнительный уровень табличных замен после последнего раунда – см. далее), в каждом из которых производятся следующие действия:

уровень табличных замен – каждое слово состояния прогоняется через таблицу замен S₀ или S₁ в зависимости от значения определенного бита раундовой константы; используются таблицы замен известного алгоритма шифрования Lucifer (см., например, [10]);
линейное преобразование, поочередно обрабатывающее по два слова состояния с помощью операций XOR над определенными битами входных слов;
перестановка слов состояния по определенному закону.

Автор алгоритма JH привел также несколько его вариантов, отличающихся количеством измерений массива состояния, что позволяет (фактически, без изменения используемых в алгоритме преобразований) варьировать размером блока данных и состояния, что в итоге напрямую влияет на требования алгоритма к ресурсам при его реализации, а также на его быстродействие.

Флориан Мендель (Florian Mendel) и Сорен Томсен (Soren Thomsen) предложили сертификационную атаку на 512-битный вариант алгоритма JH, которой для успешного вычисления прообраза требуется 2^510,3 операций и столько же блоков памяти [11]. Однако, автор JH доказал в [12], что в работе Менделя и Томсена не учитываются операции сравнения и доступа к памяти, общее число которых составляет 2⁵²⁵, т. е. трудоемкость данной атаки превышает теоретическую – 2⁵¹² операций.

Keccak

Авторы алгоритма Keccak – Гвидо Бертони (Guido Bertoni), Джоан Деймен (Joan Daemen), Михаэль Петерс (Michael Peeters) и Жиль Ван Аске (Gilles Van Assche).

Алгоритм построен по принципу криптографической губки (данная структура криптографических алгоритмов была предложена авторами алгоритма Keccak ранее). Входное сообщение разбивается на блоки по 1024 бит [13].

Основой функции сжатия алгоритма является функция f(), выполняющая перемешивание внутреннего состояния алгоритма. Состояние (обозначим его A) представляется в виде двумерного массива 5 X 5, элементами которого являются 64-битные слова, инициализированные нулевыми битами (т. е. размер состояния составляет 1600 битов). Функция f() выполняет 18 раундов, в каждом из которых производятся следующие действия (см. рис. 4, номера на рисунке обозначают последовательность операций):

C[x] = A[x, 0] A[x, 1] A[x, 2] A[x, 3] A[x, 4], x = 0…4;

D[x] = C[x – 1] (С[x + 1] >>> 1), x = 0…4;

A[x, y] = A[x, y] D[x], x = 0…4, y = 0…4;

B[y, 2x + 3y] = A[x, y] >>> r[x, y], x = 0…4, y = 0…4;

A[x, y] = B[x, y] (~B[x + 1, y] & B[x + 2, y], x = 0…4, y = 0…4,

где:

B – временный массив, аналогичный по структуре массиву состояния;

C и D – временные массивы, содержащие по 5 64-битных слов;

r – массив, определяющий количество битов вращения для каждого слова состояния;

~x – побитовый комплемент к x;

операции с индексами массива выполняются по модулю 5.

Рис. 4 Раунд алгоритма Keccak

Кроме приведенных выше операций, в каждом раунде также выполняется наложение операцией XOR раундовой константы на слово A[0, 0].

Перед выполнением функции сжатия на часть состояния операцией XOR накладывается блок хэшируемых данных. Данное наложение в совокупности с функцией сжатия, выполняемые для каждого блока входных данных, представляют собой «впитывающую» (absorbing) фазу криптографической губки.

Стоит отметить, что функция f() использует только операции, стойкие к атакам, использующим утечки данных по побочным каналам.

Результирующее хэш-значение вычисляется в процессе выполнения «сжимающей» (squeezing) фазы криптографической губки, основу которой также составляет описанная выше функция f(). Возможные размеры хэш-значений – 224, 256, 384 и 512 бит.

Выше описан вариант алгоритма Keccak, представленный на конкурс SHA-3. Оригинальный алгоритм Keccak имеет множество настраиваемых параметров с целью обеспечения оптимального соотношения криптостойкости и быстродействия для определенного применения алгоритма на определенной платформе. Настраиваемыми величинами являются: размер блока данных, размер состояния алгоритма, количество раундов в функции f() и другие.

Авторы Keccak учредили ряд призов за достижения в криптоанализе данного алгоритма. В 2009 г. появилось несколько работ, посвященных криптоанализу алгоритма Keccak (например, [14-16]), однако, их авторы не обнаружили каких-либо уязвимостей в данном алгоритме.

Skein

Алгоритм Skein разработан командой всемирно известных специалистов-криптологов, представляющих известные университеты и корпорации (преимущественно из США).

Алгоритм предложен на конкурс SHA-3 в трех следующих вариантах [17]:

Skein-512 – основной вариант;
Skein-1024 – усиленный вариант;
Skein-256 – вариант для применений в условиях ограниченных ресурсов.

Число в названии варианта обозначает размер внутреннего состояния алгоритма в битах.

Рекомендуемые размеры выходного значения алгоритма: 128, 160, 224, 256, 384 и 512 битов, что соответствует размерам хэш-значений алгоритмов MD5 и SHA-1/SHA-2, на замену которых претендует алгоритм Skein.

Основой функции сжатия алгоритма Skein является блочный шифр Threefish, размеры блока которого соответствуют размерам состояния алгоритма Skein. Данный алгоритм шифрования представляет собой подстановочно-перестановочную сеть, основой которой является операция mix(), обрабатывающая два 64-битных слова x0 и x1 следующим образом (см. рис. 5):

y0 = x0 + x1 mod 2⁶⁴;

y1 = (x1 <<< R) y0,

где y0 и y1 – выходные значения операции, а R – одна из заданных таблицей констант вращения.

Рис. 5 Операция mix() алгоритма Threefish (Skein)

Раунд алгоритма представляет собой последовательность следующих операций:

параллельное применение операций mix() к каждым двум соседним словам состояния;
перестановка слов состояния.

Кроме того, перед первым раундом и после каждых четырех раундов выполняется наложение соответствующего фрагмента расширенного ключа шифрования операцией сложения по модулю 2ⁿ, где n – размер состояния в битах.

Threefish выполняет 72 раунда для 256- или 512-битного блока или 80 раундов для 1024-битного блока. Размер ключа шифрования алгоритма эквивалентен размеру блока шифруемых данных. Кроме того, в качестве дополнительного параметра алгоритма используется 128-битное модифицирующее значение (tweak), которое имеет определенную структуру.

На верхнем уровне алгоритм использует разработанную его авторами схему UBI (Unique Block Iteration – уникальная итерация блока).

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

Криптоанализ алгоритма проводился, в основном, в работе [18], авторы которой достигли, в частности, следующих результатов против Skein-512:

Объект атаки	Цель атаки	Количество раундов	Трудоемкость
Функция сжатия	Near-коллизия	17	224
Threefish	Ключ шифрования	34	2312

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

Заключение

Все алгоритмы-финалисты являются весьма быстродействующими и обладают большим запасом криптостойкости. Уже ясно, что новым стандартом хэширования США станет один из описанных выше алгоритмов. Ждем подведения итогов конкурса SHA-3.

Литература

Preneel B. Analysis and design of cryptographic hash functions. // http://homes.esat.kuleuven.be – February 2003.
Aumasson J.-P., Henzen L., Meier W., Phan R. C.-W. SHA-3 proposal BLAKE. // http://csrc.nist.gov – Version 1.2.
Li J., Xu L. Attacks on Round-Reduced BLAKE. // http://eprint.iacr.org – Sony China Research Laboratory.
Guo J., Matusiewicz K. Round-Reduced Near-Collisions of BLAKE-32. // http://gouglegroups.com.
Gauravaram P., Knudsen L. R., Matusiewicz K., Mendel F., Rechberger C., Schlaffer M., Thomsen S. S. Grostl – a SHA-3 candidate. // http://csrc.nist.gov – October 31, 2008.
Mendel F., Peyrin T., Rechberger C., Schlaffer M. Improved Cryptanalysis of the Reduced Grostl Compression Function, ECHO Permutation and AES Block Cipher. // http://online.tu-graz.ac.at.
Kelsey J. Some notes on Grostl. // http://ehash.iaik.tugraz.at – April 2009 – NIST.
Mendel F., Rechberger C., Schlaffer M., Thomsen S. S. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grostl. // http://online.tu-graz.ac.at – 2009.
Wu H. The Hash Function JH. // http://csrc.nist.gov – January 15, 2009 – Institute for Infocomm Research, Singapore.
Панасенко С. П. Алгоритмы шифрования. Специальный справочник. – СПб.: БХВ-Петрбург, 2009 – 576 с.
Mendel F., Thomsen S. S. An Observation on JH-512. // http://ehash.iaik.tugraz.at.
Wu H. The Complexity of Mendel and Thomsen’s Preimage Attack on JH-512. // http://csrc.nist.gov – Institute for Infocomm Research, Singapore.
Bertoni G., Daemen J., Peeters M., Van Assche G. Keccak sponge function family main document. // http://keccak.noekeon.org – Version 1.2 – April 23, 2009.
Aumasson J.-P., Khovratovich D. First Analysis of Keccak. // http://131002.net.
Lathrop J. Cube Attacks on Cryptographic Hash Functions. // http://www.cs.rit.edu – May 21, 2009 – Rochester Institute of Technology.
Aumasson J.-P., Meier W. Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. // http://131002.net – FHNW, Windisch, Switzerland.
Ferguson N., Lucks S., Schneier B., Whiting D., Bellare M., Kohno T., Callas J., Walker J. The Skein Hash Function Family. // http://csrc.nist.gov – Version 1.1 – 15 Nov 2008.
Aumasson J.-P., Calik C., Meier W., Ozen O., Phan R. C.-W., Varici K. Improved Cryptanalysis of Skein. // http://eprint.iacr.org.