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

Содержание

  • 1 История
  • 2 Криптостойкость
  • 3 Быстродействие и реализация
  • 4 Алгоритм 4.1 Константы
  • 4.2 Функции сжатия
  • 4.3 Инициализация
  • 4.4 Раундовая функция
  • 4.5 Последний шаг
  • 4.6 Хеширование сообщения
  • 4.7 Отличия от quarterround алгоритма ChaCha
  • 5 Хеши BLAKE
  • 6 BLAKE2
      6.1 Отличия от BLAKE
  • 6.2 Хеши BLAKE2
  • 7 Комментарии
  • 8 Источники
  • 9 Литература
  • 10 Ссылки
  • Быстродействие и реализация

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

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

    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 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 ) {displaystyle {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}}} ← ( h 0 h 1 h 2 h 3 h 4 h 5 h 6 h 7 s 0 ⊕ c 0 s 1 ⊕ c 1 s 2 ⊕ c 2 s 3 ⊕ c 3 t 0 ⊕ c 4 t 0 ⊕ c 5 t 1 ⊕ c 6 t 1 ⊕ c 7 ) {displaystyle {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 раундов. Раунд — это операция над состоянием v {displaystyle v} , которая производит вычисления, разбитые на следующие блоки:
    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-ом раунде блок вычислений G i ( a , b , c , d ) {displaystyle G_{i}(a,b,c,d)} работает следующим образом:


    Графическая иллюстрация работы блока вычислений Gi j ← σr%10[2×i] k ← σr%10[2×i+1] a ← a + b + (mj ⊕ ck) d ← (d ⊕ a) &gt,&gt,&gt, 16 c ← c + d b ← (b ⊕ c) &gt,&gt,&gt, 12 a ← a + b + (mk ⊕ cj) d ← (d ⊕ a) &gt,&gt,&gt, 8 c ← c + d b ← (b ⊕ c) &gt,&gt,&gt, 7


    Column step and diagonal step of BLAKE-256 hash function algorythm

    Первые четыре блока G0,…,G3

    могут вычисляться параллельно, так как каждый изменяет свою определённую
    колонку
    переменных матрицы состояний. Назовём процедуру вычисления
    G0,…,G3column step
    . Точно также могут быть параллельно вычислены
    G4,…,G7
    , но они в свою очередь изменяют каждый свою
    диагональ
    матрицы состояния
    v
    . Поэтому назовём процедуру вычисления
    G4,…,G7diagonal step
    . Возможность параллельного вычисления Gi представлена графически.











    На раундах, номера r

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

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

    После всех раундов новое значение переменных цепочки h’0,…,h’7 вычисляется из переменных v 0 , . . . , v 15 {displaystyle v_{0},…,v_{15}} матрицы состояния, входных переменных h {displaystyle h} и из соли s {displaystyle s} :

    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&lt,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

    • Добавление констант к сообщению.
    • Изменённое направление сдвига.

    Алгоритмы для АСИК

    Первые ASIC-майнеры, созданные в 2014 году, сразу завоевали симпатию майнеров. Их преимущества заключались в компактности, минимальном потреблении энергии и высокой производительности, что важно для майнинга. Сначала АСИКи выпускались под SHA-256, но сегодня выбор устройств шире. Для добычи на ASIC-майнерах применяется шесть алгоритмов.

    SHA-256

    Для Bitcoin, Namecoin, Terracoin, Bitcoin Cash и ряда других цифровых монет. Аббревиатура протокола — «безопасный алгоритм хеширования». Выпуск второй версии SHA датируется 2001 годом, а основная сфера применения — использование в виде стандарта безопасности для АНБ Соединенных Штатов.

    «Нулевая» версия SHA выпущена задолго до этого (в 1993 году), а спустя два года появилась SHA-1. Число 256 отражает величина сообщений (256 бит). Шифрованные сведения носят название хеш, а время обработки блока — около десяти минут. Новый блок появляется после подбора единственно правильного значения.

    При небольшой сложности криптосети SHA-256 подойдет для майнинга на CPU. В ситуации с BTC или его форком (Биткоин Кэш) эффективность добычи равна нулю. Для майнинга новых коинов (в том числе Биткоин) применяются ASIC-майнеры.

    К популярным моделям относится Bitmain AntMiner T9+, Bitmain AntMiner S9, Canaan AvalonMiner 821, Ebang Ebit E 10.1 Miner 18T. Производительность упомянутого оборудования от 10 до 18 ТХ/с в зависимости от модели.

    Scrypt

    Первой криптовалютой после Биткоина стал Лайткоин, основанный на алгоритме Scrypt. Сегодня на этом протоколе работают разные криптовалюты: Novacoin, Verge, Dogecoin, Florincoin и другие. Протокол отличается большим количеством уровней, запускаемых с помощью процесса SHA-256.

    Поиск хеша усложняется появлением шума из случайных цифр. При создании ключа применяется пароль, поэтому процесс взлома вызывает трудности. Атаковать систему путем подбора единственно верного значения не получится.

    Использование Scrypt требует оборудования с большей оперативкой, поэтому АСИК-майнеры на Скрипт появились не сразу. Преимущества протокола заключаются в меньшем потреблении электричества и возможности добычи на более простом оборудовании, к примеру, процессорах или видеокартах. Из-за высокой сложности майнинга Лайткоина майнить эту криптовалюту с помощью CPU или GPU нерентабельно.

    Особенность Scrypt в способности подменять величину хеша на меньший параметр. Этот фактор обеспечивает лучшую скорость работы. На формирование нового элемента цепи уходит около 30 секунд. Популярные программы для майнинга на алгоритме: CGMiner, SGMiner и другие.

    Вместе с некоторыми АСИК-майнерами идет программное обеспечение, что упрощает задачу майнеру. Популярные ASIC, работающие на Scrypt, — Bitmain Antminer L3+, Innosilicon A6 LTC Master, Innosilicon A4+ LTC Master, BW L-21. Хешрейт указанных устройств составляет от 504 до 1230 МХ/с.

    X11

    Алгоритм, созданный в 2014 году. На нем работают Dash, CannabisCoin и Startcoin. Протокол создавался под криптовалюту Дарккоин, впоследствии переименованной в Даш. Создатель ставил задачей сделать алгоритм для майнинга, устойчивый к вычислительным мощностям АСИК-майнеров. Для этого в X11 было объединено 11 различных функций хеш. Разработчик — Эван Даффилд.

    Стремления создателя не увенчались успехом — вскоре после АСИКов на Scrypt появились устройства для добычи Даш. Наиболее востребованные модели — Innosilicon A5 DashMaster, Pinidea ASIC X11 Miner DR-100, Bitmain AntMiner D3, iBeLink DM22G X11/Dash Miner. Производительность упомянутых аппаратов — от 19 до 32,5 ГХ/с.

    Преимущества X11 заключаются в безопасности, небольшом пороге для входа и возможности для добычи на слабом оборудовании (для «молодых» коинов). Программа — CCMiner. Сегодня продолжена тенденция развития X11. Это вылилось в появление протоколов от Х12 и выше (до Х17). Их отличие заключается в большем числе применяемых функций.

    Ethash

    Уникальный алгоритм, созданный специально для майнинга Эфира. Разработка началась в 2013 году, но функционирует алгоритм с 2015 года (появился вместе с криптовалютой). В 2020 году произошел хардфорк. В результате выделился Эфириум Классик (майнинг цифровой монеты происходит на Ethash). Создатель — Виталик Бутерин.

    Алгоритм Ethash работает следующим образом. Задача аппаратуры для добычи заключается в захвате элементов набора данных и их последующем объединении. Обновление информации происходит с периодичностью раз в 30 тысяч блоков. В процессе разработки алгоритма делался упор на устойчивость к АСИКам.

    Первое устройство ASIC на Ethash появилось в 2020 году. Единственный представитель — Bitmain Antminer E3. Хешрейт — 190 МХ/с. Кроме АСИКов, для майнинга Эфириума можно применять мощные видеокарты NVIDIA, к примеру, 1080 Ti.

    Equihash

    Алгори]майнинга Zcash[/anchor], получивший популярность благодаря упомянутой криптовалюте. На протоколе, кроме Zcash, работают монеты Horizen, Bitcoin Gold, ZenCash и другие, которые пользуются меньшим спросом. Особенность Equihash заключается в повышенных требованиях к оперативной памяти (объем от 2 гигабайт и выше). Разработчики — Бирюков А. и Ховратович Д.

    Суть протокола заключается в повышении шансов получения нужного хеша с увеличением числа участников. Вероятность нахождения равна два в степени «N» и разделенное на два. В 2020 году появился первый АСИК для майнинга монет на Equihash — Antminer Z9 mini, а еще через время AntMiner Z9. Производительность — от 10 кСол/с.

    Blake-256 (r14 или r8)

    Гибридные системы, обеспечивающие баланс между PoW и PoS. Оба алгоритма могут использоваться для добычи на видеокартах или АСИК-майнерах. Разработчиками считаются четыре человека — Хенцен Л., Омассон Ф, Фан Р., Майер В.

    Преимущества: простота, понятный интерфейс, уменьшение требований к оборудованию, быстрая обработка данных и возможность настройки. Blake-256 надежно защищен от взлома, устойчив к увеличению размера хеша и защищен от атак со стороны внешнего канала.

    На алгоритме работают следующие криптовалюты: Blakecoin, Decred, Dirac и другие. АСИК для добычи — AntMiner DR3. Производительность — 7,8 ТХ/с.

    Для остальных алгоритмов ASIC-майнеры пока не изготавливаются.

    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

    Технические особенности Декрет

    В консенсусной системе для назначения POS-майнеров применяется принцип децентрализованной лотереи, позволяющей голосовать за блоки PoW. Распределение субсидий для PoS и PoW происходит в соотношении 30% и 60% соответственно. Децентрализованная распределенная добыча долей позволяет участвовать в подтверждении даже участникам с малым количеством долей.

    Техническое устройство, помимо этого, отличают следующие параметры:

    • хеш-алгоритм Blake-256 в PoW-майнинге обеспечивает высокий уровень безопасности без потери скорости,
    • в неизменных transaction IDs (транзакционных хешах) подписи транзакций отделены от остальных операционных данных. Аналогичным образом реализовано исправление хеша сделки,
    • механизм Schnorr-подписи (с пороговой n-of-n поддержкой) позволяет группам подписантов заверять сделки офф-цепи своими подписями постоянного размера совместно. Это снижает нагрузку на блокчейн и обеспечивает повышенную конфиденциальность.

    В момент запуска криптосеть сразу задумывалась как система, совместимая со скриптами Bitcoin-транзакций, включая их возможные обновления в будущем. Обратная совместимость тоже была запланирована изначально.


    Понравилась статья? Поделиться с друзьями:
    Добавить комментарий