CN105138478A - Memory integrity protection method employing unbalanced hash tree mode - Google Patents

Abstract

The invention relates to the field of memory integrity checking, in particular to a memory integrity protection method employing an unbalanced hash tree mode. The memory integrity protection method comprises the following steps: (1) initialization; (2) building of the unbalanced hash tree; (3) writing operation; and (4) reading operation. According to the method, the check cost is lower than that of an ordinary balanced binary tree in general; and the performance of the method is not higher than the check cost of the ordinary balanced binary tree and is the same as the check cost of the ordinary balanced binary tree even if in the worst case. The path length during data authentication is shortened on the whole.

Description

A Memory Integrity Protection Method for Unbalanced Hash Tree

technical field

The invention relates to the field of memory integrity verification, in particular to a memory integrity protection method of an unbalanced hash tree.

technical background

With the development of science and technology, the application of computers is becoming more and more popular. Since the data processed by computers will involve a lot of confidentiality, ensuring the security of these data processed by computers has become a current research focus. Data security includes confidentiality and integrity. Here the invention only concerns how to ensure the integrity of the data. Attackers can perform spoofing, reassembly, and replay attacks on the data flowing on the bus. Integrity protection is to ensure that malicious tampering of data by attackers, such as hardware piggyback attacks, can be detected. The focus is on protecting information from replay attacks. Replay attack means that the attacker replaces the data previously stored in a certain address unit with the current data. At present, the defense against replay attacks is mainly through the use of tree verification mechanisms. According to the method used by the authentication unit and the tree construction process, it can be divided into three schemes: MerkleTree, parallel verification tree PATtree and TEC-Tree.

MerkleTree, also known as HashTree, is a tree mechanism that was first used for integrity verification. It was proposed by Merkle in 1980 and is mainly used for efficient calculation problems in public key systems. Blum et al. modified it for use in integrity checking of memory contents. It builds a tree by performing iterative hash calculation on memory data blocks, and saves the root node on the CPU to ensure data integrity, especially to resist replay attacks. The disadvantage is that data block updates cannot be calculated in parallel, so the delay is relatively large. Aiming at this shortcoming, a parallel verification tree PAT is proposed. Since this method corresponds to a random number every time the hash calculation is performed, the calculation of the high-level nodes does not directly depend on the low-level nodes. The upper-level nodes pass the random number of the sub-nodes The MAC is calculated after the number of connections, so it realizes the parallel calculation when the data is updated. However, MerkleTree and PAT trees can only guarantee the integrity of data, that is, their integrity protection and confidentiality protection schemes are separated. To address this shortcoming, TEC-Tree is proposed, which adds redundant data to the data to ensure data integrity. Integrity also ensures data confidentiality.

A common feature of these three trees is that the trees they build are all balanced trees, and the check path lengths of all data blocks are the same. Although a cache hash tree CHTree has been proposed, which saves some upper-level nodes of the MerkleTree in the cache, although this method can effectively shorten the verification length, the verification path length of data blocks with high access frequency and low access frequency Still the same, so on average the block is still hashed with a lot of latency.

Contents of the invention

The purpose of the present invention is to provide a memory integrity protection method of an unbalanced hash tree which shortens the average check path length of the leaf nodes in the tree.

The purpose of the present invention is achieved like this:

(1) Initialization

(1.1) Divide the memory into data blocks data_block[i] of the same size, and each data block has a counter counter[i] to record the number of read/write times of the data block; initially, counter[i]=0, when When the processor reads and writes the data block data_block[i], the counter value counter[i]=counter[i]+1; the data block structure adopts 3 linked lists:

(1.2) Set a timer Time; when the timer reaches the set time, build an unbalanced binary tree, and simultaneously clear the counters of all data blocks data_block to zero, and recount;

(2) Build an unbalanced binary tree

(2.1) Taking the read/write times of n data blocks in the memory as weights, n weights {w ₁ ,w ₂ ,w ₃ ,w ₄ ,w ₅ ,...w _n } are obtained, and each weight Values constitute a tree T _i with only root nodes, then get a collection of n trees F={T ₁ , T ₂ , T ₃ , T ₄ , T ₅ ,...T _n };

