Difference between revisions of "Talk:Pseudo-random Number Generator"
m |
m |
||
| Line 13: | Line 13: | ||
-- [[User:Ppaatt Lynagh|Ppaatt Lynagh]] 07:41, 25 August 2012 (PDT) | -- [[User:Ppaatt Lynagh|Ppaatt Lynagh]] 07:41, 25 August 2012 (PDT) | ||
The problem with using MD5 in this way is how tightly it loops. So you start with a seed string that that produces a hash you use as the next seed, the question is how long before you generate a hash that is the same as the hash of your initial seed. It could happen in a short time frame or a long time frame. I would recommend using an incremental counter and using the integer seed for llMD5String. This way you are guarantied* that the size of a loop is a multiple of 2^32. Oh and it makes your function safer. | The problem with using MD5 in this way is how tightly it loops (which is hard to know). So you start with a seed string that that produces a hash you use as the next seed, the question is how long before you generate a hash that is the same as the hash of your initial seed. It could happen in a short time frame or a long time frame. I would recommend using an incremental counter and using the integer seed for llMD5String. This way you are guarantied* that the size of a loop is a multiple of 2^32. Oh and it makes your function safer. | ||
Also the initial algorithm (not using a counter) makes it easy to predict the next number. If you give an attacker access to NextInt, the attacker can quickly* zero in on the seed by guessing the end of the seed of second number they request. They would likely need to request three numbers in a row. It would be computationally difficult but it lends it self to be brute forced. Adding a counter does not eliminate this attack, it just makes it much more expensive (as you need to also determine the counter). A solution to this problem too is to add in a second static secret. I wouldn't bother adding the extra secret but I would add the counter. | Also the initial algorithm (not using a counter) makes it easy to predict the next number. If you give an attacker access to NextInt, the attacker can quickly* zero in on the seed by guessing the end of the seed of second number they request. They would likely need to request three numbers in a row. It would be computationally difficult but it lends it self to be brute forced. Adding a counter does not eliminate this attack, it just makes it much more expensive (as you need to also determine the counter). A solution to this problem too is to add in a second static secret. I wouldn't bother adding the extra secret but I would add the counter. | ||
Latest revision as of 08:08, 25 August 2012
> Seedable PRNG Based On MD5 Hashing > I haven't noticed any irregular behavior in this one, > i would love to know what you guys think - Kyrah Abattoir
Walking randomly by taking one built-in cryptohash after another sounds efficient and re-seedable and pseudo-random, aye.
On the down side, in this moment, my own knowledge of crypto maths isn't much deeper than Bruce Schneier's "Applied Cryptography", so I'd wonder about how solidly random the bits feel.
We could write code, to measure how random the bits feel, running inside or outside SecondLife, giving attention to particular bits not just the whole value.
I'd guess we'd thus show that cascading llMD5String feels more random than our instance of Linear Congruential, which in turn feels more random than our idiosyncratic Multiply Add Overflow.
-- Ppaatt Lynagh 07:41, 25 August 2012 (PDT)
The problem with using MD5 in this way is how tightly it loops (which is hard to know). So you start with a seed string that that produces a hash you use as the next seed, the question is how long before you generate a hash that is the same as the hash of your initial seed. It could happen in a short time frame or a long time frame. I would recommend using an incremental counter and using the integer seed for llMD5String. This way you are guarantied* that the size of a loop is a multiple of 2^32. Oh and it makes your function safer.
Also the initial algorithm (not using a counter) makes it easy to predict the next number. If you give an attacker access to NextInt, the attacker can quickly* zero in on the seed by guessing the end of the seed of second number they request. They would likely need to request three numbers in a row. It would be computationally difficult but it lends it self to be brute forced. Adding a counter does not eliminate this attack, it just makes it much more expensive (as you need to also determine the counter). A solution to this problem too is to add in a second static secret. I wouldn't bother adding the extra secret but I would add the counter.
<lsl> //counter is a global integer seed = llMD5String(seed, ++counter); </lsl>
<lsl> //counter is a global integer //secret never changes during execution seed = llMD5String(seed + secret, ++counter); </lsl>
-- Strife (talk|contribs) 09:05, 25 August 2012 (PDT)
rand can be optimized to and will be mono safe as...
integer rand(integer spread) {
seed2 = (seed2 * seed2Mod + 0xB);
return (seed1Mod = ((seed1 = (seed1 * (seed2Mod = seed1Mod) + 0xB)) * seed2)) % spread;
}
-- Strife Onizuka 11:25, 21 November 2007 (PST)
- I like to try to keep the code human-readable at first, but I'll add this as the optimized version. Thanks --Xaviar Czervik 09:55, 26 November 2007 (PST)
If we use 2 seeds, could we XOR "^" the seeds after modifiing the seeds, instead of "+" or "*"? to make it faster? —The preceding unsigned comment was added by Ollj Oh
- I haven't done cryptographic analysis of this function to ensure it's distribution but I'm inclined to say that you shouldn't use XOR. I think it would result in some quantity of bits being predictable. I'm pretty sure the distribution of this function is skewed regardless. If you feed it 1431655765, you should notice that numbers between -715827882 & 715827882 have twice the probability then those outside. With smaller numbers this type of skew is less noticeable, but as long as
((2147483648 % spread ) != 0)is true then you will have a skew. -- Strife Onizuka 09:07, 11 February 2008 (PST)