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