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 стала одним из пяти финалистов конкурса (англ. финалисты).

КриптостойкостьПравить

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

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

Быстродействие и реализацияПравить

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

Процессор	Скорость (тактов/байт)
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 построена из трёх ранее изученных компонентов:

режим итерации 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 констант (Первые цифры числа пи):

c₀ = 243F6A88  c₁ = 85A308D3
c₂ = 13198A2E  c₃ = 03707344
c₄ = A4093822  c₅ = 299F31D0
c₆ = 082EFA98  c₇ = EC4E6C89
c₈ = 452821E6  c₉ = 38D01377
c₁₀ = BE5466CF  c₁₁ = 34E90C6C
c₁₂ = C0AC29B7  c₁₃ = C97C50DD
c₁₄ = 3F84D5B5  c₁₅ = B5470917

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

σ₀ =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
σ₁ = 14 10  4  8  9 15 13  6  1 12  0  2 11  7  5  3
σ₂ = 11  8 12  0  5  2 15 13 10 14  3  6  7  1  9  4
σ₃ =  7  9  3  1 13 12 11 14  2  6  5 10  4  0 15  8
σ₄ =  9  0  5  7  2  4 10 15 14  1 11 12  6  8  3 13
σ₅ =  2 12  6 10  0 11  8  3  4 13  7  5 15 14  1  9
σ₆ = 12  5  1 15 14 13  4 10  0  7  6  3  9  2  8 11
σ₇ = 13 11  7 14 12  1  3  9  5  0 15  4  8  6  2 10
σ₈ =  6 15 14  9 11  3  0  8 12  2 13  7  1  4 10  5
σ₉ = 10  2  8  4  7  6  1  5 15 11  9 14  3 12 13  0

Функции сжатияПравить

Функция сжатия алгоритма BLAKE-256 принимает на вход:

Переменные цепочки h = h₀,…,h₇ (8 слов);
Блок сообщения m = m₀,…,m₁₅;
Значение соли s = s₀,…,s₃;
Значение счётчика t = t₀,t₁.

Таким образом, на вход ей подаётся 30 слов (8+16+4+2=30, 30*4 = 120 байт = 960 бит). Возвращает функция сжатия только новое значение переменных цепочки: h' = h'₀,…,h'₇. В дальнейшем будем обозначать h'=compress(h, m, s, t).

ИнициализацияПравить

16 переменных, v₀,…,v₁₅, описывающих текущее состояние v, инициализируются начальными значениями в зависимости от входных данных и представлены в виде матрицы 4×4:

