RU2680033C2 - Method of ensuring the integrity of data - Google Patents

Abstract

FIELD: information technology.SUBSTANCE: invention relates to a method for ensuring data integrity. Method consists in the fact that the detection and localization of an error in the records m, m, …, mdata block M is provided by a system of hash codes by calculating the hash function signatures, moreover, the hash code system provides for records m, m, …, m, which are an information group of n records designed to uniquely restore the integrity of the data block M, calculating the control group of k-n records m, …, m, additionally entered to correct the error arising under the conditions of deliberate actions of the attacker, in the event of which the restoration of the integrity of the data block M is carried out by reconfiguring the system by eliminating one or severalrecords, where i=1, 2, …, k, with an error that has occurred, error detection and verification of data integrity recovery is performed by comparing the calculated signature S of the hash function h(M) from the checked data block M with the previously calculated signature S* hash function h(M*) from the original block data M*.EFFECT: ensuring the integrity of the data and the restoration of the integrity of the data with their possible change in the conditions of the deliberate effects of the attacker.1 cl, 5 dwg, 1 tbl

Description

FIELD OF THE INVENTION

The present invention relates to information technology and can be used to ensure data integrity in information systems through monitoring, as well as restoring data integrity when it is possible to change under the conditions of deliberate attacks by an attacker.

State of the art

a) Description of analogues

Known methods for ensuring data integrity through the use of various types of redundancy (using software or hardware or software implementation of RAID technology (Redundant Array of Independent Disks) (RAID arrays), duplication methods, redundant coding methods) (US Patent No. 7392458 publ. 24.06 .2008; US Patent No. 7437658 publ. 10/14/2008; US Patent No. 7600176 publ. 10/06/2009; Application for US patent No. 20090132851 publ. 05/21/2009; Application for US patent No. 20100229033 publ. 09/09/2010; Patent application USA No. 201101145677 publ. 06/16/2011; Application for US patent No. 20110167294 publ. 07/07/2011; Application for US patent No. 20110264949 published 10.27.2011; Warren, G. Counting bits: algorithmic tricks for programmers (Hacker's Delight) [Text] / G. Warren, Jr. - M .: "Williams", 2007. - 512 p.; Morelos-Zaragoza , R. The art of error-correcting coding. Methods, algorithms, application [Text] / R. Morelos-Zaragoza; translated from English by VB Afanasyev. - M .: Technosphere, 2006. - 320 p .; Hemming, R.V. . Coding Theory and Information Theory [Text] / R.V. Hamming translation from English - M.: “Radio and Communications”, 1983. - 176 p.).

The disadvantages of these methods are:

- high redundancy;

- A large number of cryptographic transformations.

Known methods for ensuring data integrity through the use of cryptographic methods: key and keyless hashing, electronic signature means (Application for a patent of the Russian Federation No. 2012107193/08 publ. 10.10.2013; Application for a patent of the Russian Federation No. 2006116797/09 publ. 01/27/2008; Application for RF patent No. 2007141753/09 publ. 09/10/2010; Application for a patent of the Russian Federation No. 2013149120/08 publ. 05/10/2015; Application for a patent of the Russian Federation No. 2004110622/09 publ. 10.10.2007; Application for a patent of the Russian Federation No. 2005113932/09 publ. January 20, 2007; Knut, D.E. The Art of Computer Programming, Volume 3, sorting and searching [Text] / D.E. Knut. - M.: Mir, 1978. - 824 p .; Menezes, AJ Handbook of Applied Cryptography [Tech Art.] / AJ Menezes, Paul C. van Oorschot, Scott A. Vanstone. - M .: CRC Press, Inc., 1996. - 816 c .; Biham, EA framework for iterative hash functions. - HAIFA [Text] / E . Biham, O. Dunkelman. - M .: HAIFA, ePrint Archive, Report 2007/278. - 20 p .; Also [Electronic resource]. - Access mode: eprint.iacr.org/2007/278.pdf (July , 2007); Wang, X. How to break MD5 and Other Hash Function [Text] / 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 [Text] / M. Bellare. - M .: CRYPTO 2006, ePrint Archive, Report 2006/043. - 31 p .; The same [Electronic resource]. - Access mode: eprint.iacr.org/2006/043.pdf (2006)), for which two generalized schemes for obtaining hash codes are typical: for each record in the data block (Fig. 1) and for the whole data block (Fig. 2).

The disadvantages of these methods are:

for the circuit (Fig. 1):

- high redundancy when monitoring the integrity of the sequences of records of small dimension;

for the circuit (Fig. 2):

- the lack of localization of distorted records in each data block.

b) Description of the closest analogue (prototype)

The closest in technical essence to the claimed invention (prototype) is a method of providing the necessary level of security (integrity) of data based on a set of hash codes (Fig. 3) obtained using the standard procedure for implementing a hash function from a combination of data (records) in the order defined by a special procedure for selecting a record based on the mathematical apparatus of linear algebra (linear hash code systems (LSKhK)) (Finko, O.A. Ensuring data integrity in automated systems based on linear systems of hash codes / O.A. Finko, S.V. Savin // Political Mathematical Electronic Scientific Journal of the Kuban State Agrarian University. - 2015. - No. 114. - P. 796-811), where data integrity control (detection errors), by analogy with linear codes, is carried out by calculating the syndrome, upon verification of which we can conclude that there is or is not an error.

The disadvantage of this method is the inability to correct the error that occurs in the records (data recovery when they change) under the conditions of the deliberate actions of an attacker.

Disclosure of invention

a) The technical result, the achievement of which the invention is directed

The aim of the present invention is to develop a method for ensuring data integrity by means of control, as well as restoring data integrity when it is possible to change under the conditions of deliberate actions of an attacker.

b) the Set of essential features

