← Back to branch summary

~ubuntu-branches/ubuntu/utopic/dropbear/utopic-proposed

« back to all changes in this revision

Viewing changes to libtomcrypt/src/pk/ecc/ecc_sys.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2005-12-08 19:20:21 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051208192021-nyp9rwnt77nsg6ty
Tags: 0.47-1
* New upstream release.
* SECURITY: Fix incorrect buffer sizing.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libtomcrypt/src/pk/ecc/ecc_sys.c
 
1
/* LibTomCrypt, modular cryptographic library -- Tom St Denis
 
2
 *
 
3
 * LibTomCrypt is a library that provides various cryptographic
 
4
 * algorithms in a highly modular and flexible manner.
 
5
 *
 
6
 * The library is free for all purposes without any express
 
7
 * guarantee it works.
 
8
 *
 
9
 * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.org
 
10
 */
 
11
 
 
12
/**
 
13
  @file ecc_sys.c
 
14
  ECC Crypto, Tom St Denis
 
15
*/
 
16
  
 
17
/**
 
18
  Encrypt a symmetric key with ECC 
 
19
  @param in         The symmetric key you want to encrypt
 
20
  @param inlen      The length of the key to encrypt (octets)
 
21
  @param out        [out] The destination for the ciphertext
 
22
  @param outlen     [in/out] The max size and resulting size of the ciphertext
 
23
  @param prng       An active PRNG state
 
24
  @param wprng      The index of the PRNG you wish to use 
 
25
  @param hash       The index of the hash you want to use 
 
26
  @param key        The ECC key you want to encrypt to
 
27
  @return CRYPT_OK if successful
 
28
*/
 
29
int ecc_encrypt_key(const unsigned char *in,   unsigned long inlen,
 
30
                          unsigned char *out,  unsigned long *outlen, 
 
31
                          prng_state *prng, int wprng, int hash, 
 
32
                          ecc_key *key)
 
33
{
 
34
    unsigned char *pub_expt, *ecc_shared, *skey;
 
35
    ecc_key        pubkey;
 
36
    unsigned long  x, y, pubkeysize;
 
37
    int            err;
 
38
 
 
39
    LTC_ARGCHK(in      != NULL);
 
40
    LTC_ARGCHK(out     != NULL);
 
41
    LTC_ARGCHK(outlen  != NULL);
 
42
    LTC_ARGCHK(key     != NULL);
 
43
 
 
44
    /* check that wprng/cipher/hash are not invalid */
 
45
    if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
 
46
       return err;
 
47
    }
 
48
 
 
49
    if ((err = hash_is_valid(hash)) != CRYPT_OK) {
 
50
       return err;
 
51
    }
 
52
 
 
53
    if (inlen > hash_descriptor[hash].hashsize) {
 
54
       return CRYPT_INVALID_HASH;
 
55
    }
 
56
 
 
57
    /* make a random key and export the public copy */
 
58
    if ((err = ecc_make_key(prng, wprng, ecc_get_size(key), &pubkey)) != CRYPT_OK) {
 
59
       return err;
 
60
    }
 
61
 
 
62
    pub_expt   = XMALLOC(ECC_BUF_SIZE);
 
63
    ecc_shared = XMALLOC(ECC_BUF_SIZE);
 
64
    skey       = XMALLOC(MAXBLOCKSIZE);
 
65
    if (pub_expt == NULL || ecc_shared == NULL || skey == NULL) {
 
66
       if (pub_expt != NULL) {
 
67
          XFREE(pub_expt);
 
68
       }
 
69
       if (ecc_shared != NULL) {
 
70
          XFREE(ecc_shared);
 
71
       }
 
72
       if (skey != NULL) {
 
73
          XFREE(skey);
 
74
       }
 
75
       ecc_free(&pubkey);
 
76
       return CRYPT_MEM;
 
77
    }
 
78
 
 
79
    pubkeysize = ECC_BUF_SIZE;
 
80
    if ((err = ecc_export(pub_expt, &pubkeysize, PK_PUBLIC, &pubkey)) != CRYPT_OK) {
 
81
       ecc_free(&pubkey);
 
82
       goto LBL_ERR;
 
83
    }
 
84
    
 
85
    /* make random key */
 
86
    x        = ECC_BUF_SIZE;
 
87
    if ((err = ecc_shared_secret(&pubkey, key, ecc_shared, &x)) != CRYPT_OK) {
 
88
       ecc_free(&pubkey);
 
89
       goto LBL_ERR;
 
90
    }
 
91
    ecc_free(&pubkey);
 
92
    y = MAXBLOCKSIZE;
 
