TRANSITION FROM A BOOLEAN MASKING TO AN ARITHMETIC MASKING

Abstract

A method for the transition is provided from a Boolean masking of a value to be kept secret to an additive masking of the value to be kept secret. The value to be kept secret is present in the Boolean masking as a representation masked with a first Boolean mask and a second Boolean mask. A first additive mask and a second additive mask are determined for the value to be kept secret. A first masking transition is executed in which the first Boolean mask is converted into the first additive mask. A second masking transition is executed in which the obfuscation value is converted into an additive correction value, and a third masking transition is executed in which the second Boolean mask is converted into the second additive mask.

Claims

1.-15. (canceled)

16. A method for the transition, protected against spying out, from a Boolean masking of a value to be kept secret to an additive masking of the value to be kept secret, wherein the value to be kept secret is present in the Boolean masking as a representation masked with a first Boolean mask and a second Boolean mask, and wherein a first additive mask and a second additive mask are determined for the value to be kept secret, and wherein a first masking transition is executed, in which the first Boolean mask is converted into the first additive mask, wherein the first additive mask is a masked representation of an additive mask corresponding to the first Boolean mask, which additive mask is masked with an obfuscation value serving as a Boolean mask, a second masking transition is executed in which the obfuscation value is converted into an additive correction value, and a third masking transition is executed in which the second Boolean mask is converted into the second additive mask.

17. The method according to claim 16, wherein the obfuscation value serving as Boolean mask is determined randomly.

18. The method according to claim 16, wherein at least two further random obfuscation values are used and that each masking transition uses at least one of these further random obfuscation values or a value derived therefrom.

19. The method according to claim 16, wherein at least two further random obfuscation values are used and that both the first and the third masking transition respectively use at least two of these further random obfuscation values or values derived therefrom.

20. The method according to claim 16, wherein the first masking transition is executed with the value to be kept secret as the base value.

21. The method according to claim 16, wherein the second masking transition is executed with a base value which results from an additive mask corresponding to the first Boolean mask.

22. The method according to claim 16, wherein the third masking transition is executed with a base value which results from an additive masking of the value to be kept secret with an additive mask corresponding to the first Boolean mask.

23. The method according to claim 16, wherein the third masking transition is executed at least partly before the first masking transition or at least partly before the second masking transition.

24. The method according to claim 16, wherein the second additive mask is determined by applying the additive correction value in an additive operation to an additive mask corresponding to the second Boolean mask.

25. The method according to claim 16, wherein the second additive mask corresponds to the second Boolean mask and that the additive correction value is supplied as a further method result.

26. The method according to claim 16, wherein the method is embedded between two sections of a cryptographic calculation, wherein in the first section the masked representation is generated or processed by at least one operation which is compatible with the Boolean masking, and in the second section the masked representation is further processed by at least one operation which is compatible with the arithmetic masking.

27. The method according to claim 16, wherein at least one of the first, second and third masking transition is executed according to a method which, when regarded alone, is protected against first-order side channel attacks, but not against second-order side channel attacks.

28. The method according to claim 16, wherein the method serves for the protection against second-order side channel attacks.

29. A computer program product having a plurality of program commands which cause at least one processor to execute a method of claim 16.

30. A portable data carrier or chip module, having at least one processor and at least one memory, wherein the device is arranged to execute a method according to claim 16.

Description

[0026] Further features, objects and advantages of the invention can be found in the following description of several exemplary embodiments, alternative embodiments and exemplary implementations. Reference is made to the schematic drawing.

[0027] FIG. 1 as the only FIGURE shows a diagram illustrating the operations of an embodiment example of the invention and the data utilized and generated by these operations.

[0028] In FIG. 1 there is depicted a part of a cryptographic calculation, e.g. of a hash function or of an IDEA encryption or decryption. A masking transition method 10 according to an embodiment example of the invention is embedded between a first section 12 and a second section 14 of the cryptographic calculation. The operations of the cryptographic calculation executed in the first section 12 are compatible with a Boolean masking rule and are executed using several Boolean masks. The result of the first section 12 is a masked representation x of a value d to be kept secret, which is masked according to a Boolean masking rule with two Boolean masks s.sub.1, s.sub.2; thus it holds e.g. that x=ds.sub.1s.sub.2.

