The present invention relates to a tamper-resistant information processing device. It is particularly very effective when applied to cards such as the IC card.
An IC card is a device used for such purposes as to hold personal information which should not be altered without permission, to encrypt data by use of a cryptographic key (which is secret information), or to decrypt ciphertext. The IC card does not have any power source therein, but when it is inserted in a,reader/writer for IC cards, the IC card is supplied with power and becomes operable. When the IC card is in the operable state, it receives a command transmitted from the reader/writer, and carries out a process such as transfer of data according to the command.
FIG. 1 shows a basic conceptual configuration of an IC card in which an IC card chip 102 is mounted on a card 101. As shown in the figure, an IC card generally has disposed thereon a supply voltage terminal Vcc, a ground terminal GND, a reset terminal RST, an input/output terminal I/O, and a clock terminal CLK. The positions of these terminals are specified in ISO International Standard 7816. The IC card receives power from the reader/writer and exchanges data with the reader/writer. Such communication between the IC card and the reader/writer is described, for example, on page 41 of a book entitled xe2x80x9cSMARTCARD HANDBOOKxe2x80x9d authored by W. Rankl and W. Effing and published by John Wiley and Sons in 1997.
The configuration of the semiconductor chip mounted on an IC card is basically the same as that of the ordinary microcomputer. FIG. 2 is a block diagram showing the basic configuration of the semiconductor chip mounted on an IC card. As shown in FIG. 2, the semiconductor chip for cards has a central processing unit (CPU) 201, a memory device 204, an input/output (I/O) port 207, and coprocessor 202. Some systems do not employ the coprocessor. The CPU 201 is a device for performing logic and arithmetic operations, while the memory device 204 stores programs and data. The input/output port is a device for communicating with the reader/writer. The coprocessor performs cryptographic processing itself or operations necessary for cryptographic processing at high speed. For example, types of coprocessors employed include a particular operation device for performing a residue operation for RSA and a cryptographic device for performing a rounding process for DES. There are many IC card processors which do not have any coprocessors. A data bus 203 is a bus connecting one device to another.
The memory device 204 includes such memories as a ROM (Read Only Memory), a RAM (Random Access Memory), and an EEPROM (Electric Erasable Programmable Read Only Memory). Information stored in a ROM cannot be altered, and therefore ROMs are used to store mainly programs. Information stored in a RAM, on the other hand, can be freely rewritten, but the stored information disappears once the power supply is interrupted. That is, since the power supply to an IC card is interrupted when the IC card is removed from the reader/writer, the RAM can no longer hold its contents after that. The EEPROM, in contrast, can continue holding its contents even if its power supply is interrupted. Therefore, the EEPROM is used for storing data which it is necessary to rewrite, and hold even when the IC card is removed from the reader/writer. For example, the number of the remaining call units of a prepaid telephone card is rewritten each time the card is used, and the call unit data must continue to be held even after the card is removed from the reader/writer. This is why the call unit data of the prepaid card is held in an EEPROM.
The present invention provides a tamper-resistant information device for use with cards having high security.
Specifically, an object of an embodiment according to the present invention is to reduce the correlation between the contents of data processing operations and consumed currents in a card component such as the IC card chip. Reducing the correlation between the contents of the data processing operations and the consumed currents in the chip makes it difficult to estimate what is being processed in the IC card chip and how, and to derive the cryptographic key from the observed waveforms of the consumed currents. Thus, the present invention provides cards with high security.
Since IC cards have an IC card chip mounted thereon which is capable of holding programs and important information, they are used to store important information or internally perform cryptographic processing. It has been conventionally considered that the difficulty of breaking a code stored in an IC card is the same as the difficulty of deriving its encryption algorithm. However, it is pointed out that the details of the encryption processing operation and the cryptographic key may be derived by observing and analyzing the current consumed during the encryption process in the IC card, which may be easier than deriving of the encryption algorithm. The consumed current is obtained by measuring the current supplied from the reader/writer to the IC card. The details of this attack and its danger are described, for example, on page 263 (8.5.1.1 Passive Protective Mechanisms) of the book xe2x80x9cSMARTCARD HANDBOOKxe2x80x9d authored by W. Rankl and W. Effing and published by John Wiley and Sons. The following specifically describes the attack. Each CMOS constituting an IC card chip consumes a current when its output state switches from xe2x80x9c1xe2x80x9d to xe2x80x9c0xe2x80x9d or vice versa. Particularly, a large current flows through the data bus 203 when the bus value changes from 1 to 0 or vice versa. The current of the bus driver, the wiring employed, and the capacitance associated with transistors connected to the wiring cause such a current to flow. Therefore, it is possible to identify what is operating in the IC card chip by observing the consumed current.
FIG. 3 shows single-cycle waveforms of currents consumed in an IC card chip. The current waveforms are different from one another as indicated by reference numerals 301 and 302, depending on the processed data. More specifically, such a difference occurs depending on data flowing through the bus 203 and data processed in the central processing unit 201.
The coprocessor 202 can perform, for example, 512-bit modular multiplication in parallel with the CPU processing. This means that it is possible to observe the waveform of a current different from that in the CPU for a long time. Therefore, the number of operations performed by the coprocessor can be measured by observing its particular current waveform. If the number of operations performed by the coprocessor has some relationship to the cryptographic key, it might be possible to derive the key from the number of the operations.
Further, if which operation is performed or what is operated by the coprocessor changes depending on the cryptographic key, the dependency might be found by observing the corresponding change in the consumed current, and the cryptographic key might be derived.
Similarly, in the CPU, the influence of each bit value of the cryptographic key on processed data might be obtained by changing the data a plurality of times and observing the corresponding change in each consumed current. It might be possible to derive the cryptographic key by statistically processing the waveforms of these consumed currents.
The ideas on which embodiments of the present invention are based include: dividing a process performed in an IC card so that attackers cannot specify the process as a whole; and inserting a dummy process. These methods make it difficult to identify the original process and derive the cryptographic key from the waveforms of the consumed currents.
A tamper-resistant device as represented by the IC card chip is regarded as an information processing device having one or more data processing means which each comprise: a program storage unit for storing a program; a memory unit having a data storage unit for storing data; and a central processing unit (CPU) for performing a predetermined process to process data according to the program; wherein the program is composed of process instructions for giving an execution direction to the CPU.
A method according to an embodiment of the present invention for scrambling the correlation between processed data and consumed currents in an IC card chip is to divide the data into pieces, and instead of performing a given operation(s) on the entire data as a whole, perform another different operation(s) on each piece of the divided data so as to still produce the same results as those that will be obtained if the given operation is performed on the entire data as a whole. As a result, the essential operation(s) can be concealed.
Specifically, pieces of scramble data R1, R2, . . . , and Rn are prepared. Original data D1 to be processed is divided into data blocks D1[1], D1[2], . . . , and D1[n].
The data blocks and scramble data are used to produce scrambled data blocks x[1], x[2], . . . , and x[n] by employing, for example, one of the following methods.
(1) logical AND operation
(2) x[1]=0, x[2]=xxe2x88x92v
(3) x[1]=x AND R, x[2]=x AND xcx9cR, where xcx9cR is the inverse of R
That is, by using the scramble data R1, R2, . . . , and Rn, where R1 XOR R2 XOR . . . XOR Rn=2{circumflex over ( )}Lxe2x88x921 (L is the bit length of D1), the data block (original data) D1 is divided so that D2[1]=D1 AND R1, D2[2]=D1 AND R2, . . . , and D2[n]=D1 AND Rn, where n is an integer. In this case, the equation D2[1]+D2[2]+ . . . +D2[n]=D1 holds. In addition to the above logical AND operation, an ordinary addition operation or subtraction operation can be used for this purpose. A ring multiplication operation is performed on values obtained as a result of the above addition operation or subtraction operation to produce the final proper value. Since the randomly divided data blocks D2[1], D2[2], . . . , and D2[n] are used instead of directly using the original data D1, it is difficult to determine the original data D1 from information included in the observed current waveform alone. When a plurality of waveforms are statistically processed (for example, averaged to remove noise components from them), the characteristics of each waveform are eliminated, which further makes it difficult to determine original data (effectively hiding original information). It should be noted that the above randomly divided data may be produced through a division operation using pseudorandom numbers.
Another method for reducing the correlation between the contents of the data processing operation and the consumed current is to change the original data to be processed, and instead of performing a given operation on the original data, perform another different operation on the changed data so as to still produce the final proper results but consume a current different from that which will be consumed if the given operation is performed on the original data.
Specifically, random scalar data R for scrambling other data is prepared. Then, by using the prepared random scalar data R and a particular element V, the element to be processed is changed from x to x+R*V, where the symbols xe2x80x9c+xe2x80x9d and xe2x80x9c*xe2x80x9d denote ordinary addition and multiplication operations, respectively. The element V has the characteristic that whether or not the element V is added to data, an operation on the data produces the same results as if the element V were not added to the data. The above x+R*V can be used as an exponent or a scalar to scramble statistical processing of waveform observation data of consumed currents. It should be noted that the above element V acts as a number of 1 in a multiplication operation, and 0 in an addition operation. For example, when N=pq, where N is the modulus of a public key in the RSA cryptosystem, the element V is a multiple of (pxe2x88x921) (qxe2x88x921). When a scalar multiple of a base point on an elliptic curve is used, the element V is a multiple of the order of the base point.
Further, randomly determining the order in which each piece of the divided data is processed further makes it difficult to find the correlation between the contents of the data processing operation and the consumed current.
Still further, combining all the above methods for scrambling encrypted data is effective in further reducing the correlation between the contents of the data processing operation and the consumed current.
The present invention can be applied to information hiding for modular multiplication and modular exponentiation in the RSA cryptography. Furthermore, in the elliptic curve cryptography, it can be applied to information hiding for multiplication and division in underlying fields, and the calculation of a scalar multiple of a base point. In modular multiplications, the logical AND operation described above is used to divide data, and then the distributive law is used to obtain the final proper result from the divided data. In the modular exponentiation and the calculation of a scalar multiple of a base point, the exponent is divided by means of ordinary subtraction, then modular exponentiation is performed on each piece of the divided exponent, and the product of the operation results is calculated to obtain the final result (proper answer). These operations are effective in scrambling encrypted data. It should be noted that the above modular multiplications include multiplication in a prime field.