СПОСОБ КОНТРОЛЯ ЦЕЛОСТНОСТИ ДАННЫХ НА ОСНОВЕ ПРАВИЛ ПОСТРОЕНИЯ ГЕОМЕТРИЧЕСКИХ КОДОВ Российский патент 2021 года по МПК G06F11/08 G06F12/16 

Область техники, к которой относится изобретение

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

Уровень техники

а) Описание аналогов

Известны способы контроля целостности данных за счет применения криптографических методов: ключевое и бесключевое хэширование, средства электронной подписи (Патент на изобретение RUS №26207030 07.12.2015; Патент на изобретение RUS №2669144 28.11.2017; Патент на изобретение RUS №2680033 22.05.2017; Патент на изобретение RUS №2680350 02.05.2017; Патент на изобретение RUS №2680739 28.11.2017; Патент на изобретение RUS №2686024 25.04.2018; Патент на изобретение RUS №2696425 22.05.2018; Кнут, Д.Э. Искусство программирования для ЭВМ. Том 3 сортировка и поиск [Текст] / Д.Э. Кнут. - М.: «Мир», 1978. - 824 с.; Dichenko, S. Two-dimensional control and assurance of data integrity in information systems based on residue number system codes and cryptographic hash functions / S. Dichenko, O. Finko // Integrating Research Agendas and Devising Joint Challenges International Multidisciplinary Symposium ICT Research in Russian Federation and Europe. 2018. P. 139-146; Диченко, С.А. Контроль и обеспечение целостности информации в системах хранения данных. Наукоемкие технологии в космических исследованиях Земли. - 2019. - Т. 11. - №1. - С. 49-57; Диченко, С.А. Гибридный крипто-кодовый метод контроля и восстановления целостности данных для защищенных информационно-аналитических систем / С. Диченко, О. Финько // Вопросы кибербезопасности. - 2019. - №6(34). - С. 17-36), для которых типичны две обобщенные схемы получения хэш-кодов: для каждого подблока в блоке данных и для целого блока данных.

Недостатками данных способов являются:

- высокая избыточность при контроле целостности последовательности подблоков блока данных небольшой размерности (при хэшировании каждого подблока в блоке данных);

- отсутствие возможности локализации искаженных подблоков в блоке данных (при хэшировании целого блока данных);

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

б) Описание ближайшего аналога (прототипа)

Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ обеспечения необходимого уровня защищенности (целостности) данных на основе множества хэш-кодов (фиг. 1), полученных с помощью стандартной процедуры реализации хэш-функции от совокупности данных в порядке, определенном специальной процедурой выбора подблока, основанной на математическом аппарате линейной алгебры (линейных систем хэш-кодов) (Финько, О.А. Обеспечение целостности данных в автоматизированных системах на основе линейных систем хэш-кодов / О.А. Финько, С.В. Савин // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. - 2015. - №114. - С. 796-811), где контроль целостности данных обнаружение ошибки) по аналогии с линейными кодами осуществляется за счет вычисления синдрома, при проверке которого можно сделать вывод о нарушении целостности данных (наличии ошибки).

Недостатком известного способа является отсутствие возможности повышения обнаруживающей способности при контроле целостности данных в условиях ограничений на допустимые затраты ресурса.

Раскрытие изобретения

а) Технический результат, на достижение которого направлено изобретение

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

б) Совокупность существенных признаков

