BreakDance.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::uint64_t, std::size_t
#include <array>     // std::array - used for passing and storing sequences
#include <limits>    // std::numeric_limits - min/max
#include <chrono>    // std::chrono::high_resolution_clock

// BreakDance is a proof of concept Stream Cipher with an extremely
// similar construction to ChaCha20, with a few key differences.
//
// The most glaring difference is that BreakDance is a 64-bit cipher,
// using an 8 by 8 matrix of 64 bit integers to do its mixing compared
// to the 4 by 4 matrix of 32 bit integers that ChaCha20 uses. This
// allows BreakDance to have a much larger state space, 8 times larger
// to be exact.
//
// This required the mixing (known as the quarter round in ChaCha20)
// to be modified to not only handle 64 bit integers, but also to handle
// 8 of them. A lot of testing was done in order to find a mixing function
// that quickly distributes bits while also remaining fast. The function
// takes advantage of rotating integers by multiples of 8 in-order to take
// advantage of some byte level optimizations. The final iteration of this
// function only uses 2 times the number operations as ChaCha's however is
// able to distribute bits 7-8 times faster.
//
// The round construction follows ChaCha20's lead with vertical rounds
// followed by diagonal rounds. The number of rounds is also the same
// due to the mixing function being able to handle the increased number
// of bits. The mixed state is also added to the result at 2 points instead
// of just one like in ChaCha20's construction. This should further
// complicate the process of unmixing the state. The rounds do require
// twice the number of calls to the mixing function due to the matrix
// being 8 by 8 instead of 4 by 4. This leads to the mixing function
// taking approximately 4 times as long as ChaCha20's, on 64 bit hardware.
// However it's result is also 8 times longer than ChaCha20's.
//
// The most important difference however is the ability to use MUCH larger
// key's, nonce's, and counters. The construction of BreakDance contains a
// 1024bit constant, 2048bit key, 512bit nonce, and 512bit counter. The key
// itself is 4 times the size of ChaCha20's entire state.
//
// While I do not have enough cryptographic experience to write a formal
// cryptographic analysis of this cipher, I do believe that it is secure
// and that it is a good proof of concept for a 64 bit stream cipher.
// It works really really well as a cryptographically secure 64 bit PRNG,
// However speed is something I am not as sure about.
//
// - Sam Belliveau (sam.belliveau@gmail.com)
namespace BreakDance
{
    // Types used throughout code
    namespace Type
    {
        // Base Types
        using u64 = std::uint64_t;

        // State Type
        using State = std::array<u64, 64>;

        // Input To State Types
        using Constant = std::array<u64, 16>;
        using Key = std::array<u64, 32>;
        using Nonce = std::array<u64, 8>;
        using Counter = std::array<u64, 8>;

        // Output Types
        using Result = std::array<u64, 32>;
    }

    // BreakDance Stream with an 8x8 64 bit construction with the layout
    //
    // The layout of the internal state is as follows:
    // Each cell is a 64 bit integer, and each cell is filled with either
    //  - Key
    //  - Constant
    //  - Nonce
    //  - Counter
    //
    //    |0x0|0x1|0x2|0x3|0x4|0x5|0x6|0x7|
    // ---+---+---+---+---+---+---+---+---+
    // 00x|Key|Key|Key|Key|Key|Key|Key|Key|
    // ---+---+---+---+---+---+---+---+---+
    // 01x|Key|Key|Key|Key|Key|Key|Key|Key|
    // ---+---+---+---+---+---+---+---+---+
    // 02x|Con|Con|Con|Con|Con|Con|Con|Con|
    // ---+---+---+---+---+---+---+---+---+
    // 03x|Non|Non|Non|Non|Non|Non|Non|Non|
    // ---+---+---+---+---+---+---+---+---+
    // 04x|Ctr|Ctr|Ctr|Ctr|Ctr|Ctr|Ctr|Ctr|
    // ---+---+---+---+---+---+---+---+---+
    // 05x|Con|Con|Con|Con|Con|Con|Con|Con|
    // ---+---+---+---+---+---+---+---+---+
    // 06x|Key|Key|Key|Key|Key|Key|Key|Key|
    // ---+---+---+---+---+---+---+---+---+
    // 07x|Key|Key|Key|Key|Key|Key|Key|Key|
    // ---+---+---+---+---+---+---+---+---+
    //
    // Only the non key cells are ever returned to the user, preventing
    // an attacker from unmixing the result in order to get the key.
    template<std::size_t Rounds = 20>
    class BreakDance
    {
    public: // Static Assertions
        static_assert(0 < Rounds,
                    "Rounds Must Be Greater Than 0");

        static_assert((Rounds & 0b11) == 0,
                    "Rounds Must Be Divisible By 4");

    private: // Variables
        Type::State state_;

    public: // Constructors
        // Initialize BreakDance with a key and nonce, and a counter of 0.
        // The key should be private and generated in a cryptographically secure manner.
        // The nonce should not be reused unless you require repeatable results
        inline constexpr BreakDance(
            const Type::Key& key,
            const Type::Nonce& nonce)
        {
            // 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];
            state_[010] = key[010]; state_[011] = key[011];
            state_[012] = key[012]; state_[013] = key[013];
            state_[014] = key[014]; state_[015] = key[015];
            state_[016] = key[016]; state_[017] = key[017];

            // Constant [1/2]
            state_[020] = 0x4120706f70756c61; state_[021] = 0x72206174686c6574;
            state_[022] = 0x6963207374796c65; state_[023] = 0x206f662073747265;
            state_[024] = 0x65742064616e6365; state_[025] = 0x206f726967696e61;
            state_[026] = 0x74696e672066726f; state_[027] = 0x6d20746865204166;

            // Nonce
            state_[030] = nonce[000]; state_[031] = nonce[001];
            state_[032] = nonce[002]; state_[033] = nonce[003];
            state_[034] = nonce[004]; state_[035] = nonce[005];
            state_[036] = nonce[006]; state_[037] = nonce[007];

            // Counter
            state_[040] = 0; state_[041] = 0;
            state_[042] = 0; state_[043] = 0;
            state_[044] = 0; state_[045] = 0;
            state_[046] = 0; state_[047] = 0;

            // Constant [2/2]
            state_[050] = 0x726963616e20416d; state_[051] = 0x65726963616e2061;
            state_[052] = 0x6e64205075657274; state_[053] = 0x6f20526963616e20;
            state_[054] = 0x636f6d6d756e6974; state_[055] = 0x69657320696e2074;
            state_[056] = 0x686520556e697465; state_[057] = 0x6420537461746573;

            // Key [2/2]
            state_[060] = key[020]; state_[061] = key[021];
            state_[062] = key[022]; state_[063] = key[023];
            state_[064] = key[024]; state_[065] = key[025];
            state_[066] = key[026]; state_[067] = key[027];
            state_[070] = key[030]; state_[071] = key[031];
            state_[072] = key[032]; state_[073] = key[033];
            state_[074] = key[034]; state_[075] = key[035];
            state_[076] = key[036]; state_[077] = key[037];
        }

        // Initialize BreakDance with a single 64 bit integer.
        // This is useful for testing / non-cryptographic purposes.
    inline constexpr BreakDance(const Type::u64 seed = 0)
        : BreakDance({seed, seed, seed, seed, seed, seed, seed, seed,
                      seed, seed, seed, seed, seed, seed, seed, seed,
                      seed, seed, seed, seed, seed, seed, seed, seed,
                      seed, seed, seed, seed, seed, seed, seed, seed},
                     {seed, seed, seed, seed, seed, seed, seed, seed}) {}

    public: // Copy Constructors
        inline constexpr BreakDance(const BreakDance& other) noexcept = default;
        inline constexpr BreakDance& operator=(const BreakDance& other) = default;

    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
        // Reset the counter to zero
        constexpr void reset() noexcept
        {
            state_[040] = 0; state_[041] = 0;
            state_[042] = 0; state_[043] = 0;
            state_[044] = 0; state_[045] = 0;
            state_[046] = 0; state_[047] = 0;
        }

        // Skip ahead by a number of blocks.
        // The size of the counter is 512 bits, so this function will
        // cary over to the next 64 bit integer if the counter overflows.
        constexpr void count(const Type::u64 d = 1) noexcept
        {
            if (d <= (state_[040] += d)) return;
            if (1 <= (state_[041] += 1)) return;
            if (1 <= (state_[042] += 1)) return;
            if (1 <= (state_[043] += 1)) return;
            if (1 <= (state_[044] += 1)) return;
            if (1 <= (state_[045] += 1)) return;
            if (1 <= (state_[046] += 1)) return;
            if (1 <= (state_[047] += 1)) return;
        }

        // Generate a block of random data and store it in an array passed into the function.
        // The random data will be from the first and last 16 64 bit integers of the state.
        // These were choosen because the key is not stored there, in the event that the rounds
        // could be reversed, they would only be able to retrieve already known data.
        constexpr void operator()(Type::Result& r) noexcept
        {
            Type::State m = state_;

            // Initially set the result to the non key data in the state.
            // This will make it really difficult to unmix the data because
            // they will have to have known the original state to begin unmixing.
            r[000] = m[020]; r[001] = m[021]; r[002] = m[022]; r[003] = m[023];
            r[004] = m[024]; r[005] = m[025]; r[006] = m[026]; r[007] = m[027];
            r[010] = m[030]; r[011] = m[031]; r[012] = m[032]; r[013] = m[033];
            r[014] = m[034]; r[015] = m[035]; r[016] = m[036]; r[017] = m[037];
            r[020] = m[040]; r[021] = m[041]; r[022] = m[042]; r[023] = m[043];
            r[024] = m[044]; r[025] = m[045]; r[026] = m[046]; r[027] = m[047];
            r[030] = m[050]; r[031] = m[051]; r[032] = m[052]; r[033] = m[053];
            r[034] = m[054]; r[035] = m[055]; r[036] = m[056]; r[037] = m[057];

            for (std::size_t r = 0; r < Rounds; 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 final mixing state to the result. Because the result is
            // already filled with random data, it will be impossible to determine
            // the mixing state after its added to the result.
            r[000] += m[020]; r[001] += m[021]; r[002] += m[022]; r[003] += m[023];
            r[004] += m[024]; r[005] += m[025]; r[006] += m[026]; r[007] += m[027];
            r[010] += m[030]; r[011] += m[031]; r[012] += m[032]; r[013] += m[033];
            r[014] += m[034]; r[015] += m[035]; r[016] += m[036]; r[017] += m[037];
            r[020] += m[040]; r[021] += m[041]; r[022] += m[042]; r[023] += m[043];
            r[024] += m[044]; r[025] += m[045]; r[026] += m[046]; r[027] += m[047];
            r[030] += m[050]; r[031] += m[051]; r[032] += m[052]; r[033] += m[053];
            r[034] += m[054]; r[035] += m[055]; r[036] += m[056]; r[037] += m[057];

            // Increase the counter to get new data on the next call
            count();
        }
    };

    // This is an STL compatible prng that uses the BreakDance stream algorithm.
    // Every 32 calls, it will generate a new block and return the values int by int.
    // It can be initialized in the same manner as the BreakDance class.
    template<std::size_t Rounds = 20>
    class BreakDancePRNG
    {
    private: // Variables
        BreakDance<Rounds> stream_;
        Type::Result result_;
        std::size_t counter_;

    public: // Constructors
        // Initialize BreakDance with a key and nonce, and a counter of 0.
        // The key should be private and generated in a cryptographically secure manner.
        // The nonce should not be reused unless you require repeatable results
        inline constexpr BreakDancePRNG(
            const Type::Key& key,
            const Type::Nonce& nonce)
                : stream_{key, nonce}, result_{}, counter_{result_.size()} {}

        // Initialize BreakDance with a single 64 bit integer.
        // This is useful for testing / non-cryptographic purposes.
        inline constexpr BreakDancePRNG(const Type::u64 seed = 0)
                : stream_{seed}, result_{}, counter_{result_.size()} {}

    public: // Copy Constructors
        inline constexpr BreakDancePRNG(const BreakDancePRNG& other) noexcept = default;
        inline constexpr BreakDancePRNG& operator=(const BreakDancePRNG& other) = default;

    public: // Standard Random Interface (Information)
        using result_type = Type::u64;

        static constexpr result_type min(void)
        { return std::numeric_limits<result_type>::min(); }

        static constexpr result_type max(void)
        { return std::numeric_limits<result_type>::max(); }

    public: // Standard Random Interface (Generation)
        // Reset the counter to zero and generate a new block.
        inline constexpr void reset(void) noexcept
        {
            stream_.reset();
            counter_ = result_.size();
        }

        // Get the next random number in the sequence.
        inline constexpr result_type get(void) noexcept
        {
            if (result_.size() <= counter_)
            {
                stream_(result_);
                counter_ = 0;
            }

            return result_[counter_++];
        }

        // Get the next random number in the sequence.
        inline constexpr result_type operator()(void) noexcept
        { return get(); }

        // Skip over the next n random numbers in the sequence. This can
        // be done in O(1) time because BreakDance uses a counting construction.
        inline constexpr void discard(std::size_t delta = 1) noexcept
        {
            counter_ += delta;

            std::size_t blocks = counter_ / result_.size();

            if (blocks > 0)
            {
                counter_ -= blocks * result_.size();
                stream_.count(blocks - 1);
                stream_(result_);
            }
        }
    };

    using BreakDance20 = BreakDance<20>;
    using BreakDance8 = BreakDance<8>;

    using BreakDancePRNG20 = BreakDancePRNG<20>;
    using BreakDancePRNG8 = BreakDancePRNG<8>;
}