]>
Commit | Line | Data |
---|---|---|
5b01421b | 1 | /* $OpenBSD: schnorr.c,v 1.3 2009/03/05 07:18:19 djm Exp $ */ |
5adf6b9a | 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 | ||
5b01421b | 43 | #include "schnorr.h" |
5adf6b9a | 44 | |
45 | /* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ | |
46 | /* #define SCHNORR_MAIN */ /* Include main() selftest */ | |
47 | ||
5adf6b9a | 48 | #ifndef SCHNORR_DEBUG |
49 | # define SCHNORR_DEBUG_BN(a) | |
50 | # define SCHNORR_DEBUG_BUF(a) | |
51 | #else | |
5b01421b | 52 | # define SCHNORR_DEBUG_BN(a) debug3_bn a |
53 | # define SCHNORR_DEBUG_BUF(a) debug3_buf a | |
5adf6b9a | 54 | #endif /* SCHNORR_DEBUG */ |
55 | ||
56 | /* | |
57 | * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) | |
5b01421b | 58 | * using the hash function defined by "evp_md". Returns signature as |
59 | * bignum or NULL on error. | |
5adf6b9a | 60 | */ |
61 | static BIGNUM * | |
62 | schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, | |
5b01421b | 63 | const EVP_MD *evp_md, const BIGNUM *g_v, const BIGNUM *g_x, |
5adf6b9a | 64 | const u_char *id, u_int idlen) |
65 | { | |
66 | u_char *digest; | |
67 | u_int digest_len; | |
68 | BIGNUM *h; | |
5adf6b9a | 69 | Buffer b; |
70 | int success = -1; | |
71 | ||
72 | if ((h = BN_new()) == NULL) { | |
73 | error("%s: BN_new", __func__); | |
74 | return NULL; | |
75 | } | |
76 | ||
77 | buffer_init(&b); | |
5adf6b9a | 78 | |
dca75d4b | 79 | /* h = H(g || p || q || g^v || g^x || id) */ |
5adf6b9a | 80 | buffer_put_bignum2(&b, g); |
dca75d4b | 81 | buffer_put_bignum2(&b, p); |
82 | buffer_put_bignum2(&b, q); | |
5adf6b9a | 83 | buffer_put_bignum2(&b, g_v); |
84 | buffer_put_bignum2(&b, g_x); | |
85 | buffer_put_string(&b, id, idlen); | |
86 | ||
87 | SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), | |
88 | "%s: hashblob", __func__)); | |
5b01421b | 89 | if (hash_buffer(buffer_ptr(&b), buffer_len(&b), evp_md, |
5adf6b9a | 90 | &digest, &digest_len) != 0) { |
91 | error("%s: hash_buffer", __func__); | |
92 | goto out; | |
93 | } | |
94 | if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { | |
95 | error("%s: BN_bin2bn", __func__); | |
96 | goto out; | |
97 | } | |
98 | success = 0; | |
99 | SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); | |
100 | out: | |
101 | buffer_free(&b); | |
5adf6b9a | 102 | bzero(digest, digest_len); |
103 | xfree(digest); | |
104 | digest_len = 0; | |
105 | if (success == 0) | |
106 | return h; | |
107 | BN_clear_free(h); | |
108 | return NULL; | |
109 | } | |
110 | ||
111 | /* | |
112 | * Generate Schnorr signature to prove knowledge of private value 'x' used | |
113 | * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' | |
5b01421b | 114 | * using the hash function "evp_md". |
5adf6b9a | 115 | * 'idlen' bytes from 'id' will be included in the signature hash as an anti- |
116 | * replay salt. | |
5b01421b | 117 | * |
118 | * On success, 0 is returned. The signature values are returned as *e_p | |
119 | * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values. | |
120 | * On failure, -1 is returned. | |
5adf6b9a | 121 | */ |
122 | int | |
123 | schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, | |
5b01421b | 124 | const EVP_MD *evp_md, const BIGNUM *x, const BIGNUM *g_x, |
125 | const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p) | |
5adf6b9a | 126 | { |
127 | int success = -1; | |
5adf6b9a | 128 | BIGNUM *h, *tmp, *v, *g_v, *r; |
129 | BN_CTX *bn_ctx; | |
130 | ||
131 | SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); | |
132 | SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); | |
133 | ||
134 | /* Avoid degenerate cases: g^0 yields a spoofable signature */ | |
135 | if (BN_cmp(g_x, BN_value_one()) <= 0) { | |
136 | error("%s: g_x < 1", __func__); | |
137 | return -1; | |
138 | } | |
139 | ||
140 | h = g_v = r = tmp = v = NULL; | |
141 | if ((bn_ctx = BN_CTX_new()) == NULL) { | |
142 | error("%s: BN_CTX_new", __func__); | |
143 | goto out; | |
144 | } | |
145 | if ((g_v = BN_new()) == NULL || | |
146 | (r = BN_new()) == NULL || | |
147 | (tmp = BN_new()) == NULL) { | |
148 | error("%s: BN_new", __func__); | |
149 | goto out; | |
150 | } | |
151 | ||
152 | /* | |
153 | * v must be a random element of Zq, so 1 <= v < q | |
154 | * we also exclude v = 1, since g^1 looks dangerous | |
155 | */ | |
156 | if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { | |
157 | error("%s: bn_rand_range2", __func__); | |
158 | goto out; | |
159 | } | |
160 | SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); | |
161 | ||
162 | /* g_v = g^v mod p */ | |
163 | if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { | |
164 | error("%s: BN_mod_exp (g^v mod p)", __func__); | |
165 | goto out; | |
166 | } | |
167 | SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); | |
168 | ||
169 | /* h = H(g || g^v || g^x || id) */ | |
5b01421b | 170 | if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x, |
5adf6b9a | 171 | id, idlen)) == NULL) { |
172 | error("%s: schnorr_hash failed", __func__); | |
173 | goto out; | |
174 | } | |
175 | ||
176 | /* r = v - xh mod q */ | |
177 | if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { | |
178 | error("%s: BN_mod_mul (tmp = xv mod q)", __func__); | |
179 | goto out; | |
180 | } | |
181 | if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { | |
182 | error("%s: BN_mod_mul (r = v - tmp)", __func__); | |
183 | goto out; | |
184 | } | |
5b01421b | 185 | SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__)); |
5adf6b9a | 186 | SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); |
187 | ||
5b01421b | 188 | *e_p = g_v; |
189 | *r_p = r; | |
190 | ||
191 | success = 0; | |
192 | out: | |
193 | BN_CTX_free(bn_ctx); | |
194 | if (h != NULL) | |
195 | BN_clear_free(h); | |
196 | if (v != NULL) | |
197 | BN_clear_free(v); | |
198 | BN_clear_free(tmp); | |
199 | ||
200 | return success; | |
201 | } | |
202 | ||
203 | /* | |
204 | * Generate Schnorr signature to prove knowledge of private value 'x' used | |
205 | * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' | |
206 | * using a SHA256 hash. | |
207 | * 'idlen' bytes from 'id' will be included in the signature hash as an anti- | |
208 | * replay salt. | |
209 | * On success, 0 is returned and *siglen bytes of signature are returned in | |
210 | * *sig (caller to free). Returns -1 on failure. | |
211 | */ | |
212 | int | |
213 | schnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, | |
214 | const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, | |
215 | u_char **sig, u_int *siglen) | |
216 | { | |
217 | Buffer b; | |
218 | BIGNUM *r, *e; | |
219 | ||
220 | if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(), | |
221 | x, g_x, id, idlen, &r, &e) != 0) | |
222 | return -1; | |
223 | ||
224 | /* Signature is (e, r) */ | |
5adf6b9a | 225 | buffer_init(&b); |
226 | /* XXX sigtype-hash as string? */ | |
5b01421b | 227 | buffer_put_bignum2(&b, e); |
5adf6b9a | 228 | buffer_put_bignum2(&b, r); |
229 | *siglen = buffer_len(&b); | |
230 | *sig = xmalloc(*siglen); | |
231 | memcpy(*sig, buffer_ptr(&b), *siglen); | |
232 | SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), | |
233 | "%s: sigblob", __func__)); | |
234 | buffer_free(&b); | |
5b01421b | 235 | |
5adf6b9a | 236 | BN_clear_free(r); |
5b01421b | 237 | BN_clear_free(e); |
5adf6b9a | 238 | |
5b01421b | 239 | return 0; |
5adf6b9a | 240 | } |
241 | ||
242 | /* | |
5b01421b | 243 | * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against |
244 | * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and | |
245 | * 'grp_g' using hash "evp_md". | |
5adf6b9a | 246 | * Signature hash will be salted with 'idlen' bytes from 'id'. |
247 | * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. | |
248 | */ | |
249 | int | |
250 | schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, | |
5b01421b | 251 | const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen, |
252 | const BIGNUM *r, const BIGNUM *e) | |
5adf6b9a | 253 | { |
254 | int success = -1; | |
5b01421b | 255 | BIGNUM *h, *g_xh, *g_r, *expected; |
5adf6b9a | 256 | BN_CTX *bn_ctx; |
5adf6b9a | 257 | |
258 | SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); | |
259 | ||
260 | /* Avoid degenerate cases: g^0 yields a spoofable signature */ | |
261 | if (BN_cmp(g_x, BN_value_one()) <= 0) { | |
262 | error("%s: g_x < 1", __func__); | |
263 | return -1; | |
264 | } | |
265 | ||
5b01421b | 266 | h = g_xh = g_r = expected = NULL; |
5adf6b9a | 267 | if ((bn_ctx = BN_CTX_new()) == NULL) { |
268 | error("%s: BN_CTX_new", __func__); | |
269 | goto out; | |
270 | } | |
5b01421b | 271 | if ((g_xh = BN_new()) == NULL || |
5adf6b9a | 272 | (g_r = BN_new()) == NULL || |
273 | (expected = BN_new()) == NULL) { | |
274 | error("%s: BN_new", __func__); | |
275 | goto out; | |
276 | } | |
277 | ||
5b01421b | 278 | SCHNORR_DEBUG_BN((e, "%s: e = ", __func__)); |
5adf6b9a | 279 | SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); |
280 | ||
281 | /* h = H(g || g^v || g^x || id) */ | |
5b01421b | 282 | if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x, |
5adf6b9a | 283 | id, idlen)) == NULL) { |
284 | error("%s: schnorr_hash failed", __func__); | |
285 | goto out; | |
286 | } | |
287 | ||
288 | /* g_xh = (g^x)^h */ | |
289 | if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { | |
290 | error("%s: BN_mod_exp (g_x^h mod p)", __func__); | |
291 | goto out; | |
292 | } | |
293 | SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); | |
294 | ||
295 | /* g_r = g^r */ | |
296 | if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { | |
297 | error("%s: BN_mod_exp (g_x^h mod p)", __func__); | |
298 | goto out; | |
299 | } | |
300 | SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); | |
301 | ||
302 | /* expected = g^r * g_xh */ | |
303 | if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { | |
304 | error("%s: BN_mod_mul (expected = g_r mod p)", __func__); | |
305 | goto out; | |
306 | } | |
307 | SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); | |
308 | ||
5b01421b | 309 | /* Check e == expected */ |
310 | success = BN_cmp(expected, e) == 0; | |
5adf6b9a | 311 | out: |
312 | BN_CTX_free(bn_ctx); | |
313 | if (h != NULL) | |
314 | BN_clear_free(h); | |
5adf6b9a | 315 | BN_clear_free(g_xh); |
316 | BN_clear_free(g_r); | |
317 | BN_clear_free(expected); | |
318 | return success; | |
319 | } | |
320 | ||
5b01421b | 321 | /* |
322 | * Verify Schnorr signature 'sig' of length 'siglen' against public exponent | |
323 | * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a | |
324 | * SHA256 hash. | |
325 | * Signature hash will be salted with 'idlen' bytes from 'id'. | |
326 | * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. | |
327 | */ | |
328 | int | |
329 | schnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, | |
330 | const BIGNUM *grp_g, | |
331 | const BIGNUM *g_x, const u_char *id, u_int idlen, | |
332 | const u_char *sig, u_int siglen) | |
333 | { | |
334 | Buffer b; | |
335 | int ret = -1; | |
336 | u_int rlen; | |
337 | BIGNUM *r, *e; | |
338 | ||
339 | e = r = NULL; | |
340 | if ((e = BN_new()) == NULL || | |
341 | (r = BN_new()) == NULL) { | |
342 | error("%s: BN_new", __func__); | |
343 | goto out; | |
344 | } | |
345 | ||
346 | /* Extract g^v and r from signature blob */ | |
347 | buffer_init(&b); | |
348 | buffer_append(&b, sig, siglen); | |
349 | SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), | |
350 | "%s: sigblob", __func__)); | |
351 | buffer_get_bignum2(&b, e); | |
352 | buffer_get_bignum2(&b, r); | |
353 | rlen = buffer_len(&b); | |
354 | buffer_free(&b); | |
355 | if (rlen != 0) { | |
356 | error("%s: remaining bytes in signature %d", __func__, rlen); | |
357 | goto out; | |
358 | } | |
359 | ||
360 | ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(), | |
361 | g_x, id, idlen, r, e); | |
362 | out: | |
363 | BN_clear_free(e); | |
364 | BN_clear_free(r); | |
365 | ||
366 | return ret; | |
367 | } | |
368 | ||
369 | /* Helper functions */ | |
370 | ||
371 | /* | |
372 | * Generate uniformly distributed random number in range (1, high). | |
373 | * Return number on success, NULL on failure. | |
374 | */ | |
375 | BIGNUM * | |
376 | bn_rand_range_gt_one(const BIGNUM *high) | |
377 | { | |
378 | BIGNUM *r, *tmp; | |
379 | int success = -1; | |
380 | ||
381 | if ((tmp = BN_new()) == NULL) { | |
382 | error("%s: BN_new", __func__); | |
383 | return NULL; | |
384 | } | |
385 | if ((r = BN_new()) == NULL) { | |
386 | error("%s: BN_new failed", __func__); | |
387 | goto out; | |
388 | } | |
389 | if (BN_set_word(tmp, 2) != 1) { | |
390 | error("%s: BN_set_word(tmp, 2)", __func__); | |
391 | goto out; | |
392 | } | |
393 | if (BN_sub(tmp, high, tmp) == -1) { | |
394 | error("%s: BN_sub failed (tmp = high - 2)", __func__); | |
395 | goto out; | |
396 | } | |
397 | if (BN_rand_range(r, tmp) == -1) { | |
398 | error("%s: BN_rand_range failed", __func__); | |
399 | goto out; | |
400 | } | |
401 | if (BN_set_word(tmp, 2) != 1) { | |
402 | error("%s: BN_set_word(tmp, 2)", __func__); | |
403 | goto out; | |
404 | } | |
405 | if (BN_add(r, r, tmp) == -1) { | |
406 | error("%s: BN_add failed (r = r + 2)", __func__); | |
407 | goto out; | |
408 | } | |
409 | success = 0; | |
410 | out: | |
411 | BN_clear_free(tmp); | |
412 | if (success == 0) | |
413 | return r; | |
414 | BN_clear_free(r); | |
415 | return NULL; | |
416 | } | |
417 | ||
418 | /* | |
419 | * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success, | |
420 | * with digest via 'digestp' (caller to free) and length via 'lenp'. | |
421 | * Returns -1 on failure. | |
422 | */ | |
423 | int | |
424 | hash_buffer(const u_char *buf, u_int len, const EVP_MD *md, | |
425 | u_char **digestp, u_int *lenp) | |
426 | { | |
427 | u_char digest[EVP_MAX_MD_SIZE]; | |
428 | u_int digest_len; | |
429 | EVP_MD_CTX evp_md_ctx; | |
430 | int success = -1; | |
431 | ||
432 | EVP_MD_CTX_init(&evp_md_ctx); | |
433 | ||
434 | if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) { | |
435 | error("%s: EVP_DigestInit_ex", __func__); | |
436 | goto out; | |
437 | } | |
438 | if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) { | |
439 | error("%s: EVP_DigestUpdate", __func__); | |
440 | goto out; | |
441 | } | |
442 | if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) { | |
443 | error("%s: EVP_DigestFinal_ex", __func__); | |
444 | goto out; | |
445 | } | |
446 | *digestp = xmalloc(digest_len); | |
447 | *lenp = digest_len; | |
448 | memcpy(*digestp, digest, *lenp); | |
449 | success = 0; | |
450 | out: | |
451 | EVP_MD_CTX_cleanup(&evp_md_ctx); | |
452 | bzero(digest, sizeof(digest)); | |
453 | digest_len = 0; | |
454 | return success; | |
455 | } | |
456 | ||
457 | /* print formatted string followed by bignum */ | |
458 | void | |
459 | debug3_bn(const BIGNUM *n, const char *fmt, ...) | |
460 | { | |
461 | char *out, *h; | |
462 | va_list args; | |
463 | ||
464 | out = NULL; | |
465 | va_start(args, fmt); | |
466 | vasprintf(&out, fmt, args); | |
467 | va_end(args); | |
468 | if (out == NULL) | |
469 | fatal("%s: vasprintf failed", __func__); | |
470 | ||
471 | if (n == NULL) | |
472 | debug3("%s(null)", out); | |
473 | else { | |
474 | h = BN_bn2hex(n); | |
475 | debug3("%s0x%s", out, h); | |
476 | free(h); | |
477 | } | |
478 | free(out); | |
479 | } | |
480 | ||
481 | /* print formatted string followed by buffer contents in hex */ | |
482 | void | |
483 | debug3_buf(const u_char *buf, u_int len, const char *fmt, ...) | |
484 | { | |
485 | char *out, h[65]; | |
486 | u_int i, j; | |
487 | va_list args; | |
488 | ||
489 | out = NULL; | |
490 | va_start(args, fmt); | |
491 | vasprintf(&out, fmt, args); | |
492 | va_end(args); | |
493 | if (out == NULL) | |
494 | fatal("%s: vasprintf failed", __func__); | |
495 | ||
496 | debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : ""); | |
497 | free(out); | |
498 | if (buf == NULL) | |
499 | return; | |
500 | ||
501 | *h = '\0'; | |
502 | for (i = j = 0; i < len; i++) { | |
503 | snprintf(h + j, sizeof(h) - j, "%02x", buf[i]); | |
504 | j += 2; | |
505 | if (j >= sizeof(h) - 1 || i == len - 1) { | |
506 | debug3(" %s", h); | |
507 | *h = '\0'; | |
508 | j = 0; | |
509 | } | |
510 | } | |
511 | } | |
512 | ||
513 | /* | |
514 | * Construct a MODP group from hex strings p (which must be a safe | |
515 | * prime) and g, automatically calculating subgroup q as (p / 2) | |
516 | */ | |
517 | struct modp_group * | |
518 | modp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p) | |
519 | { | |
520 | struct modp_group *ret; | |
521 | ||
522 | ret = xmalloc(sizeof(*ret)); | |
523 | ret->p = ret->q = ret->g = NULL; | |
524 | if (BN_hex2bn(&ret->p, grp_p) == 0 || | |
525 | BN_hex2bn(&ret->g, grp_g) == 0) | |
526 | fatal("%s: BN_hex2bn", __func__); | |
527 | /* Subgroup order is p/2 (p is a safe prime) */ | |
528 | if ((ret->q = BN_new()) == NULL) | |
529 | fatal("%s: BN_new", __func__); | |
530 | if (BN_rshift1(ret->q, ret->p) != 1) | |
531 | fatal("%s: BN_rshift1", __func__); | |
532 | ||
533 | return ret; | |
534 | } | |
535 | ||
536 | void | |
537 | modp_group_free(struct modp_group *grp) | |
538 | { | |
539 | if (grp->g != NULL) | |
540 | BN_clear_free(grp->g); | |
541 | if (grp->p != NULL) | |
542 | BN_clear_free(grp->p); | |
543 | if (grp->q != NULL) | |
544 | BN_clear_free(grp->q); | |
545 | bzero(grp, sizeof(*grp)); | |
546 | xfree(grp); | |
547 | } | |
548 | ||
549 | /* main() function for self-test */ | |
550 | ||
5adf6b9a | 551 | #ifdef SCHNORR_MAIN |
552 | static void | |
553 | schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, | |
554 | const BIGNUM *grp_g, const BIGNUM *x) | |
555 | { | |
556 | BIGNUM *g_x; | |
557 | u_char *sig; | |
558 | u_int siglen; | |
559 | BN_CTX *bn_ctx; | |
560 | ||
561 | if ((bn_ctx = BN_CTX_new()) == NULL) | |
562 | fatal("%s: BN_CTX_new", __func__); | |
563 | if ((g_x = BN_new()) == NULL) | |
564 | fatal("%s: BN_new", __func__); | |
565 | ||
566 | if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) | |
567 | fatal("%s: g_x", __func__); | |
5b01421b | 568 | if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4, |
569 | &sig, &siglen)) | |
5adf6b9a | 570 | fatal("%s: schnorr_sign", __func__); |
5b01421b | 571 | if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, |
5adf6b9a | 572 | sig, siglen) != 1) |
573 | fatal("%s: verify fail", __func__); | |
5b01421b | 574 | if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4, |
5adf6b9a | 575 | sig, siglen) != 0) |
576 | fatal("%s: verify should have failed (bad ID)", __func__); | |
577 | sig[4] ^= 1; | |
5b01421b | 578 | if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, |
5adf6b9a | 579 | sig, siglen) != 0) |
580 | fatal("%s: verify should have failed (bit error)", __func__); | |
581 | xfree(sig); | |
582 | BN_free(g_x); | |
583 | BN_CTX_free(bn_ctx); | |
584 | } | |
585 | ||
586 | static void | |
587 | schnorr_selftest(void) | |
588 | { | |
589 | BIGNUM *x; | |
5b01421b | 590 | struct modp_group *grp; |
5adf6b9a | 591 | u_int i; |
592 | char *hh; | |
593 | ||
594 | grp = jpake_default_group(); | |
595 | if ((x = BN_new()) == NULL) | |
596 | fatal("%s: BN_new", __func__); | |
597 | SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); | |
598 | SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); | |
599 | SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); | |
600 | ||
601 | /* [1, 20) */ | |
602 | for (i = 1; i < 20; i++) { | |
603 | printf("x = %u\n", i); | |
604 | fflush(stdout); | |
605 | if (BN_set_word(x, i) != 1) | |
606 | fatal("%s: set x word", __func__); | |
607 | schnorr_selftest_one(grp->p, grp->q, grp->g, x); | |
608 | } | |
609 | ||
610 | /* 100 x random [0, p) */ | |
611 | for (i = 0; i < 100; i++) { | |
612 | if (BN_rand_range(x, grp->p) != 1) | |
613 | fatal("%s: BN_rand_range", __func__); | |
614 | hh = BN_bn2hex(x); | |
615 | printf("x = (random) 0x%s\n", hh); | |
616 | free(hh); | |
617 | fflush(stdout); | |
618 | schnorr_selftest_one(grp->p, grp->q, grp->g, x); | |
619 | } | |
620 | ||
621 | /* [q-20, q) */ | |
622 | if (BN_set_word(x, 20) != 1) | |
623 | fatal("%s: BN_set_word (x = 20)", __func__); | |
624 | if (BN_sub(x, grp->q, x) != 1) | |
625 | fatal("%s: BN_sub (q - x)", __func__); | |
626 | for (i = 0; i < 19; i++) { | |
627 | hh = BN_bn2hex(x); | |
628 | printf("x = (q - %d) 0x%s\n", 20 - i, hh); | |
629 | free(hh); | |
630 | fflush(stdout); | |
631 | schnorr_selftest_one(grp->p, grp->q, grp->g, x); | |
632 | if (BN_add(x, x, BN_value_one()) != 1) | |
633 | fatal("%s: BN_add (x + 1)", __func__); | |
634 | } | |
635 | BN_free(x); | |
636 | } | |
637 | ||
638 | int | |
639 | main(int argc, char **argv) | |
640 | { | |
641 | log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); | |
642 | ||
643 | schnorr_selftest(); | |
644 | return 0; | |
645 | } | |
646 | #endif | |
647 |