Ágnes Kiss
email: agnes.kiss@crisp-da.de

Juliane Krämer
email: juliane@sec.t-labs.tu-berlin.de

Pablo Rauzy
email: pablo.rauzy@inria.fr

Jean-Pierre Seifert
email: jpseifert@sec.t-labs.tu-berlin.de

Algorithmic Countermeasures Against Fault Attacks and Power Analysis for RSA-CRT

Keywords: Bellcore attack, RSA-CRT, modular exponentiation, power analysis

In this work, we analyze all existing RSA-CRT countermeasures against the Bellcore attack that use binary self-secure exponentiation algorithms. We test their security against a powerful adversary by simulating fault injections in a fault model that includes random, zeroing, and skipping faults at all possible fault locations. We find that most of the countermeasures are vulnerable and do not provide sufficient security against all attacks in this fault model. After investigating how additional measures can be included to counter all possible fault injections, we present three countermeasures which prevent both power analysis and many kinds of fault attacks.

Introduction

In a fault attack, an adversary is able to induce errors into the computation of a cryptographic algorithm and thereby to gain information about the secret key or other secret information used in the algorithm. The first fault attack [START_REF] Boneh | On the importance of checking cryptographic protocols for faults[END_REF] targets an RSA implementation using the Chinese remainder theorem, RSA-CRT, and is known as the Bellcore attack. The Bellcore attack aroused great interest and led to many publications about fault attacks on RSA-CRT,e.g., [START_REF] Aumüller | Fault attacks on RSA with CRT: concrete results and practical countermeasures[END_REF][START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF][START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF][START_REF] Joye | Chinese remaindering based cryptosystems in the presence of faults[END_REF][START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF]. Countermeasures to prevent the Bellcore attack can be categorized into two families: the first one relies on a modification of the RSA modulus and the second one uses self-secure exponentiation. The countermeasures in the first family were recently analyzed [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF], and a formal proof of their (in)security was provided.

We complement the work of [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF] by comprehensively analyzing the countermeasures in the second family, i.e., those based on self-secure exponentiation. These countermeasures use specific algorithms that include redundancy within the exponentiations. The first such method is based on the Montgomery ladder [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]. This was adapted to the right-to-left version of the square-and-multiplyalways algorithm [START_REF] Boscher | Blinded fault resistant exponentiation revisited[END_REF][START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF] and to double exponentiation [START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF][START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF]. We test the security of these methods using an automated testing framework. We use the same fault model as in [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF], but extend it to meet the particularities of self-secure exponentiation algorithms. We reveal that the countermeasures have certain vulnerabilities in this extended fault model. Based on these findings, we improve the countermeasures and present three self-secure exponentiation methods that are secure against fault injections, safe-error attacks, and power analyses. We note that non-algorithmic level countermeasures are not in the scope of this paper.

Our Contribution: In this paper, we test the security of the self-secure exponentiation countermeasures against the Bellcore attack by simulating random, zeroing, and skipping faults at all possible fault locations (Section 4). Thereafter, we propose secure countermeasures, step-by-step achieving protection against all fault injections and resistance to power analysis and safe-error attacks. We present one countermeasure for each of the exponentiation algorithms used as self-secure exponentiation: the Montgomery ladder, the squareand-multiply-always algorithm, and the double exponentiation method. Despite the natural overhead caused by the included measures against all the considered attack types, our algorithms remain highly efficient (Section 5).

Background

In this section, we give the necessary background information for our work.

The Bellcore Attack on RSA-CRT

We use the standard notation for RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]: M denotes the message, N = pq the public modulus with secret primes p and q, ϕ(N ) = (p -1)(q -1). The public exponent e with gcd(e, ϕ(N )) = 1 is chosen along with the secret exponent d, where e • d ≡ 1 mod ϕ(N ). The signature is calculated S = M d mod N , and S e ≡ (M d ) e ≡ M mod N. The calculation can be speeded up by a factor of four using the RSA-CRT implementation [START_REF] Quisquater | Fast decipherment algorithm for RSA public-key cryptosystem[END_REF]. Two smaller exponentiations S p = M dp mod p and S q = M dq mod q are performed with exponents d p = d mod (p -1), d q = d mod (q -1), and recombined with the method S = CRT(S p , S q ) = ((S p -S q )i q mod p)q + S q , where i q = q -1 mod p. The public key of RSA-CRT is (e, N ) and the private key includes p, q, d p , d q and i q .

A fault attack is a physical attack where the attacker is able to induce faults into the execution of the algorithm. The first attack on RSA-CRT was proposed by Bellcore researchers [START_REF] Boneh | On the importance of checking cryptographic protocols for faults[END_REF]. The fault is induced into the calculation of strictly one of the intermediate signatures, resulting in S p (or S q ). If S p (or S q ) is used during recombination, a faulty signature S is returned. With high probability q (or p) can be deduced as gcd(S -S, N ) [START_REF] Boneh | On the importance of checking cryptographic protocols for faults[END_REF] or as gcd( S e -M mod N, N ) [START_REF] Joye | Chinese remaindering based cryptosystems in the presence of faults[END_REF].

During the discussion of fault attacks, the precise description of the fault model is essential: it includes the assumptions on the adversary's abilities. The Bellcore attack targeting an unprotected implementation uses one fault injection and loose assumptions in the fault model, i.e., a very weak attacker. The attacker is only assumed to alter an intermediate signature, which can be achieved by an arbitrary modification of any variable throughout the exponentiation, i.e., affecting any bit or any byte results in a successful attack.

Safe-Error Attacks

Classical fault attacks exploit the corrupted result or the difference between a correct and faulty results. However, it was noted in [START_REF] Yen | Checking before output may not be enough against fault-based cryptanalysis[END_REF] that secret information may leak depending on if a fault has effect on the result of the computation or not. The techniques that exploit such behavior are called safe-error (SE) attacks.

