Package: gnupg / 1.4.18-7+deb8u5

0044-mpi-Avoid-data-dependent-timing-variations-in-mpi_po.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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
From 6cbc75e71295f23431c4ab95edc7573f2fc28476 Mon Sep 17 00:00:00 2001
From: NIIBE Yutaka <gniibe@fsij.org>
Date: Thu, 26 Feb 2015 21:00:05 +0900
Subject: [PATCH 44/45] mpi: Avoid data-dependent timing variations in
 mpi_powm.

* include/mpi.h, mpi/mpiutils.c (mpi_set_cond): New.
* mpi/mpi-pow.c (SIZE_PRECOMP): Rename from SIZE_B_2I3.
(mpi_powm): Access all data in the table and use mpi_set_cond.

--

Access to the precomputed table was indexed by a portion of EXPO,
which could be mounted by a side channel attack.  This change fixes
this particular data-dependent access pattern.
---
 include/mpi.h |  1 +
 mpi/mpi-pow.c | 93 ++++++++++++++++++++++++++++++++++-------------------------
 mpi/mpiutil.c | 28 ++++++++++++++++++
 3 files changed, 82 insertions(+), 40 deletions(-)

diff --git a/include/mpi.h b/include/mpi.h
index a027d2a..a4c16f5 100644
--- a/include/mpi.h
+++ b/include/mpi.h
@@ -81,6 +81,7 @@ void *mpi_get_opaque( MPI a, unsigned int *len );
 void mpi_set_secure( MPI a );
 void mpi_clear( MPI a );
 void mpi_set( MPI w, MPI u);
+void mpi_set_cond( MPI w, MPI u, unsigned long set);
 void mpi_set_ui( MPI w, ulong u);
 MPI  mpi_alloc_set_ui( unsigned long u);
 void mpi_m_check( MPI a );
diff --git a/mpi/mpi-pow.c b/mpi/mpi-pow.c
index 1c3fadb..7f23a5a 100644
--- a/mpi/mpi-pow.c
+++ b/mpi/mpi-pow.c
@@ -344,7 +344,7 @@ mul_mod (mpi_ptr_t xp, mpi_size_t *xsize_p,
      *xsize_p = rsize + ssize;
 }
 
-#define SIZE_B_2I3 ((1 << (5 - 1)) - 1)
+#define SIZE_PRECOMP ((1 << (5 - 1)))
 
 /****************
  * RES = BASE ^ EXPO mod MOD
@@ -375,11 +375,12 @@ mpi_powm (MPI res, MPI base, MPI expo, MPI mod)
   mpi_ptr_t bp_marker = NULL;
   mpi_ptr_t ep_marker = NULL;
   mpi_ptr_t xp_marker = NULL;
-  mpi_ptr_t b_2i3[SIZE_B_2I3]; /* Pre-computed array: BASE^3, ^5, ^7, ... */
-  mpi_size_t b_2i3size[SIZE_B_2I3];
+  mpi_ptr_t precomp[SIZE_PRECOMP]; /* Pre-computed array: BASE^1, ^3, ^5, ... */
+  mpi_size_t precomp_size[SIZE_PRECOMP];
   mpi_size_t W;
   mpi_ptr_t base_u;
   mpi_size_t base_u_size;
+  mpi_size_t max_u_size;
 
   esize = expo->nlimbs;
   msize = mod->nlimbs;
