Алгоритмы / Как устроен Whirlpool Опции

[Decker]

Whirlpool хеш больше похож на алгоритм шифрования AES чем на хеши MD5 и SHA1. Он весьма запутан и реализовать его сложнее чем AES, да и работает он не очень быстро, зато для него пока не нашли коллизий. Здесь я собираюсь рассказать как по простому, без хитрых оптимизаций, написать этот алгоритм.








Конечные поля




Также как AES, Whirlpool производит все вычисления в конечных полях. Под «конечным полем» здесь подразумеваются всего лишь операции • (умножить) и + (сложить) определённые хитрым образом над парами целых чисел. Здесь используют следующую идею. Будем считать, что число 0x17=1'0111 это компактная запись многочлена у которого 1'0111 — коэффициенты: x⁴+x²+x+1.



Для сложения двух чисел их записывают в виде многочленов и складывают коэффициенты при соответсвующих степенях, при этом считая, что коэффициенты это биты с двумя значениями и правилами сложения 1+0=1, 1+1=0 и т.д. Вообщем получается, что сложение двух чисел это xor.



Умножение двух чисел берётся по модулю некоторого специально выбранного многочлена, вид которого зависит от разрядности чисел. Whirlpool оперирует полями GF(2⁴) (4-битные числа) и GF(2⁸) (8-битные числа). Для GF(2⁴) авторами Whirlpool было выбрано число 0x13=1'0011=x⁴+x+1. Найдём например произведение 0xb•0xb=1011•1011:



1011•1011 = (x³+x+1)(x³+x+1) mod(x⁴+x+1)



Вычислять это напрямую долго, однако видно, что это умножение сводится к умножению на простой многочлен x:



1011•1011 = 1011•x³+1011•x+1011 = 1011•10•10•10+1011•10+1011



Найдём правило умножения p•x. Если p•x не помещается в 4 бита, надо отнять от p•x многочлен 0x13, иначе оставить p•x без изменений.



1011•10 = 1'0110 - 1'0011 = 1'0110 ^ 1'0011 = 101
1011•10•10 = 101•10 = 1010
1011•10•10•10 = 1010•10 = 1'0100 - 1'0011 = 110




Теперь складываем три слагаемых:



1011•10•10•10+1011•10+1011 = 110+101+1011 = 10+1011 = 1001 = 0x9



Получилось, что 0xb•0xb=0x9. Правила умножения в GF(2⁸) такие же, только многочлен другой: 0x11d (в AES используется 0x11b).