(2.2) Select two trees T _i and T _j with the smallest weight from the set F, and construct a new tree T as the left and right children. The weight of the new tree T node is the sum of the weights of the two child nodes; Delete T _i and T _j from the set F, and add the tree T to the set F;

(2.3) Repeat step (2.2) until only one tree remains in the set F;

(3) Write operation

(3.1) When the CPU writes the data block data_block[i] to the memory, update the counter counter[i]=counter[i]+1;

(3.2) Find the pointer of the corresponding leaf node of the data block data_block[i];

(3.3) Connect the data block and the data block corresponding to the brother node, recalculate the hash value hash after the data block connection, update the hash value of the parent node, repeat (3.1)—(3.3) until the root node;

(3.4) Check whether the timer Time reaches the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the write operation ends;

(4) Read operation

(4.1) When the CPU reads the memory data block data_block[i], update its counter counter[i]=counter[i]+1;

(4.2) Find the pointer of the corresponding leaf node of the data block data_block[i];

(4.3) Connect the data block and the data block corresponding to the sibling node, then calculate the hash value hash after the data block connection, compare the hash result with the hash value of the parent node, repeat this process until the root node, if The hash value of the root node calculated at the end is the same as the hash value of the root node stored in the CPU, which means that the data is correct and has not been tampered with, and the CPU can use the data; otherwise, it means that the data has been tampered with and an alarm is issued;

(4.4) Check whether the timer Time reaches the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the read operation ends.

The beneficial effects of the present invention are:

The present invention shortens the path length during data authentication as a whole.

In the process of building an unbalanced binary tree, there will be three situations. The first is the general situation listed in Figure 1. In this case, it has been proved that the method in this paper is smaller than the average check length of an ordinary balanced binary tree. . In addition to the general situation, there are two extreme situations in the process of building an unbalanced binary tree, namely:

(1) The constructed tree is the same as the original balanced binary tree. In this case their verification costs are the same.

(2) The unbalanced binary tree constructed is a single branch binary tree. In this case, the verification cost of an unbalanced binary tree is lower than that of an ordinary balanced binary tree.

In summary, under normal circumstances, the verification cost of this method is lower than that of ordinary balanced binary trees. Even in the worst case, the performance of this method will not be higher than that of ordinary balanced binary trees. The cost is the same as its verification cost.

Description of drawings

Figure 1 shows a balanced binary tree and an unbalanced binary tree.

Figure 2 shows the steps of building an unbalanced binary tree.

Figure 3 shows the steps of writing data into the memory.

Figure 4 shows the steps of reading data from memory.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings.

The invention relates to the field of memory integrity verification, and relates to a memory integrity protection method of an unbalanced hash tree based on the principle of locality. In order to prevent replay attacks, tree structures are currently used to protect data integrity. The trees currently used are all balanced N-ary trees, and all leaf nodes are at the same level in the tree, that is, the check path lengths of all data blocks are the same. According to the locality principle of the program, some data access frequency is high and some data access frequency is low within a period of time. Therefore, the present invention improves the hash tree and establishes an unbalanced binary tree, so that those nodes with high access frequency are close to the root node, and those nodes with low access frequency are far away from the root node. In this way, the verification path of data blocks with high access frequency is short, and the verification path of data blocks with low access frequency is long. On the whole, the verification path is shortened and the delay is reduced.

In order to shorten the average check path length of the leaf nodes in the tree, the invention proposes a memory integrity protection method of the unbalanced hash tree. According to the principle of program locality, the access frequency of data in the memory is different within a period of time. Some data access frequency is higher, and some data access frequency is lower. Therefore, the method proposed by the present invention is to build an unbalanced binary tree, and place those data blocks with high frequency of recent access near the root node, on the contrary, those data blocks that are not frequently used are placed far away from the root node. The place. Reduce the average checksum path length of data blocks. As shown in Figure 1 (the number on the leaf node is the number of visits).

The present invention divides the memory into data blocks data_block[i] of the same size, and sets a counter counter[i] for each data block to record the times of reading/writing to the data block. While storing the data block in the memory, store the pointer of the corresponding leaf node, and the leaf node is the hash value of the data block. Set a timer Time, when the timer Time reaches the set time, build an unbalanced hash tree with the hash value of the memory data block as the leaf node, and change the pointer of the corresponding leaf node every time the leaf node is moved, and The root node of the hash tree is reserved in the CPU for integrity verification.

