Эффективна ли маскировка для предотвращения атак по побочным каналам?

Question

Эффективна ли маскировка для предотвращения атак по побочным каналам?

Я работаю с криптографическим кодом с открытым ключом bigint. Безопасно ли использовать побитовое маскирование, чтобы гарантировать, что время расчета и адреса памяти, к которым обращаются, не зависят от значений данных?

Является ли этот метод уязвимым для атак по побочным каналам, основанных на синхронизации команд, мощности, радиочастотном излучении или других вещах, о которых я не знаю? (Для справки мне известны такие методы, как ослепление RSA, лестница ЕС Монтгомери, очистка кэша и тому подобное.)

Пример простого кода (C / C ++):

uint a = (...), b = (...);
if (a < b)
a += b;

Теперь переведено для использования маскировки с постоянным временем:

uint a = (...), b = (...);
uint mask = -(uint)(a < b);
a = ((a + b) & mask) | (a & ~mask);

Обратите внимание, что a < b 0 или 1, а маска 0x00000000 или 0xFFFFFFFF.

Точно так же для операции высокого уровня (C ++):

Integer x = (...);
if (x.isFoo())
x.doBar();

Является ли следующий приемлемый безопасный перевод?

Integer x = (...);
uint mask = -(uint)x.isFoo();  // Assume this is constant-time
Integer y(x);                  // Copy constructor
y.doBar();                     // Assume this is constant-time
x.replace(y, mask);            // Assume this uses masking

5

c++constant-time cryptography

Решение

Другие решения

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

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

2

Источник

Accepted Answer

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

В частности, давайте посмотрим на ваш первый пример:

uint a = (...), b = (...);
uint mask = -(uint)(a < b);
a = ((a + b) & mask) | (a & ~mask);

Я вижу два несколько правдоподобных способа, которыми это может не работать в постоянное время:

Сравнение a < b может или не может занять постоянное время, в зависимости от компилятора (и процессора). Если он скомпилирован для простой битовой манипуляции, он может быть постоянным; если он скомпилирован для использования условного перехода, он может и не быть.
При высоких уровнях оптимизации вполне возможно, что слишком умный компилятор может обнаружить происходящее (скажем, разделив код на два пути на основе сравнения и оптимизировав их по отдельности, прежде чем объединить их обратно), и «оптимизировать» его обратно в не постоянный временной код, который мы пытались избежать.

(Конечно, также возможно, что достаточно умный компилятор может оптимизировать наивный, казалось бы, непостоянный временной код в операцию с постоянным временем, если он считает, что это будет более эффективно!)

Один из возможных способов избежать первой проблемы — заменить сравнение явной битовой манипуляцией, например:

uint32_t a = (...), b = (...);
uint32_t mask = -((a - b) >> 31);
a = ((a + b) & mask) | (a & ~mask);

Тем не менее, обратите внимание, что это эквивалентно вашему исходному коду, только если мы можем быть уверены, что a а также b отличаются менее чем на 2³¹. Если это не гарантировано, нам нужно преобразовать переменные в более длинный тип перед вычитанием, например:

uint32_t mask = (uint32_t)(( (uint64_t)a - (uint64_t)b ) >> 32);

Все это говорит о том, что даже это не является надежной задачей, так как компилятор все же может решить превратить этот код во что-то, что не является постоянным временем. (Например, 64-разрядное вычитание на 32-разрядном ЦП может потенциально занять переменное время в зависимости от того, есть ли заимствование или нет — это именно то, что мы пытаемся скрыть, здесь.)

В общем, единственный способ сделать конечно что такие утечки времени не происходят, чтобы:

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

Очевидно, вам также нужно будет делать это отдельно для каждой комбинации компилятора и целевой платформы, которую вы хотите поддерживать.

3