Стандарт FIPS PUB 202 определяет Secure Hash Algorithm-3 (SHA-3) как семейство функций, оперирующих бинарными данными. Каждая из функций основана на кечак-алгоритме (KECCAK algorithm). Семейство включает четыре криптографические хэш-функции SHA3-224, SHA3-256, SHA3-384, SHA3-512 и две функции с расширенным выходом (extendable-output function, XOF) – SHAKE128 и SHAKE256.
В статье рассматриваются избранные места SHA-3 стандарта, относящиеся к анатомии кечак-функции (KECCAK) и, частично, к структуре губчатой функции (sponge function). Не затрагиваются многие другие части стандарта, в частности, описывающие функции с расширенным выходом SHAKE, RawSHAKE, рассуждения о криптостойкости алгоритмов и прочее.
Ниже показана схема губчатой структуры (sponge construction), использующей кечак-функцию, которая обрабатывает каждый битовый стейт B (связанный с конкретным инпут-блоком Ri) определенное количество раундов.
Некоторые битовые нотации и соглашения
Нотация 1n означает строку из n единичных битов. Аналогично, 0n означает строку из n нуль-битов. Например, 13021 = 111001. Нотация 130*1 означает, что слева идут 3 единицы, затем в битовой строке идут сплошные нули и в конце одна единица. Нотация 0* означает, что в строке одни нули, либо это может быть вообще пустая строка. То же самое можно сказать и про 1*. A||B обозначает конкатенацию битовых строк, например 101||001 = 101001. Усечение (обрезка хвоста) битовой строки M до ее первых k битов обозначают как Trunck[M]. Например, Trunc5[1100010]. = 11000.
В статье используются некоторые англицизмы, упрощающие изложение материала (и его восприятие) для русскоязычного читателя. Инпут - относящееся к входным данным (input). Ксоринг - операция исключающего ИЛИ (XOR) с двумя битовыми операндами. Мессидж - входящее битовое сообщение (input message). Падинг - добавление к битовой строке специальных битов (padding). Стейт - состояние битовой строки (state). Степ - любой из пяти алгоритмов (step mapping), выполняемых последовательно в раунде. В разделе "Трансформация стейта в раунде" будет добавлено еще несколько терминов.
Разбивка входящего сообщения M на блоки
Мессидж M (с добавленными к нему двумя битами 01) разбивается на блоки (data block) размером r (Rate, bit rate). Это будут инпут-блоки, подаваемые в кечак-функцию (Keccak) для абсорбции (absorbing phase). На основе очередного инпут-блока после его ксоринга с R-частью предыдущего стейта формируется текущий стейт B (=> r || c) из b бит подаваемый в кечак-функцию. Битовая строка стейта состоит из R-части (Rate, старшие биты в количестве r) и C-части (Capacity, младшие биты в количестве c). Кечак-функция работает с битовым стейтом B (b = r + c). В таблице ниже приведены четыре разновидности кечак хэш-функции SHA-3, которые берут на вход стейт из 1600 бит (b = 1600) и выдают хэш размером d.
Детали разбивки мессиджа M на блоки. В последнем блоке остаток мессиджа добивается падингом 10*1. Если для падинга в блоке остается 2 бита, то это будут две единицы. Если 1 бит, то блок добивается единицей и добавляется еще блок (последний) из нулей и в конце единица – 0*1. Если длина мессиджа кратна R, то все равно добавляется последний блок из нулей с двумя единицами (вначале и в конце) – 10*1.
Общие соображения
Стандарт SHA-3 допускает несколько конфигураций стейта с количеством бит 25×2^L, где степень двойки L может быть в диапазоне от 0 до 6. То есть в стейте может быть 25, 50, 100, 200, 400, 800, 1600 бит.
Стандарт допускает разное число раундов Nr у кечак-функции, выполняющей трансформацию стейта. Такая вариативность предложена в алгоритме 7 стандарта - KECCAK-p[b, Nr](S) . При этом индексация раундных итераций (Ir) должна определяться по правилу – от 12 + 2L - Nr до 12 + 2L - 1. Например, если выбран стейт из 800 бит (L = 5) и кечак-функция должна обрабатывать каждый инпут-блок-стейт 16 раундов, то индексация этих раундов должна быть – от 6 до 21 (12 + 2×5 - 16 = 6).
Наиболее используемая конфигурация стейта: 1600 бит (L = 6) длины, число раундов для обработки одного инпут-блока Nr = 24 (индексация раундов Ir = 0…23).
Каждый раунд, в свою очередь, состоит из 5 последовательно выполняемых алгоритмов. Итак, имеем мессидж с падингом, разбитый на инпут-блоки R. Для первой итерации формируется начальный стейт из 1600 нуль-битов, выполняется ксоринг r-части стейта с первым инпут-блоком R1 и результат подается на вход кечак-функции. Кечак-функция выполняет 24 раунда трансформации стейта (в каждом раунде по 5 степов) и на выходе мы получим 1600-битный стейт, который после ксоринга r-части этого стейта с инпут-блоком R2 подается снова на вход кечак-функции и та делает еще 24 раунда трансформации стейта. Так будет продолжаться, пока не закончатся все инпут-блоки. На этом фаза абсорбции (absorbing phase) мессиджа будет окончена.
После чего из r-битов стейта формируется хэш (hash, digest) для мессиджа M. Это называют фазой отжима (squeezing phase). Если нужен хэш большей длины, то стейт еще раз пропускается через кечак-функцию (уже без ксоринга с блочными битами, они закончились) и из r-битов трансформированного стейта делают добавку к хэшу путем конкатенации.
Стандарт SHA-3 идет дальше и вводит общее понятие губчатой функции sponge[f, pad, r](N, d). У нее есть три настроечных параметра – f (функция трансформации стейта фиксированной длины, в частности кечак-функция), pad (правило падинга последнего блока при разбивке входной битовой строки N на блоки), r (длина блока == длина r-части стейта == длина части, выжимаемой единожды из стейта, в частности длина хэша без расширения) и два входных параметра – N (битовая строка, подаваемая на вход губчатой функции, в частности – мессидж для вычисления хэша) и d (длина битовой строки Z на выходе из губчатой функции).
Таким образом губчатая функция sponge() принимает на вход произвольное количество бит N, «впитывает» их (как в губку) с помощью стейта и трансформирующей этот стейт f функции, а затем «выжимает» из стейта заданное параметром d количество бит на выходе.
Трансформация стейта в раунде
Разберем детально один раунд работы кечак-функции (трансформации стейта). Он состоит из пяти последовательных алгоритмов – степов (step mapping). Каждый степ (шаг) обозначен греческой буквой – тета (θ, Theta), ро (ρ, Rho), пи (π, Pi), чи (χ, Chi) и йота (ι, Iota). Но для начала необходимо выполнить конверсию стейта.
0. Конверсия стейт / трехмерная структура
Для более удобного описания трансформаций стейта в кечак-функции стейт (битовую строку) надо представить в виде объемной фигуры – прямоугольного параллелепипеда.
Строка S из b бит (битовая строка, стейт B) упаковывается в штабель – трехмерную структуру 5×5×w, где w – глубина штабеля, может принимать значения степеней L двойки (на рисунке каждый кубик – это бит).
Поперечные срезы 5×5 называются слайсы (Slice). Горизонтальные продольные срезы 5×w называются плоскости (Planes). Вертикальные продольные срезы 5×w называются листы (Sheets). Вертикальные 5-битные бруски – столбцы (Columns). Горизонтальные поперечные 5-битные бруски – ряды (Rows). Горизонтальные продольные w-битные бруски – дорожки (Lanes).
Штабель можно представить как битовый трехмерный массив A[x,y,z]. Важная особенность (x, y) индексов – они начинают отсчет из центра слайсов, а не с левого нижнего угла. Слайс однозначно определяется координатой (z). Плоскость однозначно определяется координатой (y). Лист однозначно определяется координатой (x). Столбец однозначно определяется координатами (x, z). Ряд однозначно определяется координатами (y, z). Дорожка однозначно определяется координатами (x, y).
Итак, имеем строку S[0…(b-1)] из b бит. Правила упаковки этих бит в штабель (массив A) следующие. Сначала битами S[0…(w-1)] заполняется дорожка (из w бит) штабеля в его центре, (x, y, z) = (0, 0, 0…(w-1)). Затем следующими w битами строки S – соседняя дорожка справа (1, 0). Затем дорожка еще правее (2, 0). Затем дорожка слева через одну (3, 0). Затем соседняя дорожка слева (4, 0). Таким образом будет заполнена битами строки плоскость в середине штабеля (y) = (0). Далее точно таким же образом заполняется битами строки соседняя плоскость над уже заполненной (y) = (1). Потом самая верхняя плоскость (y) = (2). Потом самая нижняя плоскость (y) = (3). И наконец – плоскость между самой нижней и срединной (y) = (4). И вот так мы заполнили битами строки весь штабель. Общая формула будет: A[x, y, z] = S[w (5 y + x) + z].
В конце всех трансформаций стейта (24 раунда, в каждом по 5 степов), относящегося к конкретному инпут-блоку, из штабеля извлекается b-битная итоговая строка S (стейт B) в таком же порядке, в каком штабель паковался (по той же формуле, но перевернутой, S = A). Сначала первые w бит центровой (0, 0) дорожки штабеля задают начало строки S[0…(w-1)]. Затем биты дорожки справа (1, 0) добавят к строке еще w бит. И так далее.
1. Тета-степ
Тета-степ состоит исключительно из ксоринга битов в столбцах штабеля. Сначала формируется временная плоскость C. Бит (x, z) этой плоскости являет собой результат ксоринга между собой 5 битов столбца (x, z) штабеля. Затем формируется вспомогательная плоскость D. Бит (x, z) этой плоскости являет собой результат ксоринга двух битов из плоскости C. Один – соседний слева от (x, z), второй – соседний с правого нижнего угла (если смотреть сверху). Если бит у левого края (x = 3), то «соседний слева» – это бит с противоположного края штабеля. То же правило верно и для оси z (так работает операция взятия по модулю). И, наконец, трансформация битов массива A выполняется столбец за столбцом в штабеле следующим образом – в столбце (x, z) штабеля каждый из 5 битов ксорится с битом (x, z) вспомогательной плоскости D.
2. Ро-степ
На входе в ро-степ имеем штабель, претерпевший изменения в процессе тета-степа. Трансформации циклического сдвига подвергаются биты в w-битных дорожках штабеля. Из трансформаций исключаем центровую (0, 0) дорожку штабеля, биты этой дорожки останутся неизменными. Поскольку должны быть трансформированы оставшиеся 24 дорожки, то делаем это в цикле со счетчиком t[0…23]. На первой итерации берем дорожку (1, 0) справа от центровой. Тело цикла таково:
Сначала (a) в соответствующей дорожке, производится циклический сдвиг ее битов «вдаль» (в сторону от наблюдателя) на величину (t + 1) (t + 2) / 2.
Затем (b) вычисляются координаты дорожки для следующей итерации на основе координат (x, y) текущей итерации. Для примера, первая итерация t = 0. Биты дорожки (1, 0) сдвигаются циклически на 1 позицию от нас. Затем вычисляются координаты дорожки (x, y) = (0, 2) для следующей итерации. Итерация t = 1. Биты дорожки (0, 2) сдвигаются циклически на 3 позиции от нас. И так далее.
3. Пи-степ
На входе в пи-степ имеем штабель, претерпевший изменения в процессе ро-степа. Алгоритм пи-степа работает так.
Бруски-дорожки переставляются в новые позиции в штабеле по следующему правилу: (x, y) = ((x + 3y) mod 5, x). Центровая дорожка (0, 0) остается на месте. В позицию (1, 0) переставляется дорожка, которая была в позиции (1, 1) [(1 + 3 × 0) mod 5, 1]. В позицию (2, 0) переставляется дорожка, которая была в позиции (2, 2) [(2 + 3 × 0) mod 5, 2]. В позицию (0, 2) переставляется дорожка, которая была в позиции (1, 0) [(0 + 3 × 2) mod 5, 0], поскольку 6 mod 5 = 1. И так далее.
4. Чи-степ
На входе в чи-степ имеем штабель, претерпевший изменения в процессе пи-степа.
Трансформации ксоринга и перемножения подвергаются биты в 5-битных рядах штабеля. Алгоритм чи-степа для бита (x) в ряду работает так. Сначала вычисляется битовое значение d – бит (x + 1) справа от (x) ксорится с единицей и затем результат ксоринга умножается (логическое AND) на следующий бит справа (x + 2). Взятие по модулю 5 позволяет разрешить затруднение для двух крайних справа битов в ряду (бит/биты для вычислений буду взяты с левого конца ряда).
Итоговое значение бита (x) будет результатом ксоринга бита (x) с битом d.
5. Йота-степ
На входе в йота-степ имеем штабель, претерпевший изменения в процессе чи-степа. Трансформации будет подвергнута только центровая (0, 0) дорожка штабеля. Все остальные биты штабеля останутся нетронутыми.
Алгоритм модифицирует центровую дорожку (0, 0) штабеля путем ее ксоринга с раундной константой RC (Round Constant).
Представим, что имеем конфигурацию с длиной дорожки 64 бита (степень двойки L = 6) и что кечак-функция делает 24 раунда (12 + 2L) трансформаций стейта. Допустим, в данный момент вычисления выполняются для 8-го раунда Ir = 8.
Сначала обнуляем RC (все 64 бита – нулевые). Затем в цикле от 0 до 6 вычисляем 7 битов для RC, которые встанут в RC на битовые позиции с индексами 0, 1, 3, 7, 15, 31, 63. Для этого на каждой из 7 итераций цикла вызываем функцию вычисления одного бита rc(t). Функция будет вызвана со следующими значениями (для Ir = 8) параметра t – 56, 57, 59, 63, 71, 87, 119.
После того, как вычислено и установлено 7 битов раундной константы RC, выполняется ксоринг этой константы с центровой дорожкой (0, 0) штабеля. На этом йота-степ для конкретного раунда Ir завершается.
Эти раундные константы, само собой, давно посчитаны и известны. Например, для конфигурации стейта 1600 бит (степень двойки L = 6, длина дорожки 64, число раундов 24) известны 24 константы: RC0 = 0x0000000000000001, RC1 = 0x0000000000008082, RC2 = 0x800000000000808a и так далее.
Для полноты картины можно разобрать алгоритм, по которому работает функция rc(t). Если t = 0 (или кратно 255), то функция сразу возвращает бит 1. При других значениях t функция запускает цикл из t итераций. Рассматриваемый алгоритм проще понять не в терминах сдвига битов в ячейках сдвигового регистра с линейной обратной связью (LFSR), а в терминах манипуляции битами на бесконечном ряду пустых ячеек.
Перед началом запуска цикла 8 пустых ячеек ряда инициализируются битами 10000000. Далее выполняется t итераций. В итерации сначала слева к 8 битам присоединяется бит 0. Получаем 9-битный регистр R, ячейки которого проиндексированы слева-направо от 0 до 8. Затем биты в ячейках 0, 4, 5, 6 изменяются в результате ксоринга их с битом из ячейки 8. Затем последний бит в ячейке 8 отбрасывается («откусывается») и остается 8-битный регистр R. На следующей итерации к 8 битам слева вновь присоединяется бит 0. Снова получаем 9-битный регистр R, выполняем ксоринг четырех битов регистра с последним битом в ряду и «откусываем» этот последний бит. И так далее. После завершения всех (t) итераций функция возвращает бит, находящийся в 0-ячейке (крайний левый).
Заключение
В статье была затронута часть стандарта SHA-3, касающаяся алгоритма KECCAK, детально рассмотрены битовые операции в одном раунде. Также кратко описана структура губчатой схемы (Sponge Construction).