11345717360

Committed 15 Oct 2024 12:09PM UTC coverage: 91.512% (+0.4%) from 91.131%

Build # 11345717360

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #4270 from Rohde-Schwarz/feature/ml-dsa-ipd-after-refactoring

PQC: ML-DSA

Run Details

73266 of 80062 relevant lines covered (91.51%)

11223399.72 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.76

/src/lib/pubkey/dilithium/dilithium_common/dilithium.cpp

/*
* Crystals Dilithium Digital Signature Algorithms
* Based on the public domain reference implementation by the
* designers (https://github.com/pq-crystals/dilithium)
*
* Further changes
* (C) 2021-2023 Jack Lloyd
* (C) 2021-2022 Manuel Glaser - Rohde & Schwarz Cybersecurity
* (C) 2021-2023 Michael Boric, René Meusel - Rohde & Schwarz Cybersecurity
* (C) 2024      René Meusel - Rohde & Schwarz Cybersecurity
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/dilithium.h>

#include <botan/exceptn.h>
#include <botan/rng.h>

#include <botan/internal/dilithium_algos.h>
#include <botan/internal/dilithium_keys.h>
#include <botan/internal/dilithium_symmetric_primitives.h>
#include <botan/internal/dilithium_types.h>
#include <botan/internal/fmt.h>
#include <botan/internal/pk_ops_impl.h>
#include <botan/internal/stl_util.h>

namespace Botan {
namespace {

DilithiumMode::Mode dilithium_mode_from_string(std::string_view str) {
   if(str == "Dilithium-4x4-r3") {
      return DilithiumMode::Dilithium4x4;
   }
   if(str == "Dilithium-4x4-AES-r3") {
      return DilithiumMode::Dilithium4x4_AES;
   }
   if(str == "Dilithium-6x5-r3") {
      return DilithiumMode::Dilithium6x5;
   }
   if(str == "Dilithium-6x5-AES-r3") {
      return DilithiumMode::Dilithium6x5_AES;
   }
   if(str == "Dilithium-8x7-r3") {
      return DilithiumMode::Dilithium8x7;
   }
   if(str == "Dilithium-8x7-AES-r3") {
      return DilithiumMode::Dilithium8x7_AES;
   }
   if(str == "ML-DSA-4x4") {
      return DilithiumMode::ML_DSA_4x4;
   }
   if(str == "ML-DSA-6x5") {
      return DilithiumMode::ML_DSA_6x5;
   }
   if(str == "ML-DSA-8x7") {
      return DilithiumMode::ML_DSA_8x7;
   }

   throw Invalid_Argument(fmt("'{}' is not a valid Dilithium mode name", str));
}

}  // namespace

DilithiumMode::DilithiumMode(const OID& oid) : m_mode(dilithium_mode_from_string(oid.to_formatted_string())) {}

DilithiumMode::DilithiumMode(std::string_view str) : m_mode(dilithium_mode_from_string(str)) {}

OID DilithiumMode::object_identifier() const {
   return OID::from_string(to_string());
}

std::string DilithiumMode::to_string() const {
   switch(m_mode) {
      case DilithiumMode::Dilithium4x4:
         return "Dilithium-4x4-r3";
      case DilithiumMode::Dilithium4x4_AES:
         return "Dilithium-4x4-AES-r3";
      case DilithiumMode::Dilithium6x5:
         return "Dilithium-6x5-r3";
      case DilithiumMode::Dilithium6x5_AES:
         return "Dilithium-6x5-AES-r3";
      case DilithiumMode::Dilithium8x7:
         return "Dilithium-8x7-r3";
      case DilithiumMode::Dilithium8x7_AES:
         return "Dilithium-8x7-AES-r3";
      case DilithiumMode::ML_DSA_4x4:
         return "ML-DSA-4x4";
      case DilithiumMode::ML_DSA_6x5:
         return "ML-DSA-6x5";
      case DilithiumMode::ML_DSA_8x7:
         return "ML-DSA-8x7";
   }

   BOTAN_ASSERT_UNREACHABLE();
}

bool DilithiumMode::is_aes() const {
   return m_mode == Dilithium4x4_AES || m_mode == Dilithium6x5_AES || m_mode == Dilithium8x7_AES;
}

bool DilithiumMode::is_modern() const {
   return !is_aes();
}

bool DilithiumMode::is_ml_dsa() const {
   return m_mode == ML_DSA_4x4 || m_mode == ML_DSA_6x5 || m_mode == ML_DSA_8x7;
}

bool DilithiumMode::is_available() const {
#if defined(BOTAN_HAS_DILITHIUM_AES)
   if(is_dilithium_round3() && is_aes()) {
      return true;
   }
#endif
#if defined(BOTAN_HAS_DILITHIUM)
   if(is_dilithium_round3() && is_modern()) {
      return true;
   }
#endif
#if defined(BOTAN_HAS_ML_DSA)
   if(is_ml_dsa()) {
      return true;
   }
#endif
   return false;
}

class Dilithium_Signature_Operation final : public PK_Ops::Signature {
   public:
      Dilithium_Signature_Operation(DilithiumInternalKeypair keypair, bool randomized) :
            m_keypair(std::move(keypair)),
            m_randomized(randomized),
            m_h(m_keypair.second->mode().symmetric_primitives().get_message_hash(m_keypair.first->tr())),
            m_s1(ntt(m_keypair.second->s1().clone())),
            m_s2(ntt(m_keypair.second->s2().clone())),
            m_t0(ntt(m_keypair.second->t0().clone())),
            m_A(Dilithium_Algos::expand_A(m_keypair.first->rho(), m_keypair.second->mode())) {}

      void update(std::span<const uint8_t> input) override { m_h->update(input); }

      /**
       * NIST FIPS 204, Algorithm 2 (ML-DSA.Sign) and Algorithm 7 (ML-DSA.Sign_internal)
       *
       * Note that the private key decoding is done ahead of time. Also, the
       * matrix expansion of A from 'rho' along with the NTT-transforms of s1,
       * s2 and t0 are done in the constructor of this class, as a 'signature
       * operation' may be used to sign multiple messages.
       *
       * TODO: Implement support for the specified 'ctx' context string which is
       *       application defined and "empty" by default and <= 255 bytes long.
       */
      std::vector<uint8_t> sign(RandomNumberGenerator& rng) override {
         auto scope = CT::scoped_poison(*m_keypair.second);

         const auto mu = m_h->final();
         const auto& mode = m_keypair.second->mode();
         const auto& sympri = mode.symmetric_primitives();

         const auto rhoprime = sympri.H_maybe_randomized(m_keypair.second->signing_seed(), mu, maybe(rng));
         CT::poison(rhoprime);

         for(uint16_t nonce = 0, n = 0; n <= DilithiumConstants::SIGNING_LOOP_BOUND; ++n, nonce += mode.l()) {
            const auto y = Dilithium_Algos::expand_mask(rhoprime, nonce, mode);

            auto w_ntt = m_A * ntt(y.clone());
            w_ntt.reduce();
            auto w = inverse_ntt(std::move(w_ntt));
            w.conditional_add_q();

            auto [w1, w0] = Dilithium_Algos::decompose(w, mode);
            const auto ch = CT::driveby_unpoison(sympri.H(mu, Dilithium_Algos::encode_commitment(w1, mode)));

            const auto c = ntt(Dilithium_Algos::sample_in_ball(ch, mode));
            const auto cs1 = inverse_ntt(c * m_s1);
            auto z = y + cs1;
            z.reduce();

            // We validate the infinity norm of z before proceeding to calculate cs2
            if(!Dilithium_Algos::infinity_norm_within_bound(z, to_underlying(mode.gamma1()) - mode.beta())) {
               continue;
            }
            CT::unpoison(z);  // part of the signature

            const auto cs2 = inverse_ntt(c * m_s2);

            // Note: w0 is used as a scratch space for calculation. We're aliasing
            //       the results to const&'s merely to communicate which value the
            //       intermediate results represent in the specification.
            w0 -= cs2;
            w0.reduce();
            const auto& r0 = w0;
            if(!Dilithium_Algos::infinity_norm_within_bound(r0, to_underlying(mode.gamma2()) - mode.beta())) {
               continue;
            }

            auto ct0 = inverse_ntt(c * m_t0);
            ct0.reduce();
            // We validate the infinity norm of ct0 before proceeding to calculate the hint.
            if(!Dilithium_Algos::infinity_norm_within_bound(ct0, mode.gamma2())) {
               continue;
            }

            w0 += ct0;
            w0.conditional_add_q();
            const auto& w0cs2ct0 = w0;

            const auto hint = Dilithium_Algos::make_hint(w0cs2ct0, w1, mode);
            if(CT::driveby_unpoison(hint.hamming_weight()) > mode.omega()) {
               continue;
            }
            CT::unpoison(hint);  // part of the signature

            return Dilithium_Algos::encode_signature(ch, z, hint, mode).get();
         }

         throw Internal_Error("ML-DSA/Dilithium signature loop did not terminate");
      }

      size_t signature_length() const override { return m_keypair.second->mode().signature_bytes(); }

      AlgorithmIdentifier algorithm_identifier() const override {
         return AlgorithmIdentifier(m_keypair.second->mode().mode().object_identifier(),
                                    AlgorithmIdentifier::USE_EMPTY_PARAM);
      }

      std::string hash_function() const override { return m_h->name(); }

   private:
      std::optional<std::reference_wrapper<RandomNumberGenerator>> maybe(RandomNumberGenerator& rng) const {
         if(m_randomized) {
            return rng;
         } else {
            return std::nullopt;
         }
      }

   private:
      DilithiumInternalKeypair m_keypair;
      bool m_randomized;
      std::unique_ptr<DilithiumMessageHash> m_h;

      const DilithiumPolyVecNTT m_s1;
      const DilithiumPolyVecNTT m_s2;
      const DilithiumPolyVecNTT m_t0;
      const DilithiumPolyMatNTT m_A;
};