Computational safe-error attacks (C-SE) [START_REF] Yen | A countermeasure against one physical cryptanalysis may benefit another attack[END_REF] target dummy operations. If the result remains error-free although a fault was induced, it affects a dummy operation and thus, information about the secret key can be revealed.

Memory safe-error attacks (M-SE) [START_REF] Yen | Checking before output may not be enough against fault-based cryptanalysis[END_REF] assume a more powerful attacker. Knowing how the internal variables are processed in the memory throughout a certain step of the algorithm, one may be able to derive the secret key [START_REF] Yen | Checking before output may not be enough against fault-based cryptanalysis[END_REF]. Memory safe-error attacks are prevented by randomizing the targeted variables.

Power Analysis Methods

Simple power analysis (SPA) studies the power consumption of a single execution of the algorithm. If the execution depends on the value of the secret key, the adversary is able to obtain information by analyzing the power trace.

Differential power analysis (DPA) is a natural extension of SPA [START_REF] Kocher | Differential power analysis[END_REF]. When performing a DPA, an attacker collects several power trace measurements of the executions of the same algorithm and uses statistical methods to reveal the secret key. Prevention generally requires randomization of variables.

Algorithms for Regular Exponentiation

Classical modular exponentiation algorithms are vulnerable to SPA, since the power consumption of the different operations can be differentiated [START_REF] Krämer | Weaknesses in current RSA signature schemes[END_REF]. To prevent SPA, regularity of the modular exponentiation algorithms is required. It means that the same operations are performed independently from the value of the exponent. Below, we recapitulate the two most widely used binary methods.

Square-and-Multiply-Always: The right-to-left exponentiation algorithm was modified in [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF] to the square-and-multiply-always method, shown in Alg. 1a.

Algorithm 1 SPA-resistant modular exponentiation methods (1a) Square-and-multiply-always [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF] input: M = 0, d = (dn-1, . . . , d0)2, x output:

M d mod x 1: R0 := 1, R1 := 1, R2 := M 2: for i = 0 to n -1 do 3: R d i := R d i • R2 mod x 4: R2 := R 2 2 mod x 5: end for 6: return R0 (1b) Montgomery ladder [13] input: M = 0, d = (dn-1, . . . , d0)2, x output: M d mod x 1: R0 := 1, R1 := M 2: for i = n -1 to 0 do 3: R d i := R d i • R d i mod x 4: R d i := R 2 d i mod x 5: end for 6: return R0
By introducing dummy operations in register R 1 (line 3), one squaring and one multiplication is performed at each iteration.

Montgomery Ladder: The powering ladder, shown in Alg. 1b, was proposed in [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF] and its correctness discussed in [13]. The algorithm is regular without including dummy operations and is resistant to safe-error attacks [13].

Countermeasures Against the Bellcore Attack

To counter the Bellcore attack, straightforward countermeasures aim to verify the integrity of the computation before returning the result, e.g., by repeating the computation and comparing the results. Due to the inefficiency of such measures, several improved countermeasures appeared starting from 1999.

Two Families of Countermeasures

The advanced countermeasures were divided into two families according to the difference in their nature [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF]: Shamir's family and Giraud's family. We refer to the latter as self-secure exponentiation countermeasures.

Shamir's family consists of the countermeasures that prevent the Bellcore attack by multiplicatively extending the modulus x with a random number s. They rely on the fact that an invariant, inherited from the calculations modulo the extended modulus, i.e., modulo x•s, must hold modulo s. Shamir's algorithm from [START_REF] Shamir | Method and apparatus for protecting public key schemes from timing and fault attacks[END_REF] motivated researchers to develop such countermeasures, e.g., [START_REF] Aumüller | Fault attacks on RSA with CRT: concrete results and practical countermeasures[END_REF][START_REF] Joye | Secure evaluation of modular functions[END_REF][START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF].

The idea of self-secure exponentiation countermeasures was proposed in [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]. If the exponentiation algorithm returns more than one power of a given input and keeps a coherence between its registers throughout the exponentiation, an invariant can be formulated that must hold at the end of the algorithm. However, it is claimed to be lost if a fault injection takes place.

Self-Secure Exponentiation Countermeasures

In this section, we recapitulate the existing self-secure exponentiation countermeasures. The algorithmsare provided in Appendix A in Alg. 5-10.

The first countermeasure was proposed by Giraud [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]. It exploits the fact that while using the Montgomery ladder, the temporary registers R 0 and R 1 are of the form (M k-1 mod x, M k mod x) for some integer k after each iteration of Alg. 1b. After two exponentiations that result in the pairs (S p = M dp-1 mod p, S p = M dp mod p) and (S q = M dq-1 mod q, S q = M dq mod q), and two recombinations S = CRT(S p , S q ) = M d-1 mod pq and S = CRT(S p , S q ) = S d mod pq, the invariant M • S ≡ S mod pq holds. Giraud claims that in case of a fault attack within the exponentiation, the coherence is lost for S p , S p (or S q , S q ) and thus for S and S . Despite its advantages, the Montgomery ladder exponentiation remains vulnerable to DPA [START_REF] Kocher | Differential power analysis[END_REF] (DPA exp ). Fumaroli and Vigilant blinded the base element with a small random number r [START_REF] Fumaroli | Blinded fault resistant exponentiation[END_REF], using one more register R 2 in the exponentiation. Besides being more memory-costly, this method was proven Table 1: Self-secure exponentiation countermeasures. CRT, check, inv., reg., mult., and sq. denote the number of CRT recombinations, checking procedures, inversions, additional large registers, multiplications, and squaring operations respectively, in terms of the bit-length n of the exponent. PA and SE denote the resistance against power analysis and safe-error attacks. means that there are included countermeasures, × refers to the lack of them.

