2
\$\begingroup\$

I finished an output stream-based pseudorandom number generator, that works based on the current time and output data.

Here is the header's code (entrostream.hpp):

#ifndef ENTROSTREAM_HPP
#define ENTROSTREAM_HPP

#include <iostream>
#include <cstdlib>
#include <climits>
#include <sys/time.h>
#include <queue>
#include <sstream>

template <typename D> D rot_l(D x,unsigned r) { return ((x << r) | (x >> (CHAR_BIT*sizeof(D)-r))); }
template <typename D> D rot_r(D x,unsigned r) { return ((x >> r) | (x << (CHAR_BIT*sizeof(D)-r))); }

class entrostream : public std::ostream
{
    private:
        unsigned transform(unsigned x) // A "hashing/pseudorandom" function
        {
            unsigned yi[8] = {
                0xAD3012F1,0x56E7BA0E,0x2CD091FF,0x1FF5D329,
                0x435A0FF2,0x912ACD1A,0xB0AFE143,0x33FF0A10
            };
            unsigned y[8];
            unsigned yf = 0xC0FDE3A0;

            for (int i=0;i<8;i++)
            {
                unsigned t1 = (rot_l(x/(i+1),8-i) >> 2*i) & 0xFF;
                unsigned t2 = (rot_r(x/(i+1),8-i) >> 2*i) & 0xFF;
                y[i] = ((t1 << 16) | t2)^yi[i];
            }

            for (int i=0;i<8;i++)
            {
                for (int j=0;j<8;j++)
                {
                    y[j] = rot_r(y[i],yi[j]&0x1F)^y[j]^x;
                }
                yi[i] = rot_l(yi[i],4*i)^y[i];
            }

            for (int i=0;i<8;i++)
            {
                unsigned t = 0x1043F03A;
                for (int j=0;j<8;j++)
                {
                    t ^= rot_l(y[i]^yi[j],(i+4*j)%32);
                }
                yf ^= rot_r(t,4*i);
            }
            return yf;
        }
        unsigned tv_hash(struct timeval x) { return (unsigned(x.tv_sec) << 16) | unsigned(x.tv_usec); }
        unsigned str_to_u(char in,int idx) { return (unsigned(in) << 4*idx); }
        std::queue<unsigned> buffer;
        std::ostringstream data;
    public:
        entrostream(int _argc,char **_argv) // Generate randomness from arguments
        {
            struct timeval ts;
            std::string tmp[_argc];
            for (int i=0;i<_argc;i++) { tmp[i] = _argv[i]; }
            for (int i=0;i<_argc;i++)
            {
                for (int j=0;j<tmp[i].length()/4;j+=4)
                {
                    gettimeofday(&ts,NULL);
                    unsigned th = tv_hash(ts);
                    unsigned uis = str_to_u(tmp[i][j],i%4) |
                        str_to_u(tmp[i][j+1],(j+1)%4) |
                        str_to_u(tmp[i][j+2],(j+2)%4) |
                        str_to_u(tmp[i][j+3],(j+3)%4);
                    unsigned ui = transform(uis)^transform(th);
                    buffer.push(ui);
                }
            }
        }
        entrostream()
        {
            struct timeval ts;
            gettimeofday(&ts,NULL);
            unsigned th = transform(tv_hash(ts));
            buffer.push(th);
        }
        template <typename T> entrostream& operator<<(const T& val) // Generate more randomness from output stuff
        {
            struct timeval ts;
            std::cout << val;
            data << val;
            std::string tmp = data.str();
            for (int i=0;i<tmp.length()/4;i+=4)
            {
                gettimeofday(&ts,NULL);
                unsigned th = tv_hash(ts);
                unsigned uis = str_to_u(tmp[i],i%4) |
                    str_to_u(tmp[i+1],(i+1)%4) |
                    str_to_u(tmp[i+2],(i+2)%4) |
                    str_to_u(tmp[i+3],(i+3)%4);
                unsigned ui = transform(uis)^transform(th);
                buffer.push(ui);
            }
            return *this;
        }
        unsigned operator()() // Get a number and generate another one
        {
            unsigned o;
            struct timeval ts;
            gettimeofday(&ts,NULL);
            buffer.push(transform(tv_hash(ts)));
            if (!buffer.empty())
            {
                o = buffer.front();
                buffer.pop();
            }
            else
                o = 0;
            return o;
        }
};

#endif

Here is an example of its usage:

#include <iostream>
#include <cstdlib>
#include "entrostream.hpp"

using namespace std;

