Last active
October 31, 2022 15:15
-
-
Save Sam-Belliveau/7a98a1cc9a76d50f5991e37c70e5e0fe to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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