4 n + 2 n × Rivain [22] 8 1 2 0 2 ∼ 1.65n × × × × Rivain (SCA) [22] 9 1 2 0 3 ∼ 1.65n 0 × Le et al. [18] 10 1 2 0 3 ∼ 0.67n n × × × ×
to be insecure against fault attacks [START_REF] Kim | How can we overcome both side channel analysis and fault attacks on RSA-CRT? In: Fault Diagnosis and Tolerance in Cryptography[END_REF], due to the lack of coherence between R 2 and the other registers. Moreover, it remains vulnerable to the DPA attack on the CRT recombination from [START_REF] Witteman | A DPA attack on RSA in CRT mode[END_REF] (DPA CRT ).

The square-and-multiply-always algorithm (Alg. 1a), uses dummy operations to prevent SPA. Boscher et al. in 2007 proposed a self-secure exponentiation countermeasure based on this algorithm [START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF]. In the end of the execution, R 0 holds the value M d mod x, R 1 holds M 2 n -d-1 mod x, while R 2 only depends on the binary length n of the exponent, and equals to M 2 n mod x. Thus, the coherence

M • R 0 • R 1 ≡ R 2 mod
x is kept throughout the algorithm. Boscher et al. in 2009 [START_REF] Boscher | Blinded fault resistant exponentiation revisited[END_REF], modified the method in order to achieve resistance against DPA on the exponentiation without significant overhead. 2 w -ary versions of the algorithmwere proposed [START_REF] Baek | Regular 2 w -ary right-to-left exponentiation algorithm with very efficient DPA and FA countermeasures[END_REF][START_REF] Joye | Memory-efficient fault countermeasures[END_REF].

Rivain proposed a solution that uses double exponentiation [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF]. Such a method receives the base M , two exponents d 1 , d 2 , the modulus x, and outputs both M d1 mod x and M d2 mod x. It makes use of a double addition chain for the pair (d 1 , d 2 ), by means of which the two modular exponentiations are performed at once, using altogether 1.65n operations on average. We assume this chain to be precomputed. Le et al. presented a double exponentiation algorithm, that does not rely on precomputation [START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF]. The binary exponentiation works as two parallel executions of the right-to-left exponentiation and uses register R 0 for calculations with d 1 and register R 1 for calculations with d 2 . M 2 n mod x is computed only once and is stored in R 2 .

Table 1 summarizes the different properties of the self-secure exponentiation countermeasures. We consider the security and efficiency of the methods, since measures against physical attacks imply overhead. When discussing efficiency, we describe the following relevant properties to achieve low time and memory con-sumption: number of registers containing large values that are used additionally to the input registers (M, d, x) during the exponentiation, number of multiplications, squaring operations and inversions using large registers. We summarize if they include protection against physical attacks such as power analysis on the exponentiation and the CRT recombination and safe-error attacks.

Security of Self-Secure Exponentiation Methods

The security of self-secure exponentiation countermeasures relies mainly on the exponentiation algorithms. Each method has an invariant that holds throughout its execution, which is claimed to be lost in case a fault is injected. Accordingly, the modular exponentiation methods have to be tested against fault attacks. In this section, we recapitulate the fault model that we adopt, briefly describe our methodology and discuss our results.

Simulating Fault Injections Against Self-Secure Exponentiation Countermeasures

The designers of the countermeasures provide either formal and informal explanations for their security assumptions and their fault models differ from each other. To the best of our knowledge, we are the first to simulate all possible fault injections in a common fault model. Fault Model: We adopt the generic fault model of [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF]. Therefore, we simulate three types of fault injections: random and zeroing faults in case of which the affected variable is changed to a random value and null, respectively, and skipping faults which cause instruction skips, i.e., jumps over some lines of the pseudocode. We take the following fault types into consideration: faults on local variables, on input parameters, and on conditional tests. An adversary is able to target any variable, but cannot specify the bits his fault affects. When inducing a random fault, he does not know its concrete value. Since refined methods appear for performing instruction skips in practice (e.g. [START_REF] Blömer | A practical second-order fault attack against a real-world pairing implementation[END_REF]), we consider it as a possible threat when discussing physical attacks. The injection of skipping faults was observed as practical in [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF], but was covered by means of random and zeroing faults. This does not hold for self-secure exponentiation. When considering skipping faults, we count the number of lines that have to be skipped in the pseudocode. In the Montgomery ladder shown in Alg. 1b, the pair (R 0 , R 1 ) is of the form (M k-1 mod x, M k mod x) at each iteration, which coherence is assumed to be lost in case of a fault injection. However, an adversary might skip two consecutive lines (3-4) at any iteration of the loop. The invariant holds for the corrupted R 0 and R 1 and thus, the fault is not detected.

Our Framework: In case of self-secure exponentiation countermeasures, the underlying exponentiation algorithm has to be tested and checked that the invariant is lost if a fault is injected. When simulating the attacks, we needed features that the tool used for the analysis of Shamir's family lacked [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF]: redefinition of variables and support for loops. Therefore, we created our own framework in Java. A manual step of our method was identifying the possible fault injection locations within the exponentiation algorithms. After this manual step, the simulation of multiple fault injections in all possible combination of fault locations was fully automated, for all the three fault types. A simulation results in a successful Bellcore attack if a corrupted signature is returned.

For more details on our simulation framework, the reader is referred to the full version [START_REF] Kiss | Algorithmic countermeasures against fault attacks and power analysis for RSA-CRT[END_REF].

Simulation Results

The results of our fault injection simulations are shown in Table 2. While performing the tests with multiple faults, we considered protected checking procedures, since skipping or zeroing any of the checks would enable a successful Bellcore attack. When considering faults on the checking procedures, a method can be protected against n fault injections by repeating each check n times.

