I enjoy playing with bits, I really do. A couple of years ago, I was searching for general informations about hashing algorithms, and found the FIPS PUB 202  SHA3 standard[^], which at the time was still a draft. I started playing with it, and this article presents the resulting implementation.
Above document is pretty self explanatory, I therefore encourage you to have a look at it before reading the serie. So, I will try not to rephrase it, I could only do worse. Instead, I will try to comment and justify on the design choices which were made according to this specification.
Notes:
 You will need at least Visual Studio 2017 Community Edition to be able to use provided solution. Sorry for those who still use older versions, I do not have them installed anywhere anymore.
 You will also need to have some basic knowledge of bitwise operations. If you do not understand the joke There are only 10 types of people: those who understand binary, and those who don't., then you may have a hard time catching up with this.
There are three static methods which are used almost everywhere through proposed solution. These are grouped in a static Bin
class.
 A
Mod
method that is a modulo operation which behaves differently from the core %
modulo operator, especially for negative values. It returns the integer r
for which 0 <= r < mod
and value  r
is a multiple of mod
. It is used by sponge constructions to handle their 3D coordinate system.
% operator  1 % 5 == 1 
Mod method  Mod(1, 5) == 4 
public static int Mod(int value, int mod) {
return value  mod * (int)Math.Floor((double)value / mod);
}
 A
LowerMask
method which returns a bitmask for specified number of lower bits (modulo 8) of a byte value. This mask can be used to trim a byte value to a specified number of bits, starting from its lowest bit. For example, imagine you have the bitstring "0110 1001"
; if you apply to it a mask for its 4 lower bits (the mask would be "0000 1111"
), masked value would be "0000 1001"
.
public static byte LowerMask(int count) {
byte value = 0;
if (count > 0) {
count %= 8;
if (count == 0) {
value = 255;
}
else {
for (int i = 0; i < count; i++) {
value = (byte)(1 << i);
}
}
}
return value;
}
 A
Log2
method which returns the base2 logarithm of specified integer number. Bitwise, it corresponds to the offset of the highest nonzero bit in the number. This implementation is the one proposed in Bit Twiddling Hacks  Find the log base 2 of an Nbit integer in O(log(N)) operations[^].
private static readonly int[] _b = new int[] { 2, 12, 240, 65280, 65536 };
private static readonly int[] _s = new int[] { 1, 2, 4, 8, 16 };
public static int Log2(int value) {
int log = 0;
for (int i = 4; i > 1; i) {
if ((value & _b[i]) != 0) {
value >>= _s[i];
log = _s[i];
}
}
return log;
}
All operations on sponge constructions operate on fixed length collections of bits, called bitstrings. A bitstring can be seen as a sequence of bits of specific length^{[1]}; it can also be defined as a sequence of blocks of fixed length, whose last block can be shorter^{[1]} (when the total length of the bitstring is not a multiple of the block size). Although reference defines bitstrings with 8bits blocks specifically, I preferred a more generic definition which would eventually allow to handle bitstrings whose underlying storage uses larger unsigned integer types. Though, proposed implementation uses byte
values for underlying storage, conforming to specification.
Choice was made to implement two interfaces for the Bitstring
class:
 the
IEquatable<Bitstring>
interface, which will allow us to determine whether two instances of a Bitstring
share same length and bits sequence.  the
IEnumerable<bool>
interface, which formally defines a Bitstring
as an enumeration of bits.
The Bitstring
class itself holds two private fields:
 an integer field storing the length in bits of the bitstring.
 an array of
byte
values holding the bits.
The bits of the bitstring are indexed from zero (the leftmost bit of the bitstring) to the length of the bitstring minus one (the rightmost bit of the bitstring).


Bitstrings indexing
To map a specified bit of the bitstring to its corresponding bit in internal array, the following formula is used:
 the index of the block holding the bit is
index / 8
.  the offset of the bit inside the block is
index % 8
.
The Bitstring
class is defined as sealed
. For performance reasons, I wanted to avoid virtual members as much as possible for core objects (bitstrings and sponge states).
Base functionalities of a bitstring include:
 being able to get the length in bits of the bitstring.
 being able to get the number of bytes in internal array.
 being able to get or set the bit at specified index in the bitstring.
