[git] GCRYPT - branch, master, updated. libgcrypt-1.7.3-111-g8725c99

[by NIIBE Yutaka]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "The GNU crypto library".

The branch, master has been updated
       via  8725c99ffa41778f382ca97233183bcd687bb0ce (commit)
      from  78130828e9a140a9de4dafadbc844dbb64cb709a (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit 8725c99ffa41778f382ca97233183bcd687bb0ce
Author: NIIBE Yutaka <gniibe at fsij.org>
Date:   Thu Jun 29 11:11:37 2017 +0900

    rsa: Add exponent blinding.
    
    * cipher/rsa.c (secret_core_crt): Blind secret D with randomized
    nonce R for mpi_powm computation.
    
    --
    
    Co-authored-by: Werner Koch <wk at gnupg.org>
    Signed-off-by: NIIBE Yutaka <gniibe at fsij.org>
    
    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.

diff --git a/cipher/rsa.c b/cipher/rsa.c
index 9f83e8f..ce73f10 100644
--- a/cipher/rsa.c
+++ b/cipher/rsa.c
@@ -1019,16 +1019,37 @@ secret_core_crt (gcry_mpi_t M, gcry_mpi_t C,
   gcry_mpi_t m1 = mpi_alloc_secure ( Nlimbs + 1 );
   gcry_mpi_t m2 = mpi_alloc_secure ( Nlimbs + 1 );
   gcry_mpi_t h  = mpi_alloc_secure ( Nlimbs + 1 );
-
-  /* m1 = c ^ (d mod (p-1)) mod p */
+  gcry_mpi_t D_blind = mpi_alloc_secure ( Nlimbs + 1 );
+  gcry_mpi_t r;
+  unsigned int r_nbits;
+
+  r_nbits = mpi_get_nbits (P) / 4;
+  if (r_nbits < 96)
+    r_nbits = 96;
+  r = mpi_alloc_secure ( (r_nbits + BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB );
+
+  /* d_blind = (d mod (p-1)) + (p-1) * r            */
+  /* m1 = c ^ d_blind mod p */
+  _gcry_mpi_randomize (r, r_nbits, GCRY_WEAK_RANDOM);
+  mpi_set_highbit (r, r_nbits - 1);
   mpi_sub_ui ( h, P, 1 );
+  mpi_mul ( D_blind, h, r );
   mpi_fdiv_r ( h, D, h );
-  mpi_powm ( m1, C, h, P );
+  mpi_add ( D_blind, D_blind, h );
+  mpi_powm ( m1, C, D_blind, P );
 
-  /* m2 = c ^ (d mod (q-1)) mod q */
+  /* d_blind = (d mod (q-1)) + (q-1) * r            */
+  /* m2 = c ^ d_blind mod q */
+  _gcry_mpi_randomize (r, r_nbits, GCRY_WEAK_RANDOM);
+  mpi_set_highbit (r, r_nbits - 1);
   mpi_sub_ui ( h, Q, 1  );
+  mpi_mul ( D_blind, h, r );
   mpi_fdiv_r ( h, D, h );
-  mpi_powm ( m2, C, h, Q );
+  mpi_add ( D_blind, D_blind, h );
+  mpi_powm ( m2, C, D_blind, Q );
+
+  mpi_free ( r );
+  mpi_free ( D_blind );
 
   /* h = u * ( m2 - m1 ) mod q */
   mpi_sub ( h, m2, m1 );

-----------------------------------------------------------------------

Summary of changes:
 cipher/rsa.c | 31 ++++++++++++++++++++++++++-----
 1 file changed, 26 insertions(+), 5 deletions(-)


hooks/post-receive
-- 
The GNU crypto library
http://git.gnupg.org


_______________________________________________
Gnupg-commits mailing list
Gnupg-commits at gnupg.org
http://lists.gnupg.org/mailman/listinfo/gnupg-commits