1 /* $OpenBSD: schnorr.c,v 1.5 2010/12/03 23:49:26 djm Exp $ */
4 * Copyright (c) 2008 Damien Miller. All rights reserved.
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.
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.
20 * Implementation of Schnorr signatures / zero-knowledge proofs, based on
23 * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling",
24 * 16th Workshop on Security Protocols, Cambridge, April 2008
26 * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf
31 #include <sys/types.h>
37 #include <openssl/evp.h>
38 #include <openssl/bn.h>
48 #include "openbsd-compat/openssl-compat.h"
50 /* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */
51 /* #define SCHNORR_MAIN */ /* Include main() selftest */
54 # define SCHNORR_DEBUG_BN(a)
55 # define SCHNORR_DEBUG_BUF(a)
57 # define SCHNORR_DEBUG_BN(a) debug3_bn a
58 # define SCHNORR_DEBUG_BUF(a) debug3_buf a
59 #endif /* SCHNORR_DEBUG */
62 * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
63 * using the hash function defined by "evp_md". Returns signature as
64 * bignum or NULL on error.
67 schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
68 const EVP_MD *evp_md, const BIGNUM *g_v, const BIGNUM *g_x,
69 const u_char *id, u_int idlen)
77 if ((h = BN_new()) == NULL) {
78 error("%s: BN_new", __func__);
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);
92 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
93 "%s: hashblob", __func__));
94 if (hash_buffer(buffer_ptr(&b), buffer_len(&b), evp_md,
95 &digest, &digest_len) != 0) {
96 error("%s: hash_buffer", __func__);
99 if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
100 error("%s: BN_bin2bn", __func__);
104 SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
107 bzero(digest, digest_len);
117 * Generate Schnorr signature to prove knowledge of private value 'x' used
118 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
119 * using the hash function "evp_md".
120 * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
123 * On success, 0 is returned. The signature values are returned as *e_p
124 * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values.
125 * On failure, -1 is returned.
128 schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
129 const EVP_MD *evp_md, const BIGNUM *x, const BIGNUM *g_x,
130 const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p)
133 BIGNUM *h, *tmp, *v, *g_v, *r;
136 SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
137 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
139 /* Avoid degenerate cases: g^0 yields a spoofable signature */
140 if (BN_cmp(g_x, BN_value_one()) <= 0) {
141 error("%s: g_x < 1", __func__);
144 if (BN_cmp(g_x, grp_p) >= 0) {
145 error("%s: g_x > g", __func__);
149 h = g_v = r = tmp = v = NULL;
150 if ((bn_ctx = BN_CTX_new()) == NULL) {
151 error("%s: BN_CTX_new", __func__);
154 if ((g_v = BN_new()) == NULL ||
155 (r = BN_new()) == NULL ||
156 (tmp = BN_new()) == NULL) {
157 error("%s: BN_new", __func__);
162 * v must be a random element of Zq, so 1 <= v < q
163 * we also exclude v = 1, since g^1 looks dangerous
165 if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
166 error("%s: bn_rand_range2", __func__);
169 SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));
171 /* g_v = g^v mod p */
172 if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
173 error("%s: BN_mod_exp (g^v mod p)", __func__);
176 SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
178 /* h = H(g || g^v || g^x || id) */
179 if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x,
180 id, idlen)) == NULL) {
181 error("%s: schnorr_hash failed", __func__);
185 /* r = v - xh mod q */
186 if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
187 error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
190 if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
191 error("%s: BN_mod_mul (r = v - tmp)", __func__);
194 SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__));
195 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
213 * Generate Schnorr signature to prove knowledge of private value 'x' used
214 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
215 * using a SHA256 hash.
216 * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
218 * On success, 0 is returned and *siglen bytes of signature are returned in
219 * *sig (caller to free). Returns -1 on failure.
222 schnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
223 const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
224 u_char **sig, u_int *siglen)
229 if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(),
230 x, g_x, id, idlen, &r, &e) != 0)
233 /* Signature is (e, r) */
235 /* XXX sigtype-hash as string? */
236 buffer_put_bignum2(&b, e);
237 buffer_put_bignum2(&b, r);
238 *siglen = buffer_len(&b);
239 *sig = xmalloc(*siglen);
240 memcpy(*sig, buffer_ptr(&b), *siglen);
241 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
242 "%s: sigblob", __func__));
252 * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against
253 * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and
254 * 'grp_g' using hash "evp_md".
255 * Signature hash will be salted with 'idlen' bytes from 'id'.
256 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
259 schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
260 const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen,
261 const BIGNUM *r, const BIGNUM *e)
264 BIGNUM *h = NULL, *g_xh = NULL, *g_r = NULL, *gx_q = NULL;
265 BIGNUM *expected = NULL;
268 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
270 /* Avoid degenerate cases: g^0 yields a spoofable signature */
271 if (BN_cmp(g_x, BN_value_one()) <= 0) {
272 error("%s: g_x <= 1", __func__);
275 if (BN_cmp(g_x, grp_p) >= 0) {
276 error("%s: g_x >= p", __func__);
280 h = g_xh = g_r = expected = NULL;
281 if ((bn_ctx = BN_CTX_new()) == NULL) {
282 error("%s: BN_CTX_new", __func__);
285 if ((g_xh = BN_new()) == NULL ||
286 (g_r = BN_new()) == NULL ||
287 (gx_q = BN_new()) == NULL ||
288 (expected = BN_new()) == NULL) {
289 error("%s: BN_new", __func__);
293 SCHNORR_DEBUG_BN((e, "%s: e = ", __func__));
294 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
296 /* gx_q = (g^x)^q must === 1 mod p */
297 if (BN_mod_exp(gx_q, g_x, grp_q, grp_p, bn_ctx) == -1) {
298 error("%s: BN_mod_exp (g_x^q mod p)", __func__);
301 if (BN_cmp(gx_q, BN_value_one()) != 0) {
302 error("%s: Invalid signature (g^x)^q != 1 mod p", __func__);
306 SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
307 /* h = H(g || g^v || g^x || id) */
308 if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x,
309 id, idlen)) == NULL) {
310 error("%s: schnorr_hash failed", __func__);
315 if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
316 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
319 SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
322 if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) {
323 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
326 SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));
328 /* expected = g^r * g_xh */
329 if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
330 error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
333 SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
335 /* Check e == expected */
336 success = BN_cmp(expected, e) == 0;
347 if (expected != NULL)
348 BN_clear_free(expected);
353 * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
354 * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a
356 * Signature hash will be salted with 'idlen' bytes from 'id'.
357 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
360 schnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q,
362 const BIGNUM *g_x, const u_char *id, u_int idlen,
363 const u_char *sig, u_int siglen)
371 if ((e = BN_new()) == NULL ||
372 (r = BN_new()) == NULL) {
373 error("%s: BN_new", __func__);
377 /* Extract g^v and r from signature blob */
379 buffer_append(&b, sig, siglen);
380 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
381 "%s: sigblob", __func__));
382 buffer_get_bignum2(&b, e);
383 buffer_get_bignum2(&b, r);
384 rlen = buffer_len(&b);
387 error("%s: remaining bytes in signature %d", __func__, rlen);
391 ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(),
392 g_x, id, idlen, r, e);
400 /* Helper functions */
403 * Generate uniformly distributed random number in range (1, high).
404 * Return number on success, NULL on failure.
407 bn_rand_range_gt_one(const BIGNUM *high)
412 if ((tmp = BN_new()) == NULL) {
413 error("%s: BN_new", __func__);
416 if ((r = BN_new()) == NULL) {
417 error("%s: BN_new failed", __func__);
420 if (BN_set_word(tmp, 2) != 1) {
421 error("%s: BN_set_word(tmp, 2)", __func__);
424 if (BN_sub(tmp, high, tmp) == -1) {
425 error("%s: BN_sub failed (tmp = high - 2)", __func__);
428 if (BN_rand_range(r, tmp) == -1) {
429 error("%s: BN_rand_range failed", __func__);
432 if (BN_set_word(tmp, 2) != 1) {
433 error("%s: BN_set_word(tmp, 2)", __func__);
436 if (BN_add(r, r, tmp) == -1) {
437 error("%s: BN_add failed (r = r + 2)", __func__);
450 * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success,
451 * with digest via 'digestp' (caller to free) and length via 'lenp'.
452 * Returns -1 on failure.
455 hash_buffer(const u_char *buf, u_int len, const EVP_MD *md,
456 u_char **digestp, u_int *lenp)
458 u_char digest[EVP_MAX_MD_SIZE];
460 EVP_MD_CTX evp_md_ctx;
463 EVP_MD_CTX_init(&evp_md_ctx);
465 if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) {
466 error("%s: EVP_DigestInit_ex", __func__);
469 if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) {
470 error("%s: EVP_DigestUpdate", __func__);
473 if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) {
474 error("%s: EVP_DigestFinal_ex", __func__);
477 *digestp = xmalloc(digest_len);
479 memcpy(*digestp, digest, *lenp);
482 EVP_MD_CTX_cleanup(&evp_md_ctx);
483 bzero(digest, sizeof(digest));
488 /* print formatted string followed by bignum */
490 debug3_bn(const BIGNUM *n, const char *fmt, ...)
497 vasprintf(&out, fmt, args);
500 fatal("%s: vasprintf failed", __func__);
503 debug3("%s(null)", out);
506 debug3("%s0x%s", out, h);
512 /* print formatted string followed by buffer contents in hex */
514 debug3_buf(const u_char *buf, u_int len, const char *fmt, ...)
522 vasprintf(&out, fmt, args);
525 fatal("%s: vasprintf failed", __func__);
527 debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : "");
533 for (i = j = 0; i < len; i++) {
534 snprintf(h + j, sizeof(h) - j, "%02x", buf[i]);
536 if (j >= sizeof(h) - 1 || i == len - 1) {
545 * Construct a MODP group from hex strings p (which must be a safe
546 * prime) and g, automatically calculating subgroup q as (p / 2)
549 modp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p)
551 struct modp_group *ret;
553 ret = xmalloc(sizeof(*ret));
554 ret->p = ret->q = ret->g = NULL;
555 if (BN_hex2bn(&ret->p, grp_p) == 0 ||
556 BN_hex2bn(&ret->g, grp_g) == 0)
557 fatal("%s: BN_hex2bn", __func__);
558 /* Subgroup order is p/2 (p is a safe prime) */
559 if ((ret->q = BN_new()) == NULL)
560 fatal("%s: BN_new", __func__);
561 if (BN_rshift1(ret->q, ret->p) != 1)
562 fatal("%s: BN_rshift1", __func__);
568 modp_group_free(struct modp_group *grp)
571 BN_clear_free(grp->g);
573 BN_clear_free(grp->p);
575 BN_clear_free(grp->q);
576 bzero(grp, sizeof(*grp));
580 /* main() function for self-test */
584 schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
585 const BIGNUM *grp_g, const BIGNUM *x)
592 if ((bn_ctx = BN_CTX_new()) == NULL)
593 fatal("%s: BN_CTX_new", __func__);
594 if ((g_x = BN_new()) == NULL)
595 fatal("%s: BN_new", __func__);
597 if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
598 fatal("%s: g_x", __func__);
599 if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4,
601 fatal("%s: schnorr_sign", __func__);
602 if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
604 fatal("%s: verify fail", __func__);
605 if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
607 fatal("%s: verify should have failed (bad ID)", __func__);
609 if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
611 fatal("%s: verify should have failed (bit error)", __func__);
618 schnorr_selftest(void)
621 struct modp_group *grp;
625 grp = jpake_default_group();
626 if ((x = BN_new()) == NULL)
627 fatal("%s: BN_new", __func__);
628 SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
629 SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
630 SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));
633 for (i = 1; i < 20; i++) {
634 printf("x = %u\n", i);
636 if (BN_set_word(x, i) != 1)
637 fatal("%s: set x word", __func__);
638 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
641 /* 100 x random [0, p) */
642 for (i = 0; i < 100; i++) {
643 if (BN_rand_range(x, grp->p) != 1)
644 fatal("%s: BN_rand_range", __func__);
646 printf("x = (random) 0x%s\n", hh);
649 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
653 if (BN_set_word(x, 20) != 1)
654 fatal("%s: BN_set_word (x = 20)", __func__);
655 if (BN_sub(x, grp->q, x) != 1)
656 fatal("%s: BN_sub (q - x)", __func__);
657 for (i = 0; i < 19; i++) {
659 printf("x = (q - %d) 0x%s\n", 20 - i, hh);
662 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
663 if (BN_add(x, x, BN_value_one()) != 1)
664 fatal("%s: BN_add (x + 1)", __func__);
670 main(int argc, char **argv)
672 log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);