Re: Where to get a good seed for srandom()
Marcus Watts states: Another way to fix this, is if you're using %, make sure the random value you plug into % is smaller than the largest multiple. For 189, that would be 22724694*189 or 4294967296U. If the number you get is larger than this, discard it and obtain another random number. If you throw out the last 130 values, you've now got a fair generator. This is good advice. CHEERS -- Jack Bates Venice, CA, USA I play Texas Hold'Em at http://www.fulltiltpoker.com
Re: Where to get a good seed for srandom()
Hi,
that is an interesting (off-)topic :-) May I ask the very last question?
If % is not good enough for getting random values in a range, then what is?
I see a lot of arc4random() % ... when grepping the /usr/src on OpenBSD.
And my (probably too naive) approach to shuffling 32 cards has been:
void shuffle(card deck[])
{
unsignedk, n;
card tmp;
for (k = 0; k 32; k++) {
/* find the new position for the card at k */
n = arc4random() % 32;
/* swap the cards at the indices k and n */
tmp = deck[n];
deck[n] = deck[k];
deck[k] = tmp;
}
}
Regards
Alex
2005/7/18, Jack Bates [EMAIL PROTECTED]:
I happen to be very familiar with this subject, having developed, analyzed
and qualified two different card-shuffling algorithms for real-money play
in the online card game business. There is a fair bit of literature on
this subject.
Some tips that I can share without breaking an NDA:
1) Do not use current time other than as an _adjunct_ to initial seeding
of a quality PRNG. Under OpenBSD, you can obtain a good initial seed from
/dev/?random, so why bother using time at all?
2) Use of a hardware device (HRNG), such as the SG-100 from Protego
(Sweden) or motherboard HRNG is preferred to a PRNG, as its state cannot
be observed in memory.
3) Qualify the quality of your random seed if it is coming from an HRNG.
Some of these things have warm-up time and will initially produce poor
entropy.
4) Do not use the % (modulo) operator to select a card. The residues from
% introduce small amounts of bias, and this is a disqualifying factor for
regulated gaming.
5) Knuth's Art of Computer Programming has an algorithm for fairly
shuffling cards. Unfortunately it assumes perfect floating-point math,
which a computer cannot really do. The algorithm, however, is worth
studying.
CHEERS
--
Jack Bates
Venice, CA, USA
I play Texas Hold'Em at http://www.fulltiltpoker.com
Re: Where to get a good seed for srandom()
Alexander Farber [EMAIL PROTECTED] asks: ... If % is not good enough for getting random values in a range, then what is? ... Actually, % 32 is fine (or any reasonably small power of 2). Modulo any odd number is guaranteed to have at least a small problem, and module a large enough number is going to start to get really bad. To illustrate the problem, suppose you had a perfect rand function that returned numbers in the range 0-255. On average, about half the time, the numbers will be even or odd. That's %2. Any power of two up to 128 will work perfectly as well. Now, suppose instead we take it module 189. For values out of the rand function less than 189, things work fine. However, there are only 67 values = 189, so the output of this will be twice as likely to pick values 0-66 as it is values 67-188. That's sort of really bad. Now, the output from arc4random() is really quite large, so for small values of N, %N will be fine. It's only for large values of N that this roundoff problem is going to be significant. The for N=289 and using arcrandom(), the bias is only 0.00044, so it would take a lot of values to estimate this empirically. Another way to fix this, is if you're using %, make sure the random value you plug into % is smaller than the largest multiple. For 189, that would be 22724694*189 or 4294967296U. If the number you get is larger than this, discard it and obtain another random number. If you throw out the last 130 values, you've now got a fair generator. rc4 is a common cheap expansion function for random functions. A higher quality but slower method is to use sha-1 or some other function. Another possible alternative is to use a symmetric algorithm such as aes or blowfish. Typically you would plug your seed plus a counter into the input of these functions, then supply the output (perhaps with some truncation) as the result of your function. Incidently, I think your card shuffling algorith has some of the same problems as the rc4 key schedule algorithm. You might want to read up on that. -Marcus Watts
Re: Where to get a good seed for srandom()
Hello! On Mon, Jul 18, 2005 at 11:02:54AM -0700, Jack Bates wrote: [...] 4) Do not use the % (modulo) operator to select a card. The residues from % introduce small amounts of bias, and this is a disqualifying factor for regulated gaming. Does that point still hold, assuming I use a modulus which is a divisor of the range of the original random values? I use the following algorithm, assuming a random generator that yields k-bit unsigned numbers of randomness, to yield random numbers between 0 and n-1: - determine the maximum multiple of n which is = 2^k, call that m - get a random number from the source generator, until that number is m, call that r - return (r % n) By re-getting random numbers, I transform the source (P)RNG into a (P)RNG that yields numbers = 0, m, and m is a multiple of n, that should eliminate the bias, as long as the (P)RNG doesn't have a bias if the previous number it yielded was = m. [...] Kind regards, Hannah.
Where to get a good seed for srandom()
Hi,
I'm developing a small multiplayer card game on OpenBSD
(but also try to keep it at least compilable on Linux).
After 32 cards have been shuffled, each of 3 players gets
10 cards. At the moment I use the sum of time()s when any
data has been received from a player as the seed value:
typedef struct client_s {
.
time_t last;
} client;
.
srandom((cp-last + prev-last + next-last) % UINT_MAX);
I'm worried though, that someone will look at my source code
and since those 3 time()s are probably contained in the last 10
minutes, then there aren't actually that many variants.
So an attacker will prepare a list of possible variants,
filter them by looking at the 10 cards at his own hand and
then with each played trick will have a better idea,
what cards do the other players have in their hands.
Where could I get a better seed? Should I use the initstate()
and srandomdev() routines and how to use them (in which
order)?
Regards
Alex
PS: Also I'm worried, if my naive code above
overflows and maybe in few years it'll be equal to
srandom(UINT_MAX % UINT_MAX); or similar...
Re: Where to get a good seed for srandom()
Artur Grabowski wrote: A good suggestion might be to use arc4random(3) instead of random(3). If the security of your application depends on randomness, you should really pay an expert to help you do it. Randomness is harder than it looks and most likely you will screw it up very badly (a few years ago some online Black Jack lost a lot of money because they improved their randomness by adding the current time to it). //art Can you actually only use software code to achieve true randomness? Doesn't it require a hardware solution (like a hardware that listens to background radiation to create random numbers)? OpenBSD keep it real by keeping it free! Said Outgajjouft
Re: Where to get a good seed for srandom()
Said Outgajjouft [EMAIL PROTECTED] writes: Can you actually only use software code to achieve true randomness? Who cares? You don't need true randomness. You need good enough. What good enough is depends on your application, the potential threats, the sophisitcation of the attackers, the other secuirty problems your application might have, etc. Even the best true randomness doesn't protect your application from rubber hose cryptanalysis. //art
Re: Where to get a good seed for srandom()
Thank you for both good advices. Until I have money to pay an expert and my card game isn't using real money... Would arc4random() % 32 be the usual way to get random integers from 0 to 31, or are some bits of the returned value more random than the others? And what is the highest number returned by arc4random(), is it RAND_MAX? The man page doesn't elaborate on this subject Regards Alex 18 Jul 2005 11:50:25 +0200, Artur Grabowski [EMAIL PROTECTED]: A good suggestion might be to use arc4random(3) instead of random(3). If the security of your application depends on randomness, you should really pay an expert to help you do it. Randomness is harder than it looks and most likely you will screw it up very badly (a few years ago some online Black Jack lost a lot of money because they improved their randomness by adding the current time to it).
Re: Where to get a good seed for srandom()
Alexander Farber [EMAIL PROTECTED] writes: And what is the highest number returned by arc4random(), is it RAND_MAX? The man page doesn't elaborate on this subject 32 bits. //art
Re: Where to get a good seed for srandom()
Alexander Farber wrote:
Hi,
I'm developing a small multiplayer card game on OpenBSD
(but also try to keep it at least compilable on Linux).
After 32 cards have been shuffled, each of 3 players gets
10 cards. At the moment I use the sum of time()s when any
data has been received from a player as the seed value:
typedef struct client_s {
.
time_t last;
} client;
.
srandom((cp-last + prev-last + next-last) % UINT_MAX);
I'm worried though, that someone will look at my source code
and since those 3 time()s are probably contained in the last 10
minutes, then there aren't actually that many variants.
use arc4random(). If you need to port it to Linux, include an
arc4random() replacement. If you like, you can copy the one from
portable OpenSSH.
-d
Re: Where to get a good seed for srandom()
Good day: I happen to be very familiar with this subject, having developed, analyzed and qualified two different card-shuffling algorithms for real-money play in the online card game business. There is a fair bit of literature on this subject. Some tips that I can share without breaking an NDA: 1) Do not use current time other than as an _adjunct_ to initial seeding of a quality PRNG. Under OpenBSD, you can obtain a good initial seed from /dev/?random, so why bother using time at all? 2) Use of a hardware device (HRNG), such as the SG-100 from Protego (Sweden) or motherboard HRNG is preferred to a PRNG, as its state cannot be observed in memory. 3) Qualify the quality of your random seed if it is coming from an HRNG. Some of these things have warm-up time and will initially produce poor entropy. 4) Do not use the % (modulo) operator to select a card. The residues from % introduce small amounts of bias, and this is a disqualifying factor for regulated gaming. 5) Knuth's Art of Computer Programming has an algorithm for fairly shuffling cards. Unfortunately it assumes perfect floating-point math, which a computer cannot really do. The algorithm, however, is worth studying. CHEERS -- Jack Bates Venice, CA, USA I play Texas Hold'Em at http://www.fulltiltpoker.com
