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

At Eurocrypt 2022, May et al. proposed a partial key exposure (PKE) attack on CRT-RSA that efficiently factors N knowing only a 1/3-fraction of either most significant bits (MSBs) or least significant bits (LSBs) of private exponents d(p) and d(q) for public exponent e approximate to N-1/12. In practice, PKE attacks typically rely on the side-channel leakage of these exponents, while a side-channel resistant implementation of CRTRSA often uses additively blinded exponents d(p)' = d(p) + r(p)(p - 1) and d(q)' = d(q) + r(q)(q - 1) with unknown random blinding factors r(p) and r(q), 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 r(p)e is an element of(0, N-1/4), our extended PKE works ideally when r(p)e approximate to N-1/12, in which case the entire private key can be recovered using only 1/3 known MSBs or LSBs of the blinded CRT exponents d(p)' and d(q)'. Our extended PKE follows their novel two-step approach to first compute the key-dependent constant k ' (ed(p)' = 1 + k ' (p - 1), ed(q)' = 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 ' l(1)', . . . , k ' l(z)' 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 e(2)r(p)r(q) approximate to N-1/6) 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.