crypto/openssh/schnorr.c

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