randomcryptographystateless

Time-dependent, repeatable pseudo-random number


I need to generate a repeatable pseudo-random number that is dependent on the current time and a server secret. For example, this mechanism should generate a new pseudo-random number every minute. The next minute's random number should not be easily predictable.

Furthermore, I need to solve this in a stateless fashion (e.g., without storing a generated value in a database). It is possible that a server node might be asked to create such a number multiple times within the same minute, and it needs to generate the same number each time. Also, multiple server nodes (with the same server secret) need to generate the same number within a given time frame. The purpose of all this is not related to solving a security problem (e.g. a token generator), so it's not strictly necessary to use cryptographically secure PRNGs.

Linear-congruential PRNGs produce repeatable series of numbers when initialized with the same seed, so I could seed the PRNG with the combination of time and server secret and get the first random number it produces to meet my criteria. However, this type of PRNG typically uses a simple formula of next = (current * multiplier + offset) & mask, and, given a few known times and corresponding random numbers, it seems like it would be not all that hard to figure out the server secret (and then predict all future numbers in advance).

To make this sort of reverse engineering harder, I pull and discard a fixed number (e.g., 1000) of values from the freshly seeded PRNG before I get the "real" random number that I use. My thinking is that reverse-engineering 1000 cycles of next = (current * multiplier + offset) & mask would be significantly more difficult that reverse-engineering just a single cycle.

I am wondering if my thinking here is even correct. Is it true that figuring out a linear-congruential PRNG's seed is more difficult based on the 1000th value after seeding than it is for the first value of a freshly seeded generator? If so, how many iterations are sufficient before it stops increasing the difficulty?

If I'm completely off here, what are some better alternatives that fulfill the above stated criteria (repeatability, statelessness)?


Solution

  • In a way, this is how Time-based one-time passwords (TOTPs) work, so you can use a similar solution.

    To get a time value that changes every N seconds, you can use the following formula.

    floor(timestamp / N)

    Then, you can either turn that into a string or interpret it as bytes. Just pass it to something like HMAC in order to turn it into a pseudo-random value.

    HMAC(SecretKey, floor(timestamp / N))

    Here's a simple implementation in Python. This should be fairly similar in other languages too.

    import hmac
    import time
    
    # Duration that each value lasts, in seconds
    duration = 60
    
    # Generate randomly instead of using a phrase
    secret_key = b"very epic secret key"
    
    timestamp = int(time.time())
    timestamp = int(timestamp / duration)
    timestamp = timestamp.to_bytes(8, "big")
    
    value = hmac.digest(secret_key, timestamp, "sha256")
    print(value.hex())
    

    You can also turn the value into an integer, or use it in other ways.

    value_int = int.from_bytes(value, "big")