Cryptanalysis Techniques Using Coppersmith for RSA and ECDH Encryption

Solving Multivariate Coppersmith Problems with Known Moduli Keegan Ryan University of California, San Diego

Cryptanalysis using Coppersmith Given an RSA ciphertext with fixed padding, we can recover the plaintext if we find a small root of the polynomial ? ? = ? + ?3 ? mod? This is possible so long as the root satisfies ? < ? ?1/3. [EC:Cop96]

Cryptanalysis using Coppersmith Given an RSA public key with small private exponent, we can recover the private key if we find a small root of the polynomial ? ?,? = ?? ? ? + 1 1 mod? This is possible so long as the root satisfies ? < ? ?0.292 and ? < ? ?1/2. [EC:BonDur99]

Cryptanalysis using Coppersmith Given an oracle for the most significant bits of an ECDH shared secret, we can recover the full shared secret if we find a small root of the polynomials 2?1+ ?1?0?1+ ?1?1+ ?1?0 2?2+ ?2?0?2+ ?2?2+ ?2?0 2+ ?1?1+ ?1 mod? 2+ ?2?2+ ?2 mod? ?1?0, ,?? = ?0 ?2?0, ,?? = ?0 2??+ ???0??+ ????+ ???0 2+ ????+ ?? mod? ???0, ,?? = ?0 This is possible so long as the root satisfies ?? < ? ?1/2. [DCC:XHS20]

Cryptanalysis using Coppersmith Given an oracle for the most significant bits of an ECDH shared secret, we can recover the full shared secret if we find a small root of the polynomials 2?1+ ?1?0?1+ ?1?1+ ?1?0 2?2+ ?2?0?2+ ?2?2+ ?2?0 2+ ?1?1+ ?1 mod? 2+ ?2?2+ ?2 mod? ?1?0, ,?? = ?0 ?2?0, ,?? = ?0 2??+ ???0??+ ????+ ???0 2+ ????+ ?? mod? ???0, ,?? = ?0 This is possible so long as the root satisfies ?? < ? ?? ?,?,? where ? ?,?,? = (2?+?+2)(?+1) 2 ? ?? ? ?+1+ 2? 2 ?=0 ? ?+1+? ?=0 ? ?+1 ? ?? 1 ?+1. 1 (2? 1+2?)? ? ? [AC:XSWH22]

Shift polynomial selection The bound depends on the set ? of shift polynomials Same roots If the input polynomials have a root mod? , the shift polynomials have the same root mod??. Examples for input polynomial ? ?,? = 0 mod? : ?2(?,?) = 0 mod?2 ?2? = 0 mod?2??? ?,? = 0 mod?2 Suitability Every non-leading monomial in a shift polynomial is the leading monomial of a different shift polynomial. Formally, ? ?,? monoms(g), !? ?,LM ? = ? 1/|?|. The bound is determined by the leading terms and |?|. For best bounds, we want small ? ?LT ?

Shift polynomial selection Example Input polynomial ? ? = ?3+ ?? + ? with a root mod? ? = ?? = ??2= ? ? = ?? ? = ?4 ? ?? ??2 ?3 + ?? + ? + ??2+ ?? Same roots? The input polynomial has a root mod? , all shift polynomials have the same root mod? .

Shift polynomial selection Example Input polynomial ? ? = ?3+ ?? + ? with a root mod? ? = ?? = ??2= ? ? = ?? ? = ?4 ? ?? ??2 ?3 + ?? + ? + ??2+ ?? Suitable? Every non-leading monomial in a shift polynomial is the leading monomial of a different shift polynomial.

Shift polynomial selection Example Input polynomial ? ? = ?3+ ?? + ? with a root mod? ? = ?? = ??2= ? ? = ?? ? = ?4 ? ?? ??2 ?3 + ?? + ? + ??2+ ?? Bounds calculation We have ? ?LT ? so long as the root satisfies ? < ? ?1/5. 1/|?|= ?3/5?2. This implies Coppersmith s method can find a small root

Shift polynomial selection It s hard to generalize Coppersmith s method because the monomials in input polynomials affect the monomials in shift polynomials, which directly affect the bounds

Shift polynomial selection We can use a generic strategy for constructing suitable shift polynomials from any input, but this often results in poor bounds. [AC:JocMay06,AC:MeeNow23] We can use a handcrafted strategy specific to the input polynomials, but this requires expertise and may be outperformed by future work. [EC:BonDur99, AC:BonHalHow01, C:May02, C:BloMay03, EC:EJMW05, PKC:BleMay06, C:JocMay07, PKC:MayRit08, ACNS:SarMai09, AC:HerMay09, PKC:HerMay10, SAC:TakKun14, AFRICACRYPT:PHXHX14, AC:LZPL15, EC:TakLuPen17, DCC:XSHHP18, C:XSHWP19, DCC:XuHuSar20, AC:MayNowSar21, EC:MayNowSar22, AC:XSWH22, XJSSHWP23, ]

