JP6212377B2 - Arithmetic device, arithmetic method and computer program - Google Patents

Description

  The present invention relates to an arithmetic device, an arithmetic method, and a computer program.

  In recent years, when a program is executed by a computer, a technique for obfuscating source code and variables is known in order to protect important information handled by the program (see, for example, Non-Patent Document 1). Although protection of information by this obfuscation is effective for static analysis such as disassembly, the effect is limited for dynamic analysis in which analysis is performed while executing a program. As an effective technique for the dynamic analysis, for example, "Oblivious RAM" described in Non-Patent Document 2 is known. However, "Oblivious RAM" is effective against memory attacks, but it can not guarantee security against attacks that extract data from CPU registers.

Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang, “On the (Im) Possibility of Obfuscating Programs”, CRYPTO 2001, Lecture Notes in Computer Science Volume 2139, 2001, pp 1- 18, 2001. Oded Goldreich and Rafail Ostrovsky, “Software protection and simulation on oblivious rams”, J. ACM, 43 (3): pp 431-473, 1996.

  As described above, in the prior art, if the important information itself is held in the register used at the time of operation, the attacker may obtain the important information from the register.

  The present invention has been made in consideration of such circumstances, and provides an arithmetic device, an arithmetic method, and a computer program that can prevent important information itself from being held in a register used at the time of arithmetic operation. It will be an issue.

(1) The arithmetic device according to the present invention inputs input arithmetic expression information indicating an input arithmetic expression, and a pre-obfuscated vector obtained by obfuscating the pre-obfuscation vector used in the input arithmetic expression. The value of the element of the pre-obfuscation operation vector, the obfuscation operation parameter used for the obfuscation operation of calculating the post-obfuscation operation vector from the pre-obfuscation operation vector after the obfuscation operation. The obfuscated operation parameter calculation unit calculates using an obfuscated operation parameter calculation formula that does not appear and the obfuscated operation that calculates an after obfuscated vector from the before obfuscated vector using the obfuscated operation parameter includes and obfuscation calculating unit, wherein the obfuscation operation parameter equation, the input arithmetic expression represented using the obfuscation after the operation before vector, a plurality of exclusive OR and a plurality of exclusive theory When it is calculated by leaving at least one exclusive disjunction for each of the terms when it is expressed by an expression which operates with a binary operator represented by the input operation formula with the sum as a single term, respectively It is characterized in that it is configured .

( 2 ) In the calculation method according to the present invention, the calculation device outputs input calculation formula information indicating an input calculation formula, and a pre-obfuscation calculation vector before obfuscation used in the input calculation formula is obfuscated calculation after obfuscation The obfuscation operation parameter used in the obfuscation operation in which an input step for inputting a previous vector and the arithmetic device calculate the obfuscated vector after the obfuscation from the pre-obfuscation vector after the obfuscation is performed as the obfuscation operation parameter An obfuscated operation parameter calculating step of calculating using an obfuscated operation parameter calculation formula in which the value of the element of the pre-previous vector does not appear, and the pre-obfuscated vector before the operation using the obfuscated operation parameter see containing and obfuscation operation step of performing obfuscation operation for calculating the obfuscation after the operation after vector, from said obfuscated operational parameter calculation formula, use the obfuscation after computation before vector When the input arithmetic expression represented by the equation (1) is expressed by an expression that operates with a binary operator represented by the input arithmetic expression, each having a plurality of exclusive ORs and a plurality of exclusive ORs as one term, It is characterized in that it is calculated so as to be left with at least one exclusive OR for each of the above terms .

( 3 ) The computer program according to the present invention is a computer program that allows input operation expression information indicating an input operation expression and a pre-obfuscation operation pre-operation vector used in the input operation expression is obfuscated before operation. An obfuscation operation parameter used in an obfuscation operation to calculate a vector after the obfuscation operation from the vector before the obfuscation operation, and an input step for inputting a vector, and an obfuscation operation parameter used in the obfuscation operation The obfuscation calculation parameter calculation step of calculating using the obfuscation calculation parameter calculation formula in which the value does not appear, and the obfuscation calculation of calculating the post-obfuscation calculation vector from the pre-obfuscation calculation vector using the obfuscation calculation parameter and obfuscation operation step of performing arithmetic operation, is executed, the obfuscation operation parameter equation is expressed using the obfuscation after computation before vector Each said one term when said input arithmetic expression is represented by the formula calculated with the binary operator shown by the said input arithmetic expression by making each of several exclusive OR and several exclusive OR into one term. And a computer program configured to be calculated leaving at least one exclusive OR .

  According to the present invention, it is possible to prevent the important information itself from being held in the register used at the time of operation.