Random Faults: If a countermeasure is protected against one random fault injection, it cannot be broken with more than one random faults either. This is due to the fact that a random fault cannot induce a verification skip [START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF]. Our results confirm that in case of the algorithms that use the Montgomery ladder or the square-and-multiply-always algorithm, the intermediate secret exponent and the loop counter have to be protected against random faults. [6,8,9] use the checksum of the exponent to verify its integrity and thwart the attack. It was revealed in [START_REF] Kim | How can we overcome both side channel analysis and fault attacks on RSA-CRT? In: Fault Diagnosis and Tolerance in Cryptography[END_REF], that the introduction of register R 2 in Fumaroli and Vigilant's countermeasure [START_REF] Fumaroli | Blinded fault resistant exponentiation[END_REF] made it vulnerable to any random fault on R 2 at any iteration of the algorithm. This is due to the fact that R 2 is calculated independently of the other two registers, which are multiplied with its final value. In case of the countermeasures using double exponentiation, a possible random fault is the corruption of the intermediate message M, resulting in M . Rivain identified this vulnerability and suggested to compute a cyclic redundancy code [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF].

Zeroing Faults: Without a specific checking procedure against zeroing faults, the exponentiation algorithms (Section 2.4) are vulnerable. According to [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF], it is unlikely to be able to zero a large buffer in practice. However, as [START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF][START_REF] Rauzy | Countermeasures against high-order fault-injection attacks on CRT-RSA[END_REF], we take zeroing faults into consideration but note that their injection is very difficult to achieve in practice. In case of the methods that use the Montgomery ladder and the square-and-multiply-always exponentiation, if the message M in the beginning of the algorithms is zeroed, zeroes are returned. The same holds for any of the registers R 0 , R 1 in the method using the Montgomery ladder and for R 2 in Fumaroli and Vigilant's and Boscher et al.'s methods. Then, the checking procedure holds even though the recombination is computed with only one of the intermediate signatures. Giraud considered this vulnerability impossible, while Boscher et al. included checks against it. The two countermeasures that use double exponentiation are not vulnerable to a single zeroing fault. In the case of Rivain's method [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF], the exponent is given by the addition chain, which we assume to be protected. For the algorithm by Le et al. [START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF], two zeroing faults on the exponents d 1 , d 2 are necessary to conduct a Bellcore attack. If any other values are zeroed, the coherence check does not hold and the fault is detected.

Skipping Faults: Our simulations show that only the method by Fumaroli and Vigilant [START_REF] Fumaroli | Blinded fault resistant exponentiation[END_REF] is vulnerable to the instruction skip of one line, the calculation of register R 2 , which has a similar effect as the random fault on R 2 . When two lines are skipped together, both regular, SPA-resistant algorithms, i.e., the Montgomery ladder and the square-and-multiply-always methods are vulnerable. By skipping two consecutive lines within the loop, they preserve the coherence between the variables even though the results are corrupted. Even if the loop counter i is protected, skipping faults result in successful Bellcore attacks.

PA-SE-FA-Resistant Self-Secure Exponentiation Countermeasures

We propose a secure countermeasure for each of the exponentiation algorithms that are used for constructing self-secure exponentiation methods. We claim that our proposed countermeasures are secure against power analysis (PA), safe-error (SE) attacks, and fault attacks (FA) and remain highly efficient. For the verification of the resistance against fault injection attacks, we applied our framework from Section 4.1 on the proposed algorithms. We discuss the implied overhead by the introduced protection against physical attacks. FA j i denotes fault attacks of type j (r, z, s denote random, zeroing and skipping faults, resp.), against variable(s) i.

Algorithm 2 PA-SE-FA method with the Montgomery ladder (2a) MonExp(M, d, x, r, rinv, s) input: M,d = (dn-1, . . . ,d0)2, x, r, rinv, s output: (r

2 n • M d mod sx, r 2 n • M d+1 mod sx, r 2 n inv mod sx) 1: x := s • x FA s (6-7) , FA r, z d,i
2: R0 := r 3: R1 := r • M mod x 4: R2 := rinv mod x 5: for i from n -1 to 0 do 6:

R d i := R d i • R d i mod x 7:
R

d i := R 2 d i mod x 8:
R2 := R 2 2 mod x 9: end for 10: return (R0, R1, R2) (2b) RSA-CRT input: M = 0, p, q, dp, dq, iq, D = p ⊕ q ⊕ dp ⊕ dq ⊕ iq output: M d mod pq or error 1: Pick k-bit random prime s, such that ps M, qs M FA s (6-7) , FA r, z

d,i 2: Pick random integer r ∈ Z * pqs FA r R 2 , FA s (8)
3:

rinv := r -1 mod pqs FA r R 2 , FA s (8)
4: (Sp,S p ,Rp) :=MonExp(M mod sp,dp,p,r,rinv,s) 5: (Sq,S q ,Rq) := MonExp(M mod sq,dq,q,r,rinv,s)

6: if Sp • Sq = 0 then FA z M,R 0 ,R 1 ,

Countermeasure using the Montgomery Ladder

Fumaroli and Vigilant's countermeasure [START_REF] Fumaroli | Blinded fault resistant exponentiation[END_REF] (Alg. 6) which aimed to improve Giraud's method [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF] (Alg. 5) was proven to be vulnerable to random fault attacks [START_REF] Kim | How can we overcome both side channel analysis and fault attacks on RSA-CRT? In: Fault Diagnosis and Tolerance in Cryptography[END_REF]. Alg. 2 presents our secure method with the Montgomery ladder .

To prevent fault attacks on register R 2 (FA r R2 , FA s (8) ), we return the blinded registers R 0 and R 1 and perform the multiplication with the inverse contained in R 2 . This multiplication happens modulo pq, after the blinded CRT recombinations of all the three registers in lines 9-11 in Alg. 2b.