[0029] The second section 14 of the cryptographic calculation comprises further operations, which, however, are not compatible with the Boolean masking rule, but only with an additive masking rule. In the present embodiment example, the masking rule used in the second section 14 is x=d+r.sub.1a+r.sub.2a mod 2.sup.n, where r.sub.1a and r.sub.2a are each an additive mask and n indicates the word width in bits of the calculation performed. The masking transition method 10 should therefore determine, from the first masking of the value d to be kept secret with the Boolean masks s.sub.1, s.sub.2, a second masking which includes two additive masks r.sub.1a and r.sub.2a. In the configuration described first here, the masked representation x is to remain unchanged during the execution of the masking transition method 10, while this is not the case in other configurations described later.

[0030] In the embodiment example described here, the masking transition method 10 includes a total of three simpler masking transitions 16, 18, 20. These masking transitions 16, 18, 20 are here also referred to as first, second and third masking transitions. This, however, only serves to simplify the naming without implying an order of execution. In implementation variants, the three masking transitions 16, 18, 20 can be executed in a different order or e.g. in an interleaved fashion, i.e. for example first a part of the third masking transition 20, which does not require the correction value a, and only then the second masking transition 18.

[0031] Before describing the masking transitions 16, 18, 20 in more detail, now two general formulas are explained for a better understanding, with which masking transitions can be executed in a manner protected against first-order side channel attacks.

[0032] A masked representation x of a base value d to be kept secret, with a Boolean mask s is given, so that thus it holds that x=ds. What is to be calculated is an arithmetic mask r with which the masked representation x presents the base value d to be kept secret, for which it thus holds that x=d+r mod 2.sup.n with a given calculation bit width n. In order to secure the calculation against a first-order side channel attack, a random obfuscation value z is introduced. The arithmetic mask r then results from the formula:

r((dsz)(dz))s((sz)z)

[0033] This relation, hereinafter referred to as XOR2ADD formula, is already known in slightly modified form from EP 1 596 527 B1. The correctness of the XOR2ADD formula results from a consideration of the function defined by F(x, s):=(x(xs))mod 2.sup.n. For the above-mentioned masked representation x of the base value d to be kept secret and the above-mentioned Boolean mask s, the value F(x, s) presents the searched additive mask r, because it holds that d+F(x, s)=d+(x(xs))=d+xd=x. For the mapping F(_, s) it holds that: F(xy, s)=F(x, s)F(y, s)F(0, s). This results in the following equation chain:

[00001]$\begin{array}{c}r=.Math.F\left(x,s\right)\\ =.Math.F\left(\left(xz\right)\left(zs\right)s,s\right)\\ =.Math.F\left(xz,s\right)F\left(zs,s\right)F\left(s,s\right)\\ =.Math.\left(\left(xz\right)-\left(xzs\right)\right)\left(\left(zs\right)-z\right)s\end{array}$

[0034] The XOR2ADD formula follows by replacing the value x by ds in the just derived relation for r.

[0035] The above mentioned XOR2ADD formula can be extended by using not only one random obfuscation value z, but two obfuscation values z.sub.1 and z.sub.2. Depending on the security requirements, the obfuscation values z.sub.1, z.sub.2 may each be random in themselves, or there may be certain dependencies either between the obfuscation values z.sub.1, z.sub.2 among themselves or between one of the obfuscation values z.sub.1, z.sub.2 and another value. Using the two obfuscation values z.sub.1, z.sub.2, the arithmetic mask r then results from the following relation, which is referred to here as the extended XOR2ADD formula:

r=((dsz.sub.1z.sub.2)(dz.sub.1z.sub.2))((sz.sub.1)z.sub.1)((sz.sub.2)z.sub.2)

[0036] As already briefly explained above, the masking transition method 10 in the embodiment example shown in FIG. 1 starts out from a base value d to be kept secret, which is present in a first masking in the form of a representation x masked with two Boolean masks s.sub.1, s.sub.2 according to a Boolean masking rule; it thus holds that x=ds.sub.1s.sub.2. According to the present embodiment example, two additive masks r.sub.1a, r.sub.2a are determined, so that it holds that x=d+r.sub.1a+r.sub.2a mod 2.sup.n. In other words, a second masking of the base value d to be kept secret is ascertained, in which the masked representation x is also a masked representation according to an additive masking rule with the masks r.sub.1a, r.sub.2a. The masking transition method 10 shown in FIG. 1 utilizes for this one masking transition according to the XOR2ADD formula and two masking transitions according to the extended XOR2ADD formula. The masking transition method 10 is protected against second-order side channel attacks; even if two intermediate results are known, no information can be derived about the value d to be kept secret.