It is a block diagram showing composition of arithmetic unit 10 concerning one embodiment of the present invention. It is a figure which shows the example of the program which calculates the carry (bit string C) which concerns on one Embodiment of this invention. It is a figure which shows a part of example of a program when calculating the obfuscation calculation parameter of the division operator which concerns on one Embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  First, an outline of the present embodiment will be described. The obfuscation algorithm according to the present embodiment is shown in [Equation 1], and the decryption algorithm is shown in [Equation 2].

However, x is an integer value vector before obfuscation. y is an obfuscated integer value vector. The elements of the integer value vector x, y are integer values, and are represented using subscripts i, j, k, etc., for example, x _i , x _j , x _k etc. b is an arbitrary vector whose element is 0 or 1; A is a matrix represented by [Equation 3]. A ⁻¹ is a generalized inverse matrix of A represented by [Equation 4]. The sums used for matrix calculation are all exclusive ORs.

  In the present embodiment, when performing an operation on the important information, the operation (obfuscation operation) with the important information being obfuscated is performed to prevent the important information itself from being held in the register used at the time of the operation. The relationship between a set (vector) of each variable before and after obfuscation and before and after operation is expressed by [Equation 5].

  However, the vector of each variable is expressed by [Equation 6], [Equation 7], [Equation 8], and [Equation 9].

  Further, an arithmetic expression by an arbitrary binary operator Op is represented by [Equation 10].

  In [Equation 10], the binary operator Op is referred to as a non-assignment operator when the subscripts i and k have different values, and the binary operator Op when the subscripts i and k have the same value. Is called an assignment operator. For example, "+" in [Equation 11] is a non-assignment operator. On the other hand, since [Equation 12] means [Equation 13], “+ =” in [Equation 12] is an assignment operator.

In the case of the non-assignment operator, the post-obfuscation post-operation vector y ^new corresponding to x _k in [Equation 10] is represented by [Equation 14].

  However, Z is represented by [Equation 15].

Also in the case of the assignment operator, the post-obfuscation post-operation vector y ^new corresponding to x _k in [Equation 10] is expressed by the above [Equation 14]. However, Z in the case of the assignment operator is represented by [Equation 16].

  Z of [Equation 14] related to the above-mentioned non-assignment operator and Z of [Equation 16] related to the assignment operator can be generalized as shown in [Equation 17].

Here, if each term of Z in [Equation 17] is calculated as it is, the values of x _i , x _j , and x _k in [Equation 10] are held in the register, and the obfuscated meaning is lost. For this reason, for example, when calculating the value of [Equation 18], it may be calculated to become two terms as shown in [Equation 19], but the value of [Equation 19] should not be calculated.

Therefore, in the present embodiment, Z (obfuscation operation) used for the obfuscation operation when calculating the post-obfuscation vector y ^new after the obfuscation operation from the after-obfuscation vector y ^{old according} to [Equation 14] (obfuscation operation) Calculation of obfuscated calculation parameters to calculate parameters). In this obfuscation calculation parameter calculation, the values of x _i , x _j and x _k in [Equation 10] are not held in the register.

For this purpose, the obfuscated operation parameter calculation equation for calculating the obfuscated operation parameter Z is a binary operator of the input operation equation ([Equation 15], [Equation 16]) expressed using the pre-obfuscated vector y ^old. The terms relating to Op) have a plurality of exclusive disjunctions (exclusive disjunction on α of [Equation 17]) and multiple exclusive disjunctions (exclusive OR on β of [Equation 17]) as a single term At least one exclusive-OR for each term when it is expressed by an expression (a term related to the binary operator Op in [Equation 17]) operated by the binary operator Op indicated by the input operation expression Configured to be calculated leaving.

  [Equation 20] is used as a relational expression relating to the obfuscation calculation parameter calculation.

