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), Q1 2011 | 7,49 | 5,64 |
AMD FX-8120 (Bulldozer), Q4 2011 | 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 констант (первые цифры числа пи):
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,…,v15, описывающих текущее состояние v, инициализируются начальными значениями в зависимости от входных данных и представлены в виде матрицы 4×4:
←
Раундовая функция
[править | править код]После того, как состояние v инициализировано, запускается серия из 14 раундов. Раунд — это операция над состоянием , которая производит вычисления, разбитые на следующие блоки:
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-м раунде блок вычислений работает следующим образом:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/The_Gi_function_of_BLAKE-256_Algorythm.png/220px-The_Gi_function_of_BLAKE-256_Algorythm.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Column_step_and_diagonal_step_of_BLAKE-256_hash_function_algorythm.png/220px-Column_step_and_diagonal_step_of_BLAKE-256_hash_function_algorythm.png)
Первые четыре блока G0,…,G3 могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G0,…,G3 column step. Точно так же могут быть параллельно вычислены G4,…,G7, но они в свою очередь изменяют каждый свою диагональ матрицы состояния v. Поэтому назовём процедуру вычисления G4,…,G7 diagonal step. Возможность параллельного вычисления Gi представлена графически.
На раундах, номера r которых больше 9, используется перестановка σr%10, например на 13-м раунде используется σ3.
Последний шаг
[править | править код]После всех раундов новое значение переменных цепочки h'0,…,h'7 вычисляется из переменных матрицы состояния, входных переменных и из соли :
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 бита и будет разделено на два блока: 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.
Отличия от 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
Источники
[править | править код]- ↑ 1 2 Документация 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 с.
Ссылки
[править | править код]- Сайт BLAKE
- Сайт BLAKE2
- Исходный код на VHDL, разработанный Группой Исследователей в Области Криптографии университета Джорджа Мейсона
Для улучшения этой статьи желательно:
|