07.12.2023 18:21
ksartam 4 1500 Источник

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

Введение

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

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

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

Где применяются деревья хэширования? 

Во-первых, трудно представить Blockchain без деревьев хэширования. Без использование деревьев хэширования каждый узел всей сети должен был бы хранить полную копию каждой транзакции Bitcoin, когда-либо совершенной. Кроме того, любой запрос на аутентификацию в  Bitcoin требовал бы передачи огромного количества данных по сети, следовательно каждому устройству пришлось бы самостоятельно подтверждать подлинность данных. Чтобы подтвердить, что данные не испорчены компьютеру бы требовалась огромное количество вычислительных мощностей. 

Во-вторых, деревья хэширования могут использоваться для синхронизации данных в различных хранилищах. Например, NoSQL-система Apache Cassandra использует деревья хэширования для обнаружения несоответствия данных между своими репликами. Для отказоустойчивости каждая реплика может получать данные, и они должны быть синхронизированы между вами репликами. «Узлы» Cassandra обмениваются между собой хэш-деревьями. Преимущество этой стратегии заключается в том, что большие объемы данных могут быть сопоставлены при относительно небольшом количестве байт, передаваемых по сети. Стоит отметить, что и другие NoSQL системы(Riak и Dynamo) используют деревья хэширования.

В виду схожих соображений, деревья хэширования используются в файлов системах(IPFS, ZFS), системе резервного копирования Tahoe-LAFS.

Ну и, наконец, хэш-деревья используются в криптографии для хэширования больших объемов данных. 

В данном эссе будут рассмотрены различные древовидные способы хэширования, такие как MD6, Skein и Sakura, будут выявлены их преимущества и рассмотрены потенциальные проблемы. Таким образом, работа направлена не только на обзор основных древовидных методов хэширования, но и на выявление их реальной применимости.

Опишем общий способ формирования хэша для таких режимов работы:

  1. Входные данные делятся на блоки.

  2. Блоки помещаются в листья(последовательное преобразование слоев) либо во все узлы дерева(параллельное преобразование слоев).

  3. Узел вычисляется применением хэш-функции к соединенным с ним нижним узлам (количество этих узлов может быть больше 2).  Для вычисления итогового хэша иногда возможно применение последовательных алгоритмов. Для нижних узлов — листьев дерева хэш вычисляется от входных данных.

Далее будут описаны древовидные режимы работы для следующих функций: MD6, Skein и Sakura.

MD6

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

Можно сразу отметить достоинство алгоритма MD6 — возможность его адаптации к устройствам малой вычислительной мощности за счет ограничивающего параметра — максимальной высоты деревьев хэширования L : 0 \leq L \leq 64

Таким образом, вычисление хэша осуществляется за итераций, сжимая данные на каждом этапе в 4 раза.

Можно провести оценку этого параметра, если учесть, что входной размер данных хэш-функции не превосходит бит, а ращмер выходных данных 2^{10} бит L \leq \log_4\bigg({2^{64} \over {2^{10}}}\bigg)=27.  В силу того, что значение параметра по умолчанию L = 64

— поведение алгоритма по умолчанию гарантировано полностью иерархическое.

Для наглядности, перейдем к графической интерпретации алгоритма. 

На изображении 1 проиллюстрирован стандартный режим работы алгоритма MD6 с параметром L=64 (поведение по умолчанию — полностью древовидный режим). Опишем алгоритм подробнее:

  1. Каждый черный лист — блок входного сообщения размером 1024 бит. В силу того, что длина сообщения может быть не кратной 1024, к последнему блоку сообщения применяется паддинг нулями до 1024 бит.

  2. Каждый последующий слой (i = 1,2, \dots ) получается конкатенацией результатов вычисления хэш-функции напрямую связанных с ним нижних узлов (в данном случае, объединяются хэши от 4-х предыдущих узлов). Может возникнуть ситуация, что число предшественников не равно 4, в таком случае опять применяется паддинг до 4096 бит.

В случае нескольких деревьев хэширования, сначала вычисляются корневые значения каждого дерева, а значения из корней деревьев объединяются итеративно(последовательно — метод Меркля‑Дамгорда. К слову, не древовидная реализация MD6 работает с использованием исключительно этого метода).

