openssh/schnorr.c

   1 /* $OpenBSD: schnorr.c,v 1.2 2009/02/18 04:31:21 djm Exp $ */
   2 /*
   3  * Copyright (c) 2008 Damien Miller.  All rights reserved.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /*
  19  * Implementation of Schnorr signatures / zero-knowledge proofs, based on
  20  * description in:
  21  *
  22  * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling",
  23  * 16th Workshop on Security Protocols, Cambridge, April 2008
  24  *
  25  * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
  26  */
  27
  28 #include "includes.h"
  29
  30 #include <sys/types.h>
  31
  32 #include <string.h>
  33 #include <stdarg.h>
  34 #include <stdio.h>
  35
  36 #include <openssl/evp.h>
  37 #include <openssl/bn.h>
  38
  39 #include "xmalloc.h"
  40 #include "buffer.h"
  41 #include "log.h"
  42
  43 #include "jpake.h"
  44
  45 /* #define SCHNORR_DEBUG */             /* Privacy-violating debugging */
  46 /* #define SCHNORR_MAIN */              /* Include main() selftest */
  47
  48 /* XXX */
  49 /* Parametise signature hash? (sha256, sha1, etc.) */
  50 /* Signature format - include type name, hash type, group params? */
  51
  52 #ifndef SCHNORR_DEBUG
  53 # define SCHNORR_DEBUG_BN(a)
  54 # define SCHNORR_DEBUG_BUF(a)
  55 #else
  56 # define SCHNORR_DEBUG_BN(a)    jpake_debug3_bn a
  57 # define SCHNORR_DEBUG_BUF(a)   jpake_debug3_buf a
  58 #endif /* SCHNORR_DEBUG */
  59
  60 /*
  61  * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
  62  * using SHA1. Returns signature as bignum or NULL on error.
  63  */
  64 static BIGNUM *
  65 schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
  66     const BIGNUM *g_v, const BIGNUM *g_x,
  67     const u_char *id, u_int idlen)
  68 {
  69         u_char *digest;
  70         u_int digest_len;
  71         BIGNUM *h;
  72         EVP_MD_CTX evp_md_ctx;
  73         Buffer b;
  74         int success = -1;
  75
  76         if ((h = BN_new()) == NULL) {
  77                 error("%s: BN_new", __func__);
  78                 return NULL;
  79         }
  80
  81         buffer_init(&b);
  82         EVP_MD_CTX_init(&evp_md_ctx);
  83
  84         /* h = H(g || p || q || g^v || g^x || id) */
  85         buffer_put_bignum2(&b, g);
  86         buffer_put_bignum2(&b, p);
  87         buffer_put_bignum2(&b, q);
  88         buffer_put_bignum2(&b, g_v);
  89         buffer_put_bignum2(&b, g_x);
  90         buffer_put_string(&b, id, idlen);
  91
  92         SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
  93             "%s: hashblob", __func__));
  94         if (hash_buffer(buffer_ptr(&b), buffer_len(&b), (const EVP_MD *)EVP_sha256(),
  95             &digest, &digest_len) != 0) {
  96                 error("%s: hash_buffer", __func__);
  97                 goto out;
  98         }
  99         if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
 100                 error("%s: BN_bin2bn", __func__);
 101                 goto out;
 102         }
 103         success = 0;
 104         SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
 105  out:
 106         buffer_free(&b);
 107         EVP_MD_CTX_cleanup(&evp_md_ctx);
 108         bzero(digest, digest_len);
 109         xfree(digest);
 110         digest_len = 0;
 111         if (success == 0)
 112                 return h;
 113         BN_clear_free(h);
 114         return NULL;
 115 }
 116
 117 /*
 118  * Generate Schnorr signature to prove knowledge of private value 'x' used
 119  * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
 120  * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
 121  * replay salt.
 122  * On success, 0 is returned and *siglen bytes of signature are returned in
 123  * *sig (caller to free). Returns -1 on failure.
 124  */
 125 int
 126 schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
 127     const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
 128     u_char **sig, u_int *siglen)
 129 {
 130         int success = -1;
 131         Buffer b;
 132         BIGNUM *h, *tmp, *v, *g_v, *r;
 133         BN_CTX *bn_ctx;
 134
 135         SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
 136         SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
 137
 138         /* Avoid degenerate cases: g^0 yields a spoofable signature */
 139         if (BN_cmp(g_x, BN_value_one()) <= 0) {
 140                 error("%s: g_x < 1", __func__);
 141                 return -1;
 142         }
 143
 144         h = g_v = r = tmp = v = NULL;
 145         if ((bn_ctx = BN_CTX_new()) == NULL) {
 146                 error("%s: BN_CTX_new", __func__);
 147                 goto out;
 148         }
 149         if ((g_v = BN_new()) == NULL ||
 150             (r = BN_new()) == NULL ||
 151             (tmp = BN_new()) == NULL) {
 152                 error("%s: BN_new", __func__);
 153                 goto out;
 154         }
 155
 156         /*
 157          * v must be a random element of Zq, so 1 <= v < q
 158          * we also exclude v = 1, since g^1 looks dangerous
 159          */
 160         if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
 161                 error("%s: bn_rand_range2", __func__);
 162                 goto out;
 163         }
 164         SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));
 165
 166         /* g_v = g^v mod p */
 167         if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
 168                 error("%s: BN_mod_exp (g^v mod p)", __func__);
 169                 goto out;
 170         }
 171         SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
 172
 173         /* h = H(g || g^v || g^x || id) */
 174         if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
 175             id, idlen)) == NULL) {
 176                 error("%s: schnorr_hash failed", __func__);
 177                 goto out;
 178         }
 179
 180         /* r = v - xh mod q */
 181         if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
 182                 error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
 183                 goto out;
 184         }
 185         if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
 186                 error("%s: BN_mod_mul (r = v - tmp)", __func__);
 187                 goto out;
 188         }
 189         SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
 190
 191         /* Signature is (g_v, r) */
 192         buffer_init(&b);
 193         /* XXX sigtype-hash as string? */
 194         buffer_put_bignum2(&b, g_v);
 195         buffer_put_bignum2(&b, r);
 196         *siglen = buffer_len(&b);
 197         *sig = xmalloc(*siglen);
 198         memcpy(*sig, buffer_ptr(&b), *siglen);
 199         SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
 200             "%s: sigblob", __func__));
 201         buffer_free(&b);
 202         success = 0;
 203  out:
 204         BN_CTX_free(bn_ctx);
 205         if (h != NULL)
 206                 BN_clear_free(h);
 207         if (v != NULL)
 208                 BN_clear_free(v);
 209         BN_clear_free(r);
 210         BN_clear_free(g_v);
 211         BN_clear_free(tmp);
 212
 213         return success;
 214 }
 215
 216 /*
 217  * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
 218  * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'.
 219  * Signature hash will be salted with 'idlen' bytes from 'id'.
 220  * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
 221  */
 222 int
 223 schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
 224     const BIGNUM *g_x, const u_char *id, u_int idlen,
 225     const u_char *sig, u_int siglen)
 226 {
 227         int success = -1;
 228         Buffer b;
 229         BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected;
 230         BN_CTX *bn_ctx;
 231         u_int rlen;
 232
 233         SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
 234
 235         /* Avoid degenerate cases: g^0 yields a spoofable signature */
 236         if (BN_cmp(g_x, BN_value_one()) <= 0) {
 237                 error("%s: g_x < 1", __func__);
 238                 return -1;
 239         }
 240
 241         g_v = h = r = g_xh = g_r = expected = NULL;
 242         if ((bn_ctx = BN_CTX_new()) == NULL) {
 243                 error("%s: BN_CTX_new", __func__);
 244                 goto out;
 245         }
 246         if ((g_v = BN_new()) == NULL ||
 247             (r = BN_new()) == NULL ||
 248             (g_xh = BN_new()) == NULL ||
 249             (g_r = BN_new()) == NULL ||
 250             (expected = BN_new()) == NULL) {
 251                 error("%s: BN_new", __func__);
 252                 goto out;
 253         }
 254
 255         /* Extract g^v and r from signature blob */
 256         buffer_init(&b);
 257         buffer_append(&b, sig, siglen);
 258         SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
 259             "%s: sigblob", __func__));
 260         buffer_get_bignum2(&b, g_v);
 261         buffer_get_bignum2(&b, r);
 262         rlen = buffer_len(&b);
 263         buffer_free(&b);
 264         if (rlen != 0) {
 265                 error("%s: remaining bytes in signature %d", __func__, rlen);
 266                 goto out;
 267         }
 268         buffer_free(&b);
 269         SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
 270         SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
 271
 272         /* h = H(g || g^v || g^x || id) */
 273         if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
 274             id, idlen)) == NULL) {
 275                 error("%s: schnorr_hash failed", __func__);
 276                 goto out;
 277         }
 278
 279         /* g_xh = (g^x)^h */
 280         if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
 281                 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
 282                 goto out;
 283         }
 284         SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
 285
 286         /* g_r = g^r */
 287         if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) {
 288                 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
 289                 goto out;
 290         }
 291         SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));
 292
 293         /* expected = g^r * g_xh */
 294         if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
 295                 error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
 296                 goto out;
 297         }
 298         SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
 299
 300         /* Check g_v == expected */
 301         success = BN_cmp(expected, g_v) == 0;
 302  out:
 303         BN_CTX_free(bn_ctx);
 304         if (h != NULL)
 305                 BN_clear_free(h);
 306         BN_clear_free(g_v);
 307         BN_clear_free(r);
 308         BN_clear_free(g_xh);
 309         BN_clear_free(g_r);
 310         BN_clear_free(expected);
 311         return success;
 312 }
 313
 314 #ifdef SCHNORR_MAIN
 315 static void
 316 schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
 317     const BIGNUM *grp_g, const BIGNUM *x)
 318 {
 319         BIGNUM *g_x;
 320         u_char *sig;
 321         u_int siglen;
 322         BN_CTX *bn_ctx;
 323
 324         if ((bn_ctx = BN_CTX_new()) == NULL)
 325                 fatal("%s: BN_CTX_new", __func__);
 326         if ((g_x = BN_new()) == NULL)
 327                 fatal("%s: BN_new", __func__);
 328
 329         if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
 330                 fatal("%s: g_x", __func__);
 331         if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen))
 332                 fatal("%s: schnorr_sign", __func__);
 333         if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
 334             sig, siglen) != 1)
 335                 fatal("%s: verify fail", __func__);
 336         if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
 337             sig, siglen) != 0)
 338                 fatal("%s: verify should have failed (bad ID)", __func__);
 339         sig[4] ^= 1;
 340         if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
 341             sig, siglen) != 0)
 342                 fatal("%s: verify should have failed (bit error)", __func__);
 343         xfree(sig);
 344         BN_free(g_x);
 345         BN_CTX_free(bn_ctx);
 346 }
 347
 348 static void
 349 schnorr_selftest(void)
 350 {
 351         BIGNUM *x;
 352         struct jpake_group *grp;
 353         u_int i;
 354         char *hh;
 355
 356         grp = jpake_default_group();
 357         if ((x = BN_new()) == NULL)
 358                 fatal("%s: BN_new", __func__);
 359         SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
 360         SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
 361         SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));
 362
 363         /* [1, 20) */
 364         for (i = 1; i < 20; i++) {
 365                 printf("x = %u\n", i);
 366                 fflush(stdout);
 367                 if (BN_set_word(x, i) != 1)
 368                         fatal("%s: set x word", __func__);
 369                 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
 370         }
 371
 372         /* 100 x random [0, p) */
 373         for (i = 0; i < 100; i++) {
 374                 if (BN_rand_range(x, grp->p) != 1)
 375                         fatal("%s: BN_rand_range", __func__);
 376                 hh = BN_bn2hex(x);
 377                 printf("x = (random) 0x%s\n", hh);
 378                 free(hh);
 379                 fflush(stdout);
 380                 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
 381         }
 382
 383         /* [q-20, q) */
 384         if (BN_set_word(x, 20) != 1)
 385                 fatal("%s: BN_set_word (x = 20)", __func__);
 386         if (BN_sub(x, grp->q, x) != 1)
 387                 fatal("%s: BN_sub (q - x)", __func__);
 388         for (i = 0; i < 19; i++) {
 389                 hh = BN_bn2hex(x);
 390                 printf("x = (q - %d) 0x%s\n", 20 - i, hh);
 391                 free(hh);
 392                 fflush(stdout);
 393                 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
 394                 if (BN_add(x, x, BN_value_one()) != 1)
 395                         fatal("%s: BN_add (x + 1)", __func__);
 396         }
 397         BN_free(x);
 398 }
 399
 400 int
 401 main(int argc, char **argv)
 402 {
 403         log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);
 404
 405         schnorr_selftest();
 406         return 0;
 407 }
 408 #endif
 409