Castella: A heavyweight AES-based permutation and the hash functions built on it

This C++ library implements a heavyweight permutation function using AES CPU instructions, plus a duplex/sponge, parallel tree hashing, a keyed MAC, and a PRNG on top.

Heavyweight is the deliberate opposite of lightweight cryptography: a wide 256-byte state and a hardware AES round function, not a small-state ARX design. It describes the design, not the speed — the tree hashes rival, and in one case roughly double, multithreaded b3sum on page-cache-hot files.

Status. Castella is a personal research project — a permutation and hash design that has not been standardized, externally reviewed, or cryptanalyzed by anyone but its author. Do not use it where security matters. See SPEC.md and its security claims and non-claims.

The Castella Permutation Function

The Castella permutation function operates on a state array of N blocks, where N ∈ {2, 4, 8, 16} and each block is 16 bytes fitting in a SIMD register (e.g., x86-64 XMM, ARM NEON). It uses AES hardware instructions and matrix transpositions to achieve full diffusion of the state array.

Each round of the permutation does the following:

1. Perform 3 rounds of AES encryption on each element of the state array, where each element in each AES round uses a distinct round constant as its AES round key.
   • The number of AES rounds was empirically determined. See aes_enc_0-aes_num_rounds.cpp.
2. Transpose the state, treating it as a 16×16 matrix of bytes.

The minimum number of permutation rounds was empirically determined. See permute-num_rounds.cpp.

Round Constants

The round constants are the successive states of a 128-bit Galois LFSR with the GCM reduction polynomial (x¹²⁸ + x⁷ + x² + x + 1), stepped 128 times between constants. The LFSR seed — and the first round constant — is expand 16-byte c.

The round constants are used as AES round keys. A distinct round constant is used for every combination of permutation round, AES round, and state block, so no two blocks ever apply the same transformation. The generator is deliberately unrelated to the AES round function so that the round constants share no structure with it.

The round constants are generated at compile time. Their number equals Castella::NUM_ROUNDS_MAX × Castella::AES_NUM_ROUNDS × Castella::B_MAX — 16 × 3 × 16 = 768. All three values are fixed by SPEC.md; any other value produces different digests.

The Castella Duplex Construction

The Castella duplex class implements a customizable duplex/sponge construction inspired by Keccak (which won the SHA-3 competition). It is byte-oriented (i.e., all input, output, and padding are in whole bytes), unlike SHA-3, which is bit-oriented.

An instance of a duplex can be used as a hash object or a pseudo-random number generator (PRNG).

The source code is liberally documented with many annotations and excerpts from the design and development of Keccak. Refer to it for details.

A standalone specification — the permutation, round constants, duplex, tree mode, MAC construction, and Compress-Castella, readable without the C++ — is in SPEC.md. Its completeness is proven by research/spec-conformance.py, an independent pure-Python implementation written from the specification alone that reproduces every digest in tests/KAT.txt.

SPEC.md also states the security claims and non-claims: a falsifiable flat sponge claim in the Keccak tradition, the claimed security strengths (matching the SHA-3 levels at equal capacity), the proven mode reductions, and the supporting evidence. research/VERIFYING-CLAIMS.md maps every claim to the exact commands that reproduce its evidence, and CHALLENGES.md publishes reduced-round collision and preimage targets for anyone who wants to attack the design.

Capacity and Rate

The duplex state of B = 16 blocks is partitioned into an inner part (the capacity) of C blocks and an outer part (the rate) of R = B-C blocks, where 2 ≤ C ≤ B/2 and C must be even.

The capacity is the security parameter: the claimed level is 64·C bits, half the capacity of 128·C bits. Paired with a digest size it reproduces the SHA-3 levels exactly, and the castella program picks the capacity from the digest size by the rule that produces this mapping (smallest even C with 16·C ≥ 2n bytes for an n-byte digest):

digest size	C	capacity	collision / preimage / 2nd-preimage	matches
28 bytes	4	512	112 / 224 / 224	SHA3-224 (448-bit capacity, so this maps upward)
32 bytes	4	512	128 / 256 / 256	SHA3-256
48 bytes	6	768	192 / 384 / 384	SHA3-384
64 bytes	8	1024	256 / 512 / 512	SHA3-512