, где i=1, 2, …, k, с возникшей ошибкой, в свою очередь, обнаружение ошибки, а также проверка достоверности восстановления целостности данных производится посредством сравнения вычисленной сигнатуры S хэш-функции h(M) от проверяемого блока данных М с ранее вычисленной сигнатурой S* хэш-функции h(M*) от первоначального блока данных М*.This goal is achieved by the fact that in the known method of ensuring data integrity, which consists in the fact that the detection and localization of an occurring error in the records m ₁ , m ₂ , ..., m _n of the data block M are provided by a hash code system by computing hash signatures functions, in the presented method, the hash code system, built according to the rules similar to the rules for constructing modular codes, provides for records m ₁ , m ₂ , ..., m _n , which are an information group of n records intended for unambiguous restoration the integrity of the data block M, the calculation of the control group kn of records m _{n + 1} , ..., m _k , additionally introduced to correct the error that occurs under the deliberate actions of the attacker, in the event of which the integrity of the data block M is restored without compromising the unambiguity of its presentation by reconfiguring the system by excluding one or more entries

, where i = 1, 2, ..., k, with the error that occurred, in turn, error detection, as well as verification of the reliability of data integrity recovery, is performed by comparing the calculated signature S of the hash function h (M) from the data block M being checked with previously the computed signature S * of the hash function h (M *) from the original data block M *.

A comparative analysis of the claimed solution with the prototype shows that the proposed method differs from the known one in that the goal is achieved by detecting errors by comparing the calculated signature of the hash function from the verified data block with the previously calculated signature of the hash function from the original data block, for which to rules similar to the rules for constructing modular codes, a hash code system is being built that allows for the correction of an error that occurs under intentional influences attacker, as well as verify the reliability of data integrity recovery by re-comparing hash function signatures from the checked and original data blocks.

