From 35cd81f134c0da4e7e6fcfe40d270ee1251f52c2 Mon Sep 17 00:00:00 2001
From: Werner Koch <wk@gnupg.org>
Date: Mon, 23 Feb 2015 11:39:58 +0100
Subject: [PATCH] cipher: Use ciphertext blinding for Elgamal decryption.

* cipher/elgamal.c (USE_BLINDING): New.
(decrypt): Rewrite to use ciphertext blinding.
--

CVE-id: CVE-2014-3591

As a countermeasure to a new side-channel attacks on sliding windows
exponentiation we blind the ciphertext for Elgamal decryption.  This
is similar to what we are doing with RSA. This patch is a backport of
the GnuPG 1.4 commit ff53cf06e966dce0daba5f2c84e03ab9db2c3c8b.

Unfortunately, the performance impact of Elgamal blinding is quite
noticeable (i5-2410M CPU @ 2.30GHz TP 220):

  Algorithm         generate  100*priv  100*public
  ------------------------------------------------
  ELG 1024 bit             -     100ms        90ms
  ELG 2048 bit             -     330ms       350ms
  ELG 3072 bit             -     660ms       790ms

  Algorithm         generate  100*priv  100*public
  ------------------------------------------------
  ELG 1024 bit             -     150ms        90ms
  ELG 2048 bit             -     520ms       360ms
  ELG 3072 bit             -    1100ms       800ms

Signed-off-by: Werner Koch <wk@gnupg.org>
(cherry picked from commit 410d70bad9a650e3837055e36f157894ae49a57d)

Resolved conflicts:
	cipher/elgamal.c.
---
 cipher/elgamal.c | 49 ++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 44 insertions(+), 5 deletions(-)

diff --git a/cipher/elgamal.c b/cipher/elgamal.c
index ce4be85..b2c55b3 100644
--- a/cipher/elgamal.c
+++ b/cipher/elgamal.c
@@ -30,6 +30,12 @@
 #include "mpi.h"
 #include "cipher.h"
 
+/* Blinding is used to mitigate side-channel attacks.  You may undef
+   this to speed up the operation in case the system is secured
+   against physical and network mounted side-channel attacks.  */
+#define USE_BLINDING 1
+
+
 typedef struct
 {
   gcry_mpi_t p;	    /* prime */
@@ -486,12 +492,45 @@ do_encrypt(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
 static void
 decrypt(gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b, ELG_secret_key *skey )
 {
-  gcry_mpi_t t1 = mpi_alloc_secure( mpi_get_nlimbs( skey->p ) );
+  gcry_mpi_t t1, t2, r;
+  unsigned int nbits = mpi_get_nbits (skey->p);
+
+  mpi_normalize (a);
+  mpi_normalize (b);
+
+  t1 = mpi_snew (nbits);
+
+#ifdef USE_BLINDING
+
+  t2 = mpi_snew (nbits);
+  r  = mpi_new (nbits);
+
+  /* We need a random number of about the prime size.  The random
+     number merely needs to be unpredictable; thus we use level 0.  */
+  _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);
+
+  /* t1 = r^x mod p */
+  mpi_powm (t1, r, skey->x, skey->p);
+  /* t2 = (a * r)^-x mod p */
+  mpi_mulm (t2, a, r, skey->p);
+  mpi_powm (t2, t2, skey->x, skey->p);
+  mpi_invm (t2, t2, skey->p);
+  /* t1 = (t1 * t2) mod p*/
+  mpi_mulm (t1, t1, t2, skey->p);
+
+  mpi_free (r);
+  mpi_free (t2);
+
+#else /*!USE_BLINDING*/
 
   /* output = b/(a^x) mod p */
-  gcry_mpi_powm( t1, a, skey->x, skey->p );
-  mpi_invm( t1, t1, skey->p );
-  mpi_mulm( output, b, t1, skey->p );
+  mpi_powm (t1, a, skey->x, skey->p);
+  mpi_invm (t1, t1, skey->p);
+
+#endif /*!USE_BLINDING*/
+
+  mpi_mulm (output, b, t1, skey->p);
+
 #if 0
   if( DBG_CIPHER )
     {
@@ -502,7 +541,7 @@ decrypt(gcry_mpi_t output, gcry_mpi_t a, gcry_mpi_t b, ELG_secret_key *skey )
       log_mpidump("elg decrypted M= ", output);
     }
 #endif
-  mpi_free(t1);
+  mpi_free (t1);
 }
 
 
-- 
2.1.4