To achieve prevention against skipping faults (FA s (6-7) ), we include a check for verifying the integrity of the exponentiations. Since the coherence in the regular exponentiation algorithms is not lost when skipping faults are injected, we create a hybrid countermeasure with a technique used in Shamir's family by Aumüller et al. [START_REF] Aumüller | Fault attacks on RSA with CRT: concrete results and practical countermeasures[END_REF]. We conclude the necessity of the modulus extension to prevent skipping faults and multiply the modulus with a k-bit random prime s. S p and S q are calculated modulo p • s and q • s, respectively, and the signature is recombined to S = M d mod pq using the blinded recombination from [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]: S = CRT blinded (S p , S q ) = (((S p -S q ) mod sp) • i q mod sp) • q + S q mod pq. [START_REF] Aumüller | Fault attacks on RSA with CRT: concrete results and practical countermeasures[END_REF] To verify that no instruction was skipped, two small exponentiations modulo the k-bit number s with the k-bit exponents are performed as in lines 16-17. If a skipping fault occurs and the value of S p or S q is corrupted, the check in line 18 does not hold with probability 2 -k . Besides protecting against skipping faults, this measure detects faults on the exponent and loop counter i (FA r,z d,i ) of the exponentiation algorithm, without an additional large register. If the small exponentiations are calculated using the Montgomery ladder (Alg. 1b), then besides the k-bit message, exponent, and modulus, two k-bit registers, k multiplications and squarings are used. However, a checksum as an input has to be included to detect the corruption of p, q, i q , d p or d q in Alg. 2b in line 21.

We note that the blinded CRT recombination recapitulated in Eq. 1 also prevents the DPA attack on the CRT recombination (DPA CRT ) from [START_REF] Witteman | A DPA attack on RSA in CRT mode[END_REF].

To avoid zeroing faults (FA z M,R0,R1,R2 ), we check that none of the values returned by the exponentiation is zero. We perform this before the CRT recombinations in Alg. 2b, by verifying S p • S q = 0 in line 6. In order to make sure that this check does not violate the correctness of the algorithm when the message is a multiple of ps or qs, we choose s such that ps M and qs M .

Alg. 2 presents the algorithm that is based on the Montgomery ladder and is protected against power analysis (PA), safe-error (SE), and fault attacks (FA). For eliminating the revealed vulnerabilities against fault injection attacks, we included an additional CRT recombination, transformed two small inversions to one of doubled size, included one large input register D, two times k multiplications and k squaring operations on k-bit registers, where k is the security parameter that defines the probability of undetected skipping faults as 2 -k . We note that since modular inversion and prime generation imply significant costs, lines (1-3) can be precomputed (without the assumption ps M, qs M ) and s, r and r inv can be provided as inputs to Alg. 2b.

Countermeasure using the Square-and-Multiply-Always Exp.

Boscher et al. described a square-and-multiply always algorithm that is resistant to SPA, DPA, and SE [START_REF] Boscher | Blinded fault resistant exponentiation revisited[END_REF] (Alg. 7). The algorithm includes a technique against the exponent modification, and the check R 2 = 0 in the end of the exponentiation to detect zeroing faults (FA z M,R2 ) [START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF]. Instead of this check in both exponentiations, we suggest to verify S p • S q = 0 in Alg. 3b as in Alg. 2b.

Against skipping faults (FA s (6-7) ) we suggest the same measure as in Alg. 2: blinding the modulus and performing two small exponentiations in the RSA-CRT algorithm. For retrieving the signature, the CRT recombination in Eq. 1 is used. Though not mentioned in [START_REF] Boscher | Blinded fault resistant exponentiation revisited[END_REF], the random value r in Alg. 3b should not be Algorithm 3 PA-SE-FA method with the square-and-multiply-always exp.

(3a) SqExp(M, d, x, r, rinv, s) input: M ,d = (dn-1, . . . ,d0)2, x, r, rinv, s output: 3: rinv := r -1 mod pqs 4: (Sp,S p ,Tp) := SqExp(M mod sp, dp,p, r,rinv, s) 5: (Sq,S q ,Tq) := SqExp(M mod sq, dq,q, r,rinv, s)

(r • M d mod sx, rinv • M 2 n -d-1 mod sx, M 2 n mod sx) 1: x := s • x FA s (6-7) , FA r,z d,i 2
6: if Sp • Sq = 0 then FA z M,R 2

7:

return error 8: end if 9: S := CRT blinded (Sp, Sq) 10: S := CRT blinded (S p , S q ) 11: T := CRT blinded (Tp, Tq)

