СПОСОБ ВОССТАНОВЛЕНИЯ ДАННЫХ С ПОДТВЕРЖДЕННОЙ ЦЕЛОСТНОСТЬЮ
METHOD FOR RESTORING DATA WITH CONFIRMED INTEGRITY

Область техники, к которой относится изобретение
Предлагаемое изобретение относится к информационным технологиям и может быть использовано для контроля и восстановления целостности данных в системах хранения в условиях деструктивных воздействий злоумышленника и среды.
Уровень техники
В настоящее время перед пользователями различных информационных систем стоят задачи по защите данных, обрабатываемых в них, а также постоянно накапливаемых в подсистемах хранения. Одной из мер обеспечения защищенности данных является защита их целостности (Методический документ. Меры защиты информации в государственных информационных системах: утв. директором ФСТЭК 11.02.2014 // ФСТЭК России, 2014. - 176 с.).
Задача защиты целостности данных включает в себя контроль их целостности, а также восстановление данных, целостность которых была нарушена по каким-либо причинам. Далее для раскрытия сути изобретения приводится краткое описание существующих способов контроля и восстановления целостности данных.
а) Описание аналогов
Известны способы контроля целостности данных за счет вычисления контрольных сумм и сравнения их с эталонными (Патент РФ №2145727, опубл. 20.02.2000; Патент РФ №2467495 опубл. 20.11.2012; Патент РФ №2628894, опубл. 06.09.2016), а также способы, основанные на применении криптографических методов: ключевое и бесключевое хэширование, средства электронной подписи (Патент РФ №2408071, опубл. 27.12.2010; Патент РФ №2500027, опубл. 27.11.2013; Заявка на патент РФ №2005113932, опубл. 20.01.2007; Заявка на патент РФ №2004110622, опубл. 10.10.2007; Заявка на патент РФ №2006116797, опубл. 27.01.2008; Заявка на патент РФ №2007141753, опубл. 10.09.2010; Заявка на патент РФ №2012107193, опубл. 10.10.2013; Заявка на патент РФ №2013149120, опубл. 10.05.2015; Заявка на патент РФ №2015152423, опубл. 14.06.2017; Кнут, Д.Э. Искусство программирования для ЭВМ. Том 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-массивы), методы дублирования, методы избыточного кодирования) (Патент РФ №2406118, опубл. 10.04.2007; Патент РФ №2481632, опубл. 10.05.2013; Патент РФ №2513725, опубл. 20.04.2014; Патент РФ №2598991, опубл. 10.10.2016; Патент США №7392458, опубл. 24.06.2008; Патент США №7437658, опубл. 14.10.2008; Патент США №7600176, опубл. 06.10.2009; Заявка на патент США №20090132851, опубл. 21.05.2009; Заявка на патент США №20100229033, опубл. 09.09.2010; Заявка на патент США №20110114567, опубл. 16.06.2011; Заявка на патент США №20110167294, опубл. 07.07.2011; Заявка на патент США №20110264949, опубл. 27.10.2011; Уоррен, Г. Подсчет битов: алгоритмические трюки для программистов (Hacker's Delight) [Текст] / Г. Уоррен, мл. - М.: «Вильяме», 2007. - 512 с.; Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение [Текст] / Р. Морелос-Сарагоса; переводе англ. В.Б. Афанасьев. - М.: Техносфера, 2006. - 320 с.; Хемминг, Р.В. Теория кодирования и теория информации [Текст] / Р.В. Хемминг; перевод с англ. - М.: «Радио и связь», 1983. - 176 с.).
Недостатками данных способов являются:
- отсутствие возможности подтверждения достоверности и полноты данных после их восстановления;
- высокая избыточность.
Представленные решения показывают, что часть способов позволяет осуществить контроль целостности данных путем сравнения значений эталонных и вычисляемых хэш-кодов хэш-функции (контрольных сумм) при запросе на использование хранящихся в памяти данных (фиг. 1), однако в них отсутствует механизм их восстановления в условиях как случайных ошибок, так и ошибок, генерируемых посредством преднамеренных воздействий злоумышленника, что не обеспечивает их целостность. К тому же, контроль целостности блоков данных небольшой размерности, где от каждого блока данных, подлежащего защите, вычисляется хэш-код, характеризуется вводом высокой избыточности контрольной информации. При попытке устранения данного недостатка за счет вычисления одного хэш-кода от нескольких блоков данных приводит к отсутствию возможности осуществления локализации обнаруженной ошибки (фиг. 2).
Другие способы, позволяющие осуществить восстановление целостности данных, основаны на применении различных видов резервирования (фиг. 3), однако данные способы разрабатывались и успешно применяются для борьбы со случайными ошибками, поэтому в условиях деструктивных воздействий злоумышленника они не всегда являются эффективными. Данное утверждение складывается из того, что современная теория надежности, помимо множества других разделов математики, в основном базируется на математическом аппарате теории вероятностей. При этом для высокой вероятности обнаружения и исправления возникающих ошибок, приводящих к нарушению целостности данных, требуется большое количество вводимой избыточности. К примеру, избыточность, вводимая для восстановления целостности данных посредством применения технологии резервного копирования, равна 100% от общего объема защищаемых данных (фиг. 4).
Отдельные способы позволяют осуществить контроль и восстановление целостности данных, однако ценной высокой избыточности. Наиболее популярными являются решения комплексной защиты целостности данных, связанной с одновременным решением задач контроля и восстановления целостности данных, что достигается за счет последовательного применения сначала криптографического преобразования к данным, а затем применения технологии резервного копирования данных. При этом, защита целостности данных актуальна как для систем типа RAID, где все носители размещены в одном конструктивном блоке, так и для распределенных систем хранения, то есть для сетевых хранилищ.
Так в Заявке на патент США №20050081048, опубл. 14.04.2005 предложен способ защиты данных в RAID-массивах, согласно которому перед записью на RAID-массив (после чтения с RAID-массива) данные шифруются (расшифровываются) специально выделенным устройством, подключенным к PCI-шине. Ключ зашифрования (расшифрования) считывается с внешнего запоминающего устройства и (или) запрашивается у пользователя.
В Патенте США №7752676, опубл. 06.07.2010 предложен способ защиты данных в сетевом хранилище, согласно которому, пользовательский запрос на чтение (запись) данных сначала проходит процедуру авторизации, и только в случае разрешения операции выполняется соответственно расшифрование (шифрование) данных на сетевом хранилище. Ключи зашифрования (расшифрования) хранятся на стороне клиента.
Другой вариант комбинированной защиты предложен в Заявке на патент США №20110107103, опубл. 05.05.2011, согласно которому данные хранятся в облаке, а модуль шифрования хранится не на стороне клиента, а на стороне провайдера облачного хранилища. Это решение предназначено, как правило, для защиты резервных копий данных в облаке, хотя оригинальные данные хранятся на стороне клиента в исходном виде. При этом, для обеспечения защиты данных файл с данными сначала разбивается на части, а затем каждая часть преобразуется с помощью криптографического алгоритма и записывается на один или несколько носителей в облаке. Защита обеспечивается в случае, когда данные утрачиваются на стороне клиента. В этом случае резервная копия восстанавливается из облака.
Недостатком данных способов является отсутствие возможности восстановления данных с подтвержденной целостностью, то есть проверки достоверности и полноты данных после их восстановления.
Анализ предшествующего уровня техники и возможностей показывает, что для обеспечения целостности данных требуется осуществление агрегирования существующих решений для возможности контроля и восстановления целостности данных.
б) Описание ближайшего аналога (прототипа)
Наиболее близким по технической сущности к заявленному изобретению (прототипом) является способ защиты информации для RAID-массивов, согласно которому перед записью в массив данные разбиваются на несколько сегментов, после чего от данных из каждого сегмента отдельно вычисляются контрольные суммы. Сегменты данных и контрольные суммы далее распределяются по дискам RAID-массива (Патент США №8209551, опубл. 26.06.2012).
Недостатком известного способа является отсутствие возможности восстановления данных с подтвержденной целостностью.
Раскрытие изобретения
а) Технический результат, на достижение которого направлено изобретение
Целью настоящего изобретения является разработка способа восстановления данных с подтвержденной целостностью, при котором обеспечивается возможность проверки достоверности и полноты данных после их восстановления.
б) Совокупность существенных признаков
1
n
1
n
ij
i
j
i
i1
i2
in
i1
i2
in
i1
i2
in
1j
2j
nj
n+1,j
n+2,j
kj
ij
i
i
Поставленная цель достигается тем, что в известном способе защиты информации, заключающемся в том, что целостность данных обеспечивается за счет их резервирования с использованием технологии RAID, при которой для осуществления контроля целостности данных перед записью в массив блок данных М разбивается на несколько подблоков m, …, m, часть из которых шифруется, а часть остается в открытом виде, после чего от шифрованных и нешифрованных подблоков данных вычисляются контрольные суммы, которые вместе с подблоками m, …, m распределяются по дискам RAID-массива, в представленном же способе для восстановления данных М с подтвержденной целостностью они представляются в виде матрицы W, на n строках и n столбцах которой располагаются подблоки данных M, выраженные двоичными векторами, при этом строки матрицы образуют блоки данных M, столбцы матрицы - блоки данных M, от блоков данных M, представленных в виде подблоков фиксированной длины M, M, …, M, предварительно вычисляются эталонные хэш-коды H, H, …, H хэш-функций h(M), h(M), …, h(M), хранящиеся в среде, обеспечивающей целостность контрольной информации, значения которых в последующем сравниваются со значениями хэш-кодов  хэш-функции  вычисляемых уже от проверяемых на нарушение целостности блоков данных  подблоки которых  одновременно являются подблоками  блоков данных  которые для восстановления целостности данных в случае ее нарушения формируются по правилам, аналогичным правилам построения избыточных модулярных полиномиальных кодов, обеспечивая при этом для подблоков M, M, …, M, которые являются информационной группой n подблоков, предназначенной для однозначного восстановления блоков данных  в случае нарушения их целостности, вычисление контрольной группы k-n подблоков M,M, …, M, дополнительно вводимой для коррекции q-кратной ошибки, в случае возникновения которой восстановление целостности подблоков  блоков данных  без ущерба для однозначности их представления осуществляется посредством реконфигурации системы путем исключения из вычислений подблока  с нарушением целостности, после чего от полученного результата вычисляется подблок M взамен ранее исключенного, после восстановления целостности данных осуществляется проверка их достоверности и полноты путем сравнения значений вычисленных хэш-кодов  хэш-функции  уже от восстановленных блоков данных  со значениями предварительно вычисленных эталонных хэш-кодов хэш-функции h(M), хранящихся в среде, обеспечивающей целостность контрольной информации, от первоначальных блоков данных M.
Сопоставительный анализ заявленного решения с прототипом показывает, что предлагаемый способ отличается от известного тем, что поставленная цель достигается за счет контроля целостности данных путем сравнения значений предварительно вычисленных эталонных хэш-кодов хэш-функции от первоначальных блоков данных со значениями вычисленных хэш-кодов хэш-функции от проверяемых блоков данных, подблоки которых для восстановления целостности данных в случае ее нарушения формируются по правилам, аналогичным правилам построения избыточных модулярных полиномиальных кодов, что позволяет восстановить данные в условиях как случайных ошибок, так и ошибок, генерируемых посредством преднамеренных воздействий злоумышленника, для проверки достоверности и полноты данных после их восстановления осуществляется сравнение значений хэш-кодов хэш-функции уже от восстановленных блоков данных со значениями предварительно вычисленных эталонных хэш-кодов хэш-функции от первоначальных блоков данных.
i
i
i
ij
i
i
i
1j
2j
nj
n+1,j
kj
обн
min
min
ij
i
i
i
Контроль целостности блоков данных M будет осуществляться путем сравнения значений предварительно вычисленных от них эталонных хэш-кодов H хэш-функции h(M) со значениями хэш-кодов  хэш-функции , вычисленных уже от проверяемых на нарушение целостности блоков данных  При нарушении целостности данных в условиях как случайных ошибок, так и ошибок, генерируемых посредством преднамеренных воздействий злоумышленника (в результате преднамеренного несанкционированного изменения данных (например, посредством действия вредоносного кода) или выхода из строя части носителя (например, отдельных ячеек, секторов)) в момент времени t будет осуществляться восстановление целостности блоков данных  то есть обеспечение их целостности за счет представления на подготовительном этапе их подблоков M по правилам, аналогичным правилам построения избыточных модулярных полиномиальных кодов. Коррекция возникающей q-кратной ошибки будет осуществляться по известным правилам, применяемым при использовании кодов в модулярной арифметике (Акушский И.Я. Машинная арифметика в остаточных классах (Текст) / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.). Проверка достоверности и полноты данных после их восстановления будет осуществляться путем сравнения значений предварительно вычисленных эталонных хэш-кодов H хэш-функции h(M) от первоначальных блоков данных M со значениями хэш-кодов  хэш-функции  уже от восстановленных блоков данных  Новым является то, что в предлагаемом способе получение совокупностей подблоков M, M, …, M, M, …, M интерпретируется как построение избыточного модулярного полиномиального кода, что позволяет обнаружить возникающую q-кратную ошибку на любой стадии их обработки (при условии, что кратность гарантированно обнаруживаемой ошибки d=d-1, где d - минимальное кодовое расстояние). Новым является то, что восстановление целостности блоков данных  в случае ее нарушения возможно путем исключения из процесса восстановления любых r подблоков без ущерба для однозначности их представления (где r=k-n - количество дополнительных подблоков), вследствие чего система подблоков блоков данных  будет интерпретироваться как несистематический или неразделимый код (где каждая разрядная цифра несет часть информации о числе, включая и избыточные символы, а также любые из r разрядных цифр можно считать избыточными символами), после чего вычисляется подблок M взамен ранее исключенного подблока  с обнаруженной ошибкой. Новым является то, что сравнение значений предварительно вычисленных эталонных хэш-кодов H хэш-функции h(M) от первоначальных блоков данных M в отличие от способа-прототипа позволяет не только осуществить контроль целостности данных путем их сравнения со значениями хэш-кодов  хэш-функции  от проверяемых на нарушение целостности блоков данных , но и выполнить проверку достоверности и полноты данных после их восстановления при обеспечении их целостности за счет их сравнения со значениями хэш-кодов  хэш-функции  уже от восстановленных блоков данных
в) Причинно-следственная связь между признаками и техническим результатом
Благодаря новой совокупности существенных признаков в способе реализована возможность:
- обнаружения возникающей q-кратной ошибки в условиях как случайных ошибок, так и ошибок, генерируемых посредством преднамеренных воздействий злоумышленника;
- коррекции обнаруженной q-кратной ошибки;
- восстановления данных с подтвержденной целостностью.
Доказательства соответствия заявленного изобретения условиям патентоспособности «новизна» и «изобретательский уровень»
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного способа условию патентоспособности «новизна».
Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность отличительных существенных признаков, обуславливающих тот же технический результат, который достигнут в заявленном способе. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Краткое описание чертежей
Заявленный способ поясняется чертежами, на которых показано:
фиг. 1 - схема контроля целостности данных на основе применения хэш-функции;
фиг. 2 - схема, поясняющая недостатки, возникающие при контроле целостности данных;
фиг. 3 - схема резервирования;
фиг. 4 - схема применения технологии резервного копирования;
фиг. 5 - общая схема разработанного способа.
Осуществление изобретения
Возможность реализации заявленного способа объясняется следующим.
ij
Путем фиксации одного из измерений гиперкуба данных получим матрицу W, на строках и столбцах которой располагаются подблоки данных M, подлежащие защите:
При этом строки матрицы (1) образуют блоки данных  столбцы матрицы - блоки данных  - операция конкатенации (объединения).
i
i
i
k
i
i
Для контроля целостности данных, подлежащих защите, к блокам данных M применим хэш-функцию. Полученные хэш-коды H хэш-функции h(M) (или h(M), где k - секретный ключ) от блоков данных M будут являться эталонными:
где
ij
j
В свою очередь, для возможности восстановления целостности данных, подлежащих защите, подблоки M блоков данных M представим в полиномиальной форме:
где
ij
j
ij
Полученные подблоки M(z) блоков данных M, представленные в полиномиальной форме, интерпретируются как наименьшие неотрицательные вычеты по основаниям p(z) таким, что
При этом
где  - степень полинома
j
Далее совокупность подблоков  блока данных M представим как единый суперблок модулярного полиномиального кода (МПК) по системе оснований
В соответствии с Китайской теоремой об остатках для многочленов для заданного множества многочленов  при условии  и многочленов  таких, что  система сравнений:
имеет единственное решение X(z).
Выполним операцию расширения МПК  путем введения k-n избыточных оснований  и получим избыточные вычеты
Причем
где
Получим расширенный МПК в кольце многочленов:
и матрицу:
j
i
Для выполнения операций между полученными j-ми избыточными подблоками блоков данных M и i-ми подблоками хэш-кодов H выполним обратное сопоставление многочленов:
их двоичным векторам:
где
Получим матрицу:
i
j
Выполним сложение i-х подблоков хэш-кодов H с j-ми избыточными подблоками блоков данных M кодового вектора МПК:
где  - символ сложения в GF(2),
Получим матрицу:
Данные, подлежащие защите, представленные в виде (3) готовы к хранению.
ij
ij
При запросе на использование защищаемых данных M, представленных в виде (3), сначала выполняется контроль их целостности, для этого сопоставим двоичные векторы M их многочленам:
где
Выполним операцию расширения информационного суперблока МПК, в результате которой формируются избыточные подблоки  блоков данных  где символ  обозначает, что могло произойти нарушение целостности данных  находящихся на хранении, представленных подблоками
Получим расширенный МПК в кольце многочленов:
и матрицу:
Выполним обратное сопоставление многочленов  их двоичным векторам:
где  и обратные преобразования:
i
Сравним значения полученных хэш-кодов  со значениями ранее вычисленных эталонных хэш-кодов H, хранящихся в надежной среде. По результатам сравнения сделаем вывод об отсутствии нарушения целостности данных при  либо о нарушении целостности данных при
Таким образом, определение факта нарушения целостности подблока данных  находящихся на хранении, посредством сравнения хэш-кодов будет являться локализацией по строкам матрицы блока  с нарушением целостности входящего в него подблока  (в случае однократной ошибки) или нескольких подблоков.
Затем посредством математического аппарата МПК выполняется локализация одного или нескольких подблоков  входящих в блок данных  по столбцам (то есть определяется один или несколько блоков данных  с нарушением целостности, в который входит один или несколько подблоков ).
Под нарушением целостности в одном произвольном подблоке данных  кодового слова МПК будем понимать появление однократной ошибки, соответственно q-кратная ошибка определяется как произвольное нарушение целостности q подблоков. Известно, что МПК обнаруживает q ошибок при k-n≥q и исправляет q или менее ошибок, если k-n≥2q.
В соответствии с правилами декодирования модулярных кодов критерием отсутствия обнаруживаемых ошибок в МПК (в частности, ) является выполнение неравенства:  и  - решение системы (2) для  Критерий существования обнаруживаемой ошибки - выполнение неравенства
ij
Восстановление целостности подблока M(z) защищаемых данных выполняется путем вычисления наименьшего вычета:  где X(z) повторно вычислено с учетом исключения подблока с нарушением целостности.
i
Выполним проверку достоверности и полноты данных после их восстановления в случае нарушения их целостности путем сравнения значения предварительно вычисленного эталонного хэш-кода H со значением вычисленного хэш-кода  уже от восстановленного блока данных. По результатам сравнения сделаем вывод об подтверждении целостности данных после их восстановления при  либо о ее нарушении при
Общая схема разработанного способа восстановления данных с подтвержденной целостностью представлена на рисунке (фиг. 5).