/* * FrodoKEM matrix logic * Based on the MIT licensed reference implementation by the designers * (https://github.com/microsoft/PQCrypto-LWEKE/tree/master) * * The Fellowship of the FrodoKEM: * (C) 2023 Jack Lloyd * 2023 René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity * * Botan is released under the Simplified BSD License (see license.txt) */ #include #include #include #include #include #include #include #include #include #include #include #if defined(BOTAN_HAS_FRODOKEM_AES) #include #endif #if defined(BOTAN_HAS_FRODOKEM_SHAKE) #include #endif namespace Botan { namespace { secure_vector make_elements_vector(const FrodoMatrix::Dimensions& dimensions) { return secure_vector(static_cast(std::get<0>(dimensions)) * std::get<1>(dimensions)); } std::function out, uint16_t i)> make_row_generator(const FrodoKEMConstants& constants, StrongSpan seed_a) { #if defined(BOTAN_HAS_FRODOKEM_AES) if(constants.mode().is_aes()) { return create_aes_row_generator(constants, seed_a); } #endif #if defined(BOTAN_HAS_FRODOKEM_SHAKE) if(constants.mode().is_shake()) { return create_shake_row_generator(constants, seed_a); } #endif // If we don't have AES in this build, the instantiation of the FrodoKEM instance // is blocked upstream already. Hence, assert is save here. BOTAN_ASSERT_UNREACHABLE(); } } // namespace FrodoMatrix FrodoMatrix::sample(const FrodoKEMConstants& constants, const Dimensions& dimensions, StrongSpan r) { BOTAN_ASSERT_NOMSG(r.size() % 2 == 0); const auto n = r.size() / 2; auto elements = make_elements_vector(dimensions); BOTAN_ASSERT_NOMSG(n == elements.size()); load_le(elements.data(), r.data(), n); for(auto& elem : elements) { const auto prnd = CT::value_barrier(static_cast(elem >> 1)); // Drop the least significant bit const auto sign = CT::Mask::expand_bit(elem, 0); // Pick the least significant bit uint32_t sample = 0; // Avoid integral promotion // No need to compare with the last value. for(size_t j = 0; j < constants.cdf_table_len() - 1; ++j) { // Constant time comparison: 1 if CDF_TABLE[j] < s, 0 otherwise. sample += CT::Mask::is_lt(constants.cdf_table_at(j), prnd).if_set_return(1); } // Assuming that sign is either 0 or 1, flips sample iff sign = 1 const uint16_t sample_u16 = static_cast(sample); elem = sign.select(~sample_u16 + 1, sample_u16); } return FrodoMatrix(dimensions, std::move(elements)); } std::function FrodoMatrix::make_sample_generator( const FrodoKEMConstants& constants, Botan::XOF& shake) { return [&constants, &shake](const FrodoMatrix::Dimensions& dimensions) mutable { return sample(constants, dimensions, shake.output(sizeof(uint16_t) * std::get<0>(dimensions) * std::get<1>(dimensions))); }; } FrodoMatrix::FrodoMatrix(Dimensions dims) : m_dim1(std::get<0>(dims)), m_dim2(std::get<1>(dims)), m_elements(make_elements_vector(dims)) {} FrodoMatrix FrodoMatrix::mul_add_as_plus_e(const FrodoKEMConstants& constants, const FrodoMatrix& s, const FrodoMatrix& e, StrongSpan seed_a) { BOTAN_ASSERT(std::get<0>(e.dimensions()) == std::get<1>(s.dimensions()) && std::get<1>(e.dimensions()) == std::get<0>(s.dimensions()), "FrodoMatrix dimension mismatch of E and S"); BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n() && std::get<1>(e.dimensions()) == constants.n_bar(), "FrodoMatrix dimension mismatch of new matrix dimensions and E"); auto elements = make_elements_vector(e.dimensions()); auto row_generator = make_row_generator(constants, seed_a); /* We perform 4 invocations of SHAKE128 per iteration to obtain n 16-bit values per invocation. a_row_data contains the 16-bit values of the current 4 rows. a_row_data_bytes represents the corresponding bytes. */ std::vector a_row_data(4 * constants.n(), 0); // TODO: maybe use std::as_bytes() instead // (take extra care, as it produces a std::span) const std::span a_row_data_bytes(reinterpret_cast(a_row_data.data()), sizeof(uint16_t) * a_row_data.size()); for(size_t i = 0; i < constants.n(); i += 4) { auto a_row = BufferStuffer(a_row_data_bytes); // Do 4 invocations to fill 4 rows row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast(i + 0)); row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast(i + 1)); row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast(i + 2)); row_generator(a_row.next(constants.n() * sizeof(uint16_t)), static_cast(i + 3)); // Use generated bytes to fill 16-bit data load_le(a_row_data.data(), a_row_data_bytes.data(), 4 * constants.n()); for(size_t k = 0; k < constants.n_bar(); ++k) { std::array sum = {0}; for(size_t j = 0; j < constants.n(); ++j) { // Matrix-vector multiplication // Note: we use uint32_t for `sp` to avoid an integral promotion to `int` // when multiplying `sp` with other row values. Otherwise we might // suffer from undefined behaviour due to a signed integer overflow. // See: https://learn.microsoft.com/en-us/cpp/cpp/standard-conversions#integral-promotions const uint32_t sp = s.elements_at(k * constants.n() + j); // Go through four lines with same sp sum.at(0) += static_cast(a_row_data.at(0 * constants.n() + j) * sp); sum.at(1) += static_cast(a_row_data.at(1 * constants.n() + j) * sp); sum.at(2) += static_cast(a_row_data.at(2 * constants.n() + j) * sp); sum.at(3) += static_cast(a_row_data.at(3 * constants.n() + j) * sp); } elements.at((i + 0) * constants.n_bar() + k) = e.elements_at((i + 0) * constants.n_bar() + k) + sum.at(0); elements.at((i + 3) * constants.n_bar() + k) = e.elements_at((i + 3) * constants.n_bar() + k) + sum.at(3); elements.at((i + 2) * constants.n_bar() + k) = e.elements_at((i + 2) * constants.n_bar() + k) + sum.at(2); elements.at((i + 1) * constants.n_bar() + k) = e.elements_at((i + 1) * constants.n_bar() + k) + sum.at(1); } } return FrodoMatrix(e.dimensions(), std::move(elements)); } FrodoMatrix FrodoMatrix::mul_add_sa_plus_e(const FrodoKEMConstants& constants, const FrodoMatrix& s, const FrodoMatrix& e, StrongSpan seed_a) { BOTAN_ASSERT(std::get<0>(e.dimensions()) == std::get<0>(s.dimensions()) && std::get<1>(e.dimensions()) == std::get<1>(s.dimensions()), "FrodoMatrix dimension mismatch of E and S"); BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n_bar() && std::get<1>(e.dimensions()) == constants.n(), "FrodoMatrix dimension mismatch of new matrix dimensions and E"); auto elements = e.m_elements; auto row_generator = make_row_generator(constants, seed_a); /* We perform 8 invocations of SHAKE128 per iteration to obtain n 16-bit values per invocation. a_row_data contains the 16-bit values of the current 8 rows. a_row_data_bytes represents the corresponding bytes. */ std::vector a_row_data(8 * constants.n(), 0); // TODO: maybe use std::as_bytes() const std::span a_row_data_bytes(reinterpret_cast(a_row_data.data()), sizeof(uint16_t) * a_row_data.size()); // Start matrix multiplication for(size_t i = 0; i < constants.n(); i += 8) { auto a_row = BufferStuffer(a_row_data_bytes); // Do 8 invocations to fill 8 rows row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 0)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 1)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 2)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 3)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 4)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 5)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 6)); row_generator(a_row.next(sizeof(uint16_t) * constants.n()), static_cast(i + 7)); // Use generated bytes to fill 16-bit data load_le(a_row_data.data(), a_row_data_bytes.data(), 8 * constants.n()); for(size_t j = 0; j < constants.n_bar(); ++j) { uint16_t sum = 0; std::array sp{}; for(size_t p = 0; p < 8; ++p) { sp[p] = s.elements_at(j * constants.n() + i + p); } for(size_t q = 0; q < constants.n(); ++q) { sum = elements.at(j * constants.n() + q); for(size_t p = 0; p < 8; ++p) { sum += static_cast(sp[p] * a_row_data.at(p * constants.n() + q)); } elements.at(j * constants.n() + q) = sum; } } } return FrodoMatrix(e.dimensions(), std::move(elements)); } FrodoMatrix FrodoMatrix::mul_add_sb_plus_e(const FrodoKEMConstants& constants, const FrodoMatrix& b, const FrodoMatrix& s, const FrodoMatrix& e) { BOTAN_ASSERT(std::get<0>(b.dimensions()) == std::get<1>(s.dimensions()) && std::get<1>(b.dimensions()) == std::get<0>(s.dimensions()), "FrodoMatrix dimension mismatch of B and S"); BOTAN_ASSERT(std::get<0>(b.dimensions()) == constants.n() && std::get<1>(b.dimensions()) == constants.n_bar(), "FrodoMatrix dimension mismatch of B"); BOTAN_ASSERT(std::get<0>(e.dimensions()) == constants.n_bar() && std::get<1>(e.dimensions()) == constants.n_bar(), "FrodoMatrix dimension mismatch of E"); auto elements = make_elements_vector(e.dimensions()); for(size_t k = 0; k < constants.n_bar(); ++k) { for(size_t i = 0; i < constants.n_bar(); ++i) { elements.at(k * constants.n_bar() + i) = e.elements_at(k * constants.n_bar() + i); for(size_t j = 0; j < constants.n(); ++j) { elements.at(k * constants.n_bar() + i) += static_cast( static_cast(s.elements_at(k * constants.n() + j)) * b.elements_at(j * constants.n_bar() + i)); } } } return FrodoMatrix(e.dimensions(), std::move(elements)); } FrodoMatrix FrodoMatrix::encode(const FrodoKEMConstants& constants, StrongSpan in) { const uint64_t mask = (uint64_t(1) << constants.b()) - 1; const auto dimensions = std::make_tuple(constants.n_bar(), constants.n_bar()); auto elements = make_elements_vector(dimensions); BOTAN_ASSERT_NOMSG(in.size() * 8 == constants.n_bar() * constants.n_bar() * constants.b()); size_t pos = 0; for(size_t i = 0; i < (constants.n_bar() * constants.n_bar()) / 8; ++i) { uint64_t temp = 0; for(size_t j = 0; j < constants.b(); ++j) { temp |= static_cast(in[i * constants.b() + j]) << (8 * j); } for(size_t j = 0; j < 8; ++j) { elements.at(pos++) = static_cast((temp & mask) << (constants.d() - constants.b())); // k*2^(D-B) temp >>= constants.b(); } } return FrodoMatrix(dimensions, std::move(elements)); } FrodoMatrix FrodoMatrix::add(const FrodoKEMConstants& constants, const FrodoMatrix& a, const FrodoMatrix& b) { // Addition is defined for n_bar x n_bar matrices only BOTAN_ASSERT_NOMSG(a.dimensions() == b.dimensions()); BOTAN_ASSERT_NOMSG(std::get<0>(a.dimensions()) == constants.n_bar() && std::get<1>(a.dimensions()) == constants.n_bar()); auto elements = make_elements_vector(a.dimensions()); for(size_t i = 0; i < constants.n_bar() * constants.n_bar(); ++i) { elements.at(i) = a.elements_at(i) + b.elements_at(i); } return FrodoMatrix(a.dimensions(), std::move(elements)); } FrodoMatrix FrodoMatrix::sub(const FrodoKEMConstants& constants, const FrodoMatrix& a, const FrodoMatrix& b) { // Subtraction is defined for n_bar x n_bar matrices only BOTAN_ASSERT_NOMSG(a.dimensions() == b.dimensions()); BOTAN_ASSERT_NOMSG(std::get<0>(a.dimensions()) == constants.n_bar() && std::get<1>(a.dimensions()) == constants.n_bar()); auto elements = make_elements_vector(a.dimensions()); for(size_t i = 0; i < constants.n_bar() * constants.n_bar(); ++i) { elements.at(i) = a.elements_at(i) - b.elements_at(i); } return FrodoMatrix(a.dimensions(), std::move(elements)); } CT::Mask FrodoMatrix::constant_time_compare(const FrodoMatrix& other) const { BOTAN_ASSERT_NOMSG(dimensions() == other.dimensions()); // TODO: Possibly use range-based comparison after #3715 is merged return CT::is_equal(reinterpret_cast(m_elements.data()), reinterpret_cast(other.m_elements.data()), sizeof(decltype(m_elements)::value_type) * m_elements.size()); } FrodoMatrix FrodoMatrix::mul_bs(const FrodoKEMConstants& constants, const FrodoMatrix& b, const FrodoMatrix& s) { const Dimensions dimensions = {constants.n_bar(), constants.n_bar()}; auto elements = make_elements_vector(dimensions); for(size_t i = 0; i < constants.n_bar(); ++i) { for(size_t j = 0; j < constants.n_bar(); ++j) { auto& current = elements.at(i * constants.n_bar() + j); current = 0; for(size_t k = 0; k < constants.n(); ++k) { // Explicitly store the values in 32-bit variables to avoid integral promotion const uint32_t b_ink = b.elements_at(i * constants.n() + k); // Since the input is s^T, we multiply the i-th row of b with the j-th row of s^t const uint32_t s_ink = s.elements_at(j * constants.n() + k); current += static_cast(b_ink * s_ink); } } } return FrodoMatrix(dimensions, std::move(elements)); } void FrodoMatrix::pack(const FrodoKEMConstants& constants, StrongSpan out) const { const size_t outlen = packed_size(constants); BOTAN_ASSERT_NOMSG(out.size() == outlen); size_t i = 0; // whole bytes already filled in size_t j = 0; // whole uint16_t already copied uint16_t w = 0; // the leftover, not yet copied uint8_t bits = 0; // the number of lsb in w while(i < outlen && (j < element_count() || ((j == element_count()) && (bits > 0)))) { /* in: | | |********|********| ^ j w : | ****| ^ bits out:|**|**|**|**|**|**|**|**|* | ^^ ib */ uint8_t b = 0; // bits in out[i] already filled in while(b < 8) { const uint8_t nbits = std::min(static_cast(8 - b), bits); const uint16_t mask = static_cast(1 << nbits) - 1; const auto t = static_cast((w >> (bits - nbits)) & mask); // the bits to copy from w to out out[i] = out[i] + static_cast(t << (8 - b - nbits)); b += nbits; bits -= nbits; if(bits == 0) { if(j < element_count()) { w = m_elements.at(j); bits = static_cast(constants.d()); j++; } else { break; // the input vector is exhausted } } } if(b == 8) { // out[i] is filled in i++; } } } FrodoSerializedMatrix FrodoMatrix::serialize() const { FrodoSerializedMatrix out(2 * m_elements.size()); for(unsigned int i = 0; i < m_elements.size(); ++i) { store_le(m_elements.at(i), out.data() + 2 * i); } return out; } FrodoPlaintext FrodoMatrix::decode(const FrodoKEMConstants& constants) const { const size_t nwords = (constants.n_bar() * constants.n_bar()) / 8; const uint16_t maskex = static_cast(1 << constants.b()) - 1; const uint16_t maskq = static_cast(1 << constants.d()) - 1; FrodoPlaintext out(nwords * constants.b()); size_t index = 0; for(size_t i = 0; i < nwords; i++) { uint64_t templong = 0; for(size_t j = 0; j < 8; j++) { const auto temp = static_cast(((m_elements.at(index) & maskq) + (1 << (constants.d() - constants.b() - 1))) >> (constants.d() - constants.b())); templong |= static_cast(temp & maskex) << (constants.b() * j); index++; } for(size_t j = 0; j < constants.b(); j++) { out[i * constants.b() + j] = (templong >> (8 * j)) & 0xFF; } } return out; } FrodoMatrix FrodoMatrix::unpack(const FrodoKEMConstants& constants, const Dimensions& dimensions, StrongSpan packed_bytes) { const uint8_t lsb = static_cast(constants.d()); const size_t inlen = packed_bytes.size(); const size_t outlen = static_cast(std::get<0>(dimensions)) * std::get<1>(dimensions); BOTAN_ASSERT_NOMSG(inlen == ceil_tobytes(outlen * lsb)); auto elements = make_elements_vector(dimensions); size_t i = 0; // whole uint16_t already filled in size_t j = 0; // whole bytes already copied uint8_t w = 0; // the leftover, not yet copied uint8_t bits = 0; // the number of lsb bits of w while(i < outlen && (j < inlen || ((j == inlen) && (bits > 0)))) { /* in: | | | | | | |**|**|... ^ j w : | *| ^ bits out:| *****| *****| *** | |... ^ ^ i b */ uint8_t b = 0; // bits in out[i] already filled in while(b < lsb) { const uint8_t nbits = std::min(static_cast(lsb - b), bits); const uint16_t mask = static_cast(1 << nbits) - 1; const uint8_t t = (w >> (bits - nbits)) & mask; // the bits to copy from w to out elements.at(i) = elements.at(i) + static_cast(t << (lsb - b - nbits)); b += nbits; bits -= nbits; w &= static_cast(~(mask << bits)); // not strictly necessary; mostly for debugging if(bits == 0) { if(j < inlen) { w = packed_bytes[j]; bits = 8; j++; } else { break; // the input vector is exhausted } } } if(b == lsb) { // out[i] is filled in i++; } } return FrodoMatrix(dimensions, std::move(elements)); } FrodoMatrix FrodoMatrix::deserialize(const Dimensions& dimensions, StrongSpan bytes) { auto elements = make_elements_vector(dimensions); BOTAN_ASSERT_NOMSG(elements.size() * 2 == bytes.size()); load_le(elements.data(), bytes.data(), elements.size()); return FrodoMatrix(dimensions, std::move(elements)); } void FrodoMatrix::reduce(const FrodoKEMConstants& constants) { // Reduction is inherent if D is 16, because we use uint16_t in m_elements if(constants.d() < sizeof(decltype(m_elements)::value_type) * 8) { const uint16_t mask = static_cast(1 << constants.d()) - 1; for(auto& elem : m_elements) { elem = elem & mask; // mod q } } } } // namespace Botan