JP2004310752A - Error detection in data processing equipment - Google Patents

Abstract

An object of the present invention is to prevent illegal reading from outside of processing of a smart card or the like.
A data processing device that processes input data and generates output data processes the input data according to a predetermined algorithm during a first processing period to generate first output data. A processing device, a second processing device for processing the input data according to the predetermined algorithm during a second processing period to generate second output data, and a first output data and a second output data thereof. And a comparing device that determines whether or not there is a processing error. The first processing device and the second processing device have a first processing period and a second processing period that overlap each other. Is operable to perform the processing at least once during the first processing unit and the second processing unit such that the processing is performed according to different parts of the predetermined algorithm.
[Selection] Fig. 6A

Description

  The present invention relates to error detection in a data processing device, and more specifically, to error detection in a smart card using a cryptographic algorithm to keep data secret.

  FIG. 1 of the accompanying drawings is a block diagram showing the main parts of a typical smart card known as an integrated circuit card (ICC). 1 includes a memory unit 3, a central processing unit (CPU) 5, an input / output unit (I / O) 7, and a processing unit 9. The CPU 5 performs bidirectional communication with the memory unit 3, the I / O unit 7, and the processing device 9. These parts are usually contained within one integrated circuit embedded in the smart card 1. The smart card 1 may be a contact type or a non-contact type.

  The smart card 1 can communicate with external devices via the POWER and CLK channels to receive the required power and clock signals CLK (although some smart cards have an internal power supply or clock source), Data can be communicated to and from the smart card 1 by communicating with external devices via the I / O channel. Such communication may be by electrical signals via contact pins of the contact card or by inductive, capacitive or optical coupling of the contactless card.

  Smart cards find many uses where the security and integrity of the data stored on the card and the data communicated to or from the card are of paramount importance. For example, a smart card may serve as an identification card used to prove the identity of the cardholder. A smart card can also be used as a medical card that stores a person's entire medical history. In addition, smart cards can be used as credit / debit bank cards that allow offline transactions. For this reason, smart cards generally have encryption / decryption capabilities so that sensitive data can be encrypted before leaving the card via the I / O channel.

  In the smart card 1 shown in FIG. 1, such encryption is performed by the processing device 9. For example, when data stored in the memory unit 3 needs to communicate with an external request device via an I / O channel, this data is requested from the memory unit 3 by the CPU 5 and is processed as input data DIN by the processing unit 9 Sent to. The processing device 9 encrypts the input data DIN to generate encrypted output data DOUT. DOUT is returned to the CPU 5, transferred to the I / O unit 7, and subsequently transmitted to an external request device via an I / O channel.

  Any suitable encryption model can be used in the processing device 9 to perform the encryption. Examples of encryption algorithms used in smart cards include Data Encryption Standard (DES), Triple DES, Advanced Encryption Standard (AES), High Speed Data Encryption Algorithm (FEAL), and International Data Encryption Algorithm (IDEA). There is symmetric (or secret) key cryptography. Alternatively, the use of asymmetric (or public) key encryption algorithms, such as the RSA algorithm and the Rabin encryption scheme, is possible.

FIG. 2 of the accompanying drawings is a block diagram illustrating a conventional encryption model representing both a public key cryptosystem and a secret key cryptosystem. In this model, two parties, X and Y, attempt to conduct private communication over public channel 13 using cryptography. Party X encrypts plaintext P using encryption unit E, using encryption key K _X (which is a public key in an asymmetric encryption model and a secret key in a symmetric encryption model), A ciphertext C to be communicated to the party Y via the public channel 13 is generated. Party Y by using the secret key K _Y corresponding to the enciphering unit D and the key K _X, to decrypt the ciphertext C, and reproduce the original plaintext P.

