Java Puzzle: Square Root (opens in new tab)

(corner.squareup.com)

50 pointscrazybob13y ago56 comments

56 comments

51 comments · 20 top-level

cromwellian13y ago· 8 in thread

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

somethingnew13y ago

How about this one? http://xkcd.com/221/

Jeremysr13y ago

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.

harryh13y ago

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.

raylu13y ago

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

cromwellian13y ago

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.

GhotiFish13y ago

ah ha! That might of being too big of a hint, good sir.

1 more reply

mattvanhorn13y ago

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

spiralpolitik13y ago

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.

1 more reply

IvyMike13y ago· 6 in thread

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

lancefisher13y ago

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

IvyMike13y ago

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

IvyMike13y ago

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.

mattvanhorn13y ago

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

raylu13y ago

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

nire13y ago

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

wheaties13y ago· 3 in thread

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.

craigching13y ago

But n is also private, so you can't reassign it without using setAccessible or changing the security manager, both forbidden by the rules.

coolbrow13y ago

But "n" is private and the rules state the solution must be in a different class. Thus you can't simply reassign it.

tantalor13y ago

You can't assign anything to a private variable.

jlebar13y ago· 3 in thread

Use reflection to read n. Reflection lets you bypass |private|.

craigching13y ago

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.

GhotiFish13y ago

that should throw an exception with the security manager on. I think. I might of read the docs wrong.

jlebar13y ago

Ahh, I see.

uvdiv13y ago· 2 in thread

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.

mtpettyp13y ago

BigInteger is immutable so this won't work

uvdiv13y ago

You're right! Good catch.

TallboyOne13y ago· 2 in thread

Can someone explain what this is asking? I don't know java

Semaphor13y ago

There is a really big number you don't know. You should get the square root for it.

TallboyOne13y ago

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

4 more replies

web00713y ago· 2 in thread

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

raylu13y ago

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

web00713y ago

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?

1 more reply

powera13y ago· 1 in thread

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

craigching13y ago

Yes, I believe you and cromwellian have hit upon the main point. Or, to be more succinct, "do you know about Java spi."

somethingnew13y ago· 1 in thread

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/

sumzup13y ago

That won't work. The point here is that you don't have the number available.

tantalor13y ago· 1 in thread

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

raylu13y ago

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

wisesascha13y ago· 1 in thread

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

mtpettyp13y ago

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.

uribs13y ago· 1 in thread

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.

ISL13y ago

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.

itsdrewmiller13y ago

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?

asabil13y ago

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

Eduard13y ago

1: Pause debugging session. 2: Look into SquareRoot.n

mingpan13y ago

Are they asking for a timing attack, then?

huherto13y ago

I think you can create a new instance of SecureRandom() that provides the same value that we are looking for.

doctorpangloss13y ago

Hint: Many pseudo-random number generators take the square of a seed value to advance to the next sequence.

mcgin13y ago

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

martinced13y ago

Is this just like String that are actually mutable on most JVM implementations out there where the underlying char[] can be accessed using reflection?

j / k navigate · click thread line to collapse

56 comments

51 comments · 20 top-level

cromwellian13y ago· 8 in thread

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

somethingnew13y ago

How about this one? http://xkcd.com/221/

Jeremysr13y ago

harryh13y ago

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.

raylu13y ago

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

cromwellian13y ago

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.

GhotiFish13y ago

ah ha! That might of being too big of a hint, good sir.

1 more reply

mattvanhorn13y ago

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

spiralpolitik13y ago

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.

1 more reply

IvyMike13y ago· 6 in thread

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

lancefisher13y ago

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

IvyMike13y ago

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

IvyMike13y ago

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.

mattvanhorn13y ago

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

raylu13y ago

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

nire13y ago

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

wheaties13y ago· 3 in thread

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.

craigching13y ago

But n is also private, so you can't reassign it without using setAccessible or changing the security manager, both forbidden by the rules.

coolbrow13y ago

But "n" is private and the rules state the solution must be in a different class. Thus you can't simply reassign it.

tantalor13y ago

You can't assign anything to a private variable.

jlebar13y ago· 3 in thread

Use reflection to read n. Reflection lets you bypass |private|.

craigching13y ago

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.

GhotiFish13y ago

that should throw an exception with the security manager on. I think. I might of read the docs wrong.

jlebar13y ago

Ahh, I see.

uvdiv13y ago· 2 in thread

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.

mtpettyp13y ago

BigInteger is immutable so this won't work

uvdiv13y ago

You're right! Good catch.

TallboyOne13y ago· 2 in thread

Can someone explain what this is asking? I don't know java

Semaphor13y ago

There is a really big number you don't know. You should get the square root for it.

TallboyOne13y ago

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

4 more replies

web00713y ago· 2 in thread

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

raylu13y ago

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

web00713y ago

1 more reply

powera13y ago· 1 in thread

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

craigching13y ago

Yes, I believe you and cromwellian have hit upon the main point. Or, to be more succinct, "do you know about Java spi."

somethingnew13y ago· 1 in thread

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/

sumzup13y ago

That won't work. The point here is that you don't have the number available.

tantalor13y ago· 1 in thread

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

raylu13y ago

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

wisesascha13y ago· 1 in thread

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

mtpettyp13y ago

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.

uribs13y ago· 1 in thread

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.

ISL13y ago

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.

itsdrewmiller13y ago

asabil13y ago

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

Eduard13y ago

1: Pause debugging session. 2: Look into SquareRoot.n

mingpan13y ago

Are they asking for a timing attack, then?

huherto13y ago

I think you can create a new instance of SecureRandom() that provides the same value that we are looking for.

doctorpangloss13y ago

Hint: Many pseudo-random number generators take the square of a seed value to advance to the next sequence.

mcgin13y ago

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

martinced13y ago

Is this just like String that are actually mutable on most JVM implementations out there where the underlying char[] can be accessed using reflection?

j / k navigate · click thread line to collapse