Definition 1. A hash code system is a set of hash codes obtained using the standard procedure for implementing a hash function from a data block in the order corresponding to obtaining the smallest non-negative residue of a number from the base of the system in modular arithmetic (MA).

). Новым является то, что восстановить целостность блока данных М возможно путем исключения из процесса восстановления любых r записей без ущерба для однозначности представления первоначального блока данных М* (где r=k-n - количество дополнительных записей), вследствие чего система записей блока данных будет интерпретироваться как несистематический или неразделимый код. Новым является то, что сигнатура S хэш-функции h(M) вычисляется от проверяемого блока данных М, что в отличие от способа-прототипа позволяет обеспечить контроль целостности данных посредством обнаружения ошибки, а также проверить достоверность восстановления целостности данных путем сравнения значения вычисленной сигнатуры хэш-функции с ранее вычисленной сигнатурой хэш-функции от первоначального блока данных.The integrity of the data block M to be protected will be ensured by detecting an error that has arisen, as well as verifying the reliability of restoring data integrity by comparing the calculated signature of the hash function from the verified data block with the previously calculated signature of the hash function from the original data block, which allows at the time time t under the conditions of the deliberate actions of the attacker to restore the integrity of the original data block M *. Correction of the error will be carried out according to the well-known rules that apply when using codes in MA (Akushsky, I.Ya. Machine arithmetic in residual classes [Text] / I.Ya. Akushsky, D.I. Yuditsky. - M.: Soviet Radio, 1968 .-- 440 p.). What is new is that in the proposed method, obtaining sets of records m ₁ , m ₂ , ..., m _n , m _{n + 1} , ..., m _{k is} interpreted as building a modular code, which allows you to restore the integrity of the data block M with the possibility of correcting an error on at any stage of its processing (provided that the minimum code distance d _min and the multiplicity t _{k of a} guaranteed correctable error satisfy the inequality:

) What is new is that it is possible to restore the integrity of the data block M by excluding from the recovery process any r records without prejudice to the unambiguity of the representation of the original data block M * (where r = kn is the number of additional records), as a result of which the record system of the data block will be interpreted as unsystematic or inseparable code. What is new is that the signature S of the hash function h (M) is calculated from the data block M being checked, which, in contrast to the prototype method, allows for data integrity control by detecting errors, and also to verify the reliability of data integrity recovery by comparing the value of the calculated hash signature -functions with a previously computed hash function signature from the original data block.

In unsystematic codes, each bit digit carries a piece of information about the number, including redundant characters. In a non-systematic code, any of the r bit digits can be considered redundant characters.

c) Causal relationship between the signs and the technical result

Thanks to the new combination of essential features in the method, the opportunity is implemented:

- detection of an error in the context of the deliberate actions of an attacker;

- localization and correction of the detected error;

- restoring the integrity of the original data block by reconfiguring the system by eliminating the record with an error;

- validation checks to restore data integrity.

Evidence of compliance of the claimed invention with the conditions of patentability "novelty" and "inventive step"

The analysis of the prior art made it possible to establish that analogues that are characterized by a set of features identical to all the features of the claimed technical solution are absent, which indicates the compliance of the claimed method with the condition of patentability “novelty”.

Search results for known solutions in this and related fields of technology in order to identify features that match the distinctive features of the claimed object from the prototype showed that they do not follow explicitly from the prior art. The prior art also did not reveal the fame of the distinctive essential features that cause the same technical result, which is achieved in the claimed method. Therefore, the claimed invention meets the condition of patentability "inventive step".

Brief Description of the Drawings

The claimed method is illustrated by drawings, which show:

FIG. 1 is a diagram for generating a hash code for each record in a data block;

FIG. 2 is a diagram of generating a hash code for a data block;

FIG. 3 is a general diagram of the formation of LSHK;

FIG. 4 is a diagram explaining a procedure for generating a system of modular hash codes with the ability to detect changes in a data block;

FIG. 5 is a diagram explaining a procedure for restoring the integrity of a data block when it detects a change in a separate record.

The implementation of the invention

The possibility of implementing the inventive method is explained as follows. The error that is detected under the deliberate actions of the attacker is compared by comparing the calculated signature S of the hash function h (M), where M is the data block being checked, with the previously calculated signature S * of the hash function h (M *), where M * is the original block data (Fig. 4).

If an error is detected (violation of the integrity of the data block M), it is localized and corrected (restoration of the integrity of the original data block M *) (Fig. 5) based on the mathematical apparatus MA, according to which the data block M will be interpreted as a non-negative integer A uniquely represented by a set of residues on the basis of MA p ₁ , p ₂ , ..., p _n <p _{n + 1} <... <p _k :

A = (α ₁ , α ₂ , ..., α _n , α _{n + 1,} ..., α _k ) _MA ,