Here, α _n is the n-th number when α is binary-expanded. & Represents a logical product (AND). << represents a left shift.

Next, the arithmetic device according to the present embodiment will be described. FIG. 1 is a block diagram showing the configuration of an arithmetic unit 10 according to an embodiment of the present invention. In FIG. 1, the arithmetic device 10 includes an input unit 11, an obfuscated operation parameter calculator 12, and an obfuscated operation unit 13. The input unit 11 inputs the input arithmetic expression information and the pre-obfuscated vector y ^old . The input arithmetic expression information is information indicating the binary operator Op of [Equation 10]. The pre-obfuscation pre-operation vector y ^old is used in [ ^Equation 14].

The obfuscation calculation parameter calculation unit 12 uses the input operation formula information and the pre-obfuscated vector y ^old input from the input unit 11 to perform the obfuscation corresponding to the binary operator Op indicated by the input operation formula information. Calculate calculation parameter Z. The obfuscation operation unit 13 calculates [Equation 14] using the pre-obfuscated vector y ^old input from the input unit 11 and the obfuscated operation parameter Z calculated by the obfuscated operation parameter calculation unit 12. The matrix A used in [Equation 14] is held in advance by the obfuscation operation unit 13. The obfuscation operation unit 13 outputs the post-obfuscation post-operation vector y ^new which is the calculation result of [Equation 14].

  Hereinafter, an embodiment of a method of calculating the obfuscation calculation parameter Z corresponding to each binary operator Op will be described.

  First, arithmetic operators will be described.

[Addition operator (+)]
The obfuscation operation parameter Z corresponding to the addition operator (non-assignment operator) is expressed by [Equation 21] corresponding to [Equation 15].

  However, N is the number of digits of the bit string.

  Then, in the above [Equation 21], [Equation 22] is obtained.

The obfuscated calculation parameter Z of the above [Equation 22] can be calculated by the following procedures 1 and 2.
Step 1: Create bit string C from I and J.
Step 2: Calculate [Equation 23].

The details of the procedure 1 for producing the bit string C are as follows.
Procedure 1-1: The first (least significant) bit of the bit string C is set to 0. After that, if the condition of procedure 1-2 is not satisfied, the upper direction is set to 0 all the time.
Step 1-2: When looking at bit strings of I and J from right (lower bit) to left (upper bit), if both I and J are 1 at first, the bit next to it (one upper) It is assumed to be 1. After that, if the condition of the procedure 1-3 is not satisfied, the upper direction is set to 1 all the time.
Procedure 1-3: If the bit strings of I and J are both 0, the next (upper one) bit is set to 0.

  Procedure 1 (Procedures 1-1, 1-2, and 1-3) of creating the bit string C is carried out by carrying the arithmetic sum of integer type (here short type) variables I and J without using exclusive OR. (Bit string C) is calculated. Carry (bit string C) satisfies [Equation 24].

  FIG. 2 shows an example of a C language program for calculating carry (bit string C).

  Further, the obfuscation operation parameter Z corresponding to the addition assignment operator may be made to correspond to the [Equation 16], and the [Equation 25] may be calculated in the above-mentioned procedure 2.

[Subtraction operator (-)]
The obfuscation operation parameter Z corresponding to the subtraction operator (non-assignment operator) is expressed by [Equation 26] corresponding to [Equation 15].

  In the above [Equation 26], Z 'is expressed by [Equation 27].

  However, N is the number of digits of the bit string.

  Then, in the above [Equation 27], [Equation 28] is obtained.

  The obfuscation operation parameter Z corresponding to the subtraction operator (non-assignment operator) is calculated by this [Equation 28]. The bit string C in [Equation 28] can be calculated in the same manner as in step 1 of the calculation of the obfuscation operation parameter Z of the addition operator.

  In addition, the obfuscation operation parameter Z corresponding to the subtraction / assignment operator may be calculated by using [Equation 29] corresponding to [Equation 16].

