Castella: A heavyweight AES-based permutation function

This C++ library implements a heavyweight permutation function using AES CPU instructions, along with higher-level constructions built on it.

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. Apply (via XOR) the round constant to the first element of the state array.
2. Perform 3 rounds of AES encryption (with a zero round key) on each element of the state array.
   • The number of AES rounds was empirically determined. See aes_enc_0-aes_num_rounds.cpp.
3. 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 first Castella round constant is expand 16-byte c. Then each subsequent round constant is generated by performing 1 round of AES encryption (with a zero round key) on the preceding one, etc.

The number of round constants generated equals Castella::NUM_ROUNDS_MAX. Embiggen the value as needed.

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.

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.

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 raw data (i.e., a const void*, size_t pair) or a byte span (i.e., const std::span<const std::byte>) 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.

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.

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

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?

1. It's the opposite of lightweight. The state size is 256 bytes! For comparison, the state size of SHA-3 is 200 bytes.
2. It uses dedicated AES instructions instead of only ARX operations.

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 Compress-Castella hash is often as fast as XXH3 (xxhsum -H3)!

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

I don't know because it hasn't been scrutinized by others. 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) and supporting headers
examples/	Usage examples: cSHAKE-like, KMAC-like, and TupleHash-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

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. ↩