Include the public key in ML-DSA private keys
I went back and forth on this a bit, but I think this is the right
model. go/mldsa-mlkem-evp (internal) has some notes on the trade-offs
here.
Bug: 449751916
Change-Id: I8ba46107c5a3c0b0260538705bd2b20f28c1fb0c
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/82991
Reviewed-by: Lily Chen <chlily@google.com>
Reviewed-by: Adam Langley <agl@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
diff --git a/crypto/fipsmodule/mldsa/mldsa.cc.inc b/crypto/fipsmodule/mldsa/mldsa.cc.inc
index 9412b9c..2f14141 100644
--- a/crypto/fipsmodule/mldsa/mldsa.cc.inc
+++ b/crypto/fipsmodule/mldsa/mldsa.cc.inc
@@ -1436,9 +1436,8 @@
template <int K, int L>
struct private_key {
- uint8_t rho[kRhoBytes];
+ public_key<K> pub;
uint8_t k[kKBytes];
- uint8_t public_key_hash[kTrBytes];
vector<L> s1;
vector<K> s2;
vector<K> t0;
@@ -1492,10 +1491,10 @@
// FIPS 204, Algorithm 24 (`skEncode`).
template <int K, int L>
int mldsa_marshal_private_key(CBB *out, const private_key<K, L> *priv) {
- if (!CBB_add_bytes(out, priv->rho, sizeof(priv->rho)) ||
+ if (!CBB_add_bytes(out, priv->pub.rho, sizeof(priv->pub.rho)) ||
!CBB_add_bytes(out, priv->k, sizeof(priv->k)) ||
- !CBB_add_bytes(out, priv->public_key_hash,
- sizeof(priv->public_key_hash))) {
+ !CBB_add_bytes(out, priv->pub.public_key_hash,
+ sizeof(priv->pub.public_key_hash))) {
return 0;
}
@@ -1524,18 +1523,16 @@
return 1;
}
-// FIPS 204, Algorithm 25 (`skDecode`).
+// FIPS 204, Algorithm 25 (`skDecode`). This is only used for testing. The
+// supported external way to construct ML-DSA keys is to use the input seed.
template <int K, int L>
int mldsa_parse_private_key(private_key<K, L> *priv, CBS *in) {
- CBS s1_bytes;
- CBS s2_bytes;
- CBS t0_bytes;
+ CBS public_key_hash, s1_bytes, s2_bytes, t0_bytes;
constexpr size_t scalar_bytes =
(kDegree * plus_minus_eta_bitlen<K>() + 7) / 8;
- if (!CBS_copy_bytes(in, priv->rho, sizeof(priv->rho)) ||
+ if (!CBS_copy_bytes(in, priv->pub.rho, sizeof(priv->pub.rho)) ||
!CBS_copy_bytes(in, priv->k, sizeof(priv->k)) ||
- !CBS_copy_bytes(in, priv->public_key_hash,
- sizeof(priv->public_key_hash)) ||
+ !CBS_get_bytes(in, &public_key_hash, kTrBytes) ||
!CBS_get_bytes(in, &s1_bytes, scalar_bytes * L) ||
!vector_decode_signed(&priv->s1, CBS_data(&s1_bytes),
plus_minus_eta_bitlen<K>(), eta<K>()) ||
@@ -1548,6 +1545,22 @@
return 0;
}
+ // Compute `t1`, which is not in the `skDecode` input.
+ uint8_t unused[public_key_bytes<K>()];
+ if (!mldsa_finish_keygen(unused, priv)) {
+ return 0;
+ }
+
+ // As a side effect of computing `t1`, we also compute `t0` and
+ // `public_key_hash`. Check they match the received bytes.
+ uint8_t t0_computed[416 * K];
+ vector_encode_signed(t0_computed, &priv->t0, 13, 1 << 12);
+ if (!CBS_mem_equal(&public_key_hash, priv->pub.public_key_hash,
+ sizeof(priv->pub.public_key_hash)) ||
+ !CBS_mem_equal(&t0_bytes, t0_computed, sizeof(t0_computed))) {
+ return 0;
+ }
+
return 1;
}
@@ -1592,17 +1605,15 @@
return 1;
}
-// FIPS 204, Algorithm 6 (`ML-DSA.KeyGen_internal`). Returns 1 on success and 0
-// on failure.
+// FIPS 204, Algorithm 6 (`ML-DSA.KeyGen_internal`), steps 3 and 5–11.
+// Returns 1 on success and 0 on failure.
template <int K, int L>
-int mldsa_generate_key_external_entropy_no_self_test(
- uint8_t out_encoded_public_key[public_key_bytes<K>()],
- private_key<K, L> *priv, const uint8_t entropy[MLDSA_SEED_BYTES]) {
+int mldsa_finish_keygen(uint8_t out_encoded_public_key[public_key_bytes<K>()],
+ private_key<K, L> *priv) {
// Intermediate values, allocated on the heap to allow use when there is a
// limited amount of stack.
struct Values {
enum { kAllowUniquePtr = true };
- public_key<K> pub;
matrix<K, L> a_ntt;
vector<L> s1_ntt;
vector<K> t;
@@ -1612,6 +1623,46 @@
return 0;
}
+ // Step 3.
+ matrix_expand(&values->a_ntt, priv->pub.rho);
+
+ // Step 5.
+ OPENSSL_memcpy(&values->s1_ntt, &priv->s1, sizeof(values->s1_ntt));
+ vector_ntt(&values->s1_ntt);
+
+ matrix_mult(&values->t, &values->a_ntt, &values->s1_ntt);
+ vector_inverse_ntt(&values->t);
+ vector_add(&values->t, &values->t, &priv->s2);
+
+ // Step 6-7.
+ vector_power2_round(&priv->pub.t1, &priv->t0, &values->t);
+ // t1 is public.
+ CONSTTIME_DECLASSIFY(&priv->pub.t1, sizeof(priv->pub.t1));
+
+ // Step 8.
+ CBB cbb;
+ CBB_init_fixed(&cbb, out_encoded_public_key, public_key_bytes<K>());
+ if (!mldsa_marshal_public_key(&cbb, &priv->pub)) {
+ return 0;
+ }
+ assert(CBB_len(&cbb) == public_key_bytes<K>());
+
+ // Step 9-11.
+ BORINGSSL_keccak(priv->pub.public_key_hash, sizeof(priv->pub.public_key_hash),
+ out_encoded_public_key, public_key_bytes<K>(),
+ boringssl_shake256);
+
+ return 1;
+}
+
+// FIPS 204, Algorithm 6 (`ML-DSA.KeyGen_internal`). Returns 1 on success and 0
+// on failure.
+template <int K, int L>
+int mldsa_generate_key_external_entropy_no_self_test(
+ uint8_t out_encoded_public_key[public_key_bytes<K>()],
+ private_key<K, L> *priv,
+ const uint8_t entropy[MLDSA_SEED_BYTES]) {
+ // Step 1-2.
uint8_t augmented_entropy[MLDSA_SEED_BYTES + 2];
OPENSSL_memcpy(augmented_entropy, entropy, MLDSA_SEED_BYTES);
// The k and l parameters are appended to the seed.
@@ -1625,36 +1676,12 @@
const uint8_t *const k = expanded_seed + kRhoBytes + kSigmaBytes;
// rho is public.
CONSTTIME_DECLASSIFY(rho, kRhoBytes);
- OPENSSL_memcpy(values->pub.rho, rho, sizeof(values->pub.rho));
- OPENSSL_memcpy(priv->rho, rho, sizeof(priv->rho));
+ OPENSSL_memcpy(priv->pub.rho, rho, sizeof(priv->pub.rho));
OPENSSL_memcpy(priv->k, k, sizeof(priv->k));
-
- matrix_expand(&values->a_ntt, rho);
+ // Step 4. This is independent of A (step 3) and can be done first.
vector_expand_short(&priv->s1, &priv->s2, sigma);
-
- OPENSSL_memcpy(&values->s1_ntt, &priv->s1, sizeof(values->s1_ntt));
- vector_ntt(&values->s1_ntt);
-
- matrix_mult(&values->t, &values->a_ntt, &values->s1_ntt);
- vector_inverse_ntt(&values->t);
- vector_add(&values->t, &values->t, &priv->s2);
-
- vector_power2_round(&values->pub.t1, &priv->t0, &values->t);
- // t1 is public.
- CONSTTIME_DECLASSIFY(&values->pub.t1, sizeof(values->pub.t1));
-
- CBB cbb;
- CBB_init_fixed(&cbb, out_encoded_public_key, public_key_bytes<K>());
- if (!mldsa_marshal_public_key(&cbb, &values->pub)) {
- return 0;
- }
- assert(CBB_len(&cbb) == public_key_bytes<K>());
-
- BORINGSSL_keccak(priv->public_key_hash, sizeof(priv->public_key_hash),
- out_encoded_public_key, public_key_bytes<K>(),
- boringssl_shake256);
-
- return 1;
+ // Steps 3 and 5-11.
+ return mldsa_finish_keygen(out_encoded_public_key, priv);
}
template <int K, int L>
@@ -1666,42 +1693,6 @@
out_encoded_public_key, priv, entropy);
}
-template <int K, int L>
-int mldsa_public_from_private(public_key<K> *pub,
- const private_key<K, L> *priv) {
- // Intermediate values, allocated on the heap to allow use when there is a
- // limited amount of stack.
- struct Values {
- enum { kAllowUniquePtr = true };
- matrix<K, L> a_ntt;
- vector<L> s1_ntt;
- vector<K> t;
- vector<K> t0;
- };
- auto values = bssl::MakeUnique<Values>();
- if (values == nullptr) {
- return 0;
- }
-
- OPENSSL_memcpy(pub->rho, priv->rho, sizeof(pub->rho));
- OPENSSL_memcpy(pub->public_key_hash, priv->public_key_hash,
- sizeof(pub->public_key_hash));
-
- matrix_expand(&values->a_ntt, priv->rho);
-
- OPENSSL_memcpy(&values->s1_ntt, &priv->s1, sizeof(values->s1_ntt));
- vector_ntt(&values->s1_ntt);
-
- matrix_mult(&values->t, &values->a_ntt, &values->s1_ntt);
- vector_inverse_ntt(&values->t);
- vector_add(&values->t, &values->t, &priv->s2);
-
- vector_power2_round(&pub->t1, &values->t0, &values->t);
- // t1 is part of the public key and thus is public.
- CONSTTIME_DECLASSIFY(&pub->t1, sizeof(pub->t1));
- return 1;
-}
-
// FIPS 204, Algorithm 7 (`ML-DSA.Sign_internal`), using a pre-computed mu.
// Returns 1 on success and 0 on failure.
template <int K, int L>
@@ -1746,7 +1737,7 @@
OPENSSL_memcpy(&values->t0_ntt, &priv->t0, sizeof(values->t0_ntt));
vector_ntt(&values->t0_ntt);
- matrix_expand(&values->a_ntt, priv->rho);
+ matrix_expand(&values->a_ntt, priv->pub.rho);
// kappa must not exceed 2**16/L = 13107. But the probability of it
// exceeding even 1000 iterations is vanishingly small.
@@ -1854,8 +1845,8 @@
uint8_t mu[kMuBytes];
BORINGSSL_keccak_st keccak_ctx;
BORINGSSL_keccak_init(&keccak_ctx, boringssl_shake256);
- BORINGSSL_keccak_absorb(&keccak_ctx, priv->public_key_hash,
- sizeof(priv->public_key_hash));
+ BORINGSSL_keccak_absorb(&keccak_ctx, priv->pub.public_key_hash,
+ sizeof(priv->pub.public_key_hash));
BORINGSSL_keccak_absorb(&keccak_ctx, context_prefix, context_prefix_len);
BORINGSSL_keccak_absorb(&keccak_ctx, context, context_len);
BORINGSSL_keccak_absorb(&keccak_ctx, msg, msg_len);
@@ -2082,25 +2073,32 @@
#include "fips_known_values.inc"
static int keygen_self_test() {
- private_key<6, 5> priv;
- uint8_t pub_bytes[MLDSA65_PUBLIC_KEY_BYTES];
- if (!mldsa_generate_key_external_entropy_no_self_test(pub_bytes, &priv,
- kGenerateKeyEntropy)) {
+ struct Values {
+ enum { kAllowUniquePtr = true };
+ private_key<6, 5> priv;
+ uint8_t pub_bytes[MLDSA65_PUBLIC_KEY_BYTES];
+ uint8_t priv_bytes[BCM_MLDSA65_PRIVATE_KEY_BYTES];
+ };
+ auto values = bssl::MakeUnique<Values>();
+ if (values == nullptr ||
+ !mldsa_generate_key_external_entropy_no_self_test(
+ values->pub_bytes, &values->priv, kGenerateKeyEntropy)) {
return 0;
}
- uint8_t priv_bytes[BCM_MLDSA65_PRIVATE_KEY_BYTES];
CBB cbb;
- CBB_init_fixed(&cbb, priv_bytes, sizeof(priv_bytes));
- if (!mldsa_marshal_private_key(&cbb, &priv)) {
+ CBB_init_fixed(&cbb, values->priv_bytes, sizeof(values->priv_bytes));
+ if (!mldsa_marshal_private_key(&cbb, &values->priv)) {
return 0;
}
- static_assert(sizeof(pub_bytes) == sizeof(kExpectedPublicKey));
- static_assert(sizeof(priv_bytes) == sizeof(kExpectedPrivateKey));
- if (!BORINGSSL_check_test(kExpectedPublicKey, pub_bytes, sizeof(pub_bytes),
+ static_assert(sizeof(values->pub_bytes) == sizeof(kExpectedPublicKey));
+ static_assert(sizeof(values->priv_bytes) == sizeof(kExpectedPrivateKey));
+ if (!BORINGSSL_check_test(kExpectedPublicKey, values->pub_bytes,
+ sizeof(values->pub_bytes),
"ML-DSA keygen public key") ||
- !BORINGSSL_check_test(kExpectedPrivateKey, priv_bytes, sizeof(priv_bytes),
+ !BORINGSSL_check_test(kExpectedPrivateKey, values->priv_bytes,
+ sizeof(values->priv_bytes),
"ML-DSA keygen private key")) {
return 0;
}
@@ -2109,36 +2107,44 @@
}
static int sign_self_test() {
- private_key<6, 5> priv;
- uint8_t pub_bytes[MLDSA65_PUBLIC_KEY_BYTES];
- if (!mldsa_generate_key_external_entropy(pub_bytes, &priv, kSignEntropy)) {
+ struct Values {
+ enum { kAllowUniquePtr = true };
+ private_key<6, 5> priv;
+ uint8_t pub_bytes[MLDSA65_PUBLIC_KEY_BYTES];
+ uint8_t sig[MLDSA65_SIGNATURE_BYTES];
+ };
+ auto values = bssl::MakeUnique<Values>();
+ if (values == nullptr ||
+ !mldsa_generate_key_external_entropy(values->pub_bytes, &values->priv,
+ kSignEntropy)) {
return 0;
}
const uint8_t randomizer[BCM_MLDSA_SIGNATURE_RANDOMIZER_BYTES] = {};
- uint8_t sig[MLDSA65_SIGNATURE_BYTES];
// This message triggers the first restart case for signing.
uint8_t message[4] = {0};
- if (!mldsa_sign_internal_no_self_test(sig, &priv, message, sizeof(message),
- nullptr, 0, nullptr, 0, randomizer)) {
+ if (!mldsa_sign_internal_no_self_test(values->sig, &values->priv, message,
+ sizeof(message), nullptr, 0, nullptr, 0,
+ randomizer)) {
return 0;
}
- static_assert(sizeof(kExpectedCase1Signature) == sizeof(sig));
- if (!BORINGSSL_check_test(kExpectedCase1Signature, sig, sizeof(sig),
- "ML-DSA sign case 1")) {
+ static_assert(sizeof(kExpectedCase1Signature) == sizeof(values->sig));
+ if (!BORINGSSL_check_test(kExpectedCase1Signature, values->sig,
+ sizeof(values->sig), "ML-DSA sign case 1")) {
return 0;
}
// This message triggers the second restart case for signing.
message[0] = 123;
- if (!mldsa_sign_internal_no_self_test(sig, &priv, message, sizeof(message),
- nullptr, 0, nullptr, 0, randomizer)) {
+ if (!mldsa_sign_internal_no_self_test(values->sig, &values->priv, message,
+ sizeof(message), nullptr, 0, nullptr, 0,
+ randomizer)) {
return 0;
}
- static_assert(sizeof(kExpectedCase2Signature) == sizeof(sig));
- if (!BORINGSSL_check_test(kExpectedCase2Signature, sig, sizeof(sig),
- "ML-DSA sign case 2")) {
+ static_assert(sizeof(kExpectedCase2Signature) == sizeof(values->sig));
+ if (!BORINGSSL_check_test(kExpectedCase2Signature, values->sig,
+ sizeof(values->sig), "ML-DSA sign case 2")) {
return 0;
}
@@ -2149,7 +2155,6 @@
struct Values {
enum { kAllowUniquePtr = true };
private_key<6, 5> priv;
- public_key<6> pub;
uint8_t pub_bytes[MLDSA65_PUBLIC_KEY_BYTES];
};
auto values = bssl::MakeUnique<Values>();
@@ -2163,9 +2168,8 @@
}
const uint8_t message[4] = {1, 0};
- if (!mldsa_public_from_private(&values->pub, &values->priv) ||
- !mldsa_verify_internal_no_self_test<6, 5>(
- &values->pub, kExpectedVerifySignature, message, sizeof(message),
+ if (!mldsa_verify_internal_no_self_test<6, 5>(
+ &values->priv.pub, kExpectedVerifySignature, message, sizeof(message),
nullptr, 0, nullptr, 0)) {
return 0;
}
@@ -2174,12 +2178,10 @@
}
template <int K, int L>
-int check_key(private_key<K, L> *priv) {
+int check_key(const private_key<K, L> *priv) {
uint8_t sig[signature_bytes<K>()];
uint8_t randomizer[BCM_MLDSA_SIGNATURE_RANDOMIZER_BYTES] = {};
- mldsa::public_key<K> pub;
- if (!mldsa_public_from_private(&pub, priv) ||
- !mldsa_sign_internal_no_self_test(sig, priv, nullptr, 0, nullptr, 0,
+ if (!mldsa_sign_internal_no_self_test(sig, priv, nullptr, 0, nullptr, 0,
nullptr, 0, randomizer)) {
return 0;
}
@@ -2188,8 +2190,8 @@
sig[0] ^= 1;
}
- if (!mldsa_verify_internal_no_self_test<K, L>(&pub, sig, nullptr, 0, nullptr,
- 0, nullptr, 0)) {
+ if (!mldsa_verify_internal_no_self_test<K, L>(&priv->pub, sig, nullptr, 0,
+ nullptr, 0, nullptr, 0)) {
return 0;
}
return 1;
@@ -2338,9 +2340,10 @@
bcm_status BCM_mldsa65_public_from_private(
MLDSA65_public_key *out_public_key,
const MLDSA65_private_key *private_key) {
- return bcm_as_approved_status(mldsa_public_from_private(
- mldsa::public_key_from_external_65(out_public_key),
- mldsa::private_key_from_external_65(private_key)));
+ const auto *priv = mldsa::private_key_from_external_65(private_key);
+ auto *out_pub = mldsa::public_key_from_external_65(out_public_key);
+ *out_pub = priv->pub;
+ return bcm_status::approved;
}
bcm_status BCM_mldsa65_sign_internal(
@@ -2538,9 +2541,10 @@
bcm_status BCM_mldsa87_public_from_private(
MLDSA87_public_key *out_public_key,
const MLDSA87_private_key *private_key) {
- return bcm_as_approved_status(mldsa_public_from_private(
- mldsa::public_key_from_external_87(out_public_key),
- mldsa::private_key_from_external_87(private_key)));
+ const auto *priv = mldsa::private_key_from_external_87(private_key);
+ auto *out_pub = mldsa::public_key_from_external_87(out_public_key);
+ *out_pub = priv->pub;
+ return bcm_status::approved;
}
bcm_status BCM_mldsa87_sign_internal(
@@ -2737,9 +2741,10 @@
bcm_status BCM_mldsa44_public_from_private(
MLDSA44_public_key *out_public_key,
const MLDSA44_private_key *private_key) {
- return bcm_as_approved_status(mldsa_public_from_private(
- mldsa::public_key_from_external_44(out_public_key),
- mldsa::private_key_from_external_44(private_key)));
+ const auto *priv = mldsa::private_key_from_external_44(private_key);
+ auto *out_pub = mldsa::public_key_from_external_44(out_public_key);
+ *out_pub = priv->pub;
+ return bcm_status::approved;
}
bcm_status BCM_mldsa44_sign_internal(
diff --git a/include/openssl/mldsa.h b/include/openssl/mldsa.h
index decb5b3..d15ad3c 100644
--- a/include/openssl/mldsa.h
+++ b/include/openssl/mldsa.h
@@ -41,7 +41,7 @@
// object should never leave the address space since the format is unstable.
struct MLDSA65_private_key {
union {
- uint8_t bytes[32 + 32 + 64 + 256 * 4 * (5 + 6 + 6)];
+ uint8_t bytes[(32 + 64 + 256 * 4 * 6) + 32 + 256 * 4 * (5 + 6 + 6)];
uint32_t alignment;
} opaque;
};
@@ -180,7 +180,7 @@
// object should never leave the address space since the format is unstable.
struct MLDSA87_private_key {
union {
- uint8_t bytes[32 + 32 + 64 + 256 * 4 * (7 + 8 + 8)];
+ uint8_t bytes[(32 + 64 + 256 * 4 * 8) + 32 + 256 * 4 * (7 + 8 + 8)];
uint32_t alignment;
} opaque;
};
@@ -316,7 +316,7 @@
// object should never leave the address space since the format is unstable.
struct MLDSA44_private_key {
union {
- uint8_t bytes[32 + 32 + 64 + 256 * 4 * (4 + 4 + 4)];
+ uint8_t bytes[(32 + 64 + 256 * 4 * 4) + 32 + 256 * 4 * (4 + 4 + 4)];
uint32_t alignment;
} opaque;
};