12: if M • S • S ≡ T mod pq then 13:
return error 14: end if 15: Sps = (rinvSp mod s) dq mod (s-1) mod s 16: Sqs = (rinvSq mod s) dp mod (s- too small to avoid the following SPA during the computation of Alg. 3a: if an adversary is allowed to input the message M = 1, the value of register R 2 remains 1 for the whole computation. Therefore, the multiplication in line 6 would only depend on the bits of the secret exponent d, multiplied either with a small number (r) or with a large number (r inv ). This could result in differences in the power consumption trace and therefore we chose r to be an at least (n + k)bit integer, where n is the bitlength of p and of q, since it is used for operations of that size in Alg 3a.

Our PA-SE-FA-resistant algorithm with the square-and-multiply-always exponentiation is depicted in Alg. 3. To eliminate the identified vulnerabilities, we included one large input register D along with two times k multiplications and k squaring operations on k-bit registers, in a similar manner as in Alg. 2.

Algorithm 4 PA-SE-FA method with double exponentiation

for i = 0 to n -1 do SPA 8: R (d 1,i ,1) := R (d 1,i ,1) • R2 mod x 9: R (d 2,i ,2) := R (d 2,i ,2) • R2 mod x 10: R2 := R 2 2 mod x 11: end for 12: if R (0,1) R (1,1) ≡ R (0,2) R (1,2) mod x then C SE 13:
return error 14: end if 15: return (R (0,1) , R (0,2) ) (4b) RSA-CRT input: M, p, q, dp, dq, iq output: M d mod pq or error

1: Pick small r1, r2 ∈ Z r2 ≥ r1 + 2 2: Pick k-bit random prime s 3: (Sp, cp) := DPA, M-SE, FA r M , FA z (d 1 ,d 2 ) DoubleExp(M mod p, dp+r1(p -1), r2(p -1) -dp-1, p, s) 4: (Sq, cq) := DPA, M-SE, FA r M , FA z (d 1 ,d 2 )
DoubleExp(M mod q, dq+r1(q -1), r2(q -1) -dq-1, q, s)

5: S := CRT blinded (Sp, Sq) DPACRT 6: if M • S • cp ≡ 1 mod p then 7: return error FA r M , FA z (d 1 ,d 2 )
8: end if

9: if M • S • cq ≡ 1 mod q then 10: return error FA r M , FA z (d 1 ,d 2 )
11: end if 12: return S mod pq

Countermeasure using Double Exponentiation

Rivain proposed the first countermeasure that uses double exponentiation [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF] (Alg. 8). He included modifications by means of which it becomes SPA-DPA-SE-resistant, still requiring the precomputation of the addition chain (Alg. 9). Our aim is to consider measures in the insecure but more efficient algorithm by Le et al. [START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF] (Alg. 10), which does not include precomputation but ignores protection against PA and SE. Firstly, we transform the algorithm to become resistant to SPA. We use two additional registers with dummy operations in order to achieve regularity. Thus, the algorithm requires the use of altogether 5 registers: R (0,1) and R (1,1) belonging to exponent d 1 , R (0,2) and R (1,2) belonging to exponent d 2 , and R 2 used as before. Since for every bit of the exponents the same operations have to performed, this results in altogether 2n multiplications and n squaring operations.

Introducing regularity includes dummy operations. Registers R (1,1) and R (1,2) are unused and thus all the multiplications that assign values to them are dummy operations. To avoid computational safe-error attacks (C-SE) on these operations, in the end of the exponentiation we include the check whether

R (0,1) • R (1,1) ≡ R (0,2) • R (1,2) mod x.
Since both the products corresponding to the two exponents are M 2 n -1 mod x, this holds if the values are not corrupted. With this, we verify the correctness of the dummy values. 1 and Table 2, k-bit denoting the included k-bit operations (squaring and multiplication). We highlight with bold checkmarks () those vulnerabilities that we eliminated in our secure countermeasures and we bold the additional resources needed to be used in order to achieve security against all the considered attacks.

To achieve resistance against differential power analysis on the exponentiation (DPA exp ) and memory safe-error attacks (M-SE), we include the exponent blinding method of Rivain in the RSA-CRT algorithm [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF]. Against DPA on the CRT recombination (DPA CRT ), we apply the blinded CRT recombination method with extended modulus from [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]. For the description of r 1 and r 2 and the correctness of the blinding method, the reader is referred to [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF][START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF].

To detect any randomizing fault on the message M (FA r M ), we include its value in the coherence checks as it was seen in case of the countermeasures from [START_REF] Boscher | Blinded fault resistant exponentiation revisited[END_REF][START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF][START_REF] Fumaroli | Blinded fault resistant exponentiation[END_REF][START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]. We decrease the value of the exponents used for the calculation of c p and c q by one, and multiply the results with M , during the verification in lines 7 and 10 of Alg. 4b. For instance, if S p and c p are calculated by means of a corrupted M , the verification M • M dp+r1ϕ(p) • M r2ϕ(p)-dp-1 ≡ 1 mod p does not hold with high probability. With this, the zeroing faults on exponents d 1 and d 2 (FA z (d1,d2) ) are also thwarted, the algorithm returns (1, 1) in case of two null exponents, and the modified check does not hold anymore.

Our PA-SE-FA-resistant countermeasure using double exponentiation is depicted in Alg. 4. Though the modified countermeasure is less memory-efficient than Le et al.'s algorithm, we note its advantage against physical attacks.

Conclusion

In this paper, we analyzed the existing self-secure exponentiation countermeasures against the Bellcore attack on RSA-CRT. Using our framework, we simulated all possible fault injections considering random and zeroing faults as well as instruction skips on the lines of pseudocode. We found that all the coun-termeasures using regular exponentiation algorithms lacked protection against some kind of faults or power analyses.

We presented three countermeasures, one for each exponentiation algorithm used for designing self-secure exponentiation countermeasures(cf. Table 3). All the three methods are based on regular algorithms to prevent simple power analysis (SPA), include randomization to be resistant to differential power analysis (DPA) and memory safe-error (M-SE) attacks, and eliminate dummy operations which could be exploited by computational safe-error (C-SE) attacks. Measures are included against all considered fault injection attacks (FA) as well. We verified that we eliminated the previous vulnerabilities of the methods without introducing new ones by applying our simulation framework on the pseudocode of the improved algorithms. To prevent skipping faults, we included additional checks into two of our methods, inspired by a countermeasure in Shamir's family, resulting in hybrid methods. We included prevention against fault attacks on the previously vulnerable register in the countermeasure that uses the Montgomery ladder. Our proposed solution that uses double exponentiation includes protection against power analyses and safe-error attacks in the algorithm where it was not considered.

We note that the vulnerability of the message corruption and of the DPA on the CRT recombination in Rivain's SPA-resistant method can be eliminated in a similar algorithmic manner as in Section 5.3, gaining another, the most efficient secure software countermeasure when precomputation is allowed. When precomputation is not allowed, our proposed solution using the square-and-multiplyalways algorithm is the most efficient algorithmic countermeasure.

A Self-Secure Exponentiation Countermeasures

Algorithm 5 Giraud's countermeasure [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF] PA attack model: SPA, chosen message SPA from [START_REF] Yen | Power analysis by exploiting chosen message and internal collisions -vulnerability of checking mechanism for RSA-decryption[END_REF]. Fault model: Random faults on variables and input parameters. Zeroing attacks, disruption of checking are regarded as impossible in practice. For the integrity check of d, i, we assume that an additional register is used in Table 1. (5b) Giraud's RSA-CRT input: M, p, q, dp, dq, iq output: M d mod pq or error 1: Pick k-bit random prime r 2: (S p ,Sp) :=GirExp(M mod p,dp,p,r) 3: (S q ,Sq) :=GirExp(M mod q,dq,q,r) 4: S := CRT blinded (Sp, Sq) 5: S := CRT blinded (S p , S q ) 6: S := M • S mod (p • q) 7: if S = S then return error 8: end if 9: if p, q or iq disturbed then 10:

return error 11: end if 12: return S Algorithm 6 Fumaroli and Vigilant's countermeasure [START_REF] Fumaroli | Blinded fault resistant exponentiation[END_REF] Attack model: SPA, DPA, against which blinding is included. Fault model: That of Giraud's [START_REF] Giraud | An RSA implementation resistant to fault attacks and to simple power analysis[END_REF]. R input: M = 0, p, q, dp, dq, iq output: M d mod pq or error 1: (Sp,S p ) :=FumVigExp(M mod p,dp,p) 2: (Sq,S q ) :=FumVigExp(M mod q,dq,q) 3: S := CRT(Sp, Sq) 4: S := CRT(S p , S q ) 5: if S • M mod p • q ≡ S then 6: return error 7: end if 8: if p, q or iq disturbed then 9:

d i := R d i • R d i mod x 6: R d i := R 2 d i mod x 7: R2 := R 2 2 mod x 8: D := D + di, 9
return error 10: end if BosExp(M mod p, dp, p, r, r inv ) 4: (Sq, S q , Tq) := BosExp(M mod q, dq, q, r, r inv ) 5: S := CRT(Sp, Sq) 6: S := CRT(S p , S q ) 7: T := CRT(Tp, Tq)

8: if M • S • S ≡ T mod pq then 9:
return error 10: end if 11: return r inv •S mod pq Algorithm 8 Rivain's countermeasure [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF] The addition chain is precomputed with ChainCompute(d 1 , d 2 ) from [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF] and stored in memory or is computed on-the-fly. if (ωi = 0) then 4:

Rγ := R 2 γ mod x 5:

i := i + 1 6:

if (ωi = 1) then 7:

Rγ := Rγ • M mod x 8:

end if 9: else 10:

Rγ⊕1 := Rγ⊕1 • Rγ mod x 11:

γ := γ ⊕ 1 12:

end if 13: end for 14: return (Rγ⊕1, Rγ) (8b) Rivain's RSA-CRT input: M, p, q, dp, dq, iq output: M d mod pq or error 1: ωp := ChainCompute(dp, 2(p-1)-dp) 2: (Sp, cp) := RivExp(M mod p, ωp, p) 3: ωq := ChainCompute(dq, 2(q-1)-dq) 4: (Sq, cq) := RivExp(M mod q, ωq, q) 5: S := CRT(Sp, Sq) 6: if S • cp ≡ 1 mod p then 7:

return error 8: end if 9: if S • cq ≡ 1 mod q then 10:

return error 11: end if 12: return S Algorithm 9 Rivain's PA-resistant countermeasure [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF] Attack model: Regular SecRivExp and ChainCom against SPA, blinding against DPA. This blinding method can only be used if the double addition chain is computed on-the-fly. Fault model: M is assumed to be protected, transient faults, i.e., faults whose effect lasts for one computation, are considered. ChainCom(dq+r1(q -1),r2(q -1) -dq) 5: (Sq, cq) := SecRivExp(M mod q, ωq, q) 6: S := CRT(Sp, Sq) 7: if S • cp ≡ 1 mod p then 8:

return error 9: end if 10: if S • cq ≡ 1 mod q then 11:

return error 12: end if 13: return S mod pq Algorithm 10 Le et al.'s binary countermeasure [START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF] Attack model: No side-channel attacks are discussed in [START_REF] Le | On double exponentiation for securing RSA against fault analysis[END_REF]. Fault model: Same as that of Rivain [START_REF] Rivain | Securing RSA against fault analysis by double addition chain exponentiation[END_REF]. 2: (Sq, cq) := LeExp(M mod q, dq, 2(q -1) -dq, q)

3: S := CRT(Sp, Sq)

: R0 := r 3 : 5 :,i 2 :

 352 R1 := rinv 4: R2 := M for i from 0 to n -1 do 6:R d i := R d i • R2 mod x 7: R2 := R 2 2 mod x 8: end for 9: return (R0, R1, R2) (3b) RSA-CRT input: M = 0, p, q, dp, dq, iq, D = p ⊕ q ⊕ dp ⊕ dq ⊕ iq output: M d modpq or error 1: Pick k-bit random prime s such that ps M, qs M FA s (6-7) , FA r,z dPick random integer r ∈ Z * pqs FA r R 2 , FA s (8)

( 4a )

 4a DoubleExp(M, d1, d2, x, s) input: M = 0, d1 = (d1,n-1, . . . , d1,0)2, d2 = (d2,n-1, . . . , d2,0)2, x, s output: (M d 1 mod xs, M d 2 mod xs) 1: x := s • x DPACRT 2: R (0,1)

( 5a )

 5a Modular exp.: GirExp(M, d, x, r)input: M, d = (dn-1, . . . ,d0)2 odd, x, r output: (M d-1 mod r • x, M d mod r • x) 1: xr := r • x 2: R0 := M , R1 := R 2 0 mod xr 3: for i from n -2 to 1 do 4:Rd i := R d i • R d i modxr 5: R d i := R 2 d i mod xr 6: end for 7: R1 := R1 • R0 mod xr 8: R0 := R 2 0 mod xr 9: if i or d disturbed then 10: return error 11: end if 12: return (R0, R1)

( 6a )

 6a Modular exp.: FumVigExp(M, d, x) input: M = 0, d = (dn-1, . . . , d0)2, x output: (M d mod x, M d+1 mod x) 1: Pick k-bit random prime r 2: R0 := r, R1 := rM mod x 3: R2 := r -1 mod x, D := 0 4: for i from n -1 to 0 do 5:

  : D := D • 2 10: end for 11: D := D/2 12: R2 := R2 ⊕ D ⊕ d 13: return (R2 • R0 mod x, R2 • R1 mod x) (6b) Fumaroli and Vigilant's RSA-CRT

11: return S Algorithm 7

 7 Boscher et al's countermeasure 2007[START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF], modifications 2009[START_REF] Boscher | Blinded fault resistant exponentiation revisited[END_REF] Attack model: Regularity against SPA, blinding against DPA. Fault model: One fault per execution[START_REF] Boscher | CRT RSA algorithm protected against fault attacks[END_REF], on local variables, input parameters.

( 7a )) 1 : 1 :

 7a11 Modular exp: BosExp(M,d,x,r,r inv )input: M,d = (dn-1, . . . ,d0)2,x,r,r inv output: (r • M d mod x, r inv • M 2 n -d-1 mod x, M 2 n mod xR0 := 1 • r 2: R1 := 1 • r inv 3: R2 := M 4: D := 0 5: for i from 0 to n -1 do 6:Rd i := R d i • R2 mod x 7: R2 := R2 2 mod x 8: D := D + 2 n • di 9: D := D/2 10: end for 11: if (D = d) or (R2 = 0) then 12: return error 13: end if 14: return (R0, R1, R2) (7b) Boscher et al.'s RSA-CRT input: M = 0, p, q, dp, dq, iq output: M d mod pq or error Pick a k-bit random integer r 2: r inv := r -1 mod pq 3: (Sp, S p , Tp) :=

( 8a )

 8a Double exp.: RivExp(M,ω(d1,d2),x) input: M , ω(d1,d2) n-bits chain, d1 ≤ d2, x output: (M d 1 mod x, M d 2 mod x) 1: R0 := 1, R1 := M , γ := 1, i := 1 2: for i = 1 to n do 3:

( 9a )

 9a Double exp:SecRivExp(M,ω(d1,d2),x)input: M = 0, ω(d1, d2) n-bits, d1 ≤ d2, x output: (M d 1 mod x, M d 2 mod x) 1: R (0,0) := 1, R (0,1) := M, 2: R (1,0) := M 3: γ := 1, µ := 1, i := 0 4: while i < n do 5: t := ωi ∧ µ 6: v := ωi+1 ∧ µ 7: R (0,γ⊕t) := R (0,γ⊕t) • R ((µ⊕1),γ∧µ) mod x 8: µ := t ∨ (v ⊕ 1) 9: γ := γ ⊕ 10: i := i + µ + µ ∧ (t⊕1) 11: end while 12: return (Rγ⊕1, Rγ) (9b) RSA-CRT input: M, p, q, dp, dq, iq output: M d mod pq or error 1: Pick small r1, r2 ∈ Z r2 ≥ r1 + 2 2: ωp := ChainCom(dp+r1(p -1),r2(p -1) -dp) 3: (Sp, cp) := SecRivExp(M mod p, ωp, p) 4: ωq :=

( 10a ) 11 :

 10a11 Double exp.: LeExp(M, d1, d2, x)input: M = 0, d1 = (d1,n-1, . . . , d1,0)2 d2 = (d2,n-1, . . . , d2,0)2, x output: (M d 1 mod x, M d 2 mod x) 1: R0 := 1, R1 := 1, R2 := M 2: for i = 0 to n -1 do 3: if d1,i = 1 then 4: R0 := R0 • R2 mod x 5return (R0, R1) (10b) Rivain's RSA-CRTinput: M = 0, p, q, dp, dq, iq output: M d mod pq or error 1: (Sp, cp) := LeExp(M mod p, dp, 2(p -1) -dp, p)

Table 2 :

 2 Results of our fault injection tests on the exponentiation algorithms, assuming that the checking procedures are protected We note that we rely on the original fault models of the countermeasures from column Ref., recapitulated in Appendix A. denotes that our tests did not reveal any vulnerability against the fault type, M and d 1 , d 2 denote the vulnerability of the message and the exponents in the exponentiation algorithm, respectively. When considering skipping faults, we indicate which lines are skipped together to achieve a successful attack. The register numbering R i , i ∈ {0, 1, 2} and the lines are according to the algorithms in column Alg.

	Countermeasure		Fault injection attacks
	Author(s)	Ref. Alg. Random	Zeroing	Skipping
	Fault number		1	1	2	1	2
	Giraud	[9] 5		M, R0, R1		(4-5)
	Fumaroli, Vigilant [8] 6	R2	M, R0, R1, R2	(7) (5-6) or 2•(7)
	Boscher et al.'07	[6] 7					(6-7)
	Boscher et al.'09	[5] 7					(6-7)
	Rivain	[22] 8	M
	Rivain (SCA)	[22] 9	M
	Le et al.	[18] 10	M		d1, d2

  1) mod s

	17: if Sps = Sqs then
	18:	return error	FA s (6-7) , FA r,z d,i

