BLAKE (хеш-функция)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

BLAKEкриптографическая хеш-функция, разработанная Жеаном-Филиппом Омассоном (Jean-Philippe Aumasson), Лукой Хенцен (Luca Henzen), Вилли Майер (Willi Meier), Рафаэлем Фан(Raphael C.-W. Phan).

Существуют два варианта хеш-функции: BLAKE-256 и BLAKE-512.

История[править | править вики-текст]

Впервые BLAKE была представлена на конкурсе криптографических алгоритмов, который проводился Национальным институтом стандартов и технологий США (англ. NIST hash function competition, рус. SHA-3 (конкурс)). BLAKE стала одним из 5 финалистов конкурса (англ. финалисты).

Криптостойкость[править | править вики-текст]

Хеш функция BLAKE постороена из 3-х ранее изученных компонентов:

  • режим итерации HAIFA обеспечивает стойкость к атакам второго рода
  • внутренняя структура local wide-pipe обеспечивает защиту от коллизий
  • алгоритм сжатия для BLAKE является модифицированной версией хорошо параллелизируемого поточного шифра ChaCha, чья безопасность хорошо проанализирована[1]

Быстродействие и реализация[править | править вики-текст]

Быстродействие на 2 различных процессорах:

Процессор Скорость (тактов/байт)
BLAKE-256 BLAKE-512
Intel Core i5-2400M (Sandy Bridge) 7.49 5.64
AMD FX-8120 (Bulldozer) 11.83 6.88

Возможность реализации на различных микроконтроллерах:

Микроконтроллер BLAKE-256 BLAKE-512
RAM(байт) ROM(байт) RAM(байт) ROM(байт)
Cortex-M3 based microcontroller (32-bit processor) 280 1320 516 1776
ATmega1284P microcontroller (8-bit processor) 267 3434 525 6350

Быстродействие на ППВМ (англ. FPGA):

На ППВМ Xilinx Virtex 5, BLAKE-256 реализуется на 56 ячейках и может достигать пропускной способности более чем в 160 Мбит/с, а BLAKE-512 - на 108 ячейках и со скоростью до 270 Мбит/с.

Быстродействие на ASIC:

На 180nm ASIC, BLAKE-256 может быть реализована на 13.5 kGE. На 90nm ASIC, BLAKE-256 реализована на 38 kGE и может достигать производительности в 10 Гбит/с, а BLAKE-512 - на 79 kGE и со скоростью 15 Гбит/с [2].

Алгоритм[править | править вики-текст]

Как упоминалось ранее, хеш функция BLAKE постороена из 3-х ранее изученных компонентов:

  • Режим итерации HAIFA
  • внутренняя структура local wide-pipe
  • алгоритм сжатия для BLAKE является модифицированной версией хорошо параллелизируемого поточного шифра ChaCha, чья безопасность хорошо проанализирована.[1]

Рассмотрим алгоритм BLAKE-256[3]

BLAKE-256 оперирует с 32-х битными словами и возвращает 32-х битный хеш.

Константы[править | править вики-текст]

Существуют начальные константы, т.н. INITIAL VALUES (IV):

IV0 = 6A09E667 IV1 = BB67AE85
IV2 = 3C6EF372 IV3 = A54FF53A
IV4 = 510E527F IV5 = 9B05688C
IV6 = 1F83D9AB IV7 = 5BE0CD19

16 констант (Первые цифры числа пи):

c0  = 243F6A88  c1  = 85A308D3
c2  = 13198A2E  c3  = 03707344
c4  = A4093822  c5  = 299F31D0
c6  = 082EFA98  c7  = EC4E6C89
c8  = 452821E6  c9  = 38D01377
c10 = BE5466CF  c11 = 34E90C6C
c12 = C0AC29B7  c13 = C97C50DD
c14 = 3F84D5B5  c15 = B5470917 

перестановки {0,...,15} (используются во всех функциях BLAKE):

σ0 =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
σ1 = 14 10  4  8  9 15 13  6  1 12  0  2 11  7  5  3
σ2 = 11  8 12  0  5  2 15 13 10 14  3  6  7  1  9  4
σ3 =  7  9  3  1 13 12 11 14  2  6  5 10  4  0 15  8
σ4 =  9  0  5  7  2  4 10 15 14  1 11 12  6  8  3 13
σ5 =  2 12  6 10  0 11  8  3  4 13  7  5 15 14  1  9
σ6 = 12  5  1 15 14 13  4 10  0  7  6  3  9  2  8 11
σ7 = 13 11  7 14 12  1  3  9  5  0 15  4  8  6  2 10
σ8 =  6 15 14  9 11  3  0  8 12  2 13  7  1  4 10  5
σ9 = 10  2  8  4  7  6  1  5 15 11  9 14  3 12 13  0

Функции сжатия[править | править вики-текст]

Функция сжатия алгоритма 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,...,v0, описывающих текущее состояние v, инициализируются начальными значениями в зависимости от входных данных и представлены в виде матрицы 4×4:

\begin{pmatrix} 
v_{0}   & v_{1}   & v_{2}   & v_{3} \\
v_{4}   & v_{5}   & v_{6}   & v_{7} \\
v_{8}   & v_{9}   & v_{10}  & v_{11} \\
v_{12}  & v_{13}  & v_{14}  & v_{15} \\
\end{pmatrix}\begin{pmatrix} 
h_{0}                & h_{1}                & h_{2}                & h_{3} \\
h_{4}                & h_{5}                & h_{6}                & h_{7} \\
s_{0} \oplus c_{0}   & s_{1} \oplus c_{1}   & s_{2} \oplus c_{2}   & s_{3} \oplus c_{3}  \\
t_{0} \oplus c_{4}   & t_{0} \oplus c_{5}   & t_{1} \oplus c_{6}   & t_{1} \oplus c_{7}  \\
\end{pmatrix}

Раундовая функция[править | править вики-текст]

После того, как состояние v инициализировано, запускается серия из 14 раундов. Раунд - это операция над состоянием v, которая производит вычисления, разбитые на следующие блоки:

G0(v0, v4, v8 , v12) G1(v1, v5, v9 , v13) G2(v2, v6, v10, v14) G3(v3, v7, v11, v15) 
G4(v0, v5, v10, v15) G5(v1, v6, v11, v12) G6(v2, v7, v8 , v13) G7(v3, v4, v9 , v14)   

есь на r-том Раунде блок вычислений G_{i}(a,b,c,d) работает следующим образом:

Графическая иллюстрация работы блока вычислений Gi
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 + (m[k] ⊕ c[j])  
d ← (d ⊕ a) >>> 8
c ← c + d                   
b ← (b ⊕ c) >>> 7
Column step and diagonal step of BLAKE-256 hash function algorythm

Первые четыре блока G0,...,G3 могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G0,...,G3 column step. Точно также могут быть параллельно вычислены G4,...,G7, но они в свою очередь изменяют каждый свою диагональ матрицы состояния v. Поэтому назовём процедуру вычисления G4,...,G7 diagonal step. Возможность параллельного вычисления Gi представлена графически. На раундах , номера r которых больше 9, используется перестановка σr%10, например на 13-том раунде используется σ3.

Последний шаг[править | править вики-текст]

После всех раундов новое значение переменных цепочки h'0,...,h'7 вычисляется из переменных v_{0},...,v_{15} матрицы состояния, входных переменных h и из Соли s:

h'0 ← h0 ⊕ s0 ⊕ v8
h'1 ← h1 ⊕ s1 ⊕ v9
h'2 ← h2 ⊕ s2 ⊕ v10
h'3 ← h3 ⊕ s3 ⊕ v11
h'4 ← h4 ⊕ s4 ⊕ v12
h'5 ← h5 ⊕ s5 ⊕ v13
h'6 ← h6 ⊕ s6 ⊕ v14
h'7 ← h7 ⊕ s7 ⊕ v15

Хеширование сообщения[править | править вики-текст]

Опишем процесс хешировния сообщения 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 бита и будет разделено на 2 блока: 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.

Процесс хеширования представлен наглядно на блок-схеме:

Block-diagram of BLAKE hash function algorythm

Алгоритм 64-х битной версии функции идентичен: Значения сдвига равны 32, 25, 16 и 11 соответственно, число раундов увеличено до 16.

Отличия от quarterround алгоритма ChaCha[править | править вики-текст]

  • Добавление констант к сообщению.
  • Изменённое направление сдвига.

Хеши BLAKE[править | править вики-текст]

BLAKE-512("")
 = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B
   628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8
BLAKE-512("The quick brown fox jumps over the lazy dog")
 = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD
   2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451

BLAKE2[править | править вики-текст]

BLAKE2(Сайт BLAKE2) — улучшенная версия BLAKE - одной из 5 финалистов конкурса на хеш-функцию 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 соответственно.

3.32 5.34

Хеши BLAKE2[править | править вики-текст]

BLAKE2b-512("")
 = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419
   D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE
BLAKE2b-512("The quick brown fox jumps over the lazy dog")
 = A8ADD4BDDDFD93E4877D2746E62817B116364A1FA7BC148D95090BC7333B3673
   F82401CF7AA2E4CB1ECD90296E3F14CB5413F8ED77BE73045B13914CDCD6A918

BLAKE2s-256("")
= 69217A3079908094E11121D042354A7C1F55B6482CA1A51E1B250DFD1ED0EEF9

BLAKE2s-256("The quick brown fox jumps over the lazy dog")
= 606BEEEC743CCBEFF6CBCDF5D5302AA855C256C29B88C8ED331EA1A6BF3C8812

BLAKE2s-128("")
= 64550D6FFE2C0A01A14ABA1EADE0200C

BLAKE2s-128("The quick brown fox jumps over the lazy dog")
= 96FD07258925748A0D2FB1C8A1167A73

Примечания[править | править вики-текст]

Комментарии[править | править вики-текст]

  1. Например, к сообщению длиной 447 бит прибавится 1, затем 511 нолей (длина станет равной 447+512), затем ещё 1 и 64-х битное представление числа l=447 - 00...0110111111. Таким образом длина станет равной 447+512+1+64 = 1024, что кратно 512

Источники[править | править вики-текст]

  1. 1 2 Документация BLAKE на официальном сайте, стр.3 Introduction.
  2. Оффициальный сайт BLAKE
  3. Документация BLAKE на оффициальном сайте, стр.8 Specification.

Здесь Ист.

Литература[править | править вики-текст]

Eli Biham and Orr Dunkelman A framework for iterative hash functions - HAIFA. — ePrint, 2007. — 207 с.

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]