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, чья безопасность тщательно проанализирована

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

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

Процессор	Скорость (тактов/байт)
	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 Гбит/с .

Алгоритм

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

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

Рассмотрим алгоритм 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₀,...,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:

<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}</math>←<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} </math>

Раундовая функция

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

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-ом раунде блок вычислений <math>G_{i}(a,b,c,d)</math> работает следующим образом:

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₀,...,G₃ могут вычисляться параллельно, так как каждый изменяет свою определённую колонку переменных матрицы состояний. Назовём процедуру вычисления G₀,...,G₃ column step. Точно также могут быть параллельно вычислены G₄,...,G₇, но они в свою очередь изменяют каждый свою диагональ матрицы состояния v. Поэтому назовём процедуру вычисления G₄,...,G₇ diagonal step. Возможность параллельного вычисления G_i представлена графически. На раундах, номера r которых больше 9, используется перестановка σ_r%10, например на 13-том раунде используется σ₃.

Последний шаг

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

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₀,...,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). Хеш сообщения таким образом вычисляется:

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.net Сайт 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 соответственно.

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

Примечания

Источники

Здесь Ист.

Литература

Eli Biham and Orr Dunkelman. [eprint.iacr.org/2007/278 A framework for iterative hash functions - HAIFA]. — ePrint, 2007. — 207 с.

Ссылки

• [131002.net/blake/ Сайт BLAKE]
• [blake2.net/ Сайт BLAKE2]
• [cryptography.gmu.edu/athena/index.php?id=source_codes Исходный код на VHDL, разработанный Группой Исследователей в Области Криптографии университета Джорджа Мейсона]

Отрывок, характеризующий BLAKE (хеш-функция)