[Multiplication operator (x)]
The obfuscation operation parameter Z corresponding to the multiplication operator (non-assignment operator) is represented by [Equation 30] corresponding to [Equation 15].

  In the above [Equation 30], Z 'is expressed by [Equation 31].

  However, N is the number of digits of the bit string.

  And in said [Equation 31], it becomes [Equation 32].

  According to this [Equation 32], the obfuscation operation parameter Z corresponding to the multiplication operator (non-assignment operator) is calculated. The bit string C in [Equation 32] can be calculated in the same manner as in step 1 of the calculation of the obfuscation operation parameter Z of the addition operator.

  In addition, the obfuscation operation parameter Z corresponding to the multiplication assignment operator may calculate [Equation 33] corresponding to [Equation 16].

Division operator (/)
The obfuscation operation parameter Z corresponding to the division operator (non-assignment operator) is expressed by [Equation 34] corresponding to [Equation 15].

  Further, the obfuscation operation parameter Z corresponding to the division assignment operator is expressed by [Equation 35] corresponding to [Equation 16].

The obfuscation calculation parameter Z of the above [Equation 34] and [Equation 35] can be calculated by the following procedures A1 to A5.
Step A1: Set [Equation 36].

  Procedure A2: Starting from “n = 0”, first obtain n that satisfies [Equation 37].

  Step A3: Set [Equation 38].

Step A4: The loop process of FIG. 3 is performed.
Step A5: [Equation 39] is calculated to obtain the obfuscation operation parameter Z corresponding to the division operator (non-assignment operator). In order to obtain the obfuscation operation parameter Z corresponding to the division assignment operator, [Equation 40] is calculated.

[Modulus operator (%)]
The remainder operator (non-assignment operator) calculates [Equation 41].

  Here, [Equation 42] is obtained using the calculation algorithm of the division operator described above.

  [Equation 41] becomes [Equation 43] according to [Equation 42].

  However, N is the number of digits of the bit string.

  Then, in the above [Equation 43], it is [Equation 44].

  The obfuscation operation parameter Z corresponding to the remainder operator (non-assignment operator) is calculated by this [Equation 44]. The bit string C in [Equation 44] can be calculated in the same manner as in Procedure 1 of the calculation of the obfuscation operation parameter Z of the addition operator.

  In addition, the obfuscation operation parameter Z corresponding to the remainder assignment operator may be calculated by [Equation 45] corresponding to [Equation 16].

  Next, comparison operators will be described. In addition, in the calculation of the comparison operator, since the output may not be available as it is obfuscated, such as control by an iF statement, the output of the comparison operator is not obfuscated.

The obfuscation operation of the comparison operator is performed as follows.
When comparing a and b, “ab” is expressed by [Equation 46].

  The magnitude of a and b can be determined by examining the positive / negative of the value of this [Equation 46].

[Less than (<)]
The output “1 (true)” is set when “a−b <0”, and the output “0 (false)” is set otherwise.

[Less than equal operator (<=)]
The output “1 (true)” is set when “a−b <= 0”, and the output “0 (false)” is set otherwise.

[Major operator (>)]
The output “1 (true)” is set when “a−b> 0”, and the output “0 (false)” is set otherwise.

[Large equal operator (> =)]
The output “1 (true)” is set when “a−b> = 0”, and the output “0 (false)” is set otherwise.

[Not equal operator (! =)]
The output “1 (true)” is set when “a−b! = 0”, and the output “0 (false)” is set otherwise.
[Equal operator (==)]
The output “1 (true)” is set when “a−b = 0”, and the output “0 (false)” is set otherwise.

  Next, bit operators will be described.

[Left / right shift operator (S (left shift (<<), right shift (>>)))]
The obfuscation operation parameter Z corresponding to the left / right shift operator (non-assignment operator) is expressed by [Equation 47] corresponding to [Equation 15].

  Further, the obfuscation calculation parameter Z corresponding to the left / right shift assignment operator (Sa) is expressed by [Equation 48] corresponding to [Equation 16].

