Криптография .NET, предотвращая временную атаку

Я просматривал сайт crackstation.net и наткнулся на этот код, который был прокомментирован следующим образом:

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

 private static bool SlowEquals(byte[] a, byte[] b)
    {
        uint diff = (uint)a.Length ^ (uint)b.Length;
        for (int i = 0; i < a.Length && i < b.Length; i++)
            diff |= (uint)(a[i] ^ b[i]);
        return diff == 0;
    }

Может кто-нибудь объяснить, как работает эта функция, почему нам нужно преобразовать длину в целое число без знака и как этот метод позволяет избежать временной атаки? Что делает линия diff |= (uint)(a[i] ^ b[i]);?

Ответ 1

Это устанавливает diff в зависимости от того, существует ли разница между a и b.

Он избегает временной атаки, всегда прогуливаясь по всему короткому из двух из a и b, независимо от того, существует ли рассогласование раньше или нет.

diff |= (uint)(a[i] ^ (uint)b[i]) берет эксклюзивный или байт a с соответствующим байтом b. Это будет 0, если два байта одинаковы или не равны нулю, если они разные. Тогда or, что с diff.

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

Следовательно, конечный результат в diff будет отличным от нуля, если между соответствующими байтами a и b будет найдено различие, а 0 только если все байты (и длины) a и b равны.

Однако, в отличие от типичного сравнения, это всегда будет выполнять цикл, пока все байты в более коротком из двух входов не будут сравниваться с байтами в другом. Типичное сравнение было бы раньше, когда цикл был бы сломан, как только обнаружено несоответствие:

bool equal(byte a[], byte b[]) { 
    if (a.length() != b.length())
        return false;

    for (int i=0; i<a.length(); i++)
       if (a[i] != b[i])
           return false;
    return true;
}

При этом, исходя из количества времени, затраченного на возврат false, мы можем узнать (по крайней мере, приблизительное) количество байтов, совпадающих между a и b. Пусть говорят, что начальный тест длины занимает 10 нс, и каждая итерация цикла занимает еще 10 нс. Исходя из этого, если он возвращает false за 50 нс, мы можем быстро предположить, что у нас есть правильная длина, и первые четыре байта a и b соответствуют.

Даже не зная точного количества времени, мы можем по-прежнему использовать разницу во времени для определения правильной строки. Мы начинаем с строки длиной 1 и увеличиваем этот байт за раз, пока не увидим увеличение времени, затраченного на возврат false. Затем мы запускаем все возможные значения в первом байте, пока не увидим другое увеличение, что указывает на то, что он выполнил еще одну итерацию цикла. Продолжайте то же самое для последовательных байтов, пока все байты не совпадут, и мы получим возврат true.

Оригинал по-прежнему открыт для немного временной атаки - хотя мы не можем легко определить содержание правильной строки на основе хронометража, мы можем, по крайней мере, найти длину строки в зависимости от времени. Поскольку он сравнивается только с короткими из двух строк, мы можем начинать с строки длиной 1, затем 2, затем 3 и так далее, пока время не станет стабильным. Пока время увеличивается, наша предлагаемая строка короче, чем правильная строка. Когда мы даем ему более длинные строки, но время остается постоянным, мы знаем, что наша строка длиннее правильной строки. Правильная длина строки будет самой короткой, которая проведет эту максимальную продолжительность для тестирования.

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

Ответ 2

эта версия продолжается для длины ввода "а"

    private static bool SlowEquals(byte[] a, byte[] b)
    {
        uint diff = (uint)a.Length ^ (uint)b.Length;
        byte[] c = new byte[] { 0 };
        for (int i = 0; i < a.Length; i++)
            diff |= (uint)(GetElem(a, i, c, 0) ^ GetElem(b, i, c, 0));
        return diff == 0;
    }

    private static byte GetElem(byte[] x, int i, byte[] c, int i0)
    {
        bool ok = (i < x.Length);
        return (ok ? x : c)[ok ? i : i0];
    }