samedi 26 novembre 2016

Timing-based (truly) random numbers?

I need a random number generator. Not for pseudo-random numbers, but the truly random kind. It crossed my mind that maybe I could extract bits from the subtle timing differences in loop execution, so I put something together to do just that:

#ifdef _WIN32
#include <windows.h>
unsigned long long tick()
{
    unsigned __int64 
        tock;
    QueryPerformanceCounter((LARGE_INTEGER *)&tock);
    return (unsigned long long)tock;
}
#elif __linux__
#include <sys/time.h>
unsigned long long tick()
{
    timespec 
        tock;
    clock_gettime(CLOCK_REALTIME, &tock);
    return (unsigned long long)tock.tv_nsec;    
}
#else
#warning "random_bits()/random_word() may run slowly on this system"
#include <time.h>
unsigned long long tick()
{
    return (unsigned long long)clock();    
}
#endif
#include <limits.h>
unsigned long long random_bits(unsigned short bits)
{
/*
    The `threshold` setting determines the smallest sample to extract a bit 
    from. If set too low the result won't contain enough entropy to be useful. 
    We don't want to set it so high that we're just wasting CPU cycles either, 
    so we need to settle on a value somewhere in the middle. Heuristically, 
    256 seems to be a pretty good compromise.    
*/    
    const unsigned long long    
        threshold = 256;
    unsigned long long
        result = 0,
        increment,
        accumulator,    
        count,
        target;
    const unsigned short
        size = sizeof(result) * CHAR_BIT;    
    if(bits == 0 || bits > size)
        bits = size;
    while(bits-- > 0)
    {
        increment = 1;
        accumulator = 0;
    /*
        Build up the value to be extracted from. We don't know anything 
        about the clock resolution, so the increment is repeatedly doubled 
        until it's large enough to make a difference.
    */        
        while(accumulator < threshold)
        {
            count = 0;
            target = tick() + increment;
            while(tick() < target)
                ++count;            
            accumulator += count;
            increment <<= 1;                
        }
    /*
        Shift the previous bit up one position and insert the newly sample one.
    */        
        result <<= 1;
        result |= (accumulator & 1);
    }    
    return result;
}
unsigned long long random_word(unsigned short length)
{
    return random_bits(length * CHAR_BIT);
}

//    Example useage:

#include <stdio.h>
int main(void)
{
    for(;;)
    {
        printf(" %u\n", (unsigned)random_word(sizeof(unsigned)));
        getchar();
    }
}

It appears to work well (passes the TESTU01 test suite)...but I still wonder:

(1) did I implemented everything correctly

(2) do the platform #defines look okay

(3) is there is any (reasonable) likelihood that this could be vulnerable in the case where a hacker gains control of the system time or some such

(4) is there is some better way to achieve this

(5) are there any legitimate arguments that (a) the generated values are in fact not sufficiently random and (b) if so, whether adjusting the threshold parameter might remedy the situation in such a case




Aucun commentaire:

Enregistrer un commentaire