– Я вам дам по дворам бегать! – крикнул он.
Алпатыч вернулся в избу и, кликнув кучера, велел ему выезжать. Вслед за Алпатычем и за кучером вышли и все домочадцы Ферапонтова. Увидав дым и даже огни пожаров, видневшиеся теперь в начинавшихся сумерках, бабы, до тех пор молчавшие, вдруг заголосили, глядя на пожары. Как бы вторя им, послышались такие же плачи на других концах улицы. Алпатыч с кучером трясущимися руками расправлял запутавшиеся вожжи и постромки лошадей под навесом.
Когда Алпатыч выезжал из ворот, он увидал, как в отпертой лавке Ферапонтова человек десять солдат с громким говором насыпали мешки и ранцы пшеничной мукой и подсолнухами. В то же время, возвращаясь с улицы в лавку, вошел Ферапонтов. Увидав солдат, он хотел крикнуть что то, но вдруг остановился и, схватившись за волоса, захохотал рыдающим хохотом.
– Тащи всё, ребята! Не доставайся дьяволам! – закричал он, сам хватая мешки и выкидывая их на улицу. Некоторые солдаты, испугавшись, выбежали, некоторые продолжали насыпать. Увидав Алпатыча, Ферапонтов обратился к нему.
– Решилась! Расея! – крикнул он. – Алпатыч! решилась! Сам запалю. Решилась… – Ферапонтов побежал на двор.
По улице, запружая ее всю, непрерывно шли солдаты, так что Алпатыч не мог проехать и должен был дожидаться. Хозяйка Ферапонтова с детьми сидела также на телеге, ожидая того, чтобы можно было выехать.
Была уже совсем ночь. На небе были звезды и светился изредка застилаемый дымом молодой месяц. На спуске к Днепру повозки Алпатыча и хозяйки, медленно двигавшиеся в рядах солдат и других экипажей, должны были остановиться. Недалеко от перекрестка, у которого остановились повозки, в переулке, горели дом и лавки. Пожар уже догорал. Пламя то замирало и терялось в черном дыме, то вдруг вспыхивало ярко, до странности отчетливо освещая лица столпившихся людей, стоявших на перекрестке. Перед пожаром мелькали черные фигуры людей, и из за неумолкаемого треска огня слышались говор и крики. Алпатыч, слезший с повозки, видя, что повозку его еще не скоро пропустят, повернулся в переулок посмотреть пожар. Солдаты шныряли беспрестанно взад и вперед мимо пожара, и Алпатыч видел, как два солдата и с ними какой то человек во фризовой шинели тащили из пожара через улицу на соседний двор горевшие бревна; другие несли охапки сена.
Алпатыч подошел к большой толпе людей, стоявших против горевшего полным огнем высокого амбара. Стены были все в огне, задняя завалилась, крыша тесовая обрушилась, балки пылали. Очевидно, толпа ожидала той минуты, когда завалится крыша. Этого же ожидал Алпатыч.
– Алпатыч! – вдруг окликнул старика чей то знакомый голос.
– Батюшка, ваше сиятельство, – отвечал Алпатыч, мгновенно узнав голос своего молодого князя.
Князь Андрей, в плаще, верхом на вороной лошади, стоял за толпой и смотрел на Алпатыча.
– Ты как здесь? – спросил он.
– Ваше… ваше сиятельство, – проговорил Алпатыч и зарыдал… – Ваше, ваше… или уж пропали мы? Отец…
– Как ты здесь? – повторил князь Андрей.
Пламя ярко вспыхнуло в эту минуту и осветило Алпатычу бледное и изнуренное лицо его молодого барина. Алпатыч рассказал, как он был послан и как насилу мог уехать.
– Что же, ваше сиятельство, или мы пропали? – спросил он опять.
Князь Андрей, не отвечая, достал записную книжку и, приподняв колено, стал писать карандашом на вырванном листе. Он писал сестре:
«Смоленск сдают, – писал он, – Лысые Горы будут заняты неприятелем через неделю. Уезжайте сейчас в Москву. Отвечай мне тотчас, когда вы выедете, прислав нарочного в Усвяж».
Написав и передав листок Алпатычу, он на словах передал ему, как распорядиться отъездом князя, княжны и сына с учителем и как и куда ответить ему тотчас же. Еще не успел он окончить эти приказания, как верховой штабный начальник, сопутствуемый свитой, подскакал к нему.
– Вы полковник? – кричал штабный начальник, с немецким акцентом, знакомым князю Андрею голосом. – В вашем присутствии зажигают дома, а вы стоите? Что это значит такое? Вы ответите, – кричал Берг, который был теперь помощником начальника штаба левого фланга пехотных войск первой армии, – место весьма приятное и на виду, как говорил Берг.
Князь Андрей посмотрел на него и, не отвечая, продолжал, обращаясь к Алпатычу:
– Так скажи, что до десятого числа жду ответа, а ежели десятого не получу известия, что все уехали, я сам должен буду все бросить и ехать в Лысые Горы.
– Я, князь, только потому говорю, – сказал Берг, узнав князя Андрея, – что я должен исполнять приказания, потому что я всегда точно исполняю… Вы меня, пожалуйста, извините, – в чем то оправдывался Берг.
Что то затрещало в огне. Огонь притих на мгновенье; черные клубы дыма повалили из под крыши. Еще страшно затрещало что то в огне, и завалилось что то огромное.
– Урруру! – вторя завалившемуся потолку амбара, из которого несло запахом лепешек от сгоревшего хлеба, заревела толпа. Пламя вспыхнуло и осветило оживленно радостные и измученные лица людей, стоявших вокруг пожара.
Человек во фризовой шинели, подняв кверху руку, кричал:
– Важно! пошла драть! Ребята, важно!..
– Это сам хозяин, – послышались голоса.
– Так, так, – сказал князь Андрей, обращаясь к Алпатычу, – все передай, как я тебе говорил. – И, ни слова не отвечая Бергу, замолкшему подле него, тронул лошадь и поехал в переулок.


