rsa: Add exponent blinding.

Authored by gniibe on Jun 29 2017, 4:11 AM.

Description

rsa: Add exponent blinding.

* cipher/rsa.c (secret_core_crt): Blind secret D with randomized
nonce R for mpi_powm computation.

The paper describing attack: https://eprint.iacr.org/2017/627

Sliding right into disaster: Left-to-right sliding windows leak
by Daniel J. Bernstein and Joachim Breitner and Daniel Genkin and
Leon Groot Bruinderink and Nadia Heninger and Tanja Lange and
Christine van Vredendaal and Yuval Yarom

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.

Exponent blinding is a kind of workaround to add noise. Signal (leak)
is still there for non-constant-time implementation.

  • Co-authored-by: Werner Koch <wk@gnupg.org>
  • Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>

Details

Committed
gniibeJun 29 2017, 4:11 AM
Parents
rC78130828e9a1: Same computation for square and multiply.
Branches
Unknown
Tags
Unknown