Side Channel Attack to Actual Cryptanalysis: Breaking CRT-RSA with Low Weight Decryption Exponents

Towards the cold boot attack (a kind of side channel attack), the problems of reconstructing RSA parameters when (i) certain bits are unknown (Heninger and Shacham, Crypto 2009) and (ii) the bits are available but with some error probability (Henecka, May and Meurer, Crypto 2010) have been considered very recently. In this paper we exploit the error correction heuristic proposed by Henecka et al to show that CRT-RSA schemes having low Hamming weight decryption exponents are insecure given small encryption exponents (e.g., e=216+1). In particular, we show that the CRT-RSA schemes presented by Lim and Lee (SAC 1996) and Galbraith, Heneghan and McKee (ACISP 2005) with low weight decryption exponents can be broken in a few minutes in certain cases. Further, the scheme of Maitra and Sarkar (CT-RSA 2010), where the decryption exponents are not of low weight but they have large low weight factors, can also be cryptanalysed. We also identify a few modifications of the error correction strategy that provides significantly improved experimental outcome towards the cold boot attack.