Annotation of src/usr.bin/ssh/schnorr.c, Revision 1.2
1.2 ! djm 1: /* $OpenBSD: schnorr.c,v 1.1 2008/11/04 08:22:13 djm Exp $ */
1.1 djm 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 <sys/types.h>
29:
30: #include <string.h>
31: #include <stdarg.h>
32: #include <stdio.h>
33:
34: #include <openssl/evp.h>
35: #include <openssl/bn.h>
36:
37: #include "xmalloc.h"
38: #include "buffer.h"
39: #include "log.h"
40:
41: #include "jpake.h"
42:
43: /* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */
44: /* #define SCHNORR_MAIN */ /* Include main() selftest */
45:
46: /* XXX */
47: /* Parametise signature hash? (sha256, sha1, etc.) */
48: /* Signature format - include type name, hash type, group params? */
49:
50: #ifndef SCHNORR_DEBUG
51: # define SCHNORR_DEBUG_BN(a)
52: # define SCHNORR_DEBUG_BUF(a)
53: #else
54: # define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a
55: # define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a
56: #endif /* SCHNORR_DEBUG */
57:
58: /*
59: * Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
60: * using SHA1. Returns signature as bignum or NULL on error.
61: */
62: static BIGNUM *
63: schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
64: const BIGNUM *g_v, const BIGNUM *g_x,
65: const u_char *id, u_int idlen)
66: {
67: u_char *digest;
68: u_int digest_len;
69: BIGNUM *h;
70: EVP_MD_CTX evp_md_ctx;
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);
80: EVP_MD_CTX_init(&evp_md_ctx);
81:
1.2 ! djm 82: /* h = H(g || p || q || g^v || g^x || id) */
1.1 djm 83: buffer_put_bignum2(&b, g);
1.2 ! djm 84: buffer_put_bignum2(&b, p);
! 85: buffer_put_bignum2(&b, q);
1.1 djm 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:
![[BACK]](/icons/back.gif){kind=icon}
Return to schnorr.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / ssh