Can this code be reverse-engineered to find the random seed?

Question

local digits = {'1', '2', '3', '4', '5', '6', '8', '9'} 
math.randomseed(os.time()) 
local result = digits[math.random(8)] 
for i = 2, 50 do 
    result = result..digits[math.random(8)] 
end 
print(result)

--> 88854243421464255299891111895292628431988589634664

This is a Lua script designed to spit out fifty random digits, excluding 0 and 7. I can't seem to find the Lua randomness algorithm. Is it possible to find the value returned by os.time()?

To put it in layman's terms, here's how the script works:

1. Define a list of eight single-character strings.
2. Seed the pseudo-random algorithm with the number of seconds since midnight on January 1, 1970.
3. Select a number between one and eight using the pseudo-random algorithm, then use that to select an item from the list. E.g. the number selected is seven, the algorithm picks the seventh item in the list.
4. Add that item onto the end of the result. Repeat until the result is fifty digits long.

So because seven is left out, the random algorithm really spit this out:

77754243421464255288781111785282627431877578634664

But because seven is missing, seven and eight became eight and nine, yielding this:

88854243421464255299891111895292628431988589634664

To clarify, I'm trying to figure out how the random algorithm works to find the key that was entered as a random seed.

Also asked here: https://forum.roblox.com/Forum/ShowPost.aspx?PostID=215349554 and here: https://scriptinghelpers.org/questions/42360/can-this-script-be-reverse-engineered-to-find-the-random-seed and here: https://crypto.stackexchange.com/questions/47027/can-this-code-be-reverse-engineered-to-find-the-random-seed

Answer 1

Can this code be reverse-engineered to find the random seed?

Maybe, maybe not. It depends on the implementation of math.random.

Is it possible to find the value returned by os.time()?

Of course. os.time() is defined as (emphasis mine)

The time function, when called without arguments, returns the current date and time, coded as a number. (In most systems, that number is the number of seconds since some epoch.)

We're talking about a 32 bit integer. This can be easily brute-forced. You can even assume some bounds. This was probably generated in the last month or so and there is no need to search for the seed which is in the future. There are only 22 bit of different seconds in the last 30 days.

You can simply iterate through the seeds from now to the past and generate the 50 digit long random value each time. Then you only need to compare it with the one you have and stop when you found the match. This shouldn't take longer than a minute.

Here's the full code for that:

function GetDigits(t)
    local digits = {'1', '2', '3', '4', '5', '6', '8', '9'}
    math.randomseed(t)
    local result = digits[math.random(8)]
    for i = 2, 50 do
        result = result..digits[math.random(8)]
    end
    return result
end

ct = os.time()
while ct > 1 do
    if ct % 100000 == 0 then
        print (ct)
    end
    if GetDigits(ct) == "88854243421464255299891111895292628431988589634664" then
        print ("found: " .. ct)
        break
    end
    ct = ct - 1
end

Output

1493400000
1493300000
1493200000
1493100000
1493000000
1492900000
1492800000
1492700000
1492600000
1492500000
1492400000
1492300000
1492200000
1492100000
1492000000
1491900000
1491800000
1491700000
1491600000
1491500000
found: 1491404649

This only works up to Lua v5.1, because the implementation changed in v5.2 and v5.3. I've tried it only on windows.

Answer 2

This isn't a full answer to your question, but it might help you to get started. You can find the C source for Lua's math.random function here (that's for Lua 5.1, but other versions are similar). Lua doesn't attempt to generate pseudo-random numbers itself, but instead outsources that task to the C standard library.

Specifically, math.random generates numbers using C's rand function, and math.randomseed sets the seed for the pseudo-random-number generator using C's srand function (covered in the same man page as rand). These functions are implemented differently on every system (e.g. the x86 Windows version is different from the x86 Linux version, there will be different versions for different chipsets, etc.), so you would have to analyse the algorithm for each of the systems you are interested in.

For information about how rand is implemented, this question should give you a start.

One thing you should definitely be careful of is that if someone can guess on what second you called os.time (or if they just called it at the same time as you), then they would be able to generate the exact same psuedo-random numbers as you by passing that value to math.randomseed. It would be better to use a seed with a higher entropy if you have one available.