19: end if 20: if p ⊕ q ⊕ dp ⊕ dq ⊕ iq = D then 21: return error FA r, z p,q,iq ,dp,dq 22: end if 23: return rinv • S mod pq

Table 3 :

 3 Comparison of our PA-SE-FA self-secure exponentiation countermeasures with previous methods. The notation is consistent with that of Table

	Method			Efficiency criteria		Fault injection attacks Other
	Ref. Alg. CRT Check Inv. Reg. k-bit Reg. Mult. Sq. Ran Zeroing		Skipping	PA SE
				Total			Per exp.	1	2	1	2
	[8] 6	2	4 2 (p,q) 0	0	4 n + 3 2n R2 M,R ∀ (7) (5-6),2(7)
	2	3	4 1 (pqs) 1 4k 3 n + 2 2n
	[5,6] 7	3	5 1 (pq) 0	0	4 n + 2 n				(6-7)
	3	3	4 1 (pqs) 1 4k 3 n + 1 n
	[22] 9	1	2	0	0	0	3 1.65n 0 M
	[18] 10	1	2	0	0	0	3	1.65n	M	d1,d2		× ×
	4	1	4	0	0	0	5 2n+3 n

Acknowledgments

This work has been co-funded by the DFG as part of projects P1 and S5 within the CRC 1119 CROSSING and by the European Union's 7th Framework Program (FP7/2007-2013) under grant agreement n. 609611 (PRACTICE).