Атака по времени с PHP

Я пытаюсь произвести атаку по времени на PHP и использую PHP 7.1 со следующим скриптом:

<?php
    $find = "hello";
    $length = array_combine(range(1, 10), array_fill(1, 10, 0));
    for ($i = 0; $i < 1000000; $i++) {
        for ($j = 1; $j <= 10; $j++) {
            $testValue = str_repeat('a', $j);
            $start = microtime(true);
            if ($find === $testValue) {
                // Do nothing
            }
            $end = microtime(true);
            $length[$j] += $end - $start;
        }
    }

    arsort($length);
    $length = key($length);
    var_dump($length . " found");

    $found = '';
    $alphabet = array_combine(range('a', 'z'), array_fill(1, 26, 0));
    for ($len = 0; $len < $length; $len++) {
        $currentIteration = $alphabet;
        $filler = str_repeat('a', $length - $len - 1);
        for ($i = 0; $i < 1000000; $i++) {
            foreach ($currentIteration as $letter => $time) {
                $testValue = $found . $letter . $filler;
                $start = microtime(true);
                if ($find === $testValue) {
                    // Do nothing
                }
                $end = microtime(true);
                $currentIteration[$letter] += $end - $start;
            }
        }
        arsort($currentIteration);
        $found .= key($currentIteration);
    }
    var_dump($found);

Это поиск слова со следующими ограничениями

  • только от А до Я
  • до 10 символов

Сценарий находит длину слова без каких-либо проблем, но значение слова никогда не возвращается, как ожидалось, при атаке по времени.

Есть ли что-то, что я делаю неправильно?

Скрипт перебирает длины, правильно определяет длину. Затем он перебирает каждую букву (a-z) и проверяет их скорость. Теоретически «хаааа» должно быть немного медленнее, чем «ааааа», потому что первая буква — «h». Затем он продолжается для каждой из пяти букв.

Бег дает что-то вроде «брха», что явно неправильно (каждый раз по-разному, но всегда неправильно).


person exussum    schedule 14.01.2018    source источник
comment
Можете ли вы уточнить, где вы ожидаете результат?   -  person Martin    schedule 14.01.2018
comment
Последний результат var_dump($found); должен показать привет - я обновлю вопрос   -  person exussum    schedule 14.01.2018
comment
Запуск вашего кода дает противоречивые результаты, он выбрасывает 5 случайных букв. Это ошибка, которую вы получаете?   -  person Martin    schedule 14.01.2018
comment
зачем использовать 1000000 ?   -  person Martin    schedule 14.01.2018
comment
Просто чтобы выбрать довольно большое количество, оно может быть меньше, я не проверял, что оно работает достаточно быстро на моей машине, да, 5 случайных букв означают, что он нашел правильную длину (5), но не конкретные буквы. Случайные буквы — самые медленные буквы, найденные mircotime.   -  person exussum    schedule 14.01.2018
comment
Если я понимаю, что вы делаете правильно, то я сомневаюсь, что вы можете сделать это с помощью атаки по времени, если сравнение разных символов занимает одинаковое время (что, я думаю, так и есть)   -  person apokryfos    schedule 14.01.2018
comment
Найденный добавляется к $found .= key($currentIteration); после упорядочения массива по наибольшему времени. Реализация повторяется буква за буквой. php.net/manual/en/function.hash-equals.php следует использовать для атаки по времени ту же версию (вместо ===)   -  person exussum    schedule 14.01.2018
comment
hash_equals безопасен для атаки по времени, однако это не означает, что === всегда небезопасен для атаки по времени. Я почти уверен, что при определенных обстоятельствах === может безопасно атаковать по времени, и вы можете столкнуться с этими обстоятельствами во втором цикле.   -  person apokryfos    schedule 14.01.2018
comment
Иногда я получал ожидаемые результаты от вашего скрипта, иногда нет. Я изменил его, чтобы он принимал аргументы $find = $argv[1];, и дважды запустил это в командной строке: for s in hello marcell stack overflow; do php php-timing-attack.php $s; done. Я получил следующие результаты: string(7) "9 found" и string(9) "zgmdykrbk", string(7) "7 found" и string(7) "marcell", string(7) "5 found" и string(5) "stack", string(7) "5 found" и string(5) "uusov" (1-е место).   -  person marcell    schedule 15.01.2018
comment
И для второго запуска: string(7) "5 found" и string(5) "hello", string(7) "7 found" и string(7) "marcell", string(7) "5 found" и string(5) "stack", string(7) "8 found" и string(8) "overflow".   -  person marcell    schedule 15.01.2018
comment
@marcell, можете ли вы опубликовать код для этого? Я не понимаю, где близко   -  person exussum    schedule 15.01.2018
comment
@exussum Я только что изменил вторую строку: $find = "hello"; на $find = $argv[1];. Вот доказательство: хэш md5 исходного файла a75273828aee0c34668faa592c0a76ca и после указанной модификации: ecf5b5e18fab444fa7748cc8379dfbce. Я на macOs Sierra 10.12.6, php:PHP 7.0.26 (cli). Вам нужна другая информация?   -  person marcell    schedule 15.01.2018
comment
Интересно. Я использую Linux, и я не получаю ничего близкого к строке. Попробую другую ОС. Благодарю вас!   -  person exussum    schedule 15.01.2018
comment
Должен ли код быть таким, можно ли внести изменения? Или лучше сначала выяснить, что случилось?   -  person Pyr James    schedule 24.01.2018
comment
Изменения могут быть уверены. Если вы можете получить рабочую версию, мне будет очень интересно   -  person exussum    schedule 24.01.2018


