schnorr.c revision 197679
1197679Sdes/* $OpenBSD: schnorr.c,v 1.3 2009/03/05 07:18:19 djm Exp $ */ 2192595Sdes/* $FreeBSD: head/crypto/openssh/schnorr.c 197679 2009-10-01 17:12:52Z des $ */ 3189006Sdes/* 4189006Sdes * Copyright (c) 2008 Damien Miller. All rights reserved. 5189006Sdes * 6189006Sdes * Permission to use, copy, modify, and distribute this software for any 7189006Sdes * purpose with or without fee is hereby granted, provided that the above 8189006Sdes * copyright notice and this permission notice appear in all copies. 9189006Sdes * 10189006Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11189006Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12189006Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13189006Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14189006Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15189006Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16189006Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17189006Sdes */ 18189006Sdes 19189006Sdes/* 20189006Sdes * Implementation of Schnorr signatures / zero-knowledge proofs, based on 21189006Sdes * description in: 22189006Sdes * 23189006Sdes * F. Hao, P. Ryan, "Password Authenticated Key Exchange by Juggling", 24189006Sdes * 16th Workshop on Security Protocols, Cambridge, April 2008 25189006Sdes * 26189006Sdes * http://grouper.ieee.org/groups/1363/Research/contributions/hao-ryan-2008.pdf 27189006Sdes */ 28189006Sdes 29189006Sdes#include "includes.h" 30189006Sdes 31189006Sdes#include <sys/types.h> 32189006Sdes 33189006Sdes#include <string.h> 34189006Sdes#include <stdarg.h> 35189006Sdes#include <stdio.h> 36189006Sdes 37189006Sdes#include <openssl/evp.h> 38189006Sdes#include <openssl/bn.h> 39189006Sdes 40189006Sdes#include "xmalloc.h" 41189006Sdes#include "buffer.h" 42189006Sdes#include "log.h" 43189006Sdes 44197679Sdes#include "schnorr.h" 45189006Sdes 46192595Sdes#ifdef JPAKE 47192595Sdes 48197679Sdes#include "openbsd-compat/openssl-compat.h" 49197679Sdes 50189006Sdes/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ 51189006Sdes/* #define SCHNORR_MAIN */ /* Include main() selftest */ 52189006Sdes 53189006Sdes#ifndef SCHNORR_DEBUG 54189006Sdes# define SCHNORR_DEBUG_BN(a) 55189006Sdes# define SCHNORR_DEBUG_BUF(a) 56189006Sdes#else 57197679Sdes# define SCHNORR_DEBUG_BN(a) debug3_bn a 58197679Sdes# define SCHNORR_DEBUG_BUF(a) debug3_buf a 59189006Sdes#endif /* SCHNORR_DEBUG */ 60189006Sdes 61189006Sdes/* 62189006Sdes * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) 63197679Sdes * using the hash function defined by "evp_md". Returns signature as 64197679Sdes * bignum or NULL on error. 65189006Sdes */ 66189006Sdesstatic BIGNUM * 67189006Sdesschnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, 68197679Sdes const EVP_MD *evp_md, const BIGNUM *g_v, const BIGNUM *g_x, 69189006Sdes const u_char *id, u_int idlen) 70189006Sdes{ 71189006Sdes u_char *digest; 72189006Sdes u_int digest_len; 73189006Sdes BIGNUM *h; 74189006Sdes Buffer b; 75189006Sdes int success = -1; 76189006Sdes 77189006Sdes if ((h = BN_new()) == NULL) { 78189006Sdes error("%s: BN_new", __func__); 79189006Sdes return NULL; 80189006Sdes } 81189006Sdes 82189006Sdes buffer_init(&b); 83189006Sdes 84189006Sdes /* h = H(g || p || q || g^v || g^x || id) */ 85189006Sdes buffer_put_bignum2(&b, g); 86189006Sdes buffer_put_bignum2(&b, p); 87189006Sdes buffer_put_bignum2(&b, q); 88189006Sdes buffer_put_bignum2(&b, g_v); 89189006Sdes buffer_put_bignum2(&b, g_x); 90189006Sdes buffer_put_string(&b, id, idlen); 91189006Sdes 92189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 93189006Sdes "%s: hashblob", __func__)); 94197679Sdes if (hash_buffer(buffer_ptr(&b), buffer_len(&b), evp_md, 95189006Sdes &digest, &digest_len) != 0) { 96189006Sdes error("%s: hash_buffer", __func__); 97189006Sdes goto out; 98189006Sdes } 99189006Sdes if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { 100189006Sdes error("%s: BN_bin2bn", __func__); 101189006Sdes goto out; 102189006Sdes } 103189006Sdes success = 0; 104189006Sdes SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); 105189006Sdes out: 106189006Sdes buffer_free(&b); 107189006Sdes bzero(digest, digest_len); 108189006Sdes xfree(digest); 109189006Sdes digest_len = 0; 110189006Sdes if (success == 0) 111189006Sdes return h; 112189006Sdes BN_clear_free(h); 113189006Sdes return NULL; 114189006Sdes} 115189006Sdes 116189006Sdes/* 117189006Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 118189006Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 119197679Sdes * using the hash function "evp_md". 120189006Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 121189006Sdes * replay salt. 122197679Sdes * 123197679Sdes * On success, 0 is returned. The signature values are returned as *e_p 124197679Sdes * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values. 125197679Sdes * On failure, -1 is returned. 126189006Sdes */ 127189006Sdesint 128189006Sdesschnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 129197679Sdes const EVP_MD *evp_md, const BIGNUM *x, const BIGNUM *g_x, 130197679Sdes const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p) 131189006Sdes{ 132189006Sdes int success = -1; 133189006Sdes BIGNUM *h, *tmp, *v, *g_v, *r; 134189006Sdes BN_CTX *bn_ctx; 135189006Sdes 136189006Sdes SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); 137189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 138189006Sdes 139189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 140189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 141189006Sdes error("%s: g_x < 1", __func__); 142189006Sdes return -1; 143189006Sdes } 144189006Sdes 145189006Sdes h = g_v = r = tmp = v = NULL; 146189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 147189006Sdes error("%s: BN_CTX_new", __func__); 148189006Sdes goto out; 149189006Sdes } 150189006Sdes if ((g_v = BN_new()) == NULL || 151189006Sdes (r = BN_new()) == NULL || 152189006Sdes (tmp = BN_new()) == NULL) { 153189006Sdes error("%s: BN_new", __func__); 154189006Sdes goto out; 155189006Sdes } 156189006Sdes 157189006Sdes /* 158189006Sdes * v must be a random element of Zq, so 1 <= v < q 159189006Sdes * we also exclude v = 1, since g^1 looks dangerous 160189006Sdes */ 161189006Sdes if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { 162189006Sdes error("%s: bn_rand_range2", __func__); 163189006Sdes goto out; 164189006Sdes } 165189006Sdes SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); 166189006Sdes 167189006Sdes /* g_v = g^v mod p */ 168189006Sdes if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { 169189006Sdes error("%s: BN_mod_exp (g^v mod p)", __func__); 170189006Sdes goto out; 171189006Sdes } 172189006Sdes SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 173189006Sdes 174189006Sdes /* h = H(g || g^v || g^x || id) */ 175197679Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x, 176189006Sdes id, idlen)) == NULL) { 177189006Sdes error("%s: schnorr_hash failed", __func__); 178189006Sdes goto out; 179189006Sdes } 180189006Sdes 181189006Sdes /* r = v - xh mod q */ 182189006Sdes if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { 183189006Sdes error("%s: BN_mod_mul (tmp = xv mod q)", __func__); 184189006Sdes goto out; 185189006Sdes } 186189006Sdes if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { 187189006Sdes error("%s: BN_mod_mul (r = v - tmp)", __func__); 188189006Sdes goto out; 189189006Sdes } 190197679Sdes SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__)); 191189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 192189006Sdes 193197679Sdes *e_p = g_v; 194197679Sdes *r_p = r; 195197679Sdes 196197679Sdes success = 0; 197197679Sdes out: 198197679Sdes BN_CTX_free(bn_ctx); 199197679Sdes if (h != NULL) 200197679Sdes BN_clear_free(h); 201197679Sdes if (v != NULL) 202197679Sdes BN_clear_free(v); 203197679Sdes BN_clear_free(tmp); 204197679Sdes 205197679Sdes return success; 206197679Sdes} 207197679Sdes 208197679Sdes/* 209197679Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 210197679Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 211197679Sdes * using a SHA256 hash. 212197679Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 213197679Sdes * replay salt. 214197679Sdes * On success, 0 is returned and *siglen bytes of signature are returned in 215197679Sdes * *sig (caller to free). Returns -1 on failure. 216197679Sdes */ 217197679Sdesint 218197679Sdesschnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 219197679Sdes const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, 220197679Sdes u_char **sig, u_int *siglen) 221197679Sdes{ 222197679Sdes Buffer b; 223197679Sdes BIGNUM *r, *e; 224197679Sdes 225197679Sdes if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(), 226197679Sdes x, g_x, id, idlen, &r, &e) != 0) 227197679Sdes return -1; 228197679Sdes 229197679Sdes /* Signature is (e, r) */ 230189006Sdes buffer_init(&b); 231189006Sdes /* XXX sigtype-hash as string? */ 232197679Sdes buffer_put_bignum2(&b, e); 233189006Sdes buffer_put_bignum2(&b, r); 234189006Sdes *siglen = buffer_len(&b); 235189006Sdes *sig = xmalloc(*siglen); 236189006Sdes memcpy(*sig, buffer_ptr(&b), *siglen); 237189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 238189006Sdes "%s: sigblob", __func__)); 239189006Sdes buffer_free(&b); 240197679Sdes 241189006Sdes BN_clear_free(r); 242197679Sdes BN_clear_free(e); 243189006Sdes 244197679Sdes return 0; 245189006Sdes} 246189006Sdes 247189006Sdes/* 248197679Sdes * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against 249197679Sdes * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and 250197679Sdes * 'grp_g' using hash "evp_md". 251189006Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 252189006Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 253189006Sdes */ 254189006Sdesint 255189006Sdesschnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 256197679Sdes const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen, 257197679Sdes const BIGNUM *r, const BIGNUM *e) 258189006Sdes{ 259189006Sdes int success = -1; 260197679Sdes BIGNUM *h, *g_xh, *g_r, *expected; 261189006Sdes BN_CTX *bn_ctx; 262189006Sdes 263189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 264189006Sdes 265189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 266189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 267189006Sdes error("%s: g_x < 1", __func__); 268189006Sdes return -1; 269189006Sdes } 270189006Sdes 271197679Sdes h = g_xh = g_r = expected = NULL; 272189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 273189006Sdes error("%s: BN_CTX_new", __func__); 274189006Sdes goto out; 275189006Sdes } 276197679Sdes if ((g_xh = BN_new()) == NULL || 277189006Sdes (g_r = BN_new()) == NULL || 278189006Sdes (expected = BN_new()) == NULL) { 279189006Sdes error("%s: BN_new", __func__); 280189006Sdes goto out; 281189006Sdes } 282189006Sdes 283197679Sdes SCHNORR_DEBUG_BN((e, "%s: e = ", __func__)); 284189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 285189006Sdes 286189006Sdes /* h = H(g || g^v || g^x || id) */ 287197679Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x, 288189006Sdes id, idlen)) == NULL) { 289189006Sdes error("%s: schnorr_hash failed", __func__); 290189006Sdes goto out; 291189006Sdes } 292189006Sdes 293189006Sdes /* g_xh = (g^x)^h */ 294189006Sdes if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { 295189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 296189006Sdes goto out; 297189006Sdes } 298189006Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 299189006Sdes 300189006Sdes /* g_r = g^r */ 301189006Sdes if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { 302189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 303189006Sdes goto out; 304189006Sdes } 305189006Sdes SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); 306189006Sdes 307189006Sdes /* expected = g^r * g_xh */ 308189006Sdes if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { 309189006Sdes error("%s: BN_mod_mul (expected = g_r mod p)", __func__); 310189006Sdes goto out; 311189006Sdes } 312189006Sdes SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); 313189006Sdes 314197679Sdes /* Check e == expected */ 315197679Sdes success = BN_cmp(expected, e) == 0; 316189006Sdes out: 317189006Sdes BN_CTX_free(bn_ctx); 318189006Sdes if (h != NULL) 319189006Sdes BN_clear_free(h); 320189006Sdes BN_clear_free(g_xh); 321189006Sdes BN_clear_free(g_r); 322189006Sdes BN_clear_free(expected); 323189006Sdes return success; 324189006Sdes} 325189006Sdes 326197679Sdes/* 327197679Sdes * Verify Schnorr signature 'sig' of length 'siglen' against public exponent 328197679Sdes * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a 329197679Sdes * SHA256 hash. 330197679Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 331197679Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 332197679Sdes */ 333197679Sdesint 334197679Sdesschnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, 335197679Sdes const BIGNUM *grp_g, 336197679Sdes const BIGNUM *g_x, const u_char *id, u_int idlen, 337197679Sdes const u_char *sig, u_int siglen) 338197679Sdes{ 339197679Sdes Buffer b; 340197679Sdes int ret = -1; 341197679Sdes u_int rlen; 342197679Sdes BIGNUM *r, *e; 343197679Sdes 344197679Sdes e = r = NULL; 345197679Sdes if ((e = BN_new()) == NULL || 346197679Sdes (r = BN_new()) == NULL) { 347197679Sdes error("%s: BN_new", __func__); 348197679Sdes goto out; 349197679Sdes } 350197679Sdes 351197679Sdes /* Extract g^v and r from signature blob */ 352197679Sdes buffer_init(&b); 353197679Sdes buffer_append(&b, sig, siglen); 354197679Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 355197679Sdes "%s: sigblob", __func__)); 356197679Sdes buffer_get_bignum2(&b, e); 357197679Sdes buffer_get_bignum2(&b, r); 358197679Sdes rlen = buffer_len(&b); 359197679Sdes buffer_free(&b); 360197679Sdes if (rlen != 0) { 361197679Sdes error("%s: remaining bytes in signature %d", __func__, rlen); 362197679Sdes goto out; 363197679Sdes } 364197679Sdes 365197679Sdes ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(), 366197679Sdes g_x, id, idlen, r, e); 367197679Sdes out: 368197679Sdes BN_clear_free(e); 369197679Sdes BN_clear_free(r); 370197679Sdes 371197679Sdes return ret; 372197679Sdes} 373197679Sdes 374197679Sdes/* Helper functions */ 375197679Sdes 376197679Sdes/* 377197679Sdes * Generate uniformly distributed random number in range (1, high). 378197679Sdes * Return number on success, NULL on failure. 379197679Sdes */ 380197679SdesBIGNUM * 381197679Sdesbn_rand_range_gt_one(const BIGNUM *high) 382197679Sdes{ 383197679Sdes BIGNUM *r, *tmp; 384197679Sdes int success = -1; 385197679Sdes 386197679Sdes if ((tmp = BN_new()) == NULL) { 387197679Sdes error("%s: BN_new", __func__); 388197679Sdes return NULL; 389197679Sdes } 390197679Sdes if ((r = BN_new()) == NULL) { 391197679Sdes error("%s: BN_new failed", __func__); 392197679Sdes goto out; 393197679Sdes } 394197679Sdes if (BN_set_word(tmp, 2) != 1) { 395197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 396197679Sdes goto out; 397197679Sdes } 398197679Sdes if (BN_sub(tmp, high, tmp) == -1) { 399197679Sdes error("%s: BN_sub failed (tmp = high - 2)", __func__); 400197679Sdes goto out; 401197679Sdes } 402197679Sdes if (BN_rand_range(r, tmp) == -1) { 403197679Sdes error("%s: BN_rand_range failed", __func__); 404197679Sdes goto out; 405197679Sdes } 406197679Sdes if (BN_set_word(tmp, 2) != 1) { 407197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 408197679Sdes goto out; 409197679Sdes } 410197679Sdes if (BN_add(r, r, tmp) == -1) { 411197679Sdes error("%s: BN_add failed (r = r + 2)", __func__); 412197679Sdes goto out; 413197679Sdes } 414197679Sdes success = 0; 415197679Sdes out: 416197679Sdes BN_clear_free(tmp); 417197679Sdes if (success == 0) 418197679Sdes return r; 419197679Sdes BN_clear_free(r); 420197679Sdes return NULL; 421197679Sdes} 422197679Sdes 423197679Sdes/* 424197679Sdes * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success, 425197679Sdes * with digest via 'digestp' (caller to free) and length via 'lenp'. 426197679Sdes * Returns -1 on failure. 427197679Sdes */ 428197679Sdesint 429197679Sdeshash_buffer(const u_char *buf, u_int len, const EVP_MD *md, 430197679Sdes u_char **digestp, u_int *lenp) 431197679Sdes{ 432197679Sdes u_char digest[EVP_MAX_MD_SIZE]; 433197679Sdes u_int digest_len; 434197679Sdes EVP_MD_CTX evp_md_ctx; 435197679Sdes int success = -1; 436197679Sdes 437197679Sdes EVP_MD_CTX_init(&evp_md_ctx); 438197679Sdes 439197679Sdes if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) { 440197679Sdes error("%s: EVP_DigestInit_ex", __func__); 441197679Sdes goto out; 442197679Sdes } 443197679Sdes if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) { 444197679Sdes error("%s: EVP_DigestUpdate", __func__); 445197679Sdes goto out; 446197679Sdes } 447197679Sdes if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) { 448197679Sdes error("%s: EVP_DigestFinal_ex", __func__); 449197679Sdes goto out; 450197679Sdes } 451197679Sdes *digestp = xmalloc(digest_len); 452197679Sdes *lenp = digest_len; 453197679Sdes memcpy(*digestp, digest, *lenp); 454197679Sdes success = 0; 455197679Sdes out: 456197679Sdes EVP_MD_CTX_cleanup(&evp_md_ctx); 457197679Sdes bzero(digest, sizeof(digest)); 458197679Sdes digest_len = 0; 459197679Sdes return success; 460197679Sdes} 461197679Sdes 462197679Sdes/* print formatted string followed by bignum */ 463197679Sdesvoid 464197679Sdesdebug3_bn(const BIGNUM *n, const char *fmt, ...) 465197679Sdes{ 466197679Sdes char *out, *h; 467197679Sdes va_list args; 468197679Sdes 469197679Sdes out = NULL; 470197679Sdes va_start(args, fmt); 471197679Sdes vasprintf(&out, fmt, args); 472197679Sdes va_end(args); 473197679Sdes if (out == NULL) 474197679Sdes fatal("%s: vasprintf failed", __func__); 475197679Sdes 476197679Sdes if (n == NULL) 477197679Sdes debug3("%s(null)", out); 478197679Sdes else { 479197679Sdes h = BN_bn2hex(n); 480197679Sdes debug3("%s0x%s", out, h); 481197679Sdes free(h); 482197679Sdes } 483197679Sdes free(out); 484197679Sdes} 485197679Sdes 486197679Sdes/* print formatted string followed by buffer contents in hex */ 487197679Sdesvoid 488197679Sdesdebug3_buf(const u_char *buf, u_int len, const char *fmt, ...) 489197679Sdes{ 490197679Sdes char *out, h[65]; 491197679Sdes u_int i, j; 492197679Sdes va_list args; 493197679Sdes 494197679Sdes out = NULL; 495197679Sdes va_start(args, fmt); 496197679Sdes vasprintf(&out, fmt, args); 497197679Sdes va_end(args); 498197679Sdes if (out == NULL) 499197679Sdes fatal("%s: vasprintf failed", __func__); 500197679Sdes 501197679Sdes debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : ""); 502197679Sdes free(out); 503197679Sdes if (buf == NULL) 504197679Sdes return; 505197679Sdes 506197679Sdes *h = '\0'; 507197679Sdes for (i = j = 0; i < len; i++) { 508197679Sdes snprintf(h + j, sizeof(h) - j, "%02x", buf[i]); 509197679Sdes j += 2; 510197679Sdes if (j >= sizeof(h) - 1 || i == len - 1) { 511197679Sdes debug3(" %s", h); 512197679Sdes *h = '\0'; 513197679Sdes j = 0; 514197679Sdes } 515197679Sdes } 516197679Sdes} 517197679Sdes 518197679Sdes/* 519197679Sdes * Construct a MODP group from hex strings p (which must be a safe 520197679Sdes * prime) and g, automatically calculating subgroup q as (p / 2) 521197679Sdes */ 522197679Sdesstruct modp_group * 523197679Sdesmodp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p) 524197679Sdes{ 525197679Sdes struct modp_group *ret; 526197679Sdes 527197679Sdes ret = xmalloc(sizeof(*ret)); 528197679Sdes ret->p = ret->q = ret->g = NULL; 529197679Sdes if (BN_hex2bn(&ret->p, grp_p) == 0 || 530197679Sdes BN_hex2bn(&ret->g, grp_g) == 0) 531197679Sdes fatal("%s: BN_hex2bn", __func__); 532197679Sdes /* Subgroup order is p/2 (p is a safe prime) */ 533197679Sdes if ((ret->q = BN_new()) == NULL) 534197679Sdes fatal("%s: BN_new", __func__); 535197679Sdes if (BN_rshift1(ret->q, ret->p) != 1) 536197679Sdes fatal("%s: BN_rshift1", __func__); 537197679Sdes 538197679Sdes return ret; 539197679Sdes} 540197679Sdes 541197679Sdesvoid 542197679Sdesmodp_group_free(struct modp_group *grp) 543197679Sdes{ 544197679Sdes if (grp->g != NULL) 545197679Sdes BN_clear_free(grp->g); 546197679Sdes if (grp->p != NULL) 547197679Sdes BN_clear_free(grp->p); 548197679Sdes if (grp->q != NULL) 549197679Sdes BN_clear_free(grp->q); 550197679Sdes bzero(grp, sizeof(*grp)); 551197679Sdes xfree(grp); 552197679Sdes} 553197679Sdes 554197679Sdes/* main() function for self-test */ 555197679Sdes 556189006Sdes#ifdef SCHNORR_MAIN 557189006Sdesstatic void 558189006Sdesschnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, 559189006Sdes const BIGNUM *grp_g, const BIGNUM *x) 560189006Sdes{ 561189006Sdes BIGNUM *g_x; 562189006Sdes u_char *sig; 563189006Sdes u_int siglen; 564189006Sdes BN_CTX *bn_ctx; 565189006Sdes 566189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) 567189006Sdes fatal("%s: BN_CTX_new", __func__); 568189006Sdes if ((g_x = BN_new()) == NULL) 569189006Sdes fatal("%s: BN_new", __func__); 570189006Sdes 571189006Sdes if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) 572189006Sdes fatal("%s: g_x", __func__); 573197679Sdes if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4, 574197679Sdes &sig, &siglen)) 575189006Sdes fatal("%s: schnorr_sign", __func__); 576197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 577189006Sdes sig, siglen) != 1) 578189006Sdes fatal("%s: verify fail", __func__); 579197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4, 580189006Sdes sig, siglen) != 0) 581189006Sdes fatal("%s: verify should have failed (bad ID)", __func__); 582189006Sdes sig[4] ^= 1; 583197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 584189006Sdes sig, siglen) != 0) 585189006Sdes fatal("%s: verify should have failed (bit error)", __func__); 586189006Sdes xfree(sig); 587189006Sdes BN_free(g_x); 588189006Sdes BN_CTX_free(bn_ctx); 589189006Sdes} 590189006Sdes 591189006Sdesstatic void 592189006Sdesschnorr_selftest(void) 593189006Sdes{ 594189006Sdes BIGNUM *x; 595197679Sdes struct modp_group *grp; 596189006Sdes u_int i; 597189006Sdes char *hh; 598189006Sdes 599189006Sdes grp = jpake_default_group(); 600189006Sdes if ((x = BN_new()) == NULL) 601189006Sdes fatal("%s: BN_new", __func__); 602189006Sdes SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); 603189006Sdes SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); 604189006Sdes SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); 605189006Sdes 606189006Sdes /* [1, 20) */ 607189006Sdes for (i = 1; i < 20; i++) { 608189006Sdes printf("x = %u\n", i); 609189006Sdes fflush(stdout); 610189006Sdes if (BN_set_word(x, i) != 1) 611189006Sdes fatal("%s: set x word", __func__); 612189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 613189006Sdes } 614189006Sdes 615189006Sdes /* 100 x random [0, p) */ 616189006Sdes for (i = 0; i < 100; i++) { 617189006Sdes if (BN_rand_range(x, grp->p) != 1) 618189006Sdes fatal("%s: BN_rand_range", __func__); 619189006Sdes hh = BN_bn2hex(x); 620189006Sdes printf("x = (random) 0x%s\n", hh); 621189006Sdes free(hh); 622189006Sdes fflush(stdout); 623189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 624189006Sdes } 625189006Sdes 626189006Sdes /* [q-20, q) */ 627189006Sdes if (BN_set_word(x, 20) != 1) 628189006Sdes fatal("%s: BN_set_word (x = 20)", __func__); 629189006Sdes if (BN_sub(x, grp->q, x) != 1) 630189006Sdes fatal("%s: BN_sub (q - x)", __func__); 631189006Sdes for (i = 0; i < 19; i++) { 632189006Sdes hh = BN_bn2hex(x); 633189006Sdes printf("x = (q - %d) 0x%s\n", 20 - i, hh); 634189006Sdes free(hh); 635189006Sdes fflush(stdout); 636189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 637189006Sdes if (BN_add(x, x, BN_value_one()) != 1) 638189006Sdes fatal("%s: BN_add (x + 1)", __func__); 639189006Sdes } 640189006Sdes BN_free(x); 641189006Sdes} 642189006Sdes 643189006Sdesint 644189006Sdesmain(int argc, char **argv) 645189006Sdes{ 646189006Sdes log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); 647189006Sdes 648189006Sdes schnorr_selftest(); 649189006Sdes return 0; 650189006Sdes} 651189006Sdes#endif 652189006Sdes 653192595Sdes#endif 654