Can we automatically choose shift polynomials while achieving the same bounds as the handcrafted strategies?

Provable Graph Search Precomputation Based on Gr bner bases Graph optimization Polytopes Guarantees Strong Good Heuristic Automated? Fully Fully Partially Speed Fine Better Best Theo. Runtime Doubly Exp. Doubly Exp. Polynomial Asymp. Bounds? No No Yes

Automating Coppersmiths method 1. How do we pick shift polynomials in a generic way? 2. How do we improve the practical running time? 3. How do we match the asymptotic behavior of prior work?

Representing shift polynomials with ideals Shift polynomials from ? (mod ?) Polynomial ideal ?,? [?] Shift polynomials are constructed from ? and ?. Members of ?,? are poly. combs. of generators ? and ?. Multiplying by a power of ?doesn t change the roots (mod ?). Multiplying by a polynomial maintains membership in the ideal. Shift polynomials have a shared root (mod ??). Every polynomial in ?,?? has a shared root (mod ??). We care about the leading terms of shift polynomials The Gr bner basis describes leading terms of ideal members For input polynomials ?1, ,?? (mod ?) and multiplicity ?, the set of all possible shift polynomials is the ideal ?1, ,??,??

Provable shift polynomial strategy Given input polynomials ?1, ,?? (mod ?), multiplicity ?, and bounds ??, compute a list of shift polynomials which share a root mod ??. ?? ?? ??< ??} 1. Set monomials to ? = ?? 2. Compute ?, the Gr bner basis of ?1, ,??,??. 3. For each monomial ? ?: a. Use ? to find all candidate shift polynomials with leading monomial ?. b. Pick the candidate with the smallest leading term. c. Append that shift polynomial to a list 4. Return the list

Provable shift polynomial strategy Theoretical guarantees: Provably optimal If the Coppersmith lattice for any other shift polynomial strategy has sufficiently short vectors, our lattice has the same short vectors. Bounded lattice dimension The dimension is ? , in our case it s Poly(?). Doubly exponential runtime Running time is dominated by GB calculation. No asymptotic bounds Don t know length of short vector, just that it exists. Practical reality: Fully automated We can just enumerate multiplicities Gr bner Bases are fast J.groebner_basis() is usually not a bottleneck. Lattice dimension too large Reduction is impractical beyond dimension ~6K

Improving performance 1/|?| small, What if we keep the helpful shift polynomials that make ? ?LT ? and discard those that make it large? This could work, as long as we don t violate suitability.

Improving performance 1/|?| small, What if we keep the helpful shift polynomials that make ? ?LT ? and discard those that make it large? This could work, as long as we don t violate suitability. Example Input polynomial ? ? = ?3+ ?? + ? with a root mod? ? = ?? = ??2= ? ? = ?? ? = ?4 ? ?? 1/|?|= ?3/5?2, this is solvable Since ? ?LT ? when the root satisfies ? < ? ??/?. ??2 ?3 + ?? + ? + ??2+ ??

Improving performance 1/|?| small, What if we keep the helpful shift polynomials that make ? ?LT ? and discard those that make it large? This could work, as long as we don t violate suitability. Example Input polynomial ? ? = ?3+ ?? + ? with a root mod? ? = ?? = ??2= ? ? = ?? ? = ?4 ? ?? 1/|? |= ?2/3?7/3, this is solvable Since ? ? LT ? when the root satisfies ? < ? ??/?. ??2 ?3 + ?? + ? + ??2+ ??

Improving performance 1/|?| small, What if we keep the helpful shift polynomials that make ? ?LT ? and discard those that make it large? This could work, as long as we don t violate suitability. Example Input polynomial ? ? = ?3+ ?? + ? with a root mod? ? = ?? = ??2= ? ? = ?? ? = ?4 ? ?? 1/|? |= ?2/3?4/3, this is solvable Since ? ? LT ? when the root satisfies ? < ? ??/?. ??2 ?3 + ?? + ? + ??2+ ??

Visualizing dependencies ? ? = ?3+ ?? + ? ?? ? = ?4+ ??2+ ?? ??2 ?? ?

Visualizing dependencies ? ? = ?3+ ?? + ? ?? ? = ?4+ ??2+ ?? ??2 ?? ?

Visualizing dependencies ? ? = ?3+ ?? + ? LT = ?3 ?? ? = ?4+ ??2+ ?? LT = ?4 ??2 ?? ? LT = ??2 LT = ?? LT = ?

Searching the directed graph Suitable subsets are subgraphs with no edges leaving that subgraph (AKA a closure). Picard s algorithm efficiently finds a closure of a weighted graph with maximum total weight 1/|? | We want to find a subset ? ? with minimal ? ? LT ?

Visualizing dependencies ? ? = ?3+ ?? + ? LT = ?3 ?? ? = ?4+ ??2+ ?? LT = ?4 ??2 ?? ? LT = ??2 LT = ?? LT = ? 1/|? | Want to minimize ? ? LT ?

Visualizing dependencies ? ? = ?3+ ?? + ? wt. 3log ? ?? ? = ?4+ ??2+ ?? wt. 4log ? ??2 ?? ? wt. log? log? wt. log? wt. log? 2log? Want to maximize ? ? log??(?) This is a lie, see the paper for details

Graph-based shift polynomial strategy Given input polynomials ?1, ,?? (mod ?), multiplicity ?, and bounds ??, compute a list of shift polynomials which share a root mod ??. 1. Set ? using the provable shift polynomial strategy 2. Build the weighted directed graph a) Draw an edge from node ? ? to node ? ? if LM ? monoms(?) 1 ? ? ?logLT(? )(?) b) Set the weight of node ? ? to logLT ? ? + 3. Use Picard s algorithm to find the maximal closure ? 4. Return ?

Graph-based shift polynomial strategy Theoretical guarantees: Efficient subroutines Picard s algorithm runs in polynomial time. Bounded determinant This guarantees there are short vectors in the lattice, but, unlike the provable strategy, no guarantees it contains the shortest vectors Doubly exponential runtime Running time is dominated by GB calculation. No asymptotic bounds Don t know asymptotic structure of maximal closure Practical reality: Inexplicably effective Directly constructs basis for densest sublattice Small lattices Often smaller than lattices in prior work Occasional failure May discard helpful polynomials, typically when the input has extremely small coefficients

Improving theoretical guarantees The first two strategies solve Coppersmith problems in practice. How do we solve them in theory? Input polys in [?] Shift polys w/ mult. ? Gr bner basis Doubly exp.

Shift polynomials from polytopes Idea: Find small-multiplicity shift polynomials using GB, extend to arbitrary-multiplicity shift polynomials using polytopes. Polytopes have a deep connection to shift polynomials and Coppersmith s method [AC:JocMay06,May21,EPRINT:FNCLP24] Input polys in [?] Polytope w/ small mult. Shift polys w/ mult. ? Gr bner basis Doubly exp. Polytope scaling Poly. time

Inferring asymptotic bounds 1/|?| Idea: For this type of shift strategy, ? ?LT ? heuristically depends on a polynomial in ? [AC:MeeNow23]. Use interpolation to find asymptotic bounds. Asymptotic bounds [EPRINT:FNCLP24] eliminates this heuristic by computing the volumes of polytopes. Interpolation Heuristic Input polys in [?] Polytope w/ small mult. Shift polys w/ mult. ? Gr bner basis Doubly exp. Polytope scaling Poly. time

Precomputation of Grbner bases Idea: Represent input polynomials symbolically, compute GB before coefficients are known. Replace [?] with Frac ?,?, ? and substitute in concrete values once available. Asymptotic bounds Symbolic input polys Symbolic polytope Gr bner basis Doubly exp. Interpolation Heuristic Input polys in [?] Polytope w/ small mult. Shift polys w/ mult. ? Substitution Poly. time Polytope scaling Poly. time

Precomputation shift polynomial strategy Bounds and symbolic polytope are precomputed Asymptotic bounds Symbolic input polys Symbolic polytope Gr bner basis Doubly exp. Interpolation Heuristic Input polys in [?] Polytope w/ small mult. Shift polys w/ mult. ? Substitution Poly. time Polytope scaling Poly. time Actual attack takes polynomial time

Precomputation shift polynomial strategy Theoretical guarantees: Polynomial runtime Shift polynomials and coeffs. are polynomially bounded. Asymptotic bounds Derives bounds of the form ?? < ?? ???. Heuristic assumptions Correctness depends on polynomial assumption. No optimality guarantee Different strategies may have better bounds. Practical reality: Fast runtime Avoids Gr bner basis calculations at runtime Slow precomputation GBs and polynomial interpolation can be expensive Worse performance Suboptimal shift polynomials for low multiplicity Partially automated Must specify vertices of polytope and other parameters

Summary of Experiments How do these strategies compare to prior work? Evaluated on 14 applications of Coppersmith s method. In 3 / 14 cases, the provable strategy recovered larger roots than in prior work, the remaining 11 cases recovered roots of the same size. In 5 / 14 cases, the graph-based strategy used smaller lattices while recovering roots of the same size. In 7 cases, the lattice dimension was comparable to prior work. In 10 / 12 cases, the precomputation strategy was as fast as or faster than prior work, excluding the time spent doing precomputation. In 3 / 12 cases, the precomputation strategy improved asymptotic bounds from prior work, and in 8 cases matched the bounds.

When to use these strategies If you want practical results, try the automated graph-based strategy or the provable strategy. If you want theoretical guarantees, use the partially automated precomputation strategy. These are implemented at https://github.com/keeganryan/cuso

Thank you Paper Code ia.cr/2024/1577 https://github.com/keeganryan/cuso Keegan Ryan kryan@ucsd.edu