Java Puzzle: Square Root — Solution

Written by Wouter Coekaerts.

Here’s the solution to our square root puzzle.

Sherlock

Take another look at that code, and use your imagination. Imagine that you are the SquareRoot class. You have a square number written on a secret piece of paper in your pocket. Sherlock is interrogating you to figure out its square root. Whenever he makes a guess, you divide your number by that guess (integer division), and if the result is equal to that guess, you have to yell “Square root!”.

Suppose your number is 19,749,136, and the first guess for the square root is 20,000,000. You can quickly see that’s bigger, so 19,749,136/20,000,000 rounded down to an integer is just zero. So after a quick look at your number, you just give Sherlock a blank stare.

Next, he guesses 9,870,000. That’s way off again, what is he thinking? As any good java class, you still follow the procedure: calculate 19,749,136/9,870,000 rounded down. No? Ok then: imagine yourself going through the effort of calculating that it’s 2, so you keep quiet.

His guesses were way off for the square root, which is 4444 in case you’re wondering. But just by looking at how long you took to make those divisions, Sherlock now knows your number is probably bigger than 9,870,000 and smaller than 20,000,000. That’s a well known technique in the software security world: it’s a timing attack.

How to solve it

How does that apply to our code? SquareRoot.answer(root) calls BigInteger.divide, which calls MutableBigInteger.divide. That method avoids the slow calculation if root is bigger than or equal to the secret n. By measuring how long the call to answer takes, you know if your guess is higher or lower than n. With a binary search you can then find the exact number.

Things to consider in a practical solution:

• Call answer multiple times before measuring how long it took, because the time it takes to execute once is too short to measure reliably. The accuracy of System.nanoTime varies from system to system, but is usually not at all accurate up to the nanosecond.
• Combine multiple measurements to deal with noise caused by garbage collection or other processes.
• As for anything that involves timing in the JVM, take into account that it does just in time compilation: calculations will be slow at first, but speed up when often executed code get compiled and optimized. You can deal with that by first warming it up: execute the code enough times for it to get optimized before you start measuring. Or you can keep re-evaluating what constitutes a fast or a slow call to answer as things speed up.
• You don’t need a binary search to discover n and then a separate search for its square root. You can combine both in one search.

Show me the code

This gist is our example implementation of that. These people solved it using the timing attack: Matt Mastracci, Hugh Pyle, Ben Murphy, Larry Sanderson, Daniel Martin, Mike Nonemacher, Roy Liu, Chris Frohoff, David Scherba, Adam Hawthorne, Eran Medan, vpΔ, Peter Burka and Sergey Mkhitaryan. Congrats! We’ll contact you shortly to send you a small prize.

A lot of other submitted solutions in our judgment did not qualify, but were still interesting:

• You can change SecureRandom to be less random by replacing the security provider for secure random numbers, but the security manager will not allow that.
• By the time the brute force solution finishes, our sun and possibly the universe as we know it are long gone, so it is unlikely your computer will actually reach that point.

That tiny issue aside, it’s nice to know that you can use System.out.close() and System.out.checkError() to detect when you have found the root.

Practical application

This puzzle was deliberately setup with an easy to measure timing difference in BigInteger.divide. In the real world, much more subtle timing issues can be exploited, even remotely. A clear target of timing attacks is cryptography, but it is applicable in widely differentareas as well.

At Square, we pay close attention to issues like this, to ensure our products are as secure as they can be.

If you liked this challenge, keep an eye on our blog for more programming puzzles. Wouter Coekaerts *Follow the latest activity of Wouter Coekaerts on Medium to see their stories and recommends.*medium.com