Portable C++ Hashing Library

posted February 5, 2014 by Stephan Brumme, updated June 14, 2014

Introduction

Let's start with the core features of my C++ hashing library:

computes CRC32, MD5, SHA1 and SHA256 (most common member of the SHA2 functions), Keccak and its SHA3 sibling
optional HMAC (keyed-hash message authentication code)
no external dependencies, small code size
can work chunk-wise (for example when reading streams block-by-block)
portable: supports Windows and Linux, tested on Little Endian and Big Endian CPUs
roughly as fast as Linux core hashing functions
open source, zlib license

Usage

Since there are no external dependencies, not even dependencies within the library itself, all you need is to include the header of the hashing algorithm of your choice and add the identically named .cpp to your project. That means if you want to add SHA256 hashing to your C++ program, you only have to include sha256.h and sha256.cpp in your project.

If you prefer SHA256, then your code will look like this:

hide


     // SHA2 test program
     #include "sha256.h"
     #include <iostream> // for std::cout only, not needed for hashing library
     
     int main(int, char**)
     {
       // create a new hashing object
       SHA256 sha256;
     
       // hashing an std::string
       std::cout << sha256("Hello World") << std::endl;
       // => a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
     
       // hashing a buffer of bytes
       const char* buffer = "How are you";
       std::cout << sha256(buffer, 11) << std::endl;
       // => 9c7d5b046878838da72e40ceb3179580958df544b240869b80d0275cc07209cc
     
       // or in a streaming fashion (re-use "How are you")
       SHA256 sha256stream;
       const char* url = "create.stephan-brumme.com"; // 25 bytes
       int step = 5;
       for (int i = 0; i < 25; i += step)
         sha256stream.add(url + i, step); // add five bytes at a time
       std::cout << sha256stream.getHash() << std::endl;
       // => 82aa771f1183c52f973c798c9243a1c73833ea40961c73e55e12430ec77b69f6
     
       return 0;
     }

You can download the latest version of each source file on its own but I strongly recommend fetching them from my GIT repository. It can be found below the last download link.

Download (zipped)

Download hash-library.zip

Latest release: February 2, 2021, size: 60.9 kBytes

CRC32: 59f5a159
MD5: 52c0178ea4869f87e07496b8666e5acc
SHA1: 6ef06febecf46cd59477189fe69de73c5ace89e2
SHA256:4f7722da48efc432fd15bf436d312805f5335498a3087153a8d229bb7fa9406f

If you encounter any bugs/problems or have ideas for improving future versions, please write me an email: create@stephan-brumme.com

License

This code is licensed under the zlib License:

This software is provided 'as-is', without any express or implied warranty. In no event will the authors be held liable for any damages arising from the use of this software. Permission is granted to anyone to use this software for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions: 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 3. This notice may not be removed or altered from any source distribution.zlib License

Changelog

version 8
- latest and greatest
- February 2, 2021
- bugfix: repeated call to getHash returned wrong value if nothing new added (SHA3/Keccak only)
- Git tag hash_library_v8
version 7
- March 24, 2015
- SHA3/224 and Keccak/224 returned incomplete hash
- Git tag hash_library_v7
version 6
- February 27, 2015
- fixed padding bug in Keccak and SHA3
- added HMAC
- added simple test suite
- Git tag hash_library_v6
version 5
- September 25, 2014
- fix compiler warnings and misspelled _MSC_VER macro
- Git tag hash_library_v5
version 4
- June 14, 2014
- added SHA3 (draft FIPS 202, April 2014)
- Git tag hash_library_v4
version 3
- April 9, 2014
- added shared base class Hash (optional)
- Git tag hash_library_v3
version 2
- March 25, 2014
- added Keccak
- Git tag hash_library_v2
version 1
- February 5, 2014
- initial release
- Git tag hash_library_v1

Interface

All implemented hashing algorithms (CRC32, MD5, SHA1, SHA256 and SHA3/Keccak) share the same public interface:

they have a parameterless constructor
if the data-to-be-hashed is fully loaded into memory:
1. operator() is overloaded for std::string
2. operator() is overloaded for an arbitrary pointer void* (and the buffer size size_t)
compute hash of streaming data, where not all bytes are available instantly:
1. add a number of bytes with add
2. when done, compute the hash with getHash
if you want to re-use a hash object with new data, call reset

hide base class


     // //////////////////////////////////////////////////////////
     // hash.h
     // Copyright (c) 2014,2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #pragma once
     
     #include <string>
     
     /// abstract base class
     class Hash
     {
     public:
       /// compute hash of a memory block
       virtual std::string operator()(const void* data, size_t numBytes) = 0;
       /// compute hash of a string, excluding final zero
       virtual std::string operator()(const std::string& text) = 0;
     
       /// add arbitrary number of bytes
       virtual void add(const void* data, size_t numBytes) = 0;
     
       /// return latest hash as hex characters
       virtual std::string getHash() = 0;
     
       /// restart
       virtual void reset() = 0;
     };

The base class Hash was introduced in version 3 and is optional - in fact it's disabled by default.
To enable it, open crc32.h, md5.h, sha1.h, sha256.h, keccak.h and sha3.h, remove the slashes in front of #include "hash.h" (line 9) and derive from public Hash (about line 37).

Containing just 110 lines of code, the file digest.cpp computes all presented hashes:

