СПОСОБ КОНТРОЛЯ ЦЕЛОСТНОСТИ ДАННЫХ НА ОСНОВЕ КРИПТОГРАФИЧЕСКОЙ ПИРАМИДЫ ПАСКАЛЯ
METHOD FOR MONITORING DATA INTEGRITY BASED ON PASCAL'S CRYPTOGRAPHIC PYRAMID

Область техники, к которой относится изобретение
Предлагаемое изобретение относится к информационным технологиям и может быть использовано для контроля целостности информации в системах хранения данных на основе применения криптографических хэш-функций к защищаемым блокам данных в условиях деструктивных воздействий злоумышленника и среды.
Уровень техники
а) Описание аналогов
Известны способы контроля целостности данных за счет применения криптографических методов: ключевое и бесключевое хэширование, средства электронной подписи (Кнут, Д.Э. Искусство программирования для ЭВМ. Том 3 сортировка и поиск [Текст] / Д.Э. Кнут.- М.: «Мир», 1978. - 824 с.; Menezes, A.J. Handbook of Applied Cryptography Текст] / A.J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. - M.: CRC Press, Inc., 1996. - 816 c.; Biham, E. A framework for iterative hash functions. - HAIFA [Текст] / E. Biham, O. Dunkelman. - M.: HAIFA, ePrint Archive, Report 2007/278. - 20 с.; To же [Электронный ресурс]. - Режим доступа: eprint.iacr.org/2007/278.pdf (July, 2007); Wang, X. How to break MD5 and Other Hash Function [Текст] / X.Wang, H.Yu. - M.: EUROCRYPT 2005, LNCS 3494, Springer-Verlag 2005. - C. 19-35; Bellare, M. New Proofs for NMAC and HMAC: Security without Collision-Resistance [Текст] / M. Bellare. - M.: CRYPTO 2006, ePrint Archive, Report 2006/043. - 31 с.; To же [Электронный ресурс]. - Режим доступа: eprint.iacr.org/2006/043.pdf (2006); 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; Samoylenko, D. Protection of information from imitation on the basis of crypt-code structures / D. Samoylenko, M. Eremeev, O. Finko, S. Dichenko // Advances in Intelligent Systems and Computing. 2019. №889. P. 317-331.; Диченко, С.А. Концептуальная модель обеспечения целостности информации в современных системах хранения данных. Информатика: проблемы, методология, технологии. Сборник материалов XIX международной научно-методической конференции. Под ред. Д.Н. Борисова. Воронеж. - 2019. С. 697-701; Диченко, С.А. Контроль и обеспечение целостности информации в системах хранения данных. Наукоемкие технологии в космических исследованиях Земли. - 2019. - Т. И. - №1. - С. 49-57; Диченко, С.А. Гибридный крипто-кодовый метод контроля и восстановления целостности данных для защищенных информационно-аналитических систем / С. Диченко, О. Финько // Вопросы кибербезопасности. - 2019. - №6(34). - С. 17-36), для которых типичны две обобщенные схемы получения хэш-кодов: для каждого подблока в блоке данных и для целого блока данных.
Недостатками данных способов являются:
- высокая избыточность при контроле целостности последовательности подблоков блока данных небольшой размерности (при хэшировании каждого подблока в блоке данных);
- отсутствие возможности локализации искаженных подблоков в блоке данных (при хэшировании целого блока данных);
- отсутствие возможности осуществления контроля целостности эталонных хэш-кодов, предназначенных для осуществления контроля целостности защищаемых данных.
Известен способ обеспечения необходимого уровня защищенности (целостности) данных на основе множества хэш-кодов, полученных с помощью стандартной процедуры реализации хэш-функции от совокупности данных в порядке, определенном специальной процедурой выбора подблока, основанной на математическом аппарате линейной алгебры 'линейных систем хэш-кодов) (Финько, О.А. Обеспечение целостности данных в автоматизированных системах на основе линейных систем хэш-кодов / О.А. Финько, С.В. Савин // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. - 2015. - №114. - С. 796-811), где контроль целостности данных (обнаружение ошибки) по аналогии с линейными кодами осуществляется за счет вычисления синдрома, при проверке которого можно сделать вывод о нарушении целостности данных (наличии ошибки).
Недостатками известного способов являются отсутствие возможности осуществления контроля целостности эталонных хэш-кодов, предназначенных для осуществления контроля целостности защищаемых данных, а также обнаружения и локализации ошибок, приводящих к нарушению целостности нескольких подблоков данных.
б) Описание ближайшего аналога (прототипа)
Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ контроля целостности данных на основе криптографического треугольника Паскаля (Способ контроля целостности данных на основе криптографического треугольника Паскаля / С.А. Диченко, Д.В. Самойленко, О.А. Финько // Патент на изобретение RU 2730365, 21.08.2020. Заявка №2019143386 от 19.12.2019), где контроль целостности данных осуществляется путем сравнения значений хэш-кодов, вычисленных при запросе на использование защищаемых данных, расположенных на боковых ребрах треугольника, со значениями эталонных хэш-кодов, вычисленных ранее (фиг. 1). При этом благодаря механизму циклического вычисления хэш-кодов, находящихся на вершинах треугольника, осуществляется контроль целостности самих эталонных хэш-кодов.
Недостатком известного способа является отсутствие возможности обнаружения и локализации ошибок, приводящих к нарушению целостности нескольких подблоков данных, в условиях деструктивных воздействий злоумышленника и среды.
Раскрытие изобретения
а) Технический результат, на достижение которого направлено изобретение
Целью настоящего изобретения является разработка способа контроля целостности данных на основе применения криптографических хэш-функций к защищаемым блокам данных с возможностью обнаружения и локализации ошибок, приводящих к нарушению целостности нескольких подблоков данных, в условиях деструктивных воздействий злоумышленника и среды.
б) Совокупность существенных признаков
1
2
k
100
k00
010
0k0
001
00k
000
k+1,0,0
0,k+1,0
0,0,k+1
k10
1k0
0k1
01k
10k
k01
100
k00
010
0k0
001
00k
Поставленная цель достигается тем, что в известном способе контроля целостности данных, заключающемся в том, что обнаружение и локализация возникающей ошибки в подблоках m, m,…, m блока данных М, расположенных на боковых ребрах треугольника, обеспечиваются посредством вычисления группы хэш-кодов по правилам построения треугольника Паскаля и их сравнения с эталонными, в представленном же способе блок данных М для осуществления контроля целостности представляется в виде 3k; подблоков фиксированной длины М,…, M, М,…, M, M,…, M, к которым применяется хэш-функция h, схема хэширования при этом имеет форму пирамиды, в которой подблоки блока данных М, подлежащие защите, размещены на боковых ребрах пирамиды, исходящих из основной вершины, в которой расположен хэш-код H, предназначенный для осуществления контроля целостности хэш-кодов H, H, H, которые, в свою очередь, используются для контроля целостности хэш-кодов H,…, H, H,…, H, H,…, H, расположенных на ребрах основания пирамиды, которые вместе с хэш-кодами, расположенными в основании пирамиды, будут являться эталонными и предназначенными для контроля целостности подблоков М,…, M, М,…, M, M,…, M путем сравнения значений вычисленных при запросе на использование защищаемых данных хэш-кодов со значениями эталонных хэш-кодов, вычисленных ранее, внутри полученной пирамиды расположены промежуточные результаты преобразований.
100
k00
010
0k0
001
00k
Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет представления блока данных М подблоками фиксированной длины М,…, M, М,…, M, M,…, M, к которым хэш-функция применяется по правилам построения пирамиды Паскаля (Гарднер, М. Неисчерпаемое очарование треугольника Паскаля // Математические новеллы. - М.: Мир, 1974. - 456 с.; Gardner, Martin. (1966, December) The multiple charms of Pascal's triangle, Scientific American. - pp. 128-132; Dewdney, A.K. (1985, April) Five easy pieces for a do loop and random-number generator [Computer Recreations]. Scientific American. - p. 22; Mueller, Stephen. (1969, Spring). Recursions associated with Pascal's pyramid. Pi Mu Epsilon Journal, (Vol 4, 10). - pp. 417-422; Staib, John &; Staib, Larry. (1978, September). The Pascal Pyramid. Mathematics Teacher. - pp. 505-560), что позволяет обнаружить и локализовать ошибки, приводящие к нарушению целостности нескольких подблоков данных, в условиях деструктивных воздействий злоумышленника и среды.
100
k00
010
0k0
001
00k
Контроль целостности блока данных М будет осуществляться путем сравнения значений хэш-кодов, вычисленных при запросе на использование защищаемых данных, и эталонных хэш-кодов, что позволит в момент времени t в условиях деструктивных воздействий злоумышленника и среды определить данные, целостность которых была нарушена. Новым является то, что в предлагаемом способе блок данных М представляется в виде 3k; подблоков фиксированной длины М,…,M,М,…, M, M,…, M, к которым хэш-функция применяется по правилам построения пирамиды Паскаля. Новым является то, что применение хэш-функции по правилам построения пирамиды Паскаля позволяет осуществить контроль целостности защищаемых данных при возникновении ошибок, приводящих к нарушению целостности нескольких подблоков данных, расположенных на различных боковых ребрах пирамиды.
в) Причинно-следственная связь между признаками и техническим результатом
Благодаря новой совокупности существенных признаков в способе реализована возможность:
- обнаружения однократной ошибки, возникающей в защищаемых данных, в условиях деструктивных воздействий злоумышленника и среды;
- локализации обнаруженной ошибки;
- контроля целостности эталонных хэш-кодов, предназначенных для осуществления контроля целостности защищаемых данных;
- обнаружения и локализации ошибок, приводящих к нарушению целостности нескольких подблоков данных, подлежащих защите.
Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность отличительных существенных признаков, обуславливающих тот же технический результат, который достигнут в заявленном способе. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Краткое описание чертежей
Заявленный способ поясняется чертежами, на которых показано:
фиг. 1 - общая схема применения хэш-функции, основанная на правилах построения треугольника Паскаля;
фиг. 2 - схема представления 3k подблоков блока данных М;
фиг. 3 - общая схема применения хэш-функции, основанная на правилах построения пирамиды Паскаля;
фиг. 4 - схема применения хэш-функции, основанная на правилах построения пирамиды Паскаля (при k=3);
фиг. 5 - сеть хэширования для схемы применения хэш-функции, основанной на правилах построения пирамиды Паскаля (при k=3).
Осуществление изобретения
Блок данных М, подлежащий защите, для осуществления контроля целостности представляется в виде 3k подблоков фиксированной длины:
ijr
где «||» - операция конкатенации (объединения) подблоков M (i,j,r=1,…, k), которые обозначаются с помощью переменных х, у, z, по аналогии с осями трехмерной декартовой системы координат (фиг. 2).
ijr
Схема применения хэш-функции к подблокам блока данных М имеет форму пирамиды (фиг. 3), в которой подблоки M размещены на боковых ребрах пирамиды, образованных осями: х, у, z, исходящих из основной вершины.
000
k+1,0,0
0,k+1,0
0,0,k+1
В основной вершине пирамиды расположен хэш-код H, предназначенный для осуществления контроля целостности хэш-кодов H, H, H, находящихся в вершинах основания пирамиды, посредством использования хэш-функции h в соответствии со следующим выражением:
которые, в свою очередь, используются для контроля целостности хэш-кодов, расположенных на ребрах основания пирамиды:
k+1,0,0
0,k+1,0
0,0,k+1
k10
1k0
0k1
01k
10k
k01
Хэш-коды H, H, H и H,…, H, H,…, H, H,…, H, расположенные в вершинах и на ребрах основания пирамиды соответственно, а также в самом основании пирамиды будут являться эталонными и использоваться для осуществления контроля целостности подблоков данных, подлежащих защите.
Внутри полученной пирамиды расположены промежуточные результаты преобразований.
ijr
Контроль целостности обеспечивается тем, что каждому подблоку данных M, подлежащему защите, ставится в соответствие уникальная по составу группа эталонных хэш-кодов, вычисленных по правилам построения пирамиды Паскаля.
Пример 1. Рассмотрим схему применения хэш-функции (фиг. 4), основанную на правилах построения пирамиды Паскаля (при k=3), для которой построим сеть хэширования, представленную на фиг. 5.
ijr
Из полученной сети хэширования (фиг. 5) для каждого подблока данных M, подлежащего защите, получим уникальные по составу группы эталонных хэш-кодов, используемые при обнаружении и локализации подблока данных с нарушением целостности.
Под нарушением целостности одного подблока данных будем понимать появление однократной ошибки, соответственно q-кратная ошибка определяется как нарушение целостности q подблоков данных.
Обнаружение подблока данных с нарушением целостности выполняется путем сравнения значений предварительно вычисленных от него эталонных хэш-кодов и хэш-кодов, вычисленных при запросе на его использование. В случае несоответствия сравниваемых значений хэш-кодов делается вывод о возникновении ошибки и определяется ее синдром.
Под синдромом ошибки будем понимать двоичное число, полученное при написании символа «0» для каждой выполненной проверки на соответствие значений вычисленного и эталонного хэш-кода и символа «1» при несоответствии сравниваемых значений.
ijr
Для демонстрации наличия однократных ошибок (подблоков данных с нарушением целостности [M]) составим таблицы их синдромов, где место ошибки определяется наличием нескольких символов «1» в соответствующих столбцах и строках таблиц.
Полученные уникальные по составу группы эталонных хэш-кодов:
100
400
310
301
220
211
202
130
121
112
103
- для M: H, H, H, H, H, H, H, H, H, H;
200
400
310
301
220
211
202
- для М: H, H, H, H, H, H;
300
400
310
301
- для М: H, H, H;
010
040
130
031
220
121
022
310
211
112
013
- для М: H, H, H, H, H, H, H, H, H, H;
020
040
130
031
220
121
022
- для М: H, H, H, H, H, H;
030
040
130
031
- для М: H, H, H;
001
004
013
103
022
112
202
031
121
211
301
- для М: H, H, H, H, H, H, H, H, H, H;
002
004
013
103
022
112
202
- для М: H, H, H, H, H, H;
003
004
013
103
- для М: H, H, H
показывают возможность осуществления контроля целостности двукратных ошибок, приводящих к нарушению целостности любых двух подблоков данных, расположенных на различных боковых ребрах пирамиды.
400
310
301
220
211
202
130
121
112
103
040
031
Пример 2. При сравнении значений предварительно вычисленных эталонных хэш-кодов и хэш-кодов, вычисленных при запросе на использование данных, выявлено несоответствие сравниваемых значений у следующих хэш-кодов: H, H, H, H, H, H, H, H, H, H, H, H.
На основе таблиц синдромов ошибки определим подблоки данных с нарушением целостности.
100
030
Из полученной таблицы видно, что группе представленных хэш-кодов соответствуют подблоки данных M и М. Делается вывод о возникновении ошибки, приводящей к нарушению целостности двух подблоков данных, подлежащих защите.
Таким образом, применение хэш-функции к защищаемым данным по правилам построения пирамиды Паскаля позволяет осуществить контроль целостности защищаемых
данных при возникновении ошибки, приводящей к нарушению целостности любых двух подблоков данных, расположенных на различных боковых ребрах пирамиды.