[0037] In an experimental approach, which is now first described as an introduction to the embodiment example, two additive masks r.sub.1, r.sub.2 with x=d+r.sub.1+r.sub.2 would be determined by first performing an inner masking transition from dSi to d+r.sub.1 and then an outer masking transition from (d+r.sub.1)s.sub.2 to (d+r.sub.1)+r.sub.2. Each of these two masking transitions is effected according to the experimental approach according to the extended XOR2ADD formula with suitable obfuscation values. Thus, according to the experimental approach, the value r.sub.1 with two obfuscation values z.sub.1, z.sub.2 results from the following relation, which is referred to as (A0):

r.sub.1=((ds.sub.1z.sub.1z.sub.2)(dz.sub.1z.sub.2))((s.sub.1z.sub.1)z.sub.1)((s.sub.1z.sub.2)z.sub.2)

[0038] When analysing the experimental approach just described, however, the inventors surprisingly realized that the calculation of r.sub.1 according to the relation (A0) is susceptible to second-order side channel attacks because an attacker could draw conclusions about the value d to be kept secret from the knowledge of n and Si. In the embodiment example described now, the experimental approach is hence modified to the extent that with the first masking transition 16 there is not determined the additive mask r.sub.1 corresponding to the Boolean mask Si, but instead a value r.sub.1a modified compared to r.sub.2. The value r.sub.1a, which presents the first mask searched for altogether, is the Boolean masking of the value r.sub.1 with another Boolean mask, namely a randomly selected obfuscation value a. Thus, it holds that r.sub.1a=r.sub.1a, from which the following relation (A1) results by inserting the above relation (A0):

r.sub.1a=((ds.sub.1z.sub.1z.sub.2)(dz.sub.1z.sub.2))((s.sub.1z.sub.1)z.sub.1)((s.sub.1z.sub.2)z.sub.2)a

[0039] Since in the equation x=ds.sub.1 s.sub.2 the exclusive-or-operations can be shifted arbitrarily from the right to the left side, the relation (A1) can also be written as relation (A2) as follows:

r.sub.1a=((xs.sub.2z.sub.1z.sub.2)(xs.sub.1s.sub.2z.sub.1z.sub.2))((s.sub.1z.sub.1)z.sub.1)((s.sub.1z.sub.2)z.sub.2)a

[0040] The relation (A2) depicts the first masking transition 16 according to the embodiment example described here. With a suitable implementation, the calculation of the relation (A2) is secure against second-order side channel attacks.

[0041] As according to (A2), the value r.sub.1a was calculated instead of the actually desired value r.sub.1, a correction step is required in the embodiment example described here, for which the Boolean obfuscation value a is converted into a corresponding additive correction value . As already mentioned, the value a depicts the mask according to a Boolean masking r.sub.1a=r.sub.1 a of the value r.sub.1. In the correction step, the Boolean mask a with the base value r.sub.1 is therefore converted into a corresponding additive mask a, for which it thus holds that r.sub.1a=r.sub.1+. For this, the non-extended XOR2ADD formula and a further random obfuscation value z.sub.3 are used, so that the following relation (B) results:

=((r.sub.1az.sub.3)(r.sub.1z.sub.3))a((az.sub.3)z.sub.3)

[0042] In the embodiment example described here, the relation (B) depicts the second masking transition 18. The value r.sub.1 does not have to be explicitly used for the calculation of u, but the knowledge of the values r.sub.1a=r.sub.1a and a is sufficient.

[0043] Now, a further masking transition is required, which in the present embodiment example is based on the outer masking transition of the above-described experimental approach from (d+r.sub.1)s.sub.2 to (d+r.sub.1)+r.sub.2. For this, the extended XOR2ADD formula and two further obfuscation values z.sub.4, z.sub.5 are used, so that the following relation designated as (C0) results:

r.sub.2=(((d+r.sub.1)s.sub.2z.sub.4z.sub.5)((d+r.sub.1)z.sub.4z.sub.5))((s.sub.2z.sub.4)z.sub.4)((s.sub.2z.sub.5)z.sub.5)

[0044] Since it holds that x=(d+r.sub.1)s.sub.2, the relation (C1) can also be written as a relation (C2) as follows:

r.sub.2=((xz.sub.4z.sub.5)(xs.sub.2z.sub.4z.sub.5))((s.sub.2z.sub.4)z.sub.4)((s.sub.2z.sub.5)z.sub.5)

