На ППВМ Xilinx Virtex 5 BLAKE-256 реализуется на 56 ячейках и может достигать пропускной способности более чем в 160 Мбит/с, а BLAKE-512 — на 108 ячейках и со скоростью до 270 Мбит/с.
На 180nm ASIC, BLAKE-256 может быть реализована на 13.5 kGE. На 90nm ASIC BLAKE-256 реализована на 38 kGE и может достигать производительности в 10 Гбит/с, а BLAKE-512 — на 79 kGE и со скоростью 15 Гбит/с[2].
Алгоритм
Как упоминалось ранее, хеш-функция BLAKE построена из трёх ранее изученных компонентов:
Функция сжатия алгоритма BLAKE-256 принимает на вход:
Переменные цепочки h = h0,…,h7 (8 слов);
Блок сообщения m = m0,…,m15;
Значение соли s = s0,…,s3;
Значение счётчика t = t0,t1.
Таким образом, на вход ей подаётся 30 слов (8+16+4+2=30, 30*4 = 120 байт = 960 бит). Возвращает функция сжатия только новое значение переменных цепочки: h' = h'0,…,h'7. В дальнейшем будем обозначать h'=compress(h, m, s, t).
Инициализация
16 переменных, v0,…,v15, описывающих текущее состояние v, инициализируются начальными значениями в зависимости от входных данных и представлены в виде матрицы 4×4:
←
Раундовая функция
После того, как состояние v инициализировано, запускается серия из 14 раундов. Раунд — это операция над состоянием , которая производит вычисления, разбитые на следующие блоки:
на r-м раунде блок вычислений работает следующим образом:
j ← σr%10[2×i]
k ← σr%10[2×i+1]
a ← a + b + (mj ⊕ ck)
d ← (d ⊕ a) >>> 16
c ← c + d
b ← (b ⊕ c) >>> 12
a ← a + b + (mk ⊕ cj)
d ← (d ⊕ a) >>> 8
c ← c + d
b ← (b ⊕ c) >>> 7
Первые четыре блока G0,…,G3 могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G0,…,G3column step. Точно так же могут быть параллельно вычислены G4,…,G7, но они в свою очередь изменяют каждый свою диагональ матрицы состояния v. Поэтому назовём процедуру вычисления G4,…,G7diagonal step. Возможность параллельного вычисления Gi представлена графически.
На раундах, номера r которых больше 9, используется перестановка σr%10, например на 13-м раунде используется σ3.
Последний шаг
После всех раундов новое значение переменных цепочки h'0,…,h'7 вычисляется из переменных матрицы состояния, входных переменных и из соли :
Опишем процесс хеширования сообщения m длиной l<2^64 бит. Сначала сообщение дополняется функцией padding данными для кратности 512 битам (64 байтам), затем, блок за блоком, его обрабатывает функция сжатия compression function.
В функции padding сообщение сначала дополняется битами, так, что его длина становится по модулю 512 равной 447: сначала добавляется 1, затем необходимое количество нолей. После этого прибавляется ещё одна 1 и 64-битное представление длины сообщения l от старшего бита к младшему. Таким образом, длина сообщения становится кратной 512[Комм. 1].
Padding гарантирует, что длина сообщения станет кратной 512 битам.
Чтобы высчитать хеш сообщения, результат функции padding делится на блоки из 16 слов m0,…,mN-1. Пусть Li — количество бит исходного сообщения в блоках m0,…,mi, то есть исключая те биты, которые были добавлены в процедуре padding. Например, если сообщение имеет длину 600 бит, то после процедуры padding оно будет иметь длину 1024 бита и будет разделено на два блока: m0 и m1. Притом L0=512, L1=600. В некоторых случаях последний блок не содержит бит оригинального сообщения. Например, если в исходном сообщении 1020 бит, то в результате процедуры padding оно будет иметь длину 1536 бит и в m0 будет 512 бит исходного сообщения, в m1 — 508, а в m2 — 0. Выставим L0=512, L1=1020, а L2=0. То есть правило следующее: если в последнем блоке нет бит оригинального сообщения, то выставим счётчик LN-1 равным 0. Это гарантирует, что если i ≠ j, то Li ≠ Lj.
Значение соли определяется пользователем или задаётся равным 0, если её не нужно использовать (s0=s1=s2=s3=0). Хеш сообщения таким образом вычисляется:
h0 ← IV
for i=0,...,N-1
hi+1 ← compress(hi,mi,s,li)
return hN.
Процесс хеширования представлен наглядно на блок-схеме:
Алгоритм 64-битной версии функции идентичен: значения сдвига равны 32, 25, 16 и 11 соответственно, число раундов увеличено до 16.
BLAKE-512("The quick brown fox jumps over the lazy dog")
= 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD
2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451
BLAKE2
BLAKE2 (Сайт BLAKE2) — это улучшенная версия BLAKE — одного из пяти финалистов конкурса на хеш-функцию SHA-3 (главным образом улучшено быстродействие), представлена 21 декабря 2012 года. Разработчики: Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O'Hearn, и Christian Winnerlein. Была создана как альтернатива широко использовавшимся в прошлом MD5 и SHA-1, в которых были найдены уязвимости.
Отличия от BLAKE
В BLAKE2, в отличие от BLAKE, нет добавления констант в раундовой функции. Также изменены константы сдвига, упрощено добавление, добавлен блок параметров, который складывается с инициализирующими векторами. Кроме того, сокращено число раундов с 16 до 12 у функции BLAKE2b (аналог BLAKE-512) и с 14 до 10 у BLAKE2s (аналог BLAKE-256). В результате число тактов на бит сократилось с 7,49 для BLAKE-256 и 5,64 для BLAKE-512 до 5,34 и 3,32 для Blake2s и Blake2b соответственно.
BLAKE2b-512("The quick brown fox jumps over the lazy dog")
= A8ADD4BDDDFD93E4877D2746E62817B116364A1FA7BC148D95090BC7333B3673
F82401CF7AA2E4CB1ECD90296E3F14CB5413F8ED77BE73045B13914CDCD6A918
BLAKE2s-128("The quick brown fox jumps over the lazy dog")
= 96FD07258925748A0D2FB1C8A1167A73
Комментарии
↑Например, к сообщению длиной 447 бит прибавится 1, затем 511 нолей (длина станет равной 447+512), затем ещё 1 и 64-битное представление числа l=447 — 00…0110111111. Таким образом, длина станет равной 447+512+1+64 = 1024, что кратно 512