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?

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? — Stultuske, May 13 '15 at 09:09
I only want to prove if I can guess that SECRET_WORD, and console show us that we get the same String. — juanhl, May 13 '15 at 09:11
Put differently: Does multiple timnigs of `secret.equals(...)` reveal enough information about `secret` to conclude what it contains? — aioobe, May 13 '15 at 09:13
Related: http://stackoverflow.com/questions/7191112/how-do-i-implement-a-string-comparison-in-java-that-takes-the-same-amount-of-tim and http://security.stackexchange.com/questions/50900/are-there-any-working-proof-of-concept-string-comparison-timing-attacks — aioobe, May 13 '15 at 09:15
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` — aioobe, May 13 '15 at 09:18
Yes, when I also run your code on my machine, I get the wrong length(`8`) and the wrong content out of it (`21966839`). — Naman Gala, May 13 '15 at 09:24
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. — juanhl, May 13 '15 at 09:44
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. — Tom Hawtin - tackline, May 13 '15 at 13:38

score 5 · Answer 1 · answered May 13 '15 at 09:17

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.

String prediction through comparisons

1 Answers1