Поставленная цель достигается тем, что в известном способе обеспечения целостности данных, заключающемся в том, что обнаружение и локализация возникающей ошибки в подблоках m₁, m₂, …, m_k блока данных М обеспечиваются посредством вычисления системы хэш-кодов, формируемой из хэш-кодов хэш-функции от совокупности подблоков данных, и ее сравнении с эталонной, в представленном же способе блок данных М для осуществления контроля целостности представляется в виде трехмерной матрицы k-го порядка W=[M_ijr], к которому применяется хэш-функция по правилам построения геометрических кодов, при которых блоки данных, подлежащие защите, размещены в трехмерном кубе и заполняют k³ блоков, к каждому блоку данных, подлежащему защите, по трем осям добавляются блоки, содержащие вычисленные от них эталонные хэш-коды H_ijr хэш-функции h(M_ijr), которые размещаются на трех внешних сечениях куба данных и заполняют 3k² блоков, при этом контроль целостности блока данных M_ijr осуществляется путем сравнения значений вычисленных при запросе на использование данных, подлежащих защите, хэш-кодов и эталонных хэш-кодов H_ijr, вычисленных ранее.

Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет представления блока данных М в виде трехмерной матрицы k-го порядка W=[M_ijr], к которому хэш-функция применяется по правилам построения геометрических кодов (Hamming, R. Coding and Information Theory. Prentice-Hall, 2008. - 259 p.), что позволяет повысить обнаруживающую способность при контроле целостности данных в условиях ограничений на допустимые затраты ресурса.

Контроль целостности блока данных М будет осуществляться путем сравнения значений вычисленных при запросе на использование данных, подлежащих защите, хэш-кодов и эталонных хэш-кодов, что позволит в момент времени t в условиях ограничений на допустимые затраты ресурса определить большее количество данных, целостность которых была нарушена. Новым является то, что в предлагаемом способе блок данных М представляется в виде трехмерной матрицы k-го порядка W=[M_ijr], к которому хэш-функция применяется по правилам построения геометрических кодов. Новым является то, что применение хэш-функции по правилам построения геометрических кодов позволяет повысить обнаруживающую способность при контроле целостности данных в условиях ограничений на допустимые затраты ресурса, за счет большего количества связей между блоками данных, подлежащих защите, и хэш-кодов, размещенных определенным образом в трехмерном кубе данных.

в) Причинно-следственная связь между признаками и техническим результатом

Благодаря новой совокупности существенных признаков в способе реализована возможность:

- обнаружения ошибки, возникающей в защищаемых данных;

- локализации обнаруженной ошибки;

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

Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»

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

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

Краткое описание чертежей

Заявленный способ поясняется чертежами, на которых показано:

фиг. 1 - общая схема формирования линейной системы хэш-кодов;

фиг. 2 - принцип организации трехмерного куба данных k-го порядка;

фиг. 3 - принцип организации трехмерного куба данных (при k=2);

фиг. 4 - сеть хэширования при условии возникновения однократной ошибки;

фиг. 5 - зависимости вероятностей обнаруживаемых и локализуемых данных;

фиг. 6 - сеть хэширования для двух сочетании блоков данных с одинаковыми синдромами ошибки;

фиг. 7 - зависимость изменения вероятности Р_обн от величины k.

Осуществление изобретения

Блоки данных М, хранящиеся в системах хранения в виде упорядоченных многомерных массивов (гиперкубов), в соответствии с теорией многомерных матриц (Соколов, Н.П. Введение в теорию многомерных матриц. - М.: Просвещение, 2012. - 175 с.) могут быть представлены р-мерной матрицей k-го порядка:

где i_a=1, 2, …, k_a; а=1, 2, …, р.

При рассмотрении многомерного куба данных в качестве системы координат с осями, к примеру, для трехмерного куба (фиг. 2): x, y, z, по которым откладываются блоки данных, получим кубическую матрицу k-го порядка которая с помощью сечений ориентации (z) может быть представлена в следующем виде:

где стрелки указывают направление, в котором возрастают соответствующие индексы.

Для осуществления контроля целостности данных разместим блоки данных, подлежащие защите, в трехмерном кубе определенным образом (от 0 до (k - 1) блока вдоль каждой оси), запонив при этом k³ блоков куба данных.

Получим кубическую матрицу k-го порядка которая с помощью сечений ориентации (z) может быть представлена в следующем виде:

где «0» обозначает свободный для записи блок куба данных.

При таком расположении из (k+1)³ общего количества блоков, содержащихся в кубе, k³ блоков будут предназначены для хранения данных, подлежащих защите.

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