class Dilithium_Verification_Operation final : public PK_Ops::Verification {
   public:
      Dilithium_Verification_Operation(std::shared_ptr<Dilithium_PublicKeyInternal> pubkey) :
            m_pub_key(std::move(pubkey)),
            m_A(Dilithium_Algos::expand_A(m_pub_key->rho(), m_pub_key->mode())),
            m_t1_ntt_shifted(ntt(m_pub_key->t1() << DilithiumConstants::D)),
            m_h(m_pub_key->mode().symmetric_primitives().get_message_hash(m_pub_key->tr())) {}

      void update(std::span<const uint8_t> input) override { m_h->update(input); }

      /**
       * NIST FIPS 204, Algorithm 3 (ML-DSA.Verify) and 8 (ML-DSA.Verify_internal)
       *
       * Note that the public key decoding is done ahead of time. Also, the
       * matrix A is expanded from 'rho' in the constructor of this class, as
       * a 'verification operation' may be used to verify multiple signatures.
       *
       * TODO: Implement support for the specified 'ctx' context string which is
       *       application defined and "empty" by default and <= 255 bytes long.
       */
      bool is_valid_signature(std::span<const uint8_t> sig) override {
         const auto& mode = m_pub_key->mode();
         const auto& sympri = mode.symmetric_primitives();
         StrongSpan<const DilithiumSerializedSignature> sig_bytes(sig);

         if(sig_bytes.size() != mode.signature_bytes()) {
            return false;
         }

         const auto mu = m_h->final();

         auto signature = Dilithium_Algos::decode_signature(sig_bytes, mode);
         if(!signature.has_value()) {
            return false;
         }
         auto [ch, z, h] = std::move(signature.value());

         // TODO: The first check was removed from the final version of ML-DSA
         if(h.hamming_weight() > mode.omega() ||
            !Dilithium_Algos::infinity_norm_within_bound(z, to_underlying(mode.gamma1()) - mode.beta())) {
            return false;
         }

         const auto c_hat = ntt(Dilithium_Algos::sample_in_ball(ch, mode));
         auto w_approx = m_A * ntt(std::move(z));
         w_approx -= c_hat * m_t1_ntt_shifted;
         w_approx.reduce();
         auto w1 = inverse_ntt(std::move(w_approx));
         w1.conditional_add_q();
         Dilithium_Algos::use_hint(w1, h, mode);

         const auto chprime = sympri.H(mu, Dilithium_Algos::encode_commitment(w1, mode));

         BOTAN_ASSERT_NOMSG(ch.size() == chprime.size());
         return std::equal(ch.begin(), ch.end(), chprime.begin());
      }

