A C++ port of the OpenBSD Arc4 random number generator

arc4.hpp

#ifndef ARC4_HPP_INCLUDED
#define ARC4_HPP_INCLUDED 1

/*
 * A C++ port of the OpenBSD Arc4 random number generator
 *
 * The MIT License (MIT)
 *
 * Copyright (C) 1996 David Mazieres <[email protected]> for the OpenBSD project
 * C++ Port Copyright (c) 2014-18 Melissa E. O'Neill
 *
 * 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.
 */

/*
 * Arc4 random number generator for OpenBSD.
 * Copyright 1996 David Mazieres <[email protected]>.
 *
 * Modification and redistribution in source and binary forms is
 * permitted provided that due credit is given to the author and the
 * OpenBSD project (for instance by leaving this copyright notice
 * intact).
 */

/*
 * This code is derived from section 17.1 of Applied Cryptography,
 * second edition, which describes a stream cipher allegedly
 * compatible with RSA Labs "RC4" cipher (the actual description of
 * which is a trade secret).  The same algorithm is used as a stream
 * cipher called "arcfour" in Tatu Ylonen's ssh package.
 *
 * RC4 is a registered trademark of RSA Laboratories.
 *
 * CODE HISTORY & NOTES:
 *
 * This version is based on arc4random.c included in Apple Libc 549.9.4
 * http://opensource.apple.com/source/Libc/Libc-594.9.4/gen/FreeBSD/arc4random.c
 * At the time of writing, this version of the source is the first one
 * found with a Google search for arc4random.c, even though it is not the
 * most recent iteration.  It was, however, a reasonable starting point for
 * creating a C++ class.
 *
 * Apple's code was a direct import of FreeBSD's 2004/03/24 version of
 * arc4random.c (1.10) (which is available as revision 127373 at
 * https://svnweb.freebsd.org/base/head/lib/libc/gen/arc4random.c), which
 * itself was based the 1997/04/27 version of arc4random.c (1.2) from OpenBSD
 * (http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/arc4random.c).
 * The FreeBSD version included several small changes made to the OpenBSD
 * source, most notably changes by:
 *      - Christian S.J. Peron <[email protected]> (style, reentrancy)
 *      - Colin Percival <[email protected]> (style)
 *      - Jeff Ito <[email protected]> (discard first 1024 bytes, 2004/01/20,
 *        discussed in detail below)
 * (Apple first introduced arc4random in Mac OS X 10.2, released 2002/09/23,
 * which imported FreeBSD's 2000/01/27, revision 1.4 which it kept until
 * OS X 10.5, released 2007/10/26 which is when the above changes, including
 * Ito's change, were first shipped by Apple.)
 *
 * Interesting changes made subseqently to the Apple/FreeBSD code and changes
 * made to other versions:
 *
 * - Amount of output discarded during initialization
 *
 *   On 2008/07/21, Andrey A. Chernov <[email protected]> reduced the amount
 *   of discarded output to 512 bytes, but then the next day increased it to 768
 *   bytes.  Three days later these changes were backed out, at the request of
 *   Robert Watson  <[email protected]>, restoring the constant to 1024
 *   bytes.
 *
 *   Meanwhile, in the OpenBSD project, Damien Miller <[email protected]> made
 *   a similar change to Jeff Ito's (in revision 1.10, 2003/11/26, thus
 *   predating Ito's change) but chose to only discard the first 256 bytes of
 *   output. OpenBSD kept using a discard of only 256 bytes until it replaced
 *   Arc4 on 2013/10/01 with ChaCha20 from Nick Mathewson's libottery (an
 *   implementation of Daniel J. Bernstein's Salsa20 stream cipher).  Thus
 *   for over nine years, OpenBSD used a key scheduling scheme that was
 *   considered "too weak" by the FreeBSD developers.
 *
 * - Periodic stirring
 *
 *   In a cryptograpically secure generator, it is wise to periodically
 *   destroy the state of the generator and replace it with an entirely fresh
 *   one.   On 2005/06/04, Ted Unangst <[email protected]> added periodic
 *   stirring, causing the generator to reseed itself after producing 40000
 *   outputs.  On 2006/10/04, Andrey A. Chernov <[email protected]> adopted
 *   this change.  On 2007/02/12, Otto Moerbeek <[email protected]> changed
 *   the constant to 1600000 without any comment about why (openbsd, r1.15)
 *   and on 2008/07/21 Andrey A. Chernov <[email protected]> adopted that
 *   change for FreeBSD.
 *
 * - Avoiding *very* short periods
 *
 *   The period of RC4 depends on its initialization.  Some initializations can
 *   cause *very* short periods.  The initial implementation did not correctly
 *   avoid weak initialization, meaning that more than 1 time in 75000, the
 *   period of the generator could be tiny, only 16320 integers
 *   (i.e., 65280 bytes of output).
 *
 *   Theo de Raadt fixed the issue on 1999/09/28 (revision 1.5) but his commit
 *   comment was
 *      "Set j = i after arc4random key schedule to be more like
 *      arc4 stream cipher; from conversations between various people"
 *   which did not give much clue as to the seriousness of the issue, possibly
 *   because he was not aware just how serious it was or because he thought
 *   it unwise to draw attention to the flaw.
 *
 *   The issue it went unnoticed by the FreeBSD developers and was not fixed
 *   until Andrey A. Chernov <[email protected]> did so on 2008/07/22, almost
 *   nine years later.
 *
 *   Apple did not update its FreeBSD sources until OS X Lion (10.7,
 *   Libc-763.11), which was released on 2011/07/20, almost twelve years
 *   after the flaw was found and fixed by Theo de Raadt.  Presumably the
 *   fix was also applied to iOS 5, which was released that year.
 *
 * This version of the code applies the simple fix for avoiding short periods,
 * and keeps the amount of discarded initial output at 1024 bytes.  It does
 * not provide periodic stirring.  In my opinion, if you want to destroy your
 * RNG state, you should either
 *      - do it manually, after performing a sensitive task, or,
 *      - do it periodically using a timer
 * Also, arbitrary reseeding breaks reproducable behavior, which is required
 * by C++ and by cryptographic uses.
 *
 * This version also changes the initialization setup to use a C++11 seed
 * sequence (or work-alike).  This allows the generator to provide
 * reproducible random numbers.
 *
 * The code is also generalized to allow the number of S-Boxes to be changed.
 * The code can only be used to generate sensible random numbers if the
 * number of boxes is a power of two (controlled by setting the BITS template
 * parameter).
 *
 * Note that setting BITS < 6 creates a generator that does *not* pass
 * TestU01's BigCrush test battery (although BITS == 5 is sufficient to pass
 * SmallCrush).
 *
 */