Под хэш-функцией h понимается функция, отображающая блоки бит М ∈ (0, 1)^* в строки бит фиксированной длины Н ∈ (0, 1)^q: h(M) = Н, где «(•)^*» - произвольный размер блока бит, «(•)^q» - фиксированный размер блока бит, q ∈ N, и удовлетворяющая следующим свойствам:

- по вычисленному значению хэш-функции Н ∈ (0, 1)^q сложно вычислить исходные данные М ∈ (0, 1)^*, отображаемые в это значение;

- для заданных исходных данных М₁ ∈ (0, 1)^* сложно вычислить другие исходные данные М₂ ∈ (0, 1)^*, отображаемые в то же значение хэш-функции, то есть h(M₁) = h(M₂), где М₁ ≠ М₂;

- сложно вычислить какую-нибудь пару исходных данных (М₁, М₂), где М₁ ≠ М₂, M_t ∈ (0, 1)^*, t = 1, 2, отображаемых в одно и то же значение хэш-функции, то есть h(M₁) = h(M₂).

Под хэш-кодом понимается строка бит Н ∈ (0, 1)^q, являющаяся выходным результатом хэш-функции h.

Строки бит М ∈ (0, 1)^*, которые хэш-функция h отображает в хэш-код Н ∈ (0, 1)^q, будут называться блоком данных.

В соответствии с правилами построения геометрических (кубических) кодов, вычислим и разместим полученные хэш-коды H_ijr в кубе данных, при этом кубическая матрица k-го порядка W с помощью сечений ориентации (z) может быть представлена в следующем виде:

Вычисленные хэш-коды H_ijr хэш-функции h(M_ijr) (или h_k(M_ijr), k - секретный ключ) от блоков данных M_ijr будут являться эталонными.

Трехмерный куб данных, содержащий (k+1)³ блоков, будет состоять из:

- k³ блоков данных M_ijr, подлежащих контролю целостности (i, j, r=0, …, k - 1);

- 3k² блоков, предназначенных для записи вычисленных эталонных хэш-кодов H_ijr (i, j, r=0, …, k);

- (3k+1) оставшихся блоков.

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

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

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

Под синдромом будем понимать двоичное число, полученное при написании символа «0» для каждой выполненной проверки на соответствие значений вычисленного и эталонного хэш-кода и символа «1» для каждой из невыполненных проверок.

Для контроля целостности данных построим трехмерный куб данных (фиг. 3), описываемый кубической матрицей посредством сечений ориентации (х):

где блоки данных M_ijr, подлежащие защите, и вычисленные от них эталонные хэш-коды H_ijr представлены двоичными векторами.

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

Пример 1. Хэш-коды Н₀₀₂, H₀₁₂, Н₀₂₀, Н₀₂₁, размещенные в блоках нижнего сечения куба данных (фиг. 3) ориентации (х), вычисляются в соответствии со следующими выражениями:

Для определения синдрома возможной ошибки построим для куба данных (фиг. 3) сеть хэширования. На фиг. 4 представлена сеть хэширования при условии возникновении однократной ошибки, на основе которой составим таблицу синдромов ошибки, в которой место

ошибки (блок данных с нарушением целостности [M_ijr]) определяется наличием нескольких символов «1» в соответствующем столбце. Наличие символа «1» обозначает, что при контроле целостности данных значения вычисленного при запросе на использование данных и эталонного хэш-кодов не соответствуют друг другу.

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

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

Пример 2. Наличие свободных 432 Кбайт ресурса СХД позволяет хранить 675 хэш-кодов (при размере 1 хэш-кода равном 512 бит), которые, в свою очередь, при применении разработанного способа обеспечивают обнаружение и локализацию 100% всех блоков данных с нарушенной целостностью, размещенных в трехмерном кубе данных (при увличении его размера от k=2 до k=15).

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