The specific operation of building an unbalanced hash tree is as follows:

(1) Taking the read/write times of n data blocks in the memory as weights, n weights {w ₁ ,w ₂ ,w ₃ ,w ₄ ,w ₅ ,...w _n } are obtained, and each weight Values constitute a tree T _i with only root nodes, then get a set F={T ₁ , T ₂ , T ₃ , T ₄ , T ₅ ,...T _n } with n trees.

(2) Select two trees T _i and T _j with the smallest weight from the set F, and use them as the left and right children to construct a new tree T. The weight of the new tree T node is the sum of the weights of the two child nodes . Delete T _i and T _j from set F, and add tree T to set F.

(3) Repeat step (2) until there is only one tree left in the set F.

When the processor writes the data block data_block[i] into the memory, the access count counter[i] of the data block and the entire hash tree are updated. The specific operation is as follows:

(1) When the CPU writes the data block data_block[i] into the memory, it updates its counter counter[i]=counter[i]+1.

(2) Then find the pointer of the corresponding leaf node of the data block data_block[i].

(3) Connect the data block and the data block corresponding to the brother node, recalculate the hash value hash after the data block connection, update the hash value of the parent node, and repeat this process until the root node.

(4) Check whether the timer Time reaches the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the write operation ends.

When the processor reads the data block data_block[i] from the memory, it updates its counter counter[i], and at the same time checks the integrity of the data. The specific operation is as follows:

(1) When the CPU reads the memory data block data_block[i], it updates its counter counter[i]=counter[i]+1.

(2) Then find the pointer of the corresponding leaf node of the data block data_block[i].

(3) Connect the data block and the data block corresponding to the sibling node, then calculate the hash value hash after the data block connection, compare the hash result with the hash value of the parent node, repeat this process until the root node, if The hash value of the root node calculated at the end is the same as the hash value of the root node stored in the CPU, which means that the data is correct and has not been tampered with, and the CPU can use the data; otherwise, it means that the data has been tampered with and an alarm is issued.

(4) Check whether the timer Time has reached the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the read operation ends.

Use the weighted check length of the tree (the sum of the weighted check lengths of all leaf nodes in the tree) as the standard for performance comparison, expressed in WPL, that is The weight w _i is the read/write times of each leaf node, and l _i is the check length of the leaf node, that is, the number of branches on the path. n is the number of nodes.

The hash tree is rebuilt according to the read and write frequency of data blocks, not the number of reads and writes.

Before introducing the content of the present invention, the following definitions are provided:

Weight: the number of read/write times of the data block, represented by w.

The weighted check length of a node: the product of the check length from the node to the root node of the tree and the weight on the node, represented by WPL, that is, WPL _i =w _i *I _i .

The weighted check length of the tree: the sum of the weighted check lengths of all leaf nodes in the tree, expressed in WPL, that is $WPL={\mathrm{\Σ}}_{i=1}^{i=\mathrm{no}}{w}_i*l_i.$

Divide the memory into data blocks data_block[i] of the same size, and set a counter counter[i] for each data block to record the number of read/write times for the data block. While storing the data block in the memory, store the pointer of the corresponding leaf node, and the leaf node is the hash value of the data block. Set a timer Time, when the timer Time reaches the set time, build an unbalanced hash tree with the hash value of the memory data block as the leaf node, and change the pointer of the corresponding leaf node every time the leaf node is moved, and The root node of the hash tree is reserved in the CPU for integrity verification.

When constructing an unbalanced hash tree, according to the given n weights {w ₁ ,w ₂ ,w ₃ ,w ₄ ,w ₅ ,…w _n }, select two weights with the smallest weight from the middle each time Data blocks, as the left and right subtrees of the binary tree, the weight of the parent node is the sum of the weights of the child nodes, and at the same time delete the two selected nodes with the smallest weight, and use the newly generated binary tree as a new Trees are added to the above set. Repeat the above process until there is only one tree.

The memory integrity verification method is implemented through the following process:

