6 ms·

I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. How does this differ cryptographically fr

by maxloh 2y ago

I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? Does it really matter which random number generator you use on a webpage? It's already considered an insecure environment anyway (that's why we have server-side validation).

tomsmeding 2y ago
In a class we had to reverse-engineer an application that had encrypted some text file — we had to decrypt it without the key. Turned out the application just used the current unix timestamp as the key. A brute-force search of the past few months didn't take very long. If you include nanoseconds in your key then you have more entropy, of course, but timestamps are guessable, so it's risky.
- sverhagen 2y ago
  Those nanoseconds aren't really entropy then, are they?
  - lmm 2y ago
    They're entropy for most practical purposes. But there's only 1000 possibilities, so that's less than 10 bits' worth.
    - boothby 2y ago
      Especially if you're writing a file, the creation time is a big hint! Even nanoseconds won't help if you're leaking that many bits from your seed.
    - tomsmeding 2y ago
      That's milliseconds; nanoseconds are 1e-9 seconds. Still, the file creation time remark of sibling is pertinent.
      - lmm 2y ago
        I was thinking of the step from milli to nano, so yeah 1e6 not 1e3, 20 bits not 10. But the point stands.
hapidjus 2y ago
One attack might be exploiting One Time Passwords. Lets say you send yourself enough tokens to calculate the state, you will then be able to calculate the next token and login as another user. However that should be easily fixed by adding some salt relating to the user, meaning you would only be able to figure out _your_ next token.
atoav 2y ago
You can go back into a time before computers and use the most famous examples of how bad RNGs endanger crypto: One Time Pads (OTP). This is basically just a XOR of your message with your random numbers. If your random numbers are bad they leave patterns in the XOR-ed message that can be statistically analyzed and potentially decrypted. Bad PRNGs repeat early and have predictable patterns, as such they form a special attack vector. Whether that is really an issue for any given application, depends on the application (e.g. how shortlived the crypto is and how bad decryption acter the fact is). But if you are asking that question it likely means you don't know enough knowledge to roll your own crypto unless you wanna be in a world of pain. Just because PRNGs appear unpredictable to you does not mean they aren't. If you really wanna go the route, at least add a salt, so something like Hash(application_secret_long_and_random + timestamp_nanosecond_precision)
masklinn 2y ago
> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? That question doesn’t make any sense. The current timestamp would be a seed to initialise the PRNG, which can be MWC or xorshift. > Does it really matter which random number generator you use on a webpage? That is application dependent. If you’re coding a roulette wheel no, if you’re coding an E2E chat yes. > It's already considered an insecure environment anyway (that's why we have server-side validation). That is also application dependent. The client is considered insecure from the server pov because it is entirely under user control, so the user can mess with anything. But if it is acting entirely on behalf of the user then that can be the point and by design. In the example above, you don’t care that a user fucks up their own crypto, but you do care that the crypto holds for the average user. Even the qualitative difference between two non-CS PRNG can make or break a project due to too small a state space or short a cycle.
- sverhagen 2y ago
  I don't really disagree with anything you said, but I think the roulette wheel and the E2E chat are funny examples, you could have a high value roulette game and a casual chat about the weather, where the stakes are opposite to your point ;-)
  - cratermoon 2y ago
    I was thinking this myself. When significant amounts of real money are sitting on the spin of the wheel and bouncing of the ball, a bad PRNG like the one discussed in the article would be disastrous.
    - masklinn 2y ago
      Yeah I was thinking less casino thingie and more https://pickerwheel.com https://pickerwheel.com, I guess I used the wrong term for it.
- tetha 2y ago
rkangel 2y ago
They're call PRNG because they are pseudo random. If you know the starting state, you know what sequence they're going to generate. Putting it another way, if you always start them in the same state, they'll always produce the same sequence. So a PRNG needs "seeding". You need some value to put in at the start that is different every time. Using the time on the computer results in a different seed on each run, and so a different number sequence each time. If you need random numbers for cryptography (very good quality random numbers are important for lots of crypto processes) then you need to do more - they need to be completely unpredictable. If you just used the time, someone could seed a copy of the RNG with the same time, and predict the randomness sequence. So what we want is a seed that comes from actual randomness (also called "entropy"). That entropy has to come from somewhere - ideally some hardware source using some statistically random physical effect.
- simonmales 2y ago
  Well written, h/t.