Зависимости вероятностей Р_обн обнаруживаемых и локализуемых блоков данных с нарушением целостности представлены на графике (фиг. 5), где вероятность P_обн.1 - при применении разработанного способа, Р _обн.1 - при применении прототипа.

К тому же, разработанный способ по сравнению с прототипом позволяет повысить вероятность обнаружения и локализации q-кратных ошибок без увеличения для этого количества вычисляемых хэш-кодов (при возникновении q-кратной ошибки выполняется обнаружение и локализация всех 1-, 2-, 3-кратных ошибок, а также до 98,6% всех 4-кратных ошибок).

В частности, при размере куба данных (k=2) из всех 70 возможных различных сочетаний по четыре блока данных обнаруживаются и локализуются практически все ошибки (≈ 98,6%) за исключением одной (≈ 1,4%), возникающей в одном из двух представленных сочетаний блоков данных:

- М₀₀₁, М₀₁₀, М₁₀₀, М₁₁₁;

- М₀₀₀, М₀₁₁, М₁₀₁, М₁₁₀.

Для рассматриваемых сочетаний блоков данных построим сеть хэширования (фиг. 6).

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

При размере куба данных (k=3) уже существует 17550 различных сочетаний по четыре блока данных. При этом обнаруживаются и локализуются практически все ошибки (≈ 99,85%), за исключением 27 (≈ 0,15%), которые не обнаруживаются в результате совпадения синдромов ошибки у 27 различных пар сочетаний блоков данных.

При последующем увеличении величины к количество всех обнаруживаемых и локализуемых 4-кратных ошибок стремится к 100%.

Зависимость изменения вероятности Р_обн обнаруживаемых и локализуемых 4-кратных ошибок при увеличении блоков данных, подлежащих защите (величины k), представлена на графике (фиг. 7).

Таким образом, применение разработанного способа позволяет повысить обнаруживающую способность средств контроля целостности данных, а также обнаруживать и локализовывать все 1-, 2-, 3-кратные ошибки, а также до ≈ 98,6% всех 4-кратных ошибок без

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

Изобретение относится к информационным технологиям и может быть использовано для контроля целостности данных в системах хранения на основе применения криптографических хэш-функций к защищаемым блокам данных в условиях ограничений на допустимые затраты ресурса. Технический результат заключается в повышении обнаруживающей способности в условиях ограничений на допустимые затраты ресурса. Поставленная цель достигается за счет представления блока данных М в виде трехмерной матрицы k-го порядка W=[M_ijr], к которому хэш-функция применяется по правилам построения геометрических кодов, что позволяет повысить обнаруживающую способность при контроле целостности данных в условиях ограничений на допустимые затраты ресурса, за счет большего количества связей между блоками данных, подлежащих защите, и хэш-кодов, размещенных определенным образом в трехмерном кубе данных. 7 ил.

Способ контроля целостности данных на основе правил построения геометрических кодов, заключающийся в том, что обнаружение и локализация возникающей ошибки в подблоках m₁, m₂, …, m_k блока данных М обеспечиваются посредством вычисления системы хэш-кодов, формируемой из хэш-кодов хэш-функции от совокупности подблоков данных, и ее сравнения с эталонной, отличающийся тем, что блок данных М для осуществления контроля целостности представляется в виде трехмерной матрицы k-го порядка W=[M_ijr], к которому применяется хэш-функция по правилам построения геометрических кодов, при которых блоки данных, подлежащие защите, размещены в трехмерном кубе и заполняют k³ блоков, к каждому блоку данных, подлежащему защите, по трем осям добавляются блоки, содержащие вычисленные от них эталонные хэш-коды H_ijr хэш-функции h(M_ijr), которые размещаются на трех внешних сечениях куба данных и заполняют 3k² блоков, при этом контроль целостности блока данных M_ijr осуществляется путем сравнения значений вычисленных при запросе на использование данных, подлежащих защите, хэш-кодов и эталонных хэш-кодов H_ijr, вычисленных ранее.