This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present principles that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present principles. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Modular addition is used in many cryptographic implementations. A well-known constant-time addition algorithm is the following, where ⊕ is a bitwise XOR operation and  a bitwise AND operation.
Algorithm 1 Adder algorithm (constant-time)Input: two k-bit operands (x, y)Output: A = x + y mod 2k/* Initialization */1: A ← x ⊕ y2: B ← x   y3: C ← 0/* Main loop */4: for i = 1 to k − 1 do5: C ← C   A6: C ← C ⊕ B7: C ← 2C8: end for/* Aggregation */9: A ← A ⊕ C10: return A
With this algorithm, the carry ci computed in step i using the register C is recursively defined as
      c    i    =      {                                        0            ,                                                              for              ⁢                                                          ⁢              i                        =            0                                                                          2              ⁡                              [                                                      c                                          i                      -                      1                                                        ⩓                                                            (                                              x                        ⊕                        y                                            )                                        ⊕                                          (                                              x                        ⩓                        y                                            )                                                                      ]                                      ,                                                              for              ⁢                                                          ⁢              1                        ≤            i            ≤                          k              -              1                                          
Once the last carry ck−1 has been computed, the addition result is obtained asx+y=x⊕y⊕ck−1.
It will be appreciated that Algorithm 1 in some cases can be attacked using Differential Power Analysis (DPA) and related attacks introduced by Kocher et al. [see Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In M. Wiener, editor, Advances in Cryptology—CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 388-397. Springer-Verlag, 1999.]. Such attacks exploit side-channel leakage to uncover secret information. During the execution of a cryptographic algorithm, the secret key or some related information may be revealed by monitoring the power consumption of the electronic device executing the cryptographic algorithm. DPA-type attacks potentially apply to all cryptosystems, including popular block-ciphers like DES or AES.
The commonly suggested way to thwart DPA-type attacks for implementations of block-ciphers is random masking. The idea is to blind sensitive data with a random mask at the beginning of the algorithm. The algorithm is then executed as usual. Of course, at some step within a round the value of the mask (or a value derived thereof) must be known in order to correct the corresponding output value.
For cryptographic algorithms involving different types of operations, two masking techniques usually have to be used: a Boolean masking (generally by applying an XOR) and an arithmetic masking (by applying an +). Furthermore, it is useful to have efficient and secure methods for switching from Boolean masking to arithmetic masking, and conversely.
Two secure algorithms were proposed by Goubin [see Louis Goubin. A sound method for switching between Boolean and arithmetic masking. In ç. K. Koç, D. Naccache, and C. Paar, editors, Cryptographic Hardware and Embedded Systems—CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 3-15. Springer-Verlag, 2001.]. Each algorithm works in one direction: the first converts from Boolean to arithmetic and the second from arithmetic to Boolean. The secure Arithmetic-to-Boolean conversion is however less efficient than the secure Boolean-to-Arithmetic conversion. The cost of the latter depends on the length of the masked operands that is 5·k+5 operations, where k is the length of the operands. Thus, typically 5·32+5=165 operations are required for 32-bit inputs.
Generally expressed, the masking problem for modular addition, can be stated as how to securely compute the addition of k-bit operands x and y from Boolean masked inputs ({circumflex over (x)}, ŷ) while the k-bit result is still Boolean masked. A modular addition is a carried out with classical switching methods in three steps:                1. Convert first the Boolean masked inputs {circumflex over (x)}=x⊕rx and ŷ=y⊕ry to arithmetic masked inputs Ax=x−rx and Ay=y−ry using Boolean-to-Arithmetic conversion algorithm. This operation is efficient and takes 7 elementary operations (see Goubin's paper) for each conversion.        2. Perform two separate additions, one with the masked data and the other with the masks (Ax+Ay=x−rx+y−ry, rx+ry). This costs 2 operations; and        3. Convert the addition result of masked data back to a Boolean masked output {circumflex over (z)}=(x+y)⊕(Tx+ry) using an Arithmetic-to-Boolean conversion algorithm.        
The overall computation cost for one secure addition is then 5 k+5+2·7+2=5 k+21 operations using Goubin's conversion methods. A typical cost for one secure addition is thus 5·32+21=181 operations for 32-bit inputs.
To make Algorithm 1 masked, it must be ensured that the computations do not leak information about x, y or the carry ci. It is easily seen that the carry ci is a function of x and y. Thus, if the carry is not masked, it would leak information about x and y and this information could be used by an attacker to launch a side-channel attack (such as DPA). In his Arithmetic-to-Boolean conversion algorithm, Goubin proposed to blind the carry value using a random λ as ĉi−1=ci−1⊕2λ. This idea can be applied to Algorithm 1, which gives the following constant-time algorithm.
Algorithm 2 Adder algorithm (with blinded carry)Input: (x, y) ∈    ×  Output: x + y (mod 2k)/* Initialization */1: A ← x ⊕ y2: B ← x   y3: C ← λ/* Ω = λ ⊕ (x   y) ⊕ 2 λ   (x ⊕ y) */4: B ← B ⊕ C5: C ← 2C6: Ω ← C   A7: Ω ← Ω ⊕ B/* Main loop */8: for i = 1 to k − 1 do9: B ← B   A10: B ← B ⊕ Ω11: B ← 2B12: end for/* Aggregation */13: A ← A ⊕ B14: A ← A ⊕ C15: return A
From an efficiency perspective, it is interesting to re-use the same mask 2λ for all the successive carries. In Algorithm 2, a mask correction value Ω should thus be computed for each round as Ω=[2λ(x⊕y)⊕(xy)]⊕λ. As 2λ is re-used for every iteration, the correction term Ω is the same for each iteration. This term can thus be computed once and then passed along to all iterations of the masked carry-chain calculation. The skilled person will appreciate that it is preferred to use a new random mask for each new addition to ensure the uniform distribution of masks remains between two algorithm executions.
The masked version of the carry equation is as follows:
            c      ^        i    =      {                                                      2              ⁢                                                          ⁢              λ                        ,                                                              for              ⁢                                                          ⁢              i                        =            0                                                                          2              ⁡                              [                                                                            c                      ^                                                              i                      -                      1                                                        ⩓                                                            (                                              x                        ⊕                        y                                            )                                        ⊕                    Ω                                                  ]                                      ,                                                              for              ⁢                                                          ⁢              1                        ≤            i            ≤                          k              -              1                                          
At the end, ĉk−1=ck−1⊕2λ. Therefore, x+y can be obtained using two additional XOR operations in the Aggregation phase by calculatingx+y=x⊕y⊕ck−1⊕2λ
In previous algorithm only the carry is masked. It will be appreciated that it is desired to make such an addition more efficient and work with blinded inputs x and y. In other words to have a solution that is secure and uses less operations for the addition. The present principles provide such a solution.
USPTO Backgrounds
USPTO Backgrounds