Безопасное равенство: почему неравенство все еще неизменно занимает меньше времени?

Question

У меня есть метод, который сравнивает два байтовых массива на равенство с основным предупреждением о том, что он не терпит неудачу и завершается рано, когда обнаруживает неравенство.По сути, этот код используется для сравнения токенов подделки межсайтовых запросов и предотвращения (насколько это возможно) возможности использовать время для взлома ключа.Хотелось бы найти ссылку на статью, в которой подробно обсуждается атака, но важно то, что у моего кода все еще есть статистически измеримое смещение для более быстрого возврата, если два байтовых массива равны - хотя это порядоклучше.Итак, без лишних слов, вот код:

public static bool SecureEquals(byte[] original, byte[] potential)
{
    // They should be the same size, but we don't want to throw an
    // exception if we are wrong.
    bool isEqual = original.Length == potential.Length;
    int maxLenth = Math.Max(original.Length, potential.Length);

    for(int i=0; i < maxLength; i++)
    {
        byte originalByte = (i < original.Length) ? original[i] : (byte)0;
        byte potentialByte = (i < potential.Length) ? potential[i] : (byte)0;

        isEqual = isEqual && (originalByte == potentialByte);
    }

    return isEqual;
}

Разница в средней синхронизации между равными и неравными токенами последовательно на 10-25 мс (в зависимости от циклов сбора мусора) короче для неравных токенов.Это именно то, чего я хочу избежать.Если бы относительные сроки были равны, или среднее время поменялось в зависимости от пробега, я был бы счастлив.Проблема в том, что мы постоянно бежим короче за неравные токены.Напротив, если бы мы остановили цикл на первом неравном токене, мы могли бы получить разницу в 80 раз.

Хотя эта проверка на равенство является существенным улучшением по сравнению с обычным рвением, она все еще не годитсядовольно.По сути, я не хочу, чтобы какой-либо последовательный результат для равенства или неравенства возвращался быстрее.Если бы я мог получить результаты в диапазоне, где циклы сбора мусора будут маскировать любое постоянное смещение, я буду счастлив.

У кого-нибудь есть подсказка, что вызывает смещение времени в сторону ускорения неравенства?Сначала я подумал, что это троичный оператор, возвращающий доступ к массиву или константе, если массивы были неравного размера.Проблема в том, что я все еще получаю это смещение, если два массива имеют одинаковый размер.

ПРИМЕЧАНИЕ. В соответствии с запросом, ссылки на статьи по Timing Attacks:

• http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf (официальный документ, ссылка на который есть в сообщении блога ниже)
• http://codahale.com/a-lesson-in-timing-attacks/ (рассказывает о сбое в библиотеке Java)
• http://en.wikipedia.org/wiki/Timing_attack (подробнеев общем, но не так полно)

Answer 1

Эта строка может вызывать проблему:

isEqual = isEqual && (originalByte == potentialByte);

Это не будет беспокоить при оценке подвыражения originalByte == potentialByte, если isEquals уже ложно. Вы не хотите короткого замыкания здесь, поэтому измените его на:

isEqual = isEqual & (originalByte == potentialByte);

РЕДАКТИРОВАТЬ: обратите внимание, что вы уже эффективно утечки информации о размере исходных данных - потому что он всегда будет работать в постоянное время, пока массив potential не превысит размер массива original, в этот момент время увеличится. Вероятно, довольно сложно этого избежать ... поэтому я бы выбрал подход «выбрасывать исключение, если они не подходящего размера», который явно признает это, эффективно.

РЕДАКТИРОВАТЬ: Просто чтобы перейти к идее, которую я включил в комментарии:

// Let's assume you'll never really need more than this
private static readonly byte[] LargeJunkArray = new byte[1024 * 32];

public static bool SecureEquals(byte[] original, byte[] potential)
{
    // Reveal that the original array will never be more than 32K.
    // This is unlikely to be particularly useful.
    if (potential.Length > LargeJunkArray.Length)
    {
        return false;
    }
    byte[] copy = new byte[potential.Length];
    int bytesFromOriginal = Math.Min(original.Length, copy.Length);
    // Always copy the same amount of data
    Array.Copy(original, 0, copy, 0, bytesFromOriginal);
    Array.Copy(LargeJunkArray, 0, copy, bytesFromOriginal,
               copy.Length - bytesFromOriginal);

    bool isEqual = original.Length == potential.Length;
    for(int i=0; i < copy.Length; i++)
    {
        isEqual = isEqual & (copy[i] == potential[i]);
    }

    return isEqual;
}

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

Answer 2

В случае, если .NET должен быть достаточно умным, чтобы оптимизировать это - вы пытались ввести переменную-счетчик, которая подсчитывает количество неравных символов и возвращает true, если и только если это число равно нулю? *

public static bool SecureEquals(byte[] original, byte[] potential)
{
    // They should be the same size, but we don't want to throw an
    // exception if we are wrong.
    int maxLength = Math.Max(original.Length, potential.Length);
    int equals = maxLength - Math.Min(original.Length, potential.Length);

    for(int i=0; i < maxLength; i++)
    {
        byte originalByte = (i < original.Length) ? original[i] : (byte)0;
        byte potentialByte = (i < potential.Length) ? potential[i] : (byte)0;

        equals += originalByte != potentialByte ? 1 : 0;
    }

    return equals == 0;
}

Answer 3

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

Что бы я сделал в этой ситуации, это встроил в метод таймер, чтобы он мог измерять собственную синхронизацию при наличии двух равных ключей. (Используйте класс Секундомер.) Он должен вычислить среднее и стандартное отклонение времени успеха и спрятать его в каком-то глобальном состоянии. Когда вы получите неравный ключ, вы можете измерить, сколько времени вам потребовалось, чтобы обнаружить неравный ключ, а затем восполнить разницу, вращая крутой цикл, пока не истечет соответствующее количество времени. Вы можете выбрать случайное время вращения в соответствии с нормальным распределением на основе среднего значения и стандартного отклонения, которое вы уже вычислили.

Приятной особенностью этого подхода является то, что теперь у вас есть общий механизм, который вы можете использовать повторно при победе над другими временными атаками, и смысл кода очевиден; никто не собирается приходить и пытаться оптимизировать его.

И, как и любой другой код «безопасности», перед его отправкой проверьте его у специалиста по безопасности.