Add a function to derive an EC key from some input secret.
Chrome sync folks need to do this. Add a function for it. There doesn't
seem to be a standard way to do it, so pick something arbitrary.
Bug: chromium:1010968
Change-Id: Ib55456e4af5849cd9da33f397e8f12deb6f02917
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/38144
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/CMakeLists.txt b/crypto/CMakeLists.txt
index b874c62..d84e545 100644
--- a/crypto/CMakeLists.txt
+++ b/crypto/CMakeLists.txt
@@ -268,6 +268,7 @@
ecdh_extra/ecdh_extra.c
ecdsa_extra/ecdsa_asn1.c
ec_extra/ec_asn1.c
+ ec_extra/ec_derive.c
err/err.c
err_data.c
engine/engine.c
diff --git a/crypto/ec_extra/ec_derive.c b/crypto/ec_extra/ec_derive.c
new file mode 100644
index 0000000..ca1dc44
--- /dev/null
+++ b/crypto/ec_extra/ec_derive.c
@@ -0,0 +1,96 @@
+/* Copyright (c) 2019, Google Inc.
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+ * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
+
+#include <openssl/ec_key.h>
+
+#include <string.h>
+
+#include <openssl/buf.h>
+#include <openssl/ec.h>
+#include <openssl/err.h>
+#include <openssl/digest.h>
+#include <openssl/hkdf.h>
+#include <openssl/mem.h>
+
+#include "../fipsmodule/ec/internal.h"
+
+
+EC_KEY *EC_KEY_derive_from_secret(const EC_GROUP *group, const uint8_t *secret,
+ size_t secret_len) {
+#define EC_KEY_DERIVE_MAX_NAME_LEN 16
+ const char *name = EC_curve_nid2nist(EC_GROUP_get_curve_name(group));
+ if (name == NULL || strlen(name) > EC_KEY_DERIVE_MAX_NAME_LEN) {
+ OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP);
+ return NULL;
+ }
+
+ // Assemble a label string to provide some key separation in case |secret| is
+ // misused, but ultimately it's on the caller to ensure |secret| is suitably
+ // separated.
+ static const char kLabel[] = "derive EC key ";
+ char info[sizeof(kLabel) + EC_KEY_DERIVE_MAX_NAME_LEN];
+ BUF_strlcpy(info, kLabel, sizeof(info));
+ BUF_strlcat(info, name, sizeof(info));
+
+ // Generate 128 bits beyond the group order so the bias is at most 2^-128.
+#define EC_KEY_DERIVE_EXTRA_BITS 128
+#define EC_KEY_DERIVE_EXTRA_BYTES (EC_KEY_DERIVE_EXTRA_BITS / 8)
+
+ if (EC_GROUP_order_bits(group) <= EC_KEY_DERIVE_EXTRA_BITS + 8) {
+ // The reduction strategy below requires the group order be large enough.
+ // (The actual bound is a bit tighter, but our curves are much larger than
+ // 128-bit.)
+ OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
+ return NULL;
+ }
+
+ uint8_t derived[EC_KEY_DERIVE_EXTRA_BYTES + EC_MAX_BYTES];
+ size_t derived_len = BN_num_bytes(&group->order) + EC_KEY_DERIVE_EXTRA_BYTES;
+ assert(derived_len <= sizeof(derived));
+ if (!HKDF(derived, derived_len, EVP_sha256(), secret, secret_len,
+ /*salt=*/NULL, /*salt_len=*/0, (const uint8_t *)info,
+ strlen(info))) {
+ return NULL;
+ }
+
+ EC_KEY *key = EC_KEY_new();
+ BN_CTX *ctx = BN_CTX_new();
+ BIGNUM *priv = BN_bin2bn(derived, derived_len, NULL);
+ EC_POINT *pub = EC_POINT_new(group);
+ if (key == NULL || ctx == NULL || priv == NULL || pub == NULL ||
+ // Reduce |priv| with Montgomery reduction. First, convert "from"
+ // Montgomery form to compute |priv| * R^-1 mod |order|. This requires
+ // |priv| be under order * R, which is true if the group order is large
+ // enough. 2^(num_bytes(order)) < 2^8 * order, so:
+ //
+ // priv < 2^8 * order * 2^128 < order * order < order * R
+ !BN_from_montgomery(priv, priv, group->order_mont, ctx) ||
+ // Multiply by R^2 and do another Montgomery reduction to compute
+ // priv * R^-1 * R^2 * R^-1 = priv mod order.
+ !BN_to_montgomery(priv, priv, group->order_mont, ctx) ||
+ !EC_POINT_mul(group, pub, priv, NULL, NULL, ctx) ||
+ !EC_KEY_set_group(key, group) || !EC_KEY_set_public_key(key, pub) ||
+ !EC_KEY_set_private_key(key, priv)) {
+ EC_KEY_free(key);
+ key = NULL;
+ goto err;
+ }
+
+err:
+ OPENSSL_cleanse(derived, sizeof(derived));
+ BN_CTX_free(ctx);
+ BN_free(priv);
+ EC_POINT_free(pub);
+ return key;
+}
diff --git a/crypto/fipsmodule/ec/ec_test.cc b/crypto/fipsmodule/ec/ec_test.cc
index 9737d31..07638cd 100644
--- a/crypto/fipsmodule/ec/ec_test.cc
+++ b/crypto/fipsmodule/ec/ec_test.cc
@@ -912,3 +912,87 @@
#endif
});
}
+
+static uint8_t FromHexChar(char c) {
+ if ('0' <= c && c <= '9') {
+ return c - '0';
+ }
+ if ('a' <= c && c <= 'f') {
+ return c - 'a' + 10;
+ }
+ abort();
+}
+
+static std::vector<uint8_t> HexToBytes(const char *str) {
+ std::vector<uint8_t> ret;
+ while (str[0] != '\0') {
+ ret.push_back((FromHexChar(str[0]) << 4) | FromHexChar(str[1]));
+ str += 2;
+ }
+ return ret;
+}
+
+TEST(ECTest, DeriveFromSecret) {
+ struct DeriveTest {
+ int curve;
+ std::vector<uint8_t> secret;
+ std::vector<uint8_t> expected_priv;
+ std::vector<uint8_t> expected_pub;
+ };
+ const DeriveTest kDeriveTests[] = {
+ {NID_X9_62_prime256v1, HexToBytes(""),
+ HexToBytes(
+ "b98a86a71efb51ebdac4759937b977e9b0c05224675bb2b6a58ba306e237f4b8"),
+ HexToBytes(
+ "04fbe6cab439918e00231a2ff073cdc25823998864a9eb36f809095a1a919ece875"
+ "a145803fbe89a6cde53936e3c6d9c253ed3d38f5f58cae455c27e95645ceda9")},
+ {NID_X9_62_prime256v1, HexToBytes("123456"),
+ HexToBytes(
+ "44a72bc62087b88e5ab7126766177ed0d8f1ed09ad066cd746527fc201105a7e"),
+ HexToBytes(
+ "04ec0555cd76e991fef7f5504343937d0f38696db3360a4854052cb0d84a377a5a0"
+ "ff64c352755c28692b4ae085c2b817db9a1eddbd22e9cf39c12751e0870791b")},
+ {NID_X9_62_prime256v1, HexToBytes("00000000000000000000000000000000"),
+ HexToBytes(
+ "7ca1e2c83e6a5f2c1b3e7d58180226f269930c4b9fbe2a275096079630b7c57d"),
+ HexToBytes(
+ "0442ef70c8fc0fbe383ed0a0da36f39f9a590f3feebc07863cc858c9a8ef0465731"
+ "0408c249bd4d61929c54b71ffe056e6b4fa1eb537039b43d1c175f0ceab0f89")},
+ {NID_X9_62_prime256v1,
+ HexToBytes(
+ "de9c9b35543aaa0fba039e34e8ca9695da3225c7161c9e3a8c70356cac28c780"),
+ HexToBytes(
+ "659f5abf3b62b9931c29d6ed0722efd2349fa56f54e708cf3272f620f1bc44d0"),
+ HexToBytes(
+ "046741f806b593bf3a3d4a9d76bdcb9b0d7874633cbea8f42c05e78561f7e8ec362"
+ "b9b6f1913ded796fbdafe7f210cea897ac22a4e580c06a60f2659fd09f1830f")},
+ {NID_secp384r1, HexToBytes("123456"),
+ HexToBytes("95cd90d548997de090c7622708eccb7edc1b1bd78d2422235ad97406dada"
+ "076555309da200096f6e4b36c46002beee89"),
+ HexToBytes(
+ "04007b2d026aa7636fa912c3f970d62bb6c10fa81c8f3290ed90b2d701696d1c6b9"
+ "5af88ce13e962996a7ac37e16527cb5d69bd081b8641d07634cf84b438600ec9434"
+ "15ac6bd7a0236f7ab0ea31ece67df03fa11646ea2b75e73d1b5e45b75c18")},
+ };
+
+ for (const auto &test : kDeriveTests) {
+ SCOPED_TRACE(Bytes(test.secret));
+ bssl::UniquePtr<EC_GROUP> group(EC_GROUP_new_by_curve_name(test.curve));
+ ASSERT_TRUE(group);
+ bssl::UniquePtr<EC_KEY> key(EC_KEY_derive_from_secret(
+ group.get(), test.secret.data(), test.secret.size()));
+ ASSERT_TRUE(key);
+
+ std::vector<uint8_t> priv(BN_num_bytes(EC_GROUP_get0_order(group.get())));
+ ASSERT_TRUE(BN_bn2bin_padded(priv.data(), priv.size(),
+ EC_KEY_get0_private_key(key.get())));
+ EXPECT_EQ(Bytes(priv), Bytes(test.expected_priv));
+
+ uint8_t *pub = nullptr;
+ size_t pub_len =
+ EC_KEY_key2buf(key.get(), POINT_CONVERSION_UNCOMPRESSED, &pub, nullptr);
+ bssl::UniquePtr<uint8_t> free_pub(pub);
+ EXPECT_NE(pub_len, 0u);
+ EXPECT_EQ(Bytes(pub, pub_len), Bytes(test.expected_pub));
+ }
+}
diff --git a/include/openssl/bn.h b/include/openssl/bn.h
index b6b7e9ab..0ca9ad5 100644
--- a/include/openssl/bn.h
+++ b/include/openssl/bn.h
@@ -846,8 +846,9 @@
const BN_MONT_CTX *mont, BN_CTX *ctx);
// BN_from_montgomery sets |ret| equal to |a| * R^-1, i.e. translates values out
-// of the Montgomery domain. |a| is assumed to be in the range [0, n), where |n|
-// is the Montgomery modulus. It returns one on success or zero on error.
+// of the Montgomery domain. |a| is assumed to be in the range [0, n*R), where
+// |n| is the Montgomery modulus. Note n < R, so inputs in the range [0, n*n)
+// are valid. This function returns one on success or zero on error.
OPENSSL_EXPORT int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a,
const BN_MONT_CTX *mont, BN_CTX *ctx);
diff --git a/include/openssl/ec_key.h b/include/openssl/ec_key.h
index be0faaf8..1bc6d30 100644
--- a/include/openssl/ec_key.h
+++ b/include/openssl/ec_key.h
@@ -130,7 +130,7 @@
// EC_KEY_set_private_key sets the private key of |key| to |priv|. It returns
// one on success and zero otherwise. |key| must already have had a group
// configured (see |EC_KEY_set_group| and |EC_KEY_new_by_curve_name|).
-OPENSSL_EXPORT int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *prv);
+OPENSSL_EXPORT int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *priv);
// EC_KEY_get0_public_key returns a pointer to the public key point inside
// |key|.
@@ -195,6 +195,20 @@
// additional checks for FIPS compliance.
OPENSSL_EXPORT int EC_KEY_generate_key_fips(EC_KEY *key);
+// EC_KEY_derive_from_secret deterministically derives a private key for |group|
+// from an input secret using HKDF-SHA256. It returns a newly-allocated |EC_KEY|
+// on success or NULL on error. |secret| must not be used in any other
+// algorithm. If using a base secret for multiple operations, derive separate
+// values with a KDF such as HKDF first.
+//
+// Note this function implements an arbitrary derivation scheme, rather than any
+// particular standard one. New protocols are recommended to use X25519 and
+// Ed25519, which have standard byte import functions. See
+// |X25519_public_from_private| and |ED25519_keypair_from_seed|.
+OPENSSL_EXPORT EC_KEY *EC_KEY_derive_from_secret(const EC_GROUP *group,
+ const uint8_t *secret,
+ size_t secret_len);
+
// Serialisation.