#include <cstddef>
#include <cstdlib>
#include <cassert>
#include <cinttypes>
#include <cstring>
#include <limits>
#include <climits>
#include <random>
#include <new>
#include <type_traits>
#include <utility>
#include <iostream>

namespace arc4_detail {

template <typename ResultType = uint32_t, unsigned int BITS = 8>
class arc4_engine {
    static constexpr unsigned int BOXES = 1U << BITS;

    typedef typename std::conditional<BITS <= CHAR_BIT*sizeof(uint8_t),
                                      uint8_t, uint16_t>::type
            box_t;

    box_t i_ = 0;
    box_t j_ = 0;
    box_t s_[BOXES];

public:
    typedef ResultType result_type;

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

    static constexpr size_t boxes() {
        return size_t(BOXES);
    }

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

    arc4_engine(result_type seed = result_type(0xd0beef41U))
        : arc4_engine(std::seed_seq{seed})
    {
        // Nothing else to do.
    }

    template<typename SeedSeq>
    arc4_engine(SeedSeq&& seedSeq, typename std::enable_if<
           !std::is_convertible<SeedSeq, result_type>::value
        && !std::is_convertible<SeedSeq, arc4_engine>::value,
        std::true_type>::type = {});

    template<typename... Args>
    void seed(Args&&... args)
    {
        new (this) arc4_engine(std::forward<Args>(args)...);
    }

    void addrandom(const box_t *dat, size_t datlen);

    box_t getval();

    result_type operator()()
    {
        result_type val = 0;
        constexpr unsigned int RESULT_BITS = sizeof(result_type) * CHAR_BIT;

        for (unsigned int shift = 0; shift < RESULT_BITS; shift += BITS)
            val |= result_type(getval()) << shift;

        return val;
    }

    void discard(size_t t);

    template <typename RT, size_t B>
    friend bool operator==(const arc4_engine<RT,B>&, const arc4_engine<RT,B>&);

    template <typename CharT, typename Traits, typename RT, size_t B>
    friend std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>&, const arc4_engine<RT,B>&);

    template <typename CharT, typename Traits, typename RT, size_t B>
    friend std::basic_istream<CharT,Traits>& operator>>(std::basic_istream<CharT,Traits>&, arc4_engine<RT,B>&);
};

template <typename ResultType, unsigned int BITS>
bool operator==(const arc4_engine<ResultType, BITS>& lhs,
                const arc4_engine<ResultType, BITS>& rhs)
{
    return (lhs.i_ == rhs.i_)
         && (lhs.j_ == rhs.j_)
         && !memcmp(lhs.s_, rhs.s_, sizeof(*lhs.i_) * lhs.BOXES);
}

template <typename ResultType, unsigned int BITS>
inline bool operator!=(const arc4_engine<ResultType, BITS>& lhs,
                       const arc4_engine<ResultType, BITS>& rhs)
{
    return !(lhs == rhs);
}

template <typename CharT, typename Traits, typename ResultType, 
	  unsigned int BITS>