93
    if ((err = hash_memory(hash, ecc_shared, x, skey, &y)) != CRYPT_OK) {
 
94
       goto LBL_ERR;
 
95
    }
 
96
    
 
97
    /* Encrypt key */
 
98
    for (x = 0; x < inlen; x++) {
 
99
      skey[x] ^= in[x];
 
100
    }
 
101
 
 
102
    err = der_encode_sequence_multi(out, outlen,
 
103
                                    LTC_ASN1_OBJECT_IDENTIFIER,  hash_descriptor[hash].OIDlen,   hash_descriptor[hash].OID,
 
104
                                    LTC_ASN1_OCTET_STRING,       pubkeysize,                     pub_expt,
 
105
                                    LTC_ASN1_OCTET_STRING,       inlen,                          skey,
 
106
                                    LTC_ASN1_EOL,                0UL,                            NULL);
 
107
 
 
108
LBL_ERR:
 
109
#ifdef LTC_CLEAN_STACK
 
110
    /* clean up */
 
111
    zeromem(pub_expt,   ECC_BUF_SIZE);
 
112
    zeromem(ecc_shared, ECC_BUF_SIZE);
 
113
    zeromem(skey,       MAXBLOCKSIZE);
 
114
#endif
 
115
 
 
116
    XFREE(skey);
 
117
    XFREE(ecc_shared);
 
118
    XFREE(pub_expt);
 
119
 
 
120
    return err;
 
121
}
 
122
 
 
123
/**
 
124
  Decrypt an ECC encrypted key
 
125
  @param in       The ciphertext
 
126
  @param inlen    The length of the ciphertext (octets)
 
127
  @param out      [out] The plaintext
 
128
  @param outlen   [in/out] The max size and resulting size of the plaintext
 
129
  @param key      The corresponding private ECC key
 
130
  @return CRYPT_OK if successful
 
131
*/
 
132
int ecc_decrypt_key(const unsigned char *in,  unsigned long  inlen,
 
133
                          unsigned char *out, unsigned long *outlen, 
 
134
                          ecc_key *key)
 
135
{
 
136
   unsigned char *ecc_shared, *skey, *pub_expt;
 
137
   unsigned long  x, y, hashOID[32];
 
138
   int            hash, err;
 
139
   ecc_key        pubkey;
 
140
   ltc_asn1_list  decode[3];
 
141
 
 
142
   LTC_ARGCHK(in     != NULL);
 
143
   LTC_ARGCHK(out    != NULL);
 
144
   LTC_ARGCHK(outlen != NULL);
 
145
   LTC_ARGCHK(key    != NULL);
 
146
 
 
147
   /* right key type? */
 
148
   if (key->type != PK_PRIVATE) {
 
149
      return CRYPT_PK_NOT_PRIVATE;
 
150
   }
 
151
   
 
152
   /* decode to find out hash */
 
153
   LTC_SET_ASN1(decode, 0, LTC_ASN1_OBJECT_IDENTIFIER, hashOID, sizeof(hashOID)/sizeof(hashOID[0]));
 
154
 
 
155
   if ((err = der_decode_sequence(in, inlen, decode, 1)) != CRYPT_OK) {
 
156
      return err;
 
157
   }
 
158
   for (hash = 0; hash_descriptor[hash].name   != NULL             && 
 
159
                  (hash_descriptor[hash].OIDlen != decode[0].size   || 
 
160
                   memcmp(hash_descriptor[hash].OID, hashOID, sizeof(unsigned long)*decode[0].size)); hash++);
 
161
 
 
162
   if (hash_descriptor[hash].name == NULL) {
 
163
      return CRYPT_INVALID_PACKET;
 
164
   }
 
165
 
 
166
   /* we now have the hash! */
 
167
 
 
168
   /* allocate memory */
 
169
   pub_expt   = XMALLOC(ECC_BUF_SIZE);
 
170
   ecc_shared = XMALLOC(ECC_BUF_SIZE);
 
171
   skey       = XMALLOC(MAXBLOCKSIZE);
 
172
   if (pub_expt == NULL || ecc_shared == NULL || skey == NULL) {
 
173
      if (pub_expt != NULL) {
 
174
         XFREE(pub_expt);
 
175
      }
 
176
      if (ecc_shared != NULL) {
 
177
         XFREE(ecc_shared);
 
178
      }
 
179
      if (skey != NULL) {
 
180
         XFREE(skey);
 
181
      }
 
182
      return CRYPT_MEM;
 
183
   }
 
184
   LTC_SET_ASN1(decode, 1, LTC_ASN1_OCTET_STRING,      pub_expt,  ECC_BUF_SIZE);
 
185
   LTC_SET_ASN1(decode, 2, LTC_ASN1_OCTET_STRING,      skey,      MAXBLOCKSIZE);
 
186
 
 
187
   /* read the structure in now */
 
188
   if ((err = der_decode_sequence(in, inlen, decode, 3)) != CRYPT_OK) {
 
189
      goto LBL_ERR;
 
190
   }
 
191
 
 
192
   /* import ECC key from packet */
 
193
   if ((err = ecc_import(decode[1].data, decode[1].size, &pubkey)) != CRYPT_OK) {
 
194
      goto LBL_ERR;
 
195
   }
 
196
 
 
197
   /* make shared key */
 
198
   x = ECC_BUF_SIZE;
 
199
   if ((err = ecc_shared_secret(key, &pubkey, ecc_shared, &x)) != CRYPT_OK) {
 
200
      ecc_free(&pubkey);
 
201
      goto LBL_ERR;
 
202
   }
 
203
   ecc_free(&pubkey);
 
204
 
 
205
   y = MAXBLOCKSIZE;
 
206
   if ((err = hash_memory(hash, ecc_shared, x, ecc_shared, &y)) != CRYPT_OK) {
 
207
      goto LBL_ERR;
 
208
   }
 
209
 
 
210
   /* ensure the hash of the shared secret is at least as big as the encrypt itself */
 
211
   if (decode[2].size > y) {
 
212
      err = CRYPT_INVALID_PACKET;
 
213
      goto LBL_ERR;
 
214
   }
 
215
 
 
216
   /* avoid buffer overflow */
 
217
   if (*outlen < decode[2].size) {
 
218
      err = CRYPT_BUFFER_OVERFLOW;
 
219
      goto LBL_ERR;
 
220
   }
 
221
 
 
222
   /* Decrypt the key */
 
223
   for (x = 0; x < decode[2].size; x++) {
 
224
     out[x] = skey[x] ^ ecc_shared[x];
 
225
   }
 
226
   *outlen = x;
 
227
 
 
228
   err = CRYPT_OK;
 
229
LBL_ERR:
 
230
#ifdef LTC_CLEAN_STACK
 
231
   zeromem(pub_expt,   ECC_BUF_SIZE);
 
232
   zeromem(ecc_shared, ECC_BUF_SIZE);
 
233
   zeromem(skey,       MAXBLOCKSIZE);
 
234
#endif
 
235
 
 
236
   XFREE(pub_expt);
 
237
   XFREE(ecc_shared);
 
238
   XFREE(skey);
 
239
 
 
240
   return err;
 
241
}
 
242
 
 
243
/**
 
244
  Sign a message digest
 
245
  @param in        The message digest to sign
 
246
  @param inlen     The length of the digest
 
247
  @param out       [out] The destination for the signature
 
248
  @param outlen    [in/out] The max size and resulting size of the signature
 
249
  @param prng      An active PRNG state
 
250
  @param wprng     The index of the PRNG you wish to use
 
251
  @param key       A private ECC key
 
252
  @return CRYPT_OK if successful
 
253
*/
 
254
int ecc_sign_hash(const unsigned char *in,  unsigned long inlen, 
 
255
                        unsigned char *out, unsigned long *outlen, 
 
256
                        prng_state *prng, int wprng, ecc_key *key)
 
257
{
 
258
   ecc_key       pubkey;
 
259
   mp_int        r, s, e, p;
 
260
   int           err;
 
261
 
 
262
   LTC_ARGCHK(in     != NULL);
 
263
   LTC_ARGCHK(out    != NULL);
 
264
   LTC_ARGCHK(outlen != NULL);
 
265
   LTC_ARGCHK(key    != NULL);
 
266
 
 
267
   /* is this a private key? */
 
268
   if (key->type != PK_PRIVATE) {
 
269
      return CRYPT_PK_NOT_PRIVATE;
 
270
   }
 
271
   
 
272
   /* is the IDX valid ?  */
 
273
   if (is_valid_idx(key->idx) != 1) {
 
274
      return CRYPT_PK_INVALID_TYPE;
 
275
   }
 
276
   
 
277
   if ((err = prng_is_valid(wprng)) != CRYPT_OK) {
 
278
      return err;
 
279
   }
 
280
 
 
281
   /* get the hash and load it as a bignum into 'e' */
 
282
   /* init the bignums */
 
283
   if ((err = mp_init_multi(&r, &s, &p, &e, NULL)) != MP_OKAY) { 
 
284
      ecc_free(&pubkey);
 
285
      err = mpi_to_ltc_error(err);
 
286
      goto LBL_ERR;
 
287
   }
 
288
   if ((err = mp_read_radix(&p, (char *)sets[key->idx].order, 64)) != MP_OKAY)        { goto error; }
 
289
   if ((err = mp_read_unsigned_bin(&e, (unsigned char *)in, (int)inlen)) != MP_OKAY)  { goto error; }
 
290
 
 
291
   /* make up a key and export the public copy */
 
292
   for (;;) {
 
293
      if ((err = ecc_make_key(prng, wprng, ecc_get_size(key), &pubkey)) != CRYPT_OK) {
 
294
         return err;
 
295
      }
 
296
 
 
297
      /* find r = x1 mod n */
 
298
      if ((err = mp_mod(&pubkey.pubkey.x, &p, &r)) != MP_OKAY)                           { goto error; }
 
299
 
 
300
      if (mp_iszero(&r)) {
 
301
         ecc_free(&pubkey);
 
302
      } else { 
 
303
        /* find s = (e + xr)/k */
 
304
        if ((err = mp_invmod(&pubkey.k, &p, &pubkey.k)) != MP_OKAY)            { goto error; } /* k = 1/k */
 
305
        if ((err = mp_mulmod(&key->k, &r, &p, &s)) != MP_OKAY)                 { goto error; } /* s = xr */
 
306
        if ((err = mp_addmod(&e, &s, &p, &s)) != MP_OKAY)                      { goto error; } /* s = e +  xr */
 
307
        if ((err = mp_mulmod(&s, &pubkey.k, &p, &s)) != MP_OKAY)               { goto error; } /* s = (e + xr)/k */
 
308
 
 
309
        if (mp_iszero(&s)) {
 
310
           ecc_free(&pubkey);
 
311
        } else {
 
312
           break;
 
313
        }
 
314
      }
 
315
   }
 
316
 
 
317
   /* store as SEQUENCE { r, s -- integer } */
 
318
   err = der_encode_sequence_multi(out, outlen,
 
319
                             LTC_ASN1_INTEGER, 1UL, &r,
 
320
                             LTC_ASN1_INTEGER, 1UL, &s,
 
321
                             LTC_ASN1_EOL, 0UL, NULL);
 
322
   goto LBL_ERR;
 
323
error:
 
324
   err = mpi_to_ltc_error(err);
 
325
LBL_ERR:
 
326
   mp_clear_multi(&r, &s, &p, &e, NULL);
 
327
   ecc_free(&pubkey);
 
328
 
 
329
   return err;   
 
330
}
 
331
 
 
332
/* verify 
 
333
 *
 
334
 * w  = s^-1 mod n
 
335
 * u1 = xw 
 
336
 * u2 = rw
 
337
 * X = u1*G + u2*Q
 
338
 * v = X_x1 mod n
 
339
 * accept if v == r
 
340
 */
 
341
 
 
342
/**
 
343
   Verify an ECC signature
 
344
   @param sig         The signature to verify
 
345
   @param siglen      The length of the signature (octets)
 
346
   @param hash        The hash (message digest) that was signed
 
347
   @param hashlen     The length of the hash (octets)
 
348
   @param stat        Result of signature, 1==valid, 0==invalid
 
349
   @param key         The corresponding public ECC key
 
350
   @return CRYPT_OK if successful (even if the signature is not valid)
 
351
*/
 
352
int ecc_verify_hash(const unsigned char *sig,  unsigned long siglen,
 
353
                    const unsigned char *hash, unsigned long hashlen, 
 
354
                    int *stat, ecc_key *key)
 
355
{
 
356
   ecc_point    *mG, *mQ;
 
357
   mp_int        r, s, v, w, u1, u2, e, p, m;
 
358
   mp_digit      mp;
 
359
   int           err;
 
360
 
 
361
   LTC_ARGCHK(sig  != NULL);
 
362
   LTC_ARGCHK(hash != NULL);
 
363
   LTC_ARGCHK(stat != NULL);
 
364
   LTC_ARGCHK(key  != NULL);
 
365
 
 
366
   /* default to invalid signature */
 
367
   *stat = 0;
 
368
 
 
369
   /* is the IDX valid ?  */
 
370
   if (is_valid_idx(key->idx) != 1) {
 
371
      return CRYPT_PK_INVALID_TYPE;
 
372
   }
 
373
 
 
374
   /* allocate ints */
 
375
   if ((err = mp_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL)) != MP_OKAY) {
 
376
      return CRYPT_MEM;
 
377
   }
 
378
 
 
379
   /* allocate points */
 
