diff options
Diffstat (limited to 'schnorr.c')
| -rw-r--r-- | schnorr.c | 407 |
1 files changed, 407 insertions, 0 deletions
diff --git a/schnorr.c b/schnorr.c new file mode 100644 index 000000000..e3abe5702 --- /dev/null +++ b/schnorr.c @@ -0,0 +1,407 @@ +/* $OpenBSD: schnorr.c,v 1.1 2008/11/04 08:22:13 djm Exp $ */ +/* + * Copyright (c) 2008 Damien Miller. All rights reserved. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +/* + * Implementation of Schnorr signatures / zero-knowledge proofs, based on + * description in: + * + * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling", + * 16th Workshop on Security Protocols, Cambridge, April 2008 + * + * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf + */ + +#include "includes.h" + +#include <sys/types.h> + +#include <string.h> +#include <stdarg.h> +#include <stdio.h> + +#include <openssl/evp.h> +#include <openssl/bn.h> + +#include "xmalloc.h" +#include "buffer.h" +#include "log.h" + +#include "jpake.h" + +/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ +/* #define SCHNORR_MAIN */ /* Include main() selftest */ + +/* XXX */ +/* Parametise signature hash? (sha256, sha1, etc.) */ +/* Signature format - include type name, hash type, group params? */ + +#ifndef SCHNORR_DEBUG +# define SCHNORR_DEBUG_BN(a) +# define SCHNORR_DEBUG_BUF(a) +#else +# define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a +# define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a +#endif /* SCHNORR_DEBUG */ + +/* + * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) + * using SHA1. Returns signature as bignum or NULL on error. + */ +static BIGNUM * +schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, + const BIGNUM *g_v, const BIGNUM *g_x, + const u_char *id, u_int idlen) +{ + u_char *digest; + u_int digest_len; + BIGNUM *h; + EVP_MD_CTX evp_md_ctx; + Buffer b; + int success = -1; + + if ((h = BN_new()) == NULL) { + error("%s: BN_new", __func__); + return NULL; + } + + buffer_init(&b); + EVP_MD_CTX_init(&evp_md_ctx); + + /* h = H(g || g^v || g^x || id) */ + buffer_put_bignum2(&b, g); + buffer_put_bignum2(&b, g_v); + buffer_put_bignum2(&b, g_x); + buffer_put_string(&b, id, idlen); + + SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), + "%s: hashblob", __func__)); + if (hash_buffer(buffer_ptr(&b), buffer_len(&b), EVP_sha256(), + &digest, &digest_len) != 0) { + error("%s: hash_buffer", __func__); + goto out; + } + if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { + error("%s: BN_bin2bn", __func__); + goto out; + } + success = 0; + SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); + out: + buffer_free(&b); + EVP_MD_CTX_cleanup(&evp_md_ctx); + bzero(digest, digest_len); + xfree(digest); + digest_len = 0; + if (success == 0) + return h; + BN_clear_free(h); + return NULL; +} + +/* + * Generate Schnorr signature to prove knowledge of private value 'x' used + * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' + * 'idlen' bytes from 'id' will be included in the signature hash as an anti- + * replay salt. + * On success, 0 is returned and *siglen bytes of signature are returned in + * *sig (caller to free). Returns -1 on failure. + */ +int +schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, + const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, + u_char **sig, u_int *siglen) +{ + int success = -1; + Buffer b; + BIGNUM *h, *tmp, *v, *g_v, *r; + BN_CTX *bn_ctx; + + SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); + SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); + + /* Avoid degenerate cases: g^0 yields a spoofable signature */ + if (BN_cmp(g_x, BN_value_one()) <= 0) { + error("%s: g_x < 1", __func__); + return -1; + } + + h = g_v = r = tmp = v = NULL; + if ((bn_ctx = BN_CTX_new()) == NULL) { + error("%s: BN_CTX_new", __func__); + goto out; + } + if ((g_v = BN_new()) == NULL || + (r = BN_new()) == NULL || + (tmp = BN_new()) == NULL) { + error("%s: BN_new", __func__); + goto out; + } + + /* + * v must be a random element of Zq, so 1 <= v < q + * we also exclude v = 1, since g^1 looks dangerous + */ + if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { + error("%s: bn_rand_range2", __func__); + goto out; + } + SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); + + /* g_v = g^v mod p */ + if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { + error("%s: BN_mod_exp (g^v mod p)", __func__); + goto out; + } + SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); + + /* h = H(g || g^v || g^x || id) */ + if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, + id, idlen)) == NULL) { + error("%s: schnorr_hash failed", __func__); + goto out; + } + + /* r = v - xh mod q */ + if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { + error("%s: BN_mod_mul (tmp = xv mod q)", __func__); + goto out; + } + if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { + error("%s: BN_mod_mul (r = v - tmp)", __func__); + goto out; + } + SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); + + /* Signature is (g_v, r) */ + buffer_init(&b); + /* XXX sigtype-hash as string? */ + buffer_put_bignum2(&b, g_v); + buffer_put_bignum2(&b, r); + *siglen = buffer_len(&b); + *sig = xmalloc(*siglen); + memcpy(*sig, buffer_ptr(&b), *siglen); + SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), + "%s: sigblob", __func__)); + buffer_free(&b); + success = 0; + out: + BN_CTX_free(bn_ctx); + if (h != NULL) + BN_clear_free(h); + if (v != NULL) + BN_clear_free(v); + BN_clear_free(r); + BN_clear_free(g_v); + BN_clear_free(tmp); + + return success; +} + +/* + * Verify Schnorr signature 'sig' of length 'siglen' against public exponent + * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'. + * Signature hash will be salted with 'idlen' bytes from 'id'. + * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. + */ +int +schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, + const BIGNUM *g_x, const u_char *id, u_int idlen, + const u_char *sig, u_int siglen) +{ + int success = -1; + Buffer b; + BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected; + BN_CTX *bn_ctx; + u_int rlen; + + SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); + + /* Avoid degenerate cases: g^0 yields a spoofable signature */ + if (BN_cmp(g_x, BN_value_one()) <= 0) { + error("%s: g_x < 1", __func__); + return -1; + } + + g_v = h = r = g_xh = g_r = expected = NULL; + if ((bn_ctx = BN_CTX_new()) == NULL) { + error("%s: BN_CTX_new", __func__); + goto out; + } + if ((g_v = BN_new()) == NULL || + (r = BN_new()) == NULL || + (g_xh = BN_new()) == NULL || + (g_r = BN_new()) == NULL || + (expected = BN_new()) == NULL) { + error("%s: BN_new", __func__); + goto out; + } + + /* Extract g^v and r from signature blob */ + buffer_init(&b); + buffer_append(&b, sig, siglen); + SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), + "%s: sigblob", __func__)); + buffer_get_bignum2(&b, g_v); + buffer_get_bignum2(&b, r); + rlen = buffer_len(&b); + buffer_free(&b); + if (rlen != 0) { + error("%s: remaining bytes in signature %d", __func__, rlen); + goto out; + } + buffer_free(&b); + SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); + SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); + + /* h = H(g || g^v || g^x || id) */ + if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, + id, idlen)) == NULL) { + error("%s: schnorr_hash failed", __func__); + goto out; + } + + /* g_xh = (g^x)^h */ + if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { + error("%s: BN_mod_exp (g_x^h mod p)", __func__); + goto out; + } + SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); + + /* g_r = g^r */ + if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { + error("%s: BN_mod_exp (g_x^h mod p)", __func__); + goto out; + } + SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); + + /* expected = g^r * g_xh */ + if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { + error("%s: BN_mod_mul (expected = g_r mod p)", __func__); + goto out; + } + SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); + + /* Check g_v == expected */ + success = BN_cmp(expected, g_v) == 0; + out: + BN_CTX_free(bn_ctx); + if (h != NULL) + BN_clear_free(h); + BN_clear_free(g_v); + BN_clear_free(r); + BN_clear_free(g_xh); + BN_clear_free(g_r); + BN_clear_free(expected); + return success; +} + +#ifdef SCHNORR_MAIN +static void +schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, + const BIGNUM *grp_g, const BIGNUM *x) +{ + BIGNUM *g_x; + u_char *sig; + u_int siglen; + BN_CTX *bn_ctx; + + if ((bn_ctx = BN_CTX_new()) == NULL) + fatal("%s: BN_CTX_new", __func__); + if ((g_x = BN_new()) == NULL) + fatal("%s: BN_new", __func__); + + if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) + fatal("%s: g_x", __func__); + if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen)) + fatal("%s: schnorr_sign", __func__); + if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, + sig, siglen) != 1) + fatal("%s: verify fail", __func__); + if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4, + sig, siglen) != 0) + fatal("%s: verify should have failed (bad ID)", __func__); + sig[4] ^= 1; + if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, + sig, siglen) != 0) + fatal("%s: verify should have failed (bit error)", __func__); + xfree(sig); + BN_free(g_x); + BN_CTX_free(bn_ctx); +} + +static void +schnorr_selftest(void) +{ + BIGNUM *x; + struct jpake_group *grp; + u_int i; + char *hh; + + grp = jpake_default_group(); + if ((x = BN_new()) == NULL) + fatal("%s: BN_new", __func__); + SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); + SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); + SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); + + /* [1, 20) */ + for (i = 1; i < 20; i++) { + printf("x = %u\n", i); + fflush(stdout); + if (BN_set_word(x, i) != 1) + fatal("%s: set x word", __func__); + schnorr_selftest_one(grp->p, grp->q, grp->g, x); + } + + /* 100 x random [0, p) */ + for (i = 0; i < 100; i++) { + if (BN_rand_range(x, grp->p) != 1) + fatal("%s: BN_rand_range", __func__); + hh = BN_bn2hex(x); + printf("x = (random) 0x%s\n", hh); + free(hh); + fflush(stdout); + schnorr_selftest_one(grp->p, grp->q, grp->g, x); + } + + /* [q-20, q) */ + if (BN_set_word(x, 20) != 1) + fatal("%s: BN_set_word (x = 20)", __func__); + if (BN_sub(x, grp->q, x) != 1) + fatal("%s: BN_sub (q - x)", __func__); + for (i = 0; i < 19; i++) { + hh = BN_bn2hex(x); + printf("x = (q - %d) 0x%s\n", 20 - i, hh); + free(hh); + fflush(stdout); + schnorr_selftest_one(grp->p, grp->q, grp->g, x); + if (BN_add(x, x, BN_value_one()) != 1) + fatal("%s: BN_add (x + 1)", __func__); + } + BN_free(x); +} + +int +main(int argc, char **argv) +{ + log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); + + schnorr_selftest(); + return 0; +} +#endif + |