Getting truley random in C Options

[Siph0n]

Entropy estimation is unreliable? Unlike /dev/urandom, /dev/random is supposed to block when it has no entropy, which I would consider a good thing. However, you are saying that the decision to block or not is unreliable? Will you explain more please.

Sure. /dev/random estimates entropy and blocks when it thinks it has none, as you stated. Now, this leaves room for /dev/random to think it has some entropy, when it actually has none. Therefore, the estimation it relies on, failed. This scenario would be a bad situation if someone relies on /dev/random for cryptographic purposes, as would a state discovery. Fortuna doesn't rely on entropy estimation as much as /dev/random, and only relies on it for seeding purposes (Fortuna waits until it thinks it has enough entropy). 128 bits of entropy would be enough to last a lifetime without state discovery with Fortuna, since you're using AES in CTR mode, therefore giving a different psuedo-random result each time you increase the counter, and the fact that the universe would probably end before the counter reset. Fortuna also doesn't block.

So, I'm not saying the decision to block is unreliable; I'm saying relying heavily on entropy estimation is bad, because entropy estimation it's self is unreliable.

I hope I made more sense that time around :P

[madruse]

Sure. /dev/random estimates entropy and blocks when it thinks it has none, as you stated. Now, this leaves room for /dev/random to think it has some entropy, when it actually has none. Therefore, the estimation it relies on, failed. This scenario would be a bad situation if someone relies on /dev/random for cryptographic purposes, as would a state discovery. Fortuna doesn't rely on entropy estimation as much as /dev/random, and only relies on it for seeding purposes (Fortuna waits until it thinks it has enough entropy). 128 bits of entropy would be enough to last a lifetime without state discovery with Fortuna, since you're using AES in CTR mode, therefore giving a different psuedo-random result each time you increase the counter, and the fact that the universe would probably end before the counter reset. Fortuna also doesn't block.

So, I'm not saying the decision to block is unreliable; I'm saying relying heavily on entropy estimation is bad, because entropy estimation it's self is unreliable.

I hope I made more sense that time around :P

Actually, I was asking how you know entropy estimation is unreliable.

However, you say that the decision to block is not unreliable, but the technology used to make that decision is unreliable, how can the decision to block now therefore be reliable? Maybe consider it as: how can the decision of when to block be reliable?

[Siph0n]

Actually, I was asking how you know entropy estimation is unreliable.

However, you say that the decision to block is not unreliable, but the technology used to make that decision is unreliable, how can the decision to block now therefore be reliable? Maybe consider it as: how can the decision of when to block be reliable?

There may be a paper around giving a nice detailed description as to the unreliability of entropy estimators, I'll see if I can't find one, or someone who has one. Wikipedia has a small portion on it, however, it has to do with thermodynamics, and while information entropy theories are somewhat based on those, information entropy is not bound by thermodynamic laws.