      std::string hash_function() const override { return m_h->name(); }

   private:
      std::shared_ptr<Dilithium_PublicKeyInternal> m_pub_key;
      DilithiumPolyMatNTT m_A;
      DilithiumPolyVecNTT m_t1_ntt_shifted;
      std::unique_ptr<DilithiumMessageHash> m_h;
};

Dilithium_PublicKey::Dilithium_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> pk) :
      Dilithium_PublicKey(pk, DilithiumMode(alg_id.oid())) {}

Dilithium_PublicKey::Dilithium_PublicKey(std::span<const uint8_t> pk, DilithiumMode m) {
   DilithiumConstants mode(m);
   BOTAN_ARG_CHECK(mode.mode().is_available(), "Dilithium/ML-DSA mode is not available in this build");
   BOTAN_ARG_CHECK(pk.empty() || pk.size() == mode.public_key_bytes(),
                   "dilithium public key does not have the correct byte count");

   m_public = Dilithium_PublicKeyInternal::decode(std::move(mode), StrongSpan<const DilithiumSerializedPublicKey>(pk));
}

std::string Dilithium_PublicKey::algo_name() const {
   // Note: For Dilithium we made the blunder to return the OID's human readable
   //       name, e.g. "Dilithium-4x4-AES". This is inconsistent with the other
   //       public key algorithms which return the generic name only.
   //
   // TODO(Botan4): Fix the inconsistency described above, also considering that
   //               there might be other code locations that identify Dilithium
   //               by std::string::starts_with("Dilithium-").
   //               (Above assumes that Dilithium won't be removed entirely!)
   return (m_public->mode().is_ml_dsa()) ? std::string("ML-DSA") : object_identifier().to_formatted_string();
}

AlgorithmIdentifier Dilithium_PublicKey::algorithm_identifier() const {
   return AlgorithmIdentifier(object_identifier(), AlgorithmIdentifier::USE_EMPTY_PARAM);
}

OID Dilithium_PublicKey::object_identifier() const {
   return m_public->mode().mode().object_identifier();
}

size_t Dilithium_PublicKey::key_length() const {
   return m_public->mode().canonical_parameter_set_identifier();
}

size_t Dilithium_PublicKey::estimated_strength() const {
   return m_public->mode().lambda();
}

std::vector<uint8_t> Dilithium_PublicKey::raw_public_key_bits() const {
   return m_public->raw_pk().get();
}

std::vector<uint8_t> Dilithium_PublicKey::public_key_bits() const {
   // Currently, there isn't a finalized definition of an ASN.1 structure for
   // Dilithium aka ML-DSA public keys. Therefore, we return the raw public key bits.
   return raw_public_key_bits();
}

bool Dilithium_PublicKey::check_key(RandomNumberGenerator&, bool) const {
   return true;  // ???
}

std::unique_ptr<Private_Key> Dilithium_PublicKey::generate_another(RandomNumberGenerator& rng) const {
   return std::make_unique<Dilithium_PrivateKey>(rng, m_public->mode().mode());
}