- magicalhippo 2y ago
  > Putting it another way, if you always start them in the same state, they'll always produce the same sequence. This can be easy to bump into in fairly trivial cases. For example, initializing by time alone can be problematic if you spawn N threads at once which all do their own seeding. Then they can all reach the seeding process at the same time, relative to the clock used for the seeding. I had that problem with one of my earlier ray tracers, and so had to add add the thread id into the mix to seed the PRNGs.
  - markh1967 2y ago
    A demonstration of exactly this problem (only in older versions of .Net, newer versions use a different seeding method) https://dotnetfiddle.net/tLGMp6 https://dotnetfiddle.net/tLGMp6
  - mturmon 2y ago
    Agreed. I do a lot of Monte Carlo simulations of physical systems (radars, scientific models) in which same or close seeds will cause trouble. You do want a deterministic PRNG (for repeatability of the simulation). But if you seed with time alone, and spawn 100 parallel jobs, you will see repeats or near-repeats which will bias the Monte Carlo averages resulting from your simulation ensemble. In ancient times, you could xor in the PID and the IP address of the host to ensure no seed overlap. Nowadays there are other ways to introduce entropy to the seed, e.g. with dedicated system calls or /dev/random.
spacechild1 2y ago
> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. People typically seed a PRNG with the current time. The actual output sequence is still created with a determinstic algorithm. These two things are really orthogonal.
Retr0id 2y ago
xorshift128+ has exactly 128 bits of internal state. After collecting a small number of outputs, it is trivial to determine the internal state by constructing and then solving an equation (where the variables are GF(2) elements), regardless of how the "seed" was initialized. Once you have the internal state, you can predict all future outputs with 100% certainty. This only becomes a problem when people assume this isn't possible (for example, using it to pick lottery numbers) - this is more likely to happen on the server-side than the client-side (and v8 runs on both), but it can be security-relevant in client-only apps too (consider an insecure "password generator" app). https://en.wikipedia.org/wiki/GF(2) https://en.wikipedia.org/wiki/GF(2)
- Retr0id 2y ago
  By the way, the "password generator app" is not a contrived hypothetical, it was actually one of my first ever bug-bounty payouts.
markh1967 2y ago
It's been a while so I can't provide a link but I remember reading about someone who got hold of a video blackjack machine that used a pseudo random number generator and was able to find the seed from only a few hands and then knew exactly which cards would be dealt next. He then went on to empty every machine he could find in the local casinos.
lmm 2y ago
> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? In the early days of online poker some people made a killing by figuring out all the possible hands from the PRNGs being used and then they could just start a game and look up the hands they'd been dealt in their database.
deleted 2y ago
[deleted]

by maxloh 2y ago

tomsmeding 2y ago

In a class we had to reverse-engineer an application that had encrypted some text file — we had to decrypt it without the key. Turned out the application just used the current unix timestamp as the key. A brute-force search of the past few months didn't take very long. If you include nanoseconds in your key then you have more entropy, of course, but timestamps are guessable, so it's risky.

sverhagen 2y ago
Those nanoseconds aren't really entropy then, are they?
- lmm 2y ago
  They're entropy for most practical purposes. But there's only 1000 possibilities, so that's less than 10 bits' worth.
  - boothby 2y ago
    Especially if you're writing a file, the creation time is a big hint! Even nanoseconds won't help if you're leaking that many bits from your seed.
  - tomsmeding 2y ago
    That's milliseconds; nanoseconds are 1e-9 seconds. Still, the file creation time remark of sibling is pertinent.
    - lmm 2y ago
      I was thinking of the step from milli to nano, so yeah 1e6 not 1e3, 20 bits not 10. But the point stands.

hapidjus 2y ago

One attack might be exploiting One Time Passwords. Lets say you send yourself enough tokens to calculate the state, you will then be able to calculate the next token and login as another user. However that should be easily fixed by adding some salt relating to the user, meaning you would only be able to figure out _your_ next token.

atoav 2y ago

You can go back into a time before computers and use the most famous examples of how bad RNGs endanger crypto: One Time Pads (OTP). This is basically just a XOR of your message with your random numbers. If your random numbers are bad they leave patterns in the XOR-ed message that can be statistically analyzed and potentially decrypted. Bad PRNGs repeat early and have predictable patterns, as such they form a special attack vector. Whether that is really an issue for any given application, depends on the application (e.g. how shortlived the crypto is and how bad decryption acter the fact is). But if you are asking that question it likely means you don't know enough knowledge to roll your own crypto unless you wanna be in a world of pain. Just because PRNGs appear unpredictable to you does not mean they aren't. If you really wanna go the route, at least add a salt, so something like Hash(application_secret_long_and_random + timestamp_nanosecond_precision)

masklinn 2y ago

> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? That question doesn’t make any sense. The current timestamp would be a seed to initialise the PRNG, which can be MWC or xorshift. > Does it really matter which random number generator you use on a webpage? That is application dependent. If you’re coding a roulette wheel no, if you’re coding an E2E chat yes. > It's already considered an insecure environment anyway (that's why we have server-side validation). That is also application dependent. The client is considered insecure from the server pov because it is entirely under user control, so the user can mess with anything. But if it is acting entirely on behalf of the user then that can be the point and by design. In the example above, you don’t care that a user fucks up their own crypto, but you do care that the crypto holds for the average user. Even the qualitative difference between two non-CS PRNG can make or break a project due to too small a state space or short a cycle.

sverhagen 2y ago
I don't really disagree with anything you said, but I think the roulette wheel and the E2E chat are funny examples, you could have a high value roulette game and a casual chat about the weather, where the stakes are opposite to your point ;-)
- cratermoon 2y ago
  I was thinking this myself. When significant amounts of real money are sitting on the spin of the wheel and bouncing of the ball, a bad PRNG like the one discussed in the article would be disastrous.
  - masklinn 2y ago
    Yeah I was thinking less casino thingie and more https://pickerwheel.com https://pickerwheel.com, I guess I used the wrong term for it.
tetha 2y ago

rkangel 2y ago

They're call PRNG because they are pseudo random. If you know the starting state, you know what sequence they're going to generate. Putting it another way, if you always start them in the same state, they'll always produce the same sequence. So a PRNG needs "seeding". You need some value to put in at the start that is different every time. Using the time on the computer results in a different seed on each run, and so a different number sequence each time. If you need random numbers for cryptography (very good quality random numbers are important for lots of crypto processes) then you need to do more - they need to be completely unpredictable. If you just used the time, someone could seed a copy of the RNG with the same time, and predict the randomness sequence. So what we want is a seed that comes from actual randomness (also called "entropy"). That entropy has to come from somewhere - ideally some hardware source using some statistically random physical effect.

simonmales 2y ago
Well written, h/t.
magicalhippo 2y ago
> Putting it another way, if you always start them in the same state, they'll always produce the same sequence. This can be easy to bump into in fairly trivial cases. For example, initializing by time alone can be problematic if you spawn N threads at once which all do their own seeding. Then they can all reach the seeding process at the same time, relative to the clock used for the seeding. I had that problem with one of my earlier ray tracers, and so had to add add the thread id into the mix to seed the PRNGs.
- markh1967 2y ago
  A demonstration of exactly this problem (only in older versions of .Net, newer versions use a different seeding method) https://dotnetfiddle.net/tLGMp6 https://dotnetfiddle.net/tLGMp6
- mturmon 2y ago
  Agreed. I do a lot of Monte Carlo simulations of physical systems (radars, scientific models) in which same or close seeds will cause trouble. You do want a deterministic PRNG (for repeatability of the simulation). But if you seed with time alone, and spawn 100 parallel jobs, you will see repeats or near-repeats which will bias the Monte Carlo averages resulting from your simulation ensemble. In ancient times, you could xor in the PID and the IP address of the host to ensure no seed overlap. Nowadays there are other ways to introduce entropy to the seed, e.g. with dedicated system calls or /dev/random.

spacechild1 2y ago

> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. People typically seed a PRNG with the current time. The actual output sequence is still created with a determinstic algorithm. These two things are really orthogonal.

Retr0id 2y ago

xorshift128+ has exactly 128 bits of internal state. After collecting a small number of outputs, it is trivial to determine the internal state by constructing and then solving an equation (where the variables are GF(2) elements), regardless of how the "seed" was initialized. Once you have the internal state, you can predict all future outputs with 100% certainty. This only becomes a problem when people assume this isn't possible (for example, using it to pick lottery numbers) - this is more likely to happen on the server-side than the client-side (and v8 runs on both), but it can be security-relevant in client-only apps too (consider an insecure "password generator" app). https://en.wikipedia.org/wiki/GF(2) https://en.wikipedia.org/wiki/GF(2)

Retr0id 2y ago
By the way, the "password generator app" is not a contrived hypothetical, it was actually one of my first ever bug-bounty payouts.

markh1967 2y ago

It's been a while so I can't provide a link but I remember reading about someone who got hold of a video blackjack machine that used a pseudo random number generator and was able to find the seed from only a few hands and then knew exactly which cards would be dealt next. He then went on to empty every machine he could find in the local casinos.

lmm 2y ago

> I learned in college that most random number generators use the current timestamp to generate a pseudo-random number. > How does this differ cryptographically from algorithms like MWC1616 and xorshift128+ in backend applications? How can a random number generator be vulnerable to attacks in real life? In the early days of online poker some people made a killing by figuring out all the possible hands from the PRNGs being used and then they could just start a game and look up the hands they'd been dealt in their database.

deleted 2y ago

[deleted]