14,984,194 members
Articles / Security / Cryptography
Article
Posted 29 Jan 2018

18.4K views
11 bookmarked

# Sponge Constructions and SHA-3 Hashing Functions : a C# implementation

Rate me:
This article describes a C# implementation of the sponge construction and its use for SHA-3 hashing operations.

## Introduction

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 - SHA-3 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.

## Static methods

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(-1, 5) == 4`
C#
```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"`.
C#
```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[^].
C#
```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;
}```

## The Bitstring class

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.

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

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:

C#
```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);
}
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) {
}
else {
}
}
}
}```

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.

C#
```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() {
// HashCoder<T> class is not described in this article, but source file
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.

C#
```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:

1. create a bitstring of specified length:
C#
```public Bitstring(int length) {
if (length < 0) {
throw new ArgumentOutOfRangeException(nameof(length));
}
_length = length;
_data = new byte[(int)Math.Ceiling((double)_length / BlockBitSize)];
}```
2. create an empty bitstring (a bitstring whose length is zero):
C#
`public Bitstring() : this(0) { }`
3. create a bitstring from an existing one (copy constructor):
C#
```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;
}```
4. create a bitstring from an enumeration of bits:
C#
```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) {
// 200 bytes -> 1600 bits for most common used Keccak-p permutations
List<byte> bytes = new List<byte>(200);
byte value = 0;
int index = 0;
length = 0;
foreach (bool bit in bits) {
length++;
if (bit) {
value |= (byte)(1 << index);
}
if (++index > 7) {
index = 0;
value = 0;
}
}
}
}
return bytes.ToArray();
}```
5. 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.
C#
```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;
// Stop the loop either when there is less than 8 bits to parse, or when desired length
// exceeds the size of specified string.
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));
}
}

// Only 0's, 1's or whitespaces, empty string allowed
= 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;
}```
6. create a bitstring from a `byte` array and an optional length:
C#
```public Bitstring(byte[] data, int length = -1) {
// Sanity checks
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 the full range of bits is to be considered, whole process is a lot simpler.
if (_length != bitCount) {
// How many blocks will we need?
count = (int)Math.Ceiling((double)_length / BlockBitSize);
Array.Resize(ref data, count);
// If the last block is not full, zero the trailing bits which do not belong
// to the bitstring.
int remaining = _length % BlockBitSize;
if (remaining > 0) {
}
}
_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.

1. 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.
C#
```public Bitstring Append(byte[] bytes) {
if (bytes != null) {
if ((_length % BlockBitSize) == 0) { // Array copy if aligned data
int count = bytes.Length;
int oldCount = BlockCount;
Array.Resize(ref _data, oldCount + count);
Array.Copy(bytes, 0, _data, oldCount, count);
_length += count << Shift;
}
else {                               // Enumeration if unaligned data
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;
}```
2. 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.
C#
```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;
}```
3. A `SwapBits` method which swaps the bits at specified indices (algorithm used is this specified here):
C#
```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);
}```
4. 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.
C#
```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.

1. A `Substring` method which allows to get any substring of the bitstring:
C#
```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));
}
}```
2. A `Truncate` method which allows to get the specified number of bits from the start of the bitstring.
C#
```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) {
}
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 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.

C#
```static void Main(string[] args) {
Random random = new Random();
Func<Bitstring> randomBitstring = () => { return Bitstring.Random(random, 42); };
Console.WriteLine(randomBitstring().ToBinString());             // Binary, no spacing
Console.WriteLine(randomBitstring().ToBinString(4));            // Binary, spacing every fourth digit
Console.WriteLine(randomBitstring().ToHexString(true, false));  // Hexadecimal, spacing, lowercase
Console.WriteLine(randomBitstring().ToHexString(false, true));  // Hexadecimal, no spacing, uppercase
Console.WriteLine(randomBitstring().ToHexString(false, false)); // Hexadecimal, no spacing, lowercase
Bitstring bitstring = new Bitstring("10100101");
Console.WriteLine(bitstring.ToBinString());
bitstring.Xor(Bitstring.Ones(8));
Console.WriteLine(bitstring.ToBinString());
}
```

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 low-level object used by sponge constructions.

## The SpongeState class

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 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) Number of bits in a lane (w) Base-2 logarithm of w (l) 25 50 100 200 400 800 1600 1 2 4 8 16 32 64 0 1 2 3 4 5 6

The `SpongeSize` structure is defined as:

