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?

Algoid

I don't really understand what you are trying to do here ... anyway, what exactly is this snippet: if (SECRET_WORD.equals(str)) { } supposed to do? – Araarab

I only want to prove if I can guess that SECRET_WORD, and console show us that we get the same String. – Algoid

Put differently: Does multiple timnigs of secret.equals(...) reveal enough information about secret to conclude what it contains? – Pavla

Related: #7191612 and security.stackexchange.com/questions/50900/… – Pavla

When I run your code on my machine, I get the wrong length and the wrong content out of it. It says the secret is 0988 – Pavla

Yes, when I also run your code on my machine, I get the wrong length(8) and the wrong content out of it (21966839). – Creigh

I think the success or failure of the prediction depends on the machine used and the value of ITERS parameter, this code works for me 90% of the time. – Algoid

The standard way to compare two numerical arrays of the same length safe from timing attacks is: exclusive-or pairwise; or each of the results together. – Evidential

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.

Jacobine