1 /* $OpenBSD: schnorr.c,v 1.3 2009/03/05 07:18:19 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__);
145 h = g_v = r = tmp = v = NULL;
146 if ((bn_ctx = BN_CTX_new()) == NULL) {
147 error("%s: BN_CTX_new", __func__);
150 if ((g_v = BN_new()) == NULL ||
151 (r = BN_new()) == NULL ||
152 (tmp = BN_new()) == NULL) {
153 error("%s: BN_new", __func__);
158 * v must be a random element of Zq, so 1 <= v < q
159 * we also exclude v = 1, since g^1 looks dangerous
161 if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
162 error("%s: bn_rand_range2", __func__);
165 SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));
167 /* g_v = g^v mod p */
168 if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) {
169 error("%s: BN_mod_exp (g^v mod p)", __func__);
172 SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
174 /* h = H(g || g^v || g^x || id) */
175 if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x,
176 id, idlen)) == NULL) {
177 error("%s: schnorr_hash failed", __func__);
181 /* r = v - xh mod q */
182 if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) {
183 error("%s: BN_mod_mul (tmp = xv mod q)", __func__);
186 if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
187 error("%s: BN_mod_mul (r = v - tmp)", __func__);
190 SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__));
191 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
209 * Generate Schnorr signature to prove knowledge of private value 'x' used
210 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
211 * using a SHA256 hash.
212 * 'idlen' bytes from 'id' will be included in the signature hash as an anti-
214 * On success, 0 is returned and *siglen bytes of signature are returned in
215 * *sig (caller to free). Returns -1 on failure.
218 schnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
219 const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen,
220 u_char **sig, u_int *siglen)
225 if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(),
226 x, g_x, id, idlen, &r, &e) != 0)
229 /* Signature is (e, r) */
231 /* XXX sigtype-hash as string? */
232 buffer_put_bignum2(&b, e);
233 buffer_put_bignum2(&b, r);
234 *siglen = buffer_len(&b);
235 *sig = xmalloc(*siglen);
236 memcpy(*sig, buffer_ptr(&b), *siglen);
237 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
238 "%s: sigblob", __func__));
248 * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against
249 * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and
250 * 'grp_g' using hash "evp_md".
251 * Signature hash will be salted with 'idlen' bytes from 'id'.
252 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
255 schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g,
256 const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen,
257 const BIGNUM *r, const BIGNUM *e)
260 BIGNUM *h, *g_xh, *g_r, *expected;
263 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
265 /* Avoid degenerate cases: g^0 yields a spoofable signature */
266 if (BN_cmp(g_x, BN_value_one()) <= 0) {
267 error("%s: g_x < 1", __func__);
271 h = g_xh = g_r = expected = NULL;
272 if ((bn_ctx = BN_CTX_new()) == NULL) {
273 error("%s: BN_CTX_new", __func__);
276 if ((g_xh = BN_new()) == NULL ||
277 (g_r = BN_new()) == NULL ||
278 (expected = BN_new()) == NULL) {
279 error("%s: BN_new", __func__);
283 SCHNORR_DEBUG_BN((e, "%s: e = ", __func__));
284 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
286 /* h = H(g || g^v || g^x || id) */
287 if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x,
288 id, idlen)) == NULL) {
289 error("%s: schnorr_hash failed", __func__);
294 if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) {
295 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
298 SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
301 if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) {
302 error("%s: BN_mod_exp (g_x^h mod p)", __func__);
305 SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));
307 /* expected = g^r * g_xh */
308 if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) {
309 error("%s: BN_mod_mul (expected = g_r mod p)", __func__);
312 SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
314 /* Check e == expected */
315 success = BN_cmp(expected, e) == 0;
322 BN_clear_free(expected);
327 * Verify Schnorr signature 'sig' of length 'siglen' against public exponent
328 * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a
330 * Signature hash will be salted with 'idlen' bytes from 'id'.
331 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
334 schnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q,
336 const BIGNUM *g_x, const u_char *id, u_int idlen,
337 const u_char *sig, u_int siglen)
345 if ((e = BN_new()) == NULL ||
346 (r = BN_new()) == NULL) {
347 error("%s: BN_new", __func__);
351 /* Extract g^v and r from signature blob */
353 buffer_append(&b, sig, siglen);
354 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
355 "%s: sigblob", __func__));
356 buffer_get_bignum2(&b, e);
357 buffer_get_bignum2(&b, r);
358 rlen = buffer_len(&b);
361 error("%s: remaining bytes in signature %d", __func__, rlen);
365 ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(),
366 g_x, id, idlen, r, e);
374 /* Helper functions */
377 * Generate uniformly distributed random number in range (1, high).
378 * Return number on success, NULL on failure.
381 bn_rand_range_gt_one(const BIGNUM *high)
386 if ((tmp = BN_new()) == NULL) {
387 error("%s: BN_new", __func__);
390 if ((r = BN_new()) == NULL) {
391 error("%s: BN_new failed", __func__);
394 if (BN_set_word(tmp, 2) != 1) {
395 error("%s: BN_set_word(tmp, 2)", __func__);
398 if (BN_sub(tmp, high, tmp) == -1) {
399 error("%s: BN_sub failed (tmp = high - 2)", __func__);
402 if (BN_rand_range(r, tmp) == -1) {
403 error("%s: BN_rand_range failed", __func__);
406 if (BN_set_word(tmp, 2) != 1) {
407 error("%s: BN_set_word(tmp, 2)", __func__);
410 if (BN_add(r, r, tmp) == -1) {
411 error("%s: BN_add failed (r = r + 2)", __func__);
424 * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success,
425 * with digest via 'digestp' (caller to free) and length via 'lenp'.
426 * Returns -1 on failure.
429 hash_buffer(const u_char *buf, u_int len, const EVP_MD *md,
430 u_char **digestp, u_int *lenp)
432 u_char digest[EVP_MAX_MD_SIZE];
434 EVP_MD_CTX evp_md_ctx;
437 EVP_MD_CTX_init(&evp_md_ctx);
439 if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) {
440 error("%s: EVP_DigestInit_ex", __func__);
443 if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) {
444 error("%s: EVP_DigestUpdate", __func__);
447 if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) {
448 error("%s: EVP_DigestFinal_ex", __func__);
451 *digestp = xmalloc(digest_len);
453 memcpy(*digestp, digest, *lenp);
456 EVP_MD_CTX_cleanup(&evp_md_ctx);
457 bzero(digest, sizeof(digest));
462 /* print formatted string followed by bignum */
464 debug3_bn(const BIGNUM *n, const char *fmt, ...)
471 vasprintf(&out, fmt, args);
474 fatal("%s: vasprintf failed", __func__);
477 debug3("%s(null)", out);
480 debug3("%s0x%s", out, h);
486 /* print formatted string followed by buffer contents in hex */
488 debug3_buf(const u_char *buf, u_int len, const char *fmt, ...)
496 vasprintf(&out, fmt, args);
499 fatal("%s: vasprintf failed", __func__);
501 debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : "");
507 for (i = j = 0; i < len; i++) {
508 snprintf(h + j, sizeof(h) - j, "%02x", buf[i]);
510 if (j >= sizeof(h) - 1 || i == len - 1) {
519 * Construct a MODP group from hex strings p (which must be a safe
520 * prime) and g, automatically calculating subgroup q as (p / 2)
523 modp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p)
525 struct modp_group *ret;
527 ret = xmalloc(sizeof(*ret));
528 ret->p = ret->q = ret->g = NULL;
529 if (BN_hex2bn(&ret->p, grp_p) == 0 ||
530 BN_hex2bn(&ret->g, grp_g) == 0)
531 fatal("%s: BN_hex2bn", __func__);
532 /* Subgroup order is p/2 (p is a safe prime) */
533 if ((ret->q = BN_new()) == NULL)
534 fatal("%s: BN_new", __func__);
535 if (BN_rshift1(ret->q, ret->p) != 1)
536 fatal("%s: BN_rshift1", __func__);
542 modp_group_free(struct modp_group *grp)
545 BN_clear_free(grp->g);
547 BN_clear_free(grp->p);
549 BN_clear_free(grp->q);
550 bzero(grp, sizeof(*grp));
554 /* main() function for self-test */
558 schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
559 const BIGNUM *grp_g, const BIGNUM *x)
566 if ((bn_ctx = BN_CTX_new()) == NULL)
567 fatal("%s: BN_CTX_new", __func__);
568 if ((g_x = BN_new()) == NULL)
569 fatal("%s: BN_new", __func__);
571 if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
572 fatal("%s: g_x", __func__);
573 if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4,
575 fatal("%s: schnorr_sign", __func__);
576 if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
578 fatal("%s: verify fail", __func__);
579 if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
581 fatal("%s: verify should have failed (bad ID)", __func__);
583 if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
585 fatal("%s: verify should have failed (bit error)", __func__);
592 schnorr_selftest(void)
595 struct modp_group *grp;
599 grp = jpake_default_group();
600 if ((x = BN_new()) == NULL)
601 fatal("%s: BN_new", __func__);
602 SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__));
603 SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__));
604 SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__));
607 for (i = 1; i < 20; i++) {
608 printf("x = %u\n", i);
610 if (BN_set_word(x, i) != 1)
611 fatal("%s: set x word", __func__);
612 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
615 /* 100 x random [0, p) */
616 for (i = 0; i < 100; i++) {
617 if (BN_rand_range(x, grp->p) != 1)
618 fatal("%s: BN_rand_range", __func__);
620 printf("x = (random) 0x%s\n", hh);
623 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
627 if (BN_set_word(x, 20) != 1)
628 fatal("%s: BN_set_word (x = 20)", __func__);
629 if (BN_sub(x, grp->q, x) != 1)
630 fatal("%s: BN_sub (q - x)", __func__);
631 for (i = 0; i < 19; i++) {
633 printf("x = (q - %d) 0x%s\n", 20 - i, hh);
636 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
637 if (BN_add(x, x, BN_value_one()) != 1)
638 fatal("%s: BN_add (x + 1)", __func__);
644 main(int argc, char **argv)
646 log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);