whirlpool.gf4mul = function(a,
{
var c = 0

while (b != 0)
{
if (b & 1)
c ^= a

b = b >> 1
a = a << 1

if (a & 0x10)
a ^= 0x13
}

return c
}

whirlpool.gf8mul = function(a,
{
var c = 0

while (b != 0)
{
if (b & 1)
c ^= a

b = b >> 1
a = a << 1

if (a & 0x100)
a ^= 0x11d
}

return c
}




Чтобы умножить два числа нужно вызвать одну из этих функций, а чтобы сложить нужно просто применить xor.




Выравнивание данных




Whirlpool — блочная хеш-функция. Это значит, что алгоритм обрабатывает входное сообщение по блокам фиксированного размера — 32 байта. Сообщение может быть любой длины, поэтому перед началом работы сообщение выравнивается по таким правилам:

1. Дописывают в конец бит равный 1.
2. Дописывают в конец нулевые биты так, чтобы длина сообщения получилась кратной 32 байтам, при этом отношение длина/32 должно быть нечётным.
3. Дописывают в конец длину исходного сообщения.

Рассмотрим это на примере строки «habrahabr»:



68 61 62 72 61 68 61 62
72 80 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 48




Первые 9 байт — ASCII коды букв из строки. Байт 0x80 это добавленный бит «1». В конце записано число битов в исходном сообщении: 9Г—8=72=0x48. После такого выравнивания сообщение выглядит как несколько 64-байтных блоков.




Вспомогательные функции Whirlpool




Алгоритм использует несколько простых вспомогательных функций, таких как E-Box, R-Box, S-Box.

• R-Box это просто массив из 16-ти 4-битных чисел. Он сгенерирован так, чтобы иметь некоторые особые свойства. Для реализации важно только то, что R-Box нельзя получить алгоритмически, потому что авторы Whirlpool использовали для генерации R-Box функцию random. Вот этот R-Box: [7, 12, 11, 13, 14, 4, 9, 15, 6, 3, 8, 10, 2, 5, 1, 0]
• E-Box получается так: E(n)=0xbⁿ, E(0xf)=0. Вычисления ведутся в поле GF(2⁴) — т.е. особое умножение и сложение как xor. Функция Inv-E-Box это E^-1 — функция обратная к E-Box. Фактически E-Box это массив из 16-ти 4-битных чисел.
  
  
  
  whirlpool.ebox = function(i)
  {
  var mul = whirlpool.gf4mul
  var ebox = whirlpool.ebox
  
  switch(i)
  {
  case 0: return 1
  case 0xf: return 0
  default: return mul(ebox(i - 1), 0xb)
  }
  }
  
  whirlpool.invebox = function(i)
  {
  for (var j = 0; j < 16; j++)
  if (whirlpool.ebox(j) == i)
  return j
  }
  
• S-Box принимает аргумент в диапазоне 0x00..0xff и возвращает число в том же диапазоне. Если считать, что b — один байт, а u, v — его верхняя и нижняя 4-битные половины, то S( = S(u, v) = (E(E(u) + a), E^-1(E^-1(v) + a)) где a = R(E(u) + E^-1(v)).
  
  
  
  whirlpool.sbox = function(i)
  {
  var v = i & 0xf
  var u = i >> 4
  
  var e = whirlpool.ebox
  var ie = whirlpool.invebox
  
  var a = whirlpool.rbox[e(u) ^ ie(v)]
  var u = e(e(u) ^ a)
  var v = ie(ie(v) ^ a)
  
  return (u << 4) ^ v
  }

Whirlpool воспринимает 64-байтный блок как матрицу 8Г—8 — первые 8 байт это первая строка матрицы, следующие 8 байт — вторая строка, и т.д. Алгоритм умеет делать несколько преобразований этой матрицы:

• rotate вращает k-ый столбец на k байт вниз. Нумерация с нуля. Исходная матрица:
  
  
  
  00 01 02 03 04 05 06 07
  10 11 12 13 14 15 16 17
  20 21 22 23 24 25 26 27
  30 31 32 33 34 35 36 37
  40 41 42 43 44 45 46 47
  50 51 52 53 54 55 56 57
  60 61 62 63 64 65 66 67
  70 71 72 73 74 75 76 77
  
  
  
  
  преобразованная матрица:
  
  
  
  00 71 62 53 44 35 26 17
  10 01 72 63 54 45 36 27
  20 11 02 73 64 55 46 37
  30 21 12 03 74 65 56 47
  40 31 22 13 04 75 66 57
  50 41 32 23 14 05 76 67
  60 51 42 33 24 15 06 77
  70 61 52 43 34 25 16 07
  
  
  
• diffuse умножает матрицу на матрицу особой структуры построенной за счёт вращения одной строки. Вот пример этой особой матрицы:
  
  
  
  00 01 02 03 04 05 06 07
  07 00 01 02 03 04 05 06
  06 07 00 01 02 03 04 05
  05 06 07 00 01 02 03 04
  04 05 06 07 00 01 02 03
  03 04 05 06 07 00 01 02
  02 03 04 05 06 07 00 01
  01 02 03 04 05 06 07 00
  
  
  
  
  Видно, что все строки получаются вращением первой строки. Whirlpool использует такую матрицу:
  
  
  
  01 01 04 01 08 05 02 09
  09 01 01 04 01 08 05 02
  02 09 01 01 04 01 08 05
  05 02 09 01 01 04 01 08
  08 05 02 09 01 01 04 01
  01 08 05 02 09 01 01 04
  04 01 08 05 02 09 01 01
  01 04 01 08 05 02 09 01
  
  
  
  
  diffuse(a) = a•d где d — описанная матрица. Умножение ведётся в поле GF(2⁸).
  
  
  
  whirlpool.diffuserow = [1, 1, 4, 1, 8, 5, 2, 9]
  
  whirlpool.diffuse = function(a)
  {
  var n = whirlpool.dim
  var b = whirlpool.matrix(n, n, 0)
  
  var mul = whirlpool.gf8mul
  var row = whirlpool.diffuserow
  
  for (var i = 0; i < n; i++)
  for (var j = 0; j < n; j++)
  for (var k = 0; k < n; k++)
  b[i][j] ^= mul(a[i][k], row[(j - k + n) % n])
  
  return b
  }

Схема обработки блоков




Whirlpool хранит внутреннее состояние H — матрицу 8Г—8 байт. В самом начале H=0. Когда приходит очередной 64-байтный блок B, Whirlpool его шифрует с помощью H и получает W(H, , после чего добавляет (операция xor) к своему состоянию полученное значение и исходный блок: H = H + B + W(H, . Осталось разобраться с шифрованием W.



Функция W(H, вычисляется по следующей схеме:



W = H + B
for m = 1..10 do
H = C(m) + diffuse(rotate(sbox(H)))
W = H + diffuse(rotate(sbox(W)))




где C_m это матрица 8Г—8 у которой все элементы нули, кроме первой строчки, которая берётся из S-Box: C_m[0..7] = S-Box[8(m-1)..8m-1]. Преобразования diffuse и rotate уже описаны, в sbox(A) просто применяет к каждому элементу матрицы функцию S-Box.



Выражение A + diffuse(rotate(sbox()) удобно записать в виде отдельной функции:



whirlpool.rfun = function(k, a)
{
a = whirlpool.apply(a)
a = whirlpool.rotate(a)
a = whirlpool.diffuse(a)
a = whirlpool.add(a, k)

return a
}




Вот реализация функции W(H, :



whirlpool.cipher = function(key, text)
{
var n = whirlpool.dim
var w = whirlpool.add(key, text)
var rcon = whirlpool.matrix(n, n, 0)

for (var r = 1; r <= whirlpool.rounds; r++)
{
for (var i = 0; i < n; i++)
rcon[0][i] = whirlpool.sbox(n*(r - 1) + i)

key = whirlpool.rfun(rcon, key)
w = whirlpool.rfun(key, w)
}

return w
}




Осталось реализовать схему H = H + B + W(H, :



whirlpool.compressor.prototype.push = function(block)
{
var h = this.state
var m = whirlpool.input(block) // преобразовать массив в матрицу 8Г—8
var c = whirlpool.cipher(h, m)

var n = whirlpool.dim

for (var i = 0; i < n; i++)
for (var j = 0; j < n; j++)
h[i][j] ^= c[i][j] ^ m[i][j]
}




После того как обработан последний 64-байтный блок, значение хеша находится в внутреннем состоянии H — матрице 8Г—8. Осталось лишь записать матрицу в виде массива и соединить байты в 64-байтный хеш.




Самое главное




Whirlpool хеш от habrahabr равен



d9d81b7f991a08b89f7cb899f3320564
da5cff67fcb021980862c693caf9d1ef
715f146aff6d92008544095d34451233
ffd83a420f6cdbaff9d5ccdc92407d77





Пример




Несколько комментариев к реализации примера. На вход хеш-функции может прийти как строка, так и массив их байтов. Также хочется иметь возможность вычислять хеши от синтетических сообщений — например от миллиона букв 'a'. Из за этой неоднородности входных данных я сделал чтение данных трёхслойным:

1. reader преобразует поток байтов в 32-байтные блоки. Он выравнивает сообщение и добавляет биты как сказано в описании Whirlpool.
2. hub преобразует поток 32-байтных блоков в поток 64-байтных блоков.
3. compressor принимает поток 64-байтных блоков и меняет состояние H по алгоритму Whirlpool.

Такая схема, с одной стороны, позволяет вычислять хеш очевидным способом whirlpool.hash('habrahabr'), а с другой стороны позволяет вычислить хеш от синтетического сообщения (для тестирования):



whirlpool.hash(function() { return 0x61 }, 1000000)





Исходники




Можно скачать здесь. Там два файла: html и js.
Original source: habrahabr.ru (comments).

Читать дальше