]>
Commit | Line | Data |
---|---|---|
5adf6b9a | 1 | /* $OpenBSD: schnorr.c,v 1.1 2008/11/04 08:22:13 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 || g^v || g^x || id) */ | |
85 | buffer_put_bignum2(&b, g); | |
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), EVP_sha256(), | |
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 | EVP_MD_CTX_cleanup(&evp_md_ctx); | |
106 | bzero(digest, digest_len); | |
107 | xfree(digest); | |
108 | digest_len = 0; | |
109 | if (success == 0) | |
110 | return h; | |
111 | BN_clear_free(h); | |
112 | return NULL; | |
113 | } | |
114 | ||
115 | /* | |
116 | * Generate Schnorr signature to prove knowledge of private value 'x' used | |
117 | * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' | |
118 | * 'idlen' bytes from 'id' will be included in the signature hash as an anti- | |
119 | * replay salt. | |
120 | * On success, 0 is returned and *siglen bytes of signature are returned in | |
121 | * *sig (caller to free). Returns -1 on failure. | |
122 | */ | |
123 | int | |
124 | schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, | |
125 | const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, | |
126 | u_char **sig, u_int *siglen) | |
127 | { | |
128 | int success = -1; | |
129 | Buffer b; | |
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) */ | |
172 | if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, | |
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 | } | |
187 | SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); | |
188 | ||
189 | /* Signature is (g_v, r) */ | |
190 | buffer_init(&b); | |
191 | /* XXX sigtype-hash as string? */ | |
192 | buffer_put_bignum2(&b, g_v); | |
193 | buffer_put_bignum2(&b, r); | |
194 | *siglen = buffer_len(&b); | |
195 | *sig = xmalloc(*siglen); | |
196 | memcpy(*sig, buffer_ptr(&b), *siglen); | |
197 | SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), | |
198 | "%s: sigblob", __func__)); | |
199 | buffer_free(&b); | |
200 | success = 0; | |
201 | out: | |
202 | BN_CTX_free(bn_ctx); | |
203 | if (h != NULL) | |
204 | BN_clear_free(h); | |
205 | if (v != NULL) | |
206 | BN_clear_free(v); | |
207 | BN_clear_free(r); | |
208 | BN_clear_free(g_v); | |
209 | BN_clear_free(tmp); | |
210 | ||
211 | return success; | |
212 | } | |
213 | ||
214 | /* | |
215 | * Verify Schnorr signature 'sig' of length 'siglen' against public exponent | |
216 | * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'. | |
217 | * Signature hash will be salted with 'idlen' bytes from 'id'. | |
218 | * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. | |
219 | */ | |
220 | int | |
221 | schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, | |
222 | const BIGNUM *g_x, const u_char *id, u_int idlen, | |
223 | const u_char *sig, u_int siglen) | |
224 | { | |
225 | int success = -1; | |
226 | Buffer b; | |
227 | BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected; | |
228 | BN_CTX *bn_ctx; | |
229 | u_int rlen; | |
230 | ||
231 | SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); | |
232 | ||
233 | /* Avoid degenerate cases: g^0 yields a spoofable signature */ | |
234 | if (BN_cmp(g_x, BN_value_one()) <= 0) { | |
235 | error("%s: g_x < 1", __func__); | |
236 | return -1; | |
237 | } | |
238 | ||
239 | g_v = h = r = g_xh = g_r = expected = NULL; | |
240 | if ((bn_ctx = BN_CTX_new()) == NULL) { | |
241 | error("%s: BN_CTX_new", __func__); | |
242 | goto out; | |
243 | } | |
244 | if ((g_v = BN_new()) == NULL || | |
245 | (r = BN_new()) == NULL || | |
246 | (g_xh = BN_new()) == NULL || | |
247 | (g_r = BN_new()) == NULL || | |
248 | (expected = BN_new()) == NULL) { | |
249 | error("%s: BN_new", __func__); | |
250 | goto out; | |
251 | } | |
252 | ||
253 | /* Extract g^v and r from signature blob */ | |
254 | buffer_init(&b); | |
255 | buffer_append(&b, sig, siglen); | |
256 | SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), | |
257 | "%s: sigblob", __func__)); | |
258 | buffer_get_bignum2(&b, g_v); | |
259 | buffer_get_bignum2(&b, r); | |
260 | rlen = buffer_len(&b); | |
261 | buffer_free(&b); | |
262 | if (rlen != 0) { | |
263 | error("%s: remaining bytes in signature %d", __func__, rlen); | |
264 | goto out; | |
265 | } | |
266 | buffer_free(&b); | |
267 | SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); | |
268 | SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); | |
269 | ||
270 | /* h = H(g || g^v || g^x || id) */ | |
271 | if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, | |
272 | id, idlen)) == NULL) { | |
273 | error("%s: schnorr_hash failed", __func__); | |
274 | goto out; | |
275 | } | |
276 | ||
277 | /* g_xh = (g^x)^h */ | |
278 | if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { | |
279 | error("%s: BN_mod_exp (g_x^h mod p)", __func__); | |
280 | goto out; | |
281 | } | |
282 | SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); | |
283 | ||
284 | /* g_r = g^r */ | |
285 | if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { | |
286 | error("%s: BN_mod_exp (g_x^h mod p)", __func__); | |
287 | goto out; | |
288 | } | |
289 | SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); | |
290 | ||
291 | /* expected = g^r * g_xh */ | |
292 | if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { | |
293 | error("%s: BN_mod_mul (expected = g_r mod p)", __func__); | |
294 | goto out; | |
295 | } | |
296 | SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); | |
297 | ||
298 | /* Check g_v == expected */ | |
299 | success = BN_cmp(expected, g_v) == 0; | |
300 | out: | |
301 | BN_CTX_free(bn_ctx); | |
302 | if (h != NULL) | |
303 | BN_clear_free(h); | |
304 | BN_clear_free(g_v); | |
305 | BN_clear_free(r); | |
306 | BN_clear_free(g_xh); | |
307 | BN_clear_free(g_r); | |
308 | BN_clear_free(expected); | |
309 | return success; | |
310 | } | |
311 | ||
312 | #ifdef SCHNORR_MAIN | |
313 | static void | |
314 | schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, | |
315 | const BIGNUM *grp_g, const BIGNUM *x) | |
316 | { | |
317 | BIGNUM *g_x; | |
318 | u_char *sig; | |
319 | u_int siglen; | |
320 | BN_CTX *bn_ctx; | |
321 | ||
322 | if ((bn_ctx = BN_CTX_new()) == NULL) | |
323 | fatal("%s: BN_CTX_new", __func__); | |
324 | if ((g_x = BN_new()) == NULL) | |
325 | fatal("%s: BN_new", __func__); | |
326 | ||
327 | if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) | |
328 | fatal("%s: g_x", __func__); | |
329 | if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen)) | |
330 | fatal("%s: schnorr_sign", __func__); | |
331 | if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, | |
332 | sig, siglen) != 1) | |
333 | fatal("%s: verify fail", __func__); | |
334 | if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4, | |
335 | sig, siglen) != 0) | |
336 | fatal("%s: verify should have failed (bad ID)", __func__); | |
337 | sig[4] ^= 1; | |
338 | if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, | |
339 | sig, siglen) != 0) | |
340 | fatal("%s: verify should have failed (bit error)", __func__); | |
341 | xfree(sig); | |
342 | BN_free(g_x); | |
343 | BN_CTX_free(bn_ctx); | |
344 | } | |
345 | ||
346 | static void | |
347 | schnorr_selftest(void) | |
348 | { | |
349 | BIGNUM *x; | |
350 | struct jpake_group *grp; | |
351 | u_int i; | |
352 | char *hh; | |
353 | ||
354 | grp = jpake_default_group(); | |
355 | if ((x = BN_new()) == NULL) | |
356 | fatal("%s: BN_new", __func__); | |
357 | SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); | |
358 | SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); | |
359 | SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); | |
360 | ||
361 | /* [1, 20) */ | |
362 | for (i = 1; i < 20; i++) { | |
363 | printf("x = %u\n", i); | |
364 | fflush(stdout); | |
365 | if (BN_set_word(x, i) != 1) | |
366 | fatal("%s: set x word", __func__); | |
367 | schnorr_selftest_one(grp->p, grp->q, grp->g, x); | |
368 | } | |
369 | ||
370 | /* 100 x random [0, p) */ | |
371 | for (i = 0; i < 100; i++) { | |
372 | if (BN_rand_range(x, grp->p) != 1) | |
373 | fatal("%s: BN_rand_range", __func__); | |
374 | hh = BN_bn2hex(x); | |
375 | printf("x = (random) 0x%s\n", hh); | |
376 | free(hh); | |
377 | fflush(stdout); | |
378 | schnorr_selftest_one(grp->p, grp->q, grp->g, x); | |
379 | } | |
380 | ||
381 | /* [q-20, q) */ | |
382 | if (BN_set_word(x, 20) != 1) | |
383 | fatal("%s: BN_set_word (x = 20)", __func__); | |
384 | if (BN_sub(x, grp->q, x) != 1) | |
385 | fatal("%s: BN_sub (q - x)", __func__); | |
386 | for (i = 0; i < 19; i++) { | |
387 | hh = BN_bn2hex(x); | |
388 | printf("x = (q - %d) 0x%s\n", 20 - i, hh); | |
389 | free(hh); | |
390 | fflush(stdout); | |
391 | schnorr_selftest_one(grp->p, grp->q, grp->g, x); | |
392 | if (BN_add(x, x, BN_value_one()) != 1) | |
393 | fatal("%s: BN_add (x + 1)", __func__); | |
394 | } | |
395 | BN_free(x); | |
396 | } | |
397 | ||
398 | int | |
399 | main(int argc, char **argv) | |
400 | { | |
401 | log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); | |
402 | ||
403 | schnorr_selftest(); | |
404 | return 0; | |
405 | } | |
406 | #endif | |
407 |