This article describes a C# implementation of the sponge construction and its use for SHA-3 hashing operations.
I enjoy playing with bits, I really do. A couple of years ago, I was searching for general information about hashing algorithms, and found the FIPS PUB 202 - SHA-3 standard[^], which at the time was still a draft. I started playing with it, and this article presents the resulting implementation.
The above document is pretty self explanatory. I therefore encourage you to have a look at it before reading the series. 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 the provided solution. Sorry to 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 bit-mask 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 base-2 logarithm of specified integer number. Bitwise, it corresponds to the offset of the highest non-zero bit in the number. This implementation is the one proposed in Bit Twiddling Hacks - Find the log base 2 of an N-bit 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 8-bits 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.
A 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 bit-flags 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 item-accessor 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 the 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 byte-aligned; if so, a simple array copy can take place; if not, then the method resorts to the (slower) bit-enumerative 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 byte-aligned.
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 KECCAK-p 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.
The proposed solution is composed of three projects:
- a DLL project holding the implementation
- a unit-test project to test the DLL
- a quick console program to play with it
Unit-tests project actually holds three tests for the Bin class and seventy-five 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);
}
The above snippet produces a random result which looks like this:
At the time I discovered sponge constructions and started playing with them - during the 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 low-level 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 3D-array 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 base-2 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 sponge 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 |
| Base-2 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 3D-addressing 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 3D-coordinates:
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 KECCAK-p 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 fifty-nine 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 fixed-length
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 fixed-length 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 absorption phase, where the message is integrally processed through the sponge construction.
- a squeezing phase, which produces as many output bytes as requested 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 KECCAK-p[b,nr] 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 0s 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. KECCAK-p PERMUTATIONS.
A KECCAK-p[b,nr] 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 (nr).
In proposed solution, a KECCAK-p[b,nr] 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 twenty-five 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 non-linear 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 fed 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 KECCAK-p 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 KECCAK-f permutations are a specialization of the KECCAK-p permutations to the case where the number of rounds of a single iteration (nr) equals 12 + 2l[10].
Formally, a KECCAK-f[b] permutation is a KECCAK-p[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 KECCAK-f 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 KECCAK-p[b,nr] permutation where b equals 1600, nr = 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 SHA-3 hashing functions SHA3-224, SHA3-256, SHA3-384 and SHA3-512 (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 |
| SHA3-224 | 224 | 28 | 448 | 56 | 1152 | 144 |
| SHA3-256 | 256 | 32 | 512 | 64 | 1088 | 136 |
| SHA3-384 | 384 | 48 | 768 | 96 | 832 | 104 |
| SHA3-512 | 512 | 64 | 1024 | 128 | 576 | 72 |
SHA-3 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 extendable-output functions
RawSHAKE128, RawSHAKE256, SHAKE128 and SHAKE256. Extendable-Output Functions (XOFs) 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 extandable-output functions
SHAKE and RawSHAKE XOFs 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 extendable-output 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 fixed-length bitstrings are available at NIST - Cryptographic Standards and Guidelines / Examples with Intermediate Values / Secure Hashing / FIPS 202 - SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions[^]. They provide expected values for messages of specific widths 0, 5, 30, 1600, 1605 and 1630 bits respectively, for the four SHA-3 hashing function, and for both SHAKE128 and SHAKE256 XOFs. I did not find any example file for RawSHAKE128 and RawSHAKE256 XOFs.
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, "SHA3-224 sample of 0-bit message", _message0000, 224);
sha3 = Sha3Permutation.Sha3_256;
Output(sha3, "SHA3-256 sample of 0-bit message", _message0000, 256);
sha3 = Sha3Permutation.Sha3_384;
Output(sha3, "SHA3-384 sample of 0-bit message", _message0000, 384);
sha3 = Sha3Permutation.Sha3_512;
Output(sha3, "SHA3-512 sample of 0-bit 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 thirty-six tests. Here is what the snippet above produces (in Release mode):
All tests actually produce expected values.
Now, we have some confidence in the produced results, we may want to integrate this SHA-3 permutations implementation to the .NET HashAlgorithm infrastructure, don't we? This needs, at least, the Initialize, HashCore and HashFinal methods to be overridden.
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.
Performance-wise, 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 SHA3-224 hashing of an input message of eight million bits (8Mb = 1MB) takes about 41 seconds on my computer. If you intend to perform SHA-3 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 KECCAK-p 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 home-made.
- 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 KECCAK-p[b,nr]
- 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 KECCAK-f
- 28th January, 2018: Version 1.0.0.0 - First publication
