-
-
Save frohoff/39d97a1cd65c626ef817 to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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