summaryrefslogtreecommitdiff
path: root/schnorr.c
diff options
context:
space:
mode:
Diffstat (limited to 'schnorr.c')
-rw-r--r--schnorr.c409
1 files changed, 409 insertions, 0 deletions
diff --git a/schnorr.c b/schnorr.c
new file mode 100644
index 000000000..546975072
--- /dev/null
+++ b/schnorr.c
@@ -0,0 +1,409 @@
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 */
64static BIGNUM *
65schnorr_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__));
94 if (hash_buffer(buffer_ptr(&b), buffer_len(&b), EVP_sha256(),
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 */
125int
126schnorr_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 */
222int
223schnorr_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
315static void
316schnorr_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
348static void
349schnorr_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
400int
401main(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
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 02:27:24 +0000