Experimental study of the characteristics of one method of integrity checking of large volume data storage.pdf Введение Обеспечение целостности хранимых данных относится к основным задачам защиты информации. В настоящее время применяются различные алгоритмы и подходы: хэш-функции (MD, SHA, ГОСТ 34.11-2018 и др.), хэш-функции с ключом (HMAC), блочные шифры в режиме выработки имитовставки (CMAC). При контроле целостности (КЦ) применяются также некриптографические методы с использованием кодов, обнаруживающих и/или исправляющих ошибки (коды Хэмминга, циклические коды (CRC) и др.). При динамическом контроле больших объёмов данных, КЦ исполняющей среды функционирования, а также при проведении оперативного аудита целевых систем возникает проблема вычислений с высокой ресурсоёмкостью. Непосредственное использование для решения данной проблемы известных подходов и алгоритмов затруднительно в силу имеющихся у них недостатков: высокой ресурсоёмкости, слабых криптографических характеристик и пр. В работе предложено альтернативное решение на основе комбинации высокопроизводительного алгоритма (например, CRC32) и хэш-функции, соответствующей современным требованиям к криптографической стойкости (например, ГОСТ34.11-2018). Удачное решение подразумевает компромисс между скоростью и криптографическими свойствами алгоритмов, исключающими применение вычислительно простых методов построения коллизий (примеры имеющих подобную слабость высокопроизводительных алгоритмов известны [1]). Исследования при построении нового алгоритма были направлены на решение следующих задач: - построение высокопроизводительных алгоритмов генерации кодов контроля целостности (ККЦ) и обоснование их свойств; - обоснование выбора параметров для реализации конкретного алгоритма; - определение корректной и экономной процедуры дополнения блоков данных до подходящих размеров; - сложность поиска коллизий, а также оценка вероятности коллизий для случайных входов; - оценка вычислительной сложности построенных алгоритмов генерации ККЦ; - разработка способа встраивания высокопроизводительного алгоритма генерации ККЦ в функцию хэширования; - оценка производительности и криптографических свойств построенного алгоритма. В работе описан новый алгоритм контроля целостности хранимых данных с использованием хэширования. При реализации алгоритма массив входных данных сначала разбивается на фрагменты, для которых с помощью высокопроизводительного алгоритма генерируются уникальные ККЦ. Конкатенация полученных ККЦ образует вход криптографической хэш-функции, выход хэш-функции есть ККЦ исходных данных. Проведены экспериментальные исследования производительности и криптографических свойств этого алгоритма. 1. Описание комбинированного алгоритма Схема комбинированного алгоритма КЦ дана на рис. 1. Массив входных данных M произвольного размера разбивается на блоки размера 1 кбайт (8192 бита). Если длина массива M не кратна размеру блока, то последний блок дополняется до 1 кбайт. Проанализированы различные алгоритмы дополнения и выбрана схема с учётом характеристик дополняемого блока. Рис. 1. Схема комбинированного алгоритма AG-S -Стрибог 1 кбайт ... D L - AG-S Для генерации уникального ККЦ каждого блока данных размера 1 кбайт использована схема AG-S на основе восьми аддитивных генераторов AG0,... , AG7 и S-бокса из ГОСТ 34.11-2018. Аддитивные генераторы (AG) реализуют преобразования регистра сдвига длины 16 над множеством V64 с функцией обратной связи, определённой в [2, 3]. Восемь тактов работы схемы обеспечивают перемешивание данных и формируют 128-битовый код. Вход хэш-функции по ГОСТ 34.11-2018 есть конкатенация полученных ККЦ для всех блоков данных, а 256-битовое хэш-значение есть ККЦ массива данных M в целом. Алгоритм обозначен AG-S-Стрибог. 2. Теоретические исследования класса алгоритмов генерации ККЦ Для класса преобразований на основе АГ и S-бокса (для предложенной схемы это преобразование V8192 Vg192) доказана биективность преобразования множества состояний AG0, . . . , AG7. Это позволило более точно оценить вероятность совпадения ККЦ для двух различных случайных блоков. Оценена сложность поиска блоков с одинаковыми ККЦ (264 опробований входов для схемы из п. 1). Получены характеристики перемешивающего орграфа, определяющие обоснованный выбор параметров для реализации конкретных преобразований. В частности, с использованием оценки локального экспонента перемешивающего графа преобразования оценена приемлемая для производительности и криптографических свойств глубина итерации преобразования. Оценена теоретическая вычислительная сложность предложенных алгоритмов. 3. Экспериментальные исследования Измерена производительность генерации контрольных кодов разными алгоритмами при входных блоках 1 кбайт (табл. 1). Эксперименты проведены на ПЭВМ с процессором Intel Core i5-8600 3.1 GHz без использования процессорных инструкций SHANI, SSE4.2. Та б л и ц а 1 Характеристики производительности Алгоритм CRC32 SHA2-256 SHA3-256 MD5 CMAC-Magma Стрибог AG-S CpB, такты/байт 8,664 26,435 48,855 18,405 61,306 42,55 9,516 Проведено сравнение алгоритмов CRC32, MD5, SHA2-256, SHA3-256, Стрибог и AG-S с помощью набора тестов SMHasher [4] для проверки по известной методике [5] реализаций хэш-функций. В табл. 2 приведены результаты следующих тестов: Sanity - на идентичность реализации хэш-функции и её математической модели; Avalanche - на выполнение строгого лавинного критерия; Chi2 - на равномерность распределения хэш-значений с помощью статистики х2; Differential - на поиск коллизий в множестве входов длины 64 и 128 бит, расстояние Хэмминга между которыми не более 5 и 4 соответственно; Collisions - на поиск коллизий и сравнение их количества с ожидаемым. Символами «+» и «-» в табл. 2 обозначено соответственно пройден тест или нет. Для тестов Differential и Collisions указана доля пройденных тестов из их общего числа. Та б л и ц а 2 Результаты применения набора тестов SMHasher Тест CRC32 MD5 SHA2-256 SHA3-256 Стрибог AG-S -Стрибог Sanity + + + + + + Avalanche - + + + + + Chi2 - + + + + + Differential 1/2 2/2 2/2 2/2 2/2 2/2 Collisions 6/41 36/41 41/41 41/41 41/41 25/41 Выводы 1. Алгоритм AG-S от 1,93 до 6,44 раз превышает по производительности известные функции хэширования (бесключевые и ключевые) и близок по производительности к CRC32. 2. По результатам тестов Avalanche, Chi2 и Differential алгоритм AG-S-Стрибог не уступает известным функциям хэширования и значительно превосходит алгоритм CRC32. Для усиления свойств алгоритма AG-S следует продолжить исследование коллизий.

Скачать электронную версию публикации