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