schnorr.c revision 192595
1189006Sdes/* $OpenBSD: schnorr.c,v 1.2 2009/02/18 04:31:21 djm Exp $ */ 2192595Sdes/* $FreeBSD: head/crypto/openssh/schnorr.c 192595 2009-05-22 18:46:28Z des $ */ 3189006Sdes/* 4189006Sdes * Copyright (c) 2008 Damien Miller. All rights reserved. 5189006Sdes * 6189006Sdes * Permission to use, copy, modify, and distribute this software for any 7189006Sdes * purpose with or without fee is hereby granted, provided that the above 8189006Sdes * copyright notice and this permission notice appear in all copies. 9189006Sdes * 10189006Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11189006Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12189006Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13189006Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14189006Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15189006Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16189006Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17189006Sdes */ 18189006Sdes 19189006Sdes/* 20189006Sdes * Implementation of Schnorr signatures / zero-knowledge proofs, based on 21189006Sdes * description in: 22189006Sdes * 23189006Sdes * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling", 24189006Sdes * 16th Workshop on Security Protocols, Cambridge, April 2008 25189006Sdes * 26189006Sdes * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf 27189006Sdes */ 28189006Sdes 29189006Sdes#include "includes.h" 30189006Sdes 31189006Sdes#include <sys/types.h> 32189006Sdes 33189006Sdes#include <string.h> 34189006Sdes#include <stdarg.h> 35189006Sdes#include <stdio.h> 36189006Sdes 37189006Sdes#include <openssl/evp.h> 38189006Sdes#include <openssl/bn.h> 39189006Sdes 40189006Sdes#include "xmalloc.h" 41189006Sdes#include "buffer.h" 42189006Sdes#include "log.h" 43189006Sdes 44189006Sdes#include "jpake.h" 45189006Sdes 46192595Sdes#ifdef JPAKE 47192595Sdes 48189006Sdes/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ 49189006Sdes/* #define SCHNORR_MAIN */ /* Include main() selftest */ 50189006Sdes 51189006Sdes/* XXX */ 52189006Sdes/* Parametise signature hash? (sha256, sha1, etc.) */ 53189006Sdes/* Signature format - include type name, hash type, group params? */ 54189006Sdes 55189006Sdes#ifndef SCHNORR_DEBUG 56189006Sdes# define SCHNORR_DEBUG_BN(a) 57189006Sdes# define SCHNORR_DEBUG_BUF(a) 58189006Sdes#else 59189006Sdes# define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a 60189006Sdes# define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a 61189006Sdes#endif /* SCHNORR_DEBUG */ 62189006Sdes 63189006Sdes/* 64189006Sdes * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) 65189006Sdes * using SHA1. Returns signature as bignum or NULL on error. 66189006Sdes */ 67189006Sdesstatic BIGNUM * 68189006Sdesschnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, 69189006Sdes const BIGNUM *g_v, const BIGNUM *g_x, 70189006Sdes const u_char *id, u_int idlen) 71189006Sdes{ 72189006Sdes u_char *digest; 73189006Sdes u_int digest_len; 74189006Sdes BIGNUM *h; 75189006Sdes EVP_MD_CTX evp_md_ctx; 76189006Sdes Buffer b; 77189006Sdes int success = -1; 78189006Sdes 79189006Sdes if ((h = BN_new()) == NULL) { 80189006Sdes error("%s: BN_new", __func__); 81189006Sdes return NULL; 82189006Sdes } 83189006Sdes 84189006Sdes buffer_init(&b); 85189006Sdes EVP_MD_CTX_init(&evp_md_ctx); 86189006Sdes 87189006Sdes /* h = H(g || p || q || g^v || g^x || id) */ 88189006Sdes buffer_put_bignum2(&b, g); 89189006Sdes buffer_put_bignum2(&b, p); 90189006Sdes buffer_put_bignum2(&b, q); 91189006Sdes buffer_put_bignum2(&b, g_v); 92189006Sdes buffer_put_bignum2(&b, g_x); 93189006Sdes buffer_put_string(&b, id, idlen); 94189006Sdes 95189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 96189006Sdes "%s: hashblob", __func__)); 97189006Sdes if (hash_buffer(buffer_ptr(&b), buffer_len(&b), EVP_sha256(), 98189006Sdes &digest, &digest_len) != 0) { 99189006Sdes error("%s: hash_buffer", __func__); 100189006Sdes goto out; 101189006Sdes } 102189006Sdes if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { 103189006Sdes error("%s: BN_bin2bn", __func__); 104189006Sdes goto out; 105189006Sdes } 106189006Sdes success = 0; 107189006Sdes SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); 108189006Sdes out: 109189006Sdes buffer_free(&b); 110189006Sdes EVP_MD_CTX_cleanup(&evp_md_ctx); 111189006Sdes bzero(digest, digest_len); 112189006Sdes xfree(digest); 113189006Sdes digest_len = 0; 114189006Sdes if (success == 0) 115189006Sdes return h; 116189006Sdes BN_clear_free(h); 117189006Sdes return NULL; 118189006Sdes} 119189006Sdes 120189006Sdes/* 121189006Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 122189006Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 123189006Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 124189006Sdes * replay salt. 125189006Sdes * On success, 0 is returned and *siglen bytes of signature are returned in 126189006Sdes * *sig (caller to free). Returns -1 on failure. 127189006Sdes */ 128189006Sdesint 129189006Sdesschnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 130189006Sdes const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, 131189006Sdes u_char **sig, u_int *siglen) 132189006Sdes{ 133189006Sdes int success = -1; 134189006Sdes Buffer b; 135189006Sdes BIGNUM *h, *tmp, *v, *g_v, *r; 136189006Sdes BN_CTX *bn_ctx; 137189006Sdes 138189006Sdes SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); 139189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 140189006Sdes 141189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 142189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 143189006Sdes error("%s: g_x < 1", __func__); 144189006Sdes return -1; 145189006Sdes } 146189006Sdes 147189006Sdes h = g_v = r = tmp = v = NULL; 148189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 149189006Sdes error("%s: BN_CTX_new", __func__); 150189006Sdes goto out; 151189006Sdes } 152189006Sdes if ((g_v = BN_new()) == NULL || 153189006Sdes (r = BN_new()) == NULL || 154189006Sdes (tmp = BN_new()) == NULL) { 155189006Sdes error("%s: BN_new", __func__); 156189006Sdes goto out; 157189006Sdes } 158189006Sdes 159189006Sdes /* 160189006Sdes * v must be a random element of Zq, so 1 <= v < q 161189006Sdes * we also exclude v = 1, since g^1 looks dangerous 162189006Sdes */ 163189006Sdes if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { 164189006Sdes error("%s: bn_rand_range2", __func__); 165189006Sdes goto out; 166189006Sdes } 167189006Sdes SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); 168189006Sdes 169189006Sdes /* g_v = g^v mod p */ 170189006Sdes if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { 171189006Sdes error("%s: BN_mod_exp (g^v mod p)", __func__); 172189006Sdes goto out; 173189006Sdes } 174189006Sdes SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 175189006Sdes 176189006Sdes /* h = H(g || g^v || g^x || id) */ 177189006Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, 178189006Sdes id, idlen)) == NULL) { 179189006Sdes error("%s: schnorr_hash failed", __func__); 180189006Sdes goto out; 181189006Sdes } 182189006Sdes 183189006Sdes /* r = v - xh mod q */ 184189006Sdes if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { 185189006Sdes error("%s: BN_mod_mul (tmp = xv mod q)", __func__); 186189006Sdes goto out; 187189006Sdes } 188189006Sdes if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { 189189006Sdes error("%s: BN_mod_mul (r = v - tmp)", __func__); 190189006Sdes goto out; 191189006Sdes } 192189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 193189006Sdes 194189006Sdes /* Signature is (g_v, r) */ 195189006Sdes buffer_init(&b); 196189006Sdes /* XXX sigtype-hash as string? */ 197189006Sdes buffer_put_bignum2(&b, g_v); 198189006Sdes buffer_put_bignum2(&b, r); 199189006Sdes *siglen = buffer_len(&b); 200189006Sdes *sig = xmalloc(*siglen); 201189006Sdes memcpy(*sig, buffer_ptr(&b), *siglen); 202189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 203189006Sdes "%s: sigblob", __func__)); 204189006Sdes buffer_free(&b); 205189006Sdes success = 0; 206189006Sdes out: 207189006Sdes BN_CTX_free(bn_ctx); 208189006Sdes if (h != NULL) 209189006Sdes BN_clear_free(h); 210189006Sdes if (v != NULL) 211189006Sdes BN_clear_free(v); 212189006Sdes BN_clear_free(r); 213189006Sdes BN_clear_free(g_v); 214189006Sdes BN_clear_free(tmp); 215189006Sdes 216189006Sdes return success; 217189006Sdes} 218189006Sdes 219189006Sdes/* 220189006Sdes * Verify Schnorr signature 'sig' of length 'siglen' against public exponent 221189006Sdes * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'. 222189006Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 223189006Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 224189006Sdes */ 225189006Sdesint 226189006Sdesschnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 227189006Sdes const BIGNUM *g_x, const u_char *id, u_int idlen, 228189006Sdes const u_char *sig, u_int siglen) 229189006Sdes{ 230189006Sdes int success = -1; 231189006Sdes Buffer b; 232189006Sdes BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected; 233189006Sdes BN_CTX *bn_ctx; 234189006Sdes u_int rlen; 235189006Sdes 236189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 237189006Sdes 238189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 239189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 240189006Sdes error("%s: g_x < 1", __func__); 241189006Sdes return -1; 242189006Sdes } 243189006Sdes 244189006Sdes g_v = h = r = g_xh = g_r = expected = NULL; 245189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 246189006Sdes error("%s: BN_CTX_new", __func__); 247189006Sdes goto out; 248189006Sdes } 249189006Sdes if ((g_v = BN_new()) == NULL || 250189006Sdes (r = BN_new()) == NULL || 251189006Sdes (g_xh = BN_new()) == NULL || 252189006Sdes (g_r = BN_new()) == NULL || 253189006Sdes (expected = BN_new()) == NULL) { 254189006Sdes error("%s: BN_new", __func__); 255189006Sdes goto out; 256189006Sdes } 257189006Sdes 258189006Sdes /* Extract g^v and r from signature blob */ 259189006Sdes buffer_init(&b); 260189006Sdes buffer_append(&b, sig, siglen); 261189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 262189006Sdes "%s: sigblob", __func__)); 263189006Sdes buffer_get_bignum2(&b, g_v); 264189006Sdes buffer_get_bignum2(&b, r); 265189006Sdes rlen = buffer_len(&b); 266189006Sdes buffer_free(&b); 267189006Sdes if (rlen != 0) { 268189006Sdes error("%s: remaining bytes in signature %d", __func__, rlen); 269189006Sdes goto out; 270189006Sdes } 271189006Sdes buffer_free(&b); 272189006Sdes SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 273189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 274189006Sdes 275189006Sdes /* h = H(g || g^v || g^x || id) */ 276189006Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, 277189006Sdes id, idlen)) == NULL) { 278189006Sdes error("%s: schnorr_hash failed", __func__); 279189006Sdes goto out; 280189006Sdes } 281189006Sdes 282189006Sdes /* g_xh = (g^x)^h */ 283189006Sdes if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { 284189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 285189006Sdes goto out; 286189006Sdes } 287189006Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 288189006Sdes 289189006Sdes /* g_r = g^r */ 290189006Sdes if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { 291189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 292189006Sdes goto out; 293189006Sdes } 294189006Sdes SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); 295189006Sdes 296189006Sdes /* expected = g^r * g_xh */ 297189006Sdes if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { 298189006Sdes error("%s: BN_mod_mul (expected = g_r mod p)", __func__); 299189006Sdes goto out; 300189006Sdes } 301189006Sdes SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); 302189006Sdes 303189006Sdes /* Check g_v == expected */ 304189006Sdes success = BN_cmp(expected, g_v) == 0; 305189006Sdes out: 306189006Sdes BN_CTX_free(bn_ctx); 307189006Sdes if (h != NULL) 308189006Sdes BN_clear_free(h); 309189006Sdes BN_clear_free(g_v); 310189006Sdes BN_clear_free(r); 311189006Sdes BN_clear_free(g_xh); 312189006Sdes BN_clear_free(g_r); 313189006Sdes BN_clear_free(expected); 314189006Sdes return success; 315189006Sdes} 316189006Sdes 317189006Sdes#ifdef SCHNORR_MAIN 318189006Sdesstatic void 319189006Sdesschnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, 320189006Sdes const BIGNUM *grp_g, const BIGNUM *x) 321189006Sdes{ 322189006Sdes BIGNUM *g_x; 323189006Sdes u_char *sig; 324189006Sdes u_int siglen; 325189006Sdes BN_CTX *bn_ctx; 326189006Sdes 327189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) 328189006Sdes fatal("%s: BN_CTX_new", __func__); 329189006Sdes if ((g_x = BN_new()) == NULL) 330189006Sdes fatal("%s: BN_new", __func__); 331189006Sdes 332189006Sdes if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) 333189006Sdes fatal("%s: g_x", __func__); 334189006Sdes if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen)) 335189006Sdes fatal("%s: schnorr_sign", __func__); 336189006Sdes if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, 337189006Sdes sig, siglen) != 1) 338189006Sdes fatal("%s: verify fail", __func__); 339189006Sdes if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4, 340189006Sdes sig, siglen) != 0) 341189006Sdes fatal("%s: verify should have failed (bad ID)", __func__); 342189006Sdes sig[4] ^= 1; 343189006Sdes if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, 344189006Sdes sig, siglen) != 0) 345189006Sdes fatal("%s: verify should have failed (bit error)", __func__); 346189006Sdes xfree(sig); 347189006Sdes BN_free(g_x); 348189006Sdes BN_CTX_free(bn_ctx); 349189006Sdes} 350189006Sdes 351189006Sdesstatic void 352189006Sdesschnorr_selftest(void) 353189006Sdes{ 354189006Sdes BIGNUM *x; 355189006Sdes struct jpake_group *grp; 356189006Sdes u_int i; 357189006Sdes char *hh; 358189006Sdes 359189006Sdes grp = jpake_default_group(); 360189006Sdes if ((x = BN_new()) == NULL) 361189006Sdes fatal("%s: BN_new", __func__); 362189006Sdes SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); 363189006Sdes SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); 364189006Sdes SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); 365189006Sdes 366189006Sdes /* [1, 20) */ 367189006Sdes for (i = 1; i < 20; i++) { 368189006Sdes printf("x = %u\n", i); 369189006Sdes fflush(stdout); 370189006Sdes if (BN_set_word(x, i) != 1) 371189006Sdes fatal("%s: set x word", __func__); 372189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 373189006Sdes } 374189006Sdes 375189006Sdes /* 100 x random [0, p) */ 376189006Sdes for (i = 0; i < 100; i++) { 377189006Sdes if (BN_rand_range(x, grp->p) != 1) 378189006Sdes fatal("%s: BN_rand_range", __func__); 379189006Sdes hh = BN_bn2hex(x); 380189006Sdes printf("x = (random) 0x%s\n", hh); 381189006Sdes free(hh); 382189006Sdes fflush(stdout); 383189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 384189006Sdes } 385189006Sdes 386189006Sdes /* [q-20, q) */ 387189006Sdes if (BN_set_word(x, 20) != 1) 388189006Sdes fatal("%s: BN_set_word (x = 20)", __func__); 389189006Sdes if (BN_sub(x, grp->q, x) != 1) 390189006Sdes fatal("%s: BN_sub (q - x)", __func__); 391189006Sdes for (i = 0; i < 19; i++) { 392189006Sdes hh = BN_bn2hex(x); 393189006Sdes printf("x = (q - %d) 0x%s\n", 20 - i, hh); 394189006Sdes free(hh); 395189006Sdes fflush(stdout); 396189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 397189006Sdes if (BN_add(x, x, BN_value_one()) != 1) 398189006Sdes fatal("%s: BN_add (x + 1)", __func__); 399189006Sdes } 400189006Sdes BN_free(x); 401189006Sdes} 402189006Sdes 403189006Sdesint 404189006Sdesmain(int argc, char **argv) 405189006Sdes{ 406189006Sdes log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); 407189006Sdes 408189006Sdes schnorr_selftest(); 409189006Sdes return 0; 410189006Sdes} 411189006Sdes#endif 412189006Sdes 413192595Sdes#endif 414