schnorr.c revision 192595
1/* $OpenBSD: schnorr.c,v 1.2 2009/02/18 04:31:21 djm Exp $ */ 2/* $FreeBSD: head/crypto/openssh/schnorr.c 192595 2009-05-22 18:46:28Z des $ */ 3/* 4 * Copyright (c) 2008 Damien Miller. All rights reserved. 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19/* 20 * Implementation of Schnorr signatures / zero-knowledge proofs, based on 21 * description in: 22 * 23 * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling", 24 * 16th Workshop on Security Protocols, Cambridge, April 2008 25 * 26 * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf 27 */ 28 29#include "includes.h" 30 31#include <sys/types.h> 32 33#include <string.h> 34#include <stdarg.h> 35#include <stdio.h> 36 37#include <openssl/evp.h> 38#include <openssl/bn.h> 39 40#include "xmalloc.h" 41#include "buffer.h" 42#include "log.h" 43 44#include "jpake.h" 45 46#ifdef JPAKE 47 48/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ 49/* #define SCHNORR_MAIN */ /* Include main() selftest */ 50 51/* XXX */ 52/* Parametise signature hash? (sha256, sha1, etc.) */ 53/* Signature format - include type name, hash type, group params? */ 54 55#ifndef SCHNORR_DEBUG 56# define SCHNORR_DEBUG_BN(a) 57# define SCHNORR_DEBUG_BUF(a) 58#else 59# define SCHNORR_DEBUG_BN(a) jpake_debug3_bn a 60# define SCHNORR_DEBUG_BUF(a) jpake_debug3_buf a 61#endif /* SCHNORR_DEBUG */ 62 63/* 64 * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) 65 * using SHA1. Returns signature as bignum or NULL on error. 66 */ 67static BIGNUM * 68schnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, 69 const BIGNUM *g_v, const BIGNUM *g_x, 70 const u_char *id, u_int idlen) 71{ 72 u_char *digest; 73 u_int digest_len; 74 BIGNUM *h; 75 EVP_MD_CTX evp_md_ctx; 76 Buffer b; 77 int success = -1; 78 79 if ((h = BN_new()) == NULL) { 80 error("%s: BN_new", __func__); 81 return NULL; 82 } 83 84 buffer_init(&b); 85 EVP_MD_CTX_init(&evp_md_ctx); 86 87 /* h = H(g || p || q || g^v || g^x || id) */ 88 buffer_put_bignum2(&b, g); 89 buffer_put_bignum2(&b, p); 90 buffer_put_bignum2(&b, q); 91 buffer_put_bignum2(&b, g_v); 92 buffer_put_bignum2(&b, g_x); 93 buffer_put_string(&b, id, idlen); 94 95 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 96 "%s: hashblob", __func__)); 97 if (hash_buffer(buffer_ptr(&b), buffer_len(&b), EVP_sha256(), 98 &digest, &digest_len) != 0) { 99 error("%s: hash_buffer", __func__); 100 goto out; 101 } 102 if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { 103 error("%s: BN_bin2bn", __func__); 104 goto out; 105 } 106 success = 0; 107 SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); 108 out: 109 buffer_free(&b); 110 EVP_MD_CTX_cleanup(&evp_md_ctx); 111 bzero(digest, digest_len); 112 xfree(digest); 113 digest_len = 0; 114 if (success == 0) 115 return h; 116 BN_clear_free(h); 117 return NULL; 118} 119 120/* 121 * Generate Schnorr signature to prove knowledge of private value 'x' used 122 * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 123 * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 124 * replay salt. 125 * On success, 0 is returned and *siglen bytes of signature are returned in 126 * *sig (caller to free). Returns -1 on failure. 127 */ 128int 129schnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 130 const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, 131 u_char **sig, u_int *siglen) 132{ 133 int success = -1; 134 Buffer b; 135 BIGNUM *h, *tmp, *v, *g_v, *r; 136 BN_CTX *bn_ctx; 137 138 SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); 139 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 140 141 /* Avoid degenerate cases: g^0 yields a spoofable signature */ 142 if (BN_cmp(g_x, BN_value_one()) <= 0) { 143 error("%s: g_x < 1", __func__); 144 return -1; 145 } 146 147 h = g_v = r = tmp = v = NULL; 148 if ((bn_ctx = BN_CTX_new()) == NULL) { 149 error("%s: BN_CTX_new", __func__); 150 goto out; 151 } 152 if ((g_v = BN_new()) == NULL || 153 (r = BN_new()) == NULL || 154 (tmp = BN_new()) == NULL) { 155 error("%s: BN_new", __func__); 156 goto out; 157 } 158 159 /* 160 * v must be a random element of Zq, so 1 <= v < q 161 * we also exclude v = 1, since g^1 looks dangerous 162 */ 163 if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { 164 error("%s: bn_rand_range2", __func__); 165 goto out; 166 } 167 SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); 168 169 /* g_v = g^v mod p */ 170 if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { 171 error("%s: BN_mod_exp (g^v mod p)", __func__); 172 goto out; 173 } 174 SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 175 176 /* h = H(g || g^v || g^x || id) */ 177 if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, 178 id, idlen)) == NULL) { 179 error("%s: schnorr_hash failed", __func__); 180 goto out; 181 } 182 183 /* r = v - xh mod q */ 184 if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { 185 error("%s: BN_mod_mul (tmp = xv mod q)", __func__); 186 goto out; 187 } 188 if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { 189 error("%s: BN_mod_mul (r = v - tmp)", __func__); 190 goto out; 191 } 192 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 193 194 /* Signature is (g_v, r) */ 195 buffer_init(&b); 196 /* XXX sigtype-hash as string? */ 197 buffer_put_bignum2(&b, g_v); 198 buffer_put_bignum2(&b, r); 199 *siglen = buffer_len(&b); 200 *sig = xmalloc(*siglen); 201 memcpy(*sig, buffer_ptr(&b), *siglen); 202 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 203 "%s: sigblob", __func__)); 204 buffer_free(&b); 205 success = 0; 206 out: 207 BN_CTX_free(bn_ctx); 208 if (h != NULL) 209 BN_clear_free(h); 210 if (v != NULL) 211 BN_clear_free(v); 212 BN_clear_free(r); 213 BN_clear_free(g_v); 214 BN_clear_free(tmp); 215 216 return success; 217} 218 219/* 220 * Verify Schnorr signature 'sig' of length 'siglen' against public exponent 221 * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g'. 222 * Signature hash will be salted with 'idlen' bytes from 'id'. 223 * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 224 */ 225int 226schnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 227 const BIGNUM *g_x, const u_char *id, u_int idlen, 228 const u_char *sig, u_int siglen) 229{ 230 int success = -1; 231 Buffer b; 232 BIGNUM *g_v, *h, *r, *g_xh, *g_r, *expected; 233 BN_CTX *bn_ctx; 234 u_int rlen; 235 236 SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 237 238 /* Avoid degenerate cases: g^0 yields a spoofable signature */ 239 if (BN_cmp(g_x, BN_value_one()) <= 0) { 240 error("%s: g_x < 1", __func__); 241 return -1; 242 } 243 244 g_v = h = r = g_xh = g_r = expected = NULL; 245 if ((bn_ctx = BN_CTX_new()) == NULL) { 246 error("%s: BN_CTX_new", __func__); 247 goto out; 248 } 249 if ((g_v = BN_new()) == NULL || 250 (r = BN_new()) == NULL || 251 (g_xh = BN_new()) == NULL || 252 (g_r = BN_new()) == NULL || 253 (expected = BN_new()) == NULL) { 254 error("%s: BN_new", __func__); 255 goto out; 256 } 257 258 /* Extract g^v and r from signature blob */ 259 buffer_init(&b); 260 buffer_append(&b, sig, siglen); 261 SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 262 "%s: sigblob", __func__)); 263 buffer_get_bignum2(&b, g_v); 264 buffer_get_bignum2(&b, r); 265 rlen = buffer_len(&b); 266 buffer_free(&b); 267 if (rlen != 0) { 268 error("%s: remaining bytes in signature %d", __func__, rlen); 269 goto out; 270 } 271 buffer_free(&b); 272 SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 273 SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 274 275 /* h = H(g || g^v || g^x || id) */ 276 if ((h = schnorr_hash(grp_p, grp_q, grp_g, g_v, g_x, 277 id, idlen)) == NULL) { 278 error("%s: schnorr_hash failed", __func__); 279 goto out; 280 } 281 282 /* g_xh = (g^x)^h */ 283 if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { 284 error("%s: BN_mod_exp (g_x^h mod p)", __func__); 285 goto out; 286 } 287 SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 288 289 /* g_r = g^r */ 290 if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { 291 error("%s: BN_mod_exp (g_x^h mod p)", __func__); 292 goto out; 293 } 294 SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); 295 296 /* expected = g^r * g_xh */ 297 if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { 298 error("%s: BN_mod_mul (expected = g_r mod p)", __func__); 299 goto out; 300 } 301 SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); 302 303 /* Check g_v == expected */ 304 success = BN_cmp(expected, g_v) == 0; 305 out: 306 BN_CTX_free(bn_ctx); 307 if (h != NULL) 308 BN_clear_free(h); 309 BN_clear_free(g_v); 310 BN_clear_free(r); 311 BN_clear_free(g_xh); 312 BN_clear_free(g_r); 313 BN_clear_free(expected); 314 return success; 315} 316 317#ifdef SCHNORR_MAIN 318static void 319schnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, 320 const BIGNUM *grp_g, const BIGNUM *x) 321{ 322 BIGNUM *g_x; 323 u_char *sig; 324 u_int siglen; 325 BN_CTX *bn_ctx; 326 327 if ((bn_ctx = BN_CTX_new()) == NULL) 328 fatal("%s: BN_CTX_new", __func__); 329 if ((g_x = BN_new()) == NULL) 330 fatal("%s: BN_new", __func__); 331 332 if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) 333 fatal("%s: g_x", __func__); 334 if (schnorr_sign(grp_p, grp_q, grp_g, x, g_x, "junk", 4, &sig, &siglen)) 335 fatal("%s: schnorr_sign", __func__); 336 if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, 337 sig, siglen) != 1) 338 fatal("%s: verify fail", __func__); 339 if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "JUNK", 4, 340 sig, siglen) != 0) 341 fatal("%s: verify should have failed (bad ID)", __func__); 342 sig[4] ^= 1; 343 if (schnorr_verify(grp_p, grp_q, grp_g, g_x, "junk", 4, 344 sig, siglen) != 0) 345 fatal("%s: verify should have failed (bit error)", __func__); 346 xfree(sig); 347 BN_free(g_x); 348 BN_CTX_free(bn_ctx); 349} 350 351static void 352schnorr_selftest(void) 353{ 354 BIGNUM *x; 355 struct jpake_group *grp; 356 u_int i; 357 char *hh; 358 359 grp = jpake_default_group(); 360 if ((x = BN_new()) == NULL) 361 fatal("%s: BN_new", __func__); 362 SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); 363 SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); 364 SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); 365 366 /* [1, 20) */ 367 for (i = 1; i < 20; i++) { 368 printf("x = %u\n", i); 369 fflush(stdout); 370 if (BN_set_word(x, i) != 1) 371 fatal("%s: set x word", __func__); 372 schnorr_selftest_one(grp->p, grp->q, grp->g, x); 373 } 374 375 /* 100 x random [0, p) */ 376 for (i = 0; i < 100; i++) { 377 if (BN_rand_range(x, grp->p) != 1) 378 fatal("%s: BN_rand_range", __func__); 379 hh = BN_bn2hex(x); 380 printf("x = (random) 0x%s\n", hh); 381 free(hh); 382 fflush(stdout); 383 schnorr_selftest_one(grp->p, grp->q, grp->g, x); 384 } 385 386 /* [q-20, q) */ 387 if (BN_set_word(x, 20) != 1) 388 fatal("%s: BN_set_word (x = 20)", __func__); 389 if (BN_sub(x, grp->q, x) != 1) 390 fatal("%s: BN_sub (q - x)", __func__); 391 for (i = 0; i < 19; i++) { 392 hh = BN_bn2hex(x); 393 printf("x = (q - %d) 0x%s\n", 20 - i, hh); 394 free(hh); 395 fflush(stdout); 396 schnorr_selftest_one(grp->p, grp->q, grp->g, x); 397 if (BN_add(x, x, BN_value_one()) != 1) 398 fatal("%s: BN_add (x + 1)", __func__); 399 } 400 BN_free(x); 401} 402 403int 404main(int argc, char **argv) 405{ 406 log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); 407 408 schnorr_selftest(); 409 return 0; 410} 411#endif 412 413#endif 414