← Back to branch summary

~ubuntu-branches/ubuntu/vivid/gnupg/vivid

« back to all changes in this revision

Viewing changes to .pc/CVE-2013-4576/cipher/rsa.c

  • Committer: Package Import Robot
  • Author(s): Marc Deslauriers
  • Date: 2013-12-20 08:17:09 UTC
  • mfrom: (1.1.23 sid)
  • Revision ID: package-import@ubuntu.com-20131220081709-uylvbzvk4m7dej37
Tags: 1.4.15-2ubuntu1
* Resynchronise with Debian.  Remaining changes:
  - Disable mlock() test since it fails with ulimit 0 (on buildds).
  - Set gpg (or gpg2) and gpgsm to use a passphrase agent by default.
  - Only suggest gnupg-curl and libldap; recommendations are pulled into
    minimal, and we don't need the keyserver utilities in a minimal Ubuntu
    system.
  - Remove the Win32 build.
  - Build using dh-autoreconf
  - Disable inline assembler for ppc64el.
* Moved CVE-2013-4576 patch to the right directory, and added to series
  file so it actually gets applied.

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/CVE-2013-4576/cipher/rsa.c
 
1
/* rsa.c  -  RSA function
 
2
 *      Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn)
 
3
 *      Copyright (C) 2000, 2001 Free Software Foundation, Inc.
 
4
 *
 
5
 * This file is part of GnuPG.
 
6
 *
 
7
 * GnuPG is free software; you can redistribute it and/or modify
 
8
 * it under the terms of the GNU General Public License as published by
 
9
 * the Free Software Foundation; either version 3 of the License, or
 
10
 * (at your option) any later version.
 
11
 *
 
12
 * GnuPG is distributed in the hope that it will be useful,
 
13
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
 * GNU General Public License for more details.
 
16
 *
 
17
 * You should have received a copy of the GNU General Public License
 
18
 * along with this program; if not, see <http://www.gnu.org/licenses/>.
 
19
 */
 
20
 
 
21
/* This code uses an algorithm protected by U.S. Patent #4,405,829
 
22
   which expires on September 20, 2000.  The patent holder placed that
 
23
   patent into the public domain on Sep 6th, 2000.
 
24
*/
 
25
 
 
26
#include <config.h>
 
27
#include <stdio.h>
 
28
#include <stdlib.h>
 
29
#include <string.h>
 
30
#include "util.h"
 
31
#include "mpi.h"
 
32
#include "cipher.h"
 
33
#include "rsa.h"
 
34
 
 
35
 
 
36
typedef struct {
 
37
    MPI n;          /* modulus */
 
38
    MPI e;          /* exponent */
 
39
} RSA_public_key;
 
40
 
 
41
 
 
42
typedef struct {
 
43
    MPI n;          /* public modulus */
 
44
    MPI e;          /* public exponent */
 
45
    MPI d;          /* exponent */
 
46
    MPI p;          /* prime  p. */
 
47
    MPI q;          /* prime  q. */
 
48
    MPI u;          /* inverse of p mod q. */
 
49
} RSA_secret_key;
 
50
 
 
51
 
 
52
static void test_keys( RSA_secret_key *sk, unsigned nbits );
 
53
static void generate( RSA_secret_key *sk, unsigned nbits );
 
54
static int  check_secret_key( RSA_secret_key *sk );
 
55
static void public(MPI output, MPI input, RSA_public_key *skey );
 
56
static void secret(MPI output, MPI input, RSA_secret_key *skey );
 
57
 
 
58
 
 
59
static void
 
60
test_keys( RSA_secret_key *sk, unsigned nbits )
 
61
{
 
62
    RSA_public_key pk;
 
63
    MPI test = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
 
64
    MPI out1 = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
 
65
    MPI out2 = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
 
66
 
 
67
    pk.n = sk->n;
 
68
    pk.e = sk->e;
 
69
    {   char *p = get_random_bits( nbits, 0, 0 );
 
70
        mpi_set_buffer( test, p, (nbits+7)/8, 0 );
 
71
        xfree(p);
 
72
    }
 
73
 
 
74
    public( out1, test, &pk );
 
75
    secret( out2, out1, sk );
 
76
    if( mpi_cmp( test, out2 ) )
 
77
        log_fatal("RSA operation: public, secret failed\n");
 
78
    secret( out1, test, sk );
 
79
    public( out2, out1, &pk );
 
80
    if( mpi_cmp( test, out2 ) )
 
81
        log_fatal("RSA operation: secret, public failed\n");
 
82
    mpi_free( test );
 
83
    mpi_free( out1 );
 
84
    mpi_free( out2 );
 
85
}
 
86
 
 
87
/****************
 
88
 * Generate a key pair with a key of size NBITS
 
89
 * Returns: 2 structures filled with all needed values
 
90
 */
 
91
static void
 
92
generate( RSA_secret_key *sk, unsigned nbits )
 
93
{
 
94
    MPI p, q; /* the two primes */
 
95
    MPI d;    /* the private key */
 
96
    MPI u;
 
97
    MPI t1, t2;
 
98
    MPI n;    /* the public key */
 
99
    MPI e;    /* the exponent */
 
100
    MPI phi;  /* helper: (p-1)(q-1) */
 
101
    MPI g;
 
102
    MPI f;
 
103
 
 
104
    /* make sure that nbits is even so that we generate p, q of equal size */
 
105
    if ( (nbits&1) )
 
106
      nbits++; 
 
107
 
 
108
    n = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
 
109
 
 
110
    p = q = NULL;
 
111
    do {
 
112
      /* select two (very secret) primes */
 
113
      if (p)
 
114
        mpi_free (p);
 
115
      if (q)
 
116
        mpi_free (q);
 
117
      p = generate_secret_prime( nbits / 2 );
 
118
      q = generate_secret_prime( nbits / 2 );
 
119
      if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
 
120
        mpi_swap(p,q);
 
121
      /* calculate the modulus */
 
122
      mpi_mul( n, p, q );
 
123
    } while ( mpi_get_nbits(n) != nbits );
 
124
 
 
125
    /* calculate Euler totient: phi = (p-1)(q-1) */
 
126
    t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
 
127
    t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
 
128
    phi = mpi_alloc_secure ( mpi_nlimb_hint_from_nbits (nbits) );
 
129
    g   = mpi_alloc_secure ( mpi_nlimb_hint_from_nbits (nbits) );
 
130
    f   = mpi_alloc_secure ( mpi_nlimb_hint_from_nbits (nbits) );
 
131
    mpi_sub_ui( t1, p, 1 );
 
132
    mpi_sub_ui( t2, q, 1 );
 
133
    mpi_mul( phi, t1, t2 );
 
134
    mpi_gcd(g, t1, t2);
 
135
    mpi_fdiv_q(f, phi, g);
 
136
 
 
137
    /* Find an public exponent.
 
138
       Benchmarking the RSA verify function with a 1024 bit key yields
 
139
       (2001-11-08):
 
140
         e=17    0.54 ms
 
141
         e=41    0.75 ms
 
142
         e=257   0.95 ms
 
143
         e=65537 1.80 ms
 
144
 
 
145
       This code used 41 until 2006-06-28 when it was changed to use
 
146
       65537 as the new best practice.  See FIPS-186-3.
 
147
     */
 
148
    e = mpi_alloc ( mpi_nlimb_hint_from_nbits (32) );
 
149
    mpi_set_ui( e, 65537); 
 
150
    while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
 
151
      mpi_add_ui( e, e, 2);
 
152
 
 
153
    /* calculate the secret key d = e^1 mod phi */
 
154
    d = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
 
155
    mpi_invm(d, e, f );
 
156
    /* calculate the inverse of p and q (used for chinese remainder theorem)*/
 
157
    u = mpi_alloc ( mpi_nlimb_hint_from_nbits (nbits) );
 
158
    mpi_invm(u, p, q );
 
159
 
 
160
    if( DBG_CIPHER ) {
 
161
        log_mpidump("  p= ", p );
 
162
        log_mpidump("  q= ", q );
 
163
        log_mpidump("phi= ", phi );
 
164
        log_mpidump("  g= ", g );
 
165
        log_mpidump("  f= ", f );
 
166
        log_mpidump("  n= ", n );
 
167
        log_mpidump("  e= ", e );
 
168
        log_mpidump("  d= ", d );
 
169
        log_mpidump("  u= ", u );
 
170
    }
 
171
 
 
172
    mpi_free(t1);
 
173
    mpi_free(t2);
 
174
    mpi_free(phi);
 
175
    mpi_free(f);
 
176
    mpi_free(g);
 
177
 
 
178
    sk->n = n;
 
179
    sk->e = e;
 
180
    sk->p = p;
 
181
    sk->q = q;
 
182
    sk->d = d;
 
183
    sk->u = u;
 
184
 
 
185
    /* now we can test our keys (this should never fail!) */
 
186
    test_keys( sk, nbits - 64 );
 
187
}
 