[0045] By using the two obfuscation values z.sub.4 and z.sub.5, no further protective measures against second-order side channel attacks are required. However, the result r.sub.2 is not yet the desired second additive mask r.sub.2a, because the use of the obfuscation value a has increased the first additive mask r.sub.1a, compared to r.sub.1, by the value . This correction value must now be subtracted from the result r.sub.2, so that the second additive mask r.sub.2a with r.sub.2a=r.sub.2 results. In total, the second mask r.sub.2a is thus determined by the following relation (C3):

r.sub.2a=r.sub.2=(((xz.sub.4z.sub.5)(xs.sub.2z.sub.4z.sub.5))((s.sub.2z.sub.4)z.sub.4)((s.sub.2z.sub.5)z.sub.5)))

[0046] In the embodiment example described here, the relation (C3) depicts the third masking transition 20.

[0047] Altogether, the two additive masks r.sub.1a (according to relation (A2)) and r.sub.2a (according to relation (C3)) thus obtained form the desired result of the masking transition method 10, because it holds that:

x=d+r+r.sub.2=d+(r.sub.1a)+(r.sub.2a+)=d+r.sub.1a+r.sub.2a

[0048] It is to be understood that in alternative embodiments various modifications of the embodiment example just described are possible. For example, the method can be modified in such a way that not the corrected value r.sub.2a is output as the second mask, but instead the uncorrected value r.sub.2 and separately therefrom the correction value .

[0049] Further, in the above-described embodiment example, besides the obfuscation value a five further obfuscation values z.sub.1, z.sub.2, z.sub.3, z.sub.4 and z.sub.5 are employed. In a simple but not very efficient implementation, independent random numbers can be used for these values. For optimization reasons, however, there are also provided implementations in which the obfuscation values are derived from fewer random numbers. Of course, one must make sure that the protection against spying out the method is not impaired. As can be seen from the two following exemplary implementations, however, it is possible to reduce the number of independent random numbers for the masking transition method 10 to three without compromising the protection against spying out.

[0050] As already mentioned, various modifications of the masking transition method 10 are further provided, in which the masking transitions 16, 18 and 20or parts thereofare executed in a different order than that described above.

[0051] In the following, two further embodiment examples of the masking transition method are depicted with reference to two exemplary implementations. In order to avoid misunderstandings, it should be noted that the naming conventions used in the following differ from those of the embodiment example described above.

[0052] The first exemplary implementation starts out from the input values x, y and z, where y and z are Boolean masks and x is a masked representation of a base value d to be kept secret (which is not available as input value). Thus, it holds that x=dyz. Then the following method steps are executed:

TABLE-US-00001 Select random obfuscation values r, s and a (step 1) t s r (step 2) zs z s (step 3) xr x r (step 4) ztxr zs x (step5) ztyr zs y (step6) s11 ztxr x (step 7) s12 ztyr y (step 8) s13 s z (step 9) ra r (step 10) s11ra s11 ra (step 11) s112ra s11ra s12 (step 12) r1ra s112ra s13 (step 13) r1a r1ra r (step 14) r1r r1ra a (step 15) s31 r1ra r1r (step 16) s32 ra r (step 17) s31a s31 a (step 18) alpha s3la s32 (step 19) yt y t (step 20) xry xr y (step 21) s21 xry x (step 22) s22 yt s (step 23) s23 r y (step24) s21s s21 s (step 25) s212s s21s s22 (step 26) r2s s212s s23 (step 27) r2 r2s s (step 28) r2a r2 alpha (step 29) xm xr s (step 30)

[0053] As a result, one obtains the two additive masks r.sub.1a and r.sub.2a as well as a changed masked representation xm of the base value d. Altogether, it holds that:

xm=xrs=d(yr)(zs)=d+r.sub.1a+r.sub.2a

[0054] The just described first implementation contains 29 elementary operations. However, the input-masked representation x differs from the output-masked representation xm. This is acceptable for many applications. For applications in which the masked representation is not to be changed by the masking transition, the following second implementation can be employed. This second implementation does not introduce any additional intermediate values and differs from the first implementation with regard to the naming of the input values and output values as well as with regard to the steps 1, 2, 4, 10 and 21.

[0055] For the second exemplary implementation, the input values xm, yt and z are provided, where yt and z are Boolean masks and xm is a masked representation of the base value d to be kept secret. Thus, it holds that xm=dytz. Then the following method steps are executed:

