The method of two-dimensional control and assurance of data integrity with the possibility of their recovery for information systems operating under conditions of random errors as well as errors generated through deliberate actions of the attacker is proposed. The data recovery procedure is based on the application of the mathematical apparatus of redundant residue number system codes, and the control (veri cation of the recovered data validity (reliability, accuracy)) of data integrity is performed by means of cryptographic methods.
Introduction At present, users of various information systems are facing the tasks of protecting the data processed in them. One of the measures to ensure the security of data processed in information systems is the protection of their integrity [ISO05].
The problem solution of data integrity protection becomes especially urgent during the operation of widely created data processing centers when using di erent processing facilities in their composition with di erent building structures and operating principles under conditions of both random errors and errors generated through deliberate actions of an attacker (unauthorized data modi cation (for example, through the action of malicious code) or the failure of a part of the media (for example, individual cells, sectors)).
The challenge of data integrity protection is complicated because of its complexity, as it involves not only data integrity control, but also its provision, which means the restoration of data whose integrity has been violated for some reason.
There are various ways of solving the problem of control and assurance of data integrity, among which the following are of the greatest interest.
Analysis of existing solutions for control and assurance of data integrity There are known ways to control the data integrity by calculating checksum values and comparing them with reference values, as well as methods based on the use of cryptographic methods: key and keyless hashing, means of electronic signature [Knu73, Men96, Bih07, Bel06]. The disadvantage of these methods is the lack of the ability to insure their integrity without introducing an additional data recovery mechanism.
There are known ways to ensure the integrity of data through the use of various types of reservation (using hardware or software implementation of RAID technology (Redundant Array of Independent Disks) (RAID arrays)), duplication methods, redundant coding methods [Hen13, Mor06, Ham80]. The disadvantage of these methods is high redundancy.
The presented solutions show that some of the methods allow to control the data integrity by comparing the values of the reference and calculated hash-codes of the hash function (checksums) when requesting the use of processed or stored data, but the lack of a mechanism for their recovery does not allow their integrity assurance. Other methods, on the other hand, provide data integrity by restoring them, for example, from a backup copy, but their practical use without data integrity control is ine ective. Individual methods allow for control and ensure the data integrity, however, of valuable high redundancy.
The most popular solutions are the complex protection of data integrity associated with the simultaneous solution of control tasks and ensuring data integrity, which is achieved by consistently applying rst the cryptographic transformation to data, and then applying the technology of data backup.
At the same time, data integrity protection is relevant both for systems of RAID type, where all media are located in one constructive block, and for distributed storage systems, that is, for network storage.
Thus, in order to protect the data integrity, when considering this notion in a complex, it is necessary to aggregate existing solutions. Combining the known methods in one allows you to control and ensure the data integrity. 3
Choosing ways to control the data integrity and recovery to share them ensuring integrity while A method [App05] is known where, before writing to a RAID array (after reading), the data is encrypted (decrypted) by a dedicated device connected to the PCI-tyre, the encryption key being read from an external storage device and/or requested from the user. In [Pat12], before writing to the array, the data is divided into several segments, after which the checksums are calculated separately from the data from each segment. The data segments and checksums are further distributed over the disks of the RAID array.
In [Pat10], a method of protecting data in a network storage is proposed, where a user's request for reading (writing) data rst passes the authorization procedure, and only if the operation is allowed, the data on the network storage is decrypted (encrypted) accordingly. The keys of encryption (decryption) are stored on the client side.
Another version of combined protection is proposed in [App11], where the data is stored in the cloud, and the encryption module is stored not on the client side, but on the side of the cloud storage provider. This solution is intended, as a rule, to protect the backup copies of data in the cloud, although the original data is stored on the client side in its original form. In order to protect the data, the data le is rst divided into parts, and then each part is transformed using a cryptographic algorithm and written to one or more media in the cloud. Protection is provided when data is lost on the client side. In this case, the backup is restored from the cloud.
The disadvantage of the presented combined methods is the high redundancy, as well as the lack of the possibility, without the introduction of an additional monitoring mechanism, to verify the validity (reliability, accuracy) of the recovered data while ensuring their integrity.
In order to eliminate the drawbacks of the known combined methods, a solution is proposed in which cryptographic methods are chosen to perform data integrity control, in particular, a hash function designed speci cally for this purpose, and the data recovery procedure is performed by using redundant residue number system codes, the application of the mathematical apparatus of which allows to provide minimal redundancy, and most importantly, provides, when used together with cryptographic methods the construction of unique scheme which allows to verify the validity (reliability, accuracy) of recovered data while ensuring its integrity in case of violation.
Structural-parametric synthesis of the system of parallel control and assurance of data integrity For control and integrity purposes, the data blocks Mi (i = 1; 2; : : : ; n), to be protected are represented in the form of sub-blocks of xed length Mi = fmi; 1jjmi; 2jj : : : jjmi; ng, where 0 mi; j < pi; j (i; j = 1; : : : ; n; pi; j 2 N); \jj" | is the concatenation operation, n | is the number of data blocks Mi, to be protected, and also xed-length sub-blocks in each data block under consideration Mi. And the length of the data blocks Mi.
Obtaining the matrix W: . . .
m1; n 3 m2; n 7
... 775 : mn; n
To implement integrity control, a hash function is applied to the data blocks Mi, the construction rules of which are de ned in [ISO08]. The received hash-codes Si (or MAC) hash functions h(Mi) (or hk(Mi), k | secret key) from data blocks Mi will be the reference codes, we obtain the matrix : . . . mn; n ! ! ! . . . . . .
Let: si; j = Pt=10+log pi; j &i(;tj)2t; mi; j = Pt=10+log pi; j (t)i; j 2i n 1; gi; j = Pt=10+log pi; j i(;tj)2j 1; i; j ; &i; j ; i; j 2 f0; 1g. Then the numbers mi; j , si; j and gi; j can be mapped to binary vectors: si; j = [ &i(;0j) &i(;1j) : : : &i(; j1+log pi; j) ]; mi; j = [ i(;0j) i(;1j) : : : i(; j1+log pi; j) ]; gi; j = [ i(;0j) i(;1j) : : : i(; j1+log pi; j) ]. We add the i-th sub-blocks of hash-codes Si with j-th redundant sub-blocks of data blocks Mj of the vector of RRNS codes:
Gi = Si
Mj = [ si; 1 mn+1; j si; 2 mn+2; j : : : si; n mk; j ] where the sign \ " denotes the summation in the GF(2);
Si = [ si; 1 si; 2 : : : si; n ];
Mj = [ mn+1; j mn+2; j : : : mk; j ]; Gi = [ gi; 1 gi; 2 : : : gi; n ]: We obtain the matrix : . . . mn; n . . .
At the end of the preparatory stage of the construction of the system (Figure 1), the data subject to protection is presented in the form (1), which will allow control and ensuring their integrity. 5 Procedure for control of data integrity When requesting the use of data (the main stage) to be protected, they are control for their integrity, which can be ensured by performing the base extension the information super-block of RRNS codes [Baj04, Baj05], with this redundant sub-blocks are created m0n+1; 1; m0n+2; 1; : : : ; m0k; 1; m0n+1; 2; m0n+2; 2; : : : ; m0k; 2; : : : : : : ; m0n+1; n; m0n+2; n; : : : ; m0k; n of the data blocks Mj 0 of the vector of the RRNS codes, where \ 0" denotes that changes could occur in sub-blocks m01; 1; m01; 2; : : : ; m01; n; m02; 1; m02; 2; : : : ; m02; n; : : : ; m0n; 1; m0n; 2; : : : ; m0n; n of data blocks Mi0.
The matrix with the redundant sub-blocks of the vector of RRNS codes takes the form: 2 m01; 1 6666 m02...; 1 66 m0n; 1 6 0 = 66 # 66m0n+1; 1 66m0n+2; 1 664 ...
m0k; 1 m01; 2 m02; 2 . .
. m0n; 2
# m0n+1; 2 m0n+2; 2 . .
. m0k; 2 . . . . . . . . .
m01; n m02; n . .
. m0n; n
# m0n+1; n m0n+2; n . .
. m0k; n g10; 1 g20; 1 . .
. gn0; 1 g10; 2 g20; 2 . .
. gn0; 2 . . .
g10; n 3 We perform the inverse transformation (here the bit vectors gi0;j ; m0i; j is equivalent to the numbers gi0;j ; m0i;j ): If the values of the hash-codes of the hash function compared with each other are di erent, which will be characterized by the occurrence of an error (violation of integrity) in the data being processed, we shall perform its localization.
The localization of the detected error (sub-blocks m~i; j with integrity violation) is performed initially on the rows of the matrix 0 (the i-th data block with the integrity violation, which includes the sub-block m~i; j is determined), and then on the columns (the j-th data block with integrity violation, which includes the sub-block m~ i; j is determined).
A data block M~ i with integrity violation, whose sub-blocks are located along the row of the matrix 0, is determined from the results of a comparison of the calculated and reference hash-codes of the hash function. A data block M~ j with an integrity violation whose sub-blocks are arranged along the column of the matrix 0 is determined by means of a mathematical apparatus RRNS codes based on the fundamental provisions of the Chinese remainder theorem.
In accordance with the mathematical apparatus of RNS [Baj04], in which the tested data block Mj will be interpreted as a nonnegative integer Aj unambiguously represented by a set of residues on RNS basis p1; j ; p2; j ; : : : ; pn; j < pn+1; j < : : : < pk; j :
Aj = ( 1; j ; 2; j ; : : : ; n; j ; n+1; j ; : : : ; k; j ); where Pn; j = p1; j p2; j : : : pn; j > Aj ; i; j = jAjpi; j ; j jp | is the smallest nonnegative residue of the number \ " modulo p; j = 1; 2; : : : ; n; n + 1; : : : ; k; i = 1; 2; : : : ; n; p1; j ; p2; j ; : : : ; pn; j < pn+1; j < : : : < pk; j | are pairwise simple.
The resulting residues i; j will be interpreted as sub-blocks mi; j of the data block Mj , that is, the remnants of the RNS 1; j ; 2; j ; : : : ; n; j will be interpreted as sub-blocks m1; j ; m2; j ; : : : ; mn; j and will be considered informational (informational group n sub-blocks), and n+1; j ; : : : ; k; j | interpreted as sub-blocks mn+1; j ; : : : ; mk; j and considered as control (redundant) (control (redundant) group (k n) sub-blocks). The RNS itself is in this case extended, where Pk; j = Pn; j pn+1; j : : : pk; j , and covers the complete set of states represented by all k deductions. This area will be the full range of the RNS [0; Pk; j ) and consist of a working range [0; Pn; j ), where Pn; j = p1; j p2; j : : : pn; j , is de ned by nonredundant of the RNS bases (subblocks m1; j ; m2; j ; : : : ; mn; j ), and a range [Pn; j ; Pk; j ) de ned by redundant of the RNS bases (sub-blocks mn+1; j ; : : : ; mk; j ) and representing invalid area. This means that operations on the number Aj are performed in the range [0; Pk; j ), and if the result of the RNS operation goes beyond the Pn; j , then there is a conclusion about the calculation error. Checking this rule allows you to localize the error in the data block M~ j of the matrix 0.
Choose a base system p1 = 2; p2 = 3; p3 = 5; p4 = 7 for which the operating range is P4 = p1p2p3p4 = = 2 3 5 7 = 210. Then introduce the control bases p5 = 11; p6 = 13, then the full range is de ned as P6 = P4p5p6 = 210 11 13 = 30030.
Let us calculate the orthogonal bases of the system: B1 = (1; 0; 0; 0; 0; 0) = 15015; B2 = (0; 1; 0; 0; 0; 0) = = 20020; B3 = (0; 0; 1; 0; 0; 0) = 6006; B4 = (0; 0; 0; 1; 0; 0) = 25740; B5 = (0; 0; 0; 0; 1; 0) = 16380; B6 = (0; 0; 0; 0; 0; 1) = 6930.
Given a number A = (1; 2; 2; 3; 6; 4) = 17. Instead of it, after data processing we received A~ = (1; 2; 2; 3; 1; 4). To localize the error, calculate the value of the number A~:
A~ = 1 15015 + 2 20020 + 2 6006 + 3 25740 + 1 16380 + 4 6930 R 30030 = 8207 > 210:
The resulting number is incorrect (A~ > 210), which indicates an error in the processing of data. As a result of localization, it was determined that the number ~5 on the base p5 = 11 was wrong.
After determining the data blocks M~ i and M~ j with broken integrity, a decision is made that an error occurred in the sub-block m~i; j , located at the intersection of the localized row and column of the matrix 0 an error occurred (data integrity violation). After localizing the error ( nding the sub-block m~i; j with integrity violation), we perform a recon guration, the possibility of which is provided by RRNS codes [Yan01].
The recon guration is performed by calculating A from the system of equations: on the \correct" bases of the RNS: = j 1jp1 ; ; A = j njpn ; ; A
= j kjpk ; = j ~1B1; r + : : : + ~nBn; r + : : : + ~kBk; rjPr ; (2) i 1 . . . . . . n k
B1; r 0 . .
.
Pn 1; n p1 . .
.
Pk 1; k p1
A A . . .
. . .
After calculating A on the correct bases of the system, we calculate i instead of the previously excluded from the calculation residue with error ~i:
In accordance with (2) we calculate A (the initial data from Example 1 ), using Table 1, we obtain A = j 1B1; r + : : : + ~5B5; r +
6B6; rjP5 = j1 B1; r + : : : + 0 B5; r + 4 B6; rjP5 = 17: In accordance with (3), we calculate i, we obtain
i = jA jpi = j17j11 = 6:
In the proposed system, a set of sub-blocks m1; j ; m2; j ; : : : ; mn; j ; mn+1; j ; : : : ; mk; j , which is interpreted as RRNS codes that allow to detect an error at any stage of their processing (provided that the multiplicity of the guaranteed error to be detected tdet = dmin 1, where dmin | is the minimum code distance).
Restoration of data blocks Mj0 in case of their integrity violation is possible by excluding from the recovery process any r sub-blocks without sacri cing the unambiguous representation (where r = k n | is the number of additional sub-blocks), so that the system of sub-blocks of data blocks Mj0 will be interpreted as nonsystematic code, or an inseparable code, and then the sub-block is calculated mi; j instead of the previously excluded sub-block m~i; j with the detected error.
Thus, the integrity of the data block Mi was ensured by control and restoring the data sub-block m~i; j with broken integrity. Performing the veri cation of the data validity (reliability, accuracy) after recovery while Bn; r P1 n; 1 pn . . . 0 . .
.
Pk n; k pn . . .
. . . i = jA jpi :
Bk; r P1 k; 1 pk . .
.
Pn k; n pk . . . 0 p2 : : : pn : : : pk
Pr . . . . .
. p1 : : : pn 1pn+1 : : : pk p1 : : : pn : : : pk 1 (3)
Calculating redundant sub-blocks mʹn+1,j, mʹn+2,j,…, mʹk,j
Calculating hash-code Sʹʹi hash-function h(Mʹi) hash-code Si Input Mʹi Input Gʹi
Checking the data blocks integrity Mʹi Calculating hash-code Sʹi ensuring their integrity in case of violation is performed by comparing the value of the previously calculated hash-code Si0 with the value of the calculated hash-code Si00 hash function h(Mi0) already from the restored data block Mi0 (Figure 2).
The general scheme of the developed method of two-dimensional control and data integrity in information systems based on RNSC and cryptographic hash functions is shown in the Figure 3. Evaluation of the developed method is carried out in comparison with the most popular of existing solutions integrated protection of data integrity, which consistently applies rst cryptographic data transformation to control their integrity, and then a backup technology copy data to restore them in case of violation of integrity.
The indicator of quality is the redundancy factor Kred, which is calculated by the formula: where Vr(ecdo.nd) | is the amount of redundant data entered to control the integrity of the protected data, Vr(eads.sd) | is the amount of redundant data entered to assurance the integrity of the protected data, Vprot.d | is the amount of data to be protected. The criterion of quality is Kred ! min.
Since the amount of redundant data Vr(ecdo.nd) introduced to control integrity in the developed method and the existing solution are equal, then (4) takes the form:
Vr(eads.sd) :
In accordance with (5) for the existing solution Kred = 1, since the amount of input redundancy is equal to (5) [Ham80] R. Hamming. Coding and Information Theory. Prentice-Hall, 1980. [ISO08] ISO/IEC 14888{1:2008. Information technology | Security techniques | Digital signatures with appendix | Part 1: General, 2008.