Round counts appear nowhere in that table — as in SHA-3, they are safety margin rather than a security parameter. SPEC.md derives these strengths from the claim, states which (C, num_rounds) instances the claim covers, and gives the margin rationale behind the round counts.

Instantiation Parameters

An instance of Castella::Duplex takes these parameters:

type	name	default value	constraint	description
uint8_t	capacity_blocks	none	∈ [Castella::Duplex::C_MIN, Castella::Duplex::C_MAX]	The size (in blocks) of the capacity
uint8_t	num_rounds	none	∈ [Castella::NUM_ROUNDS_MIN, Castella::NUM_ROUNDS_MAX]	The number of rounds to perform in the Castella permutation function
std::byte	input_suffix	0	none	The byte to append to the input buffer before squeezing
std::string_view	function_name	""	none	The function-name byte string
std::string_view	customization_str	""	none	The customization byte string

The number of rounds determines the safety margin. The capacity size determines the security level. See Yes, this is Keccak!.

Adding/Absorbing Input

Input data may be given in the form of a byte span (i.e., std::span<const std::byte> — the primary interface) or raw data (i.e., a const void*, size_t pair, implemented in terms of the byte-span form) with these member functions:

• add
  • Add the given data to the input buffer.
• add_left_encoded
  • Add the left-encoded length of the given data, followed by the data itself, to the input buffer.
• add_right_encoded
  • Add the given data, followed by its right-encoded length, to the input buffer.

When the input buffer is full, it is absorbed (via XOR) into the outer part of the state.

See The sponge and duplex constructions to learn how the sponge and duplex constructions work.

Padding Scheme

The duplex uses the pad10*1 padding rule.

Input padding bytes are added before every squeeze_bytes, even if 0 bytes are squeezed.

The padding rule may be explicitly applied via the apply_padding_rule() member function.

Squeezing Output

The squeeze_bytes member function performs the following:

1. Append the input suffix to the input buffer.
2. Apply the padding rule.
3. Return the first n bytes of the outer state as a std::vector<std::byte>, where n is an integer in the interval [0, get_rate_size_bytes()].
   • Typical values of n are 32, 48, or 64.
   • The default value of n is get_capacity_size_bytes() / 2.
   • An n outside that interval is clamped into it rather than rejected, so a too-large n yields get_rate_size_bytes() bytes and a negative n yields none. Steps 1 and 2 still happen either way, so any call advances the state. This leniency is a convenience of the C++ API: the specification defines squeeze(n) only for 0 ≤ n ≤ 16R.

Tree Hashing

A byte-stream hash is inherently sequential, so a single duplex can never use more than one CPU core. The generic tree-hash layer (Castella::HashTree) restores parallelism with a KangarooTwelve-style two-level tree: the input is split into fixed-size chunks, each chunk after the first is hashed to a fixed-size chaining value by an independent leaf node, and the chaining values are absorbed by a final node in chunk order. The digest depends only on the tree geometry, the node parameters, and the input bytes — never on the thread count or how the input was split across add() calls.

Castella::DuplexTree is the tree instantiated with Castella::Duplex nodes. (The cch hash program uses a second instantiation over a faster non-cryptographic compression node.)