Well, the decision to block is part of the design of /dev/random. Without entropy estimation there would be no need to block, however, one could have the option to do so. The blocking is trivial without the estimation, so in turn, the decision would be up to the author of random.c. (there wouldn't be any need to, but they might want to in order to preserve backwards compatibility if any widespread program used /dev/random to that extent)

[Valirian_Oak]

Actually, I was asking how you know entropy estimation is unreliable.

The word Entropy implies the result is unreliable. Entropy is a measure of disorder in a system. Disorder is not psedo-random, it is truly random. Disorder can not be predicted consistantly, else it wouldnt be disorder, it would be order.

Secondly, while /dev/random might be more chaotic, it is limited . If i tried to poll the random device, lets say, 50 times, i would eventualy stop getting an output. No output = no entropy..
You cant really see this on os x, but on a straight fedora distro, if you cat /dev/random, the output will stop, but if you move the mouse it will generate more.. Its pretty cool actualy.

[madruse]

The word Entropy implies the result is unreliable. Entropy is a measure of disorder in a system. Disorder is not psedo-random, it is truly random. Disorder can not be predicted consistantly, else it wouldnt be disorder, it would be order.

The word entropy does not imply the result is unreliable, just that there is some amount of error. There are techniques for measuring entropy in a system, with knowledge of the error bounds. The question becomes how does /dev/random measure its entropy pool. Does it wait until it thinks it has no entropy (consider every byte of input yields a fixed number of output bytes), or until it doesn't have sufficient (for some notion of sufficient) entropy. This is further complicated by the fact that the random device cannot know how much entropy is in its input. It has to make some assumption there too.

Originally, this was about "[/dev/random's entropy estimation] leaves room for /dev/random to think it has some entropy, when it actually has none." This is actually the source of an attack on PRNGs where the input actually has little entropy, e.g. only, always write 0s to /dev/random. How does /dev/random on Fedora decide to block?

[Peradox]

Ah, guys. urandom is from more than just keyboard and mouse, but still, there is a RELATIVELY small period for it. Try seeding the Mersenne Twister with a byte from /dev/urandom...

The Mersenne Twister has a COLLOSAL period (hehe, cool word).

Enjoy.

[Valirian_Oak]

From Man Pages

The character special files /dev/random and /dev/urandom (present since Linux 1.3.30) provide an interface to the kernel's random number generator. File /dev/random has major device number 1 and minor device number 8. File /dev/urandom has major device number 1 and minor device number 9.
The random number generator gathers environmental noise from device drivers and other sources into an entropy pool. The generator also keeps an estimate of the number of bits of noise in the entropy pool. From this entropy pool random numbers are created.

When read, the /dev/random device will only return random bytes within the estimated number of bits of noise in the entropy pool. /dev/random should be suitable for uses that need very high quality randomness such as one-time pad or key generation. When the entropy pool is empty, reads from /dev/random will block until additional environmental noise is gathered.

When read, /dev/urandom device will return as many bytes as are requested. As a result, if there is not sufficient entropy in the entropy pool, the returned values are theoretically vulnerable to a cryptographic attack on the algorithms used by the driver. Knowledge of how to do this is not available in the current non-classified literature, but it is theoretically possible that such an attack may exist. If this is a concern in your application, use /dev/random instead.

The word entropy does not imply the result is unreliable, just that there is some amount of error. There are techniques for measuring entropy in a system, with knowledge of the error bounds.

Secondly, the term entropy, which is often used in chaos math [one of my specialties] so i am going to try to explain it a little more clearly.. For the above statement made by madruse, is only partialy correct.

Entropy is, by deffinition, the measure of dissorder in a system. Think of it as just an int which holds the number of "errors" in a system. [errors is not really a good term to use here, but for lack of a better word] You will find that the words Entropy and uncertainty, are used interchangably in most chaos math theories. the mathmatical formulay to calculate entropy is :
 entropy01.gif ( 1021bytes ) Number of downloads: 25


If any of the probabilities approach zero then the system is mathmaticlly ambiguous. In other words, if H of x = 0 , then there is no uncertainty. [Or rather, assumed to be no uncertainty... I mean this is chaos math ;)].

Ill give a quick example..

Lets say we have :

Category A B C D E
Probablility 0.0 1.0 0.0 0.0 0.0

then we could calculate the disorder as

E(x) = 0 x log2(1/0) + 1 x log 2(1/1) + 0 x log2(1/0) + ...
E(x) = 0

which implies no uncertainty.


So if we apply that to the random and urandom devices, we can hold true this example:

With the keys A, B, C, D, and E, lets say the probablity of the user pressing the A key next is .25, pressing the B key is 0, pressing the C key is .25, pressing the D key is .25 and pressing the E key is .25.

We could calculate the entropy as such:

E(x) = .25 x log2(1/.25) + 0 x log2(1/0) + .25 x log2(1/.25) + ...
E(x) = 2

which implies that there are two bytes of uncertainty, so if i polled /dev/random for entropy, i would get effectivly only 2 bytes ENTRIPIC, or random data.

