CN1413398A - Method for making data processing resistant to extraction of data by analysis of unintended side-channel signals - Google Patents

Abstract

The invention provides a method of processing of and storing data to reduce the risk of unauthorized access to the data, especially through side-channel observations. The method includes the steps of designing of algorithms, particularly ciphers, for maximum benefit from this technique, modifying the algorithm implementation to operate on mapped data, initially mapping of data, especially cryptographic keys, for storage, changing the data mapping from a prior data mapping by use of a secondary mapping, mapping incoming data for input to the modified algorithm implementation, and mapping data output from the modified algorithm for further use. The method results in enhanced secrecy of the original data and the mapping on the data. The data mapping and the secondary data mapping may be in the form of a lookup-table, an algorithm with mapping selection data, or the like. The data mapping may be implemented as cascaded mappings to further reduce the risk of unauthorized access.

Description

Data processing method preventing data extraction by analyzing unintentional side channel signals

Technical Field of the Invention

The present invention relates to data security. In particular, the invention relates to reducing the risk of unauthorized use of data.

Background of the invention

A cryptographic system is traditionally described as a black box with a cipher (encryption or decryption), where input data (whether plaintext or ciphertext) is processed inside it using a key, and the only information leaving the black box is the expected output data.

Side channel information, such as radiation or power fluctuations of electromagnetic waves associated with emissions generated by devices, can be easily and effectively exploited in attacks aimed at monitoring the information being processed, a technique that has recently emerged (e.g. , in: Differential Power Analysis by P. Kocher, J. Jaffe and B. Jun, Advance in Cryptology-Proceeding of Crypto'99, Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, 1999). This makes extracting keys much easier than traditional cryptanalysis, leading us to believe that direct monitoring of internal processing thereafter becomes exploitable to attackers, even if the noise is severe.

Where a key is used repeatedly in cryptographic operations, an attacker can usually obtain the key by monitoring and analyzing side channel information during several operations without resorting to traditional cryptanalysis techniques. The minimum number of repetitions of the operation that must be observed to extract the key value (or any internal data that is reused) varies inversely with the ratio of the signal power to the noise power that one is trying to monitor (signal-to-noise ratio). For example, by improving the hardware so that the ratio is reduced by a factor of 100 (ie 20dB), the attacker will monitor the encryption operation about 100 times to extract the key.

There are practical and economical limitations to the reduction of the signal-to-noise ratio of the side channel, such as the use of masking and additive noise. When a secure processor (such as an integrated circuit card) falls into the hands of a potential attacker, he can easily repeatedly stimulate the processor by providing an input signal while monitoring the side channel signal in close proximity. Examples of integrated circuit cards include bank cards and pay TV cards. By spending very little money and time, the attacker can decipher the information he is interested in through statistical techniques, which is called DPA (Differential Power Analysis) here. It is so named because the most common side channel monitoring for IC cards is the monitoring of power fluctuations produced by the device. DPA technology can also be applied to covertly receive and analyze radio frequency signals produced by computing performing data manipulation.

For simple IC card designs, analysis of the difference between the average values of several similar sets of waveforms allows encrypted data to be deduced. This is an example of a first-order DPA attack. It has been shown that currently available commercially available IC cards, with few exceptions, are vulnerable to such an attack with such an approach available for most identified parameters. Through proper algorithm design and inclusion of randomness, it is possible to keep data confidential in the face of first-order or even higher-order DPA attacks.

The order of DPA attack can be defined by the minimum number of intermediate variables. Through these variables, any data under the attack can be obtained. Here, these intermediate variables are the monitoring data obtained by averaging a large number of monitoring data. obtained from . A more intuitive (but imprecise) definition could be: the order is the number of internal digital states that (if noisy) control the side channel observations to obtain any information.

With more advanced data processing (so-called high-order DPA attacks) and a large amount of monitoring data, it is still possible to theoretically infer with a certain reliability that any classified data is being processed, although the amount of monitoring data required can be made Surprisingly large.

The technical purpose of the invention described here is to reduce the amount of useful information an attacker can obtain from side channel signals and to increase the minimum complexity and difficulty of a successful breach. The technique includes defenses against first-order and higher-order attacks.

In general, security devices that involve data secrecy are designed to keep the amount of information disclosure about classified data below acceptable limits during the secrecy period. This can be achieved by means of cryptographic means, which accomplishes the process of combining small amounts of leaked information into a usable whole that is difficult to compute. This purpose can also be achieved by the following methods: limit the proportion of the leakage part of the information, so that the accumulated (according to the common sense definition of information theory) leakage content related to the confidentiality during the confidentiality period of the information is at an acceptable low level, so as to achieve this goal. purpose of the invention.

Mathematical basis

One set of data (such as a few bits) can be mapped to another set of data in such a way that even if the second set of data is known to the detector, the previous set of data is not useful for the detection is still completely unknown. If the mapping selection method is known, the original data (first group) can be recovered from the mapped data (second group). In order to maintain the confidentiality of the data, the method of selection of the mapping must be unknown to the detector, and the mapping to each new set of data must be chosen randomly, so that each possible set of original data can be obtained with equal probability is mapped into every possible mapped representation. The present invention has just adopted this principle.

Operators (combining one or more operands into a result) are used as building blocks in cryptographic design. Examples of these operators include: look-up tables - unary operators - modular addition or subtraction, full word bitwise XOR, and modulo p multiplication (set of values 1 to p-1, where p is a prime number) - the latter are all binary operators son. The well-known IDEA cipher (designed by Xuejia Lai and James Massey) uses three such binary operators, and the well-known DES cipher uses look-up tables, bitwise-OR operators, and bit permutations.

In general, independently arbitrarily chosen one-to-one mappings can be applied to the input and output of any operator, respectively. In this way, an equivalent operator can be defined such that, for each chosen mapping, the correct mapped output is produced from the mapped input value. For each given operator, there can exist a set of mappings such that this equivalent operator is identical to the original operator and satisfies the necessary condition that there is no information enlightening the original data. This principle of including the same operator constraints is often referred to as concealment, although the range of mapping intervals available for general operators is rarely known.

For example, the map of the modulo addition operation - x+y≡z(mod m) - under this constraint, the operator remains unchanged to allow from (x, y, z) to ( _xi , _y , _zi ), where x _i ≡a _i x+b _i (modm), y _i ≡a _i y+ci (mod m), z _i ≡a _i z+b _i + _{ci (} mod m), where a _i and m are mutually prime numbers, and b _i and c _i are arbitrary numbers. Where m is a power of 2 (ie m=2 ⁿ ), a _i has m/2 possible values, and any one of b _i and _ci has m possible values. Many kinds of operators (such as addition, multiplication and exponentiation) will show similar properties.

矩阵中的任何一个——有逆矩阵的那些——并且b_i和c_i可以分别为2ⁿ的任意值，对于每一个值给出 个不同的映射(忽略共用矩阵A_i暗含的限制)。当n＝8比特时，就有大约2^70.2个这样的映射。Multi-bit full-word XOR operation (here we regard it as the addition of two n-element vectors on the number field Z2, addition and multiplication are equivalent to binary "XOR" and "AND" operations, and we Use lower case letters for vectors and upper case letters for matrices)—x+y=z—which has more data mapping options than modulo ²ⁿ addition, while the algorithm remains the same. These have the form: x _i =A _i x+ _bi , y _i =A _i y+ _ci and z _i =A _i z+ _bi + _ci . A _i can be

Any of the matrices—those that have an inverse—and bi _{and ci} can be any value of 2 ⁿ each, giving for each different mappings (ignoring the restriction implied by the shared matrix A _i ). When n=8 bits, there are about 2 ^70.2 such mappings.

The large set of mappings available for XOR operations can significantly reduce the availability of side-channel signals, and doing so can allow some requisites for secrecy to be compromised. This trade-off (such as reusing the chosen mappings) can effectively reduce the complexity in the final design of the algorithm while the amount of information leaked to the attacker is kept acceptably low.

Multiple maps can be used consecutively on the same data to form compound maps - eg _xi = f _i (x), _xij = f _j (xi ₎ . While this is equivalent to a single mapping x _k = f _k (x) where f _k = f _i ⁰ f _j , if properly arranged, the attacker must obtain information on multiple independent data sets (in this case three -x _k , f _i , f _j ) to obtain any information about the original data. This increases the order of DPA attacks (generally equal to the number of independent data sets) and the number of required monitoring (generally equal to the power of the number of independent data sets), in order to extract useful information from the monitoring.

First-order operators (such as lookup tables or bit permutations) are still used in encryption. Mappings that allow operators to stay the same are only limited when there is data loss in the operation (like many-to-one), though in this case it makes more sense to change the operator, e.g. by using a map-dependent query surface.

International Publication No. WO99/67919 by Kocher, Jaffe and Jun proposes a method and apparatus for improving the DES cryptographic protocol to prevent attacks by alien monitoring by reducing the amount of leakage (and signal-to-noise ratio) of information available during signal processing. An improved DES implemented by this invention instead uses two 56-bit keys (K1 and K2) and two 64-bit plaintext messages (M1 and M2), each of which is associated with a permutation (i.e., K1P, K2P and M1P,M2P) such that K1P{K1}XOR K2P{K2} is equal to a "standard" DES key K, and M1P{M1}XORM2P{M2} is equal to a "standard" message. During the operation of the device, the calculation table is preferably regularly updated, and the average amount of refreshed information is introduced into the table faster than information leakage, so that the attacker cannot obtain the content in the table by analyzing the detection results. The technology can be applied to encrypted integrated circuit cards (smart cards), tamper-resistant chips and all types of secure processing systems. In the case that concealment is used, the relationship between the number of monitoring results required to extract useful information through a side-grown channel and the power of the channel's SNR is different from the aforementioned inverse relationship, and is not given in this application There are signs of recognition of this principle. Where concealment is used in this application (with or without permutation), the number of monitoring required should vary inversely as the square of the power SNR (ie SNR to the fourth power).

SUMMARY OF THE INVENTION

The techniques of the present invention provide practical and efficient modifications to cryptography and other methods based on data secrecy changing the mapping of all secret and intermediate data used for computation and storage. These data can be, for example, keys, stored and transmitted data.

When the data being mapped or the mapping selected (or all mappings in the composite mapping used) is unknown, no information about the encrypted data can be determined. This technique has the ability to effectively reduce the information about the original data obtained from the side channel leakage, so that the monitorable side channel leakage is low enough.

Secret data, especially cryptographic keys, are never necessarily in their original form (no mapping applied), unless they were used in the initial mapping, and are randomly remapped on a per-use basis to avoid duplication of data vulnerable to DPA Appear.

An example of the high value of this technology is used in integrated circuit cards. In some cases, DPA can enable illegal users to use these integrated circuits in just a few minutes only through the analysis of the leaked side channel signals. circuit card. Another possible application is data calculation and storage in computing equipment, where electromagnetic radiation will endanger the security of data.

Therefore, in order to realize the advantages of the present invention, a method for processing data is provided here, to reduce the risk of continuing illegal access to data by methods such as DPA, the method includes the following steps:

- Algorithm design, unique and not proprietary ciphers, to benefit the most from this technology;

- Extend known data concealment techniques to larger mapping groups;

- Algorithmic tool improvements to be applied to already mapped data;

- an initial map for storing data, especially keys;

- Data mapping transformation for each previous data mapping by using secondary mapping;

- Map input data for input to the modified algorithmic executive; and

- Map the data output from the revised algorithm for further use.

The method may include maintaining data confidentiality of the secret data and the selected method of mapping.

Data maps and secondary data maps may be look-up tables, algorithms with map selection method data, or other similar forms.

The approach consists of applying mappings compoundly (cascadedly) rather than individually, to reduce the amount of information an attacker can obtain through a limited number of inspections, and to increase the minimum order for a successful DPA attack.

The mapped data and mapping selection method are communicated to the remote unit.

The invention can be better understood from the following description, non-limiting examples and accompanying drawings.

Fig. 1 shows, the schematic diagram of the prior art of encryption process;

FIG. 2 shows a schematic diagram of leakage of side channel information during the encryption process of FIG. 1;

Figure 3 shows a schematic diagram of replacing a double-input operation with a mapped data equivalent;

Figure 4 shows a schematic diagram of the combination of continuous mapping;

Figure 5 shows a schematic diagram of the encryption device being replaced by its modified equivalent;

Figure 6 shows a schematic diagram of an initial mapping for stored keys;

FIG. 7 shows a schematic diagram of repeated mapping of keys;

Figure 8 shows a schematic diagram illustrating the mapping process with the simplest cipher; and

Figure 9 illustrates the case of Embodiment 3: making the DES cipher resistant to ^1st- and ^2nd -order DPA attacks.

In FIG. 1, reference numeral 10 generally designates a "black box" cryptographic operation in the conventional sense. In operation 10 , input data 12 is converted into output signal 16 using key 14 .

In FIG. 2, reference numeral 20 generally designates a conventional cryptographic operation, such as the encryption operation shown in FIG. 1, and further indicates side channel leakage. Operation 20 includes input 22 of data, conversion of input data to output data 26 using a key 24 and leakage 28 of a signal.

In FIG. 3, reference numeral 30 generally designates a procedure in which a data masking equivalent replaces a two-input operation. In operation 30 , a standard two-input operation is implemented with inputs 32 and 34 being operated on in operator 31 to produce output 36 . The data concealment operation again receives inputs 32 and 34 and is subsequently mapped by mappings 35 and 37 before being operated on by operator 33 . The synthesized output is then mapped by an output map 39 to provide a steganographic output 36 .

In FIG. 4, reference numeral 40 generally designates the combination of the consecutive maps of FIG. 3 realized by cascading operations. Operators 41 and 47 correspond to two different operations of operation 33 in FIG. 3 . Mapping 43 corresponds to output mapping 39 referring to operator 41 and mapping 45 corresponds to an input mapping (eg 35 or 37 ) referring to operator 47 . Map 49(f _cd ) is a single composite map from the combination of 43 and 45, which does not produce any data associated with the original data, even intermediate values.

In Fig. 5, reference numeral 50 generally indicates the replacement of a cipher by its revised equivalent (as an intermediate step in the final realization of the invention). It can be seen that in an unmodified operation, the input data 52 is acted upon by an encryption operation 53 using a key 51 to provide an output 54 . In the modified equivalent, the input data 52 is converted to the mapped form by the transformation operation 56 before being acted on by the modified encryptor 57 using the key in the mapped form, providing a mapped output, via The raw output 54 can be derived therefrom using a transformation algorithm 58 .

In FIG. 6 , reference numeral 60 designates a step of making an unpredictable selection of mappings. According to the obtained selection result, the unmapped key 62 is mapped 63 and stored as 64 . The mapping selection method is stored 68 for use with the mapped key.

In Fig. 7, reference numeral 70 denotes a step of making an unpredictable selection of the secondary mapping. A further mapping 73 is performed on the previously mapped key 72 and stored as 74 instead of 72 using the selected secondary mapping. Previously stored mapping selection results are processed 76 to generate mapping selections available for 74 and stored 78 for replacement 76 based on selection experience for selecting a secondary mapping.

In FIG. 8 , reference numeral 80 generally indicates that an original operation algorithm is replaced by an operation algorithm performed on the mapped data. Encryptor 83 operates on input text 81 and key 82 to produce output text block 84 . After substitution, the input text is mapped 85 by the appropriate mapping. A similar arbitrary mapping 86 is performed on the original key 82 to produce a mapping key 89 . Alternatively, 89 may be derived from the output of an encryption operation, already in mapped form. 86 further refers to the iteratively changing mapping applied to the key. A modified cipher 87 operates on the mapped data, and its mapped output is randomly operated 88 by the mapping operator to produce the same data 84 as produced by the unmodified cipher. Alternatively, the output of 87 can be used directly with mapping selection data in a similar correction algorithm to equivalents 85 and 86 to avoid unmapped data.

In FIG. 9, reference numeral 90 generally indicates that the bit transformation is replaced by performing such processing on both the mapped data and the selected data of the mapping method to apply the mapping independently to the mapped data bits. Reference numeral 91 designates the same substitution for duplication of a data bit, this substitution does not introduce a different mapping law, but beware of redundant unforeseen eliminations when these data are recombined. Reference numeral 92 denotes the same replacement operation, except that unpredictable information 95 is introduced to avoid the elimination involved in 91 . Reference numeral 93 similarly designates an alternative to an exclusive OR operation. Reference numeral 94 denotes the replacement of the DES S function lookup table (with six input bits and four output bits) by a precomputed lookup table using mapped values. In a pre-computation, the unpredictable data 96 and all possible input values 97 are combined with the original table to produce all mapped input-output combinations 98 for writing into the mapped look-up table 99 . Depending on design choice, this precomputation can be done before each use or multiple uses of the lookup table. The look-up table 99 is then used in a fully independent remapping operation (exclusive OR) that operates on the mapped data. No two data bit vectors in the figure can be used to reconstruct the original data. To achieve sufficient isolation, introduce delays in the signal path (such as by using timed latches between XOR operations).

Detailed introduction of the invention

password design

Consideration should be given to the choice of cryptographic algorithm. Proper cryptographic design can add little to the cryptographic processing overhead in the next step (cipher revision). It is very important that the equipment selected for cryptographic enforcement has the least possible complexity and the greatest possible degree of data privacy when it is exposed to side channel attacks. An understanding of the following techniques is essential in design.

Reusing a mapping in the same algorithm for multiple sets of data will provide an attacker with a potentially vulnerable flaw, but this flaw is not very serious (such as when only resisting first-order DPA attacks), so that by using the adder Great savings can be realized. This must be kept in mind in algorithm design.

A new mapping option may be used for every data value throughout the encryption device (including the output of each operation), otherwise a mapping may be used fixedly between two operations. When the two operations are unrelated, the latter is clearly not possible and may only be useful if complexity is kept low. Care must be taken that the mapping combined with all intermediate computed values guarantees the privacy requirements (eg when two values with the same mapping applied are combined via the XOR operator, a previously zero output will always be mapped to a zero value).

As shown in FIG. 3, each operator is replaced by an operator that performs an equivalent operation and causes all values to be mapped. The output map 39 ( _fc ) is determined from the input maps 35, 37 ( _fa and _fb ) and any changes to the center operation. For example, where the input mapping is the addition of an optional value to each adder input, the output mapping is the sum of the arbitrary values subtracted from the output, assuming that the central operation is invariant.

The original values 32, 34 and 36 (a, b, c) still appear in Figure 3, however not after the next step is applied. If it is impractical to find an appropriate alternative, then the operation performed on the mapped values is generally chosen to be the same as before (eg for addition), although it is also possible if the substitution is reasonable. Choose a different operation (eg for a random lookup table).

The next step is to merge the consecutive maps 43 and 45 (f _c and f _d ) from the cascaded operations 41 and 47 into a single map 49 (f _cd ), as shown in FIG. 4 . This mapping must not, even intermediate computed values, produce the original data or any data related to the original data. This is usually achievable when the mapping 49 consists only of information that cannot be used to derive information about the original data from the mapped values. The presence of relevant data provides prime targets for DPA attacks. For example, if the two mappings 43 and 45 were modulo additions of individual random values, mapping 49 would be the addition of the sum of these values, from which no information about the choice of each mapping can be deduced. Linked to adjacent operations, this mapping can be simplified. Here the choice of consecutive maps 43 and 45 is linked (ie the choice of one affects the choice of the other), the composite map can be slightly simpler or even become the same operation (and thus omitted).

When the concatenation operators 41 and 47 are unrelated, compound operations as performed by map 49(f _cd ) will be necessary. It will be performed using lookup tables or other algorithms if necessary. If one of the adjacent operations is a lookup table, the lookup tables resulting in the concatenation will be combined into one. After this step, except for input data, key data, and output data, all data in the calculation process remain confidential through the mapping. These external mappings will be handled separately in the next step.

Through careful cipher design choices and constraints on mapping choices, the modified cipher is not necessarily more complex than the original cipher, ignoring the mapping choices, operations, and mappings external to the modified cipher 57. The amount of calculation involving mapping in each operation is kept to a minimum. The resulting mathematically equivalent cipher is shown in FIG. 5 .

Initial storage of keys

In Figure 5, the original key, input data, and output data are still shown without the mapping applied, and when they are read by an operation, especially for mapping processing, they can still be the target of DPA attacks. Keys must only be stored in mapped form, where the choice of mapping has the necessary randomness. In addition, the information that encodes the selected method of the mapping must be stored. This initial storage is only necessary when the initial or master key is downloaded (typically in a protected environment), and never for keys downloaded in encrypted messages (see Encryptor Output Data mapping). This can be expressed as: first storing the key k by applying the mapping k ₀ =f ₀ (k), while storing the information identifying the selected method of the mapping f ₀ . The mapping family will most commonly be chosen according to the operator used in the encryptor, where keys are used to avoid unnecessary duplicate mappings.

per key map

Even if stored by an application map, as in the initial storage of the key, repeated reads may lead to the retrieval of secret data and map information by first-order DPA techniques (for example, by analyzing the average of groups of monitoring records). Therefore, before each use of the key, the mapping should be replaced with a new, randomly selected mapping subject to the constraints imposed by the design. The raw data of the key must never be calculated, even if only as a temporary variable in the process. This leads to derivation of values in the form k _i =g _i (k _i-1 ) and f _i =g _i ⁰ f _i-1 . The latter means deriving f _i such that f _i (q) = g _i (f _i-1 (q)) holds for any q. The values _ki and f _i will replace the stored values ki _-1 and f _i-1 . These values will remain related by the equation _ki = f _i (k).

Encryptor input data map

The input data 52 (x in FIG. 5) is first mapped through the mapping relationship selected for these inputs. This is similar to the initial mapping of keys (see Initial storage of keys), except that all data will be processed, such as ciphertext received to be decrypted or plaintext to be encrypted for transmission. Where extremely confidential data (such as keys) are to be encrypted, they must have been stored in mapped form and replaced by appropriate mappings (as described in Key Mapping).

Encryptor output data map

The output will be mapped back to its original value, at which point its secrecy is irrelevant (e.g. a ciphertext has been generated for transmission). When this data must be kept secret (such as keys after transmission), they and mapping selection method information should be stored and not reverse mapped back to the original form. Therefore, the above mentioned initial mapping of keys will not be used for the received and decrypted keys. This makes the process of downloading keys DPA resistant.

Example 1: Implementing a DPA defense based on an XOR-based cipher

In this example, a very simple cipher consists entirely of modulo-2 addition-exclusive-or-operations in octets (vectors of each octet) and a single look-up table for each 8-bit input Produces 8-bit output. Due to the simplistic nature of ciphers, only a single set of data can be securely encrypted (as in a Vernam cipher or one-time extender) corresponding to the use of the key, although repeated encryption of the same data can achieve order DPA resistance. Per-use key mapping is not specified, but it is necessary in defense against DPA. This example attempts to illustrate the design of a cipher for use in a strictly defined computing environment, such as that used in integrated circuit cards. He uses a single lookup table instead.

In this example, the mapping is applied to each 8-bit data with k _ni =A _i k _n + _bi , x _ni =A _i x _n +c _i and y _ni =A _i y _n +d the form of _i . The subscripts n and i represent the octet selection and cipher usage count in each data group, respectively. A _i is a full-rank 8×8 matrix of randomly selected bits, and each of b _i , c _i and d _i is a randomly selected 8-bit byte.

This example will be described below in conjunction with the operation in FIG. 8 . A typical cipher (encryption or decryption) may use many operations, and the data size of each k, x, y is generally at least 64 bits. Each arrow represents the flow of an octet. The figure shows the equivalent operation of the mapping of the data. Both the initial and incremental (described in each keymap) mappings of keys are shown in the keymap.

The key k _n,0 =A ₀ k _n +b ₀ and the mapping f ₀ =A ₀ ,b ₀ ) after the initial mapping are stored.

Preferably, a new mapping is determined by selecting new G _i and _hi before using the key. We replace k _{n, i-1} with k _{n, i} = G _i k _{n, i-1} + h _i , A _i-1 with A _i = G _i A _i-1 , and b _i-1 with b _i =G _i b _ii +h _i .

Each lookup table s is replaced by its equivalent value s _i to operate on the mapped value, defined as s _i (z)=A _i s(A _i-1 (z+b _i +c _i ) )+d _i . The input data octet x _n is mapped using the correlation map x _n,i =A _i x _n + _ci . The mapped input is encrypted using the original encryptor instead of the replaced lookup table. Other than per-key mappings, replaced lookup tables, initial mappings, and final mappings, there are no computational changes involved in the encryption procedure.

Finally, when the output y is kept secret, e.g. by a key, use y _i , A _i and d _i instead of y. If it is mapped to its original state, this will be expressed as y _n =A _i-1 y _n,i +d _i .

An important observation is that due to the large number of possible mappings (2 ^70.2 ), the same mapping can be used for efficient encryption of more than one 8-bit data. A simple mapping cannot guarantee that multiple bytes are sufficiently secure against DPA. Simplifications based on repeated use of the same mapping should be minimized, and should be feasible, mappings chosen for different data sets should be chosen separately.

Since the mapping (A _i , bi ₎ and the mapped data d change in each use, the processed data (including the key) has nothing to do with the original data. Only a few bits of the data and the mapped function are related to the original data. Each bit of raw data can be represented as a function of 17 bits being processed.

This example is applied to a strong encryptor, which can be effectively applied to currently used IC cards, including IC cards using 8-bit processors and small storage space.

Example 2: Implementing DPA defense of IDEA encryptor

This example illustrates the use of this concept when applied to a known cipher that was designed without any intent to defend against DPA.

The IDEA cipher, with the aim of being simple and easy to apply to most general-purpose computers, was intentionally designed to consist of three mutually incompatible operators—binary XOR, addition, and multiplication of 16-bit values. In order for this encryptor to implement DPA defense, since operators are incompatible with each other, a lookup table will be introduced in each data path for the purpose of mapping the mapped value from one operator to the next.

As in the example above, each XOR has a mapping, except that the length of the vector is increased to 16 bits. "Every time" mentioned above means that throughout the encryption process, the random mapping is not limited to the same mapping, and as long as remapping is performed, the mapping can be independently selected.

Adders have less freedom of choice of mapping than XOR operators. Multipliers have the same freedom of mapping choice as adders. The mapping must be randomly selected from an appropriate device, keys and data must be mapped accordingly, look-up tables must be generated, and encryption procedures must be executed.

Here, the system manages several lookup tables, the storage of information identifying the mappings applied to the keys, and the system workload of processing twice as many queries as there are operations performed, where each query managed by the system The tables each have 65536 16-bit words.

In a typical modern computer, these resources are readily available. As this example demonstrates, many existing applications can be easily secured against most DPA attacks using this technique. In this way, it becomes infeasible to use DPA that surreptitiously intercepts electromagnetic waves emitted from computers performing cryptographic operations.

It must be established that when a large amount of data needs to be processed, the mapping of these data should be updated from time to time during the processing.

Example 3: DPA defense implementing DES encryption

Data Encryption Standard (DES) encryption is widely used, although its 56-bit key length makes it vulnerable to exhaustive search attacks, but it is still widely used. It is also used in more secure synonymous ciphers such as Triple Data Encryption Algorithm (TDEA, more generally known as Triple-DES) and DESX (an encryption method derived from DES). Therefore, it is considered appropriate to apply the present invention to DES.

DES was not designed with DPA in mind. In general, the method used to increase the length of the password reduces the compatibility of mappings that may be used in subsequent operations. Three important operations are applied to DES - modulo 2 addition (exclusive OR), expansion (much like permutation, except some or all of the input bits are copied into two) and eight 6 to 4 bit look-up tables (called for S or a choice function). Shifts, bit permutations (reordering), and register swaps are not considered in this discussion, because these mapping choices for each data bit are simply followed (assuming the signals are kept in isolation) and need not be considered as related to the selected Operations with distinctly different mapping strategies. Replacing uncorrected bit shifting with corrected bit shifting including tracking map selection is illustrated at 90 .

While the use of special permutations, expansions, and XOR operations allows for a large set of mappings to data (including keys), any mapping involving multiple bits must be remapped to allow using only six bits of data at a time as The input of an S function. On this occasion, it is prohibited to treat the eight S-functions collectively as a single entity. For simplicity, mappings involving more than one data bit will not be considered here. This does not mean that more complex mappings with remapping after almost every operation have to be complex.

The mapping to be considered here involves the individual selection of each data bit processed in the algorithm. Although special care needs to be taken here to ensure that the order of the DPA defense is not lower than required, there are trade-offs that can be made to reduce the need for new random data such that the selection is relevant. This example will not cover the implementation of this compromise.

Assume in this example we ask for a ^2nd order DPA defense. To achieve this, we will use the principle that the required independent digit quantity must have a high value of 3 before any information about the original data can be reconstructed. Because digital signals can interact with each other in many unforeseen ways, the signals cannot be assumed to be independent unless they are properly isolated.

Signal isolation in general-purpose processors is usually much less isolated than implied by the functional description. For example, loading a value into a register such as an accumulator can be hidden for future use, such as determining whether the value is zero. Removing data from the circuit after a period of time before loading new data generally provides sufficient isolation even if minor interactions occur (like mutual heating of data or ion migration). Interactions between data values in word RAM that are not accessed directly, remain evident during execution of other accesses due to the execution of the addressing logic. Here, we assume that the hardware is implemented by data storage registers with appropriate properties. The first of these properties is that once data is removed from a circuit after a suitable time interval (such as a clock cycle), there will be no interaction with subsequent data in the circuit. The second property is that the mutual influence of data in discrete circuits is negligible, although a more conservative form of this property is that the mutual influence of data in discrete circuits is suitably isolated so that all circuits are connected at the same time. No data association signal transitions are generated. It is important to note that different bits of data that are processed simultaneously cannot generally be assumed to be isolated and therefore should not be considered independent.

We assume that all input data to the algorithm is in mapped form (a single bit of mapped data is described as a single bit), and for each data bit, there are two independently applied mappings, each with a unique Independently a map selects unpredictable bits of information. Each mapping is picked from a set of two. The first mapping in the group leaves the data bits unchanged, and the second swaps the two possible values. It can be found that if the three bits related to the original bit are combined using an exclusive OR operation, the original bit can be derived. Omitting any of the three bits would render the original data confidential (assuming each mapping choice is unpredictable, each case is equally likely, and there is no form of correlation between each choice).

In modifying the DES encryption, any mapped data bits are subjected to any transformations as before, and the associated mapped bits are tracked (90). The same is true for unrolling, except when bit-copying is done (including the case where all bits are copied), such copying shall be done independently unless further analysis indicates that this is not necessary (in the case of corrections such as in 91) . Using two independently selected maps (requiring two bits of random data), a composite map can be formed. The incoming mapping data can be applied to both pairs of mappings (remapping each replicated data separately using an XOR operation), plus for each replicated result, the combination derived for either of the two mappings selected map. This involves four unpredictable new option bits, one of which can be omitted associated with each incoming mapping without reducing security (shown at 92). The two replicated results are not correlated with each other and can be used together in subsequent operations without worrying that the subsequent combination will introduce DPA exploitable flaws. The XOR operation in DES encryption remains unchanged under this mapping, although a combined mapping is derived for the first and second mappings applied to each data bit. This definition can be done in hardware - when an exclusive OR of two map data bits is found, each select bit is combined with the corresponding select bit of the other data map using the same operation (93). The resulting three data bits are then used as mask data bits and two application maps. Choosing the smallest order that can sometimes be judiciously made relevant without reducing the minimum order of an effective DPA attack can reduce additional computational complexity and unpredictable data requirements as a result.

In the foregoing it must be noted that certain simplifications suggested in the description of the invention have been applied in this example. In particular, the mapping applied to the output of the superordinate operation is the same as applied to the input of the XOR operation, reducing remapping to the same operation (which can be omitted). Through data expansion (92), only enough additional unpredictable value (95) is added to ensure that subsequent operations will not reduce the DPA defense capability. Subsequent simplifications based on deliberate correlation of mapping choices are possible.

In this example, the S-function is the only area that remains addressed. By keeping the types of mappings chosen distinct from each other, we will limit the choices of mappings for the purposes of this example to mapping individual bits of data. When introducing simplifications, there are various approaches that can be taken. The approach taken here is to use new mappings based on the input of the function (lookup table), remap the input data (thus allowing multiple uses of the table), and combine the unpredictable situation of the input mapping and the output mapping of the lookup table to combine. When modifying the S-function look-up table (94), the remapping method is used here, but it must be kept in mind that the output bits of the S-function should be independent of the input bits. Before use, we randomly and independently select two mappings (96) for each input and output bit of the S-function from all other mappings for each possible input (generated in this example by counter 97 ). A replacement entry for the S-function table is written (98). Afterwards, remapping is performed on the mapped input data, using the S-function lookup table written with the mapping, and the selected output mapping is passed along with the input mapping and used for added unpredictability, although simplification may be performed. The S-function look-up table is stored in hardware registers (the sum of all register bits will be 2048 bits to implement eight S-functions) or in RAM. The values stored in this memory must be precomputed from the application map, in a sense, this guarantees the required resistance against 2 ^nd order DPA attacks. Each resulting mapped input value is used to address the register file and the mapped value is stored in selected four register bits.

The random bits of data introduced for data unwrapping (eg 95 in Modification 92) are usually expensive. In this case (assuming that the S-function output mapping is irrelevant), it can be omitted because the non-linearly related replication result is used as the input of the XOR operation each time. Since multiple keys are the result of replication, the refreshed S-function output map needs to ensure this non-correlation. Also consider that each key bit is used roughly an average of 14 times.

Computation of a new set of S-function tables for each DES cycle (16 cycles per cipher application) involves obtaining two random bits for each output bit (32 cycles per cycle), which is Very wasteful. In hardware, it is possible to recalculate the S-function table for each cycle of encryption. Because of this expense, a typical executive may reuse these lookup tables unchanged for more than one lookup, and possibly even more than one encryption algorithm call as such. This violates the previous assumption of a non-linear correlation between the output maps of the output data bits in different cycles, and care must be taken to determine under what circumstances this reduces the minimum order of a viable DPA attack. Furthermore, the strength of the side signal is related to the number of uses of the internal data bits, and this must be taken into account when determining whether the leakage of the signal is small enough. In some cases, it is necessary to keep the remapping random, especially for a key bit (which is used more than once). Another limitation caused by this simplification is that the input mapping of a data bit of an S-function is the same in every use before changing the content of the lookup table. There is no constraint on the mapping (including the key) used for individual data bits, but the mapping to the data must be replaced by a pair of mappings applicable to the input to the S-function. This should be done in two steps (via two separate XOR operations), applying the combination of the two maps (one to the S-function and one to the data) respectively.

The added complexity for ^2nd order defenses, other than the mapping used for data external to the modified central cipher, amounts to nearly three times the XOR operation and the S-function input and output with variable mapping, including random Use of Data. Externally, the data applied to it must be replaced with the mapped data and the mapped selection data, an initial mapping must be performed on the key, then an incremental mapping must be performed on it, and stored, where additional mappings are stored data. In this example, the storage requirements for the mapped data are tripled. The output data, here a key for DES, must be stored in this form for future use, except for the output mapping dependencies between the output bits, and since it is possible to utilize a refreshed mapping selection via the pair The output performs incremental mapping, which can eliminate the relatively static S-function mapping.

It is worth noting that until the S-function is considered, the distinction between the use of concealed values with mapped selected data and multiple "sharing" - equivalent to data being combined using algorithms to determine the original data - is not apparent on the surface. In particular, operations performed on mapped selection data are similar to those performed on mapped data. However, for the S-function (and any function not related to or more complex than mapping operations), it can be seen that the operations applied to the selected data of the mapping are related to the selection of the mapping, and indirectly related to the operation of the algorithm. In the process of mapping the input and output of the S-function, the processing of the mapping selected data is completely different from the similar operation on the "share" obtained from the original data.

advantage

A method of increasing the order of the DPA attack (essentially the number of points in the observed signal that are combined to obtain the original data). This makes the attack more cumbersome and complex.

By extending the previous concept of concealing all (or at least more) of the possible mappings to allow core operations to remain unchanged, the attacker's job is made more difficult. For economical reasons, by associating the mapping selection method applied to one data bit with the mapping selection method of another data bit, the large number of possible mappings can be reasonably simplified without causing excessive data leakage.

Furthermore, the number of monitoring times necessary to extract the original data from the noisy side channel monitoring is sufficiently increased, and the effect is more obvious than that achieved by hardware masking, and the hardware masking provided is sufficiently high. This increase can even be effectively applied to high-order DPA attacks.

Still further, the required data storage and processing is not as much increased as in some related schemes. An example of these schemes is that each data bit is represented by a pair of data bits, the first value is chosen at random and the second is the original bit when the first bit is zero, and its value when the first bit is one Boolean transformation (binary "exclusive OR").

Still further, the system containing the cryptographic components remains unaffected (eg, the protocol remains the same), although the cryptographic choices are optimized to facilitate the use of the technology.

Furthermore, this technique can be applied to both symmetric (with a single, shared key) and asymmetric (with different but related keys) ciphers.

Furthermore, this technique can also be applied in combination with other techniques used to improve DPA defenses by continuously modifying the key using a complex function that takes the same form in both encryption and decryption.

Claims (25)

1. one kind is used for reducing the data processing method of data being carried out the risk of unauthorized access, and this method comprises, with one or more steps of following any order:

(a) import the first private data group to processor, comprise the repetition of this follow-up step that may exist;

(b) a unpredictable data source is provided for this processor;

(c) a kind of method is provided for this processor, is used to use unknowable data to select suitable mapping;

(d) at least a algorithm is provided for this processor, is used for the first private data group is mapped to projected forms;

(e) the first private data group is carried out initial mapping, so, it is stored with the form after shining upon with by use the mapping of selecting unpredictablely;

(f) the correction algorithm executive program is with to the data after the mapping with comprise that other data of unpredictable data carry out computing, select so that output is mapping back data and mapping, it is minimum to possibility relevant between the output of the primal algorithm of original input data computing and the above-mentioned output;

(g) utilize the secondary of unpredictable information to shine upon by use, changed into the data map that is applied to any data from previous data map;

(h) data of input are shone upon, to input to revised algorithm executive program; With

(i) to shining upon, in order to further using from the data of revised algorithm executive program output.

2. the method for claim 1, wherein the private data group of step (a) is to be selected from a key and/or a random value.

3. the method described in claim 1 or 2, wherein the unpredictable data source in the step (b) is selected from a hardware or a pseudorandom number generator and/or stored private data.

4. as the described method of above-mentioned any one claim, wherein the data that its mapping changes in step (g) are storage, that send or intermediate computations data.

5. as the described method of above-mentioned any one claim, comprise to put on the mapping steps of mapping back data and/or these data by the secondary mapping of using unpredictable information to choose.

6. as the described method of above-mentioned any one claim, comprise hiding to the primary data that is mapped as storage.

7. as the described method of above-mentioned any one claim, wherein the mapping of data map and/or secondary data shows as question blank.

8. as the described method of above-mentioned any one claim, wherein the mapping of data map and/or secondary shows as a kind of algorithm that data or parameter are selected in mapping.

9. as the described method of above-mentioned any one claim, wherein data and/or the mapping after the mapping is transmitted to a remote unit.

10. as the described method of above-mentioned any one claim, mapping is performed as one group of mapping choosing, so that when the input operation object is replaced by using this mapping,, from the output result, be resumed out by using the original output of mapping from the input mapping.

11. method as claimed in claim 10, wherein for any operand, the set of all input mappings can be determined from the output mapping.

12. as the described method of above-mentioned any one claim, wherein choosing of mapping is arbitrarily, so that each data can be mapped to the arbitrary value in the determined scope of this mapping selection of serving as reasons.

13. as the described method of above-mentioned any one claim, wherein the computing of primal algorithm is the mould-m addition that is designated as x+y ≡ z (mod m), and employed corresponding computing remains unchanged in the revised algorithm, operable mapping is designated as x _i≡ a _iX+b _i(mod m), y _i≡ a _iY+c _i(mod m) and z _i≡ a _iZ+b _i+ c _i(mod m) wherein shines upon a _iBe and m prime number each other, and b _iAnd c _iBe arbitrary value, so a _i, b _iAnd c _iBeing limited in 0 arrives within the scope of m-1.

14. method as claimed in claim 13, wherein m has m=2 ⁿForm, so for corresponding to a _iAll odd number values and b _iThe input x of all values, have 2 ^2n-1Individual effective mapping is selected, and in selecting for these each, for corresponding to c _iThe output y of all values, have 2 ⁿIndividual effective mapping is selected, wherein a _i, b _iAnd c _iBeing limited in 0 arrives within the scope of m-1.

15. as any one described method among the claim 1-12, wherein corresponding to the computing of the primal algorithm of the mould that is designated as xy ≡ z (mod m)-m multiplication, remain unchanged with the corresponding computing that is applied to revised enciphered method, operable mapping is designated as x _i≡ b _ix ^Ai(mod m), y _i≡ c _iy ^Ai(mod m) and z _i≡ b _ic _iz ^Ai(mod m) wherein shines upon a _iBe and Φ (m) (the Euler Φ function of the m) arbitrary value of prime number, and b each other _iAnd c _iBe and the m arbitrary value of prime number each other.

16. as the described method of above-mentioned any one claim, wherein mapping comprises that two n-dimensional vectors are at Z ₂Addition on the territory.

17. method as claimed in claim 16, the mapping that wherein is applied at least one vector has x _i≡ A _iX+b _iForm (vector of expression expression and capitalize matrix of expression) here, A wherein _iIt is matrix with inverse matrix

In any one, b wherein _iBe 2 ⁿArbitrary value in the individual value.

18. method as claimed in claim 17 comprises A _iAnd/or b _iThat determine, restricted or selection mechanism at random, wherein matrix A _iThe position that comprises unit matrix and vector is changed.

19. as the described method of above-mentioned any one claim, algorithm wherein comprises the use of monadic operator.

20. method as claimed in claim 19, wherein operator is corrected for and almost allows to carry out mapping arbitrarily on the input and output path of operator.

21. a deal with data is with the method for reduction to the risk of the unauthorized access of data, this method comprises by data hidden, this is by changing the mapping to some or all processed data, realizing so that it is mapped as a kind of projected forms that is used to calculate and/or store.

22. a deal with data is to reduce or to weaken computer system or the algorithm to the risk of the unauthorized access of data, this system comprises following one or more step:

(a) processor is used to utilize first key that is used by this processor, handles first data set;

(b) make this processor have a kind of at least one that is used for first data set and key at least and be mapped as the algorithm of mapping back form;

(c) storage device is used for storing with projected forms at least one of first data set and key;

(d) correction algorithm executive program is to carry out computing to the data after the mapping;

(e), periodically change data map from formerly data map by using Quadratic Map;

(f) the input data are shone upon, to input to revised algorithm executive program; With

(g) mapping is from the data of revised algorithm output, in order to further using.

23. the system as claimed in claim 22 or algorithm further comprise data input device and data output device.

24. as claim 22 or 23 described system or algorithms, further comprise communication device, to carry out communication with remote computer or terminal.

25. as the described method of above-mentioned any one claim, wherein shining upon choosing method is determined by any means, comprise and determine that use can be predicted or unpredictable information, have all even inhomogeneous possibility on possible or effective choice method, and have the method for restriction of the scope of the choosing method that is applied to can be used for any prerequisite.

Images