No Room for Haraka Hashing in FIPS 205
In tests, the Haraka hashing method for SPHINCS+ beats the SHA256 version by a considerable margin, and which also beats the SHAKE256 method [here]:
But, there’s no room for Haraka in the FIPS 205 specification, as it is not a NIST defined hashing method, while SHA-256 and SHAKE-256 (derived from SHA-3) are. This means that FIPS 205 can be around three times slower than the SPHINCS+ with the Haraka version.
Here is a SPHINCS+ version with the SHA-256 and SHAKE-256 hashes:
Here is a SPHINCS+ version with the Haraka hash:
Haraka256
In cryptography, we often focus on making sure we can create a hash for any number of bytes as an input. But what happens if we have a short input that we want to hash? Using methods such as SHA-1 and SHA-2 (aka SHA-256) will often be inefficient as they tend to compress (or squeeze) the data inputs through a number of stages. The focus is thus to squeeze the data down to a standard number of bits and then add collision protection. Haraka is different and focuses on inputs of just 256 bits (32 bytes) or 512 bits (64 bytes) [here]:
This makes the method is useful when we are dealing with key and hash values, and is especially useful for hash-based signatures. The output is 256 bits long, but where the input can either be 256 bits (Haraka256) or 512 bits (Haraka512). Overall, the greatest inefficiency for SHA-256 and SHA3–256 is when they are dealing with small message lengths of 500 bytes and less:
The Haraka method, too, has been optimized with AES instructions (AES-NI) and which are often supported within the hardware of the processor. As Haraka is focused on short messages, the number of rounds within the hashing process has been reduced. Along with this, we normally have to integrate collision resistance within our hashing method, but this is not required within a short-message input scheme.
Overall, the approach uses an AES approach with the following internal structure:
The internal structure then uses an SPN (Substitution Permutation Network) and where an AES-defined s-Box is used to scramble the data, and which is then fed into a mixer function:
An assessment of SPHINCS+ for Haswell shows a 50% improvement in speed for signing, a 60% improvement for key generation, and a 115% improvement in verification.
Coding
Last year, Bouncy Castle for C# added SPHINCS+ and a core part of this is the addition of Haraka256 and Haraka512 [here]:
So, now let’s code for this, and also integrate the test vectors from this paper [here]:
We can create a Dotnet console project for .NET 9.0 with:
dotnet new console --framework net9.0First, we install the Bouncy Castle library:
dotnet add package BouncyCastle.Cryptography --version 2.4.0Next, some code [here]:
namespace AES
{
using System.Security.Cryptography;
using Org.BouncyCastle.Crypto.Digests;
class Program
{
static void Main(string[] args)
{
string str="hello";
if (args.Length >0) str=args[0];
try {
Console.WriteLine ("Message:\t{0}\n",str);
var h1 = new Haraka256Digest();
var test=Convert.FromHexString("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f");
h1.BlockUpdate(test, 0, test.Length);
var hash1=new byte[h1.GetDigestSize()];
h1.DoFinal(hash1, 0);
Console.WriteLine ("Haraka256:\t\t{0}\n Input (hex): [{1}]\n",Convert.ToHexString(hash1),Convert.ToHexString(test));
var h2 = new Haraka256Digest();
str=str.PadRight(32, (char)0);
h2.BlockUpdate(System.Text.Encoding.UTF8.GetBytes(str), 0, str.Length);
var hash2=new byte[h2.GetDigestSize()];
h2.DoFinal(hash2, 0);
Console.WriteLine ("Haraka256:\t\t{0}\n Input: [{1}]\n\n",Convert.ToHexString(hash2),str);
var h3 = new Haraka512Digest();
var test2=Convert.FromHexString("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f");
h3.BlockUpdate(test2, 0, test2.Length);
var hash3=new byte[h3.GetDigestSize()];
h3.DoFinal(hash3, 0);
Console.WriteLine ("Haraka512:\t\t{0}\n Input (hex): [{1}]\n",Convert.ToHexString(hash3),Convert.ToHexString(test2));
var h4 = new Haraka512Digest();
str=str.PadRight(64, (char)0);
h4.BlockUpdate(System.Text.Encoding.UTF8.GetBytes(str), 0, str.Length);
var hash4=new byte[h4.GetDigestSize()];
h4.DoFinal(hash4, 0);
Console.WriteLine ("Haraka512:\t\t{0}\n Input: [{1}]\n",Convert.ToHexString(hash4),str);
} catch (Exception e) {
Console.WriteLine("Error: {0}",e.Message);
}
}
}
}Haraka256 takes a fixed input of 32 bytes and Haraka512 takes a fixed input of 64 bytes. For this, we will pad the input string with NULL characters so that it fills the input to the correct size.
A sample run is [here]:
Message: hello
Haraka256: 8027CCB87949774B78D0545FB72BF70C695C2A0923CBD47BBA1159EFBF2B2C1C
Input (hex): [000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F]
Haraka256: 99DA89DE939EC4DB4A20D58235AFA906F3C9649663A80A55DB6C88AD6BEAAC4C
Input: [hello ]
Haraka512: BE7F723B4E80A99813B292287F306F625A6D57331CAE5F34DD9277B0945BE2AA
Input (hex): [000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2F303132333435363738393A3B3C3D3E3F]
Haraka512: 964597082F33CDADBBBE99C3913BB8B589FD5A7C9999618D62EAF8F2E43F77B0
Input: [hello ]We can see the two test vectors work and where an input of 0x000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F gives a hash of 0x8027CCB87949774B78D0545FB72BF70C695C2A0923CBD47BBA1159EFBF2B2C1C, and 0x000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2F303132333435363738393A3B3C3D3E3F gives a hash of 0xBE7F723B4E80A99813B292287F306F625A6D57331CAE5F34DD9277B0945BE2AA and which ties-up with the test vector:
Conclusions
In a digital world where every single tick of the clock consumes energy and time, it is good to optimise our implementations. This is especially important when we look at embedded devices with battery power, as every extra tick of the clock will consume a bit more energy. So, while SHA-1 and SHA-256 might be great at being general-purpose methods, Haraka focuses on those small inputs and keeps the same level of security.
References
[1] Kölbl, S., Lauridsen, M. M., Mendel, F., & Rechberger, C. (2016). Haraka v2–efficient short-input hashing for post-quantum applications. IACR Transactions on Symmetric Cryptology, 1–29. [here]
[2] Haraka v2, Github. Link: [here]