int main(int argc,char **argv)
{
    entrostream eout(argc,argv);
    eout << "Hello.\n";
    unsigned x = eout();
    eout << "entrostream output 1: " << x << "\n";
    x = eout();
    eout << "entrostream output 2: " << x << "\n";
    x = eout();
    eout << "entrostream output 3: " << x << "\n";
    x = eout();
    eout << "entrostream output 4: " << x << "\n";
    x = eout();
    cout << "entrostream output 5: " << x << "\n";
}

As always, suggestions, improvements, etc. are welcome.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Can you specify your entropy quality requirements/goal? Because doing review for encryption-grade RNG is something completely different from "just for fun/game" RNG - where it would suffice to review the look of the code and make sure there's no obvious mistake. For encryption-grade RNG it would have to be proven there's no simple attack on first and subsequent RNG calls, etc... (I'm not qualified enough to judge quality of such thing, but by a rule of thumb: purely timestamp based RNG is almost never encryption-grade suitable). If for fun/game, you can maybe state how it compares to Mersenne? \$\endgroup\$
    – Ped7g
    Jul 7, 2016 at 10:27
  • \$\begingroup\$ @Ped7g: For now, it's just for fun, although I need to improve it. \$\endgroup\$ Jul 7, 2016 at 18:54

1 Answer 1

1
\$\begingroup\$

I had only some limited quick look, just cherry-picking some things to comment on:

Entropy level: I'm not expert on this topic, but I think using time stamp as additional entropy source every time you produce a number is not a very good idea. But I'm even afraid you use it as only source of entropy in some cases, which is definitely wrong. I was unable to quickly show what's wrong about it, as you have weird way of buffer updating, masking the problem out in your example. But after you change this I'm afraid it will become obvious this needs rather some "seeding", and building up upon seed data.

About buffer: You do great deal of pushing all around into it, yet only operator() pops from it, and only once. So after running this for a while (using it as output stream, without calling RNG) the buffer will grow a lot, eventually running out of memory.

If this one is supposed to be a buffer of pre-generated random numbers, then the operator() should generate new buffer value only when buffer is empty, and then it should pop value from buffer and return it.

But I would do something different, I would change buffer into single unsigned number, used as seed. At any point of your current source, where you end with buffer.push, you would instead use old value of buffer as input for the transformation (in some way), storing result back to buffer. Then operator() will do yet another transform over it, and return the value. But at this moment the timestamp-every-call will start affecting the statistics of random numbers a lot for particular date-time and RNG calling period.

So I would use timestamp only for initial seeding, then the RNG would work as any common pseudo-random arithmetic RNG, with added twist of output stream being further source of entropy.

About output stream as entropy source: well, you should check the common output stream byte values first, they are not "random" 0..FF bytes. From the code it looks like you are aware of that, trying to build an unsigned value ORing 4 shifted values, but the result is only 20b wide for ASCII, and the values are overlapping, so the upper bits of ASCII (not varying much) will affect the lower bits of next character (I hope I did read the source correctly, didn't debug it, BTW for better readability you should put these transformations from string to unsigned into some function, so you can test it on it's own). I would probably take only 3 bits (or maybe just alternating 2+3, to avoid ASCII specific values definition to affect the entropy of such value too much) of each output character, and cumulate them in 32b buffer till it's full (the overlapping 1-2 bits kept for next value), then use it for transforming the seed buffer (so roughly every 10 output chars the seed will get additional entropy). This may still go quite wrong with UTF-8 or unicode16/32 output stream variants, just imagine somebody using it with UTF-8 Arabic texts, having every second byte something like D9 or what's the actual prefix (too lazy to check).

About API:

  • argc/argv initializer is not a good idea, leave that for main only, use uint8_t[] (byte) field for seeding, do the conversion in main. This way you can use for seeding any byte array generator, like in linux /dev/urandom.
  • make the ostream "transparent" replacement, so get rid of hard-coded std::cout, and give the class the desired output stream as configuration parameter (default being std::cout). For example: get entrostream for some file output stream, writing data into file, and having the entropy cumulated in that instance of file entrostream.

Code style:

  • you have lot of duplicity, like calling gettimeofday in each place and transforming the value in the same way every time (transform(tv_hash(ts)), although sometimes you don't have it together). If you would put the entrostream() code except the buffer.push into separate function returning unsigned, you could use that at every other place.
  • you can make your variable names more verbose, like ts = time_stamp, etc. It's somewhat difficult to read first time, the names itself are not that bad, but they need at least some support in comments, like some short intro in transform telling what is hashed and how much. I had to quite dig into the code itself to understand some of the variables purpose.

unsigned uis = str_to_u(tmp[i][j],i%4) in argc/argv is probably bug, the i%4 at end should have been j%4? Or it's on purpose? If it is bug, you could have avoided it by using internal method, to avoid duplicity code with operator<< implementation.

Ok, enough for now. :) I hope I'm not way off, and this will give you some ideas how to improve it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.