diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c index 3850946a..a08ae310 100644 --- a/cipher/ecc-eddsa.c +++ b/cipher/ecc-eddsa.c @@ -1,864 +1,864 @@ /* ecc-eddsa.c - Elliptic Curve EdDSA signatures * Copyright (C) 2013, 2014 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "context.h" #include "ec-context.h" #include "ecc-common.h" void reverse_buffer (unsigned char *buffer, unsigned int length) { unsigned int tmp, i; for (i=0; i < length/2; i++) { tmp = buffer[i]; buffer[i] = buffer[length-1-i]; buffer[length-1-i] = tmp; } } /* Helper to scan a hex string. */ static gcry_mpi_t scanval (const char *string) { gpg_err_code_t rc; gcry_mpi_t val; rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL); if (rc) log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc)); return val; } /* Encode MPI using the EdDSA scheme. MINLEN specifies the required length of the buffer in bytes. On success 0 is returned an a malloced buffer with the encoded point is stored at R_BUFFER; the length of this buffer is stored at R_BUFLEN. */ static gpg_err_code_t eddsa_encodempi (gcry_mpi_t mpi, unsigned int minlen, unsigned char **r_buffer, unsigned int *r_buflen) { unsigned char *rawmpi; unsigned int rawmpilen; rawmpi = _gcry_mpi_get_buffer (mpi, minlen, &rawmpilen, NULL); if (!rawmpi) return gpg_err_code_from_syserror (); *r_buffer = rawmpi; *r_buflen = rawmpilen; return 0; } /* Encode (X,Y) using the EdDSA scheme. MINLEN is the required length in bytes for the result. If WITH_PREFIX is set the returned buffer is prefixed with a 0x40 byte. On success 0 is returned and a malloced buffer with the encoded point is stored at R_BUFFER; the length of this buffer is stored at R_BUFLEN. */ static gpg_err_code_t eddsa_encode_x_y (gcry_mpi_t x, gcry_mpi_t y, unsigned int minlen, int with_prefix, unsigned char **r_buffer, unsigned int *r_buflen) { unsigned char *rawmpi; unsigned int rawmpilen; int off = with_prefix? 1:0; rawmpi = _gcry_mpi_get_buffer_extra (y, minlen, off?-1:0, &rawmpilen, NULL); if (!rawmpi) return gpg_err_code_from_syserror (); if (mpi_test_bit (x, 0) && rawmpilen) rawmpi[off + rawmpilen - 1] |= 0x80; /* Set sign bit. */ if (off) rawmpi[0] = 0x40; *r_buffer = rawmpi; *r_buflen = rawmpilen + off; return 0; } /* Encode POINT using the EdDSA scheme. X and Y are either scratch variables supplied by the caller or NULL. CTX is the usual context. If WITH_PREFIX is set the returned buffer is prefixed with a 0x40 byte. On success 0 is returned and a malloced buffer with the encoded point is stored at R_BUFFER; the length of this buffer is stored at R_BUFLEN. */ gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec, gcry_mpi_t x_in, gcry_mpi_t y_in, int with_prefix, unsigned char **r_buffer, unsigned int *r_buflen) { gpg_err_code_t rc; gcry_mpi_t x, y; x = x_in? x_in : mpi_new (0); y = y_in? y_in : mpi_new (0); if (_gcry_mpi_ec_get_affine (x, y, point, ec)) { log_error ("eddsa_encodepoint: Failed to get affine coordinates\n"); rc = GPG_ERR_INTERNAL; } else rc = eddsa_encode_x_y (x, y, ec->nbits/8, with_prefix, r_buffer, r_buflen); if (!x_in) mpi_free (x); if (!y_in) mpi_free (y); return rc; } /* Make sure that the opaque MPI VALUE is in compact EdDSA format. This function updates MPI if needed. */ gpg_err_code_t _gcry_ecc_eddsa_ensure_compact (gcry_mpi_t value, unsigned int nbits) { gpg_err_code_t rc; const unsigned char *buf; unsigned int rawmpilen; gcry_mpi_t x, y; unsigned char *enc; unsigned int enclen; if (!mpi_is_opaque (value)) return GPG_ERR_INV_OBJ; buf = mpi_get_opaque (value, &rawmpilen); if (!buf) return GPG_ERR_INV_OBJ; rawmpilen = (rawmpilen + 7)/8; if (rawmpilen > 1 && (rawmpilen%2)) { if (buf[0] == 0x04) { /* Buffer is in SEC1 uncompressed format. Extract y and compress. */ rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD, buf+1, (rawmpilen-1)/2, NULL); if (rc) return rc; rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD, buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2, NULL); if (rc) { mpi_free (x); return rc; } - rc = eddsa_encode_x_y (x, y, nbits/8, 0, &enc, &enclen); + rc = eddsa_encode_x_y (x, y, (nbits+7)/8, 0, &enc, &enclen); mpi_free (x); mpi_free (y); if (rc) return rc; mpi_set_opaque (value, enc, 8*enclen); } else if (buf[0] == 0x40) { /* Buffer is compressed but with our SEC1 alike compression indicator. Remove that byte. FIXME: We should write and use a function to manipulate an opaque MPI in place. */ if (!_gcry_mpi_set_opaque_copy (value, buf + 1, (rawmpilen - 1)*8)) return gpg_err_code_from_syserror (); } } return 0; } /* Recover X from Y and SIGN (which actually is a parity bit). */ gpg_err_code_t _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec) { gpg_err_code_t rc = 0; gcry_mpi_t u, v, v3, t; static gcry_mpi_t p58, seven; if (ec->dialect != ECC_DIALECT_ED25519) return GPG_ERR_NOT_IMPLEMENTED; if (!p58) p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD"); if (!seven) seven = mpi_set_ui (NULL, 7); u = mpi_new (0); v = mpi_new (0); v3 = mpi_new (0); t = mpi_new (0); /* Compute u and v */ /* u = y^2 */ mpi_mulm (u, y, y, ec->p); /* v = b*y^2 */ mpi_mulm (v, ec->b, u, ec->p); /* u = y^2-1 */ mpi_sub_ui (u, u, 1); /* v = b*y^2+1 */ mpi_add_ui (v, v, 1); /* Compute sqrt(u/v) */ /* v3 = v^3 */ mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p); /* t = v3 * v3 * u * v = u * v^7 */ mpi_powm (t, v, seven, ec->p); mpi_mulm (t, t, u, ec->p); /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8) */ mpi_powm (t, t, p58, ec->p); /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */ mpi_mulm (t, t, u, ec->p); mpi_mulm (x, t, v3, ec->p); /* Adjust if needed. */ /* t = v * x^2 */ mpi_mulm (t, x, x, ec->p); mpi_mulm (t, t, v, ec->p); /* -t == u ? x = x * sqrt(-1) */ mpi_sub (t, ec->p, t); if (!mpi_cmp (t, u)) { static gcry_mpi_t m1; /* Fixme: this is not thread-safe. */ if (!m1) m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7" "2F431806AD2FE478C4EE1B274A0EA0B0"); mpi_mulm (x, x, m1, ec->p); /* t = v * x^2 */ mpi_mulm (t, x, x, ec->p); mpi_mulm (t, t, v, ec->p); /* -t == u ? x = x * sqrt(-1) */ mpi_sub (t, ec->p, t); if (!mpi_cmp (t, u)) rc = GPG_ERR_INV_OBJ; } /* Choose the desired square root according to parity */ if (mpi_test_bit (x, 0) != !!sign) mpi_sub (x, ec->p, x); mpi_free (t); mpi_free (v3); mpi_free (v); mpi_free (u); return rc; } /* Decode the EdDSA style encoded PK and set it into RESULT. CTX is the usual curve context. If R_ENCPK is not NULL, the encoded PK is stored at that address; this is a new copy to be released by the caller. In contrast to the supplied PK, this is not an MPI and thus guaranteed to be properly padded. R_ENCPKLEN receives the length of that encoded key. */ gpg_err_code_t _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result, unsigned char **r_encpk, unsigned int *r_encpklen) { gpg_err_code_t rc; unsigned char *rawmpi; unsigned int rawmpilen; int sign; if (mpi_is_opaque (pk)) { const unsigned char *buf; buf = mpi_get_opaque (pk, &rawmpilen); if (!buf) return GPG_ERR_INV_OBJ; rawmpilen = (rawmpilen + 7)/8; /* Handle compression prefixes. The size of the buffer will be odd in this case. */ if (rawmpilen > 1 && (rawmpilen%2)) { /* First check whether the public key has been given in standard uncompressed format (SEC1). No need to recover x in this case. */ if (buf[0] == 0x04) { gcry_mpi_t x, y; rc = _gcry_mpi_scan (&x, GCRYMPI_FMT_STD, buf+1, (rawmpilen-1)/2, NULL); if (rc) return rc; rc = _gcry_mpi_scan (&y, GCRYMPI_FMT_STD, buf+1+(rawmpilen-1)/2, (rawmpilen-1)/2,NULL); if (rc) { mpi_free (x); return rc; } if (r_encpk) { rc = eddsa_encode_x_y (x, y, ctx->nbits/8, 0, r_encpk, r_encpklen); if (rc) { mpi_free (x); mpi_free (y); return rc; } } mpi_snatch (result->x, x); mpi_snatch (result->y, y); mpi_set_ui (result->z, 1); return 0; } /* Check whether the public key has been prefixed with a 0x40 byte to explicitly indicate compressed format using a SEC1 alike prefix byte. This is a Libgcrypt extension. */ if (buf[0] == 0x40) { rawmpilen--; buf++; } } /* EdDSA compressed point. */ rawmpi = xtrymalloc (rawmpilen? rawmpilen:1); if (!rawmpi) return gpg_err_code_from_syserror (); memcpy (rawmpi, buf, rawmpilen); reverse_buffer (rawmpi, rawmpilen); } else { /* Note: Without using an opaque MPI it is not reliable possible to find out whether the public key has been given in uncompressed format. Thus we expect native EdDSA format. */ rawmpi = _gcry_mpi_get_buffer (pk, ctx->nbits/8, &rawmpilen, NULL); if (!rawmpi) return gpg_err_code_from_syserror (); } if (rawmpilen) { sign = !!(rawmpi[0] & 0x80); rawmpi[0] &= 0x7f; } else sign = 0; _gcry_mpi_set_buffer (result->y, rawmpi, rawmpilen, 0); if (r_encpk) { /* Revert to little endian. */ if (sign && rawmpilen) rawmpi[0] |= 0x80; reverse_buffer (rawmpi, rawmpilen); *r_encpk = rawmpi; if (r_encpklen) *r_encpklen = rawmpilen; } else xfree (rawmpi); rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx); mpi_set_ui (result->z, 1); return rc; } /* Compute the A value as used by EdDSA. The caller needs to provide the context EC and the actual secret D as an MPI. The function returns a newly allocated 64 byte buffer at r_digest; the first 32 bytes represent the A value. NULL is returned on error and NULL stored at R_DIGEST. */ gpg_err_code_t _gcry_ecc_eddsa_compute_h_d (unsigned char **r_digest, gcry_mpi_t d, mpi_ec_t ec) { gpg_err_code_t rc; unsigned char *rawmpi = NULL; unsigned int rawmpilen; unsigned char *digest; gcry_buffer_t hvec[2]; int hashalgo, b; *r_digest = NULL; hashalgo = GCRY_MD_SHA512; if (hashalgo != GCRY_MD_SHA512) return GPG_ERR_DIGEST_ALGO; b = (ec->nbits+7)/8; if (b != 256/8) return GPG_ERR_INTERNAL; /* We only support 256 bit. */ /* Note that we clear DIGEST so we can use it as input to left pad the key with zeroes for hashing. */ digest = xtrycalloc_secure (2, b); if (!digest) return gpg_err_code_from_syserror (); memset (hvec, 0, sizeof hvec); rawmpi = _gcry_mpi_get_buffer (d, 0, &rawmpilen, NULL); if (!rawmpi) { xfree (digest); return gpg_err_code_from_syserror (); } hvec[0].data = digest; hvec[0].off = 0; hvec[0].len = b > rawmpilen? b - rawmpilen : 0; hvec[1].data = rawmpi; hvec[1].off = 0; hvec[1].len = rawmpilen; rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2); xfree (rawmpi); if (rc) { xfree (digest); return rc; } /* Compute the A value. */ reverse_buffer (digest, 32); /* Only the first half of the hash. */ digest[0] = (digest[0] & 0x7f) | 0x40; digest[31] &= 0xf8; *r_digest = digest; return 0; } /** * _gcry_ecc_eddsa_genkey - EdDSA version of the key generation. * * @sk: A struct to receive the secret key. * @E: Parameters of the curve. * @ctx: Elliptic curve computation context. * @flags: Flags controlling aspects of the creation. * * Return: An error code. * * The only @flags bit used by this function is %PUBKEY_FLAG_TRANSIENT * to use a faster RNG. */ gpg_err_code_t _gcry_ecc_eddsa_genkey (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx, int flags) { gpg_err_code_t rc; int b = 256/8; /* The only size we currently support. */ gcry_mpi_t a, x, y; mpi_point_struct Q; gcry_random_level_t random_level; char *dbuf; size_t dlen; gcry_buffer_t hvec[1]; unsigned char *hash_d = NULL; point_init (&Q); memset (hvec, 0, sizeof hvec); if ((flags & PUBKEY_FLAG_TRANSIENT_KEY)) random_level = GCRY_STRONG_RANDOM; else random_level = GCRY_VERY_STRONG_RANDOM; a = mpi_snew (0); x = mpi_new (0); y = mpi_new (0); /* Generate a secret. */ hash_d = xtrymalloc_secure (2*b); if (!hash_d) { rc = gpg_err_code_from_syserror (); goto leave; } dlen = b; dbuf = _gcry_random_bytes_secure (dlen, random_level); /* Compute the A value. */ hvec[0].data = dbuf; hvec[0].len = dlen; rc = _gcry_md_hash_buffers (GCRY_MD_SHA512, 0, hash_d, hvec, 1); if (rc) goto leave; sk->d = _gcry_mpi_set_opaque (NULL, dbuf, dlen*8); dbuf = NULL; reverse_buffer (hash_d, 32); /* Only the first half of the hash. */ hash_d[0] = (hash_d[0] & 0x7f) | 0x40; hash_d[31] &= 0xf8; _gcry_mpi_set_buffer (a, hash_d, 32, 0); xfree (hash_d); hash_d = NULL; /* log_printmpi ("ecgen a", a); */ /* Compute Q. */ _gcry_mpi_ec_mul_point (&Q, a, &E->G, ctx); if (DBG_CIPHER) log_printpnt ("ecgen pk", &Q, ctx); /* Copy the stuff to the key structures. */ sk->E.model = E->model; sk->E.dialect = E->dialect; sk->E.p = mpi_copy (E->p); sk->E.a = mpi_copy (E->a); sk->E.b = mpi_copy (E->b); point_init (&sk->E.G); point_set (&sk->E.G, &E->G); sk->E.n = mpi_copy (E->n); sk->E.h = mpi_copy (E->h); point_init (&sk->Q); point_set (&sk->Q, &Q); leave: point_free (&Q); _gcry_mpi_release (a); _gcry_mpi_release (x); _gcry_mpi_release (y); xfree (hash_d); return rc; } /* Compute an EdDSA signature. See: * [ed25519] 23pp. (PDF) Daniel J. Bernstein, Niels Duif, Tanja * Lange, Peter Schwabe, Bo-Yin Yang. High-speed high-security * signatures. Journal of Cryptographic Engineering 2 (2012), 77-89. * Document ID: a1a62a2f76d23f65d622484ddd09caf8. * URL: http://cr.yp.to/papers.html#ed25519. Date: 2011.09.26. * * Despite that this function requires the specification of a hash * algorithm, we only support what has been specified by the paper. * This may change in the future. Note that we don't check the used * curve; the user is responsible to use Ed25519. * * Return the signature struct (r,s) from the message hash. The caller * must have allocated R_R and S. */ gpg_err_code_t _gcry_ecc_eddsa_sign (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r_r, gcry_mpi_t s, int hashalgo, gcry_mpi_t pk) { int rc; mpi_ec_t ctx = NULL; int b; unsigned int tmp; unsigned char *digest = NULL; gcry_buffer_t hvec[3]; const void *mbuf; size_t mlen; unsigned char *rawmpi = NULL; unsigned int rawmpilen; unsigned char *encpk = NULL; /* Encoded public key. */ unsigned int encpklen; mpi_point_struct I; /* Intermediate value. */ mpi_point_struct Q; /* Public key. */ gcry_mpi_t a, x, y, r; memset (hvec, 0, sizeof hvec); if (!mpi_is_opaque (input)) return GPG_ERR_INV_DATA; /* Initialize some helpers. */ point_init (&I); point_init (&Q); a = mpi_snew (0); x = mpi_new (0); y = mpi_new (0); r = mpi_snew (0); ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0, skey->E.p, skey->E.a, skey->E.b); b = (ctx->nbits+7)/8; if (b != 256/8) { rc = GPG_ERR_INTERNAL; /* We only support 256 bit. */ goto leave; } rc = _gcry_ecc_eddsa_compute_h_d (&digest, skey->d, ctx); if (rc) goto leave; _gcry_mpi_set_buffer (a, digest, 32, 0); /* Compute the public key if it has not been supplied as optional parameter. */ if (pk) { rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen); if (rc) goto leave; if (DBG_CIPHER) log_printhex ("* e_pk", encpk, encpklen); if (!_gcry_mpi_ec_curve_point (&Q, ctx)) { rc = GPG_ERR_BROKEN_PUBKEY; goto leave; } } else { _gcry_mpi_ec_mul_point (&Q, a, &skey->E.G, ctx); rc = _gcry_ecc_eddsa_encodepoint (&Q, ctx, x, y, 0, &encpk, &encpklen); if (rc) goto leave; if (DBG_CIPHER) log_printhex (" e_pk", encpk, encpklen); } /* Compute R. */ mbuf = mpi_get_opaque (input, &tmp); mlen = (tmp +7)/8; if (DBG_CIPHER) log_printhex (" m", mbuf, mlen); hvec[0].data = digest; hvec[0].off = 32; hvec[0].len = 32; hvec[1].data = (char*)mbuf; hvec[1].len = mlen; rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 2); if (rc) goto leave; reverse_buffer (digest, 64); if (DBG_CIPHER) log_printhex (" r", digest, 64); _gcry_mpi_set_buffer (r, digest, 64, 0); _gcry_mpi_ec_mul_point (&I, r, &skey->E.G, ctx); if (DBG_CIPHER) log_printpnt (" r", &I, ctx); /* Convert R into affine coordinates and apply encoding. */ rc = _gcry_ecc_eddsa_encodepoint (&I, ctx, x, y, 0, &rawmpi, &rawmpilen); if (rc) goto leave; if (DBG_CIPHER) log_printhex (" e_r", rawmpi, rawmpilen); /* S = r + a * H(encodepoint(R) + encodepoint(pk) + m) mod n */ hvec[0].data = rawmpi; /* (this is R) */ hvec[0].off = 0; hvec[0].len = rawmpilen; hvec[1].data = encpk; hvec[1].off = 0; hvec[1].len = encpklen; hvec[2].data = (char*)mbuf; hvec[2].off = 0; hvec[2].len = mlen; rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3); if (rc) goto leave; /* No more need for RAWMPI thus we now transfer it to R_R. */ mpi_set_opaque (r_r, rawmpi, rawmpilen*8); rawmpi = NULL; reverse_buffer (digest, 64); if (DBG_CIPHER) log_printhex (" H(R+)", digest, 64); _gcry_mpi_set_buffer (s, digest, 64, 0); mpi_mulm (s, s, a, skey->E.n); mpi_addm (s, s, r, skey->E.n); rc = eddsa_encodempi (s, b, &rawmpi, &rawmpilen); if (rc) goto leave; if (DBG_CIPHER) log_printhex (" e_s", rawmpi, rawmpilen); mpi_set_opaque (s, rawmpi, rawmpilen*8); rawmpi = NULL; rc = 0; leave: _gcry_mpi_release (a); _gcry_mpi_release (x); _gcry_mpi_release (y); _gcry_mpi_release (r); xfree (digest); _gcry_mpi_ec_free (ctx); point_free (&I); point_free (&Q); xfree (encpk); xfree (rawmpi); return rc; } /* Verify an EdDSA signature. See sign_eddsa for the reference. * Check if R_IN and S_IN verifies INPUT. PKEY has the curve * parameters and PK is the EdDSA style encoded public key. */ gpg_err_code_t _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey, gcry_mpi_t r_in, gcry_mpi_t s_in, int hashalgo, gcry_mpi_t pk) { int rc; mpi_ec_t ctx = NULL; int b; unsigned int tmp; mpi_point_struct Q; /* Public key. */ unsigned char *encpk = NULL; /* Encoded public key. */ unsigned int encpklen; const void *mbuf, *rbuf; unsigned char *tbuf = NULL; size_t mlen, rlen; unsigned int tlen; unsigned char digest[64]; gcry_buffer_t hvec[3]; gcry_mpi_t h, s; mpi_point_struct Ia, Ib; if (!mpi_is_opaque (input) || !mpi_is_opaque (r_in) || !mpi_is_opaque (s_in)) return GPG_ERR_INV_DATA; if (hashalgo != GCRY_MD_SHA512) return GPG_ERR_DIGEST_ALGO; point_init (&Q); point_init (&Ia); point_init (&Ib); h = mpi_new (0); s = mpi_new (0); ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0, pkey->E.p, pkey->E.a, pkey->E.b); b = ctx->nbits/8; if (b != 256/8) { rc = GPG_ERR_INTERNAL; /* We only support 256 bit. */ goto leave; } /* Decode and check the public key. */ rc = _gcry_ecc_eddsa_decodepoint (pk, ctx, &Q, &encpk, &encpklen); if (rc) goto leave; if (!_gcry_mpi_ec_curve_point (&Q, ctx)) { rc = GPG_ERR_BROKEN_PUBKEY; goto leave; } if (DBG_CIPHER) log_printhex (" e_pk", encpk, encpklen); if (encpklen != b) { rc = GPG_ERR_INV_LENGTH; goto leave; } /* Convert the other input parameters. */ mbuf = mpi_get_opaque (input, &tmp); mlen = (tmp +7)/8; if (DBG_CIPHER) log_printhex (" m", mbuf, mlen); rbuf = mpi_get_opaque (r_in, &tmp); rlen = (tmp +7)/8; if (DBG_CIPHER) log_printhex (" r", rbuf, rlen); if (rlen != b) { rc = GPG_ERR_INV_LENGTH; goto leave; } /* h = H(encodepoint(R) + encodepoint(pk) + m) */ hvec[0].data = (char*)rbuf; hvec[0].off = 0; hvec[0].len = rlen; hvec[1].data = encpk; hvec[1].off = 0; hvec[1].len = encpklen; hvec[2].data = (char*)mbuf; hvec[2].off = 0; hvec[2].len = mlen; rc = _gcry_md_hash_buffers (hashalgo, 0, digest, hvec, 3); if (rc) goto leave; reverse_buffer (digest, 64); if (DBG_CIPHER) log_printhex (" H(R+)", digest, 64); _gcry_mpi_set_buffer (h, digest, 64, 0); /* According to the paper the best way for verification is: encodepoint(sG - h·Q) = encodepoint(r) because we don't need to decode R. */ { void *sbuf; unsigned int slen; sbuf = _gcry_mpi_get_opaque_copy (s_in, &tmp); slen = (tmp +7)/8; reverse_buffer (sbuf, slen); if (DBG_CIPHER) log_printhex (" s", sbuf, slen); _gcry_mpi_set_buffer (s, sbuf, slen, 0); xfree (sbuf); if (slen != b) { rc = GPG_ERR_INV_LENGTH; goto leave; } } _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx); _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx); _gcry_mpi_sub (Ib.x, ctx->p, Ib.x); _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx); rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen); if (rc) goto leave; if (tlen != rlen || memcmp (tbuf, rbuf, tlen)) { rc = GPG_ERR_BAD_SIGNATURE; goto leave; } rc = 0; leave: xfree (encpk); xfree (tbuf); _gcry_mpi_ec_free (ctx); _gcry_mpi_release (s); _gcry_mpi_release (h); point_free (&Ia); point_free (&Ib); point_free (&Q); return rc; } diff --git a/cipher/ecc.c b/cipher/ecc.c index 4679eca2..59837bc5 100644 --- a/cipher/ecc.c +++ b/cipher/ecc.c @@ -1,2279 +1,2281 @@ /* ecc.c - Elliptic Curve Cryptography * Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc. * Copyright (C) 2013, 2015 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ /* This code is originally based on the Patch 0.1.6 for the gnupg 1.4.x branch as retrieved on 2007-03-21 from http://www.calcurco.cat/eccGnuPG/src/gnupg-1.4.6-ecc0.2.0beta1.diff.bz2 The original authors are: Written by Sergi Blanch i Torne , Ramiro Moreno Chiral Maintainers Sergi Blanch i Torne Ramiro Moreno Chiral Mikael Mylnikov (mmr) For use in Libgcrypt the code has been heavily modified and cleaned up. In fact there is not much left of the originally code except for some variable names and the text book implementaion of the sign and verification algorithms. The arithmetic functions have entirely been rewritten and moved to mpi/ec.c. ECDH encrypt and decrypt code written by Andrey Jivsov. */ /* TODO: - In mpi/ec.c we use mpi_powm for x^2 mod p: Either implement a special case in mpi_powm or check whether mpi_mulm is faster. */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "context.h" #include "ec-context.h" #include "pubkey-internal.h" #include "ecc-common.h" static const char *ecc_names[] = { "ecc", "ecdsa", "ecdh", "eddsa", "gost", NULL, }; /* Sample NIST P-256 key from RFC 6979 A.2.5 */ static const char sample_public_key_secp256[] = "(public-key" " (ecc" " (curve secp256r1)" " (q #04" /**/ "60FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB6" /**/ "7903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299#)))"; static const char sample_secret_key_secp256[] = "(private-key" " (ecc" " (curve secp256r1)" " (d #C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721#)" " (q #04" /**/ "60FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB6" /**/ "7903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299#)))"; /* Registered progress function and its callback value. */ static void (*progress_cb) (void *, const char*, int, int, int); static void *progress_cb_data; /* Local prototypes. */ static void test_keys (ECC_secret_key * sk, unsigned int nbits); static void test_ecdh_only_keys (ECC_secret_key * sk, unsigned int nbits, int flags); static unsigned int ecc_get_nbits (gcry_sexp_t parms); void _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *, int, int, int), void *cb_data) { progress_cb = cb; progress_cb_data = cb_data; } /* static void */ /* progress (int c) */ /* { */ /* if (progress_cb) */ /* progress_cb (progress_cb_data, "pk_ecc", c, 0, 0); */ /* } */ /** * nist_generate_key - Standard version of the ECC key generation. * @sk: A struct to receive the secret key. * @E: Parameters of the curve. * @ctx: Elliptic curve computation context. * @flags: Flags controlling aspects of the creation. * @nbits: Only for testing * @r_x: On success this receives an allocated MPI with the affine * x-coordinate of the poblic key. On error NULL is stored. * @r_y: Ditto for the y-coordinate. * * Return: An error code. * * The @flags bits used by this function are %PUBKEY_FLAG_TRANSIENT to * use a faster RNG, and %PUBKEY_FLAG_NO_KEYTEST to skip the assertion * that the key works as expected. * * FIXME: Check whether N is needed. */ static gpg_err_code_t nist_generate_key (ECC_secret_key *sk, elliptic_curve_t *E, mpi_ec_t ctx, int flags, unsigned int nbits, gcry_mpi_t *r_x, gcry_mpi_t *r_y) { mpi_point_struct Q; gcry_random_level_t random_level; gcry_mpi_t x, y; const unsigned int pbits = mpi_get_nbits (E->p); point_init (&Q); if ((flags & PUBKEY_FLAG_TRANSIENT_KEY)) random_level = GCRY_STRONG_RANDOM; else random_level = GCRY_VERY_STRONG_RANDOM; /* Generate a secret. */ if (ctx->dialect == ECC_DIALECT_ED25519 || (flags & PUBKEY_FLAG_DJB_TWEAK)) { char *rndbuf; int len = (pbits+7)/8; unsigned int h; mpi_get_ui (&h, E->h); sk->d = mpi_snew (pbits); rndbuf = _gcry_random_bytes_secure (len, random_level); if ((pbits % 8)) rndbuf[0] &= (1 << (pbits % 8)) - 1; rndbuf[0] |= (1 << ((pbits + 7) % 8)); rndbuf[(pbits-1)/8] &= (256 - h); _gcry_mpi_set_buffer (sk->d, rndbuf, len, 0); xfree (rndbuf); } else sk->d = _gcry_dsa_gen_k (E->n, random_level); /* Compute Q. */ _gcry_mpi_ec_mul_point (&Q, sk->d, &E->G, ctx); /* Copy the stuff to the key structures. */ sk->E.model = E->model; sk->E.dialect = E->dialect; sk->E.p = mpi_copy (E->p); sk->E.a = mpi_copy (E->a); sk->E.b = mpi_copy (E->b); point_init (&sk->E.G); point_set (&sk->E.G, &E->G); sk->E.n = mpi_copy (E->n); sk->E.h = mpi_copy (E->h); point_init (&sk->Q); x = mpi_new (pbits); if (r_y == NULL) y = NULL; else y = mpi_new (pbits); if (_gcry_mpi_ec_get_affine (x, y, &Q, ctx)) log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q"); /* We want the Q=(x,y) be a "compliant key" in terms of the * http://tools.ietf.org/html/draft-jivsov-ecc-compact, which simply * means that we choose either Q=(x,y) or -Q=(x,p-y) such that we * end up with the min(y,p-y) as the y coordinate. Such a public * key allows the most efficient compression: y can simply be * dropped because we know that it's a minimum of the two * possibilities without any loss of security. Note that we don't * do that for Ed25519 so that we do not violate the special * construction of the secret key. */ if (r_y == NULL || E->dialect == ECC_DIALECT_ED25519) point_set (&sk->Q, &Q); else { gcry_mpi_t negative; negative = mpi_new (pbits); if (E->model == MPI_EC_WEIERSTRASS) mpi_sub (negative, E->p, y); /* negative = p - y */ else mpi_sub (negative, E->p, x); /* negative = p - x */ if (mpi_cmp (negative, y) < 0) /* p - y < p */ { /* We need to end up with -Q; this assures that new Q's y is the smallest one */ if (E->model == MPI_EC_WEIERSTRASS) { mpi_free (y); y = negative; } else { mpi_free (x); x = negative; } mpi_sub (sk->d, E->n, sk->d); /* d = order - d */ mpi_point_set (&sk->Q, x, y, mpi_const (MPI_C_ONE)); if (DBG_CIPHER) log_debug ("ecgen converted Q to a compliant point\n"); } else /* p - y >= p */ { /* No change is needed exactly 50% of the time: just copy. */ mpi_free (negative); point_set (&sk->Q, &Q); if (DBG_CIPHER) log_debug ("ecgen didn't need to convert Q to a compliant point\n"); } } *r_x = x; if (r_y) *r_y = y; point_free (&Q); /* Now we can test our keys (this should never fail!). */ if ((flags & PUBKEY_FLAG_NO_KEYTEST)) ; /* User requested to skip the test. */ else if (sk->E.model != MPI_EC_MONTGOMERY) test_keys (sk, nbits - 64); else test_ecdh_only_keys (sk, nbits - 64, flags); return 0; } /* * To verify correct skey it use a random information. * First, encrypt and decrypt this dummy value, * test if the information is recuperated. * Second, test with the sign and verify functions. */ static void test_keys (ECC_secret_key *sk, unsigned int nbits) { ECC_public_key pk; gcry_mpi_t test = mpi_new (nbits); mpi_point_struct R_; gcry_mpi_t c = mpi_new (nbits); gcry_mpi_t out = mpi_new (nbits); gcry_mpi_t r = mpi_new (nbits); gcry_mpi_t s = mpi_new (nbits); if (DBG_CIPHER) log_debug ("Testing key.\n"); point_init (&R_); pk.E = _gcry_ecc_curve_copy (sk->E); point_init (&pk.Q); point_set (&pk.Q, &sk->Q); _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM); if (_gcry_ecc_ecdsa_sign (test, sk, r, s, 0, 0) ) log_fatal ("ECDSA operation: sign failed\n"); if (_gcry_ecc_ecdsa_verify (test, &pk, r, s)) { log_fatal ("ECDSA operation: sign, verify failed\n"); } if (DBG_CIPHER) log_debug ("ECDSA operation: sign, verify ok.\n"); point_free (&pk.Q); _gcry_ecc_curve_free (&pk.E); point_free (&R_); mpi_free (s); mpi_free (r); mpi_free (out); mpi_free (c); mpi_free (test); } static void test_ecdh_only_keys (ECC_secret_key *sk, unsigned int nbits, int flags) { ECC_public_key pk; gcry_mpi_t test; mpi_point_struct R_; gcry_mpi_t x0, x1; mpi_ec_t ec; if (DBG_CIPHER) log_debug ("Testing ECDH only key.\n"); point_init (&R_); pk.E = _gcry_ecc_curve_copy (sk->E); point_init (&pk.Q); point_set (&pk.Q, &sk->Q); if ((flags & PUBKEY_FLAG_DJB_TWEAK)) { char *rndbuf; const unsigned int pbits = mpi_get_nbits (sk->E.p); int len = (pbits+7)/8; unsigned int h; mpi_get_ui (&h, sk->E.h); test = mpi_new (pbits); rndbuf = _gcry_random_bytes (len, GCRY_WEAK_RANDOM); if ((pbits % 8)) rndbuf[0] &= (1 << (pbits % 8)) - 1; rndbuf[0] |= (1 << ((pbits + 7) % 8)); rndbuf[(pbits-1)/8] &= (256 - h); _gcry_mpi_set_buffer (test, rndbuf, len, 0); xfree (rndbuf); } else { test = mpi_new (nbits); _gcry_mpi_randomize (test, nbits, GCRY_WEAK_RANDOM); } ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, flags, pk.E.p, pk.E.a, pk.E.b); x0 = mpi_new (0); x1 = mpi_new (0); /* R_ = hkQ <=> R_ = hkdG */ _gcry_mpi_ec_mul_point (&R_, test, &pk.Q, ec); if (!(flags & PUBKEY_FLAG_DJB_TWEAK)) _gcry_mpi_ec_mul_point (&R_, ec->h, &R_, ec); if (_gcry_mpi_ec_get_affine (x0, NULL, &R_, ec)) log_fatal ("ecdh: Failed to get affine coordinates for hkQ\n"); _gcry_mpi_ec_mul_point (&R_, test, &pk.E.G, ec); _gcry_mpi_ec_mul_point (&R_, sk->d, &R_, ec); /* R_ = hdkG */ if (!(flags & PUBKEY_FLAG_DJB_TWEAK)) _gcry_mpi_ec_mul_point (&R_, ec->h, &R_, ec); if (_gcry_mpi_ec_get_affine (x1, NULL, &R_, ec)) log_fatal ("ecdh: Failed to get affine coordinates for hdkG\n"); if (mpi_cmp (x0, x1)) { log_fatal ("ECDH test failed.\n"); } mpi_free (x0); mpi_free (x1); _gcry_mpi_ec_free (ec); point_free (&pk.Q); _gcry_ecc_curve_free (&pk.E); point_free (&R_); mpi_free (test); } /* * To check the validity of the value, recalculate the correspondence * between the public value and the secret one. */ static int check_secret_key (ECC_secret_key *sk, mpi_ec_t ec, int flags) { int rc = 1; mpi_point_struct Q; gcry_mpi_t x1, y1; gcry_mpi_t x2 = NULL; gcry_mpi_t y2 = NULL; point_init (&Q); x1 = mpi_new (0); if (ec->model == MPI_EC_MONTGOMERY) y1 = NULL; else y1 = mpi_new (0); /* G in E(F_p) */ if (!_gcry_mpi_ec_curve_point (&sk->E.G, ec)) { if (DBG_CIPHER) log_debug ("Bad check: Point 'G' does not belong to curve 'E'!\n"); goto leave; } /* G != PaI */ if (!mpi_cmp_ui (sk->E.G.z, 0)) { if (DBG_CIPHER) log_debug ("Bad check: 'G' cannot be Point at Infinity!\n"); goto leave; } /* Check order of curve. */ if (sk->E.dialect == ECC_DIALECT_STANDARD && !(flags & PUBKEY_FLAG_DJB_TWEAK)) { _gcry_mpi_ec_mul_point (&Q, sk->E.n, &sk->E.G, ec); if (mpi_cmp_ui (Q.z, 0)) { if (DBG_CIPHER) log_debug ("check_secret_key: E is not a curve of order n\n"); goto leave; } } /* Pubkey cannot be PaI */ if (!mpi_cmp_ui (sk->Q.z, 0)) { if (DBG_CIPHER) log_debug ("Bad check: Q can not be a Point at Infinity!\n"); goto leave; } /* pubkey = [d]G over E */ if (!_gcry_ecc_compute_public (&Q, ec, &sk->E.G, sk->d)) { if (DBG_CIPHER) log_debug ("Bad check: computation of dG failed\n"); goto leave; } if (_gcry_mpi_ec_get_affine (x1, y1, &Q, ec)) { if (DBG_CIPHER) log_debug ("Bad check: Q can not be a Point at Infinity!\n"); goto leave; } if ((flags & PUBKEY_FLAG_EDDSA)) ; /* Fixme: EdDSA is special. */ else if (!mpi_cmp_ui (sk->Q.z, 1)) { /* Fast path if Q is already in affine coordinates. */ if (mpi_cmp (x1, sk->Q.x) || (y1 && mpi_cmp (y1, sk->Q.y))) { if (DBG_CIPHER) log_debug ("Bad check: There is NO correspondence between 'd' and 'Q'!\n"); goto leave; } } else { x2 = mpi_new (0); y2 = mpi_new (0); if (_gcry_mpi_ec_get_affine (x2, y2, &sk->Q, ec)) { if (DBG_CIPHER) log_debug ("Bad check: Q can not be a Point at Infinity!\n"); goto leave; } if (mpi_cmp (x1, x2) || mpi_cmp (y1, y2)) { if (DBG_CIPHER) log_debug ("Bad check: There is NO correspondence between 'd' and 'Q'!\n"); goto leave; } } rc = 0; /* Okay. */ leave: mpi_free (x2); mpi_free (x1); mpi_free (y1); mpi_free (y2); point_free (&Q); return rc; } /********************************************* ************** interface ****************** *********************************************/ static gcry_err_code_t ecc_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) { gpg_err_code_t rc; unsigned int nbits; elliptic_curve_t E; ECC_secret_key sk; gcry_mpi_t Gx = NULL; gcry_mpi_t Gy = NULL; gcry_mpi_t Qx = NULL; gcry_mpi_t Qy = NULL; char *curve_name = NULL; gcry_sexp_t l1; mpi_ec_t ctx = NULL; gcry_sexp_t curve_info = NULL; gcry_sexp_t curve_flags = NULL; gcry_mpi_t base = NULL; gcry_mpi_t public = NULL; gcry_mpi_t secret = NULL; int flags = 0; memset (&E, 0, sizeof E); memset (&sk, 0, sizeof sk); rc = _gcry_pk_util_get_nbits (genparms, &nbits); if (rc) return rc; /* Parse the optional "curve" parameter. */ l1 = sexp_find_token (genparms, "curve", 0); if (l1) { curve_name = _gcry_sexp_nth_string (l1, 1); sexp_release (l1); if (!curve_name) return GPG_ERR_INV_OBJ; /* No curve name or value too large. */ } /* Parse the optional flags list. */ l1 = sexp_find_token (genparms, "flags", 0); if (l1) { rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); sexp_release (l1); if (rc) goto leave; } /* Parse the deprecated optional transient-key flag. */ l1 = sexp_find_token (genparms, "transient-key", 0); if (l1) { flags |= PUBKEY_FLAG_TRANSIENT_KEY; sexp_release (l1); } /* NBITS is required if no curve name has been given. */ if (!nbits && !curve_name) return GPG_ERR_NO_OBJ; /* No NBITS parameter. */ rc = _gcry_ecc_fill_in_curve (nbits, curve_name, &E, &nbits); if (rc) goto leave; if (DBG_CIPHER) { log_debug ("ecgen curve info: %s/%s\n", _gcry_ecc_model2str (E.model), _gcry_ecc_dialect2str (E.dialect)); if (E.name) log_debug ("ecgen curve used: %s\n", E.name); log_printmpi ("ecgen curve p", E.p); log_printmpi ("ecgen curve a", E.a); log_printmpi ("ecgen curve b", E.b); log_printmpi ("ecgen curve n", E.n); log_printmpi ("ecgen curve h", E.h); log_printpnt ("ecgen curve G", &E.G, NULL); } ctx = _gcry_mpi_ec_p_internal_new (E.model, E.dialect, flags, E.p, E.a, E.b); if (E.model == MPI_EC_MONTGOMERY) rc = nist_generate_key (&sk, &E, ctx, flags, nbits, &Qx, NULL); else if ((flags & PUBKEY_FLAG_EDDSA)) rc = _gcry_ecc_eddsa_genkey (&sk, &E, ctx, flags); else rc = nist_generate_key (&sk, &E, ctx, flags, nbits, &Qx, &Qy); if (rc) goto leave; /* Copy data to the result. */ Gx = mpi_new (0); Gy = mpi_new (0); if (E.model != MPI_EC_MONTGOMERY) { if (_gcry_mpi_ec_get_affine (Gx, Gy, &sk.E.G, ctx)) log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "G"); base = _gcry_ecc_ec2os (Gx, Gy, sk.E.p); } if ((sk.E.dialect == ECC_DIALECT_ED25519 || E.model == MPI_EC_MONTGOMERY) && !(flags & PUBKEY_FLAG_NOCOMP)) { unsigned char *encpk; unsigned int encpklen; if (E.model != MPI_EC_MONTGOMERY) /* (Gx and Gy are used as scratch variables) */ rc = _gcry_ecc_eddsa_encodepoint (&sk.Q, ctx, Gx, Gy, !!(flags & PUBKEY_FLAG_COMP), &encpk, &encpklen); else { encpk = _gcry_mpi_get_buffer_extra (Qx, nbits/8, -1, &encpklen, NULL); if (encpk == NULL) rc = gpg_err_code_from_syserror (); else { encpk[0] = 0x40; encpklen++; } } if (rc) goto leave; public = mpi_new (0); mpi_set_opaque (public, encpk, encpklen*8); } else { if (!Qx) { /* This is the case for a key from _gcry_ecc_eddsa_generate with no compression. */ Qx = mpi_new (0); Qy = mpi_new (0); if (_gcry_mpi_ec_get_affine (Qx, Qy, &sk.Q, ctx)) log_fatal ("ecgen: Failed to get affine coordinates for %s\n", "Q"); } public = _gcry_ecc_ec2os (Qx, Qy, sk.E.p); } secret = sk.d; sk.d = NULL; if (E.name) { rc = sexp_build (&curve_info, NULL, "(curve %s)", E.name); if (rc) goto leave; } if ((flags & PUBKEY_FLAG_PARAM) || (flags & PUBKEY_FLAG_EDDSA) || (flags & PUBKEY_FLAG_DJB_TWEAK)) { rc = sexp_build (&curve_flags, NULL, ((flags & PUBKEY_FLAG_PARAM) && (flags & PUBKEY_FLAG_EDDSA))? "(flags param eddsa)" : ((flags & PUBKEY_FLAG_PARAM) && (flags & PUBKEY_FLAG_EDDSA))? "(flags param djb-tweak)" : ((flags & PUBKEY_FLAG_PARAM))? "(flags param)" : ((flags & PUBKEY_FLAG_EDDSA))? "(flags eddsa)" : "(flags djb-tweak)" ); if (rc) goto leave; } if ((flags & PUBKEY_FLAG_PARAM) && E.name) rc = sexp_build (r_skey, NULL, "(key-data" " (public-key" " (ecc%S%S(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)))" " (private-key" " (ecc%S%S(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)(d%m)))" " )", curve_info, curve_flags, sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, sk.E.h, public, curve_info, curve_flags, sk.E.p, sk.E.a, sk.E.b, base, sk.E.n, sk.E.h, public, secret); else rc = sexp_build (r_skey, NULL, "(key-data" " (public-key" " (ecc%S%S(q%m)))" " (private-key" " (ecc%S%S(q%m)(d%m)))" " )", curve_info, curve_flags, public, curve_info, curve_flags, public, secret); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("ecgen result p", sk.E.p); log_printmpi ("ecgen result a", sk.E.a); log_printmpi ("ecgen result b", sk.E.b); log_printmpi ("ecgen result G", base); log_printmpi ("ecgen result n", sk.E.n); log_printmpi ("ecgen result h", sk.E.h); log_printmpi ("ecgen result Q", public); log_printmpi ("ecgen result d", secret); if ((flags & PUBKEY_FLAG_EDDSA)) log_debug ("ecgen result using Ed25519+EdDSA\n"); } leave: mpi_free (secret); mpi_free (public); mpi_free (base); { _gcry_ecc_curve_free (&sk.E); point_free (&sk.Q); mpi_free (sk.d); } _gcry_ecc_curve_free (&E); mpi_free (Gx); mpi_free (Gy); mpi_free (Qx); mpi_free (Qy); _gcry_mpi_ec_free (ctx); xfree (curve_name); sexp_release (curve_flags); sexp_release (curve_info); return rc; } static gcry_err_code_t ecc_check_secret_key (gcry_sexp_t keyparms) { gcry_err_code_t rc; gcry_sexp_t l1 = NULL; int flags = 0; char *curvename = NULL; gcry_mpi_t mpi_g = NULL; gcry_mpi_t mpi_q = NULL; ECC_secret_key sk; mpi_ec_t ec = NULL; memset (&sk, 0, sizeof sk); /* Look for flags. */ l1 = sexp_find_token (keyparms, "flags", 0); if (l1) { rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); if (rc) goto leave; } /* Extract the parameters. */ if ((flags & PUBKEY_FLAG_PARAM)) rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?/q?+d", &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n, &sk.E.h, &mpi_q, &sk.d, NULL); else rc = sexp_extract_param (keyparms, NULL, "/q?+d", &mpi_q, &sk.d, NULL); if (rc) goto leave; /* Add missing parameters using the optional curve parameter. */ sexp_release (l1); l1 = sexp_find_token (keyparms, "curve", 5); if (l1) { curvename = sexp_nth_string (l1, 1); if (curvename) { rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL); if (rc) goto leave; } } if (mpi_g) { if (!sk.E.G.x) point_init (&sk.E.G); rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g); if (rc) goto leave; } /* Guess required fields if a curve parameter has not been given. FIXME: This is a crude hacks. We need to fix that. */ if (!curvename) { sk.E.model = ((flags & PUBKEY_FLAG_EDDSA) ? MPI_EC_EDWARDS : MPI_EC_WEIERSTRASS); sk.E.dialect = ((flags & PUBKEY_FLAG_EDDSA) ? ECC_DIALECT_ED25519 : ECC_DIALECT_STANDARD); if (!sk.E.h) sk.E.h = mpi_const (MPI_C_ONE); } if (DBG_CIPHER) { log_debug ("ecc_testkey info: %s/%s\n", _gcry_ecc_model2str (sk.E.model), _gcry_ecc_dialect2str (sk.E.dialect)); if (sk.E.name) log_debug ("ecc_testkey name: %s\n", sk.E.name); log_printmpi ("ecc_testkey p", sk.E.p); log_printmpi ("ecc_testkey a", sk.E.a); log_printmpi ("ecc_testkey b", sk.E.b); log_printpnt ("ecc_testkey g", &sk.E.G, NULL); log_printmpi ("ecc_testkey n", sk.E.n); log_printmpi ("ecc_testkey h", sk.E.h); log_printmpi ("ecc_testkey q", mpi_q); if (!fips_mode ()) log_printmpi ("ecc_testkey d", sk.d); } if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.E.h || !sk.d) { rc = GPG_ERR_NO_OBJ; goto leave; } ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect, flags, sk.E.p, sk.E.a, sk.E.b); if (mpi_q) { point_init (&sk.Q); rc = _gcry_mpi_ec_decode_point (&sk.Q, mpi_q, ec); if (rc) goto leave; } else { /* The secret key test requires Q. */ rc = GPG_ERR_NO_OBJ; goto leave; } if (check_secret_key (&sk, ec, flags)) rc = GPG_ERR_BAD_SECKEY; leave: _gcry_mpi_ec_free (ec); _gcry_mpi_release (sk.E.p); _gcry_mpi_release (sk.E.a); _gcry_mpi_release (sk.E.b); _gcry_mpi_release (mpi_g); point_free (&sk.E.G); _gcry_mpi_release (sk.E.n); _gcry_mpi_release (sk.E.h); _gcry_mpi_release (mpi_q); point_free (&sk.Q); _gcry_mpi_release (sk.d); xfree (curvename); sexp_release (l1); if (DBG_CIPHER) log_debug ("ecc_testkey => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_mpi_t data = NULL; gcry_sexp_t l1 = NULL; char *curvename = NULL; gcry_mpi_t mpi_g = NULL; gcry_mpi_t mpi_q = NULL; ECC_secret_key sk; gcry_mpi_t sig_r = NULL; gcry_mpi_t sig_s = NULL; memset (&sk, 0, sizeof sk); _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, 0); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_mpidump ("ecc_sign data", data); /* * Extract the key. */ if ((ctx.flags & PUBKEY_FLAG_PARAM)) rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?/q?+d", &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n, &sk.E.h, &mpi_q, &sk.d, NULL); else rc = sexp_extract_param (keyparms, NULL, "/q?+d", &mpi_q, &sk.d, NULL); if (rc) goto leave; if (mpi_g) { point_init (&sk.E.G); rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g); if (rc) goto leave; } /* Add missing parameters using the optional curve parameter. */ l1 = sexp_find_token (keyparms, "curve", 5); if (l1) { curvename = sexp_nth_string (l1, 1); if (curvename) { rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL); if (rc) goto leave; } } /* Guess required fields if a curve parameter has not been given. FIXME: This is a crude hacks. We need to fix that. */ if (!curvename) { sk.E.model = ((ctx.flags & PUBKEY_FLAG_EDDSA) ? MPI_EC_EDWARDS : MPI_EC_WEIERSTRASS); sk.E.dialect = ((ctx.flags & PUBKEY_FLAG_EDDSA) ? ECC_DIALECT_ED25519 : ECC_DIALECT_STANDARD); if (!sk.E.h) sk.E.h = mpi_const (MPI_C_ONE); } if (DBG_CIPHER) { log_debug ("ecc_sign info: %s/%s%s\n", _gcry_ecc_model2str (sk.E.model), _gcry_ecc_dialect2str (sk.E.dialect), (ctx.flags & PUBKEY_FLAG_EDDSA)? "+EdDSA":""); if (sk.E.name) log_debug ("ecc_sign name: %s\n", sk.E.name); log_printmpi ("ecc_sign p", sk.E.p); log_printmpi ("ecc_sign a", sk.E.a); log_printmpi ("ecc_sign b", sk.E.b); log_printpnt ("ecc_sign g", &sk.E.G, NULL); log_printmpi ("ecc_sign n", sk.E.n); log_printmpi ("ecc_sign h", sk.E.h); log_printmpi ("ecc_sign q", mpi_q); if (!fips_mode ()) log_printmpi ("ecc_sign d", sk.d); } if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.E.h || !sk.d) { rc = GPG_ERR_NO_OBJ; goto leave; } sig_r = mpi_new (0); sig_s = mpi_new (0); if ((ctx.flags & PUBKEY_FLAG_EDDSA)) { /* EdDSA requires the public key. */ rc = _gcry_ecc_eddsa_sign (data, &sk, sig_r, sig_s, ctx.hash_algo, mpi_q); if (!rc) rc = sexp_build (r_sig, NULL, "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s); } else if ((ctx.flags & PUBKEY_FLAG_GOST)) { rc = _gcry_ecc_gost_sign (data, &sk, sig_r, sig_s); if (!rc) rc = sexp_build (r_sig, NULL, "(sig-val(gost(r%M)(s%M)))", sig_r, sig_s); } else { rc = _gcry_ecc_ecdsa_sign (data, &sk, sig_r, sig_s, ctx.flags, ctx.hash_algo); if (!rc) rc = sexp_build (r_sig, NULL, "(sig-val(ecdsa(r%M)(s%M)))", sig_r, sig_s); } leave: _gcry_mpi_release (sk.E.p); _gcry_mpi_release (sk.E.a); _gcry_mpi_release (sk.E.b); _gcry_mpi_release (mpi_g); point_free (&sk.E.G); _gcry_mpi_release (sk.E.n); _gcry_mpi_release (sk.E.h); _gcry_mpi_release (mpi_q); point_free (&sk.Q); _gcry_mpi_release (sk.d); _gcry_mpi_release (sig_r); _gcry_mpi_release (sig_s); xfree (curvename); _gcry_mpi_release (data); sexp_release (l1); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("ecc_sign => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms) { gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; char *curvename = NULL; gcry_mpi_t mpi_g = NULL; gcry_mpi_t mpi_q = NULL; gcry_mpi_t sig_r = NULL; gcry_mpi_t sig_s = NULL; gcry_mpi_t data = NULL; ECC_public_key pk; int sigflags; memset (&pk, 0, sizeof pk); _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY, ecc_get_nbits (s_keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_mpidump ("ecc_verify data", data); /* * Extract the signature value. */ rc = _gcry_pk_util_preparse_sigval (s_sig, ecc_names, &l1, &sigflags); if (rc) goto leave; rc = sexp_extract_param (l1, NULL, (sigflags & PUBKEY_FLAG_EDDSA)? "/rs":"rs", &sig_r, &sig_s, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_mpidump ("ecc_verify s_r", sig_r); log_mpidump ("ecc_verify s_s", sig_s); } if ((ctx.flags & PUBKEY_FLAG_EDDSA) ^ (sigflags & PUBKEY_FLAG_EDDSA)) { rc = GPG_ERR_CONFLICT; /* Inconsistent use of flag/algoname. */ goto leave; } /* * Extract the key. */ if ((ctx.flags & PUBKEY_FLAG_PARAM)) rc = sexp_extract_param (s_keyparms, NULL, "-p?a?b?g?n?h?/q", &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n, &pk.E.h, &mpi_q, NULL); else rc = sexp_extract_param (s_keyparms, NULL, "/q", &mpi_q, NULL); if (rc) goto leave; if (mpi_g) { point_init (&pk.E.G); rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g); if (rc) goto leave; } /* Add missing parameters using the optional curve parameter. */ sexp_release (l1); l1 = sexp_find_token (s_keyparms, "curve", 5); if (l1) { curvename = sexp_nth_string (l1, 1); if (curvename) { rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL); if (rc) goto leave; } } /* Guess required fields if a curve parameter has not been given. FIXME: This is a crude hacks. We need to fix that. */ if (!curvename) { pk.E.model = ((sigflags & PUBKEY_FLAG_EDDSA) ? MPI_EC_EDWARDS : MPI_EC_WEIERSTRASS); pk.E.dialect = ((sigflags & PUBKEY_FLAG_EDDSA) ? ECC_DIALECT_ED25519 : ECC_DIALECT_STANDARD); if (!pk.E.h) pk.E.h = mpi_const (MPI_C_ONE); } if (DBG_CIPHER) { log_debug ("ecc_verify info: %s/%s%s\n", _gcry_ecc_model2str (pk.E.model), _gcry_ecc_dialect2str (pk.E.dialect), (sigflags & PUBKEY_FLAG_EDDSA)? "+EdDSA":""); if (pk.E.name) log_debug ("ecc_verify name: %s\n", pk.E.name); log_printmpi ("ecc_verify p", pk.E.p); log_printmpi ("ecc_verify a", pk.E.a); log_printmpi ("ecc_verify b", pk.E.b); log_printpnt ("ecc_verify g", &pk.E.G, NULL); log_printmpi ("ecc_verify n", pk.E.n); log_printmpi ("ecc_verify h", pk.E.h); log_printmpi ("ecc_verify q", mpi_q); } if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !pk.E.h || !mpi_q) { rc = GPG_ERR_NO_OBJ; goto leave; } /* * Verify the signature. */ if ((sigflags & PUBKEY_FLAG_EDDSA)) { rc = _gcry_ecc_eddsa_verify (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q); } else if ((sigflags & PUBKEY_FLAG_GOST)) { point_init (&pk.Q); rc = _gcry_ecc_os2ec (&pk.Q, mpi_q); if (rc) goto leave; rc = _gcry_ecc_gost_verify (data, &pk, sig_r, sig_s); } else { point_init (&pk.Q); if (pk.E.dialect == ECC_DIALECT_ED25519) { mpi_ec_t ec; /* Fixme: Factor the curve context setup out of eddsa_verify and ecdsa_verify. So that we don't do it twice. */ ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, 0, pk.E.p, pk.E.a, pk.E.b); rc = _gcry_ecc_eddsa_decodepoint (mpi_q, ec, &pk.Q, NULL, NULL); _gcry_mpi_ec_free (ec); } else { rc = _gcry_ecc_os2ec (&pk.Q, mpi_q); } if (rc) goto leave; if (mpi_is_opaque (data)) { const void *abuf; unsigned int abits, qbits; gcry_mpi_t a; qbits = mpi_get_nbits (pk.E.n); abuf = mpi_get_opaque (data, &abits); rc = _gcry_mpi_scan (&a, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL); if (!rc) { if (abits > qbits) mpi_rshift (a, a, abits - qbits); rc = _gcry_ecc_ecdsa_verify (a, &pk, sig_r, sig_s); _gcry_mpi_release (a); } } else rc = _gcry_ecc_ecdsa_verify (data, &pk, sig_r, sig_s); } leave: _gcry_mpi_release (pk.E.p); _gcry_mpi_release (pk.E.a); _gcry_mpi_release (pk.E.b); _gcry_mpi_release (mpi_g); point_free (&pk.E.G); _gcry_mpi_release (pk.E.n); _gcry_mpi_release (pk.E.h); _gcry_mpi_release (mpi_q); point_free (&pk.Q); _gcry_mpi_release (data); _gcry_mpi_release (sig_r); _gcry_mpi_release (sig_s); xfree (curvename); sexp_release (l1); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("ecc_verify => %s\n", rc?gpg_strerror (rc):"Good"); return rc; } /* ecdh raw is classic 2-round DH protocol published in 1976. * * Overview of ecc_encrypt_raw and ecc_decrypt_raw. * * As with any PK operation, encrypt version uses a public key and * decrypt -- private. * * Symbols used below: * G - field generator point * d - private long-term scalar * dG - public long-term key * k - ephemeral scalar * kG - ephemeral public key * dkG - shared secret * * ecc_encrypt_raw description: * input: * data[0] : private scalar (k) * output: A new S-expression with the parameters: * s : shared point (kdG) * e : generated ephemeral public key (kG) * * ecc_decrypt_raw description: * input: * data[0] : a point kG (ephemeral public key) * output: * result[0] : shared point (kdG) */ static gcry_err_code_t ecc_encrypt_raw (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms) { unsigned int nbits; gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; char *curvename = NULL; gcry_mpi_t mpi_g = NULL; gcry_mpi_t mpi_q = NULL; gcry_mpi_t mpi_s = NULL; gcry_mpi_t mpi_e = NULL; gcry_mpi_t data = NULL; ECC_public_key pk; mpi_ec_t ec = NULL; int flags = 0; memset (&pk, 0, sizeof pk); _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT, (nbits = ecc_get_nbits (keyparms))); /* Look for flags. */ l1 = sexp_find_token (keyparms, "flags", 0); if (l1) { rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); if (rc) goto leave; } sexp_release (l1); l1 = NULL; /* * Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* * Extract the key. */ - rc = sexp_extract_param (keyparms, NULL, - (flags & PUBKEY_FLAG_DJB_TWEAK)? - "-p?a?b?g?n?h?/q" : "-p?a?b?g?n?h?+q", + rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?/q", &pk.E.p, &pk.E.a, &pk.E.b, &mpi_g, &pk.E.n, &pk.E.h, &mpi_q, NULL); if (rc) goto leave; if (mpi_g) { point_init (&pk.E.G); rc = _gcry_ecc_os2ec (&pk.E.G, mpi_g); if (rc) goto leave; } /* Add missing parameters using the optional curve parameter. */ l1 = sexp_find_token (keyparms, "curve", 5); if (l1) { curvename = sexp_nth_string (l1, 1); if (curvename) { rc = _gcry_ecc_fill_in_curve (0, curvename, &pk.E, NULL); if (rc) goto leave; } } /* Guess required fields if a curve parameter has not been given. */ if (!curvename) { pk.E.model = MPI_EC_WEIERSTRASS; pk.E.dialect = ECC_DIALECT_STANDARD; if (!pk.E.h) pk.E.h = mpi_const (MPI_C_ONE); } /* * Tweak the scalar bits by cofactor and number of bits of the field. * It assumes the cofactor is a power of 2. */ if ((flags & PUBKEY_FLAG_DJB_TWEAK)) { int i; for (i = 0; i < mpi_get_nbits (pk.E.h) - 1; i++) mpi_clear_bit (data, i); mpi_set_highbit (data, mpi_get_nbits (pk.E.p) - 1); } if (DBG_CIPHER) log_mpidump ("ecc_encrypt data", data); if (DBG_CIPHER) { log_debug ("ecc_encrypt info: %s/%s\n", _gcry_ecc_model2str (pk.E.model), _gcry_ecc_dialect2str (pk.E.dialect)); if (pk.E.name) log_debug ("ecc_encrypt name: %s\n", pk.E.name); log_printmpi ("ecc_encrypt p", pk.E.p); log_printmpi ("ecc_encrypt a", pk.E.a); log_printmpi ("ecc_encrypt b", pk.E.b); log_printpnt ("ecc_encrypt g", &pk.E.G, NULL); log_printmpi ("ecc_encrypt n", pk.E.n); log_printmpi ("ecc_encrypt h", pk.E.h); log_printmpi ("ecc_encrypt q", mpi_q); } if (!pk.E.p || !pk.E.a || !pk.E.b || !pk.E.G.x || !pk.E.n || !pk.E.h || !mpi_q) { rc = GPG_ERR_NO_OBJ; goto leave; } /* Compute the encrypted value. */ ec = _gcry_mpi_ec_p_internal_new (pk.E.model, pk.E.dialect, flags, pk.E.p, pk.E.a, pk.E.b); /* Convert the public key. */ if (mpi_q) { point_init (&pk.Q); if (ec->model == MPI_EC_MONTGOMERY) rc = _gcry_ecc_mont_decodepoint (mpi_q, ec, &pk.Q); else rc = _gcry_ecc_os2ec (&pk.Q, mpi_q); if (rc) goto leave; } /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so */ { mpi_point_struct R; /* Result that we return. */ gcry_mpi_t x, y; unsigned char *rawmpi; unsigned int rawmpilen; rc = 0; x = mpi_new (0); if (ec->model == MPI_EC_MONTGOMERY) y = NULL; else y = mpi_new (0); point_init (&R); /* R = kQ <=> R = kdG */ _gcry_mpi_ec_mul_point (&R, data, &pk.Q, ec); if (_gcry_mpi_ec_get_affine (x, y, &R, ec)) { /* * Here, X is 0. In the X25519 computation on Curve25519, X0 * function maps infinity to zero. So, when PUBKEY_FLAG_DJB_TWEAK * is enabled, return the result of 0 not raising an error. * * This is a corner case. It never occurs with properly * generated public keys, but it might happen with blindly * imported public key which might not follow the key * generation procedure. */ if (!(flags & PUBKEY_FLAG_DJB_TWEAK)) { /* It's not for X25519, then, the input data was simply wrong. */ rc = GPG_ERR_INV_DATA; goto leave_main; } } if (y) mpi_s = _gcry_ecc_ec2os (x, y, pk.E.p); else { rawmpi = _gcry_mpi_get_buffer_extra (x, nbits/8, -1, &rawmpilen, NULL); if (!rawmpi) rc = gpg_err_code_from_syserror (); else { rawmpi[0] = 0x40; rawmpilen++; mpi_s = mpi_new (0); mpi_set_opaque (mpi_s, rawmpi, rawmpilen*8); } } /* R = kG */ _gcry_mpi_ec_mul_point (&R, data, &pk.E.G, ec); if (_gcry_mpi_ec_get_affine (x, y, &R, ec)) { rc = GPG_ERR_INV_DATA; goto leave_main; } if (y) mpi_e = _gcry_ecc_ec2os (x, y, pk.E.p); else { rawmpi = _gcry_mpi_get_buffer_extra (x, nbits/8, -1, &rawmpilen, NULL); if (!rawmpi) rc = gpg_err_code_from_syserror (); else { rawmpi[0] = 0x40; rawmpilen++; mpi_e = mpi_new (0); mpi_set_opaque (mpi_e, rawmpi, rawmpilen*8); } } leave_main: mpi_free (x); mpi_free (y); point_free (&R); if (rc) goto leave; } if (!rc) rc = sexp_build (r_ciph, NULL, "(enc-val(ecdh(s%m)(e%m)))", mpi_s, mpi_e); leave: _gcry_mpi_release (pk.E.p); _gcry_mpi_release (pk.E.a); _gcry_mpi_release (pk.E.b); _gcry_mpi_release (mpi_g); point_free (&pk.E.G); _gcry_mpi_release (pk.E.n); _gcry_mpi_release (pk.E.h); _gcry_mpi_release (mpi_q); point_free (&pk.Q); _gcry_mpi_release (data); _gcry_mpi_release (mpi_s); _gcry_mpi_release (mpi_e); xfree (curvename); sexp_release (l1); _gcry_mpi_ec_free (ec); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("ecc_encrypt => %s\n", gpg_strerror (rc)); return rc; } /* input: * data[0] : a point kG (ephemeral public key) * output: * resaddr[0] : shared point kdG * * see ecc_encrypt_raw for details. */ static gcry_err_code_t ecc_decrypt_raw (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms) { unsigned int nbits; gpg_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; gcry_mpi_t data_e = NULL; ECC_secret_key sk; gcry_mpi_t mpi_g = NULL; char *curvename = NULL; mpi_ec_t ec = NULL; mpi_point_struct kG; mpi_point_struct R; gcry_mpi_t r = NULL; int flags = 0; memset (&sk, 0, sizeof sk); point_init (&kG); point_init (&R); _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT, (nbits = ecc_get_nbits (keyparms))); /* Look for flags. */ l1 = sexp_find_token (keyparms, "flags", 0); if (l1) { rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); if (rc) goto leave; } sexp_release (l1); l1 = NULL; /* * Extract the data. */ rc = _gcry_pk_util_preparse_encval (s_data, ecc_names, &l1, &ctx); if (rc) goto leave; rc = sexp_extract_param (l1, NULL, "e", &data_e, NULL); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("ecc_decrypt d_e", data_e); if (mpi_is_opaque (data_e)) { rc = GPG_ERR_INV_DATA; goto leave; } /* * Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "-p?a?b?g?n?h?+d", &sk.E.p, &sk.E.a, &sk.E.b, &mpi_g, &sk.E.n, &sk.E.h, &sk.d, NULL); if (rc) goto leave; if (mpi_g) { point_init (&sk.E.G); rc = _gcry_ecc_os2ec (&sk.E.G, mpi_g); if (rc) goto leave; } /* Add missing parameters using the optional curve parameter. */ sexp_release (l1); l1 = sexp_find_token (keyparms, "curve", 5); if (l1) { curvename = sexp_nth_string (l1, 1); if (curvename) { rc = _gcry_ecc_fill_in_curve (0, curvename, &sk.E, NULL); if (rc) goto leave; } } /* Guess required fields if a curve parameter has not been given. */ if (!curvename) { sk.E.model = MPI_EC_WEIERSTRASS; sk.E.dialect = ECC_DIALECT_STANDARD; if (!sk.E.h) sk.E.h = mpi_const (MPI_C_ONE); } if (DBG_CIPHER) { log_debug ("ecc_decrypt info: %s/%s\n", _gcry_ecc_model2str (sk.E.model), _gcry_ecc_dialect2str (sk.E.dialect)); if (sk.E.name) log_debug ("ecc_decrypt name: %s\n", sk.E.name); log_printmpi ("ecc_decrypt p", sk.E.p); log_printmpi ("ecc_decrypt a", sk.E.a); log_printmpi ("ecc_decrypt b", sk.E.b); log_printpnt ("ecc_decrypt g", &sk.E.G, NULL); log_printmpi ("ecc_decrypt n", sk.E.n); log_printmpi ("ecc_decrypt h", sk.E.h); if (!fips_mode ()) log_printmpi ("ecc_decrypt d", sk.d); } if (!sk.E.p || !sk.E.a || !sk.E.b || !sk.E.G.x || !sk.E.n || !sk.E.h || !sk.d) { rc = GPG_ERR_NO_OBJ; goto leave; } ec = _gcry_mpi_ec_p_internal_new (sk.E.model, sk.E.dialect, flags, sk.E.p, sk.E.a, sk.E.b); /* * Compute the plaintext. */ if (ec->model == MPI_EC_MONTGOMERY) rc = _gcry_ecc_mont_decodepoint (data_e, ec, &kG); else rc = _gcry_ecc_os2ec (&kG, data_e); if (rc) goto leave; if (DBG_CIPHER) log_printpnt ("ecc_decrypt kG", &kG, NULL); if ((flags & PUBKEY_FLAG_DJB_TWEAK)) { /* For X25519, by its definition, validation should not be done. */ /* (Instead, we do output check.) * * However, to mitigate secret key leak from our implementation, * we also do input validation here. For constant-time * implementation, we can remove this input validation. */ if (_gcry_mpi_ec_bad_point (&kG, ec)) { rc = GPG_ERR_INV_DATA; goto leave; } } else if (!_gcry_mpi_ec_curve_point (&kG, ec)) { rc = GPG_ERR_INV_DATA; goto leave; } /* R = dkG */ _gcry_mpi_ec_mul_point (&R, sk.d, &kG, ec); /* The following is false: assert( mpi_cmp_ui( R.x, 1 )==0 );, so: */ { gcry_mpi_t x, y; x = mpi_new (0); if (ec->model == MPI_EC_MONTGOMERY) y = NULL; else y = mpi_new (0); if (_gcry_mpi_ec_get_affine (x, y, &R, ec)) { rc = GPG_ERR_INV_DATA; goto leave; /* * Note for X25519. * * By the definition of X25519, this is the case where X25519 * returns 0, mapping infinity to zero. However, we * deliberately let it return an error. * * For X25519 ECDH, comming here means that it might be * decrypted by anyone with the shared secret of 0 (the result * of this function could be always 0 by other scalar values, * other than the private key of SK.D). * * So, it looks like an encrypted message but it can be * decrypted by anyone, or at least something wrong * happens. Recipient should not proceed as if it were * properly encrypted message. * * This handling is needed for our major usage of GnuPG, * where it does the One-Pass Diffie-Hellman method, * C(1, 1, ECC CDH), with an ephemeral key. */ } if (y) r = _gcry_ecc_ec2os (x, y, sk.E.p); else { unsigned char *rawmpi; unsigned int rawmpilen; rawmpi = _gcry_mpi_get_buffer_extra (x, nbits/8, -1, &rawmpilen, NULL); if (!rawmpi) { rc = gpg_err_code_from_syserror (); goto leave; } else { rawmpi[0] = 0x40; rawmpilen++; r = mpi_new (0); mpi_set_opaque (r, rawmpi, rawmpilen*8); } } if (!r) rc = gpg_err_code_from_syserror (); else rc = 0; mpi_free (x); mpi_free (y); } if (DBG_CIPHER) log_printmpi ("ecc_decrypt res", r); if (!rc) rc = sexp_build (r_plain, NULL, "(value %m)", r); leave: point_free (&R); point_free (&kG); _gcry_mpi_release (r); _gcry_mpi_release (sk.E.p); _gcry_mpi_release (sk.E.a); _gcry_mpi_release (sk.E.b); _gcry_mpi_release (mpi_g); point_free (&sk.E.G); _gcry_mpi_release (sk.E.n); _gcry_mpi_release (sk.E.h); _gcry_mpi_release (sk.d); _gcry_mpi_release (data_e); xfree (curvename); sexp_release (l1); _gcry_mpi_ec_free (ec); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("ecc_decrypt => %s\n", gpg_strerror (rc)); return rc; } /* Return the number of bits for the key described by PARMS. On error * 0 is returned. The format of PARMS starts with the algorithm name; * for example: * * (ecc * (curve ) * (p ) * (a ) * (b ) * (g ) * (n ) * (q )) * * More parameters may be given. Either P or CURVE is needed. */ static unsigned int ecc_get_nbits (gcry_sexp_t parms) { gcry_sexp_t l1; gcry_mpi_t p; unsigned int nbits = 0; char *curve; l1 = sexp_find_token (parms, "p", 1); if (!l1) { /* Parameter P not found - check whether we have "curve". */ l1 = sexp_find_token (parms, "curve", 5); if (!l1) return 0; /* Neither P nor CURVE found. */ curve = sexp_nth_string (l1, 1); sexp_release (l1); if (!curve) return 0; /* No curve name given (or out of core). */ if (_gcry_ecc_fill_in_curve (0, curve, NULL, &nbits)) nbits = 0; xfree (curve); } else { p = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG); sexp_release (l1); if (p) { nbits = mpi_get_nbits (p); _gcry_mpi_release (p); } } return nbits; } /* See rsa.c for a description of this function. */ static gpg_err_code_t compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparms) { #define N_COMPONENTS 7 static const char names[N_COMPONENTS] = "pabgnhq"; gpg_err_code_t rc; gcry_sexp_t l1; gcry_mpi_t values[N_COMPONENTS]; int idx; char *curvename = NULL; int flags = 0; enum gcry_mpi_ec_models model = 0; enum ecc_dialects dialect = 0; + const unsigned char *raw; + unsigned int n; /* Clear the values first. */ for (idx=0; idx < N_COMPONENTS; idx++) values[idx] = NULL; /* Look for flags. */ l1 = sexp_find_token (keyparms, "flags", 0); if (l1) { rc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); if (rc) goto leave; } /* Extract the parameters. */ if ((flags & PUBKEY_FLAG_PARAM)) - { - if ((flags & PUBKEY_FLAG_DJB_TWEAK)) - rc = sexp_extract_param (keyparms, NULL, "p?a?b?g?n?h?/q", - &values[0], &values[1], &values[2], - &values[3], &values[4], &values[5], - &values[6], NULL); - else - rc = sexp_extract_param (keyparms, NULL, "p?a?b?g?n?h?q", - &values[0], &values[1], &values[2], - &values[3], &values[4], &values[5], - &values[6], NULL); - } + rc = sexp_extract_param (keyparms, NULL, "p?a?b?g?n?h?/q", + &values[0], &values[1], &values[2], + &values[3], &values[4], &values[5], + &values[6], NULL); else - { - if ((flags & PUBKEY_FLAG_DJB_TWEAK)) - rc = sexp_extract_param (keyparms, NULL, "/q", - &values[6], NULL); - else - rc = sexp_extract_param (keyparms, NULL, "q", - &values[6], NULL); - } + rc = sexp_extract_param (keyparms, NULL, "/q", &values[6], NULL); if (rc) goto leave; /* Check whether a curve parameter is available and use that to fill in missing values. */ sexp_release (l1); l1 = sexp_find_token (keyparms, "curve", 5); if (l1) { curvename = sexp_nth_string (l1, 1); if (curvename) { rc = _gcry_ecc_update_curve_param (curvename, &model, &dialect, &values[0], &values[1], &values[2], &values[3], &values[4], &values[5]); if (rc) goto leave; } } /* Guess required fields if a curve parameter has not been given. FIXME: This is a crude hacks. We need to fix that. */ if (!curvename) { model = ((flags & PUBKEY_FLAG_EDDSA) ? MPI_EC_EDWARDS : MPI_EC_WEIERSTRASS); dialect = ((flags & PUBKEY_FLAG_EDDSA) ? ECC_DIALECT_ED25519 : ECC_DIALECT_STANDARD); if (!values[5]) - values[5] = mpi_const (MPI_C_ONE); + values[5] = mpi_const (MPI_C_ONE); } /* Check that all parameters are known and normalize all MPIs (that should not be required but we use an internal function later and thus we better make 100% sure that they are normalized). */ for (idx = 0; idx < N_COMPONENTS; idx++) if (!values[idx]) { rc = GPG_ERR_NO_OBJ; goto leave; } else _gcry_mpi_normalize (values[idx]); /* Uncompress the public key with the exception of EdDSA where compression is the default and we thus compute the keygrip using the compressed version. Because we don't support any non-eddsa compression, the only thing we need to do is to compress EdDSA. */ - if ((flags & PUBKEY_FLAG_DJB_TWEAK)) + if ((flags & PUBKEY_FLAG_EDDSA) && dialect == ECC_DIALECT_ED25519) { - rc = _gcry_ecc_eddsa_ensure_compact (values[6], 256); + const unsigned int pbits = mpi_get_nbits (values[0]); + + rc = _gcry_ecc_eddsa_ensure_compact (values[6], pbits); if (rc) goto leave; } + else if ((flags & PUBKEY_FLAG_DJB_TWEAK)) + { + /* Remove the prefix 0x40 for keygrip computation. */ + raw = mpi_get_opaque (values[6], &n); + if (raw) + { + n = (n + 7)/8; + + if (n > 1 && (n%2) && raw[0] == 0x40) + if (!_gcry_mpi_set_opaque_copy (values[6], raw + 1, (n - 1)*8)) + rc = gpg_err_code_from_syserror (); + } + else + { + rc = GPG_ERR_INV_OBJ; + goto leave; + } + } /* Hash them all. */ for (idx = 0; idx < N_COMPONENTS; idx++) { char buf[30]; if (idx == 5) continue; /* Skip cofactor. */ if (mpi_is_opaque (values[idx])) { - const unsigned char *raw; - unsigned int n; - raw = mpi_get_opaque (values[idx], &n); n = (n + 7)/8; snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], n); _gcry_md_write (md, buf, strlen (buf)); _gcry_md_write (md, raw, n); _gcry_md_write (md, ")", 1); } else { unsigned char *rawmpi; unsigned int rawmpilen; rawmpi = _gcry_mpi_get_buffer (values[idx], 0, &rawmpilen, NULL); if (!rawmpi) { rc = gpg_err_code_from_syserror (); goto leave; } snprintf (buf, sizeof buf, "(1:%c%u:", names[idx], rawmpilen); _gcry_md_write (md, buf, strlen (buf)); _gcry_md_write (md, rawmpi, rawmpilen); _gcry_md_write (md, ")", 1); xfree (rawmpi); } } leave: xfree (curvename); sexp_release (l1); for (idx = 0; idx < N_COMPONENTS; idx++) _gcry_mpi_release (values[idx]); return rc; #undef N_COMPONENTS } /* Low-level API helper functions. */ /* This is the worker function for gcry_pubkey_get_sexp for ECC algorithms. Note that the caller has already stored NULL at R_SEXP. */ gpg_err_code_t _gcry_pk_ecc_get_sexp (gcry_sexp_t *r_sexp, int mode, mpi_ec_t ec) { gpg_err_code_t rc; gcry_mpi_t mpi_G = NULL; gcry_mpi_t mpi_Q = NULL; if (!ec->p || !ec->a || !ec->b || !ec->G || !ec->n || !ec->h) return GPG_ERR_BAD_CRYPT_CTX; if (mode == GCRY_PK_GET_SECKEY && !ec->d) return GPG_ERR_NO_SECKEY; /* Compute the public point if it is missing. */ if (!ec->Q && ec->d) ec->Q = _gcry_ecc_compute_public (NULL, ec, NULL, NULL); /* Encode G and Q. */ mpi_G = _gcry_mpi_ec_ec2os (ec->G, ec); if (!mpi_G) { rc = GPG_ERR_BROKEN_PUBKEY; goto leave; } if (!ec->Q) { rc = GPG_ERR_BAD_CRYPT_CTX; goto leave; } if (ec->dialect == ECC_DIALECT_ED25519) { unsigned char *encpk; unsigned int encpklen; rc = _gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0, &encpk, &encpklen); if (rc) goto leave; mpi_Q = mpi_set_opaque (NULL, encpk, encpklen*8); encpk = NULL; } else if (ec->model == MPI_EC_MONTGOMERY) { unsigned char *encpk; unsigned int encpklen; encpk = _gcry_mpi_get_buffer_extra (ec->Q->x, (ec->nbits+7)/8, -1, &encpklen, NULL); if (encpk == NULL) rc = gpg_err_code_from_syserror (); else { encpk[0] = 0x40; encpklen++; rc = 0; } if (rc) goto leave; mpi_Q = mpi_set_opaque (NULL, encpk, encpklen*8); } else { mpi_Q = _gcry_mpi_ec_ec2os (ec->Q, ec); } if (!mpi_Q) { rc = GPG_ERR_BROKEN_PUBKEY; goto leave; } /* Fixme: We should return a curve name instead of the parameters if if know that they match a curve. */ if (ec->d && (!mode || mode == GCRY_PK_GET_SECKEY)) { /* Let's return a private key. */ rc = sexp_build (r_sexp, NULL, "(private-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)(d%m)))", ec->p, ec->a, ec->b, mpi_G, ec->n, ec->h, mpi_Q, ec->d); } else if (ec->Q) { /* Let's return a public key. */ rc = sexp_build (r_sexp, NULL, "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)(q%m)))", ec->p, ec->a, ec->b, mpi_G, ec->n, ec->h, mpi_Q); } else rc = GPG_ERR_BAD_CRYPT_CTX; leave: mpi_free (mpi_Q); mpi_free (mpi_G); return rc; } /* Self-test section. */ static const char * selftest_sign (gcry_sexp_t pkey, gcry_sexp_t skey) { /* Sample data from RFC 6979 section A.2.5, hash is of message "sample" */ static const char sample_data[] = "(data (flags rfc6979)" " (hash sha256 #af2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268e98915" /**/ "62113d8a62add1bf#))"; static const char sample_data_bad[] = "(data (flags rfc6979)" " (hash sha256 #bf2bdbe1aa9b6ec1e2ade1d694f41fc71a831d0268e98915" /**/ "62113d8a62add1bf#))"; static const char signature_r[] = "efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716"; static const char signature_s[] = "f7cb1c942d657c41d436c7a1b6e29f65f3e900dbb9aff4064dc4ab2f843acda8"; const char *errtxt = NULL; gcry_error_t err; gcry_sexp_t data = NULL; gcry_sexp_t data_bad = NULL; gcry_sexp_t sig = NULL; gcry_sexp_t l1 = NULL; gcry_sexp_t l2 = NULL; gcry_mpi_t r = NULL; gcry_mpi_t s = NULL; gcry_mpi_t calculated_r = NULL; gcry_mpi_t calculated_s = NULL; int cmp; err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data)); if (!err) err = sexp_sscan (&data_bad, NULL, sample_data_bad, strlen (sample_data_bad)); if (!err) err = _gcry_mpi_scan (&r, GCRYMPI_FMT_HEX, signature_r, 0, NULL); if (!err) err = _gcry_mpi_scan (&s, GCRYMPI_FMT_HEX, signature_s, 0, NULL); if (err) { errtxt = "converting data failed"; goto leave; } err = _gcry_pk_sign (&sig, data, skey); if (err) { errtxt = "signing failed"; goto leave; } /* check against known signature */ errtxt = "signature validity failed"; l1 = _gcry_sexp_find_token (sig, "sig-val", 0); if (!l1) goto leave; l2 = _gcry_sexp_find_token (l1, "ecdsa", 0); if (!l2) goto leave; sexp_release (l1); l1 = l2; l2 = _gcry_sexp_find_token (l1, "r", 0); if (!l2) goto leave; calculated_r = _gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG); if (!calculated_r) goto leave; sexp_release (l2); l2 = _gcry_sexp_find_token (l1, "s", 0); if (!l2) goto leave; calculated_s = _gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG); if (!calculated_s) goto leave; errtxt = "known sig check failed"; cmp = _gcry_mpi_cmp (r, calculated_r); if (cmp) goto leave; cmp = _gcry_mpi_cmp (s, calculated_s); if (cmp) goto leave; errtxt = NULL; /* verify generated signature */ err = _gcry_pk_verify (sig, data, pkey); if (err) { errtxt = "verify failed"; goto leave; } err = _gcry_pk_verify (sig, data_bad, pkey); if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE) { errtxt = "bad signature not detected"; goto leave; } leave: sexp_release (sig); sexp_release (data_bad); sexp_release (data); sexp_release (l1); sexp_release (l2); mpi_release (r); mpi_release (s); mpi_release (calculated_r); mpi_release (calculated_s); return errtxt; } static gpg_err_code_t selftests_ecdsa (selftest_report_func_t report) { const char *what; const char *errtxt; gcry_error_t err; gcry_sexp_t skey = NULL; gcry_sexp_t pkey = NULL; what = "convert"; err = sexp_sscan (&skey, NULL, sample_secret_key_secp256, strlen (sample_secret_key_secp256)); if (!err) err = sexp_sscan (&pkey, NULL, sample_public_key_secp256, strlen (sample_public_key_secp256)); if (err) { errtxt = _gcry_strerror (err); goto failed; } what = "key consistency"; err = ecc_check_secret_key(skey); if (err) { errtxt = _gcry_strerror (err); goto failed; } what = "sign"; errtxt = selftest_sign (pkey, skey); if (errtxt) goto failed; sexp_release(pkey); sexp_release(skey); return 0; /* Succeeded. */ failed: sexp_release(pkey); sexp_release(skey); if (report) report ("pubkey", GCRY_PK_ECC, what, errtxt); return GPG_ERR_SELFTEST_FAILED; } /* Run a full self-test for ALGO and return 0 on success. */ static gpg_err_code_t run_selftests (int algo, int extended, selftest_report_func_t report) { (void)extended; if (algo != GCRY_PK_ECC) return GPG_ERR_PUBKEY_ALGO; return selftests_ecdsa (report); } gcry_pk_spec_t _gcry_pubkey_spec_ecc = { GCRY_PK_ECC, { 0, 1 }, (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR), "ECC", ecc_names, "pabgnhq", "pabgnhqd", "sw", "rs", "pabgnhq", ecc_generate, ecc_check_secret_key, ecc_encrypt_raw, ecc_decrypt_raw, ecc_sign, ecc_verify, ecc_get_nbits, run_selftests, compute_keygrip, _gcry_ecc_get_curve, _gcry_ecc_get_param_sexp };