However, the third party Z eavesdrops on the private exchange between X and Y by monitoring the public channel 13. Third party Z, all the details of the cryptographic algorithms used, resulting know all but the secret key K _X, has a sample of many ciphertext, some plaintext and a pair of a ciphertext ( (With plaintext obtained from either party X or party Y by some other means). Thus collected information is then judges be subjected to computationally intensive cryptanalysis, decodes the used were encryption, the key K _X, which is used to generate the ciphertext.

  However, modern encryption techniques have been developed to be more resistant to such conventional attacks based on brute-force computational analysis of information gathered in conventional ways. Accordingly, the use of less obscure information sources based on the physical implementation of the encryption system has recently received attention.

  In practice, a cryptographic system interacts with its environment and is implemented on a physical device that is affected by the environment. Electronic devices such as pagers and smart cards consume power, emit radiation, and respond to temperature changes and electromagnetic fields during operation. These physical interactions can be manipulated and monitored by a third party, such as Z, to provide information useful in cryptanalysis. The conventional cryptographic model shown in FIG. 2 does not consider the physical side effects of using cryptography in the real world, and a more realistic model is the "side channel" as shown in FIG. 3 of the accompanying drawings. Can be explained using the concept of The side channel is a source of information specific to the physical implementation, and attacks using such information are called "side channel attacks".

  For example, the amount of time it takes to calculate a cryptographic function depends not only on what the function does, but also on what input is passed. In addition to the message to be encrypted, the encryption function typically takes a secret key as input, and thus the value of the secret key can affect publicly observable timing characteristics. Such an attack based on timing side channel information is proposed by Paul Kocher et al. In an article named "Timing Attack on Implementation of Diffie-Hellman, RSA, DSS and Other Systems" (CRYPTO $ 96). This document outlines a cryptanalysis method that can analyze a measure of the time it takes an attacker to calculate some RSA signatures and guess the secret key of the signing entity.

  In addition, the electronic device draws current from the power supply during operation. The amount of current drawn by an electronic device, or power consumption, varies as logic gates (typically CMOS) switch during the operation of the encryption algorithm.

  Power consumption is useful to the adversary as it correlates with the computation being performed. One of the most threatening types of power analysis based side channel attacks is the type called Differential Power Analysis (DPA) proposed by Kocher et al. In the document "Differential Power Analysis" CRYPTO '99. belongs to.

  Another form of side channel attack is based on artificially introducing errors into the encryption system and subsequently monitoring the effects caused by the errors. In a document entitled "On the Importance of Checking Cryptographic Protocols for Faults" (1997), Boneh, DeMillo and Lipton are based on the observation of errors induced in hardware device leak information for implemented encryption algorithms. Introduces side channel attacks using mistakes. By exposing the encryption device to ionization or microwave radiation, errors can be introduced into random bit positions in one of the registers, which can be used to factor the coefficients of the RSA public key cryptographic algorithm. Bihim and Shamir proposed an error-based channel attack called differential error analysis (DFA) in a document named "Differential Fault Analysis of Secret Key Cryptosystems" (CRYPTO'97). This attack works against symmetric or secret key cryptosystems such as DES. The DFA can use less than 200 ciphertexts (no plaintext) to find the last DES round key and even reveal the structure of an unknown cryptosystem implemented in a smart card. The best non-side channel attacks against DES require slightly less than 64 tetrabytes of plaintext and one key encrypted ciphertext.

  Such side-channel attacks can be applied to a wide variety of data processing devices to reveal confidential information about the physical implementation of the device. As these side-channel attacks have become more sophisticated, the information leaked to the side-channels has been reduced as much as possible, making it more difficult to introduce errors and detecting attempted attacks, thereby making them more intelligent. It is important to protect data processing devices such as cards.

(Summary of the Invention)
1. A data processing device for processing input data and generating output data,
A first processing device that processes the input data according to a predetermined algorithm during a first processing period to generate first output data;
A second processing device that processes the input data according to the predetermined algorithm during a second processing period to generate second output data;
A comparison device that compares the first output data and the second output data to determine whether there is a processing error;
The first processing device and the second processing device may be configured such that the first processing period and the second processing period overlap, and the first processing device and the second processing device at least once during the overlapping period. A data processing device operable to perform the processing such that the processing is performed according to different parts of the predetermined algorithm.
2. Item 2. The data processing device according to item 1, wherein the first processing device and the second processing device are operable to start processing at different times.
3. 3. The data processing device according to item 1 or 2, wherein the predetermined algorithm is an encryption algorithm for encrypting the input data.
4. The data processing device according to item 3, wherein the predetermined algorithm includes performing a plurality of calculation rounds.
5. Item 5. The data processing device according to item 4, wherein the encryption algorithm is a digital encryption standard algorithm.
6. The data processing device according to any of the preceding items, further comprising an input for receiving a clock signal, wherein the operations of the first processing device and the second processing device are controlled by the clock signal.
7. 7. The data processing device of item 6, wherein the second processing device is operable to start processing a predetermined number of clock cycles after the first processing device.
8. Item 8. The data processing device according to item 7, wherein the predetermined number of clock cycles is one.
9. The second processing device is operable after the first processing device to start processing a predetermined number of calculation rounds, item 4 or 5, or item 6 when subordinate to item 4. Or the data processing device according to 7.
10. Item 10. The data processing device according to item 9, wherein the predetermined number of calculation rounds is one.
11. The data processing device of any of the preceding items, wherein at least one of the processing devices is operable to add one or more delays during processing as part of the predetermined algorithm.
12. Item 12. The data processing device of item 11, wherein the at least one of the processing devices is operable to perform a dummy operation that does not affect the output data during such a delay.
13. Item 13. The data processing device according to item 11 or 12, wherein the one or more delays are random.
14． 14. The data processing apparatus of item 13, wherein the random delay is substantially neutral in power.
15. Item 15. Any one of items 1 to 7, 9 and 11 to 14, wherein the second processing device is operable to start processing at a random time after the first processing device. Data processing equipment.
16. The data processing device according to any one of the above items, wherein the comparison device determines that a processing error has occurred when the first output data and the second output data are the same.
17. The above item, further comprising a processing control device for ensuring that the first processing device is active during a down period that is within the second processing period and outside the first processing period. The data processing device according to any one of the above.
18. Item 18. The data processing device according to item 17, wherein the first processing device operates on random input data during such a down period.
19. 18. The data processing of item 17, wherein the first processing device performs an encryption round and a subsequent decryption round, or vice versa, on the input data during such a down period. apparatus.
20. The data processing apparatus according to any of the preceding items, wherein the first processing apparatus and the second processing apparatus perform processing according to different parts of the predetermined algorithm during at least a quarter of the overlapping period. .
21. 21. The data processing device of item 20, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during at least half of the overlapping period.
22. 22. The data processing device according to item 21, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during at least three-quarters of the overlapping period.
23. Item 23. The data processing device according to item 22, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during the entire overlapping period.
24. The at least one further processing period further comprises at least one further processing device for processing the input data according to the predetermined algorithm to generate at least one further output data, wherein the comparing device comprises the first device. Comparing the output data of the first processing device, the second processing device, and the at least one further output data to determine whether there was a processing error. The processing units overlap the processing periods, such that the first processing unit, the second processing unit, and the at least one further processing unit perform processing according to different parts of the predetermined algorithm at least once during the overlapping period. A data processing apparatus according to any of the preceding items, operable to perform the processing.
25. If the comparing device determines that a processing error has occurred, the comparing device converts one of the first output data, the second output data, or at least one further output data into a correct output corresponding to the input data. The data processing apparatus of item 24, further operable to select as data.
26. The data processing device according to item 25, wherein the comparison device determines the correct output data based on a majority voting system.
27. 25. The data processing device according to any one of items 1 to 24, wherein output data is not emitted from the data processing device when the comparison device determines that a processing error has occurred.
28. A data processing method for processing input data to generate output data,
(A) during the first processing period, processing the input data according to a predetermined algorithm to generate first output data;
(B) during the second processing period, processing the input data according to the predetermined algorithm to generate second output data;
(C) comparing the first output data and the second output data to determine whether or not there has been a processing error;
In the processing of steps (a) and (b), the first processing period and the second processing period overlap, and during the overlapping period, the processing of steps (a) and (b) is performed by the predetermined algorithm. The method that is performed, as is performed according to different parts of the method.
29. A data processing device substantially as described above with reference to FIGS. 6A to 14.
30. A data processing method substantially as described above with reference to FIGS. 6A to 14.
31. A smart card comprising the data processing device according to any one of items 1 to 27 and 29.
32. An operating program that, when loaded into a data processing device, causes the device to be an apparatus according to any one of items 1-27 and 29 or a smart card according to item 31.
33. An operating program that, when executed on a data processing device, causes the device to perform the method of item 28.
34. 34. The operating program according to item 32 or 33, being executed on a carrier medium.
35. 35. The operating program according to item 34, wherein the carrier medium is a transmission medium.
36. 35. The operating program according to item 34, wherein the carrier medium is a storage medium.

  According to a first aspect of the present invention, there is provided a data processing apparatus for processing input data and generating output data, wherein the data processing apparatus processes the input data according to a predetermined algorithm during a first processing period, and outputs a first output data. A first processing device for generating data, a second processing device for processing input data according to a predetermined algorithm during a second processing period to generate second output data, A comparison device that compares the second output data to determine whether or not there is a processing error, wherein the first processing device and the second processing device have a first processing period and a second processing period. At least once during the overlapping period, the first processing device and the second processing device are operable to perform the processing such that the processing is performed according to different parts of the predetermined algorithm; Data processing apparatus is provided.

  It is preferable that the first processing device and the second processing device start processing at different times. This is an advantageous way of ensuring that the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm at least once during the overlapping period.

  When it is determined by the comparison device that a processing error has occurred, it is possible to suppress emission of arbitrary output data from the data processing device. This helps to preserve the integrity of any data released to the outside and make it difficult for someone to make error-based side-channel attacks on the data processing device.

  The data processing device further comprises at least one further processing device, wherein the at least one further processing device processes the input data according to a predetermined algorithm during the at least one further processing period to obtain at least one further output data. And the comparing device compares the first output data, the second output data, and the at least one further output data to determine whether there is a processing error, and the first processing device, the second processing data, , And at least one further processing device, wherein the processing periods overlap, and at least once during the overlapping period, the first processing device, the second processing device, and the at least one further processing device perform a predetermined process. It is operable to perform the processing as it does according to different parts of the algorithm. Using more than two processing units in this way makes it more difficult to introduce undetected errors into the data processing unit, and thus makes side-channel attacks that utilize errors more difficult.

  The comparison device may determine that a processing error has occurred when two or more output data are not the same. The predetermined algorithm may be an encryption algorithm for encrypting input data. A given algorithm may include performing multiple rounds of computation. For example, the encryption algorithm may be a digital encryption standard algorithm.

  The data processing device further comprises an input for receiving a clock signal, and the operation of the processing device may be controlled by the clock signal. One of the processing devices may be operable to start processing a predetermined number of clock cycles, eg, one clock cycle, after the other processing device.

  If the predetermined algorithm involves the execution of a plurality of calculation rounds, one of the processing units is operable to start a predetermined number of calculation rounds, eg, one round, after the other processing unit. It may be.

  At least one processing device may be operable to add one or more delays during processing. Such a processing device preferably performs dummy processing during such a delay without affecting output data. Such a delay may be considered as part of a given algorithm. The delay is preferably random and the power is preferably neutral. One of the processing devices may be operable to start processing randomly after the other processing device. These measures help to reduce information leaking out through the power and timing side channels, and make the error detection more likely.

  The data processing device further comprises a processing control device that ensures that the first processing device is active during a down period that is within the second processing period and outside the first processing period. Preferably, the first processing device operates on random input data during such a down period. Alternatively, if the predetermined algorithm involves performing multiple rounds of calculation, the first processing unit performs an encryption round and a subsequent decryption round, or vice versa, on the input data during such a down period. It may be done. If there are many processing units, there are still some advantages even if only two of these processing units operate in this way. These measures can help reduce information leaking out through the power side channel.

  If it is determined that there has been a processing error, the comparing device, or some other device, may select one of the output data as the correct output data corresponding to the input data. For example, if more than two processing devices are utilized, such a selection may be based on a majority voting system. Therefore, error correction and error detection are possible.

  The first processing device and the second processing device are preferably for at least a quarter of the overlapping period, more preferably for at least half of the overlapping period, even more preferably for at least a quarter of the overlapping period. For three, and even more preferably, during the entire overlapping period, the processing is performed according to different parts of the predetermined algorithm.

  According to a second aspect of the present invention, there is provided a data processing method for processing input data to generate output data, comprising: (a) processing input data according to a predetermined algorithm during a first processing period; Generating first output data; (b) processing input data according to a predetermined algorithm during a second processing period to generate second output data; and (c) generating first output data. Comparing the data and the second output data to determine whether there is a processing error. The processing in steps (a) and (b) includes a first processing period and a second processing period. Are overlapped and performed at least once during the overlap period such that the processing of steps (a) and (b) is performed according to different parts of a predetermined algorithm.

  According to a third aspect of the present invention, there is provided a smart card including the data processing device according to the first aspect of the present invention.

  According to a fourth aspect of the invention, an operating program, when loaded into a data processing device, makes the device an apparatus according to the first aspect of the invention or a smart card according to the third aspect of the invention. Provided.

  According to a fifth aspect of the present invention, there is provided an operating program, which when executed on a data processing device, causes the device to perform the method according to the second aspect of the present invention.

  For the purpose of illustration, reference is made to the accompanying drawings.

  It is a primary object of the present invention to defend against side channel attacks that make use of errors, and before presenting a detailed description, first consider the previously considered methods of defending such attacks. This will be briefly described.

  In general, attacks such as DFA require that the attacker have access to the generated erroneous ciphertext after the attacker introduces the error. Therefore, one way to prevent such an attack is to keep the erroneous ciphertext away from the attacker and check before the device emits the output of the computation so as to negate the attack. If several attacks are detected, the smart card may be locked so that no further attacks are attempted.

  One method of protecting against error injection attacks is to perform encryption twice with the same input and check that the two outputs are the same. If the attacker introduces an error in one calculation, the resulting ciphertext will be different. The only way in which an attacker could not detect and introduce an error is if the same error could be introduced in both calculations.

FIG. 4A is a block diagram showing one embodiment of realizing this protection mechanism, and FIG. 4B is a timing chart showing the operation of the circuit of FIG. 4A. The data DIN to be encrypted, and passes through the processing apparatus 2, the processing apparatus 2 in the first processing period T _1, to process the input data DIN in accordance with a selected encryption algorithm, the first output data to generate a DOUT _1. Thereafter, the processing period T ₂ following the processing period T _1, the processing unit 2 processes the same input data DIN in accordance with the same encryption algorithm to generate a second output data DOUT _2. Thereafter, during the comparison period T _C , the comparing device 4 compares the first output data and the second output data, and when a difference is detected, the error signal ERR output from the comparing device detects the error. Changes as shown. If there is no difference, the output data DOUT (equal to the first output data DOUT ₁ and the second output data DOUT ₂₎ is outputted from the comparator 4.

  In this way, the input data DIN is serially encrypted twice using the data processing device shown in FIG. 4A. Even though such protection mechanisms require very little additional hardware, it takes about twice as long to perform the calculations. Furthermore, it is not easy for an attacker to introduce the same error twice, but it is still very likely. For example, in the random transient error model, there are 512 bit positions where an error can occur, and if there are two error ciphers, the probability of the same error occurring in each is one in 512. Thus, the number of encryptions that a malicious user must try to obtain the required number of erroneous ciphertexts has only increased by a factor of 512.

As an alternative to the serial doubling process as described with reference to FIGS. 4A and 4B, a parallel version can be implemented as shown in FIGS. 5A and 5B. The data processing device of FIG. 5A includes a first processing device 6 and another second processing device 8. The first processing device 6, in the first processing period T _1, according to the selected encryption algorithm, processes the input data DIN, to generate a first output data DOUT _1. The second processor 8, a second process during the period T ₂ is completely parallel first processing period T ₁ and the same input data DIN, and treated according to the same encryption algorithm, the second output to generate the data DOUT _2. Nature first processing period T ₁ and the second processing period T ₂ in parallel is illustrated in Figure 5B. After the first output data DOUT ₁ and the second output data DOUT ₂ is generated, comparator 4 compares the data in the manner similar to that described above with reference to FIG. 4A, according to the result of the comparison, The error signal ERR output from the comparison device changes. If there is no difference, the output data DOUT (the first output data DOUT ₁ and the second output data DOUT ₂₎ is outputted from the comparator 4.

  The parallel version described with reference to FIGS. 5A and 5B has the advantage that the extra time is much less than the serial version described with reference to FIGS. 4A and 4B, but is twice as great. Circuit area is required. However, a further major drawback is that it is very likely that the same error will be introduced into both processing units, for example, because a power anomaly affects both calculations at exactly the same time in the calculations as well. That is. This may not provide sufficient protection.

  Two different designs of processing units may be used in each of the parallel branches, both producing the same output for the same input. This makes it less likely that the same error will be introduced in both calculations. However, this requires twice as much effort in the design and it is very complicated to ensure that the same error cannot be introduced in both processing units.

  As an alternative to the serial and parallel techniques described above, encryption may be followed by decryption (or vice versa), followed by a check that the final result is the same as the original input. This can be particularly useful for algorithms such as RSA where public key operations are often much faster than private key operations. For encryption such as DES, encryption is almost the same as decryption, with the main difference being that the order in which round keys are used is reversed.

  Similar to performing a full encryption operation and checking the result, it is possible to check whether the result is the same for each step for an arbitrary step size. For example, for calculations using repeated rounds, the results may be compared after individual rounds, rather than after performing all rounds. This allows errors to be detected more quickly, but is not always practical for ciphers such as DES, since the time to perform all rounds is very short. Furthermore, more comparisons may mean more overhead and may not be as efficient, as errors can be introduced between steps.

  This alternative technique is disclosed in Karri et al., "Concurrent Error Detection of Fault-Based Side-Channel Cryptanalysis of 128-Bit Symmetric Block Ciphers" (2001). As described in this document, encryption / decryption checks can be performed at the algorithm level (ie, cross-check after performing the entire encryption and decryption) or at the round level (cross-check at the end of each encryption / decryption round). ), Or even at the operation level (cross-check at the end of an operation within a round).

  FIG. 6A is a block diagram showing a data processing device embodying the present invention. FIG. 6B is a timing chart showing the operation of the data processing device of FIG. 6A. The data processing device embodying the present invention includes a first processing device 12, a second processing device 14, and a comparison device 4.

Similar to the parallel version of the data processing circuit described above with reference to FIG. 5A, the first processing device 12 processes the input data DIN according to a predetermined encryption algorithm during a _first processing period T1, generates one of the output data DOUT _1, second processor 14, in the second processing period _{T 2,} to process the same input data DIN in accordance with the same encryption algorithm, outputting a second output data DOUT ₂ I do. Thereafter, the comparison period T _C, the comparator 4, the output data of the two sets are compared, whether or not there is processing error is determined. If there is a processing error, the level of the error signal ERR can be set accordingly and ensure that a large amount of output data is not emitted to the outside. The suppression of the output data may be performed by the comparison device 4 as shown, or may be performed by some other device depending on the error signal ERR. If there is no processing error, output data DOUT corresponding to input data DIN can be emitted.

However, unlike the previously considered techniques, in this embodiment of the invention, the first processing device 12 and the second processing device 14 perform the first processing period T ₁ as illustrated in FIG. 6B. and the second processing period T ₂ as overlap is operable to initiate the process at different times. Thus, one encryption is slightly delayed than the other.

  In this way, the total processing time is only slightly longer than the parallel version described above with reference to FIGS. 5A and 5B, but since the two processing units are not performing the same cryptographic operation at the same time, an error will occur. If introduced at a certain moment, it is introduced in a different part of the calculation, thus producing a different output. Therefore, it is very difficult for an attacker to introduce the same error twice and to escape the attention of the error checking mechanism.

  This embodiment of the invention is much more robust to error-based side channel attacks than the serial version described above with reference to FIGS. 4A and 4B. This is because, in a serial fashion, two separate error-inducing operations (eg, using a laser beam) at different times actually introduce the same error into both calculations (the time between error-inducing operations). Is the same as the time between serial processing periods). In such a case, the introduction of an error avoids detection in the direct method, and an erroneous ciphertext is output. Using a scheme embodying the present invention, the act of inducing two such errors during processing is to distinguish four different errors, two in the first processing period and two in the second processing. It is likely to be introduced during the period, and an attack is detected. For a successful attack on this scheme, the attacker needs to inject a number of mistakes each time into the completely correct location. For every error that the attacker injected into one processing unit, the other (different) error could have been injected into the other processing unit. This makes it necessary to inject other errors to offset the newly introduced error, whereby another error is again generated, and so on.

  The time difference D between the time when the first processing device 12 starts encrypting the input data DIN and the time when the second processing device starts encrypting the input data DIN is determined by the time difference in order for this technique to be effective. It doesn't need to be big. For example, a time difference D of one clock cycle is appropriate and does not introduce a significant time penalty, but other time differences are possible. In an embodiment in which the first processing device 12 and the second processing device 14 perform the DES encryption algorithm, one processing device performs a predetermined number of encryption rounds, for example, one round, after another processing device performs a DES encryption algorithm. It can be manufactured to start the process. Alternatively, a random time difference may be used.

  Resistance to error-based side-channel attacks may be further improved in some embodiments of the present invention by adding a delay, preferably a random delay, through processing operations performed by the processing device. This makes it more difficult to introduce the same error twice. Further, if the delay is power neutral, which means that the delay cannot be seen in power tracking, it protects against other side-channel attacks such as differential power analysis (DPA) Can help you. At least one of the processing devices may be adapted to perform a dummy operation that does not affect the output data during such a delay. During such dummy processing, the processing device preferably continues to use the same amount of power as if it were performing normal calculations.

FIG. 7A is a block diagram illustrating another data processing device embodying the present invention, and FIG. 7B is a timing diagram illustrating an operation of the data processing device of FIG. 7A. 7A includes a third processing device 16 in addition to the first processing device 12, the second processing device 14, and the comparing device 4 illustrated in FIG. 6A. The third processing device 16 processes the same input data DIN as the first processing device 12 and the second processing device 14 according to the same encryption algorithm, and generates a _third output DOUT3. This operation is performed during a third treatment period T _3. The first processing unit 12, the second processing unit 14 and the third processing unit 16, a first processing period _{T 1,} as shown in FIG. 7B, the second processing period _{T 2,} and a third process as the period T ₃ overlap, it is operable to initiate the process at different times.

  Thus, this embodiment allows the three sets of output data to be compared by the comparison device 4 to determine whether there was a processing error, and to apply the same error to the three algorithms at the same time in each algorithm. To provide better error detection performance possibilities. Of course, more than three processing units can be provided to further enhance the error detection capability.

In the above embodiment, if there is a processing error, the level of the error signal ERR is set accordingly, and it can be ensured that a large amount of output data is not released to the outside. However, when three or more sets of output data are used, it is possible to determine which one (or one or more) of the output data is likely to be correct, and emit the output data. For example, although DOUT ₁ and DOUT ₂ are the same, if the DOUT ₃ is different from both the DOUT ₁ and DOUT _2, based on the majority voting system, DOUT ₁ (or equal to DOUT ₂₎ is the final output data DOUT Can be selected as This error correction function may be performed by the comparing device 4 as shown, or may be performed by a separately provided device.

  Further increasing resistance to differential power analysis (DPA) attacks can be achieved by ensuring that both processing units work together for as long as possible. This is because the power consumption of one processing device can serve to mask the power consumption of the other processing device. With a processing device embodying the present invention that operates according to the timing diagram shown in FIG. 6B, at the beginning and end of the encryption operation, only one of the two processing devices operates, thus making power consumption easier. There is a short period that can be analyzed.

FIG. 8A is a block diagram showing a data processing device embodying the present invention, including a processing control device 18 in addition to the components shown in FIG. 6A. FIG. 8B is a timing chart showing the operation of the data processing device of FIG. 8A. The processing control device 18 is provided to control the processing of the first processing device and the second processing device, and one of the processing devices is inactive while the other processing device is performing processing during the processing period. Avoiding this increases resistance to the DPA attack described above. Down period when there is no down time is the one or the other of the processing apparatus can be a inactive, in FIG. 8B, shown as T _D. For example, down period _{T D} of the first processing unit 12 is in the second processing period _T within ₂ (inside), in the first process out of the period _{T 1} (outside). In the previous embodiment, the processing control device provided for the purpose of controlling the processing of the processing device performs the control in the manner shown in FIG. 6B or 7B.

  One possibility is that the processing controller 18 ensures that the processing unit 12 or 14 is provided with random data that can operate on it during a down period, which can be inactive in the absence of a down period. It is to be. This is shown in the table below, where "E" indicates an encryption round, "D" indicates a decryption round, and "Kn" indicates an nth round key.

あるいは、１６ラウンドを有するＤＥＳなどの暗号を用いる場合、処理制御装置１８は、ダウン期間がない場合にイナクティブになるダウン期間の間、処理装置に暗号化のさらなるラウンドを行い、その後に同じラウンド鍵を用いて対応する解読のラウンドを行わせるように処理装置を制御し得、これは、最終的な出力に影響を与えない。この場合、第１の処理装置および第２の処理装置がそれぞれの処理を開始する時刻の差は、２ラウンドになり得る。このことは、以下の表に示されるが、この表において、「Ｅ」は、暗号化ラウンドを指し、「Ｄ」は解読ラウンドを示し、「Ｋｎ」はｎ番目のラウンド鍵を示す。

Alternatively, when using a cipher such as DES having 16 rounds, the processing controller 18 performs an additional round of encryption on the processing unit during the down period when it is inactive if there is no down period, followed by the same round key. Can be used to control the processing unit to cause a corresponding round of decryption, which does not affect the final output. In this case, the difference between the times at which the first processing device and the second processing device start processing may be two rounds. This is shown in the table below, where "E" indicates an encryption round, "D" indicates a decryption round, and "Kn" indicates an nth round key.

図９は、図８Ａの処理装置１２および処理装置１４によって行われる処理を模式的に示す、図８Ｂに対応する例示的なタイミング図である。図９において、第１の処理装置１２および第２の処理装置１４によって所定のアルゴリズムに従って行われる処理は、概念上の計算ブロック１〜８に分割される。例えば、計算ブロックは、ＤＥＳ暗号化アルゴリズムにおける暗号化ラウンドであり得る。処理装置１２および処理装置１４は、第１の処理装置１２が計算期間ｔ_１において処理を開始し、第２の処理装置１４が計算期間ｔ_２において処理を開始する状態で、それぞれ、９つの計算期間ｔ_１〜ｔ_９のうちの１つの間、計算ブロック１〜８を順次行う。計算期間ｔ_９において第１の処理装置のダウン期間の間、処理装置１２によって、出力データＤＯＵＴに影響を与えない何らかの形の処理が行われ、処理装置１４についても、同様のことが処理期間ｔ_１の間に行われる。ダウン期間の間のこのような処理は、図９において、「Ｆ」と表示される。

FIG. 9 is an exemplary timing diagram corresponding to FIG. 8B, schematically illustrating the processing performed by the processing devices 12 and 14 of FIG. 8A. In FIG. 9, the processing performed by the first processing device 12 and the second processing device 14 according to a predetermined algorithm is divided into conceptual calculation blocks 1 to 8. For example, a computation block may be an encryption round in a DES encryption algorithm. Processor 12 and processor 14, in a state where the first processing unit 12 starts the process in the calculation period t _1, the second processing unit 14 starts the process in the calculation period t _2, respectively, the nine calculation During _{one of the} periods t _{1 to} t ₉ , the calculation blocks 1 to 8 are sequentially performed. During the calculation period t ₉ the down period of the first processing unit, the processing unit 12, the processing of some form that does not affect the output data DOUT is performed, the processing apparatus 14, the same is treatment period t ₁ is performed. Such processing during the down period is indicated as "F" in FIG.

In the embodiment described with reference to FIGS. 8A, 8B, and 9, the processing control device 18 starts the processing of the first processing device 12 and the second processing device 14 at different times. by explained that the delay is to be terminated in the first processing period T ₁ and the second processing period T ₂ the different times when not introduced into the process) is controlled so as. However, it is not essential that the first processing device 12 and the second processing device 14 start processing at different times, and as described below, the first processing device 12 and the second processing device 14 However, it is not essential to complete the process at different times.

FIG. 10 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention using the apparatus shown in FIG. 8A. As in FIG. 9, in this embodiment, the processing performed by the first processing device 12 and the second processing device 14 according to a predetermined algorithm is divided into conceptual calculation blocks 1 to 8. However, processing control unit 18 in this embodiment, processing is started at the same time, as the first calculation block 1 is performed during the calculation period t ₁ by both of the processing apparatus, the first processing unit 12 and the The second processing device 14 is controlled. Thereafter, the first processing unit 12, in the subsequent calculation period _t 2 ~t _8, respectively, perform the subsequent calculation block 2-8.

Delay period that is displayed when X is between calculation period t _2, is inserted into the processing performed by the second processing unit 14. Thereafter, the second processing unit 14, the calculation period _t 3 ~t _9, respectively, perform the subsequent calculation block 2-8. By inserting a delay period X, the first processing unit 12 and the second processing unit 14 is to begin the process to the same time t _1, to complete the process, at different times t ₈ and t _9.

The second processing device 14 may be idle during the delay period X, but preferably performs a dummy process that does not affect the output data to reduce leakage through the power side channel. Delay period X during the second period T _2, may be inserted at random locations throughout the random length of time. The random delay is preferably power neutral as described above to further protect against side channel attacks such as differential power analysis (DPA).

FIG. 11 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. In this embodiment, the first processing unit 12 and the second processing unit 14, at different times t ₁ and t _2, but is adapted to start the respective processing, the first processing period in the calculation period t ₈ by inserting a delay period X to T _1, the first processing unit 12 and the second processing unit 14 completes the process at the same time t _9.

FIG. 12 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. In this embodiment, the first processing unit 12 and the second processing unit 14, both in the delay period X each time t ₂ and t _8, the first processing period T ₁ and the second processing period T by inserting _2, the process starts in the calculation period t _1, the process is completed in the calculation period t _9.

FIG. 13 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. In this embodiment, the first processing unit 12, before the second processing unit 14 starts the process at t _2, but starting the process at t _1, processing the second processing unit 14 in t ₉ After completing the process, the process is completed. This two delay periods X is, at time t ₄ and t ₈ is inserted into the first processing period T _1, it is because there is no delay period is inserted in the second processing period T _2.

FIG. 14 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention that is similar to the embodiment of FIG. In this embodiment, the delay period X is, in the first processing period _{T 1} and the second processing period _{T 2,} respectively, are inserted at time _{t 5} and _{t 6.}

Embodying the present invention, FIGS. 9 to all of the processing method shown in 14, the first processing unit 12 and the second processing unit 14, a first processing period T ₁ and the second processing period T ₂ Are operable to perform the processing such that the first processing device 12 and the second processing device 14 perform the processing according to different portions of the predetermined algorithm at least once during the overlapping period. The point is common. In this regard, the term “overlap” refers to the case of FIGS. 9 to 11 and 13 where the processing periods T ₁ and T ₂ partially overlap, the first processing period T ₁ and the second processing period T ₁ It should be understood that this includes both the cases shown in FIGS. 12 and 14 where ₂ is the same.

For example, in FIG. 9, overlap period, includes a calculation period t ₂ ~t _8, the first processing unit 12 and the second processing unit 14, during the entire overlap period, the process in accordance with different portions of a predetermined algorithm I do. This means that at any time during the overlapping period, errors introduced into the device may affect both processing units, but are between different parts of the calculation, and such errors are therefore This is advantageous because it is more likely to be detected. An attempt to introduce an error into both calculation blocks 1 and avoid detection is that during t ₂ , the error, together with the processing block 1 of the second processing unit 14, the processing block of the first processing unit 12 2 is highly likely to affect, and thus is likely to fail.

In the scheme of FIG. 9, each of the calculation blocks 1 to 8 is protected (covered) by at least one differently numbered calculation block. For example, computing block 1, the calculation period t _2, (covered) is protected by the calculation block 2. Calculation block 2, in the calculation period t ₂ is protected by the computation block 1 (covered), and in calculation period t _3, it is covered by the calculation block 3. The same applies hereinafter. Thus, an attempt to introduce an error into a particular computation block in both processing units also introduces the error into one instance of at least one other computation block and may therefore be detected. To a lesser extent, as in the schemes shown in FIGS. 10-13, some advantages are obtained even when not all of the computation blocks are so protected.

In FIG. 10, the overlapping period covers the calculation periods t _{1 to} t ₈ , and the first processing device 12 and the second processing device 14 perform the predetermined algorithm from t ₂ to t ₈ , that is, not the entire overlapping period. The processing is performed according to different parts of In this embodiment, calculation block 2-8 (i.e., computation block included in the calculation period t ₂ ~t ₈₎ each, by the calculation block at least one different numbers attached, is protected as described above You. Therefore, errors introduced into both the processing device during t ₁ is likely to affect the same part of the calculation, therefore, is not detected during the detection period t ₂ ~t _8, protection obtained Can be In this regard, the delay period X does not affect the output data, but can be considered to be part of a given algorithm.

In FIG. 13, the processing is performed according to different parts of a predetermined algorithm at calculation blocks t ₂ , t ₃ , t ₄ , t ₈ , and t ₉ , and each of calculation blocks 1 to 3, 7, and 8 (ie, calculation period _{t 2, t 3, t 4} , blocks contained in _{t 8} and _{t 9),} as described above, it is protected by the calculation block at least one different numbers attached. A similar analysis applies to FIGS. 11 and 12.

14, overlapping period covers the calculation period _t 1 ~t _9. In this embodiment, the delay period X is a part of a predetermined algorithm, the processing in accordance with different portions of a predetermined algorithm first processing unit 12 and the second processing unit 14 in the calculation block t ₅ and t ₆ You can think of doing. The calculation block 5 is not protected as described above by the at least one differently numbered calculation block (the first processing unit 12 and the second processing unit 14 are at least once during the overlapping period). It is preferred that the processing be performed according to different parts of the predetermined algorithm that actually affect the output data, so it is preferable to protect it), so that the calculation block 5 is protected by being covered by the dummy block X.

  The scheme shown in FIG. 14 is similar to the combination of the serial and parallel versions described above with reference to FIGS. 4B and 5B, respectively, but has potential benefits, both separately. For example, if an attacker attempts to introduce an error into the modulus of the parallel computation blocks 1-4 and also introduces it into the serial computation block 5, the attacker attacks with sufficient accuracy to introduce the same error into the block 5 exactly twice. There is a high possibility that the timing cannot be adjusted. In addition, the attacker needs to introduce errors in a way that affects two parallel computational blocks simultaneously. This limits the possibility of introducing errors. Furthermore, this scheme is simpler than the scheme of simply adding blocks 5 in series and not protecting the other blocks.

  Although the main application of the error detection technique has been described above for use in a smart card as shown in FIG. 1, this technique can be used for other secure devices such as USB token, secure memory, secure multimedia, And a secure access module (SAM). Embodiments of the present invention are not limited to a processing device in which encryption is performed. Embodiments of the present invention may be used in any application where error detection is required and even error correction is required. For error correction, the data processing application may be set to reprocess the input data DIN when there is an error signal, or as described with reference to FIGS. 7A and 7B, three or more processing devices. Is used, a voting system can be used to determine which output data is authentic.

  Embodiments of the present invention may be applied to DES, AES, and any other type of symmetric encryption algorithm. It can also be applied to asymmetric algorithms such as RSA. The same device can be used for DES and triple DES.

  Although the processing device of one embodiment of the present invention has been described as being implemented in hardware, embodiments of the present invention may be implemented in software. For example, in the smart card device described above with reference to FIG. 1, instead of providing a separate processing unit 9 on the smart card as described above, an operating program is provided instead (using the memory part 3). Stored) to control the CPU 5 to fulfill the function of the processing device 9, so to speak.

  However, in embodiments of the present invention, it is generally not possible to use a single CPU, as two or more processing units are required to perform the processing in an overlapping manner as described above. Alternatively, two or more CPUs corresponding to two or more processing devices may be provided so that simultaneous processing can be performed. One CPU may be used when the CPU itself is operable to perform parallel processing of operations. For example, while many operations in a CPU are essentially bit-by-bit operations (eg, AND, OR, XOR), a 32-bit processor can process 32 bits simultaneously, resulting in substantially 32 Operations can be performed in parallel. Thus, it is possible to write an operating program to control the CPU so that some of these 32 bits are from one processing round and some are from other processing rounds.

  An operating program embodying the present invention can be stored on a computer-readable medium, but can also be implemented in a signal, such as a downloadable data signal provided from an Internet website. The appended claims should be construed to include the operating program itself, as a record on a carrier, as a signal, or in any other form.

A data processing device is provided for processing input data (DIN) and generating output data (DOUT). A first processing unit configured to process the input data (DIN) in a _first processing period (T ₁ ) according to a predetermined algorithm to generate _first output data (DOUT ₁ ); comprising the input data (DIN) was treated according to a second predetermined algorithm in the processing period _{(T 2)} of the second processing unit for generating a second output data (DOUT ₂₎ and (14). The data processing apparatus further includes comparing the first and second output data (DOUT ₁ and DOUT _2), comparing device determines whether a processing error (4). First and second processing apparatuses (12 and 14) overlaps the first and second processing period (T ₁ and T ₂₎ are, at least once during the overlapping period, the first and second processing unit (12 and 14) are operable to perform the processing such that the processing is performed according to different parts of the predetermined algorithm.

  It is understood that two similar, but not necessarily identical, sequences of calculations that produce the same output data for the same input data are considered to be performed according to the same algorithm.

FIG. 1 is a block diagram showing main parts of a typical smart card as described above. FIG. 2 is an exemplary block diagram used in describing a conventional encryption model, as described above. FIG. 3 is an exemplary block diagram used to describe the encryption model, including the side channel, as described above. FIG. 4A is a diagram used to illustrate the use of a previously contemplated serial technique for detecting errors in a data processing device. FIG. 4B is a diagram used to illustrate the use of a previously contemplated serial technique for detecting errors in a data processing device. FIG. 5A is a diagram used to describe a previously considered parallel technique for detecting errors in a data processing device. FIG. 5B is a diagram used to explain a previously considered parallel technique for detecting errors in a data processing device. FIG. 6A is a diagram illustrating a data processing device according to an embodiment of the present invention. FIG. 6B is a diagram illustrating a data processing method according to an embodiment of the present invention. FIG. 7A is a diagram illustrating a data processing device according to another embodiment of the present invention. FIG. 7B is a diagram illustrating a data processing method according to another embodiment of the present invention. FIG. 8A is a diagram illustrating a data processing device according to another embodiment of the present invention. FIG. 8B is a diagram illustrating a data processing method according to another embodiment of the present invention. FIG. 9 is an exemplary timing diagram corresponding to the timing diagram shown in FIG. 8B to schematically show the processing performed by the data processing device of FIG. 8A. FIG. 10 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. FIG. 11 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. FIG. 12 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. FIG. 13 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention. FIG. 14 is an exemplary timing diagram illustrating the operation of another embodiment of the present invention.

Claims (36)

A data processing device that processes input data and generates output data,
A first processing device that processes the input data according to a predetermined algorithm during a first processing period to generate first output data;
A second processing device that processes the input data according to the predetermined algorithm during a second processing period to generate second output data;
A comparison device that compares the first output data and the second output data to determine whether there is a processing error;
The first processing device and the second processing device may be configured such that the first processing period and the second processing period overlap, and the first processing device and the second processing device at least once during the overlapping period. A data processing device operable to perform the processing such that the processing is performed according to different parts of the predetermined algorithm.   The data processing device according to claim 1, wherein the first processing device and the second processing device are operable to start processing at different times.   The data processing device according to claim 1, wherein the predetermined algorithm is an encryption algorithm for encrypting the input data.   The data processing device according to claim 3, wherein the predetermined algorithm includes execution of a plurality of calculation rounds.   The data processing device according to claim 4, wherein the encryption algorithm is a digital encryption standard algorithm.   The data processing device according to any of the preceding claims, further comprising an input for receiving a clock signal, wherein operation of the first processing device and the second processing device is controlled by the clock signal.   The data processing device according to claim 6, wherein the second processing device is operable to start processing a predetermined number of clock cycles after the first processing device.   The data processing device according to claim 7, wherein the predetermined number of clock cycles is one.   The method according to claim 4 or 5, wherein the second processing device is operable after the first processing device to start processing a predetermined number of calculation rounds. The data processing device according to claim 6.   The data processing apparatus according to claim 9, wherein the predetermined number of calculation rounds is one.   A data processing device according to any of the preceding claims, wherein at least one of the processing devices is operable to add one or more delays during processing as part of the predetermined algorithm. .   12. The data processing device of claim 11, wherein the at least one of the processing devices is operable to perform a dummy operation that does not affect the output data during such a delay.   13. The data processing device according to claim 11, wherein the one or more delays are random.   14. The data processing apparatus according to claim 13, wherein the random delay is substantially neutral in power.   The method according to any one of claims 1 to 7, 9, and 11, wherein the second processing device is operable to start processing at a random time after the first processing device. The data processing device as described in the above.   The data processing device according to claim 1, wherein the comparison device determines that a processing error has occurred when the first output data and the second output data are the same.   The above claim, further comprising a processing control device that ensures that the first processing device is active during a down period that is within the second processing period and outside the first processing period. The data processing device according to any one of the above items.   18. The data processing device according to claim 17, wherein the first processing device operates on random input data during such a down period.   18. The method according to claim 17, wherein the first processing device performs an encryption round and a subsequent decryption round, or vice versa, on the input data during such a down period. Data processing device.   Data processing according to any of the preceding claims, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during at least a quarter of the overlapping period. apparatus.   21. The data processing device according to claim 20, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during at least half of the overlapping period.   22. The data processing device according to claim 21, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during at least three quarters of the overlap period.   23. The data processing device according to claim 22, wherein the first processing device and the second processing device perform processing according to different parts of the predetermined algorithm during the entire overlapping period.   The at least one further processing period further comprises at least one further processing device for processing the input data according to the predetermined algorithm to generate at least one further output data, wherein the comparing device comprises the first device. Comparing the output data of the first processing device, the second processing device, and the at least one further output data to determine whether there was a processing error. The processing units overlap the processing periods, such that the first processing unit, the second processing unit, and the at least one further processing unit perform processing according to different parts of the predetermined algorithm at least once during the overlapping period. A data processing device according to any of the preceding claims, operable to perform the processing. .   If the comparing device determines that a processing error has occurred, the comparing device outputs one of the first output data, the second output data, or at least one further output data to a correct output corresponding to the input data. 25. The data processing device of claim 24, further operable to select as data.   26. The data processing device according to claim 25, wherein the comparing device determines the correct output data based on a majority voting system.   The data processing device according to any one of claims 1 to 24, wherein output data is not released from the data processing device when the comparison device determines that a processing error has occurred. A data processing method for processing input data to generate output data,
(A) during the first processing period, processing the input data according to a predetermined algorithm to generate first output data;
(B) during the second processing period, processing the input data according to the predetermined algorithm to generate second output data;
(C) comparing the first output data and the second output data to determine whether or not there has been a processing error;
In the processing of steps (a) and (b), the first processing period and the second processing period overlap, and during the overlapping period, the processing of steps (a) and (b) is performed by the predetermined algorithm. The method that is performed, as is performed according to different parts of the method.   A data processing device substantially as described above with reference to FIGS. 6A to 14.   A data processing method substantially as described above with reference to FIGS. 6A to 14.   A smart card comprising the data processing device according to any one of claims 1 to 27 and 29.   An operating program which, when loaded into a data processing device, causes the device to be an apparatus according to any one of claims 1 to 27 and 29 or a smart card according to claim 31.   29. An operating program which, when executed on a data processing device, causes the device to perform the method of claim 28.   34. The operating program according to claim 32 or 33, running on a carrier medium.   35. The operating program according to claim 34, wherein the carrier medium is a transmission medium.   The operating program according to claim 34, wherein the carrier medium is a storage medium.

Images