schnorr.c revision 192595 
1/* $OpenBSD: schnorr.c,v 1.2 2009/02/18 04:31:21 djm Exp $ */
2/* $FreeBSD: head/crypto/openssh/schnorr.c 192595 2009-05-22 18:46:28Z des $ */
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 */
67static BIGNUM *
68schnorr_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 */
128int
129schnorr_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 */
225int
226schnorr_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
318static void
319schnorr_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
351static void
352schnorr_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
403int
404main(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
414