Предотвращает ли спекуляция зависимость от памяти постоянное время BN_consttime_swap?
контекст
Функция 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);
Предполагается, что для обеспечения того, чтобы операции bignum более высокого уровня занимали постоянное время, эта функция либо заменяет два bignum, либо оставляет их на месте в постоянное время. Когда он оставляет их на месте, он фактически читает каждое слово каждого bignum, вычисляет новое слово, идентичное старому слову, и записывает результат обратно в исходное местоположение.
Предполагается, что это займет столько же времени, как если бы bignums были эффективно заменены.
В этом вопросе я предполагаю современную, широко распространенную архитектуру, подобную описанной Агнером Фогом в его руководствах по оптимизации. Также предполагается простая трансляция кода C в сборку (без компилятора C, который отменяет усилия программиста).
Вопрос
Я пытаюсь понять, характеризует ли приведенная выше конструкция как "наилучшее усилие" для выполнения в постоянном времени или как совершенное выполнение в постоянном времени.
В частности, меня беспокоит сценарий, в котором bignum a уже находится в кэше данных L1, когда функция BN_consttime_swap вызывается, и код сразу после возврата функции начинает работать с bignum a сразу. На современном процессоре одновременно может выполняться достаточное количество инструкций, чтобы копия не была технически закончена, когда bignum a используется. Механизм, позволяющий инструкции после вызова BN_consttime_swap работать на a является спекуляция зависимость от памяти. Давайте предположим наивные предположения о зависимости от памяти.
Вопрос сводится к следующему:
Когда процессор наконец обнаруживает, что код после BN_consttime_swap чтение из памяти, которая, вопреки предположениям, была записана внутри функции, отменяет ли она спекулятивное выполнение, как только обнаруживает, что адрес был записан, или позволяет себе сохранять его, когда обнаруживает, что значение что было написано так же, как значение, которое уже было там?
В первом случае BN_consttime_swap похоже, он реализует идеальное постоянное время. Во втором случае это только постоянное время наилучшего усилия: если bignums не были поменяны местами, выполнение кода, который идет после вызова BN_consttime_swap будет заметно быстрее, чем если бы они были поменяны местами.
Даже во втором случае это выглядит так, как будто это может быть исправлено в обозримом будущем (пока процессоры остаются достаточно наивными), для каждого слова каждого из двух чисел записывая значение, отличное от двух возможных окончательных значений. значения перед записью либо старого значения снова или нового значения. volatile Определитель типа может потребоваться в какой-то момент, чтобы обычный компилятор не слишком оптимизировал последовательность, но это все еще кажется возможным.
ПРИМЕЧАНИЕ. Я знаю о пересылке в магазин, но пересылка в магазин - это всего лишь ярлык. Это не препятствует выполнению чтения до записи, за которой он должен следовать. И в некоторых обстоятельствах это терпит неудачу, хотя никто не ожидал бы этого в этом случае.
3 ответа
Этот пост в блоге и комментарии, сделанные автором Генри по этому вопросу, следует рассматривать как авторитетные, как и следовало ожидать. Я воспроизведу последнее здесь для архива:
Я не думал, что случай перезаписи ячейки памяти с тем же значением имеет практическое применение. Я думаю, что ответ заключается в том, что в современных процессорах стоимость магазина не имеет значения, важен только адрес.
Здесь, в научных кругах, я слышал о двух подходах к устранению неоднозначности в памяти: на основе адресов или на основе значений. Насколько я знаю, все современные процессоры выполняют устранение неоднозначности на основе адресов.
Я думаю, что текущий микробенчмарк имеет некоторые доказательства того, что значение не имеет значения. Во многих случаях многократное сохранение одного и того же значения в одном и том же месте (особенно в случаях со смещением = 0). Они не были ненормально быстрыми.
Схемы на основе адреса используют очередь хранилища и очередь загрузки для отслеживания незавершенных операций с памятью. Загрузки проверяют очередь хранилища на совпадение адресов (должна ли эта загрузка выполнять пересылку из хранилища в загрузку вместо чтения из кэша?), В то время как хранилища проверяют очередь загрузки (не перекрыл ли это хранилище местоположение более поздней загрузки, которую я позволил выполнить рано?). Эти проверки полностью основаны на адресах (где хранилище и нагрузка столкнулись). Одним из преимуществ этой схемы является то, что она является довольно простым расширением поверх пересылки из хранилища в загрузку, поскольку там также используется поиск в очереди хранилищ.
Схемы, основанные на значениях, избавляют от ассоциативного поиска (т. Е. Быстрее, с меньшим энергопотреблением и т. Д.), Но требуют лучшего предиктора для пересылки из хранилища в загрузку (теперь вам нужно угадать, следует ли и куда пересылать, а не искать SQ). Эти схемы проверяют нарушения порядка (и неправильную пересылку) путем повторного выполнения нагрузок во время фиксации и проверки правильности их значений. В этих схемах, если у вас есть конфликтующее хранилище (или вы допустили какую-то другую ошибку), которое все равно привело к правильному значению результата, оно не будет обнаружено как нарушение порядка.
Могут ли будущие процессоры перейти на схемы, основанные на стоимости? Я подозреваю, что они могли бы. Они были предложены в середине 2000-х годов (?) Для уменьшения сложности аппаратного обеспечения памяти.
Также предполагается простая трансляция кода C в сборку (без компилятора C, который отменяет усилия программиста).
Я знаю, что это не суть вашего вопроса, и я знаю, что вы это знаете, но мне нужно разглагольствовать на минуту. Это даже не квалифицируется как попытка "наилучшего усилия" для обеспечения выполнения в постоянном времени. Компилятор имеет лицензию на проверку значения conditionи пропустить все это, если condition это ноль. Запутывая настройки condition делает это менее вероятным, но это не гарантия.
Предположительно, код с постоянным временем не должен быть написан на C, полная остановка. Даже если сегодня постоянное время на тестируемых компиляторах, умный компилятор придет и победит вас. Один из ваших пользователей будет использовать этот компилятор раньше вас, и они не будут знать о риске, которому вы их подвергали. Есть ровно три способа достижения постоянного времени, о которых я знаю: выделенное оборудование, сборка или DSL, который генерирует машинный код, плюс доказательство выполнения в постоянном времени.
Отбросим в сторону реальный вопрос об архитектуре: предполагая, что тупо наивный компилятор, этот код является постоянным временем в тех мархитах, с которыми я достаточно знаком, чтобы оценить вопрос, и я ожидаю, что в целом это будет так по одной простой причине: мощность. Я ожидаю, что проверка в очереди или кеше магазина того, соответствует ли хранимое значение значению, которое уже присутствует, и условное короткое замыкание магазина или предотвращение загрязнения строки кэша в каждом магазине потребляет больше энергии, чем было бы сэкономлено в том редком случае, когда вы получаете чтобы избежать какой-либо работы. Однако я не являюсь разработчиком ЦП и не берусь говорить от их имени, поэтому возьмите это с несколькими столовыми ложками соли и, пожалуйста, проконсультируйтесь с одной из них, прежде чем предположить, что это правда.
Идея, лежащая в основе реализации в постоянном времени, заключается не в том, чтобы фактически выполнять все в постоянное время. Этого никогда не произойдет на архитектуре, вышедшей из строя. Требование состоит в том, что никакая секретная информация не может быть раскрыта путем анализа времени Чтобы предотвратить это, есть два основных требования:
а) Не используйте ничего секретного в качестве условия остановки для цикла или в качестве предиката для ветви. Несоблюдение этого требования откроет вам атаку с предсказанием перехода https://eprint.iacr.org/2006/351.pdf
б) Не используйте ничего секретного в качестве индекса доступа к памяти. Это приводит к таймингу кеш-атак http://www.daemonology.net/papers/htt.pdf
Что касается вашего кода: если предположить, что ваш секрет - это "условие" и, возможно, содержимое a и b, то код является абсолютно постоянным временем в том смысле, что его выполнение не зависит от фактического содержимого a, b и условия. Конечно, расположение a и b в памяти будет влиять на время выполнения цикла, но не на содержание, которое является секретным. Это при условии, что, конечно, условие вычислялось в постоянном времени. Что касается оптимизации на C: компилятор может оптимизировать код только на основе информации, которую он знает. Если "условие" действительно является секретным, компилятор не сможет распознать его содержимое и оптимизировать. Если он может быть вычтен из вашего кода, то компилятор, скорее всего, выполнит оптимизацию для случая 0.