1) Initialization

(1) Divide the memory into data blocks of the same size data_block[i], and each data block has a counter counter[i] to record the number of read/write times of the data block. Initially, counter[i]=0, when the processor reads and writes the data block data_block[i], its counter value counter[i]=counter[i]+1.

(2) The data structure adopts 3 linked lists, as follows:

node

{

longintcounter; //Read/write times, as the weight of the data block

longinthash; // hash value

Structnode *lchild; // left child

Structnode *rchild; //right child

Structnode*parent;//parent node

} node;

(3) Set up a timer Time. When the timer reaches the set time, build an unbalanced binary tree, and at the same time clear the counters of all data blocks data_block to make them count again.

2) Build an unbalanced binary tree

The process for the processor to build an unbalanced binary tree is shown in Figure 2, and the specific operations are as follows:

(1) Taking the read/write times of n data blocks in the memory as weights, n weights {w ₁ ,w ₂ ,w ₃ ,w ₄ ,w ₅ ,...w _n } are obtained, and each weight Values constitute a tree T _i with only root nodes, then get a set F={T ₁ , T ₂ , T ₃ , T ₄ , T ₅ ,...T _n } with n trees.

(2) Select two trees T _i and T _j with the smallest weight from the set F, and use them as the left and right children to construct a new tree T. The weight of the new tree T node is the sum of the weights of the two child nodes . Delete T _i and T _j from set F, and add tree T to set F.

(3) Repeat step (2) until there is only one tree left in the set F.

3) Write operation

When the processor writes the data block data_block[i] into the memory, the access count counter[i] of the data block and the entire hash tree are updated. The process for the processor to write to the memory is shown in Figure 3, and the specific operations are as follows:

(1) When the CPU writes the data block data_block[i] into the memory, it updates its counter counter[i]=counter[i]+1.

(2) Then find the pointer of the corresponding leaf node of the data block data_block[i].

(3) Connect the data block and the data block corresponding to the brother node, recalculate the hash value hash after the data block connection, update the hash value of the parent node, and repeat this process until the root node.

(4) Check whether the timer Time reaches the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the write operation ends.

4) Read operation

When the processor reads the data block data_block[i] from the memory, it updates its counter counter[i], and at the same time checks the integrity of the data. The process for the processor to read the memory is shown in Figure 4, and the specific operations are as follows:

(1) When the CPU reads the memory data block data_block[i], it updates its counter counter[i]=counter[i]+1.

(2) Then find the pointer of the corresponding leaf node of the data block data_block[i].

(3) Connect the data block and the data block corresponding to the sibling node, then calculate the hash value hash after the data block connection, compare the hash result with the hash value of the parent node, repeat this process until the root node, if The hash value of the root node calculated at the end is the same as the hash value of the root node stored in the CPU, which means that the data is correct and has not been tampered with, and the CPU can use the data; otherwise, it means that the data has been tampered with and an alarm is issued.

(4) Check whether the timer Time has reached the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the read operation ends.

Below is the concrete implementation content of the present invention:

The content of the present invention uses the simulator SimpleScalartool to realize the content of the algorithm proposed by the present invention, and the specific implementation pseudocode of each step algorithm is introduced respectively below.

1. Build an unbalanced binary tree

The process for the processor to build an unbalanced binary tree is shown in Figure 2, and the specific operations are as follows:

(1) Taking the read/write times of n data blocks in the memory as weights, n weights {w ₁ ,w ₂ ,w ₃ ,w ₄ ,w ₅ ,...w _n } are obtained, and each weight Values constitute a tree T _i with only root nodes, then get a set F={T ₁ , T ₂ , T ₃ , T ₄ , T ₅ ,...T _n } with n trees.

(2) Select two trees T _i and T _j with the smallest weight from the set F, and use them as the left and right children to construct a new tree T. The weight of the new tree T node is the sum of the weights of the two child nodes . Delete T _i and T _j from set F, and tree T is added to set F.

(3) Repeat step (2) until there is only one tree left in the set F.

The specific implementation code for building an unbalanced binary tree is shown in Algorithm 1.

2. Write data to memory