hide program digest.cpp


     // //////////////////////////////////////////////////////////
     // digest.cpp
     // Copyright (c) 2014,2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     // g++ -O3 digest.cpp crc32.cpp md5.cpp sha1.cpp sha256.cpp keccak.cpp sha3.cpp -o digest
     
     #include "crc32.h"
     #include "md5.h"
     #include "sha1.h"
     #include "sha256.h"
     #include "keccak.h"
     #include "sha3.h"
     
     #include <iostream>
     #include <fstream>
     
     int main(int argc, char** argv)
     {
       // syntax check
       if (argc < 2 || argc > 3)
       {
         std::cout << "./digest filename [--crc|--md5|--sha1|--sha256|--keccak|--sha3]" << std::endl;
         return 1;
       }
     
       // parameters
       std::string filename  = argv[1];
       std::string algorithm = argc == 3 ? argv[2] : "";
       bool computeCrc32     = algorithm.empty() || algorithm == "--crc";
       bool computeMd5       = algorithm.empty() || algorithm == "--md5";
       bool computeSha1      = algorithm.empty() || algorithm == "--sha1";
       bool computeSha2      = algorithm.empty() || algorithm == "--sha2" || algorithm == "--sha256";
       bool computeKeccak    = algorithm.empty() || algorithm == "--keccak";
       bool computeSha3      = algorithm.empty() || algorithm == "--sha3";
     
       CRC32  digestCrc32;
       MD5    digestMd5;
       SHA1   digestSha1;
       SHA256 digestSha2;
       Keccak digestKeccak(Keccak::Keccak256);
       SHA3   digestSha3  (SHA3  ::Bits256);
     
       // select input source: either file or standard-in
       std::ifstream file;
       std::istream* input = NULL;
       // accept std::cin, syntax will be: "./digest - --sha3 < data"
       if (filename == "-")
       {
         input = &std::cin;
       }
       else
       {
         // open file
         file.open(filename.c_str(), std::ios::in | std::ios::binary);
         if (!file)
         {
           std::cerr << "Can't open '" << filename << "'" << std::endl;
           return 2;
         }
     
         input = &file;
       }
     
       // each cycle processes about 1 MByte (divisible by 144 => improves Keccak/SHA3 performance)
       const size_t BufferSize = 144*7*1024;
       char* buffer = new char[BufferSize];
     
       // process file
       while (*input)
       {
         input->read(buffer, BufferSize);
         std::size_t numBytesRead = size_t(input->gcount());
     
         if (computeCrc32)
           digestCrc32 .add(buffer, numBytesRead);
         if (computeMd5)
           digestMd5   .add(buffer, numBytesRead);
         if (computeSha1)
           digestSha1  .add(buffer, numBytesRead);
         if (computeSha2)
           digestSha2  .add(buffer, numBytesRead);
         if (computeKeccak)
           digestKeccak.add(buffer, numBytesRead);
         if (computeSha3)
           digestSha3  .add(buffer, numBytesRead);
       }
     
       // clean up
       file.close();
       delete[] buffer;
     
       // show results
       if (computeCrc32)
         std::cout << "CRC32:      " << digestCrc32 .getHash() << std::endl;
       if (computeMd5)
         std::cout << "MD5:        " << digestMd5   .getHash() << std::endl;
       if (computeSha1)
         std::cout << "SHA1:       " << digestSha1  .getHash() << std::endl;
       if (computeSha2)
         std::cout << "SHA2/256:   " << digestSha2  .getHash() << std::endl;
       if (computeKeccak)
         std::cout << "Keccak/256: " << digestKeccak.getHash() << std::endl;
       if (computeSha3)
         std::cout << "SHA3/256:   " << digestSha3  .getHash() << std::endl;
     
       return 0;
     }

Algorithms

Descriptions of the algorithms can be found on Wikipedia (CRC32, MD5, SHA1, SHA256, Keccak, SHA3 and HMAC and). My CRC implementation is based on the Slicing-by-8 technique which I describe more in detail in my blog, too. I recently added the faster Slicing-by-16 algorithm there but not in this library to keep the code size low. The rest is pretty much a straightforward implementation of the standard algorithms.

Several years ago I wrote an online hash calculator in PHP using the built-in hashing functions. It might be useful if you want to compare your output against an "independent" implementation.

And please don't send me comments on the design of that website - I deliberately chose awkward colors ;-)

Performance

The great OpenSSL team is working hard to provide the best hashing implementations. Not only in terms of reliability but also in terms of throughput. They often convert the core routines to assembler code. So it's no surprise that their library outperformes mine.

However, when compared to the Linux coreutils, my C++ code gives about the same performance numbers. My main system runs on a Core i7 2600K CPU (3.4 GHz). In my tests I compared these libraries (64 bit binaries):

Library	Version / Settings
mine	GCC 4.7 (`g++ -O3 -march=native`)
OpenSSL	1.0.1e-fips
CoreUtils	8.4

Yes, I'm aware that newer versions are available - especially CoreUtils - but I used the default versions of my CentOS 6.5 distribution.

My test file is enwik9, a snapshot of the first 1 billion bytes (1,000,000,000 bytes) of the English wikipedia from March 3, 2006.
A compressed copy can be downloaded from my server, too: GZip (296 MByte) or XZ (220 MByte).

Before running the tests I ensured that the file is completely loaded into the cache.

Algorithm	Library	command line	user time	throughput	comparison
CRC32	my code	`time ./digest enwik9 --crc`	0.45 seconds	2,222 MByte/sec
MD5	OpenSSL	`time openssl md5 enwik9`	1.47 seconds	680 MByte/sec	fastest
	my code	`time ./digest enwik9 --md5`	1.65 seconds	606 MByte/sec	12% slower
	CoreUtils	`time md5sum enwik9`	1.65 seconds	606 MByte/sec	12% slower
SHA1	OpenSSL	`time openssl sha1 enwik9`	1.43 seconds	699 MByte/sec	fastest
	my code	`time ./digest enwik9 --sha1`	2.58 seconds	388 MByte/sec	80% slower
	CoreUtils	`time sha1sum enwik9`	3.01 seconds	332 MByte/sec	110% slower
