math_group.c

   1 /* borrowed from isakmpd-20030718 (-; */
   2
   3 /*      $OpenBSD: math_group.c,v 1.18 2003/06/03 14:28:16 ho Exp $      */
   4 /*      $EOM: math_group.c,v 1.25 2000/04/07 19:53:26 niklas Exp $      */
   5
   6 /*
   7  * Copyright (c) 1998 Niels Provos.  All rights reserved.
   8  * Copyright (c) 1999, 2000 Niklas Hallqvist.  All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 /*
  32  * This code was written under funding by Ericsson Radio Systems.
  33  */
  34
  35 #include <assert.h>
  36 #include <sys/param.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39 #include <netinet/in.h>
  40
  41 #include <gcrypt.h>
  42
  43 #include "math_group.h"
  44
  45 /* We do not want to export these definitions.  */
  46 static void modp_free(struct group *);
  47 static struct group *modp_clone(struct group *, struct group *);
  48 static void modp_init(struct group *);
  49
  50 static int modp_getlen(struct group *);
  51 static void modp_getraw(struct group *, gcry_mpi_t, unsigned char *);
  52 static int modp_setraw(struct group *, gcry_mpi_t, unsigned char *, int);
  53 static int modp_setrandom(struct group *, gcry_mpi_t);
  54 static int modp_operation(struct group *, gcry_mpi_t, gcry_mpi_t, gcry_mpi_t);
  55
  56 /*
  57  * This module provides access to the operations on the specified group
  58  * and is absolutly free of any cryptographic devices. This is math :-).
  59  */
  60
  61 /* Describe preconfigured MODP groups */
  62
  63 /*
  64  * The Generalized Number Field Sieve has an asymptotic running time
  65  * of: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))), where q is the
  66  * group order, e.g. q = 2**768.
  67  */
  68
  69 static const struct modp_dscr oakley_modp[] = {
  70         {
  71                 OAKLEY_GRP_1, 72, /* This group is insecure, only sufficient for DES */
  72                 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  73                 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  74                 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  75                 "E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF",
  76                 "2"
  77         },
  78         {
  79                 OAKLEY_GRP_2, 82, /* This group is a bit better */
  80                 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  81                 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  82                 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  83                 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
  84                 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
  85                 "FFFFFFFFFFFFFFFF",
  86                 "2"
  87         },
  88         {
  89                 OAKLEY_GRP_5, 102, /* This group is yet a bit better, but non-standard */
  90                 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
  91                 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
  92                 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
  93                 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
  94                 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
  95                 "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
  96                 "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
  97                 "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF",
  98                 "2"
  99         },
 100 };
 101
 102 /* XXX I want to get rid of the casting here.  */
 103 static struct group groups[] = {
 104         {
 105                 MODP, OAKLEY_GRP_1, 0, NULL, &oakley_modp[0], NULL, NULL, NULL, NULL, NULL,
 106                 (int (*)(struct group *))modp_getlen,
 107                 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
 108                 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
 109                 (int (*)(struct group *, void *))modp_setrandom,
 110                 (int (*)(struct group *, void *, void *, void *))modp_operation
 111         },
 112         {
 113                 MODP, OAKLEY_GRP_2, 0, NULL, &oakley_modp[1], NULL, NULL, NULL, NULL, NULL,
 114                 (int (*)(struct group *))modp_getlen,
 115                 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
 116                 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
 117                 (int (*)(struct group *, void *))modp_setrandom,
 118                 (int (*)(struct group *, void *, void *, void *))modp_operation
 119         },
 120         {
 121                 MODP, OAKLEY_GRP_5, 0, NULL, &oakley_modp[2], NULL, NULL, NULL, NULL, NULL,
 122                 (int (*)(struct group *))modp_getlen,
 123                 (void (*)(struct group *, void *, unsigned char *))modp_getraw,
 124                 (int (*)(struct group *, void *, unsigned char *, int))modp_setraw,
 125                 (int (*)(struct group *, void *))modp_setrandom,
 126                 (int (*)(struct group *, void *, void *, void *))modp_operation
 127         },
 128 };
 129
 130 /*
 131  * Initialize the group structure for later use,
 132  * this is done by converting the values given in the describtion
 133  * and converting them to their native representation.
 134  */
 135 void group_init(void)
 136 {
 137         int i;
 138
 139         for (i = sizeof(groups) / sizeof(groups[0]) - 1; i >= 0; i--) {
 140                 assert(groups[i].type == MODP);
 141                 modp_init(&groups[i]); /* Initialize an over GF(p) */
 142         }
 143 }
 144
 145 struct group *group_get(int id)
 146 {
 147         struct group *new, *clone;
 148
 149         assert(id >= 1);
 150         assert(id <= (int)(sizeof(groups) / sizeof(groups[0])));
 151
 152         clone = &groups[id - 1];
 153
 154         new = malloc(sizeof *new);
 155         assert(new);
 156
 157         assert(clone->type == MODP);
 158         new = modp_clone(new, clone);
 159         return new;
 160 }
 161
 162 void group_free(struct group *grp)
 163 {
 164         assert(grp->type == MODP);
 165         modp_free(grp);
 166         free(grp);
 167 }
 168
 169 static struct group *modp_clone(struct group *new, struct group *clone)
 170 {
 171         struct modp_group *new_grp, *clone_grp = clone->group;
 172
 173         new_grp = malloc(sizeof *new_grp);
 174         assert(new_grp);
 175
 176         memcpy(new, clone, sizeof(struct group));
 177
 178         new->group = new_grp;
 179         new_grp->p = gcry_mpi_copy(clone_grp->p);
 180         new_grp->gen = gcry_mpi_copy(clone_grp->gen);
 181
 182         new_grp->a = gcry_mpi_new(clone->bits);
 183         new_grp->b = gcry_mpi_new(clone->bits);
 184         new_grp->c = gcry_mpi_new(clone->bits);
 185
 186         new->gen = new_grp->gen;
 187         new->a = new_grp->a;
 188         new->b = new_grp->b;
 189         new->c = new_grp->c;
 190
 191         return new;
 192 }
 193
 194 static void modp_free(struct group *old)
 195 {
 196         struct modp_group *grp = old->group;
 197
 198         gcry_mpi_release(grp->p);
 199         gcry_mpi_release(grp->gen);
 200         gcry_mpi_release(grp->a);
 201         gcry_mpi_release(grp->b);
 202         gcry_mpi_release(grp->c);
 203
 204         free(grp);
 205 }
 206
 207 static void modp_init(struct group *group)
 208 {
 209         const struct modp_dscr *dscr = group->group_dscr;
 210         struct modp_group *grp;
 211
 212         grp = malloc(sizeof *grp);
 213         assert(grp);
 214
 215         group->bits = dscr->bits;
 216
 217         gcry_mpi_scan(&grp->p, GCRYMPI_FMT_HEX, (const unsigned char*)dscr->prime, 0, NULL);
 218         gcry_mpi_scan(&grp->gen, GCRYMPI_FMT_HEX, (const unsigned char *)dscr->gen, 0, NULL);
 219
 220         grp->a = gcry_mpi_new(group->bits);
 221         grp->b = gcry_mpi_new(group->bits);
 222         grp->c = gcry_mpi_new(group->bits);
 223
 224         group->gen = grp->gen;
 225         group->a = grp->a;
 226         group->b = grp->b;
 227         group->c = grp->c;
 228
 229         group->group = grp;
 230 }
 231
 232 static int modp_getlen(struct group *group)
 233 {
 234         struct modp_group *grp = (struct modp_group *)group->group;
 235
 236         return (gcry_mpi_get_nbits(grp->p) + 7) / 8;
 237 }
 238
 239 static void modp_getraw(struct group *grp, gcry_mpi_t v, unsigned char *d)
 240 {
 241         size_t l, l2;
 242         unsigned char *tmp;
 243         int ret;
 244
 245         l = grp->getlen(grp);
 246         ret = gcry_mpi_aprint(GCRYMPI_FMT_STD, &tmp, &l2, v);
 247         memcpy(d, tmp + (l2 - l), l);
 248         gcry_free(tmp);
 249 #if 0
 250         {
 251                 char *p;
 252                 gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, v);
 253                 printf("export %d - %d(%d):\n%s\n", l, l2, ret, p);
 254                 gcry_free(p);
 255         }
 256 #endif
 257 }
 258
 259 static int modp_setraw(struct group *grp, gcry_mpi_t d, unsigned char *s, int l)
 260 {
 261         int i;
 262
 263         grp = NULL; /* unused */
 264
 265         gcry_mpi_set_ui(d, 0);
 266         for (i = 0; i < l; i++) {
 267                 gcry_mpi_mul_2exp(d, d, 8);
 268                 gcry_mpi_add_ui(d, d, s[i]);
 269         }
 270 #if 0
 271         {
 272                 char *p;
 273                 gcry_mpi_aprint(GCRYMPI_FMT_HEX, (void **)&p, NULL, d);
 274                 printf("import %d:\n%s\n", l, p);
 275                 gcry_free(p);
 276         }
 277 #endif
 278         return 0;
 279 }
 280
 281 static int modp_setrandom(struct group *grp, gcry_mpi_t d)
 282 {
 283         int i, l = grp->getlen(grp);
 284         uint32_t tmp = 0;
 285
 286         gcry_mpi_set_ui(d, 0);
 287
 288         for (i = 0; i < l; i++) {
 289                 if (i % 4)
 290                         gcry_randomize((unsigned char *)&tmp, sizeof(tmp), GCRY_STRONG_RANDOM);
 291
 292                 gcry_mpi_mul_2exp(d, d, 8);
 293                 gcry_mpi_add_ui(d, d, tmp & 0xFF);
 294                 tmp >>= 8;
 295         }
 296         return 0;
 297 }
 298
 299 static int modp_operation(struct group *group, gcry_mpi_t d, gcry_mpi_t a, gcry_mpi_t e)
 300 {
 301         struct modp_group *grp = (struct modp_group *)group->group;
 302
 303         gcry_mpi_powm(d, a, e, grp->p);
 304         return 0;
 305 }