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) состоит из двух этапов:

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[] представляет собой предопределенный набор значений, в котором указывается на сколько необходимо сдвигать байты на каждом раунде:

SHA-3 алгоритм

Массив RC это набор констант, которые тоже являются предопределенными:

Keccak майнинг

См. также на BitcoinWiki

Источники