The castella command-line program wraps DuplexTree and adds a keyed MAC mode (--key-file; KMAC's structure at tree scale). For the higher-level SP 800-185 constructions built directly on a single Duplex — cSHAKE-, KMAC-, TupleHash-, and ParallelHash-like functions — see the examples/ programs.

VAES Optimizations

On x86-64 processors with VAES, two execution-level optimizations apply (neither ever affects a digest):

• Register-resident permutation. The permutation (every supported state size N) runs in a folded representation that stays in N/2 ymm registers for all rounds (element j holds blocks j and j+N/2, one per 128-bit lane), instead of bouncing the state through memory between the AES rounds' 256-bit accesses and the transpose's 128-bit accesses — a pattern that defeats store-to-load forwarding. For the 16-block state used by Duplex, measured ~1.7× faster (a plain duplex absorbs at ~3.2 GiB/s per core instead of ~1.9). Measured by research/permute_folded-benchmark.cpp (results in research/README.md); the absorb rates come directly from research/duplex-throughput-benchmark.cpp.
• Leaf batching. Both tree hashes process adjacent leaf chunks two at a time on one thread. DuplexTree packs two duplex states into the two 128-bit lanes of ymm registers (Castella::DuplexX2), where VAES applies an independent AES round per lane and the AVX2 unpack network transposes both 16×16 byte matrices at once without mixing the lanes (Castella::permute_x2); one paired permutation measures ~1.7× faster than two sequential (register-resident) permutations (research/permute_x2-benchmark.cpp). The cch tree instead interleaves two nodes' compression chains in one loop (compress_castella_hash_x2) — a single cch node is latency-bound, so the second state's chains fill the idle AES slots (a modest ~1.1× on pinned runs, measured by research/simd_compress-num_states-benchmark.cpp; see the findings in research/README.md). Pairing applies on every parallel path: batch workers, the inline (single-threaded) path, and the streaming pipeline, whose pool workers claim up to two adjacent ring slots per wake-up (streamed castella --no-mmap input at 2 threads reaches the producer-bound floor that previously needed 4).

All of these ratios are machine-dependent. To reproduce them, build research/ (see Building) and run bash run-benchmarks.bash there — it pins each benchmark to core 0 and saves raw results to research/results/. Benchmark on an otherwise idle machine.

Performance

Heavyweight does not mean slow. On a modern x86-64 Linux system, with VAES leaf batching and multiple threads:

• castella — the cryptographic DuplexTree — roughly matches fully-multithreaded b3sum on page-cache-hot files; some minimal-round configurations beat b2sum, sha1sum, and md5sum.
• cch — the same tree over faster non-cryptographic nodes — beats fully-multithreaded b3sum by about 2× on the same files, and single-threaded roughly matches XXH3.

These figures are machine-dependent; reproduce them with hash-programs/benchmark.hash-programs.bash (it uses hyperfine). See the speed FAQ for the fuller picture.

Dependencies

To build and use Castella

• GCC 14 or newer
  • C++23 features are used
  • clang++ is not supported
• An x86-64 or ARM64 processor with AES instructions
  • x86-64 is the only tested platform
  • ARM64 is supported in principle, and no ARM64 build has been checked against tests/KAT.txt

Building

The top-level Makefile recurses into the subdirectories:

• make — build the examples, the hash programs, and the tests
• make test — build and run every test suite, by delegating to each subdirectory's own test target: the fixed tests, the KAT file checker, the randomized equivalence tests, the folded-vs-generic permute comparison and the differential fuzzer (tests/); the examples (examples/); the correctness script (hash-programs/); and the spec-conformance model (research/). The two Python steps need python3, and say so rather than failing obscurely if it is missing
• make everything — additionally build research/ (needs google-benchmark) and http-prng-service/ (needs spdlog; httplib.h is committed in-tree, re-downloaded by the Makefile only if missing)
• make BUILD=debug — build with ASan and UBSan instead of -O3 -flto=auto, and with the internal assertions enabled (see config.mk). BUILD is a variable rather than a target, so it applies to whatever goals are given: make BUILD=debug test and make BUILD=debug everything are debug builds throughout. Run make clean first when switching between release and debug — the two use the same binary names.
  • The assertions check internal invariants; they are not input validation, and they are compiled out of a release build, so no release behavior depends on them. Every user-reachable constraint — the Duplex constructor parameters, the hash programs' options — is checked by throwing instead, in every build. The exception is the deliberately unchecked accessors, where an assertion backs a documented narrow contract and a checked counterpart exists: fixed_vector::operator[] versus at(), unchecked_emplace_back() versus push_back().
• make test-san — run every test suite under the sanitizers, doing the make clean that switching build types requires: it cleans, builds BUILD=debug, and runs the suites with UBSan set to fail rather than only report. The sanitizer binaries are left in place afterward, so make clean again before building for release.
• make clean, make lint — recurse into every subdirectory

Each subdirectory also has its own Makefile with the same all/clean/lint targets, and the four with tests to run — tests/, examples/, hash-programs/, research/ — add test, so a single one can be worked on in isolation: make -C tests test builds and runs just that directory's suites. (research/'s test runs the pure-Python conformance script only, and so does not build the benchmarks or require google-benchmark.)

FAQ

What is a castella?

In real life, castella is the name of a type of sponge cake. https://en.wikipedia.org/wiki/Castella

Why did you choose the name castella?

