Binary search structured timing attack solution for http://corner.squareup.com/2013/03/puzzle-square-root.html. Usually runs in 3-10s after JVM warm-up on an unloaded Core2Duo 1.8GHz, but can take longer on a more loaded system due to recalculation of high-timing-jitter iterations.

SquareRootHack.java

package square;

import java.lang.management.ManagementFactory;
import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.TimeUnit;

public class SquareRootHack {
	private static final BigInteger UPPER_BOUND = new BigInteger("2").pow(SquareRoot.BITS);
	private static final BigInteger ONE = BigInteger.ONE;
	private static final BigInteger TWO = new BigInteger("2");
	private static final int WARM_UP_ITER = 10000;
	private static final int RESOL_ITER = 5;		
	private static final int TIMING_ITER = 2;
	private static final int SLOWDOWN_FACTOR = 1;
	
	public static void main(String[] args) throws Exception {
		warmJvm();
		System.out.println("finding square root");
		long time = getTime();
		long iter = 1;
		// iterate until we calculate the same answer twice to weed out errors from jitter
		Set<BigInteger> answers = new HashSet<BigInteger>();
		BigInteger answer = null;
		do {
			answer = findSquareRoot();
			iter++;
		} while (answers.add(answer)); // break if already in set
		time = getTime() - time;
		System.out.println("found it in " + iter + " iterations over " 
				+ TimeUnit.SECONDS.convert(time, TimeUnit.NANOSECONDS) + "s");
		System.out.println("the answer is: " + answer.bitLength() + " bits, " + answer);
		System.out.println("want proof? here you go: calling SquareRoot.answer()");
		SquareRoot.answer(answer);
	}

	static BigInteger findSquareRoot() { // iterative binary search over square-root space
		int iter = 1;
		BigInteger highGuess = UPPER_BOUND; // more than max mystery value
		BigInteger lowGuess = ONE;		
		//     highGuess - lowGuess > 1                           termination failsafe
		while (highGuess.subtract(lowGuess).compareTo(ONE) > 0 && iter < SquareRoot.BITS + 100) { 
			BigInteger midGuess = lowGuess.add(highGuess.subtract(lowGuess).divide(TWO));
			BigInteger squaredMidGuess = midGuess.pow(2); // square guess for comparison with n
			if (isGreaterOrEqual(squaredMidGuess)) { // fast => low < n < mid
				highGuess = midGuess;
			} else {                                 // slow => mid < n < high
				lowGuess = midGuess;
			}
			iter++;
		}
		// will likely end up with two candidates, find correct one
		BigInteger answer = isGreaterOrEqual(lowGuess) ? lowGuess :	highGuess;
		return answer;
	}

	// use timing info leak at MutableBigInteger.java:891-901 to compare values to SquareRoot.n
	private static boolean isGreaterOrEqual(BigInteger guess) {
		BigInteger definitelyHigher = guess.add(ONE);			
		Long minLessTime = Long.MAX_VALUE;
		Long minNewTime = Long.MAX_VALUE;
		// iterate several times and compare the best times for known and unknown comparisons
		for (int i = 0; i < TIMING_ITER; i++) {
			minLessTime = Math.min(timeDivide(guess, definitelyHigher),minLessTime); 
			minNewTime = Math.min(timeSquareRoot(guess), minNewTime);
		}			
		return minNewTime < SLOWDOWN_FACTOR * minLessTime;		
	}	
	
	// timing jitter settles down if we thoroughly warm the jvm
	private static void warmJvm() {
		for (int i = 0; i < WARM_UP_ITER; i++) {
			SquareRoot.answer(UPPER_BOUND);
			SquareRoot.answer(ONE);
		}
	}
	
	private static long timeSquareRoot(BigInteger bi) {
		long start = getTime();
		// iterate enough times to account for inadequate measurement resolution
		for (int i = 0; i < RESOL_ITER; i++)
			SquareRoot.answer(bi);
		return getTime() - start;
	}
	
	private static long timeDivide(BigInteger a, BigInteger b) {
		long start = getTime();
		// iterate enough times to account for inadequate measurement resolution
		for (int i = 0; i < RESOL_ITER; i++)
			a.divide(b);
		return getTime() - start;
	}

	// get best approximation of actual CPU time consumed
	private static long getTime() {
		return ManagementFactory.getThreadMXBean().getCurrentThreadUserTime();
	}	
}