Create a gist now

Instantly share code, notes, and snippets.

@frohoff /SquareRootHack.java Secret
Last active Dec 15, 2015

What would you like to do?
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.
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment