Lua Randomness Library

General discussion about LÖVE, Lua, game development, puns, and unicorns.
EliterScripts
Citizen
Posts: 85
Joined: Sat Oct 25, 2014 7:07 pm

Lua Randomness Library

Post by EliterScripts » Sat Dec 15, 2018 12:24 am

Hello,
In my game, it would be super useful if I could get a really good randomness library. Now, I know Lua has math.random and LOVE2D has love.math.random, but I haven't really been impressed by either pseudo random number generator/algorithm. It is too predictable.

I've done a little bit of research a while ago about randomness, and I came across what is known as a CSPRNG (Cryptographically Secure Pseudo-Random Number Generator). Since true randomness is hard to come by, you have to fake it. Now, I'm not a super-expert in math, so I don't understand how pseudo-randomness works, but I know that OpenSSL does a good job at making the randomness very unpredictable (even if you try predicting it with math, it is difficult).

I have only found one Lua OpenSSL binding on the Internet, and wanted to know what your thoughts on it are. I'm tempted to just run a command in Linux to fetch a random value, but that poses two potential problems: 1.) if the user has not installed OpenSSL, it will not work and 2.) if the user is running Windows...I don't know, but it would be a bad idea in my opinion.

grump
Party member
Posts: 612
Joined: Sat Jul 22, 2017 7:43 pm

Re: Lua Randomness Library

Post by grump » Sat Dec 15, 2018 1:44 am

EliterScripts wrote:
Sat Dec 15, 2018 12:24 am
I haven't really been impressed by either pseudo random number generator/algorithm. It is too predictable.
Can you elaborate? How did you come to this conclusion?
I came across what is known as a CSPRNG (Cryptographically Secure Pseudo-Random Number Generator).
I'm no expert either, but as far as I know, CSRNGs rely on a good entropy source, and that is one reason why they are slow. Much slower than PRNGs. When the RNG runs out of entropy, your game is fucked.

User avatar
zorg
Party member
Posts: 2914
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Lua Randomness Library

Post by zorg » Sat Dec 15, 2018 10:17 am

grump wrote:
Sat Dec 15, 2018 1:44 am
When the RNG runs out of entropy, your game is fucked.
Only in the sense if your game would actually need cryptographically secure random numbers, and i'd wager that's nowhere near true.
But yes, do elaborate on how did you "predict" Löve's own prng? It's seeded each time Löve runs, so it should give different runs each time.
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.

User avatar
pgimeno
Party member
Posts: 2176
Joined: Sun Oct 18, 2015 2:58 pm

Re: Lua Randomness Library

Post by pgimeno » Sat Dec 15, 2018 11:30 am

I would also like to know why. Love's PRNG is obviously not a source of cryptographically secure random numbers, but it's quite decent for game usage. Much more than LCGs, for sure. I haven't tested it for repeated re-seeding, though, which is a weakness in many generators (so bad that Knuth changed his LFG based on my feedback in that respect, see https://www-cs-faculty.stanford.edu/~kn ... 2.html#rng).

LuaJIT departs from PUC Lua and implements its own generator, both for better quality and for cross-platform compatibility, but I don't think it's cryptographically secure either. See http://luajit.org/extensions.html#math_random.

About entropy: If you want it to be cryptographically secure, then yes, you need a source of entropy. But let me put the record straight on this.

The main usage for which you need as much entropy as output bits, is key generation. If you're generating keys, and have, say, 64 bits of entropy, and use them to generate a series of 64 bit keys, then if an adversary manages to do an exhaustive search through all 64 bits, they have ALL keys at the same time (by applying the same algorithm as you used to derive the keys from the entropy). However, by having as much input entropy as output bits, you ensure that each key must be independently brute-forced, and the key size DOES reflect the actual difficulty in cracking each key.

But that usage is very specific. For normal usage, you can do with as much entropy as the desired key size, and then generate pseudorandom numbers based on that. That's what stream ciphers consist of, for example RC4 or any cipher algorithm in CTR mode. A stream cipher is a CSPRNG with a secret seed and unpredictable output, which is XORed with the plaintext to obtain the ciphertext. The key size should be chosen so that you can be confident enough that no one will attempt to brute-force it. This does not necessarily depend on the state of the art with respect machine power and parallel processing, but also on weighing benefit vs. effort. If it's used, say, to send a record to the high score table in a server, you can be fairly confident that no one is going to hire a cluster of cloud servers to break it so that they can send a fake score.

As far as I know, LÖVE has no built-in encryption features, so the next best is either looking for an encryption algorithm in Lua or LuaJIT, or using one of the built-in hash functions in CTR mode as if it were an encryption algorithm. MD5 is the simplest and fastest it supports, and the weaknesses of MD5 don't really apply to this kind of usage, so that would be a good choice.

But depending on the kind of purpose you want, that may be, as we say in Spain, "killing fleas with cannon shots".
Last edited by pgimeno on Sat Dec 15, 2018 4:32 pm, edited 1 time in total.

User avatar
arampl
Party member
Posts: 248
Joined: Mon Oct 20, 2014 3:26 pm

Re: Lua Randomness Library

Post by arampl » Sat Dec 15, 2018 2:08 pm

zorg wrote:
Sat Dec 15, 2018 10:17 am
Only in the sense if your game would actually need cryptographically secure random numbers, and i'd wager that's nowhere near true.
Agreed!

@EliterScripts, it can be right the opposite on how to generate random numbers for games. Good explanation here: http://howtomakeanrpg.com/a/better-than-dice.html.