TABLE-US-00002 Select random obfuscation values y, s and a (step 1) t yt y (step 2) zs z s (step 3) x xm t (step 4) ztxr zs x (step 5) ztyr zs y (step 6) s11 ztxr x (step 7) s12 ztyr y (step 8) s13 s z (step 9) r t s (step 10) ra r a (step 11) s11ra s11 ra (step 12) s112ra s11ra s12 (step 13) r1ra s112ra s13 (step 14) r1a r1ra r (step 15) r1r r1ra a (step 16) s31 r1ra r1r (step 17) s32 ra r (step 18) s31a s31 a (step 19) alpha s31a s32 (step 20) xr x r (step 21) xry xr y (step 22) s21 xry x (step 23) s22 yt s (step 24) s23 r y (step 25) s21s s21 s (step 26) s212s s21s s22 (step 27) r2s s212s s23 (step 28) r2 r2s s (step 29) r2a r2 alpha (step 30)

[0056] As a result, one obtains the two additive masks r.sub.1a and r.sub.2a. The masked representation xm of the base value d to be kept secret remains unchanged. Altogether, it holds that:

xm=d(yr)(zs)=d+r.sub.1a+r.sub.2a

[0057] By numerical simulation for all input values with a width of 4 bits, it was proven for the two implementations just described that they are resistant to second-order side channel attacks.

[0058] The correctness of the above first implementation can be illustrated as follows. According to the relation (A2) from the first embodiment example it holds that:

r.sub.1a=((xs.sub.2z.sub.1z.sub.2)(xs.sub.1s.sub.2z.sub.1z.sub.2))((s.sub.1z.sub.1)z.sub.1)((s.sub.1z.sub.2)z.sub.2)a

[0059] With z.sub.2:=z and s.sub.1:=zs=zs there first follows that:

r.sub.1a=((xs.sub.2z.sub.1z)(xS s.sub.2z.sub.1))((zsz.sub.1)z.sub.1)(sz)a

[0060] Through the substitution z.sub.1:=y it further results that:

r.sub.1a=((xs.sub.2yz)(xss.sub.2y))((zsy)y)(sz)a

[0061] With xs.sub.2:=xys and a:=a, it finally results that:

r.sub.1a=((xsz)x))((zsy)y)(sz)a

[0062] However, this corresponds exactly to the value r.sub.1a calculated as the result of steps (2)-(14) of the first implementation, because it holds that:

[00002]$\begin{array}{c}r.Math..Math.1.Math.a=.Math.s.Math..Math.11s.Math..Math.12s.Math..Math.13a\\ =.Math.\left(\left(\mathrm{zs}x\right)-x\right)\left(\left(\mathrm{zs}y\right)-y\right)\left(s-z\right)a\end{array}$

[0063] The same holds for to the value r.sub.2 according to the relation (C2):

r.sub.2=((xz.sub.4z.sub.5)(xs.sub.2z.sub.4z.sub.5))((s.sub.2z.sub.4)z.sub.4)((s.sub.2z.sub.5)z.sub.5)

[0064] With s.sub.2:=yr=yr and z.sub.5:=y one obtains:

r.sub.2=((xz.sub.4y)((xyr)yz.sub.4))((yrz.sub.4)z.sub.4)(ry)

[0065] Then, with z.sub.4:=s it finally results that:

[00003]$\begin{array}{c}{r}_2=.Math.\left(\left(xsy\right)-\left(\left(x\mathrm{yr}\right)ys\right)\right)\left(\left(\mathrm{yr}s\right)-s\right)\left(r-y\right)\\ =.Math.\left(\left(xry\right)-x\right)\left(\left(yt\right)-s\right)\left(r-y\right)\end{array}$

[0066] However, this corresponds exactly to the value r2 which was calculated according to steps (20)-(28) of the first implementation as follows:

[00004]$\begin{array}{c}r.Math..Math.2=.Math.s.Math..Math.21s.Math..Math.22s.Math..Math.23\\ =.Math.\left(\left(xry\right)-x\right)\left(\left(yt\right)-s\right)\left(r-y\right)\end{array}$

[0067] The method according to FIG. 1 and the embodiment examples, alternative embodiments and implementations described here are provided to be executed by a processor of a portable data carrier, in particular of a chip card or a chip module. The methods are implemented in the form of program commands which are contained in a ROM or an EEPROM or other memory of the data carrier.