От Смоленска войска продолжали отступать. Неприятель шел вслед за ними. 10 го августа полк, которым командовал князь Андрей, проходил по большой дороге, мимо проспекта, ведущего в Лысые Горы. Жара и засуха стояли более трех недель. Каждый день по небу ходили курчавые облака, изредка заслоняя солнце; но к вечеру опять расчищало, и солнце садилось в буровато красную мглу. Только сильная роса ночью освежала землю. Остававшиеся на корню хлеба сгорали и высыпались. Болота пересохли. Скотина ревела от голода, не находя корма по сожженным солнцем лугам. Только по ночам и в лесах пока еще держалась роса, была прохлада. Но по дороге, по большой дороге, по которой шли войска, даже и ночью, даже и по лесам, не было этой прохлады. Роса не заметна была на песочной пыли дороги, встолченной больше чем на четверть аршина. Как только рассветало, начиналось движение. Обозы, артиллерия беззвучно шли по ступицу, а пехота по щиколку в мягкой, душной, не остывшей за ночь, жаркой пыли. Одна часть этой песочной пыли месилась ногами и колесами, другая поднималась и стояла облаком над войском, влипая в глаза, в волоса, в уши, в ноздри и, главное, в легкие людям и животным, двигавшимся по этой дороге. Чем выше поднималось солнце, тем выше поднималось облако пыли, и сквозь эту тонкую, жаркую пыль на солнце, не закрытое облаками, можно было смотреть простым глазом. Солнце представлялось большим багровым шаром. Ветра не было, и люди задыхались в этой неподвижной атмосфере. Люди шли, обвязавши носы и рты платками. Приходя к деревне, все бросалось к колодцам. Дрались за воду и выпивали ее до грязи.
Князь Андрей командовал полком, и устройство полка, благосостояние его людей, необходимость получения и отдачи приказаний занимали его. Пожар Смоленска и оставление его были эпохой для князя Андрея. Новое чувство озлобления против врага заставляло его забывать свое горе. Он весь был предан делам своего полка, он был заботлив о своих людях и офицерах и ласков с ними. В полку его называли наш князь, им гордились и его любили. Но добр и кроток он был только с своими полковыми, с Тимохиным и т. п., с людьми совершенно новыми и в чужой среде, с людьми, которые не могли знать и понимать его прошедшего; но как только он сталкивался с кем нибудь из своих прежних, из штабных, он тотчас опять ощетинивался; делался злобен, насмешлив и презрителен. Все, что связывало его воспоминание с прошедшим, отталкивало его, и потому он старался в отношениях этого прежнего мира только не быть несправедливым и исполнять свой долг.
Правда, все в темном, мрачном свете представлялось князю Андрею – особенно после того, как оставили Смоленск (который, по его понятиям, можно и должно было защищать) 6 го августа, и после того, как отец, больной, должен был бежать в Москву и бросить на расхищение столь любимые, обстроенные и им населенные Лысые Горы; но, несмотря на то, благодаря полку князь Андрей мог думать о другом, совершенно независимом от общих вопросов предмете – о своем полку. 10 го августа колонна, в которой был его полк, поравнялась с Лысыми Горами. Князь Андрей два дня тому назад получил известие, что его отец, сын и сестра уехали в Москву. Хотя князю Андрею и нечего было делать в Лысых Горах, он, с свойственным ему желанием растравить свое горе, решил, что он должен заехать в Лысые Горы.
Он велел оседлать себе лошадь и с перехода поехал верхом в отцовскую деревню, в которой он родился и провел свое детство. Проезжая мимо пруда, на котором всегда десятки баб, переговариваясь, били вальками и полоскали свое белье, князь Андрей заметил, что на пруде никого не было, и оторванный плотик, до половины залитый водой, боком плавал посредине пруда. Князь Андрей подъехал к сторожке. У каменных ворот въезда никого не было, и дверь была отперта. Дорожки сада уже заросли, и телята и лошади ходили по английскому парку. Князь Андрей подъехал к оранжерее; стекла были разбиты, и деревья в кадках некоторые повалены, некоторые засохли. Он окликнул Тараса садовника. Никто не откликнулся. Обогнув оранжерею на выставку, он увидал, что тесовый резной забор весь изломан и фрукты сливы обдерганы с ветками. Старый мужик (князь Андрей видал его у ворот в детстве) сидел и плел лапоть на зеленой скамеечке.
Он был глух и не слыхал подъезда князя Андрея. Он сидел на лавке, на которой любил сиживать старый князь, и около него было развешено лычко на сучках обломанной и засохшей магнолии.
Князь Андрей подъехал к дому. Несколько лип в старом саду были срублены, одна пегая с жеребенком лошадь ходила перед самым домом между розанами. Дом был заколочен ставнями. Одно окно внизу было открыто. Дворовый мальчик, увидав князя Андрея, вбежал в дом.
Алпатыч, услав семью, один оставался в Лысых Горах; он сидел дома и читал Жития. Узнав о приезде князя Андрея, он, с очками на носу, застегиваясь, вышел из дома, поспешно подошел к князю и, ничего не говоря, заплакал, целуя князя Андрея в коленку.