grump
Party member
Posts: 612
Joined: Sat Jul 22, 2017 7:43 pm

Re: Lua Randomness Library

Post by grump » Sat Dec 15, 2018 3:30 pm

zorg wrote:
Sat Dec 15, 2018 10:17 am
grump wrote:
Sat Dec 15, 2018 1:44 am
When the RNG runs out of entropy, your game is fucked.
Only in the sense if your game would actually need cryptographically secure random numbers, and i'd wager that's nowhere near true.
Yep. it'd be total overkill.

What I meant to say was: if you truly use a CSRNG for something like procedural generation like you would with a LCG or LÖVE's LFSR, and it runs out of entropy, the RNG (and the game) would come to a halt while it gathers entropy. In that case, just use the entropy generated from the player smashing his head on the keyboard from frustration over the loading times.

I'm joking - I don't know much about that stuff, other than it's not suitable to be used for a game.

EliterScripts
Citizen
Posts: 85
Joined: Sat Oct 25, 2014 7:07 pm

Re: Lua Randomness Library

Post by EliterScripts » Sun Dec 16, 2018 11:06 am

Yeah, I don't need cryptography. I just figured it would be safe to go with a CSPRNG, because it sounds more random than a regular RNG.

Now, I have booted up LOVE2D a couple of times, I think it was with a thing that I coded as a test project for changing the background color to random colors (it would do a smooth transition--it was very nice to look at, and hypnotizing), but the color changes just seemed to repeat and be super super predictable by-the-eye. I didn't go in and do mathematical voo-doo magic to predict the randomness, it just seemed super predictable, as it seemed to repeat, even after opening up multiple windows and closing and opening it again. Maybe I'm wrong, but that is what I remember.

I also figure that people/companies like Google, Amazon, and almost literally anyone running Apache, nginx or any webserver that connects to the modern internet, and the rest of the world literally send thousands, millions, billions of pages and messages encrypted over the Internet. I figured OpenSSL (which I assume runs everything that is non-governmental cryptography) would be really fast and secure, since many many many people use it every day.

I'm not a super smart tech guy, but I run a few non-critical (non-secure, non-not-secure--too lazy to lock it down more than it is) web servers and I try to force Let's Encrypt and SSL on all connections to Apache2. To my knowledge, it uses OpenSSL and does not bring my webserver to a screeching halt to generate random private/public keys every time it needs to (which I imagine happens many times a second, as I am running a forums board that is being attacked by Russia, but I haven't bothered cleaning it up or banning IP's).

grump
Party member
Posts: 612
Joined: Sat Jul 22, 2017 7:43 pm

Re: Lua Randomness Library

Post by grump » Sun Dec 16, 2018 11:27 am

EliterScripts wrote:
Sun Dec 16, 2018 11:06 am
the color changes just seemed to repeat and be super super predictable by-the-eye
You're probably using the same seed every time, or made some other mistake. Show some code?
To my knowledge, it uses OpenSSL and does not bring my webserver to a screeching halt to generate random private/public keys every time it needs to (which I imagine happens many times a second, as I am running a forums board that is being attacked by Russia, but I haven't bothered cleaning it up or banning IP's).
It does not work like that. Crypto generates a relatively small key once per session, and that's it. In a game, you may indeed need thousands of random numbers per second. It's a whole different use case. And you actually want repeatability in a game, almost always. Implementing Minecraft would not be possible with a CSRNG, for instance.

User avatar
zorg
Party member
Posts: 2914
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Lua Randomness Library

Post by zorg » Sun Dec 16, 2018 11:28 am

Again, if you're having issues with löve seemingly having less randomness than you're expecting, you might have an issue in your own code that's causing it. Keep it in mind, you haven't really shown the code itself that exhibits that issue (the background color one, for instance)
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.

User avatar
pgimeno
Party member
Posts: 2176
Joined: Sun Oct 18, 2015 2:58 pm

Re: Lua Randomness Library

Post by pgimeno » Sun Dec 16, 2018 12:16 pm

EliterScripts wrote:
Sun Dec 16, 2018 11:06 am
Yeah, I don't need cryptography. I just figured it would be safe to go with a CSPRNG, because it sounds more random than a regular RNG.
Not really. The subtle correlations that allow the output of a non-cryptographically secure PRNG to be predicted, aren't typically detectable except if you explicitly look for them with maths in hand.
EliterScripts wrote:
Sun Dec 16, 2018 11:06 am
Now, I have booted up LOVE2D a couple of times, I think it was with a thing that I coded as a test project for changing the background color to random colors (it would do a smooth transition--it was very nice to look at, and hypnotizing), but the color changes just seemed to repeat and be super super predictable by-the-eye. I didn't go in and do mathematical voo-doo magic to predict the randomness, it just seemed super predictable, as it seemed to repeat, even after opening up multiple windows and closing and opening it again. Maybe I'm wrong, but that is what I remember.
This suggest that either (1) the code had a flaw, as other have said, or (2) your expectations of randomness are as flawed as everyone else's. arampl posted a relevant article, here's another: https://en.wikipedia.org/wiki/Clustering_illusion

As for datacenters not stalling and all that, they probably have one of these: https://en.wikipedia.org/wiki/Hardware_ ... _generator

The Linux kernel has one, but its throughput is slow. I made a test in which I got just under 600 MB of random numbers during about 5 years.

Post Reply

Who is online

Users browsing this forum: No registered users and 6 guests