Interested Article - BLAKE (хеш-функция)
- 2020-07-15
- 1
BLAKE — криптографическая хеш-функция , в разработке которой принимали участие Жан-Филипп Омассон (Jean-Philippe Aumasson), Лука Хенцен (Luca Henzen), Вилли Майер (Willi Meier), Рафаэль Фан (Raphael C.-W. Phan).
Существуют два варианта хеш-функции: BLAKE-256 и BLAKE-512.
История
Впервые BLAKE была представлена на конкурсе криптографических алгоритмов, который проводился Национальным институтом стандартов и технологий США ( англ. , рус. SHA-3 (конкурс) ). BLAKE стала одним из пяти финалистов конкурса ( англ. ).
Криптостойкость
Хеш-функция BLAKE построена из трёх ранее изученных компонентов:
- режим итерации HAIFA обеспечивает стойкость к атакам второго рода
- внутренняя структура local wide-pipe обеспечивает защиту от коллизий
- алгоритм сжатия для BLAKE является модифицированной версией хорошо параллелизируемого поточного шифра , чья безопасность тщательно проанализирована
Быстродействие и реализация
Быстродействие на двух различных процессорах:
Процессор | Скорость (тактов/байт) | |
---|---|---|
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 |
Быстродействие на ППВМ ( англ. ):
На ППВМ 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 Гбит/с .
Алгоритм
Как упоминалось ранее, хеш-функция BLAKE построена из трёх ранее изученных компонентов:
- режим итерации HAIFA
- внутренняя структура local wide-pipe
- алгоритм сжатия для BLAKE, является модифицированной версией хорошо параллелизируемого поточного шифра , чья безопасность тщательно проанализирована.
Рассмотрим алгоритм BLAKE-256
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 = h 0 ,…,h 7 (8 слов);
- Блок сообщения m = m 0 ,…,m 15 ;
- Значение соли s = s 0 ,…,s 3 ;
- Значение счётчика t = t 0 ,t 1 .
Таким образом, на вход ей подаётся 30 слов (8+16+4+2=30, 30*4 = 120 байт = 960 бит). Возвращает функция сжатия только новое значение переменных цепочки: h' = h' 0 ,…,h' 7 . В дальнейшем будем обозначать h'=compress(h, m, s, t).
Инициализация
16 переменных, v 0 ,…,v 15 , описывающих текущее состояние 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-м раунде блок вычислений работает следующим образом:
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
Первые четыре блока G 0 ,…,G 3 могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G 0 ,…,G 3 column step . Точно так же могут быть параллельно вычислены G 4 ,…,G 7 , но они в свою очередь изменяют каждый свою диагональ матрицы состояния v . Поэтому назовём процедуру вычисления G 4 ,…,G 7 diagonal step . Возможность параллельного вычисления G i представлена графически.
На раундах, номера 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 . Padding гарантирует, что длина сообщения станет кратной 512 битам.
Чтобы высчитать хеш сообщения, результат функции padding делится на блоки из 16 слов m 0 ,…,m N-1 . Пусть L i — количество бит исходного сообщения в блоках m 0 ,…,m i , то есть исключая те биты, которые были добавлены в процедуре padding. Например, если сообщение имеет длину 600 бит, то после процедуры padding оно будет иметь длину 1024 бита и будет разделено на два блока: m 0 и m 1 . Притом L 0 =512, L 1 =600. В некоторых случаях последний блок не содержит бит оригинального сообщения. Например, если в исходном сообщении 1020 бит, то в результате процедуры padding оно будет иметь длину 1536 бит и в m 0 будет 512 бит исходного сообщения, в m 1 — 508, а в m 2 — 0. Выставим L 0 =512, L 1 =1020, а L 2 =0. То есть правило следующее: если в последнем блоке нет бит оригинального сообщения, то выставим счётчик L N-1 равным 0. Это гарантирует, что если i ≠ j , то L i ≠ L j . Значение соли определяется пользователем или задаётся равным 0, если её не нужно использовать ( s 0 =s 1 =s 2 =s 3 =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 ( ) — это улучшенная версия BLAKE — одного из пяти финалистов конкурса на хеш-функцию SHA-3 (главным образом улучшено быстродействие), представлена 21 декабря 2012 года. Разработчики: , , , и . Была создана как альтернатива широко использовавшимся в прошлом 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
Источники
- ↑ от 9 декабря 2017 на Wayback Machine , стр.3 Introduction.
- . Дата обращения: 21 декабря 2013. 16 апреля 2018 года.
- от 9 декабря 2017 на Wayback Machine , стр.8 Specification.
Литература
Eli Biham and Orr Dunkelman. . — ePrint, 2007. — 207 с.
Ссылки
- 2020-07-15
- 1