40
40
#include "buffer.h"
45
#include "openbsd-compat/openssl-compat.h"
45
47
/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */
46
48
/* #define SCHNORR_MAIN */ /* Include main() selftest */
49
/* Parametise signature hash? (sha256, sha1, etc.) */
50
/* Signature format - include type name, hash type, group params? */
52
50
#ifndef SCHNORR_DEBUG
53
51
# define SCHNORR_DEBUG_BN(a)
54
52
# define SCHNORR_DEBUG_BUF(a)
56
# define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a
57
# define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a
54
# define SCHNORR_DEBUG_BN(a) debug3_bn a
55
# define SCHNORR_DEBUG_BUF(a) debug3_buf a
58
56
#endif /* SCHNORR_DEBUG */
61
59
* Calculate hash component of Schnorr signature H(g || g^v || g^x || id)
62
* using SHA1. Returns signature as bignum or NULL on error.
60
* using the hash function defined by "evp_md". Returns signature as
61
* bignum or NULL on error.
65
64
schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g,
66
const BIGNUM *g_v, const BIGNUM *g_x,
65
const EVP_MD *evp_md, const BIGNUM *g_v, const BIGNUM *g_x,
67
66
const u_char *id, u_int idlen)
72
EVP_MD_CTX evp_md_ctx;
118
114
* Generate Schnorr signature to prove knowledge of private value 'x' used
119
115
* in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g'
116
* using the hash function "evp_md".
120
117
* 'idlen' bytes from 'id' will be included in the signature hash as an anti-
122
* On success, 0 is returned and *siglen bytes of signature are returned in
123
* *sig (caller to free). Returns -1 on failure.
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.
126
125
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)
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)
130
129
int success = -1;
132
130
BIGNUM *h, *tmp, *v, *g_v, *r;
186
184
error("%s: BN_mod_mul (r = v - tmp)", __func__);
187
SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__));
189
188
SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
191
/* Signature is (g_v, r) */
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-
211
* On success, 0 is returned and *siglen bytes of signature are returned in
212
* *sig (caller to free). Returns -1 on failure.
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)
222
if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(),
223
x, g_x, id, idlen, &r, &e) != 0)
226
/* Signature is (e, r) */
193
228
/* XXX sigtype-hash as string? */
194
buffer_put_bignum2(&b, g_v);
229
buffer_put_bignum2(&b, e);
195
230
buffer_put_bignum2(&b, r);
196
231
*siglen = buffer_len(&b);
197
232
*sig = xmalloc(*siglen);
199
234
SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b),
200
235
"%s: sigblob", __func__));
209
238
BN_clear_free(r);
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'.
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".
219
248
* Signature hash will be salted with 'idlen' bytes from 'id'.
220
249
* Returns -1 on failure, 0 on incorrect signature or 1 on matching signature.
223
252
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)
253
const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen,
254
const BIGNUM *r, const BIGNUM *e)
227
256
int success = -1;
229
BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected;
257
BIGNUM *h, *g_xh, *g_r, *expected;
233
260
SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__));
241
g_v = h = r = g_xh = g_r = expected = NULL;
268
h = g_xh = g_r = expected = NULL;
242
269
if ((bn_ctx = BN_CTX_new()) == NULL) {
243
270
error("%s: BN_CTX_new", __func__);
246
if ((g_v = BN_new()) == NULL ||
247
(r = BN_new()) == NULL ||
248
(g_xh = BN_new()) == NULL ||
273
if ((g_xh = BN_new()) == NULL ||
249
274
(g_r = BN_new()) == NULL ||
250
275
(expected = BN_new()) == NULL) {
251
276
error("%s: BN_new", __func__);
255
/* Extract g^v and r from signature blob */
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);
265
error("%s: remaining bytes in signature %d", __func__, rlen);
269
SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__));
280
SCHNORR_DEBUG_BN((e, "%s: e = ", __func__));
270
281
SCHNORR_DEBUG_BN((r, "%s: r = ", __func__));
272
283
/* h = H(g || g^v || g^x || id) */
273
if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x,
284
if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x,
274
285
id, idlen)) == NULL) {
275
286
error("%s: schnorr_hash failed", __func__);
298
309
SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__));
300
/* Check g_v == expected */
301
success = BN_cmp(expected, g_v) == 0;
311
/* Check e == expected */
312
success = BN_cmp(expected, e) == 0;
303
314
BN_CTX_free(bn_ctx);
305
316
BN_clear_free(h);
308
317
BN_clear_free(g_xh);
309
318
BN_clear_free(g_r);
310
319
BN_clear_free(expected);
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
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.
331
schnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q,
333
const BIGNUM *g_x, const u_char *id, u_int idlen,
334
const u_char *sig, u_int siglen)
342
if ((e = BN_new()) == NULL ||
343
(r = BN_new()) == NULL) {
344
error("%s: BN_new", __func__);
348
/* Extract g^v and r from signature blob */
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);
358
error("%s: remaining bytes in signature %d", __func__, rlen);
362
ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(),
363
g_x, id, idlen, r, e);
371
/* Helper functions */
374
* Generate uniformly distributed random number in range (1, high).
375
* Return number on success, NULL on failure.
378
bn_rand_range_gt_one(const BIGNUM *high)
383
if ((tmp = BN_new()) == NULL) {
384
error("%s: BN_new", __func__);
387
if ((r = BN_new()) == NULL) {
388
error("%s: BN_new failed", __func__);
391
if (BN_set_word(tmp, 2) != 1) {
392
error("%s: BN_set_word(tmp, 2)", __func__);
395
if (BN_sub(tmp, high, tmp) == -1) {
396
error("%s: BN_sub failed (tmp = high - 2)", __func__);
399
if (BN_rand_range(r, tmp) == -1) {
400
error("%s: BN_rand_range failed", __func__);
403
if (BN_set_word(tmp, 2) != 1) {
404
error("%s: BN_set_word(tmp, 2)", __func__);
407
if (BN_add(r, r, tmp) == -1) {
408
error("%s: BN_add failed (r = r + 2)", __func__);
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.
426
hash_buffer(const u_char *buf, u_int len, const EVP_MD *md,
427
u_char **digestp, u_int *lenp)
429
u_char digest[EVP_MAX_MD_SIZE];
431
EVP_MD_CTX evp_md_ctx;
434
EVP_MD_CTX_init(&evp_md_ctx);
436
if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) {
437
error("%s: EVP_DigestInit_ex", __func__);
440
if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) {
441
error("%s: EVP_DigestUpdate", __func__);
444
if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) {
445
error("%s: EVP_DigestFinal_ex", __func__);
448
*digestp = xmalloc(digest_len);
450
memcpy(*digestp, digest, *lenp);
453
EVP_MD_CTX_cleanup(&evp_md_ctx);
454
bzero(digest, sizeof(digest));
459
/* print formatted string followed by bignum */
461
debug3_bn(const BIGNUM *n, const char *fmt, ...)
468
vasprintf(&out, fmt, args);
471
fatal("%s: vasprintf failed", __func__);
474
debug3("%s(null)", out);
477
debug3("%s0x%s", out, h);
483
/* print formatted string followed by buffer contents in hex */
485
debug3_buf(const u_char *buf, u_int len, const char *fmt, ...)
493
vasprintf(&out, fmt, args);
496
fatal("%s: vasprintf failed", __func__);
498
debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : "");
504
for (i = j = 0; i < len; i++) {
505
snprintf(h + j, sizeof(h) - j, "%02x", buf[i]);
507
if (j >= sizeof(h) - 1 || i == len - 1) {
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)
520
modp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p)
522
struct modp_group *ret;
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__);
539
modp_group_free(struct modp_group *grp)
542
BN_clear_free(grp->g);
544
BN_clear_free(grp->p);
546
BN_clear_free(grp->q);
547
bzero(grp, sizeof(*grp));
551
/* main() function for self-test */
314
553
#ifdef SCHNORR_MAIN
316
555
schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q,
329
568
if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1)
330
569
fatal("%s: g_x", __func__);
331
if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen))
570
if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4,
332
572
fatal("%s: schnorr_sign", __func__);
333
if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
573
if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
334
574
sig, siglen) != 1)
335
575
fatal("%s: verify fail", __func__);
336
if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
576
if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4,
337
577
sig, siglen) != 0)
338
578
fatal("%s: verify should have failed (bad ID)", __func__);
340
if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4,
580
if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4,
341
581
sig, siglen) != 0)
342
582
fatal("%s: verify should have failed (bit error)", __func__);