Abstract:
The invention relates to a cryptographic mechanism and to a cryptographic device incorporating such cryptographic mechanism. The cryptographic mechanism offers a better resistance to side channel attacks than that of known cryptographic mechanisms by incorporating a new type of masking mechanism.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to methods for protecting cryptographic devices against side channel attacks, and to cryptographic devices embedding such methods. 
     2. Description of the Related Art 
     As known in the art, cryptographic devices are devices implementing cryptographic mechanisms. Examples of cryptographic devices include smart cards, USB keys, dongles, Personal Digital Assistants (a.k.a PDAs), mobile phones, personal computers (a.k.a PCs), etc. Such cryptographic devices are used in particular for securing a user&#39;s electronic transactions. The expression “electronic transaction” is to be taken in its broadest meaning. I.E. it is not limited to financial transaction but also contain any Internet transaction, any transaction occurring through a telecommunication network etc. Securing electronic transactions may comprise the cryptographic mechanisms of digitally signing electronic documents, decrypting electronic documents, negotiating session keys with a third party and/or authenticating a user. The above four cryptographic mechanisms are well known in the art. They are not limitative (other cryptographic mechanisms exist), and not mandatory (for example a cryptographic device does not necessarily embed a digital signature mechanism). 
     Cryptographic mechanisms have an input and an output. For example, an encryption mechanism may have an input consisting of a plaintext and an output consisting of a ciphertext. When first cryptographic devices were designed, people had the feeling that the only attacks possible on their cryptographic mechanisms consisted in attacking the input and output. However, it turned out that cryptographic devices are also susceptible to so-called “side channel attacks”. Side channel attacks rely on the fact that a cryptographic device has input and output means other than the legitimate input and output means. For example use of illegitimate, input means may comprise altering cryptographic operations by heating the cryptographic device, by modifying its clock (e.g. speeding up above the recommended limit), by putting it under UV light, X-Ray, or ultrasonic waves, by shaking it or otherwise mechanically acting on it, etc. Such alteration can be carefully designed (for example a glitch can be introduced at the exact moment that a counter is about to be decremented) or can be random (for example the aim might simply be to induce a random fault and analyze the consequence of the fault, which may leak sensitive information). Use of illegitimate output means may comprise analyzing the power consumption of the cryptographic device (e.g. an electronic component requires more electric power to perform a complex operation such as “square and multiply” than it does for a simple operation such as “square only”), analyzing the electromagnetic field created by the cryptographic device, analyzing the sounds emitted by the cryptographic device, etc. Well-known side channel attacks include Simple Power Analysis (SPA), Differential Power Analysis (DPA) or Differential Fault Analysis (DFA). 
     Cryptographic mechanisms consist of mechanisms involving at least a secret D which is supposed to be stored securely in a cryptographic device. D should not be leaked outside the cryptographic device through any attack. In a manner known in the art, D can be represented in the form of an n-bit number (d 0 , d 1 , . . . d n−1 ) 2 , where d i  is a bit (for each integer i between 0 and n−1). In the rest of the document, the exponent D will be denoted {d 0 , d 1 , . . . d n−1 } 2  instead of (d 0 , d 1 , . . . d n−1 ) 2  as is usually the case in mathematics in order not to introduce any ambiguity with the reference signs placed in the claims between parentheses as per the European Patent Convention. 
     In abstract algebra, which is a branch of mathematics, a monoid (M, ⊥) is defined as an algebraic set, the set being closed under an associative binary operation ⊥, the set having an identity element. Contrary to a group, in a monoid every element does not necessarily have an inverse. The operation ⊥ can also be represented with other symbols. For example, the operation ⊥ can be represented as an additive operation (symbol +), as a multiplicative operation (symbol *), etc. This representation is purely formal and does not affect the properties of the monoid. In the rest of the application, monoids will be represented with the multiplicative operation *, and will be denoted {M, *} instead of (M, *) in order not to introduce any ambiguity with the reference signs placed in the claims between parentheses as per the European Patent Convention. 
     Monoids are widespread in cryptography. The most widespread monoids in the field of cryptography are large monoids having many invertible elements, e.g. 2 80  invertible elements. For example, with the RSA algorithm, almost all elements are invertible (the exceptions being in particular the multiples of p and q). M* denotes the set containing all invertible elements of the set M of the monoid {M, *}. 
     In the rest of the application, all monoids are abelian monoids, that is monoids in which all elements commute. 
     Cryptographic mechanisms particularly sensitive to side channel attacks comprise mechanisms in which for each d i  equal to a certain value v (i.e. v=0 or v=1), the mechanism calculates X 2  and Y*Z (where X, Y and Z are three elements of a monoid {M, *}), and for each d j  equal to the other value (d j =1−v), the mechanism calculates T 2  (where T is an element of the monoid {M, *}). Examples of such mechanisms include RSA modular exponentiation. 
     X 2  is called a squaring operation and stands for X*X. 
     X n  stands for X*X* . . . *X where X appears n times. 
     Note: in a monoid with an additive notation, X 2  would be written 2X and would stand for X+X. Similarly, X n  would be written nX and would stand for X+X+ . . . +X where X appears n times. 
     Y*Z is called a multiplication operation. 
     The invention improves the resistance of above-mentioned particularly sensitive cryptographic mechanisms to side channel attacks. Examples of such mechanisms include elliptic curve point multiplications, and modular exponentiations used when performing an RSA operation or a Diffie Hellman key establishment. The invention also limits the amount of processing required for securing the cryptographic mechanisms. It does so by introducing a particular type of masking mechanism (also known as blinding mechanism). 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention and its advantages will be explained more in details in the following specification referring to the appended drawings, in which: 
         FIG. 1  represents a typical cryptographic mechanism without any protections against side channel attacks. 
         FIG. 2  represents a cryptographic mechanism with a first level of protection against side channel attacks, known in the art as the “balanced modular exponentiation algorithm”. 
         FIG. 3  represents a cryptographic mechanism with a second level of protection against side channel attacks, known in the art as “Joye &amp; Al. modular exponentiation algorithm”. 
         FIG. 4  represents a possible masking mechanism for modular exponentiation. 
         FIG. 5  represents a preferred cryptographic mechanism according to the invention, offering a higher level of protection against side channel attacks. 
         FIG. 6  and  FIG. 7  represent variants of the mechanism of  FIG. 5 . 
         FIG. 8  is a schematic illustration of a cryptographic device, for example, a smart card. 
         FIG. 9  is a block diagram illustrating programs that may be stored in the cryptographic device of  FIG. 8 . 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 1  describes an example of cryptographic mechanism consisting of a modular exponentiation. This sort of modular exponentiations is implemented in particular with RSA and Diffie Hellman algorithms. 
     As can be seen on step  2 , for each bit d i  of the exponent D, a modular squaring is performed (sub-step  2 . i ). When d i  is equal to 1, a modular multiplication is performed (sub-step  2 . ii ). 
     D is usually derived from a random number. In general, the hamming weight of D is approximately n/2. Therefore, in general the method of  FIG. 1  involves n modular squaring operations and around n/2 modular multiplications. 
     As known in the art, this type of cryptographic mechanisms is extremely sensitive even to the simplest side channel attacks such as SPA. Indeed, the power consumption is not the same during the execution of the multiplication operation and of the squaring operation. Therefore, one can put a probe on the cryptographic device implementing the cryptographic mechanism, measure the power consumption, and distinguish the multiplication and the squaring in the power trace, thereby identifying the value of all bits d i . The exponent D is then recovered by the attacker. 
       FIG. 2  describes an example of cryptographic mechanism comprising a first level of protection against side channel attacks, known in the art as the “balanced modular exponentiation algorithm” 
     This method is similar to the one of  FIG. 1 , except that when d i  is equal to 0, a third step iii is added, in which a dummy multiplication is executed. Thanks to this third step, the power consumption is very close whether the bit is equal to 0 or to 1. 
     The complexity of this method is increased since there are n multiplications and n square operations. However its resistance to basic side channel attacks is improved as well, as indicated above. 
     Unfortunately, this method remains very sensitive to another side channel attack known as the SE attack (safe error attack). Indeed, if the cryptographic mechanism is disrupted during a dummy multiplication, the multiplication fails, but the final result remains unaffected since the dummy multiplication is not used for the final result. Therefore an attacker can find out the dummy bits, which are bits equal to 0 in this example, and infer that all other bits are equal to 1, which results in the secret value of D being recovered. 
       FIG. 3  describes an example of known cryptographic mechanism comprising a second level of protection against side channel attacks, known in the art as “Joye &amp; Al. modular exponentiation algorithm”, and disclosed at CHES 2002 by Joye and Yen. It is based on the Montgomery Ladder algorithm. 
     The cryptographic mechanism of  FIG. 3  aims at overcoming the limitation of the cryptographic mechanism of  FIG. 2 . 
     To this end, there is no more dummy operation. Instead, The result of all multiplications is used in the final result (except in the last round). Therefore disturbing the mechanism always leads to an erroneous output. 
     The complexity of this cryptographic mechanism is the same as the one of  FIG. 2  (n multiplications, n square operations). 
     However, this cryptographic mechanism is still sensitive to DPA attacks. As known in the art, in a DPA attack, if the attacker is able to set the value of the input X, he can predict the value of the next intermediate value of steps i and ii by making assumptions on the values of d i  and verifying them by studying correlations in the power consumption over a number of selected samples. 
     It is an object of the invention to improve known techniques such as the cryptographic mechanism of  FIG. 3 . 
     It would be possible to combine the teaching of  FIG. 3  with a masking mechanism, as shown on  FIG. 4 . The masking may consist in multiplying the input element with a random number, thereby rendering the prediction step of the DPA attacks impossible. Unfortunately, the technique shown on  FIG. 4  requires approximately 4*n operations, which makes it twice slower than previous techniques. The technique shown on  FIG. 4  also performs the modular exponentiation twice. A first time for the masked input, and another time for the mask used for the masking. Due to this double modular exponentiation, the secret exponent D is used twice, which potentially weakens the mechanism. 
     A cryptographic mechanism according to the invention involves a secret D which can be represented as an n-bit number {d 0 , d 1 , . . . d n−1 } 2 . The cryptographic mechanism is arranged to calculate an output element OUT equal to X D , X being an element of a monoid {M, *}. The mechanism comprises a first variable VAR 0  and a second variable VAR 1 . The cryptographic mechanism comprises n steps {MUL i } i=n−1 . . . 0  such that during each step MUL i , the cryptographic device calculates VAR 1−di *VAR di , and n other steps {SQ i } i=n−1 . . . 0  such that during each step SQ i , the cryptographic device calculates VAR di *VAR di . Each step SQ i  is executed after the step MUL i  for any i between 0 and n−1, and each step MUL i−1  is executed after step MUL i  for any i between 1 and n−1. The mechanism is characterized in that it comprises the steps of:
         a. generating a random element MSK_INPUT,   b. creating a masked element MASKED_X by using the element X and the random element MSK_INPUT,   c. calculating a masked output element MASKED_OUT using the masked element MASKED_X, the calculation of the masked output element MASKED_OUT involving the abovementioned steps {MUL i } i=n−1 . . . 0  and {SQ i } i=n−1 . . . 0 ,   d. calculating an output mask MSK_OUTPUT from the random element MSK_INPUT without involving the secret D,   e. calculating the output element OUT using the masked output element MASKED_OUT and the output mask MSK_OUTPUT,       

     wherein the step d occurs at any time between step a and step e, and 
     wherein the steps a, b, c, e are consecutive. 
     As seen on  FIG. 5 , the computation of the output mask can take place together with the computation of the masked output element. As seen on  FIG. 6 , this computation can also take place serially (either after, as shown on step  4  of the figure, or before). It is also possible to perform this computation in parallel, for example inside two different threads, as depicted on  FIG. 7  (C.F. steps  3   a  and  3   b ). 
     Thanks to the masking operation, the DPA attack is no longer applicable, as the attacker does not know the mask and does not have the possibility to make assumptions regarding the intermediate results. 
     The element X can be an input element supplied to the cryptographic mechanism by another mechanism, or can be generated inside the cryptographic mechanism. For example, in a cryptographic mechanism consisting of a timestamp mechanism, the current time may be determined securely inside the mechanism and then digitally signed inside the mechanism. 
     Similarly, the output element OUT can be communicated by the cryptographic mechanism to another mechanism, can be kept internally in the cryptographic mechanism, or can be post-processed in the cryptographic mechanism and sent to another mechanism in the post-processed form. 
     In preferred embodiments, the cryptographic mechanism according to the invention is such that the random element MSK_INPUT belongs to M* (the set of invertible elements of M, as seen above). If MSK_INPUT is equal to a value R, we denote by R −1  the inverse of R for the operation * of the monoid {M, *}. With cryptographic mechanisms where the function f: MASKED_X→MASKED_OUT is such that there exists a function g such that f(R*X)=g(R)*f(X), one can apply a mask MSK_INPUT on the element X by multiplying X and R, and compute the output mask (g(R)) −1  to apply on the masked output in order to obtain the output element. In certain instances (g(R)) −1  may be equal to g(R −1 ). In such embodiments, the inverse element R −1  may therefore be used to compute the output mask MSK_OUTPUT. 
     Preferred cryptographic mechanisms according to the invention may be such that the calculation of the output mask MSK_OUTPUT comprises n steps {R_SQ i } i=n−1 . . . 0 , such that during each step R_SQ i , the cryptographic device calculates MSK i *MSK i , MSK i  being an element of the monoid {M, *}, the initial value MSK n  being obtained from the inverse of the random number R, the last value MSK 0  being the output mask MSK_OUTPUT used to unmask the value of the masked output MASKED_OUT. This is advantageous in particular for mechanisms associated with a function g such that the computation of the function g may be executed by involving the steps R_SQ i . 
     More specifically, in a preferred mechanism according to the invention, MSK i  may be equal to MSK i+1 *MSK i+1  for i equal to n−1 down to 0. This is particularly advantageous for mechanisms associated with a function g: MSK n →MSK 0  where MSK i =MSK i +*MSK i+1  for i equal to n−1 down to 0. 
     In a preferred cryptographic mechanism, the masked element MASKED_X is equal to X*R and the output element OUT is equal to MASKED_OUT*MSK 0 , MSK n  being equal to R −1 , the initial value of the first variable VAR 0  being set to the value R of the random element, the initial value of the second variable VAR 1  being set to the value of the masked element MASKED_X, each step MUL i  consisting in calculating VAR 1−di *VAR di  and storing the result in VAR 1−di , each step SQ i  consisting in calculating VAR di *VAR di  and storing the result in VAR di . 
       FIG. 5  describes an example of such preferred embodiment of the invention comprising:
         1. a first step in which a random number is generated. This can be done for example by a hardware random number generator embedded in a cryptographic device implementing the cryptographic mechanism. Indeed, the random number is preferably as unpredictable as possible, which is best achieved with hardware means as known in the art;   2. a second step in which variables VAR 0 , VAR 1  and MSK n  are initialized;   3. a third step in which a masked output (value of VAR 0  after the last round of the loop) is calculated from the masked element, and an output mask MSK 0  is calculated;   4. a fourth step in which the masked output is unmasked with the output mask MSK 0  and is returned to the entity which invoked the cryptographic mechanism.       

     The cryptographic mechanism uses the element X and the secret D as inputs. In preferred embodiments, the secret D is stored securely and therefore does not need to be passed to the cryptographic mechanism each time the cryptographic mechanism is invoked. The element X is generally passed to the cryptographic mechanism as an input parameter, but may also be determined by the cryptographic mechanism itself (e.g. as seen above with time stamps based on a clock available in the cryptographic mechanism, etc.). 
     The invention also concerns a cryptographic device storing a secret D and implementing a cryptographic mechanism as described above. The invention concerns more particularly cryptographic devices of the smart card type. 
     The invention is particularly advantageous for embedded systems such as smart cards as it has very few additional requirements compared to state of the art cryptographic mechanisms. It is well suited to the RSA algorithm. Indeed, it does not require any additional information on the key material compared to traditional cryptographic mechanisms. In particular, it does not require the public exponent of the RSA key pair to be available to the cryptographic mechanism. 
     It is similarly advantageous for the Diffie Hellman algorithm, as it does not require any extra parameter, and is therefore very convenient in particular for establishing session keys in static mode. 
     It is also advantageous for both above algorithms in that it does not require an additive mask on the exponent, nor on the element X, which would require a more powerful processor (or crypto processor in case the cryptographic algorithms are implemented partially or fully in hardware). 
     The complexity of the preferred embodiment of  FIG. 5  involves approximately 2*n square operations and n multiplications, i.e. around 3*n CPU intensive operations, which is only 50% more than the closest method (Montgomery ladder of  FIG. 3 ), and does not require much more RAM (50% at most). 
     It should be noted that for some random elements used as input masks, the steps SQ_RD i  may lead (for a certain value i_weak of the index i) to MSK i     —     weak =1, in which case all subsequent values (MSK i     —     weak−1 , MSK i     —     weak−2 , etc.) are equal to 1 as well. This situation corresponds to a weak output mask, since it is equivalent to not having an output mask (the masked output and the output are equal). However, this weakness is hard to exploit, and is very unlikely to happen. The probability of a random element leading to a weak mask is very low. For example, it is estimated that for RSA 2048, the probability of picking a weak random element is at most equal to 1.9*10 −7 . The probability depends on the value of the RSA key, and in practice it is often much lower than the above value. The probability can be made arbitrarily small by picking several invertible random elements and multiplying them together (only if all elements are weak will the product of the elements be weak). 
       FIG. 8  is a schematic illustration of a cryptographic device  109 , for example, a smart card. The cryptographic device  109  may include a processor  201  connected via a bus  202  to a random access memory (RAM)  203 , a read-only memory (ROM)  204 , and a non-volatile memory (NVM)  205 . The cryptographic device  109  further includes an input/output interface  207  for connecting the processor  201 , again typically via the bus  202 , to a connector  211  by which the portable security device  109  may be connected to the host computer  103 . The connector  211  may include power connections. 
     The NVM  205  and/or ROM  204  may include computer programs  301  as is illustrated in  FIG. 9 . While it is here depicted that the computer programs  301  are all co-located in the ROM  202  or the NVM  205 , in actual practice there is no such restriction as programs may be spread out over multiple memories and even temporarily installed in RAM  203 . Furthermore, the cryptographic device  109  may include multiple ROMs or NVMs. The programs  301  include operating system programs as well as application programs loaded on to the cryptographic device  109 . The NVM  205  or ROM  202  may also contain private data, such as a private key  209  or a shared secret key  210 , stored either in its basic form or in derived quantities. 
     The cryptographic device  109  programs  301  may include a cryptography module  213 , other programs  215 ,  217 , and the operating system OS  219 . The cryptography module, for example, may implement the cryptographic mechanisms described herein.