Контекст
Функция BN_consttime_swap в OpenSSL Красота. В этом фрагменте condition вычисляется как 0 или (BN_ULONG)-1:
#define BN_CONSTTIME_SWAP(ind) \
do { \
t = (a->d[ind] ^ b->d[ind]) & condition; \
a->d[ind] ^= t; \
b->d[ind] ^= t; \
} while (0)
…
BN_CONSTTIME_SWAP(9);
…
BN_CONSTTIME_SWAP(8);
…
BN_CONSTTIME_SWAP(7);
Цель состоит в том, чтобы гарантировать, что операции с большими числами более высокого уровня занимают постоянное время, эта функция либо меняет местами два больших числа, либо оставляет их на месте в постоянное время. Когда он оставляет их на месте, он фактически считывает каждое слово каждого бигнума, вычисляет новое слово, идентичное старому слову, и записывает этот результат обратно в исходное место.
Предполагается, что это займет столько же времени, как если бы бигнумы были эффективно заменены местами.
В этом вопросе я предполагаю современную широко распространенную архитектуру, подобную описанной Агнером Фогом в его руководствах по оптимизации. . Также предполагается прямой перевод кода C на ассемблер (без того, чтобы компилятор C отменял усилия программиста).
Вопрос
Я пытаюсь понять, характеризует ли вышеприведенная конструкция как выполнение с постоянным временем "наилучших усилий" или как идеальное выполнение с постоянным временем.
В частности, меня беспокоит сценарий, когда bignum a уже находится в кеше данных L1, когда вызывается функция BN_consttime_swap, а код сразу после возврата функции начинает работать с bignum a сразу. На современном процессоре одновременно может выполняться достаточно инструкций, чтобы копия не была технически завершена, когда используется bignum a. Механизм, позволяющий инструкциям после вызова BN_consttime_swap работать с a, является предположением о зависимости от памяти. Давайте предположим наивное предположение о зависимости от памяти ради аргумента.
Кажется, вопрос сводится к следующему:
Когда процессор, наконец, обнаруживает, что код после BN_consttime_swap считывается из памяти, которая, вопреки предположениям, была записана внутрь функции, отменяет ли он спекулятивное выполнение, как только обнаруживает, что адрес был записан, или позволяет ли он себе сохранить его, когда обнаруживает, что записанное значение совпадает со значением, которое уже было?
В первом случае BN_consttime_swap выглядит так, как будто реализует идеальное постоянное время. Во втором случае это только постоянное время наилучшего усилия: если большие числа не были заменены, выполнение кода, следующего за вызовом BN_consttime_swap, будет заметно быстрее, чем если бы они были заменены.
Даже во втором случае это выглядит так, как будто это может быть исправлено в обозримом будущем (пока процессоры остаются достаточно наивными) путем записи для каждого слова каждого из двух больших чисел значения, отличного от двух возможных конечных значений. значения перед повторной записью старого значения или нового значения. В какой-то момент может потребоваться использование квалификатора типа volatile, чтобы обычный компилятор не переоптимизировал последовательность, но это все еще кажется возможным.
ПРИМЕЧАНИЕ. Я знаю об переадресации хранилища, но только ярлык. Это не мешает чтению выполняться до записи, которая должна быть после него. И в некоторых случаях он терпит неудачу, хотя этого и не следовало ожидать в данном случае.
BN_consttime_swapбыл добавлен в марте 2014 г. в ответ на Восстановление одноразовых номеров OpenSSL ECDSA с использованием побочного канала FLUSH+RELOAD Cache Атака. Вот коммит с комментариями. - person jww schedule 20.03.2015