SHA-3
SHA-3 (Keccak) – алгоритм хеширования переменной разрядности, разработанный группой во главе с Йоаном Дайменом в 2012 году. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Алгоритм SHA-3 построен по принципу криптографической губки.
Содержание
История
В 2004-2005 годах несколько алгоритмов хеширования были атакованы, в том числе были опубликованы серьезные атаки против алгоритма SHA-1, утвержденного Национальным институтом стандартов и технологий (NIST).
В ответ NIST провел открытые семинары и 2 ноября 2007 года анонсировал конкурс на разработку нового алгоритма хеширования.
2 октября 2012 года победителем конкурса стал алгоритм Keccak и был стандартизован как новый алгоритм SHA-3.
5 августа 2015 года алгоритм утвержден и опубликован в качестве стандарта FIPS 202.
Алгоритм был разработан Гвидо Бертони, Йоаном Дайменом, Жилем Ван Аше из STMicroelectronics и Микаэлем Питерсом из NXP.
Алгоритм основан на более ранних хеш-функциях Panama и RadioGatún. Panama был разработан Дайменом и Крейгом Клэппом в 1998 году, RadioGatún был реализован на основе Panama Дайменом, Питерсом и Ван Аше в 2006 году.
В ходе конкурса конкурсантам разрешалось вносить изменения в свой алгоритм для исправления обнаруживающихся проблем. Изменения, внесенные в алгоритм Keccak:
- Количество раундов было увеличено с 12 + l до 12 + 2l;
- Padding был изменён со сложной формы на более простую, описанную ниже;
- Скорость (rate) r была увеличена до предела безопасности (ранее округлялась вниз до ближайшей степени 2).
Описание Алгоритма
Keccak основан на конструкции Sponge. Это означает, что для получения хеша нужно проделать следующие незамысловатые действия: Взять исходное сообщение M и дополнить его до длины кратной r. В виде формулы их можно изобразить следующим образом: M=M||0x01||0x00||..||0x00||0x80. То есть к сообщению дописывается единичный байт, необходимое количество нулей и завершается байт со значением 0x80.
UPD: Все вышесказанное справедливо только для случаев, когда добавляется более одного байта.
Однако в случае, если необходимо дополнить всего один байт, то достаточно добавить лишь 0x81.
Затем для каждого блока Mi длиной r бит выполняем:
- Сложение по модулю 2 с первыми r-битами набора начальных состояний S. Перед началом работы функции все элементы S будут равны нулю.
- N раз применяем к полученным в результате данным функцию f. Набором начальных состояний S для блока Mi+1 будет результат последнего раунда блока Mi.
- После того как все блоки Mi закончатся взять итоговый результат и вернуть его в качестве хеш-значения.
Параметры r и c
Хеш-функция Keccak реализована таким образом, что функцию перестановки f, применяемую для каждого блока Mi, пользователь может выбирать самостоятельно из набора предопределенных функции b={f-25, f-50, f-100, f-200, f-400, f-800, f-1600}.
Для использования функции f-800, необходимо выбрать такие r и c, чтобы выполнялось равенство r+c=800.
Кроме того, изменяя значения r и c, вы тем самым изменяете количество раундов вашей хеш-функции.
Т.к. количество оных вычисляется по формуле n=12+2l, где 2l=(b/25). Так для b=1600, Количество раундов равно 24.
Однако хотя пользователь в праве выбирать для своей реализации любую из предложенных авторами функций, следует отметить что в качестве стандарта SHA-3 принята только функция Keccak-1600 и авторы всячески рекомендуют пользоваться только ею. Так в качестве основных значений для хешей разной длины авторы выбрали следующие параметры:
- SHA-224: r=1156, c=448 (вернуть первые 28 байт результат)
- SHA-256: r=1088, c=512 (вернуть первые 32 байт результат)
- SHA-384: r=832, c=768 (вернуть первые 48 байт результат)
- SHA-512: r=576, c=1024 (вернуть первые 64 байт результат)
Схема работы
Схема SHA-3 (Keccak) состоит из двух этапов:
- Absorbing (впитывание). Исходное сообщение M подвергается многораундовым перестановкам f.
- Squeezing (отжатие). Вывод получившегося в результате перестановок значения Z.
Функция Keccak представляет из себя следующее:
Keccak[r,c](M) { Initialization and padding for(int x=0; x<5; x++) for(int y=0; y<5; y++) S[x,y] = 0; P = M || 0x01 || 0x00 || … || 0x00; P = P xor (0x00 || … || 0x00 || 0x80); //Absorbing phase forall block Pi in P for(int x=0; x<5; x++) for(int y=0; y<5; y++) S[x,y] = S[x,y] xor Pi[x+5*y]; S = Keccak-f[r+c](S); //Squeezing phase Z = empty string; do { for(int x=0; x<5; x++) for(int y=0; y<5; y++) if((x+5y)<r/w) Z = Z || S[x,y]; S = Keccak-f[r+c](S) } while output is requested return Z; } - На этапе Absorbig производится вычисление хеш значения.
- А на этапе Squeezing вывод результатов до тех пор пока не будет достигнута требуемая длина хеша.
Этап absorbing
Этап absorbing можно представить в виде следующей функции:
Keccak-f[b](A) { forall i in 0…nr-1 A = Round[b](A, RC[i]) return A } - Здесь b это значение выбранной функции(по умолчанию 1600).
- А функция Round()-псевдослучайная перестановка, применяемая на каждом раунде. Количество раундов nr вычисляется из значений r и c.
Операции выполняемые на каждом раунде представляют из себя следующую функцию:
Round[b](A,RC) { θ step for(int x=0; x<5; x++) C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4]; for(int x=0; x<5; x++) D[x] = C[x-1] xor rot(C[x+1],1); for(int x=0; x<5; x++) A[x,y] = A[x,y] xor D[x]; ρ and π steps for(int x=0; x<5; x++) for(int y=0; y<5; y++) B[y,2*x+3*y] = rot(A[x,y], r[x,y]); χ step for(int x=0; x<5; x++) for(int y=0; y<5; y++) A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]); ι step A[0,0] = A[0,0] xor RC return A } Тут 4 шага на каждом из которых над входящими данными производится ряд логических действий.
Здесь функция rot(X,n) обозначает циклический сдвиг элемента X на n позиций.
Массив r[] представляет собой предопределенный набор значений, в котором указывается на сколько необходимо сдвигать байты на каждом раунде:
Массив RC это набор констант, которые тоже являются предопределенными:
