RSA 1024 Bits - Side channel - Sliding right into disaster


For Your Information :slight_smile:

It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits.

In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about exponent bits than for right-to-left. We show how to incorporate this additional information into the Heninger-Shacham algorithm for partial key reconstruction, and use it to obtain very efficient full key recovery for RSA-1024. We also provide strong evidence that the same attack works for RSA-2048 with only moderately more computation.

Very cool - thanks for posting! Congrats on getting it into CHES too if you’re one of the authors. I’ll be there in person so look forward to the presentation.

I’m working on a simple demo of SPA-style RSA attack on the XMEGA, so people might be able to even play with implementing the attack there. The primary issue is the XMEGA is way too slow to run full RSA-1024 using standard libraries… the full decryption is taking like 5 mins :confused: So the tutorial will run with a hacked together few-byte key instead so that you aren’t waiting too long to see results :stuck_out_tongue: