Java Puzzle: Square Root • Hacker News Board

Re: Java Puzzle: Square Root

#51

Post by IvyMike » Wed, Mar 20, 2013, 4:33 AM UTC

lancefisher wrote: post #48

IvyMike wrote: post #27

I'm surprised nobody's given the obvious algorithm yet: while(i Before anyone complains, this algorithm is correct and does not break any of the rules as far as I can tell. :) I think the timing attack is probably what he's really looking for. Edit: as mattvanhorn pointed out, answer() is void, but that's ok... changed to a "constant time" algorithm. :)

The BigInteger is really big. An i7 does about 109 gigaFLOPS, or 109 operations per nanosecond. [1] Suppose we can do 1 guess per operation. There are 2^10,000 possible roots. [2] 2^10,000 / 109 nanoseconds is 5.804×10^2991 years. [3] The stars will burn out before you brute force it. [1] http://en.wikipedia.org/wiki/FLOPS [2] http://bit.ly/ZIWkkt (parens in the original link) [3] http://www.wolframalpha.com/input/?i…

As an optimist, I must point out that if Moore's law holds for the next 10000 doublings we'll have the answer in 20000 years, plus 9 picoseconds.

Re: Java Puzzle: Square Root

#52

Post by itsdrewmiller » Wed, Mar 20, 2013, 4:53 AM UTC

Not really a Java guy, but could you subclass BigInteger in such a way that when .divide is called and accesses root's representation of the data, that property access reflectively examines the calling expression to find out n's representation of the data, then just square roots that and sets it as its own representation before allowing the expression to evaluate? Or something along those lines, anyway?

Re: Java Puzzle: Square Root

#53

Post by cromwellian » Wed, Mar 20, 2013, 6:06 AM UTC

spiralpolitik wrote: post #47

mattvanhorn wrote: post #37

Earlier quoted context omitted.

...and that you can remove all the existing ones and insert your own.

You can't change Providers while running under the SecurityManager he specifies you must use in the rules. SecurityManager.checkSecurityAccess(java.lang.String) is called if you try and mess with the Providers.

You're right, looks like a Timing Attack might be the only solution that satisfies the spirit of the test.

Re: Java Puzzle: Square Root

#54

Post by mcgin » Wed, Mar 20, 2013, 8:19 AM UTC

Presumably something from the java.lang.instrument package will allow you to solve this

Re: Java Puzzle: Square Root

#55

Post by asabil » Wed, Mar 20, 2013, 10:58 AM UTC

Maybe read /proc/self/maps and /proc/self/mem and try to locate the BigInteger value in the JVM heap?

Re: Java Puzzle: Square Root

#56

Post by mtpettyp » Wed, Mar 20, 2013, 6:24 PM UTC

wisesascha wrote: post #35

is using the ASM library not a legitimate way or would that violate the rules in some way?

I read "Solve the problem in a single separate .java file which compiles and runs with JDK 6 or 7." to mean that the entire solution has to be in one Java file.

Re: Java Puzzle: Square Root

#57

Post by mtpettyp » Wed, Mar 20, 2013, 7:42 PM UTC

uvdiv wrote: post #28

Force a race condition on the variable `root'. if (n.divide(root).equals(root)) { Try to set it to 2^20001 on the first funcall and 0 on the second.

BigInteger is immutable so this won't work

Re: Java Puzzle: Square Root

#58

Post by [deleted] » Thu, Mar 21, 2013, 12:48 AM UTC

IvyMike wrote: post #27

I'm surprised nobody's given the obvious algorithm yet: while(i Before anyone complains, this algorithm is correct and does not break any of the rules as far as I can tell. :) I think the timing attack is probably what he's really looking for. Edit: as mattvanhorn pointed out, answer() is void, but that's ok... changed to a "constant time" algorithm. :)

[deleted]

Re: Java Puzzle: Square Root

#59

Post by harryh » Thu, Mar 21, 2013, 1:56 AM UTC

cromwellian wrote: post #6

Consider that SecureRandom is really a facade around multiple providers that can plug in varying implementations. :)

If that's really the answer they are looking for then it's a stupid question.

Trying to write a timing attack sounds much more interesting.

Re: Java Puzzle: Square Root

#60

Post by nire » Thu, Mar 21, 2013, 10:33 PM UTC

mattvanhorn wrote: post #38

IvyMike wrote: post #27

I'm surprised nobody's given the obvious algorithm yet: while(i Before anyone complains, this algorithm is correct and does not break any of the rules as far as I can tell. :) I think the timing attack is probably what he's really looking for. Edit: as mattvanhorn pointed out, answer() is void, but that's ok... changed to a "constant time" algorithm. :)

answer() has a void return, although I suppose you might be able to watch System.out to see if it worked.

Yup, just set a new PrintStream(new ByteArrayOutputStream()) in System.setOut() and you're good.