Xарактеристики алгоритма контроля целостности данных на основе аддитивных генераторов и s-боксов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/19

Xарактеристики алгоритма контроля целостности данных на основе аддитивных генераторов и s-боксов

При проведении анализа программного обеспечения актуальна задача контроля целостности данных больших массивов, при решении которой важно обеспечить приемлемый компромисс между криптографическими свойствами алгоритма контроля целостности и ресурсами, необходимыми для его реализации. Для блоков данных размера 1 кбайт (1024 байта) предложен алгоритм генерации 128-битового кода контроля целостности (ККЦ) с положительными (с позиции синтеза) эксплуатационными и криптографическими свойствами. Алгоритм построен на основе преобразований аддитивных генераторов и s-боксов и реализует функцию ^(g*): V213 ^ V128 со свойством полного перемешивания входных данных. При 6 ^ t ^ 100 каждый бит кода существенно зависит от всех битов информационного блока. При случайном равновероятном выборе начального состояния u вероятность получить любой код Q оценивается величиной 2-128. Среднее число опробований пар блоков (u,u!), где u = u! и Q(u) = Q(u'), приблизительно равно 264. Сложность вычисления функции ^(g*) имеет порядок t(5u + 8v), где u - вычислительная сложность суммирования двух чисел по модулю 264; v - сложность вычисления s-бокса. В соответствии с проведёнными экспериментами скорость генерации ККЦ варьируется в пределах от 3500 (t = 6) до 250 Мбит/с (t = 96), соответственно при тех же значениях t время генерации ККЦ варьируется в пределах от 18 до 250 мкс.

Characteristics of the data integrity check algorithm based on additive generators and s-boxes.pdf Введение Одной из важных задач защиты информации является контроль целостности, который осуществляется с помощью присоединения создателем информации к информационному /-битовому блоку m-битового кода контроля целостности, m < /, представляющего собой двоичную комбинацию, функционально связанную с блоком. Для генерации ККЦ обычно применяются криптографические хэш-функции (SHA, ГОСТ 34.11-2018 и др.) или алгоритмы генерации циклических избыточных кодов (CRC16, CRC32 и др.). Надёжные криптографические хэш-функции требуют значительных ресурсов. При использовании циклических избыточных кодов, обеспечивающих помехоустойчивое кодирование, сложность нахождения коллизии не высока. Поэтому актуально построение альтернативных алгоритмов генерации ККЦ, обладающих следующими положительными свойствами: - биективность преобразования, на основе которого строится алгоритм генерации ККЦ, это минимизирует вероятность совпадения ККЦ для разных блоков; - полное перемешивание входных данных (существенная зависимость каждого бита ККЦ от каждого бита блока данных), это затрудняет навязывание ложных блоков и более надёжно обеспечивает целостность данных; - невысокая вычислительная и емкостная (по памяти) сложность реализации, позволяющая экономить ресурсы при контроле целостности больших массивов данных. Для повышения надёжности контроля целостности можно дополнительно использовать известные методы [1]: включение в блоки данных меток времени, номеров блоков (или оба приёма одновременно); использование ККЦ, зависящих от секретных параметров (ключей), что сильно усложняет подделку ККЦ. 1. Алгоритм генерации ККЦ Обозначим: n,m - натуральные числа; Vn - множество двоичных n-мерных векторов; Z2n -кольцо вычетов по модулю 2n; X - двоичное представление числа X из кольца Z264; Ш - сложение чисел в кольце Z264; ф - суммирование двоичных строк по модулю 2. Булева функция называется вполне перемешивающей [2], если она существенно зависит от каждой переменной. Отображение Vn ^ Vm называется вполне перемешивающим, если каждая его координатная функция вполне перемешивающая. Обозначим: s0(a0,... , а7),.. .,s7(a0,... , a7) - булевы координатные функции вполне перемешивающего преобразования s(a0,... ,а7) (s-бокса размера 8 х 8 бит); ^ - регистровое преобразование множества состояний аддитивного генератора длины 16 над множеством V64 с одной обратной связью f (X0,... , X15), где в ячейке регистра записан вычет X £ Z264 или, что равносильно, вектор X £ V64: ^(X0, . . . , X15) = (X1, . . . , X15, X0 Ш X5 Ш X10 Ш X15). Построим алгоритм генерации r-битового ККЦ для информационного /-битового блока, где / = 213 бит (1 кбайт), r = 128. Алгоритм реализует функцию ^(g*): V2i3 ^ V128, где g: V2i3 ^ V2i3 - преобразование регистрового типа множества состояний схемы из восьми идентичных аддитивных генераторов AG0,... , AG7, модифицированное с помощью преобразования s(a0,..., а7) (рис. 1). Алгоритм моделируется автономным автоматом Мили без выходов A = (V8,16,64, g), где g - функция переходов и V8,16,64 = {xi,j,q} -множество состояний автомата, пред-ставимое как трёхмерное множество целых неотрицательных чисел, множество координат которых биективно соответствует подмножеству P элементов трёхмерного пространства с целыми координатами, ограниченному параллелепипедом (рис.2): 0 ^ i < 8, 0 ^ j < 16, 0 ^ k < 64. Множество состояний автомата в такте t ^ 0 обозначим Vg i6 64 = }, или матрицей М^ = ^xiнад Z264, где X-j = (xfj 0,..., xfj 63) - состояние на t-м такте j-й ячейки AGj. Построим функцию переходов автомата, используя отображение z(s): V8 ^ V64, зависящее от преобразования s, реализуемого s-боксом. При t ^ 0 определим 8-битовую строку = (a(X0:i5,..., a(X7д5)), где a(xo,..., Х6з) = Хо Ф ... Ф Х63 - булева функция, определяющая чётность веса вектора (x0,... ,x63). Построим 64-битовую конкатенацию S ю восьми байтов: S

Ключевые слова

аддитивные генераторы, контроль целостности, матрично-графовый подход, перемешивающие свойства, регистры сдвига, additive generators, data integrity control, matrix-graph approach, mixing properties, shift registers

Авторы

ФИООрганизацияДополнительноE-mail
Фомичев Владимир МихайловичООО «Код Безопасности»; Финансовый университет при Правительстве РФ; НИЯУ МИФИ; ФИЦ ИУ РАНдоктор физико-математических наук, профессор, научный консультант; профессор; профессор; ведущий научный сотрудникfomichev.2016@yandex.ru
Коренева Алиса МихайловнаООО «Код Безопасности»кандидат физико-математических наук, начальник отделаa.koreneva@securitycode.ru
Набиев Тимур РуслановичМГТУ им. Н. Э. Баумана; ООО «Код Безопасности»студент; программистt.nabiev@securitycode.ru
Всего: 3

Ссылки

Будзко В. И., Мельников Д. А., Фомичёв В. М. Базовые требования к подсистемам обеспечения криптоключами в информационно-технологических системах высокой доступности // Системы высокой доступности. 2016. Т. 12. №3. С. 73-82.
Fomichev V. M. Matrix-graph approach for studying nonlinearity of transformations on vector space // VIII симп. «Современные тенденции в криптографии» CTCrypt 2019. https: //ctcrypt.ru/files/files/2019/materials/08_Fomichev.pdf
Fomichev V. M. and Koreneva A. M. Mixing properties of modified additive generators // J. Appl. Ind. Math. 2017. V. 11. P. 215-226.
Fomichev V. M., Avezova Ya. E., Koreneva A. M., and Kyazhin S. N. Primitivity and local primitivity of digraphs and nonnegative matrices // J. Appl. Ind. Math. 2018. V. 12. P. 453-469.
 Xарактеристики алгоритма контроля целостности данных на основе аддитивных генераторов и s-боксов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/19

Xарактеристики алгоритма контроля целостности данных на основе аддитивных генераторов и s-боксов | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/19