Строковый прогноз через сравнения

Question

Сегодня я проснулся и подумал, можно ли предсказать строки, только анализируя время между каждым сравнением.

Я создаю элементарный класс (я знаю, что это не лучший алгоритм, но он работает для меня), чтобы попытаться доказать это, и ответ - да.

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;
    }

}

Это консольное шоу:

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

Этот код может предсказать мне String с вероятностью успеха 90%, тогда я думаю, что хороший алгоритм может быть проблемой.

Может ли эта проблема иметь последствия для безопасности?

Answer 1

Да, такая проблема может иметь последствия для безопасности. Это называется атакой по времени и широко известно в криптографии. Обычно конфиденциальные данные сравниваются с использованием разных алгоритмов, например, все символы сравниваются до конца независимо от того, была ли найдена разница. Однако следует принять меры предосторожности, потому что умные JIT-компиляторы могут оптимизировать ваш код, чтобы он по-прежнему оставался уязвимым.