188
 
 
189
 
 
190
/****************
 
191
 * Test wether the secret key is valid.
 
192
 * Returns: true if this is a valid key.
 
193
 */
 
194
static int
 
195
check_secret_key( RSA_secret_key *sk )
 
196
{
 
197
    int rc;
 
198
    MPI temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 );
 
199
 
 
200
    mpi_mul(temp, sk->p, sk->q );
 
201
    rc = mpi_cmp( temp, sk->n );
 
202
    mpi_free(temp);
 
203
    return !rc;
 
204
}
 
205
 
 
206
 
 
207
 
 
208
/****************
 
209
 * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
 
210
 *
 
211
 *      c = m^e mod n
 
212
 *
 
213
 * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
 
214
 */
 
215
static void
 
216
public(MPI output, MPI input, RSA_public_key *pkey )
 
217
{
 
218
    if( output == input ) { /* powm doesn't like output and input the same */
 
219
        MPI x = mpi_alloc( mpi_get_nlimbs(input)*2 );
 
220
        mpi_powm( x, input, pkey->e, pkey->n );
 
221
        mpi_set(output, x);
 
222
        mpi_free(x);
 
223
    }
 
224
    else
 
225
        mpi_powm( output, input, pkey->e, pkey->n );
 
226
}
 
227
 
 
228
#if 0
 
229
static void
 
230
stronger_key_check ( RSA_secret_key *skey )
 
231
{
 
232
    MPI t = mpi_alloc_secure ( 0 );
 
233
    MPI t1 = mpi_alloc_secure ( 0 );
 
234
    MPI t2 = mpi_alloc_secure ( 0 );
 
235
    MPI phi = mpi_alloc_secure ( 0 );
 
236
 
 
237
    /* check that n == p * q */
 
238
    mpi_mul( t, skey->p, skey->q);
 
239
    if (mpi_cmp( t, skey->n) )
 
240
        log_info ( "RSA Oops: n != p * q\n" );
 
241
 
 
242
    /* check that p is less than q */
 
243
    if( mpi_cmp( skey->p, skey->q ) > 0 )
 
244
        log_info ("RSA Oops: p >= q\n");
 
245
 
 
246
 
 
247
    /* check that e divides neither p-1 nor q-1 */
 
248
    mpi_sub_ui(t, skey->p, 1 );
 
249
    mpi_fdiv_r(t, t, skey->e );
 
250
    if ( !mpi_cmp_ui( t, 0) )
 
251
        log_info ( "RSA Oops: e divides p-1\n" );
 
252
    mpi_sub_ui(t, skey->q, 1 );
 
253
    mpi_fdiv_r(t, t, skey->e );
 
254
    if ( !mpi_cmp_ui( t, 0) )
 
255
        log_info ( "RSA Oops: e divides q-1\n" );
 
256
 
 
257
    /* check that d is correct */
 
258
    mpi_sub_ui( t1, skey->p, 1 );
 
259
    mpi_sub_ui( t2, skey->q, 1 );
 
260
    mpi_mul( phi, t1, t2 );
 
261
    mpi_gcd(t, t1, t2);
 
262
    mpi_fdiv_q(t, phi, t);
 
263
    mpi_invm(t, skey->e, t );
 
264
    if ( mpi_cmp(t, skey->d ) )
 
265
        log_info ( "RSA Oops: d is wrong\n");
 
266
 
 
267
    /* check for crrectness of u */
 
268
    mpi_invm(t, skey->p, skey->q );
 
269
    if ( mpi_cmp(t, skey->u ) )
 
270
        log_info ( "RSA Oops: u is wrong\n");
 
271
   
 
272
    log_info ( "RSA secret key check finished\n");
 
273
 
 
274
    mpi_free (t);
 
275
    mpi_free (t1);
 
276
    mpi_free (t2);
 
277
    mpi_free (phi);
 
278
}
 
279
#endif
 
280
 
 
281
 
 
282
/****************
 
283
 * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
 
284
 *
 
285
 *      m = c^d mod n
 
286
 *
 
287
 * Or faster:
 
288
 *
 
289
 *      m1 = c ^ (d mod (p-1)) mod p 
 
290
 *      m2 = c ^ (d mod (q-1)) mod q 
 
291
 *      h = u * (m2 - m1) mod q 
 
292
 *      m = m1 + h * p
 
293
 *
 
294
 * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY.
 
295
 */
 
296
static void
 
297
secret(MPI output, MPI input, RSA_secret_key *skey )
 
298
{
 
299
#if 0
 
300
    mpi_powm( output, input, skey->d, skey->n );
 
301
#else
 
302
    MPI m1   = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
 
303
    MPI m2   = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
 
304
    MPI h    = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 );
 
305
 
 
306
    /* m1 = c ^ (d mod (p-1)) mod p */
 
307
    mpi_sub_ui( h, skey->p, 1  );
 
308
    mpi_fdiv_r( h, skey->d, h );   
 
309
    mpi_powm( m1, input, h, skey->p );
 
310
    /* m2 = c ^ (d mod (q-1)) mod q */
 
311
    mpi_sub_ui( h, skey->q, 1  );
 
312
    mpi_fdiv_r( h, skey->d, h );
 
313
    mpi_powm( m2, input, h, skey->q );
 
314
    /* h = u * ( m2 - m1 ) mod q */
 
315
    mpi_sub( h, m2, m1 );
 
316
    if ( mpi_is_neg( h ) ) 
 
317
        mpi_add ( h, h, skey->q );
 
318
    mpi_mulm( h, skey->u, h, skey->q ); 
 
319
    /* m = m2 + h * p */
 
320
    mpi_mul ( h, h, skey->p );
 
321
    mpi_add ( output, m1, h );
 
322
    /* ready */
 
323
    
 
324
    mpi_free ( h );
 
325
    mpi_free ( m1 );
 
326
    mpi_free ( m2 );
 
327
#endif
 
328
}
 
329
 
 
330
 
 
331
/*********************************************
 
332
 **************  interface  ******************
 
333
 *********************************************/
 
334
 
 
335
int
 
336
rsa_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
 
337
{
 
338
    RSA_secret_key sk;
 
339
 
 
340
    if( !is_RSA(algo) )
 
341
        return G10ERR_PUBKEY_ALGO;
 
342
 
 
343
    generate( &sk, nbits );
 
344
    skey[0] = sk.n;
 
345
    skey[1] = sk.e;
 
346
    skey[2] = sk.d;
 
347
    skey[3] = sk.p;
 
348
    skey[4] = sk.q;
 
349
    skey[5] = sk.u;
 
350
    /* make an empty list of factors */
 
351
    if (retfactors)
 
352
      *retfactors = xmalloc_clear( 1 * sizeof **retfactors );
 
353
    return 0;
 
354
}
 
355
 
 
356
 
 
357
int
 
358
rsa_check_secret_key( int algo, MPI *skey )
 
359
{
 
360
    RSA_secret_key sk;
 
361
 
 
362
    if( !is_RSA(algo) )
 
363
        return G10ERR_PUBKEY_ALGO;
 
364
 
 
365
    sk.n = skey[0];
 
366
    sk.e = skey[1];
 
367
    sk.d = skey[2];
 
368
    sk.p = skey[3];
 
369
    sk.q = skey[4];
 
370
    sk.u = skey[5];
 
371
    if( !check_secret_key( &sk ) )
 
372
        return G10ERR_BAD_SECKEY;
 
373
 
 
374
    return 0;
 
375
}
 
376
 
 
377
 
 
378
 
 
379
int
 
380
rsa_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
 