std::basic_ostream<CharT,Traits>&
operator<<(std::basic_ostream<CharT,Traits>& out,
           const arc4_engine<ResultType, BITS>& rng)
{
    auto orig_flags = out.flags(std::ios_base::dec | std::ios_base::left);
    auto space = out.widen(' ');
    auto orig_fill = out.fill();

    out << uint32_t(rng.i_) << space << uint32_t(rng.j_);
    for (auto s : rng.s_)
        out << space << uint32_t(s);

    out.flags(orig_flags);
    out.fill(orig_fill);

    return out;
}

template <typename CharT, typename Traits, typename ResultType,
	  unsigned int BITS>
std::basic_istream<CharT,Traits>&
operator>>(std::basic_istream<CharT,Traits>& in,
           arc4_engine<ResultType, BITS>& rng)
{
    typename std::basic_istream<CharT,Traits>::sentry s(in);

    if (!s)
         return in;

    uint32_t temp;
    bool fail = false;

    in >> temp;
    fail = temp > rng.boxes();
    if (fail || !in.good())
        goto bail;
    rng.i_ = temp;


    in >> temp;
    fail = temp > rng.boxes();
    if (fail || !in.good())
        goto bail;
    rng.j_ = temp;

    for (auto& s : rng.s_) {
        in >> temp;
        fail = temp > rng.boxes();
        if (fail || !in)
            break;
        s = temp;
    }

bail:
    if (fail)
        in.setstate(std::ios::failbit);

    return in;
}


template <typename ResultType, unsigned int BITS>
void arc4_engine<ResultType, BITS>::addrandom(const box_t *dat, size_t datlen)
{
    box_t si;

    --i_;
    for (size_t n = 0; n < BOXES; ++n) {
        i_ = (i_ + 1) % BOXES;
        si = s_[i_];
        j_ = (j_ + si + dat[n % datlen]) % BOXES;
        s_[i_] = s_[j_];
        s_[j_] = si;
    }
    j_ = i_;

    /*
     * Throw away the first N bytes of output, as suggested in the
     * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
     * by Fluher, Mantin, and Shamir.  N=1024 is based on
     * suggestions in the paper "(Not So) Random Shuffles of RC4"
     * by Ilya Mironov.
     */
    for (size_t n = 0; n < 1024; ++n)
        getval();
}

template <typename ResultType, unsigned int BITS>
auto arc4_engine<ResultType, BITS>::getval() -> box_t
{
    box_t si, sj;

    i_ = (i_ + 1) % BOXES;
    si = s_[i_];
    j_ = (j_ + si) % BOXES;
    sj = s_[j_];
    s_[i_] = sj;
    s_[j_] = si;

    return s_[(si + sj) % BOXES];
}


template <typename ResultType, unsigned int BITS>
void arc4_engine<ResultType, BITS>::discard(size_t amount)
{
    constexpr unsigned int RESULT_BITS = sizeof(result_type) * CHAR_BIT;

    for (size_t i = 0; i < amount; ++i)
        for (unsigned int shift = 0; shift < RESULT_BITS; shift += BITS)
            getval();
}


template <typename ResultType, unsigned int BITS>
template<typename SeedSeq>
arc4_engine<ResultType, BITS>::arc4_engine(
    SeedSeq&& seedSeq, typename std::enable_if<
           !std::is_convertible<SeedSeq, result_type>::value
        && !std::is_convertible<SeedSeq, arc4_engine>::value,
        std::true_type>::type)
{
    for (size_t n = 0; n < BOXES; ++n)
        s_[n] = n;
    constexpr size_t MAX_POSSIBLE_BOXES = 1U << BITS;
    constexpr bool IS_EFFICIENT = MAX_POSSIBLE_BOXES == BOXES;
    constexpr size_t BOXES_PER_INT32 =
        IS_EFFICIENT ? (sizeof(uint32_t)*CHAR_BIT) / BITS
                     : 1;
    constexpr size_t SEED_BOXES = BOXES/2;
    constexpr size_t SCRIBBLE_SIZE =
        (SEED_BOXES + BOXES_PER_INT32-1) / BOXES_PER_INT32;
    uint32_t scribble[SCRIBBLE_SIZE];
    seedSeq.generate(scribble, scribble+SCRIBBLE_SIZE);
    box_t seeds[SEED_BOXES];
    for (size_t i = 0; i < SEED_BOXES; ++i) {
        seeds[i] =
            (scribble[i / BOXES_PER_INT32] >> (BITS * (i % BOXES_PER_INT32)))
          % BOXES;
    }
    addrandom(seeds, SEED_BOXES);
}

} // namespace arc4_detail

using arc4_rand32 = arc4_detail::arc4_engine<uint32_t>;
using arc4_rand64 = arc4_detail::arc4_engine<uint64_t>;
using arc4_rand   = arc4_rand32;

#endif