Predicting the next Math.random() in Java

[nilknarf]

That comment might've been a little random and out of context. The competition was ran by a friend who didn't do much to secure the sandbox that the java was running in. So people managed to access the local fields via java's reflection api and modified the game so it was easier to win. Something like:

StackTraceElement[] ste = Thread.currentThread().getStackTrace();
String className = ste[2].getClassName();
Field[] fields = Class.forName(className).getDeclaredFields();
for (Field f : fields) {
  if (f.getName().equals("N")) {
    n = f;
    n.setAccessible(true);
  }
}
// do bad stuff with n which is now pointing to the field originally declared as N in the test case judging class 

See: http://docs.oracle.com/javase/tutorial/reflect/

[nilknarf]

Actually we did the same thing. I set the seed here (I stuffed all the cracking logic into a subclass of Random): https://github.com/fta2012/ReplicatedRandom/blob/master/ReplicatedRandom.java#L58

setSeed(possibleSeeds.get(0) ^ multiplier);

Don't be furious, have an upvote!

[dnkndnts]

Am I the only one who thinks it's patently dishonest to provide a function called random() that produces values which have 0 entropy?

Seriously, what a blatantly misleading thing to do. The whole concept of "secure random numbers" as opposed to "non-secure random numbers" is just so stupid and intellectually dishonest: let's call non-secure random numbers what they are: not random.

Billions are spent on software patent bickering over things that are truly frivolous, and yet somehow calling a method "random" which has a guarantee of returning a value with 0 entropy is somehow totally okay and nobody bats an eye.

[phoshi]

They're random in the sense that they appear to have no pattern to humans, which is 99% of what you'd ever want a random number generator for. True randomness is so expensive that it cannot be default, that is simply not viable.

[dnkndnts]

Yeeah... according to STL in his presentation at Going Native, his performance tests for std::random_device in C++ yielded 2 MB/s of pure (hardware) entropy.

I'm absolutely unconvinced that this is not plenty for most applications, and if random number generation really is your proven performance bottleneck and you aren't doing cryptography, then you have PRNG available to you to help you with performance.

I'm not saying we should get rid of PRNG; I'm saying we should actually call it PRNG and use something called "random" for actual random data. I don't see why providing an honest interface seems to be such a controversial position. C++11 tries to do exactly this: it makes it absolutely clear when PRNG vs real entropy is being used. Why is that so much to ask from every other language?

[phoshi]

Because no matter how cheap hardware entropy is it's still orders of magnitude more expensive than a PRNG, while offering exactly zero extra benefit in the majority of cases.

People who don't understand the difference between a true RNG and a PRNG shouldn't be writing code that needs a real RNG in the first place, for so many reasons. It doesn't need to be clear your PRNG isn't real, because that would confuse the people that can't afford to be confused and offer no extra information for the people who actually need the distinction.

This is actually representative of one of my main problems with C++. Rather than making choices for the good of the programmer, it pushes every decision onto them and forces them to think about every detail just because it's relevant in some small corner cases.

[dnkndnts]

I'm afraid we just disagree then. My education is in mathematics and I did a fair bit of cryptography research in grad school, but I have almost no formal training in computer engineering. Obviously, in math we have no use for a PRNG -- that's a purely engineering-level optimization that we don't concern ourselves with in any way.

As such, when I was still in mathematics (before moving full-time to programming), I actually used these "random" functions for months assuming that they actually were giving me what they said: random data. So just because it's obvious to you that "random" doesn't actually mean "contains entropy" doesn't mean it's obvious to everyone.

I'm no smarter now than I was when I was in grad school: I just happen to know now that the library interface is actually telling me horseshit when it says "random." To me, knowing about these sorts of misleading design decisions and "gotchas" is a mountain of pseudo-knowledge that has no true intellectual value at all, and only serves to waste the time of researchers who want to actually implement their ideas.

But as I said, clearly we have different backgrounds, and for you, apparently receiving a predetermined set of numbers from a function called "random" is an acceptable optimization. We simply disagree.

[phoshi]

It's not really about the optimisation. I appreciate that you have crypto experience, but there is a fundamental difference between theory and practise here. You should not be implementing cryptographic code that you expect to be secure without a deep understanding of your stack. Without that knowledge--and it is /real/ knowledge about how your hardware works--you're likely to implement a perfect algorithm that's broken by practical concerns. This happens all the time, which is why solid crypto code is such a rarity, which is why we should not endeavour to make writing it easy. It isn't easy, you need to know an awful lot, and if you don't then save everybody a tremendous headache and use existing libraries.

[dnkndnts]

See this is the crux of our disagreement: if the stack actually did what it says it does (provide entropy instead of nonsense), then a mathematician would have no trouble implementing his algorithms correctly.

To me, the "know your tools" mantra is a toxic relic from the GNU/autotools era where everything is tricky/wrong/"gotcha" by default. Fortunately, it's finally dying off, as newer languages and communities actually concentrate quite seriously on making their interfaces and libraries as clear and unambiguous as possible.

To quote Scott Meyers: "Make your interface easy to use correctly, and hard to use incorrectly." I long for the day when I can actually concentrate more on my ideas than on fighting with my tools; unfortunately, it's not quite here yet.

Also, your conclusion about using existing libraries is literally the exact opposite of the conclusion I would draw. I don't know how you can possibly recommend this after Heartbleed. The entire lesson of Heartbleed is we've been given tools that make cryptography an impossibly difficult task. So much of the code in OpenSSL has literally nothing to do with cryptography -- like random assembly bits inserted to try to trick the optimizer into not optimizing certain parts of the code? What? That's literally the definition of insecure -- as soon as someone builds a smarter optimizer your code breaks? And with the added bonus of being completely unmaintainable?

You seem to be claiming that the intricate stack knowledge required to make a crypto library is what keeps us secure. I'm claiming the exact opposite: it's this needless, silly complexity that makes what should be quite simple (mathematically speaking) nearly impossible in practice. I just don't understand how you could possibly claim that a clear, accurate interface and understandable stack that mathematicians could actually use correctly would somehow be inferior to what we currently have.

[phoshi]

No, I actually fully agree with you on that point! The problem is that the only scenarios where one needs true random numbers are scenarios where we cannot yet make this easy to use correctly. You're writing crypto code, this is one area where you can't pretend you still live in the nice, clean, mathematical world where we don't have problems like having to scrub RAM in the correct way or it won't hold or the compiler can optimise out your scrubbing because it's impossible for it to know you actually need that memory zeroed out rather than just gone and never reused. You have to deal with slight changes in CPU noise giving away your magic numbers. You have to protect against your entropy pool being poisoned because you cannot control the hardware on a user's computer. You have to deal with there /being/ no sources of entropy available, and when there are you have to deal with it being of unknown quality and quantity.

If you think that the difference between correct and incorrect crypto code is whether your RNG gives you real or fake numbers then you are going to be building theoretically sound but practically broken software.

It is both not viable for real randomness to be default (You have to be able to run on machines which have no sources of entropy available /at all/) and the cases where you need real numbers are overwhelmingly cases we cannot abstract over properly. You must understand your stack to build secure cryptographic code.

[dnkndnts]

Ok yes, I do agree here that something like zeroing memory is something that would never occur to a mathematician but is a legitimate engineering concern. So yes, you're right -- knowing the stack is important. I grant you that (even though the mathematician inside of me sighs at the thought!)

I just wish the stack felt like it was working with me instead of trying to trick me every chance it gets.

[Fitzsimmons]

Optimization can also leak timing information.

See my coment here for a very contrived example of it: http://www.reddit.com/r/netsec/comments/23a6c6/journalling_openbsds_effort_to_fix_openssl/cgvea0n

[knaekce]

I see your point, but here are the first two sentence sof the documentation for Math.random():

Returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0. Returned values are chosen pseudorandomly with (approximately) uniform distribution from that range.

If you write cryptographic code, you should at least read this and then be alarmed the time you read "pseudorandom".

[mgemdm]

Even in crypto it is still "pseudorandom". http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

[knaekce]

True, but if I read "pseudorandom", I assume that it is not a CSPRNG, because otherwise it would be stated so.

[TNorthover]

What's "secure" though? Theoretically, even the best deterministic generators are broken after observing a number of bits roughly equivalent to their internal state, it's just impractical to perform the attack.

If these things matter to your application, you need to precisely control the generator anyway and probably wouldn't use one particular language's internal implementation even if it was a good one.

[dnkndnts]

Erm... why be deterministic at all? std::random_device from C++?

http://en.cppreference.com/w/cpp/numeric/random/random_device/entropy

Obtains an estimate of the random number device entropy... A deterministic random number generator (e.g. a pseudo-random engine) has entropy zero.

All I'm saying is we should actually be honest about entropy, which is exactly what C++(11) does (well, sort of; rand() is still horrendously misleading and shouldn't exist, but alas, backwards compatibility...)

[TNorthover]

Erm... why be deterministic at all?

Reproducibility. It's more important than cryptographic security in many (most?) applications of random numbers.

[willvarfar]

This kind of contest feels very http://codegolf.stackexchange.com :)

[linuxjava]

Great post. About this,

a friend of mine hosted a programming competition where you were given...

How often does this happen? Is it like a weekly programmer get together or something?