Hi there,
Its a pretty commonly-complained-about thing at least in my NWN circles that the RNG in NWN1 is pretty cooked. I have some experience with writing these kind of pseudorandom number generators, but I am not sure if it’s possible: can one replace the RNG within NWN with their own home-cooked algo or is it hard-coded into the engine?
I would bet that the random number generator is deeply buried in the engine.
What sense would it make to replace it?
I suspect so as well, but if it is addressable by nwscript I would prefer a much more actually-pseudorandom generator, NWN’s baked in one is pretty cooked in it’s distribution. The question is “if”
The random number generator is baked into the engine, like all functions in nwscript.nss.
I suppose the developers could expose it, but they might have other priorities.
Failing that, you can’t change the RNG for existing modules at a stroke.
You could write a new function, but editing every RNG instance in an existing module would be tedious. Even for a new module, there would be a lot of included functions to fix.
I’m no expert, but I wonder whether the new function, which would have to be written in nwscript, with little more than time functions for seeding, could actually be superior to what we already have.
While I likely won’t pursue this if it’s inaccessible in something that’s hardcorded, I do want to touch on one thing:
I’m no expert, but I wonder whether the new function, which would have to be written in nwscript, with little more than time functions for seeding, could actually be superior to what we already have.
Many high end security applications are using ECDSA and related algorithms seeded only on the system clock. Insecurity of this approach nonwithstanding - knowing when the seed was made trivializes cracking - even just the ingame timestamp is sufficent large a domain for our purposes. To say nothing of doing something fancier like making the seed based on the aggregate of the last few movements, which emulates the random mouse movements programs like PuTTYgen encourage for even stronger seeds.
Whereas I don’t feel like reimplementing every roll in the game - and I doubt anyone would take me up on requests to do so, this is likely a thought experiment. It’s a bit unfortunate that we cannot directly override the pseudorandom number generator however.
Why do you need a cryptographically secure prng to roll d20s for a game? In the distant past (like when it first came out) the prng in NWN was indeed pretty bad. I think it did not get reseeded enough. So for example you could know what the next roll would be on a saved game. But I believe that was fixed a while ago.
Use real security for your sshkeys and encryption etc. But just play the game…
No one enjoys a game relying on loaded dice. Or at least not I.
But I wasn’t soliciting thoughts on whether the RNG is sufficient, I was asking if it was replacable, to which I already have an answer.
Well, you asked about replacing it. Seems reasonable for me to ask why, but whatever.
The game just does rand() % numSides + 1, if you’re on linux you can preload a replacement of rand(), which someone did in this thread: Another discussion about RNG and dice roll behavior — Beamdog Forums
That said, have you done any statistical analysis using the nwscript Random() function or is the cooked-ness just in your head? 
FWIW, I have a small suite of prng routines written in Modula 2. The algorithm that they are based on was converted from a version in C that was converted from the original in FORTRAN (I only did the conversion from C to Modula 2).
Here is the *.def file (the modula 2 equivalent to ANSI C’s *.h file)
DEFINITION MODULE PRandum;
(* 12/95 *)
(************************************************************************)
(* An improved pseudo random number generator. This suite of routines *)
(* are based around an algorithm that was obtained from Lancaster *)
(* University. The random number generator as received from L.U. was *)
(* in C, and is itself a conversion from the original, which was *)
(* written in FORTRAN. *)
(************************************************************************)
PROCEDURE RandomProbability () : REAL;
(************************************************************************)
(* Returns a "random" number in the range 0 to 1 *)
(************************************************************************)
PROCEDURE RealRandom ( MaxReal : REAL ) : REAL;
(************************************************************************)
(* Returns a "random" number in the range 1 to MaxReal *)
(************************************************************************)
PROCEDURE IntRandom ( MaxInt : INTEGER ) : INTEGER;
(************************************************************************)
(* Returns a "random" number in the range 1 to MaxInt *)
(************************************************************************)
PROCEDURE SeedRandom ( First, Second : INTEGER );
(************************************************************************)
(* Changes the sequence of "random" numbers in a "predictable" manner - *)
(* NOTE - *)
(* First must be in the range 0 to 31328, and *)
(* Second must be in the range 0 to 30081. *)
(************************************************************************)
PROCEDURE Randomise;
(************************************************************************)
(* Alters the sequence of "random" numbers in an unpredictable manner *)
(*----------------------------------------------------------------------*)
(* INFORMATION *)
(* ----------- *)
(* The algorithm used is claimed to have a periodicity of 2 to the power*)
(* 144 or approximately 2.2300745 * 10 to the power 43. The periodicity *)
(* is the number of random numbers that have to be generated before the *)
(* sequence of numbers is exactly repeated. Further to the above, the *)
(* algorithm is also claimed to pass ALL the tests for random number *)
(* generators. Another thing that is claimed for this algorythm is that *)
(* if the first of the 2 seed values is left unaltered, then the *)
(* periodicity of the sub-sequence that is produced is roughly 10 to *)
(* the power 30 and there are 900,000,000 such sub-sequences *)
(* approximately. *)
(************************************************************************)
END PRandum.
Note - This suite is more than overkill for use in games, being intended for scientific use when originally created. Also, due to the way the main algorithm works, I don’t think it could be converted to NWScript either.
TR
I don’t have it to hand at the office, but yes, albeit over a relatively small sample size since I wasn’t going to get into deep analysis if it wasn’t possible to fix.
The game just does
rand() % numSides + 1, if you’re on linux you can preload a replacement of rand(), which someone did in this thread: Another discussion about RNG and dice roll behavior — Beamdog Forums
That’s a great link, and gives me an in to fix this. Thanks for that!
I couldn’t really comment on xorshift* algorithms, I don’t actually have any experience with them.
We’re getting a bit into the weeds, not sure if there’s DMs here, but it might be better there.
In general, when it comes to cryptography, the thing to realize is that the approach of the security programmer is akin to the maker of a mechanical lock: it isn’t about keeping someone out per se. Anyone with enough time can break a lock physically, even if they cannot overcome the mechanism. The approach rather is to maximize the delay to a potential attacker. When the opportunity cost is high enough, drive-by attacks and other intrusions of opportunity move on to softer targets. When you’re the specific target of a directed attack, it comes down to knowing the attacker and having specific and tailored countermeasures, along with not making mistakes in general security.
PCG is generally-effective against several algorithms, especially weak ones, though RSA et al usually have quicker exploits given the inherent backdoor. ed* style cryptology schemes tend to be harder to crack with PCG*
In the context of NWN, on a proper dedicated machine, RNG is likely not a problem. However, I am running a headless server on a virtual machine, where available entropy is (relatively) low. Normally, a Linux machine uses a combination of sensors on the computer to generate the chaos (unpredictable inputs) to have sufficient entropy. On a virtual machine, the available entropy is generally weak, since these sensors are not usually exposed from the hypervisor. This is very likely the root cause of my problem, but there are things I can do to alleviate this situation, since it’s just using the system-provided randomization.
It occurs to me to say this for those that google may lead here with similar issues:
Consider either using Intels Digital Random Number Generator if it is included with your processor, or as software alternatives such as virtio-rng if they are available with your Linux distribution/their packaging streams.
heya, I’m not generally knowledgeable enough in low level pRNG stuff to warrant much discussion,
am not concerned with security either, just RNG for dice rolls and what not. So, more concerned with distribution, periodicity, etc.
currently pleased with an implementation of xorshift64* (subjectively – and in a different game)
uint64_t next()
{
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
return x * 2685821657736338717ULL;
}
void setSeed(uint64_t seed)
{
if (seed == 0)
x = static_cast<uint64_t>(std::chrono::system_clock::now().time_since_epoch().count());
else
x = seed;
}
int generate(int min, int max)
{
if (min == max) return min;
if (min > max) std::swap(min, max);
return static_cast<int>(next() % static_cast<uint64_t>(max - min + 1)) + min;
}
As you see, very sparse and fast. PCG is more recent and, from what I’ve read, seems to be roughly equivalent or better in the aspects that id want.
Apparently PCG handles multiple streams better. In fact the more i delve down into it, the better PCG looks for “overall fairness.”
Nwn1/2 came out at a time (roughly) before these fast/fair pRNG algorithms were available …
I don’t know about that; the BOOM sourceport for DOOM ends up with a fairly immaculate probability distribution for its RNG, though if you wanted to nick it, you’d have to adapt it to your specific needs.