[gssapi-openssh.git] / openssh / schnorr.c

/* $OpenBSD: schnorr.c,v 1.2 2009/02/18 04:31:21 djm Exp $ */
/*
 * Copyright (c) 2008 Damien Miller.  All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * Implementation of Schnorr signatures / zero-knowledge proofs, based on
 * description in:
 * 	
 * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling",
 * 16th Workshop on Security Protocols, Cambridge, April 2008
 *
 * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
 */

#include "includes.h"

#include <sys/types.h>

#include <string.h>
#include <stdarg.h>
#include <stdio.h>

#include <openssl/evp.h>
#include <openssl/bn.h>

#include "xmalloc.h"
#include "buffer.h"
#include "log.h"

#include "jpake.h"

/* #define SCHNORR_DEBUG */		/* Privacy-violating debugging */
/* #define SCHNORR_MAIN */		/* Include main() selftest */

/* XXX */
/* Parametise signature hash? (sha256, sha1, etc.) */
/* Signature format - include type name, hash type, group params? */

#ifndef SCHNORR_DEBUG
# define SCHNORR_DEBUG_BN(a)
# define SCHNORR_DEBUG_BUF(a)
#else
# define SCHNORR_DEBUG_BN(a)	jpake_debug3_bn a
# define SCHNORR_DEBUG_BUF(a)	jpake_debug3_buf a
#endif /* SCHNORR_DEBUG */

/*
 * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
 * using SHA1. Returns signature as bignum or NULL on error.
 */
static BIGNUM *
schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
    const BIGNUM *g_v, const BIGNUM *g_x,
    const u_char *id, u_int idlen)
{
	u_char *digest;
	u_int digest_len;
	BIGNUM *h;
	EVP_MD_CTX evp_md_ctx;
	Buffer b;
	int success = -1;

	if ((h = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		return NULL;
	}

	buffer_init(&b);
	EVP_MD_CTX_init(&evp_md_ctx);

	/* h = H(g || p || q || g^v || g^x || id) */
	buffer_put_bignum2(&b, g);
	buffer_put_bignum2(&b, p);
	buffer_put_bignum2(&b, q);
	buffer_put_bignum2(&b, g_v);
	buffer_put_bignum2(&b, g_x);
	buffer_put_string(&b, id, idlen);

	SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
	    "%s: hashblob", __func__));
	if (hash_buffer(buffer_ptr(&b), buffer_len(&b), (const EVP_MD *)EVP_sha256(),
	    &digest, &digest_len) != 0) {
		error("%s: hash_buffer", __func__);
		goto out;
	}
	if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
		error("%s: BN_bin2bn", __func__);
		goto out;
	}
	success = 0;
	SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
 out:
	buffer_free(&b);
	EVP_MD_CTX_cleanup(&evp_md_ctx);
	bzero(digest, digest_len);
	xfree(digest);
	digest_len = 0;
	if (success == 0)
		return h;
	BN_clear_free(h);
	return NULL;
}

/*
 * Generate Schnorr signature to prove knowledge of private value 'x' used
 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
 * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
 * replay salt.
 * On success, 0 is returned and *siglen bytes of signature are returned in
 * *sig (caller to free). Returns -1 on failure.
 */
int
schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
    const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
    u_char **sig, u_int *siglen)
{
	int success = -1;
	Buffer b;
	BIGNUM *h, *tmp, *v, *g_v, *r;
	BN_CTX *bn_ctx;

	SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
	SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));

	/* Avoid degenerate cases: g^0 yields a spoofable signature */
	if (BN_cmp(g_x, BN_value_one()) <= 0) {
		error("%s: g_x < 1", __func__);
		return -1;
	}

	h = g_v = r = tmp = v = NULL;
	if ((bn_ctx = BN_CTX_new()) == NULL) {
		error("%s: BN_CTX_new", __func__);
		goto out;
	}
	if ((g_v = BN_new()) == NULL ||
	    (r = BN_new()) == NULL ||
	    (tmp = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		goto out;
	}

	/*
	 * v must be a random element of Zq, so 1 <= v < q
	 * we also exclude v = 1, since g^1 looks dangerous
	 */
	if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
		error("%s: bn_rand_range2", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));

	/* g_v = g^v mod p */
	if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_exp (g^v mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));

	/* h = H(g || g^v || g^x || id) */
	if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
	    id, idlen)) == NULL) {
		error("%s: schnorr_hash failed", __func__);
		goto out;
	}

	/* r = v - xh mod q */
	if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
		error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
		goto out;
	}
	if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
		error("%s: BN_mod_mul (r = v - tmp)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));

	/* Signature is (g_v, r) */
	buffer_init(&b);
	/* XXX sigtype-hash as string? */
	buffer_put_bignum2(&b, g_v);
	buffer_put_bignum2(&b, r);
	*siglen = buffer_len(&b);
	*sig = xmalloc(*siglen);
	memcpy(*sig, buffer_ptr(&b), *siglen);
	SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
	    "%s: sigblob", __func__));
	buffer_free(&b);
	success = 0;
 out:
	BN_CTX_free(bn_ctx);
	if (h != NULL)
		BN_clear_free(h);
	if (v != NULL)
		BN_clear_free(v);
	BN_clear_free(r);
	BN_clear_free(g_v);
	BN_clear_free(tmp);

	return success;
}

/*
 * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
 * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'.
 * Signature hash will be salted with 'idlen' bytes from 'id'.
 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
 */
