library/dhm.c

   1 /*
   2  *      Diffie-Hellman-Merkle key exchange
   3  *
   4  *      Based on XySSL: Copyright (C) 2006-2008  Christophe Devine
   5  *
   6  *      Copyright (C) 2009      Paul Bakker <polarssl_maintainer at polarssl dot org>
   7  *
   8  *      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  *
  14  *        * Redistributions of source code must retain the above copyright
  15  *              notice, this list of conditions and the following disclaimer.
  16  *        * Redistributions in binary form must reproduce the above copyright
  17  *              notice, this list of conditions and the following disclaimer in the
  18  *              documentation and/or other materials provided with the distribution.
  19  *        * Neither the names of PolarSSL or XySSL nor the names of its contributors
  20  *              may be used to endorse or promote products derived from this software
  21  *              without specific prior written permission.
  22  *
  23  *      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  *      "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  *      LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26  *      FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  *      OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  *      SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  *      TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  *      PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  *      LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  *      NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  *      SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35 /*
  36  *      Reference:
  37  *
  38  *      http://www.cacr.math.uwaterloo.ca/hac/ (chapter 12)
  39  */
  40
  41 #include "tropicssl/config.h"
  42
  43 #if defined(TROPICSSL_DHM_C)
  44
  45 #include "tropicssl/dhm.h"
  46
  47 #include <string.h>
  48
  49 /*
  50  * helper to validate the mpi size and import it
  51  */
  52 static int dhm_read_bignum(mpi * X, unsigned char **p, const unsigned char *end)
  53 {
  54         int ret, n;
  55
  56         if (end - *p < 2)
  57                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
  58
  59         n = ((*p)[0] << 8) | (*p)[1];
  60         (*p) += 2;
  61
  62         if ((int)(end - *p) < n)
  63                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
  64
  65         if ((ret = mpi_read_binary(X, *p, n)) != 0)
  66                 return (TROPICSSL_ERR_DHM_READ_PARAMS_FAILED | ret);
  67
  68         (*p) += n;
  69
  70         return (0);
  71 }
  72
  73 /*
  74  * Parse the ServerKeyExchange parameters
  75  */
  76 int dhm_read_params(dhm_context * ctx, unsigned char **p, const unsigned char *end)
  77 {
  78         int ret, n;
  79
  80         memset(ctx, 0, sizeof(dhm_context));
  81
  82         if ((ret = dhm_read_bignum(&ctx->P, p, end)) != 0 ||
  83             (ret = dhm_read_bignum(&ctx->G, p, end)) != 0 ||
  84             (ret = dhm_read_bignum(&ctx->GY, p, end)) != 0)
  85                 return (ret);
  86
  87         ctx->len = mpi_size(&ctx->P);
  88
  89         if (end - *p < 2)
  90                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
  91
  92         n = ((*p)[0] << 8) | (*p)[1];
  93         (*p) += 2;
  94
  95         if (end != *p + n)
  96                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
  97
  98         return (0);
  99 }
 100
 101 /*
 102  * Setup and write the ServerKeyExchange parameters
 103  */
 104 int dhm_make_params(dhm_context * ctx, int x_size,
 105                     unsigned char *output, int *olen,
 106                     int (*f_rng) (void *), void *p_rng)
 107 {
 108         int i, ret, n, n1, n2, n3;
 109         unsigned char *p;
 110
 111         /*
 112          * generate X and calculate GX = G^X mod P
 113          */
 114         n = x_size / sizeof(t_int);
 115         MPI_CHK(mpi_grow(&ctx->X, n));
 116         MPI_CHK(mpi_lset(&ctx->X, 0));
 117
 118         n = x_size >> 3;
 119         p = (unsigned char *)ctx->X.p;
 120         for (i = 0; i < n; i++)
 121                 *p++ = (unsigned char)f_rng(p_rng);
 122
 123         while (mpi_cmp_mpi(&ctx->X, &ctx->P) >= 0)
 124                 mpi_shift_r(&ctx->X, 1);
 125
 126         MPI_CHK(mpi_exp_mod(&ctx->GX, &ctx->G, &ctx->X, &ctx->P, &ctx->RP));
 127
 128         /*
 129          * export P, G, GX
 130          */
 131 #define DHM_MPI_EXPORT(X,n)                                             \
 132         MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \
 133         *p++ = (unsigned char)( n >> 8 );                       \
 134         *p++ = (unsigned char)( n          ); p += n;
 135
 136         n1 = mpi_size(&ctx->P);
 137         n2 = mpi_size(&ctx->G);
 138         n3 = mpi_size(&ctx->GX);
 139
 140         p = output;
 141         DHM_MPI_EXPORT(&ctx->P, n1);
 142         DHM_MPI_EXPORT(&ctx->G, n2);
 143         DHM_MPI_EXPORT(&ctx->GX, n3);
 144
 145         *olen = p - output;
 146
 147         ctx->len = n1;
 148
 149 cleanup:
 150
 151         if (ret != 0)
 152                 return (ret | TROPICSSL_ERR_DHM_MAKE_PARAMS_FAILED);
 153
 154         return (0);
 155 }
 156
 157 /*
 158  * Import the peer's public value G^Y
 159  */
 160 int dhm_read_public(dhm_context * ctx, const unsigned char *input, int ilen)
 161 {
 162         int ret;
 163
 164         if (ctx == NULL || ilen < 1 || ilen > ctx->len)
 165                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
 166
 167         if ((ret = mpi_read_binary(&ctx->GY, input, ilen)) != 0)
 168                 return (TROPICSSL_ERR_DHM_READ_PUBLIC_FAILED | ret);
 169
 170         return (0);
 171 }
 172
 173 /*
 174  * Create own private value X and export G^X
 175  */
 176 int dhm_make_public(dhm_context * ctx, int x_size,
 177                     unsigned char *output, int olen,
 178                     int (*f_rng) (void *), void *p_rng)
 179 {
 180         int ret, i, n;
 181         unsigned char *p;
 182
 183         if (ctx == NULL || olen < 1 || olen > ctx->len)
 184                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
 185
 186         /*
 187          * generate X and calculate GX = G^X mod P
 188          */
 189         n = x_size / sizeof(t_int);
 190         MPI_CHK(mpi_grow(&ctx->X, n));
 191         MPI_CHK(mpi_lset(&ctx->X, 0));
 192
 193         n = x_size >> 3;
 194         p = (unsigned char *)ctx->X.p;
 195         for (i = 0; i < n; i++)
 196                 *p++ = (unsigned char)f_rng(p_rng);
 197
 198         while (mpi_cmp_mpi(&ctx->X, &ctx->P) >= 0)
 199                 mpi_shift_r(&ctx->X, 1);
 200
 201         MPI_CHK(mpi_exp_mod(&ctx->GX, &ctx->G, &ctx->X, &ctx->P, &ctx->RP));
 202
 203         MPI_CHK(mpi_write_binary(&ctx->GX, output, olen));
 204
 205 cleanup:
 206
 207         if (ret != 0)
 208                 return (TROPICSSL_ERR_DHM_MAKE_PUBLIC_FAILED | ret);
 209
 210         return (0);
 211 }
 212
 213 /*
 214  * Derive and export the shared secret (G^Y)^X mod P
 215  */
 216 int dhm_calc_secret(dhm_context * ctx, unsigned char *output, int *olen)
 217 {
 218         int ret;
 219
 220         if (ctx == NULL || *olen < ctx->len)
 221                 return (TROPICSSL_ERR_DHM_BAD_INPUT_DATA);
 222
 223         MPI_CHK(mpi_exp_mod(&ctx->K, &ctx->GY, &ctx->X, &ctx->P, &ctx->RP));
 224
 225         *olen = mpi_size(&ctx->K);
 226
 227         MPI_CHK(mpi_write_binary(&ctx->K, output, *olen));
 228
 229 cleanup:
 230
 231         if (ret != 0)
 232                 return (TROPICSSL_ERR_DHM_CALC_SECRET_FAILED | ret);
 233
 234         return (0);
 235 }
 236
 237 /*
 238  * Free the components of a DHM key
 239  */
 240 void dhm_free(dhm_context * ctx)
 241 {
 242         mpi_free(&ctx->RP, &ctx->K, &ctx->GY,
 243                  &ctx->GX, &ctx->X, &ctx->G, &ctx->P, NULL);
 244 }
 245
 246 #if defined(TROPICSSL_SELF_TEST)
 247
 248 /*
 249  * Checkup routine
 250  */
 251 int dhm_self_test(int verbose)
 252 {
 253         return (verbose++);
 254 }
 255
 256 #endif
 257
 258 #endif