Project Topics
Get Complete Project Material File(s) Now! »
Lattices in Physical Attacks
If physical attacks sometimes allow the retrieval of the whole secret, in many cases, only part of the secret is revealed to the attacker. In those cases, lattice-based techniques (see Chapter 2 and Chapter 3 for further details) turn out to be very useful and complementary to physical attacks. Namely, the information brought by physical attacks can account for a substantial input which allows to make possible the discovery of the entire secret thanks to lattice-based techniques. In the following, we reconsider the three examples of physical attacks recalled in this chapter and we provide some extensions based on lattices.
SPA on Modular Exponentiation and Lattices:
It is well-known that the use of a small private key d in RSA, namely an exponent d < N0:292 should be prohibited. This result has emerged from a lattice-based technique due to Coppersmith [BD00] which allows to recover the entire secret d if such a condition is fulfilled. Alternatively, if d is large and if one knows a portion of the bits of d, then the same method can be applied to recover the whole secret d. Namely, in [BDF98], the authors show that for low public exponent e, a quarter of the bits of the private key d is sufficient to recover the entire private key. Similar results (though not as strong) are obtained for larger values of e. Furthermore, they also deal with the case where the known bits are the most or the least significant ones, or when a part in both sides is known. Thusly, such methods can be employed in the case where part of the bits of d was recovered thanks to a side-channel analysis such as the SPA described in Section 1.2.
The other part of the secret d can indeed be straightforwardly retrieved thanks to these lattice-based techniques.
CPA on CRT-Recombination and Lattices:
It has been shown in [Cop96a] that the knowledge of half of the bits of prime q is sufficient to recover the rest of q by using lattice-based techniques, namely by using Coppersmith’s method (which is recalled in Chapter 3). Thusly, such a method can be very useful in the case where half of the bits of q was recovered thanks to a side-channel attack such as the CPA described in Section 1.2. The other part of the secret q is indeed directly retrieved thanks to lattice techniques.
Fault Attacks on RSA and Lattices:
The fault attack on RSA Signature described in Section 1.2 is noteworthy in the sense that a single fault allows to directly recover the entire secret. However, many published fault attacks with a different context of application, allow to recover part of the secret, sometimes with the necessity of many fault injections. Then the use of lattice-based techniques is decisive to recover the whole secret.
One can mention for example randomized RSA encoding/signature schemes (e.g. the randomized version of ISO/IEC9796-2 Standard) which were usually considered to be resistant to traditional fault attacks since a part of the message is unknown to the attacker and varies for each signature computation. However this common assumption was mitigated regarding the works of [CJK+09] and [CNT10] which defeat two randomised RSA encoding schemes. These attacks use lattice-based techniques, and more precisely Coppersmith’s method to solve a bivariate polynomial equation whose coefficients are built thanks to the generated faulty signatures.
One can also mention the attack published in [EBNNT11], where the authors take advantage of the disturbance of the public modulus. The generated faulty signatures allow them to build a lattice, which in turn leads to factorize the public modulus.
Finding Small Integer Solutions
As previously said, the 10-th Hilbert problem is difficult in its general form. However, with the publication of LLL-reduction algorithms in polynomial time, one of its subproblems consisting in finding small integer solutions, has been shown to be solvable in polynomial time. Namely, Coppersmith in [Cop96b, Cop96a, Cop97] showed that if the searched integer roots are small enough, then lattice-based techniques can allow to recover them. The core idea involves finding new polynomial equations thanks to latticereduction in order to get as many equations as variables, and then solve the system easily. We describe in more details those techniques in Chapter 3.
Simultaneous Diophantine Approximation
Another famous application of lattice reduction algorithms involves the theory of Diophantine approximation. Apart from its own interest, being able to have good simultaneous approximations is a very useful building block for many algorithms. This theory deals with the approximation of numbers (rational or irrational), by rational numbers with special properties. Namely, let n be a positive integer, e1; e2; : : : ; en be rational numbers and » 2 R satisfying 0 < » < 1. A theorem from Cassels [Cas, Sec.V.10] specifies that there exist integers p1; p2; : : : ; pn; q such that jpi qeij 6 » for 1 6 i 6 n, and 1 6 q 6 « n :
However, even if it is proven that such integers exist, no known polynomial-time algorithm can find them. Yet, in [LLL82] it is shown that the LLL algorithm can be used to recover integers that satisfy a slightly weaker condition. Namely, they show the following theorem:
Theorem 20 (Simultaneous Diophantine Approximation). There exists a polynomial time algorithm (LLL) that, given a positive integer n and rational numbers e1; e2; : : : ; en; » satisfying 0 < » < 1, finds integers p1; p2; : : : ; pn; q for which jpi qeij 6 » for 1 6 i 6 n .
Coppersmith’s Method for Finding Small Roots to Univariate Modular Equations
Coppersmith in [Cop96b, Cop97] showed how to find efficiently all small roots of univariate modular polynomial equations. In the following, we recall Coppersmith’s theorem which gives a condition on the size of the small roots and the complexity of the method.
Theorem 22 (Coppersmith). Let f(x) be a monic polynomial of degree in one variable, modulo an integer N of unknown factorization. Let X be such that X < N 1 . One can find all integers x0 with f(x0) 0 mod N and jx0j < X in time polynomial in logN and .
The technique designed by Coppersmith to obtain this result was later simplified by Howgrave-Graham in [HG97]. Coppersmith and Howgrave-Graham’s methods have the same asymptotical complexity, but since the latter one holds a more natural approach And is easier to implement (in fact both methods lie in dual vectorial spaces relative to ne another), it is commonly adopted. Therefore we describe in the sequel the method, following the classical Howgrave-Graham’s approach and we refer the reader to [Cop96b, Cop97] or to [Rit10,Bau08] for descriptions of the original Coppersmith’s method. For the sake of simplicity, one will adopt the calling “ Coppersmith’s method” even when Howgrave-Graham’s approach is employed.
Coppersmith’s Method for Finding Small Roots to Bivariate Equations Over the Integers
As specified before, Coppersmith also proposed a method that allows to find small integer roots of bivariate polynomials over Z [Cop96b, Cop97]. Namely, one would like to find small (x0; y0) such that f(x0; y0) = 0. In the following, we recall Coppersmith’s main result for the bivariate integer case. Theorem 26 (Coppersmith). Let f(x; y) be an irreducible polynomial in two variables over Z, of maximum degree in each variable separately. Let X and Y be upper bounds on the desired integer solution (x0; y0), and let W = maxi;j jfij jXiY j . If XY < W2=(3), then in time polynomial in (logW; 2), one can find all integer pairs (x0; y0) such that f(x0; y0) = 0, jx0j X, and jy0j Y .
Table of contents :
I State Of The Art
1 RSA on Embedded Devices and Physical Attacks
1.1 RSA Cryptosystem on Embedded Devices
1.1.1 RSA Signature in Standard mode
1.1.2 RSA Signature in CRT mode
1.2 Physical Attacks
1.2.1 Non-invasive Attacks
1.2.2 Invasive Attacks
1.3 Lattices in Physical Attacks
1.3.1 SPA on Modular Exponentiation and Lattices:
1.3.2 CPA on CRT-Recombination and Lattices:
1.3.3 Fault Attacks on RSA and Lattices:
2 Lattice Reduction
2.1 Euclidean Lattices
2.1.1 Some Basic Definitions
2.1.2 Volume and Determinant
2.1.3 Shortest Vector Problem and Orthogonality
2.2 LLL-Reduction
2.2.1 Size-Reduced Basis
2.2.2 LLL-Reduced Basis
2.2.3 A Basic Version of the LLL Algorithm
2.2.4 Bounds of LLL-Reduced Vectors
2.2.5 Complexities of the LLL, L2 and ~L1 Algorithms
2.2.6 Number of Iterations of LLL-Reduction Algorithms
2.3 Diophantine Problem and LLL-Reduction
2.3.1 Finding Small Integer Solutions
2.3.2 Simultaneous Diophantine Approximation
3 Finding Small Solutions to Polynomial Equations
3.1 Coppersmith’s Method for Univariate Modular Equations
3.1.1 The Main Result
3.1.2 The Method
3.1.3 Complexity
3.1.4 Applications
3.2 Coppersmith’s Method for Bivariate Equations over Z
3.2.1 The Main Result
3.2.2 Core Idea of the Method
3.2.3 Applications
3.3 The BDH Method for Factoring N = prq
3.3.1 Motivations
3.3.2 The Main Result
3.3.3 The Method
II Contributions
4 Rounding and Chaining LLL
4.1 Speeding up Coppersmith’s Algorithm by Rounding
4.1.1 Rounding for Coppersmith’s Algorithm
4.1.2 Running time: proof of Theorem
4.1.3 A Remark on the Original Coppersmith’s Complexity
4.1.4 A Summary of the Complexities
4.2 Chaining LLL
4.2.1 Exploiting Relations Between Consecutive Lattices
4.2.2 Rounding and Chaining LLL
4.2.3 Complexity Analysis: A Heuristic Approach
4.3 Experiments
4.3.1 Practical Considerations
4.3.2 Implementation Results
4.4 Other Small-Root Algorithms
4.4.1 Gcd Generalization
4.4.2 Multivariate Equations
5 Factoring N = prqs for Large r
5.1 BDH’s Theorem Slightly Revisited
5.2 Factoring N = prqs for Large r
5.2.1 Two Natural Approaches that Fail
5.2.2 The Main Theorem
5.2.3 An Outline of the Method
5.2.4 A Useful Lemma: Decomposition of r and s
5.2.5 Proof of the Main Theorem
5.2.6 Refinement of the Condition on r for Small s or for s Close to r
5.3 Generalization for N = Q pri i for Large ri’s
5.3.1 A Condition on r1 Depending on the Ratio r1=rk1
5.3.2 Factoring with Gaps
5.3.3 An Iterative Definition of Function t
5.3.4 Proof of the Generalization Theorem
5.4 Speeding-up by Rounding and Chaining
5.4.1 Rounding
5.4.2 Chaining
5.5 Experiments
5.5.1 Practical Considerations
5.5.2 Speed-up by Rounding and Chaining
5.5.3 Implementation Results
5.5.4 Comparison with ECM
6 Combined Attack on RSA-CRT
6.1 Context and Principle
6.1.1 RSA Signature Using the CRT Mode
6.1.2 Countermeasures Against SCA and FI
6.2 A New Combined Attack on CRT-RSA
6.2.1 A Useful Relation
6.2.2 Recovering the Private Key
6.3 Experiments
6.4 Reducing the Complexity Using Coppersmith’s Methods
6.4.1 Bringing Up the Original Problem to Solving a Modular Equation
6.4.2 Results From Our Implementation
6.5 Countermeasures
6.5.1 Blind Before Splitting
6.5.2 Verification Blinding
6.6 Conclusion
