News for hackers. Stuff that matters.
Re:Java Puzzle: Square Root by cromwellian on Tuesday March 19, 2013 @09:40PM (#5405018)
Consider that SecureRandom is really a facade around multiple providers that can plug in varying implementations. :)
Re:Java Puzzle: Square Root by somethingnew on Tuesday March 19, 2013 @09:49PM (#5405062)
How about this one? http://xkcd.com/221/
Re:Java Puzzle: Square Root by Jeremysr on Tuesday March 19, 2013 @10:01PM (#5405116)
Heh, not knowing Java very well, I scoured the BigInteger docs for quirks and loopholes, then gave up and found your comment. I guess "java.security.SecureRandom" sounded too impregnably secure to be worth looking into.
Re:Java Puzzle: Square Root by harryh on Wednesday March 20, 2013 @09:56PM (#5412267)
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 by raylu on Tuesday March 19, 2013 @11:14PM (#5405392)
SquareRoot.n is static, so it runs before any code in your main().
Re:Java Puzzle: Square Root by cromwellian on Tuesday March 19, 2013 @11:18PM (#5405404)
Java Service Providers (SPI) trigger before main() is run. You can create a SecureRandom() provider, add it to the classpath with SPI, removing other providers.
Re:Java Puzzle: Square Root by GhotiFish on Tuesday March 19, 2013 @09:46PM (#5405049)
ah ha! That might of being too big of a hint, good sir.
Re:Java Puzzle: Square Root by mattvanhorn on Tuesday March 19, 2013 @11:01PM (#5405337)
...and that you can remove all the existing ones and insert your own.
Re:Java Puzzle: Square Root by spiralpolitik on Tuesday March 19, 2013 @11:57PM (#5405547)
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.

Re:Java Puzzle: Square Root by cromwellian on Wednesday March 20, 2013 @02:06AM (#5405881)
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 by uvdiv on Tuesday March 19, 2013 @10:32PM (#5405236)
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.
Re:Java Puzzle: Square Root by mtpettyp on Wednesday March 20, 2013 @03:42PM (#5409673)
BigInteger is immutable so this won't work
Re:Java Puzzle: Square Root by uvdiv on Friday March 22, 2013 @10:03PM (#5426944)
You're right! Good catch.
Re:Java Puzzle: Square Root by powera on Tuesday March 19, 2013 @09:33PM (#5404978)
I'm not sure this is interesting. Unless I'm missing something, the question is "find what way of breaking the compartmentalization of the JVM we haven't forbidden in these English-language rules".
Re:Java Puzzle: Square Root by craigching on Tuesday March 19, 2013 @10:50PM (#5405298)
Yes, I believe you and cromwellian have hit upon the main point. Or, to be more succinct, "do you know about Java spi."
Re:Java Puzzle: Square Root by IvyMike on Tuesday March 19, 2013 @10:30PM (#5405234)
I'm surprised nobody's given the obvious algorithm yet: while(i < BigInt(2).pow(10000)) ++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. :)

Re:Java Puzzle: Square Root by lancefisher on Wednesday March 20, 2013 @12:05AM (#5405575)
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=2%5E10%2C000+%2F+109+na...

Re:Java Puzzle: Square Root by IvyMike on Wednesday March 20, 2013 @12:16AM (#5405608)
I must dryly point out that this does not invalidate the correctness of the algorithm.
Re:Java Puzzle: Square Root by IvyMike on Wednesday March 20, 2013 @12:33AM (#5405654)
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 by mattvanhorn on Tuesday March 19, 2013 @11:06PM (#5405356)
answer() has a void return, although I suppose you might be able to watch System.out to see if it worked.
Re:Java Puzzle: Square Root by raylu on Tuesday March 19, 2013 @11:15PM (#5405394)
Nobody said you had to stop after reaching that line ;)
Re:Java Puzzle: Square Root by nire on Thursday March 21, 2013 @06:33PM (#5419693)
Yup, just set a new PrintStream(new ByteArrayOutputStream()) in System.setOut() and you're good.
Re:Java Puzzle: Square Root by somethingnew on Tuesday March 19, 2013 @09:31PM (#5404968)
Someone should just modify the StackSort algorithm that was posted yesterday (made up by xkcd) to search for Square Root functions instead and run them.

http://gkoberger.github.com/stacksort/

Re:Java Puzzle: Square Root by sumzup on Tuesday March 19, 2013 @09:54PM (#5405081)
That won't work. The point here is that you don't have the number available.
Re:Java Puzzle: Square Root by itsdrewmiller on Wednesday March 20, 2013 @12:53AM (#5405725)
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 by asabil on Wednesday March 20, 2013 @06:58AM (#5406513)
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 by tantalor on Tuesday March 19, 2013 @10:53PM (#5405313)
I'd start by trying to create an evil subclass of BigInteger, as it is not a final class.
Re:Java Puzzle: Square Root by raylu on Tuesday March 19, 2013 @11:35PM (#5405468)
I've tried this but failed to create something that was evil enough to pass on .equals but benign enough that it didn't choke on .divide
Re:Java Puzzle: Square Root by wheaties on Tuesday March 19, 2013 @10:41PM (#5405275)
I hate to break it to you but "n" is not final. Hence, you can reassign any BigInteger to it. Why not just set n = 9 and the root = 3...

Immutability is your friend. Use it or lose it.

Re:Java Puzzle: Square Root by craigching on Tuesday March 19, 2013 @10:45PM (#5405286)
But n is also private, so you can't reassign it without using setAccessible or changing the security manager, both forbidden by the rules.
Re:Java Puzzle: Square Root by coolbrow on Tuesday March 19, 2013 @10:46PM (#5405289)
But "n" is private and the rules state the solution must be in a different class. Thus you can't simply reassign it.
Re:Java Puzzle: Square Root by tantalor on Tuesday March 19, 2013 @10:45PM (#5405287)
You can't assign anything to a private variable.
Re:Java Puzzle: Square Root by TallboyOne on Tuesday March 19, 2013 @09:46PM (#5405048)
Can someone explain what this is asking? I don't know java
Re:Java Puzzle: Square Root by Semaphor on Tuesday March 19, 2013 @09:54PM (#5405083)
There is a really big number you don't know. You should get the square root for it.
Re:Java Puzzle: Square Root by TallboyOne on Tuesday March 19, 2013 @09:56PM (#5405088)
So why are people talking about vulnerabilities and 'timing attacks' then? and how are you supposed to get the square root of a number you dont know..
Re:Java Puzzle: Square Root by craigching on Tuesday March 19, 2013 @10:00PM (#5405109)
You don't need to use timing attacks or other vulnerabilities. Others have pointed out how to do it, use SPI and provide your own implementation. The xkcd post is probably the best hint ;)
Re:Java Puzzle: Square Root by shardling on Tuesday March 19, 2013 @10:01PM (#5405113)
The private function divides the unknown square by another number you provide. It's possible that how long this division takes depends on just what the secret number is -- keeping track of this and carefully feeding it input might reveal the number. That's a timing attack. (This is something you really have to consider when designing cryptographic functions and other such hardcore stuff.)

I suspect that doing something with the random seed is more what the author had in mind, though.

Re:Java Puzzle: Square Root by Semaphor on Tuesday March 19, 2013 @10:00PM (#5405110)
From what I understand a timing attack on SecureRandom to find out which number it generated. But I might be wrong in which case I'm sure someone knowledgeable will give you a better answer:)

edit: Yeah… just ignore this and look at the other answers ;)

Re:Java Puzzle: Square Root by Eduard on Tuesday March 19, 2013 @10:07PM (#5405142)
1: Pause debugging session. 2: Look into SquareRoot.n
Re:Java Puzzle: Square Root by mingpan on Tuesday March 19, 2013 @09:31PM (#5404969)
Are they asking for a timing attack, then?
Re:Java Puzzle: Square Root by huherto on Tuesday March 19, 2013 @10:33PM (#5405243)
I think you can create a new instance of SecureRandom() that provides the same value that we are looking for.
Re:Java Puzzle: Square Root by doctorpangloss on Tuesday March 19, 2013 @10:27PM (#5405224)
Hint: Many pseudo-random number generators take the square of a seed value to advance to the next sequence.
Re:Java Puzzle: Square Root by mcgin on Wednesday March 20, 2013 @04:19AM (#5406120)
Presumably something from the java.lang.instrument package will allow you to solve this
Re:Java Puzzle: Square Root by web007 on Tuesday March 19, 2013 @11:31PM (#5405449)
Subclass BigInteger, and override equals() on your subclass to "return true;"?
Re:Java Puzzle: Square Root by raylu on Tuesday March 19, 2013 @11:34PM (#5405466)
equals() isn't being called on your class; it's being called on the result of n.divide()
Re:Java Puzzle: Square Root by web007 on Tuesday March 19, 2013 @11:55PM (#5405536)
I don't know Java, clearly, as I don't even know what to name a file that's going to do the override. Also, as mentioned elsewhere, SecureRandom seems the easier target as it's a pluggable interface for entropy providers.

That said, can't you override the equals() for your subtype? I'm talking about the implementation of BigInteger::equals(MyBigInt x), not MyBigInt::equals(BigInteger x). Or does that need to be done on BigInteger-proper, versus its subclass?

Re:Java Puzzle: Square Root by raylu on Wednesday March 20, 2013 @12:16AM (#5405609)
You can override the .equals() for your subtype but look at the check:

    if (n.divide(root).equals(root)) {
It never calls root.equals(). It calls .equals() on the result of the .divide(), which is a standard java.math.BigInteger.
Re:Java Puzzle: Square Root by jlebar on Tuesday March 19, 2013 @09:42PM (#5405030)
Use reflection to read n. Reflection lets you bypass |private|.
Re:Java Puzzle: Square Root by craigching on Tuesday March 19, 2013 @09:55PM (#5405084)
He specifically says you need to leave the security manager in place and you can't use setAccessbile() which you need to do with the default security manager.
Re:Java Puzzle: Square Root by GhotiFish on Tuesday March 19, 2013 @09:47PM (#5405052)
that should throw an exception with the security manager on. I think. I might of read the docs wrong.
Re:Java Puzzle: Square Root by jlebar on Tuesday March 19, 2013 @09:51PM (#5405068)
Ahh, I see.
Re:Java Puzzle: Square Root by wisesascha on Tuesday March 19, 2013 @10:51PM (#5405305)
is using the ASM library not a legitimate way or would that violate the rules in some way?
Re:Java Puzzle: Square Root by mtpettyp on Wednesday March 20, 2013 @02:24PM (#5409149)
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 by uribs on Tuesday March 19, 2013 @09:31PM (#5404973)
The only possibilities seem to be a timing attack, exploiting a bug or taking advantage of an implementation that puts the dividend value in the exception when dividing by zero.

I'm not sure anyone will bother writing the timing attack since he apparently gives out no prize.

Re:Java Puzzle: Square Root by ISL on Tuesday March 19, 2013 @10:02PM (#5405124)
Unless there's something in Java that allows you to manipulate private copies of private variables without access to the stored values.

I'm familiar with Java, but not so familiar that I can state with authority that such a thing is impossible.

Re:Java Puzzle: Square Root by martinced on Tuesday March 19, 2013 @10:15PM (#5405173)
Is this just like String that are actually mutable on most JVM implementations out there where the underlying char[] can be accessed using reflection?