where P _n = p ₁ p ₂ ... p _n >A; α _j = | A | _pj ; | ⋅ | _p is the smallest non-negative residue of the number "⋅" modulo p; p ₁ , p ₂ , ..., p _n <p _{n + 1} <... <p _k are pairwise simple; j = 1, 2, ..., n, n + 1, ..., k (Akushsky, I.Ya. Machine arithmetic in residual classes [Text] / I.Ya. Akushsky, D.I. Yuditsky. - M .: Soviet Radio, 1968. - 440 p .; Torgashev, V.A. System of residual classes and reliability of a digital computer [Text] / V.A. Torgashev. M.: Soviet radio, 1973. 120 p.).

The resulting residues α _j will be interpreted as records m _j of the data block M, that is, residues MA α ₁ , α ₂ , ..., α _n will be interpreted as records m ₁ , m ₂ , ..., m _n and be considered an information group of n records, and α _{n + 1} , ..., α _k - interpreted as a control group kn of records m _{n + 1} , ..., m _k . In this case, the MA itself is extended, where P _k = P _n p _{n + 1} ... p _k , and covers the complete set of states represented by all residues. This area will be the full range of MA [0, P _k ) and will consist of the working range [0, P _n ), where P _n = p ₁ p ₂ ... p _n defined by non-redundant MA bases (records m ₁ , m ₂ , ... , m _n ), and the range [P _n , P _k ) determined by the excess MA bases (records m _{n + 1} , ..., m _k ) and representing an unacceptable region. This means that operations on the number A are performed in the range [0, P _k ). Therefore, the correctness of the correction of the detected error will be confirmed by the result of the operation MA, falling within the limits of P _n .

The mathematical apparatus of modular codes is based on the fundamental principles of the Chinese remainder theorem, therefore, the correction of the error that will occur will be based on the following theorems:

Theorem 1. Let the bases p ₁ , p ₂ , ..., p _n , p _{n + 1} MA satisfy the condition p _i <p _{n + 1} (i = 1, 2, ..., n) and let A = (α ₁ , α ₂ , ..., α _i , ..., α _n , α _{n + 1} ) is the correct number. Then the value of the number A will not change if we represent it in the base system from which the base p _i is removed (that is, if the number α _{i is} crossed out in the representation A).

тождественно следующему неравенству А<p₁p₂, …, p_i-1 p_i+1, p_n+1, и, следовательно, число А может быть единственным образом представлено своими остатками по этим основаниям.Evidence. Inequality

is identical to the following inequality A <p ₁ p ₂ , ..., p _i-1 p _{i + 1} , p _{n + 1} , and therefore, the number A can be uniquely represented by its residues on these grounds.

, полученное из А зачеркиванием цифры

, называется проекцией числа А по основанию p_i.Definition 2. Number

obtained from A by striking out the numbers

, is called the projection of the number A at the base p _i .

Definition 3. The base system p ₁ , p ₂ , ..., p _n , p _{n + 1} , satisfying the condition p ₁ <p ₂ <... <p _n <p _{n + 1} , is called an ordered base system.

.Theorem 2. If the correct number A = (α ₁ , α ₂ , ..., α _i , ..., α _n , α _{n + 1} ) is given in the ordered base system, then the projections of this number for all bases coincide, that is

.

и в соответствии с предыдущей теоремой величину А сохранит его проекция по каждому основанию (Акушский, И.Я. Машинная арифметика в остаточных классах [Текст] / И.Я. Акушский, Д.И. Юдицкий. - М.: Советское радио, 1968. - 440 с.).Evidence. For the correct number, subject to the theorem, the inequalities

and in accordance with the previous theorem, the value A will be preserved by its projection on each base (Akushsky, I.Ya. Machine arithmetic in residual classes [Text] / I.Ya. Akushsky, D.I. Yuditsky. - M.: Soviet Radio, 1968 . - 440 p.).

с возникшей ошибкой операция реконфигурации выполняется вычислением А* из системыThus, after recording localization

with an error, the reconfiguration operation is performed by calculating A * from the system

on the “correct” grounds of MA:

- ошибочный остаток; B_i,j - ортогональные базисы; i, j=1, …, n, …, k; i≠j;

μ_i,j подбирается так, чтобы имело место следующее сравнение:

Where

- erroneous balance; B _{i, j} - orthogonal bases; i, j = 1, ..., n, ..., k; i ≠ j;

μ _{i, j is} selected so that the following comparison takes place:

Table 1 is compiled containing the values of the orthogonal bases and modules of the system, provided that a single error occurs for each MA basis.

