Skip to content

Instantly share code, notes, and snippets.

@Sam-Belliveau

Sam-Belliveau/BreakHash.hpp

Last active October 31, 2022 15:15
Show Gist options
  • Save Sam-Belliveau/7a98a1cc9a76d50f5991e37c70e5e0fe to your computer and use it in GitHub Desktop.
Save Sam-Belliveau/7a98a1cc9a76d50f5991e37c70e5e0fe to your computer and use it in GitHub Desktop.
Download ZIP
A theoretically secure hashing algorithm that was constructed as a proof of concept for a recursive sponge hash construction in order to produce arbitrarily slow password hashes with very large states.
Raw
BreakHash.hpp
/**
* MIT License
*
* Copyright (c) 2022, Samuel Robert Belliveau
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
#pragma once
#include <cstdint> // std::uint8_t, std::uint64_t, std::size_t
#include <array> // std::array - used for passing and storing sequences
// WARNING: THIS HASH IS NOT FOR LEGITIMATE USE IN ANY CYPTOGRAPHICALLY SECURE SYSTEM
// THIS WAS DESIGNED AS A THOUGHT EXPERIMENT FOR RECURSIVE HASH CONSTRUCTION
// THE NEXT SECION IS A HYPOTHETICAL ARGUMENT IN FAVOR OF THIS HASH FUNCTION
//
// A proof of concept cryptographically secure hashing algorithm
// with a runtime complexity of O(R * 4^E) and a memory complexity of O(2^E)
//
// This is done by building a recursive binary tree of 4096bit sponges
// that work on 2048bit blocks. The various sponges pass the block between
// eachother in a way that makes it impossible to not have them all constructed
// at the same time as the data makes it through each sponge at least twice.
// This should prevent people from making low memory versions of the hash.
// Because 50% of the state is never read by the attacker in each step,
// and 50% of the state is never written to by the attacker in each step,
// it is very difficult for length extension attacks, collision attacks,
// or preimage attacks to be constructed, just due to the huge size of the state.
//
// Because the runtime can be made abysmally slow, this is optimal for key
// generation or password hashing. Not only can the memory requirement be made
// large, but every single bit in the memory used has such a profound impact that
// a single gamma ray would completely change the result of the algorithm.
//
// The last intersting thing about BreakHash's construction is that, since this
// is a Sponge construction with an extremely large state, it can generate infinite
// length output. A 2048bit counter could theoretically be implemented, but the
// cycle length would likely be substantially longer due to the state size being
// huge. However this is not implemented due to the requirement of more than
// 256 * 2 ^ 64 bytes of random data from a hash is very unlikely to occur.
//
// This hash can also be Key'd, so that if you are using this as a password hasher,
// you can add a 1024bit nonce to the hash that will prevent rainbow tables from
// being used.
//
// Here is an example usage for hashing a string:
//
// BreakHash::BreakHash<4, 256> hash;
// hash.soak_string(bytes.begin(), bytes.end());
// BreakHash::Type::Block a = hash.squeeze();
// BreakHash::Type::Block b = hash.squeeze();
namespace BreakHash
{
// Types used throughout code
namespace Type
{
using u8 = std::uint8_t;
using u64 = std::uint64_t;
using State = std::array<u64, 64>;
using Key = std::array<u64, 16>;
using Block = std::array<u64, 32>;
}
// E = Expansions
// R = Rounds
template<std::size_t E, std::size_t R>
class BreakHashSponge
{
public: // Definitions
using SubHash = BreakHashSponge<E - 1, R>;
private: // Variables
SubHash hash_a_;
SubHash hash_b_;
public: // Constructors
inline constexpr BreakHashSponge(const Type::Key& key = {})
: hash_a_(key), hash_b_(key) {}
public: // Interfacing Functions
inline constexpr void operator()(Type::Block& block)
{
Type::Block m = block;
hash_a_(block);
hash_b_(block);
for (std::size_t i = 0; i < m.size(); ++i)
m[i] ^= block[i];
hash_a_(block);
hash_b_(block);
for (std::size_t i = 0; i < m.size(); ++i)
block[i] += m[i];
}
};
template<std::size_t R>
class BreakHashSponge<0, R>
{
public: // Static Assertions
static_assert(0 < R,
"Rounds Must Be Greater Than 0");
static_assert((R & 0b11) == 0,
"Rounds Must Be Divisible By 4");
private: // Variables
Type::State state_;
public: // Constructors
inline constexpr BreakHashSponge(const Type::Key& key = {})
{
// Key [1/2]
state_[000] = key[000]; state_[001] = key[001];
state_[002] = key[002]; state_[003] = key[003];
state_[004] = key[004]; state_[005] = key[005];
state_[006] = key[006]; state_[007] = key[007];
// Constant [1/2]
state_[010] = 0x4120706f70756c61; state_[011] = 0x72206174686c6574;
state_[012] = 0x6963207374796c65; state_[013] = 0x206f662073747265;
state_[014] = 0x65742064616e6365; state_[015] = 0x206f726967696e61;
state_[016] = 0x74696e672066726f; state_[017] = 0x6d20746865204166;
// Counter
state_[020] = 0; state_[021] = 0; state_[022] = 0; state_[023] = 0;
state_[024] = 0; state_[025] = 0; state_[026] = 0; state_[027] = 0;
state_[030] = 0; state_[031] = 0; state_[032] = 0; state_[033] = 0;
state_[034] = 0; state_[035] = 0; state_[036] = 0; state_[037] = 0;
state_[040] = 0; state_[041] = 0; state_[042] = 0; state_[043] = 0;
state_[044] = 0; state_[045] = 0; state_[046] = 0; state_[047] = 0;
state_[050] = 0; state_[051] = 0; state_[052] = 0; state_[053] = 0;
state_[054] = 0; state_[055] = 0; state_[056] = 0; state_[057] = 0;
// Constant [2/2]
state_[060] = 0x726963616e20416d; state_[061] = 0x65726963616e2061;
state_[062] = 0x6e64205075657274; state_[063] = 0x6f20526963616e20;
state_[064] = 0x636f6d6d756e6974; state_[065] = 0x69657320696e2074;
state_[066] = 0x686520556e697465; state_[067] = 0x6420537461746573;
// Key [2/2]
state_[070] = key[010]; state_[071] = key[011];
state_[072] = key[012]; state_[073] = key[013];
state_[074] = key[014]; state_[075] = key[015];
state_[076] = key[016]; state_[077] = key[017];
}
public: // Round Helpers
template<std::size_t B>
static inline constexpr Type::u64 rotr(const Type::u64 x)
{ return (x >> B) | (x << (64 - B)); }
// This function mixes 8 64bit integers with a similar construction to
// the mixing function in ChaCha20. This function has been rigorously tested
// and optimized. On average a single bit flip will flip ~83.2/512 bits in
// the output. Compared to ChaCha20, which flips ~12.5/128 bits on average.
static inline constexpr void mix(
Type::u64& n0, Type::u64& n1, Type::u64& n2, Type::u64& n3,
Type::u64& n4, Type::u64& n5, Type::u64& n6, Type::u64& n7)
{
n7 += n0; n6 = rotr<32>(n6 ^ n7);
n5 += n6; n4 = rotr<27>(n4 ^ n5);
n3 += n4; n2 = rotr<24>(n2 ^ n3);
n1 += n2; n0 = rotr<19>(n0 ^ n1);
n5 += n0; n2 = rotr<16>(n2 ^ n5);
n7 += n2; n4 = rotr<11>(n4 ^ n7);
n1 += n4; n6 = rotr<8>(n6 ^ n1);
n3 += n6; n0 = rotr<3>(n0 ^ n3);
}
public: // Interfacing Functions
constexpr void operator()(Type::Block& b) noexcept
{
// This is effectively an alias to make the next code readable
Type::State& m = state_;
// Set the center of the state to be equal to the current block of data
m[020] = b[000]; m[021] = b[001]; m[022] = b[002]; m[023] = b[003];
m[024] = b[004]; m[025] = b[005]; m[026] = b[006]; m[027] = b[007];
m[030] = b[010]; m[031] = b[011]; m[032] = b[012]; m[033] = b[013];
m[034] = b[014]; m[035] = b[015]; m[036] = b[016]; m[037] = b[017];
m[040] = b[020]; m[041] = b[021]; m[042] = b[022]; m[043] = b[023];
m[044] = b[024]; m[045] = b[025]; m[046] = b[026]; m[047] = b[027];
m[050] = b[030]; m[051] = b[031]; m[052] = b[032]; m[053] = b[033];
m[054] = b[034]; m[055] = b[035]; m[056] = b[036]; m[057] = b[037];
// Mix the state forwards for half of the rounds
for (std::size_t r = 0; r < R / 2; r += 2)
{
// 1st half round [columns]
mix(m[000], m[010], m[020], m[030], m[040], m[050], m[060], m[070]);
mix(m[001], m[011], m[021], m[031], m[041], m[051], m[061], m[071]);
mix(m[002], m[012], m[022], m[032], m[042], m[052], m[062], m[072]);
mix(m[003], m[013], m[023], m[033], m[043], m[053], m[063], m[073]);
mix(m[004], m[014], m[024], m[034], m[044], m[054], m[064], m[074]);
mix(m[005], m[015], m[025], m[035], m[045], m[055], m[065], m[075]);
mix(m[006], m[016], m[026], m[036], m[046], m[056], m[066], m[076]);
mix(m[007], m[017], m[027], m[037], m[047], m[057], m[067], m[077]);
// 2nd half round [diagonals]
mix(m[000], m[011], m[022], m[033], m[044], m[055], m[066], m[077]);
mix(m[001], m[012], m[023], m[034], m[045], m[056], m[067], m[070]);
mix(m[002], m[013], m[024], m[035], m[046], m[057], m[060], m[071]);
mix(m[003], m[014], m[025], m[036], m[047], m[050], m[061], m[072]);
mix(m[004], m[015], m[026], m[037], m[040], m[051], m[062], m[073]);
mix(m[005], m[016], m[027], m[030], m[041], m[052], m[063], m[074]);
mix(m[006], m[017], m[020], m[031], m[042], m[053], m[064], m[075]);
mix(m[007], m[010], m[021], m[032], m[043], m[054], m[065], m[076]);
}
// Add the original block of data to the hidden part of the state after mixing
m[000] += b[000]; m[001] += b[001]; m[002] += b[002]; m[003] += b[003];
m[004] += b[004]; m[005] += b[005]; m[006] += b[006]; m[007] += b[007];
m[010] += b[010]; m[011] += b[011]; m[012] += b[012]; m[013] += b[013];
m[014] += b[014]; m[015] += b[015]; m[016] += b[016]; m[017] += b[017];
m[060] += b[020]; m[061] += b[021]; m[062] += b[022]; m[063] += b[023];
m[064] += b[024]; m[065] += b[025]; m[066] += b[026]; m[067] += b[027];
m[070] += b[030]; m[071] += b[031]; m[072] += b[032]; m[073] += b[033];
m[074] += b[034]; m[075] += b[035]; m[076] += b[036]; m[077] += b[037];
// Xor the state with the block of data to complicate the unmixing process
b[000] ^= m[020]; b[001] ^= m[021]; b[002] ^= m[022]; b[003] ^= m[023];
b[004] ^= m[024]; b[005] ^= m[025]; b[006] ^= m[026]; b[007] ^= m[027];
b[010] ^= m[030]; b[011] ^= m[031]; b[012] ^= m[032]; b[013] ^= m[033];
b[014] ^= m[034]; b[015] ^= m[035]; b[016] ^= m[036]; b[017] ^= m[037];
b[020] ^= m[040]; b[021] ^= m[041]; b[022] ^= m[042]; b[023] ^= m[043];
b[024] ^= m[044]; b[025] ^= m[045]; b[026] ^= m[046]; b[027] ^= m[047];
b[030] ^= m[050]; b[031] ^= m[051]; b[032] ^= m[052]; b[033] ^= m[053];
b[034] ^= m[054]; b[035] ^= m[055]; b[036] ^= m[056]; b[037] ^= m[057];
// For the next half of the rounds, mix the state backwards.
// This makes sure that any bias's in the mixing function are canceled out.
for (std::size_t r = 0; r < R / 2; r += 2)
{
// 1st half round [columns reversed]
mix(m[070], m[060], m[050], m[040], m[030], m[020], m[010], m[000]);
mix(m[071], m[061], m[051], m[041], m[031], m[021], m[011], m[001]);
mix(m[072], m[062], m[052], m[042], m[032], m[022], m[012], m[002]);
mix(m[073], m[063], m[053], m[043], m[033], m[023], m[013], m[003]);
mix(m[074], m[064], m[054], m[044], m[034], m[024], m[014], m[004]);
mix(m[075], m[065], m[055], m[045], m[035], m[025], m[015], m[005]);
mix(m[076], m[066], m[056], m[046], m[036], m[026], m[016], m[006]);
mix(m[077], m[067], m[057], m[047], m[037], m[027], m[017], m[007]);
// 2nd half round [diagonals reversed]
mix(m[077], m[066], m[055], m[044], m[033], m[022], m[011], m[000]);
mix(m[070], m[067], m[056], m[045], m[034], m[023], m[012], m[001]);
mix(m[071], m[060], m[057], m[046], m[035], m[024], m[013], m[002]);
mix(m[072], m[061], m[050], m[047], m[036], m[025], m[014], m[003]);
mix(m[073], m[062], m[051], m[040], m[037], m[026], m[015], m[004]);
mix(m[074], m[063], m[052], m[041], m[030], m[027], m[016], m[005]);
mix(m[075], m[064], m[053], m[042], m[031], m[020], m[017], m[006]);
mix(m[076], m[065], m[054], m[043], m[032], m[021], m[010], m[007]);
}
// Add the mixed state to the original block of data to prevent unmixing
b[000] += m[020]; b[001] += m[021]; b[002] += m[022]; b[003] += m[023];
b[004] += m[024]; b[005] += m[025]; b[006] += m[026]; b[007] += m[027];
b[010] += m[030]; b[011] += m[031]; b[012] += m[032]; b[013] += m[033];
b[014] += m[034]; b[015] += m[035]; b[016] += m[036]; b[017] += m[037];
b[020] += m[040]; b[021] += m[041]; b[022] += m[042]; b[023] += m[043];
b[024] += m[044]; b[025] += m[045]; b[026] += m[046]; b[027] += m[047];
b[030] += m[050]; b[031] += m[051]; b[032] += m[052]; b[033] += m[053];
b[034] += m[054]; b[035] += m[055]; b[036] += m[056]; b[037] += m[057];
}
};
template<std::size_t E, std::size_t R>
class BreakHash
{
private:
std::size_t word_;
Type::Block block_;
BreakHashSponge<E, R> sponge_;
std::size_t bytes_;
std::size_t blocks_;
public:
inline constexpr BreakHash(const Type::Key& key = {})
: word_(0), block_(), sponge_(key), bytes_(0), blocks_(0)
{
}
public: // Interfacing Functions
inline constexpr BreakHash& soak(const Type::u64 word)
{
bytes_ += sizeof(Type::u64);
block_[word_++] = word;
if (word_ == block_.size())
{
sponge_(block_);
word_ = 0;
}
return *this;
}
inline constexpr BreakHash& soak_bytes(
const Type::u8 a, const Type::u8 b = 0,
const Type::u8 c = 0, const Type::u8 d = 0,
const Type::u8 e = 0, const Type::u8 f = 0,
const Type::u8 g = 0, const Type::u8 h = 0)
{
return soak(
(Type::u64(a) << 0) |
(Type::u64(b) << 8) |
(Type::u64(c) << 16) |
(Type::u64(d) << 24) |
(Type::u64(e) << 32) |
(Type::u64(f) << 40) |
(Type::u64(g) << 48) |
(Type::u64(h) << 56)
);
}
template<typename Iter>
inline constexpr BreakHash& soak_string(Iter begin, const Iter end)
{
while (8 <= end - begin)
{
soak_bytes(
begin[0], begin[1], begin[2], begin[3],
begin[4], begin[5], begin[6], begin[7]
);
begin += 8;
}
switch (end - begin) {
case 7:
soak_bytes(begin[0], begin[1], begin[2], begin[3], begin[4], begin[5], begin[6], 0x80);
bytes_ -= 1; break;
case 6:
soak_bytes(begin[0], begin[1], begin[2], begin[3], begin[4], begin[5], 0x80);
bytes_ -= 2; break;
case 5:
soak_bytes(begin[0], begin[1], begin[2], begin[3], begin[4], 0x80);
bytes_ -= 3; break;
case 4:
soak_bytes(begin[0], begin[1], begin[2], begin[3], 0x80);
bytes_ -= 4; break;
case 3:
soak_bytes(begin[0], begin[1], begin[2], 0x80);
bytes_ -= 5; break;
case 2:
soak_bytes(begin[0], begin[1], 0x80);
bytes_ -= 6; break;
case 1:
soak_bytes(begin[0], 0x80);
bytes_ -= 7; break;
default:
soak_bytes(0x80);
bytes_ -= 8; break;
}
return *this;
}
inline constexpr Type::Block squeeze()
{
if (word_ != 0)
{
block_[word_++] = 0x8000000000000000;
while (word_ < block_.size())
block_[word_++] = 0;
sponge_(block_);
word_ = 0;
}
block_[0] = bytes_;
block_[block_.size() - 1] = ++blocks_;
for (std::size_t i = 1; i < block_.size() - 1; ++i)
block_[i] = 0;
sponge_(block_);
return block_;
}
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment