Repository: randombit/botan
Pull request #3672 (2023-08-16 11:15:19)

Use XOF interface in Kyber and Dilithium
### Pull Request Dependencies

* ~#3673~
* ~#3671~
* ~#3701~

### Description

Instead of misusing `StreamCipher` for this job, we now have the top-level `XOF` interface. Also, I added a common XOF implementation based on AES-256/CTR for both Kyber and Dilithium in their 90s-modes.

### Potential Future Work

The polymorphic construction to distinguish between 90s and modern modes in Kyber and Dilithium is instantiating a lot of hash functions that are then just used once by the business logic. There might be room for performance improvements.

coveralls: 
[![Coverage Status](https://coveralls.io/builds/62019044/badge)](https://coveralls.io/builds/62019044)

coverage: 91.7% (+0.002%) from 91.698% when pulling **9a39e705a8c5dccf2915f154780abb19fdff0795 on Rohde-Schwarz:feature/xof_in_crystals** into **fc4b4271fbaa47e886ee4028c2b2cb8eb3384543 on randombit:master**.

reneme: WIP: At the moment the adaption of the `SHAKE_Cipher` is buggy. I'll need to look into that tomorrow.
reneme: This will need reconsideration once #3671 is finished and merged. Converted to a draft-PR for now.
reneme: Rebased to the latest revision of #3671 and adapted to the `XOF::start()` method to apply the IV and key to the AES-256/CTR XOF.
reneme: Rebased to the latest revision of https://github.com/randombit/botan/pull/3671 and adapted to the XOF::valid_salt_length() method. Also, fixes a missing module dependency in `kyber`.
reneme: Rebased to the latest revision of https://github.com/randombit/botan/pull/3671 again to resolve expected conflicts with [the cSHAKE test hack](https://github.com/randombit/botan/pull/3671#issuecomment-1717994514).
reneme: Rebased to master after #3671 was merged.
reneme: Rebased ont #3701 to address a similar issues as pointed out here: https://github.com/randombit/botan/pull/3701#discussion_r1327963781

Patch:
diff --git a/src/lib/pubkey/dilithium/dilithium/dilithium_modern.h b/src/lib/pubkey/dilithium/dilithium/dilithium_modern.h
index 604dfc83a..56e377a15 100644
--- a/src/lib/pubkey/dilithium/dilithium/dilithium_modern.h
+++ b/src/lib/pubkey/dilithium/dilithium/dilithium_modern.h
@@ -11,8 +11,9 @@
 
 #include <botan/internal/dilithium_symmetric_primitives.h>
 
+#include <botan/internal/loadstor.h>
 #include <botan/internal/shake.h>
-#include <botan/internal/shake_cipher.h>
+#include <botan/internal/shake_xof.h>
 
 #include <array>
 #include <memory>
@@ -22,27 +23,25 @@ namespace Botan {
 
 class Dilithium_Common_Symmetric_Primitives : public Dilithium_Symmetric_Primitives {
    public:
-      std::unique_ptr<StreamCipher> XOF(XofType type, std::span<const uint8_t> seed, uint16_t nonce) const override {
-         // Input is a concatination of seed | nonce used as input for shake128
-         std::vector<uint8_t> input;
-         input.reserve(seed.size() + 2);
-         input.insert(input.end(), seed.begin(), seed.end());
-         input.push_back(static_cast<uint8_t>(nonce));
-         input.push_back(static_cast<uint8_t>(nonce >> 8));
-
-         std::unique_ptr<StreamCipher> cipher;
-         switch(type) {
-            case XofType::k128:
-               cipher = std::make_unique<SHAKE_128_Cipher>();
-               break;
-            case XofType::k256:
-               cipher = std::make_unique<SHAKE_256_Cipher>();
-               break;
-         }
-
-         cipher->set_key(input);
-
-         return cipher;
+      std::unique_ptr<Botan::XOF> XOF(XofType type, std::span<const uint8_t> seed, uint16_t nonce) const override {
+         const auto xof_type = [&] {
+            switch(type) {
+               case XofType::k128:
+                  return "SHAKE-128";
+               case XofType::k256:
+                  return "SHAKE-256";
+            }
+
+            BOTAN_ASSERT_UNREACHABLE();
+         }();
+
+         std::array<uint8_t, sizeof(nonce)> nonce_buffer;
+         store_le(nonce, nonce_buffer.data());
+
+         auto xof = Botan::XOF::create_or_throw(xof_type);
+         xof->update(seed);
+         xof->update(nonce_buffer);
+         return xof;
       }
 };
 
diff --git a/src/lib/pubkey/dilithium/dilithium/info.txt b/src/lib/pubkey/dilithium/dilithium/info.txt
index d27b448be..f8d71340d 100644
--- a/src/lib/pubkey/dilithium/dilithium/info.txt
+++ b/src/lib/pubkey/dilithium/dilithium/info.txt
@@ -8,7 +8,7 @@ name -> "Dilithium"
 
 <requires>
 dilithium_common
-shake_cipher
+shake_xof
 </requires>
 
 <header:internal>
diff --git a/src/lib/pubkey/dilithium/dilithium_aes/dilithium_aes.h b/src/lib/pubkey/dilithium/dilithium_aes/dilithium_aes.h
index 8d02b6f5a..eff8cb4e2 100644
--- a/src/lib/pubkey/dilithium/dilithium_aes/dilithium_aes.h
+++ b/src/lib/pubkey/dilithium/dilithium_aes/dilithium_aes.h
@@ -11,7 +11,7 @@
 
 #include <botan/internal/dilithium_symmetric_primitives.h>
 
-#include <botan/stream_cipher.h>
+#include <botan/internal/aes_crystals_xof.h>
 #include <botan/internal/loadstor.h>
 
 #include <array>
@@ -23,9 +23,7 @@ namespace Botan {
 class Dilithium_AES_Symmetric_Primitives : public Dilithium_Symmetric_Primitives {
    public:
       // AES mode always uses AES-256, regardless of the XofType
-      std::unique_ptr<StreamCipher> XOF(XofType /* type */, std::span<const uint8_t> seed, uint16_t nonce) const final {
-         auto cipher = StreamCipher::create_or_throw("CTR(AES-256)");
-
+      std::unique_ptr<Botan::XOF> XOF(XofType /* type */, std::span<const uint8_t> seed, uint16_t nonce) const final {
          // Algorithm Spec V. 3.1 Section 5.3
          //    In the AES variant, the first 32 bytes of rhoprime are used as
          //    the key and i is extended to a 12 byte nonce for AES-256 in
@@ -33,13 +31,14 @@ class Dilithium_AES_Symmetric_Primitives : public Dilithium_Symmetric_Primitives
          //
          // I.e. when the XOF is used in "ExpandS" `seed` (aka rhoprime) will be
          // 64 bytes long and must be truncated to the 32 most significant bytes.
-         BOTAN_ASSERT_NOMSG(seed.size() >= cipher->key_spec().minimum_keylength());
-         cipher->set_key(seed.data(), cipher->key_spec().minimum_keylength());
+         BOTAN_ASSERT_NOMSG(seed.size() >= 32);
+
+         const std::array<uint8_t, 12> iv{get_byte<1>(nonce), get_byte<0>(nonce), 0};
+         const auto key = seed.first(32);
 
-         // The nonce is padded as needed by the CTR_BE mode
-         std::array<uint8_t, 2> iv{get_byte<1>(nonce), get_byte<0>(nonce)};
-         cipher->set_iv(iv.data(), iv.size());
-         return cipher;
+         auto xof = std::make_unique<AES_256_CTR_XOF>();
+         xof->start(iv, key);
+         return xof;
       }
 };
 
diff --git a/src/lib/pubkey/dilithium/dilithium_aes/info.txt b/src/lib/pubkey/dilithium/dilithium_aes/info.txt
index d8b0272ca..13920cb7a 100644
--- a/src/lib/pubkey/dilithium/dilithium_aes/info.txt
+++ b/src/lib/pubkey/dilithium/dilithium_aes/info.txt
@@ -8,8 +8,7 @@ name -> "Dilithium (AES)"
 
 <requires>
 dilithium_common
-aes
-ctr
+aes_crystals_xof
 </requires>
 
 <header:internal>
diff --git a/src/lib/pubkey/dilithium/dilithium_common/dilithium_polynomials.h b/src/lib/pubkey/dilithium/dilithium_common/dilithium_polynomials.h
index abe5a3557..569c67d8d 100644
--- a/src/lib/pubkey/dilithium/dilithium_common/dilithium_polynomials.h
+++ b/src/lib/pubkey/dilithium/dilithium_common/dilithium_polynomials.h
@@ -154,11 +154,11 @@ class Polynomial {
          auto xof = mode.XOF_256(seed, nonce);
 
          secure_vector<uint8_t> buf(mode.poly_uniform_eta_nblocks() * mode.stream256_blockbytes());
-         xof->write_keystream(buf.data(), buf.size());
+         xof->output(buf);
          size_t ctr = Polynomial::rej_eta(a, 0, DilithiumModeConstants::N, buf, buf.size(), mode);
 
          while(ctr < DilithiumModeConstants::N) {
-            xof->write_keystream(buf.data(), mode.stream256_blockbytes());
+            xof->output(std::span(buf).first(mode.stream256_blockbytes()));
             ctr += Polynomial::rej_eta(a, ctr, DilithiumModeConstants::N - ctr, buf, mode.stream256_blockbytes(), mode);
          }
       }
@@ -996,7 +996,7 @@ class PolynomialVector {
          std::vector<uint8_t> buf(buflen + 2);
 
          auto xof = mode.XOF_128(seed, nonce);
-         xof->write_keystream(buf.data(), buflen);
+         xof->output(std::span(buf).first(buflen));
 
          size_t ctr = Polynomial::rej_uniform(sample_poly, 0, DilithiumModeConstants::N, buf.data(), buflen);
          size_t off;
@@ -1006,7 +1006,7 @@ class PolynomialVector {
                buf[i] = buf[buflen - off + i];
             }
 
-            xof->write_keystream(buf.data() + off, mode.stream128_blockbytes());
+            xof->output(std::span(buf).subspan(off, mode.stream128_blockbytes()));
             buflen = mode.stream128_blockbytes() + off;
             ctr += Polynomial::rej_uniform(sample_poly, ctr, DilithiumModeConstants::N - ctr, buf.data(), buflen);
          }
diff --git a/src/lib/pubkey/dilithium/dilithium_common/dilithium_symmetric_primitives.h b/src/lib/pubkey/dilithium/dilithium_common/dilithium_symmetric_primitives.h
index 93cfd17d8..6d9a12676 100644
--- a/src/lib/pubkey/dilithium/dilithium_common/dilithium_symmetric_primitives.h
+++ b/src/lib/pubkey/dilithium/dilithium_common/dilithium_symmetric_primitives.h
@@ -11,8 +11,8 @@
 #define BOTAN_DILITHIUM_ASYM_PRIMITIVES_H_
 
 #include <botan/dilithium.h>
-#include <botan/stream_cipher.h>
 
+#include <botan/xof.h>
 #include <botan/internal/shake.h>
 
 #include <memory>
@@ -46,13 +46,11 @@ class Dilithium_Symmetric_Primitives {
 
       // ExpandMatrix always uses the 256 version of the XOF
       secure_vector<uint8_t> ExpandMask(std::span<const uint8_t> seed, uint16_t nonce, size_t out_len) const {
-         return XOF(XofType::k256, seed, nonce)->keystream_bytes(out_len);
+         return XOF(XofType::k256, seed, nonce)->output(out_len);
       }
 
       // Mode dependent function
-      virtual std::unique_ptr<StreamCipher> XOF(XofType type,
-                                                std::span<const uint8_t> seed,
-                                                uint16_t matrix_position) const = 0;
+      virtual std::unique_ptr<Botan::XOF> XOF(XofType type, std::span<const uint8_t> seed, uint16_t nonce) const = 0;
 };
 
 enum DilithiumEta : uint32_t { Eta2 = 2, Eta4 = 4 };
@@ -161,11 +159,11 @@ class DilithiumModeConstants {
          return m_symmetric_primitives->CRH(in, DilithiumModeConstants::CRHBYTES);
       }
 
-      std::unique_ptr<StreamCipher> XOF_128(std::span<const uint8_t> seed, uint16_t nonce) const {
+      std::unique_ptr<Botan::XOF> XOF_128(std::span<const uint8_t> seed, uint16_t nonce) const {
          return this->m_symmetric_primitives->XOF(Dilithium_Symmetric_Primitives::XofType::k128, seed, nonce);
       }
 
-      std::unique_ptr<StreamCipher> XOF_256(std::span<const uint8_t> seed, uint16_t nonce) const {
+      std::unique_ptr<Botan::XOF> XOF_256(std::span<const uint8_t> seed, uint16_t nonce) const {
          return this->m_symmetric_primitives->XOF(Dilithium_Symmetric_Primitives::XofType::k256, seed, nonce);
       }
 
diff --git a/src/lib/pubkey/kyber/kyber/info.txt b/src/lib/pubkey/kyber/kyber/info.txt
index 696581386..6c787e458 100644
--- a/src/lib/pubkey/kyber/kyber/info.txt
+++ b/src/lib/pubkey/kyber/kyber/info.txt
@@ -8,8 +8,9 @@ name -> "Kyber"
 
 <requires>
 kyber_common
+sha3
 shake
-shake_cipher
+shake_xof
 </requires>
 
 <header:internal>
diff --git a/src/lib/pubkey/kyber/kyber/kyber_modern.h b/src/lib/pubkey/kyber/kyber/kyber_modern.h
index 4c8943f7e..15faa3c17 100644
--- a/src/lib/pubkey/kyber/kyber/kyber_modern.h
+++ b/src/lib/pubkey/kyber/kyber/kyber_modern.h
@@ -10,12 +10,12 @@
 #define BOTAN_KYBER_MODERN_H_
 
 #include <botan/hash.h>
-#include <botan/stream_cipher.h>
+#include <botan/xof.h>
 
 #include <botan/internal/kyber_symmetric_primitives.h>
 #include <botan/internal/shake.h>
-#include <botan/internal/shake_cipher.h>
 
+#include <array>
 #include <memory>
 #include <vector>
 
@@ -26,7 +26,8 @@ class Kyber_Modern_Symmetric_Primitives : public Kyber_Symmetric_Primitives {
       Kyber_Modern_Symmetric_Primitives() :
             m_sha3_512(HashFunction::create_or_throw("SHA-3(512)")),
             m_sha3_256(HashFunction::create_or_throw("SHA-3(256)")),
-            m_shake256_256(HashFunction::create_or_throw("SHAKE-256(256)")) {}
+            m_shake256_256(HashFunction::create_or_throw("SHAKE-256(256)")),
+            m_shake128(Botan::XOF::create_or_throw("SHAKE-128")) {}
 
       std::unique_ptr<HashFunction> G() const override { return m_sha3_512->new_object(); }
 
@@ -34,30 +35,14 @@ class Kyber_Modern_Symmetric_Primitives : public Kyber_Symmetric_Primitives {
 
       std::unique_ptr<HashFunction> KDF() const override { return m_shake256_256->new_object(); }
 
-      std::unique_ptr<Kyber_XOF> XOF(std::span<const uint8_t> seed) const override {
-         class Kyber_Modern_XOF final : public Kyber_XOF {
-            public:
-               Kyber_Modern_XOF(std::span<const uint8_t> seed) : m_cipher(std::make_unique<SHAKE_128_Cipher>()) {
-                  m_key.reserve(seed.size() + 2);
-                  m_key.insert(m_key.end(), seed.begin(), seed.end());
-                  m_key.push_back(0);
-                  m_key.push_back(0);
-               }
+      Botan::XOF& XOF(std::span<const uint8_t> seed, std::tuple<uint8_t, uint8_t> matrix_position) const override {
+         m_shake128->clear();
+         m_shake128->update(seed);
 
-               void set_position(const std::tuple<uint8_t, uint8_t>& matrix_position) override {
-                  m_key[m_key.size() - 2] = std::get<0>(matrix_position);
-                  m_key[m_key.size() - 1] = std::get<1>(matrix_position);
-                  m_cipher->set_key(m_key);
-               }
-
-               void write_output(std::span<uint8_t> out) override { m_cipher->write_keystream(out.data(), out.size()); }
-
-            private:
-               std::unique_ptr<StreamCipher> m_cipher;
-               secure_vector<uint8_t> m_key;
-         };
-
-         return std::make_unique<Kyber_Modern_XOF>(seed);
+         const std::array<uint8_t, 2> matrix_position_buffer{std::get<0>(matrix_position),
+                                                             std::get<1>(matrix_position)};
+         m_shake128->update(matrix_position_buffer);
+         return *m_shake128;
       }
 
       secure_vector<uint8_t> PRF(std::span<const uint8_t> seed,
@@ -73,6 +58,7 @@ class Kyber_Modern_Symmetric_Primitives : public Kyber_Symmetric_Primitives {
       std::unique_ptr<HashFunction> m_sha3_512;
       std::unique_ptr<HashFunction> m_sha3_256;
       std::unique_ptr<HashFunction> m_shake256_256;
+      std::unique_ptr<Botan::XOF> m_shake128;
 };
 
 }  // namespace Botan
diff --git a/src/lib/pubkey/kyber/kyber_90s/info.txt b/src/lib/pubkey/kyber/kyber_90s/info.txt
index d935286f4..2190fa573 100644
--- a/src/lib/pubkey/kyber/kyber_90s/info.txt
+++ b/src/lib/pubkey/kyber/kyber_90s/info.txt
@@ -8,8 +8,7 @@ name -> "Kyber 90s"
 
 <requires>
 kyber_common
-aes
-ctr
+aes_crystals_xof
 sha2_32
 sha2_64
 </requires>
diff --git a/src/lib/pubkey/kyber/kyber_90s/kyber_90s.h b/src/lib/pubkey/kyber/kyber_90s/kyber_90s.h
index 52fda8f0e..cebced2a8 100644
--- a/src/lib/pubkey/kyber/kyber_90s/kyber_90s.h
+++ b/src/lib/pubkey/kyber/kyber_90s/kyber_90s.h
@@ -10,7 +10,7 @@
 #define BOTAN_KYBER_90S_H_
 
 #include <botan/hash.h>
-#include <botan/stream_cipher.h>
+#include <botan/internal/aes_crystals_xof.h>
 
 #include <botan/internal/kyber_symmetric_primitives.h>
 
@@ -24,7 +24,8 @@ class Kyber_90s_Symmetric_Primitives : public Kyber_Symmetric_Primitives {
       Kyber_90s_Symmetric_Primitives() :
             m_sha512(HashFunction::create_or_throw("SHA-512")),
             m_sha256(HashFunction::create_or_throw("SHA-256")),
-            m_aes256_ctr(StreamCipher::create_or_throw("CTR-BE(AES-256)")) {}
+            m_aes256_ctr_xof(std::make_unique<AES_256_CTR_XOF>()),
+            m_aes256_ctr_prf(std::make_unique<AES_256_CTR_XOF>()) {}
 
       std::unique_ptr<HashFunction> G() const override { return m_sha512->new_object(); }
 
@@ -32,40 +33,27 @@ class Kyber_90s_Symmetric_Primitives : public Kyber_Symmetric_Primitives {
 
       std::unique_ptr<HashFunction> KDF() const override { return m_sha256->new_object(); }
 
-      std::unique_ptr<Kyber_XOF> XOF(std::span<const uint8_t> seed) const override {
-         class Kyber_90s_XOF final : public Kyber_XOF {
-            public:
-               Kyber_90s_XOF(std::unique_ptr<StreamCipher> cipher, std::span<const uint8_t> seed) :
-                     m_cipher(std::move(cipher)) {
-                  m_cipher->set_key(seed);
-               }
-
-               void set_position(const std::tuple<uint8_t, uint8_t>& matrix_position) override {
-                  std::array<uint8_t, 12> iv = {std::get<0>(matrix_position), std::get<1>(matrix_position), 0};
-                  m_cipher->set_iv(iv.data(), iv.size());
-               }
-
-               void write_output(std::span<uint8_t> out) override { m_cipher->write_keystream(out.data(), out.size()); }
-
-            private:
-               std::unique_ptr<StreamCipher> m_cipher;
-         };
-
-         return std::make_unique<Kyber_90s_XOF>(m_aes256_ctr->new_object(), seed);
+      Botan::XOF& XOF(std::span<const uint8_t> seed, std::tuple<uint8_t, uint8_t> mpos) const override {
+         m_aes256_ctr_xof->clear();
+         const std::array<uint8_t, 12> iv{std::get<0>(mpos), std::get<1>(mpos), 0};
+         m_aes256_ctr_xof->start(iv, seed);
+         return *m_aes256_ctr_xof;
       }
 
       secure_vector<uint8_t> PRF(std::span<const uint8_t> seed,
                                  const uint8_t nonce,
                                  const size_t outlen) const override {
-         m_aes256_ctr->set_key(seed);
-         m_aes256_ctr->set_iv(std::array<uint8_t, 12>{nonce, 0});
-         return m_aes256_ctr->keystream_bytes(outlen);
+         m_aes256_ctr_prf->clear();
+         const std::array<uint8_t, 12> nonce_buffer{nonce, 0};
+         m_aes256_ctr_prf->start(nonce_buffer, seed);
+         return m_aes256_ctr_prf->output(outlen);
       }
 
    private:
       std::unique_ptr<HashFunction> m_sha512;
       std::unique_ptr<HashFunction> m_sha256;
-      std::unique_ptr<StreamCipher> m_aes256_ctr;
+      std::unique_ptr<AES_256_CTR_XOF> m_aes256_ctr_xof;
+      std::unique_ptr<AES_256_CTR_XOF> m_aes256_ctr_prf;
 };
 
 }  // namespace Botan
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.cpp b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
index 320a0e1d1..107e93f28 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber.cpp
+++ b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
@@ -20,7 +20,6 @@
 #include <botan/pubkey.h>
 #include <botan/rng.h>
 #include <botan/secmem.h>
-#include <botan/stream_cipher.h>
 
 #include <botan/internal/ct_utils.h>
 #include <botan/internal/fmt.h>
@@ -210,7 +209,9 @@ class KyberConstants {
 
       std::unique_ptr<HashFunction> KDF() const { return m_symmetric_primitives->KDF(); }
 
-      std::unique_ptr<Kyber_XOF> XOF(std::span<const uint8_t> seed) const { return m_symmetric_primitives->XOF(seed); }
+      Botan::XOF& XOF(std::span<const uint8_t> seed, std::tuple<uint8_t, uint8_t> matrix_position) const {
+         return m_symmetric_primitives->XOF(seed, matrix_position);
+      }
 
       secure_vector<uint8_t> PRF(std::span<const uint8_t> seed, const uint8_t nonce, const size_t outlen) const {
          return m_symmetric_primitives->PRF(seed, nonce, outlen);
@@ -441,38 +442,13 @@ class Polynomial {
        * Run rejection sampling on uniform random bytes to generate uniform
        * random integers mod q.
        */
-      static Polynomial sample_rej_uniform(Kyber_XOF& xof) {
-         class XOF_Reader {
-            public:
-               XOF_Reader(Kyber_XOF& xof) : m_xof(xof), m_buf(), m_buf_pos(m_buf.size()) {}
-
-               std::array<uint8_t, 3> next_3_bytes() {
-                  if(m_buf_pos == m_buf.size()) {
-                     m_xof.write_output(m_buf);
-                     m_buf_pos = 0;
-                  }
-
-                  BOTAN_ASSERT_NOMSG(m_buf_pos + 3 <= m_buf.size());
-
-                  std::array<uint8_t, 3> buf{m_buf[m_buf_pos], m_buf[m_buf_pos + 1], m_buf[m_buf_pos + 2]};
-
-                  m_buf_pos += 3;
-
-                  return buf;
-               }
-
-            private:
-               Kyber_XOF& m_xof;
-               std::array<uint8_t, 3 * 64> m_buf;
-               size_t m_buf_pos;
-         };
-
-         auto xof_reader = XOF_Reader(xof);
+      static Polynomial sample_rej_uniform(XOF& xof) {
          Polynomial p;
 
          size_t count = 0;
          while(count < p.size()) {
-            auto buf = xof_reader.next_3_bytes();
+            std::array<uint8_t, 3> buf;
+            xof.output(buf);
 
             const uint16_t val0 = ((buf[0] >> 0) | (static_cast<uint16_t>(buf[1]) << 8)) & 0xFFF;
             const uint16_t val1 = ((buf[1] >> 4) | (static_cast<uint16_t>(buf[2]) << 4)) & 0xFFF;
@@ -709,13 +685,10 @@ class PolynomialMatrix {
 
          PolynomialMatrix matrix(mode);
 
-         auto xof = mode.XOF(seed);
-
          for(uint8_t i = 0; i < mode.k(); ++i) {
             for(uint8_t j = 0; j < mode.k(); ++j) {
                const auto pos = (transposed) ? std::tuple(i, j) : std::tuple(j, i);
-               xof->set_position(pos);
-               matrix.m_mat[i][j] = Polynomial::sample_rej_uniform(*xof);
+               matrix.m_mat[i][j] = Polynomial::sample_rej_uniform(mode.XOF(seed, pos));
             }
          }
 
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber_symmetric_primitives.h b/src/lib/pubkey/kyber/kyber_common/kyber_symmetric_primitives.h
index f4cbff236..37fe6c5c9 100644
--- a/src/lib/pubkey/kyber/kyber_common/kyber_symmetric_primitives.h
+++ b/src/lib/pubkey/kyber/kyber_common/kyber_symmetric_primitives.h
@@ -11,7 +11,6 @@
 
 #include <botan/hash.h>
 #include <botan/secmem.h>
-#include <botan/stream_cipher.h>
 
 #include <memory>
 #include <span>
@@ -20,14 +19,7 @@
 
 namespace Botan {
 
-class Kyber_XOF {
-   public:
-      virtual ~Kyber_XOF() = default;
-
-      virtual void set_position(const std::tuple<uint8_t, uint8_t>& matrix_position) = 0;
-
-      virtual void write_output(std::span<uint8_t> out) = 0;
-};
+class XOF;
 
 /**
  * Adapter class that uses polymorphy to distinguish
@@ -41,7 +33,7 @@ class Kyber_Symmetric_Primitives {
       virtual std::unique_ptr<HashFunction> H() const = 0;
       virtual std::unique_ptr<HashFunction> KDF() const = 0;
 
-      virtual std::unique_ptr<Kyber_XOF> XOF(std::span<const uint8_t> seed) const = 0;
+      virtual Botan::XOF& XOF(std::span<const uint8_t> seed, std::tuple<uint8_t, uint8_t> matrix_position) const = 0;
 
       virtual secure_vector<uint8_t> PRF(std::span<const uint8_t> seed, uint8_t nonce, size_t outlen) const = 0;
 };
diff --git a/src/lib/xof/aes_crystals_xof/aes_crystals_xof.cpp b/src/lib/xof/aes_crystals_xof/aes_crystals_xof.cpp
new file mode 100644
index 000000000..c8e93b258
--- /dev/null
+++ b/src/lib/xof/aes_crystals_xof/aes_crystals_xof.cpp
@@ -0,0 +1,52 @@
+/*
+ * XOF based on AES-256/CTR for CRYSTALS Kyber/Dilithium 90s-modes
+ * (C) 2023 Jack Lloyd
+ *     2023 René Meusel - Rohde & Schwarz Cybersecurity
+ *
+ * Botan is released under the Simplified BSD License (see license.txt)
+ */
+
+#include <botan/internal/aes_crystals_xof.h>
+
+#include <botan/exceptn.h>
+#include <botan/stream_cipher.h>
+#include <botan/internal/fmt.h>
+
+namespace Botan {
+
+AES_256_CTR_XOF::AES_256_CTR_XOF() : m_stream_cipher(StreamCipher::create_or_throw(name())) {}
+
+AES_256_CTR_XOF::~AES_256_CTR_XOF() = default;
+
+void AES_256_CTR_XOF::reset() {
+   m_stream_cipher->clear();
+}
+
+void AES_256_CTR_XOF::start_msg(std::span<const uint8_t> iv, std::span<const uint8_t> key) {
+   m_stream_cipher->set_key(key);
+   m_stream_cipher->set_iv(iv);
+}
+
+bool AES_256_CTR_XOF::valid_salt_length(size_t iv_length) const {
+   return m_stream_cipher->valid_iv_length(iv_length);
+}
+
+Key_Length_Specification AES_256_CTR_XOF::key_spec() const {
+   return m_stream_cipher->key_spec();
+}
+
+std::unique_ptr<XOF> AES_256_CTR_XOF::copy_state() const {
+   throw Not_Implemented(fmt("Copying the state of XOF {} is not implemented", name()));
+}
+
+void AES_256_CTR_XOF::add_data(std::span<const uint8_t> input) {
+   if(!input.empty()) {
+      throw Not_Implemented(fmt("XOF {} does not support data input", name()));
+   }
+}
+
+void AES_256_CTR_XOF::generate_bytes(std::span<uint8_t> output) {
+   m_stream_cipher->write_keystream(output);
+}
+
+}  // namespace Botan
diff --git a/src/lib/xof/aes_crystals_xof/aes_crystals_xof.h b/src/lib/xof/aes_crystals_xof/aes_crystals_xof.h
new file mode 100644
index 000000000..50e2ad1ba
--- /dev/null
+++ b/src/lib/xof/aes_crystals_xof/aes_crystals_xof.h
@@ -0,0 +1,69 @@
+/*
+ * XOF based on AES-256/CTR for CRYSTALS Kyber/Dilithium 90s-modes
+ * (C) 2023 Jack Lloyd
+ *     2023 René Meusel - Rohde & Schwarz Cybersecurity
+ *
+ * Botan is released under the Simplified BSD License (see license.txt)
+ */
+
+#ifndef BOTAN_AES_CRYSTALS_XOF_H_
+#define BOTAN_AES_CRYSTALS_XOF_H_
+
+#include <botan/secmem.h>
+#include <botan/xof.h>
+
+namespace Botan {
+
+class StreamCipher;
+
+/**
+ * XOF implementation for Kyber/Dilithium 90s-modes based on
+ * AES-256 in counter mode.
+ *
+ * This is an internal class that is not meant for consumption
+ * by library users. It is therefore not registered in XOF::create().
+ */
+class BOTAN_TEST_API AES_256_CTR_XOF final : public XOF {
+   public:
+      AES_256_CTR_XOF();
+      ~AES_256_CTR_XOF() override;
+
+      void reset() override;
+
+      std::string name() const override { return "CTR-BE(AES-256)"; }
+
+      /**
+       * Checks that the given @p iv_length is compatible with this XOF
+       */
+      bool valid_salt_length(size_t iv_length) const override;
+      Key_Length_Specification key_spec() const override;
+
+      size_t block_size() const override { return 16; }
+
+      std::unique_ptr<XOF> copy_state() const override;
+
+      std::unique_ptr<XOF> new_object() const override { return std::make_unique<AES_256_CTR_XOF>(); }
+
+      bool accepts_input() const override { return false; }
+
+   private:
+      /**
+       * Sets the @p IV and @p key of the underlying AES-256/CTR object.
+       * Do not call AES_256_CTR_XOF::update(), on this object!
+       */
+      void start_msg(std::span<const uint8_t> iv = {}, std::span<const uint8_t> key = {}) override;
+
+      /**
+       * @throws Not_Implemented, use XOF::start() instead of XOF::update()
+       */
+      void add_data(std::span<const uint8_t>) override;
+
+      void generate_bytes(std::span<uint8_t> output) override;
+
+   private:
+      std::unique_ptr<StreamCipher> m_stream_cipher;
+};
+
+}  // namespace Botan
+
+#endif
diff --git a/src/lib/xof/aes_crystals_xof/info.txt b/src/lib/xof/aes_crystals_xof/info.txt
new file mode 100644
index 000000000..7fe10533e
--- /dev/null
+++ b/src/lib/xof/aes_crystals_xof/info.txt
@@ -0,0 +1,14 @@
+<defines>
+AES_CRYSTALS_XOF -> 20230816
+</defines>
+
+<module_info>
+name -> "CRYSTALS XOF"
+brief -> "XOF used in Kyber 90s and Dilithium AES"
+type -> "Internal"
+</module_info>
+
+<requires>
+aes
+ctr
+</requires>


Test patch:
diff --git a/src/tests/data/xof/aes256_ctr.vec b/src/tests/data/xof/aes256_ctr.vec
new file mode 100644
index 000000000..234ee87b1
--- /dev/null
+++ b/src/tests/data/xof/aes256_ctr.vec
@@ -0,0 +1,136 @@
+[CTR-BE(AES-256)]
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f8
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f840
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f840ceb3995f29ab255dd43d
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f840ceb3995f29ab255dd43db61a8eb5d54e0e9f1a25c5514719e162
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f840ceb3995f29ab255dd43db61a8eb5d54e0e9f1a25c5514719e16254
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f840ceb3995f29ab255dd43db61a8eb5d54e0e9f1a25c5514719e162549e
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddeeff
+In =
+Out = da57ba59f840ceb3995f29ab255dd43db61a8eb5d54e0e9f1a25c5514719e162549e2af73b87b11deca10cdd15650f1567029ac73ed19004f7e71e68a65f1c49
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccddee
+In =
+Out = 81D2ACE4208C44ECDD9EEAFDA0D46402C55AAE4AEDA6042BF7C53FBA7E146AA0E771701DCF448AA92A6638AE3DB034064443C5EBC3B5E85B016A2B606C3CFC2A
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbccdd
+In =
+Out = 42CAD864F6BF6F16DB6D3469F0B595012D7047B93DA343E11CB2529D2A3B002D9D9CB1011E58374FF5D2D275D5A4E6A77262F0E623EBDD12798AF1C82D14E40A
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabbcc
+In =
+Out = 7F47B334ACC62CC4EAAA49D82A552937FF751464ECFEFDC78CB20D43293FA29333FDDFAC40D4D868BC9B92DE8568757315A48835AD55D03A587D6A2E89A4E239
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aabb
+In =
+Out = 7C53CE287F825557C0C24AB2C2BF52C926E10B90940C4CA21B9A075869DEEAEEA08571F194DCD1F25859EE9A319209614604BA0F0B28F5C409F759501E433CB0
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900aa
+In =
+Out = E968DB960BB9141C5B4F48B9511BBFC1D896205AAB4CBA47A44C7345912B186B62E4C14BB0C56C93F251E08BA0CDC58D83FB7303CC831A8041C2AE5EE12C3CF2
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677889900
+In =
+Out = 5483CDB99217E8A410707941C3D38F4B06446CAF98190D1F86F3EB381571F38EFA3BC60D2AC09348023609431C0929F63BD46C32B0696F6E09415A83AB0F5E0C
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 112233445566778899
+In =
+Out = 5483CDB99217E8A410707941C3D38F4B06446CAF98190D1F86F3EB381571F38EFA3BC60D2AC09348023609431C0929F63BD46C32B0696F6E09415A83AB0F5E0C
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 1122334455667788
+In =
+Out = 6E6160352B50512090B95C9E0E0A5FED4172153BFDFD38AF008F4D15E5C3F4090F58BDC1506C62DC93376E775F4B206F3839E88C70A66068AA390BA569E76161
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344556677
+In =
+Out = 2C01B53715BB09D90BD910CBB9C81D915862F7610AB16A7AF3C9E2EFB9DA4132C14D0C72874023BC743F686DE42CA0BD7D93C3A48350E87890E923E78F2E7F99
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 112233445566
+In =
+Out = BDF9EBEC67E683554A744AE0958B75B65C053EBD0679C2EEA4AFA7F5C3AEDBD95F1E814E3836783666CC67B82660B12DDED4C608CB8AE4A293DB4B4D8FA23AE6
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 1122334455
+In =
+Out = AAC23439A86AC1E655358BA47DE94595A61598A4A44FF921354F2CD67FFC65F573C8FF59883070F95A0F59FD11316D76129EAFCE624ED8FBF187E4255FF0A9A9
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11223344
+In =
+Out = 724A9753713A0F87BB687F8632585396C160046EFDB158366C09BD3C3AF4D23909A40637CBE0F02A919317EB9DE46FF15C93C37A9B8FA5D211EF223628D82328
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 112233
+In =
+Out = CEA2CABE1650909B8DAA9FE0E4534CB950D94D3303248F59249714BD88C69D71A3116E455E242E99BB3C8B1B1AEA278FDB8C54D6BE04279728E2C35E0CC33FA4
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 1122
+In =
+Out = 2EE27141BC79C6B4D4D8D67FCF5AD5A6E0E91972412D385042A5175DB920445AAEA27E6D7BDC45D12764AB2AA14B0A632723163ABD2FEB70655E4CBAE4F9B471
+
+Key = aabb07488ff9edd05d6a603b7791b60a16d45093608f1badc0c9cc9a9154f215
+Salt = 11
+In =
+Out = A2DBF3EAF9A46943E75464B106E36FF2C3908FCF44F2749C2ABB305C5A6BC321E45C9BEFCD17413D58A80112F957FE2AED17334AAD96EA4EF14EDBF328CE968C
+
+Key = d8405f29add43db61a8eb5d562e2af7eca115650f1567029ac73e4f71e6f1c49
+Salt =
+In =
+Out =  06dc17c6588920a2641806e8cfd759720bcbfbb6c26220a5d0b2dcc876dbeb3acd121791ea385379f270fce012c04ce158089e29bdec3c25188041224c6e4697af44702723f3
diff --git a/src/tests/test_xof.cpp b/src/tests/test_xof.cpp
index f7aa56212..2f825d716 100644
--- a/src/tests/test_xof.cpp
+++ b/src/tests/test_xof.cpp
@@ -17,6 +17,12 @@
       // and is therefore not registered in the XOF::create() factory.
       #include <botan/internal/cshake_xof.h>
    #endif
+
+   #if defined(BOTAN_HAS_AES_CRYSTALS_XOF)
+      // This XOF implementation is not exposed via the library's public interface
+      // and is therefore not registered in the XOF::create() factory.
+      #include <botan/internal/aes_crystals_xof.h>
+   #endif
 #endif
 
 namespace Botan_Tests {
@@ -45,6 +51,11 @@ class XOF_Tests final : public Text_Based_Test {
             }
    #endif
 
+   #if defined(BOTAN_HAS_AES_CRYSTALS_XOF)
+            if(algo == "CTR-BE(AES-256)") {
+               return {"base"};
+            }
+   #endif
             return provider_filter(Botan::XOF::providers(algo));
          }();
 
@@ -63,6 +74,12 @@ class XOF_Tests final : public Text_Based_Test {
                   return std::make_unique<Botan::cSHAKE_256_XOF>(name);
                }
    #endif
+
+   #if defined(BOTAN_HAS_AES_CRYSTALS_XOF)
+               if(algo == "CTR-BE(AES-256)") {
+                  return std::make_unique<Botan::AES_256_CTR_XOF>();
+               }
+   #endif
                return Botan::XOF::create(algo, provider_ask);
             }();
 
@@ -165,18 +182,30 @@ class XOF_Tests final : public Text_Based_Test {
       std::vector<Test::Result> run_final_tests() override {
          return {
    #if defined(BOTAN_HAS_CSHAKE_XOF)
-            Botan_Tests::CHECK("cSHAKE without a name", [](Test::Result& result) {
-               std::vector<std::unique_ptr<Botan::XOF>> cshakes;
-               cshakes.push_back(std::make_unique<Botan::cSHAKE_128_XOF>(""));
-               cshakes.push_back(std::make_unique<Botan::cSHAKE_256_XOF>(""));
-
-               for(auto& cshake : cshakes) {
-                  result.confirm("cSHAKE without a name rejects empty salt", !cshake->valid_salt_length(0));
-                  result.confirm("cSHAKE without a name requests at least one byte of salt",
-                                 cshake->valid_salt_length(1));
-                  result.test_throws("cSHAKE without a name throws without salt", [&]() { cshake->start({}); });
-               }
-            }),
+            Botan_Tests::CHECK(
+               "cSHAKE without a name",
+               [](Test::Result& result) {
+                  std::vector<std::unique_ptr<Botan::XOF>> cshakes;
+                  cshakes.push_back(std::make_unique<Botan::cSHAKE_128_XOF>(""));
+                  cshakes.push_back(std::make_unique<Botan::cSHAKE_256_XOF>(""));
+
+                  for(auto& cshake : cshakes) {
+                     result.confirm("cSHAKE without a name rejects empty salt", !cshake->valid_salt_length(0));
+                     result.confirm("cSHAKE without a name requests at least one byte of salt",
+                                    cshake->valid_salt_length(1));
+                     result.test_throws("cSHAKE without a name throws without salt", [&]() { cshake->start({}); });
+                  }
+               }),
+   #endif
+   #if defined(BOTAN_HAS_AES_CRYSTALS_XOF)
+               Botan_Tests::CHECK("AES-256/CTR XOF failure modes", [](Test::Result& result) {
+                  Botan::AES_256_CTR_XOF aes_xof;
+                  result.test_throws("AES-256/CTR XOF throws for empty key", [&]() { aes_xof.start({}, {}); });
+                  result.test_throws("AES-256/CTR XOF throws for too long key",
+                                     [&]() { aes_xof.start({}, std::vector<uint8_t>(33)); });
+                  result.test_throws("AES-256/CTR XOF throws for too long IV",
+                                     [&]() { aes_xof.start(std::vector<uint8_t>(17), std::vector<uint8_t>(32)); });
+               }),
    #endif
          };
       }