Это началось как редактирование ответа fgrieu, но оно было очень длинным, поэтому я решил опубликовать его как отдельный ответ.
Я согласен со всем, что fgrieu написал в своем ответе
Я процитирую здесь ответ fgrieu, чтобы сделать больший акцент:
Единственное близкое к надежному решение для выполнения с постоянным временем на языке высокого уровня без указания целевой среды: Убедитесь, что путь выполнения кода и шаблоны доступа к памяти не зависят от данных..
Если мы не рассматриваем шаблоны доступа к памяти, поскольку это не входит в объем вопроса. Цитата может Только теоретически достигается с постоянным временем доступа к памяти и постоянным временем выполнения каждой инструкции. Конечно, это связано с дополнительными тактовыми циклами и дополнительным доступом к памяти.
Паттерны доступа к памяти относятся к другому типу атаки по побочному каналу, который требует, чтобы Oblivious Random Access Memory (ORAM) была защищена от атак по побочному каналу.
Если функция_1 и функция_2 имеют постоянное время и занимают одинаковое время
время вычислить их, такое ветвление все еще уязвимо для
атаки по сторонним каналам?
Чаще всего да, если/иначе уязвим для атаки по времени, потому что при использовании оператора if/else можно легко ожидать от компилятора или среды выполнения выполнения ветки. В любом случае вы обычно стараетесь избегать этого.
Выбор функции для вызова по индексу массива, как, например, в ответе mentallurg на Python, не так уж и плох, он имеет постоянное время доступа к памяти, а код, который выполняется Python для вызова функции, является постоянным временем.
Прежде чем я начну.
- В случае доступа к памяти обратите внимание, что, поскольку нас интересуют атаки по времени, нас интересует только доступ к памяти. время и нет узоры это может привести к утечке информации, потому что это немного усложнит нашу ситуацию.
- Я рассматриваю кеши только в конце, а сейчас мы не рассматриваем кеши, так как всем известно, что кеши ЦП могут быть худшим кошмаром криптографа в таких ситуациях.
- Я предполагаю, что каждая инструкция, которая не включает доступ к памяти, требует для выполнения одних и тех же тактов.
Анализ ответа менталурга:
Возьмем, к примеру, этот простой код Python.
защита f1(x):
вернуть х + 1
защита f2(x):
вернуть х + 2
деф основной():
функции = [f1, f2]
x = int(input("Введите значение:"))
я = х% 2
результат = функции [i] (x)
печать (результат)
если __name__=='__main__':
главный()
Это компилируется в следующий байт-код Python (вывод pycdas для .pyc, скомпилированный с помощью Python 3.10):
[Код]
Имя файла: test.py
Имя объекта: основной
Количество аргументов: 0
Pos Only Arg Count: 0
KW Только число аргументов: 0
Местные жители: 4
Размер стека: 3
Флаги: 0x00000043 (CO_OPTIMIZED | CO_NEWLOCALS | CO_NOFREE)
[Имена]
'f1'
'f2'
'инт'
'вход'
'Распечатать'
[Имена Вар]
«функции»
'Икс'
'я'
'результат'
[Бесплатные вары]
[Переменные ячейки]
[Константы]
Никто
'Введите значение:'
2
[Разборка]
0 ЗАГРУЗКА_ГЛОБАЛЬНАЯ 0: f1
2 ЗАГРУЗКА_ГЛОБАЛЬНАЯ 1: f2
4 СПИСОК_СТРУКТУР 2
6 STORE_FAST 0: функции
8 LOAD_GLOBAL 2: целое число
10 LOAD_GLOBAL 3: ввод
12 LOAD_CONST 1: «Введите значение:»
14 ВЫЗОВ_ФУНКЦИЯ 1
16 ВЫЗОВ_ФУНКЦИЯ 1
18 STORE_FAST 1: х
20 LOAD_FAST 1: х
22 ПОСТОЯННАЯ НАГРУЗКА 2: 2
24 БИНАРНЫЙ_МОДУЛЬ
26 STORE_FAST 2: я
28 LOAD_FAST 0: функции
30 LOAD_FAST 2: я
32 BINARY_SUBSCR
34 LOAD_FAST 1: х
36 ВЫЗОВ_ФУНКЦИЯ 1
38 STORE_FAST 3: результат
40 LOAD_GLOBAL 4: печать
42 LOAD_FAST 3: результат
44 ВЫЗОВ_ФУНКЦИЯ 1
46 ПОП_ТОП
48 LOAD_CONST 0: Нет
50 ВОЗВРАТ_ЗНАЧЕНИЕ
Поиск и выполнение строки результат = функции [i] (x) делается из строк байты 26-36. Давайте посмотрим на BINARY_SUBSCR оператор. Он принимает два аргумента, список (это может быть словарь или кортеж, но давайте не будем заострять на этом внимание) в качестве первого и индекс из стека (те, которые были ранее загружены с помощью LOAD_FAST), возвращает значение по этому индексу и уменьшает стек на 1.
Теперь давайте посмотрим, как BINARY_SUBSCR реализован на CPython. Реализацию можно найти здесь и заключается в следующем:
ЦЕЛЬ(BINARY_SUBSCR) {
ПРОГНОЗ (BINARY_SUBSCR);
PyObject *sub = POP();
PyObject *container = TOP();
PyObject *res = PyObject_GetItem (контейнер, суб);
Py_DECREF (контейнер);
Py_DECREF(суб);
SET_TOP (разрешение);
если (рез == NULL)
ошибка перехода;
JUMPBY(INLINE_CACHE_ENTRIES_BINARY_SUBSCR);
ОТПРАВЛЯТЬ();
}
Теперь весь анализ можно сосредоточить на PyObject *res = PyObject_GetItem (контейнер, суб);. Это общий метод, и до тех пор, пока элемент не будет получен, в промежуточном звене вызываются различные другие методы. Конечно, мы можем ожидать $O(1)$ сложность. Осталось это проверить. В конце PyList_GetItem называется следующее:
ПиОбъект *
PyList_GetItem (PyObject * op, Py_ssize_t i)
{
если (!PyList_Check(оп)) {
PyErr_BadInternalCall();
вернуть НУЛЬ;
}
если (!valid_index(i, Py_SIZE(op))) {
_Py_DECLARE_STR(list_err, "индекс списка вне допустимого диапазона");
PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));
вернуть НУЛЬ;
}
return ((PyListObject *)op) -> ob_item[i];
}
Как мы видим в последней строке. Оно имеет $O(1)$ сложность.Конечно, из-за сложности языков высокого уровня они никогда не используются на практике для таких приложений. Итак, давайте попробуем этот код на языке более низкого уровня, таком как C, чтобы увидеть, что он производит.
#include <stdio.h>
интервал f1 (целый х) {
вернуть х + 1;
}
интервал f2 (целый х) {
вернуть х + 2;
}
интервал основной () {
интервал х;
сканф("%d", &x);
int (*(функции[2]))(int) = {f1, f2};
инт я;
я = х %2;
результат int = functions[i](x);
}
Это x86_64 от Godbolt с последним GCC без оптимизаций:
f1:
дополнение $сп,$сп,-8
SW $fp,4($сп)
двигаться $fp,$сп
SW $4,8($фп)
лв $2,8($фп)
нет
дополнение $2,$2,1
двигаться $сп,$фп
лв $fp,4($сп)
дополнение $сп,$сп,8
младший $ 31
нет
f2:
дополнение $сп,$сп,-8
SW $fp,4($сп)
двигаться $fp,$сп
SW $4,8($фп)
лв $2,8($фп)
нет
дополнение $2,$2,2
двигаться $сп,$фп
лв $fp,4($сп)
дополнение $сп,$сп,8
младший $ 31
нет
$LC0:
.ascii "%d\000"
главный:
добавить $сп,$сп,-56
ув $31,52($сп)
ув $fp, 48 ($сп)
переместить $фп,$сп
добавить $2,$fp, 32
переместить $5,2 доллара
Луи $2,%привет($LC0)
добавить $4,$2,%10($ЛК0)
Джал __isoc99_scanf
нет
Луи $2,%привет(f1)
добавить $2,$2,%10(f1)
ув $2,36($fp)
Луи $2,%привет(f2)
дополнение $2,$2,%10(f2)
SW $2,40($фп)
лв $3,32($фп)
ли $2,-2147483648 # 0xffffffff80000000
ори $2,$2,0x1
и $2,$3,$2
бгез $2,$L6
нет
дополнение $2,$2,-1
ли $3,-2 # 0xfffffffffffffffe
или $2,$2,$3
дополнение $2,$2,1
$L6:
ув $2,24($fp)
лв $2,24($fp)
нет
продать $2,$2,2
добавить $3,$fp, 24
добавить $2,$3,$2
лв $2,12($2)
лв $3,32($фп)
нет
двигаться $4,$3
двигаться $25,$2
Джалр $ 25
нет
SW $2,28($фп)
двигаться $2,$0
двигаться $сп,$фп
лв $31,52($сп)
лв $fp,48($сп)
дополнение $сп,$сп, 56
младший $ 31
нет
Более конкретно нас интересуют эти инструкции, в которых делается вызов соответствующей функции:
лв $2,24($фп)
нет
еще $2,$2,2
дополнение $3,$фп, 24
адду $2,$3,2 доллара
лв $2,12($2)
лв $3,32($fp)
нет
переместить $4,$3
переместить $25,2 доллара
Джалр $25
нет
SW $2,28($фп)
двигаться $2,$0
Как мы видим, никаких ветвей не делается, кроме как от jalr, которые вызывают соответствующую функцию.
Анализ ответа фгрие
Конечно, легко видеть, что это постоянное время:
#include <stdio.h>
интервал f1 (целый х) {
вернуть х + 1;
}
интервал f2 (целый х) {
вернуть х + 2;
}
интервал основной () {
интервал х;
сканф("%d", &x);
int (*(функции[2]))(int) = {f1, f2};
интервал м = -(х&1); // переменная маски m должна иметь тот же тип, что и x
х = (функция_1 (х) и м) | (функция_2(х) и ~м);
печать (х);
}
Опять Голдболт с теми же опциями:
f1:
толчок рбп
мов рбп, рсп
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
добавить еакс, 1
поп рбп
рет
f2:
толчок рбп
мов рбп, рсп
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
добавить еакс, 2
поп рбп
рет
.LC0:
.строка "%d"
главный:
толчок рбп
мов рбп, рсп
толчок rbx
саб рсп, 40
леа ракс, [rbp-24]
мов рси, ракс
mov edi, OFFSET FLAT:.LC0
движение акс, 0
позвони __isoc99_scanf
mov QWORD PTR [rbp-48], OFFSET FLAT:f1
mov QWORD PTR [rbp-40], OFFSET FLAT:f2
mov eax, DWORD PTR [rbp-24]
и акс, 1
отрицательный акс
mov DWORD PTR [rbp-20], eax
mov eax, DWORD PTR [rbp-24]
мов эди, эакс
движение акс, 0
вызов функции_1
и eax, DWORD PTR [rbp-20]
мов ebx, eax
mov eax, DWORD PTR [rbp-24]
мов эди, эакс
движение акс, 0
вызов функции_2
mov edx, DWORD PTR [rbp-20]
не edx
и еакс, эдкс
или eax, ebx
mov DWORD PTR [rbp-24], eax
mov eax, DWORD PTR [rbp-24]
cdqe
мов рди, ракс
движение акс, 0
вызов printf
движение акс, 0
mov rbx, QWORD PTR [rbp-8]
оставлять
рет
Мы сосредоточимся на этой части, где выполняется присваивание m и встроенное ветвление:
mov eax, DWORD PTR [rbp-24]
и акс, 1
отрицательный акс
mov DWORD PTR [rbp-20], шт.
mov eax, DWORD PTR [rbp-24]
мов эди, эакс
движение акс, 0
вызов функции_1
и eax, DWORD PTR [rbp-20]
мов ebx, eax
mov eax, DWORD PTR [rbp-24]
мов эди, эакс
движение акс, 0
вызов функции_2
mov edx, DWORD PTR [rbp-20]
не edx
и еакс, эдкс
или eax, ebx
mov DWORD PTR [rbp-24], eax
На самом деле мы можем видеть выполнение с постоянным временем.
Итак, в чем разница между этими решениями:
Оба удовлетворяют мерам антивременного анализа, но второй также скрывает шаблоны доступа. Он всегда вызывает обе функции. Поскольку мы пока не упоминали кеши, при наличии кешей второй кажется более защищенным от атак по сторонним каналам по времени.Просто потому, что для выполнения инструкции код обеих функций должен находиться в кеше. Во втором случае кэшируется только тот, который вызывается. Если предположить, что за какой-то конкретный период времени f1 был вызван и f2 был вытеснен из кеша, будет разница во времени, когда f2 будет вызван снова.
Для других решений и дальнейшего чтения по этому вопросу вы можете рассмотреть [1] и [2].