[Bit product operator (&)]
The obfuscation operation parameter Z corresponding to the bit product operator (non-assignment operator) is represented by [Equation 49] corresponding to [Equation 15].

  Further, the obfuscation operation parameter Z corresponding to the bit product assignment operator is expressed by [Equation 50] corresponding to [Equation 16].

Bitwise Sum Operator (|)
The bit sum operator is represented by [Equation 51].

  The obfuscation operation parameter Z corresponding to the bit sum operator (non-assignment operator) is expressed by [Equation 52] corresponding to [Equation 15] by this [Equation 51].

  Further, the obfuscation operation parameter Z corresponding to the bit sum substitution operator is expressed by [Equation 53] corresponding to [Equation 16].

[Bit exclusive OR operator (XOR)]
In the case of bit exclusive OR operator (non-assignment operator), since the operation is commutative, it can be obfuscated simply by exchanging the order of operations. Thus, the obfuscation operation parameter Z corresponding to the bit exclusive OR operator (non-assignment operator) is represented by [Equation 54] corresponding to [Equation 15].

On the other hand, in the case of the bit exclusive OR assignment operator, [Equation 16] can not be applied. This is because x _j will be held in the register as expressed in [Equation 55] when [Equation 16] is applied.

Therefore, noting that the element a _{ij of the} matrix A is 0 or 1, the obfuscation operation of the bit exclusive OR assignment operator is performed by [Equation 56].

In [Equation 56], the part shown by [Equation 57] is divided. Then, with respect to the divided portions, the order of operations is exchanged as in the case of the bit exclusive OR operator (non-assignment operator) described above. Thus, x _j can be calculated without being held in the register.

Next, the simple assignment operator will be described as another operator. As an example of a simple assignment operator, take “x _i = x _j ” that assigns the value of x _j to x _i . In this case, the obfuscation calculation parameter Z is expressed by [Equation 58].

Therefore, the obfuscation operation parameter Z corresponding to the simple assignment operator “x _i = x _j ” is calculated by [Equation 59].

  The above is the description of the example of the calculation method of the obfuscation calculation parameter Z according to the present embodiment.

According to the above-described embodiment, obfuscation operation parameter calculation unit 12 of the arithmetic unit 10 is used obfuscation after the operation after vector y ^{new new} later obfuscation operation before vector y ^old in obfuscation operation of calculating remain obfuscated that obfuscation operation parameter Z, is calculated using the obfuscation before the operation before the vector x ^old element value does not appear obfuscation operation parameter calculation formula. The obfuscation operation unit 13 performs its use obfuscation operation parameter Z, the obfuscation operation for calculating the obfuscation after the operation after vector y ^{new new} later obfuscation operation before vector y ^old. Thereby, it is possible to prevent the important information (the value of the element of the pre-obfuscation operation vector ^xold ) itself from being held in the register used at the time of operation. This contributes to protecting the key used for encryption, the personal information used for authentication, etc., which are important information on security, by using the computing device 10 for the encryption device, authentication device, etc. it can.

  Note that the arithmetic unit 10 according to the present embodiment may be realized by dedicated hardware, or may be configured by a memory and a CPU (central processing unit) to realize the functions of the arithmetic unit 10. The function may be realized by the CPU executing the program of

  Although the embodiments of the present invention have been described in detail with reference to the drawings, the specific configuration is not limited to this embodiment, and design changes and the like within the scope of the present invention are also included.

  For example, the arithmetic device 10 according to the present embodiment is applicable to various applications. For example, by applying the arithmetic device 10 according to the present embodiment to an application that performs arithmetic processing using secret information such as encryption processing and authentication processing, an effect of contributing to protection of the secret information is obtained. can get.

  Alternatively, a computer program for realizing the above-described arithmetic device 10 may be recorded in a computer readable recording medium, and the program recorded in the recording medium may be read into a computer system and executed. Note that the “computer system” referred to here may include an OS and hardware such as peripheral devices.

  The “computer readable recording medium” is a writable non-volatile memory such as a flexible disk, a magneto-optical disk, a ROM, a flash memory, etc., a portable medium such as a DVD (Digital Versatile Disk), and a computer system Storage devices such as hard disks.