Example

We choose the base system p ₁ = 2, p ₂ = 3, p ₃ = 5, p ₄ = 7, for which the working range is P ₄ = p ₁ p ₂ p ₃ p ₄ = 2⋅3⋅5⋅7 = 210. We introduce the control base p ₅ = 11, p ₆ = 13, then the full range is defined as P ₆ = P ₄ p ₅ p ₆ = 210⋅11⋅13 = 30030.

We calculate the orthogonal bases of the system:

. Вместо него при обработке данных получили

Для локализации ошибки вычисляем величину числа

:Number given

. Instead, when processing data received

To localize the error, we calculate the value of the number

:

, что свидетельствует об ошибке при обработке данных.The resulting number is incorrect

, which indicates an error during data processing.

по каждому из оснований.We calculate the projection of the number

for each of the grounds.

On the basis of p ₁ = 2:

Тогдаfor MA bases p ₂ = 3, p ₃ = 5, p ₄ = 7, p ₅ = 11, p ₆ = 13, we calculate the orthogonal bases

Then

On the basis of p ₂ = 3:

Тогдаfor MA bases p ₁ = 2, p ₃ = 5, p ₄ = 7, p ₅ = 11, p ₆ = 13, we calculate the orthogonal bases

Then

On the basis of p ₃ = 5:

Тогдаfor MA bases p ₁ = 2, p ₂ = 3, p ₄ = 7, p ₅ = 11, p ₆ = 13, we calculate the orthogonal bases

Then

On the basis of p ₄ = 7:

Тогдаfor MA bases p ₁ = 2, p ₂ = 3, p ₃ = 5, p ₅ = 11, p ₆ = 13, we calculate the orthogonal bases

Then

On the basis of p ₅ = 11:

Тогдаfor MA bases p ₁ = 2, p ₂ = 3, p ₃ = 5, p ₄ = 7, p ₆ = 13, we calculate the orthogonal bases

Then

On the basis of p ₆ = 13:

Тогдаfor MA bases: p ₁ = 2, p ₂ = 3, p ₃ = 5, p ₄ = 7, p ₅ = 11, we calculate the orthogonal bases

Then

, кроме

, неправильные. Следовательно, ошибочна цифра

по основанию р₅=11.So, all the projections of the number

, Besides

wrong. Therefore, the erroneous figure

on the basis of p ₅ = 11.

с возникшей ошибкой, что позволит восстановить целостность первоначального блока данных.After localizing the error, we reconfigure the system by eliminating the record

with an error that will allow you to restore the integrity of the original data block.

In accordance with (1), we calculate A * using table 1. We obtain

с возникшей ошибкой. Проверка достоверности восстановления целостности данных обеспечивается сравнением повторно вычисленной сигнатуры S хэш-функции h(M), где М - проверяемый блок данных, с ранее вычисленной сигнатурой S* хэш-функции h(M*) от первоначального блока данных М*.Restoring the integrity of the original M * data block is provided by reconfiguring the system by eliminating the record

with the error that occurred. Validation of the restoration of data integrity is provided by comparing the recalculated signature S of the hash function h (M), where M is the data block being checked, with the previously calculated signature S * of the hash function h (M *) from the original data block M *.

Claims (1)

The way to ensure data integrity is that the detection and localization of an occurring error in the records m ₁ , m ₂ , ..., m _n of the data block M is provided by a hash code system by computing hash function signatures, characterized in that the hash system -codes, constructed according to the rules similar to the rules for constructing modular codes, provides for records m ₁ , m ₂ , ..., m _n , which are an information group of n records intended to uniquely restore the integrity of the data block M, the calculation of the control group py kn records m _{n + 1} , ..., m _k , additionally introduced to correct an error that occurs under the deliberate actions of an attacker, in the event of which restoration of the integrity of the data block M without compromising the unambiguity of its presentation is carried out by reconfiguring the system by eliminating one or more records

, where i = 1, 2, ..., k, with the error that occurred, in turn, error detection, as well as verification of the reliability of data integrity recovery, is performed by comparing the calculated signature S of the hash function h (M) from the data block M being checked with previously the computed signature S * of the hash function h (M *) from the original data block M *.

Images