Add SSWU_NU encode-to-curve functions from RFC 9380. Change-Id: Ia4e82c5b3302b490a39fa926f6f12c76378cdce2 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/82608 Commit-Queue: David Benjamin <davidben@google.com> Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/ec/hash_to_curve.cc b/crypto/ec/hash_to_curve.cc index b9601fc..a046ca6 100644 --- a/crypto/ec/hash_to_curve.cc +++ b/crypto/ec/hash_to_curve.cc
@@ -183,6 +183,24 @@ return 1; } +// hash_to_field1 implements the operation described in section 5.2 +// of RFC 9380, with count = 1. |k| is the security factor. +static int hash_to_field1(const EC_GROUP *group, const EVP_MD *md, + EC_FELEM *out, const uint8_t *dst, size_t dst_len, + unsigned k, const uint8_t *msg, size_t msg_len) { + size_t L; + uint8_t buf[2 * EC_MAX_BYTES]; + if (!num_bytes_to_derive(&L, &group->field.N, k) || + !expand_message_xmd(md, buf, L, msg, msg_len, dst, dst_len)) { + return 0; + } + BN_ULONG words[2 * EC_MAX_WORDS]; + size_t num_words = 2 * group->field.N.width; + big_endian_to_words(words, num_words, buf, L); + group->meth->felem_reduce(group, out, words, num_words); + return 1; +} + // hash_to_scalar behaves like |hash_to_field2| but returns a value modulo the // group order rather than a field element. |k| is the security factor. static int hash_to_scalar(const EC_GROUP *group, const EVP_MD *md, @@ -358,6 +376,28 @@ return 1; } +static int encode_to_curve(const EC_GROUP *group, const EVP_MD *md, + const EC_FELEM *Z, const EC_FELEM *c2, unsigned k, + EC_JACOBIAN *out, const uint8_t *dst, size_t dst_len, + const uint8_t *msg, size_t msg_len) { + EC_FELEM u; + if (!hash_to_field1(group, md, &u, dst, dst_len, k, msg, msg_len)) { + return 0; + } + + // Compute |c1| = (p - 3) / 4. + BN_ULONG c1[EC_MAX_WORDS]; + size_t num_c1 = group->field.N.width; + if (!bn_copy_words(c1, num_c1, &group->field.N)) { + return 0; + } + bn_rshift_words(c1, c1, /*shift=*/2, /*num=*/num_c1); + + map_to_curve_simple_swu(group, Z, c1, num_c1, c2, out, &u); + // All our curves have cofactor one, so |clear_cofactor| is a no-op. + return 1; +} + static int felem_from_u8(const EC_GROUP *group, EC_FELEM *out, uint8_t a) { uint8_t bytes[EC_MAX_BYTES] = {0}; size_t len = BN_num_bytes(&group->field.N); @@ -456,6 +496,76 @@ msg, msg_len); } +int ec_encode_to_curve_p256_xmd_sha256_sswu(const EC_GROUP *group, + EC_JACOBIAN *out, + const uint8_t *dst, size_t dst_len, + const uint8_t *msg, + size_t msg_len) { + // See section 8.3 of RFC 9380. + if (EC_GROUP_get_curve_name(group) != NID_X9_62_prime256v1) { + OPENSSL_PUT_ERROR(EC, EC_R_GROUP_MISMATCH); + return 0; + } + + // Z = -10, c2 = sqrt(10) + EC_FELEM Z, c2; + if (!felem_from_u8(group, &Z, 10) || + !ec_felem_from_bytes(group, &c2, kP256Sqrt10, sizeof(kP256Sqrt10))) { + return 0; + } + ec_felem_neg(group, &Z, &Z); + + return encode_to_curve(group, EVP_sha256(), &Z, &c2, /*k=*/128, out, dst, + dst_len, msg, msg_len); +} + +int EC_encode_to_curve_p256_xmd_sha256_sswu(const EC_GROUP *group, + EC_POINT *out, const uint8_t *dst, + size_t dst_len, const uint8_t *msg, + size_t msg_len) { + if (EC_GROUP_cmp(group, out->group, nullptr) != 0) { + OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return ec_encode_to_curve_p256_xmd_sha256_sswu(group, &out->raw, dst, dst_len, + msg, msg_len); +} + +int ec_encode_to_curve_p384_xmd_sha384_sswu(const EC_GROUP *group, + EC_JACOBIAN *out, + const uint8_t *dst, size_t dst_len, + const uint8_t *msg, + size_t msg_len) { + // See section 8.3 of RFC 9380. + if (EC_GROUP_get_curve_name(group) != NID_secp384r1) { + OPENSSL_PUT_ERROR(EC, EC_R_GROUP_MISMATCH); + return 0; + } + + // Z = -12, c2 = sqrt(12) + EC_FELEM Z, c2; + if (!felem_from_u8(group, &Z, 12) || + !ec_felem_from_bytes(group, &c2, kP384Sqrt12, sizeof(kP384Sqrt12))) { + return 0; + } + ec_felem_neg(group, &Z, &Z); + + return encode_to_curve(group, EVP_sha384(), &Z, &c2, /*k=*/192, out, dst, + dst_len, msg, msg_len); +} + +int EC_encode_to_curve_p384_xmd_sha384_sswu(const EC_GROUP *group, + EC_POINT *out, const uint8_t *dst, + size_t dst_len, const uint8_t *msg, + size_t msg_len) { + if (EC_GROUP_cmp(group, out->group, nullptr) != 0) { + OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return ec_encode_to_curve_p384_xmd_sha384_sswu(group, &out->raw, dst, dst_len, + msg, msg_len); +} + int ec_hash_to_scalar_p384_xmd_sha384(const EC_GROUP *group, EC_SCALAR *out, const uint8_t *dst, size_t dst_len, const uint8_t *msg, size_t msg_len) {
diff --git a/crypto/ec/internal.h b/crypto/ec/internal.h index 0e4a5ae..d3ad220 100644 --- a/crypto/ec/internal.h +++ b/crypto/ec/internal.h
@@ -69,6 +69,20 @@ const EC_GROUP *group, EC_JACOBIAN *out, const uint8_t *dst, size_t dst_len, const uint8_t *msg, size_t msg_len); +// ec_encode_to_curve_p256_xmd_sha256_sswu hashes |msg| to a point on |group| +// and writes the result to |out|, implementing the P256_XMD:SHA-256_SSWU_NU_ +// suite from RFC 9380. It returns one on success and zero on error. +OPENSSL_EXPORT int ec_encode_to_curve_p256_xmd_sha256_sswu( + const EC_GROUP *group, EC_JACOBIAN *out, const uint8_t *dst, size_t dst_len, + const uint8_t *msg, size_t msg_len); + +// ec_encode_to_curve_p384_xmd_sha384_sswu hashes |msg| to a point on |group| +// and writes the result to |out|, implementing the P384_XMD:SHA-384_SSWU_NU_ +// suite from RFC 9380. It returns one on success and zero on error. +OPENSSL_EXPORT int ec_encode_to_curve_p384_xmd_sha384_sswu( + const EC_GROUP *group, EC_JACOBIAN *out, const uint8_t *dst, size_t dst_len, + const uint8_t *msg, size_t msg_len); + // ec_hash_to_scalar_p384_xmd_sha384 hashes |msg| to a scalar on |group| // and writes the result to |out|, using the hash_to_field operation from the // P384_XMD:SHA-384_SSWU_RO_ suite from RFC 9380, but generating a value modulo
diff --git a/crypto/fipsmodule/ec/ec_test.cc b/crypto/fipsmodule/ec/ec_test.cc index 2f269fa..1e4e7c7 100644 --- a/crypto/fipsmodule/ec/ec_test.cc +++ b/crypto/fipsmodule/ec/ec_test.cc
@@ -1280,6 +1280,51 @@ "ecb9f0eadc9aeed232dabc53235368c1394c78de05dd96893eefa6" "2b0f4757dc"}, + // See RFC 9380, appendix J.2.1. + {&EC_hash_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_", "", + "eb9fe1b4f4e14e7140803c1d99d0a93cd823d2b024040f9c067a8e" + "ca1f5a2eeac9ad604973527a356f3fa3aeff0e4d83", + "0c21708cff382b7f4643c07b105c2eaec2cead93a917d825601e63" + "c8f21f6abd9abc22c93c2bed6f235954b25048bb1a"}, + {&EC_hash_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_", "abc", + "e02fc1a5f44a7519419dd314e29863f30df55a514da2d655775a81" + "d413003c4d4e7fd59af0826dfaad4200ac6f60abe1", + "01f638d04d98677d65bef99aef1a12a70a4cbb9270ec55248c0453" + "0d8bc1f8f90f8a6a859a7c1f1ddccedf8f96d675f6"}, + {&EC_hash_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_", "abcdef0123456789", + "bdecc1c1d870624965f19505be50459d363c71a699a496ab672f9a" + "5d6b78676400926fbceee6fcd1780fe86e62b2aa89", + "57cf1f99b5ee00f3c201139b3bfe4dd30a653193778d89a0accc5e" + "0f47e46e4e4b85a0595da29c9494c1814acafe183c"}, + {&EC_hash_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_", + "q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqqqqqqqqqqqq", + "03c3a9f401b78c6c36a52f07eeee0ec1289f178adf78448f43a385" + "0e0456f5dd7f7633dd31676d990eda32882ab486c0", + "cc183d0d7bdfd0a3af05f50e16a3f2de4abbc523215bf57c848d5e" + "a662482b8c1f43dc453a93b94a8026db58f3f5d878"}, + {&EC_hash_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_RO_", + "a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", + "7b18d210b1f090ac701f65f606f6ca18fb8d081e3bc6cbd937c560" + "4325f1cdea4c15c10a54ef303aabf2ea58bd9947a4", + "ea857285a33abb516732915c353c75c576bf82ccc96adb63c094dd" + "e580021eddeafd91f8c0bfee6f636528f3d0c47fd2"}, + // See draft-irtf-cfrg-hash-to-curve-07, appendix G.2.1. {hash_to_curve_p384_sha512_draft07, EC_group_p384(), "P384_XMD:SHA-512_SSWU_RO_TESTGEN", "", @@ -1315,6 +1360,96 @@ "37f2913224287b9dfb64742851f760eb14ca115ff9", "1510e764f1be968d661b7aaecb26a6d38c98e5205ca150f0ae426d" "2c3983c68e3a9ffb283c6ae4891d891b5705500475"}, + + // See RFC 9380, appendix J.1.2. + {&EC_encode_to_curve_p256_xmd_sha256_sswu, EC_group_p256(), + "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_", "", + "f871caad25ea3b59c16cf87c1894902f7e7b2c822c3d3f73596c5a" + "ce8ddd14d1", + "87b9ae23335bee057b99bac1e68588b18b5691af476234b8971bc4" + "f011ddc99b"}, + {&EC_encode_to_curve_p256_xmd_sha256_sswu, EC_group_p256(), + "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_", "abc", + "fc3f5d734e8dce41ddac49f47dd2b8a57257522a865c124ed02b92" + "b5237befa4", + "fe4d197ecf5a62645b9690599e1d80e82c500b22ac705a0b421fac" + "7b47157866"}, + {&EC_encode_to_curve_p256_xmd_sha256_sswu, EC_group_p256(), + "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_", "abcdef0123456789", + "f164c6674a02207e414c257ce759d35eddc7f55be6d7f415e2cc17" + "7e5d8faa84", + "3aa274881d30db70485368c0467e97da0e73c18c1d00f34775d012" + "b6fcee7f97"}, + {&EC_encode_to_curve_p256_xmd_sha256_sswu, EC_group_p256(), + "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_", + "q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqqqqqqqqqqqq", + "324532006312be4f162614076460315f7a54a6f85544da773dc659" + "aca0311853", + "8d8197374bcd52de2acfefc8a54fe2c8d8bebd2a39f16be9b710e4" + "b1af6ef883"}, + {&EC_encode_to_curve_p256_xmd_sha256_sswu, EC_group_p256(), + "QUUX-V01-CS02-with-P256_XMD:SHA-256_SSWU_NU_", + "a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", + "5c4bad52f81f39c8e8de1260e9a06d72b8b00a0829a8ea004a610b" + "0691bea5d9", + "c801e7c0782af1f74f24fc385a8555da0582032a3ce038de637ccd" + "cb16f7ef7b"}, + + // See RFC 9380, appendix J.2.2. + {&EC_encode_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_", "", + "de5a893c83061b2d7ce6a0d8b049f0326f2ada4b966dc7e7292725" + "6b033ef61058029a3bfb13c1c7ececd6641881ae20", + "63f46da6139785674da315c1947e06e9a0867f5608cf24724eb379" + "3a1f5b3809ee28eb21a0c64be3be169afc6cdb38ca"}, + {&EC_encode_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_", "abc", + "1f08108b87e703c86c872ab3eb198a19f2b708237ac4be53d7929f" + "b4bd5194583f40d052f32df66afe5249c9915d139b", + "1369dc8d5bf038032336b989994874a2270adadb67a7fcc32f0f88" + "24bc5118613f0ac8de04a1041d90ff8a5ad555f96c"}, + {&EC_encode_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_", "abcdef0123456789", + "4dac31ec8a82ee3c02ba2d7c9fa431f1e59ffe65bf977b948c59e1" + "d813c2d7963c7be81aa6db39e78ff315a10115c0d0", + "845333cdb5702ad5c525e603f302904d6fc84879f0ef2ee2014a6b" + "13edd39131bfd66f7bd7cdc2d9ccf778f0c8892c3f"}, + {&EC_encode_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_", + "q128_qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq" + "qqqqqqqqqqqqqqqqqqqqqqqqq", + "13c1f8c52a492183f7c28e379b0475486718a7e3ac1dfef39283b9" + "ce5fb02b73f70c6c1f3dfe0c286b03e2af1af12d1d", + "57e101887e73e40eab8963324ed16c177d55eb89f804ec9df06801" + "579820420b5546b579008df2145fd770f584a1a54c"}, + {&EC_encode_to_curve_p384_xmd_sha384_sswu, EC_group_p384(), + "QUUX-V01-CS02-with-P384_XMD:SHA-384_SSWU_NU_", + "a512_aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" + "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", + "af129727a4207a8cb9e9dce656d88f79fce25edbcea350499d65e9" + "bf1204537bdde73c7cefb752a6ed5ebcd44e183302", + "ce68a3d5e161b2e6a968e4ddaa9e51504ad1516ec170c7eef3ca6b" + "5327943eca95d90b23b009ba45f58b72906f2a99e2"}, }; for (const auto &test : kTests) {
diff --git a/include/openssl/ec.h b/include/openssl/ec.h index 29dc86a..4b60f3b 100644 --- a/include/openssl/ec.h +++ b/include/openssl/ec.h
@@ -16,7 +16,7 @@ #ifndef OPENSSL_HEADER_EC_H #define OPENSSL_HEADER_EC_H -#include <openssl/base.h> // IWYU pragma: export +#include <openssl/base.h> // IWYU pragma: export #if defined(__cplusplus) extern "C" { @@ -312,6 +312,30 @@ const EC_GROUP *group, EC_POINT *out, const uint8_t *dst, size_t dst_len, const uint8_t *msg, size_t msg_len); +// EC_encode_to_curve_p256_xmd_sha256_sswu hashes |msg| to a point on |group| +// and writes the result to |out|, implementing the P256_XMD:SHA-256_SSWU_NU_ +// suite from RFC 9380. It returns one on success and zero on error. +// +// This is a nonuniform encoding from byte strings to points in |group|. That +// is, the set of possible outputs is only a fraction of the points in |group|, +// and some points in this set are more likely to be output than others. See +// also RFC 9380, section 10.4 +OPENSSL_EXPORT int EC_encode_to_curve_p256_xmd_sha256_sswu( + const EC_GROUP *group, EC_POINT *out, const uint8_t *dst, size_t dst_len, + const uint8_t *msg, size_t msg_len); + +// EC_encode_to_curve_p384_xmd_sha384_sswu hashes |msg| to a point on |group| +// and writes the result to |out|, implementing the P384_XMD:SHA-384_SSWU_NU_ +// suite from RFC 9380. It returns one on success and zero on error. +// +// This is a nonuniform encoding from byte strings to points in |group|. That +// is, the set of possible outputs is only a fraction of the points in |group|, +// and some points in this set are more likely to be output than others. See +// also RFC 9380, section 10.4 +OPENSSL_EXPORT int EC_encode_to_curve_p384_xmd_sha384_sswu( + const EC_GROUP *group, EC_POINT *out, const uint8_t *dst, size_t dst_len, + const uint8_t *msg, size_t msg_len); + // Deprecated functions.