When the processor writes the data block data_block[i] into the memory, the access count counter[i] of the data block and the entire hash tree are updated. The process for the processor to write to the memory is shown in Figure 3, and the specific operations are as follows:

(1) When the CPU writes the data block data_block[i] into the memory, it updates its counter counter[i]=counter[i]+1.

(2) Then find the pointer of the corresponding leaf node of the data block data_block[i].

(3) Connect this data block with the data block corresponding to the brother node, recalculate the hash value hash after the data block connection, update the hash value of the parent node, and repeat this process until the root node.

(4) Check whether the timer Time reaches the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the write operation ends.

The specific implementation process when writing a data block into the memory is shown in Algorithm 2.

3. Read data from memory

When the processor reads the data block data_block[i] from the memory, it updates its counter counter[i], and at the same time checks the integrity of the data. The process for the processor to read the memory is shown in Figure 4, and the specific operations are as follows:

(1) When the CPU reads the data block data_block[i] from the memory, it updates its counter counter[i]=counter[i]+1.

(2) Then find the pointer of the corresponding leaf node of the data block data_block[i].

(3) Connect this data block with the data block corresponding to the sibling node, then calculate the hash value hash after the data block connection, compare the hash result with the hash value of the parent node, and repeat this process until Root node, if the calculated hash value of the root node is the same as the hash result of the root node stored on the CPU, it means that the data is correct and has not been tampered with, and the CPU can use the data; otherwise, it means that the data has been tampered with ,Alert.

(4) Check whether the timer Time has reached the set time, if it has reached the set time, re-establish the unbalanced hash tree, otherwise, the read operation ends.

The specific implementation process when reading a data block from memory is shown in Algorithm 3.

.

Claims (1)

1. a memory integrity protection method for non-equilibrium Hash tree, is characterized in that, comprises the steps:

(1) initialization

(1.1) internal memory is divided into the data block data_block [i] of formed objects, each data block has a counter counter [i] to record read/write number of times to this data block; Time initial, counter [i]=0, when processor reads and writes data block data_block [i], Counter Value counter [i]=counter [i]+1; Block data structure adopts 3 linked list type:

(1.2) a timer Time is set; After timer arrives the time of setting, build a non-equilibrium binary tree, the counter counter of all data block data_block is all reset simultaneously, again count;

(2) non-equilibrium binary tree is built

(2.1) using the read/write number of times of the data block of n in internal memory as weights, then obtain n weights { w ₁, w ₂, w ₃, w ₄, w ₅... w _n, each weights form the tree T that is only had root node _i, then the set F={T of n tree is obtained ₁, T ₂, T ₃, T ₄, T ₅... T _n;

(2.2) from set F, choose two tree T that weights are minimum _iand T _j, build a new tree T as left and right child, the weights of new tree T node are two child nodes weights sums; T is deleted from set F _iand T _j, and tree T is added in set F;

(2.3) step (2.2) is repeated, until only remaining one tree in set F;

(3) write operation

(3.1) when CPU is to internal memory writing data blocks data_block [i], refresh counter counter [i]=counter [i]+1;

(3.2) pointer of the respective leaves child node of data block data_block [i] is found;

(3.3) connection data block and the data block corresponding to sibling, recalculates the cryptographic hash hash after data block connects, upgrades the cryptographic hash of father node, repeats (3.1)-(3.3) until root node;

(3.4) check whether timer Time arrives setting-up time, if arrive setting-up time, then re-establish non-equilibrium Hash tree, otherwise write operation terminates;

(4) read operation

(4.1) as CPU rdma read data block data_block [i], its counter counter [i]=counter [i]+1 is upgraded;

(4.2) pointer of the respective leaves child node of data block data_block [i] is found;

(4.3) connection data block and the data block corresponding to sibling, then the cryptographic hash hash after data block connects is calculated, the cryptographic hash of Hash result and father node is compared, repeat this process until root node, if the cryptographic hash of the last root node calculated is identical with the cryptographic hash of the root node stored in CPU, then illustrate that data are correct, are not tampered, CPU can usage data; Otherwise, then illustrate that data are tampered, and give the alarm;

(4.4) check whether timer Time arrives setting-up time, if arrive setting-up time, then re-establish non-equilibrium Hash tree, otherwise read operation terminates.