Furthermore, the “computer-readable recording medium” is a volatile memory (for example, DRAM (Dynamic Memory) inside a computer system that becomes a server or a client when a program is transmitted via a network such as the Internet or a communication line such as a telephone line). As Random Access Memory), it is assumed that the program which holds the program for a fixed time is included.
The program may be transmitted from a computer system in which the program is stored in a storage device or the like to another computer system via a transmission medium or by transmission waves in the transmission medium. Here, the “transmission medium” for transmitting the program is a medium having a function of transmitting information, such as a network (communication network) such as the Internet or a communication line (communication line) such as a telephone line.
Further, the program may be for realizing a part of the functions described above. Furthermore, it may be a so-called difference file (difference program) that can realize the above-described functions in combination with a program already recorded in the computer system.

DESCRIPTION OF SYMBOLS 10 ... Arithmetic unit, 11 ... Input part, 12 ... Obfuscated arithmetic parameter calculation part, 13 ... Obfuscated arithmetic part

Claims (3)

Input operation formula information indicating an input operation formula, and an input unit for inputting a pre-obfuscated vector before the obfuscation of the pre-obfuscation vector used for the input arithmetic expression;
An obfuscation operation parameter used in an obfuscation operation for calculating an obfuscated vector after an obfuscation operation from the pre-obfuscation operation vector, an obfuscation operation parameter in which a value of an element of the pre-obfuscation operation vector does not appear An obfuscated calculation parameter calculation unit that calculates using a calculation formula,
An obfuscation operation unit for performing an obfuscation operation of calculating a post-obfuscation vector from the pre-obfuscation vector using the obfuscation operation parameter;
Equipped with
In the obfuscated calculation parameter calculation formula, the input calculation formula represented using the pre-obfuscated vector before calculation is a plurality of exclusive ORs and a plurality of exclusive ORs as one term in the input calculation formula. A computing device characterized by being calculated so as to leave at least one exclusive OR for each of the single terms when represented by an expression which is operated by a binary operator shown . An input step in which an arithmetic device inputs input arithmetic expression information indicating an input arithmetic expression, and a pre-obfuscated vector before the obfuscation of the pre-obfuscation vector used in the input arithmetic expression;
The value of the element of the pre-obfuscation operation vector is an obfuscation operation parameter used for the obfuscation operation in which the operation device calculates the after-obfuscation operation vector from the pre-obfuscation operation vector after the obfuscation operation. Obfuscated operation parameter calculation step which is calculated using an obfuscated operation parameter calculation formula which does not appear;
An obfuscation operation step in which the operation device performs an obfuscation operation of calculating an after-obfuscation vector after the obfuscation operation from the pre-obfuscation vector using the obfuscation operation parameter;
Only including,
In the obfuscated calculation parameter calculation formula, the input calculation formula represented using the pre-obfuscated vector before calculation is a plurality of exclusive ORs and a plurality of exclusive ORs as one term in the input calculation formula. A computing method characterized in that it is calculated with leaving at least one exclusive OR for each of the terms when represented by an expression which operates with a binary operator shown . On the computer
Input operation formula information indicating an input operation formula, and an input step for inputting a pre-obfuscated vector before the obfuscation of the pre-obfuscation vector used in the input arithmetic expression;
An obfuscation operation parameter used in an obfuscation operation for calculating an obfuscated vector after an obfuscation operation from the pre-obfuscation operation vector, an obfuscation operation parameter in which a value of an element of the pre-obfuscation operation vector does not appear The obfuscated calculation parameter calculation step which is calculated using a calculation formula,
An obfuscation operation step for performing an obfuscation operation of calculating a post-obfuscation vector from the pre-obfuscation vector using the obfuscation operation parameter;
Was executed,
In the obfuscated calculation parameter calculation formula, the input calculation formula represented using the pre-obfuscated vector before calculation is a plurality of exclusive ORs and a plurality of exclusive ORs as one term in the input calculation formula. A computer program configured to be calculated leaving at least one exclusive OR for each of the terms, as represented by an expression that operates with a binary operator shown .

Images