I hope that this helped to explain entropy.. and that the word itself , is just a measure of disorder, which can be calculated, but not predicted.

[Poiuyt]

I quickly scanned over this post and didn't really read it so excuse my retardation if I've missed the point.

I didn't see any mention of the Mersenne Twister pseudo random number generation algorithm so I thought I'd mention it, as it's viewed as 'professional' pseudo random number generation quality.

Many of the online poker sites use it for card 'randomization'.

http://en.wikipedia.org/wiki/Mersenne_twister

Google it.


The following generates uniformly 32 bit integers in the range [0, 2^32 - 1] with the MT19937 algorithm:

// Create a length 624 array to store the state of the generator
var int[0..623] MT
// Initialise the generator from a seed
function initialiseGenerator ( 32-bit int seed ) {
MT[0] := seed
for i from 1 to 623 { // loop over each other element
MT[i] := last_32bits_of(69069 * MT[i-1])
}
}

// Generate an array of 624 untempered numbers
function generateNumbers() {
for i from 0 to 622 {
y := 32nd_bit_of(MT[i]) + last_31bits_of(MT[i+1])
if y even {
MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y))
} else if y odd {
MT[i] := MT[(i + 397) % 624] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
}
}
y := 32nd_bit_of(MT[623]) + last_31bits_of(MT[0])
if y even {
MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y))
} else if y odd {
MT[623] := MT[396] bitwise_xor (right_shift_by_1_bit(y)) bitwise_xor (2567483615)
}
}

// Extract a tempered pseudorandom number based on the i-th value
function extractNumber(int i) {
y := MT[i]
y := y bitwise_xor (right_shift_by_11_bits(y))
y := y bitwise_xor (left_shift_by_7_bits(y) bitwise_and (2636928640))
y := y bitwise_xor (left_shift_by_15_bits(y) bitwise_and (4022730752))
y := y bitwise_xor (right_shift_by_18_bits(y))
return y
}

HTH.

[Siph0n]

here an implementation..i think...

CODE

#!/usr/bin/python

global n; n = 624
global m; m = 397

global mt; mt = [None]*n

def init_genrand(s):
    mt[0] = s & 0xffffffffL
    for i in xrange(1,n):
        mt[i] = (1812433253L * (mt[i-1] ^ (mt[i-1] >> 30)) + i)
        mt[i] &= 0xffffffffL
        
def genrand():
    for i in xrange(n-2):
        y = (mt[i] >> 31) + (mt[i+1] >> 1)
        
        mt[i] = mt[(i+m)%n] ^ ( y >> 1)
        
        if y % 2 != 0:
            mt[i] ^= 2567483615
            
    y = (mt[n-1] >> 31) + (mt[0] >> 1)
    
    mt[n-1] = mt[m-1] ^ (y >> 1)
    
    if y % 2 != 0:
        mt[n-1] ^= 2567483615
        
def extract_rand(i):
    y = mt[i]
    
    y ^= (y >> 11)
    y ^= (y << 7) & 2636928640
    y ^= (y << 15) & 4022730752
    y ^= (y >> 18)
    
    return y

def extract_real2(i):
    return extract_rand(i)*(1.0/4294967296.0)
        
    
def main():
    import time
    
    init_genrand(int(time.time()))
    genrand()
    
    print extract_rand(int(time.time())%(n-1))
    print extract_real2(int(time.time())%(n-1))
    
if __name__ == '__main__':
    main()

It appears to work decent...

CODE

[reikon@reikon: ~ ]$ python /Users/reikon/Desktop/mt.py
1464568889
0.340996517101
[reikon@reikon: ~ ]$ python /Users/reikon/Desktop/mt.py
4219900082
0.982522052247
[reikon@reikon: ~ ]$ python /Users/reikon/Desktop/mt.py
3228189403
0.751621416537
[reikon@reikon: ~ ]$