int
schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
    const BIGNUM *g_x, const u_char *id, u_int idlen,
    const u_char *sig, u_int siglen)
{
	int success = -1;
	Buffer b;
	BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected;
	BN_CTX *bn_ctx;
	u_int rlen;

	SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));

	/* Avoid degenerate cases: g^0 yields a spoofable signature */
	if (BN_cmp(g_x, BN_value_one()) <= 0) {
		error("%s: g_x < 1", __func__);
		return -1;
	}

	g_v = h = r = g_xh = g_r = expected = NULL;
	if ((bn_ctx = BN_CTX_new()) == NULL) {
		error("%s: BN_CTX_new", __func__);
		goto out;
	}
	if ((g_v = BN_new()) == NULL ||
	    (r = BN_new()) == NULL ||
	    (g_xh = BN_new()) == NULL ||
	    (g_r = BN_new()) == NULL ||
	    (expected = BN_new()) == NULL) {
		error("%s: BN_new", __func__);
		goto out;
	}

	/* Extract g^v and r from signature blob */
	buffer_init(&b);
	buffer_append(&b, sig, siglen);
	SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
	    "%s: sigblob", __func__));
	buffer_get_bignum2(&b, g_v);
	buffer_get_bignum2(&b, r);
	rlen = buffer_len(&b);
	buffer_free(&b);
	if (rlen != 0) {
		error("%s: remaining bytes in signature %d", __func__, rlen);
		goto out;
	}
	buffer_free(&b);
	SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
	SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));

	/* h = H(g || g^v || g^x || id) */
	if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
	    id, idlen)) == NULL) {
		error("%s: schnorr_hash failed", __func__);
		goto out;
	}

	/* g_xh = (g^x)^h */
	if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_exp (g_x^h mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));

	/* g_r = g^r */
	if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_exp (g_x^h mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));

	/* expected = g^r * g_xh */
	if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
		error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
		goto out;
	}
	SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));

	/* Check g_v == expected */
	success = BN_cmp(expected, g_v) == 0;
 out:
	BN_CTX_free(bn_ctx);
	if (h != NULL)
		BN_clear_free(h);
	BN_clear_free(g_v);
	BN_clear_free(r);
	BN_clear_free(g_xh);
	BN_clear_free(g_r);
	BN_clear_free(expected);
	return success;
}

#ifdef SCHNORR_MAIN
static void
schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
    const BIGNUM *grp_g, const BIGNUM *x)
{
	BIGNUM *g_x;
	u_char *sig;
	u_int siglen;
	BN_CTX *bn_ctx;

	if ((bn_ctx = BN_CTX_new()) == NULL)
		fatal("%s: BN_CTX_new", __func__);
	if ((g_x = BN_new()) == NULL)
		fatal("%s: BN_new", __func__);

	if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
		fatal("%s: g_x", __func__);
	if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen))
		fatal("%s: schnorr_sign", __func__);
	if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
	    sig, siglen) != 1)
		fatal("%s: verify fail", __func__);
	if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
	    sig, siglen) != 0)
		fatal("%s: verify should have failed (bad ID)", __func__);
	sig[4] ^= 1;
	if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
	    sig, siglen) != 0)
		fatal("%s: verify should have failed (bit error)", __func__);
	xfree(sig);
	BN_free(g_x);
	BN_CTX_free(bn_ctx);
}

static void
schnorr_selftest(void)
{
	BIGNUM *x;
	struct jpake_group *grp;
	u_int i;
	char *hh;

	grp = jpake_default_group();
	if ((x = BN_new()) == NULL)
		fatal("%s: BN_new", __func__);
	SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
	SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
	SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));

	/* [1, 20) */
	for (i = 1; i < 20; i++) {
		printf("x = %u\n", i);
		fflush(stdout);
		if (BN_set_word(x, i) != 1)
			fatal("%s: set x word", __func__);
		schnorr_selftest_one(grp->p, grp->q, grp->g, x);
	}

	/* 100 x random [0, p) */
	for (i = 0; i < 100; i++) {
		if (BN_rand_range(x, grp->p) != 1)
			fatal("%s: BN_rand_range", __func__);
		hh = BN_bn2hex(x);
		printf("x = (random) 0x%s\n", hh);
		free(hh);
		fflush(stdout);
		schnorr_selftest_one(grp->p, grp->q, grp->g, x);
	}

	/* [q-20, q) */
	if (BN_set_word(x, 20) != 1)
		fatal("%s: BN_set_word (x = 20)", __func__);
	if (BN_sub(x, grp->q, x) != 1)
		fatal("%s: BN_sub (q - x)", __func__);
	for (i = 0; i < 19; i++) {
		hh = BN_bn2hex(x);
		printf("x = (q - %d) 0x%s\n", 20 - i, hh);
		free(hh);
		fflush(stdout);
		schnorr_selftest_one(grp->p, grp->q, grp->g, x);
		if (BN_add(x, x, BN_value_one()) != 1)
			fatal("%s: BN_add (x + 1)", __func__);
	}
	BN_free(x);
}

int
main(int argc, char **argv)
{
	log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);

	schnorr_selftest();
	return 0;
}
#endif
Commit	Line	Data
ac450140	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__));
326f21be	94	if (hash_buffer(buffer_ptr(&b), buffer_len(&b), (const EVP_MD *)EVP_sha256(),
ac450140	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