Search

Abstract Partial key exposure attacks present a significant threat to RSA-type cryptosystems. These attacks factorize the RSA modulus by utilizing partial knowledge of the decryption exponent, which is typically revealed by side-channel attacks, cold boot attacks, etc. In practice, the RSA implementations typically employ countermeasures to resist physical attacks, such as additive exponent blinding $$d' = d + r \varphi (N)$$ d ′ = d + r φ ( N ) with unknown random blinding factor r. Although there are a couple of partial key exposure attacks on blinding RSA, these attacks require a considerable amount of leakage and fail to work when e is up to full size. In this paper, we propose new partial key exposure attacks on RSA with additive exponent blinding, focusing on leakage scenarios where the Most Significant Bits (MSBs) or Least Significant Bits (LSBs) of $$d'$$ d ′ are revealed. For the case where e is small, we first recover partial information of p by solving the quadratic congruence equation, and then find the small roots of the integer equation to recover entire private key. Our method relaxes the attack requirements, for instance, we reduce the amount of MSBs for a successful attack from 75 to 25% when $$e \approx N^{0.25}$$ e ≈ N 0.25 and $$r\approx N^{0}$$ r ≈ N 0 . Furthermore, we propose new attacks using the unique algebraic relationship in blinding RSA, which extend the attack to the case where e is of full size.

Abstract During the standardisation process of post-quantum cryptography, NIST encourages research on side-channel analysis for candidate schemes. As the recommended lattice signature scheme, CRYSTALS-Dilithium, when implemented on hardware, has seen limited research on side-channel analysis, and current attacks are incomplete or requires a substantial quantity of traces. Therefore, we conducted a more complete analysis to investigate the leakage of an FPGA implementation of CRYSTALS-Dilithium using the Correlation Power Analysis (CPA) method, where with a minimum of 70,000 traces partial private key coefficients can be recovered. Furthermore, we optimise the attack by extracting Point-of-Interests using known information due to parallelism (named CPA-PoI) and by iteratively utilising parallel leakages (named CPA-ITR). Our experimental results show that CPA-PoI reduces the number of traces by up to 16.67%, CPA-ITR by up to 25%, and both increase the number of recovered key coefficients by up to 55.17% and 93.10% using the same number of traces. They outperfom the CPA method. As a result, it suggests that the FPGA implementation of CRYSTALS-Dilithium is more vulnerable than thought before to side-channel analysis.

Abstract Many real world attacks often target the implementation of a cryptographic scheme, rather than the algorithm itself, and a system designer has to consider new models that can capture these attacks. For example, if the key can be tampered by physical attacks on the device, the security of the scheme becomes totally unclear. In this work, we investigate predicate encryption (PE), a powerful encryption primitive, in the setting of tampering attacks. First, we show that many existing frameworks to construct PE are vulnerable to tampering attacks. Then we present a new security notion to capture such attacks. Finally, we take Attrapadung’s framework in Eurocrypt’14 as an example to show how to “compile" these frameworks to tampering resilient ones. Moreover, our method is compatible with the original pair encoding schemes without introducing any redundancy.