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 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 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 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.
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 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 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 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 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.
Trying to write a timing attack sounds much more interesting.
SecurityManager.checkSecurityAccess(java.lang.String) is called if you try and mess with the Providers.
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. :)
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...
http://gkoberger.github.com/stacksort/
Immutability is your friend. Use it or lose it.
I suspect that doing something with the random seed is more what the author had in mind, though.
edit: Yeah… just ignore this and look at the other answers ;)
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?
I'm not sure anyone will bother writing the timing attack since he apparently gives out no prize.
I'm familiar with Java, but not so familiar that I can state with authority that such a thing is impossible.