std::unique_ptr<PK_Ops::Verification> Dilithium_PublicKey::create_verification_op(std::string_view params,
                                                                                  std::string_view provider) const {
   BOTAN_ARG_CHECK(params.empty() || params == "Pure", "Unexpected parameters for verifying with Dilithium");
   if(provider.empty() || provider == "base") {
      return std::make_unique<Dilithium_Verification_Operation>(m_public);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

std::unique_ptr<PK_Ops::Verification> Dilithium_PublicKey::create_x509_verification_op(
   const AlgorithmIdentifier& alg_id, std::string_view provider) const {
   if(provider.empty() || provider == "base") {
      if(alg_id != this->algorithm_identifier()) {
         throw Decoding_Error("Unexpected AlgorithmIdentifier for Dilithium X.509 signature");
      }
      return std::make_unique<Dilithium_Verification_Operation>(m_public);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

/**
 * NIST FIPS 204, Algorithm 1 (ML-DSA.KeyGen), and 6 (ML-DSA.KeyGen_internal)
 *
 * This integrates the seed generation and the actual key generation into one
 * function. After generation, the relevant components of the key are kept in
 * memory; the key encoding is deferred until explicitly requested.
 *
 * The calculation of (t1, t0) is done in a separate function, as it is also
 * needed for the decoding of a private key.
 */
Dilithium_PrivateKey::Dilithium_PrivateKey(RandomNumberGenerator& rng, DilithiumMode m) {
   DilithiumConstants mode(m);
   BOTAN_ARG_CHECK(mode.mode().is_available(), "Dilithium/ML-DSA mode is not available in this build");
   std::tie(m_public, m_private) = Dilithium_Algos::expand_keypair(
      rng.random_vec<DilithiumSeedRandomness>(DilithiumConstants::SEED_RANDOMNESS_BYTES), std::move(mode));
}

Dilithium_PrivateKey::Dilithium_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> sk) :
      Dilithium_PrivateKey(sk, DilithiumMode(alg_id.oid())) {}

Dilithium_PrivateKey::Dilithium_PrivateKey(std::span<const uint8_t> sk, DilithiumMode m) {
   DilithiumConstants mode(m);
   auto& codec = mode.keypair_codec();
   std::tie(m_public, m_private) = codec.decode_keypair(sk, std::move(mode));
}

secure_vector<uint8_t> Dilithium_PrivateKey::raw_private_key_bits() const {
   return this->private_key_bits();
}

secure_vector<uint8_t> Dilithium_PrivateKey::private_key_bits() const {
   return m_private->mode().keypair_codec().encode_keypair({m_public, m_private});
}

std::unique_ptr<PK_Ops::Signature> Dilithium_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
                                                                             std::string_view params,
                                                                             std::string_view provider) const {
   BOTAN_UNUSED(rng);

   BOTAN_ARG_CHECK(params.empty() || params == "Deterministic" || params == "Randomized",
                   "Unexpected parameters for signing with ML-DSA/Dilithium");

   // FIPS 204, Section 3.4
   //   By default, this standard specifies the signing algorithm to use both
   //   types of randomness [fresh from the RNG and a value in the private key].
   //   This is referred to as the “hedged” variant of the signing procedure.
   const bool randomized = (params.empty() || params == "Randomized");
   if(provider.empty() || provider == "base") {
      return std::make_unique<Dilithium_Signature_Operation>(DilithiumInternalKeypair{m_public, m_private}, randomized);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

std::unique_ptr<Public_Key> Dilithium_PrivateKey::public_key() const {
   return std::make_unique<Dilithium_PublicKey>(*this);
}
}  // namespace Botan

1	/*
2	* Crystals Dilithium Digital Signature Algorithms
3	* Based on the public domain reference implementation by the
4	* designers (https://github.com/pq-crystals/dilithium)
5	*
6	* Further changes
7	* (C) 2021-2023 Jack Lloyd
8	* (C) 2021-2022 Manuel Glaser - Rohde & Schwarz Cybersecurity
9	* (C) 2021-2023 Michael Boric, René Meusel - Rohde & Schwarz Cybersecurity
10	* (C) 2024 René Meusel - Rohde & Schwarz Cybersecurity
11	*
12	* Botan is released under the Simplified BSD License (see license.txt)
13	*/
14
15	#include <botan/dilithium.h>
16
17	#include <botan/exceptn.h>
18	#include <botan/rng.h>
19
20	#include <botan/internal/dilithium_algos.h>
21	#include <botan/internal/dilithium_keys.h>
22	#include <botan/internal/dilithium_symmetric_primitives.h>
23	#include <botan/internal/dilithium_types.h>
24	#include <botan/internal/fmt.h>
25	#include <botan/internal/pk_ops_impl.h>
26	#include <botan/internal/stl_util.h>
27
28	namespace Botan {
29	namespace {
30
31	DilithiumMode::Mode dilithium_mode_from_string(std::string_view str) {	273✔
32	if(str == "Dilithium-4x4-r3") {	273✔
33	return DilithiumMode::Dilithium4x4;	18✔
34	}
35	if(str == "Dilithium-4x4-AES-r3") {	255✔
36	return DilithiumMode::Dilithium4x4_AES;	16✔
37	}
38	if(str == "Dilithium-6x5-r3") {	239✔
39	return DilithiumMode::Dilithium6x5;	69✔
40	}
41	if(str == "Dilithium-6x5-AES-r3") {	170✔
42	return DilithiumMode::Dilithium6x5_AES;	16✔
43	}
44	if(str == "Dilithium-8x7-r3") {	154✔
45	return DilithiumMode::Dilithium8x7;	16✔
46	}
47	if(str == "Dilithium-8x7-AES-r3") {	138✔
48	return DilithiumMode::Dilithium8x7_AES;	33✔
49	}
50	if(str == "ML-DSA-4x4") {	105✔
51	return DilithiumMode::ML_DSA_4x4;	21✔
52	}
53	if(str == "ML-DSA-6x5") {	84✔
54	return DilithiumMode::ML_DSA_6x5;	66✔
55	}
56	if(str == "ML-DSA-8x7") {	18✔
57	return DilithiumMode::ML_DSA_8x7;	18✔
58	}
59
60	throw Invalid_Argument(fmt("'{}' is not a valid Dilithium mode name", str));	×
61	}
62
63	} // namespace
64
65	DilithiumMode::DilithiumMode(const OID& oid) : m_mode(dilithium_mode_from_string(oid.to_formatted_string())) {}	223✔
66
67	DilithiumMode::DilithiumMode(std::string_view str) : m_mode(dilithium_mode_from_string(str)) {}	50✔
68
69	OID DilithiumMode::object_identifier() const {	624✔
70	return OID::from_string(to_string());	1,248✔
71	}
72
73	std::string DilithiumMode::to_string() const {	624✔
74	switch(m_mode) {	624✔
75	case DilithiumMode::Dilithium4x4:	53✔
76	return "Dilithium-4x4-r3";	53✔
77	case DilithiumMode::Dilithium4x4_AES:	52✔
78	return "Dilithium-4x4-AES-r3";	52✔
79	case DilithiumMode::Dilithium6x5:	177✔
80	return "Dilithium-6x5-r3";	177✔
81	case DilithiumMode::Dilithium6x5_AES:	52✔
82	return "Dilithium-6x5-AES-r3";	52✔
83	case DilithiumMode::Dilithium8x7:	52✔
84	return "Dilithium-8x7-r3";	52✔
85	case DilithiumMode::Dilithium8x7_AES:	75✔
86	return "Dilithium-8x7-AES-r3";	75✔
87	case DilithiumMode::ML_DSA_4x4:	22✔
88	return "ML-DSA-4x4";	22✔
89	case DilithiumMode::ML_DSA_6x5:	119✔
90	return "ML-DSA-6x5";	119✔
91	case DilithiumMode::ML_DSA_8x7:	22✔
92	return "ML-DSA-8x7";	22✔
93	}
94
95	BOTAN_ASSERT_UNREACHABLE();	×
96	}
97
98	bool DilithiumMode::is_aes() const {	11,104✔
99	return m_mode == Dilithium4x4_AES \|\| m_mode == Dilithium6x5_AES \|\| m_mode == Dilithium8x7_AES;	11,104✔
100	}
101
102	bool DilithiumMode::is_modern() const {	5,899✔
103	return !is_aes();	5,899✔
104	}
105
106	bool DilithiumMode::is_ml_dsa() const {	13,966✔
107	return m_mode == ML_DSA_4x4 \|\| m_mode == ML_DSA_6x5 \|\| m_mode == ML_DSA_8x7;	13,966✔
108	}
109
110	bool DilithiumMode::is_available() const {	3,036✔
111	#if defined(BOTAN_HAS_DILITHIUM_AES)
112	if(is_dilithium_round3() && is_aes()) {	3,036✔
113	return true;
114	}
115	#endif
116	#if defined(BOTAN_HAS_DILITHIUM)
117	if(is_dilithium_round3() && is_modern()) {	1,744✔
118	return true;
119	}
120	#endif
121	#if defined(BOTAN_HAS_ML_DSA)
122	if(is_ml_dsa()) {	406✔
123	return true;
124	}
125	#endif
126	return false;
127	}
128
129	class Dilithium_Signature_Operation final : public PK_Ops::Signature {	×
130	public:
131	Dilithium_Signature_Operation(DilithiumInternalKeypair keypair, bool randomized) :	1,498✔
132	m_keypair(std::move(keypair)),	1,498✔
133	m_randomized(randomized),	1,498✔
134	m_h(m_keypair.second->mode().symmetric_primitives().get_message_hash(m_keypair.first->tr())),	2,996✔
135	m_s1(ntt(m_keypair.second->s1().clone())),	1,498✔
136	m_s2(ntt(m_keypair.second->s2().clone())),	1,498✔
137	m_t0(ntt(m_keypair.second->t0().clone())),	1,498✔
138	m_A(Dilithium_Algos::expand_A(m_keypair.first->rho(), m_keypair.second->mode())) {}	2,996✔
139
140	void update(std::span<const uint8_t> input) override { m_h->update(input); }	1,522✔
141
142	/**
143	* NIST FIPS 204, Algorithm 2 (ML-DSA.Sign) and Algorithm 7 (ML-DSA.Sign_internal)
144	*
145	* Note that the private key decoding is done ahead of time. Also, the
146	* matrix expansion of A from 'rho' along with the NTT-transforms of s1,
147	* s2 and t0 are done in the constructor of this class, as a 'signature
148	* operation' may be used to sign multiple messages.
149	*
150	* TODO: Implement support for the specified 'ctx' context string which is
151	* application defined and "empty" by default and <= 255 bytes long.
152	*/
153	std::vector<uint8_t> sign(RandomNumberGenerator& rng) override {	1,516✔
154	auto scope = CT::scoped_poison(*m_keypair.second);	1,516✔
155
156	const auto mu = m_h->final();	1,516✔
157	const auto& mode = m_keypair.second->mode();	1,516✔
158	const auto& sympri = mode.symmetric_primitives();	1,516✔
159
160	const auto rhoprime = sympri.H_maybe_randomized(m_keypair.second->signing_seed(), mu, maybe(rng));	1,516✔
161	CT::poison(rhoprime);	1,516✔
162
163	for(uint16_t nonce = 0, n = 0; n <= DilithiumConstants::SIGNING_LOOP_BOUND; ++n, nonce += mode.l()) {	6,842✔
164	const auto y = Dilithium_Algos::expand_mask(rhoprime, nonce, mode);	6,842✔
165
166	auto w_ntt = m_A * ntt(y.clone());	6,842✔
167	w_ntt.reduce();	6,842✔
168	auto w = inverse_ntt(std::move(w_ntt));	6,842✔
169	w.conditional_add_q();	6,842✔
170
171	auto [w1, w0] = Dilithium_Algos::decompose(w, mode);	6,842✔
172	const auto ch = CT::driveby_unpoison(sympri.H(mu, Dilithium_Algos::encode_commitment(w1, mode)));	6,842✔
173
174	const auto c = ntt(Dilithium_Algos::sample_in_ball(ch, mode));	6,842✔
175	const auto cs1 = inverse_ntt(c * m_s1);	6,842✔
176	auto z = y + cs1;	6,842✔
177	z.reduce();	6,842✔
178
179	// We validate the infinity norm of z before proceeding to calculate cs2
180	if(!Dilithium_Algos::infinity_norm_within_bound(z, to_underlying(mode.gamma1()) - mode.beta())) {	6,842✔
181	continue;	2,726✔
182	}
183	CT::unpoison(z); // part of the signature	4,116✔
184
185	const auto cs2 = inverse_ntt(c * m_s2);	4,116✔
186
187	// Note: w0 is used as a scratch space for calculation. We're aliasing
188	// the results to const&'s merely to communicate which value the
189	// intermediate results represent in the specification.
190	w0 -= cs2;	4,116✔
191	w0.reduce();	4,116✔
192	const auto& r0 = w0;	4,116✔
193	if(!Dilithium_Algos::infinity_norm_within_bound(r0, to_underlying(mode.gamma2()) - mode.beta())) {	4,116✔
194	continue;	2,585✔
195	}
196
197	auto ct0 = inverse_ntt(c * m_t0);	1,531✔
198	ct0.reduce();	1,531✔
199	// We validate the infinity norm of ct0 before proceeding to calculate the hint.
200	if(!Dilithium_Algos::infinity_norm_within_bound(ct0, mode.gamma2())) {	1,531✔
201	continue;	×
202	}
203
204	w0 += ct0;	1,531✔
205	w0.conditional_add_q();	1,531✔
206	const auto& w0cs2ct0 = w0;	1,531✔
207
208	const auto hint = Dilithium_Algos::make_hint(w0cs2ct0, w1, mode);	1,531✔
209	if(CT::driveby_unpoison(hint.hamming_weight()) > mode.omega()) {	3,062✔
210	continue;	15✔
211	}
212	CT::unpoison(hint); // part of the signature	1,516✔
213
214	return Dilithium_Algos::encode_signature(ch, z, hint, mode).get();	3,032✔
215	}	27,368✔
216
217	throw Internal_Error("ML-DSA/Dilithium signature loop did not terminate");	×
218	}	3,032✔
219
220	size_t signature_length() const override { return m_keypair.second->mode().signature_bytes(); }	3✔
221
222	AlgorithmIdentifier algorithm_identifier() const override {	81✔
223	return AlgorithmIdentifier(m_keypair.second->mode().mode().object_identifier(),	162✔
224	AlgorithmIdentifier::USE_EMPTY_PARAM);	162✔
225	}
226
227	std::string hash_function() const override { return m_h->name(); }	125✔
228
229	private:
230	std::optional<std::reference_wrapper<RandomNumberGenerator>> maybe(RandomNumberGenerator& rng) const {	1,516✔
231	if(m_randomized) {	1,516✔
232	return rng;
233	} else {
234	return std::nullopt;	702✔
235	}
236	}
237
238	private:
239	DilithiumInternalKeypair m_keypair;
240	bool m_randomized;
241	std::unique_ptr<DilithiumMessageHash> m_h;
242
243	const DilithiumPolyVecNTT m_s1;
244	const DilithiumPolyVecNTT m_s2;
245	const DilithiumPolyVecNTT m_t0;
246	const DilithiumPolyMatNTT m_A;
247	};
248
249	class Dilithium_Verification_Operation final : public PK_Ops::Verification {	×
250	public:
251	Dilithium_Verification_Operation(std::shared_ptr<Dilithium_PublicKeyInternal> pubkey) :	1,708✔
252	m_pub_key(std::move(pubkey)),	1,708✔
253	m_A(Dilithium_Algos::expand_A(m_pub_key->rho(), m_pub_key->mode())),	1,708✔
254	m_t1_ntt_shifted(ntt(m_pub_key->t1() << DilithiumConstants::D)),	1,708✔
255	m_h(m_pub_key->mode().symmetric_primitives().get_message_hash(m_pub_key->tr())) {}	6,832✔
256
257	void update(std::span<const uint8_t> input) override { m_h->update(input); }	3,103✔
258
259	/**
260	* NIST FIPS 204, Algorithm 3 (ML-DSA.Verify) and 8 (ML-DSA.Verify_internal)
261	*
262	* Note that the public key decoding is done ahead of time. Also, the
263	* matrix A is expanded from 'rho' in the constructor of this class, as
264	* a 'verification operation' may be used to verify multiple signatures.
265	*
266	* TODO: Implement support for the specified 'ctx' context string which is
267	* application defined and "empty" by default and <= 255 bytes long.
268	*/
269	bool is_valid_signature(std::span<const uint8_t> sig) override {	4,450✔
270	const auto& mode = m_pub_key->mode();	4,450✔
271	const auto& sympri = mode.symmetric_primitives();	4,450✔
272	StrongSpan<const DilithiumSerializedSignature> sig_bytes(sig);	4,450✔
273
274	if(sig_bytes.size() != mode.signature_bytes()) {	4,450✔
275	return false;
276	}
277
278	const auto mu = m_h->final();	4,450✔
279
280	auto signature = Dilithium_Algos::decode_signature(sig_bytes, mode);	4,450✔
281	if(!signature.has_value()) {	4,450✔
282	return false;
283	}
284	auto [ch, z, h] = std::move(signature.value());	4,450✔
285
286	// TODO: The first check was removed from the final version of ML-DSA
287	if(h.hamming_weight() > mode.omega() \|\|	13,350✔
288	!Dilithium_Algos::infinity_norm_within_bound(z, to_underlying(mode.gamma1()) - mode.beta())) {	4,450✔
289	return false;	×
290	}
291
292	const auto c_hat = ntt(Dilithium_Algos::sample_in_ball(ch, mode));	4,450✔
293	auto w_approx = m_A * ntt(std::move(z));	4,450✔
294	w_approx -= c_hat * m_t1_ntt_shifted;	4,450✔
295	w_approx.reduce();	4,450✔
296	auto w1 = inverse_ntt(std::move(w_approx));	4,450✔
297	w1.conditional_add_q();	4,450✔
298	Dilithium_Algos::use_hint(w1, h, mode);	4,450✔
299
300	const auto chprime = sympri.H(mu, Dilithium_Algos::encode_commitment(w1, mode));	4,450✔
301
302	BOTAN_ASSERT_NOMSG(ch.size() == chprime.size());	4,450✔
303	return std::equal(ch.begin(), ch.end(), chprime.begin());	8,900✔
304	}	22,250✔
305
306	std::string hash_function() const override { return m_h->name(); }	77✔
307
308	private:
309	std::shared_ptr<Dilithium_PublicKeyInternal> m_pub_key;
310	DilithiumPolyMatNTT m_A;
311	DilithiumPolyVecNTT m_t1_ntt_shifted;
312	std::unique_ptr<DilithiumMessageHash> m_h;
313	};
314
315	Dilithium_PublicKey::Dilithium_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> pk) :	144✔
316	Dilithium_PublicKey(pk, DilithiumMode(alg_id.oid())) {}	144✔
317
318	Dilithium_PublicKey::Dilithium_PublicKey(std::span<const uint8_t> pk, DilithiumMode m) {	1,525✔
319	DilithiumConstants mode(m);	1,525✔
320	BOTAN_ARG_CHECK(mode.mode().is_available(), "Dilithium/ML-DSA mode is not available in this build");	1,525✔
321	BOTAN_ARG_CHECK(pk.empty() \|\| pk.size() == mode.public_key_bytes(),	1,525✔
322	"dilithium public key does not have the correct byte count");
323
324	m_public = Dilithium_PublicKeyInternal::decode(std::move(mode), StrongSpan<const DilithiumSerializedPublicKey>(pk));	1,525✔
325	}	1,525✔
326
327	std::string Dilithium_PublicKey::algo_name() const {	308✔
328	// Note: For Dilithium we made the blunder to return the OID's human readable
329	// name, e.g. "Dilithium-4x4-AES". This is inconsistent with the other
330	// public key algorithms which return the generic name only.
331	//
332	// TODO(Botan4): Fix the inconsistency described above, also considering that
333	// there might be other code locations that identify Dilithium
334	// by std::string::starts_with("Dilithium-").
335	// (Above assumes that Dilithium won't be removed entirely!)
336	return (m_public->mode().is_ml_dsa()) ? std::string("ML-DSA") : object_identifier().to_formatted_string();	308✔
337	}
338
339	AlgorithmIdentifier Dilithium_PublicKey::algorithm_identifier() const {	336✔
340	return AlgorithmIdentifier(object_identifier(), AlgorithmIdentifier::USE_EMPTY_PARAM);	336✔
341	}
342
343	OID Dilithium_PublicKey::object_identifier() const {	543✔
344	return m_public->mode().mode().object_identifier();	543✔
345	}
346
347	size_t Dilithium_PublicKey::key_length() const {	37✔
348	return m_public->mode().canonical_parameter_set_identifier();	37✔
349	}
350
351	size_t Dilithium_PublicKey::estimated_strength() const {	123✔
352	return m_public->mode().lambda();	123✔
353	}
354
355	std::vector<uint8_t> Dilithium_PublicKey::raw_public_key_bits() const {	2,857✔
356	return m_public->raw_pk().get();	2,857✔
357	}
358
359	std::vector<uint8_t> Dilithium_PublicKey::public_key_bits() const {	2,840✔
360	// Currently, there isn't a finalized definition of an ASN.1 structure for
361	// Dilithium aka ML-DSA public keys. Therefore, we return the raw public key bits.
362	return raw_public_key_bits();	2,840✔
363	}
364
365	bool Dilithium_PublicKey::check_key(RandomNumberGenerator&, bool) const {	18✔
366	return true; // ???	18✔
367	}
368
369	std::unique_ptr<Private_Key> Dilithium_PublicKey::generate_another(RandomNumberGenerator& rng) const {	9✔
370	return std::make_unique<Dilithium_PrivateKey>(rng, m_public->mode().mode());	9✔
371	}
372
373	std::unique_ptr<PK_Ops::Verification> Dilithium_PublicKey::create_verification_op(std::string_view params,	1,633✔
374	std::string_view provider) const {
375	BOTAN_ARG_CHECK(params.empty() \|\| params == "Pure", "Unexpected parameters for verifying with Dilithium");	1,633✔
376	if(provider.empty() \|\| provider == "base") {	1,634✔
377	return std::make_unique<Dilithium_Verification_Operation>(m_public);	1,633✔
378	}
379	throw Provider_Not_Found(algo_name(), provider);	×
380	}
381
382	std::unique_ptr<PK_Ops::Verification> Dilithium_PublicKey::create_x509_verification_op(	75✔
383	const AlgorithmIdentifier& alg_id, std::string_view provider) const {
384	if(provider.empty() \|\| provider == "base") {	75✔
385	if(alg_id != this->algorithm_identifier()) {	75✔
386	throw Decoding_Error("Unexpected AlgorithmIdentifier for Dilithium X.509 signature");	×
387	}
388	return std::make_unique<Dilithium_Verification_Operation>(m_public);	75✔
389	}
390	throw Provider_Not_Found(algo_name(), provider);	×
391	}
392
393	/**
394	* NIST FIPS 204, Algorithm 1 (ML-DSA.KeyGen), and 6 (ML-DSA.KeyGen_internal)
395	*
396	* This integrates the seed generation and the actual key generation into one
397	* function. After generation, the relevant components of the key are kept in
398	* memory; the key encoding is deferred until explicitly requested.
399	*
400	* The calculation of (t1, t0) is done in a separate function, as it is also
401	* needed for the decoding of a private key.
402	*/
403	Dilithium_PrivateKey::Dilithium_PrivateKey(RandomNumberGenerator& rng, DilithiumMode m) {	1,417✔
404	DilithiumConstants mode(m);	1,417✔
405	BOTAN_ARG_CHECK(mode.mode().is_available(), "Dilithium/ML-DSA mode is not available in this build");	1,417✔
406	std::tie(m_public, m_private) = Dilithium_Algos::expand_keypair(	2,834✔
407	rng.random_vec<DilithiumSeedRandomness>(DilithiumConstants::SEED_RANDOMNESS_BYTES), std::move(mode));	4,251✔
408	}	1,417✔
409
410	Dilithium_PrivateKey::Dilithium_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> sk) :	79✔
411	Dilithium_PrivateKey(sk, DilithiumMode(alg_id.oid())) {}	79✔
412
413	Dilithium_PrivateKey::Dilithium_PrivateKey(std::span<const uint8_t> sk, DilithiumMode m) {	101✔
414	DilithiumConstants mode(m);	101✔
415	auto& codec = mode.keypair_codec();	101✔
416	std::tie(m_public, m_private) = codec.decode_keypair(sk, std::move(mode));	101✔
417	}	101✔
418
419	secure_vector<uint8_t> Dilithium_PrivateKey::raw_private_key_bits() const {	8✔
420	return this->private_key_bits();	8✔
421	}
422
423	secure_vector<uint8_t> Dilithium_PrivateKey::private_key_bits() const {	1,515✔
424	return m_private->mode().keypair_codec().encode_keypair({m_public, m_private});	3,030✔
425	}
426
427	std::unique_ptr<PK_Ops::Signature> Dilithium_PrivateKey::create_signature_op(RandomNumberGenerator& rng,	1,498✔
428	std::string_view params,
429	std::string_view provider) const {
430	BOTAN_UNUSED(rng);	1,498✔
431
432	BOTAN_ARG_CHECK(params.empty() \|\| params == "Deterministic" \|\| params == "Randomized",	2,983✔
433	"Unexpected parameters for signing with ML-DSA/Dilithium");
434
435	// FIPS 204, Section 3.4
436	// By default, this standard specifies the signing algorithm to use both
437	// types of randomness [fresh from the RNG and a value in the private key].
438	// This is referred to as the “hedged” variant of the signing procedure.
439	const bool randomized = (params.empty() \|\| params == "Randomized");	2,281✔
440	if(provider.empty() \|\| provider == "base") {	1,499✔
441	return std::make_unique<Dilithium_Signature_Operation>(DilithiumInternalKeypair{m_public, m_private}, randomized);	2,996✔
442	}
443	throw Provider_Not_Found(algo_name(), provider);	×
444	}
445
446	std::unique_ptr<Public_Key> Dilithium_PrivateKey::public_key() const {	22✔
447	return std::make_unique<Dilithium_PublicKey>(*this);	22✔
448	}
449	} // namespace Botan

randombit / botan / 11345717360

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous