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

Question

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

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

---

Пример простого кода (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 

Answer 1

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

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

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

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

1. The сравнение a < b может или не потребовать постоянного времени, в зависимости от компилятора (и процессора). Если он скомпилирован для простой манипуляции с битами, он может быть постоянным временем; если он скомпилирован для использования условного перехода, этого вполне может не быть.

2. На высоких уровнях оптимизации возможно, что слишком умный компилятор может обнаружить, что происходит (скажем, разбивая код на два пути на основе сравнения и оптимизируя их отдельно перед их объединением) и «оптимизировать», это обратно в непостоянный код времени, который мы пытались избежать.

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

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

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-битном ЦП может потенциально занять переменное время в зависимости от того, есть ли заимствование или нет —, что именно мы пытаемся скрыть здесь.)

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

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

2. действительно тестирует код, чтобы убедиться, что он это делает, ind eed, выполняйте одно и то же время для запуска независимо от входных данных.

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

Answer 2

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

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