СПОСОБ МНОГОУРОВНЕВОГО КОНТРОЛЯ И ОБЕСПЕЧЕНИЯ ЦЕЛОСТНОСТИ ДАННЫХ

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

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

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

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

Известны способы контроля целостности данных за счет применения криптографических методов: ключевое и бесключевое хеширование, средства электронной подписи (Заявка на патент РФ №2012107193/08 публ. 10.10.2013; Заявка на патент РФ №2006116797/09 публ. 27.01.2008; Заявка на патент РФ №2007141753/09 публ. 10.09.2010; Заявка на патент РФ №2013149120/08 публ. 10.05.2015; Заявка на патент РФ №2004110622/09 публ. 10.10.2007; Заявка на патент РФ №2005113932/09 публ. 20.01.2007; Кнут, Д.Э. Искусство программирования для ЭВМ. Том 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)), для которых типичны две обобщенные схемы получения хэш-кодов: для каждого подблока в блоке данных и для целого блока данных.

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

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

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

Известны способы обеспечения целостности данных за счет применения различных видов резервирования (с использованием программно-аппаратной или программной реализации технологии RAID (Redundant Array of Independent Disks) (RAID-массивы), методы дублирования, методы избыточного кодирования) (Патент США №7392458 публ. 24.06.2008; Патент США №7437658 публ. 14.10.2008; Патент США №7600176 публ. 06.10.2009; Заявка на патент США №20090132851 публ. 21.05.2009; Заявка на патент США №20100229033 публ. 09.09.2010; Заявка на патент США №201101145677 публ. 16.06.2011; Заявка на патент США №20110167294 публ. 07.07.2011; Заявка на патент США №20110264949 публ. 27.10.2011; Уоррен, Г. Подсчет битов: алгоритмические трюки для программистов (Hacker's Delight) [Текст] / Г. Уоррен, мл. - М.: «Вильямс», 2007. - 512 с.; Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение [Текст] / Р. Морелос-Сарагоса; перевод с англ. В.Б. Афанасьев. - М.: Техносфера, 2006. - 320 с.; Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).

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

- высокая избыточность.

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе обеспечения целостности данных, заключающемся в том, что обнаружение и локализация возникающей ошибки в подблоках m₁, m₂, …, m_n блока данных М обеспечиваются посредством вычисления системы хэш-кодов, формируемой из хэш-кодов хэш-функции от совокупности подблоков данных, и ее сравнении с эталонной, в представленном же способе блок данных М для осуществления многоуровневого контроля и обеспечения его целостности представляется в виде подблоков фиксированной длины m₁, m₂, …, m_n, которые являются информационной группой n подблоков, к которой по правилам построения избыточных кодов добавляется контрольная группа r подблоков m_n+1, …, m_n+r, дополнительно вводимая для коррекции ошибки, при возникновении которой восстановление блока данных М осуществляется на нижнем уровне, где осуществляется обеспечение целостности данных посредством применения математического аппарата избыточных кодов, в свою очередь обнаружение ошибки, возникающей в условиях деструктивных воздействий злоумышленника и среды, выполняется на верхнем уровне, где осуществляется контроль целостности данных путем сравнения значений вычисленной и эталонной систем хэш-кодов, правила построения которых основаны на математическом аппарате линейной алгебры.

Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет представления блока данных М подблоками фиксированной длины m₁, m₂, …, m_n, к которым по правилам построения избыточных кодов добавляются контрольные подблоки m_n+1, …, m_n+r, что позволяет после обнаружения ошибки путем сравнения значений вычисленной и эталонной систем хэш-кодов, восстановить данные, целостность которых была нарушена в условиях деструктивных воздействий злоумышленника и среды.

Защита целостности блока данных М будет осуществляться за счет многоуровневого контроля целостности данных (на верхнем уровне путем сравнения значений вычисленной и эталонной систем хэш-кодов) и обеспечения целостности на нижнем уровне, что позволит в момент времени t в условиях деструктивных воздействий злоумышленника и среды восстановить данные, целостность которых была нарушена. Восстановление данных будет осуществляться по известным правилам, применяемым при использовании избыточных кодов (Блейхут, Р. Теория и практика кодов, контролирующих ошибки [Текст] / Р. Блейхут; перевод с англ. - М.: Мир, 1986. - 576 с.). Новым является то, что в предлагаемом способе блок данных М представляется в виде подблоков фиксированной длины m₁, m₂, …, m_n, к которым по правилам построения избыточных кодов добавляются контрольные подблоки m_n+1, …, m_n+r, что позволяет восстановить данные в случае нарушения их целостности. Новым является то, что избыточному коду, по правилам которого строится блок данных из информационных и контрольных подблоков, достаточно обладать корректирующими способностями, необходимыми для обнаружения, а не исправления ошибки.

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

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

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

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

- восстановления данных на основе математического аппарата избыточных кодов.

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

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

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

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

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

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

фиг. 2 - схема представления кодового слова (n+r, n)-кода;

фиг. 3 - схема, поясняющая процедуру построения кодового слова (n+r, n)-кода на нижнем уровне;

фиг. 4 - общая схема, поясняющая способ многоуровневого контроля и обеспечения целостности данных;

фиг. 5 - схема, поясняющая способ многоуровневого контроля и обеспечения целостности данных при использовании на нижнем уровне правил построения кода с проверкой на четность и на верхнем уровне - систему линейно независимых векторов для построения (7,4)-кода Хемминга.

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

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

Полученное кодовое слово (n+r, n)-кода представлено на фиг. 2.

Добавление дополнительных контрольных символов выполняется по правилам построения избыточных кодов в зависимости от требуемых корректирующих характеристик получаемого кода (фиг. 3). Полученный код в последующем будет использоваться для восстановления на нижнем уровне защищаемых данных (n подблоков блока данных М) в случае нарушения их целостности. Правила построения (n+r, n)-кодов, их параметры: длина блока n+r, длина информационной части блока n и минимальное кодовое расстояние d_min широко представлены в известных источниках (Блейхут, Р. Теория и практика кодов, контролирующих ошибки [Текст] / Р. Блейхут; перевод с англ. - М.: Мир, 1986. - 576 с.; Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).

Процедуре восстановления данных предшествует контроль их целостности, который осуществляется на верхнем уровне посредством криптографических методов, где к n информационным и r контрольным подблокам блока данных М, применяется хэш-функция h, удовлетворяющая свойствам, определенным в национальном стандарте (ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования. Стандартинформ, 2013. - 19 с.).

На верхнем уровне для контроля целостности данных формируется система хэш-кодов, правила построения которой аналогичны правилам построения линейных избыточных кодов, в частности, кодов Хемминга. Данная система известна как линейная система хэш-кодов (ЛСХК), под которой понимается множество хэш-кодов, полученных с помощью стандартной процедуры реализации хэш-функции от совокупности подблоков блока данных в порядке, определенном специальной процедурой выбора подблоков, основанной на математическом аппарате линейной алгебры, что позволяет сократить количество вычисляемых хэш-кодов по сравнению с классическими схемами хэширования.

ЛСХК основана на математическом аппарате теории систем векторов и линейных векторных пространств, где данные, подлежащие защите, представлены двоичными векторами , их множество рассматривается как система линейно независимых векторов:

только при нулевом наборе коэффициентов: x₁, x₂, …, x_c; x_q∈{0,1}, где q=1, 2, …, с.

Данная система образует базис:

Множество подблоков блока данных, подлежащих защите, и их хэш-кодов , в свою очередь, также можно рассматривать как систему линейно независимых векторов, где базисом для них будет: Е₀, E₁, …, E_k.

Множество всех возможных схем хэширования подблоков блока данных представляется в виде двоичной матрицы, составленной из коэффициентов базиса:

где каждая строка соответствует схеме хэширования и n≤k. При этом строки матрицы обладают свойствами: являются различными и линейно независимыми векторами; расстояние между векторами (по Хэммингу) d_min≥2; каждый вектор имеет вес (в смысле Хэмминга) ω≥d_min; нулевой вектор не входит в матрицу.

Аналогичными свойствами обладает порождающая матрица в теории линейных кодов (Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.), что обеспечивает возможность использования правил построения линейных кодов для построения ЛСХК.

Хэширование исходного блока данных представляется в виде следующего выражения:

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

Тогда получение защищенного блока данных с помощью хэширования представляется в виде следующего выражения:

где или

где символ означает специальную многомерную некоммутативную операцию хэширования подблоков , отмеченных единичным символом матрицы G; если же a_k=0, то ; - информационный вектор (блок данных).

Для контроля целостности данных (обнаружения ошибки) в теории линейных кодов используют понятие синдром. Синдром S - это матрица-строка с L элементами (u=1, 2, …, L) по одному для каждого проверочного символа.

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

где обозначает вычисленный хэш-код при запросе на использование данных, - эталонный хэш-код, υ=i+k+1, …, i+g; «1» означает, что нарушения целостности проверяемого подблока блока данных нет, «0» - есть.

Схема применения хэш-функции к подблокам m₁, m₂, …, m_n+r защищенного блока данных, основанная на ЛСХК, предназначена для криптографического контроля целостности данных и выполняется на верхнем уровне за счет сравнения вычисленной и эталонной систем хэш-кодов s_n+r+1, …, s_n+z (фиг. 4).

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

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

Пример

Рассмотрим случай, где на нижнем уровне используется простой код с проверкой на четность, а на верхнем уровне - система линейно независимых векторов для построения (7,4)-кода Хемминга.

Для этого используем систему линейно независимых векторов, которая в теории линейных кодов используется для построения (7,4)-кода Хемминга:

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

Для контроля целостности защищенного блока данных, полученного путем хэширования в соответствии с (1):

вычисляется синдром , соответствующий предикату (2):

где s_y - эталонный хэш-код, вычисленный ранее, а - хэш-код, вычисленный от данных, подлежащих проверке, y=1, 2, 3.

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

После контроля целостности данных (обнаружения и локализации подблока блока данных с нарушением целостности) выполняется процедура восстановления.

По условию на нижнем уровне используется код с проверкой на четность, в соответствии с правилами построения которого, где к n информационным символам дописывается n+1 контрольный символ, так чтобы полное число единиц в кодовом слове было четным (Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.):

где означает операцию сложения по модулю 2, поэтому для n=3 получим:

и так далее. Минимальное расстояние выбранного кода d_min=2, и, следовательно, никакие ошибки не могут быть исправлены. Как известно, простой код с проверкой на четность используется для обнаружения, но не исправления ошибки. Однако, ввиду оригинальности схемы построения, разработанный способ, в котором агрегированы известные решения, позволяет после локализации подблока блока данных с нарушением целостности посредством криптографических методов восстановить его

посредством кода, обладающего корректирующими способностями, лишь для обнаружения, а не исправления ошибки.