I asked ChatGPT to suggest names of food that had the word sponge in them, or had sponge-like quality. I narrowed the choices to those based on sponge cake or similar desserts. Coincidentally, a castella cake may be large and rectangular, just like the Castella state array.

Why heavyweight?

It's the deliberate opposite of lightweight cryptography — the family of designs (Ascon and friends) built for constrained devices out of a small state and cheap ARX operations. Castella goes the other way on both axes:

1. A large state. 256 bytes! For comparison, the state size of SHA-3 is 200 bytes.
2. A hardware round function. It uses dedicated AES instructions instead of only ARX operations.

Heavyweight describes the design, not the speed: it assumes a CPU with an AES unit and spends it freely, so the tree hashes are fast.

Is this as fast as b3sum?

No! Nothing is as fast as b3sum!

But seriously, in my testing on a modern Linux x86-64 system, some configurations of Castella hash (with minimal rounds) are faster than b2sum, sha1sum, and md5sum, and (with VAES leaf batching and multiple threads) it roughly matches fully-multithreaded b3sum on page-cache-hot files. And Compress-Castella hash — the same tree structure built from much faster non-cryptographic nodes — beats fully-multithreaded b3sum by about 2× on the same files, and even single-threaded it roughly matches XXH3 (xxhsum -H3)!

Don't take my word for it: these comparisons come from hash-programs/benchmark.hash-programs.bash, which uses hyperfine to time castella and cch against b3sum, xxhsum, OpenSSL, and coreutils/uutils cksum on a 500 MiB file (hyperfine's warm-up runs make it page-cache-hot). Run it yourself — the results are machine-dependent.

Could Castella be considered a cryptographic hash function or a cryptographic primitive?

Not yet — it hasn't been scrutinized by others, and until it has been, the honest answer stays no. What exists now is a precise target for that scrutiny: SPEC.md states a falsifiable security claim with its supporting evidence, and CHALLENGES.md publishes reduced-round collision and preimage challenges. Although I myself can't break it. ¹

Don't roll your own crypto.

1. That's not a question.
2. I didn't roll anything. That is, I'm not using this for anything serious, and neither should you.

This project was started to satiate a curiosity about the sponge construction and SHA-3. Sometimes it's fun to build something just to learn how it works.

Why is the duplex input parameter capacity in blocks instead of bytes?

The capacity (C) determines the rate (R). The size of the input buffer is R blocks and it has an alignment of 1 block (i.e., 16 bytes).

If the unit of the capacity was bytes instead of blocks, the value would have to be a multiple of 16 anyways.

Repository Layout

directory	contents
include/	The Castella library headers (castella-permute.hpp, castella-duplex.hpp, castella-hash-tree.hpp, castella-duplex-tree.hpp, castella-duplex-x2.hpp) and supporting headers
examples/	Usage examples: cSHAKE-like, KMAC-like, TupleHash-like, and ParallelHash-like operations
tests/	Correctness tests
research/	Programs for empirically determining optimal parameters; benchmarks
hash-programs/	Command-line hash utilities (castella and cch)
http-prng-service/	HTTP server exposing a Castella-backed PRNG via /absorb and /squeeze endpoints

License

Castella is licensed under the Mozilla Public License 2.0 (MPL-2.0); every source file carries an SPDX header.

References

• Cryptographic sponge functions
• Duplexing the sponge: single-pass authenticated encryption and other applications
• FIPS PUB 202 SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions
• NIST Special Publication 800-185 SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash
• The sponge and duplex constructions
• Keccak specifications summary
• The making of Keccak
• The Joy Of Duplexes
• A software interface for Keccak
• Glossary
• Strengths of Keccak
• Sponge-based pseudo-random number generators
• SHA-3, Keccak and disturbing implementation stories
• Byte ordering and bit numbering in Keccak and SHA-3
• SHAKE, cSHAKE and some more bit ordering
• SHAKE and SP 800-185
• The Design of Rijndael
• The Design Of Rijndael – Errata

Keywords

• permutation function
• AES
• matrix transpose/transposition
• bit diffusion
• duplex
• sponge
• customizable
• hash
• PRNG
• Keccak
• SHA-3
• XOF
• SHAKE
• cSHAKE
• KMAC
• TupleHash

Footnotes

1. Schneier's Law Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. ↩