8 ms·

Predicting the next Math.random() in Java

150 points by nilknarf 12y ago

mnw21cam 12y ago
That is a nice not-so-subtle reminder. When a PRNG says it is insecure, it is insecure. When a PRNG says it is secure, it might be - get someone very clever to check it first.
drinchev 12y ago
How dangerous this prediction can be? I can't stop thinking of java-backended real money, poorly written, gaming websites.
- mabbo 12y ago
  It's well known. If someone is doing anything with real money, and isn't doing something more secure than this, they've already been hacked, are already out of business, and are already not allowed to write code that deals with real money.
  - dj-wonk 12y ago
    This is a convenient but flawed argument that assumes an equilibrium. Hacking is often (mostly?) about vulnerabilities that change over time.
- Hernanpm 12y ago
  Real random numbers are useless because everything follow some distribution. Actually random generators in programming languages should be called pseudorandom to avoid confusions.
  - UnoriginalGuy 12y ago
    By that logic nothing should ever be called random (in any context). There are things we can measure but don't understand the source of the entropy, but they aren't random we just haven't figured out the source yet. Most things we consider random are quantifiable and predictable with enough data (be it nature or computers). Plus there are several definitions of the term "random" (English) which are in-line with the programming usage such as "random: a haphazard course."
    - MichaelGG 12y ago
      I thought quantum processes were truly random.
      - TheLoneWolfling 12y ago
        As far as we know. That isn't the same thing as "it is". If you assume that quantum processes are truly random, there are a bunch of ways for a computer to generate truly random noise - the easiest class being shot noise (connect a computer to a good camera in an almost pitch-black enclosure, or send a small current through a diode), but there are others.
  - lutusp 12y ago
    > Real random numbers are useless because everything follow some distribution. First, real random numbers are quite valuable. Second, yes, all numerical sequences follow a distribution, but one of those distributions is called the "normal distribution", and I think you may be able to guess what that refers to. > Actually random generators in programming languages should be called pseudorandom to avoid confusions. It would have been useful to explain the difference between the terms random and pseudorandom. "Pseudorandom" doesn't necessarily mean easily predictable or flawed, it means the sequence results from a deterministic algorithm and can be recreated exactly by restarting the generator with the same seed value.
    - eru 12y ago
      Why is the normal distribution important here? (In programming, people often start from the uniform distribution, don't they?)
      - lutusp 12y ago
        > Why is the normal distribution important here? There may be a terminological confusion at work here. A normal or uniform number shows no internal pattern: http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number Quote: "In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b^2 pairs of digits are equally likely with density b^−2, all b^3 triplets of digits equally likely with density b^−3, etc." There are also pseudorandom generators whose purpose it is to generate results that agree with a normal or Gaussian distribution, for particular purposes. http://www.design.caltech.edu/erik/Misc/Gaussian.html http://www.design.caltech.edu/erik/Misc/Gaussian.html Quote: "This note is about the topic of generating Gaussian pseudo-random numbers given a source of uniform pseudo-random numbers." The problem here is that a normal number shows a uniform distribution of its digits among the possible values, and the term normal distribution is sometimes used to describe this outcome. > In programming, people often start from the uniform distribution, don't they? Yes, and as set out above, this starting point may be described in a confusing way.
- UnoriginalGuy 12y ago
  Those likely won't be vulnerable even if they implemented their site using the insecure random function. The reason why this works is that you're the only consumer of Java-randomness, as you add additional consumers it becomes infinitely more difficult. Consumers also don't need to be users, AI players and cards dealt will also consume randomness. You would also need to know the mapping from the random output into the game (e.g. in card games are there multiple decks each assigned 1 value of entropy? 2 decks, 3 decks, etc? Plus any mappings or conversions will make this impossible (as you wouldn't know the real output of the random number generator)). Ultimately it will likely work pretty reliably locally, but as soon as you stick it on a web service then all bets are off.
  - banthar 12y ago
    This more probable than you think. Java code is likely to use Collections.shuffle(). That method uses internal Random which is used only for shuffling. Shuffling is unlikely to be used for other purposes than shuffling cards. There isn't that many ways to shuffle them either.
    - xxs 12y ago
      shuffle does allow specifying a j.u.Random as second parameter. If you don't use SecureRandom when you have to, it's your own fall.
    - ivanche 12y ago
      I worked for 6 years in a company which makes online (gambling) games. I can tell you that anyone who even thinks of using Collections.shuffle() for shuffling cards in production code is an amateur.
  - cynicalkane 12y ago
    In the event tptacek doesn't show up to explain how awfully wrong this is, I'll do my best to fill in. An attacker who can predict your PRNG and guess a seeded value knows a potentially infinite number of future random numbers. Now all he needs to do is guess what random numbers, from a very small pool of possible numbers, will show up at what time. Devs often code assuming that PRNG numbers aren't predictable at all, so compromising your RNG is like setting your password to "hunter2" in a situation where nobody thinks about limiting the number of guesses. Such attacks were famously used to steal a lot of money on PlanetPoker, one of the first poker websites. RNG attacks are also deadly in encryption, where it's reasonable for an attacker to be able to make millions of guesses from his laptop computer.
