On the padding algorithm of large-sized blocks in integrity control systems.pdf Введение При работе с большими блоками (порядка 1 кбайт), например, как в алгоритме контроля целостности данных на основе аддитивных генераторов и s-боксов [1, 2], определение корректной и экономной процедуры дополнения блоков данных до подходящих размеров является одной из важнейших задач, так как для достижения хорошего перемешивания биты дополнения должны быть реализацией псевдослучайной функции. Для сравнения проанализированы известные схемы дополнения: дополнение битами (00. . . 0, 00. . . 01), двухступенчатое дополнение (SHA, MD5). Оценена производительность и свойства предложенного алгоритма. 1. Описание схемы дополнения Процедура дополнения файлов произвольной длины (в битах) до длины, кратной l, использует линейный конгруэнтный генератор (ЛКГ) над кольцом вычетов Zm , то есть линейное преобразование g кольца Zm вида g(X) = (aX + c) mod m. где X. a. c G Zm ; a = 0; числа a и c суть множитель и сдвиг соответственно. Обозначим X0 G Zm - начальное состояние ЛКГ; Xn+1 = g(Xn), n 0. ЛКГ порождает периодическую последовательность с начальным состоянием X0 и длиной периода m, если сдвиг нечётный и a = 1 (mod 4). Пусть D G V* - исходный файл, представимый как битовая последовательность, где V* -множество всех двоичных строк конечной длины; D' - последний неполный блок файла D. Если длинаp блока D' меньше l, то он дополняется до длины l блоком L длины l - p, и дополненный блок имеет вид D' || L (|| означает присоединение). Блок L длины l - p вырабатывается следующим образом: 1. Формируется начальное значение ЛКГ X0: а) строке P присваивается значение D', т. е. P = D'; б) строка P дополняется нулями до длины, кратной r = 64, т. е. P* = = (P||0 r -( p mod r ) ) ; в) строка P* разбивается на Tp/r~| блоков длины r: P* = (P1 || ... || P\\p/r-]), где Р1 . .... P[p/r~\\ G Vr; г) X0 = (P1 ffi ... ffi P\\p/r~\\) ((p/8) mod 64), где a b - операция цикли ческого сдвига элементов строки а на b позиций; ffl - сложение по модулю 2r. 2. С помощью ЛКГ [3] c начальным значением X0 и параметрами a = 6364136223846793005. c = 1442695040888963407. m = 264 порождается последовательность f(l - p)/r"| элементов {X1.... .Xp(l-p)/r^}, из которых формируется строка L*: L* = (X1||... ||Xr(, 3. Дополнение L образуют старшие l - p бит строки L*. 2. Экспериментальное сравнение характеристик процедур дополнения С помощью экспериментов исследованы следующие процедуры дополнения: 1) дополнение нулями; 2) дополнение битовым вектором (100. . . 000); 3) дополнение битовым вектором (100... 000)|| A, где A - запись длины дополняемой строки (для записи требуется 2 байта); 4) дополнение в соответствии с процедурой, описанной в п. 1. Обозначим данные процедуры дополнения как Padding 1, . . . , Padding 4 соответственно. 2.1. П р о д о л ж и т е л ь н о с т ь в ы п о л н е н и я о п е р а ц и и д о п о л н е н и я Проведено сравнение производительности процедур дополнения входных векторов. В ходе эксперимента сгенерировано по 20000 случайных входных строк длины L, которые дополнялись до длины 1024 байта, длина L изменялась от 100 до 1000 с шагом 100 байтов. Программная реализация процедур дополнения выполнена на языке программирования С++. Эксперименты проведены на ПЭВМ с процессором Intel(R) Core(TM) i5-8600 с постоянной тактовой частотой U = 4,1 ГГц, архитектура операционной системы 64-битная (x64). Оптимизация программного кода - /02. Время t, затраченное на формирование дополненного блока длины 1024 байт, измерялось с помощью системных часов реального времени стандартной библиотеки std::chrono. По формуле tU/L рассчитано среднее время, затраченное на дополнение, а также независимая от частоты процессора характеристика производительности процедуры - среднее количество тактов на байт (CpB). Результаты экспериментов приведены в табл. 1 и на рис. 1. Та б л и ц а 1 Результаты замера скорости процедуры дополнения Характеристика Padding 1 Padding 2 Padding 3 Padding 4 Среднее время дополнения, нс 148 189 204 320 Среднее число тактов на байт, CpB 1,475 2,266 2,399 3,452 По результатам эксперимента длительность дополнения с помощью ЛКГ больше, чем у других процедур, от 1,5 до 2 раз. Однако важно, что в системах контроля целостности файлов произвольной длины, использующих алгоритмы с большим блоком, например алгоритм AG-S [1], время генерации кода контроля целостности без учёта дополнения составляет 7100 нс. Следовательно, суммарное время с процедурой дополнения нулями составляет 7248 нс, а с предложенной процедурой дополнения - 7420 нс, т. е. общее замедление незначительно и не превышает 2,37%. Значит, с учётом общей продолжительности генерации кода процедура дополнения на основе ЛКГ другим процедурам существенно не уступает. 2.2. К р и п т о г р а ф и ч е с к и е х а р а к т е р и с т и к и п р о ц е д у р дополнения При анализе алгоритмов генерации кодов контроля целостности важные криптографические характеристики связаны с равномерностью распределения хэш-зна-чений, оценкой лавинного эффекта, поиском коллизий и производительностью хэш- Padding 1 Padding 2 Padding 3 • Padding 4 Рис. 1. Зависимость времени дополнения от размера входного блока функций. Статистические испытания были выполнены с помощью хорошо зарекомендовавшего себя на практике тестового пакета SMHasher [3]. В 2017 г. компания «Positive Technologies» использовала данный пакет тестов для тестирования разработанной функции хэширования [4]. Этот набор тестов (open-source продукт) предназначен для тестирования указанных криптографических характеристик. При тестировании за основу был взят алгоритм AG-S-Стрибог [2]. Были подготовлены четыре реализации, где входы дополнялись процедурами дополнения Padding 1-Padding 4. Сравнительные результаты тестирования данных реализаций с помощью тестов SMHasher представлены в табл. 2-4. Криптографические свойства реализаций в связи с процедурой дополнения были протестированы пакетом SMHasher, а именно группами тестов: «Avalanche»-на выполнение строгого лавинного критерия; «Sparse»-на поиск коллизий среди входов с большим количеством нулевых битов; «Permutation» -на поиск коллизий среди входов, составленных из повторяющихся блоков. Та б л и ц а 2 Общие результаты тестирования (количество пройденных тестов) Группа тестов Padding 1 Padding 2 Padding 3 Padding 4 Всего тестов «Avalanche» 6 6 12 12 12 «Sparse» 7 7 7 9 11 «Permutation» 0 2 2 2 15 Общее число пройденных тестов 13 15 21 23 38 Суммарное количество пройденных тестов реализации с процедурой дополнения на основе выходов ЛКГ больше, чем при других процедурах дополнения. Группа тестов «Avalanche» полностью пройдена при двухступенчатом дополнении и при дополнении на основе выходов ЛКГ. Результаты по группам тестов «Sparse» и «Permutation» представлены в табл. 3 и 4. Та б л и ц а 3 Количество коллизий при различных длинах входа в группе тестов «Sparse» Размер входного вектора, бит Padding 1 Padding 2 Padding 3 Padding 4 Всего входных векторов 72 241644 259209 109595 0 15082603 (0,016%) (0,017%) (0,007%) 96 46809 48817 28666 0 3469497 (0,013%) (0,014%) (0,008%) 160 719293 724939 468548 77968 26977161 (0,026 %) (0,024 %) (0,017%) (0,003 %) 256 179226 170800 131358 5465 2796417 (0,064 %) (0,061 %) (0,047%) (0,002 %) Всего коллизий 1186972 1203765 738167 83433 48325678 Доля коллизий среди всех входов 0,024562 0,024909 0,015275 0,001726 Применение процедуры дополнения на основе ЛКГ в группе тестов «Sparse» снижает количество коллизий примерно от 9 до 14 раз, что положительно характеризует её криптографические свойства. Та б л и ц а 4 Количество коллизий в группе тестов «Permutation» Параметр Padding 1 Padding 2 Padding 3 Padding 4 Всего входных векторов Общее число коллизий по всем тестам 8217021 6622245 6089853 4256492 20143432 Доля коллизий среди всех входов 0,407926 0,328755 0,302324 0,211309 Применение процедуры дополнения на основе ЛКГ в группе тестов «Permutation» снижает количество коллизий примерно от 1,5 до 2 раз. Выводы 1. Процедура дополнения на основе ЛКГ продолжительнее стандартных процедур дополнения от 1,5 до 2 раз, однако при этом общая продолжительность генерации кода другим процедурам существенно не уступает, замедление составляет не более 2,37%. 2. На примере алгоритма AG-S-Стрибог экспериментально показано, что процедура дополнения на основе ЛКГ может обеспечить преимущества перед другими известными процедурами по ряду важных криптографических свойств.

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