1262566Sdes/* $OpenBSD: schnorr.c,v 1.9 2014/01/09 23:20:00 djm Exp $ */ 2192595Sdes/* $FreeBSD: releng/10.2/crypto/openssh/schnorr.c 262566 2014-02-27 17:29:02Z 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" 45262566Sdes#include "digest.h" 46189006Sdes 47192595Sdes#ifdef JPAKE 48192595Sdes 49197679Sdes#include "openbsd-compat/openssl-compat.h" 50197679Sdes 51189006Sdes/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ 52189006Sdes/* #define SCHNORR_MAIN */ /* Include main() selftest */ 53189006Sdes 54189006Sdes#ifndef SCHNORR_DEBUG 55189006Sdes# define SCHNORR_DEBUG_BN(a) 56189006Sdes# define SCHNORR_DEBUG_BUF(a) 57189006Sdes#else 58197679Sdes# define SCHNORR_DEBUG_BN(a) debug3_bn a 59197679Sdes# define SCHNORR_DEBUG_BUF(a) debug3_buf a 60189006Sdes#endif /* SCHNORR_DEBUG */ 61189006Sdes 62189006Sdes/* 63189006Sdes * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) 64262566Sdes * using the hash function defined by "hash_alg". Returns signature as 65197679Sdes * bignum or NULL on error. 66189006Sdes */ 67189006Sdesstatic BIGNUM * 68189006Sdesschnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, 69262566Sdes int hash_alg, const BIGNUM *g_v, const BIGNUM *g_x, 70189006Sdes const u_char *id, u_int idlen) 71189006Sdes{ 72189006Sdes u_char *digest; 73189006Sdes u_int digest_len; 74189006Sdes BIGNUM *h; 75189006Sdes Buffer b; 76189006Sdes int success = -1; 77189006Sdes 78189006Sdes if ((h = BN_new()) == NULL) { 79189006Sdes error("%s: BN_new", __func__); 80189006Sdes return NULL; 81189006Sdes } 82189006Sdes 83189006Sdes buffer_init(&b); 84189006Sdes 85189006Sdes /* h = H(g || p || q || g^v || g^x || id) */ 86189006Sdes buffer_put_bignum2(&b, g); 87189006Sdes buffer_put_bignum2(&b, p); 88189006Sdes buffer_put_bignum2(&b, q); 89189006Sdes buffer_put_bignum2(&b, g_v); 90189006Sdes buffer_put_bignum2(&b, g_x); 91189006Sdes buffer_put_string(&b, id, idlen); 92189006Sdes 93189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 94189006Sdes "%s: hashblob", __func__)); 95262566Sdes if (hash_buffer(buffer_ptr(&b), buffer_len(&b), hash_alg, 96189006Sdes &digest, &digest_len) != 0) { 97189006Sdes error("%s: hash_buffer", __func__); 98189006Sdes goto out; 99189006Sdes } 100189006Sdes if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { 101189006Sdes error("%s: BN_bin2bn", __func__); 102189006Sdes goto out; 103189006Sdes } 104189006Sdes success = 0; 105189006Sdes SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); 106189006Sdes out: 107189006Sdes buffer_free(&b); 108189006Sdes bzero(digest, digest_len); 109255767Sdes free(digest); 110189006Sdes digest_len = 0; 111189006Sdes if (success == 0) 112189006Sdes return h; 113189006Sdes BN_clear_free(h); 114189006Sdes return NULL; 115189006Sdes} 116189006Sdes 117189006Sdes/* 118189006Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 119189006Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 120262566Sdes * using the hash function "hash_alg". 121189006Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 122189006Sdes * replay salt. 123197679Sdes * 124197679Sdes * On success, 0 is returned. The signature values are returned as *e_p 125197679Sdes * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values. 126197679Sdes * On failure, -1 is returned. 127189006Sdes */ 128189006Sdesint 129189006Sdesschnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 130262566Sdes int hash_alg, const BIGNUM *x, const BIGNUM *g_x, 131197679Sdes const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p) 132189006Sdes{ 133189006Sdes int success = -1; 134189006Sdes BIGNUM *h, *tmp, *v, *g_v, *r; 135189006Sdes BN_CTX *bn_ctx; 136189006Sdes 137189006Sdes SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); 138189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 139189006Sdes 140189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 141189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 142189006Sdes error("%s: g_x < 1", __func__); 143189006Sdes return -1; 144189006Sdes } 145221420Sdes if (BN_cmp(g_x, grp_p) >= 0) { 146221420Sdes error("%s: g_x > g", __func__); 147221420Sdes return -1; 148221420Sdes } 149189006Sdes 150189006Sdes h = g_v = r = tmp = v = NULL; 151189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 152189006Sdes error("%s: BN_CTX_new", __func__); 153189006Sdes goto out; 154189006Sdes } 155189006Sdes if ((g_v = BN_new()) == NULL || 156189006Sdes (r = BN_new()) == NULL || 157189006Sdes (tmp = BN_new()) == NULL) { 158189006Sdes error("%s: BN_new", __func__); 159189006Sdes goto out; 160189006Sdes } 161189006Sdes 162189006Sdes /* 163189006Sdes * v must be a random element of Zq, so 1 <= v < q 164189006Sdes * we also exclude v = 1, since g^1 looks dangerous 165189006Sdes */ 166189006Sdes if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { 167189006Sdes error("%s: bn_rand_range2", __func__); 168189006Sdes goto out; 169189006Sdes } 170189006Sdes SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); 171189006Sdes 172189006Sdes /* g_v = g^v mod p */ 173189006Sdes if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { 174189006Sdes error("%s: BN_mod_exp (g^v mod p)", __func__); 175189006Sdes goto out; 176189006Sdes } 177189006Sdes SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 178189006Sdes 179189006Sdes /* h = H(g || g^v || g^x || id) */ 180262566Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, hash_alg, g_v, g_x, 181189006Sdes id, idlen)) == NULL) { 182189006Sdes error("%s: schnorr_hash failed", __func__); 183189006Sdes goto out; 184189006Sdes } 185189006Sdes 186189006Sdes /* r = v - xh mod q */ 187189006Sdes if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { 188189006Sdes error("%s: BN_mod_mul (tmp = xv mod q)", __func__); 189189006Sdes goto out; 190189006Sdes } 191189006Sdes if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { 192189006Sdes error("%s: BN_mod_mul (r = v - tmp)", __func__); 193189006Sdes goto out; 194189006Sdes } 195197679Sdes SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__)); 196189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 197189006Sdes 198197679Sdes *e_p = g_v; 199197679Sdes *r_p = r; 200197679Sdes 201197679Sdes success = 0; 202197679Sdes out: 203197679Sdes BN_CTX_free(bn_ctx); 204197679Sdes if (h != NULL) 205197679Sdes BN_clear_free(h); 206197679Sdes if (v != NULL) 207197679Sdes BN_clear_free(v); 208197679Sdes BN_clear_free(tmp); 209197679Sdes 210197679Sdes return success; 211197679Sdes} 212197679Sdes 213197679Sdes/* 214197679Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 215197679Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 216197679Sdes * using a SHA256 hash. 217197679Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 218197679Sdes * replay salt. 219197679Sdes * On success, 0 is returned and *siglen bytes of signature are returned in 220197679Sdes * *sig (caller to free). Returns -1 on failure. 221197679Sdes */ 222197679Sdesint 223197679Sdesschnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 224197679Sdes const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, 225197679Sdes u_char **sig, u_int *siglen) 226197679Sdes{ 227197679Sdes Buffer b; 228197679Sdes BIGNUM *r, *e; 229197679Sdes 230262566Sdes if (schnorr_sign(grp_p, grp_q, grp_g, SSH_DIGEST_SHA256, 231197679Sdes x, g_x, id, idlen, &r, &e) != 0) 232197679Sdes return -1; 233197679Sdes 234197679Sdes /* Signature is (e, r) */ 235189006Sdes buffer_init(&b); 236189006Sdes /* XXX sigtype-hash as string? */ 237197679Sdes buffer_put_bignum2(&b, e); 238189006Sdes buffer_put_bignum2(&b, r); 239189006Sdes *siglen = buffer_len(&b); 240189006Sdes *sig = xmalloc(*siglen); 241189006Sdes memcpy(*sig, buffer_ptr(&b), *siglen); 242189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 243189006Sdes "%s: sigblob", __func__)); 244189006Sdes buffer_free(&b); 245197679Sdes 246189006Sdes BN_clear_free(r); 247197679Sdes BN_clear_free(e); 248189006Sdes 249197679Sdes return 0; 250189006Sdes} 251189006Sdes 252189006Sdes/* 253197679Sdes * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against 254197679Sdes * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and 255262566Sdes * 'grp_g' using hash "hash_alg". 256189006Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 257189006Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 258189006Sdes */ 259189006Sdesint 260189006Sdesschnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 261262566Sdes int hash_alg, const BIGNUM *g_x, const u_char *id, u_int idlen, 262197679Sdes const BIGNUM *r, const BIGNUM *e) 263189006Sdes{ 264189006Sdes int success = -1; 265221420Sdes BIGNUM *h = NULL, *g_xh = NULL, *g_r = NULL, *gx_q = NULL; 266221420Sdes BIGNUM *expected = NULL; 267189006Sdes BN_CTX *bn_ctx; 268189006Sdes 269189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 270189006Sdes 271189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 272189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 273221420Sdes error("%s: g_x <= 1", __func__); 274189006Sdes return -1; 275189006Sdes } 276221420Sdes if (BN_cmp(g_x, grp_p) >= 0) { 277221420Sdes error("%s: g_x >= p", __func__); 278221420Sdes return -1; 279221420Sdes } 280189006Sdes 281197679Sdes h = g_xh = g_r = expected = NULL; 282189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 283189006Sdes error("%s: BN_CTX_new", __func__); 284189006Sdes goto out; 285189006Sdes } 286197679Sdes if ((g_xh = BN_new()) == NULL || 287189006Sdes (g_r = BN_new()) == NULL || 288221420Sdes (gx_q = BN_new()) == NULL || 289189006Sdes (expected = BN_new()) == NULL) { 290189006Sdes error("%s: BN_new", __func__); 291189006Sdes goto out; 292189006Sdes } 293189006Sdes 294197679Sdes SCHNORR_DEBUG_BN((e, "%s: e = ", __func__)); 295189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 296189006Sdes 297221420Sdes /* gx_q = (g^x)^q must === 1 mod p */ 298221420Sdes if (BN_mod_exp(gx_q, g_x, grp_q, grp_p, bn_ctx) == -1) { 299221420Sdes error("%s: BN_mod_exp (g_x^q mod p)", __func__); 300221420Sdes goto out; 301221420Sdes } 302221420Sdes if (BN_cmp(gx_q, BN_value_one()) != 0) { 303221420Sdes error("%s: Invalid signature (g^x)^q != 1 mod p", __func__); 304221420Sdes goto out; 305221420Sdes } 306221420Sdes 307221420Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 308189006Sdes /* h = H(g || g^v || g^x || id) */ 309262566Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, hash_alg, e, g_x, 310189006Sdes id, idlen)) == NULL) { 311189006Sdes error("%s: schnorr_hash failed", __func__); 312189006Sdes goto out; 313189006Sdes } 314189006Sdes 315189006Sdes /* g_xh = (g^x)^h */ 316189006Sdes if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { 317189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 318189006Sdes goto out; 319189006Sdes } 320189006Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 321189006Sdes 322189006Sdes /* g_r = g^r */ 323189006Sdes if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { 324189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 325189006Sdes goto out; 326189006Sdes } 327189006Sdes SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); 328189006Sdes 329189006Sdes /* expected = g^r * g_xh */ 330189006Sdes if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { 331189006Sdes error("%s: BN_mod_mul (expected = g_r mod p)", __func__); 332189006Sdes goto out; 333189006Sdes } 334189006Sdes SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); 335189006Sdes 336197679Sdes /* Check e == expected */ 337197679Sdes success = BN_cmp(expected, e) == 0; 338189006Sdes out: 339189006Sdes BN_CTX_free(bn_ctx); 340189006Sdes if (h != NULL) 341189006Sdes BN_clear_free(h); 342221420Sdes if (gx_q != NULL) 343221420Sdes BN_clear_free(gx_q); 344221420Sdes if (g_xh != NULL) 345221420Sdes BN_clear_free(g_xh); 346221420Sdes if (g_r != NULL) 347221420Sdes BN_clear_free(g_r); 348221420Sdes if (expected != NULL) 349221420Sdes BN_clear_free(expected); 350189006Sdes return success; 351189006Sdes} 352189006Sdes 353197679Sdes/* 354197679Sdes * Verify Schnorr signature 'sig' of length 'siglen' against public exponent 355197679Sdes * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a 356197679Sdes * SHA256 hash. 357197679Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 358197679Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 359197679Sdes */ 360197679Sdesint 361197679Sdesschnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, 362197679Sdes const BIGNUM *grp_g, 363197679Sdes const BIGNUM *g_x, const u_char *id, u_int idlen, 364197679Sdes const u_char *sig, u_int siglen) 365197679Sdes{ 366197679Sdes Buffer b; 367197679Sdes int ret = -1; 368197679Sdes u_int rlen; 369197679Sdes BIGNUM *r, *e; 370197679Sdes 371197679Sdes e = r = NULL; 372197679Sdes if ((e = BN_new()) == NULL || 373197679Sdes (r = BN_new()) == NULL) { 374197679Sdes error("%s: BN_new", __func__); 375197679Sdes goto out; 376197679Sdes } 377197679Sdes 378197679Sdes /* Extract g^v and r from signature blob */ 379197679Sdes buffer_init(&b); 380197679Sdes buffer_append(&b, sig, siglen); 381197679Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 382197679Sdes "%s: sigblob", __func__)); 383197679Sdes buffer_get_bignum2(&b, e); 384197679Sdes buffer_get_bignum2(&b, r); 385197679Sdes rlen = buffer_len(&b); 386197679Sdes buffer_free(&b); 387197679Sdes if (rlen != 0) { 388197679Sdes error("%s: remaining bytes in signature %d", __func__, rlen); 389197679Sdes goto out; 390197679Sdes } 391197679Sdes 392262566Sdes ret = schnorr_verify(grp_p, grp_q, grp_g, SSH_DIGEST_SHA256, 393197679Sdes g_x, id, idlen, r, e); 394197679Sdes out: 395197679Sdes BN_clear_free(e); 396197679Sdes BN_clear_free(r); 397197679Sdes 398197679Sdes return ret; 399197679Sdes} 400197679Sdes 401197679Sdes/* Helper functions */ 402197679Sdes 403197679Sdes/* 404197679Sdes * Generate uniformly distributed random number in range (1, high). 405197679Sdes * Return number on success, NULL on failure. 406197679Sdes */ 407197679SdesBIGNUM * 408197679Sdesbn_rand_range_gt_one(const BIGNUM *high) 409197679Sdes{ 410197679Sdes BIGNUM *r, *tmp; 411197679Sdes int success = -1; 412197679Sdes 413197679Sdes if ((tmp = BN_new()) == NULL) { 414197679Sdes error("%s: BN_new", __func__); 415197679Sdes return NULL; 416197679Sdes } 417197679Sdes if ((r = BN_new()) == NULL) { 418197679Sdes error("%s: BN_new failed", __func__); 419197679Sdes goto out; 420197679Sdes } 421197679Sdes if (BN_set_word(tmp, 2) != 1) { 422197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 423197679Sdes goto out; 424197679Sdes } 425197679Sdes if (BN_sub(tmp, high, tmp) == -1) { 426197679Sdes error("%s: BN_sub failed (tmp = high - 2)", __func__); 427197679Sdes goto out; 428197679Sdes } 429197679Sdes if (BN_rand_range(r, tmp) == -1) { 430197679Sdes error("%s: BN_rand_range failed", __func__); 431197679Sdes goto out; 432197679Sdes } 433197679Sdes if (BN_set_word(tmp, 2) != 1) { 434197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 435197679Sdes goto out; 436197679Sdes } 437197679Sdes if (BN_add(r, r, tmp) == -1) { 438197679Sdes error("%s: BN_add failed (r = r + 2)", __func__); 439197679Sdes goto out; 440197679Sdes } 441197679Sdes success = 0; 442197679Sdes out: 443197679Sdes BN_clear_free(tmp); 444197679Sdes if (success == 0) 445197679Sdes return r; 446197679Sdes BN_clear_free(r); 447197679Sdes return NULL; 448197679Sdes} 449197679Sdes 450262566Sdes/* XXX convert all callers of this to use ssh_digest_memory() directly */ 451197679Sdes/* 452197679Sdes * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success, 453197679Sdes * with digest via 'digestp' (caller to free) and length via 'lenp'. 454197679Sdes * Returns -1 on failure. 455197679Sdes */ 456197679Sdesint 457262566Sdeshash_buffer(const u_char *buf, u_int len, int hash_alg, 458197679Sdes u_char **digestp, u_int *lenp) 459197679Sdes{ 460262566Sdes u_char digest[SSH_DIGEST_MAX_LENGTH]; 461262566Sdes u_int digest_len = ssh_digest_bytes(hash_alg); 462197679Sdes 463262566Sdes if (digest_len == 0) { 464262566Sdes error("%s: invalid hash", __func__); 465262566Sdes return -1; 466197679Sdes } 467262566Sdes if (ssh_digest_memory(hash_alg, buf, len, digest, digest_len) != 0) { 468262566Sdes error("%s: digest_memory failed", __func__); 469262566Sdes return -1; 470197679Sdes } 471197679Sdes *digestp = xmalloc(digest_len); 472197679Sdes *lenp = digest_len; 473197679Sdes memcpy(*digestp, digest, *lenp); 474197679Sdes bzero(digest, sizeof(digest)); 475197679Sdes digest_len = 0; 476262566Sdes return 0; 477197679Sdes} 478197679Sdes 479197679Sdes/* print formatted string followed by bignum */ 480197679Sdesvoid 481197679Sdesdebug3_bn(const BIGNUM *n, const char *fmt, ...) 482197679Sdes{ 483197679Sdes char *out, *h; 484197679Sdes va_list args; 485255767Sdes int ret; 486197679Sdes 487197679Sdes out = NULL; 488197679Sdes va_start(args, fmt); 489255767Sdes ret = vasprintf(&out, fmt, args); 490197679Sdes va_end(args); 491255767Sdes if (ret == -1 || out == NULL) 492197679Sdes fatal("%s: vasprintf failed", __func__); 493197679Sdes 494197679Sdes if (n == NULL) 495197679Sdes debug3("%s(null)", out); 496197679Sdes else { 497197679Sdes h = BN_bn2hex(n); 498197679Sdes debug3("%s0x%s", out, h); 499197679Sdes free(h); 500197679Sdes } 501197679Sdes free(out); 502197679Sdes} 503197679Sdes 504197679Sdes/* print formatted string followed by buffer contents in hex */ 505197679Sdesvoid 506197679Sdesdebug3_buf(const u_char *buf, u_int len, const char *fmt, ...) 507197679Sdes{ 508197679Sdes char *out, h[65]; 509197679Sdes u_int i, j; 510197679Sdes va_list args; 511255767Sdes int ret; 512197679Sdes 513197679Sdes out = NULL; 514197679Sdes va_start(args, fmt); 515255767Sdes ret = vasprintf(&out, fmt, args); 516197679Sdes va_end(args); 517255767Sdes if (ret == -1 || out == NULL) 518197679Sdes fatal("%s: vasprintf failed", __func__); 519197679Sdes 520197679Sdes debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : ""); 521197679Sdes free(out); 522197679Sdes if (buf == NULL) 523197679Sdes return; 524197679Sdes 525197679Sdes *h = '\0'; 526197679Sdes for (i = j = 0; i < len; i++) { 527197679Sdes snprintf(h + j, sizeof(h) - j, "%02x", buf[i]); 528197679Sdes j += 2; 529197679Sdes if (j >= sizeof(h) - 1 || i == len - 1) { 530197679Sdes debug3(" %s", h); 531197679Sdes *h = '\0'; 532197679Sdes j = 0; 533197679Sdes } 534197679Sdes } 535197679Sdes} 536197679Sdes 537197679Sdes/* 538197679Sdes * Construct a MODP group from hex strings p (which must be a safe 539197679Sdes * prime) and g, automatically calculating subgroup q as (p / 2) 540197679Sdes */ 541197679Sdesstruct modp_group * 542197679Sdesmodp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p) 543197679Sdes{ 544197679Sdes struct modp_group *ret; 545197679Sdes 546258343Sdes ret = xcalloc(1, sizeof(*ret)); 547197679Sdes ret->p = ret->q = ret->g = NULL; 548197679Sdes if (BN_hex2bn(&ret->p, grp_p) == 0 || 549197679Sdes BN_hex2bn(&ret->g, grp_g) == 0) 550197679Sdes fatal("%s: BN_hex2bn", __func__); 551197679Sdes /* Subgroup order is p/2 (p is a safe prime) */ 552197679Sdes if ((ret->q = BN_new()) == NULL) 553197679Sdes fatal("%s: BN_new", __func__); 554197679Sdes if (BN_rshift1(ret->q, ret->p) != 1) 555197679Sdes fatal("%s: BN_rshift1", __func__); 556197679Sdes 557197679Sdes return ret; 558197679Sdes} 559197679Sdes 560197679Sdesvoid 561197679Sdesmodp_group_free(struct modp_group *grp) 562197679Sdes{ 563197679Sdes if (grp->g != NULL) 564197679Sdes BN_clear_free(grp->g); 565197679Sdes if (grp->p != NULL) 566197679Sdes BN_clear_free(grp->p); 567197679Sdes if (grp->q != NULL) 568197679Sdes BN_clear_free(grp->q); 569197679Sdes bzero(grp, sizeof(*grp)); 570255767Sdes free(grp); 571197679Sdes} 572197679Sdes 573197679Sdes/* main() function for self-test */ 574197679Sdes 575189006Sdes#ifdef SCHNORR_MAIN 576189006Sdesstatic void 577189006Sdesschnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, 578189006Sdes const BIGNUM *grp_g, const BIGNUM *x) 579189006Sdes{ 580189006Sdes BIGNUM *g_x; 581189006Sdes u_char *sig; 582189006Sdes u_int siglen; 583189006Sdes BN_CTX *bn_ctx; 584189006Sdes 585189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) 586189006Sdes fatal("%s: BN_CTX_new", __func__); 587189006Sdes if ((g_x = BN_new()) == NULL) 588189006Sdes fatal("%s: BN_new", __func__); 589189006Sdes 590189006Sdes if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) 591189006Sdes fatal("%s: g_x", __func__); 592197679Sdes if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4, 593197679Sdes &sig, &siglen)) 594189006Sdes fatal("%s: schnorr_sign", __func__); 595197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 596189006Sdes sig, siglen) != 1) 597189006Sdes fatal("%s: verify fail", __func__); 598197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4, 599189006Sdes sig, siglen) != 0) 600189006Sdes fatal("%s: verify should have failed (bad ID)", __func__); 601189006Sdes sig[4] ^= 1; 602197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 603189006Sdes sig, siglen) != 0) 604189006Sdes fatal("%s: verify should have failed (bit error)", __func__); 605255767Sdes free(sig); 606189006Sdes BN_free(g_x); 607189006Sdes BN_CTX_free(bn_ctx); 608189006Sdes} 609189006Sdes 610189006Sdesstatic void 611189006Sdesschnorr_selftest(void) 612189006Sdes{ 613189006Sdes BIGNUM *x; 614197679Sdes struct modp_group *grp; 615189006Sdes u_int i; 616189006Sdes char *hh; 617189006Sdes 618189006Sdes grp = jpake_default_group(); 619189006Sdes if ((x = BN_new()) == NULL) 620189006Sdes fatal("%s: BN_new", __func__); 621189006Sdes SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); 622189006Sdes SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); 623189006Sdes SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); 624189006Sdes 625189006Sdes /* [1, 20) */ 626189006Sdes for (i = 1; i < 20; i++) { 627189006Sdes printf("x = %u\n", i); 628189006Sdes fflush(stdout); 629189006Sdes if (BN_set_word(x, i) != 1) 630189006Sdes fatal("%s: set x word", __func__); 631189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 632189006Sdes } 633189006Sdes 634189006Sdes /* 100 x random [0, p) */ 635189006Sdes for (i = 0; i < 100; i++) { 636189006Sdes if (BN_rand_range(x, grp->p) != 1) 637189006Sdes fatal("%s: BN_rand_range", __func__); 638189006Sdes hh = BN_bn2hex(x); 639189006Sdes printf("x = (random) 0x%s\n", hh); 640189006Sdes free(hh); 641189006Sdes fflush(stdout); 642189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 643189006Sdes } 644189006Sdes 645189006Sdes /* [q-20, q) */ 646189006Sdes if (BN_set_word(x, 20) != 1) 647189006Sdes fatal("%s: BN_set_word (x = 20)", __func__); 648189006Sdes if (BN_sub(x, grp->q, x) != 1) 649189006Sdes fatal("%s: BN_sub (q - x)", __func__); 650189006Sdes for (i = 0; i < 19; i++) { 651189006Sdes hh = BN_bn2hex(x); 652189006Sdes printf("x = (q - %d) 0x%s\n", 20 - i, hh); 653189006Sdes free(hh); 654189006Sdes fflush(stdout); 655189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 656189006Sdes if (BN_add(x, x, BN_value_one()) != 1) 657189006Sdes fatal("%s: BN_add (x + 1)", __func__); 658189006Sdes } 659189006Sdes BN_free(x); 660189006Sdes} 661189006Sdes 662189006Sdesint 663189006Sdesmain(int argc, char **argv) 664189006Sdes{ 665189006Sdes log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); 666189006Sdes 667189006Sdes schnorr_selftest(); 668189006Sdes return 0; 669189006Sdes} 670189006Sdes#endif 671189006Sdes 672192595Sdes#endif 673