Алгоритм MD6 принимал участие в конкурсе хэш-функций на разработку функции стандарта SHA-3 проводимым NIST. Несмотря на преимущества алгоритма для параллельных вычислений и его надежность и безопасность, MD6 не прошел во второй раунд состязания[4]. Причиной этому стала недостаточная скорость работы хэш-функции (о чем заявляли и сами разработчики). Чтобы решить проблему со скоростью работы, необходимо было бы сократить число «раундов» вычисления хэш-функции до 30-40, однако алгоритм на этих раундах теряет свои доказательства криптографической устойчивости к дифференциальным атакам.

Кроме того, можно отметить еще одну проблему, выявленную компанией Fortify, связанную с переполнением буфера[1]. Она была решена увеличением буфера в 2 раза (до 128 бит).

Алгоритм MD6 проявляет высокую эффективность в контексте параллелизации вычислений. Тем не менее, из-за определенных недостатков данный алгоритм не получил признание в рамках конкурса SHA-3, что ограничило его широкое принятие и популярность.

Skein

В алгоритме MD6 последнее сообщение дополняется до размера блока, однако существуют древовидные режимы способные работать без дополнения слоев дерева хэширования. Одним из них является древовидный режим алгоритма Skein. Этот алгоритм был разработан в 2008 году, основными требованиями при разработке служили оптимизация для минимального использования памяти и оптимизация под 64-разрядные процессоры. 

Древовидный режим алгоритма Skein работает на основе блочного шифра Threefish(как раз это и оптимизирует работы на 64-битных процессорах) и функции сжатия UBI. В силу достаточно сложной реализации алгоритма не будем приводить подробный анализ его принципа работы. 

Главное, что стоит отметить — высокая скорость работы Skein. Приведем результаты сравнения скоростей различных древовидных режимов:

На графике выше отображено сравнение скоростей различных древовидных режимов[8]. Можно заменить, что на больших объемах входных данных алгоритм Skein имеет колоссальное преимущество.  

Sakura

В силу увеличиваемых объемов обрабатываемых данных все сильнее встаёт необходимость поддержать параллельное хэширование в стандартах, в том числе в стандарте SHA-3. Неплохим решением проблемы выглядит использование подхода Sakura, позволяющего использовать для вычисления узлов дерева хэширования произвольные хэш-функции (они называются внутренними).

Этот режим работы определяется размером блоков входных данных B, а также атрибутом —меткой листа дерева — номером слоя дерева, на котором данный блок начинает обрабатываться.  За счет этого достигается большая гибкость алгоритма. 

Сначала разберём общий принцип работы Sakura.

  1. Как и в случае с MD6 исходное сообщение разбивается на блоки M_0 || \dots || M_{m-1} длины B, длина последнего блока может быть меньше B.

  2. Пусть l=0 , m_0 = m .

    Для каждого листа дерева вычисляется его атрибут — номер слоя начала вычислений. Опишем рекурсивный алгоритм вычисления этой метки:

    a) В случае, если 2^{j_0-1} \leq m_0 \leq 2^{j_0} , то всем блокам M_0, \dots , M_{2^{j_0-1}-1}последовательно присваиваются строки длины j_0 со значениями p \in 0,1,\dots,2^{j_0-1} -1

    b) Полагаем l = l + 1 , m_l = m_{l-1} - 2^{j_{l-1} -1}

    В случае, если 2^{j_l-1} \leq m_l \leq 2^{j_l}, то блокам M_{2^{j_0-1}+\dots+2^{j_{l-1}-1}}, \dots , M_{2^{j_0-1}+\dots+2^{j_{l}-1}-1} присваиваются j_l-битные строки со значениями 1^l ||p , где p \in 0,1,...2^{j_l-1}-1 .

  3. Узлы следующего слоя хэш-дерева создаются на основе объединения результата применения внутренней функции со значениями меток, соответствующими последовательным парам узлов предыдущего слоя, до тех пор, пока результирующий слой не будет состоять из одного узла.

    Причем, момент обработки с помощью внутренней функции листа с меткой длины j бит начинается на (k+1-j) слое.

На изображении 5 в глаза бросается деталь — возможная неравномерность использования алгоритмом входных данных. При некоторых значениях длины входного сообщения некоторые листья начнут обрабатываться только на предпоследнем слое дерева. Возможно, данный фактор способен оказать влияние на криптографическую защищенность функции. 