So, here is the core skeleton of the Bitstring
class:
public sealed class Bitstring : IEquatable<Bitstring>, IEnumerable<bool>
{
public const int BlockBitSize = 8;
public const int BlockByteSize = BlockBitSize >> Shift;
public const int Shift = 3;
private byte[] _data;
private int _length;
public int BlockCount { get { return _data.Length; } }
public int Length { get { return _length; } }
public bool this[int index] {
get {
if ((index < 0)  (index >= _length)) {
throw new ArgumentOutOfRangeException(nameof(index));
}
int blockIndex = index >> Shift;
int bitOffset = index % BlockBitSize;
byte chunk = _data[blockIndex];
byte mask = (byte)(1 << bitOffset);
return ((chunk & mask) == mask);
}
set {
if ((index < 0)  (index >= _length)) {
throw new ArgumentOutOfRangeException(nameof(index));
}
int blockIndex = index >> Shift;
int bitOffset = index % BlockBitSize;
byte chunk = _data[blockIndex];
byte mask = (byte)(1 << bitOffset);
if (value) {
_data[blockIndex] = mask;
}
else {
_data[blockIndex] &= (byte)(~mask & 0xFF);
}
}
}
}
You can see that the mathematics are those which we would use with bitflags enumerations, for example. Formally:
 For the property getter, from the flat index, retrieve the block index as well as the bit offset. Use the block index to get corresponding byte, and construct a bit mask from the bit offset. Returns whether the byte value matches the bit at specified offset, using the mask.
 For the property setter, depending on the value to set (
true
or false
), either set the bit at specified offset using the same masking process as above (through a bitwise OR operation), or unset it using the two's complement of the mask (through a bitwise AND operation).
Operations on byte values, especially bitwise operations, are quite fast. As the this
itemaccessor property will be heavily used (see Step Mappings), it is important here that we try to make it as efficient as possible.
The IEquatable<Bitstring>
interface implementation is interesting, as a generic implementation of this interface for a reference type.
public bool Equals(Bitstring other) {
if (ReferenceEquals(other, null)) {
return false;
}
if (ReferenceEquals(this, other)) {
return true;
}
return (_length == other._length) && Enumerable.SequenceEqual(_data, other._data);
}
public override bool Equals(object obj) {
return (obj is Bitstring) && Equals((Bitstring)obj);
}
public override int GetHashCode() {
return HashCoder<int>.Boost.Compute(_length, HashCoder<byte>.Boost.Compute(_data));
}
public static bool operator ==(Bitstring lhs, Bitstring rhs) {
return ReferenceEquals(lhs, rhs)  (!ReferenceEquals(lhs, null) && lhs.Equals(rhs));
}
public static bool operator !=(Bitstring lhs, Bitstring rhs) {
return !ReferenceEquals(lhs, rhs) && (ReferenceEquals(lhs, null)  !lhs.Equals(rhs));
}
The IEnumerable<bool>
interface is implemented through a private GetBits
method, which iteratively yields the bits of the bitstring and provides required enumerator.
public IEnumerator<bool> GetEnumerator() {
return GetBits().GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
private IEnumerable<bool> GetBits() {
for (int i = 0; i < _length; i++) {
yield return this[i];
}
}
The Bitstring
class has been given six constructors which allow to:
 create a bitstring of specified length:
public Bitstring(int length) {
if (length < 0) {
throw new ArgumentOutOfRangeException(nameof(length));
}
_length = length;
_data = new byte[(int)Math.Ceiling((double)_length / BlockBitSize)];
}
 create an empty bitstring (a bitstring whose length is zero):
public Bitstring() : this(0) { }
 create a bitstring from an existing one (copy constructor):
public Bitstring(Bitstring bitstring) {
bitstring = bitstring ?? throw new ArgumentNullException(nameof(bitstring));
int count = bitstring.BlockCount;
_data = new byte[count];
Array.Copy(bitstring._data, 0, _data, 0, count);
_length = bitstring._length;
}
 create a bitstring from an enumeration of bits:
public Bitstring(IEnumerable<bool> bits) {
bits = bits ?? throw new ArgumentNullException(nameof(bits));
_data = Parse(bits, out _length);
}
private static byte[] Parse(IEnumerable<bool> bits, out int length) {
List<byte> bytes = new List<byte>(200);
byte value = 0;
int index = 0;
bool add = true;
length = 0;
foreach (bool bit in bits) {
length++;
if (bit) {
value = (byte)(1 << index);
}
if (++index > 7) {
index = 0;
bytes.Add(value);
value = 0;
add = false;
}
else if (!add) {
add = true;
}
}
if (add) {
bytes.Add(value);
}
return bytes.ToArray();
}
 create a bitstring from a
string
of binary digits and an optional length (parsing constructor). A regular expression, which matches only ones, zeroes and whitespaces, is used to validate that provided string is a valid binary representation. The length
parameter is optional, and a negative value will cause all input bits to be parsed.
public Bitstring(string bits, int length = 1) {
if (ValidateAndSanitize(ref bits, ref length)) {
int count = (int)Math.Ceiling((double)length / BlockBitSize);
_data = new byte[count];
int left = bits.Length;
int i;
for (i = 0; (left >= BlockBitSize) && ((i << Shift) < length); i++) {
_data[i] = ParseByte(bits.Substring(i << Shift, BlockBitSize));
left = BlockBitSize;
}
if (left > 0) {
_data[i] = ParseByte(bits.Substring(i << Shift, left));
}
_length = length;
}
else {
throw new ArgumentException("Invalid bitstring representation.", nameof(bits));
}
}
private static readonly Regex _bitstringRegex
= new Regex(
@"^[01\s]*$",
RegexOptions.Compiled  RegexOptions.CultureInvariant
);
private static bool ValidateAndSanitize(ref string bits, ref int length) {
return (ValidateBits(ref bits) && ValidateLength(ref length, bits.Length);
}
private static bool ValidateBits(ref string bits) {
bool ok = (bits != null);
if (ok) {
ok = _bitstringRegex.IsMatch(bits);
if (ok && bits.Contains(" ")) {
bits = bits.Replace(" ", "");
}
}
return ok;
}
private static bool ValidateLength(ref int length, int stringLength) {
if (length < 0) {
length = stringLength;
}
return true;
}
private static byte ParseByte(string chunk) {
byte result = 0;
int length = chunk.Length;
for (int i = 0; i < length; i++) {
if (chunk[i] == '1') {
result = (byte)(1 << i);
}
}
return result;
}
 create a bitstring from a
byte
array and an optional length:
public Bitstring(byte[] data, int length = 1) {
data = data ?? throw new ArgumentNullException(nameof(data));
int count = data.Length;
int bitCount = count << Shift;
_length = (length < 0) ? bitCount : length;
if (_length > bitCount) {
throw new ArgumentOutOfRangeException(nameof(length));
}
if (_length != bitCount) {
count = (int)Math.Ceiling((double)_length / BlockBitSize);
Array.Resize(ref data, count);
int remaining = _length % BlockBitSize;
if (remaining > 0) {
data[count  1] &= Bin.LowerMask(remaining);
}
}
_data = data;
}
Then, five instance methods are provided which allow to modify the internal byte array of the bitstring. These methods do modify the instance for which they are called, and return this same instance so that they can eventually be chained.
 Two
Append
methods, which add specified bits or byte array to the end of the bitstring. The byte array version first checks whether current length is bytealigned; if so, a simple array copy can take place; if not, then the method resorts to the (slower) bitenumerative version.
public Bitstring Append(byte[] bytes) {
if (bytes != null) {
if ((_length % BlockBitSize) == 0) {
int count = bytes.Length;
int oldCount = BlockCount;
Array.Resize(ref _data, oldCount + count);
Array.Copy(bytes, 0, _data, oldCount, count);
_length += count << Shift;
}
else {
return Append(new Bitstring(bytes));
}
}
return this;
}
public Bitstring Append(IEnumerable<bool> bits) {
int count = bits?.Count() ?? 0;
if (count > 0) {
int blockIndex = _length >> Shift;
int bitOffset = _length % BlockBitSize;
_length += count;
int newBlockCount = (int)Math.Ceiling((double)_length / BlockBitSize);
if (newBlockCount > BlockCount) {
Array.Resize(ref _data, newBlockCount);
}
foreach (bool bit in bits) {
if (bit) {
_data[blockIndex] = (byte)(1 << bitOffset);
}
if (++bitOffset > 7) {
bitOffset = 0;
blockIndex++;
}
}
}
return this;
}
 Two
Prepend
methods, which insert specified bits or byte array to the start of the bitstring. Here the byte array version is quite straightforward, as by essence a byte array is bytealigned.
public Bitstring Prepend(byte[] bytes) {
if (bytes != null) {
int count = bytes.Length;
int oldCount = BlockCount;
Array.Resize(ref _data, oldCount + count);
Array.Copy(_data, 0, _data, count, oldCount);
Array.Copy(bytes, 0, _data, 0, count);
_length += count << Shift;
}
return this;
}
public Bitstring Prepend(IEnumerable<bool> bits) {
Bitstring copy = new Bitstring(this);
int count = bits?.Count() ?? 0;
if (count > 0) {
_length += count;
int newBlockCount = (int)Math.Ceiling((double)_length / BlockBitSize);
if (newBlockCount > BlockCount) {
Array.Resize(ref _data, newBlockCount);
}
int blockIndex = 0;
int bitOffset = 0;
foreach (bool bit in bits) {
if (bit) {
_data[blockIndex] = (byte)(1 << bitOffset);
}
else {
_data[blockIndex] &= (byte)~(1 << bitOffset);
}
if (++bitOffset > 7) {
bitOffset = 0;
blockIndex++;
}
}
foreach (bool bit in copy) {
if (bit) {
_data[blockIndex] = (byte)(1 << bitOffset);
}
else {
_data[blockIndex] &= (byte)~(1 << bitOffset);
}
if (++bitOffset > 7) {
bitOffset = 0;
blockIndex++;
}
}
}
return this;
}
 A
SwapBits
method which swaps the bits at specified indices (algorithm used is this specified here):
public Bitstring SwapBits(int lhs, int rhs) {
if (IsValidIndex(lhs) && IsValidIndex(rhs) && (lhs != rhs)) {
this[lhs] ^= this[rhs];
this[rhs] ^= this[lhs];
this[lhs] ^= this[rhs];
}
return this;
}
public bool IsValidIndex(int index) {
return (index > 1) && (index < _length);
}
 Two
Xor
methods, which perform a bitwise XOR operation on the bits of the bitstring with the bits of a specified bitstring or byte array of same length. Other bitwise operations are also implemented, but not shown here (and actually not even needed in the context of KECCAKp permutations). Xor
method, on the other hand, is used each time an input message is submitted to the sponge construction. Note that nothing is done if the length of specified bitstring does not equal the length of current instance.
public Bitstring Xor(byte[] data) {
int count = BlockCount;
if ((data != null) && (data.Length == count)) {
for (int i = 0; i < count; i++) {
_data[i] ^= data[i];
}
}
return this;
}
public Bitstring Xor(Bitstring other) {
return (other.Length == _length) ? Xor(other._data) : this;
}
Then, two instance methods are provided which, instead of modifying the internal state of the bitstring, do return a new bitstring.
 A
Substring
method which allows to get any substring of the bitstring:
public Bitstring Substring(int index, int length) {
if (IsValidIndex(index)) {
if (((index % BlockBitSize) == 0) && ((length % BlockBitSize) == 0)) {
int count = length >> Shift;
byte[] data = new byte[count];
Array.Copy(_data, index >> Shift, data, 0, count);
return new Bitstring(data);
}
else {
return new Bitstring(this.Skip(index).Take(length));
}
}
else {
throw new ArgumentOutOfRangeException(nameof(index));
}
}
 A
Truncate
method which allows to get the specified number of bits from the start of the bitstring.
public Bitstring Truncate(int length) {
length = Math.Min(_length, Math.Max(0, length));
int count = (int)Math.Ceiling((double)length / BlockBitSize);
byte[] data = new byte[count];
Array.Copy(_data, 0, data, 0, count);
int left = length % BlockBitSize;
if (left != 0) {
data[count  1] &= Bin.LowerMask(left);
}
return new Bitstring(data, length);
}
Finally, some methods are provided to get a string representation of the bitstring, either in hexadecimal or binary form, as well as static properties and methods which will ease the usage of the class. I will not show them here, but they can easily be found in proposed download at the top of this article. Here is the class diagram for the public interface of the Bitstring
class.
Bitstring tests
As the core storage object which will be used everywhere through the solution, it is important at this stage to test whether it actually behaves as expected.
Proposed solution is composed of three projects:
 A dll project holding the implementation.
 A unittest project to test the dll.
 A quick console program to play with it.
Unittests project actually holds three tests for the Bin
class and seventyfive tests for the Bitstring
class.
I invite you to run and explore them as they expose the public interface usage of the class.
static void Main(string[] args) {
Random random = new Random();
Func<Bitstring> randomBitstring = () => { return Bitstring.Random(random, 42); };
Console.WriteLine(randomBitstring().ToBinString());
Console.WriteLine(randomBitstring().ToBinString(4));
Console.WriteLine(randomBitstring().ToHexString());
Console.WriteLine(randomBitstring().ToHexString(true, false));
Console.WriteLine(randomBitstring().ToHexString(false, true));
Console.WriteLine(randomBitstring().ToHexString(false, false));
Bitstring bitstring = new Bitstring("10100101");
Console.WriteLine(bitstring.ToBinString());
bitstring.Xor(Bitstring.Ones(8));
Console.WriteLine(bitstring.ToBinString());
Console.ReadKey(true);
}
Above snippet produces a random result which looks like this:
At the time I discovered sponge constructions and started playing with them  during summer of 2016  I was not aware of the .NET BitArray
class, which roughly fullfills the same purpose as a Bitstring
. I may have used it then. But here it is. I cannot bring myself to throw it off, as it is quite fit for the task at hand. So be it.
We can now present the SpongeState
class, which is the second lowlevel object used by sponge constructions.
The sponge construction and all operations on it use an internal object called state. It holds its bits in a bitstring, but allows to access them with 3Darray coordinates.
You can find its primary description in FIPS PUB 202  Page 7  3.1 State.
A state then partitions a bitstring into several parts, and permutations and transformations applied to the state will be able to be performed on those discrete parts:
 a bit is defined by its three fixed coordinates x, y, and z.
 a row is defined by its y and z coordinates (and can be seen as a collection of 5 bits).
 a column is defined by its x and z coordinates (and can be seen as a collection of 5 bits).
 a lane is defined by its x and y coordinates (and can be seen as a collection of w bits).
 a plane is defined by its y coordinate (and can be seen as a collection of w rows or 5 lanes).
 a slice is defined by its z coordinate (and can be seen as a collection of 5 rows or 5 columns).
 a sheet is defined by its x coordinate (and can be seen as a collection of w columns or 5 lanes).
The size of a sponge state
The first important property of a sponge state is its size (b). Formally, it is the number of bits it contains (and thus, the length of the bitstring it is using).
There are two other quantities which are related to this total number of bits:
 the number of bits in a lane (w), which is the total number of bits divided by 25, since there are 25 lanes in a sponge state. It can also be seen as the depth of the sponge state.
 the base2 logarithm of w (l), which usage will be detailed soon.
Seven sizes are actually used with sponge constructions. A custom structure is provided to represent a sponge state size, and seven static fields provide a quick access to predefined values.
The size b of a sponge state has to be a multiple of 25. For alignment reasons, it is better the width w being a power of two. So, all in all, the size of a songe state should be a multiple of 25 and a multiple of a power of two at the same time. The constructor of the SpongeSize
structure has been made internal, preventing outside world to create exotic sizes which would not fit in the state.
The seven sizes are the following, along with their corresponding w and l values:
Total number of bits (b)  25  50  100  200  400  800  1600 
Number of bits in a lane (w)  1  2  4  8  16  32  64 
Base2 logarithm of w (l)  0  1  2  3  4  5  6 
Sponge state sizes and related quantities[^]
The SpongeSize
structure is defined as:
public struct SpongeSize
{
private readonly int _b;
public int B { get { return _b; } }
public int W { get { return _b / 25; } }
public int L { get { return Bin.Log2(W); } }
internal SpongeSize(int b) {
_b = b;
}
public static readonly SpongeSize W01 = new SpongeSize(25);
public static readonly SpongeSize W02 = new SpongeSize(50);
public static readonly SpongeSize W04 = new SpongeSize(100);
public static readonly SpongeSize W08 = new SpongeSize(200);
public static readonly SpongeSize W16 = new SpongeSize(400);
public static readonly SpongeSize W32 = new SpongeSize(800);
public static readonly SpongeSize W64 = new SpongeSize(1600);
}
The sponge state
Besides its size, a state is defined by its rate (or bitrate). In fact, the total number of bits b in the state is divided into two parts:
 the rate, which is the number of bits which are xored with input messages.
 the capacity, which is the number of bits which are left unchanged while xoring input messages.
Usage of rate and capacity will be explicited in the next part, where I will describe the process which takes place in a sponge construction.
At any time, the following equality holds: SpongeState.Size.B = SpongeState.Rate + SpongeState.Capacity
.
Here is the definition of the SpongeState
class.
public sealed class SpongeState
{
private readonly int _rate;
private readonly SpongeSize _size;
private Bitstring _bitstring;
public SpongeSize Size { get { return _size; } }
public int Rate { get { return _rate; } }
public int Capacity { get { return _size.B  _rate; } }
}
The core 3Daddressing of the sponge state is achieved through a single method:
public int GetIndex(int x, int y, int z) {
return _size.W * (5 * y + x) + z;
}
This method allows to get the index in the bitstring of any bit, given its x, y and z coordinates in the state. x and y coordinates are implicitly taken modulo 5, while z coordinate is implicitly taken modulo Size.W
.
We can see that, starting from a flat bitstring, its translation to a sponge state is done in this order:
 z is incremented until it reaches w, in which case z is reset to zero.
 When z is reset, x is incremented until it reaches 5, in which case x is reset to zero.
 When x is reset, y is incremented.
Using this single method, we are then able to write the following properties, which allow to address a single bit of the state, either with its index in the bitstring, or with its 3Dcoordinates:
public bool this[int index] {
get { return _bitstring[index]; }
set { _bitstring[index] = value; }
}
public bool this[int x, int y, int z] {
get { return _bitstring[GetIndex(x, y, z)]; }
set { _bitstring[GetIndex(x, y, z)] = value; }
}
Now, we would like to be able to address a specific lane, for example. A Lane
struct is defined, which holds the x and y coordinates of the lane, as well as a reference to the state to which it belongs.
public struct Lane
{
public readonly SpongeState State;
public readonly int X;
public readonly int Y;
public int Depth { get { return State.Size.W; } }
internal Lane(SpongeState state, int x, int y) {
State = state;
X = x;
Y = y;
}
public IEnumerable<bool> GetBits() {
int w = State.Size.W;
for (int z = 0; z < w; z++) {
yield return State[State.GetIndex(X, Y, z)];
}
}
}
This simple structure allows to represent a specific lane with minimal overhead. The actual bits of the lane are not stored in the structure, but rather enumerated when needed. Moreover, the constructor of the structure being internal, a lane may only be obtained from the GetLane
method of the SpongeState
class:
public sealed class SpongeState
{
public Lane GetLane(int x, int y) {
return new Lane(this, x, y);
}
}
Other parts of the state (column, row, plane, sheet and slice) are also defined, but I will not show them here. In fact, apart from the GetColumn
method, they are not even needed for actual KECCAKp permutations. Other (or future) usages of the sponge construction, duplex construction, or monkey construction, may take advantage of them.
Finally, the following delegate has been defined, which is used to perform operations on a single bit of the state:
private delegate bool OperationDelegate(int x, int y, int z, bool bit);
x
, y
and z
are the coordinates of the bit whose value to set, bit
is the right operand to the operation which will be made on the bit at x, y and z in the state.
Applied to a lane, for example, here is what this allows:
private void LaneOperation(OperationDelegate function, Lane lane, IEnumerable<bool> bits) {
int z = 0;
foreach (bool bit in bits) {
this[GetIndex(lane.X, lane.Y, z)] = function(lane.X, lane.Y, z, bit);
z++;
}
}
public void SetLane(Lane lane, IEnumerable<bool> bits) {
LaneOperation(
(x, y, z, bit) => { return bit; },
lane,
bits
);
}
public void XorLane(Lane lane, IEnumerable<bool> bits) {
LaneOperation(
(x, y, z, bit) => { return this[x, y, z] ^ bit; },
lane,
bits
);
}
The same logic is applied to other parts of the state but, again, I will not show them here.
Finally, three constructors are provided, which allow to:
 create a new sponge state specifying its size and rate:
public SpongeState(SpongeSize size, int rate) {
int b = size.B;
if ((rate < 1)  (rate >= b)) {
throw new ArgumentException($"Invalid rate {rate} for width {b}.", nameof(rate));
}
_size = size;
_rate = rate;
_bitstring = Bitstring.Zeroes(b);
}
 create a sponge state from an existing bitstring and a rate:
public SpongeState(Bitstring bitstring, int rate) {
_bitstring = bitstring ?? throw new ArgumentNullException(nameof(bitstring));
int length = _bitstring.Length;
if (length < 1) {
throw new ArgumentException("Bitstring cannot be empty.", nameof(bitstring));
}
_size = new SpongeSize(length);
if ((rate < 1)  (rate >= _size.B)) {
throw new ArgumentException($"Invalid rate {rate} for width {_size.B}.", nameof(rate));
}
_rate = rate;
}
 create a sponge state from an existing one:
public SpongeState(SpongeState state) {
_size = state._size;
_rate = state._rate;
_bitstring = new Bitstring(state._bitstring);
}
You can watch the diagram for the SpongeState
class and its related members here. As you can see, its public interface is quite important, but each method is quite simple and straightforward by itself.
There exist fiftynine unit tests for the SpongeState
class, which quickly check that basic operations are handled properly.
Now that we have the core Bitstring
and SpongeState
classes, we can happily jump into the definition of the sponge construction.
The definition of a sponge construction on which I based my implementation can be found in FIPS PUB 202  Page 17  4. SPONGE CONSTRUCTION. It has three main characteristics:
 an underlying function (transformation or permutation) which operates on fixedlength bitstrings.
 a rate (or bitrate), which is in fact the rate of the sponge state which the construction is using.
 a padding rule, which aims at producing fixedlength input bitstrings to the function.
As a side note, the sponge construction is stateless: this means that no state is maintained between calls to the function. This is not true for duplex and monkey constructions, which maintain their internal state between calls. I may explore both these constructions in a future article.
The processing of a message by a sponge construction can be roughly divided into two distinct phases:
 an aborption phase, where the message is integrally processed through the sponge construction.
 a squeezing phase, which produces as many output bytes as resquested from the sponge construction.
At this stage, we will define its interface.
public interface ISpongeConstruction
{
int Capacity { get; }
int Rate { get; }
SpongeSize Size { get; }
byte[] Process(byte[] bytes, int outputLength, int inputLength = 1);
}
The Process
method allows to restrict the number of bits of the input byte array to consider. When inputLength
parameter is not specified, it is assumed to be the number of bits in the array.
Now that we defined those elements, we can implement the interface:
public abstract class SpongeConstruction : ISpongeConstruction
{
protected readonly SpongeState State;
public int Capacity { get { return State.Capacity; } }
public int Rate { get { return State.Rate; } }
public SpongeSize Size { get { return State.Size; } }
protected SpongeConstruction(SpongeSize size, int rate)
{
State = new SpongeState(size, rate);
}
public virtual byte[] Process(byte[] bytes, int outputLength, int inputLength = 1) {
byte[] result = null;
if (bytes != null) {
inputLength = (inputLength > 1) ? inputLength : bytes.Length << Bitstring.Shift;
Absorb(bytes, inputLength);
result = Squeeze(outputLength);
}
return result;
}
protected virtual void Absorb(byte[] bytes, int length) {
State.Clear();
Bitstring message = new Bitstring(bytes, length);
int rate = State.Rate;
message.Append(Suffix());
message.Append(GetPadding(rate, message.Length));
int n = message.Length / rate;
Bitstring zeroes = new Bitstring(Capacity);
Bitstring chunk;
for (int i = 0; i < n; i++) {
chunk = message.Substring(rate * i, rate);
chunk.Append(zeroes);
State.Bitstring.Xor(chunk);
Function();
}
}
protected abstract void Function();
protected abstract Bitstring GetPadding(int r, int m);
protected virtual byte[] Squeeze(int outputLength) {
int rate = State.Rate;
Bitstring q = new Bitstring();
while (true) {
q.Append(State.Bitstring.Truncate(rate));
if (q.Length >= outputLength) {
return (q.Length == outputLength) ? q.Bytes : q.Truncate(outputLength).Bytes;
}
Function();
}
}
protected virtual Bitstring Suffix() {
return new Bitstring();
}
}
Key points here:
 The class is abstract. There is no default permutation nor padding rule defined, so subclasses will be in charge of implementing them.
Absorb
, Squeeze
and Suffix
methods provide a default implementation of the absorbing, squeezing and suffixing phases, respectively. They are flagged as virtual, though, so subclasses can override this behaviour.
The KECCAKp[b,n_{r}] permutations are a family of permutation functions. They all use the pad10*1^{[2]} padding rule, which adds a single 1, followed by as much 0's as needed, followed by a single 1, to the end of input bitstrings, such that the total length is a multiple of the rate of the sponge construction. Their formal definition can be found in FIPS PUB 202  Page 7  3. KECCAKp PERMUTATIONS.
A KECCAKp[b,n_{r}] permutation is characterized by:
 the number of bits (the length of the bitstrings) it will permute (b).
 the number of internal iterations of a single permutation (n_{r}).
In proposed solution, a KECCAKp[b,n_{r}] permutation is implemented in class KeccakPermutation
, which inherits from the SpongeConstruction
class.
public class KeccakPermutation : SpongeConstruction
{
private readonly int _roundCount;
public int RoundCount { get { return _roundCount; } }
protected KeccakPermutation(SpongeSize size, int rate, int roundCount)
: base(size, rate) {
_roundCount = roundCount;
}
protected override void Function() {
int start = 12 + (State.Size.L << 1);
for (int round = start  _roundCount; round < start; round++) {
Iota(Khi(Pi(Rho(Theta(State)))), round);
}
}
}
KECCAK permutations algorithm^{[3]} is the application of five consecutive core permutations called step mappings^{[4]}: θ (theta), ρ (rho), π (pi), χ (khi) and ι (iota). From this five step mappings, only the last one (iota) actually cares about the round
argument.
θ  Theta performs a XOR operation on each bit of the state with the parity of two adjacent columns^{[5]}. 

public static SpongeState Theta(SpongeState state) {
int w = state.Size.W;
bool[,] c = new bool[5, w];
for (int x = 0; x < 5; x++) {
for (int z = 0; z < w; z++) {
c[x, z] = state.GetColumn(x, z).GetBits()
.Aggregate((bool lhs, bool rhs) => { return lhs ^ rhs; });
}
}
bool[,] d = new bool[5, w];
for (int x = 0; x < 5; x++) {
for (int z = 0; z < w; z++) {
d[x, z] = c[Bin.Mod(x  1, 5), z] ^ c[Bin.Mod(x + 1, 5), Bin.Mod(z  1, w)];
}
}
for (int x = 0; x < 5; x++) {
for (int z = 0; z < w; z++) {
bool bit = d[x, z];
for (int y = 0; y < 5; y++) {
state[x, y, z] ^= bit;
}
}
}
return state;
}

ρ  Rho performs a rotation on each of the twentyfive lanes of the state which depends on the x and y coordinates of the lane^{[6]}. 

public static SpongeState Rho(SpongeState state) {
SpongeState newState = new SpongeState(state.Size, state.Rate);
int w = state.Size.W;
newState.SetLane(newState.GetLane(0, 0), state.GetLane(0, 0).GetBits());
int x = 1;
int y = 0;
int u, oldX;
for (int t = 0; t < 24; t++) {
u = ((t + 1) * (t + 2)) >> 1;
for (int z = 0; z < w; z++) {
newState[x, y, z] = state[x, y, Bin.Mod(z  u, w)];
}
oldX = x;
x = y;
y = Bin.Mod(2 * oldX + 3 * y, 5);
}
state.SetBitstring(newState.Bitstring);
return state;
}

π  Pi performs a rearrangement of the lanes of the state^{[7]}. 

public static SpongeState Pi(SpongeState state) {
SpongeState newState = new SpongeState(state.Size, state.Rate);
int w = state.Size.W;
for (int y = 0; y < 5; y++) {
for (int x = 0; x < 5; x++) {
for (int z = 0; z < w; z++) {
newState[x, y, z] = state[Bin.Mod(x + 3 * y, 5), x, z];
}
}
}
state.SetBitstring(newState.Bitstring);
return state;
}

χ  Khi performs a XOR operation on each bit of the state with a nonlinear function of two other bits in its row^{[8]}. 

public static SpongeState Khi(SpongeState state) {
SpongeState newState = new SpongeState(state.Size, state.Rate);
int w = state.Size.W;
for (int y = 0; y < 5; y++) {
for (int x = 0; x < 5; x++) {
for (int z = 0; z < w; z++) {
newState[x, y, z] = state[x, y, z]
^ ((state[Bin.Mod(x + 1, 5), y, z] ^ true) && state[Bin.Mod(x + 2, 5), y, z]);
}
}
}
state.SetBitstring(newState.Bitstring);
return state;
}

ι  Iota affects only the first lane (i.e., the lane which is at the center of the sponge construction), and modifies it according in a way which depends on the round number^{[9]}. The result of the RoundConstant method depending only on the integer parameter it is feeded with, it can be cached. A Dictionary<int, bool> is used for that. Moreover, this method contains a loop which calls the RoundConstant method several times, and the result depends on two parameters: the round argument passed to the Iota method, and the t parameter provided to the RoundConstant method. In order to use a dictionary, a private RoundT structure is defined, quickly implementing the IEquatable<RoundT> interface. 

public static SpongeState Iota(SpongeState state, int round) {
int w = state.Size.W;
int l = state.Size.L;
Bitstring rc = Bitstring.Zeroes(w);
RoundT roundT;
int t;
int rnd = 7 * round;
for (int j = 0; j <= l; j++) {
t = j + rnd;
roundT = new RoundT(round, t);
if (!_roundTConstants.ContainsKey(roundT)) {
_roundTConstants.Add(roundT, RoundConstant(t));
}
rc[(1 << j)  1] = _roundTConstants[roundT];
}
state.XorLane(state.GetLane(0, 0), rc.GetBits());
return state;
}
private static readonly Dictionary<int, bool> _roundConstants = new Dictionary<int, bool> {
{ 0, true }
};
private static readonly Dictionary<RoundT, bool> _roundTConstants = new Dictionary<RoundT, bool>();
private struct RoundT : IEquatable<RoundT>
{
public readonly int Round;
public readonly int T;
public RoundT(int round, int t) {
Round = round;
T = t;
}
public bool Equals(RoundT other) {
return (Round == other.Round) && (T == other.T);
}
public override bool Equals(object obj) {
return (obj is RoundT) && Equals((RoundT)obj);
}
public override int GetHashCode() {
return HashCoder<int>.Boost.Compute(RoundT, T);
}
public static bool operator ==(RoundT lhs, RoundT rhs) {
return lhs.Equals(rhs);
}
public static bool operator !=(RoundT lhs, RoundT rhs) {
return !lhs.Equals(rhs);
}
}
private static bool RoundConstant(int t) {
t = Bin.Mod(t, 255);
if (_roundConstants.ContainsKey(t)) {
return _roundConstants[t];
}
Bitstring r = new Bitstring("10000000", 8);
for (int i = 0; i < t; i++) {
r.Prepend(Bitstring.Zero);
r[0] ^= r[8];
r[4] ^= r[8];
r[5] ^= r[8];
r[6] ^= r[8];
r = r.Truncate(8);
}
bool bit = r[0];
_roundConstants.Add(t, bit);
return bit;
}

Effects of KECCAKp permutations step mappings
The KeccakPermutation
class also overrides the GetPadding
method and provides the pad10*1^{[2]} padding rule.
protected override Bitstring GetPadding(int r, int m) {
int j = Bin.Mod(m  2, r);
Bitstring pad = new Bitstring(j + 2);
pad[0] = true;
pad[pad.Length  1] = true;
return pad;
}
The KECCAKf permutations are a specialization of the KECCAKp permutations to the case where the number of rounds of a single iteration (n_{r}) equals 12 + 2l^{[10]}.
Formally, a KECCAKf[b] permutation is a KECCAKp[b, 12 + 2l] permutation.
It is implemented in the KeccakFunction
class, as a subclass of the KeccakPermutation
class, which provides the seven possible sizes as static methods.
public class KeccakFunction : KeccakPermutation
{
protected KeccakFunction(SpongeSize size, int rate)
: base(size, rate, 12 + (size.L << 1)) { }
public static KeccakFunction F25(int rate) {
return new KeccakFunction(SpongeSize.W01, rate);
}
public static KeccakFunction F50(int rate) {
return new KeccakFunction(SpongeSize.W02, rate);
}
public static KeccakFunction F100(int rate) {
return new KeccakFunction(SpongeSize.W04, rate);
}
public static KeccakFunction F200(int rate) {
return new KeccakFunction(SpongeSize.W08, rate);
}
public static KeccakFunction F400(int rate) {
return new KeccakFunction(SpongeSize.W16, rate);
}
public static KeccakFunction F800(int rate) {
return new KeccakFunction(SpongeSize.W32, rate);
}
public static KeccakFunction F1600(int rate) {
return new KeccakFunction(SpongeSize.W64, rate);
}
}
The KECCAK[c] permutations are a restriction of the KECCAKf permutations to the case where b equals 1600. In this case, the permutation is defined by c, the capacity of the sponge state. A KECCAK[c] permutation is then a KECCAKp[b,n_{r}] permutation where b equals 1600, n_{r} = 12 + 2l, where the rate equals 1600  c, and which uses pad10*1 as padding rule.
It is implemented in the Keccak
class, which inherits from the KeccakFunction
class, and provides four of the most common instances, for functions with capacity 448, 512, 768 and 1024 bits. Note that, for a specific function, the capacity is double the length of desired output (448 for a 224 bits output, 512 for a 256 bits output, etc.).
public class Keccak : KeccakFunction
{
protected Keccak(int capacity)
: base(SpongeSize.W64, 1600  capacity) { }
public static Keccak Keccak224() {
return new Keccak(448);
}
public static Keccak Keccak256() {
return new Keccak(512);
}
public static Keccak Keccak384() {
return new Keccak(768);
}
public static Keccak Keccak512() {
return new Keccak(1024);
}
}
Based on the KECCAK[c] permutations, eight functions are then defined:
 Four SHA3 hashing fuctions SHA3224, SHA3256, SHA3384 and SHA3512 (with a respective output length of 224, 256, 384 and 512 bits). These functions use a
"01"
suffix.
Function  Output length  Capacity  Rate 
bits  bytes  bits  bytes  bits  bytes 
SHA3224  224  28  448  56  1152  144 
SHA3256  256  32  512  64  1088  136 
SHA3384  384  48  768  96  832  104 
SHA3512  512  64  1024  128  576  72 
SHA3 hashing functions
public sealed class Sha3Permutation : Keccak
{
public int Width {
get { return Capacity >> 1; }
}
private Sha3Permutation(int capacity)
: base(capacity) { }
public static Sha3Permutation Sha3_224() {
return new Sha3Permutation(448);
}
public static Sha3Permutation Sha3_256() {
return new Sha3Permutation(512);
}
public static Sha3Permutation Sha3_384() {
return new Sha3Permutation(768);
}
public static Sha3Permutation Sha3_512() {
return new Sha3Permutation(1024);
}
protected override Bitstring Suffix() {
return new Bitstring("01");
}
}
 Four extendableoutput functions RawSHAKE128, RawSHAKE256, SHAKE128 and SHAKE256. ExtendableOutput Functions (XOF's) differ from hashing functions in that they can produce an output of infinite length. This functionality is managed by the
SpongeConstruction.Squeeze
method.
Function  Capacity  Rate 
bits  bytes  bits  bytes 
RawSHAKE128  256  32  1344  168 
RawSHAKE256  512  64  1088  136 
SHAKE128  256  32  1344  168 
SHAKE256  512  64  1088  136 
SHAKE extandableoutput functions
SHAKE and RawSHAKE XOF's differ only in the suffix they append to input bitstrings before padding them: RawSHAKE use a "11"
suffix, while SHAKE use a "1111"
one.
public sealed class RawShakePermutation : Keccak
{
private RawShakePermutation(int capacity)
: base(capacity) { }
public static RawShakePermutation RawShake128() {
return new RawShakePermutation(256);
}
public static RawShakePermutation RawShake256() {
return new RawShakePermutation(512);
}
protected override Bitstring Suffix() {
return new Bitstring("11");
}
}
public sealed class ShakePermutation : Keccak
{
private ShakePermutation(int capacity)
: base(capacity) { }
public static ShakePermutation Shake128() {
return new ShakePermutation(256);
}
public static ShakePermutation Shake256() {
return new ShakePermutation(512);
}
protected override Bitstring Suffix() {
return new Bitstring("1111");
}
}
We now have a base implementation of hashing and extendableoutput functions. Let us do a few quick tests to see if these work as expected.
To test whether this implementation respects the standard, a bunch of base tests with fixedlength bitstrings are available at NIST  Cryptographic Standards and Guidelines / Examples with Intermediate Values / Secure Hashing / FIPS 202  SHA3 Standard: PermutationBased Hash and ExtendableOutput Functions[^]. They provide expected values for messages of specific widths 0, 5, 30, 1600, 1605 and 1630 bits respectively, for the four SHA3 hashing function, and for both SHAKE128 and SHAKE256 XOF's. I did not find any example file for RawSHAKE128 and RawSHAKE256 XOF's.
internal class Program
{
private static readonly Bitstring _message0000 = new Bitstring();
private static void Main(string[] args) {
Sha3Test();
Exit();
}
private static void Sha3Test() {
Sha3Permutation sha3 = Sha3Permutation.Sha3_224;
Output(sha3, "SHA3224 sample of 0bit message", _message0000, 224);
sha3 = Sha3Permutation.Sha3_256;
Output(sha3, "SHA3256 sample of 0bit message", _message0000, 256);
sha3 = Sha3Permutation.Sha3_384;
Output(sha3, "SHA3384 sample of 0bit message", _message0000, 384);
sha3 = Sha3Permutation.Sha3_512;
Output(sha3, "SHA3512 sample of 0bit message", _message0000, 512);
}
private void Output(SpongeConstruction sponge, string caption, Bitstring bitstring, int outputLength) {
Console.WriteLine(caption);
Stopwatch stopwatch = Stopwatch.StartNew();
Bitstring b = new Bitstring(sponge.Process(bitstring.Bytes, outputLength, bitstring.Length));
Console.WriteLine($"{b.ToHexString(false, false)} ({stopwatch.ElapsedMilliseconds}ms)");
Console.WriteLine();
}
private static void Exit() {
Console.Write("Press a key to exit...");
Console.ReadKey(true);
}
}
I do not show here the whole thirtysix tests. Here is what the snippet above produces (in Release mode):
All tests actually produce expected values.
Now we have some confidence on produced results, we may want to integrate this SHA3 permutations implementation to the .NET HashAlgorithm
infrastructure, don't we? This needs, at least, the Initialize
, HashCore
and HashFinal
methods to be overriden.
public sealed class Sha3HashAlgorithm : HashAlgorithm
{
public enum Size : byte
{
Bits224,
Bits256,
Bits384,
Bits512
}
private readonly Sha3Permutation _permutation;
private Bitstring _hash;
public Sha3HashAlgorithm(Size size)
: base() {
switch (size) {
case Size.Bits224:
_permutation = Sha3Permutation.Sha3_224();
break;
case Size.Bits256:
_permutation = Sha3Permutation.Sha3_256();
break;
case Size.Bits384:
_permutation = Sha3Permutation.Sha3_384();
break;
case Size.Bits512:
_permutation = Sha3Permutation.Sha3_512();
break;
}
}
public override void Initialize() {
_hash = new Bitstring();
}
protected override void HashCore(byte[] array, int ibStart, int cbSize) {
byte[] data = new byte[cbSize];
Array.Copy(array, ibStart, data, 0, cbSize);
_hash.Append(data);
}
protected override byte[] HashFinal() {
_hash = _permutation.Process(_hash, _permutation.Width);
return _hash?.Bytes ?? new byte[0];
}
}
Actual implementation may not be optimized, as it needs the whole input data to be loaded into memory before running the hash function.
Performancewise, for short inputs (order of a few thousand bits), a hashing operation resorts to a few milliseconds (see screenshot above). For larger ones, though, this may be an issue; for example, still in release mode, a SHA3224 hashing of an input message of eight million bits (8Mb = 1MB) takes about 41 seconds on my computer. If you intend to perform SHA3 hash operations on large files, there exists[^] a C implementation provided by KECCAK team itself, which may be more suitable. If you just intend to hash small inputs (like passwords), proposed C# implementation would suffice. Anyway, the goal of this article is rather presenting you with sponge constructions than providing a universal and highly optimized implementation.
 Sponge constructions, and all cryptographic sponge functions including KECCAKp permutations, are the original and amazing work of Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
 Except for the sponge construction schema, all images are homemade.
 Sponge construction schema comes from common.wikimedia.org.
 Cryptographic sponge functions  Page 11  2.1.1 Bitstrings
 The KECCAK reference  Page 7  1.1.2 Padding rules
 FIPS PUB 202  Page 16  3.3 KECCAKp[b,n_{r}]
 FIPS PUB 202  Page 11  3.2 Step Mappings
 FIPS PUB 202  Page 11  3.2.1 Specification of θ
 FIPS PUB 202  Page 12  3.2.2 Specification of ρ
 FIPS PUB 202  Page 14  3.2.3 Specification of π
 FIPS PUB 202  Page 15  3.2.4 Specification of χ
 FIPS PUB 202  Page 15  3.2.5 Specification of ι
 FIPS PUB 202  Page 17  3.4 Comparison with KECCAKf
 2018/01/28: Version 1.0.0.0  First publication