Ответы (1)


Есть ли что-то, что я делаю неправильно?

Я так не думаю. Я попробовал ваш код, и я тоже, как и вы и другие люди, которые пробовали в комментариях, получаю совершенно случайные результаты для второго цикла. Первый (длина) в основном надежен, хотя и не в 100% случаев. Между прочим, предложенный трюк $argv[1] на самом деле не улучшил согласованность результатов, и, честно говоря, я действительно не понимаю, почему это должно быть так.

Поскольку мне было любопытно, я взглянул на исходный код PHP 7.1. Функция идентификации строки (zend_is_identical) выглядит следующим образом:

    case IS_STRING:
        return (Z_STR_P(op1) == Z_STR_P(op2) ||
            (Z_STRLEN_P(op1) == Z_STRLEN_P(op2) &&
             memcmp(Z_STRVAL_P(op1), Z_STRVAL_P(op2), Z_STRLEN_P(op1)) == 0));

Теперь легко понять, почему первая атака по времени на длину работает отлично. Если длина отличается, то memcmp никогда не вызывается и, следовательно, возвращается намного быстрее. Разница легко заметна даже без слишком большого количества итераций.

Как только вы определили длину, во втором цикле вы в основном пытаетесь атаковать базовый memcmp. Проблема в том, что разница во времени сильно зависит от:

  1. реализация memcmp
  2. текущая нагрузка и мешающие процессы
  3. архитектура машины.

Я рекомендую эту статью под названием "Сравнение memcmp для атак по времени" для получения более подробной информации. объяснения. Они сделали гораздо более точный тест и все еще не смогли получить четкой заметной разницы во времени. Я просто процитирую заключение статьи:

В заключение, это сильно зависит от обстоятельств, если memcmp() подвергается атаке по времени.

person rlanvin    schedule 23.01.2018
comment
Просто чтобы добавить немного к этому ответу, не совсем уверен, что это может быть полезно, скорость php, вероятно, увеличится из-за его системы байт-кода. Таким образом, он, вероятно, кэширует код, поэтому иногда в зависимости от того, какие расширения вы установили, ваша скорость может увеличиться. И, как мы знаем, реклама php7 заключается в его повышенной скорости. - person Ezekiel; 23.01.2018