Что же касается стандартизации, Sakura поддерживает функцию Keccak (победитель конкурса SHA-3) в роли внутренней функции. При хэшировании больших файлов скорость является основным фактором. Древовидное хэширование повышает безопасность, а также скорость за счет использования многоядерных архитектур. В статье [10] описан выигрыш по времени при использовании режима Sakura для хэширования (с внутренним алгоритмом Keccak). Результаты проводились на разном количестве ядер одной и той же машины c использованием фреймворка OpenMP. 

Архитектура

Скорость (MB/s)

Время (с)

Ускорение

Intel Xeon 5645 (1 core)

208

9.8

1.0

Intel Xeon 5645 (6 cores)

839

2.4

4.03

Intel Xeon 5645 (12 cores)

1077

1.9

5.15

Можно заметить, что использование режима Sakura значительно оптимизирует процесс вычисления хэша от больших данных.

Заключение

В ходе нашего исследования мы рассмотрели три различных древовидных метода хэширования – MD6, Skein и Sakura, каждый из которых представляет собой уникальный подход к обработке данных. Эти методы внедряют новаторские стратегии для обеспечения безопасности и эффективности в условиях современных вычислительных требований.

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

Skein, созданный с учетом оптимизации использования памяти и предназначенный для работы на 64-битных процессорах, демонстрирует великолепную скорость обработки данных. Гибридный подход, включающий блочный шифр Threefish и функцию сжатия UBI, делает Skein конкурентоспособным и эффективным в условиях современных вычислительных требований.

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

В итоге, каждый из этих методов имеет свои преимущества и недостатки. MD6 обеспечивает иерархическую структуру, Skein выделяется выдающейся скоростью, а Sakura предоставляет стандартизированный и гибкий подход. Выбор между ними зависит от конкретных требований задачи, уровня безопасности и доступных вычислительных ресурсов. Существует множество методов древовидного хэширования, каждый со своими уникальными характеристиками, и выбор оптимального зависит от контекста применения.

Список источников

  1. Реализация функции MD6. GitHub. 2009.

  2. Ronald Rivest, Benjamin Agre, Daniel V Bailey, Christopher Crutchfield. «The MD6 hash function A proposal to NIST for SHA-3». 2009

3. Arnaud Bienner, Benoit Dequidt. «Parallel implementations of MD6, a modern cryptographic hash function». 2009

4. Schneier on Security. «MD6 Withdrawn from SHA-3 Competition». 2009.

5. Дали Ф. А., Миронкин В. О.. «Обзор подходов к построению древовидных режимов работы некоторых хэш-функций». 2017.

6. Дали Ф. А., Миронкин В. О.. «О древовидных режимах работы хэш-функций». 2018.

7. Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker. «The Skein Hash Function Family». 2010.

8. Богданов Д. С., Дали Ф. А., Миронкин В. О.. «Сравнительный анализ FT-режима с не- которыми древовидными режимами выработки хэш-кода». 2018

9. Guido Bertoni, Joan Daemen, Michaël Peeters & Gilles Van Assche. «Sakura: A Flexible Coding for Tree Hashing». 2013.

10. Raul H C Lopes, Virginia N. L. Franqueira, Peter Hobson. «Efficient computation of hashes». 2014.

11. Jack Vanlightly. «Exploring the use of Hash Trees for Data Synchronization - Part 1». 2016.

Комментарии (4)


  1. nin-jin
    08.12.2023 07:08
    #26243598
    +1

    А что мешает просто разбить файл на число равных частей заведомо превышающее числу ядер (64?), параллельно вычислить хеш для каждой из них, соединить хеши и вычислить хеш для них? хеш-функция может быть любой.


  1. mpa4b
    08.12.2023 07:08
    #26244152

    Придумать, как считать хеш деревом в много потоков особого ума не надо (у некоторых при этом ещё и неограниченная память получается, O(log n)). А вот придумать криптостойкий и при этом реально быстрый (скажем, быстрее чем MD5) однопоточный хеш -- надо постараться. Насколько я знаю, если не считать расширение команд типа SHA-NI, быстрее MD5 в 1 поток, так ничего и не придумали, притом что у MD5 бооольшие проблемы с collision resistance (которой у него нет).

    Есть ли в этом направлении какие-то разработки, интересно?


    1. GAG
      08.12.2023 07:08
      #26246568

      Если рассматривать реальную производительность на современном железе, а не исключительно однопоточные варианты, то стоит посмотреть в сторону семейства BLAKE, например, BLAKE3.


      1. mpa4b
        08.12.2023 07:08
        #26248194

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