C#
```public struct SpongeSize
{

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.

C#
```public sealed class SpongeState
{

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:

C#
```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:

1. z is incremented until it reaches w, in which case z is reset to zero.
2. When z is reset, x is incremented until it reaches 5, in which case x is reset to zero.
3. 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:

C#
```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.

C#
```public struct Lane
{

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:

C#
```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:

C#
`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:

C#
```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:

1. create a new sponge state specifying its size and rate:
C#
```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);
}```
2. create a sponge state from an existing bitstring and a rate:
C#
```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;
}```
3. create a sponge state from an existing one:
C#
```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 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:

1. an aborption phase, where the message is integrally processed through the sponge construction.
2. a squeezing phase, which produces as many output bytes as resquested from the sponge construction.

At this stage, we will define its interface.

C#
```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:

C#
```public abstract class SpongeConstruction : ISpongeConstruction
{

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());
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

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

C#
```public class KeccakPermutation : SpongeConstruction
{

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);
}
}
}```

### The step mappings

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]. C#Copy Code ```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]. C#Copy Code ```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]. C#Copy Code ```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]. C#Copy Code ```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` 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` interface. C#Copy Code ```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 _roundConstants = new Dictionary { { 0, true } }; private static readonly Dictionary _roundTConstants = new Dictionary(); private struct RoundT : IEquatable { 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.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; }```

The `KeccakPermutation` class also overrides the `GetPadding` method and provides the pad10*1[2] padding rule.

C#
```protected override Bitstring GetPadding(int r, int m) {
int j = Bin.Mod(-m - 2, r);
Bitstring pad = new Bitstring(j + 2);
}```

## The KECCAK-f permutations

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.

C#
```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

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

C#
```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);
}
}```

## The SHA-3 hashing functions and SHAKE extendable-output functions

Based on the KECCAK[c] permutations, eight functions are then defined:

• Four SHA-3 hashing fuctions 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
C#
```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 (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 extandable-output 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.

C#
```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.

## Testing the functions

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 XOF's. I did not find any example file for RawSHAKE128 and RawSHAKE256 XOF's.

C#
```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...");
}
}```

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.

## SHA-3 permutations as hash algorithms

Now we have some confidence on 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 overriden.

C#
```public sealed class Sha3HashAlgorithm : HashAlgorithm
{
public enum Size : byte
{
Bits224,
Bits256,
Bits384,
Bits512
}

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.

## Credits

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

## References

1. Cryptographic sponge functions - Page 11 - 2.1.1 Bitstrings
2. The KECCAK reference - Page 7 - 1.1.2 Padding rules
3. FIPS PUB 202 - Page 16 - 3.3 KECCAK-p[b,nr]
4. FIPS PUB 202 - Page 11 - 3.2 Step Mappings
5. FIPS PUB 202 - Page 11 - 3.2.1 Specification of θ
6. FIPS PUB 202 - Page 12 - 3.2.2 Specification of ρ
7. FIPS PUB 202 - Page 14 - 3.2.3 Specification of π
8. FIPS PUB 202 - Page 15 - 3.2.4 Specification of χ
9. FIPS PUB 202 - Page 15 - 3.2.5 Specification of ι
10. FIPS PUB 202 - Page 17 - 3.4 Comparison with KECCAK-f

## History

• 2018/01/28: Version 1.0.0.0 - First publication

## Share

Olivier is currently working as a network administrator in an IT Company near Lyon, France.

He discovered computer development in the early 80's, beginning with Basic programs. Since then he has worked with Visual Basic 6, and later with the .NET platform since 2003.

Now he's using .NET products to develop small applications helping him in his every-day tasks. He prefers C# actually.

 First Prev Next
 ShakePermutation shake128 and 256 question FloatingPoint44411-May-20 9:01 FloatingPoint444 11-May-20 9:01
 Re: ShakePermutation shake128 and 256 question phil.o12-May-20 3:31 phil.o 12-May-20 3:31
 Shake 128 Implementation FloatingPoint44426-Apr-20 4:16 FloatingPoint444 26-Apr-20 4:16
 Re: Shake 128 Implementation phil.o5-May-20 8:07 phil.o 5-May-20 8:07
 Re: Shake 128 Implementation FloatingPoint44412-May-20 2:50 FloatingPoint444 12-May-20 2:50
 Re: Shake 128 Implementation phil.o12-May-20 3:16 phil.o 12-May-20 3:16
 Keccak Member 1450885322-Jun-19 2:35 Member 14508853 22-Jun-19 2:35
 Re: Keccak phil.o26-Aug-19 3:53 phil.o 26-Aug-19 3:53
 Sha3 hash results Member 1411612414-Jan-19 1:47 Member 14116124 14-Jan-19 1:47
 Re: Sha3 hash results phil.o23-Mar-19 0:29 phil.o 23-Mar-19 0:29
 Last Visit: 31-Dec-99 18:00     Last Update: 5-Aug-21 15:30 Refresh 1