381
{
 
382
    RSA_public_key pk;
 
383
 
 
384
    if( algo != 1 && algo != 2 )
 
385
        return G10ERR_PUBKEY_ALGO;
 
386
 
 
387
    pk.n = pkey[0];
 
388
    pk.e = pkey[1];
 
389
    resarr[0] = mpi_alloc( mpi_get_nlimbs( pk.n ) );
 
390
    public( resarr[0], data, &pk );
 
391
    return 0;
 
392
}
 
393
 
 
394
int
 
395
rsa_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
 
396
{
 
397
    RSA_secret_key sk;
 
398
 
 
399
    if( algo != 1 && algo != 2 )
 
400
        return G10ERR_PUBKEY_ALGO;
 
401
 
 
402
    sk.n = skey[0];
 
403
    sk.e = skey[1];
 
404
    sk.d = skey[2];
 
405
    sk.p = skey[3];
 
406
    sk.q = skey[4];
 
407
    sk.u = skey[5];
 
408
    *result = mpi_alloc_secure( mpi_get_nlimbs( sk.n ) );
 
409
    secret( *result, data[0], &sk );
 
410
    return 0;
 
411
}
 
412
 
 
413
int
 
414
rsa_sign( int algo, MPI *resarr, MPI data, MPI *skey )
 
415
{
 
416
    RSA_secret_key sk;
 
417
 
 
418
    if( algo != 1 && algo != 3 )
 
419
        return G10ERR_PUBKEY_ALGO;
 
420
 
 
421
    sk.n = skey[0];
 
422
    sk.e = skey[1];
 
423
    sk.d = skey[2];
 
424
    sk.p = skey[3];
 
425
    sk.q = skey[4];
 
426
    sk.u = skey[5];
 
427
    resarr[0] = mpi_alloc( mpi_get_nlimbs( sk.n ) );
 
428
    secret( resarr[0], data, &sk );
 
429
 
 
430
    return 0;
 
431
}
 
432
 
 
433
int
 
434
rsa_verify( int algo, MPI hash, MPI *data, MPI *pkey )
 
435
{
 
436
    RSA_public_key pk;
 
437
    MPI result;
 
438
    int rc;
 
439
 
 
440
    if( algo != 1 && algo != 3 )
 
441
        return G10ERR_PUBKEY_ALGO;
 
442
    pk.n = pkey[0];
 
443
    pk.e = pkey[1];
 
444
    result = mpi_alloc ( mpi_nlimb_hint_from_nbits (160) );
 
445
    public( result, data[0], &pk );
 
446
    rc = mpi_cmp( result, hash )? G10ERR_BAD_SIGN:0;
 
447
    mpi_free(result);
 
448
 
 
449
    return rc;
 
450
}
 
451
 
 
452
 
 
453
unsigned int
 
454
rsa_get_nbits( int algo, MPI *pkey )
 
455
{
 
456
    if( !is_RSA(algo) )
 
457
        return 0;
 
458
    return mpi_get_nbits( pkey[0] );
 
459
}
 
460
 
 
461
 
 
462
/****************
 
463
 * Return some information about the algorithm.  We need algo here to
 
464
 * distinguish different flavors of the algorithm.
 
465
 * Returns: A pointer to string describing the algorithm or NULL if
 
466
 *          the ALGO is invalid.
 
467
 * Usage: Bit 0 set : allows signing
 
468
 *            1 set : allows encryption
 
469
 */
 
470
const char *
 
471
rsa_get_info( int algo,
 
472
              int *npkey, int *nskey, int *nenc, int *nsig, int *r_usage )
 
473
{
 
474
    *npkey = 2;
 
475
    *nskey = 6;
 
476
    *nenc = 1;
 
477
    *nsig = 1;
 
478
 
 
479
    switch( algo ) {
 
480
      case 1: *r_usage = PUBKEY_USAGE_SIG | PUBKEY_USAGE_ENC; return "RSA";
 
481
      case 2: *r_usage = PUBKEY_USAGE_ENC; return "RSA-E";
 
482
      case 3: *r_usage = PUBKEY_USAGE_SIG; return "RSA-S";
 
483
      default:*r_usage = 0; return NULL;
 
484
    }
 
485
}