Lt304888.ru

Туристические услуги

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

14-05-2023

Перейти к: навигация, поиск

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 = 5BE0CD1

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 раундов. Раунд - это операция над состоянием , которая производит вычисления, разбитые на следующие блоки:

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-том Раунде блок вычислений работает следующим образом:


Графическая иллюстрация работы блока вычислений 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 вычисляется из переменных матрицы состояния, входных переменных и из Соли :

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.

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

Алгоритм 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(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

Примечания

Комментарии

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

Источники

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

Здесь Ист.

Литература

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

Ссылки

  • Сайт BLAKE
  • Сайт BLAKE2
  • Исходный код на VHDL, разработанный Группой Исследователей в Области Криптографии университета Джорджа Мейсона
  Хеш-функции
Общего назначения

Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические

JH • HAVAL • Keccak (SHA-3) • LM-хеш • Luffa • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • Scrypt • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94 • ГОСТ Р 34.11-2012

Примечания

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

© 2020–2023 lt304888.ru, Россия, Волжский, ул. Больничная 49, +7 (8443) 85-29-01