$\text{[math]}$ $\text{[math]}$ ${\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}}$ ← $\text{[math]}$ $\text{[math]}$ ${\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 раундов. Раунд — это операция над состоянием $\text{[math]}$ $\text{[math]}$ $v$ , которая производит вычисления, разбитые на следующие блоки:

G₀(v₀, v₄, v₈, v₁₂) G₁(v₁, v₅, v₉, v₁₃) G₂(v₂, v₆, v₁₀, v₁₄) G₃(v₃, v₇, v₁₁, v₁₅) 
G₄(v₀, v₅, v₁₀, v₁₅) G₅(v₁, v₆, v₁₁, v₁₂) G₆(v₂, v₇, v₈, v₁₃) G₇(v₃, v₄, v₉, v₁₄)

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

Графическая иллюстрация работы блока вычислений Gi

j ← σ_r%10[2×i]
k ← σ_r%10[2×i+1]
a ← a + b + (m_j ⊕ c_k)  
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

Первые четыре блока G₀,…,G₃ могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G₀,…,G₃ column step. Точно также могут быть параллельно вычислены G₄,…,G₇, но они в свою очередь изменяют каждый свою диагональ матрицы состояния v. Поэтому назовём процедуру вычисления G₄,…,G₇ diagonal step. Возможность параллельного вычисления G_i представлена графически.

На раундах, номера r которых больше 9, используется перестановка σ_r%10, например на 13-том раунде используется σ₃.

Последний шагПравить

После всех раундов новое значение переменных цепочки h'₀,…,h'₇ вычисляется из переменных $\text{[math]}$ $\text{[math]}$ $v_{0},...,v_{15}$ матрицы состояния, входных переменных $\text{[math]}$ $\text{[math]}$ $h$ и из соли $\text{[math]}$ $\text{[math]}$ $s$ :

h'₀ ← h₀ ⊕ s₀ ⊕ v₈
h'₁ ← h₁ ⊕ s₁ ⊕ v₉
h'₂ ← h₂ ⊕ s₂ ⊕ v₁₀
h'₃ ← h₃ ⊕ s₃ ⊕ v₁₁
h'₄ ← h₄ ⊕ s₄ ⊕ v₁₂
h'₅ ← h₅ ⊕ s₅ ⊕ v₁₃
h'₆ ← h₆ ⊕ s₆ ⊕ v₁₄
h'₇ ← h₇ ⊕ s₇ ⊕ v₁₅

Хеширование сообщенияПравить

Опишем процесс хеширования сообщения m длиной l<2^64 бит. Сначала сообщение дополняется функцией padding данными для кратности 512 битам (64 байтам), затем, блок за блоком, его обрабатывает функция сжатия compression function.

В функции padding сообщение сначала дополняется битами, так, что его длина становится по модулю 512 равной 447: сначала добавляется 1, затем необходимое количество нолей. После этого прибавляется ещё одна 1 и 64-битное представление длины сообщения l от старшего бита к младшему. Таким образом, длина сообщения становится кратной 512^{[Комм. 1]}. Padding гарантирует, что длина сообщения станет кратной 512 битам.

Чтобы высчитать хеш сообщения, результат функции padding делится на блоки из 16 слов m₀,…,m_N-1. Пусть L_i — количество бит исходного сообщения в блоках m₀,…,m_i, то есть исключая те биты, которые были добавлены в процедуре padding. Например, если сообщение имеет длину 600 бит, то после процедуры padding оно будет иметь длину 1024 бита и будет разделено на два блока: m₀ и m₁. Притом L₀=512, L₁=600. В некоторых случаях последний блок не содержит бит оригинального сообщения. Например, если в исходном сообщении 1020 бит, то в результате процедуры padding оно будет иметь длину 1536 бит и в m₀ будет 512 бит исходного сообщения, в m₁ — 508, а в m₂ — 0. Выставим L₀=512, L₁=1020, а L₂=0. То есть правило следующее: если в последнем блоке нет бит оригинального сообщения, то выставим счётчик L_N-1 равным 0. Это гарантирует, что если i ≠ j, то L_i ≠ L_j. Значение соли определяется пользователем или задаётся равным 0, если её не нужно использовать (s₀=s₁=s₂=s₃=0). Хеш сообщения таким образом вычисляется:

h⁰ ← IV
for i=0,...,N-1
   hⁱ⁺¹ ← compress(hⁱ,mⁱ,s,lⁱ)
return h^N.

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

Алгоритм 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 — одного из пяти финалистов конкурса на хеш-функцию 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 соответственно.

Хеши 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

КомментарииПравить

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

ИсточникиПравить

↑ ¹ ² Документация BLAKE на официальном сайте Архивная копия от 9 декабря 2017 на Wayback Machine, стр.3 Introduction.
↑ Официальный сайт BLAKE (неопр.). Дата обращения: 21 декабря 2013. Архивировано 16 апреля 2018 года.
↑ Документация BLAKE на официальном сайте Архивная копия от 9 декабря 2017 на Wayback Machine, стр.8 Specification.

ЛитератураПравить

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

СсылкиПравить

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

[Documentation_Introduction-1] ¹ ² Документация BLAKE на официальном сайте Архивная копия от 9 декабря 2017 на Wayback Machine, стр.3 Introduction.

[Site_BLAKE-2] Официальный сайт BLAKE (неопр.). Дата обращения: 21 декабря 2013. Архивировано 16 апреля 2018 года.

[Documentation_Specification-3] Документация BLAKE на официальном сайте Архивная копия от 9 декабря 2017 на Wayback Machine, стр.8 Specification.

[1]

[2]

[3]

[Комм. 1]