1263970Sdes/* $OpenBSD: schnorr.c,v 1.9 2014/01/09 23:20:00 djm Exp $ */ 2192595Sdes/* $FreeBSD$ */ 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" 30263970Sdes__RCSID("$FreeBSD$"); 31189006Sdes 32189006Sdes#include <sys/types.h> 33189006Sdes 34189006Sdes#include <string.h> 35189006Sdes#include <stdarg.h> 36189006Sdes#include <stdio.h> 37189006Sdes 38189006Sdes#include <openssl/evp.h> 39189006Sdes#include <openssl/bn.h> 40189006Sdes 41189006Sdes#include "xmalloc.h" 42189006Sdes#include "buffer.h" 43189006Sdes#include "log.h" 44189006Sdes 45197679Sdes#include "schnorr.h" 46263970Sdes#include "digest.h" 47189006Sdes 48192595Sdes#ifdef JPAKE 49192595Sdes 50197679Sdes#include "openbsd-compat/openssl-compat.h" 51197679Sdes 52189006Sdes/* #define SCHNORR_DEBUG */ /* Privacy-violating debugging */ 53189006Sdes/* #define SCHNORR_MAIN */ /* Include main() selftest */ 54189006Sdes 55189006Sdes#ifndef SCHNORR_DEBUG 56189006Sdes# define SCHNORR_DEBUG_BN(a) 57189006Sdes# define SCHNORR_DEBUG_BUF(a) 58189006Sdes#else 59197679Sdes# define SCHNORR_DEBUG_BN(a) debug3_bn a 60197679Sdes# define SCHNORR_DEBUG_BUF(a) debug3_buf a 61189006Sdes#endif /* SCHNORR_DEBUG */ 62189006Sdes 63189006Sdes/* 64189006Sdes * Calculate hash component of Schnorr signature H(g || g^v || g^x || id) 65263970Sdes * using the hash function defined by "hash_alg". Returns signature as 66197679Sdes * bignum or NULL on error. 67189006Sdes */ 68189006Sdesstatic BIGNUM * 69189006Sdesschnorr_hash(const BIGNUM *p, const BIGNUM *q, const BIGNUM *g, 70263970Sdes int hash_alg, const BIGNUM *g_v, const BIGNUM *g_x, 71189006Sdes const u_char *id, u_int idlen) 72189006Sdes{ 73189006Sdes u_char *digest; 74189006Sdes u_int digest_len; 75189006Sdes BIGNUM *h; 76189006Sdes Buffer b; 77189006Sdes int success = -1; 78189006Sdes 79189006Sdes if ((h = BN_new()) == NULL) { 80189006Sdes error("%s: BN_new", __func__); 81189006Sdes return NULL; 82189006Sdes } 83189006Sdes 84189006Sdes buffer_init(&b); 85189006Sdes 86189006Sdes /* h = H(g || p || q || g^v || g^x || id) */ 87189006Sdes buffer_put_bignum2(&b, g); 88189006Sdes buffer_put_bignum2(&b, p); 89189006Sdes buffer_put_bignum2(&b, q); 90189006Sdes buffer_put_bignum2(&b, g_v); 91189006Sdes buffer_put_bignum2(&b, g_x); 92189006Sdes buffer_put_string(&b, id, idlen); 93189006Sdes 94189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 95189006Sdes "%s: hashblob", __func__)); 96263970Sdes if (hash_buffer(buffer_ptr(&b), buffer_len(&b), hash_alg, 97189006Sdes &digest, &digest_len) != 0) { 98189006Sdes error("%s: hash_buffer", __func__); 99189006Sdes goto out; 100189006Sdes } 101189006Sdes if (BN_bin2bn(digest, (int)digest_len, h) == NULL) { 102189006Sdes error("%s: BN_bin2bn", __func__); 103189006Sdes goto out; 104189006Sdes } 105189006Sdes success = 0; 106189006Sdes SCHNORR_DEBUG_BN((h, "%s: h = ", __func__)); 107189006Sdes out: 108189006Sdes buffer_free(&b); 109189006Sdes bzero(digest, digest_len); 110263970Sdes free(digest); 111189006Sdes digest_len = 0; 112189006Sdes if (success == 0) 113189006Sdes return h; 114189006Sdes BN_clear_free(h); 115189006Sdes return NULL; 116189006Sdes} 117189006Sdes 118189006Sdes/* 119189006Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 120189006Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 121263970Sdes * using the hash function "hash_alg". 122189006Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 123189006Sdes * replay salt. 124197679Sdes * 125197679Sdes * On success, 0 is returned. The signature values are returned as *e_p 126197679Sdes * (g^v mod p) and *r_p (v - xh mod q). The caller must free these values. 127197679Sdes * On failure, -1 is returned. 128189006Sdes */ 129189006Sdesint 130189006Sdesschnorr_sign(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 131263970Sdes int hash_alg, const BIGNUM *x, const BIGNUM *g_x, 132197679Sdes const u_char *id, u_int idlen, BIGNUM **r_p, BIGNUM **e_p) 133189006Sdes{ 134189006Sdes int success = -1; 135189006Sdes BIGNUM *h, *tmp, *v, *g_v, *r; 136189006Sdes BN_CTX *bn_ctx; 137189006Sdes 138189006Sdes SCHNORR_DEBUG_BN((x, "%s: x = ", __func__)); 139189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 140189006Sdes 141189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 142189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 143189006Sdes error("%s: g_x < 1", __func__); 144189006Sdes return -1; 145189006Sdes } 146221420Sdes if (BN_cmp(g_x, grp_p) >= 0) { 147221420Sdes error("%s: g_x > g", __func__); 148221420Sdes return -1; 149221420Sdes } 150189006Sdes 151189006Sdes h = g_v = r = tmp = v = NULL; 152189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 153189006Sdes error("%s: BN_CTX_new", __func__); 154189006Sdes goto out; 155189006Sdes } 156189006Sdes if ((g_v = BN_new()) == NULL || 157189006Sdes (r = BN_new()) == NULL || 158189006Sdes (tmp = BN_new()) == NULL) { 159189006Sdes error("%s: BN_new", __func__); 160189006Sdes goto out; 161189006Sdes } 162189006Sdes 163189006Sdes /* 164189006Sdes * v must be a random element of Zq, so 1 <= v < q 165189006Sdes * we also exclude v = 1, since g^1 looks dangerous 166189006Sdes */ 167189006Sdes if ((v = bn_rand_range_gt_one(grp_p)) == NULL) { 168189006Sdes error("%s: bn_rand_range2", __func__); 169189006Sdes goto out; 170189006Sdes } 171189006Sdes SCHNORR_DEBUG_BN((v, "%s: v = ", __func__)); 172189006Sdes 173189006Sdes /* g_v = g^v mod p */ 174189006Sdes if (BN_mod_exp(g_v, grp_g, v, grp_p, bn_ctx) == -1) { 175189006Sdes error("%s: BN_mod_exp (g^v mod p)", __func__); 176189006Sdes goto out; 177189006Sdes } 178189006Sdes SCHNORR_DEBUG_BN((g_v, "%s: g_v = ", __func__)); 179189006Sdes 180189006Sdes /* h = H(g || g^v || g^x || id) */ 181263970Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, hash_alg, g_v, g_x, 182189006Sdes id, idlen)) == NULL) { 183189006Sdes error("%s: schnorr_hash failed", __func__); 184189006Sdes goto out; 185189006Sdes } 186189006Sdes 187189006Sdes /* r = v - xh mod q */ 188189006Sdes if (BN_mod_mul(tmp, x, h, grp_q, bn_ctx) == -1) { 189189006Sdes error("%s: BN_mod_mul (tmp = xv mod q)", __func__); 190189006Sdes goto out; 191189006Sdes } 192189006Sdes if (BN_mod_sub(r, v, tmp, grp_q, bn_ctx) == -1) { 193189006Sdes error("%s: BN_mod_mul (r = v - tmp)", __func__); 194189006Sdes goto out; 195189006Sdes } 196197679Sdes SCHNORR_DEBUG_BN((g_v, "%s: e = ", __func__)); 197189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 198189006Sdes 199197679Sdes *e_p = g_v; 200197679Sdes *r_p = r; 201197679Sdes 202197679Sdes success = 0; 203197679Sdes out: 204197679Sdes BN_CTX_free(bn_ctx); 205197679Sdes if (h != NULL) 206197679Sdes BN_clear_free(h); 207197679Sdes if (v != NULL) 208197679Sdes BN_clear_free(v); 209197679Sdes BN_clear_free(tmp); 210197679Sdes 211197679Sdes return success; 212197679Sdes} 213197679Sdes 214197679Sdes/* 215197679Sdes * Generate Schnorr signature to prove knowledge of private value 'x' used 216197679Sdes * in public exponent g^x, under group defined by 'grp_p', 'grp_q' and 'grp_g' 217197679Sdes * using a SHA256 hash. 218197679Sdes * 'idlen' bytes from 'id' will be included in the signature hash as an anti- 219197679Sdes * replay salt. 220197679Sdes * On success, 0 is returned and *siglen bytes of signature are returned in 221197679Sdes * *sig (caller to free). Returns -1 on failure. 222197679Sdes */ 223197679Sdesint 224197679Sdesschnorr_sign_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 225197679Sdes const BIGNUM *x, const BIGNUM *g_x, const u_char *id, u_int idlen, 226197679Sdes u_char **sig, u_int *siglen) 227197679Sdes{ 228197679Sdes Buffer b; 229197679Sdes BIGNUM *r, *e; 230197679Sdes 231263970Sdes if (schnorr_sign(grp_p, grp_q, grp_g, SSH_DIGEST_SHA256, 232197679Sdes x, g_x, id, idlen, &r, &e) != 0) 233197679Sdes return -1; 234197679Sdes 235197679Sdes /* Signature is (e, r) */ 236189006Sdes buffer_init(&b); 237189006Sdes /* XXX sigtype-hash as string? */ 238197679Sdes buffer_put_bignum2(&b, e); 239189006Sdes buffer_put_bignum2(&b, r); 240189006Sdes *siglen = buffer_len(&b); 241189006Sdes *sig = xmalloc(*siglen); 242189006Sdes memcpy(*sig, buffer_ptr(&b), *siglen); 243189006Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 244189006Sdes "%s: sigblob", __func__)); 245189006Sdes buffer_free(&b); 246197679Sdes 247189006Sdes BN_clear_free(r); 248197679Sdes BN_clear_free(e); 249189006Sdes 250197679Sdes return 0; 251189006Sdes} 252189006Sdes 253189006Sdes/* 254197679Sdes * Verify Schnorr signature { r (v - xh mod q), e (g^v mod p) } against 255197679Sdes * public exponent g_x (g^x) under group defined by 'grp_p', 'grp_q' and 256263970Sdes * 'grp_g' using hash "hash_alg". 257189006Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 258189006Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 259189006Sdes */ 260189006Sdesint 261189006Sdesschnorr_verify(const BIGNUM *grp_p, const BIGNUM *grp_q, const BIGNUM *grp_g, 262263970Sdes int hash_alg, const BIGNUM *g_x, const u_char *id, u_int idlen, 263197679Sdes const BIGNUM *r, const BIGNUM *e) 264189006Sdes{ 265189006Sdes int success = -1; 266221420Sdes BIGNUM *h = NULL, *g_xh = NULL, *g_r = NULL, *gx_q = NULL; 267221420Sdes BIGNUM *expected = NULL; 268189006Sdes BN_CTX *bn_ctx; 269189006Sdes 270189006Sdes SCHNORR_DEBUG_BN((g_x, "%s: g_x = ", __func__)); 271189006Sdes 272189006Sdes /* Avoid degenerate cases: g^0 yields a spoofable signature */ 273189006Sdes if (BN_cmp(g_x, BN_value_one()) <= 0) { 274221420Sdes error("%s: g_x <= 1", __func__); 275189006Sdes return -1; 276189006Sdes } 277221420Sdes if (BN_cmp(g_x, grp_p) >= 0) { 278221420Sdes error("%s: g_x >= p", __func__); 279221420Sdes return -1; 280221420Sdes } 281189006Sdes 282197679Sdes h = g_xh = g_r = expected = NULL; 283189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) { 284189006Sdes error("%s: BN_CTX_new", __func__); 285189006Sdes goto out; 286189006Sdes } 287197679Sdes if ((g_xh = BN_new()) == NULL || 288189006Sdes (g_r = BN_new()) == NULL || 289221420Sdes (gx_q = BN_new()) == NULL || 290189006Sdes (expected = BN_new()) == NULL) { 291189006Sdes error("%s: BN_new", __func__); 292189006Sdes goto out; 293189006Sdes } 294189006Sdes 295197679Sdes SCHNORR_DEBUG_BN((e, "%s: e = ", __func__)); 296189006Sdes SCHNORR_DEBUG_BN((r, "%s: r = ", __func__)); 297189006Sdes 298221420Sdes /* gx_q = (g^x)^q must === 1 mod p */ 299221420Sdes if (BN_mod_exp(gx_q, g_x, grp_q, grp_p, bn_ctx) == -1) { 300221420Sdes error("%s: BN_mod_exp (g_x^q mod p)", __func__); 301221420Sdes goto out; 302221420Sdes } 303221420Sdes if (BN_cmp(gx_q, BN_value_one()) != 0) { 304221420Sdes error("%s: Invalid signature (g^x)^q != 1 mod p", __func__); 305221420Sdes goto out; 306221420Sdes } 307221420Sdes 308221420Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 309189006Sdes /* h = H(g || g^v || g^x || id) */ 310263970Sdes if ((h = schnorr_hash(grp_p, grp_q, grp_g, hash_alg, e, g_x, 311189006Sdes id, idlen)) == NULL) { 312189006Sdes error("%s: schnorr_hash failed", __func__); 313189006Sdes goto out; 314189006Sdes } 315189006Sdes 316189006Sdes /* g_xh = (g^x)^h */ 317189006Sdes if (BN_mod_exp(g_xh, g_x, h, grp_p, bn_ctx) == -1) { 318189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 319189006Sdes goto out; 320189006Sdes } 321189006Sdes SCHNORR_DEBUG_BN((g_xh, "%s: g_xh = ", __func__)); 322189006Sdes 323189006Sdes /* g_r = g^r */ 324189006Sdes if (BN_mod_exp(g_r, grp_g, r, grp_p, bn_ctx) == -1) { 325189006Sdes error("%s: BN_mod_exp (g_x^h mod p)", __func__); 326189006Sdes goto out; 327189006Sdes } 328189006Sdes SCHNORR_DEBUG_BN((g_r, "%s: g_r = ", __func__)); 329189006Sdes 330189006Sdes /* expected = g^r * g_xh */ 331189006Sdes if (BN_mod_mul(expected, g_r, g_xh, grp_p, bn_ctx) == -1) { 332189006Sdes error("%s: BN_mod_mul (expected = g_r mod p)", __func__); 333189006Sdes goto out; 334189006Sdes } 335189006Sdes SCHNORR_DEBUG_BN((expected, "%s: expected = ", __func__)); 336189006Sdes 337197679Sdes /* Check e == expected */ 338197679Sdes success = BN_cmp(expected, e) == 0; 339189006Sdes out: 340189006Sdes BN_CTX_free(bn_ctx); 341189006Sdes if (h != NULL) 342189006Sdes BN_clear_free(h); 343221420Sdes if (gx_q != NULL) 344221420Sdes BN_clear_free(gx_q); 345221420Sdes if (g_xh != NULL) 346221420Sdes BN_clear_free(g_xh); 347221420Sdes if (g_r != NULL) 348221420Sdes BN_clear_free(g_r); 349221420Sdes if (expected != NULL) 350221420Sdes BN_clear_free(expected); 351189006Sdes return success; 352189006Sdes} 353189006Sdes 354197679Sdes/* 355197679Sdes * Verify Schnorr signature 'sig' of length 'siglen' against public exponent 356197679Sdes * g_x (g^x) under group defined by 'grp_p', 'grp_q' and 'grp_g' using a 357197679Sdes * SHA256 hash. 358197679Sdes * Signature hash will be salted with 'idlen' bytes from 'id'. 359197679Sdes * Returns -1 on failure, 0 on incorrect signature or 1 on matching signature. 360197679Sdes */ 361197679Sdesint 362197679Sdesschnorr_verify_buf(const BIGNUM *grp_p, const BIGNUM *grp_q, 363197679Sdes const BIGNUM *grp_g, 364197679Sdes const BIGNUM *g_x, const u_char *id, u_int idlen, 365197679Sdes const u_char *sig, u_int siglen) 366197679Sdes{ 367197679Sdes Buffer b; 368197679Sdes int ret = -1; 369197679Sdes u_int rlen; 370197679Sdes BIGNUM *r, *e; 371197679Sdes 372197679Sdes e = r = NULL; 373197679Sdes if ((e = BN_new()) == NULL || 374197679Sdes (r = BN_new()) == NULL) { 375197679Sdes error("%s: BN_new", __func__); 376197679Sdes goto out; 377197679Sdes } 378197679Sdes 379197679Sdes /* Extract g^v and r from signature blob */ 380197679Sdes buffer_init(&b); 381197679Sdes buffer_append(&b, sig, siglen); 382197679Sdes SCHNORR_DEBUG_BUF((buffer_ptr(&b), buffer_len(&b), 383197679Sdes "%s: sigblob", __func__)); 384197679Sdes buffer_get_bignum2(&b, e); 385197679Sdes buffer_get_bignum2(&b, r); 386197679Sdes rlen = buffer_len(&b); 387197679Sdes buffer_free(&b); 388197679Sdes if (rlen != 0) { 389197679Sdes error("%s: remaining bytes in signature %d", __func__, rlen); 390197679Sdes goto out; 391197679Sdes } 392197679Sdes 393263970Sdes ret = schnorr_verify(grp_p, grp_q, grp_g, SSH_DIGEST_SHA256, 394197679Sdes g_x, id, idlen, r, e); 395197679Sdes out: 396197679Sdes BN_clear_free(e); 397197679Sdes BN_clear_free(r); 398197679Sdes 399197679Sdes return ret; 400197679Sdes} 401197679Sdes 402197679Sdes/* Helper functions */ 403197679Sdes 404197679Sdes/* 405197679Sdes * Generate uniformly distributed random number in range (1, high). 406197679Sdes * Return number on success, NULL on failure. 407197679Sdes */ 408197679SdesBIGNUM * 409197679Sdesbn_rand_range_gt_one(const BIGNUM *high) 410197679Sdes{ 411197679Sdes BIGNUM *r, *tmp; 412197679Sdes int success = -1; 413197679Sdes 414197679Sdes if ((tmp = BN_new()) == NULL) { 415197679Sdes error("%s: BN_new", __func__); 416197679Sdes return NULL; 417197679Sdes } 418197679Sdes if ((r = BN_new()) == NULL) { 419197679Sdes error("%s: BN_new failed", __func__); 420197679Sdes goto out; 421197679Sdes } 422197679Sdes if (BN_set_word(tmp, 2) != 1) { 423197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 424197679Sdes goto out; 425197679Sdes } 426197679Sdes if (BN_sub(tmp, high, tmp) == -1) { 427197679Sdes error("%s: BN_sub failed (tmp = high - 2)", __func__); 428197679Sdes goto out; 429197679Sdes } 430197679Sdes if (BN_rand_range(r, tmp) == -1) { 431197679Sdes error("%s: BN_rand_range failed", __func__); 432197679Sdes goto out; 433197679Sdes } 434197679Sdes if (BN_set_word(tmp, 2) != 1) { 435197679Sdes error("%s: BN_set_word(tmp, 2)", __func__); 436197679Sdes goto out; 437197679Sdes } 438197679Sdes if (BN_add(r, r, tmp) == -1) { 439197679Sdes error("%s: BN_add failed (r = r + 2)", __func__); 440197679Sdes goto out; 441197679Sdes } 442197679Sdes success = 0; 443197679Sdes out: 444197679Sdes BN_clear_free(tmp); 445197679Sdes if (success == 0) 446197679Sdes return r; 447197679Sdes BN_clear_free(r); 448197679Sdes return NULL; 449197679Sdes} 450197679Sdes 451263970Sdes/* XXX convert all callers of this to use ssh_digest_memory() directly */ 452197679Sdes/* 453197679Sdes * Hash contents of buffer 'b' with hash 'md'. Returns 0 on success, 454197679Sdes * with digest via 'digestp' (caller to free) and length via 'lenp'. 455197679Sdes * Returns -1 on failure. 456197679Sdes */ 457197679Sdesint 458263970Sdeshash_buffer(const u_char *buf, u_int len, int hash_alg, 459197679Sdes u_char **digestp, u_int *lenp) 460197679Sdes{ 461263970Sdes u_char digest[SSH_DIGEST_MAX_LENGTH]; 462263970Sdes u_int digest_len = ssh_digest_bytes(hash_alg); 463197679Sdes 464263970Sdes if (digest_len == 0) { 465263970Sdes error("%s: invalid hash", __func__); 466263970Sdes return -1; 467197679Sdes } 468263970Sdes if (ssh_digest_memory(hash_alg, buf, len, digest, digest_len) != 0) { 469263970Sdes error("%s: digest_memory failed", __func__); 470263970Sdes return -1; 471197679Sdes } 472197679Sdes *digestp = xmalloc(digest_len); 473197679Sdes *lenp = digest_len; 474197679Sdes memcpy(*digestp, digest, *lenp); 475197679Sdes bzero(digest, sizeof(digest)); 476197679Sdes digest_len = 0; 477263970Sdes return 0; 478197679Sdes} 479197679Sdes 480197679Sdes/* print formatted string followed by bignum */ 481197679Sdesvoid 482197679Sdesdebug3_bn(const BIGNUM *n, const char *fmt, ...) 483197679Sdes{ 484197679Sdes char *out, *h; 485197679Sdes va_list args; 486263970Sdes int ret; 487197679Sdes 488197679Sdes out = NULL; 489197679Sdes va_start(args, fmt); 490263970Sdes ret = vasprintf(&out, fmt, args); 491197679Sdes va_end(args); 492263970Sdes if (ret == -1 || out == NULL) 493197679Sdes fatal("%s: vasprintf failed", __func__); 494197679Sdes 495197679Sdes if (n == NULL) 496197679Sdes debug3("%s(null)", out); 497197679Sdes else { 498197679Sdes h = BN_bn2hex(n); 499197679Sdes debug3("%s0x%s", out, h); 500197679Sdes free(h); 501197679Sdes } 502197679Sdes free(out); 503197679Sdes} 504197679Sdes 505197679Sdes/* print formatted string followed by buffer contents in hex */ 506197679Sdesvoid 507197679Sdesdebug3_buf(const u_char *buf, u_int len, const char *fmt, ...) 508197679Sdes{ 509197679Sdes char *out, h[65]; 510197679Sdes u_int i, j; 511197679Sdes va_list args; 512263970Sdes int ret; 513197679Sdes 514197679Sdes out = NULL; 515197679Sdes va_start(args, fmt); 516263970Sdes ret = vasprintf(&out, fmt, args); 517197679Sdes va_end(args); 518263970Sdes if (ret == -1 || out == NULL) 519197679Sdes fatal("%s: vasprintf failed", __func__); 520197679Sdes 521197679Sdes debug3("%s length %u%s", out, len, buf == NULL ? " (null)" : ""); 522197679Sdes free(out); 523197679Sdes if (buf == NULL) 524197679Sdes return; 525197679Sdes 526197679Sdes *h = '\0'; 527197679Sdes for (i = j = 0; i < len; i++) { 528197679Sdes snprintf(h + j, sizeof(h) - j, "%02x", buf[i]); 529197679Sdes j += 2; 530197679Sdes if (j >= sizeof(h) - 1 || i == len - 1) { 531197679Sdes debug3(" %s", h); 532197679Sdes *h = '\0'; 533197679Sdes j = 0; 534197679Sdes } 535197679Sdes } 536197679Sdes} 537197679Sdes 538197679Sdes/* 539197679Sdes * Construct a MODP group from hex strings p (which must be a safe 540197679Sdes * prime) and g, automatically calculating subgroup q as (p / 2) 541197679Sdes */ 542197679Sdesstruct modp_group * 543197679Sdesmodp_group_from_g_and_safe_p(const char *grp_g, const char *grp_p) 544197679Sdes{ 545197679Sdes struct modp_group *ret; 546197679Sdes 547263970Sdes ret = xcalloc(1, sizeof(*ret)); 548197679Sdes ret->p = ret->q = ret->g = NULL; 549197679Sdes if (BN_hex2bn(&ret->p, grp_p) == 0 || 550197679Sdes BN_hex2bn(&ret->g, grp_g) == 0) 551197679Sdes fatal("%s: BN_hex2bn", __func__); 552197679Sdes /* Subgroup order is p/2 (p is a safe prime) */ 553197679Sdes if ((ret->q = BN_new()) == NULL) 554197679Sdes fatal("%s: BN_new", __func__); 555197679Sdes if (BN_rshift1(ret->q, ret->p) != 1) 556197679Sdes fatal("%s: BN_rshift1", __func__); 557197679Sdes 558197679Sdes return ret; 559197679Sdes} 560197679Sdes 561197679Sdesvoid 562197679Sdesmodp_group_free(struct modp_group *grp) 563197679Sdes{ 564197679Sdes if (grp->g != NULL) 565197679Sdes BN_clear_free(grp->g); 566197679Sdes if (grp->p != NULL) 567197679Sdes BN_clear_free(grp->p); 568197679Sdes if (grp->q != NULL) 569197679Sdes BN_clear_free(grp->q); 570197679Sdes bzero(grp, sizeof(*grp)); 571263970Sdes free(grp); 572197679Sdes} 573197679Sdes 574197679Sdes/* main() function for self-test */ 575197679Sdes 576189006Sdes#ifdef SCHNORR_MAIN 577189006Sdesstatic void 578189006Sdesschnorr_selftest_one(const BIGNUM *grp_p, const BIGNUM *grp_q, 579189006Sdes const BIGNUM *grp_g, const BIGNUM *x) 580189006Sdes{ 581189006Sdes BIGNUM *g_x; 582189006Sdes u_char *sig; 583189006Sdes u_int siglen; 584189006Sdes BN_CTX *bn_ctx; 585189006Sdes 586189006Sdes if ((bn_ctx = BN_CTX_new()) == NULL) 587189006Sdes fatal("%s: BN_CTX_new", __func__); 588189006Sdes if ((g_x = BN_new()) == NULL) 589189006Sdes fatal("%s: BN_new", __func__); 590189006Sdes 591189006Sdes if (BN_mod_exp(g_x, grp_g, x, grp_p, bn_ctx) == -1) 592189006Sdes fatal("%s: g_x", __func__); 593197679Sdes if (schnorr_sign_buf(grp_p, grp_q, grp_g, x, g_x, "junk", 4, 594197679Sdes &sig, &siglen)) 595189006Sdes fatal("%s: schnorr_sign", __func__); 596197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 597189006Sdes sig, siglen) != 1) 598189006Sdes fatal("%s: verify fail", __func__); 599197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "JUNK", 4, 600189006Sdes sig, siglen) != 0) 601189006Sdes fatal("%s: verify should have failed (bad ID)", __func__); 602189006Sdes sig[4] ^= 1; 603197679Sdes if (schnorr_verify_buf(grp_p, grp_q, grp_g, g_x, "junk", 4, 604189006Sdes sig, siglen) != 0) 605189006Sdes fatal("%s: verify should have failed (bit error)", __func__); 606263970Sdes free(sig); 607189006Sdes BN_free(g_x); 608189006Sdes BN_CTX_free(bn_ctx); 609189006Sdes} 610189006Sdes 611189006Sdesstatic void 612189006Sdesschnorr_selftest(void) 613189006Sdes{ 614189006Sdes BIGNUM *x; 615197679Sdes struct modp_group *grp; 616189006Sdes u_int i; 617189006Sdes char *hh; 618189006Sdes 619189006Sdes grp = jpake_default_group(); 620189006Sdes if ((x = BN_new()) == NULL) 621189006Sdes fatal("%s: BN_new", __func__); 622189006Sdes SCHNORR_DEBUG_BN((grp->p, "%s: grp->p = ", __func__)); 623189006Sdes SCHNORR_DEBUG_BN((grp->q, "%s: grp->q = ", __func__)); 624189006Sdes SCHNORR_DEBUG_BN((grp->g, "%s: grp->g = ", __func__)); 625189006Sdes 626189006Sdes /* [1, 20) */ 627189006Sdes for (i = 1; i < 20; i++) { 628189006Sdes printf("x = %u\n", i); 629189006Sdes fflush(stdout); 630189006Sdes if (BN_set_word(x, i) != 1) 631189006Sdes fatal("%s: set x word", __func__); 632189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 633189006Sdes } 634189006Sdes 635189006Sdes /* 100 x random [0, p) */ 636189006Sdes for (i = 0; i < 100; i++) { 637189006Sdes if (BN_rand_range(x, grp->p) != 1) 638189006Sdes fatal("%s: BN_rand_range", __func__); 639189006Sdes hh = BN_bn2hex(x); 640189006Sdes printf("x = (random) 0x%s\n", hh); 641189006Sdes free(hh); 642189006Sdes fflush(stdout); 643189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 644189006Sdes } 645189006Sdes 646189006Sdes /* [q-20, q) */ 647189006Sdes if (BN_set_word(x, 20) != 1) 648189006Sdes fatal("%s: BN_set_word (x = 20)", __func__); 649189006Sdes if (BN_sub(x, grp->q, x) != 1) 650189006Sdes fatal("%s: BN_sub (q - x)", __func__); 651189006Sdes for (i = 0; i < 19; i++) { 652189006Sdes hh = BN_bn2hex(x); 653189006Sdes printf("x = (q - %d) 0x%s\n", 20 - i, hh); 654189006Sdes free(hh); 655189006Sdes fflush(stdout); 656189006Sdes schnorr_selftest_one(grp->p, grp->q, grp->g, x); 657189006Sdes if (BN_add(x, x, BN_value_one()) != 1) 658189006Sdes fatal("%s: BN_add (x + 1)", __func__); 659189006Sdes } 660189006Sdes BN_free(x); 661189006Sdes} 662189006Sdes 663189006Sdesint 664189006Sdesmain(int argc, char **argv) 665189006Sdes{ 666189006Sdes log_init(argv[0], SYSLOG_LEVEL_DEBUG3, SYSLOG_FACILITY_USER, 1); 667189006Sdes 668189006Sdes schnorr_selftest(); 669189006Sdes return 0; 670189006Sdes} 671189006Sdes#endif 672189006Sdes 673192595Sdes#endif 674