- jonahx 12y ago
  This has happened in the past. Interesting read: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...
  - MrBuddyCasino 12y ago
    If one were to use such tactics to make money - would that be considered "hacking" and be illegal?
- UrMomReadsHN 12y ago
  It has happened before! See http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph... for a very detailed explanation of how one figured out all the cards in Texas hold-em.
Peksa 12y ago
Hah, funny! I recently did the same to circumvent CSRF-protection based on java.util.Random. Here's my solver in JS: https://peks.as/experiments/random/ https://peks.as/experiments/random/
mda 12y ago
Reminded me an interesting Java Random issue with small seeds and power of two intervals: for(int i = 0; i < 256; i++) { System.out.println(new Random(i).nextInt(8)); } It returns same number for all seeds.
imaginenore 12y ago
If you want cryptographic-quality random numbers, both Java and Javascript have them. Math.random() is simply a super-fast decent RNG. Example: var buf = new Uint32Array(10); window.crypto.getRandomValues(buf); console.log(buf); Outputs things like: [4027145128, 258543382, 1205615760, 2665675208, 4033127244, 2280027866, 3983484449, 510932333, 1911490534, 2609399642] This works in Chrome and FF. IE11 has Crypto.getRandomValues(...) Java has SecureRandom: http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html http://docs.oracle.com/javase/6/docs/api/java/security/Secur...
- Osmium 12y ago
  Devil's advocate, but why not rename "Random" to "AlmostRandom" instead, and call "SecureRandom" just "Random"? It's not unreasonable for a lay programmer to expect "random" to be exactly that; though, obviously, non-experts shouldn't be implementing crypto regardless. But since they will, despite everyone's best advice otherwise, why not reduce their chances of introducing bugs?
  - sgift 12y ago
    How far do you want to go? The Javadocs state it plain and clear that this is not cryptographically secure. Is AlmostRandom enough? Maybe we should force people to set an enum? new AlmostRandom(AlmostRandomCertification.YES_I_M_NOT_AN_IDIOT_AND_WONT_USE_THIS_FOR_CRYPTOGRAPHIC_PURPOSES)? You have to draw the line somewhere.
    - jonahx 12y ago
      True, although honestly your tongue-in-cheek enum example is probably closer to where the line should be.
      - cornewut 12y ago
        Also a nice reminder: "Never write your own crypto"
phpnode 12y ago
nitpick, Firefox doesn't use Rhino, it uses SpiderMonkey which is C++. https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey https://developer.mozilla.org/en-US/docs/Mozilla/Projects/Sp...
jlebar 12y ago
As another commenter has said, Firefox doesn't use Rhino. Here's the relevant code in Firefox's JS engine. http://dxr.mozilla.org/mozilla-central/source/js/src/jsmath.cpp#765 http://dxr.mozilla.org/mozilla-central/source/js/src/jsmath....
lunixbochs 12y ago
I tested a similar attack against ApacheCommons' RandomStringUtil. Given a few bytes of output, I could recover the RNG state in 20 minutes on CPU.
xxs 12y ago
Math.random() should be used only for tests. That's it. Performance sucks as it's shared. ThreadLocalRandom is a lot better if you need fast but not-quality random. And there is SecureRandom for security concerns. Last fun fact Math.random() and a Monte Carlo test introduced "CAS in Java" and all that followed with JSR 166.

150 points by nilknarf 12y ago

