]>
Commit | Line | Data |
---|---|---|
ac450140 | 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 | */ | |
64 | static BIGNUM * | |
65 | schnorr_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__)); | |
326f21be | 94 | if (hash_buffer(buffer_ptr(&b), buffer_len(&b), (const EVP_MD *)EVP_sha256(), |
ac450140 | 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 | */ | |
125 | int | |
126 | schnorr_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 | */ | |
222 | int | |
223 | schnorr_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 | |
315 | static void | |
316 | schnorr_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 | ||
348 | static void | |
349 | schnorr_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 | ||
400 | int | |
401 | main(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 |