1 /* $OpenBSD: schnorr.c,v 1.2 2009/02/18 04:31:21 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 /* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */
49 /* #define SCHNORR_MAIN */ /* Include main() selftest */
52 /* Parametise signature hash? (sha256, sha1, etc.) */
53 /* Signature format - include type name, hash type, group params? */
56 # define SCHNORR_DEBUG_BN(a)
57 # define SCHNORR_DEBUG_BUF(a)
59 # define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a
60 # define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a
61 #endif /* SCHNORR_DEBUG */
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.
68 schnorr_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)
75 EVP_MD_CTX evp_md_ctx;
79 if ((h = BN_new()) == NULL) {
80 error("%s: BN_new", __func__);
85 EVP_MD_CTX_init(&evp_md_ctx);
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);
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__);
102 if (BN_bin2bn(digest, (int)digest_len, h) == NULL) {
103 error("%s: BN_bin2bn", __func__);
107 SCHNORR_DEBUG_BN((h, "%s: h = ", __func__));
110 EVP_MD_CTX_cleanup(&evp_md_ctx);
111 bzero(digest, digest_len);
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-
125 * On success, 0 is returned and *siglen bytes of signature are returned in
126 * *sig (caller to free). Returns -1 on failure.
129 schnorr_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)
135 BIGNUM *h, *tmp, *v, *g_v, *r;
138 SCHNORR_DEBUG_BN((x, "%s: x = ", __func__));
139 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
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__);
147 h = g_v = r = tmp = v = NULL;
148 if ((bn_ctx = BN_CTX_new()) == NULL) {
149 error("%s: BN_CTX_new", __func__);
152 if ((g_v = BN_new()) == NULL ||
153 (r = BN_new()) == NULL ||
154 (tmp = BN_new()) == NULL) {
155 error("%s: BN_new", __func__);
160 * v must be a random element of Zq, so 1 <= v < q
161 * we also exclude v = 1, since g^1 looks dangerous
163 if ((v = bn_rand_range_gt_one(grp_p)) == NULL) {
164 error("%s: bn_rand_range2", __func__);
167 SCHNORR_DEBUG_BN((v, "%s: v = ", __func__));
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__);
174 SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
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__);
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__);
188 if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) {
189 error("%s: BN_mod_mul (r = v - tmp)", __func__);
192 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
194 /* Signature is (g_v, r) */
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__));
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.
226 schnorr_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)
232 BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected;
236 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
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__);
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__);
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__);
258 /* Extract g^v and r from signature blob */
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);
268 error("%s: remaining bytes in signature %d", __func__, rlen);
272 SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
273 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
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__);
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__);
287 SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__));
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__);
294 SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__));
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__);
301 SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
303 /* Check g_v == expected */
304 success = BN_cmp(expected, g_v) == 0;
313 BN_clear_free(expected);
319 schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
320 const BIGNUM *grp_g, const BIGNUM *x)
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__);
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,
338 fatal("%s: verify fail", __func__);
339 if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
341 fatal("%s: verify should have failed (bad ID)", __func__);
343 if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
345 fatal("%s: verify should have failed (bit error)", __func__);
352 schnorr_selftest(void)
355 struct jpake_group *grp;
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__));
367 for (i = 1; i < 20; i++) {
368 printf("x = %u\n", i);
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);
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__);
380 printf("x = (random) 0x%s\n", hh);
383 schnorr_selftest_one(grp->p, grp->q, grp->g, x);
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++) {
393 printf("x = (q - %d) 0x%s\n", 20 - i, hh);
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__);
404 main(int argc, char **argv)
406 log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1);