String prediction through comparisons

Question

Today I woke up and thought if it would be possible to predict Strings only analyzing the time between each comparison.

I create a rudimentary class (I know that it is not the best alghorithm, but it works for me) to try prove this, and the answer is yes.

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Test {

    public static final int iters = 1000000;
    public static final String SECRET_WORD = "85742";
    public static final char[] LETTERS = new char[] { '1', '2', '3', '4', '5',
            '6', '7', '8', '9', '0' };

    public static void main(String[] args) {
        int length = calculateLength();
        System.out.println("Secret word is " + SECRET_WORD
                + " with a real length of " + SECRET_WORD.length()
                + " and a calculate Length of " + length);
        prediceText(length);

    }

    private static String prediceText(int length) {
        StringBuilder sbMain = new StringBuilder(length);
        for (int i = 0; i < length; i++) {
            Map<Character, Double> map = map2();

            while (map.entrySet().size() > 1) {
                for (Entry<Character, Double> entry : map.entrySet()) {
                    String str = sbMain.toString() + entry.getKey();
                    while (str.length() < length) {
                        str += " ";
                    }
                    long[] diffs = new long[iters];
                    for (int j = 0; j < iters; j++) {
                        long timeInit = System.nanoTime();
                        if (SECRET_WORD.equals(str)) {
                        }
                        diffs[j] = System.nanoTime() - timeInit;
                    }

                    long total = 0;
                    for (long diff : diffs) {
                        total += diff;
                    }

                    entry.setValue((double) total / iters);
                }

                double min = Double.MAX_VALUE;
                char myChar = 'a';
                for (Entry<Character, Double> entry : map.entrySet()) {
                    if (entry.getValue() < min) {
                        myChar = entry.getKey();
                        min = entry.getValue();
                    }
                }
                System.out.print(".");
                map.remove(myChar);
            }

            sbMain.append(map.keySet().iterator().next());
            System.out.println("####### " + sbMain.toString() + " ######");

        }

        return sbMain.toString();
    }

    private static int calculateLength() {
        Map<Integer, Double> map = map();
        int iter = 0;
        while (map.entrySet().size() > 1) {
            for (Entry<Integer, Double> entry : map.entrySet()) {
                StringBuilder sb = new StringBuilder();
                while (sb.length() < entry.getKey()) {
                    sb.append("a");
                }
                String str = sb.toString();
                long[] diffs = new long[iters];
                for (int i = 0; i < iters; i++) {
                    long timeInit = System.nanoTime();
                    if (SECRET_WORD.equals(str)) {
                    }
                    diffs[i] = System.nanoTime() - timeInit;
                }

                long total = 0;
                for (long diff : diffs) {
                    total += diff;
                }

                entry.setValue((double) total / iters);
            }

            double min = Double.MAX_VALUE;
            int length = 0;
            for (Entry<Integer, Double> entry : map.entrySet()) {
                if (entry.getValue() < min) {
                    length = entry.getKey();
                    min = entry.getValue();
                }
            }
            System.out.print(".");

            iter++;
            map.remove(length);
        }

        return map.keySet().iterator().next();
    }

    private static Map<Integer, Double> map() {
        Map<Integer, Double> map = new HashMap<Integer, Double>();
        for (int i = 1; i < 21; i++) {
            map.put(i, (double) 0);
        }
        return map;
    }

    private static Map<Character, Double> map2() {
        Map<Character, Double> map = new HashMap<Character, Double>();
        for (char myChar : LETTERS) {
            map.put(myChar, (double) 0);
        }
        return map;
    }

}

This console show:

...................Secret word is 85742 with a real length of 5 and a calculate Length of 5
.........####### 8 ######
.........####### 85 ######
.........####### 857 ######
.........####### 8574 ######
.........####### 85742 ######

That code can predict for me the String with a success rate of 90%, then I think that a good algorithm can be a problem.

Could this issue have security implications?

Answer 1

Yes, such issue may have security implications. It's called timing attack and widely known in cryptography. Usually sensitive data is compared using different algorithms, e.g. all the symbols are compared till the end regardless whether the difference was found. However precautions should be taken, because smart JIT compilers can optimize your code so it still be vulnerable.