International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Third is All You Need: Extended Partial Key Exposure Attack on CRT-RSA with Additive Exponent Blinding

Authors:
Yuanyuan Zhou , Crypto Group, ICTEAM Institute, UCLouvain, Louvain-la-Neuve, Belgium
Joop van de Pol , Unaffiliated
Yu Yu , The Department of Computer Science and Engineering, Shanghai Jiao Tong University Shanghai, China
François-Xavier Standaert , Crypto Group, ICTEAM Institute, UCLouvain, Louvain-la-Neuve, Belgium
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: At Eurocrypt 2022, May et al. proposed a partial key exposure (PKE) attack on CRT-RSA that efficiently factors N knowing only a 13-fraction of either most significant bits (MSBs) or least significant bits (LSBs) of private exponents dp and dq for public exponent e≈N112. In practice, PKE attacks typically rely on the side-channel leakage of these exponents, while a side-channel resistant implementation of CRT-RSA often uses additively blinded exponents dp′=dp+rp(p−1) and dq′=dq+rq(q−1) with unknown random blinding factors rp and rq, which makes PKE attacks more challenging. Motivated by the above, we extend the PKE attack of May et al. to CRT-RSA with additive exponent blinding. While admitting rpe∈(0,N14), our extended PKE works ideally when rpe≈N112, in which case the entire private key can be recovered using only 13 known MSBs or LSBs of the blinded CRT exponents dp′ and dq′. Our extended PKE follows their novel two-step approach to first compute the key-dependent constant k′ (edp′=1+k′(p−1), edq′=1+l′(q−1)), and then to factor N by computing the root of a univariate polynomial modulo k′p. We extend their approach as follows. For the MSB case, we propose two options for the first step of the attack, either by obtaining a single estimate k′l′ and calculating k′ via factoring, or by obtaining multiple estimates k′l1′,…,k′lz′ and calculating k′ probabilistically via GCD. For the LSB case, we extend their approach by constructing a different univariate polynomial in the second step of the LSB attack. A formal analysis shows that our LSB attack runs in polynomial time under the standard Coppersmith-type assumption, while our MSB attack either runs in sub-exponential time with a reduced input size (the problem is reduced to factor a number of size e2rprq≈N16) or in probabilistic polynomial time under a novel heuristic assumption. Under the settings of the most common key sizes (1024-bit, 2048-bit, and 3072-bit) and blinding factor lengths (32-bit, 64-bit, and 128-bit), our experiments verify the validity of the Coppersmith-type assumption and our own assumption, as well as the feasibility of the factoring step. To the best of our knowledge, this is the first PKE on CRT-RSA with experimentally verified effectiveness against 128-bit unknown exponent blinding factors. We also demonstrate an application of the proposed PKE attack using real partial side-channel key leakage targeting a Montgomery Ladder exponentiation CRT implementation.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32425,
  title={A Third is All You Need: Extended Partial Key Exposure Attack on CRT-RSA with Additive Exponent Blinding},
  publisher={Springer-Verlag},
  author={Yuanyuan Zhou and Joop van de Pol and Yu Yu and François-Xavier Standaert},
  year=2022
}