SHA256	OpenSSL	`time openssl sha256 enwik9`	4.70 seconds	213 MByte/sec	fastest
	my code	`time ./digest enwik9 --sha256`	5.98 seconds	167 MByte/sec	27% slower
	CoreUtils	`time sha256sum enwik9`	5.48 seconds	182 MByte/sec	17% slower
SHA3 / Keccak (-256)	OpenSSL	`time openssl sha3-256 enwik9`	2.78 seconds	360 MByte/sec	fastest
SHA3 / Keccak (-256)	my code	`time ./digest enwik9 --sha3`	4.17 seconds	240 MByte/sec	50% slower

Note: when performing the test on my Raspberry Pi (ARM architecture CPU) OpenSSL runs at pretty much the same speed as mine for MD5 but is 22% faster for SHA1 and 22% faster for SHA256, too. Due to limited resources, I computed only the hashes of the first 100 MByte (enwik8 instead enwik9): you can download this test file from my server compressed as GZip (35 MByte) or XZ (27 MByte).

Portability

I successfully compiled and ran the source code on all my systems / environments:

	Windows 8	CentOS 6	Debian Wheezy / ARM	Debian Wheezy / PowerPC
Visual Studio 2010	yes	-	-	-
GCC 4.4	-	yes	-	-
GCC 4.7	-	yes	-	yes
GCC 4.8	-	yes	yes	-
GCC 4.9	-	yes	yes	-
CLang / LLVM 3.0	-	yes	-	-
CLang / LLVM 3.4	-	yes	yes	-

In short: any modern C++ compiler (I have access to) happily compiles my code.

My Windows and CentOS installations are 64 bit systems. Debian Wheezy / ARM refers to my Raspberry Pi (32 bit system).
The Debian/PowerPC installation is just a QEMU virtual machine. I explicitly mention it because it is a big endian architecture - in contrast to Intel's little endian architecture. Please read my blog posting on setting up such a virtual machine, too.

