Package: gnupg / 1.4.18-7+deb8u5

0029-Use-ciphertext-blinding-for-Elgamal-decryption.patch Patch series | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
From ff53cf06e966dce0daba5f2c84e03ab9db2c3c8b Mon Sep 17 00:00:00 2001
From: Werner Koch <wk@gnupg.org>
Date: Mon, 11 Aug 2014 16:15:40 +0200
Subject: [PATCH 29/45] 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.

Unfortunately, the performance impact of Elgamal blinding is quite
noticeable: For a 3072 bit Elgamal key the decryption used to take
13ms; with the blinding it takes 24ms.  This has been measured using
time(1), calling gpg with a 100 byte message, and having gpg modified
to run the pubkey_decrypt function 100 times and finally scale the
result (using an i5-2410M CPU @ 2.30GHz TP 220).
---
 cipher/elgamal.c | 63 +++++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 49 insertions(+), 14 deletions(-)

diff --git a/cipher/elgamal.c b/cipher/elgamal.c
index 5143ecc..2ec5217 100644
--- a/cipher/elgamal.c
+++ b/cipher/elgamal.c
@@ -31,6 +31,11 @@
 #include "cipher.h"
 #include "elgamal.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 {
     MPI p;	    /* prime */
     MPI g;	    /* group generator */
@@ -372,25 +377,55 @@ do_encrypt(MPI a, MPI b, MPI input, ELG_public_key *pkey )
 static void
 decrypt(MPI output, MPI a, MPI b, ELG_secret_key *skey )
 {
-    MPI t1 = mpi_alloc_secure( mpi_get_nlimbs( skey->p ) );
+  MPI t1, t2, r;
+  unsigned int nbits = mpi_get_nbits (skey->p);
+
+  mpi_normalize (a);
+  mpi_normalize (b);
+
+  t1 = mpi_alloc_secure (mpi_nlimb_hint_from_nbits (nbits));
+#ifdef USE_BLINDING
+
+  t2 = mpi_alloc_secure (mpi_nlimb_hint_from_nbits (nbits));
+  r  = mpi_alloc (mpi_nlimb_hint_from_nbits (nbits));
+
+  /* We need a random number of about the prime size.  The random
+     number merely needs to be unpredictable; thus we use level 0.  */
+  randomize_mpi (r, nbits, 0);
+
+  /* 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_normalize (a);
-    mpi_normalize (b);
+  mpi_free (r);
+  mpi_free (t2);
+
+#else /*!USE_BLINDING*/
+
+  /* output = b/(a^x) mod 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);
 
-    /* output = b/(a^x) mod p */
-    mpi_powm( t1, a, skey->x, skey->p );
-    mpi_invm( t1, t1, skey->p );
-    mpi_mulm( output, b, t1, skey->p );
 #if 0
-    if( DBG_CIPHER ) {
-	log_mpidump("elg decrypted x= ", skey->x);
-	log_mpidump("elg decrypted p= ", skey->p);
-	log_mpidump("elg decrypted a= ", a);
-	log_mpidump("elg decrypted b= ", b);
-	log_mpidump("elg decrypted M= ", output);
+  if (DBG_CIPHER)
+    {
+      log_mpidump("elg decrypted x= ", skey->x);
+      log_mpidump("elg decrypted p= ", skey->p);
+      log_mpidump("elg decrypted a= ", a);
+      log_mpidump("elg decrypted b= ", b);
+      log_mpidump("elg decrypted M= ", output);
     }
 #endif
-    mpi_free(t1);
+  mpi_free (t1);
 }
 
 
-- 
2.1.4