That is a nice not-so-subtle reminder. When a PRNG says it is insecure, it is insecure. When a PRNG says it is secure, it might be - get someone very clever to check it first.

drinchev 12y ago

How dangerous this prediction can be? I can't stop thinking of java-backended real money, poorly written, gaming websites.

mabbo 12y ago
It's well known. If someone is doing anything with real money, and isn't doing something more secure than this, they've already been hacked, are already out of business, and are already not allowed to write code that deals with real money.
- dj-wonk 12y ago
  This is a convenient but flawed argument that assumes an equilibrium. Hacking is often (mostly?) about vulnerabilities that change over time.
Hernanpm 12y ago
Real random numbers are useless because everything follow some distribution. Actually random generators in programming languages should be called pseudorandom to avoid confusions.
- UnoriginalGuy 12y ago
  By that logic nothing should ever be called random (in any context). There are things we can measure but don't understand the source of the entropy, but they aren't random we just haven't figured out the source yet. Most things we consider random are quantifiable and predictable with enough data (be it nature or computers). Plus there are several definitions of the term "random" (English) which are in-line with the programming usage such as "random: a haphazard course."
  - MichaelGG 12y ago
    I thought quantum processes were truly random.
    - TheLoneWolfling 12y ago
      As far as we know. That isn't the same thing as "it is". If you assume that quantum processes are truly random, there are a bunch of ways for a computer to generate truly random noise - the easiest class being shot noise (connect a computer to a good camera in an almost pitch-black enclosure, or send a small current through a diode), but there are others.
- lutusp 12y ago
  > Real random numbers are useless because everything follow some distribution. First, real random numbers are quite valuable. Second, yes, all numerical sequences follow a distribution, but one of those distributions is called the "normal distribution", and I think you may be able to guess what that refers to. > Actually random generators in programming languages should be called pseudorandom to avoid confusions. It would have been useful to explain the difference between the terms random and pseudorandom. "Pseudorandom" doesn't necessarily mean easily predictable or flawed, it means the sequence results from a deterministic algorithm and can be recreated exactly by restarting the generator with the same seed value.
  - eru 12y ago
    Why is the normal distribution important here? (In programming, people often start from the uniform distribution, don't they?)
    - lutusp 12y ago
      > Why is the normal distribution important here? There may be a terminological confusion at work here. A normal or uniform number shows no internal pattern: http://en.wikipedia.org/wiki/Normal_number http://en.wikipedia.org/wiki/Normal_number Quote: "In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b^2 pairs of digits are equally likely with density b^−2, all b^3 triplets of digits equally likely with density b^−3, etc." There are also pseudorandom generators whose purpose it is to generate results that agree with a normal or Gaussian distribution, for particular purposes. http://www.design.caltech.edu/erik/Misc/Gaussian.html http://www.design.caltech.edu/erik/Misc/Gaussian.html Quote: "This note is about the topic of generating Gaussian pseudo-random numbers given a source of uniform pseudo-random numbers." The problem here is that a normal number shows a uniform distribution of its digits among the possible values, and the term normal distribution is sometimes used to describe this outcome. > In programming, people often start from the uniform distribution, don't they? Yes, and as set out above, this starting point may be described in a confusing way.
UnoriginalGuy 12y ago
Those likely won't be vulnerable even if they implemented their site using the insecure random function. The reason why this works is that you're the only consumer of Java-randomness, as you add additional consumers it becomes infinitely more difficult. Consumers also don't need to be users, AI players and cards dealt will also consume randomness. You would also need to know the mapping from the random output into the game (e.g. in card games are there multiple decks each assigned 1 value of entropy? 2 decks, 3 decks, etc? Plus any mappings or conversions will make this impossible (as you wouldn't know the real output of the random number generator)). Ultimately it will likely work pretty reliably locally, but as soon as you stick it on a web service then all bets are off.
- banthar 12y ago
  This more probable than you think. Java code is likely to use Collections.shuffle(). That method uses internal Random which is used only for shuffling. Shuffling is unlikely to be used for other purposes than shuffling cards. There isn't that many ways to shuffle them either.
  - xxs 12y ago
    shuffle does allow specifying a j.u.Random as second parameter. If you don't use SecureRandom when you have to, it's your own fall.
  - ivanche 12y ago
    I worked for 6 years in a company which makes online (gambling) games. I can tell you that anyone who even thinks of using Collections.shuffle() for shuffling cards in production code is an amateur.
- cynicalkane 12y ago
  In the event tptacek doesn't show up to explain how awfully wrong this is, I'll do my best to fill in. An attacker who can predict your PRNG and guess a seeded value knows a potentially infinite number of future random numbers. Now all he needs to do is guess what random numbers, from a very small pool of possible numbers, will show up at what time. Devs often code assuming that PRNG numbers aren't predictable at all, so compromising your RNG is like setting your password to "hunter2" in a situation where nobody thinks about limiting the number of guesses. Such attacks were famously used to steal a lot of money on PlanetPoker, one of the first poker websites. RNG attacks are also deadly in encryption, where it's reasonable for an attacker to be able to make millions of guesses from his laptop computer.
jonahx 12y ago
This has happened in the past. Interesting read: http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph...
- MrBuddyCasino 12y ago
  If one were to use such tactics to make money - would that be considered "hacking" and be illegal?
UrMomReadsHN 12y ago
It has happened before! See http://www.cigital.com/papers/download/developer_gambling.php http://www.cigital.com/papers/download/developer_gambling.ph... for a very detailed explanation of how one figured out all the cards in Texas hold-em.

Peksa 12y ago

Hah, funny! I recently did the same to circumvent CSRF-protection based on java.util.Random. Here's my solver in JS: https://peks.as/experiments/random/ https://peks.as/experiments/random/

mda 12y ago

Reminded me an interesting Java Random issue with small seeds and power of two intervals: for(int i = 0; i < 256; i++) { System.out.println(new Random(i).nextInt(8)); } It returns same number for all seeds.

imaginenore 12y ago

If you want cryptographic-quality random numbers, both Java and Javascript have them. Math.random() is simply a super-fast decent RNG. Example: var buf = new Uint32Array(10); window.crypto.getRandomValues(buf); console.log(buf); Outputs things like: [4027145128, 258543382, 1205615760, 2665675208, 4033127244, 2280027866, 3983484449, 510932333, 1911490534, 2609399642] This works in Chrome and FF. IE11 has Crypto.getRandomValues(...) Java has SecureRandom: http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html http://docs.oracle.com/javase/6/docs/api/java/security/Secur...

Osmium 12y ago
Devil's advocate, but why not rename "Random" to "AlmostRandom" instead, and call "SecureRandom" just "Random"? It's not unreasonable for a lay programmer to expect "random" to be exactly that; though, obviously, non-experts shouldn't be implementing crypto regardless. But since they will, despite everyone's best advice otherwise, why not reduce their chances of introducing bugs?
- sgift 12y ago
  How far do you want to go? The Javadocs state it plain and clear that this is not cryptographically secure. Is AlmostRandom enough? Maybe we should force people to set an enum? new AlmostRandom(AlmostRandomCertification.YES_I_M_NOT_AN_IDIOT_AND_WONT_USE_THIS_FOR_CRYPTOGRAPHIC_PURPOSES)? You have to draw the line somewhere.
  - jonahx 12y ago
    True, although honestly your tongue-in-cheek enum example is probably closer to where the line should be.
    - cornewut 12y ago
      Also a nice reminder: "Never write your own crypto"

phpnode 12y ago

nitpick, Firefox doesn't use Rhino, it uses SpiderMonkey which is C++. https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey https://developer.mozilla.org/en-US/docs/Mozilla/Projects/Sp...

jlebar 12y ago

As another commenter has said, Firefox doesn't use Rhino. Here's the relevant code in Firefox's JS engine. http://dxr.mozilla.org/mozilla-central/source/js/src/jsmath.cpp#765 http://dxr.mozilla.org/mozilla-central/source/js/src/jsmath....

lunixbochs 12y ago

I tested a similar attack against ApacheCommons' RandomStringUtil. Given a few bytes of output, I could recover the RNG state in 20 minutes on CPU.

xxs 12y ago

Math.random() should be used only for tests. That's it. Performance sucks as it's shared. ThreadLocalRandom is a lot better if you need fast but not-quality random. And there is SecureRandom for security concerns. Last fun fact Math.random() and a Monte Carlo test introduced "CAS in Java" and all that followed with JSR 166.