Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Java Puzzle: Square Root

corner.squareup.com

Post reply on HN
Print view View original

41–50 of 61 posts

Re: Java Puzzle: Square Root

#41

Post by raylu »

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.

Nobody said you had to stop after reaching that line ;)

Re: Java Puzzle: Square Root

#42

Post by cromwellian »

raylu wrote: post #40
cromwellian wrote: post #6

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

SquareRoot.n is static, so it runs before any code in your main().

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

#45

Post by raylu »

tantalor wrote: post #36

I'd start by trying to create an evil subclass of BigInteger, as it is not a final class.

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

#46

Post by web007 »

raylu wrote: post #44
web007 wrote: post #43

Subclass BigInteger, and override equals() on your subclass to "return true;"?

equals() isn't being called on your class; it's being called on the result of n.divide()

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

#47

Post by spiralpolitik »

mattvanhorn wrote: post #37
cromwellian wrote: post #6

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

...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.

Re: Java Puzzle: Square Root

#48

Post by lancefisher »

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=2%5E10%2C000+%2F+109+na...

Re: Java Puzzle: Square Root

#49

Post by IvyMike »

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…

I must dryly point out that this does not invalidate the correctness of the algorithm.

Re: Java Puzzle: Square Root

#50

Post by raylu »

web007 wrote: post #46
raylu wrote: post #44

Earlier quoted context omitted.

equals() isn't being called on your class; it's being called on the result of n.divide()

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…

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.
Post reply on HN