The endianness is detected at compile time. On Linux systems, the library automatically includes endian.h which defines the preprocessor symbol __BYTE_ORDER.
On Windows systems (or when that symbol isn't defined), I assume a little endian machine.
On MacOS the endian.h header is found in the machine sub-directory. So please change in each cpp file the include to #include <machine/endian.h>.

Excerpts from sha256.cpp:

    
     #ifndef _MSC_VER
     #include <endian.h>
     #endif

hide


     #if defined(__BYTE_ORDER) && (__BYTE_ORDER != 0) && (__BYTE_ORDER == __BIG_ENDIAN)
       words[i] = input[i];
     #else
       words[i] = swap(input[i]);
     #endif

Swapping bytes is a common operation of all hashing algorithms. Therefore the library uses faster compiler-specific intrinsics and provides a portable fallback code path:

hide


     inline uint32_t swap(uint32_t x)
     {
     #if defined(__GNUC__) || defined(__clang__)
       return __builtin_bswap32(x);
     #endif
     #ifdef _MSC_VER
       return _byteswap_ulong(x);
     #endif
     
       return (x >> 24) |
             ((x >>  8) & 0x0000FF00) |
             ((x <<  8) & 0x00FF0000) |
              (x << 24);
     }

Code Size

Here are some statistics about the lines-of-code (counted with CLOC):

	code	comments	blank	total
hash.h	11 lines	11 lines	6 lines	28 lines
crc32.h and crc32.cpp	370 lines	66 lines	45 lines	481 lines
md5.h and md5.cpp	308 lines	82 lines	85 lines	475 lines
sha1.h and sha1.cpp	242 lines	84 lines	67 lines	393 lines
sha256.h and sha256.cpp	309 lines	93 lines	76 lines	478 lines
keccak.h and keccak.cpp	221 lines	74 lines	62 lines	357 lines
sha3.h and sha3.cpp	221 lines	74 lines	62 lines	357 lines

The CRC32 implementation is actually pretty simple but crc32.cpp contains a huge lookup table.

Keccak

Keccak is the designated SHA3 hashing algorithm. It's website contains lots of freely available code, mostly in C/C++. However, it severely lacks proper code documentation and trying to understand the way their code is structured was unexpectedly hard for me.

My implementation computes only the most common variants (all with 1600 bits of internal state): Keccak224, Keccak256, Keccak384 and Keccak512 - just use the proper enum in the constructor.

keccak.h and keccak.cpp can be found in the Git repository (scroll up) and in the downloadable zipped file. Or just read the code right here (click show):

show keccak.h


     // //////////////////////////////////////////////////////////
     // keccak.h
     // Copyright (c) 2014,2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #pragma once
     
     //#include "hash.h"
     #include <string>
     
     // define fixed size integer types
     #ifdef _MSC_VER
     // Windows
     typedef unsigned __int8  uint8_t;
     typedef unsigned __int64 uint64_t;
     #else
     // GCC
     #include <stdint.h>
     #endif
     
     
     /// compute Keccak hash (designated SHA3)
     /** Usage:
         Keccak keccak;
         std::string myHash  = keccak("Hello World");     // std::string
         std::string myHash2 = keccak("How are you", 11); // arbitrary data, 11 bytes
     
         // or in a streaming fashion:
     
         Keccak keccak;
         while (more data available)
           keccak.add(pointer to fresh data, number of new bytes);
         std::string myHash3 = keccak.getHash();
       */
     class Keccak //: public Hash
     {
     public:
       /// algorithm variants
       enum Bits { Keccak224 = 224, Keccak256 = 256, Keccak384 = 384, Keccak512 = 512 };
     
       /// same as reset()
       explicit Keccak(Bits bits = Keccak256);
     
       /// compute hash of a memory block
       std::string operator()(const void* data, size_t numBytes);
       /// compute hash of a string, excluding final zero
       std::string operator()(const std::string& text);
     
       /// add arbitrary number of bytes
       void add(const void* data, size_t numBytes);
     
       /// return latest hash as hex characters
       std::string getHash();
     
       /// restart
       void reset();
     
     private:
       /// process a full block
       void processBlock(const void* data);
       /// process everything left in the internal buffer
       void processBuffer();
     
       /// 1600 bits, stored as 25x64 bit, BlockSize is no more than 1152 bits (Keccak224)
       enum { StateSize    = 1600 / (8 * 8),
              MaxBlockSize =  200 - 2 * (224 / 8) };
     
       /// hash
       uint64_t m_hash[StateSize];
       /// size of processed data in bytes
       uint64_t m_numBytes;
       /// block size (less or equal to MaxBlockSize)
       size_t   m_blockSize;
       /// valid bytes in m_buffer
       size_t   m_bufferSize;
       /// bytes not processed yet
       uint8_t  m_buffer[MaxBlockSize];
       /// variant
       Bits     m_bits;
     };

show keccak.cpp


     // //////////////////////////////////////////////////////////
     // keccak.cpp
     // Copyright (c) 2014,2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #include "keccak.h"
     
     // big endian architectures need #define __BYTE_ORDER __BIG_ENDIAN
     #ifndef _MSC_VER
     #include <endian.h>
     #endif
     
     
     /// same as reset()
     Keccak::Keccak(Bits bits)
     : m_blockSize(200 - 2 * (bits / 8)),
       m_bits(bits)
     {
       reset();
     }
     
     
     /// restart
     void Keccak::reset()
     {
       for (size_t i = 0; i < StateSize; i++)
         m_hash[i] = 0;
     
       m_numBytes   = 0;
       m_bufferSize = 0;
     }
     
     
     /// constants and local helper functions
     namespace
     {
       const unsigned int KeccakRounds = 24;
       const uint64_t XorMasks[KeccakRounds] =
       {
         0x0000000000000001ULL, 0x0000000000008082ULL, 0x800000000000808aULL,
         0x8000000080008000ULL, 0x000000000000808bULL, 0x0000000080000001ULL,
         0x8000000080008081ULL, 0x8000000000008009ULL, 0x000000000000008aULL,
         0x0000000000000088ULL, 0x0000000080008009ULL, 0x000000008000000aULL,
         0x000000008000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL,
         0x8000000000008003ULL, 0x8000000000008002ULL, 0x8000000000000080ULL,
         0x000000000000800aULL, 0x800000008000000aULL, 0x8000000080008081ULL,
         0x8000000000008080ULL, 0x0000000080000001ULL, 0x8000000080008008ULL
       };
     
       /// rotate left and wrap around to the right
       inline uint64_t rotateLeft(uint64_t x, uint8_t numBits)
       {
         return (x << numBits) | (x >> (64 - numBits));
       }
     
       /// convert litte vs big endian
       inline uint64_t swap(uint64_t x)
       {
     #if defined(__GNUC__) || defined(__clang__)
         return __builtin_bswap64(x);
     #endif
     #ifdef _MSC_VER
         return _byteswap_uint64(x);
     #endif
     
         return  (x >> 56) |
                ((x >> 40) & 0x000000000000FF00ULL) |
                ((x >> 24) & 0x0000000000FF0000ULL) |
                ((x >>  8) & 0x00000000FF000000ULL) |
                ((x <<  8) & 0x000000FF00000000ULL) |
                ((x << 24) & 0x0000FF0000000000ULL) |
                ((x << 40) & 0x00FF000000000000ULL) |
                 (x << 56);
       }
     
     
       /// return x % 5 for 0 <= x <= 9
       unsigned int mod5(unsigned int x)
       {
         if (x < 5)
           return x;
     
         return x - 5;
       }
     }
     
     
     /// process a full block
     void Keccak::processBlock(const void* data)
     {
     #if defined(__BYTE_ORDER) && (__BYTE_ORDER != 0) && (__BYTE_ORDER == __BIG_ENDIAN)
     #define LITTLEENDIAN(x) swap(x)
     #else
     #define LITTLEENDIAN(x) (x)
     #endif
     
       const uint64_t* data64 = (const uint64_t*) data;
       // mix data into state
       for (unsigned int i = 0; i < m_blockSize / 8; i++)
         m_hash[i] ^= LITTLEENDIAN(data64[i]);
     
       // re-compute state
       for (unsigned int round = 0; round < KeccakRounds; round++)
       {
         // Theta
         uint64_t coefficients[5];
         for (unsigned int i = 0; i < 5; i++)
           coefficients[i] = m_hash[i] ^ m_hash[i + 5] ^ m_hash[i + 10] ^ m_hash[i + 15] ^ m_hash[i + 20];
     
         for (unsigned int i = 0; i < 5; i++)
         {
           uint64_t one = coefficients[mod5(i + 4)] ^ rotateLeft(coefficients[mod5(i + 1)], 1);
           m_hash[i     ] ^= one;
           m_hash[i +  5] ^= one;
           m_hash[i + 10] ^= one;
           m_hash[i + 15] ^= one;
           m_hash[i + 20] ^= one;
         }
     
         // temporary
         uint64_t one;
     
         // Rho Pi
         uint64_t last = m_hash[1];
         one = m_hash[10]; m_hash[10] = rotateLeft(last,  1); last = one;
         one = m_hash[ 7]; m_hash[ 7] = rotateLeft(last,  3); last = one;
         one = m_hash[11]; m_hash[11] = rotateLeft(last,  6); last = one;
         one = m_hash[17]; m_hash[17] = rotateLeft(last, 10); last = one;
         one = m_hash[18]; m_hash[18] = rotateLeft(last, 15); last = one;
         one = m_hash[ 3]; m_hash[ 3] = rotateLeft(last, 21); last = one;
         one = m_hash[ 5]; m_hash[ 5] = rotateLeft(last, 28); last = one;
         one = m_hash[16]; m_hash[16] = rotateLeft(last, 36); last = one;
         one = m_hash[ 8]; m_hash[ 8] = rotateLeft(last, 45); last = one;
         one = m_hash[21]; m_hash[21] = rotateLeft(last, 55); last = one;
         one = m_hash[24]; m_hash[24] = rotateLeft(last,  2); last = one;
         one = m_hash[ 4]; m_hash[ 4] = rotateLeft(last, 14); last = one;
         one = m_hash[15]; m_hash[15] = rotateLeft(last, 27); last = one;
         one = m_hash[23]; m_hash[23] = rotateLeft(last, 41); last = one;
         one = m_hash[19]; m_hash[19] = rotateLeft(last, 56); last = one;
         one = m_hash[13]; m_hash[13] = rotateLeft(last,  8); last = one;
         one = m_hash[12]; m_hash[12] = rotateLeft(last, 25); last = one;
         one = m_hash[ 2]; m_hash[ 2] = rotateLeft(last, 43); last = one;
         one = m_hash[20]; m_hash[20] = rotateLeft(last, 62); last = one;
         one = m_hash[14]; m_hash[14] = rotateLeft(last, 18); last = one;
         one = m_hash[22]; m_hash[22] = rotateLeft(last, 39); last = one;
         one = m_hash[ 9]; m_hash[ 9] = rotateLeft(last, 61); last = one;
         one = m_hash[ 6]; m_hash[ 6] = rotateLeft(last, 20); last = one;
                           m_hash[ 1] = rotateLeft(last, 44);
     
         // Chi
         for (unsigned int j = 0; j < StateSize; j += 5)
         {
           // temporaries
           uint64_t one = m_hash[j];
           uint64_t two = m_hash[j + 1];
     
           m_hash[j]     ^= m_hash[j + 2] & ~two;
           m_hash[j + 1] ^= m_hash[j + 3] & ~m_hash[j + 2];
           m_hash[j + 2] ^= m_hash[j + 4] & ~m_hash[j + 3];
           m_hash[j + 3] ^=      one      & ~m_hash[j + 4];
           m_hash[j + 4] ^=      two      & ~one;
         }
     
         // Iota
         m_hash[0] ^= XorMasks[round];
       }
     }
     
     
     /// add arbitrary number of bytes
     void Keccak::add(const void* data, size_t numBytes)
     {
       const uint8_t* current = (const uint8_t*) data;
     
       if (m_bufferSize > 0)
       {
         while (numBytes > 0 && m_bufferSize < m_blockSize)
         {
           m_buffer[m_bufferSize++] = *current++;
           numBytes--;
         }
       }
     
       // full buffer
       if (m_bufferSize == m_blockSize)
       {
         processBlock((void*)m_buffer);
         m_numBytes  += m_blockSize;
         m_bufferSize = 0;
       }
     
       // no more data ?
       if (numBytes == 0)
         return;
     
       // process full blocks
       while (numBytes >= m_blockSize)
       {
         processBlock(current);
         current    += m_blockSize;
         m_numBytes += m_blockSize;
         numBytes   -= m_blockSize;
       }
     
       // keep remaining bytes in buffer
       while (numBytes > 0)
       {
         m_buffer[m_bufferSize++] = *current++;
         numBytes--;
       }
     }
     
     
     /// process everything left in the internal buffer
     void Keccak::processBuffer()
     {
       unsigned int blockSize = 200 - 2 * (m_bits / 8);
     
       // add padding
       size_t offset = m_bufferSize;
       // add a "1" byte
       m_buffer[offset++] = 1;
       // fill with zeros
       while (offset < blockSize)
         m_buffer[offset++] = 0;
     
       // and add a single set bit
       m_buffer[blockSize - 1] |= 0x80;
     
       processBlock(m_buffer);
     }
     
     
     /// return latest hash as 16 hex characters
     std::string Keccak::getHash()
     {
       // save hash state
       uint64_t oldHash[StateSize];
       for (unsigned int i = 0; i < StateSize; i++)
         oldHash[i] = m_hash[i];
     
       // process remaining bytes
       processBuffer();
     
       // convert hash to string
       static const char dec2hex[16 + 1] = "0123456789abcdef";
     
       // number of significant elements in hash (uint64_t)
       unsigned int hashLength = m_bits / 64;
     
       std::string result;
       for (unsigned int i = 0; i < hashLength; i++)
         for (unsigned int j = 0; j < 8; j++) // 64 bits => 8 bytes
         {
           // convert a byte to hex
           unsigned char oneByte = (unsigned char) (m_hash[i] >> (8 * j));
           result += dec2hex[oneByte >> 4];
           result += dec2hex[oneByte & 15];
         }
     
       // Keccak224's last entry in m_hash provides only 32 bits instead of 64 bits
       unsigned int remainder = m_bits - hashLength * 64;
       unsigned int processed = 0;
       while (processed < remainder)
       {
         // convert a byte to hex
         unsigned char oneByte = (unsigned char) (m_hash[hashLength] >> processed);
         result += dec2hex[oneByte >> 4];
         result += dec2hex[oneByte & 15];
     
         processed += 8;
       }
     
       // restore state
       for (unsigned int i = 0; i < StateSize; i++)
         m_hash[i] = oldHash[i];
     
       return result;
     }
     
     
     /// compute Keccak hash of a memory block
     std::string Keccak::operator()(const void* data, size_t numBytes)
     {
       reset();
       add(data, numBytes);
       return getHash();
     }
     
     
     /// compute Keccak hash of a string, excluding final zero
     std::string Keccak::operator()(const std::string& text)
     {
       reset();
       add(text.c_str(), text.size());
       return getHash();
     }

SHA3

In April 2014 the SHA3 proposal was slightly changed by the FIPS 202 draft (see here).
All they did is adding two bytes to the message (zero and one). The code change is minimal (just one line) but as a result, Keccak hashes differ from their SHA3 counterparts.
Most SHA3 implementations on the internet are in fact Keccak implementations which is extremely confusing.

Here is a "real" SHA3 implemetation (at least one that computes the same result vectors as the FIPS 202 draft):

show sha3.h


     // //////////////////////////////////////////////////////////
     // sha3.h
     // Copyright (c) 2014,2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #pragma once
     
     //#include "hash.h"
     #include <string>
     
     // define fixed size integer types
     #ifdef _MSC_VER
     // Windows
     typedef unsigned __int8  uint8_t;
     typedef unsigned __int64 uint64_t;
     #else
     // GCC
     #include <stdint.h>
     #endif
     
     
     /// compute SHA3 hash
     /** Usage:
         SHA3 sha3;
         std::string myHash  = sha3("Hello World");     // std::string
         std::string myHash2 = sha3("How are you", 11); // arbitrary data, 11 bytes
     
         // or in a streaming fashion:
     
         SHA3 sha3;
         while (more data available)
           sha3.add(pointer to fresh data, number of new bytes);
         std::string myHash3 = sha3.getHash();
       */
     class SHA3 //: public Hash
     {
     public:
       /// algorithm variants
       enum Bits { Bits224 = 224, Bits256 = 256, Bits384 = 384, Bits512 = 512 };
     
       /// same as reset()
       explicit SHA3(Bits bits = Bits256);
     
       /// compute hash of a memory block
       std::string operator()(const void* data, size_t numBytes);
       /// compute hash of a string, excluding final zero
       std::string operator()(const std::string& text);
     
       /// add arbitrary number of bytes
       void add(const void* data, size_t numBytes);
     
       /// return latest hash as hex characters
       std::string getHash();
     
       /// restart
       void reset();
     
     private:
       /// process a full block
       void processBlock(const void* data);
       /// process everything left in the internal buffer
       void processBuffer();
     
       /// 1600 bits, stored as 25x64 bit, BlockSize is no more than 1152 bits (Keccak224)
       enum { StateSize    = 1600 / (8 * 8),
              MaxBlockSize =  200 - 2 * (224 / 8) };
     
       /// hash
       uint64_t m_hash[StateSize];
       /// size of processed data in bytes
       uint64_t m_numBytes;
       /// block size (less or equal to MaxBlockSize)
       size_t   m_blockSize;
       /// valid bytes in m_buffer
       size_t   m_bufferSize;
       /// bytes not processed yet
       uint8_t  m_buffer[MaxBlockSize];
       /// variant
       Bits     m_bits;
     };

show sha3.cpp


     // //////////////////////////////////////////////////////////
     // sha3.cpp
     // Copyright (c) 2014,2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #include "sha3.h"
     
     // big endian architectures need #define __BYTE_ORDER __BIG_ENDIAN
     #ifndef _MSC_VER
     #include <endian.h>
     #endif
     
     #include <iostream>
     
     
     /// same as reset()
     SHA3::SHA3(Bits bits)
     : m_blockSize(200 - 2 * (bits / 8)),
       m_bits(bits)
     {
       reset();
     }
     
     
     /// restart
     void SHA3::reset()
     {
       for (size_t i = 0; i < StateSize; i++)
         m_hash[i] = 0;
     
       m_numBytes   = 0;
       m_bufferSize = 0;
     }
     
     
     /// constants and local helper functions
     namespace
     {
       const unsigned int Rounds = 24;
       const uint64_t XorMasks[Rounds] =
       {
         0x0000000000000001ULL, 0x0000000000008082ULL, 0x800000000000808aULL,
         0x8000000080008000ULL, 0x000000000000808bULL, 0x0000000080000001ULL,
         0x8000000080008081ULL, 0x8000000000008009ULL, 0x000000000000008aULL,
         0x0000000000000088ULL, 0x0000000080008009ULL, 0x000000008000000aULL,
         0x000000008000808bULL, 0x800000000000008bULL, 0x8000000000008089ULL,
         0x8000000000008003ULL, 0x8000000000008002ULL, 0x8000000000000080ULL,
         0x000000000000800aULL, 0x800000008000000aULL, 0x8000000080008081ULL,
         0x8000000000008080ULL, 0x0000000080000001ULL, 0x8000000080008008ULL
       };
     
       /// rotate left and wrap around to the right
       inline uint64_t rotateLeft(uint64_t x, uint8_t numBits)
       {
         return (x << numBits) | (x >> (64 - numBits));
       }
     
       /// convert litte vs big endian
       inline uint64_t swap(uint64_t x)
       {
     #if defined(__GNUC__) || defined(__clang__)
         return __builtin_bswap64(x);
     #endif
     #ifdef _MSC_VER
         return _byteswap_uint64(x);
     #endif
     
         return  (x >> 56) |
                ((x >> 40) & 0x000000000000FF00ULL) |
                ((x >> 24) & 0x0000000000FF0000ULL) |
                ((x >>  8) & 0x00000000FF000000ULL) |
                ((x <<  8) & 0x000000FF00000000ULL) |
                ((x << 24) & 0x0000FF0000000000ULL) |
                ((x << 40) & 0x00FF000000000000ULL) |
                 (x << 56);
       }
     
     
       /// return x % 5 for 0 <= x <= 9
       unsigned int mod5(unsigned int x)
       {
         if (x < 5)
           return x;
     
         return x - 5;
       }
     }
     
     
     /// process a full block
     void SHA3::processBlock(const void* data)
     {
     #if defined(__BYTE_ORDER) && (__BYTE_ORDER != 0) && (__BYTE_ORDER == __BIG_ENDIAN)
     #define LITTLEENDIAN(x) swap(x)
     #else
     #define LITTLEENDIAN(x) (x)
     #endif
     
       const uint64_t* data64 = (const uint64_t*) data;
       // mix data into state
       for (unsigned int i = 0; i < m_blockSize / 8; i++)
         m_hash[i] ^= LITTLEENDIAN(data64[i]);
     
       // re-compute state
       for (unsigned int round = 0; round < Rounds; round++)
       {
         // Theta
         uint64_t coefficients[5];
         for (unsigned int i = 0; i < 5; i++)
           coefficients[i] = m_hash[i] ^ m_hash[i + 5] ^ m_hash[i + 10] ^ m_hash[i + 15] ^ m_hash[i + 20];
     
         for (unsigned int i = 0; i < 5; i++)
         {
           uint64_t one = coefficients[mod5(i + 4)] ^ rotateLeft(coefficients[mod5(i + 1)], 1);
           m_hash[i     ] ^= one;
           m_hash[i +  5] ^= one;
           m_hash[i + 10] ^= one;
           m_hash[i + 15] ^= one;
           m_hash[i + 20] ^= one;
         }
     
         // temporary
         uint64_t one;
     
         // Rho Pi
         uint64_t last = m_hash[1];
         one = m_hash[10]; m_hash[10] = rotateLeft(last,  1); last = one;
         one = m_hash[ 7]; m_hash[ 7] = rotateLeft(last,  3); last = one;
         one = m_hash[11]; m_hash[11] = rotateLeft(last,  6); last = one;
         one = m_hash[17]; m_hash[17] = rotateLeft(last, 10); last = one;
         one = m_hash[18]; m_hash[18] = rotateLeft(last, 15); last = one;
         one = m_hash[ 3]; m_hash[ 3] = rotateLeft(last, 21); last = one;
         one = m_hash[ 5]; m_hash[ 5] = rotateLeft(last, 28); last = one;
         one = m_hash[16]; m_hash[16] = rotateLeft(last, 36); last = one;
         one = m_hash[ 8]; m_hash[ 8] = rotateLeft(last, 45); last = one;
         one = m_hash[21]; m_hash[21] = rotateLeft(last, 55); last = one;
         one = m_hash[24]; m_hash[24] = rotateLeft(last,  2); last = one;
         one = m_hash[ 4]; m_hash[ 4] = rotateLeft(last, 14); last = one;
         one = m_hash[15]; m_hash[15] = rotateLeft(last, 27); last = one;
         one = m_hash[23]; m_hash[23] = rotateLeft(last, 41); last = one;
         one = m_hash[19]; m_hash[19] = rotateLeft(last, 56); last = one;
         one = m_hash[13]; m_hash[13] = rotateLeft(last,  8); last = one;
         one = m_hash[12]; m_hash[12] = rotateLeft(last, 25); last = one;
         one = m_hash[ 2]; m_hash[ 2] = rotateLeft(last, 43); last = one;
         one = m_hash[20]; m_hash[20] = rotateLeft(last, 62); last = one;
         one = m_hash[14]; m_hash[14] = rotateLeft(last, 18); last = one;
         one = m_hash[22]; m_hash[22] = rotateLeft(last, 39); last = one;
         one = m_hash[ 9]; m_hash[ 9] = rotateLeft(last, 61); last = one;
         one = m_hash[ 6]; m_hash[ 6] = rotateLeft(last, 20); last = one;
                           m_hash[ 1] = rotateLeft(last, 44);
     
         // Chi
         for (unsigned int j = 0; j < StateSize; j += 5)
         {
           // temporaries
           uint64_t one = m_hash[j];
           uint64_t two = m_hash[j + 1];
     
           m_hash[j]     ^= m_hash[j + 2] & ~two;
           m_hash[j + 1] ^= m_hash[j + 3] & ~m_hash[j + 2];
           m_hash[j + 2] ^= m_hash[j + 4] & ~m_hash[j + 3];
           m_hash[j + 3] ^=      one      & ~m_hash[j + 4];
           m_hash[j + 4] ^=      two      & ~one;
         }
     
         // Iota
         m_hash[0] ^= XorMasks[round];
       }
     }
     
     
     /// add arbitrary number of bytes
     void SHA3::add(const void* data, size_t numBytes)
     {
       const uint8_t* current = (const uint8_t*) data;
     
       // copy data to buffer
       if (m_bufferSize > 0)
       {
         while (numBytes > 0 && m_bufferSize < m_blockSize)
         {
           m_buffer[m_bufferSize++] = *current++;
           numBytes--;
         }
       }
     
       // full buffer
       if (m_bufferSize == m_blockSize)
       {
         processBlock((void*)m_buffer);
         m_numBytes  += m_blockSize;
         m_bufferSize = 0;
       }
     
       // no more data ?
       if (numBytes == 0)
         return;
     
       // process full blocks
       while (numBytes >= m_blockSize)
       {
         processBlock(current);
         current    += m_blockSize;
         m_numBytes += m_blockSize;
         numBytes   -= m_blockSize;
       }
     
       // keep remaining bytes in buffer
       while (numBytes > 0)
       {
         m_buffer[m_bufferSize++] = *current++;
         numBytes--;
       }
     }
     
     
     /// process everything left in the internal buffer
     void SHA3::processBuffer()
     {
       // add padding
       size_t offset = m_bufferSize;
       // add a "1" byte
       m_buffer[offset++] = 0x06;
       // fill with zeros
       while (offset < m_blockSize)
         m_buffer[offset++] = 0;
     
       // and add a single set bit
       m_buffer[offset - 1] |= 0x80;
     
       processBlock(m_buffer);
     }
     
     
     /// return latest hash as 16 hex characters
     std::string SHA3::getHash()
     {
       // save hash state
       uint64_t oldHash[StateSize];
       for (unsigned int i = 0; i < StateSize; i++)
         oldHash[i] = m_hash[i];
     
       // process remaining bytes
       processBuffer();
     
       // convert hash to string
       static const char dec2hex[16 + 1] = "0123456789abcdef";
     
       // number of significant elements in hash (uint64_t)
       unsigned int hashLength = m_bits / 64;
     
       std::string result;
       result.reserve(m_bits / 4);
       for (unsigned int i = 0; i < hashLength; i++)
         for (unsigned int j = 0; j < 8; j++) // 64 bits => 8 bytes
         {
           // convert a byte to hex
           unsigned char oneByte = (unsigned char) (m_hash[i] >> (8 * j));
           result += dec2hex[oneByte >> 4];
           result += dec2hex[oneByte & 15];
         }
     
       // SHA3-224's last entry in m_hash provides only 32 bits instead of 64 bits
       unsigned int remainder = m_bits - hashLength * 64;
       unsigned int processed = 0;
       while (processed < remainder)
       {
         // convert a byte to hex
         unsigned char oneByte = (unsigned char) (m_hash[hashLength] >> processed);
         result += dec2hex[oneByte >> 4];
         result += dec2hex[oneByte & 15];
     
         processed += 8;
       }
     
       // restore state
       for (unsigned int i = 0; i < StateSize; i++)
         m_hash[i] = oldHash[i];
     
       return result;
     }
     
     
     /// compute SHA3 of a memory block
     std::string SHA3::operator()(const void* data, size_t numBytes)
     {
       reset();
       add(data, numBytes);
       return getHash();
     }
     
     
     /// compute SHA3 of a string, excluding final zero
     std::string SHA3::operator()(const std::string& text)
     {
       reset();
       add(text.c_str(), text.size());
       return getHash();
     }

Keccak and SHA3 Live Test

HMAC (keyed-hash message authentication code)

HMAC (see Wikipedia) was implemented as a simple template. Its header file explains its usage:

hide


     // //////////////////////////////////////////////////////////
     // hmac.h
     // Copyright (c) 2015 Stephan Brumme. All rights reserved.
     // see http://create.stephan-brumme.com/disclaimer.html
     //
     
     #pragma once
     
     // based on http://tools.ietf.org/html/rfc2104
     // see also http://en.wikipedia.org/wiki/Hash-based_message_authentication_code
     
     /** Usage:
         std::string msg = "The quick brown fox jumps over the lazy dog";
         std::string key = "key";
         std::string md5hmac  = hmac< MD5  >(msg, key);
         std::string sha1hmac = hmac< SHA1 >(msg, key);
         std::string sha2hmac = hmac<SHA256>(msg, key);
     
         Note:
         To keep my code simple, HMAC computation currently needs the whole message at once.
         This is in contrast to the hashes MD5, SHA1, etc. where an add() method is available
         for incremental computation.
         You can use any hash for HMAC as long as it provides:
         - constant HashMethod::BlockSize (typically 64)
         - constant HashMethod::HashBytes (length of hash in bytes, e.g. 20 for SHA1)
         - HashMethod::add(buffer, bufferSize)
         - HashMethod::getHash(unsigned char buffer[HashMethod::BlockSize])
       */
     
     #include <string>
     #include <cstring> // memcpy
     
     /// compute HMAC hash of data and key using MD5, SHA1 or SHA256
     template <typename HashMethod>
     std::string hmac(const void* data, size_t numDataBytes, const void* key, size_t numKeyBytes)
     {
       // initialize key with zeros
       unsigned char usedKey[HashMethod::BlockSize] = {0};
     
       // adjust length of key: must contain exactly blockSize bytes
       if (numKeyBytes <= HashMethod::BlockSize)
       {
         // copy key
         memcpy(usedKey, key, numKeyBytes);
       }
       else
       {
         // shorten key: usedKey = hashed(key)
         HashMethod keyHasher;
         keyHasher.add(key, numKeyBytes);
         keyHasher.getHash(usedKey);
       }
     
       // create initial XOR padding
       for (size_t i = 0; i < HashMethod::BlockSize; i++)
         usedKey[i] ^= 0x36;
     
       // inside = hash((usedKey ^ 0x36) + data)
       unsigned char inside[HashMethod::HashBytes];
       HashMethod insideHasher;
       insideHasher.add(usedKey, HashMethod::BlockSize);
       insideHasher.add(data,    numDataBytes);
       insideHasher.getHash(inside);
     
       // undo usedKey's previous 0x36 XORing and apply a XOR by 0x5C
       for (size_t i = 0; i < HashMethod::BlockSize; i++)
         usedKey[i] ^= 0x5C ^ 0x36;
     
       // hash((usedKey ^ 0x5C) + hash((usedKey ^ 0x36) + data))
       HashMethod finalHasher;
       finalHasher.add(usedKey, HashMethod::BlockSize);
       finalHasher.add(inside,  HashMethod::HashBytes);
     
       return finalHasher.getHash();
     }
     
     
     /// convenience function for std::string
     template <typename HashMethod>
     std::string hmac(const std::string& data, const std::string& key)
     {
       return hmac<HashMethod>(data.c_str(), data.size(), key.c_str(), key.size());
     }


June 30, 2021: Length-Limited Prefix Codes April 13, 2020: smalLZ4 - optimal LZ4 compression June 17, 2019: toojpeg - a JPEG encoder in a single C++ file ... and 30 more !	RSS	www.stephan-brumme.com bits.stephan-brumme.com photos.stephan-brumme.com minime.stephan-brumme.com
© 2011-2024 Stephan Brumme products and company names mentioned may be trademarks of their respective owners. see my disclaimer. dude, this is the end ... of this page.