Annotation of src/usr.bin/ssh/schnorr.c, Revision 1.1
1.1 ! djm 1: /* $OpenBSD$ */
! 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 <sys/types.h>
! 29:
! 30: #include <string.h>
! 31: #include <stdarg.h>
! 32: #include <stdio.h>
! 33:
! 34: #include <openssl/evp.h>
! 35: #include <openssl/bn.h>
! 36:
! 37: #include "xmalloc.h"
! 38: #include "buffer.h"
! 39: #include "log.h"
! 40:
! 41: #include "jpake.h"
! 42:
! 43: /* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */
! 44: /* #define SCHNORR_MAIN */ /* Include main() selftest */
! 45:
! 46: /* XXX */
! 47: /* Parametise signature hash? (sha256, sha1, etc.) */
! 48: /* Signature format - include type name, hash type, group params? */
! 49:
! 50: #ifndef SCHNORR_DEBUG
! 51: # define SCHNORR_DEBUG_BN(a)
! 52: # define SCHNORR_DEBUG_BUF(a)
! 53: #else
! 54: # define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a
! 55: # define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a
! 56: #endif /* SCHNORR_DEBUG */
! 57:
! 58: /*
! 59: * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
! 60: * using SHA1. Returns signature as bignum or NULL on error.
! 61: */
! 62: static BIGNUM *
! 63: schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
! 64: const BIGNUM *g_v, const BIGNUM *g_x,
! 65: const u_char *id, u_int idlen)
! 66: {
! 67: u_char *digest;
! 68: u_int digest_len;
! 69: BIGNUM *h;
! 70: EVP_MD_CTX evp_md_ctx;
! 71: Buffer b;
! 72: int success = -1;
! 73:
! 74: if ((h = BN_new()) == NULL) {
! 75: error("%s: BN_new", __func__);
! 76: return NULL;
! 77: }
! 78:
! 79: buffer_init(&b);
! 80: EVP_MD_CTX_init(&evp_md_ctx);
! 81:
! 82: /* h = H(g || g^v || g^x || id) */
! 83: buffer_put_bignum2(&b, g);
! 84: buffer_put_bignum2(&b, g_v);
! 85: buffer_put_bignum2(&b, g_x);
! 86: buffer_put_string(&b, id, idlen);
! 87:
! 88: SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
! 89: "%s: hashblob", __func__));
! 90: if (hash_buffer(buffer_ptr(&b), buffer_len(&b), EVP_sha256(),
! 91: &digest, &digest_len) != 0) {
! 92: error("%s: hash_buffer", __func__);
! 93: goto out;
! 94: }
! 95: if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
! 96: error("%s: BN_bin2bn", __func__);
! 97: goto out;
! 98: }
! 99: success = 0;
! 100: SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
! 101: out:
! 102: buffer_free(&b);
! 103: EVP_MD_CTX_cleanup(&evp_md_ctx);
! 104: bzero(digest, digest_len);
! 105: xfree(digest);
! 106: digest_len = 0;
! 107: if (success == 0)
! 108: return h;
! 109: BN_clear_free(h);
! 110: return NULL;
! 111: }
! 112:
! 113: /*
! 114: * Generate Schnorr signature to prove knowledge of private value 'x' used
! 115: * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
! 116: * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
! 117: * replay salt.
! 118: * On success, 0 is returned and *siglen bytes of signature are returned in
! 119: * *sig (caller to free). Returns -1 on failure.
! 120: */
! 121: int
! 122: schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
! 123: const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
! 124: u_char **sig, u_int *siglen)
! 125: {
! 126: int success = -1;
! 127: Buffer b;
! 128: BIGNUM *h, *tmp, *v, *g_v, *r;
! 129: BN_CTX *bn_ctx;
! 130:
! 131: SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
! 132: SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
! 133:
! 134: /* Avoid degenerate cases: g^0 yields a spoofable signature */
! 135: if (BN_cmp(g_x, BN_value_one()) <= 0) {
! 136: error("%s: g_x < 1", __func__);
! 137: return -1;
! 138: }
! 139:
! 140: h = g_v = r = tmp = v = NULL;
! 141: if ((bn_ctx = BN_CTX_new()) == NULL) {
! 142: error("%s: BN_CTX_new", __func__);
! 143: goto out;
! 144: }
! 145: if ((g_v = BN_new()) == NULL ||
! 146: (r = BN_new()) == NULL ||
! 147: (tmp = BN_new()) == NULL) {
! 148: error("%s: BN_new", __func__);
! 149: goto out;
! 150: }
! 151:
! 152: /*
! 153: * v must be a random element of Zq, so 1 <= v < q
! 154: * we also exclude v = 1, since g^1 looks dangerous
! 155: */
! 156: if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
! 157: error("%s: bn_rand_range2", __func__);
! 158: goto out;
! 159: }
! 160: SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));
! 161:
! 162: /* g_v = g^v mod p */
! 163: if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
! 164: error("%s: BN_mod_exp (g^v mod p)", __func__);
! 165: goto out;
! 166: }
! 167: SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
! 168:
! 169: /* h = H(g || g^v || g^x || id) */
! 170: if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
! 171: id, idlen)) == NULL) {
! 172: error("%s: schnorr_hash failed", __func__);
! 173: goto out;
! 174: }
! 175:
! 176: /* r = v - xh mod q */
! 177: if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
! 178: error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
! 179: goto out;
! 180: }
! 181: if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
! 182: error("%s: BN_mod_mul (r = v - tmp)", __func__);
! 183: goto out;
! 184: }
! 185: SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
! 186:
! 187: /* Signature is (g_v, r) */
! 188: buffer_init(&b);
! 189: /* XXX sigtype-hash as string? */
! 190: buffer_put_bignum2(&b, g_v);
! 191: buffer_put_bignum2(&b, r);
! 192: *siglen = buffer_len(&b);
! 193: *sig = xmalloc(*siglen);
! 194: memcpy(*sig, buffer_ptr(&b), *siglen);
! 195: SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
! 196: "%s: sigblob", __func__));
! 197: buffer_free(&b);
! 198: success = 0;
! 199: out:
! 200: BN_CTX_free(bn_ctx);
! 201: if (h != NULL)
! 202: BN_clear_free(h);
! 203: if (v != NULL)
! 204: BN_clear_free(v);
! 205: BN_clear_free(r);
! 206: BN_clear_free(g_v);
! 207: BN_clear_free(tmp);
! 208:
! 209: return success;
! 210: }
! 211:
! 212: /*
! 213: * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
! 214: * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'.
! 215: * Signature hash will be salted with 'idlen' bytes from 'id'.
! 216: * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
! 217: */
! 218: int
! 219: schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
! 220: const BIGNUM *g_x, const u_char *id, u_int idlen,
! 221: const u_char *sig, u_int siglen)
! 222: {
! 223: int success = -1;
! 224: Buffer b;
! 225: BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected;
! 226: BN_CTX *bn_ctx;
! 227: u_int rlen;
! 228:
! 229: SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
! 230:
! 231: /* Avoid degenerate cases: g^0 yields a spoofable signature */
! 232: if (BN_cmp(g_x, BN_value_one()) <= 0) {
! 233: error("%s: g_x < 1", __func__);
! 234: return -1;
! 235: }
! 236:
! 237: g_v = h = r = g_xh = g_r = expected = NULL;
! 238: if ((bn_ctx = BN_CTX_new()) == NULL) {
! 239: error("%s: BN_CTX_new", __func__);
! 240: goto out;
! 241: }
! 242: if ((g_v = BN_new()) == NULL ||
! 243: (r = BN_new()) == NULL ||
! 244: (g_xh = BN_new()) == NULL ||
! 245: (g_r = BN_new()) == NULL ||
! 246: (expected = BN_new()) == NULL) {
! 247: error("%s: BN_new", __func__);
! 248: goto out;
! 249: }
! 250:
! 251: /* Extract g^v and r from signature blob */
! 252: buffer_init(&b);
! 253: buffer_append(&b, sig, siglen);
! 254: SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
! 255: "%s: sigblob", __func__));
! 256: buffer_get_bignum2(&b, g_v);
! 257: buffer_get_bignum2(&b, r);
! 258: rlen = buffer_len(&b);
! 259: buffer_free(&b);
! 260: if (rlen != 0) {
! 261: error("%s: remaining bytes in signature %d", __func__, rlen);
! 262: goto out;
! 263: }
! 264: buffer_free(&b);
! 265: SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
! 266: SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
! 267:
! 268: /* h = H(g || g^v || g^x || id) */
! 269: if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
! 270: id, idlen)) == NULL) {
! 271: error("%s: schnorr_hash failed", __func__);
! 272: goto out;
! 273: }
! 274:
! 275: /* g_xh = (g^x)^h */
! 276: if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
! 277: error("%s: BN_mod_exp (g_x^h mod p)", __func__);
! 278: goto out;
! 279: }
! 280: SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
! 281:
! 282: /* g_r = g^r */
! 283: if (BN_mod_exp(g_r, grp_g, r, 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_r, "%s: g_r = ", __func__));
! 288:
! 289: /* expected = g^r * g_xh */
! 290: if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
! 291: error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
! 292: goto out;
! 293: }
! 294: SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
! 295:
! 296: /* Check g_v == expected */
! 297: success = BN_cmp(expected, g_v) == 0;
! 298: out:
! 299: BN_CTX_free(bn_ctx);
! 300: if (h != NULL)
! 301: BN_clear_free(h);
! 302: BN_clear_free(g_v);
! 303: BN_clear_free(r);
! 304: BN_clear_free(g_xh);
! 305: BN_clear_free(g_r);
! 306: BN_clear_free(expected);
! 307: return success;
! 308: }
! 309:
! 310: #ifdef SCHNORR_MAIN
! 311: static void
! 312: schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
! 313: const BIGNUM *grp_g, const BIGNUM *x)
! 314: {
! 315: BIGNUM *g_x;
! 316: u_char *sig;
! 317: u_int siglen;
! 318: BN_CTX *bn_ctx;
! 319:
! 320: if ((bn_ctx = BN_CTX_new()) == NULL)
! 321: fatal("%s: BN_CTX_new", __func__);
! 322: if ((g_x = BN_new()) == NULL)
! 323: fatal("%s: BN_new", __func__);
! 324:
! 325: if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
! 326: fatal("%s: g_x", __func__);
! 327: if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen))
! 328: fatal("%s: schnorr_sign", __func__);
! 329: if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
! 330: sig, siglen) != 1)
! 331: fatal("%s: verify fail", __func__);
! 332: if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
! 333: sig, siglen) != 0)
! 334: fatal("%s: verify should have failed (bad ID)", __func__);
! 335: sig[4] ^= 1;
! 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 (bit error)", __func__);
! 339: xfree(sig);
! 340: BN_free(g_x);
! 341: BN_CTX_free(bn_ctx);
! 342: }
! 343:
! 344: static void
! 345: schnorr_selftest(void)
! 346: {
! 347: BIGNUM *x;
! 348: struct jpake_group *grp;
! 349: u_int i;
! 350: char *hh;
! 351:
! 352: grp = jpake_default_group();
! 353: if ((x = BN_new()) == NULL)
! 354: fatal("%s: BN_new", __func__);
! 355: SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
! 356: SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
! 357: SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));
! 358:
! 359: /* [1, 20) */
! 360: for (i = 1; i < 20; i++) {
! 361: printf("x = %u\n", i);
! 362: fflush(stdout);
! 363: if (BN_set_word(x, i) != 1)
! 364: fatal("%s: set x word", __func__);
! 365: schnorr_selftest_one(grp->p, grp->q, grp->g, x);
! 366: }
! 367:
! 368: /* 100 x random [0, p) */
! 369: for (i = 0; i < 100; i++) {
! 370: if (BN_rand_range(x, grp->p) != 1)
! 371: fatal("%s: BN_rand_range", __func__);
! 372: hh = BN_bn2hex(x);
! 373: printf("x = (random) 0x%s\n", hh);
! 374: free(hh);
! 375: fflush(stdout);
! 376: schnorr_selftest_one(grp->p, grp->q, grp->g, x);
! 377: }
! 378:
! 379: /* [q-20, q) */
! 380: if (BN_set_word(x, 20) != 1)
! 381: fatal("%s: BN_set_word (x = 20)", __func__);
! 382: if (BN_sub(x, grp->q, x) != 1)
! 383: fatal("%s: BN_sub (q - x)", __func__);
! 384: for (i = 0; i < 19; i++) {
! 385: hh = BN_bn2hex(x);
! 386: printf("x = (q - %d) 0x%s\n", 20 - i, hh);
! 387: free(hh);
! 388: fflush(stdout);
! 389: schnorr_selftest_one(grp->p, grp->q, grp->g, x);
! 390: if (BN_add(x, x, BN_value_one()) != 1)
! 391: fatal("%s: BN_add (x + 1)", __func__);
! 392: }
! 393: BN_free(x);
! 394: }
! 395:
! 396: int
! 397: main(int argc, char **argv)
! 398: {
! 399: log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);
! 400:
! 401: schnorr_selftest();
! 402: return 0;
! 403: }
! 404: #endif
! 405:
![[BACK]](/icons/back.gif){kind=icon}
Return to schnorr.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh