From 410d70bad9a650e3837055e36f157894ae49a57d Mon Sep 17 00:00:00 2001 From: Werner Koch 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 --- cipher/elgamal.c | 46 +++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 41 insertions(+), 5 deletions(-) --- a/cipher/elgamal.c +++ b/cipher/elgamal.c @@ -38,6 +38,12 @@ } ELG_public_key; +/* 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,42 @@ 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); + + 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 +538,7 @@ log_mpidump("elg decrypted M= ", output); } #endif - mpi_free(t1); + mpi_free (t1); }