@@ -493,7 +494,7 @@ mpi_powm (MPI res, MPI base, MPI expo, MPI mod)
 
   /* Main processing.  */
   {
-    mpi_size_t i, j;
+    mpi_size_t i, j, k;
     mpi_ptr_t xp;
     mpi_size_t xsize;
     int c;
@@ -507,33 +508,29 @@ mpi_powm (MPI res, MPI base, MPI expo, MPI mod)
     memset( &karactx, 0, sizeof karactx );
     negative_result = (ep[0] & 1) && bsign;
 
-    /* Precompute B_2I3[], BASE^(2 * i + 3), BASE^3, ^5, ^7, ... */
+    /* Precompute PRECOMP[], BASE^(2 * i + 1), BASE^1, ^3, ^5, ... */
     if (W > 1)                  /* X := BASE^2 */
       mul_mod (xp, &xsize, bp, bsize, bp, bsize, mp, msize, &karactx);
-    for (i = 0; i < (1 << (W - 1)) - 1; i++)
-      {                         /* B_2I3[i] = BASE^(2 * i + 3) */
-        if (i == 0)
-          {
-            base_u = bp;
-            base_u_size = bsize;
-          }
-        else
-          {
-            base_u = b_2i3[i-1];
-            base_u_size = b_2i3size[i-1];
-          }
-
+    base_u = precomp[0] = mpi_alloc_limb_space (bsize, esec);
+    base_u_size = max_u_size = precomp_size[0] = bsize;
+    MPN_COPY (precomp[0], bp, bsize);
+    for (i = 1; i < (1 << (W - 1)); i++)
+      {                         /* PRECOMP[i] = BASE^(2 * i + 1) */
         if (xsize >= base_u_size)
           mul_mod (rp, &rsize, xp, xsize, base_u, base_u_size,
                    mp, msize, &karactx);
         else
           mul_mod (rp, &rsize, base_u, base_u_size, xp, xsize,
                    mp, msize, &karactx);
-        b_2i3[i] = mpi_alloc_limb_space (rsize, esec);
-        b_2i3size[i] = rsize;
-        MPN_COPY (b_2i3[i], rp, rsize);
+        base_u = precomp[i] = mpi_alloc_limb_space (rsize, esec);
+        base_u_size = precomp_size[i] = rsize;
+        if (max_u_size < base_u_size)
+          max_u_size = base_u_size;
+        MPN_COPY (precomp[i], rp, rsize);
       }
 
+    base_u = mpi_alloc_limb_space (max_u_size, esec);
+
     i = esize - 1;
 
     /* Main loop.
@@ -619,17 +616,26 @@ mpi_powm (MPI res, MPI base, MPI expo, MPI mod)
               rsize = xsize;
             }
 
-          if (e0 == 0)
+          /*
+           *  base_u <= precomp[e0]
+           *  base_u_size <= precomp_size[e0];
+           */
+          base_u_size = 0;
+          for (k = 0; k < (1<< (W - 1)); k++)
             {
-              base_u = bp;
-              base_u_size = bsize;
+              struct gcry_mpi w, u;
+              w.alloced = w.nlimbs = precomp_size[k];
+              u.alloced = u.nlimbs = precomp_size[k];
+              w.nbits = w.nlimbs * BITS_PER_MPI_LIMB;
+              u.nbits = u.nlimbs * BITS_PER_MPI_LIMB;
+              w.sign = u.sign = 0;
+              w.flags = u.flags = 0;
+              w.d = base_u;
+              u.d = precomp[k];
+
+              mpi_set_cond (&w, &u, k == e0);
+              base_u_size |= (precomp_size[k] & ((mpi_size_t)0 - (k == e0)) );
             }
-          else
-            {
-              base_u = b_2i3[e0 - 1];
-              base_u_size = b_2i3size[e0 -1];
-            }
-
           mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
                    mp, msize, &karactx);
           tp = rp; rp = xp; xp = tp;
@@ -655,15 +661,21 @@ mpi_powm (MPI res, MPI base, MPI expo, MPI mod)
 
     if (e != 0)
       {
-        if ((e>>1) == 0)
-          {
-            base_u = bp;
-            base_u_size = bsize;
-          }
-        else
+        base_u_size = 0;
+        for (k = 0; k < (1<< (W - 1)); k++)
           {
-            base_u = b_2i3[(e>>1) - 1];
-            base_u_size = b_2i3size[(e>>1) -1];
+            struct gcry_mpi w, u;
+            w.alloced = w.nlimbs = precomp_size[k];
+            u.alloced = u.nlimbs = precomp_size[k];
+            w.nbits = w.nlimbs * BITS_PER_MPI_LIMB;
+            u.nbits = u.nlimbs * BITS_PER_MPI_LIMB;
+            w.sign = u.sign = 0;
+            w.flags = u.flags = 0;
+            w.d = base_u;
+            u.d = precomp[k];
+
+            mpi_set_cond (&w, &u, k == (e>>1));
+            base_u_size |= (precomp_size[k] & ((mpi_size_t)0 - (k == (e>>1))) );
           }
 
         mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
@@ -713,8 +725,9 @@ mpi_powm (MPI res, MPI base, MPI expo, MPI mod)
     MPN_NORMALIZE (rp, rsize);
 
     mpihelp_release_karatsuba_ctx (&karactx );
-    for (i = 0; i < (1 << (W - 1)) - 1; i++)
-      mpi_free_limb_space (b_2i3[i]);
+    for (i = 0; i < (1 << (W - 1)); i++)
+      mpi_free_limb_space (precomp[i]);
+    mpi_free_limb_space (base_u);
   }
 
   /* Fixup for negative results.  */
diff --git a/mpi/mpiutil.c b/mpi/mpiutil.c
index 3a1d71f..8b2071a 100644
--- a/mpi/mpiutil.c
+++ b/mpi/mpiutil.c
@@ -433,6 +433,34 @@ mpi_set( MPI w, MPI u)
 
 
 void
+mpi_set_cond( MPI w, MPI u, unsigned long set)
+{
+    mpi_size_t i;
+    mpi_size_t nlimbs = u->alloced;
+    mpi_limb_t mask = ((mpi_limb_t)0) - !!set;
+    mpi_limb_t x;
+
+    if (w->alloced != u->alloced)
+      log_bug ("mpi_set_cond: different sizes\n");
+
+    for (i = 0; i < nlimbs; i++)
+      {
+        x = mask & (w->d[i] ^ u->d[i]);
+        w->d[i] = w->d[i] ^ x;
+      }
+
+    x = mask & (w->nlimbs ^ u->nlimbs);
+    w->nlimbs = w->nlimbs ^ x;
+
+    x = mask & (w->nbits ^ u->nbits);
+    w->nbits = w->nbits ^ x;
+
+    x = mask & (w->sign ^ u->sign);
+    w->sign = w->sign ^ x;
+}
+
+
+void
 mpi_set_ui( MPI w, unsigned long u)
 {
     RESIZE_IF_NEEDED(w, 1);
-- 
2.1.4