380
   mG = new_point();
 
381
   mQ = new_point();
 
382
   if (mQ  == NULL || mG == NULL) {
 
383
      err = CRYPT_MEM;
 
384
      goto done;
 
385
   }
 
386
 
 
387
   /* parse header */
 
388
   if ((err = der_decode_sequence_multi(sig, siglen,
 
389
                                  LTC_ASN1_INTEGER, 1UL, &r,
 
390
                                  LTC_ASN1_INTEGER, 1UL, &s,
 
391
                                  LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) {
 
392
      goto done;
 
393
   }
 
394
 
 
395
   /* get the order */
 
396
   if ((err = mp_read_radix(&p, (char *)sets[key->idx].order, 64)) != MP_OKAY)                  { goto error; }
 
397
 
 
398
   /* get the modulus */
 
399
   if ((err = mp_read_radix(&m, (char *)sets[key->idx].prime, 64)) != MP_OKAY)                  { goto error; }
 
400
 
 
401
   /* check for zero */
 
402
   if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT || mp_cmp(&s, &p) != MP_LT) {
 
403
      err = CRYPT_INVALID_PACKET;
 
404
      goto done;
 
405
   }
 
406
 
 
407
   /* read hash */
 
408
   if ((err = mp_read_unsigned_bin(&e, (unsigned char *)hash, (int)hashlen)) != MP_OKAY)        { goto error; }
 
409
 
 
410
   /*  w  = s^-1 mod n */
 
411
   if ((err = mp_invmod(&s, &p, &w)) != MP_OKAY)                                                { goto error; }
 
412
 
 
413
   /* u1 = ew */
 
414
   if ((err = mp_mulmod(&e, &w, &p, &u1)) != MP_OKAY)                                           { goto error; }
 
415
 
 
416
   /* u2 = rw */
 
417
   if ((err = mp_mulmod(&r, &w, &p, &u2)) != MP_OKAY)                                           { goto error; }
 
418
 
 
419
   /* find mG = u1*G */
 
420
   if ((err = mp_read_radix(&mG->x, (char *)sets[key->idx].Gx, 64)) != MP_OKAY)                 { goto error; }
 
421
   if ((err = mp_read_radix(&mG->y, (char *)sets[key->idx].Gy, 64)) != MP_OKAY)                 { goto error; }
 
422
   mp_set(&mG->z, 1);  
 
423
   if ((err = ecc_mulmod(&u1, mG, mG, &m, 0)) != CRYPT_OK)                                      { goto done; }
 
424
 
 
425
   /* find mQ = u2*Q */
 
426
   if ((err = mp_copy(&key->pubkey.x, &mQ->x)) != MP_OKAY)                                      { goto error; }
 
427
   if ((err = mp_copy(&key->pubkey.y, &mQ->y)) != MP_OKAY)                                      { goto error; }
 
428
   if ((err = mp_copy(&key->pubkey.z, &mQ->z)) != MP_OKAY)                                      { goto error; }
 
429
   if ((err = ecc_mulmod(&u2, mQ, mQ, &m, 0)) != CRYPT_OK)                                      { goto done; }
 
430
  
 
431
   /* find the montgomery mp */
 
432
   if ((err = mp_montgomery_setup(&m, &mp)) != MP_OKAY)                                         { goto error; }
 
433
   /* add them */
 
434
   if ((err = add_point(mQ, mG, mG, &m, mp)) != CRYPT_OK)                                       { goto done; }
 
435
   
 
436
   /* reduce */
 
437
   if ((err = ecc_map(mG, &m, mp)) != CRYPT_OK)                                                 { goto done; }
 
438
 
 
439
   /* v = X_x1 mod n */
 
440
   if ((err = mp_mod(&mG->x, &p, &v)) != CRYPT_OK)                                              { goto done; }
 
441
 
 
442
   /* does v == r */
 
443
   if (mp_cmp(&v, &r) == MP_EQ) {
 
444
      *stat = 1;
 
445
   }
 
446
 
 
447
   /* clear up and return */
 
448
   err = CRYPT_OK;
 
449
   goto done;
 
450
error:
 
451
   err = mpi_to_ltc_error(err);
 
452
done:
 
453
   del_point(mG);
 
454
   del_point(mQ);
 
455
   mp_clear_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, NULL);
 
456
   return err;
 
457
}
 
458
 
 
459
 
 
460
/* $Source: /cvs/libtom/libtomcrypt/src/pk/ecc/ecc_sys.c,v $ */
 
461
/* $Revision: 1.18 $ */
 
462
/* $Date: 2005/06/14 20:47:55 $ */