schnorr.c revision 255767
1255767Sdes/* $OpenBSD: schnorr.c,v 1.7 2013/05/17 00:13:14 djm Exp $ */ 2192595Sdes/* $FreeBSD: head/crypto/openssh/schnorr.c 255767 2013-09-21 21:36:09Z 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); 108255767Sdes free(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 } 144221420Sdes if (BN_cmp(g_x, grp_p) >= 0) { 145221420Sdes error("%s: g_x > g", __func__); 146221420Sdes return -1; 147221420Sdes } 148189006Sdes 149189006Sdes h = g_v = r = tmp = v = NULL; 150189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 151189006Sdes error("%s: BN_CTX_new", __func__); 152189006Sdes goto out; 153189006Sdes } 154189006Sdes if ((g_v = BN_new()) == NULL || 155189006Sdes (r = BN_new()) == NULL || 156189006Sdes (tmp = BN_new()) == NULL) { 157189006Sdes error("%s: BN_new", __func__); 158189006Sdes goto out; 159189006Sdes } 160189006Sdes 161189006Sdes /* 162189006Sdes * v must be a random element of Zq, so 1 <= v < q 163189006Sdes * we also exclude v = 1, since g^1 looks dangerous 164189006Sdes */ 165189006Sdes if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { 166189006Sdes error("%s: bn_rand_range2", __func__); 167189006Sdes goto out; 168189006Sdes } 169189006Sdes SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); 170189006Sdes 171189006Sdes /* g_v = g^v mod p */ 172189006Sdes if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { 173189006Sdes error("%s: BN_mod_exp (g^v mod p)", __func__); 174189006Sdes goto out; 175189006Sdes } 176189006Sdes SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 177189006Sdes 178189006Sdes /* h = H(g || g^v || g^x || id) */ 179197679Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, g_v, g_x, 180189006Sdes id, idlen)) == NULL) { 181189006Sdes error("%s: schnorr_hash failed", __func__); 182189006Sdes goto out; 183189006Sdes } 184189006Sdes 185189006Sdes /* r = v - xh mod q */ 186189006Sdes if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { 187189006Sdes error("%s: BN_mod_mul (tmp = xv mod q)", __func__); 188189006Sdes goto out; 189189006Sdes } 190189006Sdes if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { 191189006Sdes error("%s: BN_mod_mul (r = v - tmp)", __func__); 192189006Sdes goto out; 193189006Sdes } 194197679Sdes SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__)); 195189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 196189006Sdes 197197679Sdes *e_p = g_v; 198197679Sdes *r_p = r; 199197679Sdes 200197679Sdes success = 0; 201197679Sdes out: 202197679Sdes BN_CTX_free(bn_ctx); 203197679Sdes if (h != NULL) 204197679Sdes BN_clear_free(h); 205197679Sdes if (v != NULL) 206197679Sdes BN_clear_free(v); 207197679Sdes BN_clear_free(tmp); 208197679Sdes 209197679Sdes return success; 210197679Sdes} 211197679Sdes 212197679Sdes/* 213197679Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 214197679Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 215197679Sdes * using a SHA256 hash. 216197679Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 217197679Sdes * replay salt. 218197679Sdes * On success, 0 is returned and *siglen bytes of signature are returned in 219197679Sdes * *sig (caller to free). Returns -1 on failure. 220197679Sdes */ 221197679Sdesint 222197679Sdesschnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 223197679Sdes const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, 224197679Sdes u_char **sig, u_int *siglen) 225197679Sdes{ 226197679Sdes Buffer b; 227197679Sdes BIGNUM *r, *e; 228197679Sdes 229197679Sdes if (schnorr_sign(grp_p, grp_q, grp_g, EVP_sha256(), 230197679Sdes x, g_x, id, idlen, &r, &e) != 0) 231197679Sdes return -1; 232197679Sdes 233197679Sdes /* Signature is (e, r) */ 234189006Sdes buffer_init(&b); 235189006Sdes /* XXX sigtype-hash as string? */ 236197679Sdes buffer_put_bignum2(&b, e); 237189006Sdes buffer_put_bignum2(&b, r); 238189006Sdes *siglen = buffer_len(&b); 239189006Sdes *sig = xmalloc(*siglen); 240189006Sdes memcpy(*sig, buffer_ptr(&b), *siglen); 241189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 242189006Sdes "%s: sigblob", __func__)); 243189006Sdes buffer_free(&b); 244197679Sdes 245189006Sdes BN_clear_free(r); 246197679Sdes BN_clear_free(e); 247189006Sdes 248197679Sdes return 0; 249189006Sdes} 250189006Sdes 251189006Sdes/* 252197679Sdes * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against 253197679Sdes * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and 254197679Sdes * 'grp_g' using hash "evp_md". 255189006Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 256189006Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 257189006Sdes */ 258189006Sdesint 259189006Sdesschnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 260197679Sdes const EVP_MD *evp_md, const BIGNUM *g_x, const u_char *id, u_int idlen, 261197679Sdes const BIGNUM *r, const BIGNUM *e) 262189006Sdes{ 263189006Sdes int success = -1; 264221420Sdes BIGNUM *h = NULL, *g_xh = NULL, *g_r = NULL, *gx_q = NULL; 265221420Sdes BIGNUM *expected = NULL; 266189006Sdes BN_CTX *bn_ctx; 267189006Sdes 268189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 269189006Sdes 270189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 271189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 272221420Sdes error("%s: g_x <= 1", __func__); 273189006Sdes return -1; 274189006Sdes } 275221420Sdes if (BN_cmp(g_x, grp_p) >= 0) { 276221420Sdes error("%s: g_x >= p", __func__); 277221420Sdes return -1; 278221420Sdes } 279189006Sdes 280197679Sdes h = g_xh = g_r = expected = NULL; 281189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 282189006Sdes error("%s: BN_CTX_new", __func__); 283189006Sdes goto out; 284189006Sdes } 285197679Sdes if ((g_xh = BN_new()) == NULL || 286189006Sdes (g_r = BN_new()) == NULL || 287221420Sdes (gx_q = BN_new()) == NULL || 288189006Sdes (expected = BN_new()) == NULL) { 289189006Sdes error("%s: BN_new", __func__); 290189006Sdes goto out; 291189006Sdes } 292189006Sdes 293197679Sdes SCHNORR_DEBUG_BN((e, "%s: e = ", __func__)); 294189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 295189006Sdes 296221420Sdes /* gx_q = (g^x)^q must === 1 mod p */ 297221420Sdes if (BN_mod_exp(gx_q, g_x, grp_q, grp_p, bn_ctx) == -1) { 298221420Sdes error("%s: BN_mod_exp (g_x^q mod p)", __func__); 299221420Sdes goto out; 300221420Sdes } 301221420Sdes if (BN_cmp(gx_q, BN_value_one()) != 0) { 302221420Sdes error("%s: Invalid signature (g^x)^q != 1 mod p", __func__); 303221420Sdes goto out; 304221420Sdes } 305221420Sdes 306221420Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 307189006Sdes /* h = H(g || g^v || g^x || id) */ 308197679Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, evp_md, e, g_x, 309189006Sdes id, idlen)) == NULL) { 310189006Sdes error("%s: schnorr_hash failed", __func__); 311189006Sdes goto out; 312189006Sdes } 313189006Sdes 314189006Sdes /* g_xh = (g^x)^h */ 315189006Sdes if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { 316189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 317189006Sdes goto out; 318189006Sdes } 319189006Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 320189006Sdes 321189006Sdes /* g_r = g^r */ 322189006Sdes if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { 323189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 324189006Sdes goto out; 325189006Sdes } 326189006Sdes SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); 327189006Sdes 328189006Sdes /* expected = g^r * g_xh */ 329189006Sdes if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { 330189006Sdes error("%s: BN_mod_mul (expected = g_r mod p)", __func__); 331189006Sdes goto out; 332189006Sdes } 333189006Sdes SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); 334189006Sdes 335197679Sdes /* Check e == expected */ 336197679Sdes success = BN_cmp(expected, e) == 0; 337189006Sdes out: 338189006Sdes BN_CTX_free(bn_ctx); 339189006Sdes if (h != NULL) 340189006Sdes BN_clear_free(h); 341221420Sdes if (gx_q != NULL) 342221420Sdes BN_clear_free(gx_q); 343221420Sdes if (g_xh != NULL) 344221420Sdes BN_clear_free(g_xh); 345221420Sdes if (g_r != NULL) 346221420Sdes BN_clear_free(g_r); 347221420Sdes if (expected != NULL) 348221420Sdes BN_clear_free(expected); 349189006Sdes return success; 350189006Sdes} 351189006Sdes 352197679Sdes/* 353197679Sdes * Verify Schnorr signature 'sig' of length 'siglen' against public exponent 354197679Sdes * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a 355197679Sdes * SHA256 hash. 356197679Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 357197679Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 358197679Sdes */ 359197679Sdesint 360197679Sdesschnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, 361197679Sdes const BIGNUM *grp_g, 362197679Sdes const BIGNUM *g_x, const u_char *id, u_int idlen, 363197679Sdes const u_char *sig, u_int siglen) 364197679Sdes{ 365197679Sdes Buffer b; 366197679Sdes int ret = -1; 367197679Sdes u_int rlen; 368197679Sdes BIGNUM *r, *e; 369197679Sdes 370197679Sdes e = r = NULL; 371197679Sdes if ((e = BN_new()) == NULL || 372197679Sdes (r = BN_new()) == NULL) { 373197679Sdes error("%s: BN_new", __func__); 374197679Sdes goto out; 375197679Sdes } 376197679Sdes 377197679Sdes /* Extract g^v and r from signature blob */ 378197679Sdes buffer_init(&b); 379197679Sdes buffer_append(&b, sig, siglen); 380197679Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 381197679Sdes "%s: sigblob", __func__)); 382197679Sdes buffer_get_bignum2(&b, e); 383197679Sdes buffer_get_bignum2(&b, r); 384197679Sdes rlen = buffer_len(&b); 385197679Sdes buffer_free(&b); 386197679Sdes if (rlen != 0) { 387197679Sdes error("%s: remaining bytes in signature %d", __func__, rlen); 388197679Sdes goto out; 389197679Sdes } 390197679Sdes 391197679Sdes ret = schnorr_verify(grp_p, grp_q, grp_g, EVP_sha256(), 392197679Sdes g_x, id, idlen, r, e); 393197679Sdes out: 394197679Sdes BN_clear_free(e); 395197679Sdes BN_clear_free(r); 396197679Sdes 397197679Sdes return ret; 398197679Sdes} 399197679Sdes 400197679Sdes/* Helper functions */ 401197679Sdes 402197679Sdes/* 403197679Sdes * Generate uniformly distributed random number in range (1, high). 404197679Sdes * Return number on success, NULL on failure. 405197679Sdes */ 406197679SdesBIGNUM * 407197679Sdesbn_rand_range_gt_one(const BIGNUM *high) 408197679Sdes{ 409197679Sdes BIGNUM *r, *tmp; 410197679Sdes int success = -1; 411197679Sdes 412197679Sdes if ((tmp = BN_new()) == NULL) { 413197679Sdes error("%s: BN_new", __func__); 414197679Sdes return NULL; 415197679Sdes } 416197679Sdes if ((r = BN_new()) == NULL) { 417197679Sdes error("%s: BN_new failed", __func__); 418197679Sdes goto out; 419197679Sdes } 420197679Sdes if (BN_set_word(tmp, 2) != 1) { 421197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 422197679Sdes goto out; 423197679Sdes } 424197679Sdes if (BN_sub(tmp, high, tmp) == -1) { 425197679Sdes error("%s: BN_sub failed (tmp = high - 2)", __func__); 426197679Sdes goto out; 427197679Sdes } 428197679Sdes if (BN_rand_range(r, tmp) == -1) { 429197679Sdes error("%s: BN_rand_range failed", __func__); 430197679Sdes goto out; 431197679Sdes } 432197679Sdes if (BN_set_word(tmp, 2) != 1) { 433197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 434197679Sdes goto out; 435197679Sdes } 436197679Sdes if (BN_add(r, r, tmp) == -1) { 437197679Sdes error("%s: BN_add failed (r = r + 2)", __func__); 438197679Sdes goto out; 439197679Sdes } 440197679Sdes success = 0; 441197679Sdes out: 442197679Sdes BN_clear_free(tmp); 443197679Sdes if (success == 0) 444197679Sdes return r; 445197679Sdes BN_clear_free(r); 446197679Sdes return NULL; 447197679Sdes} 448197679Sdes 449197679Sdes/* 450197679Sdes * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success, 451197679Sdes * with digest via 'digestp' (caller to free) and length via 'lenp'. 452197679Sdes * Returns -1 on failure. 453197679Sdes */ 454197679Sdesint 455197679Sdeshash_buffer(const u_char *buf, u_int len, const EVP_MD *md, 456197679Sdes u_char **digestp, u_int *lenp) 457197679Sdes{ 458197679Sdes u_char digest[EVP_MAX_MD_SIZE]; 459197679Sdes u_int digest_len; 460197679Sdes EVP_MD_CTX evp_md_ctx; 461197679Sdes int success = -1; 462197679Sdes 463197679Sdes EVP_MD_CTX_init(&evp_md_ctx); 464197679Sdes 465197679Sdes if (EVP_DigestInit_ex(&evp_md_ctx, md, NULL) != 1) { 466197679Sdes error("%s: EVP_DigestInit_ex", __func__); 467197679Sdes goto out; 468197679Sdes } 469197679Sdes if (EVP_DigestUpdate(&evp_md_ctx, buf, len) != 1) { 470197679Sdes error("%s: EVP_DigestUpdate", __func__); 471197679Sdes goto out; 472197679Sdes } 473197679Sdes if (EVP_DigestFinal_ex(&evp_md_ctx, digest, &digest_len) != 1) { 474197679Sdes error("%s: EVP_DigestFinal_ex", __func__); 475197679Sdes goto out; 476197679Sdes } 477197679Sdes *digestp = xmalloc(digest_len); 478197679Sdes *lenp = digest_len; 479197679Sdes memcpy(*digestp, digest, *lenp); 480197679Sdes success = 0; 481197679Sdes out: 482197679Sdes EVP_MD_CTX_cleanup(&evp_md_ctx); 483197679Sdes bzero(digest, sizeof(digest)); 484197679Sdes digest_len = 0; 485197679Sdes return success; 486197679Sdes} 487197679Sdes 488197679Sdes/* print formatted string followed by bignum */ 489197679Sdesvoid 490197679Sdesdebug3_bn(const BIGNUM *n, const char *fmt, ...) 491197679Sdes{ 492197679Sdes char *out, *h; 493197679Sdes va_list args; 494255767Sdes int ret; 495197679Sdes 496197679Sdes out = NULL; 497197679Sdes va_start(args, fmt); 498255767Sdes ret = vasprintf(&out, fmt, args); 499197679Sdes va_end(args); 500255767Sdes if (ret == -1 || out == NULL) 501197679Sdes fatal("%s: vasprintf failed", __func__); 502197679Sdes 503197679Sdes if (n == NULL) 504197679Sdes debug3("%s(null)", out); 505197679Sdes else { 506197679Sdes h = BN_bn2hex(n); 507197679Sdes debug3("%s0x%s", out, h); 508197679Sdes free(h); 509197679Sdes } 510197679Sdes free(out); 511197679Sdes} 512197679Sdes 513197679Sdes/* print formatted string followed by buffer contents in hex */ 514197679Sdesvoid 515197679Sdesdebug3_buf(const u_char *buf, u_int len, const char *fmt, ...) 516197679Sdes{ 517197679Sdes char *out, h[65]; 518197679Sdes u_int i, j; 519197679Sdes va_list args; 520255767Sdes int ret; 521197679Sdes 522197679Sdes out = NULL; 523197679Sdes va_start(args, fmt); 524255767Sdes ret = vasprintf(&out, fmt, args); 525197679Sdes va_end(args); 526255767Sdes if (ret == -1 || out == NULL) 527197679Sdes fatal("%s: vasprintf failed", __func__); 528197679Sdes 529197679Sdes debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : ""); 530197679Sdes free(out); 531197679Sdes if (buf == NULL) 532197679Sdes return; 533197679Sdes 534197679Sdes *h = '\0'; 535197679Sdes for (i = j = 0; i < len; i++) { 536197679Sdes snprintf(h + j, sizeof(h) - j, "%02x", buf[i]); 537197679Sdes j += 2; 538197679Sdes if (j >= sizeof(h) - 1 || i == len - 1) { 539197679Sdes debug3(" %s", h); 540197679Sdes *h = '\0'; 541197679Sdes j = 0; 542197679Sdes } 543197679Sdes } 544197679Sdes} 545197679Sdes 546197679Sdes/* 547197679Sdes * Construct a MODP group from hex strings p (which must be a safe 548197679Sdes * prime) and g, automatically calculating subgroup q as (p / 2) 549197679Sdes */ 550197679Sdesstruct modp_group * 551197679Sdesmodp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p) 552197679Sdes{ 553197679Sdes struct modp_group *ret; 554197679Sdes 555197679Sdes ret = xmalloc(sizeof(*ret)); 556197679Sdes ret->p = ret->q = ret->g = NULL; 557197679Sdes if (BN_hex2bn(&ret->p, grp_p) == 0 || 558197679Sdes BN_hex2bn(&ret->g, grp_g) == 0) 559197679Sdes fatal("%s: BN_hex2bn", __func__); 560197679Sdes /* Subgroup order is p/2 (p is a safe prime) */ 561197679Sdes if ((ret->q = BN_new()) == NULL) 562197679Sdes fatal("%s: BN_new", __func__); 563197679Sdes if (BN_rshift1(ret->q, ret->p) != 1) 564197679Sdes fatal("%s: BN_rshift1", __func__); 565197679Sdes 566197679Sdes return ret; 567197679Sdes} 568197679Sdes 569197679Sdesvoid 570197679Sdesmodp_group_free(struct modp_group *grp) 571197679Sdes{ 572197679Sdes if (grp->g != NULL) 573197679Sdes BN_clear_free(grp->g); 574197679Sdes if (grp->p != NULL) 575197679Sdes BN_clear_free(grp->p); 576197679Sdes if (grp->q != NULL) 577197679Sdes BN_clear_free(grp->q); 578197679Sdes bzero(grp, sizeof(*grp)); 579255767Sdes free(grp); 580197679Sdes} 581197679Sdes 582197679Sdes/* main() function for self-test */ 583197679Sdes 584189006Sdes#ifdef SCHNORR_MAIN 585189006Sdesstatic void 586189006Sdesschnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, 587189006Sdes const BIGNUM *grp_g, const BIGNUM *x) 588189006Sdes{ 589189006Sdes BIGNUM *g_x; 590189006Sdes u_char *sig; 591189006Sdes u_int siglen; 592189006Sdes BN_CTX *bn_ctx; 593189006Sdes 594189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) 595189006Sdes fatal("%s: BN_CTX_new", __func__); 596189006Sdes if ((g_x = BN_new()) == NULL) 597189006Sdes fatal("%s: BN_new", __func__); 598189006Sdes 599189006Sdes if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) 600189006Sdes fatal("%s: g_x", __func__); 601197679Sdes if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4, 602197679Sdes &sig, &siglen)) 603189006Sdes fatal("%s: schnorr_sign", __func__); 604197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 605189006Sdes sig, siglen) != 1) 606189006Sdes fatal("%s: verify fail", __func__); 607197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4, 608189006Sdes sig, siglen) != 0) 609189006Sdes fatal("%s: verify should have failed (bad ID)", __func__); 610189006Sdes sig[4] ^= 1; 611197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 612189006Sdes sig, siglen) != 0) 613189006Sdes fatal("%s: verify should have failed (bit error)", __func__); 614255767Sdes free(sig); 615189006Sdes BN_free(g_x); 616189006Sdes BN_CTX_free(bn_ctx); 617189006Sdes} 618189006Sdes 619189006Sdesstatic void 620189006Sdesschnorr_selftest(void) 621189006Sdes{ 622189006Sdes BIGNUM *x; 623197679Sdes struct modp_group *grp; 624189006Sdes u_int i; 625189006Sdes char *hh; 626189006Sdes 627189006Sdes grp = jpake_default_group(); 628189006Sdes if ((x = BN_new()) == NULL) 629189006Sdes fatal("%s: BN_new", __func__); 630189006Sdes SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); 631189006Sdes SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); 632189006Sdes SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); 633189006Sdes 634189006Sdes /* [1, 20) */ 635189006Sdes for (i = 1; i < 20; i++) { 636189006Sdes printf("x = %u\n", i); 637189006Sdes fflush(stdout); 638189006Sdes if (BN_set_word(x, i) != 1) 639189006Sdes fatal("%s: set x word", __func__); 640189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 641189006Sdes } 642189006Sdes 643189006Sdes /* 100 x random [0, p) */ 644189006Sdes for (i = 0; i < 100; i++) { 645189006Sdes if (BN_rand_range(x, grp->p) != 1) 646189006Sdes fatal("%s: BN_rand_range", __func__); 647189006Sdes hh = BN_bn2hex(x); 648189006Sdes printf("x = (random) 0x%s\n", hh); 649189006Sdes free(hh); 650189006Sdes fflush(stdout); 651189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 652189006Sdes } 653189006Sdes 654189006Sdes /* [q-20, q) */ 655189006Sdes if (BN_set_word(x, 20) != 1) 656189006Sdes fatal("%s: BN_set_word (x = 20)", __func__); 657189006Sdes if (BN_sub(x, grp->q, x) != 1) 658189006Sdes fatal("%s: BN_sub (q - x)", __func__); 659189006Sdes for (i = 0; i < 19; i++) { 660189006Sdes hh = BN_bn2hex(x); 661189006Sdes printf("x = (q - %d) 0x%s\n", 20 - i, hh); 662189006Sdes free(hh); 663189006Sdes fflush(stdout); 664189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 665189006Sdes if (BN_add(x, x, BN_value_one()) != 1) 666189006Sdes fatal("%s: BN_add (x + 1)", __func__); 667189006Sdes } 668189006Sdes BN_free(x); 669189006Sdes} 670189006Sdes 671189006Sdesint 672189006Sdesmain(int argc, char **argv) 673189006Sdes{ 674189006Sdes log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); 675189006Sdes 676189006Sdes schnorr_selftest(); 677189006Sdes return 0; 678189006Sdes} 679189006Sdes#endif 680189006Sdes 681192595Sdes#endif 682